Abstract: In this study, a novel partial fingerprint matching approach that uses global minutiae matching and the support vector machine is presented. Global minutiae-based matching algorithm is used to record the matching pairs and their feature vectors are used to generate a model file which is used for classification. The traditional minutiae-based matching approach is studied as a classification approach by using support vector machine. We used fingerprint verification competition databases for our evaluation. Results from our experiment showed 98.5% of matching is achieved compared to 97.6% obtained using flow network-based approach.
INTRODUCTION
Fingerprint images are one of the most commonly used biometric for verifying the claimed identity of a user. The fingerprint which is stored in the database is normally full prints. When a user is tested for identification, may not be identified because of the fingerprint reader/ scanner is of not same size. Miniaturization of fingerprint sensors from different manufactures range from 1x1 to 0.42x0.42 (Jea and Govindaraju, 2005). However, most of the scanners with a sensing area smaller than 0.5x0.7 is considered to be average fingerprint size (Biometrika Inc.) can capture partial fingerprints. The problem of partial fingerprint matching, although, similar to the issue of full fingerprint matching problem, enormous work has to be carried out to handle the Partial Fingerprint Identification Systems (PFIS).
The most commonly used representation for storage of fingerprint images is a list of the minutiae points (American National Standard for Information Systems, 1993), these are the points of irregularity in the fingerprint ridges and there are usually 30-50 of them present per fingerprint. During the verification phase, a template containing minutiae point information for the test fingerprint is similarly generated and is compared with the user’s stored template to arrive at a result. Each minutiae point is stored in terms of their position and orientation in the fingerprint image. Assigning a threshold value for comparison, results are tabulated. Therefore, the value of threshold plays a crucial role in terms of accuracy. Matching the partial fingerprint to the full print images in database usually has the following problems: (1) The partial fingerprints obtained from a crime area are small and blur, (2) The number of minutia points available in such prints is less which reduces the discriminating power, (3) Loss of singular points (core and delta) is highly likely, (4) Uncontrolled impression environments (skin elasticity) result in unspecified orientations of obtained partial fingerprints. Minutiae-based approaches with local, global and secondary features yield good results comparatively. In this study, we propose a minutiae matching algorithm based on global features and train the result with SVM classifier along with a model file.
Fingerprint matching techniques may be broadly classified as being either minutiae-based or image-based (Bazen et al., 2000). Minutiae-based approaches first extract the minutiae from the fingerprint images; then, the matching between two fingerprints is made using the two sets of minutiae localizations (Jia et al., 2007). Most of the fingerprint minutiae extraction methods are thinning-based techniques. Minutiae points are detected by tracing the thin ridge contours. When the trace stops, a ridge ending point is marked. Bifurcation points are those with more than two neighbors (Simon-Zorita et al., 2001). Image-based approaches usually extract the features directly from the raw image since, a gray-level fingerprint image is available; then, the matching decision is made using these features. The AFVSs are usually based on minutiae matching. Almost all fingerprint minutiae matching techniques, uses estimation mechanism to determine the threshold value. Research shows that fingerprint matching is also done by classification methods using machine learning like neural networks, decision trees and SVM (Gutschoven and Verlinde, 2000).
PARTIAL FINGERPRINT MATCHING
Our system works on the minutiae-based representation of a fingerprint. Minutiae, in fingerprint context, are the various ridge discontinuities of a fingerprint. There are more than 100 different types of minutiae have been identified, among which ridge bifurcations and endings (Fig. 1) are the most widely used. Minutia-based representation of fingerprints is an ANSI-NIST standard (Jain et al., 1997) and contains only local information without relying on global information such as singular points or center of mass of fingerprints.
Matching two fingerprints (in minutiae-based representation) is to find the alignment and correspondences between minutiae on both prints (Jea and Govindaraju, 2005). In order to obtain a good efficiency of matching process, strong enhancement algorithms has to be done during the pre-processing stage and good realization of minutiae extraction methods has to carried out. There are two major types of features that are used in fingerprint matching: local and global features. Local features, such as the minutiae information contains the information that is in a local area only and invariant with respect to global transformation. Global features, such as number, type and position of singularities, spatial relationship and geometrical attributes of ridge lines, size and shape of the fingerings, are characterized by the attributes that capture the global spatial relationships of a fingerprint (Jea and Govindaraju, 2005). In this study, we used local and global features followed by machine learning classifier to tune the result. Back-propagation algorithm is used to extract the minutiae points. SVM is used for optimum classification by removing the false pairs and considering only true pairs. Jea and Govindaraju (2005) claimed that partial fingerprint matching requires a set of local features and localized features have the ability to tolerate more distortions. Vajna (2000) has shows that the geometric deformations on local areas can be more easily controlled than global deformations. Generating local features is time consuming and minutiae points may flip due to same distance and angle. Therefore, we may neglect some of the minutiae points when generating local secondary features which ultimately results in wrong matching. We present a modified approach of Yang et al. (2008).
| Fig. 1: | Ridge bifurcations and ridge endings |
GLOBAL MINUTIAE MATCHING ALGORITHM
| Step 1: | Sort the template and input minutiae set by radial angle and radial distance in descending order |
| Step 2: | Consider, the reference minutiae points and convert into polar coordinate system with respect to reference minutiae by following: |
For all minutiae (xi,yi, θi )t, apply the following:
where, (xr,yr,θr)t is the coordinate of reference minutiae and (ri,ai,θi)t is in the polar coordinate system (ri represents the radial distance, ai represents radial angle and θi represents the orientation of minutiae with respect to reference minutiae).
| Step 3: | Find the minutiae type, if it is same, then proceed to step4. Else find next minutiae |
| Step 4: | For each set of minutiae calculate the following: {L = number of points recorded} |
| • | Radial distance = 1/L (Σ |r (di) – r (di) |), for 0 <=i<=L |
| • | Radial angle = 1/L (Σ | ai - aj |) , for 0<=i<=L |
| • | Minutiae direction = 1/L (Σ |θi-θj|), for 0<=i<=L |
| Step 5: | Compute the similarity score of two minutiae sets by summing the radial distance, radial angle and direction |
| Step 6: | Let, ε be the threshold assumed. If the similarity score is greater than ε then we conclude two minutiae pair is matched |
| Step 7: | Calculate the matching score using: |
Match score = m2/(MixMr) |
where, m is the total number of matched minutiae pairs, Mi and Mr is the number of minutiae points in the input and template fingerprints.
| Step 8: | Record the maximum number of matching minutiae pairs |
SUPPORT VECTOR MACHINES
This literature of support vector machine is based on (Yao et al., 2001). The SVM performs pattern recognition for two-class problems by determining the separating hyperplane with maximum distance to the closest points of the training set. An appropriate nonlinear mapping Φ(•) to a sufficiently high dimension data from two categories can always be separated by a hyper plane. These points are called support vectors. If the data is not linearly separable in the input space, a non-linear transformation Φ(•) can be applied which maps the data points x ε IRn into high dimensional space 'H which is called feature space. The mapping Φ(•) is represented in the SVM classifier by a kernel function K(•,•) which defines an inner product in 'H, i.e., K(x,t) = Φ(x)• Φ(t). The decision function of the SVM has the form:
| (1) |
where, l is the number of data points and yi ε {-1,1} is the class label of training point x j. Coefficients of α i in Eq. 1 can be found by solving a quadratic programming problem with linear constraints. The support vectors are the nearest points to the separating boundary and are the only ones for which αi in Eq. 1 can be nonzero.
An important family of admissible kernel functions are the Gaussian kernel, K(x,y) = exp (-||x-y ||/2σ2 ), with σ the variance of the Gaussian and the polynomial kernels, k(x,y) = (1+x• y)d, with d the degree of polynomial. Let, M be the distance of support vectors to the hyperplane shown in Eq. 2.This quantity is called margins and it is related to the coefficients in Eq. 1:
| (2) |
The margin is an indicator of the separability of the data. Attempts to solve q-class problems with SVMs have involved training p SVMs, each of which separates a single class from all remaining classes (Vapnik, 1998) or training p2 machines, each of which separates a pair of classes ( Pontil and Verri, 1998). First type of classifiers is called as one-vs-all and second is pairwise classifiers. In the first one, test point is classified into the class whose associated classifier has the highest score among all classifiers. Where as, in the second, a test point is classified in the class which gives many possible classifiers (Friedman, 1997).
EXPERIMENTAL DESIGN
The proposed architecture is shown in Fig. 2. Input fingerprint and the template fingerprints are initially matched using algorithm discussed above. Matched minutiae pairs are recorded and feature vectors (vector 1 and 2) are calculated. For each matched points, distance and angle is found out and named as feature vector 1. Similarly, for each matched points, feature vector 2 is found using the 4-tuple (x,y,θ,φ) parameters, where, x,y represents relative position, θ represents angle and φ is the invariant moments for a small Region area of Interest (ROI). Matching score is calculated for the identical and different fingerprints. A model file is generated by the SVM and stored as separate file from feature vector 1. This model file is fed to the SVM classification along with the feature vector 2 for best classification. The result shows those false matched points which are considered as matching pair is eliminated and the correct matching pair which was not included as true match has been considered for true matching.
Training the SVM: For training the SVM, we need a large number of matching pairs of minutiae points, both from fingerprint pairs belonging to the same and to different users (Mansukhani et al., 2007). We take a pair of fingerprint templates, perform the global matching as described above and get a list of matched minutiae points. Mansukhani et al. (2007) proposed distance and orientation of minutiae points to extract feature vector, but we propose distance and angle, where angle information is more appropriate than orientation. Once, all pair information has been extracted, the SVM is trained to produce a model file.
| Fig. 2: | Proposed architecture with SVM classification |
| Table 1: | Information of data and image size |
Now, SVM along with trained model file is used to classify the matched pairs as success or failure. The SVM and matching file is used to classify whether image belongs to the same user or different user. The final match result shows the total number of False Acceptance Rate (FAR) and False Rejection Rate (FRR). We compared our approach with flow network-based method.
DATA SETS
We use the FVC 2002 database for our method to be tested. Table 1 shows the information of datasets.
The dataset are divided into 10 parts. A total of 8000 (10x800) fingerprint images is generated randomly with different sizes viz., 40 to 90%. A total of 800 fingerprints of size 40% at random position is compared with template datasets and similarly for the other sizes. Average matching results are recorded for each trial. The performance of fingerprint verification is measured by FAR and FRR. Each sample is matched against the samples of the same fingers and remaining fingers.
DISCUSSION
Each fingerprint are made to 10 units of 40, 45, 50, 55, 60, 65, 70, 75, 80 and 90% different sizes at random positions. Figure 3 shows partial fingerprint with different sizes (approximately 80 to 90%). In our experiment, 40% is considered as starting size. Any size below this will not have a considerable result in matching. The experiment showed that SVM is best suited for classification. The maximum classification rate in our method was 98.5% compared to that of flow network-based method which gave maximum classification rate as 97.6%. Flow network-method is time consuming process and appropriate bins have to be used for indexing and classifications. Also, great care has to be taken during secondary feature generation of minutiae points and possibility to flip some of minutiae points. By using SVM, the optimum hyper plane carefully selects minutiae types and performs optimum classification. Jea and Govindaraju (2005) has chosen fingerprints of size ranging from 90 to 10% (90, 80, 70, 60, 50, 40, 30, 20 and 10%). Table 2 also shows the comparisons between our method and Jea and Govindaraju (2005) approach. Results shows that error rate decrease as image size increase. From the Table 2, it shows that the error rate is considerably reduced from 70% and above.
| Table 2: | Performance with different sized partial images at random position |
| Fig. 3: | Partial fingerprints taken from FVC2002 |
This shows that partial fingerprints of size 75% and above have improved the classification rate in our approach. Table 2 show the actual differences in terms of FAR, FRR with TER. Second column and the third column indicate the number of pixels in the fingerprints. The TER rate for Jea and Govindaraju has been compared with 40, 50, 60, 70, 80 and 90%, respectively.
CONCLUSION
The main contributions in this study are designing an SVM based architecture which generates model file. A novel minutiae matching algorithm generates matching minutiae pairs. Experimental results showed a significant increase in matching rate of partial fingerprints. Future work may include verifying with different database which consists of large data and addressing strong enhancement methods.