JRM Vol.18 No.6 pp. 765-771
doi: 10.20965/jrm.2006.p0765


HM-ICP: Fast 3-D Registration Algorithm with Hierarchical and Region Selection Approach of M-ICP

Haruhisa Okuda*, Yasuo Kitaaki*, Manabu Hashimoto*,
and Shun’ichi Kaneko**

*Advanced Technology R&D Center, Mitsubishi Electric Corp., 8-1-1 Tsukaguchi-Honmachi, Amagasaki, Hyogo 661-8661, Japan

**Graduate School of Information Science and Technology, Hokkaido University, Kita 14, Nishi 9, Kita-ku, Sapporo 060-0814, Japan

April 5, 2006
July 3, 2006
December 20, 2006
3-D, ICP, M-estimator, hierarchical matching, robustness, high-speed, partial region

This paper presents a novel fast and highly accurate 3-D registration algorithm. The ICP (Iterative Closest Point) algorithm converges all the 3-D data points of two data sets to the best-matching points with minimum evaluation values. This algorithm is in widespread use because it has good validity for many applications, but it extracts a heavy computational cost and is very sensitive to error. This is because it uses all the data points of two data sets and least mean square optimization. We previously proposed the M-ICP algorithm, which uses M-estimation to realize robustness against outlying gross noise with the original ICP algorithm. In this paper, we propose a novel algorithm called HM-ICP (Hierarchical M-ICP), which is an extension of the M-ICP that selects regions for matching and hierarchical searching of selected regions. This method selects regions by evaluating the variance of distance values in the target region, and homogeneous topological mapping. Some fundamental experiments using real data sets of 3-D measurement demonstrate the effectiveness of the proposed method, achieving a reduction of more than ten thousand times for computational costs. We also confirmed an error of less than 0.1% for the measurement distance.

Cite this article as:
Haruhisa Okuda, Yasuo Kitaaki, Manabu Hashimoto, and
and Shun’ichi Kaneko, “HM-ICP: Fast 3-D Registration Algorithm with Hierarchical and Region Selection Approach of M-ICP,” J. Robot. Mechatron., Vol.18, No.6, pp. 765-771, 2006.
Data files:
  1. [1] K. Ikeuchi and K. S. Hong, “Toward automatic generation of object recognition program,” Proc. of IEEE, Vol.76, No.8, pp. 1016-1035, 1988.
  2. [2] Y. Sumi, Y. Kawai, T. Yoshimi, and F. Tomita, “Recognition of 3D Free-Form Objects Using Segment-Based Stereo Vision,” Proc. of Sixth Int’l Conf. on Computer Vision, ICCV’98, pp. 668-674, 1998.
  3. [3] Y. Sumi, Y. Ishiyama, and F. Tomita, “Hyper Frame Vision: A Real-Time Vision System for 6-DOF Object Localization,” Proc. ICPR02, III, pp. 577-580, 2002.
  4. [4] P. J. Besl and N. D. McKay, “A Method for Registration of 3-D Shapes,” IEEE Trans. on PAMI, Vol.14, No.2, pp. 673-689, 1992.
  5. [5] H. Murase and S. K. Nayar, “Appearance-based detection of 3D objects in cluttered scenes,” Pattern Recognition Letters, Vol.18, pp. 375-384, 1997.
  6. [6] T. Takeguchi, T. Kondo, S. Kaneko, and S. Igarashi, “Object Recognition based on Depth Aspect Image Matching,” IAPR Workshop on Machine Vision Applications (MVA2000), pp. 476-480, 2000.
  7. [7] S. Kaneko, T. Kondo, A. Miyamoto, and S. Igarashi, “Robust ICP Registration Algorithm Extended by M-estimation,” Trans. on JSPE (The Japan Society for Precision Engineering), Vol.67, No.8, pp. 1276-1280, 2001 (in Japanese).
  8. [8] S.Kaneko, T. Kondo, and A. Miyamoto, “Robust Matching of 3D Contours Using Iterative Closest Point Algorithm Improved by M-estimation,” Pattern Recognition, Vol.36, No.9, pp. 2041-2047, 2003.
  9. [9] R. Kurazume, K. Noshino, Z. Zhang, and K. Ikeuchi, “Simultaneous 2D images and 3D geometric model registration for texture mapping utilizing reflectance attribute,” Proc. of Fifth Asian Conference on Computer Vision (ACCV), Vol.1, pp. 99-106, 2002.
  10. [10] K. Nishino and K. Ikeuchi, “Robust simultaneous registration of multiple range images,” Proceedings of the Fifth Asian Conference on Computer Vision, pp. 454-461, January, 2002.
  11. [11] B. Ma, R. E. Ellis, and D. J. Fleet, “Spotlights: A robust method for surface-based registration in orthopedic surgery,” Medical Image Computing and Computer-Assisted Intervention – MICCAI’99, Springer Lecture Notes in Computer Science 1496, pp. 936-944, 1999.
  12. [12] M. Hirooka, K. Sumi, M. Hashimoto, H. Okuda, and S. Kuroda, “Hierarchical Distributed Template Matching,” Proc. of SPIE Symposium on Electronic Imaging and Science and Technology, Vol.3029, pp. 176-183, 1997.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Feb. 25, 2021