Automatic Global Registration of 3D Point Clouds for Reverse Engineering and Inspection Processes

Abstract:

Registration of 3D point clouds is one of the most fundamental phases during the process of reverse engineering and most challenging at the same time. This phase consists on matching two or more different point clouds into one data set in order to have them share the same global coordinate system. In this paper we present a new approach for automatic registration of 3D point clouds that uses the genetic algorithm (GA) as a global optimization method. We introduce a trips extraction technique for rough registration, which extracts important geometric information from a point cloud. Another contribution in this paper is the introduction of the Interpenetration Fraction Measure (IFM), which maximizes the number of points that overlap two different point clouds. The algorithm we present also takes advantage of the parallel computing power of today’s multi-core processors, and other techniques for further efficiency. Finally, we present some experimental data with comparisons for analysis and further discussion about the algorithm’s performance.

• Periodical: Applied Mechanics and Materials (Volumes 110-116)
• Pages: 4907-4913
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.110-116.4907
• Online since: October 2011
• Authors: Mariano Imbert, Xiao Xing Li
• Keywords: 3D Data Sets, Inspection, Point Cloud, Registration, Reverse Engineering (RE)

References

[1] P. J. Besl and N. D. McKay, A method for registration of 3-D shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence vol. 14, pp.239-256, (1992).

DOI: 10.1109/34.121791

[2] K. -H. Bae and D. D. Lichti, A method for automated registration of unorganised point clouds , ISPRS Journal of Photogrammetry and Remote Sensing, vol. 63, pp.36-54, 25 July 2007 (2007).

DOI: 10.1016/j.isprsjprs.2007.05.012

[3] Y. Chen and G. Medioni, Object modelling by registration of multiple range images, Image Vision Comput., vol. 10, pp.145-155, (1992).

DOI: 10.1016/0262-8856(92)90066-c

[4] J. Feldmar and N. Ayache, Rigid, affine and locally affine registration of free-form surfaces, International Journal of Computer Vision, vol. 18, pp.99-119, (1996).

DOI: 10.1007/bf00054998

[5] E. Trucco, et al., Robust motion and correspondence of noisy 3-D point sets with missing data, Pattern Recognition Letters, vol. 20, pp.889-898, (1999).

DOI: 10.1016/s0167-8655(99)00055-0

[6] S. Rusinkiewicz and M. Levoy, Efficient variants of the ICP algorithm, in Third International Conference on 3-D Digital Imaging and Modeling, 2001. Proceedings. , Quebec City, Que., Canada, 2001, pp.145-152.

DOI: 10.1109/im.2001.924423

[7] M. A. Rodrigues and Y. Liu, On the representation of rigid body transformations for accurate registration of free-form shapes , Robotics and Autonomous Systems, vol. 39, pp.37-52, (2001).

DOI: 10.1016/s0921-8890(02)00173-2

[8] L. Zhu, et al., Efficient registration for precision inspection of free-form surfaces, International journal of advanced manufacturing technology, vol. 32, pp.505-515, (2007).

DOI: 10.1007/s00170-005-0370-9

[9] T. Zinsser, et al., A refined ICP algorithm for robust 3-D correspondence estimation, in International Conference on Image Processing, 2003. ICIP 2003. Proceedings. 2003, 2003, pp.695-698.

DOI: 10.1109/icip.2003.1246775

[10] Y. Liu, et al., 3D shape matching using collinearity constraint, " in IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA , 04. 2004, 2004, pp.2285-2290.

DOI: 10.1109/robot.2004.1307402

[11] T. Jost and H. Hugli, A multi-resolution ICP with heuristic closest point search for fast and robust 3D registration of range images, in International Conference on 3D Digital Imaging and Modeling, 2003, pp.427-433.

DOI: 10.1109/im.2003.1240278

[12] D. Chetverikov, et al., Robust Euclidean alignment of 3D point sets: the trimmed iterative closest point algorithm , Image and Vision Computing, vol. 23, pp.299-309, 1 March 2005 (2005).

DOI: 10.1016/j.imavis.2004.05.007

[13] D. Chetverikov, et al., The trimmed iterative closest point algorithm, " in Proceedings of the 16 th International Conference on Pattern Recognition (ICPR, 02), 2002, pp.545-548.

[14] C. A. Kapoutsis, et al., Morphological iterative closest point algorithm, Image Processing, IEEE Transactions on, vol. 8, pp.1644-1646, (1999).

DOI: 10.1109/83.799892

[15] A. Makadia, et al., Fully automatic registration of 3D point clouds, presented at the Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 1, (2006).

DOI: 10.1109/cvpr.2006.122

[16] L. Velho, et al., Mathematical Optimization in Computer Graphics and Vision: Morgan Kaufmann, (2008).

[17] P. Venkataraman, Applied Optimization with MATLAB Programming, 1st ed.: Wiley Interscience, (2002).

[18] E. K. P. Chong and S. H. Zak, An Introduction to Optimization, 3th ed.: Wiley-Interscience, (2008).

[19] L. Silva, et al., Robust Range Image Registration Using Genetic Algorithms And The Surface Interpenetration Measure vol. 60: World Scientific Publishing Company, (2005).

[20] L. Silva, et al., Precision range image registration using a robust surface interpenetration measure and enhanced genetic algorithms, IEEE Trans. Pattern Anal. Mach. Intell., vol. 27, pp.762-776, (2005).

DOI: 10.1109/tpami.2005.108

[21] K. Brunnstrom and A. J. Stoddartt, Genetic algorithms for free-form surface matching, " presented at the Proceedings of the International Conference on Pattern Recognition (ICPR , 96) Volume IV-Volume 7472 - Volume 7472, (1996).

DOI: 10.1109/icpr.1996.547653

[22] S. M. Yamany, et al., A new genetic-based technique for matching 3-D curves and surfaces, Pattern recognition, vol. 32, pp.1871-1820, (1999).

DOI: 10.1016/s0031-3203(99)00060-6

[23] J. M. Rouet, et al., Genetic algorithms for a robust 3-D MR-CT registration, IEEE Transactions on Information Technology in Biomedicine, vol. 4, pp.126-136, June 2000 (2000).

DOI: 10.1109/4233.845205

[24] G. Percoco and L. M. Galantucci, Genetic Point Cloud Alignment for Computer Aided Inspection and Reverse Engineering, (2002).

[25] L. M. Galantuccia, et al., An artificial intelligence approach to registration of free-form shapes , CIRP Annals - Manufacturing Technology, vol. 53, pp.139-142 (2004).

DOI: 10.1016/s0007-8506(07)60663-5

[26] C. K. Chow, et al., Surface registration using a dynamic genetic algorithm , Pattern Recognition, vol. 37, pp.105-117, (2003).

[27] E. Lomonosov, et al., Fully automatic, robust and precise alignment of measured 3D surfaces for arbitrary orientations, in 28th Workshop of the Austrian Association for Pattern Recognition, 2004, pp.39-46.

[28] F. L. Seixas, et al., Image registration using genetic algorithms, presented at the Proceedings of the 10th annual conference on Genetic and evolutionary computation, Atlanta, GA, USA, (2008).

DOI: 10.1145/1389095.1389320

[29] C. Robertson and R. B. Fisher, Parallel evolutionary registration of range data, Comput. Vis. Image Underst., vol. 87, pp.39-50, (2002).

[30] B. Cyganek and J. P. Siebert, An Introduction to 3D Computer Vision Techniques and Algorithms: Wiley, (2009).

[31] N. Nikolaidis and I. Pitas, 3-D Image Processing Algorithms: Wiley-Interscience, (2001).

[32] S. Molkenstruck and S. Winkelbach. (2007, David Laserscanner. Available: http: /www. david-laserscanner. com.

[33] P. H. S. Torr and A. Zisserman, MLESAC: a new robust estimator with application to estimating image geometry, Comput. Vis. Image Underst., vol. 78, pp.138-156, (2000).

DOI: 10.1006/cviu.1999.0832