iccv iccv2013 iccv2013-185 iccv2013-185-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jiaolong Yang, Hongdong Li, Yunde Jia
Abstract: Registration is a fundamental task in computer vision. The Iterative Closest Point (ICP) algorithm is one of the widely-used methods for solving the registration problem. Based on local iteration, ICP is however well-known to suffer from local minima. Its performance critically relies on the quality of initialization, and only local optimality is guaranteed. This paper provides the very first globally optimal solution to Euclidean registration of two 3D pointsets or two 3D surfaces under the L2 error. Our method is built upon ICP, but combines it with a branch-and-bound (BnB) scheme which searches the 3D motion space SE(3) efficiently. By exploiting the special structure of the underlying geometry, we derive novel upper and lower bounds for the ICP error function. The integration of local ICP and global BnB enables the new method to run efficiently in practice, and its optimality is exactly guaranteed. We also discuss extensions, addressing the issue of outlier robustness.
[1] D. Aiger, N. J. Mitra, and D. Cohen-Or. 4-points congruent sets for robust pairwise surface registration. In SIGGRAPH, 2008. 2
[2] E. Ask, O. Enqvist, and F. Kahl. Optimal geometric fitting under the truncated L2-norm. In CVPR, 2013. 2
[3] J.-C. Bazin, Y. Seo, and M. Pollefeys. Globally optimal consensus set maximization through rotation search. In ACCV, 2012. 2
[4] S. Belongie, J. Malik, and J. Puzicha. Shape matching and object recognition using shape contexts. T-PAMI, 2002. 2
[5] P. Besl and N. McKay. A method for registration of 3-D shapes. T-PAMI, 1992. 1, 5
[6] D. Breitenreicher and C. Schn o¨rr. Model-based multiple rigid object detection and registration in unstructured range data. IJCV, 2011. 2
[7] T. M. Breuel. Implementation techniques for geometric branch-andbound matching methods. CVIU, 2003. 2
[8] U. Castellani and A. Bartoli. 3D shape registration. 3D Imaging, Analysis, and Applications, 2012. 2
[9] G. Champleboux, S. Lavallee, R. Szeliski, and L. Brunie. From accurate range imaging sensor calibration to accurate model-based 3D object localization. In CVPR, 1992. 7
[10] Y. Chen and G. Medioni. Object modeling by registration of multiple range images. In ICRA, 1991. 1
[11] D. Chetverikov, D. Svirko, D. Stepanov, and P. Krsek. The trimmed iterative closest point algorithm. In ICPR, 2002. 7
[12] O. Enqvist, K. Josephson, and F. Kahl. Optimal correspondences from pairwise constraints. In ICCV, 2009. 2, 3
[13] A. Fitzgibbon. Robust registration of 2D and 3D point sets. Image and Vision Computing, 2003. 2, 6, 7
[14] N. Gelfand, N. J. Mitra, L. J. Guibas, and H. Pottmann. Robust global registration. In Eurographics Symposium on Geometry Processing, 2005. 2
[15] R. I. Hartley and F. Kahl. Global optimization through searching rotation space and optimal estimation of the essential matrix. In ICCV, 2007. 2
[16] R. I. Hartley and F. Kahl. Global optimization through rotation space search. IJCV, 2009. 2, 3
[17] D. P. Huttenlocher, G. A. Klanderman, and W. J. Rucklidge. Comparing images using the hausdorff distance. T-PAMI, 1993. 2
[18] B. Jian and B. Vemuri. A robust algorithm for point set registration using mixture of gaussians. In ICCV, 2005. 2
[19] A. E. Johnson and M. Hebert. Using spin images for efficient object recognition in cluttered 3D scenes. T-PAMI, 1999. 2
[20] J.-H. Kim, H. Li, and R. Hartley. Motion estimation for multi-camera systems using global optimization. CVPR, 2008. 2
[21] K. Lai, L. Bo, X. Ren, and D. Fox. A large-scale hierarchical multiview rgb-d object dataset. In ICRA, 2011. 7
[22] H. Li. Consensus set maximization with guaranteed global optimality for robust geometry estimation. ICCV, 2009. 2
[23] H. Li and R. Hartley. The 3D-3D registration problem revisited. In ICCV, 2007. 2, 3
[24] A. Makadia, A. Patterson, and K. Daniilidis. Fully automatic registration of 3D point clouds. In CVPR, 2006. 2
[25] T. Masuda and N. Yokoya. A robust method for registration and segmentation ofmultiple range images. In CAD-Based Vision Workshop, 1994. 7
[26] D. M. Mount, N. S. Netanyahu, and J. Le Moigne. Efficient algorithms for robust feature matching. Pattern recognition, 1999. 2
[27] A. Myronenko and X. Song. Point set registration: coherent point drift. T-PAMI, 2010. 2
[28] C. Olsson, F. Kahl, and M. Oskarsson. Branch-and-bound methods for euclidean registration problems. T-PAMI, 2009. 2
[29] F. Pfeuffer, M. Stiglmayr, and K. Klamroth. Discrete and geometric branch and bound algorithms for medical image registration. Annals of Operations Research, 2012. 2
[30] T. Ruland, T. Pajdla, and L. Kruger. Globally optimal hand-eye calibration. In CVPR, 2012. 2
[31] S. Rusinkiewicz and M. Levoy. Efficient variants of the icp algorithm. In 3DIM, 2001. 2
[32] R. Sandhu, S. Dambreville, and A. Tannenbaum. Point set registration via particle filtering and stochastic dynamics. T-PAMI, 2010. 2
[33] Y. Tsin and T. Kanade. A correlation-based approach to robust point set registration. ECCV, 2004. 2
[34] M. P. Wachowiak, R. Smol ı´kov a´, Y. Zheng, J. M. Zurada, and A. S. Elmaghraby. An approach to multimodal biomedical image registration utilizing particle swarm optimization. IEEE Transactions on Evolutionary Computation, 2004. 2
[35] Z. Zhang. Iterative point matching for registration of free-form curves and surfaces. IJCV, 1994. 1 11446644