Locating Polyhedral Objects from Edge Point Data

ABSTRACT

A method is presented to locate a general polyhedron in space with six degrees of freedom. A light stripe sensor is assumed to be capable of providing three-dimensional data points on known edges of the polyhedron to within a known accuracy. A representation is found for all the ways three line segments of fixed length can fall between the edges of a polyhedron. This representation, called an edge interval, is used in a tree search to find the location of each data point to within an interval on the edge. The final location of the object is determined by a one­ dimensional line search. The method is illustrated with simulated data from a unit tetrahedron and results from a computer implementation are presented. The tree search takes a negligible amount of time and the one­ dimensional line search takes a small additional incre­ ment.

I INTRODUCTION

The general problem is to determine the identity and location of a part in 3-D space to within a known error in real time. Gordon and Seering '87 describe a method which uses light stripes between known edges of a polyhedral object. When three light stripes intersect a right corner, they are able to locate the object in negligi­ ble time. Bolles and Horaud '86 "concentrate on edges because they contain more information than surface patches and are relatively easy to detect in range data," page 8. Grimson and Lozano-Perez '84 use points on a known face and an estimate of the surface normal at each point to locate the object. On page 9, they suggest that if a point is on an edge of an object, "the recognition process is greatly simplified."

The problem treated in this paper is to locate a gen­ eral polyhedral object with six degrees of freedom using data from a light stripe sensor. We assume that the light stripes locate 3-D data points on edges of the object to within a known error. Call each of these data points an edge point. Research is currently underway to develop effective sensors for this kind of application, see Tsai '85, Gordon and Seering '87 and Bolles and Horaud '86. There is a further assumption that each edge point is on a known edge of the object. This may occur in an appli­ cation such as in Gordon and Seering '87, where the ge­ ometric relation between the sensor and the object has been specified in advance or as in Arbab '87, where the edge points are identified with an edge via an interpreta­ tion method.

LOCATING POLYHEDRAL OBJECTS FROM EDGE POINT DATA

Gary Silverman IBM Scientific Center, Los Angeles, CA 90025

Roger Tsai and Mark Lavin IBM T. J. Watson Research Center, Yorktown Heights, NY 10598

In the next section the main results are provided on how the ends of a line segment of fixed length may inter­ sect two edges of an object in 3-D space. The Edge In­ terval Tree section shows how the edge intervals may be propagated as constraints in a tree search to find the lo­ cation of each edge point to within an interval on the edge. The section on Locating The Object shows how to locate the object within error by a one-dimensional line search.

II EDGEINTERVALS

Consider a line segment of fixed length, d, whose end points are known to intersect each of two edges, ~ and e1, see Figure I. Now add an orientation to each line, so that a minus ( - ) and a plus ( +) direction is defined along the line. Edge intervals are defined as a pair of in­ tervals, one interval on each line, with the following property. As the point of intersection on the first line moves in a monotonic direction from beginning to end of the first interval, the point of intersection on the sec­ ond line moves in a monotonic direction on the second interval. These intervals are mutually exclusive and in­ clude all possible intersections of the line segment with the two edges.

To describe the edge intervals introduce vertices VOO· VOl which define a finite edge eo in Figure 1 and a positive direction on eo· Define a parameterization of a point along the edge using a convex combination of the vertices,

so that,

1. Po(O) = VOO

Similar vertices and parameterization are defined for edge el .

Consider the line segment Poo· P1 0 of length d. This line segment is constructed to be perpendicular to edge eo- As one end of the line segment moves from Poo to P01 on edge eo. the other end moves from Pto to P11 on edge e1 . One end of the line segment is movmg along eo in the negative direction and the other end is moving along e1 in the negative direction. At Pot· P11 a sense of direction must change. This is because at P11 the line segment is perpendicular to edge e1. It is impossible to continue moving in the negative direction on both edges and still maintain contact. Therefore, as the line segment moves from Pot · P11 to Po2· P12 the sense of direction along eo must change from - to +. Similarly, from Po2· P12 to P03, P13 the senses are +, +. Finally, from Po3· P13 returning to Poo· P10 the senses are - , +. To convince yourself, cut out the line and re-trace this path on Figure 1.

To calculate values of ao and a1 that correspond to edge intervals, the orthogonality conaition

and the distance condition

must be satisfied.

Equations (4) and (5) may be reduced to a standard quadratic equation in ao. The solution is the following equations for ao and a 1, where a1 , bt, c1, Kl, K2 and g3 are dependent only on the edge vertices and tlie distance. These equations are too long to include here, but are in­ cluded in Silverman et. al.'87.

Cases where equations (6) and (7) are degenerate are classified as follows. If the distance, d, is shorter than the minimum distance between the edges, then the discriminant term in (6) is negative. If the edges are orthogonal, the discriminant in (6) is equal to zero. If the edges are parallel, the term al in (6) equals zero and the edge intervals are illustrated m Figure 2. In all of these cases, degenerate or non-degenerate, it is possible to compute the edge intervals by solving simple quadratic equations.

This is a complete representation of edge intervals along edges eo and el, and although Figure 1 and Figure 2 are p1anar, th1s representation extends imme­ diately to arbitrary edges in 3-D space. Errors in the edge point data will cause error in the final location of the object. For the parallel case shown in Figure 2 if the distance, d, is within sensor error of the distance between the edges, edge interval calculation may fail.

III THE EDGE INTERVAL TREE

The edge interval tree has three levels: Oth level, 1st level and 2nd level, one for each edge point. A node at the ith level represents an interval on ei. There is an arc emanating to the next level for each edge interval. The monotonic character of the edge intervals enables an edge interval tree search for a set of three valid intervals, one on each edge. The valid intervals are subsets of the respective edge intervJlls. A set of valid intervals contains all sets of values { cxo, ex i, cxi}.. such that; if each edge point is located at the value of ex; on its respective edge, then the three mutual distances are consistent with the sensor data to within error. This is a location where the edge point data fit the object.

Valid intervals are determined by propagating the edge intervals from eo to e1 to ~ and back to eo. The monotonic property oT the -edge intervals implies there is a continuous, monotonic mapping from any point ex; within the edge interval on e;. which with d··, maps to a unique point ex; on e;. Let this mapping and Yts inverse be denoted by the transfer functions,

and

The transfer function T ij is the location of a point on an edge at a given distance from a point on another edge, where both points are expressed parametrically as in (1).

The equation for T can be derived by solving

for (8) or (9). This leads to a quadratic equation

where az, ~. c2. are functions of ex;, see Silverman et. al.'87 for details. Tli1s quadratic equation is non-degenerate for any ex; in the edge interval on e;. The function 1jt indi­ cates there are two points on e; at a given distanPe from ex;. one each for the plus and minus root in (11). At any node in the edge interval tree search the correct sign in

( 11) is determined by the edge interval on e;. In the dis­ cussion below, let T denote a specific transfer function where the sign is determined by the edge interval being propagated.

Searching the Edge Interval Tree

A unit tetrahedron is illustrated in Figure 5. Three edges, eo. e1 and e2, are cut by a simulated light stripe. Three eoge points, Po, P1 , P2, are known to within a given sensor error. The three mutual distances between edge points may be computed, ~ 1 , d12 and d20· A model of the object provides the vertices for each edge in some canonical location. The edge intervals for the the first two unit tetrahedron edge pairs are displayed in Figure 3 and Figure 4. This example will be used to il­ lustrate the tree search.

The tree is propagated by intersecting intervals on common edges and transferring the resulting intervals to the next edge with (11). Pruning occurs when the inter­ sected interval is empty. The propagation and pruning steps for the tree differ at each level. Figure 6 shows the ~e interval constraint propagation from edge interval .t.tfl in Figure 3 to Eb in Figure 4. In Figure 6 the unit tetrahedron has been "unfolded" along e 1 to make a planar figure illustrating the edge interval tree search.

The Oth level: This level propagates intervals on eo to in­ tervals on e1 using the edge intervals. Let this mterval be noted by /li-1= [cx1, ex¥]. In Figure 6, 1 1 is actually the edge interval .t.tfl on e1, ex 1 e [0.577, 0.667].

The 1st level: This level propagates intervals on e1 to in­ tervals on ~ using d12. For the edge intervals from e 1 to ~· intersect the interval on e1 with /1, the interval passed in from the Oth level. Let this intersected interval be noted by H1 = [p1, PH If H1 is empty, then the tree is pruned at tliis point. h Figure 6, this results in !JJ being intersected with Ef2. Here H1 = /1 because /1 c .t.t2·

If H1 is equal to E12 then propagate H1 to ~ by using the respective edge interval. If not, propag~te H1 to ~ using the transfer function T. That is !2 = [cx2, ex~]. where

This is illustrated in Figure 6, where /2 = [0.500, 0.622].

The 2nd level: This level propagates intervals on ~ back to intervals on eo using dzo· The propagation and pruning steps at level 1 are repeated at level 2 using the edge in­ tervals from 1!2_ to lJ) and the distance, dzo· The result is an interval, llQ = [Po. PHJ, on eo·

Now propagate Ho to e~ to (!2 and back to eo to ob­ tain another interval lo = [cxtJ, cxHJ. That is,

Errors in the sensor data may cause localizations to be missed unless both intervals are increased. Let v0 be the intersection of the increased intervals, Ho and lo. If Vo is empty the tree may be pruned at this point. Any non­ empty interval, Vo, is a valid interval. This final pruning step is possible oecause the line segments d20 and dot must intersect eo at the same point, Po, to withm error.

IV LOCATING THE OBJECT

If the solution is known to lie in Vo = [ex6, ex~] a one-dimensional line search for a fixed point to within error, of the function,

will find all solutions within the valid interval. The line search is required because while all three distances are maintained by (16), both starting and ending points of intersection on eo must be the same to within error.

The object localization problem is solved by locating the edge point, Pb at ex; o,p elch edge, ei, for i = 0, I, 2. Once a particular triple (exo, ex1 , exi), is known a transfor­ mation to within error from model space to image space may be computed to fit the object.

A program has been written implementing the ideas presented here and it has been tested on the unit tetrahedron data. The edge interval calculation involves only a few quadratic equations to solve imd takes negli­ gible time. The edge interval tree search requires a few comparisons and some evaluations of (II) per node. This too takes only a very small amount of time. Any edge interval tree with three levels has a maximum of 84 nodes, because the maximum number of branches at a·ny node is four. The edge interval tree search for the unit tetrahedron has to examine only 15 out of the possible 84 nodes. The rest are pruned from the tree. Experience with the current program indicates a few seconds of exe­ cution time on the IBM RT PC programmed in C. This includes line search of two valid intervals. It should be possible to substantially improve upon this.

V ACKNOWLEDGMENTS

We would like to thank Bob Cypher of the University of Washington and our colleagues, Bijan Arbab, Fernando Vicuna and Jim Moore for many helpful dis­ cussions. The authors are also grateful to the referee whose comments resulted in a number of important clar­ ifications.