Abstract
Automatic registration of range images is a fundamental problem in 3D modeling of free-from objects. Various feature matching algorithms have been proposed for this purpose. However, these algorithms suffer from various limitations mainly related to their applicability, efficiency, robustness to resolution, and the discriminating capability of the used feature representation. We present a novel feature matching algorithm for automatic pairwise registration of range images which overcomes these limitations. Our algorithm uses a novel tensor representation which represents semi-local 3D surface patches of a range image by third order tensors. Multiple tensors are used to represent each range image. Tensors of two range images are matched to identify correspondences between them. Correspondences are verified and then used for pairwise registration of the range images. Experimental results show that our algorithm is accurate and efficient. Moreover, it is robust to the resolution of the range images, the number of tensors per view, the required amount of overlap, and noise. Comparisons with the spin image representation revealed that our representation has more discriminating capabilities and performs better at a low resolution of the range images.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Ashbrook, A.P., Fisher, R.B., Robertson, C., and Werghi, N. 1998. Finding surface correspondence for object recognition and registration using pairwise geometric histograms. International Journal of Pattern Recognition and Artificial Intelligence, 2:674–686.
Benjemma, R. and Schmitt, F. 1997. Fast global registration of 3D sampled surfaces using a multi-Z-buffer technique. In International Conference on Recent Advances in 3D Digital Imaging, pp. 113–120.
Besl, P. 1990. Machine Vision for Three-dimensional Scenes. Academic Press.
Besl, P.J. and McKay, N.D. 1992. Reconstruction of real-world objects via simultaneous registration and robust combination of multiple range images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2):239–256.
Campbell, R.J. and Flynn, P.J. 2001. A survey of free-form object representation and recognition techniques. Computer Vision and Image Understanding, 81(2):166–210.
Chen, C., Hung, Y., and Cheng, J. 1991. RANSAC-based DARCES: A new approach to fast automatic registration of partially overlapping range images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(11):1229–1234.
Chen, Y. and Medioni, G. 1991. Object modeling by registration of multiple range images. In IEEE International Conference on Robotics and Automation, pp. 2724–2729.
Cheng, J. and Don, H. 1991. A graph matching approach to 3-D point correspondences. International Journal of Pattern Recognition and Artificial Intelligence, 5(3):399–412.
Chua, C.S. and Jarvis, R. 1996. 3D free-form surface registration and object recognition. International Journal of Computer Vision, 17:77–99.
Chua, C.S. and Jarvis, R. 1997. Point signatures: A new representation for 3D object recognition. International Journal of Computer Vision, 25(1):63–85.
Curless, B. and Levoy, M. 1996. A volumetric method for building complex models from range images. In Computer Graphics, SIGGRAPH.
Foley, J., van Dam, A., Feiner, S.K., and Hughes, J.F. 1990. Computer Graphics-Principles and Practice, 2nd ed. Addison-Wesley.
Garland, M. 1999. Quadric-based polygonal surface simplification. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213.
Garland, M. and Heckbert, P.S. 1997. Surface simplification using quadric error metrics. In SIGGRAPH, pp. 209–216.
Higuchi, K., Hebert, M., and Ikeuchi, K. 1994. Building 3-D models from unregistered range images. In IEEE International Conference on Robotics and Automation, vol. 3, pp. 2248–2253.
Johnson, A.E. 1997. Spin images: A representation for 3-D surface matching. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213. Available along with range data at http://robotics.jpl.nasa.gov/people/johnson/thesis/thesis.html.
Johnson, A.E. and Hebert, M. 1997. Surface registration by matching oriented points. In International Conference on Recent Advances in 3-D Imaging and Modelling, pp. 121–128.
Johnson, A.E. and Hebert, M. 1999. Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(5):674–686.
Lorensen, W.E. and Cline, H.E. 1987. A high resolution 3D surface construction algorithm. In Computer Graphics. ACM SIGGRAPH, pp. 163–169.
Mesh Tool Box, 2004. Vision and mobile robotics laboratory, Carnegie Mellon University, available at http://www-2.cs.cmu.edu/vmr/software/meshtoolbox/downloads.html.
Mian, A.S., Bennamoun, M., and Owens, R.A. 2004a. A novel algorithm for automatic 3D model-based free-form object recognition. In IEEE International Conference on Systems, Man and Cybernetics, pp. 6348–6353.
Mian, A.S., Bennamoun, M., and Owens, R.A. 2004b. From unordered range images to 3D models: A fully automatic multiview correspondence algorithm. In Theory and Practice of Computer Graphics. IEEE Computer Society Press, pp. 162–166.
Mian, A.S., Bennamoun, M., and Owens, R.A. 2004c. Matching tensors for automatic correspondence and registration. In European Conference on Computer Vision, vol. 2, pp. 495–505.
Mian, A.S., Bennamoun, M., and Owens, R.A., 2004d. Performance analysis of an improved tensor based correspondence algorithm for automaic 3D modeling. In IEEE International Conference on Image Processing, pp. 1951–1954.
Nishino, K. and Ikeuchi, K. 2002. Robust simultaneous registration of multiple range images. In Asian Conference on Computer Vision, pp. 454–461.
Oishi, T., Sagawa, R., Nakazawa, A., Kurazume, R., and Ikeuchi, K. 2003. Parallel alignment of a large number of range images. In International Conference on 3-D Digital Imaging and Modeling, pp. 195–202.
Rangarajan, A., Chui, H., and Duncan, J. 1999. Rigid point feature registration using mutual information. Medical Image Analysis, 3(4):425–440.
Roth, G. 1999. Registering two overlapping range images. In IEEE International Conference on 3-D Digital Imaging and Modeling, pp. 191–200.
Rusinkiewicz, S. and Levoy, M. 2001. Efficient variants of the ICP algorithm. In 3DIM, pp. 145–152.
Stanford Computer Graphics Laboratory, 2001. A volumetric range image processing package. http://graphics.stanford.edu/software/vrip/.
Stanford Computer Graphics Laboratory, 2003. The Stanford 3D scanning repository. http://graphics.stanford.edu/data/3Dscanrep/.
Stephens, R.S. 1990. A probabilistic approach to the hough transform. In British Machine Vision Conference, pp. 55–59.
The University of Stuttgart, 2001. Stuttgart range image database. http://range.informatik.uni-stuttgart.de/htdocs/html/.
Williams, J. and Bennamoun, M. 2001. Simultaneous registration of multiple corresponding point sets. Computer Vision and Image Understanding, 81(1):117–142.
Wyngaerd, J.V., Gool, L.V., Koth, R., and Proesmans, M. 1999. Invariant-based registration of surface patches. In IEEE International Conference on Computer Vision, vol. 1, pp. 301–306.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work has been provisionally patented under Australian patent number 2004902436 and is sponsored by ARC grant number DP0344338.
Rights and permissions
About this article
Cite this article
Mian, A.S., Bennamoun, M. & Owens, R.A. A Novel Representation and Feature Matching Algorithm for Automatic Pairwise Registration of Range Images. Int J Comput Vision 66, 19–40 (2006). https://doi.org/10.1007/s11263-005-3221-0
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s11263-005-3221-0