The 3D MOSAIC Scene Understanding System

1. Introduction

We are currently working with aerial photographs of Washington, D.C. (Fig. 1). Our approach of incrementally acquiring the model arises from three observations: First, single images contain only partial information about a scer;~e. Second, errors and inconsistencies often result when interpreting complex images. Third, features of visible surfaces (such as scene edges and texture) are often more apparent (and thus easier to extract) in one image than another because of differences ir. viewpoint and lighting conditions.

In our approach, information derived from a sequence of images obtained from multiple viewpoints is incrementally accumulated to construct the model. A partial 3D description of the scene is derived from each view. The initial model, constructed from the 3D information obtained from the first view, represents an initial approximation of the scene. As each successive view is processed, 2. Stereo Analysis accurate and complete.

from a new view must be matched to the model so that updating approximations of the buildings. (For a different approach, see [5).) can occur, (2) higher-level components should be ab!e to use the model to determine the parts of the scene to be analyzed in more Second, because of our wide-angle stereo images, there are detail. large disparity jumps and large portions of the scene are visible in one image but not the other. Because most stereo systems do not distinguish these from other regions of the image, they try to find matches for them and therefore have trouble [1, 2, 4, 8]. In our approach, rather than attempting to find matches for scene faces occluded in one of the images, we match face boundaries visible in both images. We do this by explicitly taking into account the way junction appearances change from one image to the other, using the knowledge that in urban scenes, roofs of buildings tend to be parallel to the ground plane, while walls tend to be perpendicular to this plane. Edges in the scene perpendicular to the ground will appear in each image to be directed towards the vertical vanishing point. If an edge lies on a roof, its orientation in the other image as a function of position along the epipolar line can be predicted if the normal to the ground plane is known.

Therefore, when a (say) FORK junction is found in one image, the leg of the junction directed towards the vertical vanishing point is initially assumed to arise from a scene edge perpendicular to the ground, while the other two legs are initially assumed to arise from scene edges lying on a roof or on the ground. Its appearance in the other image can therefore be predicted.

Structural relationships between scene vertices are also used to aid in the matching, using the knowledge that if two junctions in an image arise from scene vertices at the same height above the ground, the positions of the corresponding junctions in the other image, as a function of position along the epipolar line, can be predicted. We make the assumption that junctions close to one another in the image_ often correspond to vertices lying on top of' the same building and therefore have approximately the same height. In this way, the configurations within the neighborhoods around junctions in the two images are used in the matching.

A final reason for using junctions to perform the stereo matching is that feature-based matching results in more accurate 3D positions for occlusion boundaries than gray scale area matching.

the same face corners. Finally, 30 coordinates are derived using triangulation. Fig. 2 shows a perspective view of the 30 vertices and edges, called a wire-frame description of the scene, that result after processing the stereo pair in Fig. 1.

3. The 30 Scene Model

The following factors have determined how the scene model is represented and manipulated.

1. Partially complete, planar-faced objects must be efficiently described by the model. It is therefore represented as a graph in terms of symbolic primitives such as faces, edges, vertices, and their topology and geometry. Information is added and deleted by means of these primitives.
2. The model must be easy to use in matching. This is facilitated by representing it compactly in lerms of symbolic primitives rather than, say, surface points.
3. Because scene approximations are often more useful if they contain reasonable hypotheses for parts of the scene for which there is little data, we introduce mechanisms that permit hypotheses to be generated, added, and deleted. These mechanisms are aided by the compact, symbolic model representation. Primitive elements in the model are tagged as confirmed if they are derived directly fwm images, or unconfirmed if they are hypothesized.
4. Because incremental modifications to the model must be easy to perform, we introduce mechanisms to (a) add primitives to the Model in a manner such that constraints on geometry imp~sed by these additions are propagated throughout the model, and (b) modify and delete primitives if discrepancies arise between newly derived and current information.

4. Constructing and Updating the 30 Scene Model

4.1 . Single View

Our stereo analysis involves first extracting linear segments from This section describes the construction of an initial scene model from 30 wire-frame data (Fig. 2) extracted from a single (stereo each image [9), and then forming junctions from the segments. Next, potential matches for each junction are searched by pair) view (Fig. 1). The processing proceeds as follows. predicting its appearance in the other image. To arrive at a single First, if two wire-frame edges are nearly parallel and very close match for each junction, the space of potential matches is searched (e.g., E1 and E2 in Fig. 2), they are merged into a single edge. Next, with a beam searc;h [10] using two main heuristics: First, relative since each vertex is assumed to correspond to a corner of an junction positions in the two images should agree with predicted object', each adjacent pair of legs ordered around the vertex is positions (as described above). Second, image intensities inside assumed to correspond to the corner of a planar face. Partial faces,

matching junctions should be similar since the junctions arise from called web faces, are generated for such pairs (Fig. 3a).

After all web faces have been created , those that represent the corners of a single face are merged. Web faces to be merged may be either touching (e.g., Fig. 3b and F1 and F2 in Fig. 2) or non­ touching (e.g., Fig. 3c and·F3 and F4 in Fig. 2) . After all mergers, many faces may still be incomplete because they may not have closed boundaries. These are completed by first hypothesizing their shapes, either as parallelograms (for faces consisting of single corners as in Fig. 3d) or as other closed polygons (Fig. 3e), and then generating appropriate edges and vertices. After all faces have been completed, those that seem to be holes in other faces are converted to holes (Fig. 3f).

At this point, many objects may be incomplete because they may not be closed. Since we are dealing with urban scenes, faces that lie high enough above the ground are assumed to represent roofs of buildings. A hypothesized vertical wall is dropped towards the ground from each edge of such faces, unless the edge is already part of another face (Fig. 3g) . Each wall is dropped either to the ground or to the first face it intersects on the way down. The resulting scene model is displayed in Fig. 4. In order to render more realistic displays, gray scale obtained from one of the original images (Fig.1) is added to them (Fig. 5).

Note that this model is a higher level description than a depth map, but is obtained without first generating a depth map. The depth map, which is the result of many stereo analysis systems [1 , 4, 8], is like an image in that it is an array of numbers that requires description. Our 30 Mosaic model, on the other hand, is symbolic and compact, making it more useful for matching, incremental updating, and other tasks.

4.2. Multiple Views

This section describes the process by which wire-frame information derived from a second view (Fig. 6) is incorporated into the scene model of Fig. 4. This new set of wire frames was manually generated to simulate the information available from a point of view opposite to that of Fig. 1 (i.e., viewing the scene from the "back"). The primary difference between the procedure used here and the one described in the previous section is that the wire-frame data is matched with and merged into the current model. The matching step provides the coordinate transformation from the data to the model and corresponding confirmed edges and vertices in the two. We assume in this experiment that the coordinate transformation is known; the data and model may therefore be described in the same coordinate system. To determine corresponding edges and vertices, we check absolute distances and whether corresponding elements are connected in the same configuration in both the model and data.

Two objects match if they have confirmed elements that match, and are merged by (1) merging their corresponding pairs of vertices and edges into single elements by "weighted averaging" of their positions, and (2) deleting hypothesized elements in the model that are inconsistent with newly obtained or changed elements. To determine whether inconsistencies exist, dependencies are recorded for each hypothesis at the time of its creation. A hypothesis is dependent en all elements whose existence directly resulted in the creation of the hypothesis. If one of these elements is modified or deleted, the hypothesis must also be deleted since the conditions under which it was created are no longer valid. After ali mergings and deletions, the remaining edges and vertices in the wire-frame object are added to the model object.

At this point, many objects are incomplete because new wire­ frame data has been added and many hypothesized elements have been deleted. These objects are completed using the techniques described in the previous section. Fig. 7 shows the resulting updated scene model which, for easier comparison by the reader, is displayed for the same viewpoint as the initial model in Fig. 4.

Note that the updated model contains more buildings since new wire-frame data, some of which represent new buildings, have been incorporated into the initial model. Also note that for many buildings described in both versions of the model, the positions of vertices and edges are more accurate in the updated version. This is because many hypothesized vertices and edges are replaced by accurate ones obtained from the new data, and many confirmed vertices and edges are merged with correspon,ding ones in the data by "averaging" their positions, generally decreasing the amount of error. This experiment demonstrates how information provided by each additional view allows the moqel to be incrementally made more complete and accurate.

5. Summary

The 30 Mosaic system incrementally derives a 3D model of a complex urban scene from multiple images. The model plays the role of a central description which incrementally accumulates scene information and can be used, at any point along its development, for performing various tasks dealing with the scene environment.

We have demonstrated that task-specific knowledge is very 4. Grimson, W.E.L. "A Computer Implementation of a Theory of useful for interpreting complex images. Such knowledge is used Human Stereo Vision." Phil. Trans. Roy. Soc. Lon d. 8292 (1980), both for the stereo analysis and for reconstructing shapes from the 217 · 2 53. stereo output. The task-specific knowledge deals with block· "Automatl·c 5. Henderson, R. L. , Miller, W. J., and Grosch, C. B. shaped objects in an urban scene. Surfaces are assumed to be Stereo Reconstruction of Man-made Targets." Pro c. SPIE 186 planar, oriented either vertically or horizontally in the scene, and (August 1979) . shaped as parallelograms if there is no evidence to the contrary. 6. Herman, M., Kanade, T., and Kuroe, S. "Incremental Acquisition Also, the position of the ground plane is assumed to be known. of a Three-Dimensional Scene Model from Images." Proc. ARPA Heuristics for generating 3D objects from the stereo output have image Understanding Workshop (September 1982). been developed from these assumptions.