Anisotropic Geodesics for Perceptual Grouping and Domain Meshing

Sébastien Bougleux, Gabriel Peyré, Laurent D. Cohen

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.

Comparison of geodesic paths across different metric domains, including Euclidean, shape-based, isotropic, anisotropic, and surface metrics.

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.

The effect of varying the anisotropy parameter $\alpha$ on the distance field and resulting geodesic paths. As $\alpha$ increases, the paths increasingly follow the local flow of the image.

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

Abstract

This paper shows how computational Riemannian manifold can be used to solve several problems in computer vision and graphics. Indeed, Voronoi segmentations and Delaunay graphs computed with geodesic distances are shaped according to the anisotropy of the metric. A careful design of a Riemannian manifold can thus help to solve some important difficulties in computer vision and graphics. The first contribution of this paper is thus a detailed exposition of Riemannian metrics as a tool for computer vision and graphics. The second contribution of this paper is the use of this new framework to solve two important problems in computer vision and graphics. The first problem studied is perceptual grouping which is a curve reconstruction problem where one should complete in a meaningful way a sparse set of curves. Our anisotropic grouping algorithm works over a Riemannian metric that propagates the direction of a sparse set of noisy incomplete curves over the whole domain. The proposed method prunes the Delaunay graph in order to
BibTeX
@inproceedings{bougleux2008anisotropic,
  author = {Sébastien Bougleux and Gabriel Peyré and Laurent D. Cohen},
  title = {{Anisotropic Geodesics for Perceptual Grouping and Domain Meshing}},
  booktitle = {European Conference on Computer Vision},
  year = {2008},
  doi = {10.1007/978-3-540-88688-4\_10},
}
Figure