Geodesic Methods in Computer Vision and Graphics

Gabriel Peyré, Mickaël Péchaud, Laurent CohenHAL 2010 · OpenAlex

In the world of computer vision and graphics, we often need to find the "shortest path" between two points. If you’re working on a flat, empty plane, that’s a simple straight line. But what if you’re trying to track a blood vessel in a grainy 3D medical scan, or find the distance between two points on the wrinkled surface of a 3D-scanned statue? Suddenly, "straight" doesn't cut it.

This is where geodesic methods come in. In their comprehensive review, Geodesic Methods in Computer Vision and Graphics, Gabriel Peyré and his colleagues bridge the gap between abstract differential geometry and the practical algorithms that power modern shape analysis and image processing.

TL;DR

This paper provides a unified framework for computing geodesic distances on Riemannian manifolds, moving beyond simple Euclidean geometry. By defining local "cost" and "direction" rules (metrics), the authors show how to solve complex problems like image segmentation, optimal surface meshing, and bending-invariant shape recognition.

What Problem Does This Paper Address?

Standard geometry treats space as uniform. However, data in computer vision is rarely uniform. A "road" in a satellite image has a different "cost" to traverse than a "forest." Similarly, a 3D mesh of a human body has an intrinsic geometry that doesn't change just because the person moves their arm.

The challenge is two-fold:

  1. Modeling: How do we mathematically describe a space where the "cost" of moving depends on your location and your direction?
  2. Computation: How do we efficiently calculate the global shortest path across millions of pixels or triangles without it taking forever?

The authors tackle these by utilizing Riemannian manifolds—mathematical spaces equipped with a "metric tensor" at every point that defines local distances.

Methods

The paper centers on the Eikonal equation, a non-linear partial differential equation (PDE) that describes how a "distance front" propagates from a source.

Key Algorithms:

  • Fast Marching Algorithm (FMA): The star of the show. Think of it as Dijkstra’s algorithm but for continuous domains. It computes distances in $O(N \log N)$ time by propagating a front from known to unknown areas, ensuring that each point is visited only once.
  • Anisotropic Solvers: While standard FMA works for "isotropic" costs (where direction doesn't matter), the authors detail iterative schemes (like Gauss-Seidel) and modified FMA for "anisotropic" cases—where the path prefers to follow specific orientations, such as the flow of a texture or the direction of white matter fibers in the brain.
  • Farthest Point Sampling (FPS): A greedy strategy to distribute points evenly across a surface. By iteratively picking the point furthest from all existing samples (using geodesic distance), it creates a near-perfect "blue noise" distribution.

Datasets

As a foundational review paper, it doesn't introduce a single new benchmark. Instead, it demonstrates versatility across several domains:

  • Medical Imaging: 3D MRI and DTI scans for vessel extraction and brain connectivity.
  • Satellite Imagery: 2D images for road tracking.
  • 3D Mesh Libraries: Standard models like the Stanford Bunny, the David statue, and various animal shapes (elephants, camels) to test remeshing and shape correspondence.
  • Shape Databases: Libraries of 2D silhouettes (Fish, Hands, Tools) used to evaluate retrieval accuracy.

Key Insights and Ideas

  • The Metric is the Message: The "magic" isn't just in the solver, but in how you design the local metric. By setting the metric to be the inverse of image gradients, geodesics naturally "snap" to edges.
  • Bending Invariance via MDS: One of the most powerful ideas is using Multi-dimensional Scaling (MDS). By calculating all-pairs geodesic distances on a 3D surface and then "flattening" that data into a Euclidean space, you create a "canonical form." This form looks the same even if the original 3D shape is bent or articulated, making it a "holy grail" for non-rigid shape recognition.
  • Geodesic Delaunay Triangulation: The authors show that the classic Delaunay triangulation (used for meshing) can be extended to curved surfaces. This allows for "remeshing" complex objects into much simpler, higher-quality versions that follow the object's natural curvature.

Key Results

  • Efficiency: The Fast Marching method allows for near-instantaneous pathfinding on grids with millions of pixels.
  • Anisotropic Advantage: In medical imaging, anisotropic geodesics can track thin, branching structures (like capillaries) that isotropic methods often "leak" out of.
  • Compression: Using curvature-driven anisotropic meshing, the authors demonstrate that a 3D model can be represented with significantly fewer triangles (e.g., reducing a mesh from $10^6$ to $10^4$ vertices) while maintaining high visual fidelity.
  • Shape Retrieval: Geodesic "eccentricity" histograms (measuring how far points are from the center of a shape) proved highly robust for identifying objects in databases, even when those objects were deformed.

Limitations and Future Work

Despite the progress, the authors highlight several "open" frontiers:

  • Extreme Anisotropy: When a metric is very directional, the Fast Marching algorithm can lose accuracy or fail to converge. Developing "causality-consistent" solvers for these cases remains a challenge.
  • Real-time Constraints: While $O(N \log N)$ is fast, it’s still too slow for some real-time robotics or video game applications involving massive, dynamic environments.
  • High-Dimensional Scaling: Applying these methods to very high-dimensional data (beyond 3D) is computationally expensive and requires better landmark-based approximations.

This monograph remains a vital roadmap for anyone looking to move beyond "as the crow flies" and start navigating the complex, curved reality of digital data.

Summary updated

Abstract

This paper reviews both the theory and practice of the numerical computation of geodesic distances on Riemannian manifolds. The notion of Riemannian manifold allows one to define a local metric (a symmetric positive tensor field) that encodes the information about the problem one wishes to solve. This takes into account a local isotropic cost (whether some point should be avoided or not) and a local anisotropy (which direction should be preferred). Using this local tensor field, the geodesic distance is used to solve many problems of practical interest such as segmentation using geodesic balls and Voronoi regions, sampling points at regular geodesic distance or meshing a domain with geodesic Delaunay triangles. The shortest paths for this Riemannian distance, the so-called geodesics, are also important because they follow salient curvilinear structures in the domain. We show several applications of the numerical computation of geodesic distances and shortest paths to problems in surface and shape processing, in particular segmentation, sampling, meshing and comparison of shapes.
BibTeX
@inproceedings{peyre2010geodesic,
  author = {Gabriel Peyré and Mickaël Péchaud and Gabriel Peyré and Laurent Cohen},
  title = {{Geodesic Methods in Computer Vision and Graphics}},
  booktitle = {HAL},
  year = {2010},
}

Loading related content...

Figure