International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

Menu

ISSN ONLINE(2278-8875) PRINT (2320-3765)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Latent Fingerprint Matching using Alignment Algorithm Based Hough Transform

G.Rekha1, S.V.S Jaya Shyam2
  1. PG Student (DSCE), Department of ECE, S.V.Engineering College for women, Tirupati, AP, India.
  2. Assistant professor, Dept. of ECE, S.V.Engineering College for women, Tirupati, AP, India.
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

Abstract

Identifying suspects based on latents which are lifted from crime scenes is extremely important to forensics and law enforcement agencies. Latent’s are the partial fingerprints usually smudgy and blurred with small area, and contain large distortion. Due to these characteristics, they have a considerably smaller number of minutiae points compared to full fingerprints and therefore it can be extremely difficult to automatically match latent’s to plain or rolled fingerprints that are stored in law enforcement databases. The goal is to develop a latent matching algorithm that uses only minutiae information. The proposed latent matching algorithm consists of three modules: (i) Align two sets of minutiae with a descriptor based Hough Transform; (ii) Establish the correspondence between minutiae; and (iii) Compute a match score.

Keywords
Fingerprints; Hough Transform; Latents; Minutiae; Matching

INTRODUCTION
The practice of identifying suspects using latent fingerprint is not new. Law enforcement Agencies have started using fingerprint technology to identify suspects since the early 20th century. No two individuals will have same fingerprints made many law enforcement agencies aware of the potential of using fingerprints as a means of identification [14]. Fingerprint recognition started as a completely manual Approach. Growing demands on fingerprint recognition, initiated a research to automate fingerprint recognition, which developed an Automated Fingerprint Identification Systems (AFIS).These systems are used worldwide such as in law enforcement agencies, many other government and commercial applications. Today fingerprint recognition is consistently used in civilian applications that have stringent security requirements.
Fingerprints can be broadly classified in to three categories which are: 1) rolled; 2) plain; 3) latent. Rolled and plain fingerprints are also called full fingerprints. Rolled print is obtained by rolling the finger "nail-to-nail" on a paper or the platen of a scanner; plain print is obtained by placing the finger flat on a paper or the platen of a scanner without rolling; and latents are lifted from objects surface which are inadvertently touched or handled by a person typically at crime scenes as shown in Fig.1. Lifting of latents may involve a complicated process, and it involves simply photographing the print to more complex dusting or chemical processing [1].
Rolled fingerprints contain the largest amount of information since they contain information from nail-to-nail; latents typically contain the least amount of information for matching or identification. Latents capture only a small finger area. They are smudgy and blurred, and have large nonlinear distortion due to pressure variations. Due to their deprived quality and small area, latents have a drastically smaller number of minutiae compared to full prints. That uniqueness makes the latent fingerprint matching problem very tricky.
Manual latent fingerprint identification is performed following a procedure referred to as ACE-V which involves Analysis, Comparison, Evaluation and Verification. This procedure is quite tedious and time consuming for latent examiners, and requires a large amount of human intervention. Latents are generally matched against full prints of a small number of suspects. With the invention of AFIS, fingerprint examiners identify latents using a semi-automatic procedure that consists of following stages: (i) manually mark the features in the latent, (ii) launch an AFIS search, and (iii) visually verify each of the candidate fingerprints returned by AFIS. The accuracy and speed of this procedure is not satisfactory. Fig.2 shows three latents of different quality.
The objective is to develop a latent fingerprint matching algorithm that is solely based on minutiae and also to obtain higher matching accuracy. Since physically marking of minutiae in latents is a common practice in the latent fingerprint community.

II. RELATED WORK

A. Full Fingerprint Matching
Minutiae information is used in most of the algorithms to match fingerprints. Although, Minutiae hold a great amount of unfair details; in some cases added features may increase the accuracy. Most of the proposed algorithms for fingerprint matching that uses non-minutiae features also use minutiae information. Fingerprint matching using local minutiae descriptors is explained in [5]. Local minutiae descriptors are used to achieve the alignment between two fingerprints by considering the most similar minutiae pair in the initial step; obtaining a better matching performance is the next step.

B. Latent Fingerprint Matching
Latest research and development efforts on latent fingerprints can be broadly classified into three streams according to the manual input requisite from fingerprint examiners: reliable with existing practice, ever-increasing manual input, or dropping manual input. Because of great variations in latent fingerprint eminence and specific requirements of practical applications, each of the three streams has its mark. Enhanced latent matching accuracy has been resulted by using extended features, which are manually marked for latents [4]. Nevertheless, marking extended features (orientation field, ridge skeleton, etc.) in deprived quality latents is very time-consuming and might be only possible in rare cases Therefore, some studies have concentrated on latent matching using a condensed amount of manual input, i.e., region of interest (ROI) and singular points which are marked manually. Thus, only a minute portion of latents can be properly identified using this method. Thus our projected matcher takes manually marked minutiae as input and, therefore, it is reliable among existing practice. There are some developments on fusion of multiple matchers [11] or multiple latent prints [12].
In the ACE-V practice, the examiner analyzes the latent image visually and they decide whether the latent has value for exclusion, individualization or no value. If a latent is given as of no value, comparison is not performed. If the latent has a value, then comparisons are performed and the examiners can make individualization, exclusion, or determine the comparison to be uncertain. So the latents which are successfully identified constitute only a small part of all latents, which are of rational quality.

C. Evaluation of Latent Examiners
A latent examiner may be a slow but very precise “matcher”. They are comparatively slower than automatic matchers, so quantitatively estimating the accuracy of latent examiners is not so easy. It was found that latent examiner’s conclusions are not always in agreement, in particular in the case of poor quality latents. In addition, the same examiner can change his/her conclusions on the same fingerprint pair at a later on time. These inconsistencies may increase in bias.
When the automatic matcher can outperform latent examiners in accuracy all the issues associated with including latent examiners in the latent identification process will be solved. No matter how successful the application of automatic fingerprint recognition technology might be, before we can reach the goal of outperforming latent examiners we cannot say fingerprint matching is a “solved problem”.

III. LATENT MATCHING APPROACH
There are three main steps in fingerprint matching: alignment of the fingerprints, pairing of the minutiae, and score computation. In our approach, we use a Descriptor based Hough Transform to align two fingerprints.
Given two sets of aligned minutiae, two minutiae are considered as a matched pair if their Euclidean distance and direction difference are less than prespecified thresholds. Finally, a score is computed based on a variety of factors such as the number of matched minutiae and the similarity between the descriptors of the matched minutiae pairs. Fig.3 shows an overview of the proposed approach. It is important to emphasize that while latents are manually encoded (namely marking minutiae); minutiae in rolled prints are automatically extracted.

A. Local Minutia Descriptor
Minutia Cylinder-Code (MCC) is a minutiae representation based on 3D functions [5]. In the MCC representation, a local structure is associated toward each minutia, where this local structure is represented as a cylinder, which contains information about the relationship between two adjoining minutiae. The base of the cylinder is related to the spatial relationship, and its height to the directional relationship. Every cell in the cylinder accumulates help from each minutia in the neighborhood. The resulting cylinder is concatenated as a vector, and so the similarity between two minutia descriptors can be effectively computed as a vector correlation measure [5]. This representation has some advantages, Such as: invariant to translation and rotation; robust against small skin distortion and missing or spurious minutiae; and of fixed length.

B. Fingerprint Alignment
Fingerprint alignment involves estimating the parameters (rotation, translation and scale) that align two fingerprints. A number of features may be used to estimate alignment parameters between two fingerprints, including orientation field, ridges and minutiae. Generalized Hough Transform, local descriptors, energy minimization are the various methods to align two fingerprints.
In the latent fingerprint matching, singularities are not present always, making it difficult to base the alignment of the fingerprint on singular points only. To attain manually marked orientation field is expensive, and to extract orientation field from a latent image automatically is very challenging. Since manual marking of minutiae is a universal practice for latent matching, our advance to line up two fingerprints is based on minutiae.
An alignment process for minutiae matching which estimates parameters like scale, rotation, and translation by using a Generalized Hough Transform is introduced in [9]. Given two sets of points (minutiae), a matching score is computed for each transformation in the discretized set of all allowed transformations. For every pair of minutiae, one minutia from each image, and for given scale and rotation parameters, exclusive translation parameters can be computed. Each parameter receives "a vote" relative to the matching score for the corresponding transformation. The transformation that gives the greatest score is considered as the best. In our approach, the alignment is done in a very similar way, but the evidence for each parameter is accumulated based on the similarity among the local descriptors of the two involved minutiae, with the correspondence and descriptor being the ones described in Section III.A.
Given two sets of minutiae to compare, one from the latent print and the other from the rolled print. Rotation and translation parameters can be achieved for every possible minutiae pair (one minutia from each set). Let {(���� , ���� , ����)} and {(����, ����, ����)} be the minutiae sets for latent and rolled prints centered at their means respectively. Then, for every minutiae pair, we have
             (1)
            (2)
Since it is not essential to consider the scale parameters in fingerprint matching, translation parameters can be achieved uniquely for each pair depending on the rotation difference between the paired minutiae. The parameters of translation and rotation are quantized to their neighboring bins. Once quantized, evidence is accumulated in the corresponding bin based on the similarity between the local minutiae descriptors. The assumption is that true mated minutiae pairs will vote for very similar sets of alignment parameters, while non-mated minutiae pairs will vote randomly throughout the parameter space. Thus, the set of parameters that presents the highest evidence is considered the best. For robustness, more than one set of alignment parameters with high evidence are to be considered.
In order to make the alignment more accurate and computationally efficient, a two stage approach for the Descriptorbased Hough Transform is used. We first perform the voting in a relatively common parameter space. Based on the peaks in the Hough space, we replicate the voting inside a neighborhood around the peaks, but with a more advanced set of parameter range. Then keep track of the points that contribute to the peaks and compute a rigid transformation matrix from those points.

C. Minutiae Pairing
After the alignment of two sets of minutiae, we need to find the minutiae correspondences between the two sets, i.e. minutiae which need to be paired. The pairing of minutiae consists of finding minutiae that are suitably close in terms of location and direction. Let ���� = (����,���� , ����) be a minutia from the aligned latent and ���� = ������ ,���� , ���� �� be a minutia from the rolled print. Then, mi and mj are considered paired or matched minutiae if
        (3)
        (4)
In aligning two sets of minutiae, we use a one-to-one matching; this is the most natural way of pairing minutiae. Which means each minutia in the latent can be matched to only one minutia in the rolled print. Ties are broken depends on the closest minutia.

D. Score Computation
Score computation is a very essential step in the matching process. A straight approach to compute the matching score consists of the number of matched minutiae divided by the average number of minutiae in the two finger- prints. This is not appropriate for latent matching because the number of minutiae in different latents varies significantly. One solution to modify the above said scoring method is to divide the number of matched minutiae by the number of minutiae in the latent, which is almost always smaller than the number of minutiae in the rolled fingerprint.
In our approach, we use minutiae correspondence to weigh the contribution of each pair of matched minutiae. Given a latent fingerprint and a template fingerprint (rolled), and consider that the fingerprints are already aligned, let �� be the set of �� matched minutiae pairs between the two fingerprints,�� {����}�� �� = 1 be matched minutiae pairs in ��, {����}�� �� = 1 be their respective similarities, and �� be the number of minutiae in the latent. Then, the matching score between the two aligned fingerprints is given by:
        (5)
To further improve the matching performance, combine the scores based on matched minutiae from two different pairing thresholds by their weighted sum; assume equivalent weights. As we perform 10 different alignments, we compute 10 different scores between two fingerprints; the final score between the two fingerprints is the maximum among the 10 scores computed from dissimilar hypothesized alignments.

IV. EXPERIMENTAL RESULTS
Matching experiments were performed on the NIST SD 27, which contains 258 latent fingerprint Images. The background database consists of 258 mated full prints from NIST SD27, and the first 2,000 rolled impressions from NIST SD14 [8]. So, the total number of background prints is 2, 258. NIST SD27 contains latent prints of three different qualities, termed "good", "bad", and "ugly", which were classified by latent examiners as shown in Fig. 2.
The number of minutiae in the latent print shows the fingerprint quality which affects the matching performance. With the number of minutiae �� in latents in NIST SD 27 are classified into three groups: large (�� > 21), medium (13 < �� < 22), and small (�� 13), containing 86, 85, and 87 prints, correspondingly.
Manually marked minutiae are used as features in latent fingerprints. For full fingerprint images, only minutiae are needed for matching and they are automatically extracted.
Minutia Cylinder Code is used as local descriptors for minutiae. MCC parameters are set [5], with the number of cells along the cylinder diameter as 8 (����). We consider all cells in a cylinder as valid cells. For Euclidean distance pairing, we use two different thresholds, 15 and 25 pixels, and direction difference threshold of 20 degrees.
To approximate the alignment error, true mated minutiae pairs are used which are marked by fingerprint examiners, to calculate the average distance of the true mated pairs after alignment. If the average Euclidean distance for a given latent is less than a prespecified number of pixels in at least one of the ten paramount alignments, it is considered as accurate alignment.
There are very few errors in alignment, if the average alignment error is considered as less than 25 pixels. The main cause for these failure cases is there are a very small number of true mated minutia pairs in area between the latent and mated rolled print, so there are very less true mated pairs voting for the correct alignment parameters. The lack of true mated pairs is due to limited number of minutiae in latents and the poor quality region in the rolled print. One such example is shown in Fig.4. Blue squares are manually marked minutiae in the latent print (left) and automatically extracted minutiae in the rolled print (right). Red triangles indicate ground truth minutiae pairs, and the yellow lines indicate true mated pairs.
Though the pairing of minutiae is based on Euclidean distance and direction difference and is comparatively simple, it works well after the fingerprint alignment using the Descriptor based Hough Transform.
Fig.5 shows example latent prints of good and ugly qualities correctly identified at rank-1 and Fig.6 shows examples of latent prints incorrectly identified at higher ranks because of the alignment errors — there are not adequate matching minutiae pairs in the overlapping area between the latent and mated rolled print.

V. CONCLUSIONS AND FUTURE WORK
A fingerprint matching algorithm for matching latents to full fingerprints is designed and presented, which outperforms the commercial matcher VeriFinger on all qualities of Latents in NIST SD27. The development in the rank-1 accuracy of the proposed algorithm over VeriFinger varies from 2.3% to as high as 22% for latents with the quality "ugly". These results show that our matcher is more appropriate for latent fingerprints.
The proposed alignment technique performs very well even on latent’s that contain small number of minutiae. In our algorithm, maximum score is considered from several hypothesized alignments based on different alignment parameters. Sometimes, the maximum score does not correspond to the correct alignment. We plan to improve the score computation by applying learning methods. Extended features manually marked by latent examiners have been shown to be beneficial for improving latent matching accuracy. We plan to incorporate extended features which are automatically extracted from the image into the current matcher to further improve the matching accuracy.
A texture-based descriptor can be included to improve the matching accuracy especially when the overlap area between the latent and rolled prints is small. Additional automatically extracted features can be included to improve the matching performance without an increase in manual labor. Although the proposed matcher is more accurate than the two existing matchers, they are significantly faster. An indexing algorithm can be developed to speed up latent matching.

Figures at a glance
Figure 1 Figure 2 Figure 3
Figure 1 Figure 2 Figure 3
Figure 4 Figure 5 Figure 3
Figure 4 Figure 5 Figure 6
 

References