Abstract
We describe a mathematical and algorithmic study of the Lambertian “Shape-From-Shading” problem for orthographic and pinhole cameras. Our approach is based upon the notion of viscosity solutions of Hamilton-Jacobi equations. This approach provides a mathematical framework in which we can show that the problem is well-posed (we prove the existence of a solution and we characterize all the solutions). Our contribution is threefold. First, we model the camera both as orthographic and as perspective (pinhole), whereas most authors assume an orthographic projection (see Horn and Brooks (1989) for a survey of the SFS problem up to 1989 and Zhang et al. (1999), Kozera (1998), Durou et al. (2004) for more recent ones); thus we extend the applicability of shape from shading methods to more realistic acquisition models. In particular it extends the work of Prados et al. (2002a) and Rouy and Tourin (1992). We provide some novel mathematical formulations of this problem yielding new partial differential equations. Results about the existence and uniqueness of their solutions are also obtained. Second, by introducing a “generic” Hamiltonian, we define a general framework allowing to deal with both models (orthographic and perspective), thereby simplifying the formalization of the problem. Thanks to this unification, each algorithm we propose can compute numerical solutions corresponding to all the modeling. Third, our work allows us to come up with two new generic algorithms for computing numerical approximations of the “continuous solution of the “Shape-From-Shading” problem as well as a proof of their convergence toward that solution. Moreover, our two generic algorithms are able to deal with discontinuous images as well as images containing black shadows.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bardi, M. and Capuzzo-Dolcetta, I. 1997. Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Birkhauser.
Barles, G. 1994 Solutions de Viscosité des Equations de Hamilton–Jacobi. Springer–Verlag.
Barles, G. and Souganidis, P.E. 1991. Convergence of approximation schemes for fully nonlinear second order equations. Asymptotic Analysis, 4:271–283.
Brooks, M.J., Chojnacki, W., and Kozera, R. 1992. Shading without shape. Quarterly of Applied Mathematics, 50(1):27–38.
Bruckstein, A.M. 1998. On shape fron shading. Computer. Vision Graphics Image Process, 44:139–154.
Bruss, A.R. 1982. The eikonal equation: Some results applicable to computer vision. Journal of Mathematical Physics, 23(5):890–896.
Camilli, F. 2001. A characterization of the value function for a class of degenerate control problems, chapter 3, pages 47–58. Volume 59 of M. Falcone and C. Makridakis (Eds.) Numerical Methods for Viscosity Solutions and Applications, volume 59 of Series on Advances in Mathematics for Applied Sciences.
Camilli, F. and Falcone, M. 1996. An approximation scheme for the maximal solution of the shape-from-shading model. International Conference on Image Processing, pp. 49–52.
Camilli, F. and Siconolfi, A. 1999. Maximal subsolutions for a class of degenerate Hamilton-Jacobi problems. Indiana Univ. Math. J., 48(3):1111–1132.
Camilli, F. and Siconolfi, A. 2003. Hamilton-jacobi equations with measurable dependence on the state variable. Adv. Differential Equations, 8(6):733–768.
Courteille, F., Crouzil, A., Durou, J.-D., and Gurdjos, P. 2004. Shape from Shading en conditions réalistes d'acquisition photographique. In Proceedings of RFIA'04.
Crandall, M.G. 1982. Viscosity solutions of Hamilton–Jacobi equations. In Nonlinear Problems: Present and Future, Proc. 1st Los Alamos Conf., 1981, volume 61, pages 117–125. North-Holland Math. Stud.
Crandall, M.G., Ishii, H., and Lions, P.-L. 1992. User's guide to viscosity solutions of second order partial differential equations. Bull. Amer. Soc., 27:1–67.
Crandall, M.G. and Lions, P.-L. 1983. Viscosity solutions of Hamilton–Jacobi equations. Trans. AMS, 277:1–43.
Danielsson, P.-E. 1980. Euclidean Distance Mapping. Computer Graphics and Image Processing, 14(3):227–248.
Dupuis, P. and Oliensis, J. 1991. Direct method for reconstructing shape from shading. SPIE, 1570:116–128.
Dupuis, P. and Oliensis, J. 1994. An optimal control formulation and related numerical methods for a problem in shape reconstruction. The Annals of Applied Probability, 4(2):287–346.
Durou, J.-D., Falcone, M., and Sagona, M. 2004. A survey of numerical methods for shape from shading. Research report 2004-2-R, IRIT, January.
Durou, J.-D. and Maître, H. 1996. On convergence in the methods of Strat and Smith for shape from shading. The International Journal of Computer Vision, 17(3):273–289.
Durou, J.-D. and Piau, D. 2000. Ambiguous shape from shading with critical points. Journal of Mathematical Imaging and Vision, 12(2):99–108.
Falcone, M. and Makridakis, C. (Eds.) 2001. Numerical Methods for Viscosity Solutions and Applications, volume 59 of Series on Advances in Mathematics for Applied Sciences. World Scientific.
Falcone, M. and Sagona, M. 1997. An algorithm for the global solution of the shape-from-shading model. International Conference on Image Analysis and Processing, 1:596–603, LNCS 1310.
Falcone, M., Sagona, M., and Seghini, A. 2001. A scheme for the shape-from-shading model with "black shadows". In Proceedings of ENUMATH 2001.
Hasegawa, J.K. and Tozzi, C.L. 1996. Shape from shading with perspective projection and camera calibration. Computers and Graphics, 20(3):351–364.
Horn, B.K. and Brooks, M.J. (Eds.) 1989. Shape from Shading. The MIT Press.
Horn, B.K.P. 1975. Obtaining shape from shading information. In P.H. Winston, editor, The Psychology of Computer Vision. McGraw-Hill, New York.
Horn, B.K.P., Szeliski, R.S., and Yuille, A.L. 1993. Impossible shaded images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(2):166–170.
Ishii, A. 1987. A simple, direct proof of uniqueness for solutions of the hamilton-jacobi equations of eikonal type. Proceedings of the American Mathematical Society, pp. 247–251.
Ishii, H. 1985. Hamilton-Jacobi equations with discontinuous hamiltonians on arbitrary open subsets. Bull. Fac. Sci. Engrg. Chuo Univ., 28:33–77.
Ishii, H. 1989. A boundary value problem of the dirichlet type for hamilton-jacobi equations. Ann. Sci. Ecole Norm. Sup., 4(16):105–135.
Ishii, H., and Ramaswamy, M. 1995. Uniqueness results for a class of Hamilton-Jacobi equations with singular coefficients. Comm. Par. Diff. Eq., 20:2187–2213.
Kain, J. and Ostrov, D.N. 2001. Numerical shape-from-shading for discontinuous photographic images. The International Journal of Computer Vision, 44(3):163–173.
Kerautret, B. 2004. A robust discrete approach for shape from shading and photometric stereo. In Proceeding of the International Conference on Computer Vision and Graphics (ICCVG 2004), September 22–24, 2004 Warsaw, Poland..
Kimmel, R. and Bruckstein, A.M. 1995a. “Global shape-from-shading”. CVGIP: Image Understanding, pages 360–369.
Kimmel, R. and Bruckstein, A.M. 1995b. Tracking level sets by level sets : A method for solving the shape from shading problem. Computer Vision and Image Understanding, 62(2):47–58.
Kimmel, R. and Sethian, J.A. 2001. Optimal algorithm for shape from shading and path planning. Journal of Mathematical Imaging and Vision, 14(2):237–244.
Klette, R., Kozera, R., and Schlüns, K. 1998. Shape from shading and photometric stereo methods. Technical Report CITR-TR-20, CITR, University of Auckland, New Zealand.
Kozera, R. 1997. Uniqueness in shape from shading revisited. International Journal of Mathematical Imaging and Vision, 7:123–138.
Kozera, R. 1998. An overview of the shape from shading problem. Machine Graphics and Vision, 7(1–2):291–312.
Lee, K.M. and Kuo, C.C.J. 1994. Shape from shading with perspective projection. CVGIP: Image Understanding, 59(2):202–212.
Lions, P.-L. 1982. Generalized Solutions of Hamilton–Jacobi Equations. Number 69 in Research Notes in Mathematics. Pitman Advanced Publishing Program.
Lions, P.-L., Rouy, E., and Tourin, A. 1993. Shape-from-shading, viscosity solutions and edges. Numer. Math., 64:323–353.
Okatani, T. and Deguchi, K. 1996. Reconstructing Shape from Shading with a Point Light Source at the Projection Center: Shape Reconstruction from an Endoscope Image. In Proceedings of ICPR'96, pages 830–834.
Okatani, T. and Deguchi, K. 1997. Shape reconstruction from an endoscope image by shape from shading technique for a point light source at the projection center. Computer Vision and Image Understanding, 66(2):119–131.
Oliensis, J. 1991. Shape from shading as a partially well–constrained problem. CVGIP: Image Understanding, 54(2):163–183.
Oliensis, J. and Dupuis, P. 1993. A global algorithm for shape from shading. In Proceedings of ICCV'93, pp. 692–701.
Ostrov, D.N. 2000. Extending viscosity solutions to eikonal equations with discontinuous spatial dependence. Nonlinear Anal., 42(4):709–736.
Penna, M.A. 1989a. Local and semi-local shape from shading for a single perspective image of a smooth object. Computer Vision, Graphics, and Image Processing, 46(3):346–366.
Penna, M.A. 1989b. A shape from shading analysis for a single perspective image of a polyhedron. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(6):545–554.
Prados, E. and Faugeras, O. 2001. Une approche du “Shape from Shading” par solutions de viscosité. Master's thesis, University of Nice Sophia-Antipolis, France, INRIA.
Prados, E. and Faugeras, O. 2003a. A mathematical and algorithmic study of the lambertian SFS problem for orthographic and pinhole cameras. Technical Report RR-5005, INRIA.
Prados, E. and Faugeras, O. 2003b. “Perspective Shape from Shading” and viscosity solutions. In Proceedings of the 9th International Conference on Computer Vision, volume 2, pp. 826–831.
Prados, E., Faugeras, O., and Rouy, E. 2002a. Shape from shading and viscosity solutions. In A. Heyden, G. Sparr, M. Nielsen, and P. Johansen, editors, Proceedings of the 7th European Conference on Computer Vision, volume 2351, pages 790–804, Copenhagen, Denmark, Springer–Verlag.
Prados, E., Faugeras, O., and Rouy, E. 2002b. Shape from shading and viscosity solutions. Technical Report 4638, INRIA.
Rouy, E. and Tourin, A. 1992. A Viscosity Solutions Approach to Shape-from-Shading. SIAM Journal of Numerical Analysis, 29(3):867–884.
Samaras, D. and Metaxas, D.N. 1999. Coupled lighting direction and shape estimation from single images. In Proceedings of the 7th International Conference on Computer Vision, volume 2, pages 868–874, Kerkyra, Greece, IEEE Computer Society, IEEE.
Sethian, J.A. 1996. Level Set Methods. Cambridge University Press.
Soravia, P. 2000. Optimal control with discontinuous running cost: eikonal equation and shape from shading. In 39th IEEE Conference on Decision and Control, pages 79–84.
Tankus, A., Sochen, N., and Yeshurun, Y. 2003. A new perspective [on] Shape-from-Shading. In Proceedings of the 9th International Conference on Computer Vision, volume 2, pp. 862–869.
Tankus, A., Sochen, N., and Yeshurun, Y. 2004. Perspective Shape-from-Shading by Fast Marching. In IEEE Conference on Computer Vision and Pattern Recognition, Washington, DC (United States).
Tankus, A., Sochen, N., and Yeshurun, Y. 2005. Shape-from-shading under perspective projection. International Journal of Computer Vision, 63(1):21–43.
Weiss, I. 1997. A perspective 3D formalism for shape from shading. In Proceedings of DARPA Image Understanding Workshop, volume 2, pp. 1393–1402.
Yuen, S.Y., Tsui, Y.Y., Leung, Y.W., and Chen, R.M.M. 2002. Fast marching method for shape from shading under perspective projection. In Proceedings of VIIP'02, pp. 584–589.
Zhang, R., Tsai, P.-S., Cryer, J.-E., and Shah, M. 1999. Shape from Shading: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(8):690–706.
Author information
Authors and Affiliations
Additional information
First online version published in October, 2005
Rights and permissions
About this article
Cite this article
Prados, E., Faugeras, O. A Generic and Provably Convergent Shape-from-Shading Method for Orthographic and Pinhole Cameras. Int J Comput Vision 65, 97–125 (2005). https://doi.org/10.1007/s11263-005-3844-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-005-3844-1