INTRODUCTION

            Fingerprint is considered one of the most popular methods used in authentication of persons, because  person's fingerprints unique and it remains invariant with his/her age [1]. The fingerprint is made of a series of lines called ridges and spaces between them called valleys, see Fig 1: a.

            The analysis of fingerprint matching compares betweenseveral features of the fingerprint pattern, as shownin Fig. 1: b.

Fig 1: Fingerprint Sample image

Perhaps fingerprint verification is the quickest and most appropriate method for establishing an individual’s identity among all the biometric techniques. Owing to the high complexity of matching fingerprints and the enormous amount of existing fingerprints historically, fingerprint recognition systems were mostly used in forensic sciences. However, nowadays the popularity of fingerprint recognition systems is mainly due to civilian applications such as controlling physical access to facilities, controlling logical access to software, and controlling voters during elections. The key component in fingerprint recognition systems is the fingerprint matching algorithm. The modern fingerprint matching algorithms with higher quality are those based on minutiae [2]. Minutiae are the points where the ridge continuity breaks and they are typically represented as (x,y,θ); where (x,y) represent the 2D point coordinates, and θ the ridge direction at that point. As a minutiae-based matcher should be invariant to translation and rotation [3], the process of minutiae pairing is ambiguous. Thus, most matchers of this category use minutia descriptors (local minutia structures) to rapidly create the minutia correspondences. A simple and accurate minutiae descriptor is based on minutiae triplets, which are local structures represented by three minutiae. The algorithms based on minutiae triplets have the following advantages, which make them of a higher quality than the algorithms based on other representations:

• ·        They are tolerant to fingerprint deformations;
• ·        They are faster and more accurate;
• ·        They are suitable for the applications based on interoperability standards because the most popular standards are based only on minutia;
• ·        The representation and comparison of minutiae triplets can be performed efficiently; and
• ·        Minutiae triplets have a higher discriminative power than minutiae pairs and a single minutia [‎2].

            To implement a minutia extractor, a three-stage approach is widely used by researchers, as shownin Fig. 2 [4].

Fig 2: Minutia Extractor

The researchers have proposed a reliable method for extracting feature from fingerprint images. The Matching stage uses the position and orientation of such features and the total number of such features; and the accuracy of feature extraction depends on success of the fingerprint matching. Reliable and robust features can make matching algorithms simpler and the manual verification stage redundant. This method is based on projection of the image in the direction of the orientation field for segmenting the ridges from the fingerprint image; and the quality of the extracted features is evaluated quantitatively [1].

The main purpose of this research is to produce a better performance and accuracy for the fingerprint identification system.In which, there are mainly two stages; feature extraction that is played a major role of the proposed system and matching the two input vector query and template for the candidate user. The proposed is designed to reduce the time complexity of the verification process and achieve a better performance and accuracy. The sections of this paper are organized as follows: Section 2 presents some related works, Section 3 describes the basic steps of fingerprint extraction algorithm, Section4presents our proposed hybrid version of adaptive feature extraction with directional flow based on Fourier .Section 5 compares the feature extraction algorithms in typical environment and presents the result of comparison using different experimental factors. Finally, Section 6 concludes the paper and presents the future work.

Related Works

There has been great research achievement in the fingerprint and bioinformatics field, and there are many presentations of modifications and algorithms used for fingerprint identification and recognition. Here, a hard try have been made to list and demonstrate some of the latest related research progress. 

Ms. Preeti Jain, K. Sawant combined many methods to build a minutiae extractor and matching minutiae. In addition, segmented images using morphological operations, minutia marking with special considering the triple branch counting, minutiae unification by decomposing a branch into three terminations, and matching in the unified x-y coordinate system after a two-step transformation is used in the System [4].

A reliable extraction of true minutiae in fingerprint image is presented by M. Popovic as being critical in the performance of an Automated Fingerprint Identification System (AFIS). For utilizing the performance of AFIS in law enforcement agencies, they first digitalize an archive of fingerprints obtained by the ink method. This leads to improvement in the quality of extracted minutia automatically. However, a number of spurious minutiae in the blurry regions containing scars and creases are extracted. AFIS has a critical performance factor namelythenumber of extracted and saved templates of fingerprint spurious minutia which are minimized to maximal extent [5].

Humaira, N. has proposed a fingerprint recognition system which consists of three stages, namelythe preprocessing, the post-processing, and the matching stages. In fact, he applied several enhancement methods in the pre-processing stage. For fingerprint alignment, he used a core-point based “Poincare Index value” method. Curvelet transformation, a new multi-resolution and multi-orientation tool is used to extract a feature set from the image in different scales and orientations. The feature vectors extracted from Curvelet co-efficient matrix are then classified using the k nearest neighbor classifier due to identifying the exact fingerprint [6].

M. Medina-P´erez proposed a system to improve the multiple alignment strategy that reduces the time complexityfor achieving accuracy similar to or better than the accuracy of the original strategy [7].

SharatShikkerur, Chaohong Wu and VenuGovendarajuhave proposed a unified frequency domain analysis based algorithm for the enhancement and extraction of global and local features from fingerprint images.  It uses information from the Fourier domain analysis of the fingerprint, which is able to extract local ridge orientation, ridge frequency and ridge quality, in addition to a proposed algorithm for extracting the minutiae from the fingerprint image using the chain coded contour ridge method [8].

RoliBansal, PritiSehgal and PunamBediproposed a technique to extract minutiae from fingerprint imagesamong other approaches. They are distinguished on the basis of several factors like:  the kind of input images, techniques of binarization and segmentation, and whether or not thinning is required and the amount of effort required in the post processing stage, if any[9].

The Proposed Hybrid Method

There are many proposed techniques and algorithms in feature extraction of human fingerprints for specific or different applications. In [1], a proposed method is presented for feature extraction based on minutia extraction which can be modified and improved for speeding up the execution process. It is based on projection of the fingerprint image in the direction orthogonal to the orientation field due to segmentation of the ridges and quality of the extracted features. The overall process of feature extraction can be divided into three main stages which are described in details using a sample fingerprint image to show the output of each sub-phase during algorithm procedures:

I.   Preprocessing

Assume the next figure is image of a fingerprint as an input, as shown in Fig.3:

Fig3: Original Fingerprint Stamp

1.    Make sure the given image has a color scheme named gray scale scheme; and if it does not have it; transform it

Fig 4: Gray Color Map

by using the following equation to produce an output as in Fig. 4.Where the following equation is used for color gray scale conversion purpose; for a given colored pixel at coordinate x and y, (R, G, B) in 24-bit color map, the gray scale, I(x, y) or in short I, is produced based on using the following equation:

‎[11]

For edge detection process there is two major items that are required to be computed which are called gradient magnitude and gradient direction. The direction of a given ridge enclosed in a block of size 16 by 16 window that can be determined by computing the gradient Gx(i,j) ,Gy(i,j) in both x and y directions. Followed by the computation of the dominant direction using the following equation:

, Gx≠0 and Gy≠0.

Note that if either G_x or G_y is zero then the estimate of the dominant direction is trivial (0 or 90).The angle ϴ_d is quantized into 16 directions.

Edge detection using Sobel edge detector includes computation of both gradient magnitude and gradient direction over all images not block by block. Where for an image that is used as input for the detector there is images which represent Gx, Gy, gradient magnitude and gradient direction;  respectively. So that after applying the gradient edge operator for the input fingerprint image, the orientation flow is detected and determined because of splitting fingerprint image into blocks. Each block if contains minutia will also contains a ridge that is characterized by the same gradient direction of the block direction itself. But there is still a problem of certain minutia direction that is solved as stated in [11]; a strategy in later would be demonstrated during minutia details extraction.

2.    Appling (3*3) mask along the orientation field of each window of the whole fingerprint window that is extracted as the composed operations of foreground and background segmentation and the direction projection using edge detector operator. In which, the image is binarized to distinguish between foreground and background via assigning the ridge pixels to “1” and all the remaining pixels to “0”. The mask containing all 1’s enables us to count the number of 1’s in the mask area and if the count of 1’s is more than 25% of total numbers of pixels then the ridge point is retained. The mask size is determined empirically‎1] as shown in Fig 6.

Fig 6: Binary Image

II.     Processing [minutiae extraction]

Here the major processing of feature extracting of minutia details is done and extracted for the post processing stage. For extracting minutia details; i.e. minutia coordination (x, y), its direction  and minutia type either Bifurcation or Ridge endas stated steps in [1]. For extracting the features of input fingerprint, while we can hybrid the proposed method by embedding a Sherlock model inside the feature extraction procedures to speed up the extraction process running time. This model has proposed a novel method for enhancing the fingerprint extracting method based on active directional Fourier domain filtering. The proposed method, as shown in Fig.10, is typical the technique proposed in [1] Which have the first steps but is different in the next steps, based on what is stated by Sherlock for mixing up the two algorithms and gain from the first adaptive feature extraction and the Fourier direction from the second in a fast manner. After the typical steps, we apply the next steps during extracting minutia details, i.e. (x, y, , Type ). Because each block has a ridge/ minutia will have a direction that is helpful in finding out the minutia. Minutia direction is approximated to the nearest neighbor orientation of 16 predefined look up orientations. Next steps describe orientation calculations process

• · For each 16 by 16 window at the point where Local Ridge Orientation is found. In turn, the window will rotated to 16 orientations, where ϴ_i=i/16,i=0-15 and compute the projection along the Y-axis :

.

Where wi(x, y) is the delta inside the window at angle ϴi. Then a second filter removes noise from the projection.

• · The total variation of each filtered projection is evaluated through the equation :

‎[10]

• · The vi_max is the maximum of the 16 variation.
• · Compute the best theta of 16 thetas based on  to be the best minutia orientation.

Thus, the proposed minutia extraction algorithm is derived from the algorithm proposed [1] and the methodology specified in ‎[10]. The proposed method introduces more improvement in both

 After traditional steps, the flow is continued to perform:

3.    Thinning ridges so that they have single pixels for finding out minutia coordination, as shown in Fig. 7;

Fig 7: Thinned Image

4.    In order to reduce number of bad minutia details, image is smoothed before locating minutia for reducing noisy minutia, see Fig 8

Fig.8: Smoothed Image

All the ridge end points and ridge bifurcation points detected through this method are not always true features, but the method does seem to identify most of the true feature pointError! Reference source not found.. As shown in Fig 9.

Fig 9: Located Minutiae

In Table 1, the extracted samples of valid minutia are listed and each of which is classified based on ridge type whether ridge end or bifurcation.

Table 1 Extracted Minutia

In the previous table, we listed three samples of input fingerprint images. Each has subsamples of features extracted from each image. These subsamples are listed as feature vector Vij that is classified in the following general form:

Where i is the ith input image whereas j is the order of extracted feature of input. While X,Y, ϴ are used to represent coordination and orientation respectively and Type is used to inform more details about the extracted feature. For example, V13 = (124, 38, 3.141593, Ridge End) represents the third feature of the first input image, V25 = (233, 233, 0.5258251, Bifurcation) represents the fifth feature of the second input image and so on.

Fig 10: Proposed Feature Extractor

III.       Post-Processing

It eliminates spurious feature points based on the structural and spatial relationships of the minutiae, and then validates the minutiae points [1]. Therefore, a large number of spurious minutiae are deleted based on using a predefined threshold suitable to filter up the noisy minutiae, as shown in Fig. 11. This method does seem to identify most of true feature points; and the post-processing stage filters out the undesired feature points based on their structural characteristics.

Fig12: Fingerprint Minutiae

Fingerprint Matching Techniques

There are many fingerprint matching algorithms which can be classified into three categories: correlation-based matching, minutia-based matching and ridge-based feature matching. Correlation-based matching can save most information in fingerprints although it is fragile to nonlinear distortion, Minutia-based methods are flexible but are sensitive to noise, ridge feature based methods are robust to noise but it is less distinctiveError! Reference source not found..

There is many classification methods based on minutia matcher but the most simplest and efficient strategy is Traditional Minutiae-based Matching Algorithms (TMMA).TMMA combines fingerprint features, i.e. minutia; positions, orientations and type. So the matching result on the feature vector determines fingerprints matching, by comparison. Comparison is based on estimating matching score of the features that were extracted from the input query finger image and the template features. The dot product of the feature is performed to pick up the largest template with a certain threshold. The template features with highest matching score is considered as the better for identification process‎[13]. If the picked template passes the matching threshold, person/user whose own the query feature is identified and authorized to log in the system or whatever application using personal fingerprint biometric characteristics. The comparison is performed between two feature vector say a feature of template feature vector Ftemplate (XT, YT, ThetaT, TypeT)  and a feature of query feature vector Fquery (Xq, Yq, Thetaq, Typeq). Using Ftemplate and Fquery ; comparing each pair together to get is matched or not, if matching is correct, matching score is incremented by 1 but if matching is not correct, go to pick next feature for matching procedure until finish comparison of all features in the query feature vector, see Fig 12.

Fig 12: Matching Query and Template vector

Implementation and Experiments

Experiments Measures

• ·         False match rate (FMR): The probability of invalid inputs which are incorrectly accepted.
• ·         False non-match rate (FNMR): the probability of valid inputs which are incorrectly rejected.
• ·         Relative operating characteristic (ROC): The ROC plot is a visual characterization of the threshold between the FMR and the FNMR.
• ·         Equal error rate (EER): The rates at which are both accept and reject errors equal.

This experiment uses the evaluation protocol of the Fingerprint Verification Competitions [2]. The performance indicators computed in this experiments are: EER, FMR and average match time‎[14].

Evaluation of Experiments

  The experiments reported in this paper has been conducted on the public domain collection of fingerprint images , DB1_B in FVC2004 , DB3_B in FVC2004 and DB3_B in FVC2002 ‎[15], each containing fingerprint images of size (640 *480) pixels . We have done our experiments on windows 7, processor core i7 and RAM 6 GB to obtain high accuracy and performance. Results are tested and produced by adding different databases, then choose the algorithm either basic adaptive feature extractor that was proposed in [1] or modified adaptive method which is proposed here in order to be used to compute the features (minutiae, orientation image, and skeleton image) and you can also select the matcher to select the fingerprint verification algorithm. After a set of experiments have been conducted we found these results shown in Fig 13.

As shown in figure when using Fingerprint matcher with orientation image extractor, typical as stated in [1], we get lower average match time than when we use the modified and presented algorithm and the EER and FMR are the same then we deduced that using method in [11] as orientation image Extractor affects only on the average match time

Fig 13: Fingerprint matcher with stated orientation image extractor and minutia extractor stated in [1]

In Fig 13, there are three curve lines each line represents a performance of fingerprint extraction process using certain fingerprint database; FVC 2002-3-B,  FVC 2002-3-B, FVC 2004-1-B. Vertical axis represents the total time for extraction. Comparing pair time consumed by fingerprint extraction process using the same database, improved and optimum time cost. In few words, the proposed extraction is faster than traditional original extraction presented by authors in [1].

Conclusion and Future Work

After many trials and long epochs of using different cited databases, we can come to a conclusion: efficiency of the speed of hybrid algorithm using the same feature matcher. Based on these results, a hybrid algorithm is more efficient than the original one, proposed in [1]. The proposed technique gets lower average matching time than the original technique. In addition, the proposed method is classified as a local minutia extractor and can be compatible with any proposed or supported minutia matcher.