Three-Dimensional Shape From Line Drawings

I Introduction

Much recent vision research has emphasized the impor­ tance of image contour for shape interpretation [1,2,3,4,5,6,7). Tenenbaum and Barrow (1) argue that image contour, for ex­ ample, is dominant ove-r shape from shading. Pentland (8) has presented examples in which the addition of a contour substan­ tially improved the interpretation of a shaded surface. It seems that contour is one of the strongest sources or information for shape perception.

One source of evidence of the strength of contour information is line drawings. When we examine a line drawing, our perception of the three-dimensional shape implied by such a drawing is nearly always clear and unambiguous. How can we account for this, given that purely geometrical constraints admit or an infinite number or valid interpretations!

A. An Observation About Human Perception

When we observe line drawings such as those in Figure 1 (a), we have a clear perception or a non-planar three-dimensional structure. Notice that if we were to segment each of these draw­ ings at t.he circled points, each of the resulting segments would have the same shape as they did when they were still hooked together and would be approximate/11 planar, as is shown in Figure 1 (b). Thus, for these line dra-wings the problem of recover­ ing the three-dimensional structure can be reduced to the prob­ lems of ( 1) segmenting the curve into perceptually planar seg­ ments, and (2) finding the plane that contains each of the curve segments (the osculating plane) (9). Once we know the orienta­ tion of the plane which contains a curve segment we can then easily determine its three-dimensional shape.

· The research reported herein was supported by the Defense Advanced Research Projects Agency under Contract No. MDA 903-83-C-0027; this contract is monitored by the U. S. Army Engineer Topographic Laboratory. Approved for public release, distribution unlimited.

If we "by hand" try to segment image contours into planar regions, we find that the strategy can be successfully applied to a surprisingly large number of naturally-occurring image con­ tours. For some contours, however, it is not obvious how well this strategy will work, primarily because there are no points which st>gment t.he space curve into planar regions. An example of such a curve is the helix shown in Figure 2 (a). Nonetheless, it may still be possible to obtain a good approximation or the three-dimensional structure of such a curve using this strategy.

B. A Strategy For Recovering Three--Dimensional Shape

This observation about human perception leads to the fol­ lowing processing strategy:

• (I) Segment the image contour in such a way that each segment. is likely to comprise a projection or a planar segment of the space curve.
• Calculate the planes implied by the segments from (1).
• Assemble the results of (2) into an estimate of the shape of the entire space curve.

The specific criteria for the initial segmentation are not dealto with here. It is clear, however, that the image contour should be segmt>nted at singular points of curvature (maxima, minima, and inflection points). Hoffman and Richards (10) have presented a theory of curve segmentation that addresses this issue. Our approach will be to temporarily ignore the segmentation problem and to simpl)· estimat-e the orientation of parts of the space curve from many local parts of the image contour. If valid results are forthcoming with this approach the. method can only be improved with more elaborate segmentation. ·

C. Modeling the Space Curve

\Ve shall model a space curve in the conventional way, as a t.hree-dimensional \'ector function X(-') of one parameter-' which is assumed to be a natural parameter, i.e., ldx(.,)/dsl = 1. The shape of such a curve is completely determined by two properties that arc scalar functions of": curvature, ,q.,), and torsion, r(-') (9). Curvature is always nonnegative; only straight lines and inflection points have zero curvature. Torsion may be intuitively defined as the amount of "twist" in the curve at a point"· Another way to visualize torsion is as the degree to which the osculating plane (the plane which contains the curve) is changing. Only planar curves have zero torsion everywhere. Unlike curvature, torsion may be either negative or positive.

The presence of torsion is not directly evident in the image. It simply results in more or less foreshortening as the osculating plane of the contour varies. The effects of torsion', therefore, can be exactly mimicked by changes in curvature, and vice versa.

ll Theory or Contour Interpretation

Not all three-dimensional interpretations of an image con­ tour are equally likely. If we assume that spatial isotropy holds, then we know that viewer position is independent of the shape of the curve - which allows us to make a reasonable guess about the latter's three-dimensional shape [8]. The first step towards a guess at the space curve's shape is the following proposition:

Proposition (Zero Torsion). The maximum-likelihood estimate of the torsion of the space curve ia aero (i.e., no "twisting" of the curve).

This proposition follows because the assumption of spatial isotropy implies that the viewer's position and the shape of the space curve are mutually independent. ThUll, not only is it un­ likely that significant features of the curve will be hidden from view by coincidental alignment of the viewer and the curve, but, conversely, it is likely that the viewed scene will not change much with small changes in viewing position." The appearance of a curve with substantial torsion · will change considerably with small changes in viewer position; if we assume spatial isotropy, therefore, we must expect that the torsion of the curve will be smal l.

Furthermore, given that spatial isotropy implies that the viewer position and the shape of the curve are mutually inde­ pendent, the torsion of the curve must then also be independent of viev.ccr position. Consequently, the torsion of the curve is as likely to be positive as negative, and thus the mean value (and maximum-likelihood estimate) for the magnitude of the torsion is zerot . The probability that the torsion is small implies this estimate will generally be a good one.

A. Estimation 'Nith The Assumption Of Zero Tonion

Even if we assume that torsion is zero (i .e., the space curve is planar), there is still a two-parameter set of space curves that could have generated that imaged contour. The two parameters correspond to the two degrees of freedom of the osculating plane:

Assume that we are given a small portion of an imaged contour, and asked to estimate the three-dimensional shape of t.he space curve which generated that image. If we measure the position and curvat ure at three points on the imaged contour, then we can uniquely define an elliptical arc that fits the image data. By the previous proposition, this elliptical arc is most likely caused by a space curve that is either an arc of a circle or of an ellipse, as those are the two planar (zero torsion) shapes which can project to an ellipsett .

Previous research ([2], (12]) has shown that the maximumlilelihood estimate of the space curve's shape is given by the following proposition (see also [2]):

·This is often referred to as the assumption of general position. Thus, spatial isotropy implies general viewing position.

·· As a function of position on the image contour rather than as a function of 11

t Note that at places where the curvature is zero - straight segments and inflection points - the torsion is not defined and may arbitrari ly be taken to be zero. That i~, the osculating plane may be changed freely at these points without affecting the shape of the space curve.

tfThis is true of both perspective and orthographic projection, however , we will deal exclllllively with the more general case of perspec tive foreshortening.

Proposition (Planar Interpretation). Given an ellip­ tical segment of an image contour and that the space curve is planar, the maximum likelihood estimate of the space curve's three-dimensional shape ia a .egment of a circle.

Barnard [12] has constructed a maximum entropy estimator that il!lplements this proposition for perspective images and that is tolerant of digiti zat.ion noise. Operating under the assump­ tion that the space curve has zero torsion, it chooses the orienta­ tion that maximizes the entropy of backprojected image contour curvature measurements. That is, curvature is first measured at several points in the image contour, then the curvatures of hypothetical planar space curves of essentially all orientations are computed by backprojection, and, finally, the orientation that leads to the space curve of most uniform curvature (in the sense of maximum entropy) is selected. In general, three image con­ tour curvature measurements are sufficient for an unambiguollll maximum-entropy interpretation (up to a Necker reversal).

ill Three-Dimensional Estimation

Now let us return to the general problem of estimating the shape of the space curve, given a smooth imaged contour. Let us first take three curvature measurements along the imaged contour. These three measurements define an ellipse. As jllllt described, this leads to a circular interpretation of the space curve. Now suppose that we have additional image contour cur­ vature measurements. There are, then, two cases to consider:

First case: the new points 6t on the same ellipse. In the first. case we have quite strong evidence of the space curve's shape. For, if the osculating plane were changing, the curvature would have to be changing also - and in jllllt such a manner as to exactly cancel (in t.he image) the effect of the changing osculating plane. Similarly, if the curvature of the space curve were changing, the osculating plane would have to change just exactly enough to cancel the effect of the changing curvature. As sue h a "conspiracy" to cancel the visible effects of change is unlikely (a direct violation of general position), we must conclude that there was neither torsion nor change in curvature, and, thus, there is a great (in fact, maximum) likelihood that the new image curvature measurements result from the same circular space curve defined by the first three measurements.

Second case: the new points don't 6t on the same ellipse. What if the additional measurements lie off the ellipse defined by the first three measurement~! Then we can be certain that either the curvature or the osculating plane (or both) of the space curve has changed. This new point is, therefore, a possible place to segment the curve. What we must do when we encount er such a point is advance along the image contour until we are completely past the point, and obtain a new estimate of the space curve's osculating plane. If the new osculating plane has the same orientation as the previollll osculating plane, then we have evidence that the spaee curve continues to be planar, and we should not segment the curve. If, however, we obtain a different orientation for the osculating plane, then we should segment. the space curve and begin a new planar segment of the curve.

As any smooth image contour may be closely approximat-ed by portions of ellipses and straight lines · , this interpreta­ tion strat.egy will yield a single interpretation for the threedimensional shape of the space curve (up t.o Necker reversals). Further, this interpretation will be the most likely interpreta­ tion on a point-by-point basis. It should be noted that the first two steps of this estimation strategy are similar t.o the strategy proposed in [1].

·only the third and higher derivatives of the imaged contour that will fail to be exactly matched. People, it should be noted, are very poor observers of changes in the third derivatives of an image contour.

IV An Example

The interpretation strategy has been implemented and ap­ plied to a synthetic image of a helical space curve. The helix example i~ a good t.est because a helix has significant t.orsion everywhere, thus, distinguished segmentation points do not exist and it is not. clear what the estimation strategy will do. If A we can recover the ht>lical shape of the space curve with some accuracy, we shall have demonstrated that the estimation strategy can perform even when no good segmentation is available.

Figure 2 (a) shows a perspective image of a helix. Figure 2 (b) shows a plot of the spherical indicatrix of the helix. The spherical indicatrix is a plot of the orientation of the osculat­ ing plane of the space curve. The axes in this plot correspond., to the azimuth and elevation of the osculating plane. ~ men­ tioned previously, knowledge of the orientation (azimuth and elevation) of the osculating plane at each point, t.ogether with the imaged contour, uniquely determines the shape of the space curve. Thus, t.he spherical indicatrix is a method of displaying the three-dimen~ioual shape of the space curve. Figure 2 (c) shows the spherical indicatrix estimated for the cont.our in (a). When this is compared with the actual indicatrix shown in (b), it is evident that. the three-dimensional shape of the space curve has been fairly accurately recovered.

Summary. We have developed a theory for assigning a three-dimensional interpretation t.o any smooth image contour. The theory has been implemented and is undergoing evaluation, which may lead to further development. The results report.ed above indicate that the c~timation strategy performs reasonably well even for cases such as a helix, where the presence of substan­ tial torsion might have led one to expect poor performance.