ChenJainIndividuality_ICB09

Beyond Minutiae: A Fingerprint Individuality Model with Pattern, Ridge and Pore Features Yi Chen1,2 and Anil. K. Jain1 1 Michigan State University 2 DigitalPersona Inc. Abstract. Fingerprints are considered to be unique because they con- tain various distinctive features, including minutiae, ridges, pores, etc. Some attempts have been made to model the minutiae in order to get a quantitative measure for uniqueness or individuality of fingerprints. However, these models do not fully exploit information contained in non- minutiae features that is utilized for matching fingerprints in practice. We propose an individuality model that incorporates all three levels of fingerprint features: pattern or class type (Level 1), minutiae and ridges (Level 2), and pores (Level 3). Correlations among these features and their distributions are also taken into account in our model. Experimen- tal results show that the theoretical estimates of fingerprint individuality using our model consistently follow the empirical values based on the public domain NIST-4 database. Key words: fingerprint individuality, statistical models, probability of random correspondence (PRC), minutiae, ridges, pores 1 Introduction A number of court challenges have brought into question the validity and re- liability of using fingerprints for personal identification [1–3]. These challenges are based on, among other factors, the lack of (i) conclusive evidence to sup- port the claim of fingerprint uniqueness, and (ii) scientific evaluation of criteria used to determine a match between two fingerprints. These legal challenges have generated substantial interest in studies on fingerprint individuality. Fingerprint individuality can be formulated as the probability that any two prints from different fingers will be “sufficiently” similar. Because similarity be- tween fingerprints is often quantitatively defined based on the similarity of fin- gerprint features, it is equivalent to finding the probability of random correspon- dence (PRC), or the probability of matching k features, given that two impostor fingerprints contain m and n features, respectively. The key to calculating PRC is to model the distribution of fingerprint features, as it is not only the number of features, but also their spatial distributions that account for individuality. The variety of features that are incorporated in the individuality model is also important. Latent experts use three levels of features, namely, Level 1 (e.g., pat- tern), Level 2 (e.g., minutiae and ridges) and Level 3 (e.g., pores) in fingerprint matching [4]. All of these features are believed to be distinctive and unique and should be considered in the individuality model (see Fig. 1). To appear at the International Conf. on Biometrics (ICB), June 2009 2 Yi Chen and Anil. K. Jain pore ridge minutiae rige loop type whorl type (a) (b) Fig. 1. Fingerprint features (a) two different pattern types (b) minutiae, ridges and pores. To learn the spatial distribution of fingerprint features, a couple of generative models have been proposed [5, 6]. Pankanti et al. [5] modeled the minutiae as uniformly and independently distributed, however, it has been empirically deter- mined that minutiae tend to cluster where ridge directions change abruptly, with higher density in the core and delta regions [7, 8]. To account for this clustering tendency of minutiae, Zhu et al. [6] proposed a finger-specific mixture model, in which minutiae are first clustered and then independently modeled in each cluster. In modeling features other than minutiae, Fang et al. [9] modeled ridges by classifying the ridge segment associated with each minutia into one of sixteen ridge shapes. However, most of the ridge shapes used in this model were quite rare as the ridge segments associated with minutiae either terminate or bifur- cate. Roddy and Stosz [10] proposed to approximate the spatial distribution of pores using a discrete grid, and consequently, their formulation is sensitive to distortion as well as the size and the position of the grid cells. 2 Proposed Model We propose to evaluate fingerprint individuality by modeling the distribution of minutiae, ridge and pore features. In particular, the minutiae and ridge fea- tures are separately modeled for each fingerprint pattern type (whorl, left loop, right loop, arch and tented arch). This is because minutiae and ridge feature distributions are highly correlated with the fingerprint pattern [8], which was also demonstrated by Zhu et al [6]. Compared to finger-specific models, pattern- specific models can be easily generalized to different target populations and are less prone to overfitting, especially when the number of minutiae in a finger- print is small. To model ridges and pores, transform-invariant features such as ridge period, ridge curvature, and pore spacing associated with each minutia are derived. 2.1 Pattern-specific Minutiae Modeling Given a large database of fingerprints, we assign each image to one of the five ma- jor pattern types [11]: whorl, left loop, right loop, arch and tented arch. For each fingerprint class, minutiae from fingerprints in that class are consolidated and their spatial distribution is estimated. These minutiae are grouped into clusters To appear at the International Conf. on Biometrics (ICB), June 2009 Title Suppressed Due to Excessive Length 3 based on their positions (X) and directions (O) using the EM algorithm [12]. In each cluster, the minutiae position X is modeled by a bivariate Gaussian distri- bution and the minutiae direction O is modeled using a Von-Mises distribution [6]. Each minutia m(X,O) in a fingerprint of class G has the following mixture density: f(x, o|ΘG) = NG∑ g=1 τg · fX(x|µg, Σg) · fO(o|νg, κg), (1) where NG is the number of clusters in the mixture for class G, τg is the weight for the g-th cluster, ΘG is the set of parameters describing the distributions in each cluster, fX(x|µg, Σg) is the p.d.f. over minutiae position in the g-th cluster, and fO(o|νg, κg) is the p.d.f. over minutiae direction in the g-th cluster. Minu- tiae in the same cluster have the same distribution of directions, establishing a dependence between minutiae position and direction. Let T be a fingerprint belonging to class G with minutiae density f(x, o|ΘG). Similarly, let Q be a fingerprint belonging to class H with minutiae density f(x, o|ΘH). Let m(XT , OT ) and m(XQ, OQ) be two minutiae from T and Q, respectively. The probability that these two minutiae would match is defined as P (|XT −XQ| ≤ x0, |OT −OQ| ≤ o0|ΘG, ΘH) (2) = NG∑ g=1 NH∑ h=1 τg · τh · P (|XT −XQ| ≤ x0|µg, µh, Σg, Σh) · P (|OT −OQ| ≤ o0|νg, νh, κg, κh), where parameters x0 = 15 pixels and o0 = 22.5 degrees are used as tolerances. Note that this probability can be directly computed since (XT −XQ) follows a 2D Gaussian distribution with mean (µg − µh) and covariance (Σg + Σh); and (OT−OQ) can be approximated by a Von-Mises distribution with mean (νg−νh) and variance κg,h defined as [13]: A(κg,h) = A(κg)A(κh), (3) A(x) = 1− 12 − 18x2 − 18x3 + o(x−3). (4) Finally, the PRC, or the probability of matching k pairs of minutiae between Q and T , is calculated as [6] p(m,n, k) = e−λ · λk k! , λ = mnl, (5) where m and n are the number of minutiae in Q and T , respectively, and l = P (|XT − XQ| ≤ x0, |OT − OQ| ≤ o0|ΘG, ΘH) is the probability calcu- lated in Eq. (2). This PRC calculation corresponds to the Poisson probability mass function with mean λ = mnl, which can be interpreted as the expected number of matches from the total number of mn possible pairings between Q and T with the probability of each match being l. To appear at the International Conf. on Biometrics (ICB), June 2009 4 Yi Chen and Anil. K. Jain 2.2 Pattern-specific Ridge Modeling To incorporate ridge features in the model, we extend the density function in Eq. (1) to the following mixture density for class G: f(x, o, r, c|ΘG) = NG∑ g=1 τg · fX(x|µg, Σg) · fO(o|νg, κg) · fR(r|ωg, σ2g) · fC(c|λg), (6) where fR(r|ωg, σ2g) and fC(c|λg) are the probability density functions of ridge period and ridge curvature associated with each minutia in the g-th cluster, re- spectively. We use a Gaussian distribution to model ridge period because ridge period only fluctuates towards the tip (smaller) and flexion crease (larger) re- gions. Ridge curvature, on the other hand, is usually low except near the core and delta regions, and is modeled by a Poisson distribution. Note that minutiae in the same cluster have the same distribution of direction, ridge period and curvature, hence, establishing a dependency among these features. 1 2 3 1 2 3 Fig. 2. Converting local ridge structure to a canonical form such that matching two minutiae and their associated ridges is equivalent to matching the position and direction of minutiae and the period and curvature of the ridges. Let T be a fingerprint belonging to classG with minutiae density f(x, o, r, c|ΘG). Similarly, let Q be a fingerprint belonging to class H with minutiae density f(x, o, r, c|ΘH). Let m(XT , OT , RT , CT ) and m(XQ, OQ, RQ, CQ) be two minu- tiae from T and Q, respectively. The probability that these two minutiae would match is then defined as P (|XT −XQ| ≤ x0, |OT −OQ| ≤ o0, |RT −RQ| ≤ r0, |CT − CQ| ≤ c0|ΘG, ΘH) = NG∑ g=1 NH∑ h=1 τg · τh · P (|XT −XQ| ≤ x0|µg, µh, Σg, Σh) · P (|OT −OQ| ≤ o0|νg, νh, κg, κh) ·P (|RT −RQ| ≤ r0|ωg, ωh, σ2g , σ2h) · P (|CT − CQ| ≤ c0|λg, λh), (7) To appear at the International Conf. on Biometrics (ICB), June 2009 Title Suppressed Due to Excessive Length 5 where r0 = 2 and c0 = 2. Here, matching the ridges associated with two minutiae is equivalent to matching the ridge period and curvature after converting the ridge structure associated with each minutia to a canonical form centered at the minutia and rotated by the minutia direction (see Fig. 2). Similar to Eq. (2), this probability can be directly computed since (RT − RQ) follows a Gaussian distribution with mean (ωg−ωh) and variance (σ2g +σ2h) and (CT −CQ) follows a Skellam distribution [14] with mean (λg − λh) and variance (λg + λh). The final PRC is again computed as in Eq. (5), except that l is replaced by Eq. (7). 2.3 Pore Modeling Since pores are almost evenly spaced along the ridges [10], modeling pores can be approximated by modeling the intra-ridge spacing of pores on modeled ridges. As a result, each minutia and its local features (position X, direction O, ridge period R, ridge curvature C and pore spacing S) have the following mixture density for fingerprints from class G: f(x, o, r, c, s|ΘG) = (8) NG∑ g=1 τg · fX(x|µg, Σg) · fO(o|νg, κg) · fR(r|ωg, σ2g) · fC(c|λg) · fS(s|µp, σ2p), where fS(s|µp, σ2p) is the probability density function for pore spacing. Because there is no evidence that intra-ridge pore spacing is dependent on minutiae location or ridge flow patterns, pore spacing is not clustered. Let T be a fingerprint belonging to classG with minutiae density f(x, o, r, c, s|ΘG). Similarly, let Q be a fingerprint belonging to class H with minutiae density f(x, o, r, c, s|ΘH). Let m(XT , OT , RT , CT , ST ) and m(XQ, OQ, RQ, CQ, SQ) be two minutiae from T and Q, respectively. The probability of matching the two minutiae features can be calculated as follows: P (|XT −XQ| ≤ x0, |OT −OQ| ≤ o0, |RT −RQ| ≤ r0, |CT − CQ| ≤ c0, |ST − SQ| ≤ s0 |ΘG, ΘH) = NG∑ g=1 NH∑ h=1 τg · τh · P (|XT −XQ| ≤ x0|µg, µh, Σg, Σh) ·P (|OT −OQ| ≤ o0|νg, νh, κg, κh) · P (|RT −RQ| ≤ r0|ωg, ωh, σ2g , σ2h) ·P (|CT − CQ| ≤ c0|λg, λh) · P (|ST − SQ| ≤ s0|σ2p), (9) where s0 = 2. Again, this probability can be directly calculated since (ST −SQ) follows a Gaussian distribution with mean 0 and variance 2σ2p. Again, PRC is still computed as in Eq. (5), except that l is now replaced by Eq. (9). Note that after incorporating ridge and pore features in our individuality model, PRC represents the probability of matching k minutiae not only in their positions and directions, but also with respect to the local ridge period and curvature as well as pore spacing in the neighborhood of the matching minutiae. 3 Model Evaluation and Validation In order to demonstrate the utility of our individuality model, we perform the following evaluation protocol: (i) learn the mixture density of minutiae and their To appear at the International Conf. on Biometrics (ICB), June 2009 6 Yi Chen and Anil. K. Jain local ridge and pore features, (ii) compute the theoretical probability of random correspondence (PRC), and (iii) compare the theoretical PRC with the empir- ical values obtained on a public database. The database used for evaluation is the NIST Special Database 4 (NIST-4) [16], which contains 2,000 pairs (4,000 images) of inked rolled prints at 500 ppi. Rolls are appropriate for fingerprint in- dividuality study because they provide a complete representation of fingerprints. Each fingerprint in NIST-4 comes with a class label (28.2% right loop, 26.6% left loop, 21.5% whorl, 19% arch and 4.7% tented arch) assigned by forensic experts. These prints are manually aligned by the author based on the locations of core(s). For example, fingerprints of the left loop, right loop and tented arch classes are aligned at the core point; fingerprints of the whorl class are aligned at the centroid of the two cores; and fingerprints of the arch class are aligned at the highest curvature point on the most upthrusting ridge. Figure 3 shows the empirical distribution of minutiae positions from fingerprints in each of the five classes. It can be observed that the minutiae distribution is highly correlated with the fingerprint class. Note the higher minutiae density in the core and delta regions, which is consistent with Champod’s finding [8]. 100 200 300 400 500 600 100 200 300 400 500 600 100 200 300 400 500 600 100 200 300 400 500 600 100 200 300 400 500 600 100 200 300 400 500 600 100 200 300 400 500 600 100 200 300 400 500 600 100 200 300 400 500 600 100 200 300 400 500 600 (a) (b) (c) (d) (e) Fig. 3. Distribution of minutiae positions (empirically extracted [20]) in each of the five fingerprint classes (a) arch, (b) tented arch, (c) left loop, (d) right loop, and (e) whorl, obtained from 4,000 rolled fingerprints in NIST-4. The darker the area, the higher the minutiae density. These plots (with size 600 × 600) were smoothed using a disk filter with a radius of 25 pixels. The center of each plot corresponds to the alignment origin. The theoretic probability of matching a minutiae pair between impostor fin- gerprints of each class is calculated using Equation 2. As shown in Table 1, impostor fingerprints from the same class have a higher matching probability (highlighted in gray) than those from different classes. This is consistent with the results of Jain et al.’s study [18], which revealed that fingerprints from the same class are more likely to be matched (have higher False Accept Rate) than fingerprints from difference classes. For comparison, we also calculate the empirical probabilities of matching a minutiae pair between impostor fingerprints based on NIST-4. An in-house fingerprint matcher [15] was used to automatically establish minutiae correspon- dences between the impostor pairs in NIST-4. To be compatible with our model, the matcher is restricted to register fingerprints within a 50× 50 neighborhood of the manually aligned origin. A total of 7, 998, 000 impostor matches were conducted and the empirical probability of matching a minutiae pair between To appear at the International Conf. on Biometrics (ICB), June 2009 Title Suppressed Due to Excessive Length 7 Table 1. Theoretical probabilities of matching a minutiae pair between impostor fin- gerprints belonging to class A=arch, TA=tented arch, L=left loop, R=right loop and W=whorl based on the proposed model. Type A TA L R W A 13.20× 10−4 6.05× 10−4 6.33× 10−4 3.95× 10−4 4.65× 10−4 TA 6.05× 10−4 12.76× 10−4 6.85× 10−4 5.01× 10−4 6.40× 10−4 L 6.33× 10−4 6.85× 10−4 10.95× 10−4 7.44× 10−4 4.92× 10−4 R 3.95× 10−4 5.01× 10−4 7.44× 10−4 11.59× 10−4 4.74× 10−4 W 4.65× 10−4 6.40× 10−4 4.92× 10−4 4.74× 10−4 10.01× 10−4 Table 2. Empirical probabilities of matching a minutiae pair between impostor fin- gerprints belonging to class A=arch, TA=tented arch, L=left loop, R=right loop and W=whorl based on NIST-4. Type A TA L R W A 14.33× 10−4 12.25× 10−4 7.73× 10−4 8.31× 10−4 2.35× 10−4 TA 12.25× 10−4 12.54× 10−4 8.33× 10−4 9.17× 10−4 2.61× 10−4 L 7.73× 10−4 8.33× 10−4 11.46× 10−4 5.92× 10−4 4.36× 10−4 R 8.31× 10−4 9.17× 10−4 5.92× 10−4 11.54× 10−4 4.64× 10−4 W 2.35× 10−4 2.61× 10−4 4.36× 10−4 4.64× 10−4 6.36× 10−4 two impostor prints is computed by the average of k/(m × n), where k is the number of matched minutiae and m and n are the number of minutiae in the two fingerprints. This probability is tabulated by the fingerprint class informa- tion, resulting in all possible intra-class and inter-class probability values (see Table 2). Note that the theoretical probabilities based on our model are closer to empirical probabilities (with correlation coefficient 0.59) compared to those calculated by Zhu et al.’s model (empirical probability = 1.8× 10−3, theoretical probability = 6.50× 10−4) [6]. h r (a) (b) Fig. 4. Ridge features in a neighborhood (30 × 30 pixels) of a minutia. (a) ridge period (average of inter-ridge distance h), and (b) ridge curvature (inverse of radius r). To incorporate ridge features, we extract ridge period and curvature in a 30 × 30 neighborhood of each minutia (see Fig. 4). Ridge period is calculated as the average inter-ridge distances, and ridge curvature, defined as the inverse of its radius, is calculated by the second derivative of sampled ridge points. In the model, these features are used to retrain the clustering algorithm and reevaluate the theoretical probability in Equation 7. In the empirical case, minutiae cor- To appear at the International Conf. on Biometrics (ICB), June 2009 8 Yi Chen and Anil. K. Jain respondences that disagree in ridge period or curvature (with difference larger than r0 and c0, respectively) are removed. The resulting number of matched minutiae pairs k′ is used to recalculate the empirical probability as the aver- age of k′/(m× n). The theoretical and empirical matching probability matrices tabulated by fingerprint class information after incorporating the ridge features are shown in Tables 3 and 4, respectively. As we can see, higher probabilities are still observed among impostor fingerprints from the same class than those from different classes. The use of ridge features reduces the probability of ran- dom minutiae correspondence both empirically and theoretically; the correlation coefficient between the two probability matrices is increased to 0.67. Table 3. Theoretical probabilities of matching a minutiae pair and their local ridge features between impostor fingerprints belonging to class A=arch, TA=tented arch, L=left loop, R=right loop and W=whorl based on the proposed model. Type A TA L R W A 6.21× 10−4 2.59× 10−4 2.62× 10−4 1.74× 10−4 1.88× 10−4 TA 2.59× 10−4 6.06× 10−4 3.36× 10−4 2.40× 10−4 2.92× 10−4 L 2.62× 10−4 3.36× 10−4 5.52× 10−4 3.71× 10−4 2.24× 10−4 R 1.74× 10−4 2.40× 10−4 3.71× 10−4 5.99× 10−4 2.21× 10−4 W 1.88× 10−4 2.92× 10−4 2.24× 10−4 2.21× 10−4 4.56× 10−4 Table 4. Empirical probabilities of matching a minutiae pair and their local ridge features between impostor fingerprints belonging to class A=arch, TA=tented arch, L=left loop, R=right loop and W=whorl based on NIST-4. Type A TA L R W A 5.86× 10−4 4.70× 10−4 2.91× 10−4 3.10× 10−4 0.84× 10−4 TA 4.70× 10−4 5.68× 10−4 3.68× 10−4 3.89× 10−4 1.07× 10−4 L 2.91× 10−4 3.68× 10−4 5.05× 10−4 2.39× 10−4 1.79× 10−4 R 3.10× 10−4 3.89× 10−4 2.39× 10−4 5.12× 10−4 1.93× 10−4 W 0.84× 10−4 1.07× 10−4 1.79× 10−4 1.93× 10−4 2.78