Abstract
We present a new flexible wavefront propagation algorithm for the boundary value problem for sub-Riemannian (SR) geodesics in the roto-translation group $SE(2) = \mathbb{R}^2 \rtimes S^1$ with a metric tensor depending on a smooth external cost $\mathcal{C}:SE(2) \to [\delta,1]$, $\delta>0$, computed from image data. The method consists of a first step where a SR-distance map is computed as a viscosity solution of a Hamilton-Jacobi-Bellman (HJB) system derived via Pontryagin's Maximum Principle (PMP). Subsequent backward integration, again relying on PMP, gives the SR-geodesics. For $\mathcal{C}=1$ we show that our method produces the global minimizers. Comparison with exact solutions shows a remarkable accuracy of the SR-spheres and the SR-geodesics. We present numerical computations of Maxwell points and cusp points, which we again verify for the uniform cost case $\mathcal{C}=1$. Regarding image analysis applications, tracking of elongated structures in retinal and synthetic images show that our line tracking generically deals with crossings. We show the benefits of including the sub-Riemannian geometry.
Introduction
Extracting salient curves from images—such as blood vessels in medical scans or roads in satellite imagery—is a fundamental task in computer vision. Traditional 2D Riemannian methods often struggle with two primary issues: crossings and shortcuts. When two structures intersect, 2D algorithms frequently jump between them. Furthermore, standard Euclidean distance metrics often favor non-physical shortcuts that ignore the natural curvature of the underlying structure.
This paper addresses these challenges by employing Sub-Riemannian (SR) geometry within the roto-translation group $SE(2)$. By "lifting" a 2D image into a 3D space of positions $(x, y)$ and orientations $\theta$, intersecting structures are disentangled into separate paths at different "heights" in the $\theta$ dimension, making them easily distinguishable.
Methodology: Lifting and Wavefront Propagation
The proposed framework follows a rigorous mathematical pipeline to find globally optimal paths (geodesics) that respect the physical constraints of elongated shapes.
1. Image Lifting
The 2D image is first transformed into a 3D orientation score using cake wavelets. This score provides a data-driven cost $\mathcal{C}(x, y, \theta)$ that guides the geodesic. The "lifting" process ensures that the tangent of the curve is always aligned with its orientation, a constraint known as "horizontality" in sub-Riemannian geometry. This effectively separates overlapping structures in the 3D space.
2. Solving the HJB Equation
The core of the method is solving a Hamilton-Jacobi-Bellman (HJB) system derived from Pontryagin’s Maximum Principle (PMP). The authors compute a distance map $W$ as a viscosity solution to this PDE using an iterative upwind finite difference scheme. This approach is superior to local "shooting" methods because it finds the global minimizer and correctly handles complex topological features like Maxwell sets—points where multiple shortest paths meet, creating "kinks" in the distance map.
3. Geodesic Back-tracking
Once the distance map is established, the optimal SR-geodesic is found by performing backward integration from the target point to the source, following the gradient of the value function $W$.
Key Results and Discussion
The algorithm was validated on both synthetic and real-world datasets. For the uniform cost case ($\mathcal{C}=1$), the numerical results showed exceptional agreement with known analytical solutions for SR-spheres and geodesics.
Robustness to Crossings and Cusps
In retinal image tracking, the SR framework successfully navigated complex vessel crossings where traditional methods failed by "jumping" vessels. The study also highlights the importance of "cusp awareness." In $SE(2)$, certain paths can project to 2D curves with sharp, non-physical points (cusps). The proposed PDE approach allows for the identification and avoidance of these regions, ensuring smooth, biologically plausible vessel tracks.
Conclusion
By integrating image data into a sub-Riemannian geometric framework, the authors provide a robust solution for tracking elongated structures. The use of a PDE-based wavefront propagation ensures global optimality and handles intersections naturally. Future work aims to improve computational efficiency through anisotropic fast marching and to extend the model to include a scale dimension for varying vessel thicknesses.
Summary updated