Relating Properties of Surface Curvature to Image Intensity

1. THE Pr:FLECTArJCE t1AP

The apparent brightness of a surface element depends on the orientation of that element rela­ tive to the viewer and the light sources. nifferent surface elements of a nonplanar object will reflect different amounts of light towards an observer as a consequence of their differing attitude in space. A smooth opaque object will thus give rise to a shaded image (i.e., one in l'thich brightness varies spatially) even though the object may be illuminated evenly and covered by a surface r1aterial with uniform optical properties. Shading provides essential information about the object's shape and has been exploited in machine vision [l-8].

• This paper describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the laboratory's artificial intelligence research was provided in part by the Advanced Research Projects 1\gency of the nepartment of nefense under Office of flaval P.esearch Contract N00014-75-C-0643 and in part by the Office of Naval Research under Office of Naval research Contract N00014-77-0389.

A convenient representation for the relation between scene radiance and surface orientation is the "reflectance map", introduced by Horn [4]. A reflectance map R{p.q) gives scene radiance as a function of surface gradient {p,q) in a viewer-centered coordinate system. If z=f(x,y) is the elevation of the surface above a reference plane lying perpendicular to the optical axis of the imaging system, and if x and y are distances in this plane measured parallel to orthogonal coordinate axes in the image, then p and q are the first partial derivatives of z=f(x,y) with respect to x andy:

The reflectance map is usually depicted as a series of contours of constant scene radiance. It can be measured directly using a photo­ goniometer or indirectly from the image of an object of known shape. Alternatively, a reflectance map may be derived from phenomeno­ logical models of surface reflectance or cal­ culated from analytic models of surface micro­ structure. Recently, a unified approach to the specification of surface reflectance in terms of both incident and reflected beam geometry has been proposed [91. The result has been called the bidirectional reflectance-distribu­ tion function (BRDF). The reflectance map, as defined here, can be derived in terms of the BRDF [10].

Figure 1 shows the reflectance map corresponding to the phenomenological model of a perfectly diffuse (lambertian) surface which appears equally bright from all viewing directions. This reflectance map is given explicitly as:

where p is a surface reflectance factor and (ps,qs) is the gradient pointing in the direc­ tion of a single distant point source of illu­ mination. Here, R(p,q) = pcos(i) where i is the angle of incidence. Cos(i) has been expressed as the normalized dot product of the surface normal vector [p,q,-1] and the vector [ps,qs,-1] which points in the direction of illumination.

An ideal imaging device produces image ance proportional to scene radiance. is the image irradiance at image point then the relevant equation is: i rradi­ If I ( x ,y) (X ,y)'

Until recently, the calculation of shape from shading could be performed only by a rather tedious method involving the direct solution of the above nonlinear first-order partial diffe­ rential equation, using something like the method of characteristic strip expansion [3]. Progress has been made in the development of an iterative, local method based on relaxation [5). Both methods, however, embody assumptions about surface curvature.

One can view (1) as a single equation in the two unknowns p and q. In order to determine p and q, additional information must be provided. Knowledge of surface curvature can provide the required additional information.

2. THE IMAGE HESSIAN MATRIX H

Curvature at a point (x,y) on a surface z=f( x,y) can be specified in terms of the two principal radii of curvature r1 and r2 and associated directions [11]. Such a specification corres­ ponds to an object-centered definition of surface curvature. It is convenient for image analysis to specify surface curvature in the same viewer-centered coordinate system used to define the reflectance map R(p,q).

Let H be the matrix given by :

H is the standard Hessian matrix of the function z=f(x,y) [12]. Here, H is called the _:!Inage Hessia~ matrix of the surface z=f(x,y).

One can write the (approximate) equation:

('denotes vector transpose) to illustrate that the matrix H relates a movement [dx,dy] in the image to the corresponding change in surface orientation [dp,dq]. If two linearly indepen­ dent directions [dx1 ,dyl] and [dx2,dy2J and the corresponding [dp1,dq1] and [dp2,dq2] are known, then H is determined by:

Image intensity determines one correspondence. By taking partial derivatives of equation (1) with respect to x andy, two equations are obtained which can be written as the single matrix equation:

(subscripts denote partial differentiation). Thus, (4) can be rewritten as:

Image intensity determines the change in surface orientation corresponding to a movement in the image in the direction given by IRp,Rgl· This observation is the basi·s of Horn's or1ginal methoa for determining shape from shading [3). But, equation (6) still admits an infinite number of solutions. Further constraint on the matrix H is required.

When additional properties of surface curvature are known 'a priori', they can provide the needed constraint on the matrix H. One set of constraints relates to the positive/negative definiteness of H.

Theorem:

An-ob}ect surface z=f(x ,y) is convex/ concave with respect to the viewer if and only if the corresponding image Hessian matrix H is positive semi­ definite/negative semidefinite.

The use of convexity was explored in (5,6]. Another set of c~nstraints relates to the eigen­ value structure of H.

Definition:

Let-z~f\~y) be the equation of a smooth surface and let Al and A2 be the two eigenvalues of the corresponding Hessian matrix Hat image point (xo,Yo). The surface z=f(x,y) is said to be ~n2r_ at (xo.Yo) if and only if Al = A2 = 0. The surface z=f(x,y) is said to be ~.!1_9lt curv~.!! at (x0,y 0 ) if and only if one \but not both) of Al and A 2 is equal to zero. The surface z=f(x,y} is said to be ~o_I:JE_ly_ cur_yed at (x 0 ,y0) if and only if Al and A2 are not equal to zero.

3. PLANAR SURFACES

Objects whose surfaces are planar, as defined above, form the familiar blocksworld polyhedra domain. This is a degenerate case in that both· lx and ly are everywhere zero. Horn has shown, however, that whenever at least three planes meet at a point, the orientation of each plane can be determined using the reflectance map R(p,q) [4]. The technique combines the quanti­ tat i ve approach to interpreting line drawings developed by Hackworth fl3] with the additional constraint provide by image intensity.

4. SINGLY CURVED SURFACES

An important class of surfaces are those that have the property that, through every point on the surface, there passes at least one straight line lying entirely on it. In differential geometry, such a surface is called a ruled surface. The straight 1 ine lying entirely on the surface is called a ~u__!jM. If a ruled surface has the additional property that all points on a given ruling have the same tangent plane, then the surface is called a developable surface (or a torse) [11]. Huffman charmingly refers to developable surfaces as "paper" surfaces and proposes that such surfaces possess a complexity that is midway between that of a completely general surface and that of a plane surface [14].

The notion of a singly curved surface, as defined above, is equivalent to that of a developable surface (except that planar sur­ faces, while certainly developable, will not be considered singly curved). It can now be shown that, from an image analysis point of view, singly curved surfaces do indeed possess a complexity that is between that of a completely general surface and that of a plane surface.

For surfaces expressed in the form z=f(x,y), the equation: 2

is the differential equation characterizing developable surfaces. In the current notation, this equation is equivalent to the equation:

Equation (8) is satisfied at an image point (x,y) if and only if a least one of the eigen­ values of the corresponding His zero at (x,y). For convenience, assume that at least one of Al and A 2 is nonzero at each image point (x,y). (If both eigenvalues of Hare zero for all image points (x,y), then the equation z=f(x,y) describes a plane). Thus, a nonplanar surface z=f(x,y) is developable if and only if it is singly curved.

Let z=f(x,y) be a singly curved surface. Suppose that a point (xo,yo) in the image is known to have gradient (po,q 0 ). Then, the Hessian matrix H at (xo.Yo) 1s completely determined. H is given as the matrix product:

where

and

As above, Ix and Iy denote the first partial derivatives of I{x,y) at (xo,Yo) and RP. and R denote the first partial derivatives of R{p,q~ at (po,qo) 0

Given any initial image point (xo,Yo) known to have gradient (p 0 ,q 0 ), equations {3) and (9) can be used to trace out an arbitrary family of curves on the surface z=f{x,y}. For singly curved surfaces, one is not confined to tracing out characteristics in the direction 1Rp,Rq1 ~s required by Horn's original method for obta1n1ng shape from shading 131.

The fact that H has one zero eigenvalue means that there is one direction of movement in the image which results in no change to surface orientation. This direction is orthogonal to the direction a determined by the vector llx,~yl· The component of any movement ldx~dyl perpend~­ cular to llx,Iyl is in the direct1on of a rul1ng on the surface and thus does not cause a change in gradient {p,q}. The component of fdx,dyj in the direction 1 Ix,Iyl causes a change in gra­ dient ldp,dql in the direction a where the "scale factor" for that change is given by >-.

The gradients (p,q} corresponding to points on an arbitrary singly curved surface z=f(x,y} ~re constrained to lie on a one-parameter curve 1n p-q space. This illustrates that singly curved surfaces possess a complexity midway between that of a planar surface, where surface points map into a single point in p-q space, and that of a completely general surface, where surface points map into a two-parameter region in p-q space.

Figure 2 is the image o~ a right circ~lar co~e of base radius band he1ght a synthes1zed us1ng the reflectance map of figure 1. (For this example, a= 2b.) The gradients cor~esponding to points on a right circular cone l1e on the onP-potro.JIItPt.Pr curvP in p-q spuCP given para­ IIIPI.ric.tlly hy:

where -n/2 , t < TT/2. The parameter t has a physical interpretation. The circular crosssection of the cone can be represented, in cylindrical coordinates, by the function r(e) = 1, where o measures angular position about they-axis. If o is chosen so that o = 0 points in the direction of th~ vie~er, then the parameter t in (10) and (11) 1s th1s angle e.

Figure 3 shows the curve in p-q space determined by (10) and (11) superimposed on the reflectance map used to generate figure 2. There exists a 1-1 continuous mapping between any horizontal intensity profile from figure 2 and the curve in p-q space determined by (10) and (11). Thus, finding the point (p,q) corresponding to any image intensity point I(x,y) =a from figure 2 simplifies to the problem of determining reflec­ tance map values on the curve given by (10) and (11) for which R(p,q} =a. Since all 1-1 con­ tinuous mappings are monotonic, multiple solu­ tions can be resolved by systematically scanning each image line from left to right. The requi­ red ratio b/a can be determined from the boun­ dary contour in figure 2. For singly curved surfaces, image analysis using the reflectance map is straightforward.

5. _(;_~_E_R_A_L.l]I_Q C_O_N_E_S

A generalized cone is defined to be the surface swept out by moving a simple smooth cross­ section r(o) along a straight axis A, at the same time magnifying or contracting it in a smoothly varying way [15]. The concept of a generalized cone has its genesis in the genera­ lized cylinder representation of Agin and Bin­ ford !16]. There, generalized cylinders were used as a convenient representation scheme for "describing complex shapes. In [151, however, the generalized cone emerges not so much as a representation scheme but as an interpretation that is forced if one trjes to develop a theory of how to infer the shape of objects from their si lhouettes.

Some additional terminology is required. Let h(A) be the axial scaling function, where A denotes distance along the A axis. The angle ~ between the axis A and a plane containing a cross-section is called the eccentricity of the cone. ~f ~=n/2, then the cone called a _!'_i_g_h_!. g_e.!l~.r~J..lzed con~. · In addition, if the cross­ section is circular, then the cone is called a rijlht 9eneralized cone with circular cross­ s~e~_ti_o_n~- -- - ---- --- --- ----- ·----

Generalized cones are, in general, doubly curved. The curvature of a generalized cone, however, conveniently decouples in its object-centered representation. For appropriate viewing condi­ tions, this decoupling carries over to images of generalized cones. These images can be analyzed "almost" as if the surface were singly curved, as will now be shown.

Consider a right generalized cone with circular cross-section. Without loss of generality, one can assume that the axis A passes through the center of the circle. For the moment, one addi­ tional assumption is needed. Assume that the axis A is parallel to the image plane. For convenience, let the image X-Y axes be chosen so that A coincides with the image Y-axis. Dis­ tance along the A axis is then equal to distance along the Y-axis so that the axial scaling func­ tion can be denoted as h(y). Further, let the circular cross-section be denoted by r(e) = 1, where e = 0 points in the direction of the viewer. The gradients corresponding to points on such a generalized cone lie in the two­ parameter region in p-q space given parametri­ cally by:

where h'(y) denotes the derivative of h(y) with respect to y and e varies between -n/2 and n/2.

Figure 2 was an example of a right generalized cone with circular cross-section. There, h' (y) = -b/a. In general, (12) and (13) define a two-parameter region in p-q space. The rele­ vant observation, however, is that when the axis A is parallel to the viewing plane, the value of h'(A) can always be determined directly from the boundary contour . In this case, finding the (p,q) corresponding to a given image intensity point I(x,y) = a simplifies to a two step process. First, for the particular y, determine h'(y) as the rate of change of object radius with respect to y (equivalently, as l/2 the rate of change of object diameter with respect to y) at the object boundary along image line y. Second, as in the case of a singly curved object, scan a left to right profile to determine the correct reflectance map point on the curve given by (12) and (13).

Figure 4 illustrates. Here, the axial scaling function is a sinusoid while the cros s-section remains circular. Figure 5 superimposes a collection of the curves given by (12) and (13) on the reflectance map used to generate figure 4. The surface depicted in figure 4 is every­ where doubly curved. Yet from the given viewing direction, the curvature decouples so that, from an image analysis point of view, the surface behaves as if it were single curved.

Suppose now that A is not parallel to the image plane. Nevertheless, the image X-Y axes can still be chosen so that the projection of A coincides with the image Y-axis. Let the angle between the A axis and the viewing plane be ¢ (measured so that positive ¢ implies that A is tilted towards the viewer). In this case, distance along the Y-axis is the foreshortened distance along A given by:

so that

The gradients corresponding to points on such a generalized cone lie in the two-parameter region in p-q space given parametrically by:

where h'(y) and e are as before. If <P is known, then one can proceed as before, with only a slight compl1cation in the mathematical expres­ sions required. If¢ is unknown, two difficul­ ties arise. First, without knowing ¢ , the curve generated by (14) and (15) cannot be determined. Second, without knowing¢, the image profile corresponding to a fixed value of A cannot be determined. At best, it is possible to estimate the value of¢ which is most consistent with the hypothesis that the image corresponds to a right generalized cone with circular cross-section .

Greater difficulty arises when the cross-section is allowed to be an arbitrary smooth convex function. Roughly speaking, it becomes impos­ sible to resolve the trade-off between axis tilt and cross-section shape using the intensity values recorded in a single view. Let the cross-section function be given, in cylindrical coordinates, by r = r(e). To avoid unnecessary complication, suppose once again that the axis A is parallel to the viewing plane. The gra ­ dients corresponding to points on such a gene­ ralized cone lie in the two-parameter region in p-q space given parametrically by

where h'(A) denotes the derivative of h(A) with respect to A and r'(e) denotes the derivative of r( e) with respect to e.

For an arbitrary smooth convex r(e), it is not necessarily true that the "left" boundary con­ tour corresponds to o = -n/2 and the "right" boundary contour to o = n/2. If the left boun­ dary contour corresponds to the value el (where - n < El l < 0) and the right boundary contour corresponds to the value oR (where 0 <oR < n), then h'(>.. ) is given by:

h, (>.. ) = E_a~_~_g_f __ c_tlan_!]_e __ of object diameter sinT-ell + sin(eR)

The information required to determine h'(>..) is still contained in the boundary contour but it can be used only if the values el and eR are known. The values of el and eR, in turn, depend on r(e). Thus, althougn the decoupling between h(>..) and r(e) exists in the cone's object­ centered representation, it is not possible to discover this decoupling from the object sil­ houette.

6. CONC_LUS_l_DBl

Methods for determining shape from the intensity values recorded in a single view embody assump­ tions about surface curvature. Such assumptions may arise from an analysis of boundary contour or from an analysis of intensity gradations across sections of smooth surface. Reflectance ma p techniques help make such assumptions explicit. When properties of surface curvature are known 'a priori', they can be exploited in image analysis.

7. ACIS_N.Q!J.!:_E_D_�~_MENTS

The author would like to thank Berthold K.P. Horn for his help and in_tellectual guidance. Mike Brady, Anni Bruss, Mark Lavin, Tomas Lozano, Alan Hackworth, David Marr and Patrick Winston provided useful comments and criticisms.

The author would also like to thank Theresa Fong for aid in the preparation of this manuscript.

8. REFERENCES -----

• [ 1 J Diggelen, J . van, "A Photometric Investi­ gation of the Slopes and Heights of the Ranges of Hills in the Maria of the t·1oon", Bulletin of the Astronomical Institute of rlie-!i_~therl ands-,July ,195T:""
• Rindfleisch, T., "Photometric method for Lunar Topography", Photogrammetric Engine­ ~ring, pp. 262-276, March, 1966.
• 131 Horn, B.K.P., "Obtaining Shape from Sha­ ding Inforf!la~ion", in I_~ f_2LcholoJy of fQ.!!!P_uter YJSlon, P.H. Winston (ed. , McGraw-Hill, pp. 115-155, New York, 1975.
• Horn, B.K.P., "Understanding Image Inten­ sities", Arti_fj9~llDl~_l_i_g_~_!l_c_~. Vol . 8, No. ll, pp. 201-231, 1977.
• Woodham, R.J., "A Cooperative Algorithm for Determining Surface Orientation from a Single View", IJCAI-77, pp. 635-641, August, 1977. ------
• Woodham, R.J., "Reflectance Map Techniques for Analyzing Surface Defects in Metal Castings", AI-TR-457, M.I.T. Artificial Intelligence Laboratory, M.I.T., Cambndge, Mass. , June, 1978.
• Woodham, R.J., "Photometric Stereo: A Reflectance Map Technique for Determining Surface Ori entation from Image Intensity", Proc .. SPIE ~nd Technical Symposium, Vol. 155, San Diego, Calif., August, 1978.
• t8l Horn, B.K.P., Woodham, R.J. & Silver, W.N., "Determining Shape and Reflectance Using Multiple Images", AI-r~emo-490, M.I.T. Artificial Intelligence Laboratory, M.I.T., Cambridge, Mass., August, 1978.
• Nicodemus, F.E., Rich~ond, J.C. & Hisa, J.J., "Geometrical Considerations and Nomenclature for Reflectance", NBS Mono­ graph 160, National Bureau of Standards, Washington, D.C., October, 1977.
• [1 0] Horn, B.K.P. & Sjoberg, R.W., "Calculating the Reflectance Map", AI-Memo-498, M. I. T. Artificial Intelligence Laboratory, M. I. T., Cambridge, Mass., October, 1978.
• fll] Kepr, B., "Differential Geometry", in Survey of ~licable Mathematics, K. Rectorys(ed.},MTT. Press, pp. 298-373, Cambridge, 1969.
• [121 Luenberger, D.G., Introduction to Linear and Nonlinear Programming, Addison-Wesley, 1973.
• [ 13] Mackworth, A.K., "Interpreting Pictures of Polyhedral Scenes", Artificial Intelli­ gence, Vol. 4, pp. 121-137, 1973. ·
• [ 14] Huffman, D.A., "Curvature and Creases : A Primer on Paper", _proc. Conf. Computer Graphlts, Pattern Recognition and Data Structures, pp. 360-370, May, 1975-.­
• r 1 51 Marr, D. "Analysis of Occluding Contour", Proc. ~Soc. Lond . B., 197, pp. 441-475, 1977. ----
• Agin, G.J. & Binford, T.O., "Computer Description of Curved Objects", Proc. 3r~ IJCAI, pp. 629-640, August, 1973.