A new method for fingeprint clasification.

Gams, Matjaz ; Cosoi, Alexandru Catalin ; Corduneanu, Maria 等

1. INTRODUCTION

In fingerprint identification there are several aspects that must be taken in consideration, such as: fingerprint matching, enrolled image, FAR/FRR or template storage.

Fingerprint matching determines whether two fingerprints are from the same finger or not. Many fingerprint verification methods have appeared in literature over the years. In general, the two most prominent features used in fingerprint matching are ridge ending and ridge bifurcation called minutiae. The algorithm used in minutiae comparison requires a specific mode of storing features, using polar coordinates, which also brings the advantage of reducing the memory space needed. The parameters are:

* x and y coordinate of the minutia point

* orientation, defined as the local ridge orientation of the associated ridge.

* type of the minutia point, which is whether the minutia is ridge ending or ridge bifurcation.

* associated ridge.

Enrollment quality is very important to achieve high operational performance. Some enrollment applications have advanced feedback dialog messages, which provide useful information about poor quality scans, be it fingerprint, facial or speech. There should be a good balance between the feedback mechanism of the enrollment software and the understanding of acceptable quality by the enrollment officer.

The False Acceptance Rate (FAR) is the rate at which an intruder can be recognized as a valid user. Many vendors quote the false acceptance rates of their devices, typically generated through mathematical extrapolation of field trial data. As a result, it's difficult to compare these technologies based on vendors' quoted FAR numbers. But it's important to remember that during user verification (a one-to-one match), false acceptance is based on imposter attempts, not on the total number of attempts by valid users. If the FAR is 1 percent, that means one out of 100 users trying to break into the system will be successful.

The False Reject Rate (FRR) is the rate at which a valid user is rejected by the system. A 1% FRR would imply the average user would fail every hundredth time. However, it is more likely that only a few individuals may fail a lot more often. These individual may be conduits for a secondary verification mechanism. Many systems, such as the fingerprint-recognition devices, may be tuned to do less strict checking at the expense of opening the system. Administrators have to balance false acceptances versus false rejects, the possibility of fraud versus user convenience.

One method for reducing the false rejects is to use more than one template for verification. The ability to use different fingers for verification can be simply achieved by storing multiple user fingers on the smart card (Chan, 2000).

Although the biometric template typically cannot be used to create an image or physiological attribute of the user, the template still is sensitive data. The digital representation of what the reader detects should be encrypted where it's stored, and protected storage locations such as smartcards can improve overall security. The size of the template may be a factor. Most fingerprint and iris templates require between 256 bytes and 1 KB per user, though some systems need up to 8 KB.

The three basic patterns of fingerprint ridges are the arch, loop, and whorl. An arch is a pattern where the ridges enter from one side of the finger, rise in the center forming an arc, and then exit the other side of the finger. The loop is a pattern where the ridges enter from one side of a finger, form a curve, and tend to exit from the same side they enter. In the whorl pattern, ridges form circularly around a central point on the finger. Scientists have found that family members often share the same general fingerprint patterns, leading to the belief that these patterns are inherited.

The major Minutia features of fingerprint ridges are: ridge ending, bifurcation, and short ridge (or dot). The ridge ending is the point at which a ridge terminates. Bifurcations are points at which a single ridge splits into two ridges. Short ridges (or dots) are ridges, which are significantly shorter than the average ridge length on the fingerprint. Minutiae and patterns are very important in the analysis of fingerprints since no two fingers have been shown to be identical.

A terminal reads the fingerprint from the user, performs a quick preprocessing (e.g. transforming it in a single string) and then sends a query to the server. Then, the two strings are compared, and if a percent of matching is met, the access is granted, otherwise is denied. The percent of matching, called threshold can be established within the program, depending on the FAR/FRR rate required at the specific location where access control takes place. If we want to use the system for a security objective, the typical threshold is 85%, which is the usual in biometric identification system.

[FIGURE 1 OMITTED]

For improvement of security, a higher threshold can be set, which means that more minutiae must be extracted from the image acquired from the biometric sensor, when a user wants to authenticate. That procedure usually involves many retry of user fingerprint read, because the image is altered by external factors, such as dust, wet, or degrading of the fingerprint, due to a hard work.

One of the issues discussed about fingerprint analisys is fingerprint clustering. Grouping similar fingerprints based on specific features has always been a major concern in the security industry. Having such a grouping could lead to faster processing techniques, better organization of large datasets and many other applications. The huge size of fingerprint databases used for real applications seriously affects the "identification time" of AFISs (Automated Fingerprint Identification Systems). Automatic fingerprint classification, based on well known schemes of fingerprint subdivision into classes, is the usual strategy adopted for reducing the number of comparisons during the fingerprint identification process and, consequently, for reducing the identification time (Figueroa et al., 2007).

2. PROPOSED METHOD

Support vector machines (SVMs) are a set of related supervised learning methods used for classification and regression. Viewing input data as two sets of vectors in an n-dimensional space, an SVM will construct a separating hyperplane in that space, one which maximizes the margin between the two data sets. To calculate the margin, two parallel hyperplanes are constructed, one on each side of the separating hyperplane, which are "pushed up against" the two data sets. Intuitively, a good separation is achieved by the hyperplane that has the largest distance to the neighboring datapoints of both classes, since in general the larger the margin the lower the generalization error of the classifier.

It is quite easy to see by a visual analysis of fingerprint images that fingerprint "structure" can be extracted by segmenting fingerprint into regions characterized by homogeneous ridge directions. Therefore, we propose to extract and represent the structural information of fingerprints by segmenting the related directional images and by converting such segmented images into relational graphs whose nodes correspond to regions extracted by segmentation algorithm. Graph nodes are then characterized by local characteristics of regions and by the geometrical and spectral relations among adjacent regions.

The obtained graphs are then represented as a single string, called the feature vector which can be sent to the SVM for clustering or classification.

In the case of support vector machines, a data point (a fingerprint) is viewed as a p-dimensional vector (a list of p numbers), and we want to know whether we can separate such points with a p--1-dimensional hyperplane. This is called a linear classifier. There are many hyperplanes that might classify the data. However, we are additionally interested in finding out if we can achieve maximum separation (margin) between the two classes. By this we mean that we pick the hyperplane so that the distance from the hyperplane to the nearest data point is maximized. That is to say that the nearest distance between a point in one separated hyperplane and a point in the other separated hyperplane is maximized. Now, if such a hyperplane exists, it is clearly of interest and is known as the maximum-margin hyperplane and such a linear classifier is known as a maximum margin classifier.

Our SVM algorithm is quite simple:

 function [it, opt, w, gamma] = svml(A,D,nu,itmax,tol)
 % 1svm with SMW for min 1/2*u'*Q*u-e'*u s.t. u=>0,
 % Q=I/nu+H*H', H=D[A -e]
 % Input: A, D, nu, itmax, tol; Output: it, opt, w, gamma
 % [it, opt, w, gamma] = svml(A,D,nu,itmax,tol);
 [m,n]=size(A);alpha=1.9/nu;e=ones(m,1);H=D*[A
e];it=0;
 S=H*inv((speye(n+1)/nu+H'*H));
 u=nu*(1-S*(H'*e));oldu=u+1;
 while it<itmax & norm(oldu-u)>tol
 z=(1+pl(((u/nu+H*(H' *u))-alpha*u)-1));
 oldu=u;
 u=nu*(z-S*(H'*z));
 it=it+1;
 end;
 opt=norm(u-oldu);w=A' *D*u;gamma=-e' *D*u;
 function pl = pl(x); pl = (abs(x)+x)/2;

3. RESULTS

The NIST-4 database containing five fingerprint classes (A, L, R, W, T) was used for experiments. In particular, the first 1,800 fingerprints (f0001 through f0900 and s0001 through s0900) were used for classifier training. The next 200 fingerprints were used as validation set, and the last 2,000 fingerprints as test set.

We report a success rate of 80% and a missclasification rate of 0.5%. We believe that we can obtain more than just 80% and less than 0.5% error rate if we will use some fine-tuning of the segmentation algorithm. A lower threshold will increase the success rate to even 99% but it will considerably increase the error rate to almost 7%.

4. CONCLUSION

In this paper the authors try to solve one of the major problems of fingerprint based identification: processing speed. Using fingerprint segmentation algorithms and support vector machines, the clustering taks can be performed with at least 80% success rate and a low error rate.

Although not perfect, we believe that a better segmentation of the fingerprint images could lead to a better clustering and a lower error rate.

5. REFERENCES

Chan C. (2000). A secured globally access control system using smart card, Smart Card Department, Department of Electronic Engineering, City University of Hong Kong

Du Y., Ives R., Etter D., Welch B. (2002). Biometrical signal processing laboratory, Biometrical signal processing laboratory, Department of electrical engineering

Figueroa A., Goldstein A., Jiang T., Kurowski M. (2007). Aproximate Clustering of Finterprint Vectors with missing values, Computer Science Department, University of California Riverside, Riverside, CA 92521., Department of Mathematics, Yeshiva University, New York, NY 10033, Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warsaw, Poland

Gour B., Bandopadhyaya T., Sharma S. (2007). High Quality Cluster Generation of Feature Points of Fingerprint Using Neutral Network, Asst. Prof. Dept. of Computer Sc. & Engg All Saints' College of Technology, Bhopal, Professor, Bansal Institute of Science and Technology, Bhopal, Professor, RGPV, Bhopal

Marcialis G., Roli F., Frasconi P (2005). Fingerprint classification by Combination of Flat and Structural Approaches, Dept. of Electrical and Electronic Eng., University of Cagliari

Vlad M. S., Tatoiu R., Sgarciu V. (2006). Smart Card And Biometrics Used For Secured Personal Identification System Development, RAAD 2006--Hungary