A PDE Approach to Data-Driven Sub-Riemannian Geodesics in SE(2)

Erik J. Bekkers, Remco Duits, Alexey Mashtakov, Gonzalo R. Sanguinetti

TL;DR

This paper introduces a novel PDE-based method for computing sub-Riemannian (SR) geodesics in the SE(2) group, which is crucial for understanding curves with position and orientation. Their approach uses a wavefront propagation algorithm to efficiently find these geodesics, even with complex, data-driven cost functions, offering a significant improvement over existing methods for applications like image analysis.

What Problem Does This Paper Address?

In computer vision and related fields, a common task is to find "optimal" curves within images, often by minimizing a length functional that's weighted by a cost function. This cost function typically reflects the saliency or importance of different image regions. A standard approach involves computing a geodesic distance map and then following its steepest descent. However, for tasks involving curves with both position and orientation, like tracking structures in images, the underlying geometry is more complex. The SE(2) group, which represents rotations and translations, is a more appropriate mathematical framework. Finding geodesics in this group, especially when the cost function is derived from image data and is not uniform, presents a significant challenge. Existing methods often struggle with complex geometries, non-uniform costs, and handling intersections or bifurcations in data. This paper aims to provide a robust and accurate method for computing these data-driven SR-geodesics in SE(2).

Methods

The core of the paper's contribution lies in a new PDE-based wavefront propagation algorithm. This method involves two main steps:

  1. SR-Distance Map Computation: They compute a sub-Riemannian (SR) distance map by solving a Hamilton-Jacobi-Bellman (HJB) system. This system is derived from Pontryagin's Maximum Principle (PMP) and is formulated as a boundary value problem (BVP) involving a sub-Riemannian Eikonal equation. The viscosity solution of this equation provides the SR-distance.
  2. Geodesic Computation: SR-geodesics are then obtained by backward integration (back-tracking) from a target point, again guided by PMP.

A key innovation is the use of an iterative procedure to solve the HJB-BVP. This involves solving a sequence of initial value problems (IVPs) using left-invariant finite differences and an upwind scheme. For non-uniform costs, they construct a cost function by lifting image data using oriented wavelets, specifically the real part of cake wavelets, to capture local orientation information.

Datasets

The paper uses synthetic data for verification and demonstrates its application on retinal images for vessel tracking.

  • Synthetic Data: Used for verifying the accuracy of SR-spheres and geodesics against known analytical solutions, particularly for the uniform cost case (C=1).
  • Retinal Images: Patches of retinal images are used to demonstrate the method's capability in vessel tracking, handling crossings, bifurcations, and low contrast.

Key Insights and Ideas

  • SE(2) as a Natural Framework: The paper strongly advocates for using the SE(2) group (rotations and translations) as the appropriate geometric space for problems involving curves with orientation, which is common in image analysis.
  • PDE-based Wavefront Propagation for SR-Geodesics: Shifting from traditional ODE-based methods to a PDE approach using viscosity solutions of HJB equations allows for a more robust and general treatment of SR-geodesics, especially with data-driven costs.
  • Disentangling Structures: The SE(2) framework naturally disentangles intersecting structures based on their orientations, which is crucial for correctly tracking complex patterns in images.
  • Data-Driven Cost Functions: The ability to incorporate non-uniform, data-derived cost functions (using image features like orientation scores) makes the method highly adaptable to real-world vision tasks.
  • Global Optimality for Uniform Cost: For the uniform cost case (C=1), the method is proven to yield globally optimal SR-geodesics, a significant theoretical guarantee.

Key Results

  • High Accuracy: The method demonstrates remarkable accuracy in computing SR-spheres and SR-geodesics, verified against exact solutions for the uniform cost case. Maximum absolute errors are shown to be small, especially with finer grid resolutions.
  • Handling Complex Geometries: The approach successfully handles crossings and bifurcations in vessel tracking applications, outperforming standard Riemannian methods.
  • Maxwell and Cusps: The method accurately computes Maxwell points and cusp surfaces, which are critical for understanding the geometry of SR-geodesics and the limitations of optimality.
  • Computational Efficiency: While not explicitly quantified in terms of speedup, the PDE-based iterative approach offers a viable computational alternative to shooting methods for solving the boundary value problem.

Limitations and Future Work

  • Computational Cost: While the method is effective, the numerical implementation involves solving a sequence of IVPs, which can be computationally intensive, especially for high-resolution images or complex SR-geometries.
  • Parameter Tuning: The cost function construction involves parameters (λ and p) that require careful tuning for optimal performance, particularly in low-contrast image regions.
  • Future Work: The authors suggest exploring fast marching methods for more efficient implementation and extending the framework to other Lie groups like SE(3) for applications such as diffusion tensor imaging (DTI). They also aim for fully automated vascular tree segmentation.

Summary updated

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 [δ,1]$, $δ>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.
BibTeX
@article{bekkers2015pde,
  author = {Erik J. Bekkers and Remco Duits and Alexey Mashtakov and Gonzalo R. Sanguinetti},
  title = {{A PDE Approach to Data-Driven Sub-Riemannian Geodesics in SE(2)}},
  journal = {SIAM J. Imaging Sci.},
  year = {2015},
  url = {https://openreview.net/forum?id=sSNDppcYRu},
}
Figure