Fingerprint Classification Using Orientation Field Flow Curves
Fingerprint Classi?cation Using Orientation Field Flow Curves Sarat C.Dass Anil K.Jain
Michigan State University Michigan State University
sdass@https://www.sodocs.net/doc/f35696451.html, jain@https://www.sodocs.net/doc/f35696451.html,
Abstract
Manual?ngerprint classi?cation proceeds by carefully inspecting the geometric characteristics of major ridge curves in a?ngerprint image.We propose an automatic ap-proach of identifying the geometric characteristics of ridges based on curves generated by the orientation?eld called orientation?eld?ow curves(OFFCs).The geometric char-acteristics of OFFCs are analyzed by studying the isomet-ric maps of tangent planes as a point traverses along the curve from one end to the other.The path traced by the isometric map consists of several important features such as sign change points and locations as well as values of local extremas,that uniquely identify the inherent geomet-ric characteristics of each OFFC.Moreover,these features are invariant under changes of location,rotation and scal-ing of the?ngerprint.We have applied our procedure on the NIST4database consisting of4,000?ngerprint images without any training.Classi?cation into four major?nger-print classes(arch,left-loop,right-loop and whorl)with no reject options yields an accuracy of94.4.%
1.Introduction
Fingerprint classi?cation is a coarse level partitioning of a large?ngerprint database,where the class of the input ?ngerprint is?rst determined and subsequently,a search is conducted within the set of?ngerprints belonging to the same class as the input?ngerprint.In this work,we classify ?ngerprint images into4major classes in the Henry clas-si?cation system[5]:arch,left-loop,right-loop and whorl. The arch class can be further divided into two subclasses consisting of the plain arch and tented arch.These5classes of?ngerprints in the Henry classi?cation system are shown in Figure1.While the Henry classi?cation system has many classes,only4,5or7classes have been used in an automatic classi?cation procedure.The reason for using only a small number of classes is because the task of determining a?n-gerprint class can be dif?cult.Important?ngerprint features that aid classi?cation exhibit large variations,thus,
making
(a)
(b)
(c)(d)
(e)
Figure1.Five classes of?ngerprints in the
Henry system:(a)left-loop,(b)right-loop,(c)
arch,(d)tented arch,and(e)whorl.Images
are from the NIST4database[15].
the task of representing these features in an automatic sys-tem challenging.Sometimes,even human experts label the same?ngerprint as being of different classes;for example, 700?ngerprints out of the4,000?ngerprints in the NIST4 database[15]have two different class labels associated with them.
2.Previous Work on Fingerprint Classi?cation
A number of approaches have been developed for auto-
matic?ngerprint classi?cation.These approaches can be grouped into?ve main categories:(i)approaches based on singular points[6,8],(ii)structure-based[1,2,3],(iii) frequency-based[7],(iv)syntactic or grammar-based[11], and(v)approaches based on mathematical models[10].
Hybrid methods combine at least two approaches in(i-v) to arrive at a?ngerprint classi?cation algorithm(see,for example,[2,3]).Some of the hybrid methods have not been tested on large databases;for example,Chong et al[3] used89?ngerprint images.Table1compares the classi?ca-tion accuracies obtained by several?ngerprint classi?cation methods reported in the literature.
1
Table1.A comparison of classi?cation accu-racies(in%)of several?ngerprint classi?ca-tion methods in the literature.Reject rates are also given in percentages.
Method No.4class5class Reject Rate Cappelli et al[1]1,204-87.1a0.0
Chang&Fan[2]2,000-94.85.1 Chong et al[3]89-96.6b0.0 Hong&Jain[6]4,00092.387.50.0 Jain et al[7]4,00094.890.00.0 Karu&Jain[8]4,00091.485.40.0 Minut&Jain[10]4,00091.2-0.0 Wilson et al[16]4,000-94.0c10.0 Dass&Jain4,00094.4-0.0
a using the natural distribution of?ngerprints
b based on the5classes-double loop,whorl,left-loop,right-loop and arch
c using the natural distribution of?ngerprints;equal distribution of each class yields accuracies of84?88%.
The most natural topology for analyzing?ngerprint im-ages is the topology of curves created by the ridge and val-ley structures.This necessitates the use of methods from differential geometry for the analysis of properties of the curves,or curve features.The approach presented in this paper is a combination of the structure-,syntactic-and mathematical-based approaches.For a given?ngerprint im-age to be classi?ed,the algorithm?rst extracts an orienta-tion?eld for the?ngerprint image.Next,orientation?eld ?ow curves(OFFCs)are generated based on the estimated orientation?eld.There are two advantages of using OFFCs for?ngerprint classi?cation:(i)unlike ridge curve extrac-tion,breaks and discontinuities in the OFCCs are avoided, and(ii)the OFFCs are free from small scale ridge oscilla-tions.Each?ow curve is then labelled as either loop(left or right),whorl or arch depending on its intrinsic geomet-ric structure.Rigid mathematical models as in[10]are not adequate for representing all aspects of variability of the OFFCs.We develop robust procedures based on differen-tial geometry for labelling the OFFCs.The geometric char-acteristics of OFFCs are analyzed by studying the changes occurring in the tangent space as a point traverses along a OFFC from one end to the other.The tangent space at each point along an OFFC is isometrically mapped to a refer-ence tangent space.The path traced by the isometric map consists of several important features such as sign change points,locations as well as values of local extremas,that uniquely identify the inherent geometric characteristics of each OFFC.Moreover,since the methodology is derived from differential geometry,these features are invariant un-
Orientation Field
Estimation
Generation of OFFCs
Determine
OFFC labels
Determine
Fingerprint class
Fingerprint class:
W, L, R, A
Input fingerprint
Figure2.Steps involved in determining the
class of a?ngerprint.
der changes of location,rotation and scale.Based on these features,we are able to label the OFFCs into four classes, namely,left-and right-loops,whorl and arch.Subsequently, the labels the OFFCs are processed based on syntactic rules to arrive at a?ngerprint class.We have applied our proce-dure on the NIST4database consisting of2,000?ngerprint images.Classi?cation into4classes of the Henry system results in an accuracy of94.4%with no reject options.We note that our classi?cation accuracy is comparable to the ones reported in the literature(see Table1).
3.General Methodology
3.1.Generating Orientation Field Flow Curves
Our approach to?ngerprint classi?cation involves four major steps:(i)the extraction of the orientation?eld for the given?ngerprint image,(ii)generation of orientation?eld ?ow curves(OFFCs),(iii)labelling of each OFFC into the four classes:left-and right-loops,whorl and arch,and(iv) an overall classi?cation of the?ngerprint image into one of the four classes based on syntactic rules.Figure2shows the steps involved in classifying a?ngerprint image.
Consider a site s in a?ngerprint image I with r rows and c columns.The orientation?eld of I gives the direc-tion of the ridge?ow in a local neighborhood around s for all s∈I.The value of the orientation at site s,o s,is a vector(cosθs,sinθs)T whereθs is the angle of the?ow with respect to the horizontal axis.Opposite?ow directions are equivalent,and therefore,θs can only be determined uniquely in(?π/2,π/2).There are many algorithms in the literature that?nd orientations based on the gray intensities of a given image.However,the orientation?eld estimation
(b)(c)
20406080100120140160180200220
?1
?0.8
?0.6
?0.4
?0.2
0.2
0.4
0.6
0.8
1
Isometric map plot
20406080100120
?1
?0.8
?0.6
?0.4
?0.2
0.2
0.4
0.6
0.8
1
Isometric map plot
(e)(f)
Figure3.Variations in whorl curves:OFFCs
(white curves)labelled as whorls in panels(a-
c)with corresponding graphs of cosγj versus
j in panels(d-f)
algorithm reported in[4]was specially designed for?nger-
print images taking into account the smoothness of the ori-
entations at sites in the image that are close to each other.
Hence,a more robust orientation?eld estimate results(see
[4]for further details).The orientation?eld estimate is ob-
tained for sites s=(x,y)in I where x and y are integers
such that1≤x≤r and1≤y≤c.In order to obtain
the value of the ridge orientation at any site s=(x,y)in
I,we adopt an interpolation scheme.Let m and n be inte-
gers such that m=[x]and n=[y],where[g]stands for
the greatest integer less than or equal to g.The orientation
vector at site s=(x,y)is given by o s=(cosθs,sinθs)T
where
θs=
1
2
tan?1
(i,j)∈{0,1}2
u i v j sin2θ(m+i,n+j)
(i,j)∈{0,1}2
u i v j cos2θ(m+i,n+j)
,(1)
with u0=m+1?x,u1=1?u 0,v0=n+1?y,and
v1=1?v0.The interpolation scheme in(1)is a weighted
average of orientation?eld values at the integer sites(m,n),
(m,n+1),(m+1,n)and(m+1,n+1).The weights
are given by u i v j with(i,j)taking values in{0,1}2.The
interpolation scheme in(1)yields a value of orientation for
all sites s∈I while retaining the original values at the
integer sites.
An OFFC with a starting point s0∈I can be de?ned
iteratively as
s j=s j?1+d j·l j·o s
j?1
(2)
for j=1,2,...,n;d j,with values in{?1,+1},is the?ow
direction from s j?1to s j,l j is the length of the line seg-
ment from s j?1to s j,and o s
j?1
is the orientation vector at
site s j?1.The point s n denotes the termination point of the
OFFC curve,which is achieved when either(i)the bound-
(a)(b)(c)
102030405060708090100
?1
?0.8
?0.6
?0.4
?0.2
0.2
0.4
0.6
0.8
1
Isometric map plot
102030405060708090100
?1
?0.8
?0.6
?0.4
?0.2
0.2
0.4
0.6
0.8
1
Isometric map plot
20406080100120
?1
?0.8
?0.6
?0.4
?0.2
0.2
0.4
0.6
0.8
1
Isometric map plot
(d)(e)(f)
Figure4.Variations in left-loop curves:OF-
FCs(white curves)labelled as whorls in pan-
els(a-c)with corresponding graphs of cosγj
versus j in panels(d-f)
aries of the image is reached,or(ii)when n exceeds a pre-
speci?ed constant N0.The lengths l j specify the sampling
interval of the OFFC.In this paper,we select a common
l j for all the OFFCs,that is,l j=l,say.Each point s0
generates two segments of an OFFC which are obtained by
?xing d1?rst at+1,and then at?1,so that the points s j
in(2)trace opposite directions.The starting points s0are
selected in the following way:Let r start,r end,c start and
c en
d determin
e the top,bottom,left and right boundaries
of the?ngerprint pattern area,and w denote the sampling
width.The points s0are selected such that
s0=(r start+k w,c start+l w),(3)
with either(i)k=1,2,...,[r end?r start]and l=
[c end?c start]or,(ii)k=[r end?r start]and l=
1,2,...,[c end?c start].In other words,the starting points
are sampled along the horizontal and vertical lines that pass
through the midsection of the?ngerprint pattern area.Fig-
ure2shows how the OFFCs are generated given a?nger-
print image.We proceed with the labelling of each OFFC
curve using methods developed from differential geometry
[14]in the next section.
3.2.Tangent space isometric maps of OFFCs
Our goal in this section is to label each OFFC into one
of the four classes based on their global geometric shapes:
left-and right-loops,arch and whorl(see the left panels of
Figures3,4,5and6for examples of each class).Obtaining
explicit mathematical models for the global geometric char-
acteristics of OFFCs will often be too rigid to adequately
represent all possible variations of these curves.Therefore,
we adopt a non-model based approach here.We discuss
several robust features of the OFFCs that allow us to infer
(b)(c)
20406080100120
?1
?0.8
?0.6
?0.4
?0.2
0.2
0.4
0.6
0.8
1
Isometric map plot
102030405060708090100
?1
?0.8
?0.6
?0.4
?0.2
0.2
0.4
0.6
0.8
1
Isometric map plot
(e)(f)
Figure5.Variations in right-loop curves:OF-
FCs(white curves)labelled as whorls in pan-
els(a-c)with corresponding graphs of cosγj
versus j in panels(d-f)
the underlying class based on methods of differential geom-
etry.
Letα(t)≡(α1(x(t),y(t)),α2(x(t),y(t)))T with t∈
[t0,t1]denote a curve in the R2plane passing through
the point(x0,y0).The tangent vector at(x0,y0)is
(α 1(x0,y0),α 2(x0,y0))T,where the derivative is taken
with respect to t.We de?ne V(x
0,y0)
to be the translation
of(α 1(x0,y0),α 2(x0,y0))T so that the starting point of
V(x
0,y0)
is at the origin(0,0).The tangent plane,T(x
0,y0)
,
at point(x0,y0)for the curveαis a one-dimensional plane
generated by the tangent vector V(x
0,y0)
,that is,
T(x
0,y0)
={u·V(x
0,y0)
:u∈R}.(4)
In other words,T(x
0,y0)
is the set of all tangent vectors at
the point(x0,y0)translated to the origin.
Any mapping of points in the plane,F:R2→R2has
a tangent map F?that carries each tangent vector v at point
p to a tangent vector F?(v)at point F(p).The map F is
said to be an isometry if it preserves distances,that is,
d(p,q)=d(F(p),F(q)),(5)
where d is the Euclidean distance in R2.In the case of
an isometric map,the tangent map,F?,is very simple to
describe:each tangent vector v at p is“rotated”in exactly
the same way by F?,and translated to the point F(p).In
other words,the tangent map F?,modulo translations,can
be uniquely described by a rotation angleγ.
For a given OFFC,we compute the isometric maps as
follows:Let one end point of the curve be denoted by p0
and the other by p N.Our analysis is not affected by which
end is selected as p0.De?ne the chord vector V1≡1
δ
(x1?
x0,y1?y0)T,where p0≡(x0,y0),and p1≡(x1,y1)
is a point on the curve at a distanceδfrom p0.The plane
(a)(b)(c)
102030405060708090100
?1
?0.8
?0.6
?0.4
?0.2
0.2
0.4
0.6
0.8
1
Isometric map plot
1020304050607080
?1
?0.8
?0.6
?0.4
?0.2
0.2
0.4
0.6
0.8
1
Isometric map plot
102030405060708090
Isometric map plot
(d)(e)(f)
Figure6.Variations in arch curves:(OFFCs
(white curves)labelled as whorls in panels(a-
c)with corresponding graphs of cosγj versus
j in panels(d-f)
spanned by V1is denoted by T1,and the unit vector by e1≡
V j/||V j||.Subsequent chord vectors,V j,are obtained as
V j≡1
δ
(x j?x j?1,y j?y j?1)T,where p j≡(x j,y j)are
points on the curve at a distanceδapart for j=2,...,N,
with the spanned plane denoted by T j,and the unit vector
by e j≡V j/||V j||.Note that T j coincides with the tangent
plane of some pointsξj on the OFFC which lies between
p j?1and p j,for j=1,2,...,N.With T1as the reference
plane,we obtain the isometric maps F?s in terms of the
rotation anglesγj that is needed to rotate the plane T1to
match T j,withγ1≡0.The feature we consider is the
cosine ofγj which can be obtained as
cosγj=e1?e j(6)
for j=1,2,...,N,where?is the Euclidean inner product
on R2.The right panels of Figures3,4,5and6show the
graphs of cosγj versus j as the point on an OFFC traverses
from p0to p N for the classes whorl,right-loop and arch,
respectively.
3.3.Salient Features Of Isometric Maps
Figures3-6give the isometric map plots obtained for the
different classes of OFFCs:left-loop,right-loop,whorl and
arch.Salient features of the graphs are(i)the number and
locations of sign-change points,and(ii)the number and lo-
cations of local maximums and minimums.These features
are robust with respect to variations within each curve class.
Figures3(b),(d)and(f)give the graphs of the isomet-
ric maps for several different OFFCs of type whorl(indi-
cated by a white curve in the corresponding left panels).
The salient features(comparing Figures3(b),(d)and(f))
of the isometric map plots include:(i)several(more than
(a)(b)
(c)(d)
(e)
Figure7.OFFCs for the?ve different classes
(a)left-loop,(b)right-loop,(c)arch,(d)tented
arch,and(e)whorl.All these?ngerprints
have been correctly classi?ed.
one)sign-change points with local maximum and minimum values of+1and-1,respectively,between locations of sign-change points.In Figures4(b),(d)and(f),we have plotted the graph of the isometric map for different left-loops of OFFCs in the corresponding right panels.The salient fea-tures of left-loop class remain the same:one sign-change point followed by one local minimum value of-1.Figures5 (b),(d)and(f)give the isometric map plots of OFFC curves that are right-loops.Note that,similar to the left-loop,the features of the right-loop include one sign-change point fol-lowed by one local minimum value of-1.In the case of an arch type,the salient features include either(i)no sign-change points,or(ii)exactly one sign-point with the value of the local minimum far from-1.In order to determine whether a local maximum is close to or far way from+1, we use a threshold parameter,λ,0<λ<1.The value of a local maxima is determined to be close to+1if it exceeds λ.Similarly,the value of a local minimum is determined to be close to-1if its value falls below?λ.
Note that features of the isometric map plot cannot dis-tinguish between a left-and a right-loop.Once an OFFC is determined to be of type loop,a further test is necessary to classify the OFFC as either a left-or a right-loop.In order to do this,we write each chord vector V j≡(V x j,V y j)T, and de?ne U j=V x j·V y j.Left-loops correspond to sign changes of U j from+1to-1and back to+1,whereas right-loops correspond to sign changes of U j from-1to+1and back to-1.
3.4.Fingerprint Classi?cation
Let N T denote the total number of sampled OFFCs.We denote by N w,N l,N r,N a to be the number of OFFCs la-belled as whorl,left-loop,right-loop and arch(N w+N l+
(a)Input image(b)Orientation?eld(c)OFFCs
(d)Input image(e)Orientation?eld(f)OFFCs
Figure8.Noise in?ngerprint images leading
to errors in classi?cation.The true and as-
signed classes of the?ngerprints in the top
(bottom)panels are left-loop and arch(left-
loop and whorl),respectively.
N r+N a=N T).We select pre-speci?ed threshold parame-tersλw,λl andλr to?lter out noise in the labelling process. Our?ngerprint classi?cation procedure is described as fol-lows:If N w≥λw,the?ngerprint is assigned the class “whorl”;otherwise,we go to the next stage and consider the values of N l,N r and N a.If N l≥λl and N r<λr, the?ngerprint is classi?ed as“left-loop”;if N l<λl and N r≥λr,the?ngerprint is classi?ed as right-loop.If both N l<λl and N r<λr,the?ngerprint class assigned is “arch”.
4.Experimental Results
The methodology presented in the previous sections were validated on the NIST4?ngerprint database[15].The NIST4database contains2,0008-bit gray scale?ngerprint image pairs,for a total of4,000images.Each image is512-by-512pixels with32rows of white space at the bottom and is classi?ed into one of the following?ve classes:arch(A), left-loop(L),right-loop(R),tented arch(T)and whorl(W). The database is evenly distributed over the?ve classes with 800?ngerprints from each class.For our classi?cation pro-cedure,we combined classes“arch”and“tented arch”into a single“arch”class.The orientation?eld estimate was obtained using the approach described in[4].The estimate of the orientation?eld was obtained for the central part of the?ngerprint image,leaving out a boundary of50pixels along each side of the image,that is,r start=c start=51 and r end=c end=470(see Section3.1).For obtaining each OFFC,we selected a step size of l=5pixels.
The threshold parameters for classi?cationλw,λl andλr were?xed at2,2and1,respectively.The value ofλwas selected to be0.90.The classi?cation results are presented
Table2.Classi?cation results of?ngerprints
in the NIST4database into four classes:A,L,
R,and W
Assigned Class
True A L R W Total Accuracy(%)
A79721080099.62
T781190080097.62
L637301680091.25
R754720180090.00
W12231874780093.34
in Table2with no reject option.For?ngerprints that have two class labels,we determined that the assigned class is correct if it is one of the true labels.The overall accuracy of the classi?cation procedure is obtained to be94.4%.From Table2,we see that the best classi?cation was obtained for the class“arch”while the worst classi?cation rates were ob-tained for the classes left-loop and right-loop.We note that our method of classi?cation with no reject option achieves an accuracy that is comparable to the ones reported in the literature.Figure7shows the OFFCs for the?ve?ngerprint classes in the Henry system shown in Figure1.All these ?ngerprints have been correctly classi?ed.
Sources of errors in our classi?cation procedure can be assigned to one of the following factors.Spurious or missed patterns in the orientation?eld estimate,due to presence of random cuts and ink smudges in the?ngerprint image,re-sult in OFFCs with erroneous labels.Non-uniform illumi-nance at various regions of the?ngerprint image severely distorts the ridge-valley structures and makes the extraction of a correct orientation?eld dif?cult(see Figure8).Also, some left and right-loop?ngerprints have a very small loop areas which are not detected by the extracted orientation ?eld;these?ngerprints are misclassi?ed as arch.
5.Summary and Conclusions
An approach for identifying the geometric characteris-tics of OFFCs using graphs of tangent space isometric maps is developed.Salient features of the graphs are robust with respect to variations within each class of loops,whorls and arches,and are invariant under changes in translation,ro-tation and scaling.Left-and right-loops are distinguished using the sign changes that occur for the component-wise product of the tangent vectors.The class of a?ngerprint is determined from the labels of each OFFC.Our classi?ca-tion procedure achieves a classi?cation accuracy of94.4%, a rate comparable to the ones reported in the literature.Fu-ture work will include detecting the smaller loop areas and classifying?ngerprints into?ve Henry classes:left-loop, right-loop,whorl,arch and tented arch.References
[1]R.Cappelli,A.Lumini,D.Maio,and D.Maltoni.Fin-
gerprint classi?cation by directional image partitioning.
IEEE Trans.on Pattern Analysis and Machine Intelligence, 35:1209–1223,2002.
[2]J.Chang and K.Fan.A new model for?ngerprint classi?-
cation by ridge distribution sequences.Pattern Recognition, 35:1209–1223,2002.
[3]M.M.S.Chong,T.H.Ngee,L.Jun,and R.K.L.Gay.Ge-
ometric framework for?ngerprint image classi?cation.Pat-tern Recognition,30(9):1475–1488,1997.
[4]S.C.Dass.Markov random?eld models for directional?eld
and singularity extraction in?ngerprint images.To appear in IEEE Trans.on Image Processing,2004.
[5] E.R.Henry.Classi?cation and Uses of Fingerprints.Lon-
don:Routledge,1900.
[6]L.Hong and A.K.Jain.Classi?cation of?ngerprint images.
Proceedings of the11th Scandinavian Conference on Image Analysis,Kangerlussuaq,Greenland,June7-11,1999. [7] A.K.Jain,S.Prabhakar,and L.Hong.A multichannel ap-
proach to?ngerprint classi?cation.IEEE Transactions on Pattern Analysis and Machine Intelligence,21(4):348–359, 1999.
[8]K.Karu and A.K.Jain.Fingerprint classi?cation.Pattern
Recognition,29(3):389–404,1996.
[9] D.Maltoni,D.Maio,A.Jain,and S.Prabhakar.Handbook
of Fingerprint Recognition.Springer-Verlag,New York, 2003.
[10]S.Minut and A.K.Jain.Hierarchical kernel?tting for?n-
gerprint classi?cation and alignment.Proc.of International Conference on Pattern Recognition,Quebec City,August11-15,2002.
[11] B.Moayer and K.S.Fu.A syntactic approach to?ngerprint
pattern recognition.Pattern Recognition,7(1):1–23,1975.
[12] B.Moayer and K.S.Fu.An application of stochastic lan-
guages to?ngerprint pattern recognition.Pattern Recogni-tion,8:173–179,1976.
[13] B.Moayer and K.S.Fu.A tree system appraoch for?nger-
print pattern recognition.IEEE https://www.sodocs.net/doc/f35696451.html,put.,25(3):262–274,1976.
[14] B.O’Neill.Elementary Differential Geometry.Academic
Press,London,UK,1997.
[15] C.I.Watson and C.L.Wilson.Nist special database4,?n-
gerprint database.National Institute of Standards and Tech-nology,March1992.
[16] C.L.Wilson,G.T.Candela,and C.I.Watson.Neural net-
work?ngerprint classi?action.J.Arti?cial Neural Networks, 2:203–228,1994.