Fingerprint Identification Based on Hierarchical Triangulation

1. Introduction

Biometric-based identification involves identifying an individual based on physiological and/or behavioral characteristics. In this work, we are interested in one of the individual major biometrics, which can help considerably in the authentication process in secured platforms. Therefore, special focus is given to fingerprint identification.

fingerprint is a pattern formed by the lines of skin of the fingers, palms, toes, or feet. This pattern is formed during the fetal period. Every individual has a unique fingerprint, which is immutable and unchangeable over a lifetime (except by accident, e.g., burning). The probability of finding two similar fingerprints is 10^-24. Twins, for example, from the same cell, can have identical finger global shape but not the same fingerprint.

Compared to other biometric features, fingerprint-based biometrics is the most approved technique with the largest market share; it is widely used in many tasks such as criminal investigations and commercial identification devices. In terms of applications, there are two kinds of fingerprint recognition systems: verification and identification. Verification involves comparing an input fingerprint with the “enrolled” fingerprint of a known user to specify if they are similar and representative of the same finger; this technique illustrates the one-to-one match. On the other hand, in the identification process, the system compares an input fingerprint with all the enrolled users in the database to determine if the person already exists in the users ‘list under a copy or it is an incorrect identity; this technique represents the one-to-N match.

Many matching approaches were proposed in literature [1,2]. The matching method compares the selected feature set with the templates stored in the database by generating match scores. Approaches to matching are based on the image template by seeking correspondence from pixels in the two images regardless of their forms or characteristics. Other methods are based on the minutiae-extracted features, like orientation and minutiae, as mentioned in [3]. These have shown encouraging results, as they are robust against image deterioration.

This paper presents a new fingerprint identification system based on minutiae matching using the Delaunay triangulation method. First, we apply process matching by extracting similar triangles, and then extract the barycenter of similar triangles extracted in the first step. Afterward, we reapply the Delaunay triangulation and extraction of similar triangles. The aim of this approach is to ensure the right location of the matched triangles, which means well-matched minutiae points. The strengths of this system are as follows:

• The use of triangle features as matching parameter ensures robustness to zoom because triangles keep the same proportionality of the parameters in case of change of dimensions.

• Robustness of rotation in the case of a rotated testing image; the results of identification remain unchanged.

• Using only the minutiae-like features extracted; indeed, our approach is also robust with regard to image quality since we avoid using the whole image, which increases the risk of false minutiae; thus, the risk remains minimal.

• The use of the triangulation method in a hierarchical manner ensures that the minutiae found to be similar have the same geographic structure and same coordinates in both images. This guarantees the performance and relevance of the system.

The rest of this manuscript is organized as follows: Section 2 briefly discusses the major steps of fingerprint preprocessing and recognition; in Section 3, the proposed approach is detailed; experimental results are presented in Section 4; Section 5 presents the conclusion.

2. Fingerprint Preprocessing

Fingerprint processing involves analyzing the papillary ridges and then extracting the features. In literature, two kinds of features are noted: global features and local ones. The global features are represented by global shapes called singular points (delta and cores); their number and position allow classifying the fingerprints into six main classes according to an old system called Henry [4]. In this system, the ranking is based on the general topography of the fingerprint, and it allows defining the characteristics (see Fig. 1).

Local characteristics named minutiae are shapes that identify the singularity of the fingerprint image; their localization and coordinates are important key to determining individual uniqueness. Fig. 2 illustrates the main minutiae forms.

Fingerprinting systems are generally based on the use of ridge ending and bifurcation points due to the following reasons: (i) their multiplicity creates a large margin of fingerprint information; (ii) all the others shapes are a combination of bifurcation and ridge ending; (iii) minutiae detection is relatively robust against various causes of fingerprint degradation. A ridge ending point is defined as the end of each single curved segment, with bifurcation as the point where a ridge splits into two ridges. Details such as orientation, type, and location of minutiae are taken into account when performing minutiae extraction.

Fig. 1.

Main Henry classes: (a) arch, (b) tented arch, (c) left loop, (d) right loop, (e) whorl, and (f) whorl (twin loop).

Fig. 2.

Fundamental minutiae shapes: (a) ridge ending, (b) dot, (c) island, (d) ridge crossing, (e) single and double bifurcation, (f) bridge, (g) lake, (h) trifurcation, (i) hook, and (j) opposed bifurcations.

Due to all kinds of distortions and noise like recording conditions or nature of skin, fingerprints’ gray-scale images cannot simply be matched by methods of cross-correlation or Euclidean distance. In fact, the main cause is the appearance of thick ridges or missing pixels, which reduces the fingerprint retrieval performance.

As a solution to these constraints, fingerprint recognition and retrieving systems use an image preprocessing approach before applying any specific algorithm. There are usually two types of preprocessing methods. The first involves estimating the ridges ‘orientations [1] before applying the segmentation. The second type is based on the segmentation of the image and skeletonization without considering the ridges’ orientations. In the end, however, both approaches apply the extraction of minutiae or extraction of singular points for use in retrieval or classification. The succeeding section discusses the details of the aforementioned steps.

Orientation or directional field (DF): The orientation field of a fingerprint image represents the local orientation of the ridge-valley structures, and it is calculated on a regular grid in the fingerprint. In literature, various methods have been developed to estimate the orientation field [5-7] and redefined in [8]. An example of a DF is given in Fig. 3(a).

Fig. 3.

Fingerprint with directional field, singular points, skeletonization, and minutiae. (a) Directional field and singular point. The core is indicated by the circle and the delta by the triangle. (b) Skeletonization of a segmented fingerprint. (c) Minutiae extracting: end ridge in red and bifurcation in green.

Segmentation or binarization: Due to the quality of sensors or the nature of finger skin, the background of fingerprints may contain some additional points on the obtained gray-scale image. It is difficult to extract minutiae point without applying binarization, which is an important step to remove noise and keep the useful ridges (Fig. 4). Segmentation by adaptive or global thresholding is the simplest approach. An approach to reliable segmentation is proposed by [6]. The most used approach is segmentation by Otsu [9]. It involves maximizing the interclass variance defined as a weighted sum of variances of the two classes (Eq. (1)); the higher the variance is, the more the image is segmented correctly.

ω_0.1 are the probabilities of the two classes separated by threshold t, and σ_0.1² are the variances of these two classes.

Skeletonization: In order to facilitate the extraction of the minutiae, the skeletonization of a segmented image is used to reduce the thickness of ridges to one pixel. Skeletonization is invariant to linear transformations, which ensure accurate estimation of minutiae. The Zhang approach [10] yields significant results, as demonstrated in [11]. Fig. 4(b) and (c) present an example of both segmentation approaches.

Fig. 4.

Segmentation: (a) original fingerprint, (b) fingerprint segmentation with Otsu, and (c) fingerprint segmentation with global thresholding.

Extraction of minutiae: Majority of fingerprints matching systems use minutiae and focus on extracting the local characteristics formed by terminations and bifurcations as shown in Fig. 3(c). In most methods, the extraction involves dividing the skeletonized image into blocks. To improve the extraction results and eliminate false extracted minutiae, approaches such as [12] consider a cross number (CN) on a neighbor of 8 pixels. The center pixel is the location of bifurcation when the crossing number is equal to or greater than 3; it presents isolated points when the crossing number is null, and it is not considered a minutiae point when the crossing number is equal to two as shown in Fig. 5.

Fig. 5.

Examples of cross number. CN=0; isolated pixel, not considered (due to noise), CN=1 ridge minutiae, CN=2 minutiae do not exist, and CN=3 bifurcation.

Singular points (SPs): Represented by core and delta, they are the most important global characteristics of a fingerprint. They also determine the global topological structure defined by Henry classes [1,4]. A singular point core is the central point of a given region, and a delta point is the center of triangular regions where three different directions meet. The SPs are indicated in the DF of Fig. 3(a).

Regarding existing works, several algorithms have been proposed in order to match the fingerprints. The main relevant algorithms are correlation-based matching and minutiae-based matching.

In this sense, we focus on the minutiae-based matching wherein we consider the minutiae triangulation-based method. In fact, the latter represents a consistent tool for handling the discrete data comparison. Conceiving a triangle from three minutiae points keeps their typological structure and improves the matching and indexing algorithms.

The Delaunay is a triangulation minutiae method that generates triangles starting from the center point of the fingerprint image by forming an arc with the closest points to cover all minutiae points. According to the authors of [13], this method provides good results concerning complexity. In addition, the Delaunay triangulation involves creating the maximum possible triangles formed by the extracted minutiae points [14,15]. The aim issue is related to the increase in the number of generated triangles. Indeed, since the set of extracted minutiae may contain false ones, for each false minutia, multiple false triangles will be generated, and the quality of results will decrease. Note, however, that other approaches like the one proposed in [14] solicited the reduction of the number of generated triangles instead of maximization. Still, this is not efficient since it can exclude useful minutiae points (see Fig. 6). Apart from the use of generated triangles, the authors of [16] opted to consider the characteristics of the obtained triangles, i.e., the lengths of arcs and nails or surfaces of triangles.

Fig. 6.

Delaunay triangulation. (a) Delaunay triangulation with all possible triplets and (b) triangulation with reduced triplets.

For our purpose, two sets of minutiae are considered: I as an input image and T as a template image. The major problem of the aforementioned approaches is the fact that they can identify two triangles— extracted from I and T—by being similar even if they are not. Indeed, the two triangles have the same characteristics, but they are not coming from the same minutiae points (i.e., triangle nodes do not have the same position in the two fingerprints images considered). The question is how to solve and improve the recognition rate.

3. Proposed Approach

In our work, we propose a new method based on Delaunay triangulation. To this end, we use the latter in a hierarchical aspect to overcome improper fingerprint identifications (see Fig. 7).

Fig. 7.

Global sight of the proposed method, hierarchical Delaunay triangulation (HDT).

First, in order to extract minutiae points, we apply a preprocessing method to each image. The results are classified into two classes of ridges and bifurcations. Three preprocessing strategies are considered: Otsu binarization [9], Zhang’s skeletonization [10,11], and cross number-based [12]. Various possible triangles will then be generated using the obtained minutiae vector.

With 1-to-N comparison, we define the similarity between the entry fingerprint image and the others figured in the database. Thus, three angles of each triangle from DT (Delaunay triangulation) are computed. Among the existing methods, the Al-Kashi theorem is chosen to define the three angles of α, β, and γ of triangle ABC from the generated DT (see Fig. 8 and Eqs. (2), (3), and (4)).

Fig. 8.

Illustration of the considered characteristics of the triangle.

We save in “Similar_DT” the obtained triangles from DT: Delaunay triangulation of the input image and DT2: Delaunay triangulation of the compared image. The issue here is that we may find some similar triangles that come from different minutiae because the comparison in this step is based only on the triangle features without considering their position on the fingerprint impression. To deal with this problem and to take into account the location of similar triangles, the next step of our method involves extracting the barycenter of each given triangle in “Similar_DT.” The extraction of barycenter is concerned with calculating the mean of vertices A_i, B_i, and C_i, for triangle ∆_i (A_i,B_i,C_i) given in Similar_DT (equation (5),(6)). We save the barycenter points in “P_center(x_center,y_center).”

A_i(x,y),B_i(x,y),C_i(x,y) are the coordinate’s vertices.

To conserve the topological structure of the matched triangles, we reapply the Delaunay Triangulation of points saved in vector “P_center” that will be presented in “DT_Similar_DT.” We generate a triangle whose nodes are the centroids of the three triangles considered. Then, we seek similar triangles of centroids. The similarity process is applied for “DT_Similar_DT” and “DT2_Similar_DT2” (barycenter triangulation for the entry and the compared fingerprints).

By ensuring the matched triangles’ location, this method guarantees improvement regarding the similarity decision as fingerprint recognition.

The probability of identification (P) of each fingerprint compared to the database images is defined as follows:

|DT|: Cardinal of triangles obtained the first time with Delaunay triangulation.

|Similar_DT|: Cardinal of the obtained similar triangles in the first comparison.

|DT_similar_DT|: Cardinal of resulting similar triangles using Delaunay triangulation of barycenter points.

|Similar_barycenter|: Cardinal of resulting similar triangles using Delaunay triangulation of barycenter points.

4. Experiments and Results

To evaluate the performance of the proposed method, we use dataset DB1_B from the FVC2004 database available at [17]. FVC2004 DB1 and DB2 contain 880 fingerprint impressions of varying quality from 110 distinct fingers (i.e., each person is represented by eight impressions). Three different scanners and the SFinGE synthetic generator were used to collect fingerprints (see Table 1). Using the proposed algorithm, we do the preprocessing steps for each finger, and then calculate the matching score with the other impressions of the same finger to get true matching scores. Afterward, we compare it with the others in the database to get imposters’ scores.

Following the FVC protocol, experiments were conducted on the database in order to evaluate the performance of our proposal. We adopted the performance measure for verification by calculating the false acceptance rate (FAR) and false rejection rate (FRR) [18,19] for threshold t ranging from 0 to 1 as:

Fig. 9 presents some results of our HDT method. In this figure, we compare an input fingerprint image with a stored one. Fig. 9(a) presents original images, Fig. 9(b) gives similar triangles, and Fig. 9(c) traces Similar_DT. Fig. 9(d) defines the barycenter of the selected triangles, Fig. 9(e) determines the different triangles of the barycenter, and Fig. 9(f) shows Similar_barycenter. We then compare the proposed approach with simple Delaunay matching (SDM) that applies the matching of triangles obtained by Delaunay triangulation at the first phase (triangulation of the extracted minutiae points).

Fig. 9.

Example of the process results described in the stages.

Fig. 10 and Table 2 show that our method is more accurate compared to methods that consider simple Delaunay triangulation matching. Using the proposed approach, we obtain high similarity only for a request image (I10) taken from the same test group. For the rest of non-similar fingerprints, we get the value of 0% as similarity rate, which explains that they are not similar and will be dropped from the candidates.

On the other hand, when SDM is used, many false detections appeared (rates higher than 0%). Furthermore, this last approach gives two relevant images with a similarity rate of 100%, which causes false acceptance in the verification and identification steps.

The most interesting results are summarized and shown in Table 2.

Fig. 10.

Comparison of two fingerprint identification approaches: matching using a simple Delaunay and our proposed method in DB1_B.

Fig. 11.

ROC curves of the proposed approach and compared method (SDM).

The following Receiver Operating Characteristic (ROC) curve in Fig. 11 represents the performances of the proposed method HDT (noted MP) compared with the SDM by calculating the measures FAR and FRR (False Rejection Rate). Experiments are performed on DB1_1 from FVC2004, which contains 80 fingerprints. As shown below, our proposed method gives better results in terms of identification certainty.

5. Conclusion

In this paper, the different steps of identifying and retrieving fingerprints have been described. In fact, a novel approach to fingerprint retrieving, based on minutiae triangulation, is proposed. Specifically, we suggest using the Delaunay triangulation in a hierarchical manner as a matching method that is based on the generated characteristics of triangles.

First, the concept of the barycenter has been introduced. This latter guarantees the same geometric location of the matched triangles and the detected similar minutiae as well. Being sensitive to any homothetic transformation that does not keep the same location of the triangle in a fingerprint, we have introduced the centroid of the triangles as an alternative to ensure that the matched triangles are located in the compared fingerprints. The experimental results showed significant improvement compared to simple triangulation matching.

As future work, we will study the efficiency of the combination of fingerprints features and barycenter notion in both hierarchical and loop manners until the relevant similarity is obtained.