[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

A PDE Approach to Data-Driven Sub-Riemannian Geodesics in $SE$(2)

Published: 01 January 2015 Publication History

Abstract

We present a new flexible wavefront propagation algorithm for the boundary value problem for sub-Riemannian (SR) geodesics in the roto-translation group $SE(2) = \mathbb{R}^2 \rtimes S^1$ with a metric tensor depending on a smooth external cost $\mathcal{C}:SE(2) \to [\delta,1]$, $\delta>0$, computed from image data. The method consists of a first step where an SR-distance map is computed as a viscosity solution of a Hamilton--Jacobi--Bellman system derived via Pontryagin's maximum principle (PMP). Subsequent backward integration, again relying on PMP, gives the SR-geodesics. For $\mathcal{C}=1$ we show that our method produces the global minimizers. Comparison with exact solutions shows a remarkable accuracy of the SR-spheres and the SR-geodesics. We present numerical computations of Maxwell points and cusp points, which we again verify for the uniform cost case $\mathcal{C}=1$. Regarding image analysis applications, trackings of elongated structures in retinal and synthetic images show that our line tracking generically deals with crossings. We show the benefits of including the SR-geometry.

References

[1]
A.A. Agrachev and Yu.L. Sachkov, Control Theory from the Geometric Viewpoint, Springer-Verlag, 2004.
[2]
M. Akian, J.P. Quadrat, and M. Viot, Bellman processes, in Proceedings of the 11th International Conference on Analysis and Optimization of Systems: Discrete Event Systems, Lecture Notes in Control and Inform. Sci., Springer-Verlag, 1994, pp. 302--311.
[3]
A.M. Bayen and C.J. Tomlin, A construction procedure using characteristics for viscosity solutions of the Hamilton-Jacobi equation, in Proceedings of the 40th IEEE Conference on Decision and Control, 2001, pp. 1657--1662.
[4]
E.J. Bekkers, R. Duits, B.M. ter Haar Romeny, and T. Berendschot, A multi-orientation analysis approach to retinal vessel tracking, J. Math. Imaging Vision, 49 (2014), pp. 583--610.
[5]
E.J. Bekkers, R. Duits, and M. Loog, Training of templates for object recognition in invertible orientation scores: Application to optic nerve head detection in retinal images, in Proceedings of the 10th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), Lecture Notes in Comput. Sci. 8932, Springer, 2014, pp. 464--477.
[6]
E.J. Bekkers, R. Duits, A. Mashtakov, and G.R. Sanguinetti, Sub-Riemannian geodesics with non-uniform cost, in Proceedings of the 5th International Conference on Scale Space and Variational Methods in Computer Vision (SSVM 2015), J.-F. Aujol, M. Nikolova, and N. Papadakis, eds., Lecture Notes in Comput. Sci. 9087, Springer, 2015, pp. 613--625.
[7]
F. Benmansour and L.D. Cohen, Tubular structure segmentation based on minimal path method and anisotropic enhancement, Internat. J. Comput. Vision, 92 (2011), pp. 192--210.
[8]
G. Ben-Yosef and O. Ben-Shahar, A tangent bundle theory for visual curve completion, IEEE Trans. Pattern Anal. Mach. Intell., 34 (2012), pp. 1263--1280.
[9]
U. Boscain, G. Charlot, and F. Rossi, Existence of planar curves minimizing length and curvature, Proc. Steklov Inst. Math., 270 (2010), pp. 43--46.
[10]
U. Boscain, R. Duits, F. Rossi, and Y. Sachkov, Curve cuspless reconstruction via sub-Riemannian geometry, ESAIM Control Optim. Calc. Var., 20 (2014), pp. 748--770.
[11]
A. Bressan, Viscosity Solutions of Hamilton-Jacobi Equations and Optimal Control Problems, Lecture Notes Dept. of Math., Pennsylvania State University, 2011.
[12]
B. Burgeth and J. Weickert, An explanation for the logarithmic connection between linear and morphological system theory, Internat. J. Comput. Vision, 64 (2005), pp. 157--169.
[13]
H. Chakir, J.P. Gauthier, and I. Kupka, Small sub-Riemannian balls on $\R^3$, J. Dynam. Control Syst., 2 (1996), pp. 359--421.
[14]
D. Chen, L. Cohen, and J.-M. Mirebeau, Piecewise geodesics for vessel centerline extraction and boundary delineation with application to retina segmentation, in Proceedings of the 5th International Conference on Scale Space and Variational Methods in Computer Vision (SSVM 2015), J.-F. Aujol, M. Nikolova, and N. Papadakis, eds., Lecture Notes in Comput. Sci. 9087, Springer, 2015, pp. 270--281.
[15]
G. Citti and A. Sarti, A cortical based model of perceptual completion in the roto-translation space, J. Math. Imaging Vision, 24 (2006), pp. 307--326.
[16]
R. Duits, U. Boscain, F. Rossi, and Y. Sachkov, Association fields via cuspless sub-Riemannian geodesics in SE$(2)$, J. Math. Imaging Vision, 49 (2014), pp. 384--417.
[17]
R. Duits, T. Dela Haije, E. Creusen, and A. Ghosh, Morphological and linear scale spaces for fiber enhancement in DW-MRI, J. Math. Imaging Vision, 46 (2013), pp. 326--368.
[18]
R. Duits, M. Felsberg, G. Granlund, and B.H. Romeny, Image analysis and reconstruction using a wavelet transform constructed from a reducible representation of the Euclidean motion group, Internat. J. Comput. Vision, 72 (2007), pp. 79--102.
[19]
L.C. Evans, Partial Differential Equations, Grad. Stud. Math. 19, AMS, Providence, RI, 1998.
[20]
E. Franken and R. Duits, Crossing-preserving coherence-enhancing diffusion on  invertible orientation scores, Internat. J. Comput. Vision, 85 (2009), pp. 253--278.
[21]
R.K. Hladky and S.D. Pauls, Minimal surfaces in the roto-translation group with applications to a neuro-biological image completion model, J. Math. Imaging Vision, 36 (2010), pp. 1--27.
[22]
H. Li and A. Yezzi, Vessels as $4$-D curves: Global minimal $4$-D paths to extract $3$-D tubular surfaces and centerlines, IEEE Trans. Med. Imaging, 26 (2007), pp. 1213--1223.
[23]
T. Lindeberg, Edge detection and ridge detection with automatic scale selection, Internat. J. Comput. Vision, 30 (1998), pp. 117--154.
[24]
P.L. Lions, Generalized Solutions of Hamilton-Jacobi Equations, Res. Notes Math. 69, Pitman, Boston, London, 1982.
[25]
A.P. Mashtakov, A.A. Ardentov, and Y.L. Sachkov, Parallel algorithm and software for image inpainting via sub-Riemannian minimizers on the group of rototranslations, Numer. Math. Theory Methods Appl., 6 (2013), pp. 95--115.
[26]
J-M. Mirebeau, Anisotropic fast-marching on Cartesian grids using lattice basis reduction, SIAM J. Numer. Anal., 52 (2014), pp. 1573--1599.
[27]
I. Moiseev and Y.L. Sachkov, Maxwell strata in sub-Riemannian problem on the group of motions of a plane, ESAIM Control Optim. Calc. Var., 16 (2010), pp. 380--399.
[28]
R. Montgomery, A Tour of Subriemannian Geometries, Their Geodesics and Applications, AMS, Providence, RI, 2002.
[29]
S. Osher and R.P. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Appl. Math. Sci., Springer, New York, 2003.
[30]
M. Péchaud, M. Descoteaux, and R. Keriven, Brain connectivity using geodesics in HARDI, in Medical Image Computing and Computer-Assisted Intervention (MICCAI 2009), Springer, Berlin, Heidelberg, 2009, pp. 482--489.
[31]
M. Péchaud, G. Peyré, and R. Keriven, Extraction of tubular structures over an orientation domain, in Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2009), 2009, pp. 336--343.
[32]
J. Petitot, The neurogeometry of pinwheels as a sub-Riemannian contact structure, J. Physiol. Paris, 97 (2003), pp. 265--309.
[33]
G. Peyré, M. Péchaud, R. Keriven, and L.D. Cohen, Geodesic methods in computer vision and graphics, Found. Trends. Comp. in Computer Graphics and Vision, 5 (2010), pp. 197--397.
[34]
J.A. Reeds and L.A. Shepp, Optimal paths for a car that goes both forward and backward, Pacific J. Math. 145 (1990), pp. 367--393.
[35]
E. Rouy and A. Tourin, A viscosity solutions approach to shape-from-shading, SIAM J. Numer. Anal., 29 (1992), pp. 867--884.
[36]
Y.L. Sachkov, Conjugate and cut time in the sub-Riemannian problem on the group of motions of a plane, ESAIM Control Optim. Calc. Var., 16 (2009), pp. 1018--1039.
[37]
Y.L. Sachkov, Cut locus and optimal synthesis in the sub-Riemannian problem on the group of motions of a plane, ESAIM Control Optim. Calc. Var., 17 (2011), pp. 293--321.
[38]
J.A. Sethian, Level Set Methods and Fast Marching Methods, Cambridge University Press, Cambridge, UK, 1999.
[39]
E. Trelat, Global subanalytic solutions of Hamilton-Jacobi type equations, Ann. Inst. H. Poincaré Anal. Non Linéaire, 23 (2006), pp. 363--387.
[40]
K. Yosida, Functional Analysis, 6th ed., Springer, 1980.

Cited By

View all
  • (2024)Geodesic Tracking via New Data-Driven Connections of Cartan Type for Vascular Tree TrackingJournal of Mathematical Imaging and Vision10.1007/s10851-023-01170-x66:2(198-230)Online publication date: 1-Apr-2024
  • (2023)Analysis of (sub-)Riemannian PDE-G-CNNsJournal of Mathematical Imaging and Vision10.1007/s10851-023-01147-w65:6(819-843)Online publication date: 16-Apr-2023
  • (2023)Geodesic Tracking of Retinal Vascular Trees with Optical and TV-Flow Enhancement in SE(2)Scale Space and Variational Methods in Computer Vision10.1007/978-3-031-31975-4_40(525-537)Online publication date: 21-May-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Imaging Sciences
SIAM Journal on Imaging Sciences  Volume 8, Issue 4
EISSN:1936-4954
DOI:10.1137/sjisbi.8.4
Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2015

Author Tags

  1. roto-translation group
  2. Hamilton--Jacobi equations
  3. vessel tracking
  4. sub-Riemannian geometry
  5. morphological scale spaces

Author Tags

  1. 58J32
  2. 65D18
  3. 35B37
  4. 43A80
  5. 65N06

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 25 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Geodesic Tracking via New Data-Driven Connections of Cartan Type for Vascular Tree TrackingJournal of Mathematical Imaging and Vision10.1007/s10851-023-01170-x66:2(198-230)Online publication date: 1-Apr-2024
  • (2023)Analysis of (sub-)Riemannian PDE-G-CNNsJournal of Mathematical Imaging and Vision10.1007/s10851-023-01147-w65:6(819-843)Online publication date: 16-Apr-2023
  • (2023)Geodesic Tracking of Retinal Vascular Trees with Optical and TV-Flow Enhancement in SE(2)Scale Space and Variational Methods in Computer Vision10.1007/978-3-031-31975-4_40(525-537)Online publication date: 21-May-2023
  • (2022)PDE-Based Group Equivariant Convolutional Neural NetworksJournal of Mathematical Imaging and Vision10.1007/s10851-022-01114-x65:1(209-239)Online publication date: 27-Jul-2022

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media