Efficient Sparse ICP

Pavlos Mavridis       Anthousis Andreadis       Georgios Papaioannou
Department of Informatics, Athens University of Economics and Business

Computer Aided Geometric Design (Proceedings of GMP 2015)

automatic reassembly results

Figure 1. Rigid registration of two partially overlapping scans of a cultural heritage object. Left: The input scans at their initial pose. Middle: Pairwise registration using Sparse ICP. The optimizer in this case is trapped in a local minimum, failing to align the book at the middle of the scene. Right: Pairwise registration using our method provides the desired alignment. 3D dataset courtesy of Breuckmann GmbH.


The registration of two geometric surfaces is typically addressed using variants of the Iterative Closest Point (ICP) algorithm. The Sparse ICP method formulates the problem using sparsity-inducing norms, significantly improving the resilience of the registration process to large amounts of noise and outliers, but introduces a significant performance degradation. In this paper we first identify the reasons for this performance degradation and propose a hybrid optimization system that combines a Simulated Annealing search along with the standard Sparse ICP, in order to solve the underlying optimization problem more efficiently. We also provide several insights on how to further improve the overall efficiency by using a combination of approximate distance queries, parallel execution and uniform subsampling. The resulting method provides cumulative performance gain of more than one order of magnitude, as demonstrated through the registration of partially overlapping scans with various degrees of noise and outliers.

Interactive Results

Click (or tap) on the embedded 3D viewer to interactively explore the results of our rigid registration method.


The authors would like to thank the anonymous reviewers for their insightful comments and suggestions. We would also like to thank Dirk Rieke-Zapp and Michael Hermstein from Breuckmann GmbH for providing various 3D datasets and for having several valuable discussions on the topics of digitization and 3D data acquisition. The pottery dataset in Figure 8 was kindly provided by Ioannis Pratikakis from Athena Research Center. Finally, we would like to thank the authors of SparseICP and Super4PCS algorithms for freely providing the implementation of their methods. This work was supported by EC FP7 STREP project PRESIOUS, grant no. 600533.


title = "Efficient Sparse \{ICP\} ",
journal = "Computer Aided Geometric Design ",
year = "2015",
issn = "0167-8396",
doi = "http://dx.doi.org/10.1016/j.cagd.2015.03.022",
author = "Pavlos Mavridis and Anthousis Andreadis and Georgios Papaioannou",