A Divide and Conquer Method for 3D Registration of Inhomogeneous, Partially Overlapping Scans with Fourier Mellin SOFT (FMS)

High-end laser range-finders provide accurate 3D data over long ranges. But their scans are inhomogeneous, i.e., the environment is non-uniformly sampled, as there is denser data in the near range than in the far range. Furthermore, the generation of a scan is time-consuming. Thus, it is desirable to cover an area by as few scans as possible, i.e., scanning is more time-efficient if the overlap between scans is as small as possible. However, these factors pose significant challenges for state-of-the-art registration algorithms. In this work, we present a divide-and-conquer method that uses an efficient strategy to check for possible registrations between partitions of two scans. As underlying registration method, Fourier-Mellin-SOFT (FMS) is used. FMS is quite robust against partial overlaps but its performance is significantly boosted by the presented partitioning method. As concrete use case, results from the digitization of a WWII submarine bunker as a large-scale cultural heritage site are presented.