Convergent Iterative Closest-Point Algorithm to Accomodate Anisotropic and Inhomogenous Localization Error

• Published in: IEEE transactions on pattern analysis and machine intelligence 2012-08, Vol.34 (8), p.1520-1532
• Main Authors: Maier-Hein, L., Franz, A. M., dos Santos, T. R., Schmidt, M., Fangerau, M., Meinzer, H., Fitzpatrick, J. M.
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithms; Animals; anisotropic weighting; Anisotropy; Applied sciences; Artificial intelligence; Biological and medical sciences; Cameras; Computer science; control theory; systems; Covariance matrix; Diagnostic Imaging; Exact sciences and technology; Head - anatomy & histology; Humans; ICP; Image Processing, Computer-Assisted - methods; Investigative techniques, diagnostic techniques (general aspects); Iterative closest point algorithm; Measurement; Medical sciences; Noise; Pattern recognition. Digital image processing. Computational geometry; point-based registration; Principal Component Analysis; Rabbits; Registration; surface algorithms; Three dimensional displays
• ISSN: 0162-8828; 1939-3539; 2160-9292
• DOI: 10.1109/TPAMI.2011.248

Since its introduction in the early 1990s, the Iterative Closest Point (ICP) algorithm has become one of the most well-known methods for geometric alignment of 3D models. Given two roughly aligned shapes represented by two point sets, the algorithm iteratively establishes point correspondences given the current alignment of the data and computes a rigid transformation accordingly. From a statistical point of view, however, it implicitly assumes that the points are observed with isotropic Gaussian noise. In this paper, we show that this assumption may lead to errors and generalize the ICP such that it can account for anisotropic and inhomogenous localization errors. We 1) provide a formal description of the algorithm, 2) extend it to registration of partially overlapping surfaces, 3) prove its convergence, 4) derive the required covariance matrices for a set of selected applications, and 5) present means for optimizing the runtime. An evaluation on publicly available surface meshes as well as on a set of meshes extracted from medical imaging data shows a dramatic increase in accuracy compared to the original ICP, especially in the case of partial surface registration. As point-based surface registration is a central component in various applications, the potential impact of the proposed method is high.