Three-Dimensional Data Acquisition - Computer Vision for Visual Effects - page 322

Figure 8.24. A top view of one plane of voxels and three cameras with associated image planes.
Gray voxels are occupied, and white voxels are empty. A voxel is photo-consistent if its color
closely matches the color of all the pixels in the images in which it is visible. In this example, the
color of the striped voxel only needs to agree with the colors of the pixels in the left and middle
cameras, since it is occluded from the perspective of the right camera.

Kutulakos and Seitz [ 258 ] later proposed the seminal space carving approach,
which formalized the concept of the photo hull , the largest set of colored voxels
that is photo-consistent with the input images. The space carving algorithmprovably
achieves the photo hull by iteratively removing voxels from an initial volume (e.g.,
the visual hull), either one by one or along a set of orthogonal sweeping planes. While
there are no restrictions on the camera configuration, many sweep iterations may be
required to reach the photo hull.
Kolmogorov and Zabih [ 247 ] proposed an algorithm that can handle the same
camera configurations as voxel coloring, but has the advantages that spatial coher-
ence between the source image pixels is enforced, and that irreversible incremental
decisions about voxel removal are avoided. They posed the problem as a labeling
problem over the pixels in all the source images, where the label corresponded to
a discretized depth from a reference camera. The problem of finding an optimal
labeling is posed as a graph-cut problem in which the data term is related to voxel
photo-consistency and the smoothness term encourages neighboring pixels to have
similar depths. An additional visibility term is required to encode the notion that
voxels are opaque. The multi-label graph-cut problem is solved using

-expansion.
Vogiatzis et al. [ 522 ] investigated a different graph-cut approach for more realistic
multi-view stereo problems. Instead of using multiple labels, they posed a two-label
problem inwhich each voxel was classified as part of the object or not . 17 The smooth-
ness term in the problem is related to the photo-consistency of neighboring voxels,
while the data term encourages the volume to expand (to avoid incomplete recon-
structions). Voxels outside the visual hull can be automatically ruled out if image
silhouettes are available. Once the voxels are selectedwith either graph-cut approach,

α

17 In a sense, this is a 3D generalization of the matting problem.