Alignment Registration of Multiple Range Scans

Keywords: 3d alignment, 3d registration, range scans, deltasphere, unc
Summer 2002, Summer 2003
teaser image



At the University of North Carolina at Chapel Hill (UNC), I worked on a project that used a laser rangefinder device to capture and store large environments as computer models. My specific role consisted of creating a program to automatically align multiple overlapping sets of geometric data. The models created by this project have been used for many different purposes, among which there are prominent applications in historical preservation and reconstruction (for forensic, artistic, or entertainment purposes). Under the historical preservation category, one of the highlighted uses of this technology was to scan Thomas Jefferson's Monticello residence and then put the resulting computer model on display at the New Orleans Museum of Art for an exhibit detailing Jefferson's life. This exhibit allowed people to 'virtually' look into his study in full photo-realistic detail, with view dependence in the exhibit (i.e., giving spectators a 3D-accurate representation of the room when looking at it from different angles).

Another showcase use was constructing and scanning a mock crime-scene, complete with murder victim. The scene could then be analyzed in detail using the computer model. In addition, the use of a motion tracking system allowed for a user to hold a tracking-device and explore the body from all angles virtually.

The Deltasphere laser range finder we used (co-designed by Dr. Nyland) scans an area using a rotating laser and calculates the distance to each point using the time of travel. The same area is then photographed by a digital camera (placed at the same center of focus). This 2-part scanning process is done from a variety of angles, to obtain complete geometric (3D) and photographic (2D) data of the entire scene. The processing phase then aligns the multiple range scans to each other, removes or blends duplicate information (such as textures for the same region as captured from different angles), maps the 2D pictures onto the 3D geometry, and finally simplifies the data to make it smaller and more manageable. Each step of this process is quite involved, but the alignment registration of the different 3D scans (the stage I worked on) is a particularly challenging problem because the presence of noisy data makes finding an accurate alignment match very difficult.

The program I wrote for this task expanded on the works of others in the field, particularly the Stanford University dissertation of Prof. Szymon Rusinkiewicz. In this paper, Prof. Rusinkiewicz proposed a new method for registration that was ideally suited to our project because it exploited our knowledge of the camera location to more accurately sample the search space (i.e., in a radial manner as opposed to a linear one). I implemented this technique of aligning two scans, building it with a much more intuitive user-interface than previous systems. Later, I expanded this framework to align multiple scans simultaneously. However, I found that even the relatively small amount of noise in the input data greatly hampered our ability to achieve a perfect match, as local optimizations threw off the global match, and attempts at direct global registration were thwarted by the large non-overlapping portions of the data. Work on this problem still continues.


  • "Real-time Acquisition and Rendering of Large 3D Models,"
    Ph. D. dissertation, Stanford University,
    August 2001.


Simulated Murder Scene 360 Degree View

Simulated Murder Scene 360 Degree View:

This is a 360 degree view of a simulated murder scene, as captured by the range scanner. Notice that it contains geometric data only (i.e., no color data), and that it is distorted due to the radial scanning pattern of the DeltaSphere. The blue areas are those where the laser sent out by the scanner did not return. This is usually glass or other highly reflective surfaces.
Scanning Program Interface

Scanning Program Interface:

This is the interface to the scanning program, which shows a closeup from the scan. Notice that real-world distances can be found using the program. This data is originally in the form of a point cloud, but the program can be used to generate VRML files or other tesselated outputs.
Geometric Complexity of Captured Scene

Geometric Complexity of Captured Scene:

This shows the geometric complexity of the captured scene. Notice that even flat walls are highly tesselated, due to slight errors in the measurement, which cause the flat wall to appear to have some local curvatures. This is just one of the effects that has to be corrected in post-processing.
Scanning Process Output

Scanning Process Output:

One (cleaned-up) example of the output of the scanning process. This is NOT simply a photo! Notice that there are still some problems, such as the warping of the floor, the somewhat conflicting lighting on the walls, the holes in the floor and on the lamps, etc.
Simulated Murder Scene Alternate View

Simulated Murder Scene Alternate View:

This is a view of the murder scene from an angle which was NOT captured by the DeltaSphere. Here we can see just how much data is still missing from the complete room; this leads to what is currently an active research problem: the next best scan. The goal of this problem is to determine where next to place the scanner so as to get most coverage of the missing areas.
Simulated Murder Scene Alternate View 2

Simulated Murder Scene Alternate View 2:

Another view from an uncaptured angle. Notice the numerous artifacts throughout the room, suggesting the need for more post-processing work to clean up the data.
Captured View of Monticello

Captured View of Monticello:

A view of Monticello, as captured by the DeltaSphere. This was later made into a stereogram by (art)n, which is now on display at UNC-CH.
Partial Wireframe of Monticello

Partial Wireframe of Monticello:

A different view of Monticello, shown partially rendered in wireframe, to highlight the geometric complexity captured by the DeltaSphere.
Garage Scene 360 Degree View

Garage Scene 360 Degree View:

A 360 degree scan showing a garage scene.
Garage Scene Top View

Garage Scene Top View:

The garage scene, from above. The large circular holes are the floor and ceiling, which were not scanned due to the DeltaSphere being placed directly in the center of that circle.
Garage Scene Side View

Garage Scene Side View:

A side view of the garage scene.
Garage View Alternate View

Garage View Alternate View:

Another view of the garage scene.