A novel fingerprint indexing scheme using dynamic clustering

Abstract

With the increase in adoption of biometric data for various identification processes, the need for efficient indexing techniques is also on the rise as it is computationally impossible to match the query template against every enrolled entry in the database. In this paper, we have proposed two robust feature extraction techniques from fingerprint images followed by an indexing method based on clustering and m-ary trees. We extract robust translation and rotation invariant features from O(n) triangles obtained from the triangle spiral constructed for every fingerprint. The other method involves construction of M rectangles around every reference minutiae and calculation of features based on neighboring relation. Experiments with the benchmark databases confirm the superiority of our approach to the other existing techniques.

1 Introduction

As advancements are being made in every field of science and technology, the need for keeping these systems safe and secure is also increasing. As a result, the use of biometric databases for various security purposes is gaining importance. Among the many physiological (face, iris, fingerprints, DNA) and behavioral (voice, gait, typing pattern) biometrics [1], fingerprints are the most acceptable due to their accessibility, stability, uniqueness, etc.

Biometric systems can be put to use both in verification and identification. In verification , the id with which the template is to be matched is already available, that is, it is 1:1 matching. However, identification involves searching the whole database to retrieve the matching template. This 1:N matching is not only time consuming but also prone to various errors [2]. The idea of how big the databases are can be got from Aadhar, which is issued by UIDAI [3] and consists of data of more than 730 million people. To make the identification process more efficient, different classification and indexing techniques are used. Classification involves dividing the complete set of fingerprints into distinct classes and then searching only in that particular class. But, the major drawback with this system is that one can only have a countable number of distinct classes, namely arch, tented arch, right loop, left loop and whorl [4]. Further, the density in each is also not uniform. Indexing, on the other hand, works on a handful of robust features extracted from the templates and then searching the database with the same features [5].

We have proposed a novel indexing approach for fingerprints in this paper. The rest of the paper is organized as follows. Section 2 describes the existing state-of-the-art techniques used for fingerprint indexing. Our proposed methodology including the two techniques for feature extraction are presented in Sect. 3 and the results of the same in Sect. 4. Finally, we conclude our work in Sect. 5.

2 Related work

There have been many fingerprint indexing approaches that have been proposed before using minutiae [10–15], local ridge orientation [7], singular points [6], SIFT features[9] and matching scores [8]. The ones based on minutiae have proved to be the most robust and we discuss some of the state-of-the-art techniques of fingerprint indexing below.

Germain et al. [10] used the minutiae in the fingerprints to construct all possible combination of triangles. The length of the triangle, the ridge count between the sides, and the angles of the triangles were the features used for index key generation. Fast Look Up Algorithm for String Homology (FLASH) was used to compute the index. Bhanu et al. [11] also utilized minutiae triplets in their method but used different features which included the angles of the triangle, its longest, triangle handedness and direction. However, these approaches are computationally costly as they produce $O(n^3)$ triplets. Bebis et al. [12] improvised this cost, reducing it to O(n) using Delaunay triangulation. The features used were the ratio of the largest side with the smallest sides and the cosine angle between the smallest sides. Low-order Delaunay Triangulation [13] reduced the effect of spurious and missing minutiae thereby further increasing the performance. The authors in this paper included features such as triangle handedness, minimum and median angles and length of the longest side in the triangle. In [14], Delaunay Triangulation was used to extract ridge-associated features upon which clustering is performed using K-means algorithm.

Minutia Cylinder Code (MCC) representation was used in [15] where each fingerprint was represented by a set of bit vectors and the indexing was done by Locality Sensitive Hashing (LSH). Each minutia point was represented by a 384-bit binary feature vector. But, Wang et al. [16] observed this representation to be bit correlated and reduced the length to 24 bits from 384 using compact binary hash codes.

In [17], Jayaraman et al. used hash table to index invariant spatial (distance) and directional (angle) information. A fixed length vector called Minutia Binary Pattern (MBP) is also built for each minutia for accurate matching at the time of searching. Briseno et al. [18] proposed a method to find reference points by taking the difference of orientations around a block to locate singular points, that is, core and delta. The indexing features used were ridge count, triangle sign, reference point features of minutiae and its relative direction. Another indexing technique [19] involves construction of fingerprint shell which was a special triangle curve formed from the minutiae features. Hausdorff distance was used to match the query and database templates. Out of the two methods proposed in this paper for feature extraction, one of them involves the construction of a similar triangle spiral for each fingerprint. These O(n) triangles are then used to form the feature vector.

There are several other methods that have been proposed in the literature based on minutiae quadruplets instead of triplets. Iloanusi et al. [20] used all possible quadruplets that can be formed from the minutiae. They have used seven features in the vector $F = \{ \phi _1,\phi _2, \delta _1, \delta _2, \rho _1, \rho _2, \eta \}$ where, $\phi _1$ and $\phi _2$ are the differences of two opposite angles in the quadruplet, $\delta _1$ and $\delta _2$ are its diagonals, $\rho _1$ and $\rho _2$ are the heights of the inner parallelogram whose vertices are the mid-points of the quadruplet. Further, $\eta = 100 \mathrm{log}_{10} (\tau \upsilon )$ where $\tau = \root 2 \of {A_p} + \root 4 \of {x_1 \times x_2 \times x_3 \times x_4}$ and $\upsilon = \root 2 \of {A_q}\, +\, \root \of {y_1 \times y_2}$. $A_p$ is the area of the parallelogram, $x_1$, $x_2$, $x_3$ and $x_4$ are the lengths of the sides of the quadruplet, $A_q$ is the area of the quadruplet, and $y_1$ and $y_2$ are the lengths of the sides of the parallelogram.

In [29], authors proposed a fingerprint pose estimation algorithm which can register fingerprints into a common finger coordinate system. A fingerprint indexing is designed by combining the binary template and Locality Sensitive Hashing indexing algorithm in [30]. A fixed length feature vector built from each minutia, known as Coaxial Gaussian Track Code (CGTC) was proposed in [31]. The feature vector is inserted into a Quantized Lookup Table (QLT).

The above techniques suffer mainly from two disadvantages. 1. The computation cost is very high as using all possible combinations of minutiae triplets and quadruplets result in $O(n^3)$ or $O(n^4)$ complexity. 2. Moreover, when a dynamic database is to be considered, that is, where new users are enrolled while certain old ones have to be removed on a periodic basis, the index space has to be generated afresh again and again. Our proposed technique overcomes both these difficulties. Using the triangle spiral for feature extraction, gives us only O(n) triangles leading to low computation cost. Second, since dynamic clustering is employed, it is not necessary to disturb all of the existing clusters but only the ones in which new admissions are to be made. In addition, m-ary trees facilitate further in decreasing the search space and hence a high hit rate at a low penetration rate.

3 Proposed method

This section describes the proposed indexing approach for the fingerprints. The proposed approach follows these steps:

• 1. Feature extraction from a fingerprint

• 2. Dynamic clustering of the feature vector

• 3. Generation of a tree from each cluster

• 4. Retrieval of the candidate set.

3.1 Feature extraction from a fingerprint

The first step involves extraction of minutiae from the fingerprint image. Each minutia can be represented by $m_i = \{x_i, y_i, \theta _i, t_i \}$, where $\{x_i, y_i\}$ denote its coordinates, $\theta _i$ is its orientation with respect to x-axis and $t_i$ the type of minutia, that is, bifurcation or end. Figure 1 shows a sample fingerprint image having different types of minutiae along with the singular points, core and delta. In this paper, we have proposed two methods for feature extraction which have been discussed in detail below.

Fig. 1

Singular points and minutiae types in a fingerprint

Fig. 2

L rectangles with different orientations around the reference minutiae

3.1.1 Neighboring relation using rectangle

This method for feature extraction utilizes the multiline neighboring relation generation approach as proposed in [28]. Let $M = \{m_1, m_2,\ldots ,m_n \}$ denote the set of minutiae in the fingerprint. We select a reference minutia $m_r = \{x_r, y_r, \theta _r, t_r \}$ and construct L rectangles of length l and width w centered at $(x_r,y_r)$ with orientations $\theta _r, \theta _r + \frac{\pi }{L}, \theta _r + \frac{2\pi }{L}, \ldots , \theta _r + \frac{L-1\pi }{L}$. Figure 2 shows L rectangles drawn at different orientation angles around a reference minutia. We should choose three rectangles at best, because if we choose more number, the rectangles will overlap each other, so that each minutiae point may fall in more than one rectangle, which causes redundancy. All the minutia falling inside the constructed rectangle are selected and the rotation invariant distance and orientation angle of the selected minutiae with the reference minutiae are computed as:

$$\begin{aligned}&\chi = (x_j-x_r)\cos \theta _r + (y_j-y_r)\sin \theta _r\\&\gamma = (x_j-x_r)\sin \theta _r - (y_j-y_r)\cos \theta _r \\&d_{ij}= \sqrt{\chi ^2 + \gamma ^2}\\&\psi _{ij} = \left\{ \begin{array}{ll} \theta _j- \theta _r &{} \quad \theta _j>\theta _r \\ \theta _j- \theta _r + 360 &{}\quad \mathrm{otherwise} \\ \end{array} \right. \end{aligned}$$

Here, $d_{ij}$ denotes the distance from reference minutiae to the ith minutia in the jth rectangle and $\psi _{ij}$ denotes the orientation angle of the ith minutia in the jth rectangle. The above steps are repeated for all the minutia present in a fingerprint template being considered as the reference minutia. Finally, from each fingerprint, we get a set of feature vectors, $F = \{f_1, f_2,\ldots , f_n \}$, where $f_i = \{d_{ij}, \psi _{ij}, \theta _i, t_i, id_i \}$. $\theta _i$ is the orientation of the ith minutiae falling inside the jth rectangle, $t_i$ its type and $id_i$ is the fingerprint id of the user.

3.1.2 Triangle spiral

The second approach for feature extraction involves the construction of O(n) triangles for each fingerprint. Let $M = \{m_1, m_2,\ldots ,m_n \}$ denote the set of minutiae in the image. The distance of each of the minutia from the core is calculated and sorted from lowest to highest. Let $d = \{d_1,d_2,\ldots ,d_n\}$ be the set denoting the sorted distances. A user-defined parameter $d_0$ is chosen to be added to all the elements of the set d resulting in the set $d^\prime = \{d_1+d_0, d_2+d_0,\ldots ,d_n+d_0\}$. These distances are used to construct the triangle spiral which consists of n contiguous right-angled triangles. The lengths in the set $d^\prime$ act as the lengths of the hypotenuses of these triangles. The triangle spiral is made such that the distance $d_0$ serves as the leg of the first triangle and $d_1+d_0$ as the hypotenuse. The leg of the second right-angled triangle is the same as the previous one’s hypotenuse and the length $d_2+d_0$ in turn becomes its hypotenuse. The process thus continues with the legs of the current triangle same as the hypotenuse of the previous one. The heights of all these triangles can be calculated using Pythagoras Theorem. The first three right-angled triangles of the spiral are shown in Fig. 3a. Finally from each fingerprint having n minutiae, we obtain a feature vector set $F = \{f_1, f_2,\ldots , f_n \}$, where $f_i = \{ \theta _i, \phi _i, h_i, t_i, id_i \}$. $h_i$ is the height of the $i^{th}$ triangle, $\phi _i$ is the angle opposite to height, $\theta _i$ is the orientation of the minutia which is $i^{th}$ farthest from the core, $t_i$ its type and $id_i$ is the fingerprint id of the user. Figure 3b shows the triangle spiral constructed from a fingerprint.

Fig. 3

Illustration of construction of triangle spiral. a Geometric features of the right triangles, b Complete spiral of a fingerprint. Core is marked in blue and minutiae points in red in the fingerprint

3.2 Dynamic clustering of the feature vector

Let the set $F_i$ denote the feature vector set extracted from the $i^{th}$ enrolled image. Thus, from p enrolled images, we will get the feature vector set as $F = \{F_1, F_2,\ldots , F_p\}$.

If the feature extraction is carried out using the first method, the feature vector F looks like

$$\begin{aligned} F = \left( \begin{array}{l@{\quad }l@{\quad }l@{\quad }l@{\quad }l} d_{11} &{} \psi _{11} &{} \theta _1 &{} t_1 &{} id_1\\ d_{12} &{} \psi _{12} &{} \theta _2 &{} t_2 &{} id_2\\ \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots \\ d_{mL} &{} \psi _{mL} &{} \theta _m &{} t_m &{} id_m\end{array} \right) \end{aligned}$$

where mth minutia lies in the Lth rectangle when the last minutia of the pth image is taken as the reference minutia.

Alternatively, let there be a total of q minutiae in the p images, then the features from all the fingerprints extracted using triangle spiral are stored in a matrix of size $q \times 5$ as shown.

$$\begin{aligned} F = \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} \theta _1 &{} \phi _1 &{} h_1 &{} t_1 &{} id_1\\ \theta _2 &{} \phi _2 &{} h_2 &{} t_2 &{} id_2\\ \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots \\ \theta _q &{} \phi _q &{} h_q &{} t_q &{} id_q\end{array} \right) \end{aligned}$$

Clusters are formed using only the first three elements of the feature vector $(d,\psi ,\theta )$ if obtained from 3.1.1 or $(\theta , \phi , h)$ from 3.1.2. Linde–Buzo–Gray (LBG) algorithm [21] is used to carry out the dynamic clustering. As the size of biometric databases is not fixed, the more commonly used clustering technique, k-means algorithm is less preferable than dynamic clustering as here the user does not have to set the number of clusters k, beforehand. In the proposed approach, a threshold T is set such that if the number of members in a given cluster is more than the threshold, it gets divided into two using k-means where k is fixed at 2. The mean of the whole cluster is computed after which it is displaced by a small value, $\epsilon$. We do not want the new initial means to go very far from each other or out of the cluster as a result of which the value of $\epsilon$ is chosen to be very small. For instance, in this paper, we have used $\epsilon = 10^{-15}$. After obtaining the two initial means, k-means is applied to get the new clusters. This process is repeated till all the clusters have less than T elements. We finally get a list of the means of all clusters denoted by code vectors and the respective elements as well. The algorithm for the clustering procedure is presented in Algorithm 1 and its working depicted in Fig. 4.

Fig. 4

Illustration of the working of Linde–Buzo–Gray (LBG) Algorithm

3.3 Generation of a tree from each cluster

For each cluster, a generic (m-ary) tree is built. M-ary tree implies that each parent can have m or less children. The children having the same parent are called siblings. A node in the tree contains 5-D data viz.

$\{d_{ij}, \psi _{ij}, \theta _i, t_i, id_i\}$ (from 3.1.1) or $\{\theta _i, \phi _i, h_i, t_i, id_i\}$ (from 3.1.2) and points to two other nodes, one to its first child and second to its next sibling. A 3-ary tree with both the pointers is illustrated in Fig. 5. The root of the tree is formed by the code vector that is the mean of the cluster and it does not have a sibling. The siblings are such that the value of their first element is less than or equal to that of their parent. Further, to make the tree balanced, the siblings are selected in such a way that the number of descendants is nearly the same for each sibling. Let the order of the tree be m and the number of members in the cluster be e denoted by $\{f_1, f_2,\ldots , f_e\}$. First, we sort these e elements on the basis of the first dimension of the data ($\theta$ or d). While fixing the children of the root, it is done in a way that the number of descendants of the m siblings remain close to each other. The member at the (e / m)th position is appointed as the first child of the root, the one at $2\times (e/m)$th position as its next sibling and the process continues till the last element, i.e., eth of the sorted list becomes the last sibling. In a similar fashion are the rest of the nodes of the tree filled up. The m-ary tree provides an additional advantage of a lower height compared to a binary one. The algorithm for the above-described process is given in Algorithm 2.

Fig. 5

Structure of an m-ary tree showing the pointers to the first child and the siblings (m = 3)

3.4 Retrieval of the candidate set

For a query image, it is important to retrieve an accurate candidate list for a high hit rate. Let us denote the query image by Q and its feature vector set by $F_q$. $F_q$ is computed by the same method as explained in Sect. 3.1. Next, the euclidean distance between each of the feature vector element of $F_q$ and the code vectors is calculated. The clusters chosen for retrieval of the candidate list are the ones closest to the corresponding feature vectors, i.e., with lower euclidean distances. Since there is always a high probability of distortions in biometric data, we not only search in the first nearest cluster but in the next ones as well. The probable candidates for that feature element is searched for in the respective trees and the top b matches are retrieved. The minimum distances of the top b matches are initialized to a very large value like 10000. As the search for the candidate is started in the tree, the first child of the root becomes both the current and the head node. We keep traversing to the next sibling until the value of the first dimension ($\theta$ or d) of the current node data is less than the query one. The searching part is then done for child of the current node that it, current.child, becomes the new current node. The siblings before and after the current node are called as prev and next and they are also marked. In case, the euclidean distance between the first three dimensions of the head node and the query element is less than the top b matches and the type of minutiae of the two also matches, we replace the maximum of the b distances by this value and retrieve the id. In addition, if the above-calculated distance is less than a threshold D, the children of the head node are also searched thus updating the current node to head.child. The next sibling of the current head node is appointed as the new head. Further, the current node is updated to prev.child and next.child if the absolute difference between the first dimensional data of the current and query element is less than t. The procedure of retrieval of candidate list is presented in Algorithm 3.

The probable matches for all members of the feature vector are found using the method described above after which the score corresponding to each id in the database is computed as the percentage of votes it receives out of all the enrolled ids. A threshold s is set and if the score of any id is more than s, it is retrieved to be a part of the candidate list for that query. Apart from the matching score strategy, rank-based retrieval has also been done where the score of each id decides its rank and then the ids with top r ranks are retrieved.

4 Experimental results

The proposed approaches have been evaluated on the Fingerprint Verification Competition Databases (FVC) 2002 and 2004 each comprising four databases, viz., DB1, DB2, DB3 and DB4. Each of these contain eight fingerprints each from 100 different individuals making a total of 800 images.

For every user, six out of the eight images are randomly chosen to belong to the enrolled dataset while the remaining two images are used as test images. The information about the coordinates and the orientation with respect to the x-axis of the minutiae is extracted using the software Verifinger SDK. However, since core is required for the construction of triangle spiral, we have only used the templates having core in them.

Hit Rate and Penetration Rate are used to quantitatively measure the performance of the two methods. Hit Rate which is defined as the percentage of queries for which the correct id is retrieved in the candidate list is calculated as $H_r=(N_c/N)\times 100\,\%$, where $N_c$ = correctly indexed queries and N = total number of queries in the database. Penetration Rate gives the percentage of the enrolled templates searched for finding the correct match. It is computed as $P_r=(1/N\sum _{i=1}^{N}d_i/M)\times 100\,\%$, where $d_i$ = size of candidate list retrieved for i th image, N = total number of queries and M = size of the database.

The following two subsections present the results obtained upon indexing using the two proposed techniques.

4.1 Neighboring relation using rectangles results

To find the optimal value of the various parameters, numerous experiments were conducted. The values of the hit and penetration rate at different values of the parameters are listed in Tables 1, 2, 3, 4, 5. The so obtained optimum values are presented in bold in these tables.

Table 1 Hit rate and penetration rate for different values of T for FVC 2002 DB2

Table 2 Hit rate and penetration rate for different values of m for FVC 2002 DB2

Table 3 Hit rate and penetration rate for different values of t for FVC 2002 DB2

Table 4 Hit rate and penetration rate for different values of NN I and NN II for FVC 2002 DB2

Table 5 Hit rate and penetration rate for different values of D for FVC 2002 DB2

The length and breadth of the three rectangles are set at 320 and 70, respectively, as obtained from [28]. The threshold T is fixed at 100 such that if the size of the cluster > 100, it will divide into two new clusters, otherwise not. The best results are obtained when the order of the tree m is kept at 5, i.e., a 5-ary tree is made for all the clusters. For retrieval of the candidate list from the corresponding trees, top b matches are extracted. Owing to the high distortion in biometric databases, the search is carried out in the three nearest clusters thereby extracting NN I, NN II and NN III number of matching ids. For FVC 2002 DB1, their values come out to be 25, 16 and 0, respectively. As can be concluded from the table, the values of the other user-defined parameters D and t are 17 and 2, respectively. The best values of all the parameters involved in the method for all the databases have been tabulated in Table 6.

Table 6 Values of the user-defined parameters used in the experiments

Further, the hit rate and penetration rate at various matching score values and ranks for both FVC 2002 and 2004 databases are presented in Tables 7, 8, 9, 10 and Figs. 6, 7, 8, 9.

Table 7 Hit rate and penetration rate at various matching score values for FVC 2002 databases

4.2 Triangle spiral results

For the method of feature extraction using triangle spiral too, we found the suitable values of the parameters to be used during indexing. The results so obtained for FVC 2002 DB2 have been compiled in Tables 11, 12, 13, 14, 15, 16. The values that have been finally used are shown in bold.

The optimal value of the leg of the first right triangle $d_0$ is 10. Here, the limiting threshold above which the cluster divides into two is 70. The parameters used during retrieval viz., D and t should be fixed at 17 and 2, respectively. The order of the tree, m, at which the best results are obtained is five. We thus construct 5-ary trees for each cluster. During retrieval, the number of matches that are considered for matching in the three nearest clusters are denoted by NN I, NN II and NN III whose optimum values are 21, 14 and 7 as can be seen from the Table. The values of these parameters are present in Table 17 along with those obtained for the rest six databases.

Table 8 Hit rate and penetration rate at various ranks for FVC 2002 databases

Table 9 Hit rate and penetration rate at various matching score values for FVC 2004 databases

Table 10 Hit rate and penetration rate at various ranks for FVC 2004 databases

Using the above values, the hit rate and penetration rate at different score and rank have been found out and the results of the same have been tabulated in Tables 18, 19, 20 and 21, and depicted in Figs. 10, 11, 12 and 13.

The proposed methodology has been compared to various other indexing techniques over FVC 2002 and 2004 databases and the results of the approach which outperforms others have been presented in bold. As can be concluded from Table 22, our technique outperforms most of the proposed methods in the literature. We have reached a penetration rate lower than all the techniques except the one proposed by Jayaraman et al. [17] which achieves a lower penetration rate at the same hit rate. However, since they are not able to achieve a 100 % hit rate, we can conclude that our proposed approach can perform better than the existing state-of-the-art fingerprint indexing techniques.

Fig. 6

Miss rate and penetration rate vs matching score for FVC 2002 databases

Fig. 7

Miss rate and penetration rate vs rank for FVC 2002 databases

Fig. 8

Miss rate and penetration rate vs matching score for FVC 2004 databases

Fig. 9

Miss rate and penetration rate vs rank for FVC 2004 databases

Table 11 Hit rate and penetration rate for different values of T for FVC 2002 DB2

Table 12 Hit rate and penetration rate for different values of D for FVC 2002 DB2

Table 13 Hit rate and penetration rate for different values of m for FVC 2002 DB2

5 Conclusions

In this paper, we have proposed two robust techniques for extracting features to be used for fingerprint indexing. The first approach uses information of the neighboring minutiae lying inside the L rectangles to construct the feature vector while the second one involves construction of triangle spiral for each fingerprint. Our technique thus has the added advantage of lower complexity as opposed to the ones considering all possible minutiae triplets and quadruplets while extraction of features. Furthermore, dynamic clustering helps to automatically divide the data into an optimal number of clusters unlike k-means or other clustering algorithms where the number of clusters has to be provided beforehand. The dynamic nature of the biometric database has also been taken into consideration in our proposed approach as insertion and deletion is only to be carried out in the respective clusters without disturbing the remaining ones. The results also confirm that our proposed methodology works better than the existing ones. The method of feature extraction using multiline neighboring relation achieves a hit rate and penetration rate of 100 % and 2.1 %, 100 % and 3.1 %, 100 % and 3.1 %, and 100 % and 6.9 % for FVC 2002 DB1, DB2, DB3 and DB4, respectively. For FVC 2004 databases, the two rates achieved are 100 % and 5.0 %, 100 % and 7.4 %, and 100 % and 6.3 % for DB1, DB2 and DB4 respectively. On the other hand, if feature extraction is done by the construction of triangle spiral for each fingerprint, the results obtained are 100 % and 5.9 %, 100 % and 3.8 %, 100 % and 4.5 %, and 100 % and 5.3 % for FVC 2002 DB1, DB2, DB3 and DB4, respectively. The hit rate and penetration rate are 100 % and 7.2 %, 100 % and 8.0 %, and 100 % and 7.8 % for FVC 2004 DB1, DB2 and DB4 respectively. Further, the dynamic clustering used in this paper narrows down the search space of a fingerprint database.

Table 14 Hit rate and penetration rate for different values of t for FVC 2002 DB2

Table 15 Hit rate and penetration rate for different values of $d_0$ for FVC 2002 DB2

Table 16 Hit rate and penetration rate for different values of N.N. I, N.N. II and N.N. III for FVC 2002 DB2

Table 17 Values of the user defined parameters used in the experiments

Table 18 Hit rate and penetration rate at various matching score values for FVC 2002 databases

Table 19 Hit rate and penetration rate at various ranks for FVC 2002 databases

Table 20 Hit rate and penetration rate at various matching score values for FVC 2004 databases

Table 21 Hit rate and penetration rate at various ranks for FVC 2004 databases

Fig. 10

Miss rate and penetration rate vs matching score for FVC 2002 databases

Fig. 11

Miss rate and penetration rate vs rank for FVC 2002 databases

Fig. 12

Miss rate and penetration rate vs matching score for FVC 2004 databases

Fig. 13

Miss rate and penetration rate vs rank for FVC 2004 databases

Table 22 Comparison with other indexing techniques