Resolution independent spin-images

In order to register two surfaces, it is necessary to identify corresponding points on each surface, either explicitly or implicitly. Our algorithm explicitly searches for corresponding points by comparing the local surface shape. We represent local shape using a spin-image signature. This signature is a mapping of nearby points from 3D to 2D. Corresponding points on the two surfaces will have similar spin-image signatures, and we can rapidly search for corresponding points using a similarity measure which is a monotonically increasing function of correlation between two spin-images.

The spin-image for point p is found by recording the distance of all nearby points x from the surface normal n (alpha) and the distance from x to p along n (beta). Corresponding points from different views have similar spin-images.

Surface meshes generated from ground-based sensors typically have a wide variation of resolution because the sensor measures points with a fixed angular resolution. Points further away from the sensor will be spaced further apart than those that are close. Since we register sequences of range images, points that are far away in one image will be closer in the next, and we must, therefore, frequently compare points at different resolutions.

Our original registration algorithm assumed that the resolutions of the input meshes were approximately uniform and equal to each other. If this was not the case, then we used an edge decimation algorithm to equalize the resolutions. However, this algorithm was very slow and resulted in an unacceptable loss of detail in the meshes. Consequently, we could not register meshes using this method.

Our solution was to develop face-based spin-images. Previously, spin-images were generated by mapping all nearby vertices into the spin-image coordinate system. Instead, we map all faces, by bilinearly interpolating across each face. The points sampled by this interpolation are then projected into spin-image coordinates and accumulated just as with the vertex-based spin-images. Ideally, a spin-image would be an exact representation of the original surface. Face-based spin-images achieve this goal, limited only by the resolution at which each face is sampled and by the loss of information from the representation of the surface as a collection of planar faces. Experiments show that using face-based spin-images increase the similarity of corresponding points without significantly increasing the similarity of non-matching points. Therefore, face-based spin-images make it easier to distinguish matching points from non-matching ones.

Close up of the points sampled for a face-based spin-image The vertex-based spin-image for this basis point is noisy because not enough vertices fall into the region of influence. The face-based spin-image for the same basis point.

An alternate method for generating face-based spin-images was developed by Owen Carmichael. His approach maps the faces directly into the spin-image coordinate system and then scans each projected face. This method has the advantage of exactly matching the scanning resolution to the spin-image resolution.

Face-based spin-images are resolution independent. A high resolution mesh can now be compared to a low resolution mesh. This was an important step in getting the terrain matching algorithm to work. A second advantage is that we can replace the resolution equalization algorithm with a faster mesh-simplification algorithm that strives to preserve the original mesh shape rather than to equalize edge lengths.


Last modified February 15, 1999
Daniel Huber (dhuber@cs.cmu.edu)