Optimal Paths for Variants of the 2D and 3D Reeds-Shepp Car with\n Applications in Image Analysis

Remco Duits, Stephan Meesters, Jean‐Marie Mirebeau, Jorg M. PortegiesarXiv 2016 · DOI · arXiv

TL;DR

This paper introduces a powerful PDE-based framework for finding the "shortest" paths for a car-like robot (the Reeds-Shepp car) in both 2D and 3D spaces. By lifting image data into a higher-dimensional position-plus-orientation space and solving anisotropic Eikonal equations, the authors provide a robust way to track complex tubular structures—like blood vessels and brain fibers—even when they cross, branch, or disappear in low-contrast regions.

Introduction: The Challenge of Tubular Structure Tracking

In medical image analysis, tracking thin, tube-like structures such as blood vessels, nerves, or white matter fibers is a major challenge. Traditional methods often suffer from the "leakage problem," where a tracking algorithm gets confused at a crossing and jumps onto the wrong path.

To solve this, researchers use models like the Reeds-Shepp car, which doesn't just care about the shortest distance between two points, but also the "cost" of turning (curvature). However, standard Reeds-Shepp models allow for a "reverse gear," leading to sharp "cusps" in the path that don't make sense for biological structures like blood vessels. This paper addresses the mathematical and numerical hurdles of extending these models to 3D and creating a "no-reverse-gear" variant that better mimics biological growth and branching.

Overview of the Reeds-Shepp car model lifted to position-orientation space for 2D and 3D image analysis.

Methods: Lifting and Eikonal PDEs

The authors treat pathfinding as a curve optimization problem on a manifold ($\mathbb{R}^d \times \mathbb{S}^{d-1}$), which represents every possible position and orientation.

  • Lifting to Higher Dimensions: By adding orientation as a coordinate, the "leakage" at crossings is mathematically impossible because two crossing vessels have different orientations at the same spatial point. In the lifted space, these paths are distinct and do not intersect.
  • Finsler Metrics: They define highly anisotropic Finsler metrics to approximate the singular distances of the Reeds-Shepp model. This allows them to penalize curvature and enforce "forward-only" motion.
  • Fast-Marching (FM) Algorithm: To solve the Hamilton-Jacobi-Bellman (Eikonal) equation efficiently, they use an advanced FM method. The "secret sauce" is the use of adaptive discretization stencils that align with the preferred directions of the metric, ensuring the algorithm remains stable and accurate despite extreme anisotropy.

Key Insights: Cusps vs. Keypoints

In the standard Reeds-Shepp model (with reverse gear), a car might perform a three-point turn to reach a target, creating a sharp "cusp." In the new "no-reverse" model, these are replaced by keypoints—locations where the path includes an "in-place rotation." This is a much more natural way to model bifurcations in vessels, where a branch might split off at a sharp angle.

Comparison of optimal paths with and without a reverse gear, illustrating the difference between cusps and keypoints.

Results and Applications

The paper evaluates the method on several types of data, demonstrating high numerical accuracy and robustness:

  • 2D Retinal Images: The "no-reverse" model proved superior for vessel tracking. While the standard model might create a non-physical cusp to reach a branch, the new model correctly identifies the branching point as a keypoint for rotation.
  • 3D Synthetic dMRI: In simulated brain data, the sub-Riemannian approach successfully tracked fibers through crossings and areas of high torsion where standard isotropic methods failed by taking "shortcuts" through empty space.

Conclusion

This PDE-based framework provides a robust, mathematically grounded solution for tracking complex structures in medical images. By incorporating orientation and removing the reverse gear, the model mimics biological patterns more closely. Future work will focus on scaling to real, noisy 3D dMRI datasets and exploring locally adaptive metrics to further improve tracking in highly tortuous regions.

Summary updated

Abstract

We present a PDE-based approach for finding optimal paths for the Reeds-Shepp\ncar. In our model we minimize a (data-driven) functional involving both\ncurvature and length penalization, with several generalizations. Our approach\nencompasses the two and three dimensional variants of this model, state\ndependent costs, and moreover, the possibility of removing the reverse gear of\nthe vehicle. We prove both global and local controllability results of the\nmodels.\n Via eikonal equations on the manifold $\\mathbb{R}^d \\times \\mathbb{S}^{d-1}$\nwe compute distance maps w.r.t. highly anisotropic Finsler metrics, which\napproximate the singular (quasi)-distances underlying the model. This is\nachieved using a Fast-Marching (FM) method, building on work by Mirebeau. The\nFM method is based on specific discretization stencils which are adapted to the\npreferred directions of the Finsler metric and obey a generalized acuteness\nproperty. The shortest paths can be found with a gradient descent method on the\ndistance map, which we formalize in a theorem. We justify the use of our\napproximating metrics by proving convergence results.\n Our curve optimization model in $\\mathbb{R}^{d} \\times \\mathbb{S}^{d-1}$ with\ndata-driven cost allows to extract complex tubular structures from medical\nimages, e.g. crossings, and incomplete data due to occlusions or low contrast.\nOur work extends the results of Sanguinetti et al. on numerical sub-Riemannian\neikonal equations and the Reeds-Shepp Car to 3D, with comparisons to exact\nsolutions by Duits et al.\n Numerical experiments show the high potential of our method in two\napplications: vessel tracking in retinal images for the case $d=2$, and brain\nconnectivity measures from diffusion weighted MRI-data for the case $d=3$,\nextending the work of Bekkers et al. We demonstrate how the new model without\nreverse gear better handles bifurcations.\n
BibTeX
@misc{duits2016optimal,
  author = {Remco Duits and Stephan Meesters and Jean‐Marie Mirebeau and Jorg M. Portegies},
  title = {{Optimal Paths for Variants of the 2D and 3D Reeds-Shepp Car with\textbackslash\{\}n Applications in Image Analysis}},
  year = {2016},
  eprint = {1612.06137},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1612.06137},
}
Figure