FINDING THE AXIS OF AN EGG

FINDING THE AXIS OF AN EGG

Mike Brady, Department of Computer Science, University of Essex, Colchester, C04 3SQ, Essex, England.

Marr' s [2] axial symmetry theorem is extended to cater for situations in which the expansion function has no points of inflexion.

l, INTRODUCTION

Marr's [2] "analysis of occluding contour" (henceforth AOC) argues that we simply cannot avoid interpreting silhouettes as being formed by "generalised cones", where, among the various definitions which have been offered for such surfaces, we refer to the relative~y restrictive formulation given by Marr 11. p.467], That being the case, one faces the practical problem of extracting from a silhouette the cone's defining parameters: its straight line axis A, the twice continuously differentiable closed planar curve p(r, e) which is the cross section function of the cone, and the twice continuously differentiable positive real­ valued function h(z) which defines the expansion of the cross-section function p as it is moved along the axis A. Theorem 3 of [2], the "axial symmetry theorem" (henceforth AST), embodies the basic technique for extracting the image A* of the axis A. Unfortunately, one of the conditions of AST, necessary for the proof, is that h have at least one concavity. Since the end points of a generalised cone are clearly convex, this amounts to requiring at least one point of inflexion on h. which by lemma 1 of AOC is pre­ served by an orthogonal projection.

Many generalised cones have no points of inflexion in their expansion function. Fig. 1 shows some commonly occurring examples, (a) an ellipse (and in particular a circle), (b) an egg shape. and (c) a smoothed (right) cylinder. One clearly would not hesitate to assign axes to these figures, save perhaps for the circle. Of course, depending on the particular function h, the assignment of axes may be rather ambiguous (f~g. 2), This issue will not be dealt with in this paper.

0 0

ellipse

(a)

Do

egg shape

(b)

(c)

Generalised cones with no point of inflexion in their expansion function

Fig. 1

C>o

(b)

0 ellipse

(a)

(c)

Generalised cones whose axis assignment is ambiguous

Fig, 2

An examination of Fig. 1, and many similar ex­ amples, suggests a modified form of Marr's AST which relies upon finding zeroes and stationary points of the curvature of h. and upon matching parts of the contour along which the curvature (as opposed to the value of h) is monotonic. To bring this idea to fruition we need to examine how the concavity clause is used in the proof of the AST,

2. A REFORMULATED AXIAL SYMMETRY THEOREM

The assumed concavity of h is used to guarantee at least two matchable segments of contour, and to force a unique choice of axis. It is noted that a concave (convex) segment of h gives rise to two concave (convex) segments of the contour on either side of the image A* of the axis. possibly laterally displaced because of the eccentricity of the cone, The preservation of points of inflexion of h 1 where the curvature of h is zero, is guaranteed by lemma 1 of AOC and is used implicitly.

Suppose we replace "point of inflexion" by "a point where the curvature of h is zero or has a stationary value". Curvature is defined by

and

where h. = aih/azi, Since curvature depends on ~ the second derivative. its stationary points are only defined if the third derivative exists and its continuous, We now impose this requirement on h 1 which amounts to strengthening slightly the ·notion of a "nice" surface in AOC.

Marr's approach depends upon discovering which properties of a planar curve are preserved under a nonsingular linear transformation. in parti~-J ular under orthogonal projection. Lemma l of L2 shows that points of inflexion of the expansion function h are so preserved. and it is straight­ forward to show that stationary points of curv­ ature are too, Take any planar slice through the generalised cone containing the straight axis A. The definition of the generalised cone guarantees the existence of a continuous 1-1 onto function H : R + R2 which relates movement along A to the corresponding movement along the contour. Since L is linear. (LH)n = L(Hn) for

all n. In particular. it is crucial for the proof of Lemma 1 of AOC, though not noted there, that (LH) : 0 iff H = 0, n n

Most of the proof of AST carries over also. Tpe bounding contours are defined by A i)(z, ei) = h(z) * p(6i) for N ' z ' S and i = 1, 2, Th~t is to say there are two contour generators A(~) between any pair of "poles" of the generalised cone. Note that aA(i)/az: p(6.) u h 1 (z) 1 which is the basis of ~ c) the proof of AST, Moreover, An~ = p(6i) * hn(z) so that a portion of h having negative (positive) curvature produces two such components flanking the image of the axis and preserves their sense, The remainder of the proof of AST carri~s over and we have Axial symmetry theorem: Let L = p x h be a generalised cone with convex cross section Pt viewed distantly from its associated viewing plane IT, Then either the silhouette is circular and may be decomposed along any diameter or

1. the silhouette decomposes into seg­ ments by splitting it at points where the curvature is zero or is station­ ary
2. the image of the axis establishes an axial symmetry between max(2 1 n - 2) contour segments in which the corres­ pondence preserves the monotonicity of the curvature
3. if c. and c . 2 are corresponding ~1 ~ segments and if d(c .. ) denotes the ~J average perpendicular distance from d . . to the image of the axis. then ~J d(ci 1 )/d{ci 2 ) is independent of i.

3. REMARKS

Case 1 of the re-formulated AST is to cater for the case where curvature is constant and non­ zero, It is a happy feature of this re-formula­ tion that it explicitly involves curvat·ure. a surface proper~y ~hich ylays a vital role in perception ( [1], [3], [ .. ]), Since points of inflexion are points where the curvature is zero there are always at least as many sectors generated by the reformulation as in the orginal AST. and there are usually several more besides. This means that there are more points for a program to match and so the extraction of the axis is likely to be more accurate. even in the case of joins, such as Marr I]. fig. 16].

For completeness, the segmentation points and axes are given in Fig, 3 for the shapes in Fig . 1.

Segmentations points for the objects in Fig. 1

Fig. 3

ACKNOWLEDGEMENTS

The research reported here was completed while the author was a visiting scientist at the MIT Artificial Intelligence ~boratory. Thanks are due to the many fine scientists at the Labora­ tory who made the visit so memorable, particu­ larly Patrick Winston and Berthold Horn, Especial thanks are due to David Marr for his help, advice and inspiring example, Thanks are also due to the American referee for his insightful comments which led to substantial improvements in presentation of this paper.