Matching Multiple 3D Scans

To digitalize environments without occlusions, multiple 3D scans have to be registered. After registration, the scene has to be globally consistent. A straightforward method for aligning several 3D scans is pairwise matching, i.e., the new scan is registered against the scan with the largest overlapping areas. The latter one is determined in a preprocessing step. Alternatively, Chen and Medioni [6] introduced an incremental matching method, i.e., the new scan is registered against a so-called metascan, which is the union of the previously acquired and registered scans. Each scan matching has a limited precision. Both methods accumulate the registration errors such that the registration of many scans leads to inconsistent scenes (figure 5) and to problems with the robot localization.

Pulli presents a registration method that minimizes the global error and avoids inconsistent scenes [13]. This method distributes the global error while the registration of one scan is followed by registration of all neighboring scans. Other matching approaches with global error minimization have been published, e.g., by Benjemaa et. al. [2] and Eggert et. al. [7].

Figure 5: Results of the scan matching of 20 scans (top view). All 3D scans were taken in an office environment, the GMD Robobench, the first one corresponds to figure 2. (a) Pairwise matching, (b) incremental matching, (c) 3D scan matching with edge points and (d) simultaneous matching. 3D animations can be found at http://www.ais.fhg.de/ARC/3D/videos.

Based on the idea of Pulli we have designed a method called simultaneous matching. Here, the first scan is the masterscan and determines the coordinate system. This scan is fixed. The following steps register all scans and minimize the global error:

1. Based on the robot odometry, pairwise matching is used to find a start registration for each new scan. This step speeds up computation.
2. A queue is initialized with the new scan.
3. Three steps are repeated until the queue is empty:
   1. The current scan is the first scan of the queue. This scan is removed from the queue.
   2. If the current scan is not the master scan, then a set of neighbors (set of all scans that overlap with the current scan) is calculated. This set of neighbors form one point set $M$. The current scan forms the data point set $D$ and is aligned with the ICP algorithms.
   3. If the current scan changes its location by applying the transformation, then each single scan of the set of neighbors that is not in the queue, is added to the queue.

Note: One scan overlaps with another, iff more than 250 corresponding point pairs exist. To speed up the matching, $k$D trees and reduced points are used (see table 1).

In contrast to Pulli's approach, the proposed method is totally automatic and no interactive pairwise alignment needs to be done. Furthermore the point pairs are not fixed [13]. Figure 5 shows results of the scan matching using 20 scans taken in the GMD Robobench. Pairwise matching (a) works sufficient, incremental matching shows most outliers (b), and simultaneous matching (d) reconstructs the corridor perfectly.