Fingerprint indexing based on expanded Delaunay triangulation

Fingerprint indexing plays a key role in the automatic fingerprint identification systems (AFISs) which allows us to speed up the search in large databases without missing accuracy. In this paper, we propose a fingerprint indexing algorithm based on novel features of minutiae triplets to improve the performance of fingerprint indexing. The minutiae triplet based feature vectors, which are generated by ellipse properties and their relation with the triangles formed by the proposed expanded Delaunay triangulation, are used to generate indices and a recovery method based on k-means clustering algorithm is employed for fast and accurate retrieval. The proposed expanded Delaunay triangulation algorithm is based on the quality of fingerprint images and combines two robust Delaunay triangulation algorithms. This paper also employs an improved k-means clustering algorithm which can be applied over large databases, without reducing the accuracy. Finally, a candidate list reduction criteria is employed to reduce the candidate list and to generate the final candidate list for matching stage. Experimental results over some of the fingerprint verification competition (FVC) and national institute of standards and technology (NIST) databases show superiority of the proposed approach in comparison with state-of-the-art indexing algorithms. Our indexing proposal is very promising for the improvement of real-time AFISs efficiency and accuracy in the near future.