Elsevier

Expert Systems with Applications

Volume 81, 15 September 2017, Pages 251-267
Expert Systems with Applications

Fingerprint indexing based on expanded Delaunay triangulation

https://doi.org/10.1016/j.eswa.2017.03.048Get rights and content

Highlights

  • A novel and efficient fingerprint indexing based on minutiae triplets, is proposed.

  • The proposed fingerprint features are invariant to rotation and translation.

  • Our fingerprint representation is very robust to distortions and noise.

  • The experimental results demonstrate the validity of the proposed algorithm.

Abstract

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.

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)

  • M.C. Naldi et al.

    Efficiency issues of evolutionary k-means

    Applied Soft Computing

    (2011)
  • D. Peralta et al.

    Minutiae filtering to improve both efficacy and efficiency of fingerprint matching algorithms

    Engineering Applications of Artificial Intelligence

    (2014)
  • D. Peralta et al.

    A survey on fingerprint minutiae-based local matching for verification and identification: Taxonomy and experimental evaluation

    Information Sciences

    (2015)
  • D. Peralta et al.

    Fast fingerprint identification for large databases

    Pattern Recognition

    (2014)
  • H. Sutter

    The free lunch is over: A fundamental turn toward concurrency in software

    Dr. Dobb’s Journal

    (2005)
  • A. Vij et al.

    Fingerprint indexing based on local arrangements of minutiae neighborhoods

    Proceedings of the IEEE computer society conference on computer vision and pattern recognition workshops (CVPRW’12) Providence, USA

    (2012)
  • Y. Wang et al.

    A fingerprint orientation model based on 2d fourier expansion (FOMFE) and its application to singular-point detection and fingerprint indexing

    IEEE Transactions on Pattern Analysis and Machine Intelligence

    (2007)
  • W. Zhou et al.

    Fingerprint indexing based on combination of novel minutiae triplet features

    Proceedings of the 8th international conference on network and system security (NSS’14) Xi’an, China

    (2014)
  • C. Bai et al.

    An efficient indexing scheme based on k-plet representation for fingerprint database

    Proceedings of the 11th international conference on intelligent computing (ICIC’15) Fuzhou, China

    (2015)
  • S. Barman et al.

    An efficient fingerprint matching approach based on minutiae to minutiae distance using indexing with effectively lower time complexity

    Proceedings of the international conference on information technology (ICIT’14) Bhubaneswar, India

    (2014)
  • G. Bebis et al.

    Fingerprint identification using delaunay triangulation

    Proceedings of the international conference information intelligence and systems (ICIIS’99) Maryland, USA

    (1999)
  • B. Bhanu et al.

    Fingerprint indexing based on novel features of minutiae triplets

    IEEE Transactions on Pattern Analysis and Machine Intelligence

    (2003)
  • S. Biswas et al.

    Exploring ridge curvature for fingerprint indexing

    Proceedings of the 2nd IEEE international conference on biometrics: theory, applications and systems (BTAS’08) Arlington, USA

    (2008)
  • J.d. Boer et al.

    Indexing fingerprint databases based on multiple features

    Proceedings of the 12th annual workshop on circuits, systems and signal processing workshop Veldhoven, Netherlands

    (2001)
  • R. Cappelli

    Fast and accurate fingerprint indexing based on ridge orientation and frequency

    IEEE Transactions on Systems, Man, and Cybernetics

    (2011)
  • R. Cappelli et al.

    Minutia cylinder-code: A new representation and matching technique for fingerprint recognition

    IEEE Transactions on Pattern Analysis and Machine Intelligence

    (2010)
  • R. Cappelli et al.

    Fingerprint indexing based on minutia cylinder-code

    IEEE Transactions on Pattern Analysis and Machine Intelligence

    (2011)
  • R. Cappelli et al.

    Candidate list reduction based on the analysis of fingerprint indexing scores

    IEEE Transactions on Information Forensics and Security

    (2011)
  • S. Chikkerur et al.

    K-Plet and coupled BFS: A graph based fingerprint representation and matching algorithm

    Proceedings international conference on biometrics (ICB 2006) Hong Kong, China

    (2005)
  • K. Choi et al.

    An improved fingerprint indexing algorithm based on the triplet approach

    Proceedings of the 4th international conference audio and video based biometric person authentication (AVBPA’03) Guildford, UK

    (2003)
  • A. Deblonde et al.

    Fingerprint indexing through sparse decomposition of ridge flow patches

    Proceedings of the IEEE symposium on computational intelligence in biometrics and identity management (CIBIM’14) Orlando, USA

    (2014)
  • J. Demšar

    Statistical comparisons of classifiers over multiple data sets

    Journal of Machine Learning Research

    (2006)
  • H. Deng et al.

    Minutiae matching based fingerprint verification using Delaunay triangulation and aligned-edge-guided triangle matching

    Proceedings of the 5th international conference on audio- and video-based biometric person authentication (AVBPA’05) Hilton Rye Town, USA

    (2005)
  • A. Dremin et al.

    Fingerprint identification algorithm based on Delaunay triangulation and cylinder codes

    Proceedings of the third international conference analysis of images, social networks and texts (AIST’14) Yekaterinburg, Russia

    (2014)
  • M. Elmouhtadi et al.

    Fingerprint indexing based barycenter triangulation

    Proceedings of the third world conference on complex systems (WCCS’15) Marrakech, Morocco

    (2015)
  • M.F. Fahmy et al.

    A fingerprint segmentation technique based on morphological processing

    Proceedings of the IEEE international symposium on signal processing and information technology (ISSPIT’13) Athens, Greece

    (2013)
  • J. Feng et al.

    Fingerprint indexing using ridge invariants

    Proceedings of the 18th international conference on pattern recognition (ICPR’06) Hong Kong, China

    (2006)
  • M. Friedman

    The use of ranks to avoid the assumption of normality implicit in the analysis of variance

    Journal of the American Statistical Association

    (1937)
  • H. Fronthaler et al.

    Local features for enhancement and minutiae extraction in fingerprints

    IEEE Transactions on Image Processing

    (2008)
  • FVC2000: The first fingerprint verification competition. (2016). Accessed 14...
  • FVC2002: The Second fingerprint verification competition (2016). Accessed 14...
  • FVC2004: The third international fingerprint verification competition (2016). Accessed 14...
  • FVC2006: The fourth international fingerprint verification competition (2016). Accessed 14...
  • S. García et al.

    An extension on statistical comparisons of classifiers over multiple data sets for all pairwise comparisons

    Journal of Machine Learning Research

    (2008)
  • R.S. Germain et al.

    Fingerprint matching using transformation parameter clustering

    IEEE Computational Science and Engineering

    (1997)
  • P.D. Gutiérrez et al.

    A high performance fingerprint matching system for large databases based on GPU

    IEEE Transactions on Information Forensics and Security

    (2014)
  • Cited by (0)

    View full text