Li S.Z., Jain A.K. (eds.) Encyclopedia of Biometrics

Подождите немного. Документ загружается.

a newly acquired sample should replace the en-

rolled one. An alternative would be to retain

both the old and new samples for use in a

multi-instance fusion scheme.

e. Template Update

Again to address template aging, some systems

instead combine old and new sample features.

Quality could be used in this process.

Summary

Fingerprint quality measurement is an operationally

important task. This pap er enumerated ways in

which it is useful to compute a quality value from a

sample. In all cases the ultimate intention is to improve

matching performance. The authors asserted therefore

that quality algorithms should be developed to explic-

itly target matching error rates, and not human per-

ceptions of sample quality. The term quality should

not be equated to the acquisition settings of the sam-

ple, such as image resolution, dimensions in pixels,

grayscale/color bit depth, or number of features.

Though such factors may affect sample utility and

could contribute to the overall quality score. We

reviewed the existing practice of ﬁngerprint local and

global analysis. Local and global quality scores could be

combined to form a vector of overall ﬁnger image

quality. However, it is useful, even necessary for some

applications, if local and global quality measures are

summarized into a scalar which is predictive of error

rates associated with the veriﬁcation or identiﬁcation

of that sample.

Related Entries

▶ Biometric Sample Quality Standard

▶ Performance of Quality Measures

References

1. Maltoni, D., Maio, D., Jain, A.K., Prabhakar, S.: Handbook of

Fingerprint Recognition. Springer, New York (2003)

2. Grother, P., et al.: MINEX: Performance and Interoperability of

the INCITS 378 Fingerprint Template. National Institute of

Standards and Technology, NISTIR 7296 edn. (2005). http://

ﬁngerprint.nist.gov/minex04

3. Tabassi, E., Wilson, C., Watson, C.: Fingerprint Image Quality,

NFIQ. National Institute of Standards and Technology, NISTIR

7151 edn. (2004)

4. Tabassi, E., Wilson, C.L.: A novel approach to ﬁngerprint image

quality. In: ICIP (2), pp. 37–40 (2005)

5. Tilton, C., et al.: The BioAPI Speciﬁcation. American National

Standards Institute, Inc. (2002)

6. Benini, D., et al.: ISO/IEC 29794-1 Biometric Sample Quality

Standard: Framework. JTC1 / SC37 / Working Group 3 (2008).

http://isotc.iso.org/isotcportal

7. Alonso-Fernandez, F., Fierrez, J., Ortega-Garcia, J., Gonzalez-

Rodriguez, J., Fronthaler, H., Kollreider, K., Bigun, J.: A Com-

parative study of ﬁngerprint image-quality estimation methods.

IEEE Trans. Inform. Forens. Secur. 2, 734–743 (2007)

8. Lim, E., Jiang, X., Yau, W.: Fingerprint image quality and validity

analysis. In: IEEE proceedings of International Conference on

Image Processing (ICIP), pp. 469–472. New York, USA (2002)

9. Chen, Y., Dass, S.C., Jain, A.K.: Fingerprint quality indices for

predicting authentication performance. In: AVBPA, pp. 160–170

(2005)

10. Shen, L., Kot, A.C., Koo, W.M.: Quality measures of ﬁngerprint

images. In: AVBPA, pp. 266–271 (2001)

11. Ratha, N., Bolle, R.: Automatic Fingerprint Recognition Sys-

tems. Springer, New York (2004)

12. Lim, E., Toh, K.A., Saganthan, P.N., Jiang, X., Yau, W.Y.: Finger-

print image quality analysis. In: ICIP, pp. 1241–1244 (2004)

13. Chen, T.P., Jiang, X., Yau, W.Y.: Fingerprint image quality analy-

sis. In: ICIP, pp. 1253–1256 (2004)

14. Bolle, R., et al.: System and methods for determining the quality

of ﬁngerprint images. US Patent 596356 (1999)

15. Hong, L., Wan, Y., Jain, A.K.: Fingerprint image enhancement:

algorithm and performance evaluation. IEEE Trans. Pattern

Analy. Mach. Intell. 20(8), 777–789 (1998)

16. Nill, N., Bouzas, B.H.: Objective image quality measure derived

from digital image power spectra. Opt. Eng. 31(4), 813–825

(1992)

17. National Institute of Standards and Technology: NIST Biometric

Image Software (NBIS) (2008). http://www.itl.nist.gov/iad/

894.03/nigos/nbis.html

18. Ko, T., Krishnan, R.: Monitoring and reporting of ﬁngerprint

image quality and match accuracy for a large user application.

In: Proceedings of the 33rd Applied Image Pattern Recognition

Workshop, pp. 159–164. IEEE Computer Society (2004)

19. Tabassi, E., Grother, P.: Quality Summarization: Recommendations

on Enterprise-wide Biometric Quality S ummarization. N ational

Institute of Standards and Technology, NISTIR 7244 edn. (2007)

20. Wein, L.M., Baveja, M.: Using ﬁngerprint image quality to

improve the identiﬁcation performance of the u.s. visit program.

In: Proceedings of the National Academy of sciences (2005).

www.pnas.org/cgi/doi/10.1073/pnas.0407496102

21. Fierrez-Aguilar, J., Ortega-Garcia, J., Gonzalez-Rodriguez, J.,

Bigun, J.: Discriminative multimodal biometric authentication

based on quality measures. Pattern Recogn. 38(5), 777–779 (2005)

22. Tabassi, E., Quinn, G.W., Grother, P.: When to fuse two

biometrics. In: IEEE Computer Society Conference on Com-

puter Vision and Pattern Recognition CVPR-06. New York

(2006). Biometric Workshop

490

Fingerprint Image Quality

Fingerprint Indexing

GEO RGE BEBIS

University of Nevada, Reno, NV, USA

Synonyms

Continuous classiﬁcation; Fingerprint retrieval; ﬁnger-

print authentication; ﬁngerprint identiﬁcation

Definition

When matching a query ﬁngerprint to a large ﬁnger-

print database for identiﬁcation purposes, a critical

issue is how to narrow down the search space. Indexing

provides a mechanism to quickly determine if a query

ﬁngerprint is in the database and to retrieve those

ﬁngerprints that are most similar with the query, with-

out searching the whole database.

Introduction

Fingerprint matching is one of the most popular and

reliable biometric techniques used in automatic personal

identiﬁcation. Typically, ﬁngerprint matching is based

on low-level features determined by singularities in

the ﬁnger ridge pattern known as minutiae.Tobe

practical, matching should be robust to translation,

rotation, scale, shear, occlusion, and clutter. In this con-

text, matching two ﬁngerprints implies ﬁnding a subset

of minutiae in the ﬁrst ﬁngerprint that best match to a

subset of minutiae in the second ﬁngerprint through

a geometric transformation in an optimal sense.

There are two main applications involving ﬁnger-

print matching: ﬁngerprint authentication and ﬁn-

gerprint identiﬁcation. While the goal of ﬁngerprint

authentication is to verify the identity of a person,

the goal of ﬁngerprint identiﬁcation is to establish

the identity of a person. In this case, matching involves

comparing a query ﬁnge rprint against a database of

reference ﬁngerprints to establish the identity of the

query. An important issue in ﬁngerprint identiﬁcation

is how to select the most similar ﬁngerprint(s) to the

query ﬁngerprint from the ﬁngerprint database. The

easiest but least effective way to search a large database

is to compare the query ﬁngerprint with each

ﬁngerprint in the database. Since usually there is no

a-priori knowledge of possible correspondences be-

tween the query and the reference ﬁngerprints, howev-

er, matching can be computationally too expensive,

even for a moderate number of reference ﬁngerprints.

A common approach to narrow down the search is

by dividing the ﬁngerprint database into smaller sets

using ﬁngerprint classiﬁcation. The idea is to match the

query ﬁngerprint against ﬁngerprints of the same ty pe

only. Although this approach can reduce the number

of matches, it is not ver y effective since ﬁngerprints are

unevenly distributed (i.e., more than 90% of the ﬁn-

gerprints belong to only three classes [1]). Several sub-

classiﬁcation systems have been proposed to address

this issue by further dividing some of the classes into

more speciﬁc categories, however, these systems are

much more complex and difﬁcult to implement [1].

A more effective approach to narrow down the

search space is to use indexing. In principle, indexing

can quickly determine if a query ﬁngerprint is in the

database and to retrieve those reference ﬁngerprints

which are most similar to the query ﬁng erprint, with-

out searching the whole database. Therefore, methods

based on indexing are less dependent on the size of

the database. The main idea is to assign an index value

to each ﬁngerprint and match the query against those

reference ﬁngerprints having comparable indices only.

Indexing methods have been very popular in computer

vision for searching large databases of models in

object recognition [2–4]. Therefore, many indexing

schemes for ﬁnger identiﬁcation have their roots in

object recognition.

How Indexing Works

Indexing is a mechanism which, when provided with a

key value, can rapidly access some associated data.

Thus, instead of searching the space of all possible

matches and explicitly rejecting invalid ones, indexing

inverts the process so that only the most feasible

matches are considered for matching. In essence,

indexing serves as a ‘‘ﬁltering’’ step which allows to

verify a query ﬁngerprint agai nst the most similar

ﬁngerprints in the database only. To implement

indexing, certain information about the reference ﬁn-

gerprints is prestored in an index structure. During

identiﬁcation, the index structure is accessed efﬁciently

to narrow dow n the search.

Fingerprint Indexing

491

Typically, a single index can be computed from the

whole ﬁngerprint or multiple indices can be computed

from groups of local features. Using a single index,

ﬁngerprints are mapped to numerical vectors in a high-

dimensional space through a similarity-preserving

transformation. During identiﬁcation, the query

ﬁngerprint is compared against those reference ﬁnger-

prints which are close to the query in the multidimen-

sional space. This approach, also known as continuous

classiﬁcation [5 ], is in essence a classiﬁcation approach,

however, the classes are not disjoint. Commonly, the

orientation image is used in the mapping transforma-

tion, however, different transformations and distance

measures have been proposed [5–8].

Using groups of local features, reference ﬁnger-

prints are represented redundantly in the database

by computing a separate index for each group of

features and making an entry for each index [9–11].

This kind of redundancy provides robus tness during

identiﬁcation by allowing the retrieval of reference

ﬁngerprints that match the query ﬁngerprint only

partially. Speciﬁcally, for each reference ﬁngerprint,

groups of features are extracted and an index is

constructed from each group. The indexed locati-

ons are ﬁlled with entries containing information

about the reference ﬁngerprints. At a minimum, each

entry contains information about the identity of the

reference ﬁngerprint and the group of features that

generated the index.

During identiﬁcation, the information stored in the

index structure is used to quickly eliminate noncompat-

ible matches between the query and the reference ﬁn-

gerprints. To reduce the number of false matches,

geometric constraints can be used [11]. The reference

ﬁngerprints listed in the indexed locations are collected

into a list of candidate ﬁngerprints and the most

often indexed ﬁngerprints are selected for further veri-

ﬁcation. Veriﬁcation works by computing the transfor-

mation between the candidate ﬁngerprints and the

query. Then, the candidate ﬁngerprints are aligned

with the query and their similarity to the query is

estimated by ﬁnding the percentage of candidate fea-

tures that have been aligned with query features.

An Example

Here is an example, based on [9, 10], to illustrate the

use of indexing for ﬁngerprint identiﬁcation. In this

example, matching a pair of minutiae sets is performed

by comparing minutiae triangles, formed by minutiae

triplets, using geometric invariant features. In general,

a pair of corresponding minutiae triangles provides

enough information to compute a geometric transfor-

mation (e.g., similarity or afﬁne) that potentially aligns

the minutiae sets. To compute good alignments, voting

can be applied in the transformation space to ﬁnd

transformations that are supported by many minutiae

triangles [9]. A number of hypothetical transforma-

tions is obtained by considering transformations that

have received a high number of votes. Each hypotheti-

cal transformation is then explicitly veriﬁed by count-

ing the number of aligned minutiae.

The indexing mechanism used in this example

is based on geometric hashing [2]. Speciﬁcally, given

a triplet of minutiae, three geometric invariants can

be computed by considering the triangle formed by

the minutiae triplet. The geometric invariants are

based on the sides and angles of the minutiae triangle,

as shown in Fig. 1, and remain unchanged under

similarity transformations (i.e., translation, rotation,

and scale). First, the sides of the triangle are sorted to

avoid considering all possible orderings:

 l

Then, we compute the following geometric

invariants:

0 

 1

0 

 1

1  cosðAÞ1

where A is the angle between the smallest two sides.

To compute an integer index, a simple hash function

is applied on the geometric invariants which involves

linear scaling followed by quantization. For each index,

Fingerprint Indexing. Figure 1 A minutiae triangle

defined by a minutiae triplet (A,B,C).

492

Fingerprint Indexing

information is stored about the ﬁngerprint and the

minutiae triangle in a hash table. Each entry stored

in the hash table has the following format:

ðperson

ID; print ID; m

; m

where person_ID corresponds to the identit y of the

person whose ﬁngerprint is considered, print_ID is

an identiﬁcation code for the particular ﬁnge rprint

of that person, and m

are the (x,y) coordinates of

the m

minutia in the triangle. Figure 2 illustrates the

indexing step.

During identiﬁcation, each index generated by

the query ﬁngerprint is used to retrieve all reference

ﬁngerprints stored in the hash table under the same

index. For each minutiae triangle, the lengths of the

sides are computed, sorted in ascending order, and

the geometric invariants are computed as before.

Then, the invariants are scaled and quantized in the

same manner. The resulting index is used to extract

all entries from the database stored at the same index

table location. To account for noise, entries stored in

a small neighborhood around the indexed location

could be also retrieved.

Several indexing-based approaches accumulate

evidence about reference ﬁngerprints by casting a

vote for every entry stored in the indexed locations

and by ‘‘histograming’’ the entries to pick the ones

which have received a high number of votes. However,

this approach takes into consideration only the num-

ber of votes received by a particular entry and not

whether these votes are consistent among themselves.

To introduce a measure of coherence, voting in the

transformation space has been proposed [9]. The idea

is simply to consider transformations which form large

clusters in the transformation space.

Each of the entries retrieved from the index

table represents a hypothesized correspondence

between minutiae triplets in the query and a reference

ﬁngerprint. Given this information, the transforma-

tion that best maps the query triplet to the reference

triplet is computed. The computed transformation

parameters are binned and, along with the person_ID

and imprint_ID, form a key that indexes another data

structure used for ev idence accumulation. An eight-

dimensional integer array is used to store the number

of votes in the transformation space (i.e., six dimen-

sions for the parameters of the transformation, one for

the person_ID and one for the imprint_ID).

If a large number of minutiae points can be brought

into correspondence by a transformation, then all the

indices generated by the triangles formed by those min-

utiae points will yield close transformation parameters.

Hence, a larger number of votes for a correct match will

be accumulated. Although there might be a number of

random correspondences between minutiae triplets in

the query ﬁngerprint and some arbitrary reference ﬁn-

gerprints, the likelihood of a number of consistent

transformation parameters being generated by random

correspondences is small, and the veriﬁcation step will

eliminate most of them. Figure 3 illustrates these iden-

tiﬁcation procedure based on indexing.

Practical Issues

Several important issues must be considered

while employing indexing for ﬁngerprint identiﬁcation

including: index construction, index selectivity, storage

requirements, indexing mechanism, performance anal-

ysis, and error analysis. Each of them brieﬂy discussed

in the following section.

Index Construction

As illustrated in the earlier example, each index

is typically constructed from groups of local featu-

res, such as minutiae triplets. In general, index

construction should be based on features that are

robust to ﬁngerprint distortions, occlusion, and noise

[11]. To reduce storage requirements, the computation

of the index is based on geometric invariant features,

Fingerprint Indexing. Figure 2 Pre-storing information

about the reference fingerprints using indexing.

Fingerprint Indexing

493

that is, features that remain unchanged under certain

geometric transformations. In the earlier example, we

used length ratios and angles which are invariant to

similarity transformations (i.e., translation, rotation,

and scale). Other geom etric invariant features include

ridge count, triangle handedness, triangle type, triangle

direction, and maximum side, minutiae density, and

various ridge invariants [9, 11–13].

Index Selectivity

Although indexing is an attractive approach, very often

it becomes less effective because of limited index selec-

tivity. The issue of index selectivity relates to the dis-

crimination power of the features considered for

indexing. Features with low discrimination power

give rise to very similar indices (i.e., low index selectiv-

ity). As a result, a large number of hypothetical

matches can be generated during identiﬁcation,

making indexing ineffective. One way to deal with

this problem is to increase the index dimensionality

using larger groups of features, however, this would

also increase memory requirements since the number

of groups increases exponentially with group size.

Alternatively, additional information can be computed

from each group and added to the index to increase its

dimensionality. For example, the FLASH algorithm,

introduced in [3] for object recognition and adopted

in [9] for ﬁngerprint identiﬁcation, computes a nine-

dimensional index from minutiae triangles. It should

be mentioned that although this is an effective

approach, it increases time requirements and raises

the issue of computing the additional features fast

and reliably. Recent studies using high-dimensional

indices include [11] and [12].

Storage Requirements

Indexing methods have high storage requirements as

they trade space for speed. For example, the number of

entries to be indexed using minutiae triplets is of the

order of O(N

) where N is the average number of

ﬁngerprint minutiae. If M is the number of ﬁnger-

prints to be indexed, the total space requirements is

of the order of O(MN

). To reduce storage require-

ments, geometric constraints can be used to limit the

Fingerprint Indexing. Figure 3 Illustration of the identification step using indexing.

494

Fingerprint Indexing

number of minutiae triangles considered for indexing

[9]. Alternatively, a unique topological structure can be

associated with the ﬁngerprint minutiae using the

Delaunay triangulation [10, 13]. This approach con-

siders only O(N) minutiae triang les for indexing

leading to signiﬁc ant memory savings and faster iden-

tiﬁcation. A problem with this approach is that it is

sensitive to noise and distortions (e.g, introduced by

missing or spurious minutiae), however, both noise

and distortion have only a local effect on the triangu-

lation. Nevertheless, hierarchical matching schemes

have been proposed to deal with these issues [14].

Indexing Mechanism

Hashing has been the most common indexing mecha-

nism used both in ﬁngerprint identiﬁcation and object

recognition. Hashing performs a range search, retriev-

ing all points within a certain distance from the query

point. However, the highest probability hypotheses can

be discovered by observing just a few of the closest

neighbors. Hashing is not efﬁcient for nearest-neighbor

search in high dimensions since it requires time expo-

nential in the dimension of the space (i.e., the nearest

neighbors might not lie in the same hash bin as the

quer y point, but in one of the many adjacent bins).

Moreover, ‘‘good’’ hash functions are required for dis-

tributing the data uniformly [15, 16 ]. In general, more

effective indexing mechanisms can be employed, such

as kd-trees [17], to retrieve only the k nearest points.

Kd-trees are data structures used to divide the data

into hypercubes containing equal numbers of data.

When a query point is presented, the boundaries

between the hypercubes are used as decisions to discover

the hypercube that contains the query point, and the

data in this hypercube will be close matches. To guaran-

tee that the matches in the hypercube containing the

quer y point are in fact closer to the query point than

data lying just over the boundary of the hypercube, it is

necessary to examine neighboring hypercubes. This can

make search quite slow. To deal with this issue, approx-

imate nearest-neig hbor schemes can be used which

maintain good performance even in quite high dimen-

sions (i.e., 10–20) and large number of data [18, 19].

These algorithms have been demonstrated to uncover

the exact nearest neighbor a high percentage of the

time and a very close neighbor in the remaining cases.

Performance Analysis

To analyze the performance of indexing schemes, it is

typical to use identiﬁcation rate versus

▶ penetration

rate graphs. The ratio of ﬁng erprints retrieved over

the size of the database. These graphs show the identi-

ﬁcation rate achieved by varying the penetration

rate. Typically, a low penetration ra te with a high

identiﬁcation rate is desirable. Close to 99% identiﬁca-

tion accuracy with only 5% penetration rate is

reported in [12] on DB1 from FVC2002. Alternative

measures include the

▶ Correct Index Power (CIP)

and the

▶ Correct Reject Power (CRP) [11]. CIP is

deﬁned as the number of correctly retrieved ﬁnger-

prints over the size of the database while CRP is de-

ﬁned as the ratio of correctly rejected reference

ﬁngerprints over the number of query images not

having a corresponding ﬁngerprint in the database.

Using the NIST-4 special database and extrapolating

the results from 2,000 images to 30,000 images, Bhanu

et al. [11] report a CIP rate of 50% using the top 100

candidate matches (i.e., 0.33% penetration rate). Using

a smaller database (i.e., 400 image pairs) and assuming

the top candidate match, they report a CIP rate of

96.2% for good quality images, 85.5% for fair quality

images, and 83.3% for low qualit y images. Using the

top ﬁve candidate matches, the CIP rate increases to

100, 99.2 and 98% correspondingly. The CRP rate

reported using 200 query ﬁngerprints not in the data-

base was 100%.

Error Analysis

In the noise less case, each indexed location will contain

exactly the set of reference groups compatible with the

query group used to access the index structure. In

practice, however, several different sources of error

must be taken into consideration to improve robust-

ness. The most common source of errors is from the

feature extraction step. Using minutiae triplets, for

example, errors in the localization of the minutiae

can lead to errors in the computation of the geometric

invariants and, as a result, to errors in the computation

of the indices. In this case, the correct entries will not

be found in the indexed location but in a neighbor-

hood around it. Several studies have considered the

effect of localization errors on indexing performance

Fingerprint Indexing

495

for object recognition [20]. Other studies model local-

ization errors probabilistically in order to estimate the

appropriate neighborhood size to retrieve the correct

entries [15].

Summary

Indexing is an attractive method for reducing the

number of matches when comparing a query ﬁnger-

print with a ﬁngerprint database for identiﬁcation

purposes. This chapter reviewed the main concepts

behind ﬁngerprint indexing and discussed several crit-

ical issues to be addressed in practice.

Related Entries

▶ Fingerprint Authentication

▶ Fingerprint Classiﬁcation

▶ Fingerprint Identiﬁcation

▶ Fingerprint Matching

References

1. Maltoni, D., Maio, D., Jain, A., Prabhakar, S.: Handbook on

ﬁngerprint recognition. Springer, Berlin (2003)

2. Lamdan, Y., Schwartz, J., Wolfson, H.: Afﬁne invariant model-

based object recognition. IEEE Trans. Robot. Automat. 6(5),

578–589 (1990)

3. Califano, A., Mohan, R.: Multidimensional indexing for recog-

nizing visual shapes. IEEE Trans. Pattern Analy. Mach. Intell.

16(4), 373–392 (1994)

4. Bebis, G., Georgiopoulos, M., Shah, M., da Vitoria Lobo, N.:

Indexing based on algebraic functions of views. Comput. Vision

Image Understand. 72, 360–378 (1998)

5. Lumini, A., Maio, D., Maltoni, D.: Continuous versus exclusive

classiﬁcation for ﬁngerprint retrieval. Pattern Recogn. Lett.

18(10), 1027–1034 (1997)

6. Cappelli, R., Lumini, A., Maio, D., Maltoni, D.: Fingerprint

classiﬁcation by directional image partitioning. IEEE Trans. Pat-

tern Analy. Mach. Intell. 21(5), 402–421 (1999)

7. Cappelli, R., Maio, D., Maltoni, D.: Multispace kl for pattern

representation and classiﬁcation. IEEE Trans. Pattern Analy.

Mach. Intell. 23(9), 977–996 (2001)

8. Li, J., Yau, W.Y., Wang, H.: Fingerprint indexing based on sym-

metrical measurement. Int. Conf. Pattern Recogn. 1, 1038–1041

(2006)

9. Germain, R., Califano, A., Colville, S.: Fingerprint matching

using transformation parameter clustering. IEEE Computational

Science and Engineering 4(4), 42–49 (1997)

10. Bebis, G., Deaconu, T., Georgiopoulos, M.: Fingerprint identiﬁ-

cation using delaunay triangulation. In: IEEE, International

Symposium on Information, Intelligence, and Systems,

pp. 452–459 (1999)

11. Bhanu, B., Tan, X.: Fingerprint indexing based on novel features

of minutiae triplets. IEEE Trans. Pattern Analy. Mach. Intell.

25(5), 616–622 (2003)

12. Feng, J., Cai, A.: Fingerprint indexing using ridge invariants. Int.

Conf. Pattern Recogn. 4, 433–436 (2006)

13. Ross, A., Mukherjee, R.: Augmenting ridge curves with minutiae

triplets for ﬁngerprint indexing. In: Prabhakar S., Ross A. (eds.)

SPIE Defense and Security Symposium (Biometric Technology

for Human Identiﬁcation IV, vol. 6539) (2006)

14. Uz, T., Bebis, G., Erol, A., Prabhakar, S.: Minutiae-based tem-

plate synthesis and matching using hierarchical delaunay trian-

gulation. In: IEEE International Conference on Biometrics:

Theory, Applications and Systems (2007)

15. Wolfson, H., Rigoutsos, I.: Geometric hashing: An overview.

IEEE Comput. Sci. Eng. 4(4), 10–21 (1997)

16. Bebis, G., Georgiopoulos, M., La Vitoria Lobo, N.: Using self-

organizing maps to learn geometric hashing functions for

model-based object recognition. IEEE Trans. Neural Networks

9(3), 560–570 (1998)

17. Li, W., Bebis, G., Bourbakis, N.: Integrating algebraic functions

of views with indexing and learning for 3D object recognition.

IEEE Workshop on Learning in Computer Vision and Pattern

Recognition (2004)

18. Nene, S., Nayar, S.: Closest point search in high dimensions.

In: Computer Vision and Pattern Recognition Conference,

pp. 859–865 (1998)

19. Beis, J., Lowe, D.: Shape indexing using approximate nearest-

neighbor search in high-dimensional spaces. In: Computer Vi-

sion and Pattern Recognition Conference. pp. 1000–1006 (1997)

20. Grimson, W., Huttenlocher, D., Jacobs, D.: A study of afﬁne

matching with bounded sensor error. Int. J. Comput. Vision

13(1), 7–32 (1994)

Fingerprint Individuality

Fingerprint Individuality is the study of the extent of

which different ﬁngerprints tend to match with each

other. It is the most important measure to be ascer-

tained when ﬁngerprint evidence is presented in court

as it reﬂects the uncertainty with the decision of the

expert.

▶ Individuality of Fingerprints

496

Fingerprint Individuality

Fingerprint Matching, Automatic

JIE TIAN,YANGYANG ZHANG,KAI CAO

Center for Biometrics and Security Research & The Key

Laboratory of Complex System and Intelligence

Science Chinese Academy of Sciences, Institute of

Automation Zhingguancun Donglu, Beijing , China

Synonyms

Fingerprint comparing; Automatic

Definition

In contrast to manual ﬁngerprint matching, automat-

ic ﬁngerprint matching can be efﬁciently operated on

a computing machine following a series of preset

procedures. Automatic matching compares two

given ﬁngerprint templates (raw images or extracted

features) and returns their similarity score (in a con-

tinuous range) or a binary decision (matched/

non-matched).

Introduction

With the increasing expansion of large-scale databases,

manual ﬁngerprint matching cannot satisfy the de-

mand of efﬁciency in many applications. Automatic

ﬁngerprint matching simulates how human experts

compare the ﬁngerprints to measure the similarity

between two given ﬁngerprint templates or to deter-

mine whether they come from the same ﬁnger [1]. For

most ﬁngerprint matching procedures, experts calcu-

late the similarity score of two templates and give the

ﬁnal judgment with a preset threshold. If the score

exceeds the threshold, the compared templates are

considered matched, otherwise they are non-matched.

The templates are the representation of ﬁngerprints,

comprising extracted features or the raw images in case

of no extraction. The features can be categorized into

two kinds: local features (minutiae, pores) and global

features (compressed raw ﬁngerprint, ridge pattern,

orientation and curvature map).

Fingerprint matching is one of the most important

stages in

▶ Automatic Fingerprint Identiﬁcation Sys-

tem (AFIS). It is really difﬁcult to match the different

impressions of the same ﬁnger and ﬁnd the

corresponding features reliably because of the following

interferential factors. First, there are several kinds of

transformation between two impressions, including lin-

ear transformation (translation, rotation, and scale) and

non-linear distortion. The translation and rotation is

caused by the differential ﬁnger placement with respect

to the sensor surface during different acquisitions, which

may result in a partially overlapped area. If the impres-

sions are captured by different sensors with different

resolutions, there exists scale variation in the transfor-

mation space. The non-linear distortion of ﬁngerprints

is inevitable because the capture is a process of mapping

a three-dimensional ﬁnger to a two-dimensional im-

pression. The pattern of distortion is ﬁrstly determined

by ﬁnger pressure, ﬁnger condition, and the character-

istics of sensors. Secondly, the quality of raw ﬁngerprints

are also inﬂuenced by the noise (ﬁngerprint residues

from the previous capture), skin condition (dryness,

grease, skin disease), and the capture environment (hu-

midity, temperature). Figure 1 displays three examples

of these interferential factors in ﬁngerprint matching.

In addition, the algorithms of ﬁngerprint enhancement

and feature extraction are imperfect and often intro-

duce some mistakes into the extracted features. Errors

may be made and accumulated during each of the

foregoing stages (orientation estimation, singular

points detection and minutiae extraction). These

objective factors are likely to generate spurious features

or miss genuine features. All the above variations

may make the templates from the same ﬁnger appear

quite different, sometimes more severely than the

similar templates from different ﬁngers. Many ﬁnger-

print matching algorithms have been proposed in the

scientiﬁc literature. Most of these algorithms are

proved successful when dealing with good-quality ﬁn-

gerprints. However, ﬁngerprint matching is still a

challenging task due to the difﬁculty in matching

low-quality, partial, or large-distorted ﬁngerprints.

There have been a series of strategies to cope with the

transformation between two ﬁngerprints. In most of

typical ﬁngerprint matching processes, alignment is uti-

lized to estimate the optimum linear transformation

between two ﬁngerprints. It rotates and translates one

of the compared templates in order to mak e its features

mostly overlap the corresponding features in another

template. To achieve the optimum feature-pairing

requires correctly calculating the parameters of transla-

tion and rotation. Note that scale has to be taken

Fingerprint Matching, Automatic

497

into account when the resolutions of ﬁngerprints vary.

Previous researches [2] prove that the performance

of the matcher drastically decreased when the com-

pared ﬁngerprints originated from sensors with

different resolutions. Fingerprint alignment is certainly

an important but time-consuming stage. Therefore,

some algorithms [3] attempt to avoid this stage in

ﬁngerprint matching. For instance, experts construct

Fingerprint Matching, Automatic. Figure 1 Three examples of these interferential factors in fingerprint matching.

(a) a pair of ﬁngerprints with large translation and rotation; (b) a pair of poor-quality and partially overlapped ﬁngerprints;

maximal distance of corresponding minutiae in red ellipse is above 100 pixels.

498

Fingerprint Matching, Automatic

local feature structures invariant to the linear transfor-

mation for matching without priory global alignment.

Such matching algorithms ignore the global relationship

among local features and therefore may lose part of the

discriminating information. On the other hand, non-

linear distortion is univ ersal during ﬁngerprint acquisi-

tion,soitisneededtodevelopﬁngerprintmatchers

tolerant of the distortion. Some methods [4, 5] allow

corresponding features to alter in the predetermined

range (tolerance box). Others [6, 7] adopt local feature

structures for matching because distortion affects to a

lesser degree local areas. Few developers [8, 9] intro-

duce an appropriate model to recover the distortion

prior to matching. In general, tolerating more trans-

formations may increase the successful percentage of

not only

▶ genuine matching but ▶ imposter match-

ing. When designing the matching algorithms, the

degree of tolerance needs careful evaluation. Based on

the calculated transformations, the correspondences

between features can be established through the opti-

mization methods.

Classification

Because ﬁngerprint matc hing algorithms rely heavily

on the stored features in the templates, they can be

coarsely classiﬁed into three categories in terms of the

selection of features:



Local feature-based matching: The most popular

local feature is minutia, which was earliest used in

ﬁngerprint matchin g technologies [5]. Minutiae

features are extracted and stored in the templates

as sets of points in the two-dimensional plane.

They are usually described by the location, orienta-

tion, t ype, and other information in the neighbor-

hood region. Most common minutia e matching are

addressed as a point pattern matching problems

and many approaches can be applied. Furthermore,

several adjacent minutiae are constructed as local

structures in various forms of minutiae, such as

simplex [10] triangle [6] and so on.



With the advent of high-resolution ﬁngerprint sen-

sors, more precise local features (pores and ridge

contours [11]) are employed in ﬁngerprint match-

ing to satisfy the growing demand and require-

ments for accuracy. These algorithms usually

align two different templates to establish the

correspondences between two sets of local features

and calculate the similarit y score combining all the

matched features. Compared to other ﬁngerprint

features, local features have several advantages in

terms of the template size and its discriminability,

but they have inevitable drawbacks in practical

usage. Sometimes it is difﬁcult to exactly obtain

local features due to its sensitivity to the ﬁngerprint

quality and capture area, which seriously degrades

the performance.



Global feature-based matching: The global fea-

tures represent the ﬁngerprint in a global per-

sp ective, many of which are more continuous

and smooth every where except in some special

regions. For poor-quality or par tial ﬁngerprints,

g lobal features can be extracted more reliably. It

is t oo space-and time- consuming to directly store

and compare the m ap/ﬁeld of features pixel by

pixel. To reduce the template size and simplify

the m atching , features can be approached w ith

appropriat e models and stored as a serie s of

parameters. Global feature-based matching [ 12]

overlaps two given templates with different trans-

formation parameters and estimates the similarity

score between the corresponding cells. Compared

to loca l features, the global features have less dis-

tinctness, so they are often exploited together w ith

other features or in the preprocessing stage of

ﬁngerprint matching.



Combined feature-based matching: Since the local

and global features are somewhat independent and

capture contemporary information, it is reasonable

to improve the discriminating ability of matching

by fusing features. The approaches in this category

[13, 14] combine the local and global features in

the matching stage with available feature-level fus-

ing strategies. The combination can reinforce the

individuality of ﬁngerprints and improve the per-

formance for ﬁngerprint systems on large-scale

databases.



How to select features is pivotal for the effect of

feature combination. It is proved that combining

the irrelative features will bring the most obvious

improvement of accuracy or efﬁciency. On the

other hand, fusing local and global features may

result in additional time or memory cost, so the

appropriate hierarchical strategy can be utilize d to

reduce resource consumption. For instance, due to

the complexity of alignment, two ﬁngerprints can

Fingerprint Matching, Automatic

499