Geodesic
Numerical algorithms for perspective shape from shading
Kybernetika, Tome 46 (2010) no. 2, pp. 207-225 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

The Shape-From-Shading (SFS) problem is a fundamental and classic problem in computer vision. It amounts to compute the 3-D depth of objects in a single given 2-D image. This is done by exploiting information about the illumination and the image brightness. We deal with a recent model for Perspective SFS (PSFS) for Lambertian surfaces. It is defined by a Hamilton–Jacobi equation and complemented by state constraints boundary conditions. In this paper we investigate and compare three state-of-the-art numerical approaches. We begin with a presentation of the methods. Then we discuss the use of some acceleration techniques, including cascading multigrid, for all the tested algorithms. The main goal of our paper is to analyze and compare recent solvers for the PSFS problem proposed in the literature.
The Shape-From-Shading (SFS) problem is a fundamental and classic problem in computer vision. It amounts to compute the 3-D depth of objects in a single given 2-D image. This is done by exploiting information about the illumination and the image brightness. We deal with a recent model for Perspective SFS (PSFS) for Lambertian surfaces. It is defined by a Hamilton–Jacobi equation and complemented by state constraints boundary conditions. In this paper we investigate and compare three state-of-the-art numerical approaches. We begin with a presentation of the methods. Then we discuss the use of some acceleration techniques, including cascading multigrid, for all the tested algorithms. The main goal of our paper is to analyze and compare recent solvers for the PSFS problem proposed in the literature.
Classification : 35L60, 65D19, 65N06, 65N12, 68T45, 68U10
Keywords: hyperbolic partial differential equation; Hamilton–Jacobi equation; finite difference method; semi-Lagrangian scheme; Shape-from-Shading 
@article{KYB_2010_46_2_a1,
     author = {Breuss, Michael and Cristiani, Emiliano and Durou, Jean-Denis and Falcone, Maurizio and Vogel, Oliver},
     title = {Numerical algorithms for perspective shape from shading},
     journal = {Kybernetika},
     pages = {207--225},
     year = {2010},
     volume = {46},
     number = {2},
     mrnumber = {2663598},
     zbl = {1198.68266},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2010_46_2_a1/}
}
TY  - JOUR
AU  - Breuss, Michael
AU  - Cristiani, Emiliano
AU  - Durou, Jean-Denis
AU  - Falcone, Maurizio
AU  - Vogel, Oliver
TI  - Numerical algorithms for perspective shape from shading
JO  - Kybernetika
PY  - 2010
SP  - 207
EP  - 225
VL  - 46
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/KYB_2010_46_2_a1/
LA  - en
ID  - KYB_2010_46_2_a1
ER  - 
%0 Journal Article
%A Breuss, Michael
%A Cristiani, Emiliano
%A Durou, Jean-Denis
%A Falcone, Maurizio
%A Vogel, Oliver
%T Numerical algorithms for perspective shape from shading
%J Kybernetika
%D 2010
%P 207-225
%V 46
%N 2
%U http://geodesic.mathdoc.fr/item/KYB_2010_46_2_a1/
%G en
%F KYB_2010_46_2_a1
Breuss, Michael; Cristiani, Emiliano; Durou, Jean-Denis; Falcone, Maurizio; Vogel, Oliver. Numerical algorithms for perspective shape from shading. Kybernetika, Tome 46 (2010) no. 2, pp. 207-225. http://geodesic.mathdoc.fr/item/KYB_2010_46_2_a1/

[1] Bornemann, F., Deuflhard, P.: Cascadic multigrid methods. In: Domain Decomposition Methods in Sciences and Engineering (R. Glowinski, J. Periaux, Z. Shi, and O. Widlund, eds.), John Wiley, New York 1997, pp. 205–212. | MR

[2] Breuß, M., Vogel, O., Weickert, J.: Efficient numerical techniques for perspective shape from shading. In: Proc. Algoritmy 2009, Podbanské 2009 (A. Handlovičová, P. Frolkovič, K. Mikula, and D. Ševcovič, eds.), Slovak University of Technology, Bratislava 2009, pp. 11–20.

[3] Camilli, F., Prados, E.: Shape-from-Shading with discontinuous image brightness. Appl. Numer. Math. 56 (2006), 9, 1225–1237. | DOI | MR | Zbl

[4] Courteille, F., Crouzil, A., Durou, J.-D, Gurdjos, P.: Towards shape from shading under realistic photographic conditions. In: Proc. 17th Internat. Conf. Patt. Recog. (vol. II), Cambridge 2004, pp. 277–280.

[5] Cristiani, E.: Fast Marching and Semi-Lagrangian Methods for Hamilton–Jacobi Equations with Applications. Ph.D. Thesis, Dipartimento di Metodi e Modelli Matematici per le Scienze Applicate, Università di Roma “La Sapienza”, Rome 2007.

[6] Cristiani, E., Falcone, M., Seghini, A.: Numerical solution of the perspective Shape-from-Shading problem. In: Proc. Control Systems: Theory, Numerics and Applications, Rome 2005. Proceedings of Science (CSTNA2005) 008, http://pos.sissa.it/

[7] Cristiani, E., Falcone, M., Seghini, A.: Some remarks on perspective Shape-from-Shading models. In: Proc. 1st Internat. Conf. Scale Space and Variational Methods in Comput. Vis., Ischia 2007 (F. Sgallari, A. Murli, and N. Paragios, eds., Lecture Notes in Comput. Sci. 4485), Springer, Berlin 2008, pp. 276–287.

[8] Durou, J.-D., Falcone, M., Sagona, M.: Numerical methods for Shape-from-Shading: A new survey with nenchmarks. Comp. Vis. and Image Underst. 109 (2008), 1, 22–43. | DOI

[9] Falcone, M., Ferretti, R.: Semi–Lagrangian schemes for Hamilton–Jacobi equations, discrete representation formulae and Godunov methods. J. Comput. Phys. 175 (2002), 2, 559–575. | DOI | MR | Zbl

[10] Foley, J. D., Dam, A. van, Feiner, S. K., Hughes, J. F.: Computer Graphics: Principles and Practice. Addison–Wesley, Reading 1996.

[11] Hoppe, R. H. W.: Multigrid methods for Hamilton–Jacobi–Bellman equations. Numer. Math. 49 (1986), 2-3, 239–254. | DOI | MR

[12] Horn, B. K. P.: Obtaining shape from shading information. In: The Psychology of Computer Vision (P. H. Winston, ed.), McGraw-Hill, New York 1975, Ch. 4, pp. 115–155. | MR

[13] Horn, B. K. P.: Robot Vision. MIT Press, Cambridge Mass. 1986.

[14] Horn, B. K. P., Brooks, M. J.: Shape from Shading. Artificial Intelligence Series, MIT Press, Cambridge Mass.1989. | MR | Zbl

[15] Okatani, T., Deguchi, K.: Shape reconstruction from an endoscope image by Shape from Shading Technique for a point light source at the projection center. Comp. Vis. and Image Underst. 66 (1997), 2, 119–131. | DOI

[16] Prados, E., Faugeras, O.: “Perspective Shape from Shading” and viscosity solutions. In: Proc. 9th IEEE Internat. Conf. Comp. Vis. (vol. II), Nice 2003, pp. 826–831.

[17] Prados, E., Faugeras, O.: Unifying approaches and removing unrealistic assumptions in Shape From Shading: Mathematics can help. In: Proc. 8th Eur. Conf. Comp. Vis. (vol. IV), Prague 2004, Lecture Notes in Comp. Sci.3024, pp. 141–154. | Zbl

[18] Prados, E., Camilli, F., Faugeras, O.: A unifying and rigorous shape from shading method adapted to realistic data and applications. J. Math. Imag. and Vis. 25 (2006), 3, 307–328. | DOI | MR

[19] Prados, E., Camilli, F., Faugeras, O.: A viscosity solution method for shape-from-shading without image boundary data. M2AN Math. Model. Numer. Anal. 40 (2006), 2, 393–412. | DOI | MR | Zbl

[20] Rosenfeld, A.: Multiresolution Image Processing and Analysis. Springer, Berlin 1984. | Zbl

[21] Rouy, E., Tourin, A.: A Viscosity solutions approach to Shape-from-Shading. SIAM J. Numer. Anal. 29 (1992), 3, 867–884. | DOI | MR | Zbl

[22] Tankus, A., Sochen, N., Yeshurun, Y.: A new perspective [on] Shape-from-Shading. In: Proc. 9th IEEE Internat. Conf. Comp. Vis. (vol. II), Nice 2003, pp. 862–869.

[23] Vogel, O., Breuß, M., Weickert, J.: A direct numerical approach to perspective Shape-from-Shading. In: Proc. Vision, Modeling, and Visualization Workshop 2007, Saarbrücken 2007 (H. Lensch, B. Rosenhahn, H.-P. Seidel, P. Slusallek, and J. Weickert, eds.), pp. 91–100.

[24] Zhang, R., Tsai, P.-S., Cryer, J. E., Shah, M.: Shape from Shading: A survey. IEEE Trans. Patt. Anal. Mach. Intell. 21 (1999), 8, 690–706. | DOI

[25] Zhao, H.: A fast sweeping method for eikonal equations. Math. Comp. 74 (2004), 250, 603–627. | DOI | MR | Zbl