=Paper=
{{Paper
|id=Vol-3027/paper71
|storemode=property
|title=An Approach to Comparing Multidimensional Geometric Objects
|pdfUrl=https://ceur-ws.org/Vol-3027/paper71.pdf
|volume=Vol-3027
|authors=Igor Seleznev,Evgeniy Konopatskiy,Olga Voronova,Oksana Shevchuk,Andrey Bezditnyi
}}
==An Approach to Comparing Multidimensional Geometric Objects==
https://ceur-ws.org/Vol-3027/paper71.pdf
An Approach to Comparing Multidimensional Geometric Objects
Igor Seleznev 1, Evgeniy Konopatskiy 1, Olga Voronova 1, Oksana Shevchuk 1 and Andrey
Bezditnyi 2
1
Donbas National Academy of Civil Engineering and Architecture, Derzhavina Street, 2, Makeevka, 286123,
Ukraine
2
Sevastopol branch of «Plekhanov Russian University of Economics», Vakulenchuk Street, 29, Sevastopol,
299053, Russian Federation
Abstract
The paper proposes an approach to the comparison of multidimensional geometric objects,
which is used to assess the variational geometric models of multifactor processes and
phenomena obtained using the geometric theory of multidimensional interpolation. The
proposed approach consists of two stages, the first of which consists in the discretization of
multidimensional geometric objects in the form of a set of discretely given points, and the
second is in comparing the obtained discrete point sets using a criterion that is essentially
similar to the coefficient of determination. In this case, one of the discrete point sets is taken
as a reference for comparison with another point set. For a correct comparison of
multidimensional geometric models in the form of point equations, which are reduced to a
system of parametric equations, it is necessary to perform interconnection of parameters. A
computational experiment was carried out on the example of comparing geometric models of
the physical and mechanical properties of fine-grained concrete. It showed the possibility of
using the proposed approach for comparing multidimensional geometric objects and the
reliability of the results obtained in comparison with scientific visualization methods. On the
same example, it was found that for an accurate comparison of the investigated geometric
models of the physical and mechanical properties of fine-grained concrete, it is enough to
discretize 100 points. A further increase in the set of discrete points of the compared geometric
objects has no significant effect on the criterion for assessing their similarity.
Keywords 1
Geometric object, comparing multidimensional objects, similarity assessment criterion,
coefficient of determination, discretization, point sets, 3D model, response surface, point
calculus.
1. Introduction
During the development of the geometric theory of multidimensional interpolation [1-3], it was
found that the geometric models of multifactor processes obtained using multidimensional interpolation
are characterized by variability. It is a consequence of the multiplicity of choice of reference lines in
the process of developing a geometric process modeling scheme. Along with the variability of
geometric models of the same process, the problem arose of choosing the optimal model from the
available set of variations. The difficulty of this choice lies in the fact that all possible variations of
geometric interpolants fully satisfy the initial experimental and statistical data, but have different
curvatures between the interpolation nodal points. The solution to this problem led to the need to
compare geometric objects with each other. It turned out that this issue is poorly researched not only in
point calculation [4-5]. The authors managed to find a fairly large array of works [6-7] devoted to the
GraphiCon 2021: 31st International Conference on Computer Graphics and Vision, September 27-30, 2021, Nizhny Novgorod, Russia
EMAIL: i.v.seleznyov@yandex.ru (I. Seleznev); e.v.konopatskiy@mail.ru (E. Konopatskiy); kornilova.oly@mail.ru (O. Voronova);
ks81@rambler.ru (O. Shevchuk); bezdytniy@gmail.com (A. Bezditnyi)
ORCID: 0000-0002-5491-9827 (I. Seleznev); 0000-0003-4798-7458 (E. Konopatskiy); 0000-0003-3740-5151 (O. Voronova); 0000-0002-
9224-0671 (O. Shevchuk); 0000-0003-0528-9731 (A. Bezditnyi)
©️ 2021 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
development of curve matching tools (maximum information coefficient, Frechet distance, Dynamic
Time Warping, etc.), which are used in many applied fields of science and technology, such as time
analysis series, speech recognition, signature verification, etc. All these methods are focused on
matching one-parameter sets of points – lines and have no generalization to multidimensional space,
which could be used to match multi-parameter sets of points. In works [8-9], an approach is proposed
to compare three-dimensional geometric objects (human and mannequin bodies) using stochastic
methods, using form functions. Many articles are devoted to the comparison of 2D and 3D geometric
objects based on various approaches, which include the use of: generate specific distance histograms
that define a measure of the geometric similarity of the inspected objects [10], a probabilistic method
to evaluate 3D surfaces is presented [11], graph matching technique to measure the distance between
these graphs [12], Hausdorff distance (HD) and the accumulated distance difference (ADD) [13], graph
similarity into PPM and similarity measurement based on Topological Relationship Distribution (TRD)
feature [14], a probability distribution function (PDF) produced from spatial disposition of 3D
keypoints, keypoints which are stable on object surface and invariant to pose changes [15], a method of
sequential application of global descriptors, allowing the first stage to produce a "rough" screening of
obviously different objects, and then to apply more accurate algorithms on a significantly reduced object
base [16]. Also, there are a number of review articles devoted to research on the problem of comparing
2D and 3D geometric objects [17]. However, from the works considered, it is not clear whether the
proposed method has a generalization to a multidimensional space and whether it can be adapted for
use in point calculus.
Traditionally, the method of scientific visualization is used to compare geometric objects -
overlapping. However, it is only suitable for comparing one- and two-parameter geometric objects. At
the same time, even a comparison of two-parameter geometric objects encounters a number of
difficulties and the need to use an interactive three-dimensional environment to visualize the
comparison results. Comparison of multiparameter geometric objects belonging to a multidimensional
space causes a number of practically unrealizable problems associated with the complexity of
visualizing geometric objects in multidimensional space. Therefore, it becomes necessary to develop a
criterion for assessing the similarity of geometric objects, which could numerically characterize the
degree of their coincidence with each other, taking into account the prospective use in multidimensional
space.
2. Evaluation of the similarity of multidimensional geometric objects in point
calculus
One of the features of the point calculus is that all geometric objects in the point calculus are
represented by an organized set of points, which are defined using the current point. The current point
fills the space with its movement, thereby forming a geometric object. The current parameter is
responsible for the movement of the current point, which is an invariant of parallel projection and in
most cases varies from 0 to 1. Continuous change of the current parameter within the specified limits
forms a continuous geometric object. However, if you fix a number of values of the current parameter,
then you can select a series of fixed points that belong to the modeled geometric object. When there are
a lot of such points, they can characterize the geometric model with high accuracy. This feature of the
point calculus is proposed to be used to compare several geometric objects, taking into account the
generalization to a multidimensional affine space. A multidimensional geometric object in general form
is determined by the following point equation:
m
M Ai pi u , v, w,..., (1)
i 1
where Ai are the initial points, the coordinates of which, in accordance with the geometric theory of
multidimensional interpolation [1-3], correspond to the initial experimental and statistical data;
pi u, v, w,... are the continuous functions of parameters;
u, v, w,... are the current parameters of the point equation, which in most cases change from 0 to 1;
m is the number of origin points.
Passing from a point equation to a system of the same type of parametric equations, which are
projections of a geometric object on the axis of the global coordinate system, we obtain:
m
x xAi pi u , v, w,...
i 1
m
y y Ai pi u , v, w,...
i 1
m
z z Ai pi u , v, w,...
i 1
.....................................
It is important to highlight one subtlety. The degree of coincidence of multidimensional geometric
objects is determined by the degree of coincidence in all its coordinates. If geometric objects are
explicitly specified by equations (for example, a surface z f x, y ), then by setting the same values
of the variables x and y , it is possible to estimate the degree of coincidence of the surfaces by
comparing the corresponding values of the coordinate z . In our case, there is a system of parametric
equations for which the same values of the parameters can give different coordinates of points that do
not correspond to each other. Therefore, for a correct comparison of multidimensional geometric objects
in point calculus, it is imperative to correlate the parameters of point equations. In some cases, with a
uniform distribution of the initial experimental-statistical data, we can use the special properties of
curves passing through predetermined points, obtained on the basis of Bernstein polynomials, to pass
from a system of parametric equations to an explicit equation. However, the uniform distribution of the
initial experimental and statistical data is a special case and is not always possible in engineering and
scientific practice. On the other hand, if there is such a possibility, then when compiling an experiment
planning matrix, it is better to use a regular multidimensional network of experimental points, which
will greatly facilitate further mathematical processing and analysis of the data obtained.
As noted above, if you continuously change the values of the current parameters in the point equation
(1) from 0 to 1, then we get a continuous multidimensional geometric object. But if the values of the
parameters are taken with any step, then we get a set of discrete points that belong to this geometric
object. For example, for a line that characterizes a one-factor process, using a step of 0.1 for the
parameter u , we get a set consisting of 11 discrete points. If this step is used for a surface that
characterizes a two-factor process, then we get a set consisting of 121 discrete points, etc. Comparing
the obtained sets of discrete points, one can estimate their similarity. Of course, the more points a set
consists of, the more accurately the degree of similarity can be estimated. But if two geometric objects
have very similar shape and position, then for any number of points, the similarity will be very high.
For this, one of the statistical criteria can be used, the most popular of which is the coefficient of
determination in engineering practice.
The coefficient of determination is usually used to estimate the accuracy of a geometric model
obtained using multivariate approximation. It is the ratio of the sum of squared regression residuals to
the total variance:
m
yˆ y
2
i i
R 2 1 i m1 , (2)
y y
2
i
i 1
m
where yˆi yi is the sum of squares of regression residuals, which includes the actual yi and
2
i 1
calculated yˆ i values of the variable under study;
m
y y is the total variance;
2
i
i 1
y is the sample mean.
The coefficient of determination, which is determined by formula (2), can be used as a criterion for
assessing the similarity of multidimensional geometric objects. The values of one point, set (selected as
a reference) are accepted only as actual values, and another as calculated ones. Similarly, other
statistical criteria for assessing similarity can be adapted to compare multidimensional geometric
objects.
3. Computational experiment on the example of comparing geometric models
of physical and mechanical properties of fine-grained concrete
An example of variational geometric modeling of the dependence of the physical and mechanical
properties of fine-grained concrete on the composition of the combined aggregate is given, to study the
effect of the composition of the combined aggregate in the form of open-hearth slag (OHS), granulated
blast furnace slag (GBFS) and burnt rock (BR) on the strength concrete Rst. We will use the proposed
approach to assess the similarity of the obtained geometric models, the variational geometric schemes
of which are shown in Fig. 1.
Figure 1: Variational schemes of geometric modeling of the physical and mechanical properties of
fine-grained concrete from the composition of the combined aggregate
The first geometric model (Fig. 1a) is described by the following system of parametric equations:
OHS1 100u1 1 v1 ,
GBFS1 100v1 ,
R 99, 225v3 198, 45v 2 121, 275v 22,05 u 3 247,05v 3 480,6v 2 279, 45v 45,9 u 2
st1 1 1 1 1 1 1 1 1
184,725v1 341,1v1 177,625v1 21, 25 u1 37,35v1 58,05v1 16, 4v1 6, 4.
3 2 3 2
The first geometric model (Fig. 1b) is described by a similar system of parametric equations:
OHS2 100u2 ,
GBFS2 100v2 1 u2 ,
R 168,075v3 350,325v 2 204,75v 22,05 u 3 336,15v 3 670,95v 2 382,95v 45,9 u 2
st 2 2 2 2 2 2 2 2 2
205, 425v2 378,675v2 194,6v2 21, 25 u2 37,35v2 58,05v2 16, 4v2 6, 4.
3 2 3 2
As a result of an analytical comparison of these two geometric models, it was found that both
response surfaces pass through 10 initial points and can be considered reliable simulation results. But a
comparison of the same models by the method of scientific visualization showed that they are quite
close, but differ from each other in the zones highlighted in red (Fig. 2).
Taking into account the peculiarities of geometric schemes for modeling the physical and
mechanical properties of fine-grained concrete in the form of two-parameter response surfaces (Fig. 1),
which in the plan have the shape of a triangle, it is necessary to correlate the parameters of the systems
of parametric equations:
u2
u1 , v1 v2u2 v2 .
v2u2 v2 1
Figure 2: Comparison of variational geometric models by the superposition method
As a result, the system of parametric equations of the first geometric model (Fig.1a) takes the
following form:
OHS1 100u2 ,
GBFS1 100v2 1 u2 ,
3
1
Rst1 37,35(u2 1)6 v26
u2 v2 v2 1
(184,725u2 1093,725u2 2697,75u2 3548, 25u2 2624,625u2 1035, 225u2 170,1)v2
6 5 4 3 2 5
(247,05u 6 1698,75u 5 4627,1u 4 6461,9u 3 4904,85u 2 1920, 95u 302,6)v 4
2 2 2 2 2 2 2
(99, 225u26 1025,325u25 3525,175u24 5670,125u23 4624, 2u22 1807, 45u2 254,3)v23
(198, 45u2 1156,95u2 2436,15u2 2283,3u2 893,7u2 88,05)v2
5 4 3 2 2
(121, 275u2 446,625u2 545, 475u2 217,325u2 2,8)v2 22,05u2 45,9u2 21, 25u2 6, 4 .
4 3 2 3 2
Next, we will investigate the effect of the discretization of geometric objects on the criterion for
assessing similarity. To do this, we will calculate the criterion for assessing the similarity of geometric
objects for different sizes of a network of discrete points belonging to the modeled geometric object.
The research results are shown in Fig. 3.
0,97
Similarity assessment criterion
0,96
0,95
0,94
0,93
0,92
0,91
0,9
0,89
0 100 200 300 400 500
Number of discretized points
Figure 3: Analysis of the influence of discretization points on the criterion for assessing the similarity
of geometric objects
As can be seen from Fig. 3, the high level of similarity of geometric objects obtained by the method
of superimposing response surfaces is fully confirmed. It should be noted that for a specific example,
after 100 sampled points, the values of the similarity assessment criterion are aligned and no longer
significantly changes, remaining within R 2 0,956 .
4. Conclusion
The criterion for assessing the similarity of multidimensional geometric objects, akin to the
coefficient of determination from regression analysis, is, on the one hand, a universal tool for comparing
multidimensional geometric objects, on the other hand, it has all the disadvantages inherent in the
coefficient of determination. For example, the coefficient of determination provides for comparison
with the averaged value of the reference variable; therefore, the accuracy of its estimation decreases
with a significant scatter of the values of the variable taken as the reference one. And when it is
generalized to a multidimensional space, if there is a significant difference in the order of values on
each numerical axis of the data, it can give unsatisfactory results. This leads to the need for additional
research to develop a criterion for assessing the similarity of geometric objects more adapted to the
multidimensional space (for example, it can be one of the statistical criteria: the chi-square test, the
Kolmogorov-Smirnov test, the Cramer-Mises test, the Bhattachary test, the Kullback divergence -
Leibler, Jensen-Shannon divergence, Hamman coefficient, Jackard coefficient, etc.). At the same time,
the proposed approach, which is based on the discretization of geometric objects for their comparison
both explicitly and parametrically, regardless of the choice of the evaluation criterion, can find wide
application in scientific research in various fields of science and technology.
The proposed approach to comparing multidimensional geometric objects based on the similarity
criterion, akin to the coefficient of determination from regression analysis, can find a worthy place in a
number of existing and innovative approaches not only in multidimensional geometry, but also in
decision making theory. If we consider a multiparameter geometric object of a multidimensional space
as a graphic display of a multi-factor process, then the proposed one can be used to compare many
processes and phenomena in science and technology. It can also be an effective tool for comparing the
reference (exact) solution with the numerical solution of partial differential equations by approximating
the desired solution by geometric objects with predetermined differential properties [18-19]. Another
area of practical application of the proposed method can be a comparison of geometric bodies obtained
in point calculus [20].
5. References
[1] E.V. Konopatskiy, A.A. Bezditnyi, Geometric modeling of multifactor processes and phenomena
by the multidimensional parabolic interpolation method, IoP conference series: Journal of Physics:
Conf. Series 1441 (2020), 012063. doi: 10.1088/1742-6596/1441/1/012063.
[2] E.V. Konopatskiy, A.A. Bezditnyi, Application of mixed geometric interpolants for modeling the
strength characteristics of steel fiber concrete, IoP conference series: Journal of Physics: Conf.
Series 1546 (2020), 012037. doi: 10.1088/1742-6596/1546/1/012037.
[3] E.V. Konopatskiy, A.I. Bumaga, A.A. Bezditnyi, Geometric approach to finding the best possible
solutions based on composition optimization of the mixed aggregate of fine-grained concrete, IoP
conference series: Materials Science and Engineering: Conf. Series 962 (2020), 032031. doi:
10.1088/1757-899X/962/3/032031.
[4] I.G. Balyuba, Constructive geometry of manifolds in point calculus, Kiev, 1995.
[5] I.G. Balyuba, A.V. Naydysh, Point calculus, Melitopol, 2015.
[6] Meinard Müller, Dynamic Time Warping. Dynamic Time Warping. In: Information Retrieval for
Music and Motion, Springer, Berlin, Heidelberg, 2007. doi: 10.1007/978-3-540-74048-3_4.
[7] A. Efrat, S. Venkatasubramanian, Q. Fan, Curve matching, time warping, and light fields: New
algorithms for computing similarity between curves, J. Mathematic Imaging and Vision, 2007.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.5078&rep=rep1&type=pdf.
[8] S.N. Grudinin, Comparison of three-dimensional objects. Similarity assessment criteria, A young
scientist, Volume 1, No. 5(28), 2011, pp. 42–44.
[9] S.N. Grudinin, V.D. Frolovsky, Comparison methods for complex geometric objects, In collection:
Science of technology innovation. Materials of the All-Russian Scientific Conference of Young
Scientists, Novosibirsk State Technical University, 2013, pp. 189–192.
[10] M. Novotni, R. Klein, A geometric approach to 3D object comparison, Paper presented at the
Proceedings - International Conference on Shape Modeling and Applications, SMI 2001, pp. 167-
175. doi: 10.1109/SMA.2001.923387.
[11] J. Pérez, J. Guardiola, A. J. Perez, J. Perez-Cortes, Probabilistic evaluation of 3d surfaces using
statistical shape models (ssm), Sensors (Switzerland), Vol. 20, No. 22, 6554, 2020. doi:
10.3390/s20226554.
[12] K. Madi, E. Paquet, H. Kheddouci, New graph distance for deformable 3D objects recognition
based on triangle-stars decomposition, Pattern Recognition, Vol. 90, 2019, pp. 297-307. doi:
10.1016/j.patcog.2019.01.040.
[13] P. Peltola, J. Xiao, T. Moore, A. R. Jiménez, F. Seco, GNSS trajectory anomaly detection using
similarity comparison methods for pedestrian navigation, Sensors (Switzerland), Vol. 18, No. 9,
2018. doi: 10.3390/s18093165.
[14] R. Wen, W. Tang, Z. Su, Measuring 3D process plant model similarity based on topological
relationship distribution, Computer-Aided Design and Applications, Vol. 14, No. 4, pp. 422-435,
2017. doi: 10.1080/16864360.2016.1257185.
[15] V.K. Ghorpade, P. Checchin, L. Malaterre, L. Trassoudaine, 3D shape representation with spatial
probabilistic distribution of intrinsic shape keypoints, Eurasip Journal on Advances in Signal
Processing, Vol. 2017, Issue1, 2017. doi: 10.1186/s13634-017-0483-y.
[16] A.V. Pristupa, I.L. Lapatin, A.V. Zamyatin, 3D object identification based on global shape
descriptors, Tomsk State University Journal of Control and Computer Science, No. 48, pp. 57-66,
2019. doi: 10.17223/19988605/48/7.
[17] G. Lara López, A. Peña Pérez Negrón, A. De Antonio Jiménez, J. Ramírez Rodríguez, R. Imbert
Paredes, Comparative analysis of shape descriptors for 3D objects, Multimedia Tools and
Applications, Vol. 76, Issue 5, pp. 6993-7040, 2017. doi: 10.1007/s11042-016-3330-5.
[18] E.V. Konopatskiy, O.S. Voronova, O.A. Shevchuk, A.A. Bezditnyi, About one method of numeral
decision of differential equalizations in partials using geometric interpolants, CEUR Workshop
Proceedings, Volume 2763, 2020, pp. 213–219. doi:
10.30987/conferencearticle_5fce27708eb353.92843700.
[19] E.V. Konopatskiy, A.A. Bezditnyi, O.A. Shevchuk, Modeling geometric varieties with given
differential characteristics and its application, CEUR Workshop Proceedings, Volume 2744, 2020.
doi: 10.51130/graphicon-2020-2-4-31.
[20] E.V. Konopatskiy, A.A. Bezditnyi, M.V. Lagunova, A.V. Naidysh, Principles of solid modelling
in point calculus, IoP conference series: Journal of Physics: Conf. Series 1901 (2021), 012063.
doi: 10.1088/1742-6596/1901/1/012063.