Abstract
Different tasks in forensics require the use of 3D models of forensic objects (skulls, bones, corpses, etc.) captured by 3D range scanners. Since a whole object cannot be completely scanned in a single image using a range scanner, multiple acquisitions from different views are needed to supply the information to construct the 3D model by a range image registration method. There is an increasing interest in adopting evolutionary algorithms as the optimization technique for image registration methods. However, the image registration community tends to separate global and local searches in two different stages, named sequential hybridization approach, which is opposite to the scheme adopted by the memetic framework. In this work, we aim to analyze the capabilities of memetic algorithms (Moscato in On evolution, search, optimization, genetic algorithms and martial arts: towards memeticalgorithms. Report 826, Caltech Concurrent Computation Program, Pasadena, 1989) for tackling a really complex and challenging real-world problem as the 3D reconstruction of forensic objects. Our intention is threefold: firstly, designing new memetic-based methods for tackling a real-world problem and subsequently carrying out a performance and behavioral analysis of the results; secondly, comparing their performance with the one achieved by other methods based on the classical sequential hybridization approach; and thirdly, concluding the experimental study by highlighting the outcomes achieved by the best method in tackling the real-world problem. Several real-world 3D reconstruction problems from the Physical Anthropology Lab at the University of Granada, Spain, were used to support the evaluation study.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bäck T, Fogel DB, Michalewicz Z (1997) Handbook of Evolutionary Computation. IOP Publishing Ltd/Oxford University Press, Bristol/Oxford
Ballerini L, Cordon O, Damas S, Santamaria J, Aleman I, Botella M (2007) Craniofacial superimposition in forensic identification using genetic algorithms. In: IEEE International Workshop on Computational Forensics (IWCF 2007), Manchester, pp 429–434
Besl PJ, McKay ND (1992) A method for registration of 3D shapes. IEEE Trans Pattern Anal Mach Intell 14: 239–256
Beyer HG, Deb K (2001) On self-adaptive features in real-parameter evolutionary algorithms. IEEE Trans Evol Comput 5: 250–270
Cordón O, Damas S, Martí R, Santamaría J (2008) Scatter search for the 3D point matching problem in image registration. INFORMS J Comput 20(1): 55–68. doi:10.1287/ijoc.1060.0216
Cordón O, Damas S, Santamaría J (2006a) A fast and accurate approach for 3D image registration using the scatter search evolutionary algorithm. Pattern Recognit Lett 27(11): 1191–1200
Cordón O, Damas S, Santamaría J (2006b) Feature-based image registration by means of the CHC evolutionary algorithm. Image Vis Comput 22: 525–533
Cordón O, Damas S, Santamaría J (2007) A practical review on the applicability of different EAs to 3D feature-based registration. In: Cagnoni S, Lutton E, Olague G (eds) Genetic and evolutionary computation in image processing and computer vision. EURASIP Book Series on SP&C, pp 247–269
Costa D, Hertz A, Dubuis O (1995) Embedding of a sequential algorithm within an evolutionary algorithm for coloring problems in graphs. J Heuristics 1: 105–128
De Falco I, Della Cioppa A, Maisto D, Tarantino E (2008) Differential Evolution as a viable tool for satellite image registration. Appl Soft Comput (in press)
Deb K, Joshi D (2002) A computationally efficient evolutionary algorithm for real-parameter optimization. Evol Comput 10(4): 371–395
Dru F, Wachowiak MP, Peters TM (2006) An ITK framework for deterministic global optimization for medical image registration. In: Reinhardt JM, Pluim JPW (eds) SPIE, medical imaging 2006: image processing, pp 1–12
Eshelman LJ (1991) The CHC adaptive search algorithm: how to safe search when engaging in non traditional genetic recombination. In: Rawlins GJE (eds) Foundations of genetic algorithms 1. Morgan Kaufmann, San Mateo, EEUU, pp 265–283
Eshelman LJ (1993) Real-coded genetic algorithms and interval schemata. In: Whitley LD (eds) Foundations of Genetic Algorithms 2. Morgan Kaufmann, San Mateo, EEUU, pp 187–202
Fitzpatrick J, Grefenstette J, Gucht D (1984) Image registration by genetic search. In: IEEE Southeast conference. EEUU, Louisville, pp 460–464
Glover F (1977) Heuristic for integer programming using surrogate constraints. Decision Sci 8: 156–166
Hart WE (1994) Adaptive global optimization with local search. PhD Thesis, University of California, San Diego
Herrera F, Lozano M, Molina D (2005) Continuous scatter search: an analysis of the integration of some combination methods and improvement strategies. Eur J Oper Res 169(2): 450–476
Ikeuchi K, Sato Y (2001) Modeling from Reality. Kluwer
Iscan M (1993) Introduction to techniques for photographic comparison. In: Iscan M, Helmer R (eds) Forensic analysis of the skull: craniofacial analysis, reconstruction, and identification. Wiley Liss, New York, pp 57–70
Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flow shop scheduling. IEEE Trans Evol Comput 7(2): 204–223
Jenkinson M, Smith S (2001) A global optimisation method for robust affine registration of brain images. Med Image Anal 5(2): 143–156
Krasnogor N, Smith J (2000) A memetic algorithm with self-adaptive local search: Tsp as a case study. In: Genetic and evolutionary computation conference (GECCO’05), pp 987–994
Krasnogor N, Smith J (2005) A tutorial for competent memetic algorithms: model, taxonomy and design issues. IEEE Trans Evol Comput 9(5): 474–488
Laguna M, Martí R (2003) Scatter search: methodology and implementations in C. Kluwer, Boston
Lehmann E (1975) Nonparametric statistical methods based on ranks. McGraw-Hill, New York
Lozano M, Herrera F, Krasnogor N, Molina D (2004) Real-coded memetic algorithms with crossover hill-climbing. Evol Comput 12(3): 273–302
Maes F, Vandermeulen D, Suetens P (1999) Comparative evaluation of multiresolution optimization strategies for image registration by maximization of mutual information. Med Image Anal 3(4): 373–386
Merz P, Freisleben B (1999) A comparison of memetic algorithms, tabu search, and ant colonies for the quadratic assignment problem. In: Angeline PJ, Michalewicz Z, Schoenauer M, Yao X, Zalzala A (eds) Proceedings of the congress on evolutionary computation, vol 3. Mayflower Hotel, Washington DC, IEEE Press, Piscataway, pp 2063–2070
Moscato P (1989) On evolution, search, optimization, genetic algorithms and martial arts: towards memeticalgorithms. Report 826, Caltech Concurrent Computation Program, Pasadena
Noman N, Iba H (2005) Enhancing differential evolution performance with local search for high dimensional function optimization. In: Genetic and evolutionary computation conference (GECCO’05), ACM, New York, pp 967–974
Ong YS, Lim M, Zhu N, Wong K (2006) Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst Man Cybern B 36(1): 141–152
Powell M (1964) An efficient method for finding the minimum of a function of several variables without calculating derivatives. Comput J 7: 155–162
Press WH, Teukolsky SA, Vetterling WT, Flannery BP (1999) Numerical recipes in C: the art of scientific computing. Cambridge University Press, Cambridge
Price K (1999) An introduction to differential evolution. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization. McGraw-Hill, Cambridge, pp 79–108
Salomon M, Perrin G-R, Heitz F (2001) Differential evolution for medical image registration. In: Arabnia H (eds) International conference on artificial intelligence IC-AI’2001, vol 2. CSREA Press, Las Vegas, pp 123–129
Santamaría J, Cordón O, Damas S, Alemán I, Botella M (2007) A Scatter Search-based technique for pair-wise 3D range image registration in forensic anthropology. Soft Comput 11: 819–828
Satoh MYH, Kobayashi S (1996) Minimal generation Gap model for GAs considering both exploration and exploitation. In: Methodologies for the conception. Design and Application of Intelligent Systems (IIZUKA’96), pp 494–497
Shoemake K (1985) Animating rotation with quaternion curves. In: ACM SIGGRAPH. San Francisco, July 22–26, pp 245–254
Solis FJ, Wets RJB (1981) Minimization by random search techniques. Math Oper Res 6: 19–30
Storn R (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Global Optim 11: 341–359
Tang J, Lim M, Ong YS (2007) Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput 11(9): 873–888
Telenczuk B, Ledesma MJ, Velazquez JA, Sorzano COS, Carazo JM, Santos A (2006) Molecular image registration using mutual information and differential evolution optimization. In: IEEE international symposium on biomedical imaging: macro to nano, pp 844–847
Whitley D, Garrett D, Watson JP (2003) Quad search and hybrid genetic algorithms. In: Genetic and evolutionary computation conference (GECCO’03), ACM, New York, pp 1469–1480
Wolpert DH, Macready WG (1996) No free lunch theorems for search. Technical Report SFI-TR-95-02-010, The Santa Fe Insititute
Xu X, Dony RD (2004) Differential evolution with powell’s direction set method in medical image registration. In: IEEE international symposium on biomedical imaging: macro to nano, pp 732–735
Yamany SM, Ahmed MN, Farag AA (1999) A new genetic-based technique for matching 3D curves and surfaces. Pattern Recognit 32: 1817–1820
Yao J, Goh KL (2006) A refined algorithm for multisensor image registration based on pixel migration. IEEE Trans Image Process 15(7): 1839–1847
Yoshizawa S, Belyaev A, Seidel HP (2005) Fast and robust detection of crest lines on meshes. In: SPM ’05: proceedings of the 2005 ACM symposium on solid and physical modeling. EEUU, ACM Press, New York, pp 227–232
Zhang Z (1994) Iterative point matching for registration of free-form curves and surfaces. Int J Comput Vis 13(2): 119–152
Zhou Z, Ong YS, Lim M, Lee B (2007) Memetic algorithm using multi-surrogates for computationally expensive optimization problems. Soft Comput 11(10): 957–971
Zhu YM, Cochoff SM (2002) Influence of implementation parameters on registration of MR and SPECT brain images by maximization of mutual information. J Nuclear Med 43(2): 160–166
Zhu Z, Ong YS, Dash M (2007) Wrapper-filter feature selection algorithm using a memetic framework. IEEE Trans Syst Man Cybern B 37(1): 70–76
Zitová B, Flusser J (2003) Image registration methods: a survey. Image Vis Comput 21: 977–1000
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was partially supported by the Spain’s Ministerio de Educación y Ciencia (ref. TIN2006-00829) and by the Andalusian Dpto. de Innovación, Ciencia y Empresa (ref. TIC1619), both including EDRF fundings.
Rights and permissions
About this article
Cite this article
Santamaría, J., Cordón, O., Damas, S. et al. Performance evaluation of memetic approaches in 3D reconstruction of forensic objects. Soft Comput 13, 883–904 (2009). https://doi.org/10.1007/s00500-008-0351-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-008-0351-7