Albert M. (ed.) Biometrics - Unique and Diverse Applications in Nature, Science, and Technology

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

Toward An Efficient Fingerprint Classification

Fig. 6. Frequency transformation for each class (up left (Arch), up right (Left Loop), down

left (Right Loop), down right (Whorl))

Fig. 7. The patterns extracted from sub images in Figure 6. Numbers inside the dashed

circles are representing the block order

Biometrics - Unique and Diverse Applications in Nature, Science, and Technology

0 25 50 75 100 125 150

0.8

1.2

1.4

Pixel Order

Difference Coeffecients

Arch Left Loop

0 25 50 75 100 125 15

0.6

1.2

1.4

Pixel Order

Difference Coeffecients

Right Loop Whorl

Fig. 8. Difference between the standard patterns and a Whorl patterns

0 25 50 75 100 125 150

0.8

1.2

1.4

Pixel Order

Difference Coeffecients

Arch Left Loop

0 25 50 75 100 125 15

1.2

1.4

Pixel Order

Difference Coeffecients

Right Loop Whorl

Fig. 9. Difference between the standard patterns and a random input pattern (Arch)

Toward An Efficient Fingerprint Classification

3.5.2 Correlation-based matching

Image correlation is much easier especially in frequency domain. The key issue of our

proposed algorithm is the response time. We conducted intensive experimental work on

performing pattern matching in frequency domain to make the processing time as short as

possible. Comparing to image difference method, image correlation give a shorter response

time with high matching accuracy. Also, the output data of the correlation process is little and

it could be plotted or represented easily. Figure 10 and Figure 10 both are the result of the

comparisons with the standard pattern with a Whorl pattern and a random pattern,

respectively. In the graphs, "Block Number" is the number for the order of the four sub-images,

(1), (2), (3), and (4) for up left, up right, down left, and down right, respectively. By the result,

we can see that the correlation-based matching is also applicable for the patterns matching.

3.6 Decision making

The decision maker is responsible for selecting the final class from the information provided

by the pattern matching stage. As we mentioned before, the matching results are stored in a

matrix, and we use only the maximum matching values to preserve memory and plot the

results in acceptable format. In the experiments in the following section, we considered the

simple total of the elements of the matrix. However, there is scope for further study also

about strategy of the decision making.

3.7 Singular points detection

In (Section 3.2), fingerprint images are divided simply based on the length. However, we

are considering that the accuracy of classification should be improved by an ingenious

scheme of the division. Figure 1 shows the common classes of fingerprint with core and

delta points. The most popular approach for detecting fingerprint singularities is the

method based on the Poincaré index. We describe the basic idea of the method in the rest of

this subsection.

Since the Poincaré index is working on the direction changes, then the first step before

calculating the Poincaré index is to extract the directional (orientation) image corresponding

to the input fingerprint, Figure 12 shows the orientation filed for both core and delta point.

To increase the accuracy of the orientation image, some enhancement techniques such as

(Awad et al., 2007a) and (Awad et al., 2007b) can be implemented prior to the directional

field estimation. We assume that

(, )ij

is pixel orientation of any directional image element

pixel

(, )ij

, where

0(,)ij

≤

. Let

(, )

for

01kN

≤

≤−

is the element selected for

calculating the Poincaré index of a point

(, )ij

. Then, the Poincaré index is defined as:

()

−

= Δ

∑

(, ) ,

Poincaré i j k

(1)

where

δδπ

πδ δ π

πδ

Δ= + ≤−

−

⎧

⎨

⎩

() () /2

() () () /2

()

kifk

kkifk

kotherwise

(2)

Biometrics - Unique and Diverse Applications in Nature, Science, and Technology

Arch Left L Right L Whorl

0.2

0.4

0.6

0.8

Block Number (1)

Correlation Coefficients

Arch Left L Right L Whorl

0.2

0.4

0.6

0.8

Block Number (2)

Correlation Coefficients

Arch Left L Right L Whorl

0.2

0.4

0.6

0.8

Block Number (3)

Correlation Coefficients

Arch Left L Right L Whorl

0.2

0.4

0.6

0.8

Block Number (4)

Correlation Coefficients

Fig. 10. Correlation results between input image patterns (Whorl) and other four classes

Arch Left L Right L Whorl

0.2

0.4

0.6

0.8

Block Number (1)

Correlation Coefficients

Arch Left L Right L Whorl

0.2

0.4

0.6

0.8

Block Number (2)

Correlation Coefficients

Arch Left L Right L Whorl

0.2

0.4

0.6

0.8

Block Number (3)

Correlation Coefficients

Arch Left L Right L Whorl

0.2

0.4

0.6

0.8

Block Number (4)

Correlation Coefficients

Fig. 11. Correlation results between input image patterns (Arch) and other four classes

Toward An Efficient Fingerprint Classification

Fig. 12. Estimated orientation field for core (left) and delta (right)

Fig. 13. Poincaré index representation: general Poincaré index calculation (left), Poincaré

index = 1.0 (middle), Poincaré index = - 0.5 (right)

and

( 1)mod( ) ( 1)mod( )

() , )()(,

kNkN kk

kx y xy

δθ θ

=−

(3)

Then, the Poincaré index may have four kinds of values: 0 which means no singular point

available in the area, 1/2 for a core point, -1/2 for a delta point, and 1 which means that the

selected area may have two singular points. Figure 13 shows the differences between the

most dominant values of Poincaré index.

4. Experimental results and evaluations

The proposed efficient fingerprint classification algorithm has been intensively evaluated

through different conducted experiments. The overall consumed processing time has been

optimized to enhance the overall algorithm performance. We have implemented two

matching algorithms; pattern matching by image difference and by image correlation also.

Optimization process tried to reduce the algorithm’s response time to its minimum value.

4.1 Data sets

In general, standard databases are used for implementation and evaluation of fingerprint

recognition or classification methods. We used NIST-4 for evaluating the accuracy of the

classification by the proposed method. Actually, in a lot of related work the evaluation is

operated on the whole or a part of NIST-4. As for the processing time, in addition to NIST-4,

four subsets of Fingerprint Verification Competition 2004 (FVC2004) (Maltoni et al., 2009)

were used (Figure 14 shows samples of fingerprint images in different subsets of FVC2004).

Biometrics - Unique and Diverse Applications in Nature, Science, and Technology

Fig. 14. Sample fingerprint images taken form FVC2004 available databases.

The selection criterion of the databases was interested to choose variety of fingerprints

collected by different methods including optical, thermal sweeping sensors, and synthetic

fingerprints. FVC2004 includes four sub databases: two categories generated by optical

sensors, "V300" by CrossMatch and "U.are.U 4000" by Digital Persona respectively, the third

one generated by thermal sensor "FingerChip FCD4B14CB" by Atmel, and the fourth is a

synthetic by SFinGe proposed by (Cappelli, 2009).

4.2 Accuracy

The idea of confusion matrix is a common way to measure the performance of fingerprint

classification algorithms. In a confusion matrix, a row and a column correspond to each

actual class and each predicted class, respectively. Therefore, the diagonal elements are

corresponding to the fingerprints that have been correctly classified. Table 1 is the confusion

matrix resulted from applying the proposed method on NIST-4 database.

Assigned Classes

True Classes A R L W

Arch 912

37 36 5

R Loop

672

3 23

L Loop

10 6

780

Whorl

1 30 35

731

Table 1. The confusion matrix of implementing proposed method on NIST-4 database

Table 2 is the same result expressed in terms of the ratio, where “Fail Reject” and “Fail

Accept” correspond to the ratios of the samples classified correctly in each row and column,

respectively (therefore, both of them have the same value in “Total”). The result 6.9% of the

error rate for the proposed method should be compared with the result 6% in (Park & Park,

2005) which uses FFT and NIST-4. The error rate is slightly worse compared to the existing

method, however the calculation time is extremely small compared to the same existing

method.

Toward An Efficient Fingerprint Classification

Rates

True Classes Correct Fail Reject Fail Accept

Arch

92.1 7.9 1.9

R Loop

94.1 5.9 8.7

L Loop

95.3 4.7 9.8

Whorl

91.7 8.3 7.7

Total

93.1 6.9 -

Table 2. Classification results with False Acceptance and False Rejection rates of the

proposed algorithm (%)

4.3 Processing time

Response time is the key issue in all fingerprint classification methods. We evaluated the

processing time of the proposed method with respect to each step. The experiments were

operated with Intel

Pentium 4 Core 2 Due

™

processor (T9300, 2.5 GHz), 3 GB RAM, and

Matlab

R2009b version. Table 3 represents the results of the processing time of the

proposed method for one input fingerprint image. Each value is the average of the results

for the fingerprint images in the databases. In the process of pattern matching, we evaluated

the time of the difference-based method for the comparison with the correlation-based

method. Note that the processes of “Division” and “FFT” are common in both methods. By

the results, the total processing time of the proposed method is generally short in the sense

of an application as an identification system. The correlation-based method is improving the

computing time for the pattern matching process from the difference-based method.

Division FFT

Pattern Matching

Total

Correlation-based matching

0.0200 0.0229 0.0134 0.0552

Difference-based matching

0.0200 0.0229 0.0620 0.1056

Table 3. The processing time of the proposed method for each step (seconds)

4.4 Considerations

As we mentioned in (Subsection 3.6), we should consider a better scheme for the pattern

matching and decision making. Does every block has the same weight during the matching

process? Our experimental results proved that the answer is “No”, and hence each block

pattern may have different weight during the matching step. Furthermore, we go to

optimize the matching processing by selecting number of blocks to be matched in each class.

In other words, instead of matching the four blocks of each class, we match only the most

dominant blocks in each class. The weight for each block and order are different for each

fingerprint class, therefore the problem was how to select the most optimum blocks for each

class. The problem has been solved empirically by testing each block individually and tried

to assign it a weight related to the correlation matching results of the input image with its

corresponding standard one. The test has been extended to check two by two blocks, and

three by three blocks as well.

Biometrics - Unique and Diverse Applications in Nature, Science, and Technology

Matching two by two blocks, blocks number (1) and (2) of the input image with the

corresponding blocks in the standard classes as an example, is considered as the summation

of matching two individual blocks. It helped us to find the block that produces maximum

correlation in the patterns matching process. As a case study, we input a Left Loop

fingerprint, the classification algorithm detected that the input image is a Left loop correctly;

however less block difference or high correlation score was our goal. Through the

optimization process, we are trying to achieve as much smaller difference between blocks as

possible, and hence we were seeking to get a less block difference between the input image

patterns and the Left Loop standard class patterns. The first graph in Figure 15 represents

the matching results come from using two blocks matching in the matching process and

discarding the others. From that figure we see that the blocks (2) and (4) produce a

minimum block difference that considered as a high matching score, where blocks (1) and

(3) produce a low matching score. Therefore, we conclude that blocks (2) and (4) are the first

optimum choice as a base blocks for matching the input image with the Left Loop class.

0 50 100 150

0.4

0.5

0.6

0.7

Pixel Order

Difference Coefficients

0 50 100 150

0.4

0.6

0.8

Pixel Order

Difference Coefficients

0 50 100 150

0.5

1.5

Pixel Order

Difference Coefficients

Full Blocks Blocks (1,2,4)

Blocks (1,2,4) Blocks (2,3,4)

Blocks (1,3) Blocks(2,4)

Fig. 15. Patterns matching optimization by two by two blocks (Upper), three by three blocks

(Middle), and the amount of gained matching optimization (Bottom)

Due to the overlapping between classes, we found that two blocks are not sufficient for

classification decision. Therefore, they are only used as a base blocks for determination of

the maximum and minimum matching scores. To prevent overlapping between different

fingerprint classes, we used three blocks from total patterns in matching process. The

second graph in Figure 15 shows that the matching score produced from using blocks (1),

(2), and (4) is much more than one produced by using blocks (2), (3), and (4). This figure

leads us to conclude that blocks number (1), (2), and (4) are the optimum choice when

Toward An Efficient Fingerprint Classification

matching any input fingerprint image with the standard Left Loop class, and the third block

may be discarded. The third graph in Figure 15 shows the amount of optimizations achieved

by selecting three particular blocks in the matching process comparing to use the full

patterns (four blocks). As we mentioned before, this experiments are operated as a case

study and the order of blocks is different for each class. Therefore, we are going further to

extend in the future the optimization process to include the remaining three classes to

complete the general weight for our pattern matching.

5. Conclusions and future work

In this chapter, we proposed an efficient method which classifies fingerprints into the

standard four classes. The basic idea of the proposed algorithm is dividing a fingerprint

image into four sub-images before applying the standard FFT-based method of fingerprint

classification. We have evaluated the proposed method in terms of the accuracy and the

processing time by experiments with the standard databases NIST-4 and FVC2004. As the

result, the proposed method achieves an extremely speed-up with a small classification

losses compared to the simple techniques we have used. One of our future works is an

improvement of the classification accuracy. For the improvement, we are considering that

these is scope for further study about the division of images, the calculation of patterns, and

the decision making. We mentioned about some ideas for the topics in Section 3.7, Section

3.4, and Section 4.4 respectively.

6. Acknowledgement

This work was supported by the Grant-in-Aid for Young Scientists (B) No. 22700149 of the

Ministry of Education, Culture, Sports, Science and Technology (MEXT) from 2010 to 2012.

7. References

Amin, A. & Neil, Y. (2004). Fingerprint Classification: a Review. Springer Verlag, Pattern

Analysis & Applications, Vol.7, No.1, (April, 2004), 77-93.

Awad, A. I.; Mustafaa, M. & Moness, M. (2008). A New Fingerprint Classification Approach

Based on Fast Fourier Transformer. Proceedings of the 5th International Conference on

Informatics and Systems, pp. 78-83, March 2008, Faculty of Computers &

Information-Cairo University, Cairo, Egypt.

Awad, A. I.; Mustafaa, M. & Moness, M. (2007a). Fingerprint Image Enhancement based on

Frequency Domain Representation. Journal of Al Azhar University Engineering Sector

(JAUES) , Vol.2, No.12, ( April, 2007a), 483-495.

Awad, A. I.; Mustafaa, M. & Moness, M. (2007b). Fingerprint Image Enhancement based on

Wavelet Filters. Proceedings of Al Azhar Engineering Ninth International Conference,

pp. 100-113, April 2007b, Al Azhar, Cairo, Egypt.

Cappelli, R. (2009). SFinGe. in Stan Li (Editor), Encyclopedia of Biometrics. Springer.

Cappelli, R.; Lumini, A.; Maio, D. & Maltoni, D. (1999). Fingerprint Classification by

Directional Image Partitioning. IEEE Transactions on Pattern Analysis and Machine

Intelligence , Vol.21, No.5, ( May, 1999), 402-412.

Biometrics - Unique and Diverse Applications in Nature, Science, and Technology

Cappelli, R.; Maio, D. & Maltoni, D. (2002). A Multi-Classifier Approach to Fingerprint

Classification. Springer Verlag London, Pattern Analysis & Applications, Vol.5, No.2,

(May, 2002), 136-144.

Espinosa-Dur, V. (2001). Minutiae Detection Algorithm for Fingerprint Recognition.

Proceedings of IEEE 35th International Carnahan Conference on Security Technology, pp.

264-266, ISBN 0-7803-6636-0, October 2001, IEEE, London, UK.

Gonzalez, R. C.; Woods, R. E. & Eddins, S. L. (2009). Digital Image Processing Using Matlab,

Second Edition, Gatesmark Publishing, ISBN 978-0982085400.

Green, R. J. & Fitz, A. P. (1996). Fingerprint Classification using a Hexagonal Fast Fourier

Transform. Pattern Recognition, Vol.29, No.10, (October, 1996), 1587-1597.

K. Jain, A.; Flynn, P. & A. Ross, A. (2007). Handbook of Biometrics, Springer, ISBN 978-

0387710402.

K. Jain, A. & Minut, S. (2002). Hierarchical Kernel Fitting for Fingerprint Classification and

Alignment. Proceedings of IEEE 16th International Conference on Pattern Recognition

(ICPR'02), p. 20469, ISBN 0-7695-1695-X, August 2002, IEEE, Quebec City, QC,

Canada.

K. Jain, A.; Prabhakar, S. & Hong, L. (1999). A Multichannel Approach to Fingerprint

Classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.21,

No.4, (April, 1999), 348-359.

Lumini, A.; Maio, D. & Maltoni, D. (1997). Continuous versus Exclusive Classification for

Fingerprint Retrieval. Pattern Recognition Letters, Vol.18, No.10, (October, 1997),

1027-1034.

Maltoni, D. & Maio, D. (1996). A Structural Approach to Fingerprint Classification.

Proceedings of 13th international Conference on Pattern Recogintion (ICPR), ISBN 0-

8186-7282-X, August 1996, IEEE Computer Society, Vienna, Austria.

Maltoni, D.; Maio, D.; K. Jain, A. & Prabhakar, S. (2009). Handbook of Fingerprint Recognition,

Second Edition, Springer Verlag, ISBN 978-1848822535.

Manhua, L. (2010). Fingerprint classification based on Adaboost learning from singularity

features. Pattern Recognition, Vol.43, No.3, (March, 2010), 1062-1070.

Park, C. H. & Park, H. (2005). Fingerprint classification using fast Fourier transform and

nonlinear discriminant analysis. Pattern Recognition, Vol.38, No.4, (April, 2005), 495

– 503.

Sarbadhikari, S.; Basak, J.; Pal, S. & Kundu, M. (1998). Noisy Fingerprints Classification with

Directional Based Features Using MLP. Springer-Verlag London Limited, Neural

Computing & Applications , Vol.7, (1998), 180-191.

Senior, A. (2001). A Combination Fingerprint Classifier. IEEE Transactions on Pattern Analysis

and Machine Intelligence , Vol.23, No.10, ( October, 2001), 1165 - 1174.

Sherlock, B. G.; Monro, D. M. & Millard, K. (1994). Fingerprint Enhancement by Directional

Fourier Filtering. IEE Proceedings of Vision, Image, and Signal Processing, Vol.141,

No.2, (May, 1994), 87–94.

Wang, W.; Li, J. & Chen, W. (2006). Fingerprint Classification Using Improved Directional

Field and Fuzzy Wavelet Neural Networks. Proceedings of the IEEE Sixth World

Congress on Intelligent control and Automation, pp. 9961-9964, January 2006, IEEE,

Dalian, China.

Yao, Y.; Marcialisb, G. L.; Pontil, M.; Frasconi, P. & Roli, F. (2003). Combining Flat and

Structured Representations for Fingerprint Classification with Recursive Neural

Networks and Support Vector Machines. Pattern Recognition, Vol.36, 2003, 397– 406.