Yago Díez
Ferran Roure
Skip Abstract Section
Abstract
3D registration or matching is a crucial step in 3D model reconstruction. Registration applications span along a variety of research fields, including computational geometry, computer vision, and geometric modeling. This variety of applications produces many diverse approaches to the problem but at the same time yields divergent notations and a lack of standardized algorithms and guidelines to classify existing methods. In this article, we review the state of the art of the 3D rigid registration topic (focused on Coarse Matching) and offer qualitative comparison between the most relevant approaches. Furthermore, we propose a pipeline to classify the existing methods and define a standard formal notation, offering a global point of view of the literature.
Our discussion, based on the results presented in the analyzed papers, shows how, although certain aspects of the registration process still need to be tested further in real application situations, the registration pipeline as a whole has progressed steadily. As a result of this progress in all registration aspects, it is now possible to put together algorithms that are able to tackle new and challenging problems with unprecedented data sizes and meeting strict precision criteria.
- Dror Aiger, Niloy J. Mitra, and Daniel Cohen-Or. 2008. 4-points congruent sets for robust pairwise surface registration. ACM Transactions on Graphics 27, 85. Google Scholar
Digital Library
- Andrea Albarelli, Emanuele Rodola, and Andrea Torsello. 2010. A game-theoretic approach to fine surface registration without initial motion estimation. In Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, Los Alamitos, CA, 430--437.Google ScholarCross Ref
- Marc Alexa. 2002. Recent advances in mesh morphing. Computer Graphics Forum 21, 173--198.Google ScholarCross Ref
- Mathieu Aubry, Ulrich Schlickewei, and Daniel Cremers. 2011. The wave kernel signature: A quantum mechanical approach to shape analysis. In Proceedings of the 2011 International Conference on Computer Vision Workshops (ICCV Workshops). IEEE, Los Alamitos, CA, 1626--1633.Google ScholarCross Ref
- Stephen Bailey. 2012. Principal component analysis with noisy and/or missing data. Publications of the Astronomical Society of the Pacific 124, 919, 1015--1023.Google Scholar
- Paul J. Besl and Neil D. McKay. 1992. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence 14, 2, 239--256. Google ScholarDigital Library
- Harry Blum. 1967. A transformation for extracting new descriptors of shape. In Models for the Perception of Speech and Visual Form. MIT Press, Cambridge, MA, 362--380.Google Scholar
- Edmond Boyer, Alexander M. Bronstein, Michael M. Bronstein, Benjamin Bustos, Tal Darom, Radu Horaud, Ingrid Hotz, Yosi Keller, Johannes Keustermans, Artiom Kovnatsky, Roee Litman, Jan Reininghaus, Ivan Sipiran, Dirk Smeets, Paul Suetens, Dirk Vandermeulen, Andrei Zaharescu, and Valentin Zobel. 2011. SHREC 2011: Robust feature detection and description benchmark. In Proceedings of the 4th Eurographics Conference on 3D Object Retrieval. 71--78. Google ScholarDigital Library
- Alexander M. Bronstein, Michael M. Bronstein, Benjamin Bustos, Umberto Castellani, Marco Crisani, Bianca Falcidieno, Leonidas Guibas, Iasonas Kokkinos, Vittorio Murino, Maks Ovsjanikov, Giuseppe Patane, Ivan Sipiran, Michela Spagnuolo, and Jian Sun. 2010. SHREC 2010: Robust feature detection and description benchmark. In Proceedings of the Eurographics 2010 Workshop on 3D Object Retrieval. 79--86. Google ScholarDigital Library
- Benjamin Bustos, Daniel A. Keim, Dietmar Saupe, Tobias Schreck, and Dejan V. Vranić. 2005. Feature-based similarity search in 3D object databases. ACM Computing Surveys 37, 4, 345--387. Google ScholarDigital Library
- Owen Carmichael, Daniel Huber, and Martial Hebert. 1999. Large data sets and confusing scenes in 3-D surface matching and recognition. In Proceedings of the IEEE International Conference on 3D Digital Imaging and Modeling. 358--367. Google ScholarDigital Library
- Frederic Cazals and Marc Pouget. 2005. Estimating differential quantities using polynomial fitting of osculating jets. Computer Aided Geometric Design 22, 2, 121--146. Google ScholarDigital Library
- Chu-Song Chen, Yi-Ping Hung, and Jen-Bo Cheng. 1999. 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. Google ScholarDigital Library
- Hui Chen and Bir Bhanu. 2007. 3D free-form object recognition in range images using local surface patches. Pattern Recognition Letters 28, 10, 1252--1262. Google ScholarDigital Library
- Chi Kin Chow, Hung Tat Tsui, and Tong Lee. 2004. Surface registration using a dynamic genetic algorithm. Pattern Recognition 37, 1, 105--117.Google ScholarCross Ref
- Chin Seng Chua and Ray Jarvis. 1997. Point signatures: A new representation for 3D object recognition. International Journal of Computer Vision 25, 1, 63--85. Google ScholarDigital Library
- Do Hyun Chung, Il Dong Yun, and Sang Uk Lee. 1998. Registration of multiple-range views using the reverse-calibration technique. Pattern Recognition 31, 4, 457--464.Google ScholarCross Ref
- David Cohen-Steiner and Jean-Marie Morvan. 2003. Restricted Delaunay triangulations and normal cycle. In Proceedings of the ACM Annual Symposium on Computational Geometry. 312--321. Google ScholarDigital Library
- Nicu D. Cornea, M. Fatih Demirci, Deborah Silver, Ali Shokoufandeh, Sven J. Dickinson, and Paul B. Kantor. 2005. 3D object retrieval using many-to-many matching of curve skeletons. In Proceedings of the International Conference on Shape Modeling and Applications. IEEE, Los Alamitos, CA, 366--371. Google ScholarDigital Library
- Nicu D. Cornea, Deborah Silver, and Patrick Min. 2007. Curve-skeleton properties, applications, and algorithms. IEEE Transactions on Visualization and Computer Graphics 13, 3, 530--548. Google ScholarDigital Library
- Artur Czumaj, Christian Sohler, and Martin Ziegler. 2000. Property testing in computational geometry. In Algorithms—ESA 2000. Lecture Notes in Computer Science, Vol. 1879. Springer, 155--166. Google ScholarDigital Library
- Tal Darom and Yosi Keller. 2012. Scale-invariant features for 3-D mesh models. IEEE Transactions on Image Processing 21, 5, 2758--2769. Google ScholarDigital Library
- Tamal K. Dey, Joachim Giesen, and Samrat Goswami. 2003. Shape segmentation and matching with flow discretization. In Algorithms and Data Structures. Lecture Notes in Computer Science, Vol. 2748. Springer, 25--36.Google Scholar
- Tamal K. Dey, Kuiyu Li, Chuanjiang Luo, Pawas Ranjan, Issam Safa, and Yusu Wang. 2010. Persistent heat signature for pose-oblivious matching of incomplete models. Computer Graphics Forum 29, 1545--1554.Google ScholarCross Ref
- Yago Díez, Joan Martí, and Joaquim Salvi. 2012. Hierarchical Normal Space Sampling to speed up point cloud coarse matching. Pattern Recognition Letters 33, 2127--2133. Google ScholarDigital Library
- Manfredo P. Do Carmo. 1976. Differential Geometry of Curves and Surfaces. Pearson.Google Scholar
- Michael Donoser and Horst Bischof. 2006. 3D segmentation by maximally stable volumes (MSVs). In Proceedings of the 18th International Conference on Pattern Recognition. 63--66. Google ScholarDigital Library
- Helin Dutagaci, Chun Pan Cheung, and Afzal Godil. 2012. Evaluation of 3D interest point detection techniques via human-generated ground truth. Visual Computer 28, 9, 901--917. Google ScholarDigital Library
- Jacques Feldmar and Nicholas Ayache. 1996. Rigid, affine and locally affine registration of free-form surfaces. International Journal of Computer Vision 18, 2, 99--119. Google ScholarDigital Library
- Natasha Gelfand, Niloy J. Mitra, Leonidas J. Guibas, and Helmut Pottmann. 2005. Robust global registration. In Proceedings of the Eurographics Symposium on Geometry Processing. 197--206. Google ScholarDigital Library
- Armin Gruen and Devrim Akca. 2005. Least squares 3D surface and curve matching. ISPRS Journal of Photogrammetry and Remote Sensing 59, 3, 151--174.Google ScholarCross Ref
- Yulan Guo, Ferdous A. Sohel, Mohammed Bennamoun, Jianwei Wan, and Min Lu. 2013. RoPS: A local feature descriptor for 3D rigid objects based on rotational projection statistics. In Proceedings of the 1st International Conference on Communications, Signal Processing, and Their Applications. 1--6.Google Scholar
- Qi-Xing Huang, Bart Adams, Martin Wicke, and Leonidas J. Guibas. 2008. Non-rigid registration under isometric deformations. Computer Graphics Forum 27, 1449--1457. Google ScholarDigital Library
- Natraj Iyer, Subramaniam Jayanti, Kuiyang Lou, Yagnanarayanan Kalyanaraman, and Karthik Ramani. 2005. Three-dimensional shape searching: State-of-the-art review and future trends. Computer-Aided Design 37, 5, 509--530. Google ScholarDigital Library
- Andrew E. Johnson. 1997. Spin-Images: A Representation for 3-D Surface Matching. Ph.D. Dissertation. Carnegie Mellon University, Pittsburgh, PA.Google Scholar
- Andrew E. Johnson and Martial Hebert. 1999. Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Transactions on Pattern Analysis and Machine Intelligence 21, 5, 433--449. Google ScholarDigital Library
- Kourosh Khoshelham and Sander Oude Elberink. 2012. Accuracy and resolution of Kinect depth data for indoor mapping applications. Sensors 12, 2, 1437--1454.Google ScholarCross Ref
- Hansung Kim and Adrian Hilton. 2013. Evaluation of 3D feature descriptors for multi-modal data registration. In Proceedings of the 2013 International Conference on 3D Vision. 119--126. Google ScholarDigital Library
- Iasonas Kokkinos, Michael M. Bronstein, Roee Litman, and Alexander M. Bronstein. 2012. Intrinsic shape context descriptors for deformable shapes. In Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, Los Alamitos, CA, 159--166. Google ScholarDigital Library
- Marcel Körtgen, Gil-Joo Park, Marcin Novotni, and Reinhard Klein. 2003. 3D shape matching with 3D shape contexts. In Proceedings of the 7th Central European Seminar on Computer Graphics. 3, 5.Google Scholar
- Senthil Kumar, Maha Sallam, and Dmitry Goldgof. 2001. Matching point features under small nonrigid motion. Pattern Recognition 34, 12, 2353--2365. Google ScholarDigital Library
- Xinju Li and Igor Guskov. 2005. Multi-scale features for approximate alignment of point-based surfaces. In Proceedings of the Eurographics Symposium on Geometry Processing. 217. Google ScholarDigital Library
- Zhouhui Lian, Afzal Godil, Benjamin Bustos, Mohamed Daoudi, Jeroen Hermans, Shun Kawamura, Yukinori Kurita, Guillaume Lavoué, Hien Van Nguyen, Ryutarou Ohbuchi, Yuki Ohkita, Yuya Ohishi, Fatih Porikli, Martin Reuter, Ivan Sipiran, Dirk Smeets, Paul Suetens, Hedi Tabia, and Dirk Vandermeulen. 2012. A comparison of methods for non-rigid 3D shape retrieval. Pattern Recognition 46, 1, 449--461. Google ScholarDigital Library
- Yu-Shen Liu and Karthik Ramani. 2009. Robust principal axes determination for point-based shapes using least median of squares. Computer-Aided Design 41, 4, 293--305. Google ScholarDigital Library
- Wen Lik Dennis Lui, Titus Jia Jie Tang, Tom Drummond, and Wai Ho Li. 2012. Robust egomotion estimation using ICP in inverse depth coordinates. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). IEEE, Los Alamitos, CA, 1671--1678.Google Scholar
- Ameesh Makadia, Alexander Patterson, and Kostas Daniilidis. 2006. Fully automatic registration of 3D point clouds. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 1297--1304. Google ScholarDigital Library
- Siddharth Manay, Byung-Woo Hong, Anthony Yezzi, and Stefano Soatto. 2004. Integral invariant signatures. In Proceedings of the European Conference on Computer Vision. 87--99.Google ScholarCross Ref
- Takeshi Masuda. 2001. Generation of geometric model by registration and integration of multiple range images. In Proceedings of the IEEE International Conference on 3D Digital Imaging and Modeling. 254--261.Google ScholarCross Ref
- Takeshi Masuda. 2002. Registration and integration of multiple range images by matching signed distance fields for object shape modeling. Computer Vision and Image Understanding 87, 1, 51--65. Google ScholarDigital Library
- Takeshi Masuda, Katsuhiko Sakaue, and Naokazu Yokoya. 1996. Registration and integration of multiple range images for 3-D model construction. In Proceedings of the IEEE International Conference on Pattern Recognition. 879--883. Google ScholarDigital Library
- Jiri Matas, Ondrej Chum, Martin Urban, and Tomás Pajdla. 2004. Robust wide-baseline stereo from maximally stable extremal regions. Image and Vision Computing 22, 10, 761--767.Google ScholarCross Ref
- Ajmal Mian, Mohammed Bennamoun, and Robyn Owens. 2010. On the repeatability and quality of keypoints for local feature-based 3D object retrieval from cluttered scenes. International Journal of Computer Vision 89, 2, 348--361. Google ScholarDigital Library
- Laurent Najman and Michel Couprie. 2004. Quasilinear algorithm for the component tree. Proceedings of SPIEVision Geometry XII 5300, 1, 98--107.Google Scholar
- Andreas Nuchter, Kai Lingemann, and Joachim Hertzberg. 2007. Cached kd tree search for ICP algorithms. In Proceedings of the 6th International Conference on 3-D Digital Imaging and Modeling. 419--426. Google ScholarDigital Library
- Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. 2012. Functional maps: A flexible representation of maps between shapes. ACM Transactions on Graphics 31, 4, 30. Google ScholarDigital Library
- Maks Ovsjanikov, Quentin Mérigot, Facundo Mémoli, and Leonidas Guibas. 2010. One point isometric matching with the heat kernel. Computer Graphics Forum 29, 1555--1564.Google ScholarCross Ref
- Karl Pearson. 1901. LIII. On lines and planes of closest fit to systems of points in space. London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 2, 11, 559--572.Google ScholarCross Ref
- Ian R. Porteous. 2001. Geometric Differentiation: For the Intelligence of Curves and Surfaces. Cambridge University Press.Google Scholar
- Helmut Pottmann, Johannes Wallner, Qi-Xing Huang, and Yong-Liang Yang. 2009. Integral invariants for robust geometry processing. Computer Aided Geometric Design 26, 1, 37--60. Google ScholarDigital Library
- Dana Ron. 2001. Property testing. Combinatorial Optimization Dordrecht 9, 2, 597--643.Google ScholarCross Ref
- Salvador Ruiz-Correa, Linda G. Shapiro, and Marina Melia. 2001. A new signature-based method for efficient 3-D object recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. I--769.Google ScholarCross Ref
- Szymon Rusinkiewicz and Marc Levoy. 2001. Efficient variants of the ICP algorithm. In Proceedings of the IEEE International Conference on 3D Digital Imaging and Modeling. 145--152.Google ScholarCross Ref
- Radu Bogdan Rusu, Nico Blodow, and Michael Beetz. 2009. Fast point feature histograms (FPFH) for 3D registration. In Proceedings of the IEEE International Conference on Robotics and Automation. 3212--3217. Google ScholarDigital Library
- Radu Bogdan Rusu, Nico Blodow, Zoltan Csaba Marton, and Michael Beetz. 2008. Aligning point cloud views using persistent feature histograms. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. 3384--3391.Google ScholarCross Ref
- Samuele Salti, Federico Tombari, and Luigi Di Stefano. 2011. A performance evaluation of 3D keypoint detectors. In Proceedings of the IEEE International Conference on 3D Imaging, Modeling, Processing, Visualization, and Transmission. 236--243. Google ScholarDigital Library
- Joaquim Salvi, Carles Matabosch, David Fofi, and Josep Forest. 2007. A review of recent range image registration methods with accuracy evaluation. Image and Vision Computing 25, 5, 578--596. Google ScholarDigital Library
- Jose Santamaría, Oscar Cordón, and Sergio Damas. 2011. A comparative study of state-of-the-art evolutionary image registration methods for 3D modeling. Computer Vision and Image Understanding 115, 9, 1340--1354.Google ScholarCross Ref
- Gregory C. Sharp, Sang W. Lee, and David K. Wehe. 2002. ICP registration using invariant features. IEEE Transactions on Pattern Analysis and Machine Intelligence 24, 1, 90--102. Google ScholarDigital Library
- Philip Shilane, Patrick Min, Michael Kazhdan, and Thomas Funkhouser. 2004. The Princeton shape benchmark. In Proceedings of the Conference on Shape Modeling Applications. 167--178. Google ScholarDigital Library
- Ivan Sipiran and Benjamin Bustos. 2011. Harris 3D: A robust extension of the Harris operator for interest point detection on 3D meshes. Visual Computer 27, 11, 963--976. Google ScholarDigital Library
- Jian Sun, Maks Ovsjanikov, and Leonidas Guibas. 2009. A concise and provably informative multi-scale signature based on heat diffusion. Computer Graphics Forum 28, 1383--1392. Google ScholarDigital Library
- Hari Sundar, Deborah Silver, Nikhil Gagvani, and Sven Dickinson. 2003. Skeleton based shape matching and retrieval. In Proceedings of Shape Modeling International, 2003. IEEE, Los Alamitos, CA, 130--139. Google ScholarDigital Library
- Andrea Tagliasacchi, Hao Zhang, and Daniel Cohen-Or. 2009. Curve skeleton extraction from incomplete point cloud. ACM Transactions on Graphics 28, 3, Article No. 71. Google ScholarDigital Library
- Gary Tam, Zhi-Quan Cheng, Yu-Kun Lai, Frank Langbein, Yonghuai Liu, David Marshall, Ralph Martin, Xianfang Sun, and Paul Rosin. 2013. Registration of 3D point clouds and meshes: A survey from rigid to non-rigid. IEEE Transactions on Visualization and Computer Graphics 19, 7, 1199--1217. Google ScholarDigital Library
- Johan W. H. Tangelder and Remco C. Veltkamp. 2004. A survey of content based 3D shape retrieval methods. Multimedia Tools and Applications 39, 3, 441--471. Google ScholarDigital Library
- Jean-Philippe Tarel, Hakan Civi, and David B. Cooper. 1998. Pose estimation of free-form 3D objects without point matching using algebraic surface models. In Proceedings of the IEEE Workshop on Model-Based 3D Image Analysis. 13--21.Google Scholar
- Federico Tombari, Samuele Salti, and Luigi Di Stefano. 2010. Unique signatures of histograms for local surface description. In Proceedings of the European Conference on Computer Vision. 356--369. Google ScholarDigital Library
- Greg Turk and Marc Levoy. 1994. Zippered polygon meshes from range images. In Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques. 311--318. Google ScholarDigital Library
- Oliver Van Kaick, Hao Zhang, Ghassan Hamarneh, and Daniel Cohen-Or. 2011. A survey on shape correspondence. Computer Graphics Forum 30, 1681--1707.Google ScholarCross Ref
- Joris Vanden Wyngaerd and Luc Van Gool. 2002. Automatic crude patch registration: Toward automatic 3D model building. Computer Vision and Image Understanding 87, 1, 8--26. Google ScholarDigital Library
- Simon Winkelbach, Sven Molkenstruck, and Friedrich M. Wahl. 2006. Low-cost laser range scanner and fast surface registration approach. In Proceedings of the 28th Conference on Pattern Recognition. 718--728. Google ScholarDigital Library
- Chen Yang and Gérard Medioni. 1992. Object modelling by registration of multiple range images. Image and Vision Computing 10, 3, 145--155. Google ScholarDigital Library
- Yong-Liang Yang, Yu-Kun Lai, Shi-Min Hu, and Helmut Pottmann. 2006. Robust principal curvatures on multiple scales. In Proceedings of the 4th Eurographics Symposium on Geometry Processing. 223--226. Google ScholarDigital Library
- Tsz-Ho Yu, Oliver J. Woodford, and Roberto Cipolla. 2013. A performance evaluation of volumetric 3D interest point detectors. International Journal of Computer Vision 102, 1--3, 180--197. Google ScholarDigital Library
- Andrei Zaharescu, Edmond Boyer, Kiran Varanasi, and Radu Horaud. 2009. Surface feature detection and description with applications to mesh matching. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 373--380.Google ScholarCross Ref
- Zhiyuan Zhang, Sim Heng Ong, and Kelvin Foong. 2012. Improved spin images for 3D surface matching using signed angles. In Proceedings of the IEEE International Conference on Image Processing. 537--540.Google ScholarCross Ref
- Qian Zheng, Andrei Sharf, Andrea Tagliasacchi, Baoquan Chen, Hao Zhang, Alla Sheffer, and Daniel Cohen-Or. 2010. Consensus skeleton for non-rigid space-time registration. Computer Graphics Forum 29, 635--644.Google ScholarCross Ref
- Yu Zhong. 2009. Intrinsic shape signatures: A shape descriptor for 3D object recognition. In Proceedings of the IEEE International Conference on Computer Vision Workshops. 689--696.Google ScholarCross Ref
Index Terms
- A Qualitative Review on 3D Coarse Registration Methods
Recommendations
A coarse-to-fine algorithm for 3D registration based on wavelet decomposition
This paper introduces a coarse-to-fine algorithm for 3D registration that uses an alternative 3D Shape Representation: CIRCON (Cylindrical Image of Radial CONtours). Two point clouds can be aligned using their corresponding circon images for searching ...
3D registration by using an alternative 3D shape representation
ISCGAV'07: Proceedings of the 7th WSEAS International Conference on Signal Processing, Computational Geometry & Artificial VisionThis paper introduces a surface matching algorithm for 3D registration that uses an alternative 3D Shape Representation: CIRCON (Cylindrical Image of Radial Contours), that both enables the compression of the 3D data, making them more manageable, and ...
Reduction of variance of observations on pelvic structures in CBCT images using novel mean-shift and mutual information based image registration?
ICVGIP '16: Proceedings of the Tenth Indian Conference on Computer Vision, Graphics and Image ProcessingIn this paper, Cone-Beam Computed Tomography(CBCT) image data of colorectal cancer patients are considered for registering standard reference locations of bony structures in pelvic region. A solution is provided in this paper to automatically compute ...
Comments