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

they can be colored (e.g., using the average color of the corresponding pixels in the
images in which they are visible).
An interesting feature of volumetric approaches is that neither sparse nor dense
correspondences between the images are typically required, unlike some of the other
algorithms in this section. However, the general problemwith volumetric approaches
is that their accuracy is limited by the size of the voxel grid. Even at tabletop scale, the
grid needs to be hundreds of voxels on a side to achieve sub-millimeter accuracy, and
the resulting space carving or graph-cut methods are computationally demanding,
both in terms of speed and requiredmemory. Also, as with voxel carving, a reasonably
large number (tens to hundreds) of calibrated images may be required to get an
acceptable result.

8.3.2 Surface Deformation Methods

The next class of methods is based on evolving a 3D surface towrap tightly around the
region in 3D containing an object, which can be viewed as a generalization of active
contours or “snakes” for image segmentation [ 230 ]. The surface can be represented
either explicitly as a triangle mesh , or implicitly as the zero-level set of a 3D func-
tional. The triangle mesh approach is appealing in that the vertex coordinates don't
need to be discretized, and the mesh representation is immediately useful for sub-
sequent tasks. On the other hand, maintaining the correct topology of the mesh can
be difficult, especially for scenes containing multiple objects or objects containing
holes. The level-set approach gracefully handles the changing topology of the under-
lying surface, but has similar problems with resolution and memory requirements as
volumetric methods since a voxel grid is required.
The algorithm by Hernández and Schmitt [ 131 ] is a good representative of
triangle-mesh-deformation methods. First, the visual hull is estimated and fit with
a triangulated mesh 18 , which serves as the initial 3D surface S . The energy of a
candidate surface is defined as

E ( S ) = E texture ( S ) + E silhouette ( S ) + E internal ( S ) (8.9)

In Equation ( 8.9 ), the E texture term is based on the consistency of each surface point
with the projections in the resulting images, measured using the normalized cross-
correlation of windows around the projected correspondences. That is, for vectors of
image intensities u and v taken from square windows surrounding a correspondence
in a pair of images, we compute

n

1
s u s v (

NCC ( u , v ) = u i − µ )( v i − µ ) (8.10)

u v

i = 1

where

u and s u are the mean and standard deviation of the elements of u .
The normalized cross-correlation is robust to affine changes in intensity between
the windows. The E silhouette term forces the surface to project to the silhouettes in
the source images, and the E internal term acts to smooth the surface by decreasing its
surface area. The overall energy function is minimized by evolving the vertices of the

µ

18 See Section 8.4.3 for more information on fitting a mesh to 3D points.