Optimal paths for variants of the 2D and 3D reeds-shepp car with applications in image analysis

R. Duits, S.P.L. Meesters, J.-M. Mirebeau, J.M. Portegies

Research output: Book/ReportReportAcademic

99 Downloads (Pure)


We introduce a PDE-based approach for finding minimal paths for the Reeds-Shepp car. In our model we minimize a (data-driven) functional involving both curvature and length penalization, with several generalizations. Our approach encompasses the 2D and 3D variants of this model, state dependent costs, and the possibility of removing the reverse gear of the vehicle. The model without reverse gear resembles Dubins's car, but without imposing a constraint on the curvature.

We solve our model via eikonal equations on the manifold R^d ×S^{d−1} with respect to highly anisotropic Finsler functions, which approximate the singular (pseudo)-metrics underlying the model. This is achieved using a Fast-Marching method, based on specific discretization stencils which are adapted to the preferred directions of the metric and obey a generalized acuteness property. We justify our approach by convergence results. Our curve optimization model in R^d × S^{d−1} with data-driven cost allows to extract complex tubular structures from medical images and incomplete data due to occlusions or low contrast. Our work extends the results of Sanguinetti et al. on numerical sub-Riemannian eikonal equations and the Reeds-Shepp Car: we consider a 3D extension, and a new model without reverse gear which better handles bifurcations, relying on previous work by Mirebeau for the numerics.
The anisotropic fast-marching approach is optimal for efficiency with limited loss of accuracy, although the differences compared to exact solutions by Duits et al. do become noticeable.

Numerical experiments show the high potential of our method in two applications: retinal vessel tree extraction in 2D fundus images for the case d=2, and brain connectivity measures from diffusion weighted MRI-data for the case d=3, extending the work of Bekkers et al.
Original languageEnglish
Number of pages43
Publication statusPublished - 2016


  • Optimal control
  • Image Processing, Computer-Assisted
  • finsler geometry


Dive into the research topics of 'Optimal paths for variants of the 2D and 3D reeds-shepp car with applications in image analysis'. Together they form a unique fingerprint.

Cite this