Keywords

1 Introduction

Fingerprint recognition system is used to recognize the identity of a subject. Identification can be done by searching all images in the database (henceforth termed as models) against a image (henceforth termed as query). To make an efficient process, there is a need of an efficient indexing technique. A fingerprint has the following characteristics:

  • Number of minutiae extracted from a fingerprint of a subject at any two time instants may not be same.

  • There are too many minutiae in a fingerprint; some may be false.

  • Number of minutiae of any two fingerprints may not be same.

  • There may be partial occlusion in a fingerprint of a subject and it may overlap with some other subjects that are not present in the database.

  • A query fingerprint may be rotated and translated with respect to the corresponding model fingerprints in the database.

Most of the available fingerprint indexing schemes can be classified on the basis of the features such as singular points [1], directional field [2], local ridge-line orientations [3], orientation image [4], minutiae [5], minutiae descriptor, multiple features, and SIFT features. Since most matching algorithms use minutiae, the use of minutiae is especially beneficial. These schemes derive robust geometric features from triplets of minutiae and use hashing techniques to perform the search.

A prominent geometric-based indexing technique for fingerprints is proposed by Germain et al. [6] in which geometric features from triplets are used with the help of Fast Look up Algorithm for String Homology (FLASH) hashing technique. It does clustering using transformation parameter where all the fingerprints in that bin represent a hypothesis match between the three points in the query fingerprint and those in the fingerprints of database. The best coordinate transformation that matches query triplet and model triplet is calculated with the information. The transformation should be such that squared distance between the points of query triplet and model triplet is minimum. This transformation parameter reduces false matches.

The scheme in [7] uses geometric features from minutiae triplets where the triplet features are maximum length of three sides, median and minimum angles, triangle handedness, type, direction and ridge count minutiae density. Since triangles are formed using all possible minutiae, this increases both memory and computational cost. A fast and robust projective matching for fingerprints has been proposed in [8]. It performs a fast match using a Geometric Hashing [9] which needs large computational time and memory.

Bebis et al. [10] have used the geometric features from Delaunay triangles formed on the minutiae for indexing the fingerprints, instead of all possible combination of triangles. It can be shown that for a given set of minutiae, the Delaunay triangulation produces linear number of triangles. This compares favorably to the number of all possible combinations of triangles/ bases pairs considered in approaches [6–8]. However, the major issue with Delaunay triangulation is that it is more sensitive to noise and distortion. For example, if some minutiae are missed or added (spurious minutiae), the structure of Delaunay triangulation gets affected.

This paper presents an efficient indexing scheme which uses geometric information from triangles formed on minutiae to index model fingerprints. It assumes that the uncertainty of feature locations associated with minutiae feature and shear does not affect the angles of a triangle arbitrarily. Triangles are invariant to translation and rotation. It reduces the number of possible triangles by taking minutiae to form triangles within the specified region \(R\) from its core point \(C\) and is inserted exactly once into a hash table. So it effectively removes the use of all triangles/bases pairs used in [6–8] reducing memory and computational complexity.

The paper is organized as follows. Next section discusses feature extraction technique from a fingerprint image. Section 3 discusses the proposed indexing scheme. Experimental results are analyzed in the next section. Conclusions are given in the last section.

2 Feature Extraction

Feature extraction is a series of steps such as minutiae detection and core point detection [11]. Let \(M=\{m_{1},m_{2},\,\ldots ,\,m_{o}\}\) be the detected minutiae from each model fingerprint image. Each minutia \(m_{i}\) is a 4-tuple (\(x_{mi}, y_{mi}, \alpha _{mi}, T_{mi})\) which denotes their coordinates, direction, and type. Let \(C = (x_{c}, y_{c},\alpha _{c})\) be the core point, detected through [11] where (\(x_{c}, y_{c})\) denote the coordinates and \(\alpha _{c}\) is the direction of the core point. The proposed indexing scheme overcomes some of the issues and constraints in [6, 7] by considering small number of possible triangles instead of all possible triangles. In a model fingerprint, it considers the minutiae to form triangles within the specific range \(R\) from its core point \(C\) reducing computational and memory cost. Further, it introduces some additional features to reduce false correspondences. The triplet features used in the proposed indexing scheme are:

  1. 1.

    Sides of the triangles \(s_{1}, s_{2}, s_{3}\): Sides of the triangle is considered in certain order as the longest side, the medium side and the smaller side. If any two or three sides are similar, this system does not consider them because this type of triplets is negligible in number and their exclusion does not affect the results.

  2. 2.

    Regions of vertices \(r_{1}, r_{2}, r_{3}\): Considering core point \(C\) as the center, concentric circles are drawn with radius \(r\), 2\(r\), 3\(r\), 4\(r\)... till the circle’s outer line is completely outside fingerprint boundary. The optimal value of \(r\) is found out with the help of experiments. Let \(p_{1}, p_{2}, p_{3}\) be three vertices of triplet and \(r_{1}, r_{2}, r_{3}\) be their respective regions of vertices and \(d_{1}, d_{2}, d_{3 }\) be their respective distances from core point \(C\). Then the value of \(r_{i}\) is given by \(r_{i}=\frac{di}{r} + 1, i = 1, 2, 3\).

  3. 3.

    Triangle type \(\lambda \): Each minutia is either termination or bifurcation. If \(\lambda _{1}, \lambda _{2}, \lambda _{3}\) are three vertices to indicate whether they are termination or bifurcation point, then \(\lambda \) for the triplet can be used as one more attribute for indexing component. Since \(\lambda _{1}, \lambda _{2}\,{\text {and}}\,\lambda _{3}\) can have values either 0 or 1, based on termination or bifurcation, \(\lambda \) can be any value between 0 and 7 and is calculated by \(\lambda = 4 \lambda _{1} + 2 \lambda _{2 }+\lambda _{3}\).

  4. 4.

    Orientation \(\varphi \) : Sometime all the above features may be same for triplets of two triangles. They can be differentiated by their orientation which can be calculated using cross-product between the longest side and the medium side. Orientation has two values, \(+1\) or \(-\)1.

3 Proposed Indexing Scheme

The proposed indexing technique consists of two stages known as indexing and searching. During indexing, the model fingerprints in the database are indexed into a hash table. For any new fingerprint image, it can be added into a hash table without affecting the performance of the searching algorithm and without modifying the existing hash table. During searching, it recognizes the query fingerprint by searching only indexed hash bins.

3.1 Indexing

For each model fingerprint consisting of core point \(C\) and minutiae, concentric circles are drawn with radius \(r\), 2\(r\), 3\(r\), 4\(r\)... till the circle’s outer line is completely outside fingerprint boundary. The value of \(r\) is found experimentally. All possible triangles within various circles are determined. The index \(I = (s_{1}, s_{2}, s_{3}, r_{1}, r_{2}, r_{3}\lambda , \varphi )\) is generated from each triangle to select an appropriate bin in hash table. At this bin, model fingerprint ID is added. At the time of indexing, it keeps track of number of triangles generated from each model fingerprint. Let \(T_{i}\) be the total number of triangles generated from a model \(M_{i}\) used for indexing. Steps for indexing are given in Algorithm 1.

Algorithm 1: Indexing

For each model fingerprint \(M_{i}\) do the following

1. Generate all possible triangles for minutiae of fingerprint.

2. Consider only those triangles whose all sides are in the specifies range \(R\).

3. Store numbers of triangles considered in indexing and store it in \(T_{i}\) where \(T_{i}\) indicates total number of triangles of fingerprint \(M_{i}\) considered for indexing.

4. For each triplet do the following

   a) Generate index \(I = (s_{1}, s_{2}, s_{3}, r_{1}, r_{2}, r_{3}, \lambda , \varphi )\).

   b) Access appropriate bin of the hash table.

   c) Add model fingerprint ID of the image to this bin.

Algorithm 2: Searching

For the given query \(Q\) do the following

1. Generate all possible triangles from the minutiae of the query image.

2. Consider only those triangles whose all sides are in the specified range \(R\). Let there be \(T\) such triangles.

3. For each triangle, do the following

   a) Generate index \(I = (s_{1}, s_{2}, s_{3}, r_{1}, r_{2}, r_{3}, \lambda , \phi )\).

   b) Access appropriate bin of the hash table.

   c) Increment count \(C_{i}\) for all model fingerprints whose ID is in that bin.

   d) Calculate \(S_{i}\), score of image \(M_{i}\), by formula \(S_{i}=\frac{Ci}{Ti}\).

   e) Obtain largest \(t\) \(S_{i}\)’s that are to be considered for critical search.

3.2 Searching

For a given query fingerprint, all possible triangles are generated using minutiae similar to indexing stage. Then only those triangles are considered whose all sides of triangle fall within the range \(R\). Let there be \(T\) such triangles. From these triangles, an index \(I = (s_{1}, s_{2}, s_{3}, r_{1}, r_{2}, r_{3}, \lambda , \varphi \)) is generated to find an appropriate bin of hash table and to count each model fingerprint ID in that bin \(C_{i}\). Same process is repeated for remaining query’s triangles. Finally, score \(S_{i}\) is calculated by \(S_{i}=\frac{C_i}{T_i} , i =1, 2,\,...,\,N \)where \(N\) denotes the number of fingerprints in the database. Largest \(t \quad S_{i}\)’s which are considered for top \(t\) best matches are used for critical search to find out the exact match. Steps for searching are given in Algorithm 2.

4 Experimental Results

The proposed indexing scheme has been tested on IITK fingerprint database of 2,120 images acquired from 530 subjects. Every person has given four fingerprints of the same finger, at different instant of times. Four datasets have been created to carry out various experiments. DB1 contains 2120 fingerprints, DB2 has 1,336 fingerprints while DB3 and DB4 contains 668 fingerprints and 200 fingerprints respectively. In all these datasets, three impressions of each finger are used for indexing and remaining one impression is used for searching.

Fig. 1
figure 1

Performance graph: effect of core point generated features

Full size image

Figure 1 shows the performance of the proposed indexing scheme with respect to core point and database sizes. DB4 dataset is used for performing this experiment. The CRR is very high when core point is considered to obtain additional features from triangles. This CRR, when core point is used, is close to the CRR of the existing schemes like [6] and [7] . But the proposed scheme has achieved this performance without using transformation parameter cluster and imposing any geometrical constraints. Experiments have also been conducted on all datasets DB1, DB2, DB3, DB4. It is found that there is no drastic difference in CRR for different datasets and as database size is increasing, CRR is coming down for a given Penetration Rate, slightly.

5 Conclusion

This paper has proposed a fingerprint-based indexing scheme which uses core point. This has helped to overcome various issues and constraints of well-known schemes. It has been tested on IITK database containing 2,120 fingerprints of 530 subjects. Accuracy is found to be 86.79  % at top 10 best matches. This accuracy has been achieved without using clustering based on transformation parameter and without imposing geometrical constraints as in existing schemes. However, it may not perform well when a fingerprint does not contain any core point.