The space carving approach to model acquisition is more appropriate for these applications than competing methods due to the generality of the scenes which may be reconstructed. Some of the competing methods limit the class of input images to those containing large numbers of particular features, or limit the class of scene shapes which may be reconstructed to those exhibiting particular properties. Space carving thus provides a means of generating three-dimensional models of scenes for a number of important applications, without the limitations of competing methods.

Current space carving algorithms rely on dividing the scene into rectangular regions labelled voxels. At each pass the set of voxels on the surface of the proposed reconstruction must be determined and each of these voxels tested in order to calculate which cameras it would be visible to. Each surface voxel is then tested to determine whether it is consistent with the input images of the cameras to which it would be visible. Traversing the data-structure requires significant execution time, largely due to the manner in which the scene space is divided and the symbolic representation of this division. The voxel-based representation used in the state-of-the-art space-carving algorithm also suffers from the variation in resolution caused by the perspective projection of scene space into the images . Significantly more voxels are required to represent the space further away from a particular camera. Similarly, the resolution of voxel space is compromised for parts of the scene closest to the camera because a single voxel will map to multiple pixels. The proposed algorithm uses an image-based representation of scene space to avoid these limitations. Information representing the structure of the scene is attached to pixels in the image space. Consequently, the recoverable model resolution is coupled to that of the input images, thus achieving the most detailed reconstruction possible given the inputs. One of the advantages of this approach is that certain calculations involving this image-based representation may be carried out using operations implemented by commonly available graphics rendering hardware, thus achieving significant improvements in speed of execution.

Photo-consistency

The goal of space-carving based approaches to scene reconstruction is to recover scene shape from several images taken by calibrated cameras in the case where no assumptions are made about the scene or the relative orientation of the cameras . The methods do not require correspondence information but instead rely on testing the photo-consistency of scene points to generate a reconstruction. Space carving thus generates reconstructions which would reproduce the input images when re-projected into the original cameras. Such reconstructions are said to be photo-consistent with the input images.

The visibility problem

In order to be able to test photo-consistency we first need to be able to identify which parts of a proposed reconstruction would be visible in which cameras, and the point in the image at which they would appear. This has been labelled the visibility problem. A number of methods have been proposed to solve the visibility problem for space carving. The fundamental problem is that of discerning which elements of the model are occluded by other points in the scene in the view of a particular camera. This typically requires a search over the un-carved voxels, the order of which is quadratic in the number of scene elements. A number of alternative scene representations have been considered, but these representations generally shift the complexity to another area of the algorithm, or compromise the quality of the reconstruction. The same visibility challenge exists, however, when rendering an image of a three-dimensional scene. This is well understood within the field of computer graphics . We propose to utilise the corresponding hardware-based solutions to this problem.