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

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

are not evenly distributed in these classes and there are

some ambiguous ﬁngerprints that cannot be reliably

classiﬁed even by human experts. Therefore, Galton–

Henry scheme that partitions the database into

human-interpretable ﬁngerprint classes is not immune

to errors and does not offer much selectivity for ﬁn-

gerprint searching in large databases.

In fact, it is not obligatory for an automated system

to partition the database into human-interpretable ﬁn-

gerprint classes. In automatic ﬁngerprint identiﬁcation

systems (AFIS), the objective of the classiﬁcation is to

reduce the search space. This objective can be accom-

plished by partitioning the database into machine-

generated ﬁngerprint classes in feature space as long as

the classiﬁcation is consistent and reliable. For example,

some ﬁngerprint index techniques [9, 10] can reduce

the search space more efﬁciently than the Galton–

Henry scheme. Continuous classiﬁcati on techni-

ques [1, 11, 12] do not pre-classify the database, but

represent each ﬁngerprint with a numerical feature

vector. Given a query ﬁngerprint, a class is formed by

retrieving a portion of ﬁngerprints from database

whose feature vectors are close to that of the query

ﬁngerprint. Although these techniques can classify ﬁn-

gerprints into large number of classes, a query ﬁnger-

print needs to be compared with all ﬁngerprints in the

database, which could be time consuming for a large

database. This problem can be circumvented

by incorporating data clustering techniques in the

▶ ﬁngerprint retrieval framework [12, 13 ].

Feature Extraction for Classification

Not all measurements of a ﬁngerprint image remain

invariant for a given individual over the time of cap-

ture and can be used to discriminate between identi-

ties. The ﬁrst step of ﬁngerprint classiﬁcation is to ﬁnd

Fingerprint Classiﬁcation. Figure 1 Six sample fingerprints from the five commonly used fingerprint classes

(arch, tented arch, left loop, right loop, and whorl) under the Galton–Henry classification scheme where two

whorl fingerprints are shown (a plain whorl and a twin loop whorl). Singular points of the fingerprints, called core and

delta, are marked as filled circles and triangles, respectively. Note that ﬁngerprints of an arch class have neither core

nor delta.

440

Fingerprint Classification

salient features that have low intra-class variation and

high inter-class variation. Fingerprint image is an ori-

ented texture pattern that contains ridges separated by

valleys and exhibits two levels of feature as shown in

Fig. 2. At the g lobal level, the orientation ﬁeld and the

ridge frequency are two primitive and fundame ntal

features. At the ﬁne local level, the most prominent

characteristics are the minutia points, where a ridge

terminates or separates into two ridges.

An orientation ﬁeld shown in Fig. 2b of a ﬁnger-

print shown in Fig. 2a contains information about the

local dominant orientations of ﬁngerprint ridges, from

which some other features can be derived such as

singular points and dominant ridge line ﬂow as

shown in Fig. 2. The dominant ridge ﬂow is repre-

sented by a set of curves running parallel to the ridges

lines but not necessarily coinciding with ridges and

valleys. There are two t ypes of singular points: core

and delta points. A core point is the turning point of an

inner-most ridge and a delta point is a place where two

ridges running side by side diverge. Orientation ﬁeld,

dominant ridge ﬂow, and singular points are useful

features for classiﬁcation. A local ridge frequency is

the number of ridges per unit length along a

hypothetical segment orthogonal to the local ridge

orientation. Its’ inverse is the local ridge distance as

shown in Fig. 2a. Although the local ridge distance

varies across different ﬁngers, it is difﬁcult to serve as

a reliable feature due to its high within-ﬁnger variation

caused by the discontinuity of ridges and valleys and

various unfavorable skin and imaging conditions.

However, the average ridge distance over a ﬁngerprint

shows a stable and reliable feature and is employed in

some approaches [12, 13].

Minutia points as shown in Fig. 2a are in general

stable and robust to ﬁngerprint impression conditions.

They often serve as discriminative features for exact

matching in most automatic ﬁngerprint recognition

systems. However, some ﬁngerprint indexing appro-

aches [9, 10] also use minutiae for coarse level ﬁnger-

print search. Another type of feature is the ﬁlter

response of ﬁngerprint image. Gabor ﬁlters are ori-

ented band-pass ﬁlter with adjustable frequency,

orientation, and bandwidth parameters. The responses

of Gabor ﬁlters capture information of ﬁngerprint

local orientation, ridge frequency, and ridge disconti-

nuity and hence can be used for both coarse level

classiﬁcation [5] and exact matching.

Fingerprint Classiﬁcation. Figure 2 A fingerprint image and its feature representation. The orientation field consisting

of fingerprint local orientations is represented by short lines in (b). Core and delta points are marked in both (a) and ( b )by

filled circles and triangles, respectively. Two examples of ridge ending and ridge bifurcation, called minutia points, are

enclosed by circles and squares in (a), respectively. An example of local ridge distance is shown by two arrows in (a). Three

dominant ridge flow curves that can represent the Galton–Henry classes (here: right loop) are shown in both (a) and (b).

Fingerprint Classification

441

Classification Under Galton–Henry

Scheme

Over the last four decades, many techniques have

been developed for the automatic classiﬁcation of ﬁn-

gerprints under Galton–Henry scheme, which can be

coarsely assigned to one of these categories: rule-based,

syntactic, structural, statistical and other approaches.

While rule-based, syntactic and structural approaches

are mainly used to partition the database into the

human-interpretable ﬁngerprint classes deﬁned by

Galton–Henry Scheme, statistical approaches are able

to classify ﬁngerprints into compact clusters in feature

space.

The rule-based approaches codify the human

expert knowledge of manual classiﬁcation such as the

singularity and the geometrical shape of ridge lines. It

is not difﬁcult to see from Figs.1 and 2 that the ﬁve

human-interpretable ﬁngerprint classes can be deter-

mined by the number and location of the singular

points plus some local ridge orientations. Fingerprints

with neither core nor delta points are classiﬁed as arch.

Whorls (plain whorl and twin loop whorl) have one

or two cores and two deltas. Loops and tented arch

contain only one core and one delta. Tented arch is

discriminated from loops by examining the local

orientations lying along the line connecting the core

and delta points. The difference between these local

orientations and the slope of the line is much smaller

for a tented arch than loops. Left and right loops are

distinguished by examining the local orientations

around the core point with respect to the slope of the

line [6]. Although a rule-based approach is simple and

work well on rolled ﬁngerprint with high image qual-

ity, robust and consistent detection of singular points

in a poor quality ﬁngerprint remains a difﬁcult task.

Thus, the rule-based approaches are in general sensi-

tive to noise and cannot work on the partial ﬁngerprint

where the delta point is often missing.

A syntactic method represents a ﬁngerprint by a

sentence of a language extracted from the ridge ﬂow or

orientation ﬁeld. For example, the three dominant

ridge ﬂow curves in Fig. 2 show the typical pattern of

right loop. It is not difﬁcult to see from Figs.1 and 2

that, in general, the ﬁve human-interpretable ﬁnger-

print classes can be distinguished by such dominant

ridge ﬂow curves. In the syntactic approaches, a gram-

mar is deﬁned for each ﬁngerprint class to build up

sentences. Classiﬁcation is performed by determining

which grammar most likely generates the sentence

extracted from a query ﬁngerprint. In general, syntac-

tic methods tend to be robust in the presence of image

noise but often require very complex grammars to

struggle against the large intra-class and small inter-

class variations. Complex grammars often result in

unstable classiﬁcati on.

The structural approaches organize low-level

features into higher-level structure. One approach

partitions the orientation ﬁeld into connected regions

characterized by homogeneous local orientations [11].

For example, it is not difﬁcult to identify some homo-

geneous orientation regions from the orientation ﬁeld

shown in Fig. 2b. A relational graph that shows the

relations among these regions of a ﬁngerprint contains

discriminative information for classiﬁcation. An inex-

act graph matching technique is exploited to compare

the relational graphs with class-prototypes. As a robust

and consistent partition of orientation ﬁeld is not an

easy task, a template-based matching is developed

to guide the partitioning [11]. Another approach

converts the two-dimensional ﬁngerprint structure

into one-dimensional sequence and exploits hidden

Markov model for classiﬁcation [8]. A set of horizontal

lines across the ﬁngerprint is used to extract a sequence

of features. It captures information about the local

orientations and ridge distances and thus has higher

discrimination power than the orientation ﬁeld alone.

Since the structural approaches rely on global struc-

tural information, they can work on noisy images and

are able to deal with partial ﬁngerprints where some

singular points are not available.

Statistical approaches extract a ﬁx-size numerical

feature vector from a ﬁngerprint and exploit statistical

classiﬁers, such as k-nearest neighbor classiﬁers, sup-

port vector machines and artiﬁcial neural networks.

The feature vector can be constructed based on the

orientation ﬁeld [4, 11

, 12] or the responses of Gabor

ﬁlters [5]. As features extracted from different ﬁnger-

print regions show different discriminating power,

some weighting schemes [4, 11, 12 ] or non-uniform

spacing techniques [5, 13] are developed to put higher

weights in more discriminative regions of ﬁngerprint.

Karhunen–Loe

ve (KL) transform and multi-space KL

(MKL) transform [14] are also applied to reduce the

dimensionality of feature vector. Statistical classiﬁers

in general need to be trained with a ﬁngerprint data-

base. As Galton–Henry scheme deﬁnes the human-

interpretable ﬁngerprint classes rather than the natural

442

Fingerprint Classification

clusters of ﬁngerprints in feature space, supervised

training using ﬁngerprint samples with known class

labels is often applied. On the other hand, statistical

approaches are able to classify ﬁngerprints far beyond

the Galton–Henry scheme into much more classes.

Classification with Machine-Generated

Classes

The Galton–Henry Scheme does not offer much selec-

tivity for ﬁngerprint searching in large databases. Most

automated systems [4–8] can only classify ﬁngerprints

into the ﬁve classes shown in Fig. 1 and the probabil-

ities of the ﬁve classes are approximately 0.037, 0.029,

0.338, 0.317, and 0.279 for the arch, tented arch,

left loop, right loop, and whorl, respectively [15].

The uneven distribution of these human-interpretable

ﬁngerprint classes further lowers the classiﬁcation

efﬁciency. In fact, for the application of the automated

identiﬁcation, it is often not obligatory to partition the

database into human-interpretable ﬁngerprint classes.

Any classiﬁcation scheme is in principle workable so

long as different impressions of a same ﬁnger consis-

tently fall into a same class. Instead of grouping ﬁnger-

prints based on the visual appearance of ﬁngerprint

images, we can partition the database in the feature

space into the machine-generated ﬁngerprint classes,

in the hope that more classes can be formed. However,

there are always ﬁngerprints located near the class

boundaries regardless of how well the database is par-

titioned. These ﬁngerprints are likely misclassiﬁed due

to the large variations of different impressions of a

same ﬁnger. To alleviate this problem, ﬁngerprints are

not pre-classiﬁed, but associated with numerical fea-

ture vectors. Given a query ﬁngerprint, a ﬁngerprint

class is then formed by retrieving a portion of ﬁnger-

prints from database whose feature vectors are similar

or have small distance to that of the query ﬁngerprint.

Hence, this scheme is also called ‘‘continuous classiﬁ-

cation’’ [1, 11, 12].

Orientation ﬁeld is often used to construct

the numerical feature vector consisting of local orienta-

tions [4, 11–13]. Note that an orientation angle y is a

periodic variable with a period of 180

∘

rather than

360

∘

and has discontinuity at 90

∘

or 0

∘

and 180

∘

The smallest and the largest angles in a period do not

refer to two orientations far away but rather close to

each other. The distance between two orientations

and y

cannot be naively measured by jy

y

but rather by min(jy

y

j,180

∘

jy

y

j). Thus,

the distance between two feature vectors cannot be

computed by simple arithmetic such as Euclidean

distance. To simplify the distance computation, an

orientation angle y is decomposed into two compo-

nent, cos(2y) and sin(2y)[1, 11, 14] so that the simi-

larity of two ﬁngerprints can be measured by the

convenient dot product of the two feature vectors.

This also enables to put weights on different orienta-

tions, for example, r[cos(2y),sin(2y)], where r is the

weight of orientation y. In fact, the similarity of two

feature vectors can be measured by the consistency of

the orientation differences. Thus, a similarity measure

between two feature vectors O

¼ðy

; y

; :::; y

; :::Þ

and O

¼ðy

; y

; :::; y

; :::Þ is deﬁned by j∑

exp

[2j(y

y

)]j∕∑

, where r

are weights, exp[]isa

complex exponential function and jj is a magnitude

operator [12, 13]. Besides the orientation ﬁeld,

the average ridge distance over the ﬁnge rprint is

also used as an auxiliary feature in some approaches

[12, 13].

Given a query ﬁngerprint, a ﬁngerprint class is

formed by retrieving a number of ﬁngerprints from

the database whose feature vectors are nearest to that

of the query ﬁngerprint. Depending on application

scenarios, different ﬁngerprint retrieval strategies can

be applied, such as a ﬁxed distance threshold, or a ﬁxed

percentage of ﬁngerprints in database to be retrieved,

or some combination of the both [12]. In an identiﬁ-

cation system, ﬁngerprint retrieval and exact matching

can be integrated so that the retrieval threshold

increases from a small value until the query ﬁngerprint

is matched with one of the retrieved templates by a

matching algorithm. The threshold can increase by

a ﬁxed step or based on a ﬁxed number of newly

retrieved ﬁngerprints. The incorporation of matching

in the ﬁngerprint retrieval may greatly improve the

retrieval performance if a good matching algorithm is

applied [1, 11, 12].

The continuous classiﬁcation in general needs to

compare the feature vector of a qu ery ﬁngerprint with

those of all ﬁngerprints in the database. The time

consumption of ﬁngerprint retrieval thus directly

depends on the database size. For large database, the

continuous classiﬁcation could be time consuming. To

circumvent the one-by-one exhausting comparisons of

a query ﬁngerprint with all templates, database is par-

titioned into clusters and hence the query ﬁngerprint

Fingerprint Classification

443

only needs to be compared with the cluster prototypes

[12, 13]. Since in general there are always some ﬁnger-

prints near the cluster boundaries regardless of how

well the clusters are formed, it is crucial to retrieve,

instead of one, a few clusters. For the application of

automated identiﬁcation, this clustering based classiﬁ-

cation scheme is comparable to the Galton–Henry

scheme in terms of the search speed that is indepen-

dent to the database size. But the former has potential

to achieve better classiﬁcation accuracy and efﬁciency.

Fingerprint database in dexing [9, 10] is a closely

related problem to this classiﬁcation scheme. Different

from the clustering based classiﬁcation scheme, how-

ever, ﬁngerprint indexing approaches [9, 10] utilize

minutia points that most automated ﬁngerprint

matching algorithms rely on for the exac t ﬁngerprint

comparison.

Classification Performance

The performance of a ﬁngerprint classiﬁcation system is

usually measured in terms of accuracy or error

rate, efﬁciency or penetration rate, and speed or compu-

tational complexity. The measurements of these perfor-

mance indicators could be quite different on different

ﬁngerprint databases. Therefore, the performance com-

parison of different classiﬁcation algorithms should be

based on the same database. The NIST (National Insti-

tute for Standards and Technology) Special Database 4

is the most often used database for the classiﬁcation

performance evaluation. It contains 2,000 ﬁngerprint

pairs, uniformly distributed in the ﬁve Galton–Henry

classes (see Fig. 1). Some approaches are tested on a

reduced set (cal led Set 2), containing 1,204 ﬁngerprints

extracted from the database according to the real dis-

tribution of ﬁngerprints.

The error rate is computed as the ratio of the

number of misclassiﬁed ﬁngerprints to the total num-

ber of samples in the test set. For a Galton–Henry

classiﬁcation system, a ﬁngerprint is misclassiﬁed if it

is placed in a class different from the human assigned

one as the true class membership of a ﬁngerprint is

determined by human experts. For a system that is

based on the machine-generated ﬁngerprint classes, a

query ﬁngerprint is misclassiﬁed if the retrieved subset

from database contains no ﬁngerprint originating from

the same ﬁnger as that of the query ﬁngerprint.

The error rate of a classiﬁcation system in general

should be reported as a function of the penetration

rate that is a performa nce indicator of the classiﬁcation

efﬁciency.

The classiﬁcati on efﬁciency is measured by the

penetration rate deﬁned as the average ratio of the

number of ﬁngerprints in a class to the total number

of samples in the database [1, 11, 12]. If q

represents

the ratio of the number of ﬁngerprints in class i to the

total number of samples in database and p

is the class

occurrence probability, the penetration rate is calculat-

ed by ∑

. For example, for the ﬁve Galton–Henry

classes with the occurrence probabilities of 0.037,

0.029, 0.338, 0.317, and 0.279, respectively, the pene-

tration rate of a error free classiﬁer (q

¼ p

) is 0.2948,

which lies between the penetration rates of 0.25 and

0.3333 for the four and three equal-sized classes,

respectively.

Figure 3 illustrates the tradeoff between the classi-

ﬁcation error rate and the penetration rate of three

techniques tested on two data sets. Obviously, lower

classiﬁcation error rate can be achieved at higher pen-

etration rate. As higher classiﬁcation accuracy and

efﬁciency are measured by lower error rate and lower

penetration rate, respectively, a lower curve indicates

a better classiﬁcation performance. Table 1 shows the

classiﬁcation results of some Galto n–Henry scheme

based approaches (the ﬁrst seven rows) and the

clustering based approach (the last two rows). All

results are obtained from NIST Special Database 4.

Some approaches are tested on the Set 2 and some

approaches are tested on the second half of the data-

base because they use the ﬁrst half of the database to

train their programs. Classiﬁcation performance on

the real distri buted ﬁngerprints is also resembled by

the ‘‘weighted classes’’ shown in the third and the ﬁfth

columns. Note that Fig. 3 and Table 1 do not serve as a

direct comparison between different algorithms due to

different experimental settings and rate calculations.

More information about the classiﬁcation perfor-

mances of these approaches can be found in the re-

spective references [4–8, 10–12, 14].

Summary

The development of automatic ﬁngerprint identiﬁca-

tion system for large database is a challenging task due

to both accuracy and speed issues. Fingerprint classiﬁ-

cation as a tool to narrow down the searching space of

444

Fingerprint Classification

exact matching can alleviate these difﬁculties. A lot of

different techniques have been developed to automate

the Galton–Henry classiﬁcation scheme, thanks to its

human-interpretability and rigid segmentation of a

database. However, the Galton–Henry classiﬁca-

tion scheme that partitions the database into human-

interpretable ﬁngerprint classes does not reduce the

search space signiﬁcantly. The database partition

based on the machine-generated ﬁngerprint classes

seems to be a more promising alternative for efﬁcient

reduction of the search space. For a classiﬁcation

system that requires high accuracy, a ﬁngerprint rejec-

tion engine can be applied to exclude poor quality

ﬁngerprints at a price of lower classiﬁcation efﬁciency.

Further research efforts are necessary to improve the

classiﬁcation performance.

Related Entries

▶ Fingerprint Features

▶ Fingerprint Indexing

Fingerprint Classiﬁcation. Table 1 Classification error rates in % on NIST Special Database 4 of some Galton–Henry

scheme based approaches (the first seven rows) and the clustering based approach (the last two rows)

Source

Five classes

Five weighted

classes Four classes

Four weighted

classes

Test setP.R. = 20% P.R. = 29.5% P.R. = 28% P.R. = 29.7%

Candela et al. [4] – – 11.4 6.1 Second half

Karu and Jain [6] 14.6 11.9 8.6 9.4 Whole

Jain et al. [5] 10 7.0 5.2 – Second half

Cappelli et al. [11] – 12.9 – – Set 2

Cappelli et al. [14] 7.9 6.5 5.5 – Second half

Senior [8] – – – 5.1 Second half

Park and Park [7] 9.3 – 6.0 – Whole

Jiang et al. [12] 5.3 3.3 3.5 3.2 Whole

Jiang et al. [12] 4.7 2.9 3.2 2.8 Set 2

The penetration rate is shown by the value of P.R. In the columns of ‘‘weighted classes’’, error rates of different classes are weighted by

the class occurrence probabilities in the calculation of the total error rate

Fingerprint Classiﬁcation. Figure 3 Classification error rate against penetration rate: (a) approach A in [ 11] and B

in [12] tested on the the NIST Special Database 4 Set 2 containing 1,204 ﬁngerprint pairs; (b) approach B in [12] and C in

[10] tested on the the second half of the NIST Special Database 4 containing 1,000 ﬁngerprint pairs.

Fingerprint Classification

445

▶ Fingerprint Recognition Overv iew

▶ Identiﬁcation and Authentication

References

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

Fingerprint Recognition. Springer-Verlag, New York (2003)

2. Galton, F.: Finger Prints. McMillan, London (1892)

3. Henry, E.: Classiﬁcation and Uses of Finger Prints. Routledge,

London (1900)

4. Candela, G.T., Grother, P.J., Watson, C.I., Wilkinson, R.A.,

Wilson, C.L.: PCASYS – A pattern-level classiﬁcation automa-

tion system for ﬁngerprints. Technique Report: NIST TR 5647

(1995)

5. Jain, A.K., Prabhakar, S., Hong, L.: A multichannel approach to

ﬁngerprint classiﬁcation. IEEE Trans. Pattern Anal. Mach. Intell.

21(4), 348–359 (1999)

6. Karu, K., Jain, A.K.: Fingerprint classiﬁcation. Pattern Recognit.

29(3), 389–404 (1996)

7. Park, C.H., Park, H.: Fingerprint classiﬁcation using fast fourier

transform and nonlinear discriminant analysis. Pattern Recog-

nit. 38(4), 495–503 (2005)

8. Senior, A.: A combination ﬁngerprint classiﬁcation. IEEE Trans.

Pattern Anal. Mach. Intell. 23(10), 1165–1174 (2001)

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

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

25(5), 616–622 (2003)

10. Tan, X., Bhanu, B., Lin, Y.: Fingerprint identiﬁcation: Classiﬁca-

tion vs. indexing. In: Proceedings of IEEE Conference on Ad-

vanced Video and Signal Based Surveillance, pp. 151–156.

Miami, Florida (2003)

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

classiﬁcation by directional image partitioning. IEEE Trans.

Pattern Anal. Mach. Intell. 21(5), 402–421 (1999)

12. Jiang, X.D., Liu, M., Kot, A.: Fingerprint retrieval for identiﬁca-

tion. IEEE Trans. Inf. Forensics Secur. 1(4), 532–542 (2006)

13. Liu, M., Jiang, X.D., Kot, A.: Efﬁcient ﬁngerprint search based on

database clustering. Pattern Recognit. 40(6), 1793–1803 (2007)

14. Cappelli, R., Maio, D., Maltoni, D.: Fingeprint classiﬁcation

based on multi-space KL. In: Proceedings of Workshop on

Automatic Identiﬁcation Advanced Technologies, pp. 117–120

(1999)

15. Wilson, C.L., Candela, G.T., Watson, C.I.: Neural network ﬁn-

gerprint classiﬁcation. J. Artif. Neural Networks 1(2), 203–228

(1993)

Fingerprint Comparing

▶ Fingerprint Matching, Automatic

Fingerprint Compression

NIGEL M. ALL INSON

Department of Electronic and Electrical Engineering ,

University of Shefﬁeld, Shefﬁeld, UK

Synonym

Fingerprint Image Compression

Definition

Image ﬁles can be reduced in size by exploiting either

more optimized data representation and not compro-

mising the faithful recovery of the source image -

lossless compression, or permitting recovery to within

some distor tion criteria - lossy compression. Finger-

print images are relatively large detailed images, and

their compression can alleviate operational problems

of transmission and storage.

Introduction

Fingerprint images, whether prints obtained directly

from live subjects or forensically recovered latents, are

normally recorded at 500 dots or pixels per inch (ppi)

resolution with an 8-bit grayscale, though there is an

increasing tendency to use a higher resolution of 1,000

ppi that permits accurate rendering of individual sweat

pores along the ridge lines. A single digit print has a

minimum area of about 20 mm  15 mm, which yields

a raw image of about 120 kB; while a tenprint record

card (full set of individual slaps, rolls, and palm prints)

requires several 10 **MB of storage. As national Auto-

matic Fingerprint Identiﬁcation Systems (AFISs) can

contain tens of millions of indiv idual record cards,

storage requirements can be easily in excess of 100 TB

[1]. It was the rapid rise in storage requirements for

developing AFIS installations that drove the need

for effective compression of reference ﬁngerprint

images. With the availability of low-cost, very high-

capacity mass memory, this requirement may not be so

clear today as it was in the early 1990s. Perhaps of

greater importance is the need to transmit, over re-

stricted bandwidth channels, both reference prints and

latents recovered from crime and other scenes to remote

446

Fingerprint Comparing

locations. Clearly, the transfer of images to a remote

AFIS or between AFISs requires agreed standards for

image compression that do not adversely affect the

usage of ﬁngerprints as a reliable and robust biometric.

Mainstream image compression aims to meet both

the requirements of reducing storage requirements and

enabling faster transmission. Signiﬁcant compression

is possible due to the limited acuity of the human

visual system especially our low sensitivity in detecting

low- contrast spatially-ﬁne detail, the limited spatial

resolution of electronic displays and some printing

processes, and that humans are often tolerant of

some degree of visible distortion. The normal image

compression standards have been developed (1) to

provide satisfactory reductions in memory require-

ments for all types of scenes, whereas ﬁngerprints are

a very restricted type of image; and (2) to provide an

acceptable viewing experience for a viewer, whereas

ﬁngerprint image may be studied in great detail by an

expert examiner and may be submitted to extensive

automatic processing on AFIS systems.

Fingerprint Image Standards

The typical ridge-valley period is approximately 500 mm

with width of the ridge varying from about 100 - 300

mm. So a minimum image sampling frequency of

200–300 ppi would be sufﬁcient to record unambigu-

ously the friction skin details including local features or

minutiae. FBI-compliant ﬁngerprint scanners, and the

resultant images, are speciﬁed at 500 ppi. The grey-

scale resolution of some commercial ﬁngerprint scan-

ners is limited to only 2–3 bits though there is a general

recognition that simple binary images, that is 1 bit

deep, are unsatisfactory. For images to have the appear-

ance of a continuous grey-scale approximately a mini-

mum of 100 discrete levels are required, so current

standards specify 8 bit or 1 byte deep grey- scale reso-

lution (i.e., 256 possible levels). Sweat pores are smaller

in diameter than a ridge w idth with an effective diam-

eter that depends on whether the pore is open or

closed. For the capture of pore structures, an image

resolution of 1,000 ppi has been proposed [2] and is

becoming to be accepted by the ﬁngerprint community.

These standards are embodied in current national and

international standards for the data formats for the

interchange of ﬁngerprint information. These stan-

dards also recommend that the overall size of an

image should range from 406  381 mm (800  750

pixels) for a single digit to 1,397  2,032 mm (2,750 

4,000 pixels) for a complete palm print. This translates

to image sizes ranging from about 0.5 MB to 10.5 MB

for 500 ppi images and, of course, four times larger for

1,000 ppi images.

Image Compression

Image compression can be delineated into loss less and

lossy coding schemes. The former referring to an

encoding process that permits the original image to

be retrieved without any degradation. Methods include

Run-Length-Encoding where a consecutive row of

three or more pixels w ith identical grey-scale or color

values are represented by a two-byte pair. This forms

part of several well-known image ﬁle standards such as

TIFF (Tagged Image Format File) and PCX (PC Paint-

brush Exchange). Another approach utilizes entropy

coding which assigns codes to grey-scale or color

values so that code lengths match with the inverse

probabilities of these values. Reductions in storage

requirements are usually very modest – typically less

than 2:1 compression – and will not be discussed further.

However, some AFIS installations do employ lossless

compression for their archived reference images.

Lossy compression means that it is possible only to

recover the original image to within some distortion

criteria. The normal criterion for the acceptability is

based on the non-visibility of coding artifacts under

normal viewing conditions or, at least, the acceptability

of these artifacts. For ﬁngerprint images, the criteria

need to include the absence of any artifacts that could

subsequently interfere with future processing and fea-

ture recognition – either by AFIS algorithms or by a

human expert. With inappropriate compression, it is

more likely that legitimate queries will not be matched

that is the FNMR or FRR, depending on the applica-

tion, will increase. Several approaches have been ex-

plored for lossy compression but the dominant

technique is based upon transforming an image from

the spatial domain to a second domain which is based

on spatial frequencies. Such an approach exploits the

non-random distribution of the spatial frequencies in

the localized objects that make up an image and the

non-uniform sensitivity to differing frequencies by our

visual system. The basic structure of a transform-based

image coder is illustrated in Fig. 1. The decoder, which

Fingerprint Compression

447

recovers the best approximation of the original image

from the transformed one, is essentially the reverse

process. The source encoder employs a (usually) linear

transform such as the Discrete Fourier Transform ,

Discrete Cosine Transform (DCT) or Discrete Wavelet

Transform (DWT) to convert the entire image or some

region of it into the different representational domain.

The quantizer reduces the number of bits employed to

represent the coefﬁcients of the previous transform.

This loss in precision, a many-to-few mapping, is the

major source of compression in the overall encod-

ing process. Quantization may be performed on individ-

ual transform coefﬁcients, termed Scalar Quantization;

or on a group of coefﬁcients, termed Vector Quan-

tization. As there are usually some correlation between

consecutive coefﬁcients which can be usefully exploited,

vector quantization is generally more efﬁcient than

the scalar. Small valued coefﬁcients, below a prede-

ﬁned threshold value, are ignored. Quantizers may uni-

formly reduce the precision of coefﬁcients regar dless

of their magnitude or, more likely, they implement a

non-uniform approximation by giving greater weight

to higher valued coefﬁcients. The ﬁnal stage is an entropy

encoder which losslessly compresses the quantized coef-

ﬁcients to yield a smaller output code stream. Typical

methods include Huffman and Arithmetic coding with

both being variable-length coding schemes but the for-

mer applied to individual coefﬁcients while the latter is

applied to a group of coefﬁcients. Image compression

possesses an extensive literature and a useful introduc-

tion is provided in [3].

The most common image compression is the JPEG

(Joint Photog raphic Expert Group) standard which is

DCT-based; and only the baseline encoder will be dis-

cussed here that sequentially compresses a stream of

8  8 pixel blocks of the image. Each block progresses

through each processing step to yield a compressed

output data stream. As adjacent image pixels are highly

correlated, the forward DCT is the basis for achieving

data compression by focusing most of the energy into

the lower spatial frequency bands. The DCT causes no

loss to the source image but simply transforms it into a

domain where they can be efﬁciently encoded. Each of

the 64 DCT coefﬁcients is uniformly quantized

according to a 64-element quantization table, which

takes into account the fallin g sensitivity of the human

eye to ﬁne spatial details. After quantization, the quan-

tized coefﬁcients are ordered in a zig-zag sequence to

assist the entropy encoding by placing low-frequency

non-zero coefﬁcients before high-frequency coefﬁ-

cients. The DC coefﬁcient, which contains a signiﬁcant

fraction of the total image energy, is differently

encoded. Decoding is essentially the reverse process.

JPEG compression is efﬁcient and simple to impleme nt

especially in dedicated hardware. Good compression

rates can be achieved with little loss of perceived ﬁdeli-

ty for naturalistic scenes up to 20:1 or 30:1 compres-

sion ratios. The use of 8  8 pixel blocks does at higher

compression ratios create objectionable ’’blocking arti-

facts’’ especially in regions of low image contrast.

The basis function for JPEG is a discrete set of

orthogonal cosine waves. Such sinusoidal waves are con-

tinuous in the spatial domain and are, in some sense,

artiﬁcially truncated. There are numerous possible basis

functions – some with limited support, that is they

possess only a non-zero value for a limited interval.

Wavelets are such a function which are deﬁned over a

limited distance and possess a zero average. From a

single prototype wavelet function, the basis set is deﬁned

by a series of dilations and contractions of the prototype.

Wavelets are a group of mathematical functions, of

which the earliest example is the well-known Gabor

function. These functions can be approximated as dis-

crete ﬁlter structures. The variety of wavelet scales can be

achieved efﬁciently using a cascade of high and low pass

ﬁlters that decompose the image into several subbands,

with each subband possessing optimal ﬁlter coefﬁcients

to match the image statistics for that band. Different

numbers of subbands and their scope (bandwidth, ori-

entation, etc), termed decomposition trees, are possible;

and details of these, and other aspects of wavelet com-

pression, are beyond the scope of this essay and the

reader is referred to [4, 5]. As the wavelet transform is

applied to the entire image and basis functions can

overlap, there are no blocking artifacts. The t ype of

artifact visible in highly compressed images is now

low-level ’’ringing’’ around high-contrast edges. Wave-

lets, because of their local support, mimic the different

Fingerprint Compression. Figure 1 Overall structure of generic transform-based image coder.

448

Fingerprint Compression

scales of receptive ﬁelds found in the human visual

system and so produce visually more appealing images

compared to JPEG images compressed to the same

degree. JPEG, with its reliance on coding small blocks,

is limited to moderate compression ratios; while DWT-

based coding provides signiﬁcant improvement in pic-

ture quality up to compression ratios of 70:1–100:1 for

naturalistic scenes.

Fingerprint images are a very constrained class of

image and as such it is reasonable to expect that more

optimum forms of compression exist than provided by

the standard methods. They are also exposed to more

detailed scrutiny than most other images and they are

subjected to extensive image processing and pattern

recognition algorithms when submitted to an AFIS

system. Though many quality metrics can be used

to quantify the distortion introduced in lossy com-

pression ranging from generic measures such as Peak-

Signal-to- Noise (PSNR) to those developed speciﬁcally

for ﬁngerprints (such as the Image Quality Metric

(IQM) [6]). PSNR, for 8-bit images, is deﬁned as:

PSNR ¼ 20 log

255

mse



ð1Þ

where the mean square error (e

mse

) is given by

mse

m1

n1

uðm; nÞvðm; nÞ½

ð2Þ

where u(



) and v(



) are the original and compressed

images respectively – each of size M  N pixels. Higher

PSNR means less distortion with no distortion equat-

ing to a PSNR = 48.13 dB. It is a useful metric in

comparing similar image types. However, the ’’ground

truth’’ for any compression scheme is the effect it

has on the ability of ﬁngerprint experts to make

the same decisions as for the corresponding uncom-

pressed image and an AFIS system to recover the

correct match (or, when searching for matches to a

latent, to rank consistently the most likely tenprint

candidates).

Common Fingerprint Compression

Methods

Three main compression methods have been applied for

the storage, transmission and, display of ﬁngerprints

namely, JPEG, WSQ, and JPEG2000. WSQ (Wavelet

Scalar Quantization) was developed, by the FBI in asso-

ciation with Los Alamos National Laboratory and NIST,

speciﬁcally to reduce the media storage requirements

of the FBI’s expanding AFIS facility by providing

lossy compression over the range 10:1 to 20:1. It has

become an accepted standard for 500 ppi image storage

and transmission. A set of typical set of compressed

image for a latent ﬁngerprint for these three methods is

shown in Fig. 2.

Though the unsuitability of JPEG compression has

been known for some time [7] as it suffers from visible

blocking artifacts and loss of ﬁne details (e.g., ridge

pores) even at relatively low compression rates, it is still

employed in some systems. Wide-area AFIS systems

with connections to remote terminals often employ

such JPEG compression to return reference tenprint

images of potential matches to bureaux. For example,

the UK national AFIS (Ident 1) displays images of

potential tenprint matches as 12:1 JPEGs. It is possible

for examiners to discern deterioration in such images.

JPEG2000 [8] is a relatively new standard for

general-purpose image compression which attempts

to address the limitations of JPEG as well as incorpor-

ating many other functions. It offers both lossless and

lossy compression, provides a tiled representation of

images at multiple resolutions, nonuniform compres-

sion to preserve greater detail in some region of inter-

est, and embedded metadata and security functions

within the image ﬁle. Both WSQ and JPEG2000

schemes are DWT-based, but with major differences

in the form of the decomposition tree, quantization,

and entropy coding employed. The WSQ uses the

Daubechies (9,7) ﬁlter [9] to perform the DWT and

the same ﬁlter is the default for the lossy JPEG2000

transform. The JPEG2000 employs a dyadic decompo-

sition tree, while WSQ employs a ﬁxed structure with

64 subbands (Fig. 3). The greater decomposition struc-

ture of WSQ may enhance compression as it approx-

imates to orthnormalization and be better suited to the

high spatial frequency content of ﬁngerprints over

more general imagery. The decomposition structure

inﬂuences the number and length of the zero coding

runs and so enhances compression, while the bit-plane

scanning order of JPEG2000 permits ﬁner control

to achieve an arbitrarily speciﬁed compression rate.

Both schemes use scalar quantization with JPEG2000

having the quantization step varying in response to the

dynamic range of the respective subband. While for

WSQ, all quantizer steps are uniform except for a

Fingerprint Compression

449