Building terrain maps from sequences of range images

The first step is known as map registration. Given two overlapping maps (represented as surface meshes), determine the rigid body transformation that correctly aligns the two surfaces. At this time, we assume that the surfaces are sufficiently complex that they actually constrain the registration process to a single solution. (As a counter-example, two planes are underconstrained and, therefore, have no unique registration transformation.) The registration algorithm was developed by Andrew Johnson in his doctoral thesis.

To perform registration, we search for similarly shaped regions on each of the two surfaces. Once we identify enough of these corresponding points, the rigid body transformation can be calculated in closed form. We find similar regions using spin-images, which are 2D signatures that capture the local shape of a surface. Our algorithm follows these steps:

1. Given: two surface meshes representing overlapping regions of terrain
2. Compute spin images for all points on mesh1 and a sampling of points on mesh2 (e.g., 25%)
3. For each sampled point on mesh2, compute a histogram the similarity to all the points in mesh1. The points associated with (most similar) outliers in the histogram are considered to be correspondences for this point.
4. Group the candidate correspondences based on geometric consistency. In other words, form groups out of all correspondences that could conceivably arise from a single rigid-body transformation.
5. For each group, calculate the rigid-body transformation that minimizes the distance between corresponding points.
6. Output the transformation with the minimum squared error of correspondences.

Results

Top view of the integrated terrain map for the eleven data sets in the mesa sequence (center). The numbered insets illustrate individual data sets, and two sets (1 and 11) are overlaid on the top-view. The larger insets show various perspective views of the map, and the white arrows indicate the location and direction of the viewpoint. Grid lines are two-meters apart on the combined map and one meter apart on the individual data sets.

Top-view of the integrated map built using data from the autonomous helicopter (top). The scene looks down on a cliff (approx. 20m high) with a small river running along its face. Perspective views of the map (bottom). Grid lines are 5 meters apart.

Top view of the integrated map built from seven data sets in the "piles" sequence. The data was gathered at the slag heap using the BF2 mounted on Navlab 5. A long row of dirt piles (approximately 1.5 meters high) lines the side of a dirt path along which the Navlab drove. Grid lines are 1 meter apart.