Abstract: A low computational cost cancelable fingerprint template, namely the multi-line codes was proposed. The formulation of a single-line code involves the inspection of minutiae distribution along a straight line constructed based on the reference minutia. Multi-line code is introduced to elevate the performance by combining several single-line codes. Experiments were carried out on a few FVC databases. It has been proven that the proposed method yields relatively low computational complexity as compared to existing minutiae distribution-based methods, while preserving the performance. The equal error rate obtained for FVC2002 DB1 is 4.69% in stolen-key case, and the total arithmetic operations utilized are 14 520 additions and zero multiplication. Key words: cancelable fingerprint template; multi-line code; single-line code; stolen-key case
1 Introduction
Biometric authentication systems offer a great range of advantages over the conventional information-based and token-based authentication systems, such as passwords, user IDs, identification cards and PINs. Biometric traits that are used in biometric authentication systems include fingerprint, hand geometry, face, iris, signature and voice. These biometric traits provide uniqueness and permanence to the user’s identity. However, once the biometric database is compromised, the authentication system cannot be restored due to the aforementioned characteristics of biometric traits. Therefore, biometric template protection schemes are required to shield the original biometric information. Cancelable biometrics is one of the solutions. It imposes a systematic transformation to the derived biometric features to protect the original biometric information. If a cancelable biometric template is compromised, the transformation parameters can be changed and the user biometrics is mapped onto a new template, which replaces the compromised template. The three principle objectives of cancelable biometrics are [1]:
1) Non-reversibility: It should be computationally infeasible to recover the original biometric data from the biometric template.
2) Accuracy: The accuracy of fingerprint recognition should not deteriorate after transformation.
3) Diversity: No same biometric template can be
used in various applications. This leads to revocability, of which new template can be reissued in the event of compromise.
Recently, various cancelable biometrics generation schemes have been proposed. ANG et al [2] presented a geometric transformation based on the reflection of minutiae. In this approach, a line passing through the core point is drawn, and the minutiae below the line are reflected while the minutiae above remain. The gradient of the line is determined by a user-specific key. Confusion occurs when dealing with fingerprints with no core point (arch) and with more than one core point (whorl).
On the other hand, TULYAKOV et al [3−4] used symmetric hash functions to convert the minutiae into hash values. In this algorithm, a minutia is represented by a complex number ci. For each minutia in the fingerprint, a triplet (ci, cj, ck) is formed with its two nearest neighboring minutiae and is hashed using pre-defined hash functions. This work was extended [5] by combining more than one hash functions during implementation to increase the security of the template. Also, k-plets of minutiae were used instead of triplets, where k can be more than three.
For aforementioned approaches, matching of fingerprint templates requires pre-alignment of the minutiae. This increases the computational time during fingerprint matching and thus reduces its applicability in real-time authentication systems. One of the solutions of eliminating minutiae alignment is to use invariant
Received date: 2012−08−21; Accepted date: 2012−12−10 Corresponding author: WONG Wei-jing; Tel: +60−82−415353; E-mail: [email protected]
J. Cent. South Univ. (2013) 20: 1292−1297
1293
features of minutiae in the generation of fingerprint template as proposed by LEE et al [6]. These features are extracted following the same fashion as in Ref. [7]. Together with a user-specific PIN, the invariant features are used to parameterize two changing functions which contribute to the transformation of the minutiae, namely the distance-changing function and the orientation- changing function. Another cancelable template utilizing invariant features based on triplets was proposed by FAROOQ et al [8]. The features measured are the lengths of the three sides, the orientations of the three vertex minutiae and the height of the longest side of a triplet. The template is a binary string of quantized feature values, so it requires less database storage as compared to Ref. [6].
A bit-string representation of fingerprint template was introduced by LEE et al [9], where each minutia is described by a three-dimensional array. The width and height of the three-dimensional array is the x-y plane of the fingerprint image, while the depth represents the orientation of minutiae. The array is divided into cells of equal size, and the numbers of minutiae in the cells form the final bit-string. Other string-based cancelable fingerprint templates were presented in Refs. [10−12].
One of the state-of-the-art fingerprint template representations is called the minutiae cylinder-code (MCC) [13]. It forms a cylinder around a minutia and the cylinder is tessellated in the similar manner as in Ref. [9]. Instead of counting the number of minutiae in the cells, MCC considers all minutiae around the cell within certain range. The contribution of each minutia towards the cell value is regulated by its positional and orientation distance from the center of the cell. Such approach uses the basis of fixed radius-based minutia descriptor without neglecting the area outside but nearby the perimeter.
BioHashing [14−15] is the pioneer of correlation- based template protection schemes. BioHashing employs the wavelet Fourier-Mellin transform (WFMT) features of fingerprints in the transformation. The transformation involves inner product of the WFMT features with a user-specific tokenized key. User-dependent multi-state discretization was used [16] in the generation of binary bit-string to improve the performance of BioHashing specifically for stolen-token scenario.
A minutiae-distribution based cancelable fingerprint template generation method is proposed in this work. The fingerprint template is represented in a number string, which is a composition of several specially designed minutia codes, namely the multi-line codes. It is extended from our previous work [17]. 2 Proposed scheme
Figure 1 provides an overview of the proposed
system. The entire fingerprint verification system comprises of four main stages: minutiae extraction, multi-line code generation, multi-line code permutation and fingerprint matching. 2.1 Minutiae extraction
Since multi-line code is a minutiae-based template protection scheme, a decent minutiae extraction process is vital for its performance. The technique mainly consists of six stages segmentation, orientation field estimation, contextual filtering, binarization, thinning and minutiae detection. Each of the stages is explained in detail as follows:
1) Segmentation: Segmentation of the fingerprint image serves the purpose of separating the actual fingerprint area (also called the region of interest) from the background. A variance-based method was applied in our scheme. The fingerprint image is divided into blocks of equal size (w×w) and the variance of every block is calculated as
w
i
w
j
IjiIw
I1 1
22
2 ))(),((1
)( (1)
where μ(I) is the mean pixel value of the image block. If the variance of a block is less than the threshold value, τs, it is assigned as a background block, otherwise, the image block is considered as a foreground block.
2) Orientation field estimation: The gradient-based orientation estimation method was used. Similar to segmentation, the estimation of orientation field is also a block-wise operation, except that overlapping blocks are used here. The orientation of each block is calculated by
1 11
2 2
1 1
2 ( , ) ( , )1 π
tan2 2( , ) ( , )
w w
x yi j
w w
x yi j
i j i j
i j i j
g g
g g (2)
where gx(i, j) and gy(i, j) are the gradient vectors of the block centered at pixel (i, j) in x and y directions, respectively.
3) Contextual filtering: Contextual filtering approach used in Ref. [18] was adopted to enhance the fingerprint image. A fourth order band-pass Butterworth filter is applied to the image in the Fourier domain to remove noise while preserving the structures of the fingerprint.
4) Binarization: This is a simple thresholding process which converts the original gray-scale image into a black and white binary image.
5) Thinning: Image thinning reduces the ridges of the fingerprint to one pixel wide to facilitate the next step. The parallel thinning algorithm described in Ref. [19] was adapted into our minutiae extraction method.
Fig. 1 Overview of fingerprint verification system applying multi-line code
6) Minutiae detection: This step identifies the endpoints and bifurcation points of the ridges. The concept of crossing number is widely used for skeleton image-based minutiae detection. The crossing number [20] of a pixel x is defined as
8
11C 2
1)(
iii xxxN (3)
where xi is the pixel value of the eight neighbours traversing around x. NC(x)=1 is identified as an endpoint whereas NC(x)=3 represents a bifurcation point. 2.2 Line code generation
In the proposed scheme, we first construct a straight line of length l centered at the reference minutia, P(xr, yr). The orientation of the line is equivalent to the orientation of P, and is denoted by θr. On the line, we take s sample points uniformly distributed with distance, d in between one another so that s=l/d+1. The position of the sample points is calculated by xsi=xr+i×d (4) ysi=yr+i×d (5)
for }2
1
2
1|{
si
si and given dx=d×cosθ and
dy=d×sinθ. For each sample point, we apply a circular bit-wise
and mask (with radius r) to obtain the number of minutiae within the area in different angular partitions, Δφ. The angular partition that a minutia falls in is determined by the relative angle between θr and the orientation of the neighboring minutia. Figure 2 provides a visual illustration of the proposed method.
In Fig. 2(b), the number of minutiae in each over- lapping cylinder (left region and right region are separated) are arranged sequentially to form a line code that describes the reference minutia, P. Therefore, it can be written as L{a1a2 … an … aN}, where N=2×m×s, is the length of the line code, m=2π/Δφ, is the number of angular divisions, and s is the total number of sample points on the line. an is assigned an invalid value of −1 if the sample point is located outside the boundaries of the fingerprint image. In a nutshell, a fingerprint template can be concluded as F{L1L2…LK}, where K is the total number of minutiae in the fingerprint. 2.3 Line code permutation
In order to achieve revocability and diversity of the template, we have to introduce an external factor that
J. Cent. South Univ. (2013) 20: 1292−1297
1295
Fig. 2 Illustration of proposed scheme: (a) Plane view with
minutiae; (b) 3D view
offers huge variety of transformations onto the generated line code. In this work, we simply permute the code based on a user specific secret key. The secret key, obtained from a pseudo-random number generator (PRNG), will seed the permutation order of the minutia code. It is important to ensure that no two individuals or two applications of one individual can be assigned the same key. Therefore, the PRNG should generate random numbers with no duplicate.
In addition, permutation of the line code improves the performance of cancelable fingerprint template. By introducing a unique “personality” to every fingerprint, it greatly reduces the false acceptance rate (FAR) of the system. 2.4 Fingerprint matching 2.4.1 Local similarity score
Given a line code Lt from the template fingerprint (TF{L1L2…LT}) and a line code Lq from the query fingerprint (QF{L1L2…LQ}), where T and Q are the total numbers of minutiae in TF and QF, respectively. The local similarity score between Lt and Lq signifies the likelihood of Lq in QF being a correspondence to Lt in TF. We use Dice’s coefficient [21] to measure the similarity between
two line codes in our proposed scheme. The similarity score between Lt and Lq can be formulated as
otherwise ,
2
invalid are or either of 50% than more ,0
),(
22
1
n
i
n
i qt
n
i qt
qt
ii
ii
aa
aa
LL
qtS
(6) for }1),(0|{),( qtSqtS R . Similarity of 0 indicates a total mismatch between Lt and Lq, while 1 indicates a perfect match between them.
During fingerprint matching, each line code in QF is cross-matched with every line code in TF, so we will have a similarity matrix containing similarity scores among all line codes between two fingerprints. Each element in the similarity matrix is then re-evaluated with the following criterion to eliminate double-matching:
otherwise ,0
1condition ),,(),(
qtSqtS (7)
where condition 1 implies that S(t, q) must be the maximum among all values of S(t, l) (for ],1[ Qi ) and S(l, q) (for ],1[ Ti ). 2.4.2 Global matching score
To perform overall matching between TF and QF, a global matching score is used to measure the likelihood of TF and QF being two instances of the same fingerprint. From the similarity matrix obtained by Eqs. (6) and (7), we calculate the matching score with the following formula [9]:
)0),((#
),(1 1
M
qtS
qtS
S
T
t
Q
q (8)
3 Results and discussion 3.1 Parameters tuning
Prior to the testing, a series of experiments are carried out on a smaller dataset (set B of FVC2002 DB1, DB2 and FVC2004 DB1) to fine-tune the parameters so that the results obtained in Section 2.4 is optimal. The parameters under consideration are listed in Table 1, accompanied by the values which produce the best performance.
Table 1 Variable parameters of proposed method
Parameter symbol Description Value
l Length of line 320
d Distance between two
sample points 8
Δφ Range of angular division π
r Radius threshold of minutiae
around a sample point 25
J. Cent. South Univ. (2013) 20: 1292−1297
1296
Through experiments, we discovered that using more than one line to describe a minutia improves the performance of single-line code representation. This is because with multiple lines of different directions, we can capture not only the minutiae distribution along the dominant orientation, but also information in other directions. However, adding in a line greatly increases the computational complexity and the template size. In order to balance the trade-off between accuracy and computational complexity, we use three lines per minutia in this work. Hence, the multi-line code relating to a minutia can be written as LM{LθrLθr+π/3Lθr+2π/3}. 3.2 Experimental setup
The proposed algorithm is evaluated on fingerprint images taken from FVC2002 DB1, DB2 and FVC2004 DB1. Each dataset contains 100 fingerprints, and each fingerprint has 8 samples with different ways and levels of perturbations. We enroll the first impression of every fingerprint as the template and use the remaining seven impressions to match against the templates, and thus resulting in 70 000 tests in total, which include 700 genuine tests and 69 300 imposter tests for each dataset. 3.3 Accuracy
Table 2 provides a comparison of EER between the proposed algorithm and other minutiae distribution-based algorithms [9, 13]. It is notable that the performance of the proposed cancelable template is ideal (zero EER) and the secret key is secure. However, if the key is compromised, the EER increases due to intra-class variation and inter-class similarity among the fingerprints. Note that the proposed algorithm performs as well as Lee’s algorithm while using FVC2004 DB1, that is, both algorithms yield an EER of approximately 10.3%. Figure 3 shows the ROC curves of the proposed algorithm. 3.4 Computational complexity
One of the metrics of measuring computational
Table 2 EER of proposed algorithm and other existing
algorithms
EER/% Algorithm
Genuine-k Stolen-key
Fingerprint database used
Multi-line code
(proposed)
0
0
0
4.69
5.03
10.36
FVC2002 DB1
FVC2002 DB2
FVC2004 DB1
Lee’s algorithm [9]
0
0
0
10.3
9.5
6.8
FVC2004 DB1
FVC2004 DB2
FVC2004 DB3
Minutia
cylinder-code [13]
(without relaxation)
— 0.33 FVC2006 DB2
Fig. 3 ROC curves of proposed method tested on various
datasets complexity is by evaluating the number of arithmetic operations used in the algorithm. In particular, the operations we consider in this work are additions (hereafter denoted by A) and multiplications (hereafter denoted by M). The values of trigonometric functions are usually pre-calculated and thus can be implemented with lookup tables.
Even though the proposed method is alignment-free, it requires calculation of the positions of sample points for each reference minutia. In Eqs. (4) and (5), since we assume that the trigonometric functions are pre- calculated, i×dx and i×dy can also be treated as constants. Therefore, it requires only 2A and no M. From experiments, the average number of minutiae contributing to a sample point is 2, so we need an average of 1A to sum up the number of neighboring minutiae around a sample point. Let s be the number of sample points on a single line and k be the total number of minutiae, the total arithmetic operations involved in the generation of a fingerprint template (multi-line codes) is {k×3[(s−1)×2+s×1]}. According to the parameter values given in Table 1, we get s=41. Table 3 summarizes the computational complexity of the proposed algorithm and the referencing algorithms when Table 3 Number of mathematical operations required in
computation of fingerprint template Algorithm Number of operations
Multi-line code (proposed) a 14 520 A
Lee’s algorithm [9] a 4 680 A + 6 240 M
Minutia cylinder-code [13]
(without relaxation) b 230 240 A + 201 660 M
a: Complexity of permutation is excluded so that figures are
comparable with Ref. [13]; b: Complexity of algorithm is not
reported in original paper, so estimation is based on our own
assumptions. High complexity shown is mostly caused by
calculation of Gaussian-based contribution value for each cell
in cylinders.
J. Cent. South Univ. (2013) 20: 1292−1297
1297
k=40. The inputs of most of the arithmetic operations are x and y coordinates of the minutiae. Assuming that the dimension of a fingerprint image does not exceed 1 024 × 1 024, 10-bit (210=1 024) binary A’s and M’s are sufficient enough for the calculations. Knowing that a 10-bit M is 9 times more complex than a 10-bit A, we can conclude that the proposed algorithm yields the lowest computational complexity among the three. 3.5 Revocability
The revocability (or cancelability) of a cancelable template can be assessed by the number of possible templates that the algorithm is able to produce out of one fingerprint. Since the revocability of the proposed scheme is engendered by the permutation of multi-line code, the variety of templates generated from one fingerprint depends on the length of the code. With the given parameters in Table 1, we can conclude that the length of the multi-line code is 1 476. Therefore, there are 1 476! possible permutations for each database, and can accommodate more than a hundred worldwide applications. 4 Conclusions
1) Non-invertibility of the transformation is taken care by the many-to-one mapping while grouping minutiae.
2) As a result of alignment-free implementation and inspection of minutiae in a reduced dimension, the proposed method establishes a relatively low computational cost whilst preserving the recognition accuracy.
3) Permutation of the multi-line codes provides diversity and revocability to the proposed scheme.
4) However, the proposed method requires large storage capacity as the template is stored as a real number string. We can resolve this by converting the resulting number string into a bit string. A reliable quantization method is required to prevent or minimize the decay in performance after conversion. Furthermore, some other distinctive features have to be introduced to ameliorate the EER value. References [1] MALTONI D, MAIO D, JAIN A K, PRABHAKAR S. Handbook of
