A Shape Representation Based on Geometric Topology: Bumps, Gaussian Curvature, and the Topological Zodiac

I. Introduction

Shape representation is crucial in image understanding, both for object recognition as well as signal representation. General­ ized cylinder· (e.g., Binford 1971, Agin and Binford 1973, Nevatia and Binford 1977, Brooks 1981] are one well-known representa­ tion with a notable history. More recently, there has been interest in using differential geometry in shape description (e.g., Haral­ ick, Watson, Laffey 1983, Horn 1983, Nackman 1984, Brady et al. 1985, Besl and Jain 1985], as well as fractals (Pentland 1985].

Our present subject is a representation for shape based on some ideas from differential topology, which turns out to be re­ lated to all 3 of the approaches mentioned above. The shapes we are interested in are smooth 2-dimensional surfaces embedded in 3-space, a common class for vision.

My starting point for this is that I want to represent an object as a bunch of bumps. The representation should have in­ variance properties: it should be independent of position or orien­ tation of the object, i.e. it should be intrin1ic. It should also have 1tability properties, i.e. it should be constant under small per­ turbations of most anything involved in generating or matching to the representation, like noise, viewpoint, and, less obviously, perturbations ·or the shape itseH. And it should degrade well under partial information; in particular it should commute with occlusion: the representation of a subpart should be a subpart of the representation.

Anyway, the goals of invariance and stability, like spring, make a young man's thoughts turn to topology and geometry, so that is where we look for the tools of our representation.

B. What happens as the z-direction changes

We were able to describe our shape in terms of level sets by choosins a particular direction for the z coordinate as spe­ cial. Alas, if we were to choose some random other z-direction, we probably would set a different batch of critical points and a different paph ahucture.

The "obvious" mathematical solution to the choice of z. direction is to consider 1111 .z:-directions, and 1111 possible sraph structures-then thinss won't depend on choice of coordinates, since we use them all! The space of all z-directions is . . . the Gaussian sphere. So now, every choice of z-direction, hence every point on the Gaussian sphere, has a sraph associated with it that tells us the level set structure of the surface for that particular z-axit.

Let's consider stability. Look at what happens at an atomic bump (Ffsure 2). Looked at with a slishtly different vertical, it's still a bump. In particular, we can't set rid of the critical point (the tansency with the plane). It may move (and will), but it still exists somewhere, if the chanse in orientation is small enoush, and if we started at a typical orientation. This tells us that thins· are not all that bad: for typical (all but measure aero) poinb on the Gaussian sphere, the sraph structure is constant in some neishborhood of the point .

When does it chanse? Consider what happens as we keep rotatins the z-direction (Fisure 3). As the extremum from our bump moves to the left, a saddle point moves toward it to the risht, inexorably. Once they meet, poof! No more critical point, and our sraph has chansed. This is a saddle-node bifurcation, since a saddle and an extremum have annihilated each other. Runnins our ·rotation backwards would result in the birth of a saddle-node pair. Where do they meet? At an inflection, i.e. at a point where the curvature is sero. For a surface, this is where the Gaussian curvature is sero. Such points are called p11r11bo/ic point., and they senerically sroup to form p11r11bolic curve· (which are not parabolas!). That meant that if we rotate the .z:-direction somewhat differently, we can't set rid of the parabolic point­ we'll just hit the parabolic curve in a slishtly different place.

The other type of bifurcation, a saddle connection, can also occur. This will happen when chansins the z-direction results in a saddle that was hisher than another becomins lower with respect to the chansins equal-heisht planes. From now on, we will only describe the part of the structure that comes from the saddle-node bifurcations.

C. Parabolic curves and the Gaussian curvature graph

For a compact surface, the parabolic curves~the points of tansency where the saddle-node bifurcations happen-senerically are closed curves that don't intersect (Koenderink and van Doorn 1980). Now both the surface and the Gaussian sphere are divided into resions by the parabolic curves. On the Gaussian sphere, the parabolic curves (or really their irnases under the Gauss map) are the z-directionl where the levelaet sraph bifurcates (chanse· ib

topolosy) in a saddle-node. On the surface, they are the inflec­ tions. Also, they are level sets of the Gaussian curvature function, for the level value of zero. Like other level sets, they exhibit a nestins structure, so that they, too have a J!Iaph structure asso­ ciated with them. The Gaussian curvature is a smooth function defined on the surface, so we can play the same level set sraph same with it. This yields the Galissian curvature sraph of the surface, which has the same topolosic~ features as the other level set sraphs. This sraph is intrinsic, thoush, since there is only one Gaussian curvature function for (a siven embeddinr; of) the sur­ face. As we smoothly chanr;e the surface (say by deforminr; it), both the r;raph structure of the Gaussian curvature map (hence the parabolic lines) and of the surface level sets in each domain of the Gaussian sphere will remain constant, while the shape and locations of the domains will chanr;e. This will continue until we reach a bifurcation of the "parabolic" sraph, at which time a domain may be created or annihilated, siJ!nifyinl! a qualitative chanr;e in appearance for some view aspect.

There is a notion of scale for each of the sraph structures, analosous to .that for the level set tree of a function on the plane, defined by the nestins of the respective level seta. "Smoothinr;"

can be effected by loppin~ ofl' leaf nodes, or whole terminal sub­ ~raphs .

n; The topological ·odlae

We've seen so far that the (ima~es of the) parabolic curves on the Gaussian sphere mark the normal directions where the level set ~:raph under~:oes a saddle-node bifurcation. Equiva­ lently, they divide the Gaussian sphere into re~:ions where the topolo~y of the level set ~:raph is constant (modulo saddle con­ nections). We've also seen that distortions of the surface move these parabolic curves around on the Gaussian sphere. To cap­ ture the topolo~:y of these re~:ions, we can use the adjacency ~raph of the re~:ions .

Actually, we were not completely candid about the construc­ tion of the re~ions on the Gaussian sphere. You may have noticed that it's not entirely clear which of the 2 possible normals to a level plane is the ri~ht one for mappin~ to the Gaussian sphere at any ~iven time. The answer is that really they both are, and the only solution is not to use the Gaussian sphere at all, but to use the Gauuian projective plane obtained by identifyin~ an­ tipodal (diametrically opposite) points of the Gaussian sphere to sin~le points. To make our pictures completely precise, we have to map the parabolic curves to this Gauuian projective plane by the antipodal identification, and consider when the normal line to a level plane crosses one of these curves, i.e. when either nor­ mal of the level plane crosses the parabolic curve on the Gaussian sphere. Fi~ure Sa shows the result of applyin~ the above map­ pin~. We are representin~ the projective plane by a hemisphere, with features from the rear hemisphere of the Gaussian sphere mapped to the front hemisphere (which we show) by the an­ tipodal map. In such a picture, the points on the circle at the boundary of the hemisphere are understood to be identified with their antipodal points (on the same circle). The dashed lines rep­ resent the parabolic curves that were on the rear of the sphere in Fi~:ure 4, and which now have been mapped to the front of the sphere by the antipodal map, so that all the features are now on the front of the sphere, and we therefore only depict a hemi­ sphere. This projective plane represents all the line· throu~:h the center of the sphere- the normal vectors with their sense of direction stripped away. Note that rotatin~ a line throu~h only 180 de~rees results in the same line a~ain; that's why we have to identify antipodal points on the sphere.

It's the re~ions in the Gaussian projective plane that really are the re~:ions of constant level set graph. In Fi~:ure 6 we show some of the level set structures for our example surface. We've depicted the surface rotatin!l relative to fixed level planes for clarity. The relative direction of the normal line for each set of level planes lies on the associated region of the Gaussian projec­ tive plane. The adjacency ~:raph associated with these regions is shown in Fi~ure 5b. Keep in mind that antipodal nodes on the outside circle are identified, even though each one has been shown twice to allow a comprehensible graph.

Then each node in the adjacency r;raph has associated with it the level set r;raph that describes the bump structure for z-axes within its rer;ion (Fir;ure 7). We call this the topological zodiac since it is reminiscent of some astrolor;ical charts. This r;raph of r;raphs completely specifies all the level set atructures ponible for the surface, and all the ponible transitions between them. or course further information could be appended to the structure, e.r;., metric information about the sue of rer;ions, their actual orientation, etc.

The topolor;ical sodiac is related to the viiUal potential of (Koenderink and van Doorn 1979) in that both representations are graphs of topological types, based on analysis of singularities. The former, however, represents solid 1hape; the latter, shape of outlines. The full details of the relationship remain to be worked out.

III. Summary and Conelualona

We sought to repreaent protruliona with seroth order atruc­ ture, and found that this is orr;anised by ht order aingularitiet: critical points. The change· in this atructure, in turn, are gov­ erned by 2nd order ·ingularitiea: parabolic curvea. The parabolic curves embed in the graph 1tructure of the level aets of Gau11ian curvature. The retulting repre1entation provides a ·table discrete 1tructure which capture· tome (but by no meant all) of the in­ tuitive notion of shape. H allow· rettriction to a ranr;e of scale, a characteriaation of subttructure, and thu1 permits a coaue-to­ fine matchinr; 1trategy.

Since all the information we have used is really contained in the Gaussian curvature r;raph and the Gauuian projective plane adjacency graph, it thould 6e po11ible to ditpense with the topological sodiac (the graph of leveltet graph· ). It 1eem1 that the latter should be deducible by very 1imple operation· directly from the above graphs. We haven't fir;ured out how to do that yet, thour;h.

Adtnowledgmenta

I would like to thank Ted Selker for some very helpful dis­ cussions, Danny Sabbah for 1Ur;p;e1tinr; applyinr; the1e ideas to shape representation, Sanjay Addanki for hia critical apprai~al, Gabi Kuper for bringing 'lEX to Yorktown, Scott Penberthy for mating machine· in captivity, and Suh Murthy for countleu fa­ Yors.

B.efereneea

(Agin and Binford 1973) Agin, Gerald A. and Thoma1 0. Bin­ ford, "Computer Detcription of Curved Objects," Proceeding· of Third International Joint Conference on Artificial Intelligence, Stanford, California, Aur;u·t 1973, 629- 635.

[Bell and Jain 1985) Bell, Paul and Rame1h Jain, "lntrin1ic and Extrinsic Surface Characteriatict," Proceeding· of IEEE Com­ puter Vi1ion and Pattern Recognition Conference, San Francisco, June 1986, 226- 233.

(Binford 1971) Binford, Thoma· 0 ., "Visual Perception by a Computer," IEEE Conference on Slflteml and Controll, Miami, December 1971.

(BUcher 1983) Blicher, A. Peter, "The Stereo Matching Prob­ lem from the Topological Viewpoint," Proceeding· of the Eighth International Joint Conference on Artific ial 'Intelligence, 1983, 1048-1049.

[BUcher 1984) Bliclier, A. Peter, "Edge Detection and Geomet­ ric Method· in Computer Vision," Ph.D. thesis, Mathematics Department, University of California, Berkeley, December 19R4. Abo Stanford University Computer Science Department techni­ cal report STAN-CS-85-1041 and AI memo AIM-352, February 19115.

(BUcher 1987) "A Shape Representation Based on·Geometric To­ polor;y: Bumps, Gaussian Curvature, and the Topological Zo­ diac," IBM T.J. Watson Retearch Center Technical Rep·ort , to appear.

[Brady et al. 1985) Brady, Michael, Jean Ponce, Alan Yuille, and Haruo Atada, "Describinr; Surface·," in B.oboties B.eseareh, MIT Pre11, Cambridr;e, 1985.

[Broob 1981) Broob, Rodney A., "Symbolic Reasoning Among 3-D Modell and 2-D Image·," Artificial Intelligence, 17, 1981, 2115-348.

(Bruce 1981) Bruce, J .W., "The Duab of Generic Hypeuurfaces," Mathematica Scandinavica, 49, 1981, 36- 60.

[Haralick, Watson, Lafl'ey 1983) Haralick, Robert M., Layne T. Wahon, and Thomas J . Lafl'ey, "The Topographic Primal Sketch," The International Journal of Robotic· Ruearch, vol. 2, no. I , aprinr; 1983.

[Horn 1983) Horn, Berthold K.P., "Extended Gaussian Images," MIT AI Memo 740, Cambridge, July 1983.

(Koenderink and van Doorn 1976) Koenderink, J .J. and A.J . van Doorn, "The Singularitie1 of the Vi1ual Mapping," Biological Cy­ bernetiu, 24, 1976, 51-59.

(Koenderink and van Doorn 1979) Koenderink, J .J . and A.J . van Doorn, "The Internal Representation of Solid Shape with Respect to Vision," Biological Cybernetic·, 32, 1979, 211-216.

[Koenderink and van Doorn 1980) Koenderink, J .J . and A.J. van Doorn, "Photometric Invariants Related to Solid Shape," Optica Acta, vol. 27, no. 7, 1980, 981-996.

[Koenderink and van Doorn 1984) Koenderink, J .J. and A.J. van Doorn, "What Doe1 the Occludinr; Contour Tell Us About Solid Shape?," Perception, vol. 13, 1984, 321-330.

[Koenderink and van Doorn 1979) Koenderink, J .J . and A.J . van Doorn, "The Structure of Two-dimensional Scalar Fields with Applications to Vision," Biological Clfbernetie~, 33, 1979, 151158.

[Nackman 1984) Nackman, Lee R., "Two dimensional Critical Point Confir;uration Graph·," IEEE Tran1action· on Pattern Anal­ lflil and Machine Intelligence, vol. PAMI-8, no. 4, July 1984, 442-450.

(Nevatia and Binford 1977) Nentia, Ramakant and Thomas 0. Binford, "De1cription and Recor;nition of Curved Objects," Ar­ tificial Intelligenee, vol. 8, no. I, February 1977, 77- 98.

[Pentland 1985) Pentland, Alex P., "On Describinr; Complex Sur­ face Shapes," Image and Vi1ion Computing, vol. 3, no. 4, Novem­ ber 1985, 153-162.