Determining Object Attitude from Extended Gaussian Images

1 Introduction

Orientation maps can be generated by binocular stereo [Baker and Binford, 1981] [Grimson, 1981], photometric stereo [Woodham, 1980], shape from shading [Horn, 1975], or by differentiation of Iaser range images[Brou, 1984]. By translating the surface normals of an object to a common point, a representation of the distribution of surface ori­ entation is formed, called the Extended Gaussian Image (EGI) [Horn, 1984]. Figure 1 shows the Extended Gaus­ sian Image of a polyhedron and the corresponding object.

Horn and Ikeuchi[1984] demonstrated the feasibility of using EGis for attitude determination, comparing the EGI of a prototype with a sensed EGI. The reconstruction method using the mixed volume suggests a new method for attitude determination. This method is practical and more robust than direct comparison of EGis. A detailed

discussion of this method is presented in fLittle, 1985].

'1- This research was supported in part by a UBC University Graduate

Fellowship and by the Natural Science and Engineering Research Council of Canada graut A3390.

DETERMINING OBJECT ATTITUDE FROM EXTENDED GAUSSIAN IMAGES

James J. Little·

Department of Computer Science The University of British Columbia Vancouver, B.C., Canada V6T 1 WS

2 Object Models

Objects will have surfaces tiled with planar facets. The intersection of half-spaces forms a convex polyhedron. A bounded convex polyhedron is a polytope. The direction of the outward facing normal w on a face of the polytope is the surface orientation, which can be identified with a point on the unit sphere U. The set of orientations of the faces of a polytope, 0, is referenced by indices 1 ... n.

A plane J supporb a convex body G if G lies on one side of the plane and G has at least one point in common with J. For any orientation w there is a unique support plane J for G with equation (w, x) = c. A support function of orientation can be defined:

A polytope in this setting can be represented by H (h1, h2 · · · hn) = (JI(w1), Jl(w2) ... Jl(wn)), the values of the support function at 0.

Two polytopes P and Q in R 3 are homothetic if

Homotheticity is invariance under translation and scaling.

The areas and orientations of the faces describe a func­ tion A(w); if the polytope has a face with orientation w, its value is the area of the face, otherwise, zero. This function is represented as a vector A of the values of A(w;).

The Extended Gaussian Image of a polytope P can be represented as a set of vectors N: {n;!n; = w;A;, A; = A(w;)}. Minkowski[1897] showed that when N sums to O, N uniquely represents a polytope, up to translation.

1 Reeovering Shape from an EGI

The reconstruction method derives from Minkowski's theo­ rem[1897], arising from the study of mixtures(convex sums) of convex bodies. The mized volume of polytopes P and Q, V(P, Q), is the product of the support function of P and the area function of Q:

As a consequence of the theory of mixtures of polytopes:

where V(P) is the volume of P. Equality holds only when P and Q are homothetic.

Minkowski's theorem states that, among all polytopes P of fixed volume, the P which minimizes V(P, Q) is homo­ thetic to Q. The reconstruction method[Little,1983] mini­ mizes the mixed volume to recover object shape.

2 Determining Attitude

Determining the attitude of a known object is equiva­ lent to finding a rotation R , such that R(E�I,wolotr~) = EG I,.n .. d· Attitude in R 3 can be identified with a rotation R(O,n), where 9 is the angle by which an object is rotated about an axis n in R 3 ·

To access the area function it is necessary to quantize orientation, tesselating U. The projection of the icosahe­ dron onto U generates a tesselation. The nurober of facets in a tesselation U can be increased by subdividing the tri­ angular faces of the icosahedron into smaller triangles. At frequency i, each face is mapped into i 2 triangles.

Attitude is quantized by the rotation group r 6o which brings the vertices of the icosahedron into correspondence. The difference between two attitudes is the angle of the ro­ tation taking one into the other. The minimum difference among the 60 attitudes in r 60 is 72°. For a detailed discus­ sion of methods for representing and quantizing attitude in R 3 and quantizing orientation on U, see Brou [1984].

2.1 Comparing Area Fundions

To determine object attitude from the EGI, Horn and Ikeuchi [Horn and Ikeuchi,1984] match the prototype EGI and the sensed EGI at a discrete set of attitudes. At each sample attitude the matehing measure between two area distributions is:

where A; is the sensed EGI area function at direction w; and AR(i) is the prototype area function evaluated at the direction to which w; is transformed by R. This amounts to maximizing the correlation of A and A. The attitude which minimizes the measure in Equation 2 is selected.

Area matehing can fail when the object attitude is off­ set from a sample attitude[Brou, 1984]. A polytope with m faces fills at most m cells on U. As the resolution of orien­ tation increases, the number of empty cells increases. If the attitude offset is near the cell resolution, the faces of the prototype and the object may not lie in the same cells, even at the correct attitude (the attitude in r 60 nearest the ac­ tual attitude). The minimummatehing error increases and the minimum may not indicate the correct attitude.

2.2 Mixed Volumes

Reconstruction builds a polytope whose area function fits the EGI; attitude determination seeks an attitude which rotates the sensed EGI into correspondence with the pro­ tctype EGI. Both determine a fit between an EGI and a model. Rotating a polytope preserves volume, so among all P' which are rotated versions of P, that P' which has the same attitude as P minimizes the mixed volume. To determine object attitude, minimize the mixed volume:

H; is the prototype support function and A; the sensed area function.

2.3 Support and Area Fundions

For polytopes, the area function A(w) is discontinuous; in contrast, the support function Jl(w) is continuous on U. The comparative smoothness of the support function can be seen by examining its relation to the area function, most easily for polygons. The area function of a polygon, for example, consists of a finite set of non-zero points in the interval 0- 211'. Its autocorrelation is 0 almost-everywhere. Not surprisingly, when the attitude of the sensed object is slightly different from the prototype (or any attitude in the sample set), the value of the area matehing is maximum. Discretizing A by sampling U is helpful, as Brou remarks, introducing a smoothing effect, widening eaeh of the pulses to the resolution. With discretization, small changes in attitude do not affect the area function, until the size of the attitude difference exceeds the resolution on U, when the errors recur.

The support function for a polygon can be written in terms of the area function A:

when the point on the polygon where w = 0 coincides with the origin. The support function is an integral transform of A and is much smoother. Because A varies rapidly, shift­ ing A by a small rotation changes its correlation with the prototype A significantly. The support function varies less and the error rate is correspondingly lower. For a polygon, the support function is piecewise sinusoidal, as is the mixed volume.

3 Experiments

Initials tests employ the complete EGI, the total spherical distribution, to demonstrate feasibility. To examine the effects of attitudes different from the test set, at a specified resolution, the attitude difference between the object and the prototype was varied. The results can be evaluated under two criteria: the magnitude of the rotation between the selected attitude and the correct attitude, and, where the method ranks the correct attitude (it should have rank 0 - lower is better).

The EGI of the polytope shown in Figure 1 was rotated about the coordinate axes by angles of 5, 10, 15 and 20 degrees and its attitude determined by both methods. At frequency 2, the area matehing method fails at angles as small as 15.0°; both failsometimes when the angle is 20.0°. When the mixed volume method fails, its failure is less severe in two respects: the attitude selected is closer to the correct attitude and the rank of the correct attitude is lower. Area matehing fails in 4 out of 12 cases and MV in only 1 out of 12.

The results for the 20° rotation are shown in another form in Figure 2. The graph shows, on the vertical axis, the values of area matehing, in a dotted line, and mixed volume, in a solid line; the horizontal axis shows the atti­ tudes (from r 60) at whieh the matchings were evaluated. The horizontal axis is separated by tick marks into regions whieh are 0, 72, 120, 144 and 180° from the prototype at­ titude. Point A is the minimum found by MV, correctly identifying the object attitude. Point B, the value of the area matehing method for the correct attitude, is rather high; there are 21 attitudes with lower values. The area function aehieves a minimum (point C) at an attitude in the 72o set.

At frequency 3, the MV method errs in 2 out of 12 cases (both at 20° offset), while the area matehing method fails for 6 out of 12 cases (some as little as 10o offset). In general, the area matehing method performs worse at a finer resolution. Finally, at frequency 5, the nurober of errors increases, for area matching, from 6 out of 12 to 8/12, while the mixed volume method fails twice. Three other objects, of varying eccentricity, were tested. The MV method succeeded for all offsets, while area matehing failed 8 times at frequency 3 and 14 times at frequency 5.

In all cases, MV ranks the correct attitude in the top 5, suggesting that more sophisticated procedures can be ap­ plied to these to determine correct a.ttitude. Area matehing performs much more poorly at ranking the correct attitude. The better behaviour of MV at lower resolutions also sug­ gests that MV would be useful in a coarse-to-fine search strategy.

3.1 Visible Subsets of EGis

In pra.ctice, the sensed portion of a surface corresponds to a single visible hemisphere of the EGI. With only partial in­ formation, experiments with several prototypes contrasted the MV teehnique with the area method. In no case does the MV method fail where the area method succeeds; in all cases, the ranking of the MV method is lower than the

·- -- ·- ·- ·---·- ·-·-·- ·- -- ·1

Figure 3: Non-convex polygon and its reconstruction

area method. There were 3 times as many errors by the area matehing method.

Using MV for attitude determination depends on the fact that volume V(P) remains constant (see Equation 1). lgnoring this effect incurred no penalty in these experi­ ments, because the contribution of invisible faces to the mixed volume is negligible. A reconstruction method makes possible construction of suitable invisible faces.

4 Non-Convexity and Attitude

To extend the use of EGis for non-convex objects, con­ sider using the support function of the convex object re­ constructed from the area function of a non-convex object. Dashed lines in Figure 3 delimit the convex polygon corre­ sponding to the area function of this non-convex polygon. If, hypothetically, the entire area function of the sensed ob­ ject were available, then recovering the attitude of the non­ convex polygon would be indistinguishable from recovering attitude of the convex polygon~ Using complete EGis and ignoring the effects of self-occlusion, this method proved ef­ fective for a set of sample polygons, including the polygon in the Figure 3. This holds the promise that mixed volume method can be applied to attitude determination for non­ convex objects, especially where the effects of self-occlusion are small.

5 Conclusions

An EGI supplies the sensed area function for an object. The object model permits calculation of the support func­ tion. The mixed volume combines these two functions; it is minimized when the attitude of the model matches that of the sensed object. Because of the smoothness of the support function, the mixed volume technique is robust for determining the attitude of convex objects. The experi­ ments described here demoostrate its effectiveness and its insensitivity tosmall changes in attitude which affect other methods. This method can also be applied to non-convex objects when the effects of self-occlusion are small.