Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis. (English) Zbl 1398.65135
Summary: 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 \(\mathbb {R}^d \times {\mathbb {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 the third author [Numer. Math. 126, No. 3, 515–557 (2014; Zbl 1297.65074); SIAM J. Numer. Anal. 52, No. 4, 1573–1599 (2014; Zbl 1312.65172)]. 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 \(\mathbb {R}^{d} \times \mathbb {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 G. Sanguinetti et al. [“Sub-Riemannian fast marching in \(SE(2)\)”, Lect. Notes Comput. Sci. 9423, 366–374 (2015; doi:10.1007/978-3-319-25751-8_44)] on numerical sub-Riemannian eikonal equations and the Reeds-Shepp car to 3D, with comparisons to exact solutions by the first author et al. [J. Dyn. Control Syst. 22, No. 4, 771–805 (2016; Zbl 1364.53033)]. 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 E. J. Bekkers et al. [SIAM J. Imaging Sci. 8, No. 4, 2740–2770 (2015; Zbl 1336.58014)]. We demonstrate how the new model without reverse gear better handles bifurcations.
MSC:
| 65K10 | Numerical optimization and variational techniques |
References:
| [1] | Agrachev, A.A., Barilari, D., Boscain, U.: Introduction to Riemannian and sub-Riemannian geometry (2016). https://webusers.imj-prg.fr/ davide.barilari/2016-11-21-ABB.pdf · Zbl 1362.53001 |
| [2] | Agrachev, A.A., Sachkov, Y.L.: Control Theory from the Geometric Viewpoint. Encyclopaedia of Mathematical Sciences, vol. 87. Springer, Berlin (2004) · Zbl 1062.93001 · doi:10.1007/978-3-662-06404-7 |
| [3] | Arzela, C, Sulle funzioni di linee, Mem. Accad. Sci. lst. Bologna Cl. Sci. Fis. Mat., 5, 55-74, (1895) · JFM 26.0454.01 |
| [4] | Ascoli, G, Le curve limiti di una varieta data di curve, Atti della R. Accad. Dei Lincei Memorie della Cl. Sci. Fis. Mat. Nat., 18, 521-586, (1883) · JFM 16.0342.02 |
| [5] | Astola, L; Florack, LMJ, Finsler geometry on higher order tensor fields and applications to high angular resolution diffusion imaging, Int. J. Comput. Vis., 92, 325-336, (2011) · Zbl 1235.92031 · doi:10.1007/s11263-010-0377-z |
| [6] | Bao, D., Chern, S.-S., Shen, Z.: An Introduction to Riemann-Finsler Geometry. Graduate Texts in Mathematics. Springer, New York (2000) · Zbl 0954.53001 |
| [7] | Bardi, M., Capuzzo-Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Birkhäuser, Basel (1997) · Zbl 0890.49011 · doi:10.1007/978-0-8176-4755-1 |
| [8] | Bekkers, E; Duits, R; Mashtakov, A; Sanguinetti, G, A PDE approach to data-driven sub-Riemannian geodesics in SE(2), SIAM J. Imaging Sci., 8, 2740-2770, (2015) · Zbl 1336.58014 · doi:10.1137/15M1018460 |
| [9] | Bekkers, E.J., Duits, R., Mashtakov, A., Sachkov, Y.: Vessel tracking via sub-Riemannian geodesics on the projective line bundle. Geometric Science of Information, Volume 10589 in Lecture Notes in Computer Science, November (2017) · Zbl 1428.53040 |
| [10] | Boscain, U; Charlot, G; Rossi, F, Existence of planar curves minimizing length and curvature, Proc. Steklov Inst. Math., 270, 43-56, (2010) · Zbl 1215.53006 · doi:10.1134/S0081543810030041 |
| [11] | Boscain, U; Duits, R; Rossi, F; Sachkov, Y, Curve cuspless reconstruction via sub-Riemannian geometry, ESAIM Control Optim. Calc. Var., 20, 748-770, (2014) · Zbl 1381.49003 · doi:10.1051/cocv/2013082 |
| [12] | Caruyer, E., Daducci, A., Descoteaux, M., Houde, J.-C., Thiran, J.-P., Verma, R.: Phantomas: a flexible software library to simulate diffusion MR phantoms. In: ISMRM, Milan (May 2014) |
| [13] | Chen, D.: New minimal paths models for tubular structure extraction and image segmentation. Ph.D. Thesis, University Paris-Dauphine (2016) |
| [14] | Chen, D; Mirebeau, J-M; Cohen, LD, Vessel tree extraction using radius-lifted keypoints searching scheme and anisotropic fast marching method, J. Algorithms Comput. Technol., 10, 224-234, (2016) · Zbl 1540.94007 · doi:10.1177/1748301816656289 |
| [15] | Chen, D; Mirebeau, J-M; Cohen, LD, Global minimum for a Finsler elastica minimal path approach, Int. J. Comput. Vis., 122, 1-26, (2016) |
| [16] | Citti, G; Sarti, A, A cortical based model of perceptual completion in the roto-translation space, J. Math. Imaging Vis., 24, 307-326, (2006) · Zbl 1088.92008 · doi:10.1007/s10851-005-3630-2 |
| [17] | Close, TG; Tournier, J-D; Calamante, F; Johnston, LA; Mareels, I; Connelly, A, A software tool to generate simulated white matter structures for the assessment of fibre-tracking algorithms, NeuroImage, 47, 1288-1300, (2009) · doi:10.1016/j.neuroimage.2009.03.077 |
| [18] | Crandall, MG; Ishii, H; Lions, P-L, User’s guide to viscosity solutions of second order partial differential equations, Bull. Am. Math. Soc., 27, 1-67, (1992) · Zbl 0755.35015 · doi:10.1090/S0273-0979-1992-00266-5 |
| [19] | Crandall, MG; Lions, P-L, Viscosity solutions of Hamilton-Jacobi equations, Trans. Am. Math. Soc., 277, 1-42, (1983) · Zbl 0599.35024 · doi:10.1090/S0002-9947-1983-0690039-8 |
| [20] | Descoteaux, M; Deriche, R; Knosche, TR; Anwander, A, Deterministic and probabilistic tractography based on complex fibre orientation distributions, IEEE Trans. Med. Imaging, 28, 269-286, (2009) · doi:10.1109/TMI.2008.2004424 |
| [21] | Dubins, LE, On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents, Am. J. Math., 79, 497-516, (1957) · Zbl 0098.35401 · doi:10.2307/2372560 |
| [22] | Duits, R; Boscain, U; Rossi, F; Sachkov, Y, Association fields via cuspless sub-Riemannian geodesics in SE(2), J. Math. Imaging Vis., 49, 384-417, (2013) · Zbl 1296.49040 · doi:10.1007/s10851-013-0475-y |
| [23] | Duits, R; Felsberg, M; Granlund, G; Haar Romeny, B, Image analysis and reconstruction using a wavelet transform constructed from a reducible representation of the Euclidean motion group, Int. J. Comput. Vis., 72, 79-102, (2006) · doi:10.1007/s11263-006-8894-5 |
| [24] | Duits, R., Ghosh, A., Dela Haije, T., Sachkov, Y.: Cuspless sub-Riemannian geodesics within the Euclidean motion group SE(d). In: Neuromathematics of Vision, Lecture Notes in Morphogenesis, pp. 173-215 (2014). https://doi.org/10.1007/978-3-642-34444-2_5 · Zbl 1331.53054 |
| [25] | Duits, R; Ghosh, A; Dela Haije, TCJ; Mashtakov, A, On sub-Riemannian geodesics in SE(3) whose spatial projections do not have cusps, J. Dyn. Control Syst., 22, 771-805, (2016) · Zbl 1364.53033 · doi:10.1007/s10883-016-9329-4 |
| [26] | Duits, R; Janssen, MHJ; Hannink, J; Sanguinetti, GR, Locally adaptive frames in the roto-translation group and their applications in medical imaging, J. Math. Imaging Vis., 56, 367-402, (2016) · Zbl 1350.42050 · doi:10.1007/s10851-016-0641-0 |
| [27] | Duits, R., Meesters, S.P.L., Mirebeau, J.-M., Portegies, J.M.: Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis (Dec 2016). arXiv:1612.06137 [math] · Zbl 1398.65135 |
| [28] | Eshagh, M, Alternative expressions for gravity gradients in local north-oriented frame and tensor spherical harmonics, Acta Geophys., 58, 215-243, (2010) · doi:10.2478/s11600-009-0048-z |
| [29] | Fehrenbach, J; Mirebeau, J-M, Sparse non-negative stencils for anisotropic diffusion, J. Math. Imaging Vis., 49, 1-25, (2013) · Zbl 1365.68451 |
| [30] | Fletcher, PT; Joshi, S, Riemannian geometry for the statistical analysis of diffusion tensor data, Sig. Process., 87, 250-262, (2007) · Zbl 1186.94126 · doi:10.1016/j.sigpro.2005.12.018 |
| [31] | Gromov, M.: Carnot-Carathéodory spaces seen from within. In: Sub-Riemannian Geometry, Number 144 in Progress in Mathematics, pp. 79-323. Birkhäuser, Basel (1996). https://doi.org/10.1007/978-3-0348-9210-0_2 · Zbl 0864.53025 |
| [32] | Janssen, M.H.J., Janssen, A.J.E.M., Bekkers, E.J., Olivan Bescos, J., Duits, R.: Design and processing of invertible orientation scores of 3D images for enhancement of complex vasculature. Invited Submission to JMIV (Selected Paper at SSVM 2017) (July 2017). arXiv:1707.02191 [cs.CV] |
| [33] | Jbabdi, S; Bellec, P; Toro, R; Daunizeau, J; Pélégrini-Issac, M; Benali, H, Accurate anisotropic fast marching for diffusion-based geodesic tractography, Int. J. Biomed. Imaging, 2008, 2, (2008) · doi:10.1155/2008/320195 |
| [34] | Jbabdi, S; Johansen-Berg, H, Tractography: where do we go from here?, Brain Connect., 1, 169-183, (2011) · doi:10.1089/brain.2011.0033 |
| [35] | Lenglet, C; Prados, E; Pons, J; Deriche, R; Faugeras, O, Brain connectivity mapping using Riemannian geometry, control theory, and pdes, SIAM J. Imaging Sci., 2, 285-322, (2009) · Zbl 1181.68294 · doi:10.1137/070710986 |
| [36] | Mashtakov, A; Duits, R; Sachkov, Y; Bekkers, EJ; Beschastnyi, I, Tracking of lines in spherical images via sub-Riemannian geodesics in SO(3), J. Math. Imaging Vis., 58, 1-26, (2017) · Zbl 1373.49057 · doi:10.1007/s10851-017-0705-9 |
| [37] | Mashtakov, AP; Ardentov, AA; Sachkov, YL, Parallel algorithm and software for image inpainting via sub-Riemannian minimizers on the group of rototranslations, Numer. Math. Theory Methods Appl., 6, 95-115, (2013) · Zbl 1289.94013 |
| [38] | Melonakos, J; Mohan, V; Niethammer, M; Smith, K; Kubicki, M; Tannenbaum, A, Finsler tractography for white matter connectivity analysis of the cingulum bundle, Med. Image Comput. Comput. Assist. Interv., 10, 36-43, (2007) |
| [39] | Melonakos, J; Pichon, E; Angenent, S; Tannenbaum, A, Finsler active contours, IEEE Trans. Pattern Anal. Mach. Intell., 30, 412-423, (2008) · doi:10.1109/TPAMI.2007.70713 |
| [40] | Mirebeau, J-M, Efficient fast marching with Finsler metrics, Numer. Math., 126, 515-557, (2013) · Zbl 1297.65074 · doi:10.1007/s00211-013-0571-3 |
| [41] | Mirebeau, J-M, Anisotropic fast-marching on Cartesian grids using lattice basis reduction, SIAM J. Numer. Anal., 52, 1573-1599, (2014) · Zbl 1312.65172 · doi:10.1137/120861667 |
| [42] | Mirebeau, J.-M.: Anisotropic fast marching on cartesian grids using Voronoi’s reduction of quadratic forms. Preprint Available on HAL (2017). https://hal.archives-ouvertes.fr/hal-01507334 |
| [43] | Mirebeau, J.-M.: Fast marching methods for curvature penalized shortest paths. Preprint Available on HAL (2017) https://hal.archives-ouvertes.fr/hal-01538482. Accepted for publication in the same JMIV-Special issue “Differential Geometry and Orientation Analysis” |
| [44] | Moiseev, I; Sachkov, YL, Maxwell strata in sub-Riemannian problem on the group of motions of a plane, ESAIM Control Optim. Calc. Var., 16, 380-399, (2010) · Zbl 1217.49037 · doi:10.1051/cocv/2009004 |
| [45] | Montgomery, R.: A Tour of Sub-Riemannian Geometries, Their Geodesics and Applications, Volume 91 of Mathematical Surveys and Monographs (2002) · Zbl 1044.53022 |
| [46] | Mori, S.: Introduction to Diffusion Tensor Imaging. Elsevier Science, Amsterdam (2007) |
| [47] | Péchaud, M; Descoteaux, M; Keriven, R, Brain connectivity using geodesics in HARDI, Med. Image Comput. Comput. Assist. Interv., 12, 482-489, (2009) |
| [48] | Petitot, J, The neurogeometry of pinwheels as a sub-Riemannian contact structure, J. Physiol. Paris, 97, 265-309, (2003) · doi:10.1016/j.jphysparis.2003.10.010 |
| [49] | Portegies, JM; Duits, R, New exact and numerical solutions of the (convection-)diffusion kernels on SE(3), J. Differ. Geom. Appl., 53, 182-219, (2017) · Zbl 1377.35252 · doi:10.1016/j.difgeo.2017.06.004 |
| [50] | Reeds, JA; Shepp, LA, Optimal paths for a car that goes both forwards and backwards, Pac. J. Math., 145, 367-393, (1990) · Zbl 1494.49027 · doi:10.2140/pjm.1990.145.367 |
| [51] | Rouy, E; Tourin, A, A viscosity solutions approach to shape-from-shading, SIAM J. Numer. Anal., 29, 867-884, (1992) · Zbl 0754.65069 · doi:10.1137/0729053 |
| [52] | Sachkov, YL, Cut locus and optimal synthesis in the sub-Riemannian problem on the group of motions of a plane, ESAIM Control Optim. Calc. Var., 17, 293-321, (2011) · Zbl 1251.49057 · doi:10.1051/cocv/2010005 |
| [53] | Sanguinetti, G.R., Bekkers, E.J., Duits, R., Janssen, M.H.J., Mashtakov, A., Mirebeau, J.-M.: Sub-Riemannian fast marching in SE(2). In: Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, Number 9423 in Lecture Notes in Computer Science, pp. 366-374. Springer International Publishing, Berlin (2015). https://doi.org/10.1007/978-3-319-25751-8_44 · Zbl 1336.58014 |
| [54] | Sepasian, N.: Multi-valued geodesic tractography for diffusion weighted imaging. Ph.D. Thesis, Eindhoven University of Technology, Department of BME (2011) |
| [55] | Sethian, JA; Vladimirsky, A, Ordered upwind methods for static Hamilton-Jacobi equations, PNAS, 98, 11069-11074, (2001) · Zbl 1002.65112 · doi:10.1073/pnas.201222998 |
| [56] | Stefani, G., Boscain, U., Gauthier, J., Sarychev, A., Sigalotti, M.: Geometric Control Theory and Sub-Riemannian Geometry. Springer INdAM Series (2014) · Zbl 1287.49001 |
| [57] | Elst, AFM; Robinson, DW, Weighted subcoercive operators on Lie groups, J. Funct. Anal., 157, 88-163, (1998) · Zbl 0910.22005 · doi:10.1006/jfan.1998.3259 |
| [58] | Tournier, J-D; Calamante, F; Connelly, A, Mrtrix: diffusion tractography in crossing fiber regions, Int. J. Imaging Syst. Technol., 22, 53-66, (2012) · doi:10.1002/ima.22005 |
| [59] | Tsitsiklis, JN, Efficient algorithms for globally optimal trajectories, IEEE Trans. Autom. Control, 40, 1528-1538, (1995) · Zbl 0831.93028 · doi:10.1109/9.412624 |
| [60] | Tuch, DS, Q-ball imaging, Magn. Reson. Med., 52, 1358-1372, (2004) · doi:10.1002/mrm.20279 |
| [61] | Vladimirsky, A, Static PDEs for time-dependent control problems, Interfaces Free Bound., 8, 281-300, (2006) · Zbl 1102.49017 · doi:10.4171/IFB/144 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
