RU2059979C1 - Method for recognition of prints of papillary patterns - Google Patents

Abstract

FIELD: criminology. SUBSTANCE: method involves serial decoding of specific feature flows from overall structure of flows of papillary patterns. EFFECT: increased validity of identification. 16 dwg

Description

 The invention relates to methods for the recognition and coding of fingerprints of papillary patterns used in automated fingerprint information systems, personal identification systems, fingerprint comparison and access restriction systems.

 Systems using the structural features of the papillary pattern are finding wider application. The fingerprints are compared based on the analysis of the relative positioning of the small features of the pattern (by small features, we mean the endings and branches of papillary lines). A large number of small features on the fingerprint of the papillary pattern (on the fingerprint on average about 100) determines the great computational complexity of each comparison. The number of prints in large collections exceeds 100 signs and therefore the utilization rate of automated systems increases significantly when applying automatic classification of papillary patterns based on the relative position of the features of the papillary pattern, which are called deltas, loops, curls in fingerprinting (Fig. 1).

 The complexity of the automatic determination of features is due to the fact that in reality on the prints of papillary patterns there are always various kinds of interference and noise due to scars, pollution, and excess paint or excessive pressure or rolling, etc. There are patterns that cannot be unambiguously classified due to the fact that they are located on the border of classes.

 There are two main approaches for determining the papillary pattern.

 1. Methods based on the analysis of line code trace (see Pattern Recognition, vol. 25, N 2, pp. 139-153, 1992). In these methods, the imprint is represented by a set of continuous thin lines. The disadvantage of these methods is the high sensitivity to image quality due to the fact that in obscure places the lines are either intermittent or not visible at all and it is impossible to reliably trace the progress of the lines.

 2. Methods based on the analysis of papillary line flows (Pattern Recognition, vol. 17, No. 3, pp. 295-303, 1984). In these methods, the fingerprint appears to be a continuous field of tangent to the flow of papillary lines. The weakness of these methods is the presence of falsely defined features due to the fact that flow structures resembling flow structures near features are randomly implemented in obscure places. It is possible to attenuate the effect of noise by increasing the size of the region that determines the flow direction at the split points, but then the mutual screening effect of nearby features appears, leading to the omission of these features.

 A common drawback of methods for determining features of fingerprints is that after a feature is determined, it remains unclear whether this feature is true at all, and what level of error in determining features of a feature can be expected. The lack of an answer to these questions casts doubt on the possibility of using the indicated methods in those fingerprint systems in which there is no operator control over the correctness of determining features.

 A known method of generating features for recognizing segmented texture images, which consists in highlighting structural fragments of the image on the image using a binary mask, forming a spatial filter using the first Fourier transform, filtering the formed image with a homogeneous fine structure with highlighting image fragments, performing the second Fourier transform, measuring coordinates all recorded cross correlation signals relative to the autocorrel signal tion and formation of these sequence features (auth. binding. USSR N 1374260, cl. G 06 K 9/00, published. 1988).

 Closest to the proposed method is a comparative study of fingerprints, which consists in encoding areas with characteristic features and comparing the codes of the fingerprint under study with the codes of the reference fingerprint (ed. St. USSR N 114460, class G 06 K 9/46, published. 1958).

 A drawback of the methods for determining the features of fingerprints is that after determining the features, it remains unclear whether this feature is generally true and what level of error in determining the features of the feature can be expected. The lack of an answer to these questions casts doubt on the possibility of using the indicated methods in those fingerprint systems in which there is no operator control over the correctness of determining features.

 The objective of the invention is to provide a method for determining the features of the imprint of the papillary pattern by sequentially isolating the flows of features from the general structure of the flows of papillary lines. The computational efficiency of the method is achieved by preliminary dividing the image into zones that may contain features, and into zones that cannot. In addition, the aim of the invention is to provide a method for determining the probability of not exceeding a deviation of a particular feature from its true position.

 The method described below is applicable to the papillary patterns of the first phalanges of the fingers, but can easily be generalized to papillary patterns of the palms and feet.

 The image of the papillary pattern is scanned using a digital camera or scanner. The scan resolution is selected so that the thinnest papillary lines contain at least three prints. The number of gray levels is determined by the requirement of image difference in all places, that is, it is determined by the image quality. The scanning device forms an array of image elements of i rows, j columns.

 Depending on the resolution of the scan, the parameters of the algorithm can vary, therefore, it is convenient to measure all sizes not in the number of samples, which will be different each time, but in the average thickness of the papillary lines, which is an invariant. Denote the number on the papillary line of average thickness n.

 Near the features, the flow direction changes at the distance of one intercostal distance, therefore, the direction of the flow at each point of the indent should be determined in the vicinity of the point with a size commensurate with the intercostal distance. A large size of the neighborhood leads to uncertainty in the direction of the flow near the features, and a smaller size increases the spread in determining the direction due to the presence of defects and noises of various kinds in the image. In order to reduce the amount of calculations, the flow direction is determined not at each point, but with a step in i and j equal to n, which determines the maximum error in determining the coordinates of features within n / 2 (half of the papillary line). Such an error is acceptable because there is always an uncertainty in the position of a feature of the same order.

At each point in the image, a brightness gradient B is determined;
G (i, j) = grad B = (Bx (i, j), Bj (i, j)) i = 1.500
Bx (i, j) = B (i, j + 1) -B (i, j-1)
j = 1.500
By (i, j) = B (i-1, j) -B (i + 1, j)
Index i increases from top to bottom of the image (image row), index j from left to right (image column).

+90^°
-90^° ≅ arctg

≅ 90^° 0<U(i,j) ≅ 180^o
Также определяется величина градиента А(i,j), как сумма абсолютных значений Вх(i,j) и Вy(i,j)
A(i,j)=mod Bx(i,j)+mod By(i,j) i=1,500, j=1, 500
В точках разбиения k, l (k=1,100, l=1,100) определяется направление папиллярных линий, для чего для каждой точки разбиения k, l в ее расширенной окрестности 9х9 строится гистограмма Нk,l распределения направлений U(i, j) с учетом величины градиента А(i, j). Гистограмма определяется с учетом величины градиента для того, чтобы исключить влияние той части изображения, которая не относится к границам папиллярных линий и не содержит полезной информации.The direction of the image vector determines the direction of the papillary line, namely the direction of the papillary line U (i, j) is determined as follows:
u (i, j) arctg

+90 ^°
-90 ^° ≅ arctg

≅ 90 ^° 0 <U (i, j) ≅ 180 ^o
The magnitude of the gradient A (i, j) is also determined as the sum of the absolute values of Bx (i, j) and By (i, j)
A (i, j) = mod Bx (i, j) + mod By (i, j) i = 1,500, j = 1,500
At the points of the partition k, l (k = 1,100, l = 1,100), the direction of the papillary lines is determined, for which a histogram Нk, l of the distribution of directions U (i, j) is constructed taking into account the value gradient A (i, j). The histogram is determined taking into account the magnitude of the gradient in order to exclude the influence of that part of the image that does not belong to the boundaries of the papillary lines and does not contain useful information.

9 9
Нk, l = i = 1 j = 1 A * (i, j) n = 0.35 (in increments of 5 ^° )
A * (i, j) are those A (i, j) for which U (i, j) / 5 = n.

The direction U (k, l) at the points of the partition k, l is determined by the maximum sum in five adjacent digits of the histogram,
Q (k, l) = max (H _{k, l} (n-2) + H _{k, l} (n-1) + H _{k, l} (n) +
+ H _{k, l} (n + 1) + H _{k, l} (n + 2))
n = 0.35
The index n is looped, since the direction of 185 ^about identical to the direction of 5 ^about , and therefore:
H _{k, l} (-2) = H _{k, l} (34)
Hk, l (-1) = H _{k, l} (35)
H _{k, l} (36) = H _{k, l} (0)
H _{k, l} (37) = H _{k, l} (1)
The resulting flow pattern (Fig. 3) is distorted by noise due to defects in the original image of a different nature (Fig. 2). To reduce the effect of noise, a flux relaxation method is used, consisting in the fact that the flow direction at each point is replaced by a value calculated from the values of neighbors.

abs(Q(i)-Q(o))
В качестве Q(i) выбирается такое значение, чтобы abs(Q(i)-Q(0)) было меньше 90^о, т.е.At the partition points k, l (as before, k, l = 1,100), the weight coefficient W (k, l) of the direction at each point is calculated from the average deviation of the direction at this point from the directions of the neighbors:
W (k, l) 90-

abs (Q (i) -Q (o))
B was less than 90 as Q (i) is chosen such a value that abs (Q (i) -Q (0)) ^o, i.e.

(W(i)•Q(i)-Q(c))² 0 (1)
Здесь Q(i) такое, что
если Q(i)-Q(c)>90^о, то Q(i)=Q(i)-180^o
если Q(i)-Q(c)<90^о, то Q(i)=Q(i)+180^о
Q(c) это Q(i) с максимальным Q(i), i=0,B.if Q (i) -Q (O)> 90 ^o , then Q (i) = Q (i) -180 ^o
if Q (i) -Q (O) <90, then Q (i) = Q (i) +180 ^o
As a new direction, such a direction is taken so that the sum of the squares of the deviations of the new direction from the directions of the neighbors, taking into account the weight of the neighbors, is minimal, i.e. the derivative was zero:

(W (i) • Q (i) -Q (c)) ² 0 (1)
Here Q (i) is such that
if Q (i) -Q (c) > ^90, the Q (i) = Q (i ) -180 o
if Q (i) -Q (c) < ^90, then the Q (i) = Q (i ) +180 ^of
Q (c) is Q (i) with maximal Q (i), i = 0, B.

Номер элемента 0 относится к текущему индексу (k,l)
I к индексу (k-1, l-1)
2 к индексу (k-1, l)
3 (k-1, l+1)
4 (k, l+1) и т.д. (см. фиг. 4).From (1) it follows that the new value Q * (k, l) is equal to:
Q ^* (k, l)

Element number 0 refers to the current index (k, l)
I to index (k-1, l-1)
2 to the index (k-1, l)
3 (k-1, l + 1)
4 (k, l + 1), etc. (see Fig. 4).

 This procedure is applied to the direction of flows twice, allowing to reduce the effect of noise (Fig. 5). A larger number of iterations is undesirable, since along with noise smoothing, a small change in the flow pattern will occur and the algorithm accuracy will decrease.

 The next step of the method is to divide the papillary pattern into zones that may contain features, and into zones that cannot. For this, the weighting coefficient of the direction at each point is calculated from the average deviation of the directions in the vicinity of this point. In this case, a larger neighborhood is used than in the relaxation process, where only the nearest neighbors are used. Here the size of the neighborhood is 5x5.

abs(Q(i)-Q(o)),

Номер элемента О относится к текущему индексу (k,l)
1 к индексу (k-2, l-2)
2 (k-2, l-1)
3 (k-2, l)
4 (k-2, l+1) и т.д. (см. фиг. 6).W (k, l) 90

abs (Q (i) -Q (o)),

Element number O refers to the current index (k, l)
1 to index (k-2, l-2)
2 (k-2, l-1)
3 (k-2, l)
4 (k-2, l + 1), etc. (see Fig. 6).

 The obtained weights are averaged over neighbors in the 5x5 region.

W(K-2+i,l-2+j)
Устанавливается порог W1=70, превышение которого величиной W(k,l) указывает на то, что текущая точка относится к области ровного потока, и, следовательно, не может быть особой точкой. Все остальные точки потенциально могут быть особыми. На фиг. 7 потенциально особые точки объединены в области с черным цветом. Все дальнейшие операции производятся только с точками из этих областей. Для отпечатков высокого качества такие области состоят из близких окрестностей особых точек, что определяет высокую вычислительную эффективность метода. Для отпечатков плохого качества указанная область распространяется на весь отпечаток, что также естественно, поскольку не существует простых решений для сложной задачи.W (k, l)

W (K-2 + i, l-2 + j)
The threshold W1 = 70 is set, the excess of which by the value of W (k, l) indicates that the current point belongs to the region of the even flow, and, therefore, cannot be a singular point. All other points can potentially be special. In FIG. 7 potentially singular points are combined in areas with black color. All further operations are performed only with points from these areas. For high-quality prints, such areas consist of close neighborhoods of singular points, which determines the high computational efficiency of the method. For poor quality prints, the specified area extends to the entire print, which is also natural, since there are no simple solutions for a complex problem.

The singular points of the papillary pattern differ from the usual ones in that when a singular point is circled in a closed circuit in the counterclockwise direction, the tangent to the flow of papillary lines rotates
D = sum (abs (Q (i) -Q (i-1)), i = 0, 1, 8, Q (-1) = Q (8)
D = 0 ^o nonsingular point
D = 180 ^o loop
D = -180 ^o delta
D = 360 ^o curl (see Fig. 8)
To approximate the flow of papillary lines near a singular point, we use the arg (Z) function, which has a value of D = 360.

a

D

=

1

е

Fz=arg(Z)+const, D=360^o,
Каждая из функций Fp, Fd, Fz определяет направление касательной к потоку папиллярных линий вблизи соответствующих особых точек. Вид этих функций приведен на фиг. 6.

a

D

=

1

e

Fz = arg (Z) + const, D = 360 ^o ,
Each of the functions Fp, Fd, Fz determines the direction of the tangent to the flow of papillary lines near the corresponding singular points. These functions are shown in FIG. 6.

 The change in const in the functions Fp, Fd, as can be seen from FIG. 9 leads to the rotation of the picture around the axis, and a change in the function Fz changes the picture in such a way that the entire possible spectrum of curl configurations is realized (Fig. 9).

 Comparing FIG. 1 and FIG. 9, one can see that by choosing const values one can get a good approximation of the really existing flows of papillary lines near singular points.

 The described property of the functions Fp, Fd, Fz is used to search for singular points of the papillary pattern. If we subtract the corresponding function from the set of Fp, Fd, Fz from the directions of flows near a singular point, then in this neighborhood we get an even flow, i.e.

 Q (i) -F (i) = const, for all points in the neighborhood of the singular point.

(Q^*(i)-Q(i)), n 0, 35
Q*(i) те Qt(i), для которых Qt(i)-Q(i))/5=n,
Qt одна из функций Qp, Qd, Qz.The next step of the method is to find areas in which singular points are located. For each point of the regions, which may potentially contain singular points of the region marked in FIG. 7 in black, the high function Wp, Wd, Wz is calculated as follows:
Wp = sum (90 ^o -abs (Qp (i) -Q (i)))
Wd = sum (90 ^o -abs (Qd (i) -Q (i)))
Wz = sum (90 ^o -abs (Qz (i) -Q (i)))
i = 0,1,2, L-1, L = l + 1
The value of const, which is part of the functions Qp, Qd, Qz, is selected from the histogram H (n) of the deviation of Qp (i), Qd (i), Qz (i) from Q (i):
H (n)

(Q ^* (i) -Q (i)), n 0, 35
Q * (i) those Qt (i) for which Qt (i) -Q (i)) / 5 = n,
Qt is one of the functions Qp, Qd, Qz.

 The value of const is determined by the maximum amount in five adjacent digits of the histogram.

 Here a reasonable compromise is required when choosing the size l of the neighborhood of the point at which the functions Wp, Wd, Wz are determined. Too large a size will lead to poor approximation by the functions Wp, Wd, Wz of real existing papillary line flows, increase the mutual influence of similar features, and too small will emphasize the effect of noise. Nevertheless, there is an optimal size, which is determined by the nature of the papillary patterns. Two adjacent features should be separated by at least one papillary line, i.e., the maximum distance will be about four n, so 11 is a good choice for l.

 In FIG. 10, black areas indicate areas that contain loops, and in FIG. 11 areas that contain deltas. A similar picture is obtained for the case when the pattern contains a curl. The black region is the region of high values of the weight functions Wp, Wd, Wz.

 The difficult task in determining the features is the separation of weight functions of closely spaced features, which takes place in complex patterns and patterns located at the boundaries of classes. In such cases, the effect of mutual screening of features is manifested. Difficulties also arise in determining how many features lie inside a region with a high value of the weight function. These problems are solved by sequentially isolating features from the structure of papillary line flows.

The isolation begins with a singularity having the maximum value of the weight function of the medium of the functions Wp, Wd, Wz. The corresponding function of the flow of papillary lines from the set of Qp, Qd, Qz is subtracted from the general structure of the flows (Fig. 5). In the resulting structure of flows, the value of the functions Wp, Wd, Wz changes, but changes only in the vicinity of the feature that is subtracted from the general structure of flows. Therefore, the values of the functions Wp, Wd, Wz in this neighborhood are recalculated. If there was one feature in such a feature, then after its isolation, the recalculated functions Wp, Wd, Wz will have small values and, accordingly, no other features in this area will be detected. The above procedure continues until at least one of the functions Wp, Wd, Wz exceeds the set threshold Ws. In FIG. 12, 13, 14, 15 shows the realizing patterns of papillary line flows in the process of isolating the pattern features of FIG. 5, and in FIG. 16 shows corresponding features. The last pattern after isolating the features is always the classic arc pattern, which indicates that real papillary patterns can be represented with good accuracy by the sum of the classic arc pattern and the functions Qp, Qd, Qz. For deltas and curls, the coordinates i, j are fixed, and for loops, in addition to this, the direction f indicated in FIG. 13. The direction is determined by the value of const function Qc, which was realized at the maximum value of Wc
f = 2 const.

 An equally important task than determining the position of features is the task of determining the probability that a feature is defined, and not a noise point. This makes it possible to use only those features that satisfy a certain accuracy criterion for a given level of probability, and not to use dubious features.

 To solve this problem, an assumption is made that the considered feature is defined correctly. With this assumption, the direction of the flow of papillary lines is filtered, and the resulting structure of the flows is compared with the original noisy picture. The number of changes introduced by filtering is a reliable criterion for the accuracy of determining this feature.

 As already noted, the real pattern is represented by the sum of the classical arc pattern and the functions Fp, Fd, Fz. In the arc pattern, the flow reversal occurs smoothly, therefore, to approximate the behavior of the flow of papillary lines in a small neighborhood, the sum of the functions Fp, Fd, Fz features is used.

t

(

•arg(Z-Zp(i))+
Здесь: Np количество центров;
Nd количество дельт;
Nz количество завитков;

мнимая единица,
Zp(i) Xp(i)+

+Yp(i)
Хр(i) координата Х i-го центра;
Yp(i) координата Y i-го центра;
Zd(i) Xd(i)+

+Yd(i)
Хd(i) координата Х i-ой дельты;
Yd(i) координата Y i-ой дельты;
Zz(i) Xz(i)+

+Yz(i)
Хz(i) координата Х i-го завитка;
Yz(i) координата Y i-го завитка.

t

(

• arg (Z-Zp (i)) +
Here: Np number of centers;
Nd number of deltas;
Nz number of curls;

imaginary unit
Zp (i) Xp (i) +

+ Yp (i)
Xp (i) X coordinate of the i-th center;
Yp (i) Y coordinate of the i-th center;
Zd (i) Xd (i) +

+ Yd (i)
Xd (i) X coordinate of the i-th delta;
Yd (i) Y coordinate of the i-th delta;
Zz (i) Xz (i) +

+ Yz (i)
Xz (i) X coordinate of the i-th curl;
Yz (i) Y coordinate of the i-th curl.

 The weight of the direction of flows at each point is calculated, using a neighborhood of 9x9.

•sum abs(Q_i-Q_o) i=1,2,80
По аналогии с тем, как делалось раньше, новое значение направления потока Q*(k,l) получается следующим образом:
Q

Как и прежде, значение индекса О относится к центральному элементу окрестности.W (k, l) 90 ^° -

• sum abs (Q _i -Q _o ) i = 1,2,80
By analogy with what was done earlier, a new value of the flow direction Q * (k, l) is obtained as follows:
Q

As before, the value of the index O refers to the central element of the neighborhood.

abs(Q^*(i)-Q(i))
Здесь центральным элементом окрестности является особенность.As a measure of the difference between the filtered and the original noisy stream structure, the following value is used:
Wt 90 ^° -

abs (Q ^* (i) -Q (i))
Here, the central element of the neighborhood is a feature.

Q * refers to the filtered structure;
Q refers to the original structure.

 The value of Wt uniquely determines the reliability of the determination of features.

Claims (6)

 1. METHOD FOR RECOGNIZING PAPILLARY PATTERN PRINTS, which consists in scanning the image of a papillary pattern, highlighting the characteristic features of the image with their subsequent coding, forming an array of selected characteristic features, comparing their codes with the codes of selected characteristic features of the compared fingerprints of the compared papillary lines, characterized in that when forming the array of papillary lines selected characteristic features determine the direction of flow of papillary lines in the vicinity of a point commensurate with the intercostal distance lowering, smoothing the flow pattern by replacing the flow direction value with the average of the flow direction values of neighboring points, determine the probable position of the characteristic features of the papillary pattern, determine the characteristic features of the papillary pattern, and sequentially isolate the characteristic features of the papillary pattern, starting with the sign with the maximum value of the weight function .  2. The method according to claim 1, characterized in that when scanning the papillary pattern, a scanning resolution is selected in which the thinnest lines contain at least three samples.  3. The method according to p. 1, characterized in that when forming an array of selected characteristic features, measurements are made in areas of papillary lines with an average thickness.  4. The method according to p. 1, characterized in that when determining the probable position of the characteristic features of papillary patterns, the papillary pattern is divided into zones with characteristic features, the weight coefficient of the flow direction of the papillary pattern at each split point is calculated according to the average deviation of the flow direction of this point from the direction of flows neighboring points, set the threshold weight coefficient, highlight the special points, the weight coefficient of the direction of flow of which does not exceed the threshold value.  5. The method according to p. 1, characterized in that the calculation of the function of the characteristic features of papillary patterns begins with a characteristic having the maximum value of the weight function, subtract from the general structure of the papillary line flows the changes introduced by this particular point, change the values of the weight functions of the flows in the neighborhood a deductible characteristic, subtractions are performed until the weight functions are less than the threshold value.  6. The method according to p. 1, characterized in that when determining a particular point, the directions of the flow of papillary lines are approximated in the vicinity of this point, the resulting flow structure is compared with the original fingerprint of the papillary lines.

Images