Object Identification from Parallel Light Stripes

ABSTRACT

In this paper, an algorithm for identifying an object from a set of known objects is presented and justified. The novelty of this algorithm, called Mask, for object identification is in its use of three-dimensional data which has been obtained from projection of parallel laser light planes. The knowledge that laser light planes are parallel to each other allows automatic discovery of two con­ straints from the three-dimensional data. The first con­ straint is based on colinearity between various points and the second constraint on coplanarity between various segments of the three-dimensional data. These automat­ ically derived constraints, then, are used by Mask in a tree search algorithm for object identification. Mask has been implemented in Prolog and sample applications to various objects are presented.

INTRODUCTION

Suppose a specimen object is selected from a set of known objects. It is assumed that all objects are polyhedral (possibly nonconvex). The specimen object may have up to six degrees of freedom relative to the sensors. How can a robot recognize the specimen object? Recognition in this context means (1) identifying the ob­ ject as one, or none, in the set of known objects and (2) finding the exact location and orientation of the specimen object. The robot knows about an object if it has access to a polyhedral model of the object. A polyhedral model of an object consists of (1) a name for the object, (2) a list of edges, each described by starting and ending points, and (3) a list of faces, each described by the forming edges. This paper is a contribution, not to three­ dimensional sensing, but to the process of using such data in object recognition. It differs from other approaches in that it discovers constraints from the three-dimensional data which are then applied in the tree searching process.

In order to recognize the specimen object, the robot will first generate a series of parallel laser light planes. One method to accomplished this is by using optical de­ vices (Mersch and Stubbs 1986). The distance between parallel planes can be specified as well. Once the parallel light planes are generated, the space curves which are formed as a result of the intersection of each light plane with the object can be extracted, see (Echigo and Masahiko 1985), and (Tsai 1985). Since we are working with polyhedral objects, each space curve is actually composed of a series of line segments. Thus, each space curve is reduced to a list of pairs of 3-D points which

OBJECT IDENTIFICATION FROM PARALLEL LIGHT STRIPES

Bijan Arbab

IBM Scientific Center, Los Angeles, CA 90025

describe the starting and ending point of each line seg­ ment. Hereafter, this reduced Jist is referred to as the list-of-line-segments.

For example, in Figure I points pi to p8 describe the first list-of-line-segments and all lie in one plane; similarly ql to q7. After all, they were obtained from intersecting a light plane with the object. The line segments in a list­ of-line-segments are not always connected. Discontinui­ ties are due to occlusions. Thus, not every point in the list-of-line-segments corresponds to an edge of the object. Mask, however, requires that every point correspond to an object edge. To solve this problem which is caused by occlusions, the list-of-line-segments is further reduced to only those points that lie on an edge of the object. Hereafter, this reduced list is referred to as a light probe. Note that a light probe refers to a connected set of edge­ points; not just projection of a light plane on an object. This reduction is possible and applied on the grounds that a data point in the list-of-line-segments lies on an edge of the object if and only if it is connected on both sides to other points. For example, in Figure I point p2 is an edge-point, however, points p4 and p5 might not corre­ spond to edges of the object.

Mask takes as input, a collection of light probes and an enhanced polyhedral model of some object. The output consists of a set of object edge to edge-point assignments if the collection of light probes match the object model, otherwise, a failure is reported. This output can then be used to determine the object's exact location and orien­ tation, see (Silverman, Tsai and Lavin 1987). The set of object edge to edge-point assignment is also referred to as an interpretation (Grimson and Lozano-Perez 1984).

The polyhedral model of an object is enhanced by precomputing (1) a table containing Min-Max distances between every pair of edges of the object and (2) a possible-next-edge-list for each edge of the object. The Min-Max distance table is an idea taken from (Grimson and Lozano-Perez 1984). A possible-next-edge-list for an edge Ei is simply a list of all the edges on the adjacent faces. Note that consecutive edge points of a light probe would have to lie on edges of adjacent faces due to planar intersection of light with the object. These tables are precomputed and stored with the polyhedral model of every object.

Mask is composed of three phases which are described ih the following three sections. In phase I, light probes are collected in various groups and certain conditions that hold between groups are discovered. Phase II assigns to each group of light probes a list of valid interpretations. These assignments are based on the Min-Max distance table and the possible-next-edge-list. Phase III propa­ gates the conditions that were discovered by Phase I among the valid interpretations of each group as com­ puted by phase II. As a result, a set of consistent inter­ pretations is assigned to each group. Application of the algorithm to sample problems is then discussed.

PHASE I

The collection of light probes is first partitioned into various groups. Light probes correspond to the same group if and only if they come from adjacent parallel light planes that have intersected all the same edges of the specimen object. Thus, light probes are placed in the same group if and only if they satisfy two conditions. First, all the light probes in the same group must be of the same length. Light probes have the same length if they contain the same number of edge-points. Second, the corresponding points of all the light probes, in the same group, must be on the same edge of the object. This can be determined via a colinearity test.

The grouping of light probes, then, is done by selecting the first and second consecutive light probes of the same length and simply assuming that they correspond to the same edges of the object. The rest of the light probes, of the same length, which immediately follow the first two light probes can then be tested for colinearity on all the corresponding points. This technique for grouping light probes is correct on the grounds that the distance between parallel light planes is controllable and can be decreased, thus increasing the number of light planes, such that the smallest discontinuity in any of the known objects would not be skipped over. For an example of light probe grouping, see Figure 4 where light probes have been col­ lected together in six groups labeled gl to g6.

The presence of errors, introduced by various sensing devices, in the light probe data can cause the test for colinearity between three points to fail, when in fact the three points are colinear. Thus, the light probe grouping is not always unique. For example, in Figure 4 it is pos­ sible, due to errors, to collect light probes in group g3 into two or more smaller groups. Mask, however, is in­ sensitive to the various groupings of the light probe. It suffices to find any one of the possible light probe groupings.

After the initial light probe grouping, two conditions that may hold between members of any two groups are discovered. These conditions will be used in the third phase of Mask as constraints in a tree search algorithm, as in (Waltz 1973) and (Huffman 1971). The first condi­ tion holds between two groups gi and gj if for some N and M the Nth edge points of all light probes in gi are colinear with the Mth edge points of all light probes in gj . For example, in Figure 4 the second point of any light probe in group g2 is colinear with the second point of any light probe in group gl . In fact, they all lie on edge e2. The third point of any light probe in group g5 is colinear with the fourth point of any light probe in group g3. In fact, they all lie on edge elO. Note that here, colinearity be­ tween points of light probes in various groups does not always imply that the points must correspond to the same edge of the object. It could be that they correspond to two different object edges that happen to be colinear.

The second condition holds between two groups gi and gj if for some N and M the Nth line segment of all the light probes in gi is coplanar with the Mth line segment of all the light probes in gj . For example, in Figure 4 the first line segment of any light probe in group gl is coplanar with the first line segment of any light probe in groups g2, g3 and g4. In fact, they all lie on the face which is composed of edges el, e2, e3, e4 and e5. The second line segment of any ·light probe in group g5 is coplanar with the third line segment of any light probe in group g3 and g4, also with the second line segment of any group in g2 and gl . They all lie on the face which is composed of edges e2, el4, elO and el5.

The presence of errors in the light probe data can cause the tests for colinearity and coplanarity that are employed to detect the above two conditions to fail. This failure implies that not all of the conditions between points and probe segments are detected in this phase. A complete list of the two conditions, however, is not a requirement. A partial list of the conditions will suffice. Errors in the light probe data do not play an important role -in the next two phases, as the computations involved are symbolic.

PHASE II

The second phase of the algorithm starts out by pick­ ing from each group only two light probes, the first and last one. These are selected on heuristic grounds only. This heuristic is based on the grounds that Min-Max dis­ tances. between edges of the object are more likely to oc­ cur around starting and ending points of edges. For each light probe a collection of valid interpretations is formed. The exact definition of a valid interpretation is given be­ low. The set of valid interpretations for each group, then, is formed by simply taking the intersection of all valid interpretations for the first light probe with all valid in­ terpretations for the last light probe. This is on the grounds that both light probes correspond to the same group and thus must correspond to the same object edges.

An interpretation for a light probe is a list of object­ edge to data-point assignment. For example, (el , e2, el5) is one possible interpretation for the light probe composed of the three points: (pl , p2, p3) and it assigns edge el to point pl, e2 to p2 and el5 to p3. An interpretation for a light probe is valid if and only if it satisfies two constraints. It is possible to state other constraints but only two will be discussed, others are described in (Arbab 1987). The first constraint simply states that the actual distance between points Pj and Pk which has been obtained from the specimen object must be within the Min-Max distance that actually holds between edges Ej and Ek of the object. The second constraint applies on the ground that (a) the light probe data does not contain any discontinuities and (b) it is impossible, in such a case, for a laser light plane to strike any face of the specimen object more than once. Thus, edges E1 to Ei can be assigned to points P1 to Pi of a light probe if and only if (1) the distance between Pj and Pk for 1 = < j < k = < i is bounded by the Min-Max dis­ tance between Ej and Ek and (2) an edge En can not be assigned to a point Pn if it belongs to a face that has al­ ready been assigned to a point Pm for l=<m<n=<i.

With these two constraints in hand a tree search algo­ rithm for a light probe is constructed. Every node in the tree corresponds to a point in the light probe. There is an arc emanating from each node for every object edge that can possibly be assigned to the node. The depth of this tree is equal to the length of the light probe. In Fig­ ure 2, a sample search tree for the first light probe of group gl of model house object is shown. For example, the assignment of edge el to point pl is not consistent with the assignment of edge e14 to point p2 on grounds of the first constraint, i.e., the distance between points p1 and p2 is not within the Min and Max distances between edges el and e14. The assignment of edge el5 to point pl is not consistent with the assignment of edge e15 to point p2 on the grounds of the second constraint. A standard depth-first left-to-right backtrack tree search al­ gorithm is then employed to propagate the constraints among the nodes of the tree. Only those interpretations that completely satisfy both constraints remain. These are the set of valid interpretations for a light probe.

PHASE III

A collection of valid interpretations for each group of light probes was constructed in the second phase. The size of this collection typically ranges from tens to hun­ dreds for the objects experimented with so far. Recall that, in the first phase of the algorithm two conditions that could hold between various groups were extracted. They were: (1) colinearity between various light probe data points in different groups and (2) coplanarity be­ tween various light probe segments in different groups.

In this phase, those conditions are employed as con­ straints and together with the Min-Max distance con­ straint, they form the backbone of another round of tree searches.

This time, a node of the tree corresponds to a group of light probes. There is an arc emanating from a node for every possible valid interpretation that can be assigned to the node. The depth of the tree is equal to the number of groups. In Figure 3, a sample search tree for the model house object is shown. For example, interpretation (e5, e3, el4) for group g2 is not consistent with interpre­ tation ( e 1, e2, e 15) for group g 1 on the grounds of the first condition, i.e., edge e3 and e2 are not colinear. In­ terpretation (e5, e2, el5) for group g2 is not consistent with interpretation (ell, e7, e6) for group gl on the grounds of the second condition, i.e., no line segment connecting ell to e7 can be coplanar with a line segment connecting e5 to e2.

The Min-Max distance constraint is applicable to in­ terpretations Ii and Ij for groups Gi and Gj. This is on the ground that, for every light probe Pri in Gi and Prj in Gj the distance between every point of Pri and Prj must be within Min-Max distances of the corresponding edges in Ii and lj. A standard depth-first left-to-right backtrack tree search algorithm is then employed to propagate the three constraints (the first and second condition plus the Min-Max distance constraint) among the nodes of the tree. Only those interpretations for each group that completely satisfy the three constraints are left behind. These are the set of consistent interpretations for each group. A group can have an empty set of consistent in­ terpretations if light probe data from the specimen object does not correspond to the given object model.

APPLICATION

Application of Mask to a simple model house, shown in Figure 4, is described below. For more complicated examples, including non-convex and occluded objects, see (Arbab 1987). The edges of the object are labeled as el to e15. Intersection of some parallel light probes with the model house are shown. It is important to note that Figure 4 is showing the light probes and not the actual light planes that intersected the object. The distinction being that a light probe is obtained from the resulting intersection of the light planes according to the procedure specified in the introduction.

The data was obtained through simulation and some errors were artificially injected in the data. Each light probe has been classified by phase I of Mask as a member of some group. There are a total of six groups, labeled gl to g6. There are 11 colinearity and 20 coplanarity re­ lations that hold between light probe points and segments of various groups. Phase II of Mask finds 48, 84, 32, 120, 128 and 60 valid interpretations for groups gl to g6. However, there are only 4 consistent interpretations that can be assigned to groups gl through g6 and are discov­ ered by phase III of Mask in approximately eight seconds on an IBM 3081.

Assignment of an interpretation to a group means that points of a light probe within that group can be assigned to edges in the interpretation list. For example, "gl --> (el,e2,el5)" means that first point of any light probe within group gl can be assigned to edge el, second point to e2 and the last point to el5.

Mask has found the solution, up to symmetry, of every problem to which it has been applied. It also reports a failure when light probe data from the specimen object does not match the model object.

ACKNOWLEDGEMENT

The author is grateful to Bernie Dimsdale, Hal Hichborn, Mark Lavin, Jim Moore, Eugene Paik and Gary Silverman for their discussions and comments on this work. The author is also grateful to the anonymous referee whose comments resulted in a number of impor­ tant clarifications.