Three-dimensional reconstruction method utilizing reprojective optimization

#The present invention relates to image processing, and more particularly, to a method for reconstructing 3-D scenes.

#Consider a three-dimensional scene consisting of a number of objects in some localized region of space. Software that models the objects from a set of calibrated photographs of the scene is known to the art. The models are typically used to generate a view of the scene, as that scene would appear to a camera placed at a new location.

#A typical prior art system is taught in W. B. Culbertson, T. Malzbender, and G. Slabaugh, “Generalized Voxel Coloring,” Vision Algorithms Theory and Practice (ICCV 1999 Workshop), Springer-Verlag Lecture Notes in Computer Science Vol. 1883, pp. 100-115, which is hereby incorporated by reference. These systems typically reconstruct a scene by defining a “reconstruction volume” containing the objects. This volume is then divided into volume elements referred to as “voxels”, which are the three-dimensional analog of pixels in two-dimensional image processing. If a voxel can be seen in a number of photographs, it is tested to determine if the voxel has the same color in each of the photographs in question. If the voxel has a consistent color, it is assigned that color. If the voxel color is inconsistent between the various views, the voxel is assumed to be clear, i.e., the voxel is not part of any of the objects.

#FIGS. 1-2 are top views of an object 20 that is viewed by a number of cameras.

#FIG. 3 illustrates the manner in which the linked lists are generated for each camera.

#FIGS. 4 and 5 illustrate the manner in which a reconstruction is tested to determine if a new voxel should be added to the reconstruction.

#To simplify the following discussion, the present invention will be explained in terms of two-dimensional drawings whenever possible. Also, the figures show a single object, whereas real scenes will typically consist of many objects. However, it will be apparent that the method discussed may be generalized to three-dimensions. The manner in which the present invention obtains its advantages may be more easily understood with reference to FIGS. 1-2, which are top views of an object 20 that is viewed by a number of cameras shown at 11-18. The space in which object 20 is located is divided into a plurality of voxels. The goal of the voxel coloring algorithm is to create a 3D model of the scene, using only the information contained in the camera images. It does this by assigning a color to all voxels on the surface of the object and marking those outside the object as being clear. It is assumed that the surface voxels are opaque, and hence, any voxels completely within an object (not on the object's surface) are not visible in any view of an object.

#Refer now to FIG. 1. Consider voxel 21, which includes part of the surface of object 20. Cameras 16-18 can see this voxel. The remaining cameras cannot see the voxel because the object blocks the view of that voxel. It is assumed that the position, orientation, and lens characteristics of each of the cameras is known. An image taken with such a camera will be referred to as a calibrated image in the following discussion. Hence, the position on the film or electronic imager of each of the cameras at which light leaving voxel 21 is recorded can be determined, assuming that light is not occluded from the cameras by other voxels. For example, if the image is composed of pixels, then the pixels that view the voxel can be determined using scan conversion, a well-known technique in computer graphics. The color of that light is ascertained from each of the images.

#In prior art voxel carving algorithms, the consistency of the color seen at pixels that view the same voxel is used to determine whether the voxel is clear or opaque without reference to the effect such a decision has on the overall model of the scene. These modes assume that the light leaving voxel 21 and arriving at each of the cameras comes from the small region of the surface of object 20 that is within the voxel, each camera will record the same color light, and the views are defined to be consistent with the object having that color at that location. If the views are consistent, these models define the voxel to be opaque and assign it a color consistent with that seen by the various cameras.