** Fingerprint Identification Based on Hierarchical Triangulation **

Meryam Elmouhtadi* , Sanaa El Fkihi** and Driss Aboutajdine*

## Article Information

## Abstract

**Abstract:** Fingerprint-based biometric identification is one of the most interesting automatic systems for identifying individuals. Owing to the poor sensing environment and poor quality of skin, biometrics remains a challenging problem. The main contribution of this paper is to propose a new approach to recognizing a person’s fingerprint using the fingerprint’s local characteristics. The proposed approach introduces the barycenter notion applied to triangles formed by the Delaunay triangulation once the extraction of minutiae is achieved. This ensures the exact location of similar triangles generated by the Delaunay triangulation in the recognition process. The results of an experiment conducted on a challenging public database (i.e., FVC2004) show significant improvement with regard to fingerprint identification compared to simple Delaunay triangulation, and the obtained results are very encouraging.

**Keywords:** Biometric , Fingerprint Identification , Delaunay Triangulation , Fingerprint Matching , Minutiae Extraction

## **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.

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).

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.

##### (1)

[TeX:] $$\sigma _ { \omega } ^ { 2 } ( \mathrm { t } ) = \omega _ { 0 } ( \mathrm { t } ) \sigma _ { 0 } ^ { 2 } ( \mathrm { t } ) + \omega _ { 1 } ( \mathrm { t } ) \sigma _ { 1 } ^ { 2 } ( \mathrm { t } )$$ ω_{0.1} are the probabilities of the two classes separated by threshold t, and σ_{0.1}^{2} 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.

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.

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).

2.2 Delaunay Triangulation MatchingRegarding 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.

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).

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)).

##### (2)

[TeX:] $$\alpha = \arccos \left( \frac { b ^ { 2 } + c ^ { 2 } - a ^ { 2 } } { 2 b c } \right)$$

##### (3)

[TeX:] $$\beta = \arccos \left( \frac { \mathrm { a } ^ { 2 } + c ^ { 2 } - \mathrm { b } ^ { 2 } } { 2 \mathrm { ac } } \right)$$

##### (4)

[TeX:] $$\gamma = \arccos \left( \frac { a ^ { 2 } + b ^ { 2 } - c ^ { 2 } } { 2 a b } \right)$$ 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.

##### (5)

[TeX:] $$\mathrm { x } _ { - } \text { center } = \frac { \mathrm { A } _ { \mathrm { ix } } + \mathrm { B } _ { \mathrm { ix } } + \mathrm { C } _ { \mathrm { ix } } } { 3 }$$

##### (6)

[TeX:] $$\mathrm { y } _ { - } \text { center } = \frac { \mathrm { A } _ { \mathrm { iy } } + \mathrm { B } _ { \mathrm { iy } } + \mathrm { C } _ { \mathrm { iy } } } { 3 }$$ 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:

##### (7)

[TeX:] $$\mathrm { P } _ { 1 } = \frac { | \text { Similar } \mathrm { DT } | } { | \mathrm { DT } | }$$

##### (8)

[TeX:] $$\mathrm { P } _ { 2 } = \frac { | \text { Similar_barycenter| } } { | \mathrm { DT } \text { _similar_ } \mathrm { DTl } }$$

|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**

4.1 Data Sets and Experimental Process 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.

4.2 Results and DiscussionFollowing 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:

##### (10)

[TeX:] $$FAR = \frac { \text { number of accepted imposters } } { \text { total number of imposters } }$$

##### (11)

[TeX:] $$FAR = \frac { \text { number of rejected genuines } } { \text { total number of genuines } }$$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. 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.

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.

## Biography

##### Meryam Elmouhtadi

https://orcid.org/0000-0002-5089-0860She was born in Rabat, Morocco, in 1988. She received the Master degree in 2012 in Computer Science and Telecommunication from the Faculty of Science of Rabat, Morocco. She is currently a Ph.D. candidate in the Department of Computer Science Telecommunication at Faculty of Science, University Mohammed V, Rabat, Morocco. Her research interests include multimedia content, image processing, Fingerprint indexation and retrieval.

## Biography

##### Sanaa El Fkihi

https://orcid.org/0000-0002-0471-046XShe received her Ph.D. degree in Computer Sciences and Telecommunications engineering from University of Mohammed V Agdal, Rabat, Morocco, jointly with University of Sciences and Technologies of LILLE-France, in 2008. Currently, she is an associate professor at ENSIAS (Ecole Nationale Supérieure d’Informatique et d’Analyses de Systèmes)–University Mohammed V de Rabat, Rabat, Morocco. Her current research interests include graph theory, image processing, big data and wireless sensor network.

## Biography

##### Driss Aboutajdine

https://orcid.org/0000-0002-3677-5575He received the Doctorat de 3’ Cycle and the Doctorat d’état-es-Sciences degrees in signal processing from the Mohammed V-Agdal University, Rabat, Morocco, in 1980and 1985, respectively. He joined Mohammed V-Agdal University, Rabat, Morocco in 1978. He started as an assistant professor, then as an associate professor in 1985, and full Professor since 1990, where he is teaching, Signal/image Processing and Communications. Over 30 years, he developed research activities covering various topics of signal and image processing, wireless communication and pattern recognition, which allow him to publish over 300 journal papers and conference communications. He is presently by far the most highly published author in the fields of "Engineering and Computer Science" in Maghreb countries and the second in Morocco inclusive all fields as assessed by Scopus database.

## References

- 1 A. Jain, S. Pankanti, in Handbook for Image and Video Processing. San Diego, CA: Academic Press, pp. 821-836, 2000.custom:[[[-]]]
- 2 D. A. Kumar, T. U. S. Begum, "A comparative study on fingerprint matching algorithms for EVM,"
*Journal of Computer Sciences and Applications, 2013*, vol. 1, no. 4, pp. 55-60. doi:[[[10.12691/jcsa-1-4-1]]] - 3 J. Feng, J. Zhou, "A performance evaluation of fingerprint minutia descriptors," in
*Proceedings of 2011 International Conference on Hand-Based Biometrics*, Hong Kong, China, 2011;pp. 1-6. doi:[[[10.1109/ichb.2011.6094350]]] - 4 Federal Bureau of Investigation, The Science of Fingerprints: Classification and Uses. WashingtonDC: 2006. custom:[[[-]]]
- 5 M. Liu, X. Jiang, A. C. Kot, "Efficient fingerprint search based on database clustering,"
*Pattern Recognition, 2007*, vol. 40, no. 6, pp. 1793-1803. doi:[[[10.1016/j.patcog.2006.11.007]]] - 6 N. K. Ratha, K. Karu, S. Chen, A. K. Jain, "A real-time matching system for large fingerprint databases,"
*IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996*, vol. 18, no. 8, pp. 799-813. doi:[[[10.1109/34.531800]]] - 7 R. Kumar, P. Chandra, M. Hanmandlu, "A robust fingerprint matching system using orientation features,"
*Journal of Information Processing Systems, 2016*, vol. 12, no. 1, pp. 83-99. doi:[[[10.3745/JIPS.02.0020]]] - 8 J. de Boer, A. M. Bazen, S. H. Gerez, "Indexing fingerprint databases based on multiple features," in
*Proceedings of the 12th Annual Workshop on Circuits*, Systems and Signal Processing, Veldhoven, The Netherlands, 2001;pp. 300-306. custom:[[[https://research.utwente.nl/en/publications/indexing-fingerprint-databases-based-on-multiple-features]]] - 9 M. Sezgin, B. Sankur, "Survey over image thresholding techniques and quantitative performance evaluation,"
*Journal of Electronic Imaging, 2004*, vol. 13, no. 1, pp. 146-166. doi:[[[10.1117/1.1631315]]] - 10 J. R. Parker, Algorithms for Image Processing and Computer Vision. Hoboken, NJ: John Wiley Sons, 2010.custom:[[[-]]]
- 11 C. L. Tisse, L. Martin, L. Torres, M. Robert, "Système automatique de reconnaissance d'empreintes digitales. Sécurisation de l'authentification sur carte à puce,"
*in 18° Colloque sur le traitement du signal et des images. ParisFrance: Groupe d’Etudes du Traitement du Signal et des Images, 2001,*, pp. 44-47. custom:[[[http://documents.irevues.inist.fr/handle/2042/13225]]] - 12 A. Munoz-Briseno, A. Gago-Alonso, J. HernaNdez-Palancar, "Fingerprint indexing with bad quality areas,"
*Expert Systems with Applications, 2013*, vol. 40, no. 5, pp. 1839-1846. doi:[[[10.1016/j.eswa.2012.09.018]]] - 13 N. Liu, Y. Yin, H. Zhang, "A fingerprint matching algorithm based on Delaunay triangulation net," in
*The Proceedings of the 5th International Conference on Computer and Information Technology*, Shanghai, China, 2005;pp. 591-595. doi:[[[10.1109/cit.2005.9]]] - 14 G. Bebis, T. Deaconu, M. Georgiopoulos, "Fingerprint identification using Delaunay triangulation," in
*Proceedings of the International Conference on Information Intelligence and Systems*, Bethesda, MD, 1999;pp. 452-459. doi:[[[10.1109/iciis.1999.810315]]] - 15 M. A. Medina-Prrez, M. Garcia-Borroto, A. E. Gutierrez-Rodriguez, L. Altamirano-Robles, "Improving fingerprint verification using minutiae triplets,"
*Sensors, 2012*, vol. 12, no. 3, pp. 3418-3437. doi:[[[10.3390/s120303418]]] - 16 X. Liang, T. Asano, A. Bishnu, "Distorted fingerprint indexing using minutia detail and Delaunay triangle," in
*Proceedings of the 3rd International Symposium on Voronoi Diagrams Science and Engineering*, Banff, Canada, 2006;pp. 217-223. doi:[[[10.1109/isvd.2006.42]]] - 17 D. Maio, D. Maltoni, R. Cappelli, J. L. Wayman, A. K. Jain, "FVC2000: fingerprint verification competition,"
*IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002*, vol. 24, no. 3, pp. 402-412. doi:[[[10.1109/34.990140]]] - 18 J. Bhatnagar, A. Kumar, "On estimating performance indices for biometric identification,"
*Pattern Recognition, 2009*, vol. 42, no. 9, pp. 1803-1815. doi:[[[10.1016/j.patcog.2008.10.004]]] - 19 D. Maio, D. Maltoni, R. Cappelli, J. Wayman, A. Jain, "FVC2004: third fingerprint verification competition,"
*in Biometric Authentication. Heidelberg: Springer2004,*, pp. 31-35. doi:[[[10.1007/978-3-540-25948-0_1]]]