Next: Marching cubes Up: Surface model Previous: Example   Contents

## Volumetric integration

To generate a complete 3D model from different depth maps we propose to use the volumetric integration approach of Curless and Levoy [19]. This approach is described in this section.

The algorithm employs a continuous implicit function, , represented by samples. The function we represent is the weighted signed distance of each point to the nearest range surface along the line of sight to the sensor. We construct this function by combining signed distance functions , and weight functions obtained from the depth maps for the different images. The combining rules gives a cumulative signed distance function for each voxel, , and a cumulative weight . These functions are represented on a discrete voxel grid and an isosurface corresponding to is extracted. Under a certain set of assumptions, this isosurface is optimal in the least squares sense [18].

Figure 8.5 illustrates the principle of combining unweighted signed distances for the simple case of two range surfaces sampled from the same direction. Note that the resulting isosurface would be the surface created by averaging the two range surfaces along the sensor's lines of sight. In general, however, weights are necessary to represent variations in certainty across the range surfaces. The choice of weights should be specific to the depth estimation procedure. It is proposed to make weights depend on the dot product between each vertex normal and the viewing direction, reflecting greater uncertainty when the observation is at grazing angles to the surface, as Soucy [138] proposed for optical triangulation scanners. Depth values at the boundaries of a mesh typically have greater uncertainty, requiring more down-weighting.

Figure 8.6 illustrates the construction and usage of the signed distance and weight functions in 1D. In Figure 8.6a, the sensor is positioned at the origin looking down the +x axis and has taken two measurements, and . The signed distance profiles, and may extend indefinitely in either direction, but the weight functions, and , taper off behind the range points for reasons discussed below.

Figure 8.6b is the weighted combination of the two profiles. The combination rules are straightforward:

 (H1) (H2)

where, and are the signed distance and weight functions from the ith range image. Expressed as an incremental calculation, the rules are:
 (H3) (H4)

where and are the cumulative signed distance and weight functions after integrating the ith range image. In the special case of one dimension, the zero-crossing of the cumulative function is at a range, R given by:
 (H5)

i.e., a weighted combination of the acquired range values, which is what one would expect for a least squares minimization.

In principle, the distance and weighting functions should extend indefinitely in either direction. However, to prevent surfaces on opposite sides of the object from interfering with each other, we force the weighting function to taper off behind the surface. There is a trade-off involved in choosing where the weight function tapers off. It should persist far enough behind the surface to ensure that all distance ramps will contribute in the vicinity of the final zero crossing, but, it should also be as narrow as possible to avoid influencing surfaces on the other side. To meet these requirements, we force the weights to fall off at a distance equal to half the maximum uncertainty interval of the depth measurements. Similarly, the signed distance and weight functions need not extend far in front of the surface. Restricting the functions to the vicinity of the surface yields a more compact representation and reduces the computational expense of updating the volume.

In two and three dimensions, the depth measurements correspond to curves or surfaces with weight functions, and the signed distance ramps have directions that are consistent with the primary directions of sensor uncertainty.

For three dimensions, we can summarize the whole algorithm as follows. First, we set all voxel weights to zero, so that new data will overwrite the initial grid values. The signed distance contribution is computed by making the difference between the depth read out at the projection of the grid point in the depth map and the actual distance between the point and the camera projection center. The weight is obtained from a weight map that has been precomputed. Having determined the signed distance and weight we can apply the update formulae described in equations (8.3) and (8.4).

At any point during the merging of the range images, we can extract the zero-crossing isosurface from the volumetric grid. We restrict this extraction procedure to skip samples with zero weight, generating triangles only in the regions of observed data. The procedure used for this is marching cubes [81].

Subsections

Next: Marching cubes Up: Surface model Previous: Example   Contents
Marc Pollefeys 2002-11-22