=Paper=
{{Paper
|id=Vol-2268/paper2
|storemode=property
|title=Method for Determining Ridge Lines of a Latent Fingerprint
|pdfUrl=https://ceur-ws.org/Vol-2268/paper2.pdf
|volume=Vol-2268
|authors=Kirill Milovidov,Vladimir Gudkov,Daria Lepikhova
|dblpUrl=https://dblp.org/rec/conf/aist/MilovidovGL18
}}
==Method for Determining Ridge Lines of a Latent Fingerprint==
https://ceur-ws.org/Vol-2268/paper2.pdf
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)