        Multiple Range Data Set Registration  Figures 1a and 1b:    Two sets of range data taken from the same scene (click any figure for more detail)

The Problem:

When obtaining range and color information, taking data from one position in a scene cannot completely represent everything in that scene.  The data obtained by the laser from each position only contains information about the first surface the laser beam encountered, creating shadows where other surfaces are occluded from the viewpoint.  By taking multiple sets of data from different positions (figures 1a and 1b) and registering them with one another, the occluded areas can be minimized in the final rendering.  The goal of this registration process is to find a transformation matrix that will map the coordinate system of one data set onto that of another.  We register these data sets in pairs until they all can be transformed to a single coordinate system.

Our Method:

The first step in registering two data sets is to manually identify corresponding planar surfaces in the range data.  After transforming the points from the spherical coordinates of the laser into Cartesian coordinates in 3-space, we select (in each data set) points in three planar surfaces that exist in both.  The best-fit plane (in the least squares sense) is then determined for each of the selected sets of points (figures 2a and 2b).  Figures 2a and 2b:    With the three matching planar surfaces selected in each set

Once these planes are known it takes one rotation to make the first plane from each set parallel to each other, a second rotation to make the other two planes as nearly parallel as is possible, and then a translation to register the planes and therefore the sets.  Figure 3a shows the sets and their respective planes aligned, and figure 3b shows in red and green which points in the final data set came from which initial set.  Figures 3a and 3b:    After aligning the coresponding planes, and with colors to show the original data sets

This approach allows us several advantages.  First, one difficulty in using just points to align two data sets is that it is unlikely for any point in set A that there is a corresponding point in set B.  Secondly, the use of a best-fit approximation to a planar surface helps minimize the effect of the noise in the range data. Finally, the transformation matrix we obtain via the registration process is useful later on when these sets will be rendered, as knowing the transformations between camera positions helps us determine which data sets should currently be rendered.   