A Result Analysis of “A Volumetric Method for Building Complex Models from Range Images by Brian Curless and Marc Levoy ” using VripPack

Nitesh Kumar and AbdulKareem S. N
Indian Institute of Technology Delhi

Introduction

This report is an approach to formal analysis of the results obtained after implementing the technique “A Volumetric Method for Building Complex Models from Range Images”
1
as introduced by Brian Curless
2
and Marc Levoy
3
over some sets of range images and the effect of changing various attributes during the process of reconstruction. For the sake of the same the package VripPack
4
has been used which was created and made available for common use by Brian Curless himself.

Before the results are presented in the report a quick reference to the paper and VripPack has been given for better understanding.

Abstract of the Paper

“A number of techniques have been developed for reconstructing surfaces by integrating groups of aligned range images. A desirable set of properties for such algorithms includes: incremental updating, representation of directional uncertainty, the ability to fill gaps in the reconstruction, and robustness in the presence of outliers. Prior algorithms possess subsets of these properties. In this paper, we present a volumetric method for integrating range images that possesses all of these properties.
Our volumetric representation consists of a cumulative weighted signed distance function. Working with one range image at a time, we first scan-convert it to a distance function, then combine this with the data already acquired using a simple additive scheme. To achieve space efficiency, we employ a run-length encoding of the volume. To achieve time efficiency, we resample the range image to align with the voxel grid and traverse the range and voxel scanlines synchronously. We generate the final manifold by extracting an isosurface from the volumetric grid. We show that under certain assumptions, this isosurface is optimal in the least squares sense. To fill gaps in the model, we tessellate over the boundaries between regions seen to be empty and regions never observed.
Using this method, we are able to integrate a large number of range images (as many as 70) yielding seamless, high-detail models of up to 2.6 million triangles. “ -Brian Curless & Marc Levoy

About VripPack

VripPack is a package for volumetrically merging a set of range images. Developed as part of the project to build a 3D fax machine, it is based on a new approach to surface reconstruction from range images (see Brian Curless and Marc Levoy , A Volumetric Method for Building Complex Models from Range Images, Proceedings of SIGGRAPH96). VripPack is being made available for research and commercial use, free of charge. A closely related software package is Volfill, a diffusion-based hole filler for large polygon meshes.

A quick look at the paper

The algorithm employs a continuous implicit function, D(x), represented by samples. The function represented is the weighted signed distance of each point x to the nearest range surface along the line of sight to the sensor. The function is constructed by combining signed distance functions d1 (x), d2 (x), ... dn (x) and weight functions w1 (x), w2 (x), ... wn (x) obtained from range images 1 ... n. The combining rules give us for each voxel a cumulative signed distance function, D(x), and a cumulative weight W (x). The functions are represente on a discrete voxel grid and extract an isosurface corresponding to D(x) = 0. Under a certain set of assumptions, this iso-surface is optimal in the least squares sense.
image: 0_home_nitesh_paper_files_img35.gif
Figure above 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 range scanning technology. For optical triangulation scanners, for example, Soucy
5
and Turk
6
make the weight depend on the dot product between each vertex normal and the viewing direction, reflecting greater uncertainty when the illumination is at grazing angles to the surface. Turk also argues that the range data at the boundaries of the mesh typically have greater uncertainty, requiring more down-weighting. We adopt these same weighting schemes for our optical triangulation range data.
image: 1_home_nitesh_paper_files_img45.gif
Figure above illustrates the construction and usage of the signed distance and weight functions in 1D. In Figure 3a, the sensor is posi- tioned at the origin looking down the +x axis and has taken two measurements, r1 and r2 . The signed distance profiles, d1 (x) and d2 (x) may extend indefinitely in either direction, but the weight functions, w1 (x) and w2 (x), taper off behind the range points.
Figure b is the weighted combination of the two profiles. The combination rules are straightforward:
image: 2_home_nitesh_paper_files_img36.gif
image: 3_home_nitesh_paper_files_img37.gif
or recursevely:
image: 4_home_nitesh_paper_files_img40.gif
image: 5_home_nitesh_paper_files_img41.gif
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, the weighting function is forced 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, the weights are forced to fall off at a distance equal to half the maximum uncertainty interval of the range 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 range 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. The uncertainties that apply to range image integration include errors in alignment between meshes as well as errors inherent in the scanning technology. A number of algorithms for aligning sets of range images have been explored and shown to yield excellent results
7
8
. The remaining error lies in the scanner it- self. For optical triangulation scanners, for example, this error has been shown to be ellipsoidal about the range points, with the major axis of the ellipse aligned with the lines of sight of the laser
9
10
.
image: 6_home_nitesh_paper_files_img46.gif
In practice, a fixed point representation for the signed distance function is used which bounds the values to lie between Dmin and Dmax as shown in the figure. The values of Dmin and Dmax must be negative and positive, respectively, as they are on opposite sides of a signed distance zero-crossing. For three dimensions, the whole algorithm can summarized as follows: First, all voxel weights are set to zero, so that new data will overwrite the initial grid values. Next, each range image is tessellated by constructing triangles from nearest neighbors on the sampled lattice. Tessellation over step discontinuities is avoided (cliffs in the range map) by discarding triangles with edge lengths that exceed a threshold. A weight at each vertex must also be computed as described above.
Once a range image has been converted to a triangle mesh with a weight at each vertex, the voxel grid we can be updated. The signed distance contribution is computed by casting a ray from the sensor through each voxel near the range surface and then intersecting it with the triangle mesh. The weight is computed by linearly interpolating the weights stored at the intersection triangle’s vertices. Having determined the signed distance and weight the updated formulae described in equations 3 and 4 can be applied.
At any point during the merging of the range images, the zero-crossing isosurface from the volumetric grid can be extracted . This extraction procedure is restricted to skip samples with zero weight, generating triangles only in the regions of observed data.

VripPack parameters and their significances

Converting range images to range surfaces

Before merging range data, vrip first converts each range image into a range surface; i.e., it creates a triangular tesselation by connecting nearest neighbors in the range image. Some neighbors, however, are far apart, indicating a depth discontinuity. No triangles should be created over depth discontinuities, because they are likely to be erroneous. You have a choice of two methods for avoiding these bad tesselations. Neighboring vertices in the range image are connected if the resulting triangle meets one of two criteria:

(1) the dot product between the triangle normal and the viewing direction is below a threshold value, or

(2) the lengths of all edges of the triangle are below a threshold value.

The default is to use the orientation criterion, but you can choose instead to use the edge length criterion with:

vrip_param -use_length 1

When using the orientation criterion, you can set the threshold (default is 0.15 or about 81 degrees) with the command:

vrip_param -min_view_dot <float>

The view direction is taken to be the vector, v = (0,0,-1), and the dot product is negated before comparing to the threshold. Note that this usage of a fixed view direction is only stricly correct when the sensor is ortho- graphic and looking down the -z axis. The optimal approach would be to consult the actual directions of the viewing rays in the vicinity of each triangle. This approach has yet to be implemented, but the orthographic approximation will give reasonable results if the viewing rays of your scanner do not diverge severely. When using the edge length criterion, you can set the threshold (default is 0.003) with the command:

vrip_param -max_edge_length <float>

Note that you do not have to use the range image tesselator inside of vrip; vrip can also merge pretesselated range surfaces, as long as they are in the ply format and the vertex indices are ordered counter-clockwise. However, as part of the reconstruction process, vrip resamples the range surface before merging it into the volume. The resampling effectively yields another range image for which the tesselation criterion still applies. Therfore, even if you are providing pre-tessellated range surfaces as input, you must select a suitable tesellation criterion.

Assigning vertex weights

Once a range surface has been tesselated, vrip will proceed to assign weights to the vertices. The formula for vertex weight is:

W = Wv · Wb

where Wv is the view weight and Wb is the boundary weight. The view weight is defined by:

Wv = (v · n)αv

where v is the view direction, n is the normal at the vertex, and αv controls how rapidly the view weight falls off with obliquity to the sensor. You can modify the value of αv (default is 2) with:

vrip_param -view_weight_exp <float>

The boundary weight is based on the number of steps (edge traversals) a vertex is from the boundary of the mesh. The equation for boundary weight is:
Wb= { 1,Sb Smax ( Sb Smax ) α b Sb Smax }
Where Sb is the number of edge steps a vertex is from the boundary, Smax is a threshold that determines how far the boundary downweighting should diffuse into the mesh, and αb controls how rapidly the boundary weight falls off with proximity to the boundary. You can modify the value of αb (default is 1) with:

vrip_param -boundary_weight_exp <float>

and you can modify the value of Smax (default is 8) with:

vrip_param -max_boundary_steps <int>

Merging range images

Now, to construct the volume and begin merging range images you type:

vripnew <name.vri> <conf_file> <bound_volume> <res_in_meters>

The <conf_file> will either be MANIFEST or the name of the conf file in which you enumerated the meshes and the transformations. Vrip must allocate a (sparse) volumetric grid before merging meshes. It uses the <bound_volume> argument for this purpose. The <bound_volume> may be a ply file that is the same size as or larger than the object you wish to reconstruct. Alternatively, you can repeat <conf_file> instead, and vrip will sift through all your ply files to determine a bounding volume large enough to encompass them when they are transformed into one coordinate system.
The voxel grid resolution (res_in_meters) has a tricky interplay with the parameters for the distance and weight ramps. The distance ramp is ideally chosen to be as narrow as twice the maximum uncertainty in the scanner. The resolution then has to be chosen small enough that it adequately samples this ramp, even with significant variations in surface orientation. If the resolution is not chosen to be small enough, then unwanted holes may appear in the reconstruction. The upshot is that you can reduce the number of holes by either increasing the resolution (by using a smaller number for res_in_meters) or by widening the ramps. The trade-off is as follows: smaller voxel size yields more triangles, while widening the ramps leads to more interference between opposing surfaces.

Screenshotsimage: 7_home_nitesh_Advanced_Graphics_ss_bun00000.png

Input to the package is a set of range images which are actually scans of the object from different angels. The range images look like the one above.
The part of object facing the scanner is having a surface and the one behind or not facing (unseen area) is not drawn at all. Lets have a look at some more range images.
image: 8_home_nitesh_Advanced_Graphics_ss_bun04500.png image: 9_home_nitesh_Advanced_Graphics_ss_bun09000.png image: 10_home_nitesh_Advanced_Graphics_ss_bun18000.png aimage: 11_home_nitesh_Advanced_Graphics_ss_bunchin00.png
Lets see the default reconstruction i.e. the reconstruction of 3D object with default parameters of the VripPack.
image: 12_home_nitesh_Advanced_Graphics_ss_def100.png
As one can see there are some holes in the reconstruction, which makes us believe that default may be an optimal choice in most cases but not in all.
The later images have been screenshot from reconstruction with changed parameters.
image: 13_home_nitesh_Advanced_Graphics_ss_len00100.png
This is the result obtained when the value of length parameter is reduced to 0.001. As mentioned earlier the length parameter defines critera for joining vertices in terms of the distance bettween vertices with default value to ne 0.003. Reduction in length results in increase in mumber of holes.
image: 14_home_nitesh_Advanced_Graphics_ss_len0100.png
This is the reconstruction in which the length parameter has been 10 times increased as compared to the last one. The value associated with this parameter is 0.01. It can be seen that there are no visible holes in the reconstruction (there are but a few holes at the lower ear, near the ear tip and at the foot of the bunny).
image: 15_home_nitesh_Advanced_Graphics_ss_len0200.png
This reconstruction has the length value further increased to 0.02. The holes from previous image are still present here. If the two images are looked upon closely one will observe that the later image is not as smooth as the former, because of surface irregularities (point outliers participating in the surface reconstruction).
image: 16_home_nitesh_Advanced_Graphics_ss_len0500.png
On further increasng the length value to 0.05, new holes are being introcduced at bunny's foot. There are several outliers near the hole at its lower ear which have becomeclearly visible now. Increasing the length value may fill up a few holes but after some extent it starts introducing irregularities.
image: 17_home_nitesh_Advanced_Graphics_ss_ang100.png
The vertices can be connected not only according to the vertex length but also on the basis of angle between their normals. The default value of this parameter is 0.15, which was used in the dafault reconstruction. The one used here is 0.1, little reduced to cover more and more points. It is observed in the reconstruction that the number of holes have been reduced as compared to the default one. The size of holes have also been reduced.
image: 18_home_nitesh_Advanced_Graphics_ss_ang0500.png
Upon further reducing the value to 0.05, the holes at bunny's legs have vanished, but the one at its ear and foot still prevail.
image: 19_home_nitesh_Advanced_Graphics_ss_ang0200.png
Still decreased value to 0.02 introduces outliers at the ear. The one big hole at bunny's feet appear filled but new holes also have been introduced where there were no holes.
image: 20_home_nitesh_Advanced_Graphics_ss_ang200.png
Increasing the value of angle reduces the number of vertices participating in the formation of edges. Here when the value of parameter is increased to 0.2, new holes are inroduced.
The default value of view weight cofficient is 2 which was seen in the default reconstruction.
image: 21_home_nitesh_Advanced_Graphics_ss_vw0_500.png
This is the reconstruction when the value of the view weight parameter is reduced to 0.5. There is not much difference except the size of holes which have been reduced a little.
image: 22_home_nitesh_Advanced_Graphics_ss_vw1600.png
Upon increasing the weighting factor the number of holes has increased because the way in which the factor is used in formula (see VripPack parameter's introduction) increases the gradient of weightage.
image: 23_home_nitesh_Advanced_Graphics_ss_b0b800.png
Boundry weight has two parameter which can be altered, boundry weight exponent and boundry weight steps. The default value of the exponent is 1 and of steps is 8.
The above image is a reconstruction where the exponent value has been reduced to 0 and the steps is left intact. This assigns equal weight to all the vertices and hence we can notice the irregularities which are introcduced here. Size of the holes have also been affected.
image: 24_home_nitesh_Advanced_Graphics_ss_b1b100.png
Upon resetting the exponent to 1 and setting the steps to 1. No visible difference except for the little smoothness.
image: 25_home_nitesh_Advanced_Graphics_ss_b1b6400.png
The exponent value is still 1 but the steps have been increased to 64. The size of the holes have been affected. The holes at the bunny's legs have increased a little. I can be concluded from this that the increasing gradient of weight may result in fine image but may also introduce holes after some threshold.
image: 26_home_nitesh_Advanced_Graphics_ss_b1b12800.png
Exponent in this image is 1 and step is 128.
image: 27_home_nitesh_Advanced_Graphics_ss_b4b800.png
The exponent value has been increased to 4 and the steps reset to 8.
image: 28_home_nitesh_Advanced_Graphics_ss_b16b800.png
The exponent value is further increased to 16 and step left intact. The last few parameter changes have done nothing more than increasing the gradient. If the images are looked closely the ones in which the gradient is steeper appear more smooth than the ones with less gradient, but due to difference in weighting factor more and more vertices fail to participate in the formation of surface leaving holes or altering their shapes and sizes.
One can not define an optimal set of parameter value which will work in all image scans. The parameter need to be chnaged according to the image scan and they may vary from image to image. Choosing appropriate parameter value should be the task of the user.

References

1http://graphics.stanford.edu/papers/volrange/paper_1_level/paper.html
2http://homes.cs.washington.edu/~curless/
3http://homes.cs.washington.edu/~levoy/
4www-graphics.stanford.edu/software/vrip/
5M. Soucy and D. Laurendeau. A general surface approach to the integration of a set of range views. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(4):344-358, April 1995.
6G. Turk and M. Levoy. Zippered polygon meshes from range images. In Proceedings of SIGGRAPH '94 (Orlando, FL, July 24-29, 1994), pages 311-318. ACM Press, July 1994.
7H. Gagnon, M. Soucy, R. Bergevin, and D. Laurendeau. Registration of multiple range views for automatic 3-D model building. In Proceedings 1994 IEEE Com- puter Society Conference on Computer Vision and Pattern Recognition,pages 581– 586, June 1994.
8G. Turk and M. Levoy. Zippered polygon meshes from range images. In Proceed- ings of SIGGRAPH ’94 (Orlando, FL, July 24-29, 1994), pages 311–318. ACM Press, July 1994.
9P. Hebert, D. Laurendeau, and D. Poussart. Scene reconstruction and description: geometric primitive extraction from multiple viewed scattered data. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pages 286–292, June 1993.
10M. Rutishauser, M. Stricker, and M. Trobina. Merging range images of arbitrar- ily shaped objects. In Proceedings 1994 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 573–580, June 1994.