Fingerprint indexing based on minutiae pairs and convex core point

Highlights

• An efficient fingerprint indexing, which uses ellipse properties, is proposed.

• A new fingerprint indexing is proposed using minutiae pairs and convex core point.

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

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

Abstract

Fingerprint identification is an important issue for identifying fingerprints and plays a key role in the fingerprint recognition systems. However, performing a fingerprint identification over a large database can be an inefficient task due to the lack of scalability and high computing times of fingerprint matching algorithms. Fingerprint indexing is a key strategy in automatic fingerprint identification systems (AFISs) which allows us to reduce the number of candidates, the search space, and the occurrences of false acceptance in large databases. In this paper, an efficient indexing algorithm is proposed using minutiae pairs and convex core point which employs k-means clustering and candidate list reduction criteria to improve the identification performance. Our proposal can effectively reduce the search space and number of candidates for fingerprint matching, and thus achieves higher efficiency and significantly improves the system retrieval performance. Experimental results over some of the fingerprint verification competition (FVC) and the national institute of standards and technology (NIST) databases prove the superiority of the proposed approach against some of the well known indexing algorithms.

Introduction

Fingerprints are physiological characteristics of biometric recognition and have been extensively used in both forensic and non-forensic applications [49]. A fingerprint is the pattern of ridges (single curved segments) and valleys (regions that lies in between ridges) on the surface of a fingertip [41], [74]. Fig. 1 shows an example of gray-scale image of fingerprint and the details extracted from it.

A fingerprint recognition system may be called either a verification system or an identification system. The aim of fingerprint verification systems is to focus on matching the fingerprint of a person with his/her stored fingerprint templates, i.e., matching module works in one-to-one comparison mode. In these systems, the speed of a comparison mainly depends on how the similarity measure is evaluated between a query print (probe) and the fingerprint stored in the database (gallery), whereas the selection of the similarity measure usually depends on representation of the features. On the other hand the aim of the fingerprint identification systems is to establish the identity of a person, given a query print and a database of enrolled fingerprints of different individuals to seek a match. In these systems, matching module works in one-to-many comparison mode [22], [39], [49], [52], [70]. If the number of templates in a database are N, thus identification systems can be viewed as a series of N one-to-one comparisons [49], [58].

Most of the well known fingerprint matching algorithms are fast and quite accurate to deal with small databases [59], but nowadays the size of most of modern fingerprint databases is very large and need a search on all gallery fingerprints which affect both accuracy and efficiency of fingerprint matching [7], [22], [52]. If there is a need for finding a person among these databases, it must be done in reasonable time, often shorter than a few seconds. Within this context, the bottleneck step in the identification process is the matching algorithm, because it must be performed once per each gallery to determine which one has the most similary with the probe.

There are various methods to reduce the search time and computational complexity, and to speed up the matching process in the literature [52], [58]. Generally, reducing the number of comparisons and increasing the speed of a comparison can efficiently speed up the matching process [70].

Fingerprint pre-selection techniques can significantly reduce the search space [49]. These techniques can be classified into two main groups: exclusive classification, a fixed number of classes, and continuous classification, fingerprint indexing [7], [10], [46]. In exclusive classification, a fingerprint database is divided to a fixed number of classes and the query print is compared with those belonging to the same class [46]. However, exclusive classification has two drawbacks:

• Even with fixed number of classes involved exclusive classification is still a challenging problem due to small inter-class variability (much similarity between two images from different fingers), large intra-class variability (large variability in different impressions of the same finger), poor quality fingerprints, and the presence of noise [49].

• The number of classes in which the search space is divided are small and fingerprints are unevenly distributed among them. For instance in Galton-Henry classification scheme, that consists of five major classes: whorl, left loop, right loop, arch, and tended arch, about 93% of the fingerprints belong to three classes right loop, left loop, and whorl [7], [10], [22], [23], [49], [52].

Therefore, using exclusive classification will not effectively reduce the number of potential candidates to a minimum.

Fingerprint indexing works by associating a query print with index codes or feature vectors that best describe their features [32]. Each extracted feature vector 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 gallery fingerprints are computed [52].

Extraction of discriminative and reliable features is crucial for fingerprint indexing. Fingerprint indexing algorithm is usually at first is used to quickly choose a subset of candidates and then accurate but slower matching algorithm is employed to determine the final result [63]. Fingerprint indexing causes reduction of the search space of AFIS without missing accuracy [46], [52] and can be classified into three approaches [63]:

• Level-1 indexing: These approaches use level-1 features, such as the ridge flow structures, pattern types, orientation field, ridge frequency field and singular points (core and delta), and are commonly faster than level-2 indexing approaches.

• Level-2 indexing: These approaches are based on level-2 features (minutiae).

• Combined indexing: These approaches combine both level-1 and level-2 features to arrive at a better performance.

Other solutions to deal with large databases are related to hardware and parallel computing. Jiang and Crookes [37] presented an efficient implementation of fingerprint matching on field-programmable gate arrays (FPGAs), which takes advantage of an early jump-out (EJO) mechanism to speed up the large database retrieval. Peralta et al. [59] proposed a two-level distributed and parallel framework that allows a parallel search through the fingerprint database, providing an increased system performance. Gutiérrez et al. [28] presented a graphics processing unit (GPU) fingerprint matching system based on minutia cylinder-code (MCC). GPUs provide large-scale parallelism on computing platforms.

In this paper we introduce a new fingerprint indexing algorithm, a combined indexing approach, based on the minutiae pairs and convex core point which employs k-means clustering and candidate list reduction criteria to speed up the search and to improve the accuracy in large databases. k-means clustering and candidate list reduction criteria can effectively reduce the search space and number of candidates in fingerprint matching, and thus achieve higher efficiency and significantly improve the system retrieval performance. Experiments over six data sets demonstrate that the proposed algorithm outperforms some of the best state-of-the-art indexing algorithms.

The remainder of the paper is organized as follows. Section 2 presents a review of some of the related work in fingerprint indexing. Section 3 deals with image enhancement and feature extraction. Section 4 discusses the proposed indexing approach. Section 5 presents experimental results and analysis. Finally, Section 6 draws some conclusions.