A New Conceptually Attractive and Computationally Effective Approach to Shape From Shading

A NEW CONCEPTUALLY ATTRACTIVE & COMPUTATIONALLY EFFECTIVE APPROACH TO SHAPE FROM SHADING

B. Cernuschi-Frias, R. M. Bolle and D. B. Cooper

Brown University, Division of Engineering, Providence, RI 02912

ABSTRACT

A conceptually new, computationally simple approach to shape from shading is presented. It is assumed that objects of interest in 3-D space can be approximated by chunks of spheres, cylinders and planes, and that the formation of the true image can be modelled as the scattering from a Lambertian surface of light from a distant point source or distributed source. The observed image is modelled as this true image plus a white Gaussian perturbation. To permit parallel processing for computational speed, an image is partitioned into many small square windows (image patches) that can be processed simultaneously. It is assumed that a chunk of only one object type (plane, cylinder, sphere) is seen in a patch. Two kinds of results are presented. The first result is an algorithm for the recognition of the object type seen within a patch. This algorithm uses constrained 2-D quadric polynomial approximations to the picture function to implement true Bayesian recognitition. The second result is an algorithm for the estimation of the 3-space location (and orientation) of the recognized object seen within a patch. The image is thresholded with many pairs of thresholds and lines constrained to be parallel or ellipses constrained to have the same shapes and orientations are fit to the resulting swaths of data. Three-D location and orientation parameters are estimated from these statistics. The two algorithms are derived from a general formal statistical formulation of the shape from shading problem.

I. OVERVIEW

The ultimate goal of this work is the recognition of a manufactured object and the estimation of its location and orientation in 3-D space, based on the use of a single 2-D image. A priori information of object structure is used, as well as appropriate functions for image formation based on knowledge of camera location and perhaps of the illuminating light source. Our recognition and information extraction approach is based largely on data generation modelling and then the application of Bayesian recognition and roughly maximum likelihood estimation. The approach is robust to deviations from the assumed models and is computationally attractive. In this paper, we concentrate on the subproblem of object type rec~gnition and object 3-D parameters estimation based on an image patch--the· data in a single window. The patches are sufficiently large to contain important structural information, but are sufficiently small to permit simple processing. The information extracted simultaneously from many such patches must then be used to make reliable inferences concerning the object that is composed of the chunks of planes, cylinders and spheres seen. Section II describes experimental results on extracting information from a patch. Section III contains a brief introduction to our general formulation, and points out how the algorithms for extracting information from a patch come from this general formulation.

-----This work was partially supported by Army Research office grants #DAAG29-81-G-0124 and DAAG29-81-K-0167 and by the National Science Foundation grant #ECS-8119676.

II. EXPERIMENTAL RESULTS

The two results briefly described are typical of those observed in experimentation with the algorithms. Figure la is an image of a portion of a sphere taken with a vidicon camera in a room illuminated by standard ceiling mounted fluorescent tubes behind diffusers. Three data swaths can be seen in Figure lb. Each swath consists of pixels having image intensities lying between a specific pair of thresholds. An ellipse has been fit to each swath. The elliptic shape of the data swaths occurs because the contours of constant image intensity associated with the sphere are ellipses when the light source is a point source, and are approximately ellipses for a distributed source such as the ceiling fixtures commonly encountered. A new twist arising here is that the ellipse fitting has been constrained such that all ellipses have the same shape and orientation. In practice, many pairs of thresholds and associated data swaths

and fitted ellipses are involved.

The elliptic curve fitting is computationally simple and involves constrained least squares curve fitting. The location of the projection of the sphere center on the image plane can be estimated from the ellipse parameters. Though less computation is required if the sphere radius and

source direction are known, these parameters can be a priori unknown and everything can be estimated from the fitted ellipses. For the image of a cylinder, contours of constant image intensity are parallel straight lines, and an analogous constrained least squares line fitting algorithm can be used to fit parallel lines to data swaths resulting from thresholding the image.

Figure 2a is an image of a cylinder (a can) taken with the same set-up as used for the sphere. Figure 2b shows the image partitioned into patches along with the 3-D object shape-type classifications. The symbols p, c, s, m, stand for plane, cylinder, sphere, and mixed. Mixed pat ches are those which are views of two or more surfaceshape-types. The decisions are based on partially unknown 3-D surface shape parameters, because object orientation and location are a priori unknown. Each image patch in Figure 2b is a constrained 2-D polynomial fit to the raw image data in the window. The polynomial fit is constrained to be appropriate for data arising from a 3-D planar surface, a cylindrical surface, a spherical surface, or two surfaces, respectively. The 3-D cylinder viewed is slightly crushed where it is held by a clamp.

III. PICTURE FUNCTION ASSOCIATED WITH A PATCH OF 3-D OBJECT SURFACE

The true picture function g(x,y), at pixel (x,y), for the 3-D quadric surfaces of interest satisfies Eq. (1) when no noise or other perturbations are present.

There will be constraints among the/Ji depending on the 3-D surface shape being viewed. The~i are functions of the 3-D surface shape parameters, of the angle and intensity of the incident illumination, of the 3-D surface reflection properties, and of the viewer to object distance and direction. Denote Plane, Cylinder, and Sphere as 3-D shape type 1, 2, 3, respectively. Then, for example, Eq. (1) takes the form [1]

for shape type 2(cylinder). Here, K = Ipwith I the intensity of the incident illumination and P the surface reflection coefficient. v1, v2, v3 are the components of a unit column vector v lying along the cylinder axis, and u1, u2, u3-are the components of the unit vector u pointing from the distant point source to the cylinder. If the observed image is this picture function plus additive white Gaussian noise having mean 0 and variance~2, the joint likelihood of an image patch and that the patch is a view of a 3-D surface of type k is p(patch, type k)

is the mean value function for g(x,y) under the assumption that 3-D shape type k is seen;~k is the vector of unknown parameters, e.g., fork= 3, ~k consists of sphere center location parameters and any other unknowns such as perhaps unknown source-direction. The ~i in (1) and mk(x,y),are partially unknown coefficients that are determined by known parameters and by the vector ~k of unknown parameters; Pk~k) is an a priori probability density function forO( k· and Pk is the a priori probability that the - image patch is a view of 3-D shape type k. Bayesian recognition of object shape type is made by choosing that k for which (3) is a maximum. A maximum a posteriori estimate of the unknown vector parameter~ k given the image patch and the fact that it is a view of a chunk of an object of shape type k is that value of~k for which the integrand of (3) is a maxi mum.

The integral in (3) is impossible to compute exactly, but in general if there are many pixels i n the image patch, the exponential in (3) is a Gaussian function of ~k about the maximum likelihood estimate l;(k, the value of 0( at which the exponential achieveS" a maximum. Usingkthis approximation, a simple closed form expression can be derived analytically for the integral (3). Let ~T = (1, (iJl, fJ2, ... 'fl,) = (1, 1!._) and uT = (g2,gx, ··· , y, 1) = (g2, vT). Eq. (1) is wTu -;; 0 · An approximation to the MLE estimator! k-f-;;r (3) can be had by solving for the value of~ k for which (4) is a minimum

x,y,g(x,y)EPatch It can be shown that (4) can be expressed as

where R = L yy_T and~ is the coefficient vector for

x,y,g(x,y)EPatch

the unconstrained least squares approximation and is given by p- -rlZ: g2(x,y)~. - x,y,g~Patch

Of great importance in (5) is that the coefficient vector that minimizes (5) and is constrained to be appropriate to the image of an object of type k can be computed by minimizing the last term on the right side of (5), i.e., the quadratic form. This minimization takes place in the 9-dimensional space and does not involve the picture functio~ a significant computational simplification.

Even though the computations required by (5) and (3) are now feasible, further approximation is possible and results in algorithms that are both computationally simple and extremely effective for recognition, and location and orientation estimation.

IV. 3-D OBJECT RECOGNITION

If the window size is roughly between one fifth to one half the diameter of the image of a cylinder or a sphere, a quadric polynomial approximation to the mean value function ffik(x,y) is extremely effective. Then Eq. (3) simplifies further and the Bayesian recognition rule becomes: choose that k* for which

Here, a is the unconstrained least squares error coefficient vector for the approximation of the image patch by a sum of 2-D orthonormal polynomials up through 2nd degree in x and y. ~* is the coefficient vector that is a best fit to a and satisfies a constraint appropriate to the-image for object type k. ik* is an integer constant appropriate to the image constraints associated with object type k, and n is the nwnber of pixels in the image patch. For example, J1 = 1, )2 = 10, }3 = 14. See [1] for more de t ai l.

V. 3-D OBJECT LOCATION AND ORIENTATION ESTIMATION

Computationaly-simple, good, approximate maximwn-likelihood estimates of~ satisfying the image constraints for object type k can be obtained. We illustrate the approach for a sphere. Eq. (4) can be rewritten as e= L ~ L_[/14x2+Psxy+,96y2

I

L x,y such that

over all levels g(x,y) = I

(Note, that if no additive noise is present, then for each intensity level I the summand in (6) if set equal to 0 is an ellipse; the ellipses for the various levels all have the same orientation and same ratio of major to minor axes; the ellipse centers lie on a line; and ellipse size varies quadratically). If the direction of the .light source is known, ~4, t?s, >96 are known and only the~I 1 1, ;I 2 andPr,3 must be estimated. Otherw1se, ail parameters must and can be estimated. Though the optimal approach is to estimate all the /li simultaneously, our suboptimal approach is to estimate the new set of coefficients P4, /!Js, 176, Prd , PI 2 Pr. 3 for one I level at a time ---but subj~ct t~ the constraint that the estimates for 4, 5, 6 must be the same for all I levels. The required computation is greatly reduced in this way. Additional computational savings can be had by using the data associated with only a subset of the !-levels. Then 3-D object location parameters and other 3-D unknowns can be solved for using the coefficient found in (6). See [2] for more detail.

FIG. 2a