=Paper= {{Paper |id=Vol-2332/paper-04-006 |storemode=property |title= About One Principle to Identification of Shape of Object |pdfUrl=https://ceur-ws.org/Vol-2332/paper-04-006.pdf |volume=Vol-2332 |authors=Ivan M. Gostev ,Leonid A. Sevastyanov,Vladimir S. Melezhik }} == About One Principle to Identification of Shape of Object == https://ceur-ws.org/Vol-2332/paper-04-006.pdf

UDC 004.4
About One Principle to Identification of Shape of Object
Ivan M. Gostev * , Leonid A. Sevastyanov† , Vladimir S. Melezhik‡S
*
National Research University “Higher School of Economics”
20, Myasnickaya str, Moscow, Russia, 101000
†
Department of Applied Probability and Informatics
Peoples’ Friendship University of Russia (RUDN University)
6 Miklukho-Maklaya St, Moscow, 117198, Russian Federation
‡
Bogoliubov Laboratory of Theoretical Physics
Joint Institute for Nuclear Research
6 Joliot-Curie St, Dubna, Moscow region, 141980, Russian Federation
S
Institute of Applied Mathematics and Communications Technology
Peoples’ Friendship University of Russia (RUDN University)
6 Miklukho-Maklaya St, Moscow, 117198, Russian Federation
Email: igostev@hse.ru, sevast@gmail.com, melezhik@theor.jinr.ru

Process of recognition of the shape of graphic objects consists of several stages. At the
first stage as a result of processing images allocate some set of characteristic properties of
some object, and on the second, make identification of object by means of comparison of
these properties with properties of the sample. Presence of noise on real images often leads to
disturbance of quantity and values in a set of such characteristic properties. In job methods
of preliminary processing of images for receiving of set characteristic properties of objects
and present methods of the identification are stated, allowing identifying the shape of graphic
objects in conditions when the part of a set of characteristic properties of object concerning
the sample is absent or is deformed by noise. Feature of the offered methods is their invariance
to affine to transformations of the shape of object, and also high speed of identification, not
dependent on complexity of identified object.

Key words and phrases: Image Processing, Pattern Recognition, Computer Geometry.

Copyright © 2018 for the individual papers by the papers’ authors. Use permitted under the CC-BY license —
https://creativecommons.org/licenses/by/4.0/. This volume is published and copyrighted by its editors.
In: K. E. Samouylov, L. A. Sevastianov, D. S. Kulyabov (eds.): Selected Papers of the 12th International Workshop on
Applied Problems in Theory of Probabilities and Mathematical Statistics (Summer Session) in the framework of the
Conference “Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems”,
Lisbon, Portugal, October 22–27, 2018, published at http://ceur-ws.org
Gostev I. M., Sevastyanov L. A., Melezhik V. S. 33

1. Introduction
The decision of task of identification of shape of graphic objects essentially differs
from other problems of recognition by that first, images entering on an input of the
recognized device can include noise and have geometrical distortions. And secondly,
process of recognition of the shape of object as a rule is based on some characteristic
hardly formalized properties with which is necessary to receive from the image. And if
the first part – processing of the image now is well studied, the second part – process
of recognition is represented very complex task which decision can be subdivided into
two stages. At the first stage it is necessary to define native characteristic properties of
recognized object, and – on the second to develop a method allowing to these properties
to make comparison of some sample and recognized object. Complexity of the second
stage of process of identification consists of in necessity to operate hardly formalized
and verbally not expressed characteristics of the shape of graphic objects [1, 2].
Recently the big attention is given one of directions of recognition at which as a result
of primary image processing the contour of some object is allocated [3–6]. This contour
further is transformed in the set of the points representing some closed curve [7–9]. As
the description of such contour values of function of curvature are used [10–17], and
as characteristic properties the points having it the maximal values are used [18–21],
see also [22, 23]. Despite of great number of variants of the decision of such problem,
stability of its decision is absent, as at the real image always presenting noise which lead
to distortion of contour of curve and, hence to change of its curvature. And it in turn
results or in smoothing some extremum (that is to removal), or to occurrence of new
points with the high curvature, not being characteristic properties of object.
Thus, if to reject the first part of a problem of recognition – image processing and to
investigate the second part then a problem of identification to be used in the formulation
of development of the methods, allowing to identify the form of objects at partially
deformed contour. Analyzing above listed sources, it is obviously, that these methods
are reduced in general to robust to receiving of function of curvature by some tabular
defined of curve and do not mention methods of identification of the shape of object.
The purpose of the present job is the statement of the modified methods of formalization
of characteristic properties of shape of objects and representation of methods of their
identification.

2. Image Processing Stage
Now for image processing there are well studied methods of primary processing and
receiving of the closed contours in the form of the verbal description [2, 3], not only in
details stated in the literature, but also realized in widely applied packages, such as
Matlab and LabVIEW. Using these packages for preliminary processing of the image and
receiving of contours, it is possible to concentrate attention to methods of construction
of the formal description of shape of object and development of methods of identification
on their basis.
On fig. 1 the result of processing of a silhouette of the plane (at the left above)
with small noise level is shown. For reception of a contour of object (at the left above)
the following sequence of Matlab functions from package Image Processing has been
used: loading of the image; for removal of noise using a filtration; and method Contour
Following [24] for receiving of a contour of object.
For identification of the shape of object as initial data the contour of the object has
been used received as a result of preliminary processing the image. It consisting from set
of points (𝑛 >> 1) — 𝑃1 𝑃2 𝑃3 ...𝑃𝑛 , closed parameterized flat curve Γ(𝑡) = (𝑥(𝑡), 𝑦(𝑡)),
1 ≤ 𝑡 ≤ 𝑛. For construction of characteristic properties of object method Arch Height
for the first time published in 1992 [25], and in further repeatedly modified, for example
in [26] is used. The initial idea of this method consist in calculation Euclid of distance
𝑑𝑖 , between a point of a curve – 𝑃𝑖 and a chord as shown in fig. 2 which is proportional
to value of the module of curvature in this point.
34 APTP+MS’2018

Figure 1. Silhouette of the plane with added white noise (at the left above), its
received contour (on the right above) with the put points of high curvature and
function of curvature of a contour (from below), with points of the maximal
curvature.

Figure 2. A fragment of a curve Γ with points 𝑃𝑘 and a chord (𝑃𝑖 , 𝑃𝑗 ).

As a result of moving of the chord along the contour the function of curvature
represented on fig. 1 (below) turns out. As characteristic properties of such curve we
shall use a array of values of the greatest an extremum, which are received with use
of function findpeaks() from set Signal Processing Toolbox of package Matlab. For
cutting off of small extremum was using value of some threshold calculated on the basis
of a mathematical expectation and a variance of function of curvature. As a result of
Gostev I. M., Sevastyanov L. A., Melezhik V. S. 35

this operation we shall receive a array of points of coordinates in which contour has the
maximal curvature, as shown numbered points on fig. 1.

3. Process of Identification
For realization of process of identification of object in accounting of invariance to
group of affine transformations it is necessary to consider some factors. Namely, at
presence of noise, change of scale of a contour, and also its turn it is available a variation
of values of extreme points as aside increases, and reduction. In the first case it means
occurrence of new points in a array, and in the second their cutting off. Thus, for
identification of the shape of real object, is complicated because of variations of quantity
of points of extreme in arrays of the sample and current object.
The method has been developed for the decision of the problem identification shape
of object independently of its position on the image (shift), quantities of points of its
contour (scale) and a angle of its turn. The method is similar to metrics of geometrical
correlation [27] and consists in performance of following operations.
First, we shall transform coordinates received on antecedent a step of a array of
extreme points from Cartesian in polar, using as the center of coordinates of polar
system the centre of gravity of object. However in difference from methods of geometrical
correlation [27–29], the present method is based only on use of a array of points of
extreme. Besides as preliminary operation of identification we normalize arrays of object
and the sample concerning their maximal value. Due to these operations, we receive
invariance to shift and scale object and the sample.
Secondly for a statement of a method of identification, we formalize record of set of
points abscises the sample on which we shall make identification in next form.
Definition 1. We shall write down set of points of extreme of function of the sample
𝑓 (𝑡) as 𝐺𝑓 = {𝑎 = 𝑡0 < 𝑡1 < ... < 𝑡𝑙 = 𝑏} where 𝑡𝑖 – angles of turn of values of 𝑓 (𝑡) in
polar coordinates, and set of points of identified object as 𝐺ℎ = {𝑐 = 𝜏0 < 𝜏1 < ... <
𝜏𝑚 = 𝑑} for function of object ℎ(𝜏 ). Let as the quantity of points of the sample will be
more than object, that is 𝑙 > 𝑚, otherwise we interchange the position object with the
standard.
For construction of the metrics of identification we shall add m points to set of the
sample in the following way:
𝐺*𝑓 = {𝑡0 , 𝑡1 , ..., 𝑡𝑙 , (𝑡𝑙+1 = 𝑡𝑙 + 𝑡1 − 𝑡0 ), ..., (𝑡𝑙+𝑚 = 𝑡𝑙 + 𝑡𝑚 − 𝑡0 )} .
That is we shall add in the end of a array its initial fragment from m points.
Definition 2. For some set of points 𝐺𝑓 = {𝑎 = 𝑡0 < 𝑡1 < ... < 𝑡𝑙 = 𝑏} we shall
define its mirror set as 𝐺𝑚 = {𝑏 = 𝑦0 = 𝑡𝑛 > 𝑦1 = 𝑡𝑛−1 > ... > 𝑦𝑛 = 𝑡0 = 𝑎}.
Definition 3. We shall write down two-dimensional function of a difference between
𝑓 (𝑡) and ℎ(𝑡) as 𝜂𝑖,𝑗 = 𝑓 (𝑡𝑖+𝑗 ) − ℎ(𝜏𝑖 ), 𝑗 = 0, (𝑙 − 𝑚), 𝑖 = 0, 𝑚, 𝜏 ∈ 𝐺ℎ , 𝑡 ∈ 𝐺𝑓 .
Definition 4. We shall write down discrete function of an absolute error:
𝑚
1 ∑︁
𝛿𝑗 = |𝜂𝑖,𝑗 | , 𝑗 = 0, (𝑙 − 𝑚).
𝑚 + 1 𝑖=0
And discrete function relative error:
𝑚
1 ∑︁
𝜎𝑗 = |𝛿𝑗 − 𝜂𝑖,𝑗 | , 𝑗 = 0, (𝑙 − 𝑚).
𝑚 + 1 𝑖=0
Definition 5. We shall write down function of recognition for identification of
curves at incomplete data on the basis of correlation on incomplete data #1 (CID1) as
⎧
1, (𝜌𝑛𝑘1 < 𝜀𝑛𝑘1 ) ∨ (𝜌𝑚 𝑛𝑘1 < 𝜀𝑛𝑘1 ),
⎨
𝜆𝑛𝑘1 = (1)
⎩0, (𝜌 ≥𝜀𝑛𝑘1 ) ∧ (𝜌𝑚 ≥ 𝜀
𝑛𝑘1 ).
𝑛𝑘1 𝑛𝑘1
36 APTP+MS’2018

Figure 3. Object “Cross” with adding noise. Its contour and functions of
curvature of a contour with points of maxima curvature

Where 𝜌𝑛𝑘1 = min 𝛿𝑗 the metrics of correlation on incomplete data #1 and 𝜌𝑚
𝑛𝑘1 the
𝑗
metrics of correlation on incomplete data #1, calculated on a mirror data set and 𝜀𝑛𝑘1 –
the classification’s tolerance. Equality 𝜆𝑛𝑘1 = 1 means successful classification object in
relation to the sample, thus value 𝑗 corresponds to a corner of turn of object concerning
the sample.
Definition 6. We shall write down function of recognition for identification of
curves at incomplete data on the basis of correlation on incomplete data #2 (CID2) as
⎧
1, (𝜌𝑛𝑘2 < 𝜀𝑛𝑘2 ) ∨ (𝜌𝑚𝑛𝑘2 < 𝜀𝑛𝑘2 ),
⎨
𝜆𝑛𝑘2 =
⎩0, (𝜌
𝑛𝑘2 ≥𝜀 𝑛𝑘2 ) ∧ (𝜌𝑚 ≥ 𝜀
𝑛𝑘2 𝑛𝑘2 ).
Where 𝜌𝑛𝑘2 = min 𝜎𝑗 the metrics of correlation on incomplete data #2 and 𝜌𝑚
𝑛𝑘2
𝑗
the metrics of correlation on incomplete data #2, calculated on a mirror data set and
𝜀𝑛𝑘2 – the classification’s tolerance. Equality 𝜆𝑛𝑘2 = 1 means successful classification of
object in relation to the sample, and value 𝑗 corresponds to a corner of turn of object
concerning the sample.
Let’s consider examples of identification of simple objects on the basis of the in-
troduced methods. So on fig. 3-4 the object of type “cross” and its deformed value is
represented. The metrics calculated under the formula (1) for these objects is equal
0.0796, and for object “cross” silhouette of plane on fig. 1 – is equal 0.24, that is three
times it is more. Statistical researches of values of metrics between objects various
shapes (sample-nonsample) and one shape, but subjected affine to transformations; differ
at the average three times. Establishing the classification’s tolerance in the middle of an
interval between mathematical expectations of metrics of type the sample-sample and
the sample-nonsample, we shall receive the best results of recognition.
Gostev I. M., Sevastyanov L. A., Melezhik V. S. 37

Figure 4. Object “Cross2” with adding noise. Its contour and functions of
curvature of a contour with points of maxima curvature

4. Discussion
Development represented methods of identification on the basis of metrics of correla-
tion on incomplete data pursues some the purposes.
First, to present a simple method of identification of the shape of the objects,
possessing considerably smaller calculated effort, in comparison with the methods based
on geometrical correlation [27–29]. Here it is necessary to note, that the offered methods
practically non dependent from complexity of the shape of identified objects as suppose
change of "precision of representation” of shape of object due to a choice of a level of
cutting off of extremum of function of curvature and by that accuracy of representation
of the shape of object.
Secondly, in the name of the considered metrics the property supposing absent or
presence of additional extremum arising at function of curvature because of presence
of noise on the input image is incorporated. So, for example, for a figure “krestDm2”,
shown on fig. 5-6 and having on two extreme it is less, value of the metrics between the
given figure and object "cross" has increased approximately from 0.05 till, that makes
less than 1%.
Calculation of the metrics between identical objects, but with is artificial the entered
distortions, for example as on fig. 5-6. At the left in figure object with two smoothed
corners and absent points of extreme, and on the right on the contrary with additional
corners. Values of the calculated metrics equally 0.05, that allows to compare the shape
of the deformed objects stable.
Thirdly, carried out researches show, that the given metrics work not only at presence
affine transformations of identified objects, but also is much wider. So for example
objects, represented on fig. 3-4 only it is informally possible to ranking identical shape
of objects, so not exist groups of the transformations converting one these objects to
another. Nevertheless their human eye will identify as the same object.
The presented methods can be applied in various areas of computer vision and a
robotics, medicine, geology and cartography.
38 APTP+MS’2018

Figure 5. Object “KrestDp2”, with additional corners. Below presented
functions of curvature with points of maxima curvature.

Figure 6. Object “KrestDm2” with two smoothed corners and object. Below
presented functions of curvature with points of maxima curvature.
Gostev I. M., Sevastyanov L. A., Melezhik V. S. 39

Acknowledgments
The publication has been prepared with the support of the “RUDN University
Program 5-100” and funded by RFBR according to the research project No. 18-07-00567.

References
1. F. Y. Shih, Image processing and pattern recognition: fundamentals and techniques,
Published by John Wiley & Sons, New Jersey, 2010 (2010).
2. F. Cao, J.-L. Lisani, J.-M. Morel, P. Mus’e, F. Sur, A Theory of Shape Identification,
Springer-Verlag, New York, 2008 (2008).
3. T. P. Nguyen, I. Debled-Rennesson, On the local properties of digital curves,
International Journal of Shape Modeling 14 (2) (2008) 105–125 (dec 2008).
4. T. P. Nguyen, I. Debled-Rennesson, A discrete geometry approach for dominant
point detection, Pattern Recognition 44 (2011) 32–44 (2011).
5. I. Debled-Rennesson, F. Feschet, J. Rouyer-Degli, Optimal Blurred Segments De-
composition of Noisy Shapes in Linear Times, Comp. & Graphics 30 (2006) 30–36
(2006).
6. P. Bhowmick, B. B. Bhattacharya, Fast Polygonal Approximation of Digital Curves
Using Relaxed Straightness Properties, IEEE Trans. on PAMI 29 (9) (2007) 1590–
1602 (2007).
7. I. E. Sobel, Neighborhood Coding of Binary Images for Fast Contour Following and
General Binary Array Processing, Computer Graphics and Image Processing 8 (8)
(1978) 127–135 (aug 1978).
8. T. Pavlidis, Algorithms for Graphics and Image Processing, Computer Science Press,
Rockville, Maryland, 1982 (1982).
9. I. Anderson, J. Bezdek, Curvature and Tangential Deflection of Discrete Arcs: A
Theory Based on the Commutator of Scatter Matrix Pairs and Its Application to
Vertex Detec-tion in Planar Shape Data, IEEE Trans. on PAMI PAMI-6 (1) (1984).
10. S. Hermann, R. Klette, A comparative study on 2d curvature estimators, in: Pro-
ceeding International conference on computing: Theory and applications, 2007
(2007).
11. D. Chetverikov, A simple and efficient algorithm for detection of high curvature
points in planar curves, in: CAIP 03, 2003, pp. 746–753 (2003).
12. B. Kerautret, J.-O. Lachaud, Curvature Estimation along Noisy Digital Contours by
Approximate Global Optimization, Pattern Recognition 42 (10) (2009) 2265–2278
(2009).
13. R. Deriche, O. Faugeras, 2-D Curve Matching Using High Curvature Points: Appli-
cations to Stereo Vision, in: Proceedings of the 10th International Conference on
Pattern Recognition, IEEE Press, Vol. 1, 1990, pp. 240–242 (1990).
14. M. Worring, A. W. M. Smeulders, Digital Curvature Estimation, CVGIP: Image
Understanding 58 (3) (1993) 366–382 (1993).
15. Digital Curvature Estimation Worring, Marcel. CVGIP: Image Understanding,
Vol. 58 of 3, iSSN: 1077-3142 Online ISSN: 1557-7635.
16. V. Kovalevsky, Curvature in digital 2D images, International Journal of Pattern
Recognition and Artificial Intelligence 15 (7) (2001) 1183–1200 (nov 2001).
17. B. Kerautret, J. O. Lachaud, Curvature estimation along noisy digital contours by
approximate global optimization, Pattern Recognit (42) (2009) 2265–2278 (2009).
18. C. Harris, M. Stephens, A combined corner and edge detector, in: Proceedings of
the Fourth Alvey Vision Conference, Vol. 15, 1988, pp. 147–151 (1988).
19. Xiao, Chen He and Yung, Nelson H. C., Corner detector based on global and local
curvature properties, Optical Engineering 47 (5), 2008 (2008).
20. F. Feschet, L. Tougne, Optimal time computation of the tangent of a discrete curve:
Ap-plication to the curvature, in: Bertrand, G., Couprie, M., Perroton, L. (eds.)
DGCI 1999. LNCS, Vol. 1568, Springer, Heidelberg, 1999, pp. 31–40 (1999).
40 APTP+MS’2018

21. A. Masood, Dominant point detection by reverse polygonization of digital curves,
Image and Vision Computing (26) (2008) 702–715 (2008).
22. V. Begishev, R. Kovalchukov, A. Samuylov, A. Ometov, D. Moltchanov,
Y. Gaidamaka, S. Andreev, An analytical approach to SINR estimation in ad-
jacent rectangular cells, Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 9247
(2015) 446–458 (2015).
23. A. Samuylov, D. Moltchanov, Y. Gaidamaka, S. Andreev, Y. Koucheryavy, Random
Triangle: A Baseline Model for Interference Analysis in Heterogeneous Networks,
IEEE Transactions on Vehicular Technology 65 (8) (2016) 6778–6782 (2016).
24. R. Thakur, Contour Following in Binary Images.
URL http://www.mathworks.com/matlabcentral/fileexchange/
23056-contour-following-in-binary-images
25. Y. Lin, J. Dou, H. Wang, Contour shape description based on an arch height
function, Pattern Recognition 25 (1992) 17–23 (1992).
26. M. Majed, K. Reinhard, S. Pepe, Corner Detection and Curve Partitioning Using
Arc-Chord Distance, in: Combinatorial Image Analysis, Vol. 3322 of Lecture Notes
in Computer Science, 2004, pp. 512–521 (2004).
27. I. M. Gostev, On the Identification of Unclosed Curves, Pattern Recognition and
Image Analysis. (Advances in Mathematical Theory and Ap-plications) 23 (2) (2013)
217–225 (2013).
28. I. M. Gostev, Recognition of graphic patterns: Part I, Journal of Computer and
Systems Sciences International 43 (1) (2004) 129–135 (2004).
29. I. M. Gostev, Contour Fragment-Based Identification of Graphical Objects, Journal
of Computer and Systems Sciences International 44 (1) (2005) 135–142 (2005).