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

doi:10.1007/s10851-018-0795-z

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

J Math Imaging Vis. 2018;60(6):816-848. doi: 10.1007/s10851-018-0795-z. Epub 2018 Feb 20.

Authors

R Duits^#¹, S P L Meesters^#¹, J-M Mirebeau^#², J M Portegies^#¹

Affiliations

¹ 1CASA, Eindhoven University of Technology, Eindhoven, The Netherlands.
² 2University Paris-Sud, CNRS, University Paris-Saclay, 91405 Orsay, France.

^# Contributed equally.

Abstract

We present a PDE-based approach for finding optimal 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 two- and three-dimensional variants of this model, state-dependent costs, and moreover, the possibility of removing the reverse gear of the vehicle. We prove both global and local controllability results of the models. Via eikonal equations on the manifold $R^{d} \times S^{d - 1}$ we compute distance maps w.r.t. highly anisotropic Finsler metrics, which approximate the singular (quasi)-distances underlying the model. This is achieved using a fast-marching (FM) method, building on Mirebeau (Numer Math 126(3):515-557, 2013; SIAM J Numer Anal 52(4):1573-1599, 2014). The FM method is based on specific discretization stencils which are adapted to the preferred directions of the Finsler metric and obey a generalized acuteness property. The shortest paths can be found with a gradient descent method on the distance map, which we formalize in a theorem. We justify the use of our approximating metrics by proving convergence results. Our curve optimization model in $R^{d} \times S^{d - 1}$ with data-driven cost allows to extract complex tubular structures from medical images, e.g., crossings, and incomplete data due to occlusions or low contrast. Our work extends the results of Sanguinetti et al. (Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications LNCS 9423, 2015) on numerical sub-Riemannian eikonal equations and the Reeds-Shepp car to 3D, with comparisons to exact solutions by Duits et al. (J Dyn Control Syst 22(4):771-805, 2016). Numerical experiments show the high potential of our method in two applications: vessel tracking in retinal 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. (SIAM J Imaging Sci 8(4):2740-2770, 2015). We demonstrate how the new model without reverse gear better handles bifurcations.

Keywords: Bifurcations; Fast-marching; Finsler geometry; Sub-Riemannian geometry; Tracking.