An Indexing Algorithm Based on Clustering of Minutia Cylinder Codes for Fast Latent Fingerprint Identification

Abstract

Latent ngerprint identi cation is one of the leading forensic activities to clarify criminal acts. However, its computational cost hinders the rapid decision making in the identi cation of an individual when large databases are involved. To reduce the search time used to generate the ngerprint candidates' order to be compared, ngerprint indexing algorithms that reduce the search space while minimizing the increase in the error rate (compared to the identi cation) are developed. In the present research, we propose an algorithm for indexing latent ngerprints based on minutia cylinder codes (MCC). This type of minutiae descriptor presents a xed structure, which brings advantages in terms of ef ciency. Besides, in recent studies, this descriptor has shown an identi cation error rate, at the local level, lower than the other descriptors reported in the literature. Our indexing proposal requires an initial step to construct the indices, in which it uses k-meansCC clustering algorithm to create groups of similar minutia cylinder codes corresponding to the impressions of a set of databases. K-meansCC allows for a better outcome over other clustering algorithms because of the selection of the proper centroids. The buckets associated with each index are populated with the background databases. Then, given a latent ngerprint, the algorithm extracts the minutia cylinder codes associated with the clusters' indices with the lowest distance respect to each descriptor of this latent ngerprint. Finally, it integrates the votes represented by the ngerprints obtained to select the candidate impressions.We conduct a set of experiments in which our proposal outperforms current rival algorithms in presence of different databases and descriptors. Also, the primary experiment reduces the search space by four orders of magnitude when the background database contains more than one million impressions.