Top

Published in:

2013 | OriginalPaper | Chapter

9. A Brief Survey on Semi-Lagrangian Schemes for Image Processing

Authors : Elisabetta Carlini, Maurizio Falcone, Adriano Festa

Published in: Innovations for Shape Analysis

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this survey we present some semi-Lagrangian schemes for the approximation of weak solutions of first and second order differential problems related to image processing and computer vision. The general framework is given by the theory of viscosity solutions and, in some cases, of calculus of variations. The schemes proposed here have interesting stability properties for evolutive problems since they allow for large time steps, can deal with degenerate problems and are more accurate if compared to standard finite difference/element methods of the same order. Several examples on classical problems will illustrate these properties.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Stable Semi-local Features for Non-rigid Shapes

next chapter Shape Reconstruction of Symmetric Surfaces Using Photometric Stereo

Alvarez, L., Lions, P.L., Morel, J.M.: Image selective smoothing and edge detection by nonlinear diffusion. SIAM J. Numer. Anal. 29, 845–866 (1992)MathSciNetMATHCrossRef

Alvarez, L., Guichard, F., Lions, P.L., Morel, J.M.: Axioms and fundamental equations of image processing. Arch. Ration. Mech. 123, 199–257 (1993)MathSciNetMATHCrossRef

Amiaz, T., Kiryati, N.: Piecewise-smooth dense optical flow via level sets. Int. J. Comput. Vis. 68(2), 111–124 (2006)CrossRef

Barles, G.: Solutions de Viscositè des Equations d’Hamilton–Jacobi. Springer, New York (1998)

Barron, J.L., Fleet, D.J., Beauchemin, S.S.: Performance of optical flow techniques. Int. J. Comput. Vis. 12, 75–104 (1996)

Brenner S.C., Scott, L.R.: The Mathematical Theory of Finite Element Methods, 3rd edn. Springer, New York (2008)MATHCrossRef

Brent, R.: Algorithms for Minimization Without Derivatives. Pentice–Hall, Englewood Cliffs (1973)MATH

Breuss, M., Cristiani, E., Durou, J.D., Falcone, M., Vogel, O.: Numerical algorithms for perspective shape from shading. Kybernetika 46, 207–225 (2010)MathSciNetMATH

Brox, T., Bruhn, A., Papenberg, N., Weickert, J.: High Accuracy Optical Flow Estimation Based on a Theory for Warping. Lecture Notes in Computer Science, pp. 25–36. Springer, Berlin (2004)

10.

Brox, T., Bruhn, A., Weickert, J.: Variational segmentation with level sets. In: Computer Vision-ECCV, Graz, pp. 471–483 (2006)

11.

Camilli, F., Falcone, M.: An approximation scheme for the maximal solution of the shape-from-shading model. In: Proceedings ICIP 96, vol. I, pp. 49–52. IEEE, Piscataway (1996)

12.

Carlini, E., Ferretti, R.: A semi-Lagrangian approximation for the AMSS model of image processing. submitted to Applied Numerical Mathematics (in press)

13.

Carlini, E., Ferretti, R., Russo, G.: A weighted essentially non oscillatory, large time-step scheme for Hamilton Jacobi equations. SIAM J. Sci. Comput. 27(3), 1071–1091 (2005)MathSciNetMATHCrossRef

14.

Carlini, E., Falcone, M., Ferretti, R.: Convergence of a large time-step scheme for mean curvature motion. Interface Free Bound. 12, 409–441 (2010)MathSciNetMATHCrossRef

15.

Catté, F., Dibos, F., Koepfler, G.: A morphological scheme for mean curvature motion and applications to anisotropic diffusion and motion of level sets. SIAM J. Numer. Anal. 32, 1895–1909 (1995)MathSciNetMATHCrossRef

16.

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

17.

Chan, T., Sandberg, B., Vese, L.: Active contours without edges for vector-valued images. J. Vis. Commun. Image R. 11(2), 130–141 (2000)CrossRef

18.

Chen, Y.G., Giga, Y., Goto, S.: Uniqueness and existence of viscosity solutions of generalized mean curvature flow equation. J. Diff. Geom. 33, 749–786 (1991)MathSciNetMATH

19.

Courant, R., Isaacson, E., Rees, M.: On the solution of nonlinear hyperbolic differential equations by finite differences. Commun. Pure Appl. Math. 5, 243–255 (1952)MathSciNetMATHCrossRef

20.

Courteille, F., Crouzil, A., Durou, J.D., Gurdjos, P.: Towards shape from shading under realistic photographic conditions, Int. C. Patt. Recog.- ICPR 2004, Cambridge, vol. 2, pp. 277–280 (2004)

21.

Crandall, M.G., Lions, P.L.: Two approximations of solutions of Hamilton–Jacobi equations. Math. Comput. 43, 1–19 (1984)MathSciNetMATHCrossRef

22.

Crandall, M.G., 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)MathSciNetMATHCrossRef

23.

Cremers, D., Soatto, S.: Motion competition: a variational framework for piecewise parametric motion segmentation. Int. J. Comput. Vis. 63, 249–265 (2005)CrossRef

24.

Cristiani, E., Falcone, M.: Fast semi-Lagrangian schemes for the eikonal equation and applications. SIAM J. Numer. Anal. 45(5), 1979–2011 (2007)MathSciNetMATHCrossRef

25.

Cristiani, E., Falcone, M., Seghini, A.: Numerical solution of the shape-from-shading problem. In: Proceedings of Science POS (CSTNA2005) 008, 1–17, Electronic Journal site http://pos.sissa.it/

26.

De Giorgi, E.: New functionals in calculus of variations, nonsmooth optimization and related topics. In: Proceedings of the Fourth Course of the International School of Mathematics, Erice (1988)

27.

Durou, J.D., Falcone, M., Sagona, M.: Numerical methods for shape from shading: a new survey with benchmarks. Comput. Vis. Image Underst. Elsevier 109, 22–43 (2008)CrossRef

28.

Evans, L.C.: Partial Differential Equations. AMS, Providence (2010)MATH

29.

Evans, L.C., Spruck, J.: Motion of level sets by mean curvature. Int. J. Diff. Geom. 33, 635–681 (1991)MathSciNetMATH

30.

Falcone, M.: The minimum time problem and its applications to front propagation. In: Motion by Mean Curvature and Related Topics. De Gruyter Verlag, Berlino (1994)

31.

Falcone, M., Ferretti, R.: Convergence analysis for a class of high-order semi-Lagrangian advection schemes. SIAM J. Numer. Anal. 35(3), 909–940 (1998)MathSciNetMATHCrossRef

32.

Falcone, M., Ferretti, R.: Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations. SIAM, in preparation

33.

Falcone, M., Sagona, M., Seghini, A.: A global algorithm for the Shape-from-Shading problem with black shadows. Numerical Mathematics and Advanced Applications ENUMATH 2001, pp. 503–512. Springer, Milano (2003)

34.

Guichard, F., Morel, J.M.: Image Analysis and P.D.E.s. IPAM GBM Tutorial, March 27–April 6 (2001)

35.

Horn, B.K.P., Brooks M.J. (eds.): Shape from Shading. MIT, Cambridge (1989)

36.

Horn, B.K.P., Schunck, B.: Determinig optical flow. Artif. Intell. 17, 185–203 (1981)CrossRef

37.

Lions, P.L., Rouy, E., Tourin, A.: A viscosity solution approach to shape from shading. Numer. Math. 64, 323–353 (1993)MathSciNetMATHCrossRef

38.

Morel, J.M., Solimini, S.: Segmentation of images by variational methods: a constructive approach. Rev. Mat. Univ. Compl. de Madr. 1, 169–182 (1988)MathSciNetMATH

39.

Mumford, D., Shah, J.: Boundary detection by minimizing functional. In: Proceedings of the CVPR, pp. 22–26. IEEE, Silver Spring (1985)

40.

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

41.

Oberman, A.M.: A convergent monotone difference scheme for motion of level sets by mean curvature. Numer. Math. 99, 365–379 (2004)MathSciNetMATHCrossRef

42.

Osher, S.J., Fedkiw, R.P.: Level Set Methods and Dynamic Implicit Surfaces. Applied Mathematical Sciences, vol. 153. Springer, New York (2003)

43.

Osher, S.J., Sethian, J.A.: Front propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulation. J. Comput. Phys. 79, 12–49 (1988)MathSciNetMATHCrossRef

44.

Prados, E., Faugeras, O.: Perspective Shape-from-Shading and viscosity solutions. In: Proceedings of ICCV’03, pp. 826–831. IEEE, Los Alamitos (2003)

45.

Sethian, J.A.: Level Set Methods and Fast Marching Methods Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge Monograph on Applied and Computational Mathematics. Cambridge University Press, Cambridge (1999)MATH

46.

Strikwerda, J.C.: Finite Difference Schemes and Partial Differential Equations, 2nd edn. SIAM, Philadelphia (2004)MATHCrossRef

47.

Univerität Kalsruhe. http://i21www.ira.uka.de/image_sequences/

48.

Vese, L., Chan, T.: A multiphase level set framework for image segmentation using the Mumford and Shah model. Int. J. Comput. Vis. 50, 271–293 (2002)MATHCrossRef

49.

Zhao, H., Chan, T., Merriman, B., Osher, S.J.: A variational level set approach to multiphase motion. J. Comput. Phys. 127, 179–195 (1996)MathSciNetMATHCrossRef

Title: A Brief Survey on Semi-Lagrangian Schemes for Image Processing
Authors: Elisabetta Carlini
Maurizio Falcone
Adriano Festa
Publisher: Springer Berlin Heidelberg
Book: Innovations for Shape Analysis
Print ISBN: 978-3-642-34140-3

Electronic ISBN: 978-3-642-34141-0

Copyright Year: 2013
DOI: https://doi.org/10.1007/978-3-642-34141-0_9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner