Fast rotation search for real-time interactive point cloud registration

Our goal is the registration of multiple 3D point clouds obtained from LIDAR scans of underground mines. Such a capability is crucial to the surveying and planning operations in mining. Often, the point clouds only partially overlap and initial alignment is unavailable. Here, we propose an interactive user-assisted point cloud registration system. Guided by the system, the user's role is simply to identify and search for overlapping regions across the point clouds. Specifically, given two point sets, the user clicks on a point in one set, then simply hovers the mouse on the other set to find a matching point. Each mouse position gives rise to a translation, and our system instantly optimises the rotation that aligns the point clouds. Assuming that each individual point set is horizontally levelled with the ground by the level compensator on the LIDAR device, given a candidate 3D translation only one angular parameter needs to be estimated to rotationally align two 3D point sets. We propose a fast rotation search algorithm that delivers globally optimal results in real time. Our method conducts branch-and-bound optimisation with a novel bounding function whose evaluation amounts to simple sorted array operations. This provides smooth and accurate feedback to the user's search for overlapping regions. Our system is intuitive and helps to accelerate the registration of multiple scans.