Stochastic global optimization for robust point set registration

Chavdar Papazov, Darius Burschka

Research output: Contribution to journalArticlepeer-review

45 Scopus citations


In this paper, we propose a new algorithm for pairwise rigid point set registration with unknown point correspondences. The main properties of our method are noise robustness, outlier resistance and global optimal alignment. The problem of registering two point clouds is converted to a minimization of a nonlinear cost function. We propose a new cost function based on an inverse distance kernel that significantly reduces the impact of noise and outliers. In order to achieve a global optimal registration without the need of any initial alignment, we develop a new stochastic approach for global minimization. It is an adaptive sampling method which uses a generalized BSP tree and allows for minimizing nonlinear scalar fields over complex shaped search spaces like, e.g., the space of rotations. We introduce a new technique for a hierarchical decomposition of the rotation space in disjoint equally sized parts called spherical boxes. Furthermore, a procedure for uniform point sampling from spherical boxes is presented. Tests on a variety of point sets show that the proposed registration method performs very well on noisy, outlier corrupted and incomplete data. For comparison, we report how two state-of-the-art registration algorithms perform on the same data sets.

Original languageEnglish
Pages (from-to)1598-1609
Number of pages12
JournalComputer Vision and Image Understanding
Issue number12
StatePublished - Dec 2011


  • Generalized BSP tree
  • Hierarchical decomposition of SO(3)
  • Rigid registration
  • Robust cost function
  • Stochastic global optimization
  • Uniform sampling from spherical boxes


Dive into the research topics of 'Stochastic global optimization for robust point set registration'. Together they form a unique fingerprint.

Cite this