3D Object Representation and Matching with B-Splines and Surface Patches

311 OBJECT RI'PRI'SI'NTATION AND MATCHING WITH B-SPUNES AND SURFACE PATCHI'S

Bryant W. York IBM Research Laboratory, San Jose, Ca.

Allen R. Hanson l'llward M. Riscman University of Massachusetts, Amherst. Ma .

MULTIPLICITY 1

MULTIPLICITY 3

Figure 2: Running Shoe

We have interactively designed 2D and 30 cubic R-splinc curves, stored thL·m in a data base, computed their feature values. :ond associatL·d them with surface patch definitions in any of three roln -- hound:ory l'ltrvc, :onoss boundary dcriv:otivc curve, blending funL·tion. ThL· design of Coons patches is less interactive . Simple Coon- pa1cl1cs an· designed by entering the coordinates of the corner position m:olrix and pointers to desired boundary curves :ond blending functions . This is a cumbersome process and it requires that the surface patch he designed on paper before it may be entered into the data base . In progress is the design of a mechanism for interactively constructing arbitrarily complex patches using a quad tree data structure and the Coons smooth join criteria . Such :o mechanism will facilitate the construction of new object models from existing ones.

ABSTRACT

An approach to 3D object representation and matching, which employs cubic B-splinc curves and Coons surface patches is described . 3D objects arc represented as structured collections of surfaLT patches whose boundary curves arc approximated by cuhic 1\-splincs. Both curved and polyhedral objects may he rL·prcscntcd . A variety of 3D and 20 shape features arc defined which arL· easily nunput,·d for this representation . Many of the 3D features have 2D analogues , thus providing access paths from 21> to 3D. It is anticipated that this approaL'h will prove useful for matching 30 object models against 2D object descriptions . The representation. our approaches to the problems of indexing and matching, the state of the implementation, and ou.­ cxpcricnccs with the implementation are briefly discussed .

I. 311 OIIJFCT REPRESF.NTA TION

31> Ohjc,·ts arc rL'prcscntcd by structured collections of surra,.,. patdll'S. A surfan· patch may he simple or compkx . Simpk patches an· rq>rcsL·ntcd in Coons form Ill with boundary curv,·s. ano~s boundary derivative curves, and blending functions o-c-pr-c-scntcd as euhiL' B-splinc curves. A complex surface patch is forrlll·d by joining two or more patches along a common boundary . For rnorL· details on the representation sec 1!! .9] .

Two of thL· morl! significant properties of the representation are thL' ability to represent both curved and polyhedral objects in a single representation and the large number of shape features which it admits. A cubic B-splinc curve is represented by a list of points (x-y-z coordinates) called the "vertex polygon". The multiple-vertex property of cubic R-splincs permits slopL·-discontinuous and curvature-discontinuous curves to have similar representations to smooth curves; the only difference is that a discontinuous eurw will have at least one vertex of nwltiplicity greater than I in its vertex polygon. A circle may be approximated by a cubic 11-splinc with only 4 vertices in its vertex polygon and a square is approximated by a similar vertex polygon with 4 Vl'rtiL·cs of multiplicity 3 (sec Figure I) . When cubic 11-splincs arc USL'd to represent the boundary curves of a Coons surface patch, both l'lrrvcd and polyhedral objects may he obtained. Figure 2 shows a plot without hidden line removal of a smooth . curved object (a running shoe) described by a singk patch in our representation ; Figure 3 shows a polyhedral object (a wedge) . Because of thL· smooth join property of Coons surface patL·hcs , complex smooth objects may he formed by joining several component patches, as well as objects with both curved :ond polyhcdr;~l p:orts. The vertex polygon of a cubic B-splinc curve PL'rmits comput:otion of polygonal shape features and the Coons p:otch form allows the computation of additional shape katun·s whid1 :on· L'harac-tcristiL' of the p:otch rather than its houru.lary «..·urvl·s. FiJ.!un· 4 lists snml' nf thC more si~nifkant sh:opL' k:otun·s for 11-splitll' ,·urvcs :ond Coons patches.

OC = open / closed

Pl.

planarity

SM

smoothness

NV

no. of vertices

MY

no. of mult-verticcs

C

compactness

AV3D = an~ular variability

MAXAT = max angular turn

Patches

patch compactness

position vcc'tor angles

= tangent vector angles

position vector magnitude ratios

= tangent vector magnitude ratios

c

PYA

TVA

PVMR

TVMR

Curves

Figure 4 : Some Shape Features

II. ACCESSIBILITY

Acccssibilily deals with lhe problem of gaining access lo a proper set of 31> object representations based upon information extracted from a 2D image. It involves the representation of 3D shape information , lhc representation of 2D shape information. and the indexing paths available in the data base .

A. Structure!!! Visual Knowledge

In the VISIONS system [3[ visual knowledge is collected in a layered network data base called long term memory (LTM) . Each level of the network contains a single type of entity. The entity lypcs used for this work arc .,chema, object . .wrfaa patch. JD curve, ft'/l,ion. 1 D ('UfVt' . 1/('ftt'X. Each level is currently partitioned into four spaces whl'fl' a spaCl' is merely a collection of entities. The four spaces arc lhe " class" space , lhe "class feature " space , the " instance" space , and the " instance feature " space . An example of a class cnlily at the object level is , say. " table". This entity is a prototype from which many instances may he co·nstructcd. The instances may differ in a variety of ways . Consequently, separate feature spaces arc maintained for classes and instances. Figure 5 is an example of a portion of the network structure of L TM. The advantage of this network structure is that it provides a straightforward, logical view of the current structure of stored visual knowlcd)!.l' . and tht.· st·manlil's of access to particular knowkdgc is easily described in tl'fms of path travcrsals[6) .

H. 2D Representation

In the world of 2D scene analysis it is necessary to cxlracl rcprescnlalions of 2D entities from digitized images . Our approach is In allcmpl 10 keep the 2D representation as clnSl' In lhl· 3D rcprcsentalion as possihlc . Thus, lhc 2D digital CllrVl'S which result from thl' Sl,.'l-!lllCnlation of a digitit.l·d image an: converted to cuhil· R-splinc representation . A 11-splinc curVl' is filled 10 an image curve by analyzing lhc K-curvalure)2) of lhl· image curve and placing knots along the digital curVl' al appropriate points. Special algorithms have been developed for knot placement and knol coalescing (!he creation of mulliplc knots) . The fillin~ procedure is ilcralivc . First knots arc plan·d al points of high K-curvaturc. then knots arc moved or coalesced according to a sci of special heuristics. the cubic B-spline through the knots is computed. and a measure of error of fil is comptoll'll. If the error is above some threshold . we ilcralc from the knol motion / coalescing step. When the error is below threshold. lhc knot vector is convcrtl·d to lhc corresponding vertex polygon and 2D shape features arc computed. The spl'Cial heuristics arc based upon smoothness criteria such as lhc detection of corners or peaks (slope discontinuities) and the detection of "staircase" straight lines. For more details sec )9).

,-he algorithms for knot placement , knol motion , knol coalescing, B-splinc computation. and error computation have been implemented. Currently the filling procedure is intcraclivdy controlled with the user indicating the locations in lhc curve where a given special heuristic should he applied . We would eventually like to develop a mechanism which has good performance without user intervention.

C. Indexing

A small L TM has been umslruclcd containing I X single-patch objects. The graph rcprescntin)t this LTM contains approximately 150 nodes and 3000 edges. An indexing mechanism has been implemented in the GRASPI'R)5) graph procc."ing language . The mechanism provides for l'Xccution of rl·ialional sc;·rch,·s in the nl·lwork . An cxampk of a rdational search mighl he lhc query "Find all curves which arl' closed ami have angular variability = 1.2X". The ,·urrcnl mechanism merely executes raw primitive queries on the 3D kvcls of I.TM. ANDing and ORing of lhe rcsull sets is done interactively when all of the primitive rcsulls arc available .

We have not, as yet, implemented "standard vicws " )7) Correlation of certain 2D shape katurl'S (sUl'h as AV ~ ll) for standard views with the corresponding 3D features (A Vlll) . will provide indexing paths from the 2D levels lo the 3D lewis. Figures 6 and 7 demonstrate lhe importance of standard views and the change in 20 shape features wilh ch;u1gc in view. Four projections of a cubic ll-splinl' approximation to a 3D circle and its associated vertex polygon arc shown . ·The circle is defined in 3-spacc even though il lies in a plane . Thl' plane of the circil' starts oul orthogonal lo the line of sight and is rotated away from the viewer by the angular amounts indicated . As the lhc circle is rotated, it projects as an ellipse of greater and greater cccenlricily until finally it projects as a slraighl line. Figure X shows certain 2D feature-values for rolalions from 0° lo 90°. In the case of the circle some of lhc 2D feature-values for 0° arc equivail'nl lo the 30 feature-values for lhc 1D circl,·. From sucl1 a lahk Wl' can heJ,!in to correlate changt· in fl'alun· vahll'S wilh chang,l' in viewpoint. Ultimately we would likl· lo lkvclop ,·orrdalions for more complex shapes.

Ill . CONCLUSION

Matching is a difficull problem ·involvinl( exponential search. ll becomes more tractahle when the number of candidates against which a description must he matched is reduced . We· feel that our representation . the structure of LTM. the usc of standard views and mulliplc structural dccompositionsl41. and a powerful indexing mechanism will contribute grc·atly to this reduction .