Yanushkevich S.N., Wang P.S.P., Gavrilova M.L., Srihari S.N. (eds.) Image Pattern Recognition. Synthesis and Analysis in Biometrics
Подождите немного. Документ загружается.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
This page intentionally left blankThis page intentionally left blank
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Chapter 5
A Statistical Model for Biometric Verification
Sargur Srihari
∗
,HarishSrinivasan
†
Center of Excellence for Document Analysis and Recognition (CEDAR),
Department of Computer Science and Engineering, University at Buffalo,
State University of New York, Buffalo, NY, USA
∗
srihari@cedar.buffalo.edu
†
hs32@cedar.buffalo.edu
The biometric verification task is one of determining whether an input
consisting of measurements from an unknown individual matches the
corresponding measurements of a known individual. This chapter
describes a statistical learning methodology for determining whether
a pair of biometric samples belong to the same individual. The
methodology involves four parts. First, discriminating elements or
features, are extracted from each sample. Second, similarities between
the elements of each sample are computed. Third, using conditional
probability estimates of each difference, the log-likelihood ratio (LLR)
is computed for the hypotheses that the samples correspond to the
same individual and to different individuals; the conditional probability
estimates are determined in a learning phase that involves estimating
the parameters of various distributions such as Gaussian, gamma or
mixture of gamma/Gaussian. Fourth, the LLR is analyzed with the
Tippett plot to provide a measure of the strength of evidence. The
methods are illustrated in two biometric modalities: friction ridge
prints — which is a physical biometric, and handwriting — which is a
behavioural biometric. The statistical methodology has two advantages
over conventional methods such as thresholds based on receiver operating
characteristics: improved accuracy and a natural provision for combining
with other biometric modalities.
Contents
5.1. Introduction ................................... 140
5.2. DiscriminatingElementsandSimilarity.................... 141
5.3. StatisticalFormulation ............................. 142
139
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
140 Synthesis and Analysis in Biometrics
5.3.1. GaussianCase............................. 144
5.3.2. GammaCase ............................. 146
5.3.3. MixtureModelCase ......................... 147
5.3.4. StrengthofEvidence ......................... 148
5.4. ApplicationofModel .............................. 149
5.4.1. FingerprintVerification........................ 149
5.4.2. WriterVerification .......................... 153
5.5. ConcludingRemarks .............................. 156
Bibliography ....................................... 156
Glossary
AER — Average Error Rate
DE — Discriminating element
EER — Equal Error Rate
FA R — False Acceptance Rate
LLR — The log-likelihood ratio
LR — The likelihood ratio
p.d.f. — Probability density functions
ROC — Receiver Operating Characteristic
TAR — True Acceptance Rate
5.1. Introduction
The task of biometric verification is defined as that of determining whether
two samples of biometrics correspond to (or were generated by) the same or
by different individuals
[
1
]
. The biometric samples can be of any modality
such as fingerprints, handwriting, signature, speech etc. For each modality
different terminology is used for the verification task:
In fingerprint verification, one of the two samples is called the template,
and the sample being tested for match is called the input.
In writer verification, they are called known and questioned respectively,
which is derived from the domain of forensic document examination.
In signature verification they are referred to as genuine and input.
This chapter describes a statistical approach to the design of a
verification system to automatically make a decision of same(match) or
different(non-match) when two biometric samples are compared. The
approach involves a statistical learning phase and an evaluation phase.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
A Statistical Model for Biometric Verification 141
The learning phase begins with a training set of ensemble of pairs, which
capture the distribution of intra-class (or same individual) variations and
inter-class (or two different individuals) differences. It consists of four steps:
Step 1. Discriminating element extraction,
Step 2. Similarity computation,
Step 3. Estimating conditional probability density estimates
for the difference being from the same individual or from
different individuals, and
Step 4. Determining the log-likelihood ratio (LLR) function and
from it the Tippett plot, which is a function of the
distribution of the LLR.
The evaluation phase for a given pair of samples is as follows:
(i) Discriminating element extraction,
(ii) Similarity computation,
(iii) Determining the LLR from the estimated conditional probability
density estimates, and
(iv) Determining the strength of evidence from the Tippet plot.
Each of the four steps in the model are described in the following
sections.
5.2. Discriminating Elements and Similarity
Discriminating elements (DEs) are dependent upon the biometric modality.
They are objects that are located within a sample that will be used for
verification. For example, in the case of writer identification based on
handwriting on paper, an allograph or character is a DE. The shape of the
DE within a sample of handwriting is used to match against the shape of the
same DE in another sample. There is a hierarchy of DEs involving 21 classes
of DEs such as elements of execution, style, etc., which in turn consist
of finer DEs
[
2
]
. For fingerprints, the most commonly used DEs are the
location and orientation of minutiae(Ridge endings and Ridge bifurcations)
present in the fingerprint image.
Once a DE is determined to be present in the sample we extract a feature
or measurement from the DE. Some DEs are determined from the entire
sample-the corresponding features are referred to as macro features. DEs
and features that capture finer details at the individual level are called as
micro-features. Some DEs capture the class characteristics of an individual
such as gender and ethnicity.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
142 Synthesis and Analysis in Biometrics
In order to match DEs between two samples, the presence of the DE has
to be first recognized in each sample. Matching is performed between the
same elements in each sample. A formal statement of these considerations
follow.
Assume that there are r different DEs that can possibly be used. The
value of r can range from 1 to many. In the case of present-day automatic
fingerprint identification systems (AFIS), only the minutiae are considered
as the DEs, thus making r = 1. Since the features of a DE are usually
fixed, the symbol for a DE, say x
i
, is taken to denote the features of the
DE. Denote by x
i
(k
j
), vector of all the occurrences of the i
th
DE, from
the j
th
sample of the k
th
individual, where k =1,...,n is the index of the
individuals whose samples are available for training and j =1...,m is the
index of those multiple samples available for each individual.
Assume that there exists a suitable similarity or distance measure
between two DEs of the same type. For the i
th
DE that occurs in two
particular samples A and B (A and B may or may not belong to the same
individual), the distance between all the occurrences of that DE in A and
the those in B is computed as as
D
i
[x
i
(A), x
i
(B)].
The definition of the distance measure D
i
is dependent upon the
particular discriminating element i. It should be noted that the symbol
D
i
can also be used to mean a similarity measure, as opposed to a distance
measure. The two are interchangeable depending on the definition of D
i
.
5.3. Statistical Formulation
The probability of a particular pair of sample A and B belonging to the
same individual, conditioned on all the occurrences of a DE i, that occurs
in both samples, is denoted as
P
same
(D
i
[A, B]).
This probability distribution P
same
is determined from the set
{D[x
i
(s
j
), x
i
(s
m
)],
where j, m vary over all the samples of each individual s,ands =1,...,n}
and j<>m. The probability of their belonging to different individuals is
denoted as
P
different
(D
i
[A, B]),
which is determined from the set
{D[x
i
(s
j
), x
i
(t
m
)],
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
A Statistical Model for Biometric Verification 143
where j, m vary over all the samples of each pair of individuals s, t,
s =1,...,n, t =1,...,n and s<>t}. It is useful to represent the two
distributions as probability density functions (p.d.f.s) so that they can be
used in the computation of likelihood functions. The p.d.f.s corresponding
to the two similarity distributions will be denoted as
p
same
(D
i
[A, B]) and p
different
(D
i
[A, B]),
respectively.
Assume that the distances(or similarities) along different DEs are
conditionally independent given whether or not the two samples belong
to the same or different individuals. In cases, where the DEs are not
conditionally independent, then the need to learn a joint p.d.f.,
p
same
(D[A, B]) and p
different
(D[A, B])
arises, where D[A, B]isavector of distance measures, one for each DE.
In most scenarios, the independence assumption holds good and leads to a
model that can be learnt easily. When trying to match two samples A and
B,iftherearer DEs of available, then the probability of samples A and B
belonging to the same or different individual can be written as Eqs. (5.1)
and (5.2).
p
same
(A, B)=
r
i=1
p
same
(D
i
[x
i
(A), y
i
(B)]) (5.1)
p
different
(A, B)=
r
i=1
p
different
(D
i
[x
i
(A), y
i
(B)]) (5.2)
It is useful to determine the ratio of the two p.d.f.s to determine the
relative strength of the two values. We refer to
p
same
(A, B)
p
different
(A, B)
as the likelihood ratio (LR). The log-likelihood ratio (LLR), obtained by
taking the logarithm of LR is more useful since LR values tend to be very
large (or small). Then the log-likelihood ratio has the form of Eq. (5.3)
LLR(A, B)=
r
i=1
log[p
same
(D
i
(x
i
(A), x
i
(B))]
− log[p
different
(D
i
(x
i
(A), x
i
(B))] (5.3)
Similarity p.d.f.s p
same
and p
different
for scanned signatures are shown in
Fig. 5.1. In this case, the DE consists of the entire signature and hence
the number of occurrences of the DE is 1. The feature vector of this
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
144 Synthesis and Analysis in Biometrics
Fig. 5.1. Probability density functions of similarities of same and different pairs of DEs.
single DE x, consists of 1024 binary-values which respectively capture the
finest variations in the contour, intermediate stroke information and larger
concavities and enclosed regions of a signature have been shown to be useful
forwriterrecognition
[
1
]
. Since micro features are binary valued several
binary string distance measures can be used, the most effective of which is
the correlation measure
[
3
]
. The data is from pairs of signatures: genuine-
genuine pairs and genuine-forgery pairs. The closeness of the two p.d.f.s is
due to skilled forgeries. It is useful to represent the two distributions as
p.d.f.s so that they can be used in the computation of likelihood functions.
Figures 5.2(a) and 5.2(b) show the likelihood function and LLR values for
normally distributed DEs.
5.3.1. Gaussian Case
If the similarity data has both positive and negative scores, then the
similarity data can be acceptably represented by Gaussian distributions-
which can be expected since we are dealing with several factors such as
the feature measurement, distance computation, etc. — we represent the
probability density functions of distances conditioned upon the same- and
different-individual categories for a single DE x as the parametric forms
p
same
(x) N(µ
s
,σ
2
s
)andp
different
(x) N(µ
d
,σ
2
d
),
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
A Statistical Model for Biometric Verification 145
Ŧ0.5 0 0.5 1 1.5 2 2.5 3 3.5
0
10
20
30
40
50
60
70
80
90
100
similarity x
likelihood ratio for numeral 4
mean(sw)=0.7352
mean(dw)=0.6021
std(sw)=0.0717
std(dw)=0.0848
(a)
Ŧ0.5 0 0.5 1 1.5 2
Ŧ70
Ŧ60
Ŧ50
Ŧ40
Ŧ30
Ŧ20
Ŧ10
0
10
log likelihood ratio for numeral 4
similarity x
mean(sw)=0.7352
mean(dw)=0.6021
std(sw)=0.0717
std(dw)=0.0848
(b)
Fig. 5.2. Likelihood ratio (a) and log-likelihood ratio of a DE whose similarity p.d.f.s
are normally distributed (b).
whose parameters are estimated using maximum likelihood estimates. The
LLR value can be expressed as Eq. (5.4).
LLR =
(x − µ
d
)
2
2σ
2
d
−
(x − µ
s
)
2
2σ
2
s
+log
σ
d
σ
s
(5.4)
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
146 Synthesis and Analysis in Biometrics
which has the quadratic form a
1
x
2
+ a
2
x + a
3
,wherea
1
, a
2
and a
3
are
constants defined in terms of the means and variances of the two p.d.f.s as
Eq. (5.5)
a
1
=
(σ
2
s
− σ
2
d
)
2σ
2
s
σ
2
d
a
2
=
µ
s
σ
2
d
− µ
d
σ
2
s
)
2σ
2
s
σ
2
d
a
3
=
1
2σ
2
s
σ
2
d
(µ
s
σ
2
d
− µ
d
σ
2
s
)+log
σ
d
σ
s
(5.5)
5.3.2. Gamma Case
In many cases, the distance measure D
i
(A, B) is always positive. This
is because, the simplest distance measure, may be defined as an absolute
difference between different measurements on the biometric sample. Hence,
a Gaussian distribution is not ideal to model such a distribution. Here a
more robust distribution, a Gamma distribution can be used to model the
distributions of
P
same
(D
i
[A, B]) and P
different
(D
i
[A, B]).
The p.d.f. of a Gamma distribution is given in Eq. (5.6). The gamma
p.d.f. has two sufficient statistics namely the scale parameter θ and the
shape parameter α. These two parameters can be learnt from Eq. (5.7)
where σ and µ are the standard deviation and mean of the distribution.
The robustness of the Gamma distribution to model different kind of shapes
is shown in Figs. 5.3(a), 5.3(b) and 5.3(c).
P (x|α, θ)=x
α−1
e
−
x
θ
θ
α
· Γ(α)
for x>0 (5.6)
θ =
σ
2
µ
α =
µ
θ
(5.7)
Thus analogous the Gaussian case, we represent the probability density
functions of distances conditioned upon the same- and different-individual
categories for a single DE x as the parametric forms
p
same
(x) Gamma(α
s
,θ
2
s
)andp
different
(x) Gamma(α
d
,θ
2
d
) ,
whose parameters are estimated using maximum likelihood estimates. The
LLR value analogous to Eq. (5.4) for the Gamma case is given below in
Eq. (5.8)
LLR =(α
s
− α
d
)logx −
1
θ
s
−
1
θ
d
x
−α
s
θ
d
+ α
d
θ
s
+logΓ(α
s
) − log Γ(α
d
) (5.8)
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
A Statistical Model for Biometric Verification 147
0 5 10 15 20 25 30 35
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
Gamma distribution with theta=2.0 and varying alpha
s
p.d.f Gamma(s)
alpha=1.0
alpha=3.0
alpha=5.0
alpha=7.0
alpha=9.0
(a) Gamma distribution curves for
fixed θ =2.0andvaryingα.
0 5 10 15 20 25 30 35
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Gamma distribution with alpha=1.0 and varying theta
s
p.d.f Gamma(s)
theta=1.0
theta=2.0
theta=3.0
theta=4.0
theta=5.0
(b) Gamma distribution curves for
fixed α =1.0andvaryingθ.
0 5 10 15 20 25 30 35
0
0.02
0.04
0.06
0.08
0.1
0.12
0.14
0.16
0.18
0.2
Gamma distribution with alpha=5.0 and varying theta
s
p.d.f Gamma(s)
theta=1.0
theta=2.0
theta=3.0
theta=4.0
theta=5.0
(c) Gamma distribution curves for
fixed α =5.0andvaryingθ.
Fig. 5.3. Gamma distribution curves. (a) Varying α,(b)Varyingθ, α =1.0. Note how
the θ parameter defined the rate of decay of the exponential. (c) Varying θ, α =5.0.
5.3.3. Mixture Model Case
In some cases, the distribution of the distance measures, is not unimodal.
Hence, neither unimodal Gamma or Gaussians can effectively model the
distributions. Hence, a mixture model is used to learn the distribution.
A mixture model always has one extra parameter (π)knownasthe
mixing proportion, in addition to the sufficient statistics of the underlying
distribution used. For example, a mixture of Gamma distribution as three