Multiresolution Density-Equalizing Transformation for Scatterplots

Area of Science:

• Computer Vision
• Data Visualization
• Scientific Computing

Background:

• Scatterplots are essential for data analysis but suffer from overplotting, obscuring patterns.
• Optimal Transport (OT) offers a mathematical solution for density equalization but faces computational and implementation challenges.
• Existing OT solvers are often slow, complex, and lack adaptability for specific constraints.

Purpose of the Study:

• To develop a scalable and efficient algorithm for scatterplot regularization.
• To achieve density equalization comparable to exact OT solvers while preserving data structure.
• To provide a flexible method adaptable to various constraints and applications.

Main Methods:

• A multiresolution algorithm constructs a displacement field by merging local $2 \times 2$ patch optimizations.
• The method iteratively refines a globally consistent mesh across multiple resolutions.
• Systematic evaluation of local solvers, interpolation, and scheduling strategies balances cost, distortion, and efficiency.
• An efficient GPU implementation processes millions of points at interactive rates.

Main Results:

• The algorithm significantly outperforms existing OT solvers in speed and scalability.
• Achieves enhanced data uniformity with minimal distortion, even with extreme density variations.
• Demonstrates versatility through applications in constrained regularization, scatterplot gridification, and image contrast enhancement.

Conclusions:

• The proposed method offers an efficient and adaptable solution for scatterplot regularization and density equalization.
• It provides a practical alternative to computationally expensive OT solvers for large-scale data visualization.
• The algorithm's flexibility and performance make it suitable for diverse applications in data analysis and image processing.