RU2413297C2 - Method of creating and verifying fingerprint biometric code - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: method of creating and verifying fingerprint biometric code involves binarisation of an electronic image of the papillary pattern (PP) via filtration during processing, joining false abruptions on the image, removing false line merging and levelling pixels of the electronic image relative a pre-set pixel intensity threshold, after which the frame of the binary electronic image is formed by thinning its lines to given thickness. The centres of mass of minutia are calculated after determining coordinates of the minutia on the PP frame. PP cores are used to determine arguments of the function of the biometric code. The cores are minutia closest with the shortest distance to their centre of mass. A tree to the rest of the minutia is constructed from each core and the lengths of the branches of each tree are calculated and said lengths are ranked. Arguments of clustering of minutia are calculated, from which the PP biometric code is created and the threshold value of its similarity with a standard biometric code is calculated.

EFFECT: high reliability of a PP code, fewer operations performed when comparing codes.

11 cl, 9 dwg

Description

The invention relates to the field of recognition, presentation and reproduction of data, namely, methods for reading and recognizing printed or written characters or pattern recognition, in particular fingerprints and the formation of their biometric codes.

A known method of generating and verifying a biometric code (application US 2007/0036401 A1 "System for recognition fingerprint image, method and program for the same", February 15, 2007), which involves converting a papillary pattern of a fingerprint into an electronic form, processing its electronic image, determination of the arguments of the function of the biometric code of the papillary pattern - the coordinates of the minutes, which are compared with a pre-formed set of coordinates of the minutes of the reference fingerprint.

The disadvantage of this method is that the biometric code is generated in the form of a set of min coordinates in a pure form, and therefore, a large number of computational operations must be performed at the stage of comparing biometric codes. In addition, this method is unstable to uniform compression / stretching of the image of the print.

A known method of generating a biometric code (application US 2004/0252868 A1 "Method and device for matching fingerprints", December 16, 2004), which includes converting a papillary pattern of a fingerprint into an electronic form, processing its electronic image, determining the arguments of the biometric code of a papillary pattern - square areas of the electronic image and its subsequent verification.

The disadvantage of this method is that the biometric code is formed in the form of a set of square image areas, and therefore, a large number of computational operations must be performed at the stage of comparing the biometric codes. In addition, this method is unstable to rotate the image of the print.

The closest in technical essence is the method of generating a biometric code according to the international application WO 2008/030166 A1 "A method, an apparatus, and a computer program product within fingerprint matching". The prototype method consists in converting the papillary pattern of the fingerprint into electronic form, processing its electronic image, determining the coordinates of the minutes of the papillary pattern, storing them, determining the function arguments of the biometric code of the papillary pattern, which form its biometric code.

Compared with analogues, the prototype method provides resistance to uniform compression / stretching of the image and the rotation of the print.

However, the closest analogue has a relatively low reliability of the code, due to the fact that it does not take into account the increase in the probability of occurrence of false minutes when the fingerprint is removed from the center of the electronic image. Low reliability is also associated with the need to perform a large number of operations at the stage of comparing biometric codes and the lack of redundancy.

The purpose of the claimed technical solution is to develop a method for generating and verifying a biometric fingerprint code, which provides higher code reliability, reducing the number of operations performed at the stage of code comparison, generating a code taking into account the fact that the probability of false minutes increases with distance from the center of the electronic image of the fingerprint .

. Для определения аргументов функции биометрического кода выделяют 2≤K≤N сердцевин папиллярного узора, для чего для n-й минуции вычисляют ее удаление S_n от центра масс С, а в качестве К сердцевин принимают К минуций с наименьшими значениями их удалений S от центра масс С. Затем от каждой k-й сердцевины, где k=1, 2,…, K, строят деревья к остальным J=N-1 минуциям, вычисляют длины ребер

каждого k-го дерева, где j=1, 2,…, J, и ранжируют их, рассчитывают аргументы кучности минуций с сердцевинами путем вычисления соотношений длин ребер

каждой k-й сердцевины и углов

между j-м и r-м ребром, а биометрический код папиллярного узора формируют в виде

, причем значение r и r' выбирают равным j+1. Для верификации биометрического кода сравнивают данный биометрический код с предварительно сформированным эталонным биометрическим кодом путем вычисления степени их схожести W и сравнения с предварительно заданным значением порога схожести биометрических кодов W_порог. Предварительно заданный порог схожести деревьев W_порог выбирают в интервале 1÷К, а значение степени схожести W рассчитывают как количество попарно равных деревьев из двух биометрических кодов, причем два дерева считают равными, если количество попарно равных их элементов превышает предварительно заданный порог схожести деревьев U_порог. Предварительно заданный порог схожести деревьев U_порог выбирают в интервале 1÷J.This goal is achieved by the fact that in the known method of generating and verifying a biometric fingerprint code containing N minutes, which consists in converting the papillary pattern of the fingerprint into electronic form, processing its electronic image, determining the minutes coordinates of the papillary pattern, storing them, determining arguments the functions of the biometric code of the papillary pattern, according to which its biometric code is formed, binarize it when processing the electronic image of the papillary pattern (PU). Binarization of the image of a PU consists in filtering it, splicing the false gaps on it, removing false line merges and aligning the pixels of the electronic image with respect to a predetermined intensity threshold And _pore pixels, which is selected within 60 ÷ 100, and pixels with an intensity below a predetermined threshold And _{pores are} converted to black, and pixels with an intensity above a predetermined threshold And _{pores are} converted to white. Then form the skeleton of a binary electronic image by thinning its lines to a predetermined thickness Δ equal to one pixel. After determining the coordinates x _n , y _n N minutes, where n = 1, 2, ..., N, on the skeleton of the papillary pattern, the center of mass C is calculated by the formula

. To determine the arguments of the biometric code function, 2≤K≤N cores of the papillary pattern are distinguished, for which for the n-th minute its distance S _n from the center of mass C is calculated, and K minutes are taken as K cores with the smallest values of their distances S from the center of mass C. Then, from each k-th core, where k = 1, 2, ..., K, trees are built for the remaining J = N-1 minutes, the lengths of the ribs are calculated

of each k-th tree, where j = 1, 2, ..., J, and rank them, calculate the arguments of accuracy of minutes with cores by calculating the ratio of the lengths of the edges

every kth core and corners

between the jth and rth edges, and the biometric code of the papillary pattern is formed in the form

moreover, the value of r and r 'is chosen equal to j + 1. To verify the biometric code, this biometric code is compared with a preformed reference biometric code by calculating the degree of their similarity W and comparing with the predefined value of the similarity threshold of the biometric codes W _threshold. A predetermined tree similarity threshold W _{threshold is} selected in the range of 1 ÷ K, and a similarity degree value W is calculated as the number of pairwise equal trees from two biometric codes, and two trees are considered equal if the number of pairwise equal elements exceeds a predetermined tree similarity _threshold U _{threshold .} A predetermined tree similarity threshold U _{threshold is} selected in the interval 1 ÷ J.

Thanks to the new combination of features, the claimed method reduces the likelihood of false minutes, since the formation of the code takes into account several cores located in the central part of the electronic image of the PU, as well as the necessary computational operations before comparing the codes, which improves the reliability of the biometric fingerprint code and the time required to verify it.

The claimed method is illustrated by images that show:

figure 1 - image of a fingerprint in electronic form;

figure 2 - image of a fingerprint after filtering;

figure 3 - image of a fingerprint after splicing false gaps and removal of false mergers;

4 is a binary image of a fingerprint;

5 is a skeleton of a binary image of a fingerprint;

6 - minutes on the skeleton of a binary image of a fingerprint;

7 is a core on the skeleton of a binary image of a fingerprint;

Fig.8 is a tree from the core to the remaining minutes;

Fig.9 is a biometric code in a matrix representation.

The claimed method is implemented as follows.

Known methods for generating a biometric fingerprint code, as a rule, are based on determining the coordinates of the minutes and converting their values into a certain data set (see David Maltoni, Handbook of fingerprint recognition, ed. Springer 2003, p. 83). As a rule, false minutes may appear in the image structure, and with a probability that increases with an increase in the offset from the center of the image, codes are simplified to increase the processing speed, while at the verification stage a large computational load appears, and the reliability of the code decreases.

The aforementioned indicates the existence of a problem of developing technical solutions that ensure the formation of a biometric code, taking into account a decrease in the accuracy of the coordinates of the minutes with an increase in their distances from the center of the image, an increase in the reliability of the code and all settlement operations prior to verification of the code.

The marked problem is solved in the claimed method as follows.

The electronic view of the image of the papillary pattern of the fingerprint, shown in figure 1, is a bitmap image with pixel intensities in the range 0 ÷ 255 (see ANSI standard, www.ansi.com, appeal January 19, 2009), in which pixels with lower intensity the grooves of the print are represented - the lines of the papillary pattern 1, and the background with pixels with higher intensity. The original image contains high-frequency noise - noise and false line breaks 2 and false merges of lines 3 (see figure 2), caused by a loose fit of the finger to the surface of the scanning device.

Image noise removal technology is known. To do this, it is treated with a low-pass filter, for example, with a Gaussian core (see L. Shapiro, J. Stockman. Computer Vision, published by BINOM 2006, p.196). The result of this conversion is presented in figure 2.

Well-known technology is used to correct false line breaks of lines 2 and false merges of lines 3 (see Sharat Chikkerur, Alexander N. Cartwright "Fingerprint image enhancement using STFT analysis", Center of unified biometrcis and sensors. University at Buffalo, NY, USA, 2003 .): determine the local orientation of the lines and perform filtering by the Gabor core, the result of which is shown in Fig.3.

To equalize the intensities of the pixels AND, threshold image processing is performed (see L. Shapiro, J. Stockman. Computer Vision, ed. BINOM, 2006, p. 116), the result of which is shown in Fig. 4. In this case, pixels with an intensity below a predetermined threshold And <And the _{threshold is} converted to black, and pixels with an intensity above a predetermined threshold And> And the _{threshold is} converted to white. Based on the range of possible values of pixel intensities, the best quality of a binary image is achieved with AND _threshold = 60 ÷ 100.

Then, to simplify the process of searching for minutes, the skeleton of the binary image shown in FIG. 5 is constructed by thinning its lines to a predetermined thickness Δ. The thickness of the lines of the core 8 is usually chosen equal to one pixel. (Ya.A. Furman, A.N. Yuryev, V.V. Yashin. Digital methods of processing and recognition of binary images, Krasnoyarsk University Press, 1992, p. 192).

On the skeleton of the binary image, the coordinates of the minutes 9 (x _n , y _n ) are determined, located at the points where the skeleton lines of 8 are bifurcated or terminated (see ANSI standard, www.ansi.com, accession 01/19/2009), their coordinates are remembered. The size of the coordinate grid is determined by the intervals x _n = 0, 1, ..., X _max , y _n = 0, 1, ..., Y _max , where X _max and Y _max are selected in the range of 200-500 pixels (see FBI standard, www. fbi.com, appeal 01/15/2009).

. Чтобы внести избыточность, повышающую надежность кода, для определения аргументов функции биометрического кода выделяют 2≤K≤N сердцевин 10 папиллярного узора, показанных на фиг.7 в виде концентрических кругов, для чего для n-й минуции 9 вычисляют ее удаление S_n от центра масс 11, а в качестве К сердцевин 10 принимают минуции с наименьшими значениями их удалений S от центра масс 11.In order to have the greatest influence on the biometric code, the minutes located closer to the center of the electronic image have the greatest impact, the center of mass of the minutes 11 shown in Fig. 7 is calculated by the formula

. To introduce redundancy that increases the reliability of the code, 2≤K≤N cores 10 of the papillary pattern shown in Fig. 7 in the form of concentric circles are allocated to determine the arguments of the biometric code function, for which its distance S _n from the center is calculated for the nth minute 9 masses 11, and as K cores 10 take minutes with the smallest values of their distances S from the center of mass 11.

каждого k-го дерева, где j=1, 2,…, J, и ранжируют их. Рассчитывают аргументы кучности минуций с сердцевинами путем вычисления соотношений длин ребер 12

, каждой k-й сердцевины и углов

, между j-м и r-м ребром, а биометрический код папиллярного узора формируют в виде

, который представляет собой матрицу размерности K×J, показанную на фиг.9. Верификацию данного биометрического кода с предварительно сформированным эталонным биометрическим кодом реализуют следующим образом. Вычисляют степень схожести данного и эталонного биометрического кода W и сравнивают с предварительно заданной величиной порога схожести биометрических кодов W_порог, где W_порог выбирают в интервале 1÷К. При этом степень схожести W рассчитывают как количество попарно равных деревьев из двух биометрических кодов. Два дерева считают равными, если количество попарно равных их элементов превышает предварительно заданный порог схожести деревьев U_порог, который выбирают в интервале 1÷J.Then, so that all the parameters that make up the biometric code are relative, which makes the code resistant to rotations, shifts and uniform compression / stretching of the electronic image of the PU, from each k-th core 10, where k = 1, 2, ..., K, build edges trees 12 to the remaining J = N-1 minutes 9. One of these trees is shown in Fig. 8. Calculate the lengths of the ribs 12

each k-th tree, where j = 1, 2, ..., J, and rank them. Calculate the accuracy of the minutes with cores by calculating the ratio of the lengths of the ribs

, each kth core and corners

between the jth and rth edges, and the biometric code of the papillary pattern is formed as

which is a K × J matrix shown in FIG. 9. Verification of this biometric code with a preformed reference biometric code is implemented as follows. The degree of similarity of this and the reference biometric code W is calculated and compared with the predefined threshold value for the similarity of the biometric codes W _threshold , where the W _{threshold is} selected in the range 1 ÷ K. Moreover, the degree of similarity W is calculated as the number of pairwise equal trees from two biometric codes. Two trees are considered equal if the number of pairwise equal elements exceeds a predetermined threshold for tree similarity U _threshold , which is selected in the interval 1 ÷ J.

Due to the choice of cores, the generated biometric code is more susceptible to the influence of minutes located closer to the center of the electronic image. All the parameters that make up the biometric code are relative, which makes the code resistant to rotations, shifts and uniform compression / stretching of the electronic image of the control panel, and also eliminates the need for computational operations at the stage of code comparison. This is the reason for the achievement of the formulated technical result - providing higher reliability of the code, reducing the number of operations performed at the stage of code verification, generating the code taking into account the fact that the likelihood of false minutes increases when the fingerprint is removed from the center of the electronic image.

Claims (11)

1. A method of generating and verifying a biometric fingerprint code containing N minutes, which consists in preliminarily generating a reference biometric fingerprint code, converting the papillary pattern of this fingerprint into electronic form, processing its electronic image, determining the coordinates of the minutes of the papillary pattern, remembering them, the arguments of the function of the biometric code of the papillary pattern are determined, by which its biometric code is formed, the biometric code is compared with the preliminary the generated reference biometric code, characterized in that when processing the electronic image of the papillary pattern, it is binarized by filtering, splicing the false gaps on it, removing false line fusions and aligning the pixels of the electronic image with respect to a predetermined pixel intensity threshold, and then the core of the binary electronic image is formed by thinning its lines to a predetermined thickness Δ, and after determining the coordinates x _n , y _n N minutes on the coordinate grid, where n = 1, 2, ..., N, x _n = 0, 1, ..., x _max , y _n = 0, 1, ..., Y _max , and X _max and Y _max are the maximum sizes of the coordinate grid, on the backbone of the papillary of the pattern, the center of mass C is calculated, moreover, to determine the arguments of the biometric code function, 2≤K≤N cores of the papillary pattern are allocated, for which for the nth minute its distance S _n from the center of mass C is calculated, and K minutes are taken as K cores the smallest values of their distances S from the center of mass C, then from each k-th core, where k = 1, 2, ..., K, build trees to the rest J = N-1 minutes, calculate the lengths of the edges

of each k-th tree, where j = 1, 2, ..., J, and rank them, calculate the arguments of accuracy of minutes with cores by calculating the ratio of the lengths of the edges

every kth core and corners

between the jth and rth edges, where r = 1, 2, ..., J, a, the biometric code of the papillary pattern is formed as

then this biometric code is verified, for which it is compared with a preformed reference biometric code by calculating the degree of their similarity W and comparing with the predefined threshold value for the similarity of biometric codes W _threshold . 2. The method according to claim 1, characterized in that the thickness of the lines of the core of the binary image Δ is chosen equal to one pixel of the electronic image of the papillary pattern. 3. The method according to claim 1, characterized in that for aligning the intensities of the pixels of the electronic image of the papillary pattern, pixels with an intensity below a predetermined threshold are converted to black, and pixels with an intensity above a predetermined threshold are converted to white. 4. The method according to claim 1, characterized in that the predetermined threshold of the intensity of the pixels is selected in the range of 60 ÷ 100. 5. The method according to claim 1, characterized in that the value of r is chosen equal to j + 1. 6. The method according to claim 1, characterized in that the value of r 'is chosen equal to j + 1. 7. The method according to claim 1, characterized in that the value of X _max selected in the range of 200 ÷ 500 pixels. 8. The method according to claim 1, characterized in that the value of Y _max selected in the range of 200 ÷ 500 pixels. 9. The method according to claim 1, characterized in that the value of the degree of similarity W is calculated as the number of pairwise equal trees from two biometric codes, moreover, two trees are considered equal if the number of pairwise equal elements exceeds a predetermined tree similarity _threshold U _threshold . 10. The method according to claim 1, characterized in that the predetermined tree similarity _threshold U _{threshold is} selected in the range 1 ÷ J. 11. The method according to claim 1, characterized in that the predetermined tree similarity _threshold W _{threshold is} selected in the range of 1 ÷ K.

Images