Login | Register

V4PCS: Volumetric 4PCS Algorithm for Global Registration


V4PCS: Volumetric 4PCS Algorithm for Global Registration

Huang, Jida and Kwok, Tsz Ho ORCID: https://orcid.org/0000-0001-7240-1426 (2017) V4PCS: Volumetric 4PCS Algorithm for Global Registration. Journal Of Mechanical Design, 139 (11). p. 111403.

[thumbnail of JMD17_V4PCS.pdf]
Text (application/pdf)
JMD17_V4PCS.pdf - Accepted Version
Available under License Spectrum Terms of Access.

Official URL: http://doi.org/10.1115/1.4037477


With the advances in three-dimensional (3D) scanning and sensing technologies, massive human-related data are now available and create many applications in data-driven design. Similarity identification is one of basic problems in data-driven design and can facilitate many engineering applications and product paradigm such as quality control and mass customization. Therefore, reusing information can create unprecedented opportunities in advancing the theory, method, and practice of product design. To enable information reuse, different models have to be aligned so that their similarity can be identified. This alignment is commonly known as the global registration that finds an optimal rigid transformation to align two 3D shapes (scene and model) without any assumptions on their initial positions. The Super 4-Points Congruent Sets (S4PCS) is a popular algorithm used for this shape registration. While S4PCS performs the registration using a set of 4 coplanar points, we find that incorporating the volumetric information of the models can improve the robustness and the efficiency of the algorithm, which are particularly important for mass customization. In this paper, we propose a novel algorithm, Volumetric 4PCS (V4PCS), to extend the 4 coplanar points to non-coplanar ones for global registration, and theoretically demonstrate the computational complexity is significantly reduced. Experimental tests are conducted on a number of models such as tooth aligner and hearing aid to compare with S4PCS. The experimental results show that the proposed V4PCS can achieve a maximum of 20 times speedup and can successfully compute the valid transformation with very limited number of sample points. An application of the proposed method in mass customization is also investigated.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Mechanical, Industrial and Aerospace Engineering
Item Type:Article
Authors:Huang, Jida and Kwok, Tsz Ho
Journal or Publication:Journal Of Mechanical Design
Date:2 October 2017
  • Natural Sciences & Engineering Research Council of Canada
Digital Object Identifier (DOI):10.1115/1.4037477
ID Code:983469
Deposited By: Tsz Ho Kwok
Deposited On:08 Feb 2018 14:20
Last Modified:02 Oct 2018 00:00


1 Kwok, T.-H. , Ye, H. , Chen, Y. , Zhou, C. , and Xu, W. , 2016, “ Mass Customization: Reuse of Digital Slicing for Additive Manufacturing,” ASME Paper No. DETC2016-60140.

2 Besl, P. J. , and McKay, N. D. , 1992, “ A Method for Registration of 3-D Shapes.pdf,” IEEE Trans. Pattern Anal. Mach. Intell., 14(2), pp. 239–256.

3 Aiger, D. , Mitra, N. J. , and Cohen-Or, D. , 2008, “ 4-Points Congruent Sets for Robust Pairwise Surface Registration,” ACM SIGGRAPH, Los Angeles, CA, Aug. 11–15, Paper No. 85.

4 Mellado, N. , Aiger, D. , and Mitra, N. J. , 2014, “ Super 4PCS Fast Global Pointcloud Registration Via Smart Indexing,” Comput. Graphics Forum, 33(5), pp. 205–215.

5 Kwok, T.-H. , Yeung, K.-Y. , and Wang, C. C. L. , 2014, “ Volumetric Template Fitting for Human Body Reconstruction From Incomplete Data,” J. Manuf. Syst., 33(4), pp. 678–689.

6 Salvi, J. , Matabosch, C. , Fofi, D. , and Forest, J. , 2007, “ A Review of Recent Range Image Registration Methods With Accuracy Evaluation,” Image Vision Comput., 25(5), pp. 578–596.

7 Rusinkiewicz, S. , and Levoy, M. , 2001, “ Efficient Variants of the ICP Algorithm,” IEEE Third International Conference on 3-D Digital Imaging and Modeling, Quebec City, QC, Canada, May 28–June 1, pp. 145–152.

8 Bouaziz, S. , Tagliasacchi, A. , and Pauly, M. , 2013, “ Sparse Iterative Closest Point,” Comput. Graphics Forum, 32(5), pp. 113–123.

9 Fitzgibbon, A. W. , 2003, “ Robust Registration of 2D and 3D Point Sets,” Image Vision Comput., 21(13), pp. 1145–1153.

10 Gelfand, N. , Mitra, N. J. , Guibas, L. J. , and Pottmann, H. , 2005, “ Robust Global Registration,” Third Eurographics Symposium on Geometry Processing (SCP), Vienna, Austria, July 4–6, Paper No. 197.

11 Enqvist, O. , Josephson, K. , and Kahl, F. , 2009, “ Optimal Correspondences From Pairwise Constraints,” IEEE 12th International Conference on Computer Vision (ICCV), Kyoto, Japan, Sept. 29–Oct. 2, pp. 1295–1302.

12 Hartley, R. I. , and Kahl, F. , 2007, “ Global Optimization Through Searching Rotation Space and Optimal Estimation of the Essential Matrix,” IEEE 11th International Conference on Computer Vision (ICCV), Rio de Janeiro, Brazil, Oct. 14–21, pp. 1–8.

13 Fischler, M. A. , and Bolles, R. C. , 1981, “ Random Sample Consensus: A Paradigm for Model Fitting With Applications to Image Analysis and Automated Cartography,” Commun. ACM, 24(6), pp. 381–395.

14 Irani, S. , and Raghavan, P. , 1996, “ Combinatorial and Experimental Results for Randomized Point Matching Algorithms,” 12th Annual Symposium on Computational Geometry (SCG), Philadelphia, PA, May 24–26, pp. 68–77.

15 Chen, C.-S. , Hung, Y.-P. , and Cheng, J.-B. , 1999, “ RANSAC-Based DARCES: A New Approach to Fast Automatic Registration of Partially Overlapping Range Images,” IEEE Trans. Pattern Anal. Mach. Intell., 21(11), pp. 1229–1234.

16 Drost, B. , Ulrich, M. , Navab, N. , and Ilic, S. , 2010, “ Model Globally, Match Locally: Efficient and Robust 3D Object Recognition,” IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, CA, June 13–18, pp. 998–1005.

17 Osada, R. , Funkhouser, T. , Chazelle, B. , and Dobkin, D. , 2001, “ Matching 3D Models With Shape Distribution,” International Conference on Shape Modeling and Applications (SMA), Genova, Italy, May 7–11, pp. 154–166.

18 Guo, Y. , Bennamoun, M. , Sohel, F. , Lu, M. , Wan, J. , and Kwok, N. M. , 2016, “ A Comprehensive Performance Evaluation of 3D Local Feature Descriptors,” Int. J. Comput. Vis., 116(1), pp. 66–89.

19 Sun, J. , Ovsjanikov, M. , and Guibas, L. , 2009, “ A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion,” Comput. Graphics Forum, 28(5), pp. 1383–1392.

20 Tombari, F. , Salti, S. , and Di Stefano, L. , 2010, “ Unique Shape Context for 3D Data Description,” ACM Workshop on 3D Object Retrieval (3DOR), Firenze, Italy, Oct. 25–29, pp. 57–62.

21 Guo, Y. , Sohel, F. , Bennamoun, M. , Lu, M. , and Wan, J. , 2013, “ Rotational Projection Statistics for 3D Local Surface Description and Object Recognition,” Int. J. Comput. Vis., 105(1), pp. 63–86.

22 Rusu, R. B. , Blodow, N. , Marton, Z. C. , and Beetz, M. , 2008, “ Aligning Point Cloud Views Using Persistent Feature Histograms,” IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Nice, France, Sept. 22–26, pp. 3384–3391.

23 Rusu, R. B. , Blodow, N. , and Beetz, M. , 2009, “ Fast Point Feature Histograms (FPFH) for 3D Registration,” IEEE International Conference on Robotics and Automation (ICRA), Kobe, Japan, May 12–17, pp. 3212–3217.

24 Salti, S. , Tombari, F. , and Di Stefano, L. , 2014, “ SHOT: Unique Signatures of Histograms for Surface and Texture Description,” Comput. Vision Image Understanding, 125, pp. 251–264.

25 Papazov, C. , and Burschka, D. , 2011, “ An Efficient RANSAC for 3D Object Recognition in Noisy and Occluded Scenes,” Asian Conference on Computer Vision (Lecture Notes in Computer Science), Vol. 6492, Springer, Berlin, pp. 135–148.

26 Ballard, D. H. , 1981, “ Generalizing the Hough Transform to Detect Arbitrary Shapes,” Pattern Recognit., 13(2), pp. 111–122.

27 Lamdan, Y. , and Wolfson, H. J. , 1988, “ Geometric Hashing: A General and Efficient Model-Based Recognition Scheme,” Second International Conference on Computer Vision (CCV), Tampa, FL, Dec. 5–8, pp. 238–249.

28 Mian, A. S. , Bennamoun, M. , and Owens, R. , 2006, “ Three-Dimensional Model-Based Object Recognition and Segmentation in Cluttered Scenes,” IEEE Trans. Pattern Anal. Mach. Intell., 28(10), pp. 1584–1601.

29 Mohamad, M. , Ahmed, M. T. , Rappaport, D. , and Greenspan, M. , 2015, “ Super Generalized 4PCS for 3D Registration,” International Conference on 3D Vision (3DV), Lyon, France, Oct. 19–25, pp. 598–606.
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top