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 (7) introduced an incremental matching method, i.e., the new scan is registered against a so-called metascan, which is the union of the previous 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 and problems with the robot localization. Pulli presents a registration method that minimizes the global error and avoids inconsistent scenes (18). 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. (3,4) and Eggert et al. (8). Based on the idea of Pulli we designed a method called simultaneous matching. Thereby, 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 a 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 end of 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 (23,24). In contrast to Pulli's approach, the proposed method is totally automatic and no interactive pairwise alignment has to be done. Furthermore the point pairs are not fixed (18). The computed transformations are applied to the robot pose and thus a relocalization of the robot is done after every 3D scan. The simultaneous localization and mapping problem (SLAM) is solved.