Laser-scanned range data is becoming increasingly commonplace in image-based rendering and 3D model reconstruction. Scanned data can be quickly acquired with moderately-priced hardware - yielding low-noise, accurate geometric datasets of real-world environments. However, before multiple range images of a scene can be used together, they must first be registered with each other. That is, we must determine the fixed translation and rotation which places the range images into a common coordinate system.

There are many possible methods for registering range images. For example, one may apply manual or automatic feature correspondence algorithms. However, manual correspondence methods tend to be very labor-intensive, and automatic methods are prone to error (a correspondence method which reduces these problems has been developed by Chris McCue and Lars Nyland – see http://www.cs.unc.edu/~ibr/projects/multiple). Another general technique for registering range images is the Iterated Closest Point (ICP) method. This method attempts to register a pair of range images by defining a metric describing the amount of error in a candidate registration. The minimum of this error function indicates the optimal registration, and can be found with standard function optimization techniques. A significant problem in ICP-based methods, however, is their reliance on shared points in the two range images. That is, these algorithms expect a significant number of points in one range image to also be seen in the other image. For projective range-finders such as laser scanners, this can be a problem since portions of the scene will be occluded in each range image.

In this work, we have developed a new ICP-based method which greatly reduces the reliance on shared points. Instead of focusing only on the points and surfaces of a range image, we explicitly use the empty space of each range image. The empty space is the volume of space between the range camera and each sampled point. Because the laser scanner measures the distance to the first hit along a ray, we know the space along that ray must be empty until the sampled point is encountered. Using this fact, we define a new metric to measure the error in a candidate registration. The minimum of this error function is found by standard minimization techniques, yielding an optimal registration solution. The end result is a semi-automatic registration method which does not rely on shared points in a pair of range images. The following examples show the algorithm operating on a pair of range images with almost no shared points whatsoever.

Three views of the two range images, in their original position and orientation. These range images contain few (if any) overlapping points

Two views of the misregistered range images, before we apply our registration algorithm.

Three views of the range images after the empty-space registration algorithm is applied

Maintained by Paul Rademacher

Research Sponsors