Method for Determining Ridge Lines of a Latent Fingerprint Kirill Milovidov1 , Vladimir Gudkov1,2 , and Daria Lepikhova1 1 Sonda Pro Ltd, Ilmen-Tau str. 1,-2, Miass, Chelyabinsk reg., 456318, Russia 2 South Ural State University, 76 Lenin pr., Chelyabinsk, 454080, Russia 1986shinra@gmail.com,diana@sonda.ru,lepikhova@sonda.ru Abstract. The article deals with a new method of determining and se- lecting regions containing ridge parallel lines in the image of a latent fingerprint. Such images belong to a class of high-noise ones, in which the regions of interest, become unobvious. Therefore, for computer sys- tems, the problem of determining the region of interest automatically is actual. A new algorithm for identifying regions of interest based on de- scriptors 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. Keywords: latent fingerprint, image recognition, region of interest 1 Introduction Fig. 1. Types of fingerprint images: (a) rolled; (b) plain; (c) latent Fingerprint images can be divided into inked, sensor-scan, or latent (Fig. 1). Sensor-scan and inked images are typically further subdivided into rolled (nail- to-nail fingerprints), or planed fingerprints [1]. Latent fingerprints are impres- sions of the ridge lines that are unintentionally left by a subject at crime scenes. Their features are poor image quality, presence of background and inscriptions, fragmentation, noise, fuzzy structure of ridge lines. Therefore, one of the main problem of latent fingerprint identification is to select region that contains ex- actly the ridge lines, and not something else. Modern algorithms show high accuracy when working with quality rolled and plain prints, but there are difficulties in processing low-quality or noisy im- ages [2]. In NIST evaluations, the best performing AFIS achieved an identifica- tion rate 99,5% on database of 10000 plain fingerprints. And whereas accuracy of the best latent identification system could achieve only 65% rate and an average does not exceed 50% [3]. In practice latent identification 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 con- tours containing either a fingerprint or a part of it shown on Fig. 2. The main problem is user subjectivity in determining a region of interest since different users can select different 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 crite- ria 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. Fig. 2. An example of a region of interest (white-outlined manually) The paper has the following structure. The introduction contains a brief de- scription of research subject and formulates the problems and tasks. Section 2 devoted to a review of the latest works in the field of latent recognition. In Section 3 proposes a method for solving these problems and describes the algo- rithm in detail. In conclusion, the advantages and disadvantages of the proposed method are discussed. 2 Related works Basic approaches to trace recognition are: convolutional Networks [4], deep neu- ral networks [5], using of various filters [6] (Laplacian Filter, Sobel Filter, Gaus- sian Low Pass Filter, Gaussian High Pass Filter et al.) and veivlets [4, 7]. In [6] verification method independent of local gradients and resistance to background noise is proposed. Surveys of papers devoted to various approaches to latent image segmentation are presented in [3, 8]. Most of the considered in [3] algorithms are partially automated. It means that segmentation is performed in the automatic mode, but manual marking of the area containing ridge lines or manual indication of control points is required. There is no fully automatic algorithm that would work without the participation of an expert. Algorithm for directional global three-part decomposition DG3PD [9] implies breaking the image down to two or three components. As a result of the DG3PD operation, three images are generated, namely, a cartoon, texture, and residual. Such decomposition into three different images makes it possible to improve the results of segmentation and greatly facilitates the object identification in the image. Geometric objects have a smooth surface and sharp edges in a cartoon image while they are smooth and sparse in a texture image. This makes it easy to identify them in the original image. However, if the original image is noisy or contains many small objects, there are difficulties in its 3-D decomposition via the DG3PD method. In the approach suggested by Anil and Kai [10], to perform image segmen- tation, a ridge line map is used, which is based on the values of the thickness, direction, continuity, and density of the ridges. Then, a neural network is de- veloped and trained. This method demonstrates high accuracy for rolled clear fingerprints. Unfortunately, the proposed approach cannot deal with low-quality latent fingerprint images, requiring mandatory expert control. In [4] convolution networks are used for ridge lines direction estimate. In ad- dition for candidate list compilation textures and minutiae templates are formed. 3 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 Fij region, i ∈ d2 ..M − d2 , j ∈ d2 ..N − d2 . The obtained Fij regions cover the whole original image and, for any (i, j) pixel in the range of i ∈ d2 ..M − d2 , j ∈ d2 ..N − d2 , 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. Fig. 3. (a) The original image where the Fij region is highlighted with a white border; (b) the graph of the first perpendicular presented in (c); (c) magnification of the Fij region, in which the perpendiculars to the ridge lines were constructed; (d) the graph of the second perpendicular presented in (c); (e) the graph of the third perpendicular presented in (c) To detect parallel ridge lines in the Fij specified region, using the gradi- ent method [11, 12], let us define the orientation of the lines and construct the perpendiculars to them in the Fij region (Fig. 3 (c)). For each perpendicu- lar obtained, we plot the brightness, following the rule: the brightness values are distributed vertically while the indices, that is, the ordinal numbers of the points, are distributed horizontally. The optimal length of perpendiculars, equal to 40 points, was determined experimentally. Fig. 4. Dependence of brightness on the position in the section 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 magnified 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: ( bv − av , av > cv , l= (1) bv − cv , else where av , bv , cv are the values of the beginning, maximum, and end of a lobe. Let us introduce the function σ(a, b, c) characterizing the equidistant position of a lobe maximum from its borders: c + a − 2b σ(a, b, c) = 1 − , (2) c−a 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 ) : b − cv   v  , bv − av > bv − cv , θ(av , bv , cv ) = bv − b av − av (3)  v  , else. bv − cv The closer the value of the function is to 1, the more symmetrical is the consid- ered 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.4, χ(θ) = (4) 0, else, 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 different in the general case, the difference schemes roughly approximating the calculation of the derivatives give different results when estimating the shape of the lobe. To perform the difference scheme calculation, we divide the lobe into two sections: a rise from a minimum to a maximum (a positive difference scheme) and a descent from the maximum to the next minimum (negative difference scheme). The positive difference scheme is as follows: bv − av S+ = , (5) b−a b X K+ = ϕ(i, a, S + , av , si ). (6) i=a+1 Similarly, the negative difference scheme takes a form bv − cv S− = − , (7) c−b c X K− = ϕ(i, b, S − , bv , si ). (8) 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 coefficient; K − is the descent coefficient; ϕ(x0 , x1 , x2 , x3 , x4 ) is an auxiliary function, the value of which is calculated by the formula: 0 1 − ϕ + x3 − x4 , |ϕ0 + x − x | < |ϕ0 |,  3 4 ϕ(x0 , x1 , x2 , x3 , x4 ) = |ϕ0 | (9) 0, else,  where ϕ0 = (x0 − x1 )x2 . Let us introduce the function ψ(K + , K − , a, c) , which characterizes the lin- earity of the transition from the lobe borders to its maximum as follows: −  + K + K , c > a + 2, ψ(K + , K − , a, c) = c−a−2 (10) 0, else.  The value of the function ψ (10) reflects 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 effective formula to evaluate quality is (2σ + ψ) Q= , (11) 3 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 significantly different 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 differs essentially from those of the neighboring lobes, be called a false amplitude (Fig. 5 (a)). The period, which differs sig- nificantly 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 significantly different from the others. To do this, we use the following algorithm. Let there be a set of real numbers {a0 , a1 , ..., an−1 }, where ai ∈ IR, n ∈ IN, n > 2. We choose from a set of numbers three elements closest to the mean Fig. 5. (a) False amplitude; (b) false period value and calculate their arithmetic average. Let us consider complementary set {(xi,j ) ∈ R, i ∈ 0..n − 1, j ∈ {0, 1}}. Let µ and η be functions defined as follows: n−1 X xk,0 µ(i) = , xi,0 > xk,0 , (12) xi,0 k=0 n−1 X xi,0 η(i) = , xi,0 ≤ xk,0 , (13) xk,0 k=0 xi,1 = µ(i) + η(i), (14) where xi,0 = ai , i ∈ 0..n − 1. We rank the set {x0,1 , x1,1 , ..., xn−1,1 } 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: xm1,0 + xm2,0 + xm3,0 x= . (15) 3 Using the formulas (12–15), we find 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    1, |ci − ai − p| = 0,  0, 75, |c − a − p| = 1, i i mi,p = (16)    0, 5, |c i − ai − p| = 2, 0, 25, else.  2. Deviation from the average amplitude is estimated by the formula  l − li 1 −   , l > li , mi,l = l (17)  1 − l − li , l ≤ li .   li 3. An estimate that the cross section (Fig. 3) intersects ridge lines is performed by the formula n−1 X w= θi Qi mi,p mi,l (ci − ai ). (18) i=0 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). Fig. 6. (a) Original image, (b) processed image (the whiter the color, the better esti- mate) 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 final estimate Pn−1 i=0 wi W = , (19) n 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 find the borders of the region of interest, the image (Fig. 6 (b)) is bina- rized 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 orig- inal 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 ( 1, z ≥ H, Bi,j = (20) 0, else, where Pj+ d2 Pi+ d2 y=j− d x=i− d A(x, y) 2 2 z= , (21) d2 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 identifies the region of interest while the smaller frames outline other regions where ridge lines can also be presented. Due to the insufficient size of small areas, they can be neglected. Fig. 7. (a) Binarized image with regions of interest outlined; (b) original image with regions of interest outlined The program is implemented in C++ in the cross-platform Qt Creator envi- ronment. 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 man- ually. The results of the algorithm operation were visually compared with the re- gions of interest identified manually in the images of the NIST27 database (Fig. 9). Fig. 8. Original image. The black frame marks the region of interest at the following values: (a) θ > 0.4 and H = 102, (b) θ > 0.1 and H = 102, (c) θ > 0.9 and H = 102 (according to formulas (3, 20)) 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 Conclusion In the paper we propose the method of determining and selecting regions contain- ing parallel ridge lines on the fingerprint 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 fingerprint 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 de- crease 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 ban- knotes. Further research directions suggest eliminating this drawback by using other methods of image analysis. In addition, it is planned to automate the eval- uation of the quality of identifying regions of interest and implement automatic algorithm training. References 1. Svoboda J., Monti F., Bronstein M.: Generative Convolutional Networks for Latent Fingerprint Reconstruction. 2017 IEEE International Joint Conference on Biometrics (IJCB), pp. 100–107, Denver, Colorado, USA (2017) 2. Capelli R., Ferrara M., Maltoni D: Fingerprint Indexing Based on Minutia Cylinder- Code. In: IEEE Transactions on Pattern Analysis and Machine Intelligence. 33(5), 1051–1057 (2011) 3. Cao K., Liu E., Jain A. K.: Segmentation and Enhancement of Latent Fngerprints: A Coarse to Fine Ridge Structure Dictionary. In: IEEE Transactions on Pattern Analysis and Machine Intelligence. 36(9), 18471859 (2014) 4. Cao K., Jain A. K.: Automated latent fingerprint recognition. In: IEEE Transactions on Pattern Analysis and Machine Intelligence, (2018) 5. Ezeobiejesi J., Bhanu B.: Latent fingerprint image segmentation using deep neural network. Deep Learning for Biometrics. 83–107 (2017) 6. Himanshi, Anit Kaur, Amit Verma: Latent Fingerprint Recognition using Hybridiza- tion Approach of Partial Differential Equation and Exemplar Inpainting. Indian Jour- nal of Science & Technology. 9(45), 1–11 (2016) 7. Gonzalez R.C., Woods R.E.: Digital Image Processing. Prentice-Hall, Inc. Upper Saddle River, New Jersey (2002) 8. Nguyen D.-L., Cao K., Jain A.K.: Automatic Cropping Fingermarks: Latent Fin- gerprint Segmentation. BTAS, 2018 9. Thai D. H., Gottschlich C.: Directional global three-part image decomposition. In- stitute for Mathematical Stochastics, University of Goettingen, Goettingen (2016) 10. Anil K. J., Kai C.: Fingerprint Image Analysis: Role of Orientation Patch and Ridge Structure Dictionaries. Geometry Driven Statistics. 288–310 (2015) 11. Bazen A.M.: Fingerprint Identification — Feature Extraction, Matching, and Database Search. The Netherland, Twente University Press (2002) 12. Maltoni D., Maio D., Jain A. K., Prabhakar S.: Handbook of fingerprint recogni- tion. Springer-Verlag, London (2009)