JACIII Vol.20 No.5 pp. 788-802
doi: 10.20965/jaciii.2016.p0788


Evolution Strategy Sampling Consensus for Robust Estimator

Yuichiro Toda and Naoyuki Kubota

Tokyo Metropolitan University
6-6 Asahigaoka, Hino, Tokyo, Japan

May 9, 2016
July 6, 2016
Online released:
September 20, 2016
September 20, 2016
random sampling consensus, evolution strategy, homography estimation

RANdom SAmple Consensus (RANSAC) has been applied to many 3D image processing problems such as homography matrix estimation problems and shape detection from 3D point clouds, and is one of the most popular robust estimator methods. However, RANSAC has a problem related to the trade-off between computational cost and stability of search because RANSAC is based on random sampling. Genetic Algorithm SAmple Consensus (GASAC) based on a population-based multi-point search was proposed in order to improve RANSAC. GASAC can improve the performance of search. However, it is sometimes difficult to maintain the genetic diversity in the search if the large size of outliers is included in a data set. Furthermore, a computational time of GASAC sometimes is slower than that of RANSAC because of calculation of the genetic operators. This paper proposes Evolution Strategy SAmple Consensus (ESSAC) as a new robust estimator. ESSAC is based on Evolution Strategy in order to maintain the genetic diversity. In ESSAC, we apply two heuristic searches to ESSAC. One is a search range control, the other is adaptive/self-adaptive mutation. By applying these heuristic searches, the trade-off between computational speed and search stability can be improved. Finally, this paper shows several experimental results in order to evaluate the effectiveness of the proposed method.

  1. [1] Y. Li, Y. Zhao, S. Wang, and Q. Ji, “Simultaneous Facial Feature Tracking and Facial Expression Recognition,” IEEE Trans. on Image Processing, Vol.22, No.7, pp. 2559-2573, 2013.
  2. [2] M. Yasumoto, J. Hayashi, H. Koshimizu, Y. Niwa, and K. Yamamoto, “A Method of Estimating Gender and Age using Average Face,” IEIC Technical Report, Vol.101, No.422, pp. 1-6, 2001.
  3. [3] J. S. Jang and J. H. Kim, “Fast and Robust Face Detection Using Evolutionary Pruning,” IEEE Trans. on Evolutionary Computation, Vol.12, No.5, pp. 562-571, 2007.
  4. [4] Z. Wu, Q. Ke, J. Sun, and H. Y. Shum, “Scalable Face Image Retrival with Identify-Based Quantization and Multireference Reranking,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.33, No.10, pp. 1844-2001, 2011.
  5. [5] D. MingTsai, I. YungChiang, and Y. HuiTsai “A Shift-Tolerant Dissimilarity Measure for Surface Defect Detection,” IEEE Trans. on Industrial Informatics, Vol.8, No.1, pp. 128-137, 2012.
  6. [6] S. Pellegrini, A. Ess, K. Schindler, and L. van Gool, “You’ll never walk alone: modeling social behavior for multi-target tracking,” Int. Conf. on Computer Vision (ICCV), 2009.
  7. [7] J. Wang, C. Lu, M. Wang, P. Li, S. Yan, and X. Hu, “Robust Face Recognition via Adaptive Sparse Representation,” IEEE Trans. on Cybernetics, Vol.44, No.12, pp. 2368-2378, 2014.
  8. [8] K. Krawiec and B. Bhanu, “Visual Learning by Evolutionary and Coevolutionary Feature Synthesis,” IEEE Trans. on Evolutionary Computation, Vol.11, No.5, pp. 635-650, 2007.
  9. [9] H. Zhang, C. Reardon, and L. E. Parker, “Real-Time Multiple Human Perception With Color-Depth Cameras on a Mobile Robot,” IEEE Trans. on Cybernetics, Vol.43, No.5, pp. 1429-1441, 2013.
  10. [10] J. M. Frahm, P. Fite-Georgel, D. Gallup, T. Johnson, R. Raguram, C. Wu, Y. H. Jen, E. Dunn, B. Clipp, S. Lazebnik, and M. Pollefeys, “Building rome on a cloudless day,” ECCV, pp. 368-381, 2010.
  11. [11] A. Maimone and H. Fuchs, “Encumbrance-free telepresence system with real-time 3d capture and display using commodity depth cameras,” IEEE Int. Symp. on Mixed and Augmented Reality (ISMAR), pp. 137-146, 2011.
  12. [12] H. H. Mousavi, M. Khademi, L. Dodakian, S. C. Cramer, and C. V. Lopes, “A Spatial Augmented Reality Rehab System for Post-Stroke Hand Rehabilitation,” Studies in health technology and informatics, pp. 279-285, 2013.
  13. [13] Microsoft., 2010, [Accessed April 1, 2015].
  14. [14] K. Lai, L. Bo, X. Ren, and D. Fox, “A Large-Scale Hierarchical MultiView RGB-D Object Dataset,” IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 1817-1824 2011.
  15. [15] S. Vidas, P. Moghadam, and M. Bosse,“3D thermal mapping of building interiors using an RGB-D and thermal camera,” IEEE Int. Conf. on Robotics and Automation, 2013.
  16. [16] S. Kim and J. Kim, “Occupancy Mapping and Surface Reconstruction Using Local Gaussian Processes With Kinect Sensors,” IEEE Trans. on Cybernetics, Vol.43, No.5, pp. 1335-1346, 2013.
  17. [17] M. Fischler and R. Bolles, “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography,” Communications of the ACM Vol.24, No.6, pp. 381-395, 1981.
  18. [18] R. Bolles and M. Fischler, “A RANSAC-based approach to model ftting and its application to fnding cylinders in range data,” Proc., IJCAI, pp. 637-643, 1981.
  19. [19] R. Schnabel, R. Wahl, and R. Klein, “Effcient RANSAC for Point-Cloud Shape Detection,” Computer Graphics Forum, Vol.26, No.2, pp. 214-226, 2007.
  20. [20] R. Rusu, Z. Marton, N. Blodow, M. Dolha, and M. Beetz, “Towards 3D Point Cloud Based Object Maps for Household Environments,” Robotics and Autonomous System, Vol.56, pp. 927-941, 2008.
  21. [21] J. Elseberg, D. Borrmann, and A. N”uchter, “Effcient processing of large 3d point clouds,” ICAT 2011 XXIII Int. Symp. on, pp. 1-7, 2011.
  22. [22] G. K. L. Tam, Z. Q. Cheng, Y. K. Lai, F. C. Langbein, Y. Liu, D. Marshall, R. R. Martin, X. F. Sun, and P. L. Rosin, “Registration of 3D Point Clouds and Meshes: A Survey From Rigid to Non-Rigid,” IEEE Trans. on Visualization and Computer Graphics, Vol.19, No.7, pp. 1199-1217, 2013.
  23. [23] J. Han, L. Shao, D. Xu, and J. Shotton, “Enhanced Computer Vision With Microsoft Kinect Sensor: A Review,” IEEE Trans. on Cybernetics, Vol.43, No.5, pp. 1318-1334, 2013.
  24. [24] X. Qian and C. Ye, “NCC-RANSAC: A Fast Plane Extraction Method for 3-D Range Data Segmentation,” IEEE Trans. on Cybernetics, Vol.44, No.12, pp. 2771-2783, 2014.
  25. [25] Choi, Sunglok, Taemin Kim, and Wonpil Yu, “Performance evaluation of RANSAC family,” J. of Computer Vision, Vol.24, No.3 pp. 1-12, 2009.
  26. [26] V. Rodehorst and O. Hellwich, “Genetic Algorithm SAmple Consensus (GASAC) - A Parallel Strategy for Robust Parameter Estimation,” Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition Workshop, CVPRW ’06, pp. 103-110, 2006.
  27. [27] I. Rechenberg, “Evolutionsstrategie: Optimierung technischer systeme nach prinzipien der biologischen evolution,” Stuttgart: FrommannHolzboog Verlag, 1973.
  28. [28] H. P. Schwefel, “Kybernetische evolution als strategie der experimentellen forschung in der strmungstechnik,” Diploma thesis, Technical Univ. of Berlin, 1965.
  29. [29] D. G. Lowe, “Object recognition from local scaleinvariant features,” Proc. of IEEE Int. Conf. on Computer Vision (ICCV), pp. 1150-1157, 1999.
  30. [30] H. Bay, T. Tuytelaars, and L. V. Gool, “Surf: Speeded up robust features,” European Conf. on Computer Vision (ECCV), 2006.
  31. [31] N. Dalal and B. Triggs, “Histograms of Oriented Gradients for Human Detection,” CVPR, pp. 886-893, 2005.
  32. [32] CUDA,, [Accessed May 1, 2016].
  33. [33] SIFT on GPU,˜ccwu/siftgpu/, [Accessed May 1, 2016].
  34. [34] OpenCV,, [Accessed May 1, 2016].
  35. [35] A. Akbarzadeh, J. M. Frahm, P. Mordohai, B. Clipp, C. Engels, D. Gallup, P. Merrell, M. Phelps, S. Sinha, B. Talton, L. Wang, Q. Yang, H. Stewenius, R. Yang, G. Welch, H. Towles, D. Niste’r, and M. Pollefeys, “Towards urban 3D reconstruction from video,” Proc. of the 3rd Int. Symp. on 3D Data Processing, Visualization and Transmission (3DPVT), pp. 1-8, 2006.
  36. [36] K. Konolige and M. Agrawal, “FrameSLAM: From bundle adjustment to real-time visual mapping,” IEEE Trans. on Robotics, Vol.25, No.5, pp. 1066-1077, 2008.
  37. [37] N. Cornelis, B. Leibe, K. Cornelis, and L. V. Gool, “3D Urban Scene Modeling Integrating Recognition and Reconstruction,” Int. J. of Computer Vision, Vol.78, No.2-3, pp. 121-141, 2008.
  38. [38] B. Cyganek and J. P. Siebert, “Introduction to 3D Computer Vision Techniques and Algorithms,” Wiley, John & Sons, Incorporated, 2009.
  39. [39] P. H. S. Torr, “Bayesian model estimation and selection for epipolar geometry and generic manifold fitting,” Int. J. of Computer Vision, Vol.50, No.1, pp. 35-61, 2002.
  40. [40] C. L. Feng and Y. S. Hung, “A robust method for estimating the fundamental matrix,” Proc. the 7th Digital Image Computing: Techniques and Applications, pp. 633-642, 2003.
  41. [41] B. J. Tordoff and D. W. Murray, “Guided-mlesac: Faster image transform estimation by using matching priors,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.27, No.10, pp. 1523-1535, 2005.
  42. [42] O. Chum and J. Matas, “Matching with PROSAC - Progressive Sample Consensus,” Int. Conf. on Computer Vision and Pattern Recognition, pp. 220-226, 2005.
  43. [43] G. Sharp, S. Lee, and D. Wehe, “ICP registration using invariant features,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.24, No.1, pp. 90-102, 2002.
  44. [44] B. Horn, “Closed-Form Solution of Absolute Orientation Using Unit Quaternions,” J. of the Optical Society of America A, Vol.4, No.4, pp. 629-642, 1987.
  45. [45] P. J. Rousseeuw, “Least median of squares regression,” J. of the American Statistical Association, Vol.79, No.388, pp. 871-880, 1984.
  46. [46] F. Vasconcelos, C. Henggeler, and J. P. Barreto, “Adaptive and Hybrid Genetic Approaches for Estimating the Camera Motion from Image Point Correspondences,” ACM Conf. in Genetic and Evolutionary Computing Conf., 2011.
  47. [47] D. B. Fogel, “Evolutionary Computation,” IEEE Press, 1995.
  48. [48] Visual Geometry Group,˜vgg/, [Accessed May 1, 2016].
  49. [49] VASC Image Database,, [Accessed February 1, 2016].

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, IE9,10,11, Opera.

Last updated on Mar. 24, 2017