Short Papers___________________________________________________________________________________________________

Fingerprint Indexing Based on

Novel Features of Minutiae Triplets
Bir Bhanu, Fellow, IEEE, and
Xuejun Tan, Student Member, IEEE
AbstractThis paper is concerned with accurate and efficient indexing of
fingerprint images. We present a model-based approach, which efficiently
retrieves correct hypotheses using novel features of triangles formed by the
triplets of minutiae as the basic representation unit. The triangle features that we
use are its angles, handedness, type, direction, and maximum side. Geometric
constraints based on other characteristics of minutiae are used to eliminate false
correspondences. Experimental results on live-scan fingerprint images of varying
quality and NIST special database 4 (NIST-4) show that our indexing approach
efficiently narrows down the number of candidate hypotheses in the presence of
translation, rotation, scale, shear, occlusion, and clutter. We also perform scientific
experiments to compare the performance of our approach with another prominent
indexing approach and show that the performance of our approach is better for
both the live scan database and the ink based database NIST-4.
Index TermsFingerprint identification, indexing performance, NIST-4 database,
triangle features.

1 Introduction
FINGERPRINTS have long been used for person recognition due to
their uniqueness and immutability. There are two general ways in
which fingerprint based biometric systems are used: verification
and identification. In verification, the user inputs a fingerprint
image and claims an identity (ID), the system then verifies whether
the input image is consistent with the input ID. In identification,
which is more complex than verification, the user only inputs a
fingerprint image, the system identifies potential corresponding
fingerprints in the database. Efficient identification of fingerprints
is still a challenging problem, since the size of the fingerprint
image database can be large and there can be significant distortions
between different impressions of the same finger. These distortions
include: 1) translation, rotation, and scale because of different
positions and downward pressure of the finger, 2) shear
transformation as the finger may exert a different shear force on
the surface, and 3) occlusion and clutter because of scars, dryness,
sweat, smudge, etc. The problem of identifying a fingerprint can be
stated as: Given a fingerprint database and a query fingerprint,
obtained in the presence of translation, rotation, scale, shear,
occlusion, and clutter, does the query fingerprint resemble any of
the fingerprints in the database?
2 RELATED RESEARCH AND OUR CONTRIBUTIONS
2.1 Related Research
There are three kinds of approaches to solve the fingerprint
identification problem: 1) repeat the verification procedure for
each fingerprint in the database, 2) fingerprint classification, and
3) fingerprint indexing. If the size of the database is large, the first
approach is impractical. Although the scheme adopted by the FBI
defines eight classes, generally, classification techniques [3], [6],
[11] attempt to classify fingerprints into five classes: Right Loop
(R), Left Loop (L), Whorl (W), Arch (A), and Tented Arch (T).
However, the problem with classification technique is that the
number of principal classes is small and the fingerprints are
unevenly distributed (31.7 percent, 33.8 percent, 27.9 percent,
3.7 percent, and 2.9 percent for classes R, L, W, A, and T). The
classification approach does not narrow down the search enough
in the database for efficient identification of a fingerprint. The goal
of the third approach, called indexing, is to significantly reduce the
number of candidate hypotheses to be considered by the
verification algorithm. Thus, an indexing technique can be
considered as front-end processing, which would then be followed
by back-end verification processing in a complete fingerprint
recognition system. For multidimensional indexing methods,
readers are referred to a survey article by Gaede and Gunther [14].
A prominent approach for fingerprint indexing is by
Germain et al. [4]. They use the triplets of minutiae in their
indexing procedure. The features they use are: the length of each
side, the ridge count between each pair of vertices, and the angles
that the ridges make with respect to the X-axis of the reference
frame. The problems with their approach are:
1. the length changes are not insignificant under shear and
other distortions,
2. ridge counts are very sensitive to image quality,
3. the angles change greatly with different quality images of
the same finger, and
4. uncertainty of minutiae locations is not modeled explicitly.
As a result, bins that are used to quantize the invariants have to
be large, which increases the probability of collisions and causes
the performance of their approach to degrade. Our technique
follows their work in that we also use the triplets of minutiae.
However, the features that we use are quite different from theirs.
The features that we use are: triangles angles, handedness, type,
direction, and maximum side. These features are different, new,
and more robust than the features used by Germain et al. Table 1
shows the substantive differences between these two approaches.
Their approach is basically an indexing method where the top
hypothesis is taken as the identification result as has been done by
several researchers (e.g, Jones and Bhanu [13])
2.2 Contributions of this Paper
1. An indexing algorithm, based on novel features formed by
the triplets of minutiae and associated performance
analysis are presented on two different data sets.
2. The indexing performance is demonstrated in a principled
manner by using triplets as the basic representation unit.
3. Unlike the previously published research (see Table 2),
where ad hoc personalized criteria, partial data, or
handcrafted preprocessing are used for the selection of
images to demonstrate the results, in this paper the entire
NIST-4 database is processed and analyzed in an automated
manner in a black-box approach.
1
4. Comparisons of the performance of our approach with
Germain et al.s approach are carried out, which show that
our approach has performed better for both the live scan
database and the ink based database NIST-4.
3 TECHNICAL APPROACH
Our system for fingerprint identification is composed of two
stages: an offline stage and an online stage. The model database
and indexing structure are constructed during the offline stage,
616 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 25, NO. 5, MAY 2003
. The authors are with the Center for Research in Intelligent Systems,
University of California, Riverside, Riverside, CA 92521.
E-mail: {bhanu, xtan}@cris.ucr.edu.
Manuscript received 23 Feb. 2001; revised 22 Apr. 2002; accepted 16 Oct. 2002.
Recommended for acceptance by A. Khotanzad.
For information on obtaining reprints of this article, please send e-mail to:
[email protected], and reference IEEECS Log Number 113674.
1. Black-box approach means no specific data tuning within the black-box,
where the algorithm processes the entire input image.
0162-8828/03/$17.00 2003 IEEE Published by the IEEE Computer Society
and identification is carried out during the online stage. During the
offline stage, fingerprints in the database are processed one-by-one
to extract minutiae [1] to construct model database. During the
online stage, the query image is processed by the same procedure
to extract minutiae. Indexing components are derived from the
triplets of minutiae locations and used to map the points in the
feature space to the points in the indexing space. The potential
correspondences between the query image and images in the
database are searched in a local area in the indexing space. An
indexing score is computed based on the number of triangle
correspondences and candidate hypotheses are generated. The top
N ranked hypotheses are the result of our indexing algorithm.
3.1 Analysis of Angle Changes Under Distortions
Without loss of generality, we assume that one vertex, O, of the
triangle (see Fig. 1) is 0. 0, andit does not change under distortions.
Since distance is invariant under translation and rotation and
relatively invariant under scale, and angles are defined in terms of
the ratio of distance, it can be proven that angles are invariant under
these transformations. However, because of uncertainty of minutiae
locations, the location of each vertex changes independently in a
small local area in a randommanner. Suppose the locations of points
and 1 are r
1
. 0 and r
2
. y
2
, r
1
0, y
2
0, and r
2
2 1. 1.
We have toic y
2
,r
1
r
2
. Because of the uncertainty of
minutiae locations, and 1 move to
0
r
1
r
1
. 0 and 1
0
r
2

r
2
. y
2
y
2
. respectively, and c changes to c c. then
toic r
1
r
2
y
2
y
2
r
1
r
2

,r
1
r
2

2
r
1
r
2
r
1
r
2
y
2
2
y
2
y
2
.
Suppose j r
1
r
2
j<<j r
1
r
2
j , and j y
2
j<<j y
2
j , and for
small c. toic % c, we have
j c jj y
2
j ,2 j y
2
j j r
1
r
2
j ,2 j r
1
r
2
j.
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 25, NO. 5, MAY 2003 617
TABLE 1
Comparison between Germain et al.s [4] Approach and Bhanu and Tans Approaches
TABLE 2
NIST-4 Database Used in Fingerprint Recognition Research Published
Fig. 1. Illustration of variables.
That is, if the changes of minutiae locations are small enough, the
change of the angle will be less than a certain small value.
Furthermore, we can compute the expectation of j c j . Let
)r
1
. r
2
. y
2
. r
1
. r
2
. y
2
toic. Suppose r
1
, r
2
, and y
2
are independent, and 4 r
i
4, 4 y
2
4, i 1. 2, and
r
i
and y
2
are all integers, we have
qr
1
. r
2
. y
2
%
X
4
r14
X
4
r24
X
4
r34
j )r
1
. r
2
. y
2
. r
1
. r
2
. y
2
jr
1
jr
2
jy
2
j .
Assuming jr
1
, jr
2
and jy
2
are all discrete uniform
distributions in 4. 4. Let 0 < r
1
< 1, 0 < y
2
< 1 and j r
2
j< 1,
where 1 is the maximum value (150 pixels in experiments) of these
variables in the fingerprint. We compute qr
1
. r
2
. y
2
at each point
r
1
. r
2
. y
2
. Table 3 shows the expectation of the percentage of
angle changes that are less than various thresholds for the
minimum, median and maximum angles in a triangle. We observe:
1) We should use c
min
and c
med
as the indexing components to
construct the model database; 2) 2
o
4
o
can tolerate most
distortions of uncertainty and keep the size of the indexing space
that need to be searched as small as possible. We also tried other
distributions for jr
1
, jr
2
and jy
2
and found similar results.
Thus, minimum angle and median angle in a triangle formed by the
triplets of minutiae can be taken as components of the index to construct a
model database for fingerprint identification.
3.2 Triplet-Based Features for Indexing
The following features are derived from the triangle formed
by each noncollinear triplets of minutiae to form index
Hc
iii
. c
ior
. c. . j. `.
. Angles c
iii
and c
icd
. Suppose c
i
are three angles in the
triangle, i 1. 2. 3. Let
c
ior
iorfc
i
g. c
iii
iiifc
i
g. c
icd
180
o
c
ior
c
iii
.
then the labels of the triplets in this triangle are such that if
the minutia is the vertex of angle c
ior
, we label this point
as 1
1
, if the minutia is the vertex of angle c
iii
, we label it
as 1
2
, the last minutia is labeled as 1
3
which is the vertex of
angle c
icd
. Fig. 2 shows an example of this definition. We
use c
iii
and c
icd
as two components of the indexing
space. 0
o
< c
iii
60
o
and c
iii
c
icd
< 90
o
.
. Triangle Handedness c. Let 7
i
r
i
,y
i
be the com-
plex number ,

1
p
corresponding to the location
r
i
. y
i
of point 1
i
. i 1. 2. 3. Define 7
21
7
2
7
1
,
7
32
7
3
7
2
, and 7
13
7
1
7
3
. Let triangle handed-
ness c :iqi7
21
7
32
, where :iqi is the sign
function and is the cross product. Since points 1
1
,
1
2
, and 1
3
are noncollinear points, c 1 or 1.
. Triangle Type . Each minutia is either an endpoint or a
bifurcation, we define triangle type based on the types of
minutiae that form the triangle. Let 4
1
2
2

3
.
where
i
is the feature type of point 1
i
, i 1. 2. 3. If point
1
i
is an endpoint,
i
1, else
i
0. 0 7.
. Triangle Direction j. We search the minutia in the image
from top to bottom and left to right, if the minutia is the
start point of a ridge, we define the direction of the minutia
i 1, otherwise i 0. Let j 4i
1
2i
2
i
3
, where i
i
is
i value of point 1i, i 1. 2. 3. 0 j 7.
. Maximum Side `. Let ` iorf1
i
g, where 1
1
j 7
21
j ,
1
2
j 7
32
j , and 1
3
j 7
13
j .
3.3 Geometric Constraints
They are used to reduce the number of false correspondences
obtained from querying the lookup table by the index.
. Relative local orientation at mid points. Let points 1
21
,
1
32
, and 1
13
be the midpoint of line 1
2
1
1
, 1
3
1
2
, and 1
1
1
3
,
respectively, and point 1
123
be the centroid of the triangle
1
1
1
2
1
3
. Let
21

21

123
,
32

32

123
, and

13

13

123
, where
21
,
32
,
13
, and
123
are the local
orientations in the image at points 1
21
, 1
32
, 1
13
, and 1
123
,
respectively. We assume that relative local orientations

21
,
32
, and
13
will not change much in different
impressions. So, j
0
j< c
i
, where and
0
are
21
,

32
, or
13
in two different impressions.
. Relative local orientation at vertices. Let
i
be the local
orientation of point 1
i
, and .
i

i

123
, we have
j . .
0
j< c
|
, where i 1. 2. 3. and . and .
0
are .
1
, .
2
, or
.
3
in two different impressions of the same finger.
. Relative translation. Let 7
c
7
1
7
2
7
3
,3, where 7
i
is defined in Section 3.2, we have j 7 7
0
j< c
t
, where 7
and 7
0
are the 7
c
in two different impressions of the same
finger. j 7 7
0
j is the translation between the centroids of
these two triangles.
. Relative rotation. Let 0
21
oiq|c7
21
, 0
32
oiq|c7
32
,
and 0
13
oiq|c7
13
, where 7
21
, 7
32
, and 7
13
is defined in
Section 3.2, and oiq|c7 is the phase angle of 7. Let
j 0 0
0
j< c
i
, where 0 and 0
0
are 0
21
, 0
32
, or 0
13
in two
different impressions of the same finger.
3.4 Indexing Score, Algorithms, and Analysis
Suppose
1. 1 is the query image and 1
i
are the images in the database,
i 1. 2. . . . `
d
, where `
d
is the number of images in the
database,
2. ` and `
i
are the sets of minutiae in 1 and 1
i
, respectively,
3. i is a minutia, and i 2 ` [ `
i
,
4. `
i
is the number of matched triangles between 1 and 1
i
,
C
ii 1
3
`
i
C
ii
3
, and i
i
is an integer, which is the number
of potential corresponding minutiae in each image, and
5. i is the number of triangles in 1
i
which include i.
Then, we can compute the posterior probability
618 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 25, NO. 5, MAY 2003
TABLE 3
Expectation of the Percentage of Angle Changes Less than Various Thresholds
Fig. 2. Definition of feature points labels.
1`
i
1f1
i
1 j i 2 ` \ `
i
g c i, where c is a
constant factor that makes 1`
i
to be the correct
posterior probability.
We sort 1`
i
for each i, and find the i
i
largest probabilities,
suppose they are j
/
, where / 1. 2. . . . i
i
. We define the index
score of image 1
i
as:
o
i

X
ii
/1
j
/
.
. Algorithms. Fig. 3 shows the algorithms used in our
experiments.
. Probability of false indexing. Suppose:
1. o is the size of the index space,
2. )
/
is the number of triangles in the model database for
image 1
/
, and these triangles are uniformly distrib-
uted in the indexing space,
3. / is the search redundancy for each triangle in the
query image,
4. .
/
is the number of corresponding triangles between
image 1 and 1
/
, and
5. )
t
is the number of triangles for the query image [8].
Then, the value of .
/
that is greater than a threshold T can be
approximated by the Poisson distribution
jf.
/
Tg % 1 c

X
T
i0

i
,i!.
where )
t
j
1
, j
1
% /j
0
, j
0
)
/
,:. In our approach, in a
triangle if c
iii
< c
c
or t < c
t
, where t is the minimum side of
the triangle, then we do not use this triangle to build the model.
We use 0.5
o
as the bin size for angles c
iii
and c
icd
, c
`
for `, and
we search the indexing space with the uncertainty of 2
o
. Hence,
% 15.885. Fig. 4 shows the curve of 1f.
/
g T with respect to T.
When T 25. 1f.
/
g T 0.0121. That is, if there is no image in
the database corresponding to the test image, the probability of
finding 25 corresponding triangles between the test image and any
of the images in the database is about 0.0121. We can use T 25 as
the threshold to reject a test image which has no corresponding
image in the database. Note that, while the triangles are not
uniformly distributed in the model database, since we apply
geometric constraints, T can be less than 25.
4 Experiments
4.1 Database and Parameters
The data set 1 contains 400 pairs of images and 200 single images.
These images are collected from 100 persons on the same day by a
Sony fingerprint optical sensor (FIU-500-F01) with the resolution of
300 DPI (see Fig. 5a). The size of these images is 248 120 pixels.
Each pair of images is different impression of the same finger, one is
used to construct the model database, and the other one is used as
the query image. The single image data set is used to test the
rejection performance. We subjectively classify these images
according to their quality into three classes: good, fair, and poor.
Most images in the database are of fair (33.2 percent) or poor quality
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 25, NO. 5, MAY 2003 619
Fig. 3. Algorithms for runtime identification (online stage). (a) Algorithm for constructing the model database (offline stage). (b) Algorithm for runtime indentification (online
stage).
Fig. 4. 1f.
/
Tg with respect to T.
(47.8 percent). The data set 2 is the NIST special database 4 (NIST-4)
[9] that contains 2,000 pairs of images. Since these images are
collected with an ink based method, a large number of NIST-4
images are of much poorer quality. NIST-4 images often contain
other objects, such as characters and handwritten lines (see Fig. 5b).
The size of these images is 480 512 pixels with the resolution of 500
DPI. Parameters c
c
, c
t
, and c
`
are different for the two data sets: for
data set 1, c
c
5
o
, c
t
20 pixels, c
`
10 pixels, for data set 2,
c
c
10
o
, c
t
40 pixels, c
`
20 pixels. All other parameters are the
same for both data sets: c
i
30
o
, c
|
30
o
. c
i
30
o
, c
t
50 pixels,
T
c1
4
o
, T
c2
4
o
, and T 20.
4.2 Performance Evaluation Measures for Indexing
False Positive Rate (FPR) and False Negative Rate (FNR) are used
to evaluate the performance of a verification algorithm [10].
However, the goal of the indexing method in this paper is to
narrow down the number of hypotheses which need to be
considered for subsequent verification. The output of an indexing
algorithm is the set of top N hypotheses. If the corresponding
fingerprint is in the list of top N hypotheses, we should take the
indexing result as a correct result. Hence, FPR and FNR are not
suitable for evaluating the results of an indexing algorithm. We
define Correct Index Power (CIP) and Correct Reject Power (CRP)
as the performance evaluation measures for indexing: C11
`
ci
,`
d
100% and C11 `
ci
,`
:
100%, where `
ci
is the
number of correctly indexed images, `
d
is the number of images in
the database, `
ci
is the number of correctly rejected images, `
:
is
the number of the query images that dont have corresponding
images in database.
4.3 Indexing Results for Data Set 1
Fig. 6 shows the CIP for each class of images and the entire
data set 1 with respect to the length of the short list of hypotheses.
The CIP of a single hypothesis for good quality images is
96.2 percent. As the quality of images become worse, the CIP
decreases to 85.5 percent for fair and 83.3 percent for poor images.
The average CIP of a single hypothesis for the entire database is
86.5 percent. The CIP of the top 2 hypotheses is 100.0 percent for
good images, and for fair images and poor quality images, the CIP
of the top five hypotheses are 99.2 percent and 98.0 percent,
respectively. For the entire database of 400 images, the CIP of the
top nine (2.3 percent of database) hypotheses is 100.0 percent. Fig. 7
shows that on data set 1 the performance of our approach is better
than that of Germain et al.s approach. We also evaluated the
indexing performance of our algorithm for the 200 images, which
are not in the database. Our indexing algorithm rejected these
images C11 100%. Thus, threshold T based on the analysis of
620 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 25, NO. 5, MAY 2003
Fig. 5. Sample images: (a) data set 1 and (b) data set 2.
Fig. 6. CIP of data set 1.
Fig. 7. Comparison of two approaches.
Fig. 8. ROC justifies T 20.
Fig. 9. Number of corresponding triangles of the 2,000 query images of data set 2.
Fig. 10. Distribution of corresponding triangels among 2,000 query images of
data set 2.
our approach works well. Furthmore, we use the hypothesis,
which has the highest indexing score, as the result of identification
to obtain the Receiver Operating characteristic Curve (ROC) shown
in Fig. 8, where 1
ci
is the CIP for the top hypothesis and the False
Alarm Rate 11 100 C11. When T 20, the FAR is 0 and as
T decreases, FAR will increase.
4.4 Indexing Results for Data Set 2
Fig. 9 shows the number of corresponding triangles for each query
image of data set 2. Note that 32 images do not have any
corresponding triangles. That is why CIP can not reach 100 percent
as the number of hypotheses increases. Fig. 10 shows the
distribution of the number of corresponding triangles among
those 2,000 query images on a log scale. Because of bad quality, for
some queries the number of corresponding triangles is quite small.
Fig. 11 shows how CIP performance varies with the number of
corresponding triangles for different threshold T. Approximately
10 good features lead to good indexing results.
. Effect of constraints and computation time. Fig. 12 shows
the effect of geometric constraints in reducing the average
percentage of hypotheses that need to be considered for
indexing. We observe that four geometric constraints
provide a reduction by a factor of 589.487, 6.869, 1.428,
and 1.007, sequentially. On a SUN ULTRA2 workstation,
without optimization, average time for correctly indexing
or correctly rejecting a query is less than one second.
. Extrapolation of indexing performance. There exists no
general theory in the computer vision and pattern recogni-
tion field to predict the performance of model-based
indexing and matching algorithms under arbitrary trans-
formations and arbitrary size of databases. Initial attempts
have been made in [2], which takes into consideration of
uncertainty in features, occlusion, clutter and similarity of
object models. Inthe absence of a general theory, we perform
extrapolation of the results obtained on NIST-4 database to
estimate the scalabilityof our approach. Let N, the number of
hypotheses, be 10 percent of M, where M is the size of the
database, but if ` 100, then let ` 100, so that the
maximum number of hypotheses need to be considered is
100. Fig. 13 shows the extrapolated performance of our
approach on databases of different size, which uses a linear
regression model. Fig. 14 shows the extrapolation with large
M. As Mincreases, the performance will decrease andthe 95
percent confidence interval of the performance will increase.
However, these results indicate that aCIPof 50percent could
be achievedwith a short list of 100 hypotheses, which would
be only 0.33 percent of a 30,000-image database, which is
really a good performance. This extrapolation from the
results of 2,000 images to 30,000 needs to be taken with
caution. It is dependent onthequalityof input images and, as
our analysis shows, NIST-4 is a difficult database.
. Comparison of approaches. We have done a direct
comparison with Germain et al.s approach. We imple-
mented Germain et al.s approach and compared the
performance of our indexing algorithm with it on NIST-4
data set 2. Fig. 15 shows the comparisons of the two
approaches on four subsets, first 100, 500, 1,000, and
2,000 fingerprints, of data set 2. Our approach has
performed better than that of Germain et al.s approach.
When the entire data set 2 is used, although the CIP of
Germain et al.s approach increases from 53.0 percent to
67.0 percent, the CIP of our approach increases from
60.4 percent to 72.4 percent as the number of hypotheses
increases from top 1 (0.05 percent of the database) to top 10
(0.5 percent of the database). Fig. 16 shows that the
indexing performance increases as the percentage of the
database size increases. When it is 10 percent, our
approach is still better, the CIP of these two approaches
are 85.5 percent and 83.7 percent, respectively.
A direct comparison with traditional fingerprint classification
approaches can not be done for the following reasons: our approach
for indexing is different from classification techniques. They are
classifying each testing image into four or five classes, while we are
generating the top N hypotheses for an input fingerprint query. The
outputs of these two systems are different. If we take our approach
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 25, NO. 5, MAY 2003 621
Fig. 11. CIP performance varies with the number of corresponding triangles (data set 2). (a) T 1, (b) T 10, and (c) T 50.
Fig. 12. Effect of constraints. Fig. 13. Performance on NIST-4.
and traditional classification approaches as a filtering step for data
reduction before detailed verification, then it is possible to compare
the two approaches indirectly. The results of our technique can be
evaluated in term of the number of hypotheses that need to be
considered for detailed verification. We do not use error/efficiency
analysis since it has its own limitations as pointed out by Senior [11].
Fig. 15 and Fig. 16 show the percentage of the NIST-4 database that
needs to be examined in subsequent verification. Rather than
reducing the computation for verification to about 1/3 of the
database by a classification approach, our approach reduces the
computation to about 10 percent of the database for the CIP to be
85.5 percent. So, on the NIST-4 database, our approach is better than
traditional classification approach. For a database of 30,000, for our
approach, a CIP of 50 percent could be achieved with only
100 hypotheses (0.33 percent of the database). The performance of
the traditional approach will be quite low, because the number of
classes is limited (4 or 5) and quite likely there will be more than
10 percent misclassification. A thorough comparison of these two
kinds of approaches (indexing and classification followed by
verification) is the topic of future research. It is beyond the scope
of this paper. Note that a lowvalue for CIPis not a fatal flawwithour
approach for large database where a low miss rate is required,
because indexing can produce an ordered list of hypotheses of the
entire database, which will, on average, be much more efficient for
verification than a blind exhaustive search.
5 CONCLUSIONS
Our approach, based on triplets of minutiae, is promising for
identifying fingerprints under translation, rotation, scale, shear,
occlusion, and clutter. Experimental results show that it can greatly
reduce the number of candidate hypotheses for further verification.
In various comparisons with the prominent indexing approach
developed by Germain et al., our approach has performed better.
We have performed the analysis of the entire NIST-4 database in a
systematic manner and characterized indexing performance in
terms of the number of corresponding triangles. This will allow the
comparison of our results by others on the same publicly available
database. Our approach can also be applied to each class after the
fingerprints have been classified into R, L, A, T, and W classes to
produce an ordered list of hypotheses for efficient verification.
ACKNOWLEDGMENTS
This work was supported in part by grants from Sony, DiMI, and
I/O Software.
REFERENCES
[1] B. Bhanu and X. Tan, Learned Templates for Feature Extraction in
Fingerprint Images, Proc. IEEE. Conf. Computer Vision and Pattern
Recognition, vol. 2, pp. 591-596, 2001.
[2] M. Boshra and B. Bhanu, Predicting Performance of Object Recognition,
IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 9, pp. 956-
969, Sept. 2000.
[3] R. Cappelli, A. Lumini, D. Maio, and D. Maltoni, Fingerprint Classification
by Directional Image Partitioning, IEEE Trans. Pattern Analysis and Machine
Intelligence, vol. 21, no. 5, pp. 402-421 May 1999.
[4] R.S. Germain, A. Califano, and S. Colville, Fingerprint Matching Using
Transformation Parameter Clustering, IEEE Computational Science and
Eng., vol. 4, no. 4, pp. 42-49, 1997.
[5] U. Halici and G. Ongun, Fingerprint Classification through Self-Organiz-
ing Feature Maps Modified to Treat Uncertainties, Proc. IEEE, vol. 84,
no. 10, pp. 1497-1512, 1996.
[6] A.K. Jain, S. Prabhakar, and L. Hong, A Multichannel Approach to
Fingerprint Classification, IEEE Trans. Pattern Analysis and Machine
Intelligence, vol. 21, no. 4, pp. 348-359, Apr. 1999.
[7] Z.M. Kovacs-Vajna, A Fingerprint Verification System Based on Trian-
gular Matching and Dynamic Time Warping, IEEE Trans. Pattern Analysis
and Machine Intelligence, vol. 22, no. 11, pp. 1266-1276, 2000.
[8] Y. Lamdan and H.J. Wolfson, On the Error Analysis of Geometric
Hashing, Proc. IEEE. Conf. Computer Vision and Pattern Recognition, pp. 22-
27, 1991.
[9] C.I. Watson and C.L. Wilson, NIST Special Database 4, Fingerprint
Database, U.S. Natl Inst. of Standards and Technology, 1992.
[10] J.L. Wayman, Error Rate Equations for the General Biometric System,
IEEE Robotics & Automation Magazine, vol. 6, no. 1, pp. 35-48, 1999.
[11] A. Senior, A Combination Fingerprint Classifier, IEEE Trans. Pattern
Analysis and Machine Intelligence, vol. 23, no. 10, pp. 1165-1174, Oct. 2001.
[12] K. Karu and A.K. Jain, Fingerprint Classification, Pattern Recognition, vol.
29, no. 3, pp. 389-404, 1996.
[13] G. Jones and B. Bhanu, Recognition of Articulated and Occluded Objects,
IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 21, no. 7, pp. 603-
613, July 1999.
[14] V. Gaede and O. Gunther, Multidimensional Access Methods, ACM
Computing Surveys, vol. 30, no. 2, pp. 170-231, 1998.
> For more information on this or any other computing topic, please visit our
Digital Library at http://computer.org/publications/dlib.
622 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 25, NO. 5, MAY 2003
Fig. 14. Performance with large M.
Fig. 15. Comparison of Germain et al.s and our approaches on NIST-4 data set.
Fig. 16. Comparison of Germain et al.s approach and our approach on NIST-4
data set.