Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Metrics of Curves in Shape Optimization and Analysis

  • Chapter
  • First Online:
Level Set and PDE Based Reconstruction Methods in Imaging

Part of the book series: Lecture Notes in Mathematics ((LNMCIME,volume 2090))

Abstract

In these lecture notes we will explore the mathematics of the space of immersed curves, as is nowadays used in applications in computer vision. In this field, the space of curves is employed as a “shape space”; for this reason, we will also define and study the space of geometric curves, which are immersed curves up to reparameterizations. To develop the usages of this space, we will consider the space of curves as an infinite dimensional differentiable manifold; we will then deploy an effective form of calculus and analysis, comprising tools such as a Riemannian metric, so as to be able to perform standard operations such as minimizing a goal functional by gradient descent, or computing the distance between two curves. Along this path of mathematics, we will also present some current literature results (and a few examples of different “shape spaces”, including more than only curves).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook
USD 15.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 15.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We will provide more detailed definitions and properties of the “actions” in Sect. 3.8.

  2. 2.

    Due to Fréchet, 1948; but also attributed to Karcher [26].

  3. 3.

    The precise definition of what the gradient is is in Sect. 3.7.

  4. 4.

    A different gradient descent flow for curve length will be discussed in Remark 10.32.

  5. 5.

    The derivatives are computed in distributional sense, and must exists as Lebesgue integrable functions.

  6. 6.

    The fattened sets are not drawn filled—otherwise they would cover A.

  7. 7.

    That is, any A, B ∈Ξ c can be connected by a Lipschitz arc γ: [0, 1] →Ξ c .

  8. 8.

    “Generically” is meant in the Baire sense: the set of exceptions is of first category.

  9. 9.

    There is a slight abuse of notation here, since in the definition N = T ⊥ given for planar curves in 1.12, we defined N to be a “vector” and not the “vector space orthogonal to T”.

  10. 10.

    We are considering only reparameterizations in Diff+(S 1).

  11. 11.

    It seems that S is Lipschitz-arc-connected, so d g(x, y) < ∞; but we did not carry on a detailed proof.

  12. 12.

    Indeed, the continuous lifting is unique up to addition of a constant to α(s), which is equivalent to a rotation of ξ; and the constant is decided by Φ 1(α) = 2π 2.

  13. 13.

    It is though possible to define Sobolev metrics for any \(j \in \mathbb{R},j > 0\); see Prop. 3.1 in [57].

  14. 14.

    Though, a scale-invariant Sobolev metric is proposed in [39] in Sect. 4.8 as a sensible generalization.

  15. 15.

    The detailed proof has not yet been written…

  16. 16.

    Note this definition is different from (13) in [56].

  17. 17.

    We use the definition (42) of H 0.

  18. 18.

    Though, an alternate method that does not need the tracing of the curve is described in Sect. 5.3 in [56]—but it was not successively used, since it depends on some difficult-to-tune parameters.

  19. 19.

    In a sense, the focus of research in active contours has been mostly on the numerator in (52)—whereas we now focus on the denominator.

  20. 20.

    We use the definition (42) of H 0; the directional derivative was computed in 4.6.

  21. 21.

    H 0 j was defined in (39). Note that H 0 j is a seminorm on T c M, since its value is zero on constant fields; but H 0 j is a norm on D c M, by Poincaré inequality (43).

  22. 22.

    We use the definition (42) of H 0.

  23. 23.

    A.k.a. as the Picard–Lindelöf theorem.

  24. 24.

    Actually, by tracking the first part of the proof in detail, it possible to prove that all other constants \(a_{1},a_{2},a_{3},a_{4},P,Q\) may be bounded in terms of these two quantities I(t), N(t).

References

  1. L. Ambrosio, G. Da Prato, A.C.G. Mennucci, An introduction to measure theory and probability, 2007. http//dida.sns.it/dida2/cl/07-08/folde2/pdf0

  2. T.M. Apostol, Mathematical Analysis (Addison Wesley, Reading, 1974)

    MATH  Google Scholar 

  3. C.J. Atkin, The Hopf-Rinow theorem is false in infinite dimensions. Bull. Lond. Math. Soc. 7(3), 261–266 (1975) doi: 10.1112/blms/7.3.261

    Article  MathSciNet  MATH  Google Scholar 

  4. H. Brezis, Analisi Funzionale (Liguori Editore, Napoli, 1986). Italian translation of Analyse fonctionelle (Masson, Paris, 1983)

    Google Scholar 

  5. J. Canny, A computational approach to edge detection. IEEE Trans. Pattern Anal. Mach. Intell. 8(6), 679–698 (1986) ISSN 0162-8828.

    Google Scholar 

  6. V. Caselles, F. Catte, T. Coll, F. Dibos, A geometric model for edge detection. Num. Mathematik 66, 1–31 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  7. V. Caselles, R. Kimmel, G. Sapiro, Geodesic active contours, in Proceedings of the IEEE International Conference on Computer Vision, Cambridge, MA, June 1995, pp. 694–699

    Google Scholar 

  8. T. Chan, L. Vese, Active contours without edges. IEEE Trans. Image Process. 10(2), 266–277 (2001)

    Article  MATH  Google Scholar 

  9. G. Charpiat, O. Faugeras, R. Keriven, Approximations of shape metrics and application to shape warping and empirical shape statistics. Found. Comput. Math. (2004) doi: 10.1007/s10208-003-0094-xgg819. INRIA report 4820 (2003)

    Google Scholar 

  10. G. Charpiat, R. Keriven, J.P. Pons, O. Faugeras, Designing spatially coherent minimizing flows for variational problems based on active contours, in ICCV (2005). doi: 10.1109/ICCV.2005.69

    Google Scholar 

  11. G. Charpiat, P. Maurel, J.-P. Pons, R. Keriven, O. Faugeras, Generalized gradients: Priors on minimization flows. Int. J. Comp. Vis. (2007). doi: 10.1007/s11263-006-9966-2

    Google Scholar 

  12. Y. Chen, H. Tagare, S. Thiruvenkadam, F. Huang, D. Wilson, K. Gopinath, R. Briggs, E. Geiser, Using prior shapes in geometric active contours in a variational framework. Int. J. Comp. Vis. 50(3), 315–328 (2002)

    Article  MATH  Google Scholar 

  13. D. Cremers, S. Soatto, A pseuso distance for shape priors in level set segmentation, in 2nd IEEE Workshop on Variational, Geometric and Level Set Methods in Computer Vision, Nice, ed. by N. Paragios, Oct 2003, pp. 169–176

    Google Scholar 

  14. M.P. do Carmo, Riemannian Geometry (Birkhäuser, Boston, 1992)

    Google Scholar 

  15. A. Duci, A.C.G. Mennucci, Banach-like metrics and metrics of compact sets. arXiv preprint arXiv:0707.1174 (2007)

    Google Scholar 

  16. A. Duci, A.J. Yezzi, S.K. Mitter, S.Soatto, Shape representation via harmonic embedding, in International Conference on Computer Vision (ICCV03), vol. 1, Washington, DC, pp. 656–662 (IEEE Computer Society, Silver Spring, 2003). ISBN 0-7695-1950-4. doi: 10.1109/ICCV.2003.1238410

    Google Scholar 

  17. A. Duci, A.J. Yezzi, S. Soatto, K. Rocha, Harmonic embeddings for linear shape. J. Math Imag. Vis 25, 341–352 (2006). doi: 10.1007/s10851-006-7249-8

    Article  MathSciNet  Google Scholar 

  18. J. Eells, K.D. Elworthy, Open embeddings of certain Banach manifolds. Ann. Math. (2) 91, 465–485 (1970)

    Google Scholar 

  19. I. Ekeland, The Hopf-Rinow theorem in infinite dimension. J. Differ. Geom. 13(2), 287–301 (1978)

    MathSciNet  MATH  Google Scholar 

  20. A.T. Fomenko, The Plateau Problem. Studies in the Development of Modern Mathematics (Gordon and Breach, New York, 1990)

    Google Scholar 

  21. M. Gage, R.S. Hamilton, The heat equation shrinking convex plane curves. J. Differ. Geom. 23, 69–96 (1986)

    MathSciNet  MATH  Google Scholar 

  22. J. Glaunès, A. Trouvé, L. Younes, Modeling planar shape variation via Hamiltonian flows of curves, in Analysis and Statistics of Shapes, ed. by A. Yezzi, H. Krim. Modeling and Simulation in Science, Engineering and Technology, chapter 14 (Birkhäuser, Basel, 2005)

    Google Scholar 

  23. M. Grayson, The heat equation shrinks embedded planes curves to round points. J. Differ. Geom. 26, 285–314 (1987)

    MathSciNet  MATH  Google Scholar 

  24. R.S. Hamilton, The inverse function theorem of Nash and Moser. Bull. Am. Math. Soc. (N.S.) 7(1), 65–222 (1982) ISSN 0273-0979.

    Google Scholar 

  25. J. Itoh, M. Tanaka, The Lipschitz continuity of the distance function to the cut locus. Trans. A.M.S. 353(1), 21–40 (2000)

    Google Scholar 

  26. H. Karcher, Riemannian center of mass and mollifier smoothing. Comm. Pure Appl. Math. 30, 509–541 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  27. M. Kass, A. Witkin, D. Terzopoulos, Snakes: active contour models. Int. J. Comp. Vis. 1, 321–331 (1987)

    Article  Google Scholar 

  28. S. Kichenassamy, A. Kumar, P. Olver, A. Tannenbaum, A. Yezzi, Gradient flows and geometric active contour models, in Proceedings of the IEEE International Conference on Computer Vision, Cambridge, MA (1995), pp. 810–815. doi:10.1109/ICCV.1995.466855

    Google Scholar 

  29. E. Klassen, A. Srivastava, W. Mio, S.H. Joshi, Analysis of planar shapes using geodesic paths on shape spaces. IEEE Trans. Pattern Anal. Mach. Intell. 26, 372–383 (2004). ISSN 0162-8828. doi: 10.1109/TPAMI.2004.1262333

    Google Scholar 

  30. W. Klingenberg, Riemannian Geometry (W. de Gruyter, Berlin, 1982)

    MATH  Google Scholar 

  31. S. Lang, Fundamentals of Differential Geometry (Springer, Berlin, 1999)

    Book  MATH  Google Scholar 

  32. M. Leventon, E. Grimson, O. Faugeras, Statistical shape influence in geodesic active contours, IEEE Conference on Computer Vision and Pattern Recognition, Hilton Head Island, SC, vol. 1 (2000), pp. 316–323. doi:10.1109/CVPR.2000.855835

    Google Scholar 

  33. Y. Li, L. Nirenberg, The distance function to the boundary, Finsler geometry and the singular set of viscosity solutions of some Hamilton-Jacobi equations. Comm. Pure Appl. Math. 58, 85–146 (2005)

    MathSciNet  MATH  Google Scholar 

  34. R. Malladi, J. Sethian, B. Vemuri, Shape modeling with front propagation: a level set approach. IEEE Trans. Pattern Anal. Mach. Intell. 17, 158–175 (1995)

    Article  Google Scholar 

  35. A.C.G. Mennucci, A. Yezzi, G. Sundaramoorthi, Properties of Sobolev Active Contours. Interf. Free Bound. 10, 423–445 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  36. A.C.G. Mennucci, On asymmetric distances, 2nd version, preprint, 2004. http://cvgmt.sns.it/papers/and04/

  37. P.W. Michor, D. Mumford, Vanishing geodesic distance on spaces of submanifolds and diffeomorphisms. Documenta Math. 10, 217–245 (2005). http://www.univie.ac.at/EMIS/journals/DMJDMV/vol-10/05.pdf

    Google Scholar 

  38. P.W. Michor, D. Mumford, Riemannian geometris of space of plane curves. J. Eur. Math. Soc. (JEMS) 8, 1–48 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  39. P.W. Michor, D. Mumford, An overview of the Riemannian metrics on spaces of curves using the Hamiltonian approach. Appl. Comput. Harmonic Anal. 23, 76–113 (2007). doi: 10.1016/j.acha.2006.07.004. http://www.mat.univie.ac.at/~michor/curves-hamiltonian.pdf

  40. W. Mio, A. Srivastava, Elastic-string models for representation and analysis of planar shapes, in Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004 (CVPR 2004), vol. 2 (2004), pp. 10–15. doi:10.1109/CVPR.2004.1315138

    Google Scholar 

  41. W. Mio, A. Srivastava, Elastic-string models for representation and analysis of planar shapes, in Conference on Computer Vision and Pattern Recognition (CVPR), June 2004. http://stat.fsu.edu/~anuj/pdf/papers/CVPR_Paper_04.pdf

  42. D. Mumford, J. Shah, Boundary detection by minimizing functionals, in Proceedings CVPR 85: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, June 19–23, 1985, San Francisco, CA, 1985

    Google Scholar 

  43. D. Mumford, J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems. Comm. Pure Appl. Math. 42, 577–685 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  44. S. Osher, J. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on the Hamilton-Jacobi equations. J. Comp. Phys. 79, 12–49 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  45. T.R. Raviv, N. Kiryati, N. Sochen, Unlevel-set: geometry and prior-based segmentation, in Proceedings of European Conference on Computer Vision, 2004 (Computer Vision-ECCV 2004), ed. by T. Pajdla (Springer, Berlin, 2004). http://dx.doi.org/10.1007/978-3-540-24673-2_5

  46. R. Ronfard, Region based strategies for active contour models. Int. J. Comp. Vis. 13(2), 229–251 (1994). http://perception.inrialpes.fr/Publications/1994/Ron94

    Google Scholar 

  47. M. Rousson, N. Paragios, Shape priors for level set representations, in Proceedings of the European Conference on Computer Vision, vol. 2 (2002), pp. 78–93

    Google Scholar 

  48. W. Rudin, Functional Analysis (McGraw-Hill, New York, 1973)

    MATH  Google Scholar 

  49. W. Rudin, Real and Complex Analysis (McGraw-Hill, New York, 1987)

    MATH  Google Scholar 

  50. J. Shah, H 0 type Riemannian metrics on the space of planar curves. Q. Appl. Math. 66, 123–137 (2008)

    MATH  Google Scholar 

  51. S. Soatto, A.J. Yezzi, DEFORMOTION: deforming motion, shape average and the joint registration and segmentation of images. ECCV (3), 32–57 (2002)

    Google Scholar 

  52. A. Srivastava, S.H. Joshi, W. Mio, X. Liu, Statistical shape analysis: clustering, learning, and testing. IEEE Trans. Pattern Anal. Mach. Intell. 27, 590–602 (2005). ISSN 0162-8828. doi: 10.1109/TPAMI.2005.86

    Google Scholar 

  53. G. Sundaramoorthi, A. Yezzi, A.C.G. Mennucci, Sobolev active contours, in VLSM, ed. by N. Paragios, O.D. Faugeras, T. Chan, C. Schnörr. Lecture Notes in Computer Science, vol. 3752 (Springer, Berlin, 2005), pp. 109–120. ISBN 3-540-29348-5. doi: 10.1007/11567646_10

    Google Scholar 

  54. G. Sundaramoorthi, J.D. Jackson, A. Yezzi, A.C.G. Mennucci, Tracking with Sobolev active contours, in Conference on Computer Vision and Pattern Recognition (CVPR06) (IEEE Computer Society, Silver Spring, 2006). ISBN 0-7695-2372-2. doi: 10.1109/CVPR.2006.314

    Google Scholar 

  55. G. Sundaramoorthi, A. Yezzi, A.C.G. Mennucci, G. Sapiro, New possibilities with Sobolev active contours, in Scale Space Variational Methods 07 (2007). http://ssvm07.ciram.unibo.it/ssvm07_public/index.html. “Best Numerical Paper-Project Award”; also [58]

  56. G. Sundaramoorthi, A. Yezzi, A.C.G. Mennucci, Sobolev active contours. Int. J. Comp. Vis. (2007). doi: 10.1007/s11263-006-0635-2

    Google Scholar 

  57. G. Sundaramoorthi, A. Yezzi, A.C.G. Mennucci, Coarse-to-fine segmentation and tracking using Sobolev Active Contours. IEEE Trans. Pattern Anal. Mach. Intell. (TPAMI) (2008). doi: 10.1109/TPAMI.2007.70751

    Google Scholar 

  58. G. Sundaramoorthi, A. Yezzi, A.C.G. Mennucci, G. Sapiro, New possibilities with Sobolev active contours. Int. J. Comp. Vis. (2008). doi: 10.1007/s11263-008-0133-9

    Google Scholar 

  59. A. Trouvé, L. Younes, Local geometry of deformable templates. SIAM J. Math. Anal. 37(1), 17–59 (electronic) (2005). ISSN 0036-1410

    Google Scholar 

  60. A. Tsai, A. Yezzi, W. Wells, C. Tempany, D. Tucker, A. Fan, E. Grimson, A. Willsky, Model-based curve evolution technique for image segmentation, in Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2001 (CVPR 2001), vol. 1, Dec 2001, pp. I-463, I-468. doi: 10.1109/CVPR.2001.990511

    Google Scholar 

  61. A. Tsai, A. Yezzi, A.S. Willsky, Curve evolution implementation of the mumford-shah functional for image segmentation, denoising, interpolation, and magnification. IEEE Trans. Image Process. 10(8), 1169–1186 (2001)

    Article  MATH  Google Scholar 

  62. L.A. Vese, T.F. Chan, A multiphase level set framework for image segmentation using the mumford and shah model. Int. J. Comp. Vis. 50(3), 271–293 (2002)

    Article  MATH  Google Scholar 

  63. A. Yezzi, A.C.G. Mennucci, Geodesic homotopies, in EUSIPCO04 (2004). http://www.eurasip.org/content/Eusipco/2004/defevent/papers/cr1925.pdf

  64. A. Yezzi, A.C.G. Mennucci, Metrics in the space of curves. arXiv (2004)

    Google Scholar 

  65. A. Yezzi, A.C.G. Mennucci, Conformal metrics and true “gradient flows” for curves, in International Conference on Computer Vision (ICCV05) (2005), pp. 913–919. doi: 10.1109/ICCV.2005.60. URL http://research.microsoft.com/iccv2005/

  66. A. Yezzi, A. Tsai, A. Willsky, A statistical approach to snakes for bimodal and trimodal imagery, in The Proceedings of the Seventh IEEE International Conference on Computer Vision, 1999, vol. 2, October 1999, pp. 898, 903. doi:10.1109/ICCV.1999.790317

    Google Scholar 

  67. L. Younes, Computable elastic distances between shapes. SIAM J. Appl. Math. 58(2), 565–586 (1998). doi: 10.1137/S0036139995287685

    Article  MathSciNet  MATH  Google Scholar 

  68. L. Younes, P.W. Michor, J. Shah, D. Mumford, A metric on shape space with explicit geodesics. Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. Rend. Lincei (9) Mat. Appl. 19(1), 25–57 (2008). ISSN 1120-6330. doi: 10.4171/RLM/506

    Google Scholar 

  69. C.T. Zahn, R.Z. Roskies, Fourier descriptors for plane closed curves. IEEE Trans. Comput. 21(3), 269–281 (1972). ISSN 0018-9340. doi: 10.1109/TC.1972.5008949

    Google Scholar 

  70. S.C. Zhu, T.S. Lee, A.L. Yuille, Region competition: Unifying snakes, region growing, energy/bayes/MDL for multi-band image segmentation, in ICCV (1995), p. 416. citeseer.ist.psu.edu/zhu95region.html

Download references

Author information

Authors and Affiliations

  1. Scuola Normale Superiore, Pisa, Italy

    Andrea C. G. Mennucci

Authors
  1. Andrea C. G. Mennucci
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrea C. G. Mennucci .

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer International Publishing Switzerland

About this chapter

Cite this chapter

Mennucci, A.C.G. (2013). Metrics of Curves in Shape Optimization and Analysis. In: Level Set and PDE Based Reconstruction Methods in Imaging. Lecture Notes in Mathematics(), vol 2090. Springer, Cham. https://doi.org/10.1007/978-3-319-01712-9_4

Download citation

Publish with us

Policies and ethics

Search

Navigation