3-D Shape Representation by Contours

I. Introduction

A major component of Image Understanding is associating 3-D shapes with contours. First, given a set of contours, such as may be provided by some image processing device, one wants to infer the shape of the surface that they most likely describe. ln the complementery problem, given the surface, one seeks its "natural parametrization", namely contours that will convey its essential characteristics in the most economical , yet reliable way. One known mechanism that performs these tasks weil is the hu­ man visual system. A few drawn lines can create a surprisingly vivid and convincing impression of a 3-D shape jBarrow & Tan­ nenbaum, 1981;.

In this report , we address this problern on the fundamental and general Ievel of first , finding ·the principles that must guide any process of representing a surface by contours, regardless of its physical implementaton, and second, we propese a mathemat­ ical mechanism that can perform these tasks, conforming with our principles . Nevertheless, as the eye is the most successful image processing system we have, we shall test the performance of our abstract procedure against its. In the following we shall summarize the requirements that we impose on a surface recon­ struction mechanism, and their relation to previous work .

1) A mechanism should build a surface in accordance with the information it. has available about it, like boundary or other contours on it , but it should not add extraneous information of its own . lt is qualitatively clear that information is closely re­ lated to the smoothness of the curve or the surface. A straight line can be described by the Coordinates of the end points only, while a more complicated shape will require more informaton . Thus it is reasonable , and mathematically convenient, to asso­ ciat.e minimal information with minimal curvature, and to as­ sume that a surface reconstruction mechanism will Iook for a surface that will have a minimum overall curvature while fitting the given contours.

2) The reconstruction mechanism should beinvariant to ro­ tations and translation, i.e. if the input image is rotated or 1 ran·lat ~cl. 1 hP outpul should move by the same amount but not th<' ri rclc ao; an f'Xt remum over the set of all curves compatib!P with the projcned ell ipse. Limiting ourseh·e" to planar curves (zero tortion) . this rneans tht- set of Pllipses (produced by dif­ ferent slant angles). wit.b the same major axis as the apparent onc The energy principle fail s in this task as it dues not extrem­ izf' the circle over the set of ellipses . Even worse. as it is not dimensionless. t he ex tremum will depend on the apparent sizf' of th f' i mag<". cont rary t.o to our demands. \\'e now propose a modifica t io11 of the energy principle, whi ch will work for smooth c urve-~.

*Now at the Center for Automation Research , University of Maryland , College Park, MD 20742 .

Let ting D. s he the total length of t he curve. we can define thf' dimensionless variable:

whf.rp t is the length of the curve lying between a point on the curve and one of its ends. I is a measure of the relative position of a point on the curve , regardless of the curve's length . We definf' thf' ''action", in analogy to the physical quantity, as the integral :

This is equivalent to mu tiplying the "energy" by D.s . As both I and t are dimensionless, so is A . (Unlike the physical action). Another advantage of this normalization is related to the way the extremum is found . In general , one can use the Euler-Lagrange equations to obtain a differential equation for i\1). But this re­ quires that both the dependent and the independent variables will have fixed values at the end points . Our normalization pro­ vides that , as I always runs between 0 and I, unlike s.

The extremum problern is easily solved in the simple case of a curve with two boundary points. It is convenient to use a polar coordinate system, with the angle 4> defined as the angle between the tangent t and (say) the x axis . We thus have:

ThP act.ion now read~:

We shall now show that given two end points with the tangent there. the curve that passes through them is a circular arc . As a special case. extremizing over the set of ellipses with their extremf' points fixed . will yield a circle. Our variational variable ,, ''·'" r.l!l w·ith the hounoan ronoit ions 6 (0) = 6 1 and d>(J) ~ o,. w here o 1 . o, are the iuclinations of the curve at the end points . The EL equations yield :

with tht- unique solution :

which is a ci rcular arc.

III. Large- and Small-scaie Variations

Thf' simpl e mmimum energy principle. our modification not­ withstanding. su ffers from a severe shortcoming : lt cannot han­ dl f' sharp turns in t he curve. A sharp corner will complet.ely dominät<' the curve. änd the value of t.he integral will depend on the exact shape of the corner. with point-like edges leading to infinit.ies. Even a srnall bump will have a considerable inAuence, andin fact. t he small er the bump, the greater its effect on t he in­ tegral will be (keeping its shape similar ). This mal<es t he energy principle inapplicable for curves with edges. or noise. without elaborate filtering t.echn iques . On the other hand. straight lines are ignored by this principle. regardless of how long they may be.

We propose a new kind of an extremum principl e, one of whose advantages is essentially solving this small (and !arge) scale variation problem. (Another advant.age will become ap­ parent when we go over t.o 3-D) . First, we parametrize t he curvt­ by a new coordinate a , running along the curve with its Iimits being 0 and I . Then we define a new "action" A:

Intuitively, one can regard a as a variabl e which is affected by two forces, generat.ed by the fact that the ex t.remizing drives o to follow I and i', in analogy to an inertia effect. The second term in A pushes a to be as close as possible to I. In the absence of t he first term (i.e. a straight line) a will coincide with I. This makes the first term as close as possible to the not.ion of curvat ure. On the other hand , the first term drives a to follow i', (or <P) to some extent and concentrate in regions where D.t is !arge (such as a corner), so that D. i( CJ.a does not get out of control.

As a "physical" analogy, one may think of a spring which can be stretched and bent unevenly along its length . The vari­ able "a" will represent the amount of mass from a point on the spring to one end (as opposed to the spatial length /) . The anal­ ogy is not perfect , though , as an actual spring usually does not have a dimensionless A . The spring is "ideal" in the sense that it , or part of it , can shrink to an infinitesimal length (like an ideal gas) . This is what will happen in a corner. A finite "mass" CJ.a will concentrate in an infinitesimal corner , allowing the finite bending 6. </J to spread over it .

In ext. remizing A, the unknowns are the functions l(a ) and t(a) (or equivalently 1/J(a)). Solving for them will give us both a(l) , (the distribution of t.he "mass" along the mass. and t(i) , which defines the curve. These unknown functions are not al ­ ways compl etely independent, which may reduce the number of unknowns. or they may depend on a pa rametersuch a~ tllP sl~nt. that will become an unknown to be found by the ex t.remizat.ion process. As we shall see , the first. termwill berather dominant in sections of the curves having rapid curvature changes over short length, such as bumps. corners, or saw-teeth. The second term will be the major contribut.er in the large-scale features , having slow variations in curvature. such as t.he other boundaries of the ~aw. Thus we have obtained a "natural" way of treating curves with two very different scales of curvat.ure change , without hav­ ing to use arbitrarily preset. filtering widt.hs , as is commonly dune .

A simple demonstration of the workings of t.his procedure can be made for a simple corner. We shall now examine the in­ il uence of a corner on our new A , as compared t.o it.s cont ributi on to the energy.

We can build a corner from two '·sticks'. of length I. making an angle t>.o between themselves . We keep f>.d> fixed . and we are only interest.ed now in finding the distribution of the o along this rorn E>r . This turnes out to be a quite simple ext.remum probl em. Th" increment.s of o al ong the sticks and on their joint is . respenivE>I) .

As we noted before. the second quantity is indeed finite . (ln fact , we derived this result. by treating the joint as a small circular arc , with length I Jo·nt , which tends to a point.) Substituting these quantities in A we obtain in the extremum:

which is independent of the exact shape and size of the corner , only on the total turn f>.</> .

In comparison , the (modified) energy principle will give for this corner :

which tend to infinity as the length of the corner goes to zero.

A bump can be regarded as a series of relatively sharp turns. Thus, given our expression for A at a corner, it is clear that its contribution is not dominating. With filtering , that will reduce the turns f>.</> along the bump to small values , the influence of the bump will be quite negligible.

IV. Skew-synunetry

We now collect 4 corners to form a parallelogram, which is a skew-symmetric shape . Weshall allow the f>.</>-s of the corners to vary, in accordance with with interpreting the parallelgram as a shape with a slant in 3-D. We want to extremize A in respect to these f>.d>-s. to find the slant. The problern is complicated slightly by the fact that there is a constraint , namely that the sum of the angle of the 4 corners is equal to 21r. this can be handles by the method of Lagrange multipliers, and the result is that all the corner angles are equal , namely equal to 1r / 2. Hence , the parallelogram is interpreted by our extremum principle as a slanted rectangle, which is consistent with human perception . This result can be extended to general skew-symmetric shapes.

V . General Surfaces in 3-D

So far we have dealt with planar surfaces that can be de­ scribed by a one-parameter boundary curve. We now turn to

·,he general cas<' of a (reasonably) arbitrary surface in 3-D. such 1 surfacP can b(· parametrized by t.wo coordinat.es o 1. O z Our oiCLion A will """ bt- a double integral:

where the surnrnation is on i = 1.2.

Givto11 a sPt of known cont.ours, either on t h<' boundary or otherwise. W<' co11struct the surface that best fits these contours as the one that extremizes the above integral. Moreover , the o, will now have a more tangible meaning then in the one­ parameter case : they will be the natural Coordinates parametriz­ mg the surface. This isanother advantage of the new procedure over the energy principle. lt is interesting that the variables o , can serve the dual purpose ofboth handling bumps (and straight lines) and provide a set of 3-D natural Coordinates.

it is easy to prove, for example, that a circular boundary will give rise to a sphere. complete with its longitudinal" and latitu­ dinal Coordinates. Rather then do that , we shall state a general theorem about curves on surfaces , which will be very useful in finding natural coordinates as weil as the surfaces themselves (including the sphere) .

We first define a curve of local symmetry, r as one which divides the surface in two parts that are symmetric in the vicinity of the curve. Put another way, a reflection , say of the surface lying to right side of f will match the left side , near f . An example is the center line of any fold, ridge, valley or corrugation · on a surface (fig I) , if this line is planar. Another example is the three symmetry lines on an ellipsoid (this isaglobal symmetry ).

Theorem I : A curve of local symmetry is planar.

proof: Trivial. A reflection of the right side of r will not match the left side if fisnot planar. (fig I) .

Theorem 2: A local network of coordinates , consisting of a local symmetry curve r and curves that are orthogonal t.o it , locally extremizes the action A.

By "locallv extremize" we mean that an infinitesimal varia­ t ion of these c~rves, in the vicinity of f, will leave A unchanged .

We shall discuss consequences of the last theorem. (The proof is ommited .) A very interesting class of surfaces to which our theorem is easily applicable is the one having an "ignorable coordinate" , namely, its curvatures will not change as we move along this coordinate. As sub-classes one can mention (a) strips, or pipes, of arbitrary cross section, whether straight. circularly or helically bent , (fig 2), in which the ignorable coordinate is the length of the pipe. and (b) surfaces of revolution . in which the azimu t h a> is '·ignorabl e'·. (fig 3) . The coordinat.e orthogonal to t he the ignorable onf' can be regarded as a local symmetry curve. as the surface stavs the samf' on its sides. Thus. this curve. and t he curves in tb ~ ignorabl e direction that int ersect it. form a local network of curves that satisfy the cond iti ons of theorem I , and t hus it. ext remizes A .

As we can see from the figures , thesf' curves are exactly the ones t hat our visual intui t ion would expect as nat ural. so that we are justified in calling the curves extremizing A the '·natu ral coord inates'·.

A further consequence of theorem 2 is the ability to make predictions about surfaces when they arenot known in advance, without having to actually extremize A using the EL equations. lt is clear t hat generally, the greater the number of extremal local sections a surface has , the more "extremal" the global 2dimensional integral A will be. (This would be clearer if this "extremum" were a "minimum" , which it usually is, but as we have not examined here the second derivatives , we shall stick to the term "ext remum". ) Thus, a surface that extremizes A will contain as many symmetry curves as are compatible with the initial data. As a consequnce , we will tend to obtain sur­ faces containing planar , spherical or cy lindrical parts , exact or approximate , rather than bumpy ones . As a particular example, we can use this general result to conclude, without having to solve the EL equat ions, that a circular boundary will give rise to a sphere. This is because a sphere is the most symmetric surface, thus having the greatest amount of symmetry curves. More generally, boundary contours such as of fig. 3 will give rise to a surface of revolution , as this surface consists of a collection of local networks (the meridians and parallels) which fits those contours, and similarly for other surfaces .

lt is reasonable to assume, that when the conditions of the theorem are satisfied only approximately, e.g. when the curve is only approximately symmetric, a similar parametrization will still take place, with the natural Coordinates approximately foi­ Jowing the quasi-symmPtry curves. Thus our theory is appli­ cabl e t.o shapes like generalized cones. as long as the flutings varv slowl v on the lenth-srale of t he cone's radius. This also is cOI,'sist.ent .with hum<>n perception .

VI. Relation to Other Work

We have already noted the intrinsic flaws of the energy prin­ ciple, and its derivatives (such as Barrow and Tenenbaum's), as surface reconstruction mechanisms. The compactness measure of Brady and Yuille [1984] does not suffer from these deficiencies. It has been applied successfully to closed planar curves, but it is hard t.o see how it. can be mad f' a general theory. Jt should bP

best vi ewed , perhaps. as a good measure of global symmet ry.

Brady 6.: Asada IJ984. havf" studied local symmetries in pla­ nar shapes. Strictly ·speaking. our defini t ion of "local" applies to an infinitesimal vi cinitY around a curve. ln this sense. everv straight li ne on a pl ane is a local symrnetry curve , ex~ept .;t it edges. Brady examined !arger vicinit.ies. t hat extend to the nearby bound aries of t he curve. so we shall elevate the type of symmetry lte t reated to a ''regional" symmE'try. The fact that Brady 's curves are a lso nat ural Coordinates indi cate that the notio-n of symmetry is of fundamental importance at all spatial scales (global , regional. and local ) of shape representation .

In differenti al geometry terms. our local symmetry curves are planar geodesie ones . Brady et al [1984j have shown that pla­ nar geodesics are usually "natural" Coordinates . However , not all natural coordinates are planar geodesics . For example, the parallels on a surface of revolution , and th t> spirals on a helicoid (fig . 4). are not planar geodesics. The question why these Iook natural was left open , as they did not seem to fit any consis­ tent rule. In our theory, these curves are nat ural coordinates by virtue of their being orthogonal at each point of their length to planar geodesics, namely the meridians and the rulings , respec­ tively. Moreover , unlike the previous works , our results come out as a part of a general theory of shape representaton derived from sound first principles.

Acknowledgements

The author thanks Michael Brady of MIT's Al Lab for care­ fully reading earlier drafts of this paper and making very valu­ ab]f! comments and suggestions.