Introduction
In computer vision and graphics, organizing spatial data based on local "flow" or directionality—known as anisotropy—is a fundamental challenge. Traditional methods often rely on Euclidean geometry, which assumes a uniform, straight-line distance between points. However, this approach frequently fails when dealing with complex curves or non-uniform textures where the underlying geometry is far from flat.
This paper introduces a framework for solving perceptual grouping and domain meshing by transitioning from standard Euclidean geometry to anisotropic Riemannian geometry. By utilizing the Fast Marching algorithm to compute geodesic distances based on local image features, the authors construct "smart" Voronoi diagrams and Delaunay complexes that naturally adhere to the flow of curves and textures.
Methodology
The core of the proposed approach is the Riemannian metric, where the distance between points is defined as a "geodesic"—the shortest path on a manifold.
Tensor Fields and Fast Marching
Local anisotropy is represented using a tensor field $H(x)$, a $2 \times 2$ matrix at every point defining the cost of movement in various directions. For images, this field is derived from the structure tensor, which captures edge and texture orientations. To make the computation of these distances efficient, the authors employ the Fast Marching (FM) algorithm to solve the Hamilton-Jacobi (Eikonal) equation. This allows for the generation of a distance map across the entire anisotropic domain in $O(n \log n)$ time.
Anisotropic Voronoi and Delaunay Structures
Unlike previous approximations, the authors define Voronoi cells based on true geodesic distances. This ensures that the cells remain connected, a critical property for building the dual Delaunay complex used in grouping and meshing. To handle noisy data, a heat diffusion process (Laplacian) is used to interpolate the tensor field from high-confidence areas (like edges) to the rest of the domain.
Key Applications and Results
The framework is evaluated on synthetic textures, standard graphics models like the Stanford Bunny, and noisy real-world edge data.
Perceptual Grouping
The shortest path in an anisotropic metric naturally follows the "flow" of a curve, mathematically encoding the Gestalt principle of good continuation. By ordering Delaunay edges by their geodesic length and applying topological constraints, the method successfully reconstructs complex, intersecting curves where Euclidean methods typically produce "short-circuit" errors.
Domain Meshing
For meshing, the algorithm uses a Delaunay refinement strategy. It iteratively adds Voronoi vertices that have poor "radius-to-edge" ratios relative to the local metric. This produces high-quality meshes where triangles are perfectly aligned with features like the medial axis. The number of points required to represent a domain can be precisely controlled by a quality parameter $\rho^*$.
Discussion and Limitations
A significant insight of this work is that using true geodesic distances via Fast Marching guarantees the connectivity of Voronoi cells. However, the method does have limitations. The Delaunay complex is only guaranteed to be a valid planar triangulation if the point sampling is sufficiently dense. Additionally, the current work is focused on 2D manifolds; extending this to 3D volumes would significantly increase computational complexity. Finally, the quality of the output remains sensitive to the initial design of the tensor field and diffusion parameters, which may require manual tuning for specific image types.
Summary updated