Abstract
The method described here for recovering the shape of a surface from a shaded image can deal with complex, wrinkled surfaces. Integrability can be enforced easily because both surface height and gradient are represented. (A gradient field is integrable if it is the gradient of some surface height function.) The robustness of the method stems in part from linearization of the reflectance map about the current estimate of the surface orientation at each picture cell. (The reflectance map gives the dependence of scene radiance on surface orientation.) The new scheme can find an exact solution of a given shape-from-shading problem even though a regularizing term is included. The reason is that the penalty term is needed only to stabilize the iterative scheme when it is far from the correct solution; it can be turned off as the solution is approached. This is a reflection of the fact that shape-from-shading problems are not ill posed when boundary conditions are available, or when the image contains singular points.
This article includes a review of previous work on shape from shading and photoclinometry. Novel features of the new scheme are introduced one at a time to make it easier to see what each contributes. Included is a discussion of implementation details that are important if exact algebraic solutions of synthetic shape-from-shading problems are to be obtained. The hope is that better performance on synthetic data will lead to better performance on real data.
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
I.E. Abdou and K.Y. Wong, “Analysis of linear interpolation schemes for bilevel image applications,” IBM J. Res. Develop. 26(6):667–686, 1982 (see appendix).
R. Bernstein, “Digital image processing of earth observation sensor data,” IBM J. Res. Develop. 20(1):40–57, 1976 (see appendix).
A. Blake, A. Zisserman, and G. Knowles, “Surface descriptions from stereo and shading,” Image Vision Comput. 3(4):183–191, 1985. Also in Horn and Brooks, 1989.
W.J. Bonner and R.A. Schmall, “A photometric technique for determining planetary slopes from orbital photographs,” U.S. Geological Survey Professional Paper 812-A, pp. 1–16, 1973.
A. Brandt, “Multi-level adaptive solutions to boundary-value problems,” Mathematics of Computation 31(138):333–390, 1977.
A. Brandt, “Stages in developing multigrid solutions.” In E. Absi, R. Glowinski, P. Lascaux, and H. Veysseyre (eds.), Numerical Methods for Engineering. Dunod: Paris, pp. 23–44, 1980.
A. Brandt, “Multigrid techniques: 1984 guide with applications to fluid dynamics,” monograph available as GMD-Studie No. 85, from GMD-FIT, Postfach 1240, D-2505, St. Augustin 1, West Germany, 1984.
A. Brandt and N. Dinar, “Multigrid solutions of elliptic flow problems.” In S.V. Parter (ed.), Numerical Methods for PDE. Academic Press: New York, 1979.
M.J. Brooks, “Two results concerning ambiguity in shape from shading,” Proc. Nat. Conf. Artif. Intell., pp. 36–39, Washington, D.C., August 22–26, 1983.
M.J. Brooks, personal communication, 1985.
M.J. Brooks and B.K.P. Horn, “Shape and source from shading,” Proc. Intern. Joint Conf. Artif. Intell., pp. 932–936, Los Angeles, August 18–23, 1985. Also in Horn and Brooks, 1989.
A.R. Bruss “The Eikonal equation: Some results applicable to computer vision,” J. Physics 23(5):890–896, 1982. Also in Horn and Brooks, 1989.
R. Courant and D. Hilbert, Methods of Mathematical Physics, vol. I. Wiley: New York, 1953.
R. Courant and D. Hilbert, Methods of Mathematical Physics, vol. II. Wiley: New York, 1962.
P.A. Davis, and A.S. McEwen, “Photoclinometry: Analysis of inherent errors and implications for topographic measurement,” 15th Lunar and Planetary Science Conf. pp. 194–195, March 12–16, 1984.
P.A. Davis and L.A. Soderblom, “Rapid extraction of relative topography from Viking Orbiter images: II. Application to irregular topographic features,” Reports on Planetary Geology Program, NASA Technical Memorandum 86246, pp. 29–30, 1983.
P.A. Davis and L.A. Soderblom, “Modeling crater topography and albedo from monoscopic Viking Orbiter images: I. Methodology,” J. Geophys. Res. 89(B11):9449–9457, 1984.
P.A. Davis, L.A. Soderblom, and E.M. Eliason, “Rapid estimation of Martian topography from Viking Orbiter image photometry,” Reports on Planetary Geology Program, NASA Technical Memorandum 85127, pp. 331–332, 1982.
P. Deift and J. Sylvester, “Some remarks on the shape-from-shading problem in computer vision,” J. Math. Anal. Appl. 84(1):235–248, 1981.
R.T. Frankot and R. Chellappa, “A method for enforcing integrability in shape from shading algorithms,” IEEE Trans. Pattern Anal. Mach. Intell. 10(4):439–451, 1988. Also in Horn and Brooks, 1989.
P.R. Garabedian, Partial Differential Equations, Wiley: New York, 1964.
W. Hackbush, Multigrid Methods and Applications, Springer-Verlag: Berlin, 1985.
W. Hackbush and U. Trottenberg (eds.), Multigrid Methods. Springer-Verlag, Berlin, 1982.
B.W. Hapke, “A theoretical photometric function for the lunar surface,” J. Geophys. Res. 68(15):4571–4586, 1963.
B.W. Hapke, “An improved theoretical lunar photometric function,” Astronomical Journal 71(5):333–339, 1965.
B.W. Hapke, “Bidirectional reflectance spectroscopy: (1) Theory,” J. Geophys. Res. 86(B4):3039–3054, 1981.
B.W. Hapke, “Bidirectional reflectance spectroscopy: (3) Correction for macroscopic roughness,” Icarus 59:41–59, 1984.
B.W. Hapke and E. Wells, “Bidirectional reflectance spectroscopy: (2) Experiments and observations,” J. Geophys. Res. 86(B4):3055–3060, 1981.
J.G. Harris, “The coupled depth/slope approach to surface reconstruction.” S.M. Thesis, Department of Electrical Engineering and Computer Science, MIT, 1986. Also Technical Report 908, Artificial Intelligence Laboratory, MIT, Cambridge, MA, 1986.
J.G. Harris, “A new approach to surface reconstruction: The coupled depth/slope model,” Proc. Intern. Conf. Comput. Vision, pp. 277–283, London, June 8–11, 1987.
B.K.P. Horn, “Shape from shading: A method for obtaining the shape of a smooth opaque object from one view.” Ph.D. Thesis, Department of Electrical Engineering, MIT, 1970. Also Technical Report TR-79, Project MAC, MIT, Cambridge, MA. Also Technical Report TR-232, Artificial Intelligence Laboratory, MIT, Cambridge, MA, 1970.
B.K.P. Horn, “Obtaining shape from shading information.” In P.H. Winston (ed.), The Psychology of Computer Vision, McGraw Hill: New York, 1975, pp. 115–155. Also in Horn and Brooks, 1989.
B.K.P. Horn, “Understanding image intensities (sic),” Artificial Intelligence 8(2):201–231, 1977. Also in M.A. Fischler and O. Firschein (eds.), Readings in Computer Vision, pp. 45–60, Kaufmann: Los Altos, CA, 1987.
B.K.P. Horn, “Hill shading and the reflectance map,” Proc. IEEE 69(1):14–47, 1981. Also in Geo-Processing 2(1):65–146, 1982, and “Automatic hill-shading and the reflectance map,” Image Understanding Workshop, pp. 79–120, Palo Alto, CA, April 24–25, 1979.
B.K.P. Horn, “Extended Gaussian images,” Proc. IEEE 72(12):1671–1686, 1984.
B.K.P. Horn, Robot Vision. MIT Press: Cambridge, MA; and McGraw-Hill: New York, 1986.
B.K.P. Horn, “Parallel analog networks for machine vision,” memo 1071, Artificial Intelligence Laboratory, MIT, Cambridge, MA, December 1988.
B.K.P. Horn and B.L. Bachman, “Using synthetic images to register real images with surface models,” Communications of the ACM 21(11):914–924, 1978. Also “Registering real images using synthetic images.” In P.H. Winston, and R.H. Brown (eds.), Artificial Intelligence: An MIT Perspective, vol. II, pp. 129–160, MIT Press: Cambridge, MA, 1978.
B.K.P. Horn and M.J. Brooks, “The variational approach to shape from shading,” Comput. Vision, Graph. Image Process 33(2):174–208, 1986. Also in Horn and Brooks, 1989.
B.K.P. Horn and M.J. Brooks (eds.), Shape from Shading. MIT Press: Cambridge, MA, 1989.
B.K.P. Horn and B.G. Schunk, “Determining optical flow,” Artificial Intelligence 17(3):185–203, 1981. Also Memo 572, Artificial Intelligence Laboratory, MIT, Cambridge, MA, April 1980.
B.K.P. Horn, and R.W. Sjoberg, “Calculating the reflectance map,” Applied Optics, 18(11):1770–1779, June 1979. Also in Horn and Brooks, 1989.
B.K.P. Horn, R. Szeliski, and A.L. Yuille, “Impossible shaded images,” submitted to IEEE Trans. PAMI, 1989.
A.D. Howard, K.R. Blasius, and J.A. Cutt, “Photoclinometric determination of the topography of the Martian North Polar Cap,” Icarus 50:2455–258, 1982.
K. Ikeuchi, “Reconstructing a depth map from intensity maps,” Intern. Conf. Pattern Recog. pp. 736–738, Montreal, July 30–August 2, 1984. Also “Constructing a depth map from images,” Memo 744, Artificial Intelligence Laboratory, MIT, Cambridge, MA, August 1983.
K. Ikeuchi and B.K.P. Horn, “Numerical shape from shading and occluding boundaries,” Artificial Intelligence 17(3):141–184, 1981. Also in Horn and Brooks, 1989.
F. John, Partial Differential Equations. Springer-Verlag: Berlin, 1978.
R.G. Keys, “Cubic convolution interpolation for digital image processing,” IEEE Trans. Acoust., Speech Signal Process. 29(6):1153–1160, 1981.
R.L. Kirk, “A finite-element approach to two-dimensional photoclinometry,” Abstract in Bull. Amer. Astronom. Soc. 16(3):709, 1984.
R.L. Kirk, “A fast finite-element algorithm for two-dimensional photoclinometry.” Part III of Ph.D Thesis, Division of Geological and Planetary Sciences, California Institute of Technology, Pasadena, CA, 1987.
J.J. Koenderink and A.J. van Doorn, “Photometric invariants related to solid shape,” Optica Acta 27(7):981–996, 1980. Also in Horn and Brooks, 1989.
J.J. Lambiotte and G.R. Taylor, “A photometric technique for deriving slopes from lunar orbiter photography,” Proc. Conf. Use of Space Systems for Planetary Geology and Geophysics, Boston, MA, May 25–27, 1967.
C.-H. Lee and A. Rosenfeld, “Improved methods of estimating shape from shading using the light source coordinate system” Artificial Intelligence 26(2):125–143, 1985. Also in Horn and Brooks, 1989.
D. Lee, “Algorithms for shape from shading and occluding boundaries,” Proc. IEEE Conf. Comput. Vision Pattern Recog., pp. 478–485, Ann Arbor, MI, June 5–9, 1988. Also in Horn and Brooks, 1989.
B.K. Lucchitta and N.A. Gambell, “Evaluation of photoclinometric profile determination.” In Analysis of Apollo 8 Photographs and Visual Observations, NASA SP-201, National Aeronautics and Space Administration, pp. 51–59, 1970.
J. Malik and D. Maydan, “Recovering three dimensional shape from a single image of curved objects,” IEEE Trans. Pattern Anal. Mach. Intell. 11(6):555–566, 1989. Also in Horn and Brooks, 1989.
M.C. Malin and G.E. Danielson, “Topography on Ganymede derived from photoclinometry” Reports on Planetary Geology Program, NASA Technical Memorandum 86246, pp. 29–30, 1983.
A.S. McEwen, “Topography and albedo of Ius Chasma, Mars,” 16th Lunar and Planetary Sci. Conf. pp. 528–529, March 11–15, 1985.
E. Mingolla and J.T. Todd (1986), Perception of solid shape from shading,” Biological Cybernetics 53: 137–151. Also in Horn and Brooks, 1989.
M. Minnaert, “Photometry of the moon.” In G.P. Kuiper and B.M. Middlehurst (eds.), Planets and Satellites: The Solar System, vol. 3, ch. 6, pp. 213–248, University of Chicago Press: Chicago, 1961.
Q.R. Passey and E.M. Shoemaker, “Craters and basins on Ganymede and Callisto: Morphological indicators of crustal evolution.” In D. Morrison, (ed.), Satellites of Jupiter, pp. 379–434, University of Arizona Press: Tucson, 1982.
A.P. Pentland, “Local shading analysis,”IEEE Trans. Pattern Anal. Mach. Intell. 6(2):170–187, 1984. Also in Horn and Brooks, 1989.
A.P. Pentland, “Shape information from shading: A theory about human perception,” Technical Report 103, Vision Sciences, MIT Media Laboratory, MIT, Cambridge, MA, May 1988.
S.S. Rifman and D.M. McKinnon, “Evaluation of digital correction techniques—for ERTS images,” Report Number E74-10792, TRW Systems Group, July, 1974 (see ch. 4). Also Final Report TRW 20634-6003-TU-00, NASA Goddard Space Flight Center.
T. Rindfleisch, “Photometric method for lunar topography,” Photogrammetric Engineering 32(2): 262–277, March 1966. Also “A photometric method for deriving lunar topographic information,” Technical Report 32–786, Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA, September 1965.
L.C. Rowan, J.F. McCauley and E.A. Holm, “Lunar terrain mapping and relative roughness analysis,” U.S. Geological Survey Professional Paper 599-G, pp. 1–32, 1971.
B.V.H. Saxberg, “A modern differential geometric approach to shape from shading,” Ph.D. Thesis, Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA, 1988.
M. Shao, T. Simchony, and R. Chellappa, “New algorithms for reconstruction of a 3-D depth map from one of more images,” Proc. IEEE Conf. Comput. Vision Pattern Recog. Ann Arbor, MI, June 5–9, pp. 530–535, 1988.
T. Simchony, R. Chellappa, and M. Shao, “Direct analytical methods for solving Poisson equations in computer vision problems.” Published report, University of Southern California, 1989. Also in IEEE Comput. Soc. Workshop on Comput. Vision, Miami Beach, FL, November 1989.
R.W. Sjoberg and B.K.P. Horn, “Atmospheric effects in satellite imaging of mountainous terrain,” Applied Optics 22(11):1702–1716, 1983.
S.W. Squyres, “The topography of Ganymede's grooved terrain,” Icarus 46:156–168, 1981.
T. Strat, “A numerical method for shape from shading for a single image.” SM Thesis, Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA, 1979.
K. Sugihara, Machine Interpretation of Line Drawings, MIT Press: Cambridge, MA, ch. 10, 1986.
D. Terzopoulos, “Multilevel computational processes for visual surface reconstruction,” Comput. Vision, Graph. Image Process. 24:52–96, 1983. Also “Multi-level reconstruction of visual surfaces: variational principles and finite element representation,” Memo 671, Artificial Intelligence Laboratory, MIT, Cambridge, MA, April 1982.
D. Terzopoulos, “Multigrid relaxation methods and the analysis of lightness, shading, and flow,” Memo 803, Artificial Intelligence Laboratory, MIT, Cambridge, MA, October 1984. Also in S. Ullman and W. Richards (ededs.), Image Understanding 84. Ablex Publishing Corporation: Norwood, NJ, ch. 10, pp. 225–262, 1984.
G.L. Tyler, R.A. Simpson, and H.J. Moore, “Lunar slope distributions: Comparison of bi-static radar and photographic results,” J. Geophys. Res. 76(11):2790–2795, 1971.
K. Watson, “Photoclinometry from spacecraft images,” U.S. Geological Survey Professional Paper 599-B, pp. 1–10, 1968.
R.L. Wildey, “Generalized photoclinometry for Mariner 9,” Icarus 25:613–626, 1975.
R.L. Wildey, “Topography from single radar images,” Science, 224:153–156, April 1984.
R.L. Wildey, “Radarclinometry for the Venus radar mapper,” Photogram. Engineer. Remote Sens. 52(1):41–50, 1986. Also in Horn and Brooks, 1989.
D.E. Wilhelms, “A photometric technqiue for measurement of lunar slopes,” Astrogeological Studies Annual Progress Report, Part D: Studies for Space Flight Program. U.S. Geological Survey Open-File Report, pp. 1–12, NASA Catalog Number N66 35597, May 1964.
L. Wilson, M.A. Brown, E.M. Parmentier, and J.W. Head, “Theoretical aspects of photoclinometry terrain profiling on the Galilean satellites,” Reports on Planetary Geology Program, NASA Technical Memorandum 86246, pp. 27–28, 1983.
L. Wilson, J.S. Hampton, and H.C. Balen, “Photoclinometry of terrestrial and planetary surfaces,” 16th Lunar and Planetary Sci. Conf. pp. 912–913, March 11–15, 1985.
R.J. Woodham, “A cooperative algorithm for determining surface orientation from a single view,” Intern. Joint Conf. Artif. Intell., pp. 635–641, Cambridge, MA, August 22–25, 1977.
R.J. Woodham, “Photometric stereo: A reflectance map technique for determining surface orientation from a single view,” Proc. Soc. Photo-Optical Instrument. Engin. 155:136–143, 1978.
R.J. Woodham, “Analyzing curved surfaces using reflectance map techniques.” In P.H. Winston and R.H. Brown (eds.), Artificial Intelligence: An MIT Perspective (Volume II), MIT Press: Cambridge, MA, vol. II, pp. 161–184, 1979.
R.J. Woodham, “Photometric method for determining surface orientation from multiple images,” Optical Engineering 19(1):139–144. 1980a. Also in Horn and Brooks, 1989.
R.J. Woodham, “Using terrain digital data to model image formation in remote sensing,” Image Process. Guidance, SPIE 238:361–369, 1980b.
R.J. Woodham, “Determining surface curvature with photometric stereo,” Proc. IEEE Conf. Robotics Automat., May 14–19, 1989.
Additional information
Massachusetts Institute of Technology
Rights and permissions
About this article
Cite this article
Horn, B.K.P. Height and gradient from shading. Int J Comput Vision 5, 37–75 (1990). https://doi.org/10.1007/BF00056771
Issue Date:
DOI: https://doi.org/10.1007/BF00056771