Keywords

1 Introduction

Automated person identification of a person through automated systems is possible due to emerging biometric technologies. Research carried out in biometric identification includes face, IRIS, palm prints and fingerprints. Among all, finger print identification systems is considered as highly preferred biometric system due to its reliability and accuracy. Main aim of fingerprint identification system is to verify the identity of a person and the challenge arises in fingerprint matching. Fingerprints have achieved great success in past several decades and are widely used in personal verification and identification [1]. The use of fingerprint identification systems avoids the need of remembering passwords and they have been extensively used in applications like attendance systems, banks, building security, law enforcement, commercial, civilian and financial applications [2]. Due to good identification accuracy, fingerprint based identification systems have put up themselves in a better market place than any other biometric systems.

In fingerprint recognition method [3] or identification method [4], following common steps are performed to build a database of templates:

  1. 1

    Enrollment stage: Templates are formed by extracting features from a captured fingerprint and are stored in a database.

  2. 2

    Verification stage: The template of query fingerprint is formed in the same manner and it is compared with the stored template. Matching decision is made based on the matching criteria.

Captured fingerprint images cannot be directly stored to perform matching. Rather, feature extraction is done before proceeding for matching stage. Feature extraction is a process of identifying important properties of the fingerprint which later can be used in fingerprint matching. Fingerprint features can be made up of three levels [5]. Level-1 features provide macro level information about the singular points, ridge flow, ridge orientation or ridge frequency. These features form the global feature set. Other global features containing the singular points include core point, delta point, and ridge counts. Level-2 features are made up of minutiae points. Minutiae points are the unique fingerprint features obtained from a person’s fingerprint. Ridge bifurcations and endings form the local minutiae features. These minutiae points show significant variations from one fingerprint to another. Level-3 features comprises of low level minutiae features like sweat pores, ridge shape, ridge width, dots and curves.

These features are shown in Fig. 1. Left loop, right loop, whorl, arch and tented arch are the other ridge features shown in Fig. 2. Limitation of level-3 features is that it can only be observed in images captured from high resolution cameras.

Fig. 1.
figure 1

Fingerprint image features.

Full size image
Fig. 2.
figure 2

Basic ridge features.

Full size image

Most of fingerprint identification systems make use level-2 features. This is because fingerprint minutiae are the most unique and reliable features. After feature extraction step, next goal will be to identity a person’s fingerprint from stored database. The task of matching step will be to provide match score between two fingerprints based on their likeliness. Most of the methods use minutiae based matching, but there are other methods of matching. These are based on image correlations of images, level-2 and level-3 features. Shape, edge and texture features [40] can also be used for matching fingerprints. Pattern matching using minutiae features is being widely used to match the fingerprints from past decade. Results have shown that fingerprint storage is most efficiently used.

Also matching results have been proven in courts [6]. Recently, researchers have used local minutiae structures to align fingerprints and results at a global level are obtained from locally obtained results.

Latent fingerprint identification system is used in criminal investigation and forensic applications. Latent fingerprints are the impressions which are unintentionally left on the objects. The latent fingerprint matching techniques pose more difficult challenges compared to conventional fingerprint matching. This is mainly because minutiae in latent patterns may get missed out due to its nature or may get distorted by noise. Low image quality, poor texture, and non linear distortion in fingerprints create additional challenges in latent fingerprint identification system. Minutiae clustering based pattern matching technique for a latent fingerprint are unexplored. This paper proposes a study on minutiae clustering approach for pattern generation and recognition for latent fingerprint applications. Unique latent minutiae feature vector is defined from minutiae triangular features. A hash value is generated from different arrangements of feature vector. The obtained hash values are used to construct hash-table. Proposed hashing method shows significance improvement in the matching speed and accuracy. The paper is organized as following; Sect. 2 discusses about the related work carried out in conventional fingerprint matching. Section 3 introduces to the proposed pattern matching methods based on connected minutiae clusters. Section 4 describes the experiments carried out on latent database and Sect. 5 concludes the work.

2 Related Work on Fingerprint Matching

This section deals with work carried out by various researchers in the field of fingerprint matching.

2.1 Correlation Based Techniques

In most of the work carried out so far, fingerprint minutiae feature is most popularly used. This is because fingerprint minutiae contain unique and reliable features. In addition, the templates generated from minutiae information consumes less memory and are faster than the graphical based fingerprint matching. In correlation based technique, two fingerprint images are made to overlap on each other and the respective overlapping pixels at different alignment settings are used to compute the similarity score. This is simple operation but this did not yield acceptable results. This is mainly due to variations that occur in brightness and contrast of the image. Many researchers used different methods to improve this technique.

2.2 Minutiae-Based Features

Minutiae based matching algorithm are mainly designed to solve problems of connected minutiae and similarity score. Most of the indexing techniques make use of minutiae features [7,8,9,10] and are derived from its neighborhood relations. These features form geometrical patterns and are invariant to rotations and translations. Minutiae Cylinder Codes (MCC) [11] has been considered as state-of-art technique for minutiae neighborhood representation and is widely used in fingerprint matching or indexing.

2.3 Fingerprint Indexing and Clustering Technique

Fast access of fingerprint templates database for identification is possible using fingerprint indexing. Partially extracted minutiae information can be one indexing technique used to build local structures. This information can be used to calculate fingerprint similarity and to generate key indexes. Ordering of candidate templates done in this way increases the probability of match. Another indexing technique uses triangle characteristics like length, and angle [10]. This type of triangulation technique helped to improve the matching efficiency [12]. Delaunay triangulation technique connects the minutiae in its neighborhood using triangles to identify minutiae orientation and position. Triangular structure obtained using this technique doesn’t much vary even if there are deformations in rotations or translations. Thus, minutiae matching using Delaunay triangle technique provide good performance with respect to match time and nonlinear distortions. Similarly, another Delaunay Triangulation [13] approach for fingerprint alignment and matching was proposed. Here global matching was done by comparing using minutiae points and singular points. Fingerprint matching using local features called as Voronoi neighbor structures (VNSs) [1] were used which are robust, rotation and translation invariant.

Several researchers worked on indexing techniques based on clustering and found out significant improvement in the matching accuracy. Fingerprint indexing using dynamic clustering technique [14] extracts translation and rotation invariant features from triangles constructed from triangle spiral from fingerprints. Automatic Fingerprint Identification using clustering technique [15] uses identification module to detect identical minutiae clusters from template images. Here the evaluation of minutiae cluster is done and based on the results the feedback module trains the core vector. Translation and rotation invariant cluster based template generation for fingerprint matching [17] stores fingerprint templates instead of minutia feature vectors. Latent fingerprint clustering using deformable minutiae [16] uses multiple merged and overlapping matching minutia pair clusters.

2.4 Fingerprint Based Pattern Matching Technique

This is a process of matching the individual persons fingerprint features against the features of database templates for person verification [21]. Pattern matching method is used in latent fingerprints for matching a set of primitive latent features with enrolled fingerprint database. Pattern matching is achieved by developing templates using global and local features [22] and matching against stored database template. These features are invariant to global transformation functions. Success of any fingerprint based pattern matching technique depends on absence of fingerprint distortion, noise, arch [23] and identification of core point and minutiae points. Core points and minutiae points are most commonly used as they are invariant to ridge patterns.

The combinations of Euclidean distance and ridge features [20] can be used for minutiae based fingerprint matching. Initially, minutia pairs were obtained using Euclidian distance for representation of transformation invariant features. Here, minutiae features were obtained from ridges and they were grouped together. Finally, histogram based modeling was used for similarity score computation. This method is suitable for AFIS with limited memory space. Fingerprint pattern matching in AFIS using minutiae neighborhood and singular points [18] have produced good matching accuracy. In this method Euclidian distance is used to calculate the distance between singular point and minutiae. This relationship between singular point and minutiae is utilized to calculate pattern matching scores. Pattern recognition and matching algorithm using core point was proposed in [24]. Such technique is suitable for real time AFIS.

A Partial fingerprint recognition system based on local features [25] was proposed to overcome miniaturization problem arising from fingerprint sensors capturing small sensing areas. This is because sensors capture only a part of the fingertip due to small area limitation or improper fingertip placement of the fingertip or scars on fingerprint due to injury [26, 27]. Partial fingerprint recognition system using global features [19] was proposed. Here pattern matching depends on core point, delta point and ridge flow. Fingerprint recognition using Dynamic Time Warping (DTW) [44, 45] was proposed to compress the fingerprint feature matrix into a single vector to save the information.

A detailed survey done on available computational algorithms [43] for fingerprint recognition helps in selecting suitable algorithm for a given fingerprint application.

Latent fingerprints pose more complex challenge compared to normal fingerprints due to presence of background noise and poor quality latent image. This affects the matching speed as the time taken to extract minutiae features from poor quality fingerprint is more. Robust minutiae algorithms [28,29,30] were proposed to overcome false minutiae detection and matching. Image segmentation technique [31] was proposed to reduce matching speed in AFIS. Segmentation is a process of partitioning fingerprint foreground information from irrelevant background noises. For classifying fingerprint match or no match, an active learning method [41] can be used. A supervised k-NN [42] can be used for classifying the fingerprint data. Here the data which is closest to the cluster center and the farthest from the cluster fingerprint is calculated and classified to reduce classification speed. Latent fingerprint based pattern matching is an unexplored field. This paper proposes a study on latent fingerprint based pattern matching, which is discussed in Sect. 3.

2.5 Recent Trends in Fingerprint Matching

Due to advanced hardware technology, the performance of fingerprint matching used in personal identification is improving. Different fingerprint features are being used in matching to achieve high matching accuracy. These methods are discussed in the next section:

Fingerprint Matching with Hardware Acceleration:

Hardware acceleration can speed up the matching process and many researchers are working in this direction. Hardware acceleration using FPGA [32], distributed computing [33] and GPU [34] based architectures are successfully being used for this purpose.

Use of Embedded Systems:

Different embedded systems using smart cards [36] and sensors [35] are being used to improve the performance of matching.

Palmprint Matching:

This is achieved using minutiae and ridge features. Techniques followed in latent fingerprint matching [37, 38] can be utilized in palmprint matching.

Multi-feature Based Matching:

Other human features like face recognition [39] and fingerprint features can be combined to improve matching accuracy.

3 Proposed System for Latent Fingerprint Matching Using Clustered Minutiae Patterns

Latent minutiae fingerprints suffer from low resolution, background noise and nonlinear distortions. To address these problems, a minutiae feature based hash index method is adopted. First we begin with minutiae feature extraction. After obtaining minutiae features, a fixed length minutiae descriptor is created to perform matching. This descriptor is based on the neighborhood geometry pattern and is invariant to affine minutiae deformations. Hence, it can be directly applied on minutiae based templates. Another advantage of using this descriptor is that there is no need to detect singular points to align the templates.

3.1 Feature Extraction

Preprocessing of latent fingerprint is done before extracting features. Preprocessing contains steps like binarization and thinning. In binarization, a grey level image is converted into a binary image. This process involves the examination of each grey pixel value and thresholding it to binary ‘0’ or ‘1’ based on the grey level.

Thinning is carried out before proceeding to feature extraction. In this step, each pixels neighborhood from the binarized image may be deleted based on the pixel deletion criteria. It performs a morphological operation in which foreground pixels are removed until they become one pixel wide.

Finally, minutiae extraction is carried out after the preprocessing step. Crossing Number (CN) technique is used on the obtained skeleton image from the previous step. Ridge patterns are 8-connected. Hence, minutiae points are extracted by sliding a 3 × 3 window on the fingerprint image and ridge pixels are found from its local neighborhood. Based on the neighborhood connectivity, minutiae features such as ridge ending or bifurcations can be obtained.

Minutiae based indexing schemes provide better results than other indexing schemes. Hence indexing based on Minutia Cylinder Code (MCC) is most widely used and is considered to be state-of-art indexing technique. Major limitation of this method is that it is not invariant to affine transformations. A new fixed length local minutiae descriptor based indexing technique is proposed to overcome the above limitation. A latent minutiae feature vector is defined to capture the minutiae neighborhood information and is discussed next.

3.2 Latent Minutiae Feature Vector

A fixed length local latent minutiae descriptor is proposed to obtain the minutiae distinctiveness from its neighborhood. This representation is used to compare two minutiae points, which in turn helps to determine the fingerprint similarity. The procedure followed to create a latent minutiae feature vector is listed below:

  • Consider ‘n’, which defines the total number of latent minutiae feature points (L) around a central latent minutia. Let n = 7, then L1, L2, L3, L4, L6, L7, and L8 are the 7 nearest latent minutiae neighbors obtained around L5. This is indicated in Fig. 3(a).

    Fig. 3.
    figure 3

    (a) Nearest ‘n’ latent minutiae around L5 (n = 7) (b) ‘m’ invariants p, q, r, s, t, u obtained by rotating P, Q, R, S clockwise around L5.

    Full size image

  • Consider ‘m’, which defines the possible local geometric arrangements around L5. These arrangements produce geometric invariant features which will help in the construction of feature vector. This is obtained by choosing four coplanar points P, Q, R, S on latent minutiae and rotating it in clockwise direction around L5. To decrease the probability of similar geometric arrangements, higher value of ‘m’ must be chosen. If the value of m = 4 (equal to number of coplanar points) is chosen to produce geometric arrangements, then it will become difficult to discriminate these similar arrangements from one another. Hence, to increase the discrimination power the value of m = 6 is chosen. As a result of this, six geometric arrangements namely p, q, r, s, t, u will be formed by rotating the points P, Q, R, S around the six nearest latent minutiae in clockwise cyclic order. Here, L3, L4, L2, L1, L7 and L6 are the six nearest latent minutiae obtained around L5. Since n = 7 and to obtain six invariant arrangements, the farthest latent minutia should be discarded. The ‘m’ invariants pqrstu indicates the feature vector shown in Fig. 3(b). This information will be used to generate feature vectors from combination of above arrangements. This is explained later.

3.3 Triangular Features

With P, Q, R, S points, different indexing features for construction of feature vector can be extracted. They are given below:

  • The ratio of the triangle areas formed by latent minutiae triplets P, Q, R and P, Q, S.

  • The ratio of the triangle lengths (larger-side) of latent minutiae triplets P, Q, R and P, R, S.

  • The ratio of minimum and median triangle angles formed by latent minutiae triplets P, Q, R and P, R, S.

Features mentioned above are invariant to translation or rotation. Hence, the latent minutiae feature vector can be obtained by considering different combinations of above triangular features.

3.4 Fingerprint Hash-Table

Here we are creating hash table using feature vectors. The same was discussed in the previous section. By rotating P, Q, R, S points clockwise, possible permutations of these feature vectors are: pqrstu, qrstup, rstupq, stupqr, tupqrs, upqrst. Each feature vector ‘fv’ is considered for hashing. The values to be stored in the hash table depend upon the hash value and it is calculated from Eq. 1.

$$ HT_{index} \; = \;\left( {\sum\limits_{{\text{i = 1}}}^{\text{m}} {f_{u} \left[ i \right] \times k^{i} } } \right)\,\text{mod}\,HF_{size} $$
(1)

Here, ‘HTindex’ is the hash index used in construction of hash-table, ‘fv’ is the feature vector having the length ‘m’, ‘k’ is the level of quantization to be chosen for invariant and ‘HFsize’ is the size of the hash function table. ‘fv’ is the discretized invariant feature vector obtained from weighted combination of triangular features and the quantization value chosen should be in the range of [0, k] to generate unique hash-value in the table.

figure a

These produce unique hash values which will be used in construction of hash-table. Construction of fingerprint hash-table is explained in Algorithm 1. Figure 4 shows the complete construction of fingerprint hash table. The latent fingerprint-ID, minutia-ID and feature vector are stored in the corresponding hash-table index. All these features are stored in the form of linked lists. Collisions can occur when multiple feature vectors map on to the same index of hash-table. To avoid this chaining technique is employed to resolve this problem. Size of the hash-table is calculated as below:

Fig. 4.
figure 4

Construction of fingerprint hash-table.

Full size image

  • n = 7, m = 6, and k = 15.

  • Number of latent fingerprint images in the database is 80.

  • Average number of feature-points from each latent fingerprint image is 6377.

  • The latent fingerprint-ID, minutia-ID and feature vector are stored as 2-bytes, 2-bytes and 1-byte variables respectively in the corresponding hash-table index.

  • A pointer to index this hash-table requires 8 bytes.

Size of hash-table, HFsize = 80 × 6377 × 7 × (2 + 2 + 1 × 15 + 8) = 96.42 MB of memory.

3.5 Fingerprint Retrieval

Our next task is to perform the matching of query latent fingerprint with the fingerprints in the hash table. For query images, the fingerprint hash-table using feature vectors “v” is constructed in the similar manner as explained in the previous section. Using “v”, latent fingerprint candidate list is retrieved from the hash-table database. Finally, every minutia of query fingerprint casts a vote in its candidate list and based on maximum votes the list of top latent fingerprints is obtained. The fingerprint retrieval procedure is given in Algorithm 2.

figure b

4 Result and Discussions

The results were obtained after conducting an experiment on latent fingerprint FVC_2002_DB4 database. This database contains 80 fingerprint impressions. These fingerprints were used to generate the latent fingerprint hash-table. For experimentation n, m and k values were set at 7, 6 and 15 respectively. The hash function table ‘Hfsize’ is set at 10,00,00,000. In the experiments, latent fingerprint retrieval accuracy is used for analysis. The accuracy is defined in terms of Correct-Index-Power (CIP). It is the percentage of correctly indexed query latent fingerprint images (Nciq) against the total number of latent fingerprint images stored in the database (Nid) as shown in Eq. 2.

$$ {\text{Hence}},{\text{CIP}} = \left( {{\text{Nciq}}/{\text{Nid}}} \right) $$
(2)

A plot in Fig. 5 compares the performance of proposed system on the normal latent fingerprint database FVC_2002_DB4_N against FVC_2002_M (25% Missing minutiae) and FVC_2002_S (25% spurious minutiae). It can be observed that the algorithm produces average 100% retrieval for normal query fingerprints, 99% retrieval accuracy after adding 25% false (spurious minutiae) to the query fingerprints and 76% retrieval accuracy after removing 25% of minutiae (missing minutiae) from the query fingerprints.

Fig. 5.
figure 5

Comparison of Normal (N) minutiae data vs. 25% Spurious (S) minutiae data vs. 25% Missing (M) minutiae data from FVC_2002_DB4 database.

Full size image

A plot in Fig. 6 compares the performance of proposed system on the normal latent fingerprint database FVC_2002_DB4_N against FVC_2002_M (50% Missing minutiae) and FVC_2002_S (50% spurious minutiae). It can be observed that the algorithm produces average 100% retrieval for normal query fingerprints, 45% retrieval accuracy after adding 50% spurious minutiae to the query fingerprints and 22% retrieval accuracy after removing 50% of minutiae from the query fingerprints. It can be clearly observed from Figs. 5 and 6 that the proposed system produces better CIP even after adding and removing minutiae from query fingerprints.

Fig. 6.
figure 6

Comparison of Normal (N) minutiae data vs. 50% Spurious (S) minutiae data vs. 50% Missing (M) minutiae data from FVC_2002_DB4 database.

Full size image

5 Conclusion

Latent fingerprint matching using clustered minutiae patterns was proposed to tackle the fingerprint-indexing problem, where fingerprints are searched through large databases consuming lot of time. A literature survey was done on available minutiae based, index based and pattern recognition based methods. A new rotation and translation invariant method called feature vector was proposed based on neighborhood minutiae relation, which can be directly used on latent fingerprint templates. Feature vector uses triangular features like angles, length ratios, ratios of areas which are invariant to translation, rotation and scaling. A latent fingerprint hashing algorithm based on feature vector was proposed to build hash-table. For fast and accurate latent fingerprint retrieval, a finger-print retrieval algorithm was proposed. The results were obtained by conducting experiments on FVC_2002_DB4 latent database. 25% of minutiae from query fingerprints were added and removed randomly in order to check the robustness of the proposed algorithm against minutia-appearance. Results obtained showed that the retrieval algorithm is robust against the database containing missing or spurious minutiae fingerprints (noisy and low quality images). Also the algorithm effectively dealt with latent fingerprint images containing non-linear distortions. Thus the proposed algorithms are ideal in latent fingerprint matching. However, the performance of the algorithm got degraded when more than 50% noise was introduced. This was done by adding and removing 50% of minutiae from query fingerprint images randomly. More number of false minutiae appeared in the close vicinity of original neighbors in the process of generating spurious minutiae and many minutiae points were removed while creating fingerprint database containing missing minutiae. A new algorithm can overcome this problem.