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

Onderzoeksoutput: Boek/rapportRapportAcademic

73 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.
Originele taal-2Engels
Aantal pagina's43
StatusGepubliceerd - 2016


Duik in de onderzoeksthema's van 'Optimal paths for variants of the 2D and 3D reeds-shepp car with applications in image analysis'. Samen vormen ze een unieke vingerafdruk.

Citeer dit