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, $D({\tt M})$ , 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 , $d_1({\tt M}), d_2({\tt M}) \ldots d_n({\tt M})$ and weight functions $w_1({\tt M}), w_2({\tt M}) \ldots w_n({\tt M}_n)$ obtained from the depth maps for the different images. The combining rules gives a cumulative signed distance function for each voxel, $D({\tt M})$ , and a cumulative weight $W({\tt M})$. These functions are represented on a discrete voxel grid and an isosurface corresponding to $D(x)=0$ 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.5: Unweighted signed distance functions in 3D. (a) A camera looking down the x-axis observes a depth image, shown here as a reconstructed surface. Following one line of sight down the x-axis, a signed distance function as shown can be generated. The zero-crossing of this function is a point on the surface. (b) Another depth map yields a slightly different surface due to noise. Following the same line of sight as before, we obtain another signed distance function. By summing these functions, we arrive at a cumulative function with a new zero-crossing positioned midway between the original range measurements.

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, $r_1$ and $r_2$. The signed distance profiles, $d_1(x)$ and $d_2(x)$ may extend indefinitely in either direction, but the weight functions, $w_1(x)$ and $w_2(x)$ , 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:

$$D(x) = \frac{\sum w_i(x)d_i(x)}{\sum w_i(x)}$$ (H1)

$$W(x) = \sum w_i(x)$$ (H2)

where, $d_i(x)$ and $w_i(x)$ are the signed distance and weight functions from the ith range image. Expressed as an incremental calculation, the rules are:

$$D_{i+1}(x) = \frac{W_i(x)D_i(x)+w_i(x)d_i(x)}{\sum W_i(x)+w_{i+1}(x)}$$ (H3)

$$W_{i+1}(x) = W_i(x) + w_i(x)$$ (H4)

where $D_I(x)$ and $W_i(x)$ 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:

$$R = \frac{\sum w_i r_i}{\sum w_i}$$ (H5)

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

Figure 8.6: Signed distance and weight functions in one dimension. (a) The sensor looks down the x-axis and takes two measurements, $r_1$ and $r_2$ . $d_1(x)$ and $d_2(x)$ are the signed distance profiles, and $w_1(x)$ and $w_2(x)$ are the weight functions. In 1D, we might expect two sensor measurements to have the same weight magnitudes, but we have shown them to be of different magnitude here to illustrate how the profiles combine in the general case. (b) $D(x)$ is a weighted combination of $d_1(x)$ and $d_2(x)$ , and $W(x)$ is the sum of the weight functions. Given this formulation, the zero-crossing, $R$, becomes the weighted combination of $r_1$ and $r_2$ and represents our best guess of the location of the surface. In practice, we truncate the distance ramps and weights to the vicinity of the range points.

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].