Computing mutual similarity of 3D human faces in nearly linear
time

J 2025

Computing mutual similarity of 3D human faces in nearly linear time

OŠLEJŠEK, Radek; Petra URBANOVÁ a Jiří SOCHOR

Základní údaje

Originální název

Computing mutual similarity of 3D human faces in nearly linear time

Autoři

OŠLEJŠEK, Radek; Petra URBANOVÁ a Jiří SOCHOR

Vydání

PLOS ONE, United States, Public Library Science, 2025, 1932-6203

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Permalink to the publisher

Impakt faktor

Impact factor: 2.600 v roce 2024

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00141722

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

facial morphology; measure of similarity; iterative closest points; 3D registration; N:N comparison; batch processing

Štítky

14314070

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 3. 2. 2026 10:56, prof. RNDr. Petra Urbanová, Ph.D.

Anotace

V originále

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.

Návaznosti

MUNI/A/1597/2023, interní kód MU

Název: Rozvoj automatizace při zpracování obrazových dat ve forenzní a aplikované antropologii

Investor: Masarykova univerzita, Rozvoj automatizace při zpracování obrazových dat ve forenzní a aplikované antropologii

MUNI/A/1750/2024, interní kód MU

Název: Automatizace a simulace ve zpracování obrazových dat ve forenzní a aplikované antropologii

Investor: Masarykova univerzita, Automatizace a simulace ve zpracování obrazových dat ve forenzní a aplikované antropologii

Přiložené soubory

2025-computing-mutual-similarity-3d-human-faces-linear-time-paper.pdf

Citovat

OŠLEJŠEK, Radek; Petra URBANOVÁ a Jiří SOCHOR. Computing mutual similarity of 3D human faces in nearly linear time. PLOS ONE. United States: Public Library Science, 2025, roč. 20, č. 8, s. 1-24. ISSN 1932-6203. Dostupné z: https://doi.org/10.1371/journal.pone.0329489.

@article{2510958,
   author = {Ošlejšek, Radek and Urbanová, Petra and Sochor, Jiří},
   article_location = {United States},
   article_number = {8},
   doi = {https://doi.org/10.1371/journal.pone.0329489},
   keywords = {facial morphology; measure of similarity; iterative closest points; 3D registration; N:N comparison; batch processing},
   language = {eng},
   issn = {1932-6203},
   journal = {PLOS ONE},
   title = {Computing mutual similarity of 3D human faces in nearly linear time},
   url = {https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0329489&},
   volume = {20},
   year = {2025}
}

TY  - JOUR
ID  - 2510958
AU  - Ošlejšek, Radek - Urbanová, Petra - Sochor, Jiří
PY  - 2025
TI  - Computing mutual similarity of 3D human faces in nearly linear time
JF  - PLOS ONE
VL  - 20
IS  - 8
SP  - 1-24
EP  - 1-24
PB  - Public Library Science
SN  - 19326203
KW  - facial morphology
KW  - measure of similarity
KW  - iterative closest points
KW  - 3D registration
KW  - N:N comparison
KW  - batch processing
UR  - https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0329489&
N2  - 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.
ER  -

OŠLEJŠEK, Radek; Petra URBANOVÁ a Jiří SOCHOR. Computing mutual similarity of 3D human faces in nearly linear time. \textit{PLOS ONE}. United States: Public Library Science, 2025, roč.~20, č.~8, s.~1-24. ISSN~1932-6203. Dostupné z: https://doi.org/10.1371/journal.pone.0329489.

Přehled o publikaci