Transformational Form Perception in 3D: Constraints, Algorithms, Implementation

Transformational Form Perception in 3D: Constraints, Algorithms, lmplementation

Dana H. Ballard Computer Science Department University of Rochester

Abstract

Most of the geometric inFormation in a scene is captured by local coordinate Frames oriented according to local geometric Features. In polyhedral worlds these Features are faces, vertices and edges. Such features Iead naturally to parallel algorithms For building such a scene description from stereo input that are insensitive to noise and occlusion. This representation can be used For object location, object recognition, and navigation.

I. lntroduction

The critical problern of form perception is that of picking the right representation. In previous papers wc havc argucd that if frame primitives arc picked as the underlying gcometric reprcsentation. then many problems related to form perccption can bc solved in an elegant way [2.3.4.5.6. 7 .23]. Frame primitives are geometric coordinate frames that can be extractcd from morc primitive image Features. These primitives play a dual role: thcy can bc rcgarded as Features in their own right and uscd in the form matehing process directly, or thcy can he uscd to specify transformations bctwecn themselves and other Features.

ln this paper. frame primitives are developed with respect to a polyhedral model of thc geomctric environment. The advantage of a polyhedral model is that the polyhedral primitives are intimately related to the frame primitives. However, any substrate related to coordinate frames such as symmetries [8] may be used as weil.

Frame primitives express the fundamental nature of rigidity: two shapes are equivalent if there exists a rigid transformation that maps one into thc other. This idea can also be extended to the matehing of a prolotype with portions of a scene. A portion of a scene is satd tu represcnt an instance of a prolotype if there exists a rigid transformation mapping the prolotype into portions of thc scene. The usc of rigidtty distinguishes the approaeh from topoplogical matehing [ 11.17 24].

l'hc problern of matehing a 3d proLOtype to an tmagc ean be hterarehically organized into: (l) the reeovery of 3d lincs from stereo tmagc Jata ( for monocular approaches. see [2l.lll): (2) the constructlon of a 3d polyhedral scene model: and (3) the matehing of poruons of that model to a library of stored prototypes. This hicrarchical strategy is similar tothat of [9] and has several advantages Lncr the mcthods that try to match the image to the 3d proLOtype in onc step. f-'or example. [19.20] try to match the 3d prolotype directly with the 2d line drawing.

The eomputation is implemented in a connectionist architecture. motivated by biological information processing systems [2]. The eomplete processes of extracting 3d structure and matehing is carried out by a parallel probabilistic relaxation algorithm.

Hiromi Tanaka Department of Control Engineering Osaka University

2. Basic Concepts

2.1. Geometrical Primitives

A 3d plane is defined by aX + bY + cZ + d = 0 where n = (a. b. c) is a unit normal to the plane surface and d is the distance of closest approach to the origin.

A 3d /ine is defined by the equation x = D + se where D is the closest point to the origin that the line passes through. e is the unit vector direction of the line, and s ~0 is a scalar parameter.

Each of the above can be seen as the parual specificalion of local coordinale frames where the frame parameters are synonymous with geometric features. In other words. these geometrical entities provide natural choices for the orientation of local geometric features.

2.2. Frame Descriptions

A coordinate frame is defined by a transformation with respect to a base coordinate frarne which has vectors (v lo v 2· v 3) = (( 1.0.0)(0.1.0)(0.0,1)). This transformation is specified by scale factor s. a rotation of the frame by an angle 8 about a unit vector w with respect to a base coordinate frame. and a translation of the origin by x 0. Notationally we will refer to the eomplete frame as F. thc rotation part as E. Thus F = (E. x0), where E = (e 1. e 2· e 3) is an orthonormal basis.

A vi rtue of the geomctric primitives is that the transformation itself allows one to change the point of view. Thus to make ar. arbitrary frame F = (e 1· e 2· e 3· x0) the base frame. one need only apply the transformatmn in reverse to all the frame primitives. That is, T = (w. - 8. -x 0), where wand 8 are dctermined from e 1, e 2, and e 3 (we show how this is dune in Section 3.3).

This extremely important point is the main virtue of frame primitives: frame primitives contain a/1 the information necessary to change the point of view. Any particular primitive may be chosen as a reference for all the other primitives by applying the rcference transformation to each primitive.

2.3. Matehing Different Frame Descriptions

An instance of an object in thc viewer-centered frame may hc related to a prototypieal internal representation in an objeet-centered frame by a viewing transfomwtion. hut this problern is generall} underdetermined [5]. Furthermore. the image usually eontains many teatures that belang to different objects. and these tend to confound the perception of a particular shape.

A key simplifying assumption is that the internal representation contains only a single object. ln this case the viewing transformation can generally be computed and parts of the object in the image can be identified despite other image clutter [3,6]. The task of determining if a known object is in an image is posed as: is there a transformation of a subset of image features such that the transformed subset can be explained as the object? lf the answer to this question is no, then the object is not present. lf yes. then the transformation provides all the necessary information about the object.

The principal Feature oF our method is that it decouples the computations For orientation and translation. In other words, the orientation oF the object can be detected without knowing its translation.

3. Specification of Constraints

3.1. Matehing Two-Dimensional Stereo Lines

A line in the image plane defines a plane which passcs through the Focal point (Z = 0) as weil as the linc itselF (this devclopment is similar to that oF [ 121). Consider the intersection of this plane with the image plane. At the intersection locus: X = x, Y = y, and Z = 1, so that the equation oF the line in the imagc plane is

The different imaging geometries oF stereo images will produce two different lines, and correspondingly. two different planes. In order to relatc these two planes. they must be expressed in the same coordinate frame. For the simple case of parallel views separated by /:;. . the equation of the second plane (a2, 62, c2) in tenns of the first frame is simplv

The two planes, when intersectcd. define a 3d line (0. e). Given thc two nonnals n I and n 2. e can be rcadily calculated as

where the operator < > nonnalizes its vector argument. The vector from the origin D may be calculated by solving:

where

3.2. Building Polyhedral Scene Descriptions

Given a collection of 3d lines, the problern now becomes one oF recovering additional 3d structure. To do this one can exploit an instance of Barlow's notion oF "suspicious coincidences." Applied to a polyhedral world, this idea is as Follows: il is unlikely that two Lhree­ dimensional lines will hoppen to 6e coplanar or meet at a vertex accidentally. Thus we consider constraints between all pairs oF 3d lines, assuming that intersections usually reftect rigid polyhedral structure. The constraints are simple applications of vector geometry of R 3 (7,23) and are as follows.

I. Two planes define a concave or convex edge. Pairs of planes PI= (nl. di) and P2 = (n 2· d2) produce edges which have an associated coordinate Frame (e I· e ,. ~ Jl where

The distance of closest approach oF the cdge w the origin. D. can be calculated from the Following three equations:

o 1 · D = d~o n 2 · D = d2, e 1 · D = 0

!/. Two edges can determine a plane. Coplanar 3d orientations e 11 and e I2 must lie in a plane (n, d). where lines with

and d is specified by

111. Two edges can determine a verLex. IF two coplanar Jd lincs intersect, then the intcrsection points can be dctcnnincd by solvi ng two equations From

IV. Two planes and a Jd line can define an edge. 1\ 3d linc only has a direction e. but additional orientation in Fonnation can be computed in the case where the line is also the interscction locus of two planes. In this case a Frame can be specified that has thc oricntation given by (3.3) where n 1 and n 2 are the normals of the two planes.

3.3. Matehing a Scene Frame with a Prototype

!. Rotational Conslraint. To dcvelop the rotational constraint. we show how given two orientation frames f.~ and E, From the prolotype and scene. we can compute the rotation 8 about a unit vcctor w. The mathematics of quaternions. e.g .. [25). states that the rotation oF one unit vector. u. into another unit vector. v, around a unit vcctor axis. w. is givcn by:

Wc will use the orientation vectors e , From both the modcl dnd imagc as u and v, respectively. How do we define w·J Since w must be pcrpendicular to both u and v. it can be defined in tcnns uf the two orientation Frames as

In the special case oF where e lp equals e ls and e lp cquals e ls . we arbitrarily set w = ( l, 0, 0) and 8 = 0. This procedure and (3 .7) spccify the axis of rotation.

The next step is to compute 8 For the general case. The rutation from u to v is also given by

where 8 is the angle oF rutation around the unit vector axis w. Thus the angle 8 can be computed From (3.7) and (3.9).

!I. RolaLing Lhe Model. Once the rotation between the prolotype and scene has been established, then the origins uF the prolOtype Framcs can be appropriately rotated by (For details. see [25)):

This results in a new set oF urigins that only differ From their counterpans in the scene by a translalion vector.

! ! I. Translalional Constraint. The translational constraint is trivially computed iF the correspondence between a scene Frame origin x s and a rotated prolotype Frame origin x 'P is known. The answer is thc diffcrence vector

4. Algorithms

4.1. Energy Minimization

The parallel algorithm uses a Fonn oF relaxation developed for binary threshold units by [15.141. Each unit has a state. s. wh1ch IS eilher on (s = l) or off (s = 0). In the case oF tcrnary constraints. a unit k will receive a weighted input From pairs oF other value cclls i and j in an amount given by wijk si Sj. Each unit turns on according to the following computation:

1. Compute the input

1. Substract a threshold

3) Turn sk on if Pk > 0. eise turn it olf.

Units are turned on and olf acording to steps l through 3 until con\ergence is achieved. Fonnally, if all the weights wu< are -;ymmetrical ( w;Jk = wfik = wk;J) then the converged set of states will minimize the energy function E = - L w;Jk s; s 1 sk. ln practice. the examplcs that we have tried are weil conditiuned, so that convergence is achicved in one iteration.

lf the algorithm takes one iteration to converge, it is roughly equivalent to corre/ation. lf more than one iteration is required, i.e .. a sequence of states s" converges to a fixed point s* then the algorithm specified by steps 1-3 is equivalent to gradient search. Gradient search will wurk if the constraints have a single minimum. The case where E has more than one local minimum can be handled by simulated annea/ing [ U.l4.l0].

4.2. Value Cells

The constraints are represented using spectal connectionist architecture based on value cel/s. ln the \alue cell approach. a particular vcctor variable is represented as a discrete collection of cells where the centrat location of the cell is a particular value for thc variable and the width of the cell is its accuracy. For example. representing edges in an image requires a three-dimensional cell type with location (xo. Yo. Oo) and width (~x. ~y . ~0). Collections of these cells cover the range of Jll possible edge positions and

orientations.

Since value cells arc described in tenns of thrcshold units. they can be either ojfor on. i\n un valuc signifies the presence of an edge at the associated position and orientation. Additional accuracy and the avoidance of certain computational problems can be achieved through the use of overlapping cells. The technical details of overlapping cells strategies are discussed in a separate paper [22]. Value cells representing dilferent variables are related via cunstraints. In the familiar example of line detection. an edgc cell (xo. Yo. 8o) is related to the line cell (p0· 80) through the constraint xocos80 + .vosin8o = Po·

The previous line constraint was binary in that a value cell for a specific cdge valuc was connccted to a cell for a specific line. A special kind of consuaint is a temary constraint. in which three value cells are related. t\ tcrnary constraint can improve the accuracy of line detection by using two cdges. (x 1· y 1· 81) and (x2, y 2, 82) . that are on the same line ilf 81 -82 - arctan{}·2-y1, x 1- x 1). lf this constraint is satisfied. then the (p. 8) cell is detennined by

4.3. The Overall Network

Representative value cells in the overall network are shown in the folluwing Figure. Part ;\) dcnutes the prototype Frame primitives. ß) shows the cells related to the view transfonnation. C) shows the polyhcdral network. and D) shows the

stereo network. Ternary constraints are dcnoted with an arc connccting pairs of inputs. ln each parameter network. only represcntative cells are shown.

5. lmplementation

5.1. Data Structures

Thc overall algorithm is conceptually simple: asynchronously, each cell evaluates its input and tums on or olf. When the entire network converges. the on units represent the solution to the particular problem. This simple description can Iead to inefficient implementations. since most of the cells are olf in any given instant [41.

Thus when a processor checks its input pairs (in the case of a temary constraint), most of the cells will be off. To take advantage of this. we use pairs of on units to calculate incremental inputs. and when alt such pairs have been considered for any netwurk. subtract thresholds and detennine whether to turn the units on or olf. This strategy is repeated for all the ternary constraints in the network. The only dilferences are: (I) the different constraints that relate dilferent value cells: and (2) the set of on units at any given instant. The above strategy requires a data structure that only records on cells.

We use hash tables with collision resolution via chaining, e.g., [16. pp. 462-469].

5.2. Generic Relaxation Structures

For each ternary constraint. two tables must bc indexed to compute the index of a third. Thcn thc input is addcd tu the appropriate cell. as follows.

Foreach u in T1 do Foreach v in T2 do { } w : = rule (u. v, T1· T1) lncremem (w. T3)

The function of I ncrement is to add the appropriate weight to the p field of the entry in the T.linetable. lf there is no previous entry, an appropriate cell is added. Next the entries are thresholded, and if below threshold, deleted from the table:

Foreach u in T do if u < threshold then delete (u):

Given the generic format. we can specify the network of computations by specifying collections of threc tables. each group having an associated update rule. The following Summary table represents this information.

5.3. Implementation

The status of the current implementation is that the constraints for matehing an object in two coordinate frames have been shown to work by (23]. The stereo portion of the constraints are currently bemg 8 implemented. Figure 2 shows the result for a simulated three· dimensional wrench. In these first tests. the data for the wrench is rotated and translated to obtain a sccne copy and there is no selt occlusion.

This is then matched against the original using the constraints described in Section 3.3. implemented as described in Sections 4 and 5. The figure shows: A) the wrench. B) values for the direction of rotation(magnitude not shown) and C) values for the direction of translation(magnitude not shown). The multiple values are the result of false pairings between scene frame primitive and prototype.

Although the greyscale does not emphasize this, the correct transformation is found easily in this case.

6. High-Level Control

The prolotype frames form a generic basis set. ln order to represent a particular object, an appropriate subset of value units must be turned on: One way to do this is to represent objects as specific links between an object token space and the prototype frame space. This arrangement forms a basic architecture that can be used in several different ways.

I. Object Location. lf a particular object is sought, its prototype frame description is turned on by activating its object token. This turns on the appropriate frame primitives. Then if a match between the object and a subset of the scene exists. a rotauon and a translation unit will be turned on in the transformation network.

II. Object Recognition. lf an object has been segmented (by other methods. e.g.. range, color. etc.) and its identity is sought. the prolOtype frame can be loaded with several candidate objects. lf the matehing process can build a transformation between any of these objects and the segmented object, appropriate rotation and translation units will be turned on.

A

11 f. Navtgation. This architecturc can also be used for navigation in the following way. At some initial time 10 the current scene ts loaded into the prototype frame by activating the tdenuty umts m the rransformation space. This has the elfect of turnmg on umts m the prototype frame that are a copy of the scene units at that mstant. Henceforth, as the observer moves around, these umts are locked on. The result is that at any instant the transformauon umts wtll reftect the transformation between the current scene and that at lo. The inverse of this transform corresponds to the observer mouon.

c

7. Conclusions

ln this paper we have developed a number of interdependent ideas. The main point is that geometric frames provide a natural way of talk.ing about shape. This idea has been present in psychology and differential geomctry for a long time. Our comribution has been tu develop the particular constraints for polyhedra and show how they Iead naturally to algorithms for extracting Frame information from the scene and matehing it against stored prototypes.

Thc particular focus of the paper was on the extraction of linear Features from cdge data and the matehing of these Features to obtain three-dimcnsional information.

lt is cxtrcmely important to note that these algorithms all use relaxation as the computing engine and value cells as the rcprcscmation. The Fact that all these problcms can be handled in the same way argues for the gcncrality of the approach.

8. Acknowledgements

Shmucl Tomer, Matt Curtis and Owen Kimball provided inval uable programming support in devcloping the geodesie pack.age and testing !wo-dimensional versions of the algorithms. Peggy Meek.er prepared the many drafts of this manuscript. This research was supported by NSF under Grant MCS-8203290.

9. References

1. i\ttneave, F.. "Some informational aspects of perception." Psychological Review 61, 1954.
2. Ballard. D.H., "Cortical Connections: Structure and function," TR 133. Computer Science Dept., U. Rochester. July 1984b: to appea r. Brain and Behavioral Sciences.
3. ßallard. D. H .. "Generalizing the Hough transform to dctect arbitrary ~hapes." TR 55. Computer Science Dept.. U. Rochester, 1979: Paliern Recognilion 13, 2. April 1981.
4. ßallard, D.H .. "Parameter network.s: Towards a theory of low­ level vision," TR 75. Computer Science Dept.. U. Rochester, 1981: Proc .. l !h IJCAI. Vancouver, August 1981: Arlijicial lllle!ligence 22, 235-267, 1984a.
5. ßallard. D.H. and L.M. Hrechanyk. , "A connectionist model for shape perception," Computer Vision Workshop. Ringe, NH. i\ugust 1982; also appeared as "Viewframes: A connectionist mode1 of form perception," DARPA Image Unders/anding Workshop. Washington, D.C., June 1983.
6. ßallard, D.H. and D. Sabbah. "On shapes." Proc., l!h IJC Al. Vancouver, Canada, August 1981; also appeared as "Viewer independent shape recognition," IEEE Trans. on Paliern Analysis and Mach/ne ln!elligence 5, 6, 653-660, November 1983.
7. ßallard. D.H .. A. ßandyopadhyay, J. Sullins, and H. Tanak.a. "A connectionist polyhedral model of extrapersonal space." Proc .. IEEE Conference on CampUfer Vision. Annapolis, MD, 1984.
8. ßrady, M. and A. Haruo. "Smoothed local symmctries and thcir applications," /111. Journal of Robotics Research 3. 3. 1984.
9. Faugeras, o.P·· "Representation and match.ing techniques for range data, . Rank. Pnce Funds Symposium on Representation and Control m V1sual Processing, Malvern, England, April 1985.
10. lO. Geman, . S. and D. Geman. "Stochastic relaxation, Gibbs distnbutwns, and the Bayesian restoration of images." TR, Brown U., September 1983; also appeared in IEEE Trans PAMI, January 1985. · .
11. 1L Kanade, T .. "Recovery of the three-dimensional shape of an object from a smgle v1ew." Arlificial lntelligence 17, 409-460, 1981.
12. Kanadc. T.. presentation at the University of Rochester November 1984. · '
13. Kirk.patrick., S .. C.D. Gelatt, and M.P. Vecchi, "Optimization by Simulated annealing," Science 220. 671-680, 1983.
14. Hinton, G.E. and T.J. Sejnowsk.i, "Optimal perceptual inference." Proc., IEEE CampUfer and Paliern Recognilion Conference 448-453. June 1983. ·
15. Hopfield, J.J., "Neural mitworks and physical svstems with collective computational abi lities." Proc., Na(/ Ac~d Seiences USA 79, 2554-2558. 1982.
16. Horwitz, E. and S. Sahni. Fundamenlais of Da1a S!ruc/Ures. Computer Science Press. 1976.
17. Mackworth, A.K., "lnterpreting pictures of polyhedral scenes." Arlijicwllntelligence 4, 2, 121-137, June 1973.
18. Sabbah, D., "Computing with Connections in visual recognition of ongam1 objects," 10 appear. Cognilive Science Special lssue on Connectionism, Winter 1985. '
19. Silberberg, TM., D. Harwood, and L.S. Davis, "Object _recognl[wn usmg onented model points," CAR-TR-56 and CS­ f R -1387. Center for Automation Research U. Maryland Apn·l 1984. ' '
20. Stockman, G.C. and J.C. Esteva. "3D object pose via duster space stereo," TR 84-05, Computer Science Dept., Michigan State U., 1984.
21. Sugihara, .. K., ··An algebraic approach to shape-from-image problcms, Arlificwl lntelligence 23. I. 'vtav 1984.
22. Sullins, . J., "Coarse coding in connectionist networks." forthcommg TR. Computer Science Dept., LJ. Rochester. 1985.
23. Tanaka. H. , D.H. ßallard. :vt. Curtiss. and S. l'usji. "Parallel