Fingerprint indexing based on expanded Delaunay triangulation
Introduction
Biometrics, or biometric recognition, refers to the use of the certain biological characteristics, such as deoxyribonucleic acid (DNA), odor, heart beat, electroencephalogram (EEG), behavioural characteristics, such as gait, signature, voice, handwriting, and morphological characteristics, such as hand shape, face, fingerprint, blood vessel, to uniquely and automatically identify individuals. There is no trait that highlights as the best one. Among them, fingerprints have been extensively used in both forensic applications, such as criminal investigation and corpse identification, and non-forensic applications, such as passport control and distance learning. Fingerprints provide a satisfactory balance between accuracy, robustness, speed, and resource requirements (Giot, Rosenberger, 2012, Maltoni, Maio, Jain, Prabhakar, 2009, Peralta, Galar, Triguero, Paternain, Garca, Barrenechea, Bentez, Bustince, Herrera, 2015). In general, fingerprint characteristics or features can be classified into three different levels (Galar, Derrac, Peralta, Triguero, Paternain, Lopez-Molina, García, Benítez, Pagola, Barrenechea, Bustince, Herrera, 2015, Maltoni, Maio, Jain, Prabhakar, 2009, Peralta, Galar, Triguero, Miguel-Hurtado, Benitez, Herrera, 2014a):
- •
Level-1 (global level): This level refers to the macro details of fingerprint such as the ridge flow structures, pattern types, orientation field (OF), frequency field, and singular points (core and delta).
- •
Level-2 (local level): This level refers to the minute details of ridge flow patterns such as the minutiae points (ridge bifurcation and ending).
- •
Level-3 (fine-detail level): This level includes all dimensional attributes of ridge details such as sweat pores, edge contours, incipient ridges, creases, widths, shapes, and scars.
Extraction of level-3 features usually requires fingerprint images with more than 500 dots-per-inch (dpi) resolution. Nowadays, most non-forensic automatic fingerprint identification systems (AFISs) work on 500 dpi images so their recognition algorithms primarily use level-1 and level-2 features. Level-2 features can provide a very large amount of discriminatory information to determine the individuality of a fingerprint; thus these features are the most commonly used ones for fingerprint matching. Level-1 features are often used for classification of fingerprint database and are not adequate to determine the uniqueness of a fingerprint. Liu and Cao (2016) show the existence of a deep relationship between level-1 and level-2 features of the fingerprints. Fig. 1 shows the features extracted from the fingerprint images.
There are many algorithms for identification of fingerprints in the specialized literature and also in the non-forensic applications. Most of these algorithms have acceptable performance when they deal with small databases (Peralta, Triguero, Sanchez-Reillo, Herrera, & Benitez, 2014b), but nowadays the sizes of most of modern fingerprint databases are in the order of millions of entries and their sizes are continuously growing (Muñoz Briseño, Gago-Alonso, & Hernández-Palancar, 2013), so finding a person among these databases would be very time consuming.
Many approaches have been proposed in the literature to speed up the search and identification processes. Among them, fingerprint classification, fingerprint indexing, hardware improvement, and parallel computing are the most common techniques. Fingerprint classification is a technique used to assign a fingerprint to one of the several pre-specified types. This technique can be viewed as a coarse-level matching of the fingerprints. An input fingerprint is first classified into one of the pre-specified types and then it is compared to a subset of the database corresponding to that fingerprint type (Maltoni et al., 2009). Most of the classification algorithms are based on the Galton–Henry classification scheme that consists of five major classes: whorl, left loop, right loop, arch, and tended arch. The main drawback of fingerprint classification is that the number of classes are usually small and fingerprints are unevenly distributed among them, about 7% of the fingerprints belong to two classes of arch and tended arch (Muñoz Briseño, Gago-Alonso, Hernández-Palancar, 2013, Gago-Alonso, Hernández-Palancar, Rodríguez-Reina, Muñoz Briseño, 2013, Galar, Derrac, Peralta, Triguero, Paternain, Lopez-Molina, García, Benítez, Pagola, Barrenechea, Bustince, Herrera, 2015, Maltoni, Maio, Jain, Prabhakar, 2009). Therefore, this approach cannot adequately narrow down the search in the large databases.
Another mostly referenced solution is the use of fingerprint indexing (Muñoz Briseño, Gago-Alonso, Hernández-Palancar, 2013, Maltoni, Maio, Jain, Prabhakar, 2009). The purpose of fingerprint indexing is to extract feature vectors that characterize every inserted fingerprint. Each resulting vector extracted is used to conform an index which is stored in an index table. When a query is performed in the retrieving stage, the number of correspondences between the indices of the query and the stored fingerprints are computed (Muñoz Briseño et al., 2013).
Finally, other solutions to deal with large databases are related to hardware and parallel computing. There’s no doubt that the hardware improvements, e.g., the improvement in the central processing unit (CPU) and the random access memory (RAM), can increase the performance of the identification process. Sutter (2005) discussed the need to start developing software considering concurrency to fully exploit continuing exponential microprocessors throughput gains. Nowadays, microprocessor manufacturers focused on adding processing cores instead of increasing their clock frequency. Thus, it is very important to prepare the software designs and the code to exploit multicore architectures. The fingerprint recognition problem is naturally parallelizable (Peralta et al., 2014b). In the fingerprint identification (one-to-many comparison) the comparisons of the query print (prob) with each of the fingerprints stored in the database (gallery) are independent. Thus, we can take advantage of parallelism using parallel programming for processing huge databases. Peralta et al. (2014b), Gutiérrez, Lastra, Herrera, and Benítez (2014), and Jiang and Crookes (2008) proposed hardware and software mechanisms to speed up the search and computations.
This paper presents a fingerprint indexing approach based on minutiae triplets. This paper also proposes an expanded Delaunay triangulation algorithm based on the quality of fingerprint images by combining two best Delaunay triangulation algorithms which are very tolerant to distortion and missing minutiae. Experiments over some of the FVC and the NIST databases prove superiority of the proposed approach in comparison with well known algorithms.
The rest of the paper is organized as follows. Section 2 reviews some related work in fingerprint indexing. Section 3 deals with feature extraction and quality estimation. Section 4 describes our proposed indexing algorithm in detail. Experimental results are presented and analyzed in Section 5. Conclusions and directions of future work are covered in Section 6.
Section snippets
Literature review
In this section, we review the work done by other researchers in field of fingerprint indexing. After reading the articles in the literature, we classified the fingerprint indexing methods into three general categories: minutiae based approaches, non-minutiae based approaches, and combined approaches. The extracted feature is a critical parameter in the fingerprint indexing methods. Generally, the difference between indexing methods is mainly related to the selection of the features and the
Pose estimation
One of the main challenges in the AFISs is distortion problem, which can have negative effect on identification process. The distortion problem caused by pressing the finger against the sensor surface, due to elastic distortion of finger skin. Registration of multiple impressions of the same finger is beneficial to fingerprint indexing and matching methods. One of the main differences between these methods is how they deal with fingerprint registration problem. Some of the methods perform
The indexing approach
The indexing approach uses novel features of minutiae triplets to improve performance of indexing. In this section, we describe the details of the indexing approach. Fig. 9 shows the overall scheme of our indexing algorithm.
Experiment results
This section presents all the questions raised with the experimental study and the results obtained. Section 5.1 describes the hardware and software environment used in our experiments. Section 5.2 details the used data sets. Section 5.3 shows the parameters of the our algorithm and discusses the obtained results.
Conclusions and future work
In the present work, we have presented a novel fingerprint indexing algorithm based on minutiae triplets. The algorithm combines two robust Delaunay triangulation algorithms and uses them to generate triangles. The algorithm also uses ellipse properties to generate feature vectors. Ellipse has deep relations to triangle and can construct robust feature vectors. The pose estimation, the quality estimation, and the improved k-means clustering algorithms are also utilized in this paper. The pose
Acknowledgments
The authors would like to thank the anonymous reviewers for their valuable and helpful comments and suggestions to improve and clarify this paper.
References (93)
Combining minutiae descriptors for fingerprint matching
Pattern Recognition
(2008)- et al.
Indexing and retrieving in fingerprint databases under structural distortions
Expert Systems with Applications
(2013) - et al.
A survey of fingerprint classification Part I: Taxonomies on feature extraction methods and learning models
Knowledge-Based Systems
(2015) - et al.
Genetic programming for multibiometrics
Expert Systems with Applications
(2012) Fusion of finger types for fingerprint indexing using minutiae quadruplets
Pattern Recognition Letters
(2014)- et al.
An efficient minutiae based geometric hashing for fingerprint database
Neurocomputing
(2014) - et al.
An improved overlapping k-means clustering method for medical applications
Expert Systems with Applications
(2017) - et al.
Fingerprint indexing based on minutiae pairs and convex core point
Pattern Recognition
(2017) - et al.
Invariant representation of orientation fields for fingerprint indexing
Pattern Recognition
(2012) - et al.
Fingerprint indexing with bad quality areas
Expert Systems with Applications
(2013)