Recently, genetic algorithm (GA) has been introduced as an effective method to solve the registration problem. It maintains a population of candidate solutions for the problem and evolves by iteratively applying a set of stochastic operators. Accordingly, a key question is how to reduce the population size. In this study, the authors present two techniques for reducing the population size in the GA for registration of partially overlapping point sets. Based on the trimmed iterative closest point algorithm, they introduce a growth operator into the GA. The growth operator, which is also inspired by the biological evolution, can improve the GA efficiency for registration. Furthermore, they present a technique called centre alignment to confirm the value range of all the registration parameters, which can reduce the search space and allow the well-designed GA to directly solve the registration problem. Experimental results carried out with the m-dimensional point sets illustrate its advantages over previous approaches.

References

1. 1)
  - 30. Phillips, J.M., Ran, L., Tomasi, C.: ‘Outlier robust ICP for minimizing fractional RMSD’. Proc. of the Sixth Int. Conf. on 3-D Digital Imaging and Modeling (3DIM), 2007, pp. 427–434.
2. 2)
  - 28. Lenac, K., Mumolo, E., Nolich, M.: ‘Fast genetic scan matching using corresponding point measurements in mobile robotics’, Appl. Evol. Comput., Lect. Notes Comput. Sci., 2007, 4448, pp. 375–382 (doi: 10.1007/978-3-540-71805-5_41).
3. 3)
  - 2. Megyesi, Z., Kos, G., Chetverikov, D.: ‘Dense 3D reconstruction from images by normal aided matching’, Mach. Graph. Vis., 2006, 15, (1), pp. 3–28.
4. 4)
  - 35. Nuchter, A., Lingemann, K., Hertzberg, J.: ‘Cached k-d tree search for ICP algorithms’. Proc. Sixth Int. Conf. on 3D Digital Imaging and Modeling (3DIM), 2007, pp. 419–426.
5. 5)
  - 31. Du, S.Y., Zhu, J.H., Zheng, N.N., Liu, Y.H., Li, C.: ‘A robust iterative closest point algorithm for registration of point sets with outliers’, Opt. Eng., 2011, 50, (8), pp. 1–4 (doi: 10.1117/1.3607960).
6. 6)
  - J. Minguez , L. Montesano , F. Lamiraux . Metric-based iterative closest point scan matching for sensor displacement estimation. IEEE Trans. Robot. , 5 , 1047 - 1054
7. 7)
  - 20. Brunnstrom, K., Stoddart, A.: ‘Genetic algorithms for free-form surface matching’. Proc. Int. Conf. on Pattern Recognition (ICPR), 1996, pp. 689–693.
8. 8)
  - 22. Robertson, C., Fisher, R.: ‘Parallel evolutionary registration of range data’, Comput. Vis. Image Underst., 2002, 87, (1–3), pp. 39–55 (doi: 10.1006/cviu.2002.0981).
9. 9)
  - A.F. Abate , M. Nappi , D. Riccio , G. Sabatino . 2D and 3D face recognition: a survey. Pattern Recognit. , 1885 - 1906
10. 10)
  - 25. Silva, L., Bellon, Q., Boyer, K.: ‘Enhanced, robust genetic algorithms for multiview range image registration’. Proc. the Fourth Int. Conf. on 3D Digital Imaging and Modeling (3DIM), 2003, pp. 268–275.
11. 11)
  - D. Chetverikov , D. Stepanov , P. Krsek . Robust Euclidean alignment of 3D point sets: the trimmed iterative closest point algorithm. Image Vis. Comput. , 3 , 299 - 309
12. 12)
  - 17. Zhu, J.H., Du, S.Y., Yuan, Z.J., Liu, Y.H., Ma, L.: ‘Robust affine iterative closest point algorithm with bidirectional distance’, IET Comput. Vis., 2012, 6, (3), pp. 252–261 (doi: 10.1049/iet-cvi.2011.0178).
13. 13)
  - 12. Rusinkiewicz, S., Levoy, M.: ‘Efficient variants of the ICP algorithm’. Proc. of Int. Conf. 3D Digital Imaging and Modeling (3DIM), 2001, pp. 145–152.
14. 14)
  - 27. Chow, C., Tsui, H., Lee, T.: ‘Surface registration using a dynamic genetic algorithm’, Pattern Recognit., 2004, 37, (1), pp. 105–117 (doi: 10.1016/S0031-3203(03)00222-X).
15. 15)
  - 18. Melanie, M.: ‘An introduction to genetic algorithms’ (The MIT Press, Cambridge, 1999).
16. 16)
  - 21. Yamany, S., Ahmed, M., Farag, A.: ‘A new genetic-based technique for matching 3D curves and surfaces’, Pattern Recognit., 1999, 32, (4), pp. 1817–1820 (doi: 10.1016/S0031-3203(99)00060-6).
17. 17)
  - 19. Jacq, J., Roux, C.: ‘Registration of 3-D images by genetic optimization’, Pattern Recognit. Lett., 1995, 16, (8), pp. 823–841 (doi: 10.1016/0167-8655(95)00051-H).
18. 18)
  - 24. Olague, G., Hernandez, B., Dunn, E.: ‘Hybrid evolutionary ridge regression approach for high-accurate corner extraction’. Proc. of IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2003, pp. 744–749.
19. 19)
  - P.J. Besl , N.D. McKay . A method for registration of 3D shapes. IEEE Trans. Pattern Anal. Mach. Intell. , 2 , 239 - 256
20. 20)
  - 38. Latecki, L.J., Lakamper, R., Eckhardt, R.: ‘Shape descriptors for non-rigid shapes with a single closed contour’. Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2000, pp. 424–429.
21. 21)
  - 3. Pooja, A., Govindu, V.M.: ‘A multi-view extension of the ICP algorithm’. Proc. of Indian Conf. on Graphics, Vision and Image Processing (ICVGIP), 2010.
22. 22)
  - I. Kakadiaris , G. Passalis , G. Toderici , N. Murtuza , Y. Lu , T. Theoharis . Three-dimensional face recognition in the presence of facial expressions: An annotated deformable model approach. IEEE Trans. Pattern Anal. Mach. Intell. , 4 , 640 - 649
23. 23)
  - 10. Jin, T., Kuang, J.Y.: ‘A 3-D point sets registration method in reverse engineering’, Comput. Ind. Eng., 2007, 53, (2), pp. 272–276.
24. 24)
  - L. Silva , O.R.P. Bellon , K.L. Boyer . Precision range image registration using a robust surface interpenetration measure and enhanced genetic algorithms. IEEE Trans. Pattern Anal Mach. Intell. , 5 , 762 - 776
25. 25)
  - 37. Nuchter, A., Elseberg, J., Schneider, P., Paulus, D.: ‘Study of parameterizations for the rigid body transformations of the scan registration problem’, Comput. Vis. Image Underst., 2010, 114, (8), pp. 963–980 (doi: 10.1016/j.cviu.2010.03.007).
26. 26)
  - 36. Hwang, Y., Han, B., Ahn, H.K.: ‘A fast nearest neighbor search algorithm by nonlinear embedding’. Proc. of Int. Conf. on Computer Vision and Pattern Recognition (CVPR), 2012, pp. 3053–3060.
27. 27)
  - A.W. Fitzgibbon . Robust registration of 2D and 3D point sets. Image Vis. Comput. , 1145 - 1153
28. 28)
  - C.B. Barber . The Quickhull algorithm for convex hulls. ACM Trans. Math. Softw. , 4 , 469 - 483
29. 29)
  - S. Ying , J. Peng , S. Du , H. Qiao . A scale stretch method based on ICP for 3D data registration. IEEE Trans. Autom. Sci. Eng. , 3 , 559 - 565
30. 30)
  - 32. Lomonosov, E., Chetverikov, D., Ekart, A.: ‘Pre-registration of arbitrarily oriented 3D surfaces using a genetic algorithm’, Pattern Recognit. Lett., 2006, 27, (11), pp. 1201–1208 (doi: 10.1016/j.patrec.2005.07.018).
31. 31)
  - 14. Granger, S., Pennec, X.: ‘Multi-scale EM-ICP a fast and robust approach for surface registration’. Proc. of European Conf. on Computer Vision (ECCV), 2002, pp. 418–432.
32. 32)
  - A. Almhdie , C. Leger , M. Deriche , R. Ledee . 3D registration using a new implementation of the ICP algorithm based on a comprehensive lookup matrix: application to medical imaging. Pattern Recognit. Lett. , 12 , 1523 - 1533
33. 33)
  - 8. Carpin, S.: ‘Fast and accurate map merging for multi-robot systems’, Auton. Robots, 2008, 25, (3), pp. 305–316 (doi: 10.1007/s10514-008-9097-4).
34. 34)
  - G.C. Sharp , S.W. Lee , D.K. Wehe . ICP registration using invariant features. IEEE Trans. Pattern Anal. Mach. Intell. , 1 , 90 - 102
35. 35)
  - 23. Salomon, M., Perrin, G., Heitz, F.: ‘Differential evolution for medical image registration’. Proc. of Int. Conf. on Artificial Intell., 2001, pp. 201–207.
36. 36)
  - K. Lu , A.K. Jain , D. Colbry . Matching 2.5D face scans to 3D models. IEEE Trans. Pattern Anal. Mach. Intell. , 1 , 31 - 43
37. 37)
  - 1. Robert, B., Marc, S., Herve, G., Denis, L.: ‘Towards a general multi-view registration technique’, IEEE Trans. Pattern Anal. Mach. Intell., 1996, 18, (5), pp. 540–547 (doi: 10.1109/34.494643).
38. 38)
  - 34. Greenspan, M., Yurick, M.: ‘Approximate k-d tree search for efficient ICP’. Proc. of the Fourth Int. Conf. on 3-D Digital Imaging and Modeling (3DIM), 2003, pp. 419–426.

Robust registration of partially overlapping point sets via genetic algorithm with growth operator

References

Related content