The article deals with a new method of determining and selecting regions containing ridge parallel lines in the image of a latent ngerprint. Such images belong to a class of high-noise ones, in which the regions of interest, become unobvious. Therefore, for computer systems, the problem of determining the region of interest automatically is actual. A new algorithm for identifying regions of interest based on descriptors characterizing the presence of ridge lines. The structural mutual arrangement of ridge lines is analyzed. The methods for recognizing the descriptors, their relations, and morphological processing are formalized. Proposed algorithm is independent of the brightness and contrast of the image. The results of identifying the regions of interests are depicted for images in various qualities.
Fingerprint images can be divided into inked, sensor-scan, or latent (Fig. 1).
Sensor-scan and inked images are typically further subdivided into rolled
(nailto-nail ngerprints), or planed ngerprints [
Modern algorithms show high accuracy when working with quality rolled
and plain prints, but there are di culties in processing low-quality or noisy
images [
In practice latent identi cation occurs with the participation of experts, which select regions on latent images that contains ridge lines manually. An example of a region of interests which lie inside the closed non-overlapping contours containing either a ngerprint or a part of it shown on Fig. 2. The main problem is user subjectivity in determining a region of interest since di erent users can select di erent regions, especially if the image quality is low. Therefore, the problem of automating the process of determining the region of interest, as well as evaluating the reliability of this process, is topical. One of the main criteria is the presence of ridge lines. The main task of this paper is the development of algorithm for detection ridge lines and analysis their mutual arrangement.
The paper has the following structure. The introduction contains a brief description of research subject and formulates the problems and tasks. Section 2 devoted to a review of the latest works in the eld of latent recognition. In Section 3 proposes a method for solving these problems and describes the algorithm in detail. In conclusion, the advantages and disadvantages of the proposed method are discussed. 2
Basic approaches to trace recognition are: convolutional Networks [
Most of the considered in [
Algorithm for directional global three-part decomposition DG3PD [
In the approach suggested by Anil and Kai [
In [
Method for detecting ridge lines Let I be a 8-bit grayscale image M N in size, presented in Fig. 3. Let Fij denote a square region of side d, where (i; j) are coordinates of the center of the Foriijgrinegailoinm,aig2e ad2n::dM, for d2a,njy 2(i;d2j:):Npixed2l .inTthheeorbatnagieneodf iF2ij dr2e::gMions d2co,vje2r td2h:e:Nwhod2le, it is possible to perform the (i; j) point analysis in the Fij neighborhood and estimate a probability of the presence of parallel ridge lines in it.
To detect parallel ridge lines in the Fij speci ed region, using the
gradient method [
Fig. 3 shows the original image where the Fij region is intersected by three lines perpendicular to the direction of the ridge lines and the corresponding graphs.
Fig. 4 presents a magni ed copy of the graph shown in Fig. 3 (d). The graph is divided into blocks (a block example is the white area in Fig. 4). Let's call these blocks lobes. As an example, one of the lobes in Fig 4 is indicated in white.
A lobe can be described by six characteristics: the indices of its beginning, maximum, and end and the values of the beginning, maximum, and end. For the lobe in Fig. 4, the beginning index is 16, the maximum index is 20, and the end index is 23. The distance from the maximum to the greater of the lobe minima is called its amplitude: l = ( bv bv av; av > cv; cv; else (1) where av, bv, cv are the values of the beginning, maximum, and end of a lobe. (a; b; c) = 1 c + a c a 2b ; where a; b; c are indices of the beginning, maximum, and end of a lobe. The closer the value of this function is to 1, the more equidistant is the maximum index from the lobe borders.
The lobes have the property of symmetry. The degree of symmetry can be expressed as a function (av; bv; cv) : 8 bv > (av; bv; cv) = < bbvv > : bv cv cv
; bv av av ; else: av > bv cv; The closer the value of the function is to 1, the more symmetrical is the considered lobe.
Let us introduce the indicator function ( ), which characterizes the presence of a lobe in some region, in the form ( ) = (1; (3 < p < 11) ^ 0; else; > 0:4; where av, bv, cv are the values of the beginning, maximum, and end of the lobe, p = c a is a period of the lobe, that is, the distance between its borders. Threshold values are selected based on the results of the studies. If the value of ( ) is 1, then the region forms a lobe, otherwise the same region is considered noise.
Since the values of lobe minima can be di erent in the general case, the di erence schemes roughly approximating the calculation of the derivatives give di erent results when estimating the shape of the lobe. To perform the di erence scheme calculation, we divide the lobe into two sections: a rise from a minimum to a maximum (a positive di erence scheme) and a descent from the maximum to the next minimum (negative di erence scheme). The positive di erence scheme is as follows:
Let us introduce the function (a; b; c) characterizing the equidistant position of a lobe maximum from its borders:
S+ = bv b av a
; K+ =
b
X '(i; a; S+; av; si): Similarly, the negative di erence scheme takes a form i=a+1 S = bv c cv b ; (2) (3) (4) (5) (6)
The value of the function (10) re ects the degree of steepness of the lobe shape and, together with the centrality index of the lobe maximum (2), makes it possible to evaluate the quality of the lobe Q, that is, how much the shape of the lobe comes close to the peaked Gaussian. The results of the experiment showed that the e ective formula to evaluate quality is
c = X '(i; b; S ; bv; si):
i=b+1 Here S+ is a step of a rise; S is a step of a descent; a; b; c are indices of the beginning, maximum, and end of the lobe; av, bv, cv are the values of the beginning, maximum, and end of the lobe; si is the brightness value for the i-th position in the section; K+ is the rise coe cient; K is the descent coe cient; '(x0; x1; x2; x3; x4) is an auxiliary function, the value of which is calculated by the formula:
Q = where is calculated by the formula (10) and by the formula (2).
The mean values of the amplitude and period of the lobes are unbiased. However, there is deviation from mathematical expectation both for a single lobe and for sampling. This is especially noticeable in low quality images. If the shape of the lobes is signi cantly di erent from the Gaussian, for example, it tends heavier to the exponential distribution, then the median can be far from the mode, and the mean value is preferable to both estimates.
Let the amplitude, which di ers essentially from those of the neighboring lobes, be called a false amplitude (Fig. 5 (a)). The period, which di ers signi cantly from those of the neighboring lobes, will be called a false period (Fig. 5 (b)). To calculate the mean value, it is necessary to exclude the lobes signi cantly di erent from the others. To do this, we use the following algorithm.
Let there be a set of real numbers fa0; a1; :::; an 1g, where ai 2 IR, n 2 IN, n > 2. We choose from a set of numbers three elements closest to the mean (8) (10) (11) value and calculate their arithmetic average. Let us consider complementary set f(xi;j ) 2 R; i 2 0::n 1; j 2 f0; 1gg. Let and be functions de ned as follows: where xi;0 = ai; i 2 0::n 1. We rank the set fx0;1; x1;1; :::; xn 1;1g in ascending order. Let three elements giving maximum values be indexed as m1, m2, and m3. Then the average value of the parameter is calculated as follows: x = xm1;0 + xm2;0 + xm3;0 : (15)
3
Using the formulas (12{15), we nd the average values of an amplitude l and a period p. Then we estimate closeness of amplitudes and periods of each lobe to these magnitudes.
A lobe is estimated in three steps. 1. Deviation from the average period is estimated by the formula 2. Deviation from the average amplitude is estimated by the formula mi;p = 8>1; jci ><>0; 75; jci >>0; 5; jci >:0; 25; else: ai ai ai pj = 0; pj = 1; pj = 2; mi;l = 8 >>1 < >>1 : l l l li li ; l > li; li ; l li: (12) (13) (14) (16) (17) 3. An estimate that the cross section (Fig. 3) intersects ridge lines is performed by the formula
n 1 w = X i=0 iQimi;pmi;l(ci ai): (18) Here, n is the number of lobes in a line; avi, bvi, cvi are the values of the beginning, maximum, and end of the i-th lobe; ai and ci are indices of the i-th lobe beginning and end, respectively; li is the amplitude of the i-th lobe; i is the degree of the lobe symmetry (3); Qi is quality of the lobe calculated using (11); mi;p is calculated by (16), mi;l is calculated using (17).
One line is usually not enough to get a reliable estimate of wi in a low-quality image, so we use not 3 (as in Fig. 3), but, for example, 17 lines. Then the nal estimate
W =
Pin=01 wi n ; (19) where n is the number of lines.
Having ranked the estimate value and brought it to the range of 0::255, we obtain the image shown in Fig. 6.
To nd the borders of the region of interest, the image (Fig. 6 (b)) is binarized and subjected to morphological processing [7, pp. 523{525]. The result of detecting the region of interest is presented in Fig. 7. Let the original image I (Fig. 6 (a)) be of M N size and A(i; j) be the brightness value in the original image point with coordinates (i; j) and B(i; j) be the brightness value in the binarized image point with coordinates (i; j). Then, Bij is calculated by the formula
Bi;j = (1; z
H; 0; else; z =
Pjy+=jd2 d2 Pix+=d2i d2 A(x; y) d2 ; (20) (21) where d are dimensions of a square frame bounding the region in which the calculations and analysis take place, and H is brightness threshold.
The result of this transformation is shown in Fig. 7 (a). A large white frame identi es the region of interest while the smaller frames outline other regions where ridge lines can also be presented. Due to the insu cient size of small areas, they can be neglected.
The program is implemented in C++ in the cross-platform Qt Creator environment. No software libraries associated with image processing were used. For testing images from the representative latent print database NIST27 database was indexed. The threshold values mentioned in the paper (Fig. 8) were set manually. The results of the algorithm operation were visually compared with the regions of interest identi ed manually in the images of the NIST27 database (Fig. 9). Fig. 9. (a) Original image with the region of interest selected manually; (b) image after processing by the algorithm with the selected region of interest In the paper we propose the method of determining and selecting regions containing parallel ridge lines on the ngerprint images. Using the proposed approach, it was possible to automate the process of identifying the regions of interest on low-quality images. This approach is one of the key elements in ngerprint image processing.
The advantage of the method is its independence from the image brightness and contrast since their increase or decrease result only in an increase or decrease of lobe amplitudes with lobe shape saved, which additionally enhances the algorithm stability. The obtained results allow identifying regions of interest automatically with high reliability of their recognition. The main disadvantage of the method is a false recognition of printed alternating strips occurring on banknotes. Further research directions suggest eliminating this drawback by using other methods of image analysis. In addition, it is planned to automate the evaluation of the quality of identifying regions of interest and implement automatic algorithm training.