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: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
155 Downloads (Pure)

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 (Formula presented.) 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 (Formula presented.) 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 (Formula presented.) and brain connectivity measures from diffusion-weighted MRI data for the case (Formula presented.), 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.

Original languageEnglish
Pages (from-to)816-848
Number of pages33
JournalJournal of Mathematical Imaging and Vision
Volume60
Issue number6
DOIs
Publication statusPublished - 1 Jul 2018

Fingerprint

Optimal Path
image analysis
Image Analysis
Image analysis
Railroad cars
Fast Marching Method
Eikonal Equation
Finsler Metric
eikonal equation
Data-driven
Reverse
Gears
Local Controllability
Gradient Descent Method
Computer Applications
Model
retinal images
Penalization
Incomplete Data
costs

Bibliographical note

To appear in JMIV Special Issue

Keywords

  • Bifurcations
  • Fast-marching
  • Finsler geometry
  • Sub-Riemannian geometry
  • Tracking

Cite this

@article{d2819fc44404423cb5e90a4b24f98d5a,
title = "Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis",
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 (Formula presented.) 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 (Formula presented.) 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 (Formula presented.) and brain connectivity measures from diffusion-weighted MRI data for the case (Formula presented.), 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",
author = "R. Duits and S.P.L. Meesters and J.M. Mirebeau and Portegies, {J. M.}",
note = "To appear in JMIV Special Issue",
year = "2018",
month = "7",
day = "1",
doi = "10.1007/s10851-018-0795-z",
language = "English",
volume = "60",
pages = "816--848",
journal = "Journal of Mathematical Imaging and Vision",
issn = "0924-9907",
publisher = "Springer",
number = "6",

}

Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis. / Duits, R.; Meesters, S.P.L.; Mirebeau, J.M.; Portegies, J. M.

In: Journal of Mathematical Imaging and Vision, Vol. 60, No. 6, 01.07.2018, p. 816-848.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis

AU - Duits, R.

AU - Meesters, S.P.L.

AU - Mirebeau, J.M.

AU - Portegies, J. M.

N1 - To appear in JMIV Special Issue

PY - 2018/7/1

Y1 - 2018/7/1

N2 - 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 (Formula presented.) 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 (Formula presented.) 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 (Formula presented.) and brain connectivity measures from diffusion-weighted MRI data for the case (Formula presented.), 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.

AB - 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 (Formula presented.) 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 (Formula presented.) 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 (Formula presented.) and brain connectivity measures from diffusion-weighted MRI data for the case (Formula presented.), 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.

KW - Bifurcations

KW - Fast-marching

KW - Finsler geometry

KW - Sub-Riemannian geometry

KW - Tracking

UR - http://www.scopus.com/inward/record.url?scp=85042237027&partnerID=8YFLogxK

U2 - 10.1007/s10851-018-0795-z

DO - 10.1007/s10851-018-0795-z

M3 - Article

C2 - 31007388

VL - 60

SP - 816

EP - 848

JO - Journal of Mathematical Imaging and Vision

JF - Journal of Mathematical Imaging and Vision

SN - 0924-9907

IS - 6

ER -