One-Eyed Stereo: A General Approach to Modeling 3-D Scene Geometry

1 Introduction

The recovery of 3-D scene geometry from one or more images, which we will call the scene modeling problern (SMP), has so­ lutions that appear to follow one of three distinct paradigms: stereo; optic flow; and shape from shading, texture, and contour.

In the stereo paradigm, we match corresponding world/scene points in two images, and, given the relative geometry of the two cameras (eyes) that acquired the images, we can use simple trigonometry to determine the depths of the matched points [1].

In the optic flow paradigm, we use two or more images to compute the image velocity of depicted scene points. If the cam· era's motion and imaging parameters are known, we can again use simple trigonometry to convert velocity measurements in the image to depths in the scene [20].

In the shape from shading, texture, and contour (SSTC) paradigm, we must either know, or make some assumption· about the nature of the scene, the illumination, and the imaging ge· ometry. Reference [2] contains an excellent collection of papen, many of which address the problern of how to recover depth from the shading, texture, and contour information visible in a &(ngle image. Two distinct computational approaches have been em· ployed in the SSTC paradigm: (a) integration of partial differ-

The work reported herein was supported by the Defense Advanced Re· search Projects Agency under Contract No. MDA903-83-C-0027.

into regions that can be described by a single underlying model. The computation can then be carried out independently in each region, and the results knitted together.

2.2 Select a model

For each region identified by the partitioning process, we must determine the underlying model that explains that portion oC the image. Surface reflectance functions and texture pattema are ex· amples of such models. Partitioning the image and aelecting the appropriate models are difficult problems that are not addreaaed in this paper. Witkin and Kass [22] are exploring a new elua oC techniques that promises to provide answera to theae queationa. lt will not be possible to recover depth where no aingle model can be associated with a particular image region. Similarly, in· accurate or incorrect results can be expected if the partitioning or modeling is performed incorrectly.

2.3 Generate the vlrtual Image

The key to one-eyed stereo is using the model to fabricate a sec· ond (virtual) image of the scene. The idea is that the model often allows one to construct an image of the ecene that ia inde· pendent of the actual shape of the imaged aurface. Thia allowa the virtual image to be determined aolely Crom knowledge of the model without making use of the original image. For example, the markings on the surface oC Figure 1 could have ariaen from a projection of a uniform grid upon the aurface (Figure 2). For all images that fit this model, we can use a uniform grid aa the virtual image. The orientation, position, and scale oC this grid will typically be unknown, and we will show how this information can be recovered from the original image. Other modela give riae to other forms oC virtual images.

2.4 Determlne correapondencea

In order to apply stereo techniques to determine depths, we must first establish correspondences between points in the real image and the virtual image. When dealing with textures, the process is typified by counting texels in each image from a chosen start­ ing point . With shading, the generat approach is to integrate intensities. Several variations are described in the next section, and the difficulty of the procedure will depend on the nature of the model.

2.5 Compute depths using stereo

With two images and a nurober of point-to-point correspondences in band, the techniquea of binocular stereo are immediately ap­ plicable. At this point, the problern has been reduced to comput­ ing the relative camera models between the two images and using that information to compute depths by triangulation. The fact that the virtual image will normally be an orthographic projec­ tion required reformulation o( existing algorithms for performing thia computation. The appendix describes a new algorithm that computes the relative camera model and reconstructs the 3-D scene Crom eight point-correapondences between a perspective and an orthographic image.

The problern oC recovering scene and imaging geometry from· two or more imagea haa been addressed by workera in both binocular stereo and monocular perception of motion (where the two projections are aeparated in time as weil as space) . Vari­ oua approaches have been used to derive equations for the 3-D coordinates and motion parametera; these equations are gener­ ally solved by iterative techniques [4] [7] [12] [13] . Ullman [20] presents a solution Cor recovering 3-D shape Crom three ortho­ graphic projections with established correspondences among at least Cour points. His "polar equation· allows computation of ahape when the motion oC the acene is restricted to a rotation about the vertical axis and arbitrary translation. Nageland Neu­ mann [9] provide a compact system of three nonlinear equations for the unreatricted problern when five point-correspondences be­ tween the two perapective images are known. More recently, Huang [19] and Longuet-Higgins [8] have independently derived methods that only require the solution of a set of eight simul­ taneaus linear equations when eight point-correspondences are known between two perspective images. In our formulation we are Caced with a stereo problern involving a perspective and an orthographic image, and while the aforementioned references are related, none provides a aolution to thia particular problem.

The derivation described in the appendix was inspired by the Cormulation oC Longuet-Higgins Cor perapective images. When ei­ ther image nears orthography, Longuet-Higgins' method becomes unstable and is undellned if either image is truly orthographic . Moreover, his approach requires knowledge of t.he focal lengt.h and principal point in each image. Our method was specifically derived for one orthographic and one perspective image whosc internal imaging parameters may not be fully known.

S Varlatlons on tbe Theme

In this section we illustrate how our approach is used with several models of texture, shading, and contour. Where these models

(b) The virtual image

don't mateh given seene eharaeteristies, they may require ad· ditional modifieation. However, a qualitatively eorreet answer might still be obtainable by applying one of the speeifie models we diseuss in the following subseetions to what appears to be an inappropriate situation, or a situation where the validity of the assumptions eannot be established.

3.1 Shape from texture

Surface shapes are often eommunieated graphieally to humans by drawings like Figure 1. These drawings ean also be interpreted by one-eyed stereo. In this ease, there is no need to partition the image; the underlying model of the entire aeene is that the interseetions of the lines are distributed in the form of a aquare grid. When viewed from direetly above at an infinite distanee, the surfaee would appear as shown in the virtual image of Figure 2 regardless of the shape of the surfaee. This virtual image ean be eonstrued as an orthographie projeetion of the objeet aurfaee from an unknown viewing direction. Correspondeneea between the original and virtual images are easily established if there are no oeclusions in the original image. Seleet any interseetion in the original image to be the reference point and pair it with any in· terseetion in the virtual image. A aecond correaponding pair can be found by moving to an adjaeent intersection in botb imagea. Additional pairs are found in the eame manner, being eareful to eorrelate the motions in eaeh image eonsistently in both di· reetions. When oeclusions are preaent, it may atill be poasible to obtain eorrespondenees for all visible junction· by following a non-oecluded path around the occlusion. Ir no such path ean be found, the shape of each isolated region can still be computed, but there will be no way to relate the distaneea without further information. Other techniquea uaed to graphically repreaent im· ages of 3-D shapea may require other virtual imagea. Figure 3a, for example, would imply a virtual image u shown in Figure Sb. Methods for reeognizing which model to apply are needed, but are not diseussed here.

Onee eorrespondences have been determined, we can uae the algorithm given in the appendix to reeover depth. We bave presumably one perspective image and one orthographic image whose seale and origin are still unknown. The deptha that will be recovered will be scaled aecording to tbe scale choaen for the :irtu~l image 1 . T~e ehoiee. of orlgln (or the orthographlc Image 1s arbttrary, and wlll result m the same solution regardle11 of tht point ehosen as the origin. The appendix shows how to eompute the orientation of the Orthographie eoordinate system relative to the perspeetive imaging system as weil as the displacement between the two, given the ehoiee of origin for the orthographic view. 3-D eoordinates of eaeh matehed point are then easily eom­ puted using baek·projection. A unique solution will be obtained whenever the piereing point of the perspeetive image is known. A minimum of eight pairs of matehed points are required to obtain a solution; depths ean be eomputed for all matehed points.

1 Reca.ll tha.t the original ima.ge does not conta.in the informa.tion neceesa.ry to recover the absolute oize of the scene.

There exists a growing Iiterature on methods to reeover shape from natural textures [6][11][17][21]. We will now show how the constraints imposed by one particular type of natural texture can be exploited to obtain similar results by using one-eyed stereo.

Consider the pattem of streets in Figure 4. If this eity were viewed from an airplane directly overhead at high al titude, the streets would form a regular grid not unlike the one used as the virtual image in Figure 2. There are many other seene attributes that aatiafy this same model. The houses in some eities would appear to be distributed in a uniform grid if viewed from direet ly overhead. In an apple orehard growing on a hillside, the trees would be planted in rows that are evenly spaeed when measured horizontally.

lgnoring the nontrivial tasks of partitioning these images into iso·textural regions, verifying that tbey satisfy the model, and identifying individual texels, it ean be seen how these images can be interpreted using the same teehniques as in the previous aeetion. The virtual image in each ease will be a reetangular grid, and ean be considered u an orthographie view from an unlmown orientation. Correspondences ean be determined by eounting street interseetiona, roo(tops, or apple trees. As before, one can solve for the relative camera model and eompute depths o( matehed points. Obviously, for the situations diseussed here we must be aatisfled with a qualitatively-correet interpretatio~ due to the diffieulty of loeating individual texels reliably and aecurately, u weil u the numerieal instabilities arising from the underlying nonlinear transformation.

a.2 Shape from shadlns

For nur PlU'Pillea, aurCaee ahadinr can be eonsidered the limit­ ing ease of a loeally uniform texture distribution, as the texels approaeh infinitesimal dimensions (as seen near the horizon in Figure 1). To eompute eorrespondenees, we need to appropri­ ately integrate image intensities in place of counting lines, since the image intensities can be seen to be related to the density of lines projected on the surface. The feasibility of this procedure depends on the reflectance function of the surface.

What types of material possess the special property that allows their images to be treated like the Iimit of the projected texture of the previous section? lt must be the case that the integral of intensity in an image region is proportional to the number of texels that would be projected in that region. This can be described in terms of i and e, where i is the angle between the local surface normal and the light source, and e is the angle be· tween the surfac:e normal and the viewpoint . lt can be 1een that the number of texels projec:ted onto a surfac:e patch will be pro· portianal to cos i , the c:osine of the incident angle. At the same time , the surface patc:h ( as seen from the viewpoint) will be fore· shortened by c:os e, the c:osine o( the emittance angle. Thus, the integral of reflec:ted light intensity over a region will be propor· tional to the flux of the light striking the surface if the intensity of the reflected light at any point is proportional to cos i/ cose. Horn [5] has pointed out that the material in the maria of the moon, and other roc:ky, dusty objectl when viewed from great distances , possess a reflectanc:e function that allows recovery o( the rat io cos i / c:os e from the imaged intensities. This surface property has allowed unusually simple algorithms for computing shape-from-shading, so it is not surprising that it easily submits to one·eyed stereo as weil.

Ta interpret this type of shading, we can construct a virtual image whose direction of view is the lighting direction (i.e., taken from a "virtual c:amera" located at the light source). When the original shaded image is orthographic, we consider a family of parallel lines that lie in planes that include both the light source and the (distant) view point . When viewed from the light source, the image of the surface corresponding to these lines will also be a set of parallel lines regardless of the shape of the surface. These parallel lines constitute the virtual image. We will use the image intensities to refine these line·to-line correspondences to point· to-point correspondences. Figure 5 shows the geometry for an individual line in the family. A little trigonometry shows that

where As is a distance along the line in the real image and A·' is the corresponding distance along the corresponding line ln the virtual image. lntegrating this equation produces the following expression, which defines the point correspondences in the two images along the given line.

To use this equation we must first compute ~ from the intensity . cose value at each pomt along the line. This will, of course, be possible only when the reßeetanee funetion is constant for c:onstant cosi . With these point-to-point eorrespondenees in hand, it is a si;;ie matter of triangulation to find the 3-D coordinates of the surface points, given that we know the direetion to the light sourc:e. We can explore the remainder of the surface by repeating the proc:ess for eaeh of the suecessive parallel lines in the image. lt still remains to tie eaeh of the adjacent proflies together, as the scale factor o( each profile haa not been determined. Knowledge of the actual depth of one point along each profile provides the necessary additional information. lt is important to note that our assumptions and initial conditions are those used by Horn; the fact that he was able to obtain a solution under these c:onditions aa·ured the existenc:e of a suitable virtual image for the one-eyed stereo paradigm.

3.3 Shape from contour

lt is sometimes possible to extract a line drawing, such as shown in Figure 6, from scene textures. Parallel streets like those en­ countered in Figure 4 give rise to a virtual image consisting of parallel lines when the cross streets cannot be located; terraced hilla also produce a virtual image of parallel lines. Correspon­ denceB between real and virtual image lines can be found by counting adjacent lines from an arbitrary starting point. This matches a virtual image line with each point in the real image. Point-to·line correspondences are not sufficient to employ the stereo computation of the appendix to reconstmct the surfact'. Knowledge of the relative orientation bet.ween the two images (equivalent to knowing the orientation of the camera of the real image relative to the parallel lines in the scene) provides the necessary additional constraint; the surface can then be recon­ structed uniquely through back·projection. Without knowledge of the relative orientation of the virtual image, heuristics must be employed that relate points on adjacent contours so that a regular grid can be used as the virtual image. The human visual system is normally able to interpret images like Figure 6 although just what assumptions are being made remains unclear. Furth .. r study into this phenomenon may Iead to the extraction of mocleJ, suitable to the employment of one-eyed stereo on this type of im­ age without requiring prior knowledge of the virtual orientation.

3.4 Distorted Texturea and Unfrlendly Shadlng

We have already noted that image shading can be viewed as a limi ting (and, for our purposes, a degenerate) result of closely­ spaced texture elements. In order to recover depth from shading, we must use integration to replace counting the texture elements that define the locations o( the "grid lines" o( our virtual im· age. The integration process depends on having a "friendly" reflectance function and an imaging geometry that allows us to convert distance along a line in the actual image to a correspond· ing distance along a line in the virtual image.

The recovery of lunar topography from a single shaded image [5], as discussed in Section 3.2, is one of the (ew instancea in which "shape from shading· is known to be possible without a aignifl­ cant amount o! additional knowledge about the acene; and even here we are required to know the actual retlectance function, the location of the (point) source of illumination, the deptha along a curve on the object surface, and be dealing with a portion of the object having constant albedo. Further, the rellectance function had to have just the property that we require to replace direct counting, i.e., the reflectance function had to compensate exactly for the "foreshortening" o( distance due to viewing pointa on the object surface at an unknown tangent-plane orientation angle. Most of the commonly encountered reftectance functiona, such as Lambertian reftectance, do not have this friendly property, and it is not clear to what extent it ia possible to reeover depth from shading in such cases ( e.g., see Pentland [11] and Smith [14]) . Additional assumptions will probably be needed and the qualitative nature of the recovery will be more pronounced. Juat as in the case where a complex function can be evaluated by making a local linear approximation and iterating the reaulting solution, it may be pouible to deal with unfriendly, or even un· known, refl~ctance functions by assuming that they are friendly about some point, directly solving for local ahape uaing the al· gorithm applicable to the friendly eue, and then extending the solution to adjacent regiona. We are eurrently inveatigating thia approach.

The uniform reetangular grid and the polar grid that we used as virtual images to illustrate our approach to one-eyed atereo are effective in a !arge nurober o( casea, becauae there are proceaaea operating in the real world that produce corresponding texturea ( i.e., grid-like textures that appear to be orthographieally pro· jected onto the surfaces of the scene). However, there are also textures that produce similar·appearing images, but are due to different underlying processes. For example, a uniform grid-like texture might have been created on a ftat piece of terrain, which then underwent geologic deformation- in this case the virtuel image needed to recover depth (or the recovery algorithm) mt"t be different from the projective case. We have already indicated the problern o( choosing the appropriate model for the virtual image, and as noted above, image appearance is probably not suflicient to make this determination- some semantic knowledgP about the scene is undoubtedly required. Figure 7 shows an ex­ ample in which two completely different interpretations of scenc structure result, both believable, depending on whether we usP the reetangular grid model, or the polar grid model.

4 Experimental Results

The stereo reconstruction algorithm described in the appendix hu been programmed and successfully tested on both real and synthetic imagery. Given a sparse set of image points and thei r correspondence in a virtual image, a qualitative description of the imaged sur!ace can be obtained.

Synthetic images were created Crom surfaces painted wi th computer-generated graphic textures. Figure 1 shows a synthetic image constructed !rom a piece o( a digital terrain model (DTM) . The intersections of every 20th grid line constitute the set of 36 image points made available to the one-eyed stereo algori thm. Their eorrespondences were determined by selecting an arbi trary origin and counting grid lines to obtain virtual image coordinates. Proceuing these pairs by the algorithm in the appendix yields a aet of 3-D coordinates in either the viewer-centered coordinate apace, or the virtual image coordinate space (which, if correct , is aligned with the original DTM) . Figure 8 was obtained from the 3-D coordinates in the virtual image space by fi tting a surface to these points using Smith's surface interpolation algorithm [1 5]. Thia givea a dense set o! 3-D coordinates that can then be dis­ played from any viewpoint. The viewpoint that was computed by one-eyed stereo wu used to render the surface as shown in Figure 8. Ita aimilarity to the original rendering of the surface (Fig. 1) illustrates the successful reconstruction of the scene.

The aame procedure was !ollowed when working with real pho­ tographa. Uaing the photo of San Franc:isc:o in Figure 4, the intersections or 31 atreet intersections were extracted manually. Those that were occluded or indistinct were disregarded. Virtual image coordinates were obtained by counting city blocks from the lower-left intersectlon. The one·eyed stereo algorithm was then used to acquire 3-D coordinates of the corresponding image points in both viewer-centered and grid-centered coordinate sys­ tems. A continuous surface was fitted to both representations of these points. The location and orientation of the camera relative to the grid were also computed. Figure 9 shows the reconstructed surface from the derived location of the viewpoint of the original phot.o. The numbers superimposed are the computed locations of the original 31 points. While several of the original points were badly mislocated, the general shape of the landform is apparent .

There are several reasons why the algorithm can only provide a qualitative shape description. First, the problern itself can be somewhat sensitivetoslight perturbations in the estimatea ofthe piercing point or focal length. This appears to be inherent to the problern of recovering shape from a single image. How humans can determine shape monocularly without apparent knowledge of t he piercing point or semantic content of the scene remains unresolved. The second factor precluding precise, quantitative desc ription of shape is the practical difficulty of acquiring !arge numbers of corresponding points. While the algorithm can pro· ceed with as few as eight points, the location of the object will only be identified at those eight points. lf a more complete model is sought, then additional points will be required to constrain the subsequent surface interpolation.

The task remains to evaluate the effectiveness of the iterative technique, described in Section 3.4, for recovering (a) shape from shading in the case of scenes possessing "unfriendly" rellectance functions, and (b) shape from nonprojective and distorted tex· tures. Our experience with the process indicates that the key to these problems lies in the ability to establish valid correspon· dences with the virtual image. Once these are available, reeon· struction of the surface ean proeeed u outlined.

5 Conclusion

ln this paper we have shown that, in principle, it is possible to employ the stereo paradigm in place of various approaches proposed for modeling 3-D scene geometry-including the cue in which only one image is provided. Wehave further ahown that, for the case of a single image, the approach could be implemented by:

• ( 1) Setting up correspondeneea between portiona ol the image and variations of a uniform grid;
• Treating each image portion and its grid counterpart u a stereo pair, and employing a stereo tec:hnique to rec:over depth. (We present a new algorithm necessary to accomplish thia 1t11p.)

Automatie procedures to partition the image, select the ap· propriate form of the virtual image, and establish the correspon· denccs, are all difficult problems which were not addressed in this paper. Nevertheless, we have unified a number of appar·

ently distinct probtems, which, individually, would still have to contend with these same pervasive problems (i.e., partitioning, model selection, and matching). ·