Recovering Surface Shape from Boundary

ABSTRACT

Humans can recover the shape of a surface from Its Image boundary. The authors have presented a new approach to shape from boundary[4). It Includes three points: the line of curvature (LOC) ~egularlty, an algorithm for constructing LOC net from boundary, and the computation of surface orientation from LOC net. Briefing these Ideas, this paper examines the underlying problems of the approach and proposes Improvements.

h INIR<DX:T I (Ill

Probably line drawing Is the most efficient means of describing our three-dimensional world In a two-dimen­ sional manner. There are generally two kinds of contours In a line drawing: contours across surfaces and boun­ daries. This paper focuses on the latter, though the former and the latter are not completely distinct matters. It Is worthwhile to mention the pioneering paper written by Barrow and Tenenbaum[1), In which they propose a three-step paradigm for shape from boundary: ( 1 ) c I ass I f yIn g I l ·n e s Into extremal and discontinuity boundaries, (2) Interpret lng each ·2-D Image curves as 3-D space curves, and (3) Inter­ polating the surfaces.

The authors[4) have proposed a new approach to shape from boundary, from a geometrical point of view. The boun­ daries are usually not (at least not perceived as) arbitrary curves on the surfaces, but special ones that carry more Information than others. The approach has three major parts: (1) the line of curvature regularity, (2) an algorithm for knitting LOC net from boundary, and (3) the computation of surface orientation from LOC net. This paper first outlines the previous paper (It Is Impossible to describe the de­ tails because of the space limitation, and we Invite the readers to consult that paper If necessary), then examines the underlying problems of the

Gang Xu and Saburo Tsuji

Department of Control Engineering Osaka University Toyonaka, Osaka 560, japan

approach, and proposes Improvements.

In the Inference from two-dlmen­ sionalllty to three-dimensionality, additional Information Is necessary. What Is It In shape from boundary? The I lne of curvature regularity provides one answer. It Is formulated as: In absence of other evidence, the boundary segments In Image that can be Inter­ preted aa (3-D) linea of curvature on the surface they bound should be Inter­ preted ao. An ex amp I e Is shown in FIg. 1(a). A closed boundary Is segmented Into four segments A, B, C and D, which are Interpreted as two pairs of lines of curvature (A-B and C-D).

An algorithm is proposed to cons­ truct an LOC net from four boundary segments. As shown In Fig. 1(b), the segments a0-a1, b0-b1, cO-cl and d0-d1 bounds a surface. The points a2, b2, c2 and d2 are their chord centers, res­ pectively. The points a3, a4, b3, b4, c3, c4, d3 and d4 are the chord centers of the new segments. The segmentation Is repeated until sufficient resolution Is obtained. We first find a point that has both an equal distance to the points a2 and b2, and an equal distance to the points c2 and d2, which we regard as the Intersection of the seg­ ments a2-b2 and c2-d2. Similarly, we can find other points, as shown in Fig. 1(c), which approximate the segments a2-b2 and c2-d2.

Once the LOC net is knit in Image, the surface orientation can be computed from it. Orientation Is represented by slant and tilt. A right angle In space Is foreshortened to an obtuse angle In Image, which provides a constraint on perceiving the original surface orien­ tation. The more obtuse the angle, the more strong the constraint. The inter­ sect I on on the LOC net that has the most obtuse angle Is picked up, and Its tilt is estimated as the bisector (see Stevens[3) for details). Then this estimation Is propagated to other Intersections along the net by a twostep approximation method modified from the propagation on cylindrical sur­ faces. The slants are determined after the tilts.

By exploring natural regularities, one can find what he/she needs in the inference from two-dimensionality to three-dimensionality. The LOC regulari­ ty is such one that we need in the Inference of surface shape from boun ­ dary. About it, however, one might ask two questions: If a boundary in image can be interpreted as projections of lines of curvature, do they really correspond to lines of curvature in space? And, how do we decompose a closed boundary into segments that are likely to be projections of lines of curvature? The answer to the first question Is that no matter true or not, humans do interpret them as so, and that Is all that can be done. For­ tunately, observations convince us that the probability of "illusion"(3] is very low.

To answer the second question, recall that in general four lines of curvature bound a surface patch, and they Intersect at a right angle in space. When projected onto image, the Intersections are the tangent disconti­ nuities along the boundary. The only exception is when an intersection is on an extremal boundary and the I ine of sight divides the right angle; the tangent Is continuous (Fig. 2). How­ ever, such intersections can still be distinguished by curvature discontinu i ­ ties or extrema. Another criterion to assIst the previous two is simi I ar i ty. The two lines of curvature of each pair are similar In space, and reserve simi­ larity In image to some degree. A clos·d boundary should be so segmented that the two segments of each pair are as similar as possible. Any closed boundary that cannot be segmented by the above criteria should be regarded as not being projections of lines of curvature.

~ NET-KNITIIN:i AL<.XRinM

The algorithm, as described in Section 2, is based on the following three assumptions: (1) both pairs of lines of curvature have the property of constant ratio intersection; (2) the arc center of each image segment is the projection of the arc center of the corresponding space curve, and (3) the arc center is also the chord center. Actually, however, few surfaces satisfy all the three assumptions. Thus, a constructed net using this algorithm only approximates the original surface. We call It the first-order approxima­ tion. An example is Illustrated in Fig. 3.

The first-order approximation can be refined. The third assumption can be eliminated by modifying the chord cen­ ters to be the arc centers by a relaxa­ tion method. This is done two-dimen­ sionally. We call the net so modified the second-order approximation. The second assumption can also be eli­ minated. Since the surface orientation at each intersection can be computed, the 3-0 arc length can be obtained by integration. Using a relaxation method again, the 2-D arc centers are modified to be 3-D arc centers. We call this modified net the third-order approxima­ tion.

~ StRFACE <JUENTATI<Jil aM'liTATI<Jil

Once the net is knit in image plane, surface orienta f ion at each intersection can be computed up to a certain accuracy by the bisector esti­ mation and a propagation method. How­ ever, it seems that humans perceive the surface shape stably and consistently. This suggests that t~ere may be some mechanism in human vision that uniquely det~rmines surface shape from boundary. I f t he LOC net i s accurate and con­ sistent with the boundary, then the mechanism should also uniquely deter­ mine the shape from the net. This mechanism remains to be found.

Note that we are by no means attempting to model the same process in human vision. No evidence shows that humans first build an LOC net and then compute surface orientation from it.

The inference of shape from boundary is inherently a process of interpolation, no matter what the approach is. But what is different between our approach and that of Barrow and Tenenbaum? They interpret the boun­ dary segments separately, whereas we interpret the boundary segments glo­ bally and consistently. Constructing the LOC net act u a II y fun c t i on s as interpolating the surface.

We have first outlined an approach to shape from boundary which is des­ cribed in detai I in our previous p a p e r[ 4 ) ( 1 s t I CCV ) · T h i s p a p e r i s t o complement the ideas in that paper. We have proposed criteria for decomposing a closed boundary into segments that are I ikely to be projections of I ines of curvature, and a direction for refining the LOC net. Some underlying problems of the approach have also been examined.

REFFRFN:ES

1. H. G. Barrow and ]. M. Tenenbaum, Interpreting line drawings as three-dimensional surfaces, Art if i cia 1 In t e 1 I i gence I 7, 1 9 8 1 , pp.75-ll6.
2. S. R. Reuman and D. D. Hoffman, Regularities of nature: the inter­ pretation of visual motion, From Pixels To Predicates: Recent Advances in Computational and Robo­ tic Vision, Eds. A. P. Pentland, Ab I ex , 1 9 8 6 , p p. 2 0 1 - 2 3 6.
3. K. A. Stevens, The visual interpre­ tation of surface contours, Artificial Intelligence 17, 1981, pp.47-73
4. Xu and S. Tsuji, Inferring surfaces from boundaries, Proc. 1st ICCV, 1987, London.