Keywords

1 Introduction

Biometric technologies are already widely disseminated in numerous large-scale nationwide projects [1, 2]. Fingerprint indexing and matching is among the most widely used biometric technologies, it is playing a major role in automated person identification systems deployed to enhance security all over the world. Even without the advent of environmental noise, two same fingerprint impressions are not guaranteed to be identical due to variability in displacement, rotation, scanned regions, and nonlinear distortion. Displacement, rotation, and disjoint-detected regions are obviously due to the differences in the physical placement of a finger on a scanner.

In the literature, various methods of fingerprint matching exist, such as correlation-based matching, texture descriptor, minutiae points-based matching [3, 4]. Among them, minutiae-based algorithms are the most widely used [5, 6]. Most methods of matching consist of relating two minutiae points. This decreases the performance of systems when one has transformations, then the minutiae in rotation will not aligned and the high-level minutiae can be neglected. Furthermore, the complexity of matching increases more and more considering the number of extracted minutiae, which increases the computing time and reduces the result quality.

In this article, we present a new method based on the extraction of singular point, which represents the central point of the image, using the directional field to locate it, then we will focus on a block of 100 * 100 pixels around the extracted singular point. The selected block is an interval that contains the high-quality minutiae which the probability of losing them still minimum for any type of transformation. In a second step, we will apply the Delaunay triangulation of minutiae points. We apply a process matching first by extracting similar triangles, and second extracting the barycenters of similar triangles extracted in the first, and then reapply the Delaunay triangulation and the extraction of similar triangles. The aim of this method is to ensure the right location of the matched triangles, which means a good matched minutiae points. The strengths of this system are as follows:

  • The extraction of the singular point involves the reduction of the minutiae aligned at matching, which implies reducing time and complexity.

  • Location of the singular point at the center makes it robust to the loss in case of contour missing. This increases the recognition performance.

  • This method is robust to zoom, because it is interested only in the corners of triangles when searching similarity of triangles.

  • The change in orientation of the incoming image does not affect the identification results. This approves the performance of using triangulation.

  • Considering the barycenters of the similar triangles, ensures that the relevant triangles found are located in the same places in the both compared impression.

The rest of this paper is organized as follows: Sect. 2 analyzes the topological structure of fingerprint and preprocessing steps. Section 3 presents the extraction of the singular point. Section 4 details the proposed hierarchy triangulation Delaunay for matching. Section 5 presents experience and results. Conclusions are drawn in Sect. 6 (Fig. 1).

Fig. 1
figure 1

a Arch, b tented arch, c left loop, d right loop, e whorl, and f whorl (twin loop)

Full size image

2 Fingerprinting

2.1 Fingerprint Characteristics

Generally, fingerprint structure is classified into two categories: global characteristics and local ones. The local characteristics called minutiae (see Fig. 2), they represent the form of the ridges intersection, in literature, we find ten forms, but the indexation methods use only two important minutiae’s form, defined by end ridge and bifurcation. Because all others shapes are represented as a multiplication of bifurcation or end ridges. These two patterns create the uniqueness of the individual; and their positions in the fingerprint considered as a determining factor of differentiation.

Fig. 2
figure 2

Different minutiae forms

Full size image

The global characteristics are the singular points (core and delta), obtained at the points when ridges change their orientation which influence largely the directional field. They determine the topological structure and type of fingerprint, allowing a classification of fingerprints into six main classes; defined by Henry [4, 7] (see Fig. 1).

2.2 Fingerprint Pretreatment

Typically, the recognition studies are based on the multiple use features found after applying an extraction process. We can classify the fingerprints processing in two major classes (see Fig. 3), preprocessing which is a common step for all approaches. Then the indexing, which includes several process, according to the use of fingerprint extracted characteristics. Finally, we use the indexed database for an identification or verification applications.

Fig. 3
figure 3

Fingerprint processing steps

Full size image

Before applying a fingerprint indexing method, the preprocessing step of the fingerprint image is important. The main procedure is to clear the image as to make operations easier and enhance performance.

Due to the nature of skin and the quality of sensor, the scanned fingerprint is not assured with a good quality, it contain always a missing pixels, regions with a bad contrast, or a noise. This is why all the recognition and identification approaches starts with a pretreatment steps which is very useful for keeping a higher accuracy of recognition or identification method. We can find two methods of preprocessing, some approaches like the ones [4, 8] are based on the estimation of the ridges orientation noted DF (directional field), followed by binarization and finally skeletonization. Other approaches use only by binarization of the image followed by skeletoization. Both approaches end by filtering the image from noise, and apply the extraction of minutiae.

  • Binarization: It is important to derive the shape of the ridges and remove the background pixels. Because the true information that could be extracted from a scanned fingerprint must be simply binary; ridges and valleys. The simplest approach is segmentation by adaptive or global thresholding. However, the problem in performing binarization is that not all the fingerprint images have the same contrast characteristics, so a single intensity threshold using a global thresholding cannot applied. Some approaches [9] uses the fact that there is a significant difference in the variation amplitudes of the gray levels along and through the flow ridges. The widely used method is the segmentation by Otsu [10], it consists to maximize the variance interclass, and the more this variance is big, the more the threshold is going to segment the image correctly. This method has showing good results. In figure (Fig. 4), we present the difference between both methods of segmentation:

    Fig. 4
    figure 4

    a Original fingerprint. b Segmentation with Otsu. c Segmentation with global mean

    Full size image

  • Skeletonization: In order to facilitate the extraction of the minutiae, this method reduces the thickness of the ridges in a line of one pixel. It does not modify the location and orientation of minutiae compared to the original fingerprint which ensures accurate estimation of minutiae. The approach of Zhang proved important results [11, 12].

  • Minutiae extraction: Bifurcations and end of ridges are the most significant features in the fingerprint impression. In most approaches, extraction is made by dividing the skeletonized fingerprint into blocks. Alain [5] consider that the bifurcation is identified by a three neighboring pixels, while a termination is pixel with only one neighbor, and bifurcation is a pixel with the tree neighbors. To improve the certainty of minutiae extracted, approaches such as Arcelli [13], have worked by the Cross Number calculated on a blocks of eight pixels as: CN = 0: Isolated pixel, not considered; CN = 1: ridge minutiae; CN = 2: minutiae does not exist. However, the minutiae extraction is not genuine due to image processing and the noise in the fingerprint image. While the error of missing or added minutiae always exist.

3 Singular Point Extraction

The singular points, cores, and deltas are the most important global characteristics of a fingerprint, they also determine the topological structure. The singular point area defined as a region where the ridge curvature is higher than normal and where the direction of the ridge changes rapidly. A core point defined as the central point of an ogive region, and a delta point is the center of triangular regions where three different direction meet.

In the literature, different approaches were based on the extraction of a core point [14, 15], as a useful point for obtaining the directional registration, classifying fingerprint, matching, and recognition. Most of existing methods are working on directivity ridge estimation to use the directional field images. A number of methods proposed to estimate the fingerprint orientation field [5, 9, 16]. For this, the gradient-based method was adopted by many approaches [15], it has been shown as a very important result for detecting the both singulars points, and robust to very poor image quality and noisy impression. Poincare index is another proposed method and used by many approaches [17, 18] it is considered as very sensitive to noise and the variations of the grayscale level of the input image. However, in this work, we focus our interest for a singular core point location in fact to detect the center of a fingerprint impression as an important region. The performance of core point here is that:

  1. (i)

    The location of core point at the center makes him a high-level singular point.

  2. (ii)

    Whatever the finger position on the sensor, we will get the center of the impression in the required image, in contrary to the delta that can be missed in a bad position or in the case of missing parts.

In addition to its applicability by many researchers in the area of fingerprints, estimation of the orientation ridges using a directional filed it used in this work, then we will apply it to our proposed indexation method. Using a gradient approach, we compute the image derivative in the x and y directions to get the gradient vector defined as

$$\left( {\begin{array}{*{20}c} {G_{x} I\left( {x,y} \right)} \\ {G_{y} I\left( {x,y} \right)} \\ \end{array} } \right) = \left[ {\begin{array}{*{20}c} {\frac{{\partial I\left( {x,y} \right)}}{\partial x}} \\ {\frac{{\partial I\left( {x,y} \right)}}{\partial y}} \\ \end{array} } \right]$$
(1)

Orientation estimated by using least square contour alignment method using a window W (3, 3) (Eqs. 2 and 3). The advantage is that this method gives continuous values [14]. With calculating gradient at pixel level, the orientation of ridge stays orthogonal to average phase angle of changes pixels value indicated by gradients. Then orientation of an image block is determined by averaging the square gradients \(\left( {\begin{array}{*{20}c} {G_{s,x} I\left( {x,y} \right)} \\ {G_{s,y} I\left( {x,y} \right)} \\ \end{array} } \right)\) to eliminate the orientation ambiguity. Figure 5 presents an overview of extracting singular point steps.

$$\left( {\begin{array}{*{20}c} {G_{s,x} I\left( {x,y} \right)} \\ {G_{s,y} I\left( {x,y} \right)} \\ \end{array} } \right) = \left[ {\begin{array}{*{20}c} {\mathop \sum \nolimits_{W} G_{x}^{2} - \mathop \sum \nolimits_{W} G_{y}^{2} } \\ {2\mathop \sum \nolimits_{W} G_{x} G_{y} } \\ \end{array} } \right] = \left[ {\begin{array}{*{20}c} {G_{xx} - G_{yy} } \\ {2G_{xy} } \\ \end{array} } \right]$$
(2)
Fig. 5
figure 5

Overview of singular point extracting

Full size image

Then the gradient orientation \(\varvec{\theta}\) estimated as follows:

$$\theta = \frac{1}{2}\nabla \left( {G_{xx} - G_{yy} ,2G_{xy} } \right)$$
(3)

With \(\nabla \left( {x,y} \right)\) defined as (Eq. 4):

$$\nabla \left( {x,y} \right) = \left\{ {\begin{array}{*{20}l} {\tan^{ - 1} (x/y)\,x > 0} \hfill \\ {\tan^{ - 1} (x/y) + \pi \,{\text{for}}\;x < 0\;{\text{and}}\;y \ge 0} \hfill \\ {\tan^{ - 1} (x/y) - \pi x < 0\;{\text{and}}\;y \ge 0} \hfill \\ \end{array} } \right.$$
(4)

As an important region, pixels around the singular point present a high-level point on a fingerprint impression, for this we will focus to extract minutiae around the singular point extracted. Many approach approved that the high number of minutiae extracted can decrease the result matching especially when use minutiae features, because it can generate a bad point and then a false feature. We propose in this work to considering a bloc of (100 * 100) pixels around the singular point extracted, this reduce number of minutiae extracted and help to minimize time and complexity matching (Fig. 6).

Fig. 6
figure 6

a Original fingerprint with the extracted singular point. b The selection bloc of (100 * 100) pixels around singular point

Full size image

4 Hierarchical Delaunay Triangulation

Delaunay triangulation is a matching-based method produces triangles starting from the center point of the fingerprint image, forming an arc with the closest points to cover all the minutiae points. This method provides good results in terms of complexity [7, 19]. Delaunay triangulation [6, 10] consists in generating the largest possible number of triangles formed by the extracted minutiae points.

The main problem is that the number of the generated triangles may be a weakness for these kinds of algorithms. Indeed, as the set of extracted minutiae may contain false ones, so for each false minutia, multiple false triangles will be generated and the result quality will decrease. Thus, some approaches [10, 11] were proposed to reduce the number of the generated triangles, but they were not efficient as it can eliminate useful points (Fig. 7).

Fig. 7
figure 7

a Delaunay triangulation, b triangulation with reducing triplets

Full size image

Considering two sets of minutiae I (input image) and T (template image). The problem of the based triangles methods that it is possible to find two similar triangles from T and I, but in reality they are not formed by the correspondent minutiae; (i.e., triangle nodes do not have the same position in the two considered impression). Therefore, the challenge is to find similar triangles with the same topological distribution in two similar fingerprints.

In the first of our approach, we apply the preprocessing steps to each fingerprint in order to extract minutiae that will be classified into a vector of ridges and bifurcations. For this, we use the Otsu binarization method for obtaining the binary image. Zhang’s skeletonization approach was used for thinning the binary fingerprint. Then, we apply the extracting minutiae process, composed by bifurcation and end of ridges, the Cross Number-based method was applied on a neighborhood of 8 pixels, as mentioned before. Figure 8, show the different steps applied on a extracted singular point region considered as a block of 100 * 100, Next, based on the obtained minutiae vector (ridge and bifurcation), the different possible triangles will be formed applying a Delaunay triangulation (DT) function so as to obtain all possible triplets of the extracted points.

Fig. 8
figure 8

Preprocessing steps: a the input block, b binary image, c thinned image. d Present the extracted minutiae, end ridges presented by circles

Full size image

As a comparison and matching method based on triplets minutiae, we define the similarity between an input fingerprint image and the others in a database. In the work, we propose to calculate the three angles of each triangle in the obtained Delaunay triangulation (DT) for the both compared fingerprints (DT), for an input image, and DT2 for database image. Among the existing methods, we use the Akashi theorem (Eqs. 5, 6, and 7) to define the three angles α, β, and γ of each triangle ABC in DT.

$$\alpha = \arccos \left( {\frac{{b^{2} + c^{2} - a^{2} }}{2bc}} \right)$$
(5)
$$\beta = \arccos \left( {\frac{{a^{2} + c^{2} - b^{2} }}{2ac}} \right)$$
(6)
$$\gamma = \arccos \left( {\frac{{a^{2} + b^{2} - c^{2} }}{2ab}} \right)$$
(7)

For each triangle of DT identified by its three angles (α, β, and γ) we look all the triangles in the second fingerprint image; defined in DT2; that have the same angles. This similarity method gives always the best results, cause even if the fingerprint changes orientation, quality, or zoom, since the triangles do not change angles in these cases. The similar triangles will be saved in Similar_DT by the following algorithm:

For each triangle \(\Delta_{\text{i}} \left( {{\text{A}}_{\text{i}} ,{\text{B}}_{\text{i}} ,{\text{C}}_{\text{i}} } \right)\) from DT

For each triangle \(\Delta_{\text{j}} \left( {{\text{A}}_{\text{j}} ,{\text{B}}_{\text{j}} ,{\text{C}}_{\text{j}} } \right)\) from DT2

If is member \(\left( {\left( {{\text{A}}_{\text{i}} ,{\text{B}}_{\text{i}} ,{\text{C}}_{\text{i}} } \right),\left( {{\text{A}}_{\text{j}} ,{\text{B}}_{\text{j}} ,{\text{C}}_{\text{j}} } \right)} \right) = \left( {1,1,1} \right) ;\)

Similar_DT i   =  \(= \Delta_{\text{i}} \left( {{\text{A}}_{\text{i}} ,{\text{B}}_{\text{i}} ,{\text{C}}_{\text{i}} } \right)\) ;

End;

End;

End;

Similar_DT   =   unique (Similar_DT, rows);

The problem in this case that we may find similar triangles that are not formed by the same minutiae. Indeed, even if it exists a homothetic transformation between two triangles this does not guarantee that they are formed by the same minutiae points, and not effectively similar because they can be in two different positions in the compared fingerprints. To solve this problem and to take into consideration the location of similar triangles with a similar minutiae, the next step of our method consist to extract the barycenter [20], of each triangle given in Similar_DT (Fig. 9).

Fig. 9
figure 9

Delaunay triangulation of minutiae extracted on the chosen block [100 * 100]

Full size image
Fig. 10
figure 10

Singular point detecting in original fingerprints (a database image) and (b input image)

Full size image

Barycenter is calculated by using the mean of \({\text{A}}_{\text{i}}\), \({\text{B}}_{\text{i}}\) and \({\text{C}}_{\text{i}}\), nodes of each triangle \(\Delta_{\text{i}} \left( {{\text{A}}_{\text{i}} ,{\text{B}}_{\text{i}} ,{\text{C}}_{\text{i}} } \right)\) given in the extracted similar triangles (Similar_DT). The result saved in P_center (x_center, y_center). To keep the topological structure of minutiae, we apply the Delaunay Triangulation (DT_Similar_DT) of points saved in the vector P_center, and then we measure the similarity between DT_Similar_DT of the entry fingerprint and DT2_Similar_DT2 of the compared fingerprint. This method will ensure improvement the similarity decision of triangles and so the identification of fingerprints. Finally, we define the probability identification (P) of each fingerprint compared to the database images, as follows in Eq. 8:

$$P = \frac{{\left| {{\text{Similar}}\_{\text{barycenter}}} \right|}}{{\left| {{\text{DT}}\_{\text{similar}}\_{\text{DT}}} \right|}}$$
(8)

With:

|DT_similar_DT|: number of similar triangles obtained using Delaunay triangulation of barycenter points.

|Similar_barycenter|: number of similar triangles obtained using Delaunay triangulation of barycenter points.

5 Results and Discussion

To evaluate the performance of the proposed method, we use the benchmarking dataset Db1_a from FVC2002 database available at [21]. FVC2002 DB1 and DB2 contain 880 fingerprint impressions, of various quality, from 110 distinct fingers (i.e., each person is represented by 8 impressions). Three different scanners and the SFinGE synthetic generator were used to collect fingerprints.

In the first, we generate the file of blocs (100 * 100) pixels as shown in Fig. 11, obtained after extraction of the singular point in Fig. 10. Given two different fingerprint I1 and I2, Fig. 12 shows the Delaunay triangle (i.e., DT and DT2) extracted in the both images, the similar triangles founded (i.e., similar_DT and similar_DT2) as shown in Fig. 13. In Fig. 14, we present the generated barycenter and then the extracted similar triangles formed by barycenter (i.e., DT_similar_DT and DT2_similar_DT2) as mentioned in Figs. 15 and 16. Finally, we calculate the probability P of matching for an input image and others in the database.

Fig. 11
figure 11

Block of (100 * 100) pixels around singular point

Full size image
Fig. 12
figure 12

Triangulation delaunay of the both extracted blocks (i.e., DT and DT2)

Full size image
Fig. 13
figure 13

Similar triangles detected (i.e., similar_DT and similar_DT2)

Full size image
Fig. 14
figure 14

Generated barycenter in the extracted similar triangles (i.e., similar_DT and similar_DT2)

Full size image
Fig. 15
figure 15

Extracted similar triangles in DT (red) and DT_similar_DT (green)

Full size image
Fig. 16
figure 16

Extracted similar triangles in DT (green) and DT_similar_DT (red)

Full size image

Comparing a query image (I10) and others selected fingerprint from the database, Table 1 shows that the new approach is more accurate comparing with the other methods; matching using a simple Delaunay triangulation applied on the entry minutiae (SDT), matching with simple Delaunay triangulation around the singular point extracted (SPSDT). We obtain a similarity of 100% only for the query image (I10) by using our proposed method, and for all the others nonsimilar fingerprints we obtain 0% as a similarity rate. In the opposite, in the other methods, there are many false detection rates (rates not equal to 0%) that are determined. They give other relevant images with similarity rates 100%, which decrease the efficiency. The average processing time for each fingerprint is around 0.098 s.

Table 1 Matching results
Full size table

6 Conclusion

In this paper, we have presented a new fingerprint matching approach based on the extraction of the singular point, and a hierarchical Delaunay triangulation based on triangles features. As an important point, singular point is considered as a high-quality fingerprint pattern with a low probability of loss in case of the missing part on a fingerprint caption. The extraction of singular point helps to approve a high matching performance when considering minutiae on his neighbor. A Delaunay matching method was applied on the minutiae extracted around the singular point. To ensure the best correspondence of similar triangles, we calculate hierarchically similarity of triangles formed by barycenter point of the extracted triangles in the first time. This is to ensure the topological distribution of aligned minutiae. The main experiences approved the efficiency and advantages of proposed method.