An Extremum Principle for Shape From Contour

1. Introduction

An important goal of early vision is the computation of a rep­ resentation of the visible surfaces in an image, in particular the determination of the orientation of those surfaces as defined by their local surface normals [Brady 1982, Marr 1982). Many processes contribute to achieving this goal. stereopsis and structure-from-motion bei ng the most studied in image understanding. In this paper we consider the computation of shape-from-contour. Figure 1 shows a number of shapes that arc typically perceived as images of surfaces which arc oriented out of the picture plane. The method we propose is based on a preference for symmetric. or at least compact, su rfaces. Note that the contour docs not need to be closed in order to be interpreted as oriented out of the image plane. Also, in general, contours arc interpreted as curved three-dimensional surfaces.

We develop an extremum principle for determining three-­ dimensional surface orientation from a two-dimensional contour. Initially, we work out the extremum principle for the case that the contour is closed and that the interpreted surface is planar. Later, we discuss how to extend our approach to open contours and how to interpret contours as curved surfaces.

The extremum principle maximizes a familiar measure of the compactness or symmetry of an oriented surface, namely the ratio of the area to the square of the perimeter. It is shown that this measure is at the heart of tlte maximum likelihood approach to shapc-from-contom developed by Witkin [1981) and Davis, Janos, and Dunn (1982]. The maximum likelihood approach has had some success interpreting irregularly shaped objects. However, the method is ineffective when the distribution of image tangents is not random, as is the case, for example, when the image is a regular shape, such as an ellipse· or a parallelogram. Our extremum principle interprets regular figures correctly. We show that the maximum likelihood method approximates the extremum principle for irregular figures.

Kanade [1981, page 424) has suggested a method for determin­ ing the three-dimensional orientation of skew-symmetric figures, un­ der the "heuristic assumption" that such figures arc interpreted as oriented real symmetric~. We prove that our extremum principle necessarily interprets skew symmetries as oriented real symmetries, thus dispensing with the need for any heuristic assumption to that utilize the geometric model, but dispense with the second part of the statistical model in favor of an extremum principle.

This report describes research done at the Artificial Intelligence Laboratory of the Massachuscns Institute of Technology. Support for the laboratory's Artificial Intelligence research is provided in pan by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Resear­ ch contract N00014-75-C-0643. the Office of Naval Research under contract oumber NOOI4-80-C-0505. and the System Development Foundation.

First. the geometric model. Suppose that a curve is drawn in the plane (a, r) and denote by {J the angle that the tangent makes at a typic;d poim on the curve. Let a be the tangent angle in the image plane at the point corresponding to {J. Then a and f3 arc related by tan( a - r) = tan(J/cosa.

We now turn to the statistical model. which consists of two assumptions called isalropy and independence. Isotropy reasonably supposes that all surface orientations arc equally likely to occur in nature and that tangents to surface curves arc equally likely in all directions. More succinctly, it is assumed that the quantities (a, r) arc randomly distributed. and that their joint pr·Jbability density function ("density") D(u, r) is given by [Davis, Janos, and Dunn, 1982]

The independence assumption requires that the image tangents

arc statistically independent. That is. it is assumed that the tangent directions at diflcrcnt points on the image curve arc independent This is only true if the contour is highly irregularly shaped, or if the number of samples is small. In any case, the assumption of independence is an inherent weakness of the sampling approach (see for example [Witkin 1981, p 36]).

It is easy to show that the conditional density D(aia,r) of an individual image tangent angle a projected from a plane (a, r) is given by [Witkin 1981]:

Denote the sample (a 1, a2 , ..· an) by A (the sample is independent by assumption). It has conditional density

By Bayes' formula we obtain

Observe that the numerator is independent of a and r. The sampling approach takes a random sample A and defines the most likely orientation of the plane (a,r) to be that which cxtrcmizcs D(a,riA). Witkin [1981] quantizes a and r, and describes an algorithm to find the maximizing (a 1 , rk). Davis, Janos. and Dunn (1982] develop a more efficient algorithm that first estimates (J and r and then uses those estimates in a Newton iterative process. They provide evidence that their method is more accurate than Witkin's. Curiously, however, they state [Davis, Janos, and Dunn 1982, p 24] that "the iterative algorithm was not used [in the experiments t11ey report] because the intitial estimates (whose computation is trivial) arc very accurate and t11e iterative scheme often failed to converge to the solution".

3. Extremum Principles.

Brady and I lorn [1983] survcy the usc of extremum principles in image understanding. The choice of pcrf(Jrmancc index or mca~urc to be cxtremizcd. and the cl;tss of functions over which the cxtrcmization takes place. arc justified by appealing to a model of the geometry or photometry of image limning and constraints such as smoothness. For example, the usc of extremum principles in surface reconstruction is based upon surface consistency theorems [Grimson 1981, Yuille {983] and a thin plate model of visual surfaces [Brady and Horn 1983, Tcrzopoulos 1983]. Brady and Yuille 119831 discuss tl1c relationship between extremum principles and Pracgnanz theories in perceptual psychology.

There arc several plausible measures of a curve tl1at might be extrcmizcd in order to compute shapc-from·contour. Contrary to what appears to be a popular belief, given an ellipse in the image plane, f K 2 ds is no! cxtrcmizcd in the plane that transforms the ellipse into a circle [Brady and Yuille 1983, Appendix A]. Since ellipses are normally perceived as slanted circles, we reject the square curvature as a suitable measure.

Another possible measure is proposed by Barrow and Tenenbaum (1981, p89]. Assuming planarity (the torsion r is zero), it reduces to

The first strong objection to this measure is that it involves high-order derivatives of the curve. This means it is overly dependent on small scale behaviour. Consider, for example, a curve which is circular except for a small kink. The circular part of the curve will contribute a tiny proportion to the integral even when the plane containing t11c curve is rotated. The kink. on the other hand. will contribute an arbitrarily large proportion and so will dominate the integral no matter how small it is compared with tltc rest of the curve. This is clearly undesirable. For example, it suggests that the measure will be highly sensitive to noise in the position and orientation of the points forming the contour.

A second objection lO the measure proposed by narrow and Tenenbaum is tJJat it is minimized by, <Jnd hence has an intrinsic preference for, straight lines. for which dKj ds zero. This means that the measure has a bias towards planes that correspond to the (non­ general) sidcon viewing position. These planes arc perpendicular to t11c image plane and have slant 1r /2.

We base our choice of measure on the following observations.

1. Contours that arc the projection of curves in planes with large slant arc most effective for eliciting a tltrce·dimcnsiunal interpretation.

2. A curve is forcshortcd by projection by the cosine of the slant angle in the tilt direction, and not at all in tl1e orthogonal direction.

We conclude that three-dimensional interpretations arc most readily elicited for shapes that arc highly elongated in one direction. Another way to express this idea is that the im~gc contour has large aspect ratio or is radially asymmetric. The measure we suggest will pick out the plane orientation for which the curve is most compact or most radially symmetric. Specifically, our measure is

This is a scale invariant number characterizing the curve. For all possible curves it is maximized by the most symmetric one, a circle. This gives the measure an upper bound of 1/47r. Its lower bound is clearly zero and it is achieved for a straight line. It follows that our measure has a builtin prejudice against sideon views for which the slant is 1r /2.

In general, given a contour, our extremum principle will choose the orientation in which the dcprojcctcd contour maximizes M , For ex;nnple an ellipse is interpreted as a slanted circle. The tilt angle is given by the major axis of the ellipse. It is also straightforward to show that a parallelogram corresponds to a rotated square. Brady and Yuille [1983, Appendix B] show how several simple shapes are interpreted by the measure. In particular, an ellipse is interpreted as a slan ted circle, a parallelogram as a slanted square, and a triangle as a slanted equilateral triangle. In Section 5 we extend the parallelogram result to the more general case of skewed symmetry.

We note that the quantity M is commonly used in pattern recognition and industrial vision systems [Ballard and Brown 1982) as a feature that measures the compactness of an object. Furthermore, we can show that the measure M defined in Eq. (3.1) is at the heart of the geometric model in the maximum likelihood approach.

From Section 2, we sec that the maximum likelihood approach maximizes the product of a number of terms of form

Differentiating the gcoRlctric model with respect to the arc length s 1 along the image curve and sn along the rotated curve respectively we obtain

where ~<1 and ~<n are the curvature at corresponding points of the image contour and its deprojection in the rotated plane respectively. In fact, ~<1 = dajds 1 and ~<H = d{J jdsfl. There is no u or r dependence in the numerator of equation (3.3). We can write each term 1< ds as ds ds / p ds where p is the radius of curvature. Now observe that p dsjds ds is just a local computation of area divided by perimeter squared! Hence maximizing each f(a) in the maximum likelihood approach is equivalent to locally maximizing area over perimeter squared. In section (4) we will examine this connection more rigorously.

4 . Extremizing the Measure

We now write down the measure for a curve with arbitrary orientation and then cxtremize with respect to the orientation. Let the unit normals to the image plane and the rotated plane be k and n respectively. The slant r> of the rotated plane is given by the scalar . product cos u = k · n.

Let r n and r 1 be the contour in the rotated and image planes. i\ vector r in the image plane satisfies r · k = 0, and is the projection of a vector v in the rotated plane that satisfies v · n = 0. Now r R and r I have (vector) areas AFI and A1 arc related by

We find

In general there is no simple relationship between the perimeters analogous to that holding between the areas. Nevertheless, we have An/Ph= AI/P'kcosu.

and so our extremum principle is equivalent to extremizing cost uPn, which we write as

We extremize this with respect to the micntation n of the rotated plane, maintaining the constraint that n is a unit vector by a Lagrange multiplier A. i\fter algebraic manipulation [Brady and Yuille 1983), this reduces to

where t = dr/ lldrll is the unit tangent to the image contour. Let the unit vectors in the x and y directions in the image plane be i and j and let k be the nonnal to the image plane. The tangent vector t and the normal n can be written:

where a is the tangent angle in the image. We now form the scalar products of equation above with i and j to obtain eventually

to emphasize that they correspond to extrcmizing with respect to u and r.

To conclude this Section, we show that these equations are similar. though not identical, to those obtained by the maximum likelihood method in the limit as the number of sampled tangents tends to infinity. To sec this we recall that this method involves cx­ trcmit.ing D(Aiu, r) with respect to u and r. Since the denominator is independent of u and r, this amounts to cxtrcmizing D(Aiu, r)D(u, r). This is the same as cxtremizing logD(Aiu,r)D(r>,r) . We find

where we have ignored facwrs of rr which will vanish on differentiation. Dividing E by n and t;tking the limit as n tends to infinity gives:

Using the identity:

gives

This formula is similar to Eqs 4.1 and 4.2. Thus we expect the Extremum Method to give similar results to the Sampling Method when the contour is sufficiently irregular. We are currently carrying out experiments to verify this.

5. Skew Symmetry

We now consider a more general class of shapes for which the maximum likelihood approach is not effective. Kanade [1981, sec. 6.2] has introduced skewed symmelries, which arc two-dimensional linear (affine) transfonnations of real symmetries. There is a bijective correspondence between skew symmetries and images of symmetric shapes that lie in planes oriented to the image plane. Kanade proposes the heuristic assumption that a skew symmetry is interpreted as an oriented real symmetry, and he considers the problem of computing the slant and tilt of the oriented plane.

Denote the angles between the x-axis of the image and the images of the symmetry axis and an axis orthogonal to it (the skewed transverse axis) by a and {3 respectively. The orthogonality of the symmetry and transverse axes enable one constraint on the orientation of the plane to be derived. Kanadc uses gradient space (p, q) (sec Brady [1982] for references) to represent surface orientations. He shows [Kanade 1981, p. 425) that the heuristic assumption is equivalent to requiring the gradient (p, q) of the oriented plane to lie on the hyperbola

where

Kanadc [1981, p. 42o) further proposes that the vertices of the hy­ perbola, which correspond to the least slanted orientation. are chosen within this one-parameter famil y. This proposal is in accordance with a heuristic observation of Stevens [I 980]. In the special case that the skew symmetry is a real symmetry, thJt is in the case that a - P = ±" /2. the hyperbola reduces Ill a pair of orthogonal lines [Kanadc 1981 , page 426] passing through the origin. In such cases the slant is zero. In other words, Kanadc's proposal predicts that real syrnmetncs arc inevitably interpreted as lying in the image plane, and hence having zero slant. Inspection of Figure I shows that this is not the case. i\ (symmetric) ellipse is typically perceived as a slanted circle, particubrly if the major and minor axes do not line up with the horizomal and vertical.

Although Kanade's minimum slant proposal docs not seem to be correct, there is evidence (for example [Stevens 1980]) for Kanadc's assumption that skew symmetries arc interpreted as real symmetries. We can show that the assumption can in fact be deduced from our Extremum Principle [BrJdy and Yuille 1983. Section 5]. As a corollary we can determine the slant and tilt of any given skewed-symmetric figure [Brady and Yuille 1983. Appendix C); only in special cases docs it correspond to the minimum slant member of Kanadc's one-­ parameter family.

6. Interpreting Image Contours as Curved Surfaces

Figure lc shows a number of contours that arc interpreted as curved surfaces. In this section we discuss one method for extending our extremum principle to this general case. The key observation, as it was for Witkin (1981], is that our method can be applied locally. To do this. we assume that the surface is locally planar. At the surface bilundary, corresponding to the dcprojcction of the image contour, the binormal coincides with the surface normal. The idea is to compute a local estimate of the surface normal by the extremum principle described in the previous sections and then to usc an algorithm, such as that developed by Tcrzopoulos [1982) to interpolate the surface orientation in the interior of the surface. Details of one implementation can be found in [Brady and Yuille 1983].

Acknowledgements

The authors thank Ruzcna Bajcsy, Chris Tlrown. John Canny, Eric Grimson, Ellen Hildreth, Tommy Poggio, Dcmctri Tcrzopoulos, and Andy Witkin for their comments.