Using three-dimensional scans of human faces has become an emerging technique in studies of human variation, where the quantitative assessment of facial similarity complements the measurement of other somatic traits. While the algorithms for automated registration (geometrical alignment) and similarity measurement of two facial scans are well-known and used in practice, their direct application for batch processing is limited due to computational requirements. The batch N:N analysis, where all pairs of scans in a dataset must be mutually registered and compared, introduces quadratic complexity with computation times reaching hours even for relatively small datasets, making it practically unusable. This paper presents a rapid and accurate approach with nearly linear time complexity. Our solution utilizes properties of facial scan geometry to optimize individual steps. Moreover, the algorithm deals with possible holes and other artifacts in polygonal meshes automatically. Experiments demonstrate that the proposed solution is very fast and sufficiently accurate compared to a precise quadratic-time baseline approach.

Faculty of Informatics Masaryk University Brno Czech Republic

Faculty of Science Masaryk University Brno Czech Republic

Zobrazit více v PubMed

Pilloud MA, Hefner JT. Biological distance analysis: forensic and bioarchaeological perspectives. Academic Press; 2016.

Broca P. Instructions craniologiques et craniometriques. Mem de la Soc Anthrop de Paris. 1875;2:1–203.

Urbanová P, Ross AH. Advanced methods in 3-D craniofacial morphological analysis. Biological Distance Analysis. Elsevier; 2016. p. 61–90.

Ross AH, Juarez CA, Urbanová P. Complexity of assessing migrant death place of origin. Biological Distance Analysis. Elsevier; 2016. p. 265–83.

Urbanová P, Ross AH, Jurda M, Nogueira M-I. Testing the reliability of software tools in sex and ancestry estimation in a multi-ancestral Brazilian sample. Leg Med (Tokyo). 2014;16(5):264–73. doi: 10.1016/j.legalmed.2014.06.002 PubMed DOI

Sokal RR, Uytterschaut H, Rösing FW, Schwidetzky I. A classification of European skulls from three time periods. Am J Phys Anthropol. 1987;74(1):1–20. doi: 10.1002/ajpa.1330740102 PubMed DOI

Sokal RR, Uytterschaut H. Cranial variation in European populations: a spatial autocorrelation study at three time periods. Am J Phys Anthropol. 1987;74(1):21–38. doi: 10.1002/ajpa.1330740103 PubMed DOI

Eliasova H, Dostalova T, Urbanova P. A comparison of the precision of 3D images of facial tissues from the forensic point of view. Forensic Imaging. 2022;28:200471. doi: 10.1016/j.fri.2021.200471 DOI

Atsuchi M, Tsuji A, Usumoto Y, Yoshino M, Ikeda N. Assessment of some problematic factors in facial image identification using a 2D/3D superimposition technique. Leg Med (Tokyo). 2013;15(5):244–8. doi: 10.1016/j.legalmed.2013.06.002 PubMed DOI

Aeria G, Claes P, Vandermeulen D, Clement JG. Targeting specific facial variation for different identification tasks. Forens Sci Int. 2010;201(1–3):118–24. doi: 10.1016/j.forsciint.2010.03.005 PubMed DOI

Zhou S, Xiao S. 3D face recognition: a survey. Hum-Centric Comput Inf Sci. 2018;8(1):1–27.

Li M, Huang B, Tian G. A comprehensive survey on 3D face recognition methods. Eng Appl Artif Intell. 2022;110:104669.

Goodall C. Procrustes methods in the statistical analysis of shape. J Roy Statist Soc: Ser B (Methodol). 1991;53(2):285–321.

Porter G, Doran G. An anatomical and photographic technique for forensic facial identification. Forens Sci Int. 2000;114(2):97–105. doi: 10.1016/s0379-0738(00)00290-5 PubMed DOI

Ferková Z. Multimodal landmark detection for anthropology. Brno: Masaryk University, Faculty of Informatics; 2021.

Vezzetti E, Marcolin F, Tornincasa S, Ulrich L, Dagnes N. 3D geometry-based automatic landmark localization in presence of facial occlusions. Multimed Tools Appl. 2017;77(11):14177–205. doi: 10.1007/s11042-017-5025-y DOI

Paulsen RR, Juhl KA, Haspang TM, Hansen T, Ganz M, Einarsson G. Multi-view consensus CNN for 3D facial landmark placement. In: Asian Conference on Computer Vision. Springer; 2018. p. 706–19.

Wang Y, Cao M, Fan Z, Peng S. Learning to detect 3D facial landmarks via heatmap regression with graph convolutional network. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2022. p. 2595–603.

Besl PJ, McKay ND. A method for registration of 3-D shapes. IEEE Trans Pattern Anal Mach Intell. 1992;14(2):239–56. doi: 10.1109/34.121791 DOI

Granger S, Pennec X. Multi-scale EM-ICP: A fast and robust approach for surface registration. In: European conference on computer vision. Springer; 2002. p. 418–32.

Li J, Hu Q, Zhang Y, Ai M. Robust symmetric iterative closest point. ISPRS J Photogram Remote Sens. 2022;185:219–31. doi: 10.1016/j.isprsjprs.2022.01.019 DOI

Urbanová P. Performance of distance-based matching algorithms in 3D facial identification. Egypt J Forens Sci. 2016;6(2):135–51. doi: 10.1016/j.ejfs.2016.04.004 DOI

He K, Sun J. Computing nearest-neighbor fields via propagation-assisted kd-trees. In: 2012 IEEE Conference on Computer Vision and Pattern Recognition. IEEE; 2012. p. 111–8.

Ram P, Sinha K. Revisiting kd-tree for nearest neighbor search. In:Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining; 2019. p. 1378–88.

Urbanová P, Hejna P, Jurda M. Testing photogrammetry-based techniques for three-dimensional surface documentation in forensic pathology. Forens Sci Int. 2015;250:77–86. doi: 10.1016/j.forsciint.2015.03.005 PubMed DOI

Jing Y, Lu X, Gao S. 3D face recognition: a comprehensive survey in 2022 . Comput Visual Media. 2023;9(4):657–85.

Guo Y, Wang H, Wang L, Lei Y, Liu L, Bennamoun M. 3D face recognition: two decades of progress and prospects. ACM Comput Surv. 2023;56(3):1–39.

Castellani U, Bartoli A. 3d shape registration. 3D Imaging, Analysis and Applications. 2020. p. 353–411.

Turk G, Levoy M. Zippered polygon meshes from range images. In: Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques. 1994. p. 311–8.

Rusinkiewicz S, Levoy M. Efficient variants of the ICP algorithm. In: Proceedings Third International Conference on 3-D Digital Imaging and Modeling. 2001. p. 145–52.

Jurda M, Urbanová P. Sex and ancestry assessment of Brazilian crania using semi-automatic mesh processing tools. Leg Med (Tokyo). 2016;23:34–43. doi: 10.1016/j.legalmed.2016.09.004 PubMed DOI

Jandová M, Urbanová P. Sexual dimorphism in human facial expressions by 3D surface processing. Homo. 2018;69(3):98–109. doi: 10.1016/j.jchb.2018.06.002 PubMed DOI

Schnabel R, Klein R. Octree-based point-cloud compression. In: Proceedings of the 3rd Eurographics/IEEE VGTC Conference on Point-Based Graphics. 2006. p. 111–21.

Rusu RB, Cousins S. 3D is here: Point Cloud Library (PCL). In: 2011 IEEE International Conference on Robotics and Automation; 2011. p. 1–4.

Rodolà E, Albarelli A, Cremers D, Torsello A. A simple and effective relevance-based point sampling for 3D shapes. Pattern Recogn Lett. 2015;59:41–7.

Tombari F, Salti S, Di Stefano L. Performance evaluation of 3D keypoint detectors. Int J Comput Vision. 2013;102(1):198–220.

Yulan Guo, Bennamoun M, Sohel F, Min Lu, Wan J. 3D object recognition in cluttered scenes with local surface features: a survey. IEEE Trans Pattern Anal Mach Intell. 2014;36(11):2270–87. doi: 10.1109/TPAMI.2014.2316828 PubMed DOI

Guo Y, Bennamoun M, Sohel F, Lu M, Wan J, Kwok NM. A comprehensive performance evaluation of 3D local feature descriptors. Int J Comput Vision. 2016;116:66–89.

Toldo R, Beinat A, Crosilla F. Global registration of multiple point clouds embedding the generalized procrustes analysis into an ICP framework. In: 5th International Symposium 3D Data Processing, Visualization and Transmission. 2010. p. 5.

Pomidor BJ, Makedonska J, Slice DE. A landmark-free method for three-dimensional shape analysis. PLoS One. 2016;11(3):e0150368. doi: 10.1371/journal.pone.0150368 PubMed DOI PMC

Aspert N, Santa-Cruz D, Ebrahimi T. MESH: measuring errors between surfaces using the Hausdorff distance. In: Proceedings. IEEE International Conference on Multimedia and Expo. 2002. p. 705–8.

Dubuisson MP, Jain AK. A modified Hausdorff distance for object matching. In: Proceedings of 12th International Conference on Pattern Recognition. 1994. p. 566–8.

Urbanová P, Ferková Z, Jandová M, Jurda M, Černý D, Sochor J. Introducing the FIDENTIS 3D face database. Anthropol Rev. 2018;81(2):202–23.

Cavallo M, Demiralp Ç. Clustrophile 2: guided visual clustering analysis. IEEE Trans Visualiz Comput Graph. 2018;25(1):267–76. PubMed

Gu Z. Complex heatmap visualization. Imeta. 2022;1(3):e43. doi: 10.1002/imt2.43 PubMed DOI PMC

Hruda L, Kolingerová I, Váša L. Robust, fast and flexible symmetry plane detection based on differentiable symmetry measure. Visual Comput. 2022;38(2):555–71.