On fingerprint pattern recognition

I'.ttcrJ~ R~o~lnilion

Pergamon Press 1978. Vo[. 10, pp. 15 18. Printed in Greal Britain

ON FINGERPRINT PATTERN RECOGNITION* C. V. KAMESWARA RAO Department of Electrical Engineering, University of Link/Sping, S-581 83, Link/Sping, Sweden

(Received 19 October 1976; in revised form 15 September 1977) Abstract -Stochastic languages have been used for fingerprint classification that it is not possible to classify the fingerprint patterns in the absence the fingerprint. Use of features like downward fork, upward fork, end, etc. have been classification. It is noted that some of the results are either incorrect or the various algorithms are presented. Stochastic languages matrix

Fingerprints

Classification

suggested ~4~ for fingerprint incomplete. Limitations of

Fingerprint registration

Sampling

and position. Fingerprint registration is a process in which we use a reference point and a reference line to define the fingerprint data (3). The reference point and the reference line are invariant and can be detected easily even if the print is rotated, translated and varied in size (within certain limits). Since the authors analysis is based on the position of the sampiing square, the effect of translation and rotation is significant. In the absence of a perfect registration (which is not available to date) the stochastic grammar approach will fail. The following example justifies our comment. Let us consider the 18 x 18 squares in Fig. 2 as a fingerprint sampling matrix. If we consider 16 × 16 squares starting with (1,1) (marked with heavy lines), then it will be accepted by the stochastic grammar G121 with the probability 0.125 x 10 4~. For a complete description of the grammar the reader is referred to {2). The sampling matrix is constructed using the ridge direction having the maximum probability in Table 2 ~2~. Next let us shift the sampling matrix to the left by 1 square. That is the sampling matrix for stochastic analysis will be 16 x 16 squares starting with (1,2) as shown by dotted lines in Fig. 2(a). The string x' derived from the new sampling matrix will be accepted by the stochastic grammar G121 with probability P ( x ' l l 2 1 ) = 0.3 x 10 -69. It can be observed that the probability of accepting the same fingerprint taken at two instances by the same stochastic grammar has varied enormously. Note that we considered only the effect of translation, for the sake of simplicity

INTRODUCTION

Vingerprints are considered as one of the reliable ways of personal identification. The need to process large number of prints in a short time enhanced the role of digital computers in fingerprint classification. Grasselli <1~ suggested the idea of using sampling matrix for fingerprint classification. This approach has been used by several authors. Recently Moayer and Fu Ce~ proposed the use of stochastic languages for fingerprint classification. In the next section we discuss the problems involved in the proposed approach. In order to accommodate large number of fingerprints, prints are classified in a file using features like end of the ridges, bifurcation of the ridges. Malleswara Rao ¢4) proposed a method for extracting the features. Limitations of the proposed method are discussed later. APPLICATION

Features

{2~. In this note we observe of accurate registration of

OF STOCHASTIC

LANGUAGES

Moayer and Fu ~2) proposed a set of stochastic languages for the classification of fingerprints. A fingerprint is divided into 16 × 16 squares and the predominant ridge direction in each of the squares is determined. (Authors assumed 4 possible directions as shown in Fig. 1.) Then the direction code is considered as a string x to measure the probability P(xl Gi), that x being accepted by the stochastic grammar Gi. After determining the probability P(xIG~) for every j, the maximum likelihood criterion is used to decide the pattern class. It seems that the authors have missed one problem in the fingerprint processing, namely the registration of the fingerprint. Prints taken from the same finger at different instances are likely to differ orientation

Y,<, 1 2" 3

* This work is supported by the Swedish National Board for Technical I)evelopment.

Fig. 1. Four directions. 15

16

C . V . KAMESWARA RAO

the other imperfections like rotation, size variation are not considered. It may be argued that the decision procedure can accommodate this much variation in the acceptance probability. The following example shows that it is not possible. Consider the sampling matrix of another fingerprint as shown in Fig. 2(b). It differs from Fig. 2(a) in structure. The string y derived from Fig. 2(b) will be accepted by G 1 2 1 with probability P(ylG12x) = 0.229 x 10 -49. If we decide that both x' and x belongs to the subclass 121, then y also has to be assigned to the same class. The reason for the above failures can be explained as follows. 1. To ensure that the same prints are assigned to the same class, the prints must be registered in such a way that the various squares in the sampling matrix are defined with respect to a reference point and a reference axis. 2. The difference in the production probabilities between two adjacent squares should be small compared to the production probabilities in the two squares, That is, if P20,3 is maximum(P20,3 = im_-a~),3

(l,t) (/'/) ?

f ~ / / / / / i / / - - \ \ \ \ \ \ i,i////// . . . . \ \ \ \[',.~ /i/ / / / / / / . . . . \\\\[\1

lit////

......

\\\\I\',

I!II II I ......

\ \ \ \l\t

IVIIII

\\NN\L

......

I;IIIII ...... h h N klk 1 ILl I I I l l I-- --\-'X,'x\\ \ \ \J IIII/III----\\~ k\\\

/,//>/I1 1 1 - - ~ ]qxxx\;

1 1 1 1 / / I I I I----I I \ I \ \ \ \ I /~/ I/t \ \ . . . . / / Ill \NNJ~

/,/¢i\\--/-//~\\\, Ilk\

S

\ ......

~

I"~.\\I

-j I

--J

Fig. 2(a). Whorl pattern belonging to the mair's class 5 or 6 or 11 or 12. (see Fig. 1.(2))

/ / / / / / / / / / / / I I///// / / / / / / / / / / / / ////

/ / / / /

NNNN NNNN \\\\ NNN\ \ N N ~ , ~ \"N...\ N

.... ....

/ ~ ....

// // // /d/ /// //. :/ . ~( -W l l l ~ \ \\ -.~3_\ /////I

//4/t

I t/i - - i S \ \ \ \ i t~:-J t\\xx\

//l.!_\x-~/li / / ~ ~\\--I-//al // /~/\~\ = x -_-7~_ - ~ n l \

x'~.\

\ \\

"

t\\ i \\ --~ \

Fig. 2(b). Whorl pattern belonging to the mair's class 2 or 8. (see Fig. 1/2)) It differs from the whorl shown in Fig. 2(a) only in the hatched squares.

{P2o,i}) then the following conditions should be valid. (P20, 3 - P4, 3) (P20, 3 -- P3, 3) (P2o, 3 -- fis, 3) (P20,3 - P19,3)

<< P20, 3 << P20, 3 << P20, 3 << /920,3

(P20,3 - P21,3) << P2o,3 (P2o,3 - P35,3) << P2o,3 ( P 2 o , 3 - P36, 3) << /920, 3 and

(P2o. 3 -- P37, 3) << -P20, 3.

If the above conditions are not satisfied then the correlation between two adjacent squares will be very low. For example in the case of N I 3 6 and N137 of Table 2 (2) it is (0.2) (0.2) + (0.01)(0.4) + (0.2)(0.2) + (0.2)(0.59) = 0.2. The example shown in Fig. 2 arises out of the low correlation between some of the adjacent squares. It is doubtful whether one can avoid the other case of failure. That is a misclassification of different types of whorls. We know that the various types of fingerprints differ only in the ridge flow in the pattern area. If we use the sampling matrix, then we cannot detect the ridge curvature in this area. This is further complicated by the fact that the ridge direction changes abruptly in this area (when compared to outside the pattern area) and any change in the size, orientation or position of the fingerprint is going to alter the ridge direction code.

FEATURE EXTRACTION FOR FINGERPRINT CLASSIFICATION

Malleswara Rao (~) proposed a method using minute features in the fingerprint. The proposed method, utilises Deutsch's thinning algorithm after smoothing the binary image of the fingerprint. He suggested two methods for extracting the features like forks, bends and ridge ends from the thinned image of the fingerprint. It appears that some of the results reported in the above paper are either incomplete or incorrect. We shall justify our comments by considering the various algorithms of (4). A binar3, fingerprint is considered as the input to the preprocessor. It is not clear how the author obtained such a clean image from a gray scale picture. To start with, it is not stated whether the smoothing algorithm is to be applied sequentially or parallelly. Let us assume that it is a parallel algorithm. It is stated that the algorithm is simple, but it is not clear how the smoothing operation is achieved with contradicting conditions. A submatrix of 3 x 3 elements (Fig. 3) is considered to arrive at the smoothing conditions. The following 9 conditions and 27 more that follow by the rotation of the lattice through multiples of 90 ° are used. 1. R 1 A R 2 A R 3 A R 7 A R8 = 1; R4 v R5 v R 6 = 0 2. R~ A R2 A R3 A R4 A R s = 1;R6 v R7 v R8 = 0 3. R 1 v R 5 =0

On fingerprint pattern recognition

17

R4

R3

R2

1

1

R5

xij! R~

1

1 *! 1

R6

R7

1

1

R8

:

R7 = 1;R 2 v R 6 v R s = 0 = 1;R+ v Rs = 0 R 6 A R7 = 1;R+ v R 6 v Rv = 0 Rs R+ = 1;R4 v R7 v Rs = 0 R6 = 1 ; R 2 v R7 v Rs = 0 = 1;R2 v R6 v R7 = 0 R8 logical A N D and v stands for logical



Rt

l l. 12. 13. 14.



= 0; R 3

A A A A

Rs R+ R8 R3

= = = =

1; 1; 1; 1;

0 '0 0

,

(

i ' I

Ii

t

+

Ill

1 i I |l

"~ . ~*

t

x

t

t t

I + I i

t 1

l

A

R7

R+ v R 6 Rs v R 6 R,, = 1 R 6 = 1.

=

0

=

1 1

=

1

!i

1

t

'

i

I

lUs~ 1 I i

I I1

l t

t

n

| t;

It

i.

1 I1

|

t

II l

l

, | '

t

1

uI.

.

I1|

It

h .I

u

i

l

|

|

i,,

Ill

I |it

It!

i

l

I

,

l

,

,l

. . .iX . t

l*

lI

,

|

,

I

Ill

l

t.,. qpl'l ,

I

t

t

i

I1 :

I

1

,

I

,

IIIB I I I | I | t

|

1 11

i

Ill

tl

It

~

I

I 1,

,

i | t

t ¢~-+W7It|lilt|

II

ll

,~

l I

l

II|ll

II

tt l' tI

|lLtl+,lllli

I |A itllllll

,,

1

tl

,,,,,| I

lit

111

II,

1

,

4/

~

.

,,,,

x

t ,,:

;

t, ll

it

',, .....

+11 h ,

| Ill

It

It

;

I | L|| Ill

,l,

+ 1i

",+,+

1 1



1

|

It t

t

z

|111

,|,

l ,

II

", 1

|l|l

IIl||llllil l

t

t

,

1

11

+,

1

11

llI|| t

ll t

I

ill III

II|lll

I I

IILIIlttZllIltlllll

I

II I I

,I I

, Ill

III

l: 1

Ill

l

ll

II

I |Ill

lllltl

I I

in p r e p r o c e s s i n g and it need not be a part o f the t h i n n i n g procedure. In fact the c o n d i t i o n (10) in the s m o o t h i n g a l g o r i t h m does the job. Then. the question w h e t h e r Deutsch's a l g o r i t h m is fast or not c a n n o t be answered. It is well k n o w n that such c o m p a r i s o n s are subject to the type of the m a c h i n e used. C o m i n g to the feature extraction, the a u t h o r claimed that method-1 gave 80°,; results, whereas m e t h o d - 2 gave 100% correct results. If one looks at the (Fig. 17 in (41) Fig. 6, the n u m b e r of forks recognized are 8, whereas there are as m a n y m o r e unrecognized (see Fig. 6I. The reason for this failure can be attributed to the insufficient c o n d i t i o n s and i m p r o p e r searching. F o r example, the line s h o w n in Fig. 7 will be recognized as d o w n w a r d as well as u p w a r d fork. It is clear that this is not a fork. T h e three l's b e l o w the imaginary line are a c c o u n t e d in b o t h the blocks 2 and 3 as s h o w n in Fig. 7(b). In fact this is the reason why the false feature FD1 is registered in Fig. 8 (see Fig. 16('*)). A p a r t from this, it is not possible to distinguish b e t w e e n u p w a r d fork, left fork and u p w a r d fork and

i

0

0 1 1

O*

i

0q

0"i

i

i

0

i

0

i i 0

(b)

,

h I ~ll.

1+l I 1

I

Fig. 6. Figure 17 from (4). Missing forks indicated with circles•

i

(3,4)

I t It , , , ,

,+ ,h

[

:l

t

+ +, 1

i

(a)

,

I

',

11

. .I .L l.l . . I. . |.1 . . .

1

,

1

I I ~ I P-q t Iq~

Illll

I

i

l,,

tl

It

:1 . |. t

O*

(1)

~

,

in

1 I

l

t

t t

i

1|

1

I

t

~l~

l

~ll+

(3,5)

(c)

Fig. 4.

101

;

!it •

1

If we look at c o n d i t i o n s 11 14, it is obvious that the a l g o r i t h m is creating isolated O's instead of eliminating isolated l's. F o r e x a m p l e the 1" in the centre cell of Fig. 5 will be m a d e 0 by the c o n d i t i o n s (11-14). Let us consider the a u t h o r ' s conclusions on thinning algorithm. Generally, isolated l's are r e m o v e d

PR

;

t + + t!

A R s

Rt A Re R 2 ,\ R 3 R1 A R 7 R1 A R 2

t+

1

'+

P o i n t X~,j is c h a n g e d from 0 to 1 if any one of the c o n d i t i o n s (l,2) or their m i r r o r image versions are satisfied. P o i n t Rs or R t is c h a n g e d from 0 to 1 p r o v i d e d X~,j = 1, and the c o n d i t i o n 3 and any one of the conditions from 4 to 9 or their m i r r o r image versions are satisfied. Because of the c o n s i d e r a t i o n of the c o n d i t i o n s and their symmetrical r o t a t i o n s t h r o u g h multiples of 90 ° and their m i r r o r images, c o n d i t i o n 2 b e c o m e s superfluous: c o n d i t i o n 2 can be o b t a i n e d by r o t a t i n g 1 by 9 0 For the s a m e reason c o n d i t i o n s 8, 9, 12 and 14 are r e d u n d a n t . T h e c o n d i t i o n s 1-9 can be r e p r e s e n t e d by temphttes as s h o w n in Fig. 4. In Fig. 4, (3,7) m e a n s that the c o n d i t i o n s 3 and 7 are put together. Cells w h i c h are c h a n g e d if the given c o n d i t i o n s are satisfied are indicated with '*, +'. It is n o t clear why the cells m a r k e d '+' should be c h a n g e d from 0 to 1. F u r t h e r c o n d i t i o n s (5,7) can be c o m b i n e d t o g e t h e r by m a k i n g R 7 d o n ' t care (see Fig. 4 (c,e)). The following c o n d i t i o n s 10-14 and their versions after r o t a t i o n t h r o u g h multiples of 90 ~ are used to c h a n g e X~.i from 1 to 0. .10.

1

Fig. 5.

Fig. 3.

4. R 3 m R+ A 5. R 2 A R 3 A 6. R 2 A R 3 A 7. R 2 A R 3 A 8. R 3 A R+ A 9. e 3 A R 4 A (A stands for OR.)

1

0 1 1 O*

0 1 1

0+i O

O* 0

(3,6)

(d)

1

i

0"i l

0

O* 0

(3,7)

(e)

18

C.V. KAMESWARARAO ii

L

1 1 1

rejected

1

1 1

2 3 (a)

(b)

right fork. Depending on the imaginary line the features can be labelled differently. In Fig. 9 we show some examples. Similar examples also can be constructed for other types of features. It is difficult to comment on method-2 as the description is incomplete. However one could see that the search directions in Fig. 8 (4) are quite random. There is one feature which is marked as FHR3 in Fig. 8 and FU3 in Fig. 6. The author justifies the latter, rejecting the first one. It is not known how he decided so.

Fig. 7. I

I l i

I

I ! 1

t

i

l a

i1* I i e

t

1

iL I

t t

t

t1

i

i

.,, iiiiiillllllllllllll

1

I

,

1 1

i

'

t t

!•

L L

tt

.t

L .

1

llllll t II

L

U

i

i

I l IL

111

1

t

I

ilLi

l~t

1

llllli4 ILl I

Ilklll

I

"t

t1t ,

d ,

i

"i,_

zt

/

|

Jill

I

,

t

l

,

,

I

i

I

Ia

I

* IIIl*ll

I]1 Ill

ill

ill



I

I111

li

111111 I

I

lllllllllllllllllll

I

MI~.~ ~ II

1111111

Illllll ttt

ii

*J,,,I tt

tin

1

I

i

t

*tit

11

I

! ,

i-t,' '

t

11

111

1

I1

:

nail

pu,~l

*th i

cut t

'

........ al ~

1 I

It

,

,1 ii1

*

t i

,!¢ .....

it

i H

t i , Ti

, ~ h, i

l

l

t

l

[

t il

'.....

i

m. l

,,,,It

............

I

,

i

illl I

it

t t

t

,t

]

'

I

1 1

i

i

,1

i

,1 l

t

ii

i

,

i111 11111 i

I ,h,,

i i

SUMMARY

*

t

i i~

IDI i I~ t

ii

l

• i

Li

11 I

II t* |

I I

a

t

|l|

It II

I Zl

I

] t

Illill

Fig. 8. Figure 16 from (41. Method/example.

Right fork (a)

Upward fork (b)

Fig. 9.

A set of stochastic languages can be defined for different classes of fingerprint patterns. Considering the sampling matrix of a fingerprint, a set of stochastic languages to classify the fingerprints into classes has been proposed by Moayer and Fu. It is noted that such an approach will fail in the absence of accurate registration of the fingerprints. Features like ridge ends, ridge bifurcations are considered for classification. It is observed that the method suggested by Malleswara Rao for the feature extraction has several limitations.

REFERENCES

1. A. Grasselli, On the automatic classification of fingerprints, in Methodologies of Pattern Recognition (Ed. S. Watanabe). Academic Press, New York (1968). 2. B. Moayer and K. S. Fu, An application of stochastic languages to fingerprint pattern recognition, Pattern Recognition 8, 173-179 (1976). 3. J. H. Wegstein, Manual and automated fingerprint registration. Techn. Note 730, National Bureau of Standards, June (1972). 4. T. Ch. Malleswara Rao, Feature extraction for fingerprint classification, Pattern Recognition 8, 181 192 (1976).

the Author--Kameswara Rao received his B.E. degree from Andhra University, India in 1970 and the M. Tech from Indian Institute of Technology Kanpur, India in 1972. From 1972 to 1974 he worked as engineer with Indian Scientific Satellite Project of Indian Space Research Organisation. Since 1975 he is with Department of Electrical Engineering, Link6ping University, Sweden. He is currently working for his Ph.D. degree in the area of pattern recognition.

About