  Point cloud registration is a fundamental and challenging problem for
autonomous robots interacting in unstructured environments for applications
such as object pose estimation, simultaneous localization and mapping,
robot-sensor calibration, and so on. In global correspondence-based point cloud
registration, data association is a highly brittle task and commonly produces
high amounts of outliers. Failure to reject outliers can lead to errors
propagating to downstream perception tasks. Maximum Consensus (MC) is a widely
used technique for robust estimation, which is however known to be NP-hard.
Exact methods struggle to scale to realistic problem instances, whereas high
outlier rates are challenging for approximate methods. To this end, we propose
Graph-based Maximum Consensus Registration (GMCR), which is highly robust to
outliers and scales to realistic problem instances. We propose novel consensus
functions to map the decoupled MC-objective to the graph domain, wherein we
find a tight approximation to the maximum consensus set as the maximum clique.
The final pose estimate is given in closed-form. We extensively evaluated our
proposed GMCR on a synthetic registration benchmark, robotic object
localization task, and additionally on a scan matching benchmark. Our proposed
method shows high accuracy and time efficiency compared to other
state-of-the-art MC methods and compares favorably to other robust registration
methods.
