Застосування теорії балок для побудови плоских двічі диференційованих замкнутих кривих за неточними дискретними даними
The smoothing of measured noisy positions of discrete points has considerable significance in various industries and computer graphic applications. The idea of work consists of the employment of the technique of beam with spring supports. The local coordinates systems are established for beam straig...
Saved in:
| Date: | 2022 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | English |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2022
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/257192 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866302814640144384 |
|---|---|
| author | Orynyak, Igor Koltsov, Dmytro Chertov, Oleg Mazuryk, Roman |
| author_facet | Orynyak, Igor Koltsov, Dmytro Chertov, Oleg Mazuryk, Roman |
| author_sort | Orynyak, Igor |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2023-05-21T20:04:38Z |
| description | The smoothing of measured noisy positions of discrete points has considerable significance in various industries and computer graphic applications. The idea of work consists of the employment of the technique of beam with spring supports. The local coordinates systems are established for beam straight line segments, where the initial angles between them are accounted for in the conjugation equations, which provide the angular continuity. The notions of imaginary points are introduced, the purpose of which is to approach the real length of the smoothed contour to the length of the straight chord. Several examples of closed denoised curve reconstruction from an unstructured and highly noisy 2D point cloud are presented. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2022.4.10 |
| first_indexed | 2025-07-17T10:27:49Z |
| format | Article |
| fulltext |
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk, 2022
Системні дослідження та інформаційні технології, 2022, №4 119
UDC 519.652
DOI: 10.20535/SRIT.2308-8893.2022.4.10
APPLICATION OF BEAM THEORY FOR THE CONSTRUCTION
OF TWICE DIFFERENTIABLE CLOSED CONTOURS BASED
ON DISCRETE NOISY POINTS
I. ORYNYAK, D. KOLTSOV, O. CHERTOV, R. MAZURYK
Abstract. The smoothing of measured noisy positions of discrete points has consid-
erable significance in various industries and computer graphic applications. The idea
of work consists of the employment of the technique of beam with spring supports.
The local coordinates systems are established for beam straight line segments, where
the initial angles between them are accounted for in the conjugation equations,
which provide the angular continuity. The notions of imaginary points are intro-
duced, the purpose of which is to approach the real length of the smoothed contour
to the length of the straight chord. Several examples of closed denoised curve recon-
struction from an unstructured and highly noisy 2D point cloud are presented.
Keywords: spline, elastic beam, spring support, closed contour, imaginary point,
noisy data.
INTRODUCTION
Two cases are discerned at geometrical computer modeling of plane curves or
closed contours – their design or restoration from the set of measured points. In
each case the provision of the curves smoothness is a necessary requirement of
their construction.
During geometrical design the important prerequisite is an aesthetical appeal
and 2C continuity of a curve. The most popular are the methods which are based
on the Bezier curves, rational Bezier curves, B-splines and rational B-splines, or
so-called NURBS curves [1]. For their construction it is needed to define the
enumerated system of so-called control points. These curves pass exactly through
the first and last points, while all other points are only attracting the curve to
themselves. To increase or decrease the “weight” of attraction of the given control
point the rational splines are applied.
The problem of restoration of closed curves from the noise points has a big
significance in a computational geometry. It is applied in image analysis, in re-
verse engineering, for restoration of the trajectories and forces acting on the mov-
ing material points, etc. [2]. As an example, mention the extraction of silhouettes
from sensed depth images.
Very often the restoration of the geometry is performed by fitting the points
for the prescribed analytical figure (circle, ellipse, helix) with unknown character-
istics, orientation and center of coordinates. In this case the functional of error
(sum of deviations) is specified, which usually is iteratively solved by least square
method [3]. When the number of points is too big it is necessary to perform the
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 120
preliminary smoothing. Then the weighting Gaussian probability function is usu-
ally applied, which makes the closer positions of the considered points [4]. Yet its
application might lead to unpredictable loss of the useful information (over
smoothing). Furthermore, the drawback of similar techniques is that the real noise
of input points (mean deviation) is not taken into account, even if it is known in
advance [4].
Historically the first splines which exactly pass through the given measured
points were solutions based on the Strength of Materials beam technique [5] and
actually used the known equation of three moments [6]. To decrease the deviation
of the curves from the given points it was suggested to use the solutions for ini-
tially pre-tensed beams [7]. Later on, the theory of beam splines was supple-
mented by possibility to use the elastic springs (supports) placed in the points
of measurements. The increase in compliance of these springs lead to larger
smoothing of the resulting curve [8].
The most drawback of all beam based smoothing techniques is that the curve
is presented in unique global coordinate system, i.e., the solution of kind
( )y f x is searching for. Sush presentation can be effective for drawing the sta-
tistical splines, where the independent variable x is determined exactly, while the
functions y can be presented in any scale. For geometrical splines both coordi-
nated has the similar meaning and both are determined with errors. Usual ap-
proach is a parametrical presentation of both coordinates and execution the inde-
pendent smoothing with respect to each coordinate.
Significant contribution to application of the theory of beams to the geomet-
rical smoothing are works of present authors [9, 10], where the initial straight
segments between the neighboring points predetermine the local coordinate and
vector basis which are adjacent to each other at a certain angle. Namely, the goal
of the beam deformation was the smoothing of these angles [9, 10]. Note, that
idea of application of initial straight segments and their vectorial basis is the main
one in so-called corotational approaches in geometrical nonlinear analysis of the
spatial beams, when the position of the deformed geometry is essentially deviate
from the initial one [11].
The peculiarity and main idea of given work consists in that beam spring
splines are calculated iteratively with accounting for the big deviation and change
of local basis vector system (tangent and normal) [12]. Besides the notion of ficti-
tious points is introduced here which are not related with the real (measured)
points. These points are placed on calculated contour between the real points for
decreasing the angle between the neighboring segments.
GOVERNING EQUATIONS
Consider the simplest model of the bending deformation of beam, so called Euler-
Bernoulli beam [6], its equations and parameters. Beam is described by the gener-
alized vector of state )(sY
, which characterized by set of four parameters at each
local point of length coordinate s , i.e., )}();();();({)( sQsMssWcolumnsY
.
Here, instead of some function and its derivatives, as usually accepted in mathe-
matics, the following conventional parameters of the theory of beam are used. So,
Application of beam theory for the construction of twice differentiable closed contours …
Системні дослідження та інформаційні технології, 2022, № 4 121
we operate by notions of: )(sW is the deviation or displacement, the positive
value of which is directed toward the normal; )(s is the angle of rotation, the
positive direction coincides with rotation from the tangent vector to normal one,
i.e., is in clockwise direction; )(sM is the bending moment; )(sQ is transverse
force. Their positive directions are chosen in such manner that in all differential
equations the sign «+» is used. Thus, the following dependences between the
beam parameters are used:
mq
ds
sdQ
sQ
ds
sdM
EI
sM
ds
sd
s
ds
sdW
)(
);(
)(
;
)()(
);(
)(
,
where is given outer distributed force, EI is so called rigidity of the beam
section. The solution of the system of governing equations is presented in form
suitable for application of transfer matrix method, and is the following:
s
s
EI
s
EI
s
qY
s
EI
s
EI
s
EI
s
EI
s
s
sY m
2
6
24
)(
1000
100
2
10
62
1
))((
2
3
4
0
2
32
, (1)
where )0(0 sYY
is the vector of state at initial point of the segment. Note that
here we take that 1EI , and 0mq .
The set of measured positions of enumerated points ),( bibii YXB is a re-
quired input information, thus each point has number i , it is characterized by two
coordinates position which are measured with some error characterized by some
prescribed statistical deviation .
At each iteration number, j , the geometry of analyzed curve is presented as
a set of points ),( j
i
j
i
j
i YXA , where each point j
iA is related with initial point iB
with the same index i . Note, that before first iteration the positions of points
0j
iA coincide with those of measured points iB . Usually, we will omit the upper
index j in designation of points iA . Consequent points iA are connected by
straight segments. These segments form certain angles between themselves,
ii ,1 , the positive directions of which is counted clockwise (Fig. 1). Thus, the
beginning and end of each segment i , at each iteration, j , have some positions,
which coincide with positions of points iA (Fig. 1). The vectorial length of each
segment is denoted as iL
:
jYYiXXAAL iiiiiii
)()( 111 .
Each of these segments is related with local tangent vector it
and normal
vector in
, which is rotated clockwise with respect to former one. Thus, if the tan-
gent vector it
is given by:
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 122
const jbia
L
L
st ii
i
i
i
.
Then normal vector in
is found from the expression:
const)( jaibjdicsn iiiii
.
The important constituent of the modelling is accounting for the angle be-
tween two segments, name it as a misalignment angle. It must be smoothed at the
next iteration. This angle is denoted as ii ,1 , and its direction is clockwise,
Fig 1, and calculated by the formulas of the vector and scalar products of the unit
vectors:
11, *)(sin iiii tt
; 11, )(cos iiii tt
.
We use both definitions of angle to get the correct values of it in each quad-
rant of the coordinate system. Note, that if both signs are positive, then angle lies
in first quadrant, if both are negative – in third quadrant, and so on.
Formulate the main parameters, unknowns and equations which will be used
in calculation.
Introduce the following designations for main parameters (unknowns at each
iteration). At each segment, i , introduce the vector of state in initial point, thus
)0(0, sYi
, and vector of state at the last point of segment, thus )(, iei ssY
. Evi-
dently, these two vectors of state are related by Connection equations (1), at
ii Lss
.
The peculiarity of given approach consists in consideration of initial noisy
points as the fixed positions of elastic supports, where the additional force of in-
teraction is proportional to the deviation of the position of the contour point iA
from the support point iB . This deviation is determined before the next iteration
and designated as i . Other peculiarity consists in accounting for the angle of
Bn+1
An+1
n+1
An-1
tn-1
nn-1
n
An
Bn
nn tn
n+1
Bn-1
Fig. 1. The model of discrete beam segments on elastic springs (supports)
Application of beam theory for the construction of twice differentiable closed contours …
Системні дослідження та інформаційні технології, 2022, № 4 123
misalignment [10]. So, additionally to the Connection equations, write the Conju-
gation equations, which relate the vectors of state at the end of previous segment
with that at the beginning of the next one:
1,0 ,1i iW W ; (2)
1,1,0,1 iiii ; (3)
1,0 ,1i iM M ; (4)
)( 1,1,0,1 iiiii WCQQ , (5)
where iC is the rigidity of support (characteristic of spring), and i is some
conditional distance, the value of which before the first iteration is taken as
0i .
Equation (5) can lead to some computational errors when iC is a very big.
As alternative presentation of (5) we use relation
)()( 1,0,11, iiiii QQDW , (6)
where the notion of the support’s compliance iD is introduced, which is inverse
to the rigidity 1 ii CD .
Comment these equations. First one (2) is intended for that displacements
(positions) at the border between two segments should be equal — 0C continuity.
Second one (3) is intended for that angle of tangent to the next segment should be
on value of 1, ii lesser than the angle of tangent at the end of the previous one –
actually this gives the angle continuity requirement of the deformed contour —
1C continuity. Third condition (4) is a condition of continuity of second deriva-
tives. The values of calculated 1,iW and i , the latter is being determined before
each iteration by the special procedure, have the signs. The positive sign means
that value is directed toward direction of vector in
. Note that at intermediate val-
ues of iD and iC the equations (5) and (6) are equivalent. If 1iC , then equa-
tion (6) should be used, which in limit case of iC , or 0iD , actually leads
to equation: ,1 .i iW Similarly, there are no restrictions in applying of (6),
when 0iC , or iD , then equation (5) will be reduced to 1,0 ,1i iQ Q .
Thus, if the whole number of measured points is equal to N , then we intro-
duce N segments (the last one for closed contours connect the point i N with
point 1i ). This means that at whole we have NN 8*4*2 unknowns (two
sets of four ones at the beginning and at the end of each segment). For determina-
tion of them there are N sets of Connection equations (1), thus 4N ones at the
whole, and similarly 4N Conjugation equations (2) – (5).
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 124
MAIN IDEA OF ALGORITHM
Describe the procedure of consequent rebuilding of the smoothed contour at each
iteration. The main result of calculation is deviation of points iA from the previ-
ous positions, and they are designated as iW
. According to Conjugation require-
ment (2):
1,0 ,1i i iW W W
.
Yet, evidently the displacements of beam, W s are directed toward the
normal to each straight segment, which are different for two adjacent segments.
Thus, the vectorial displacements 1,0iW
and ,1iW
are different:
1,0 1,0 1 ,1 ,1i i i i i iW W n W W n
.
To provide the 0C continuity of deformed contour we make the following
original enhancement: namely, introduce the notion of continuous normal vectors
to the calculated deformed geometry. They are derived by rotation of initial nor-
mal vectors on the calculated angle of deformation )(si . We name them as de-
formed normal, denote them as 1in and calculate by the following formula:
jsdiscstsnsn iiiii
)()()(sin)(cos)( , (7)
where
i
i
i
i
b
a
ss
ss
sd
sc
))(2/(cos))(2/(sin
))(2/(sin))(2/(cos
)(
)(
.
Evidently, that due to condition (3) the deformed normal are continuous
along the whole contour including the borders between adjacent elements, i.e.
)()0(1 iii ssnsn . Then treating the calculated vectorial displacements
as )()()( snsWsW ii
, we get that positions of two adjacent border points j
iA
will be continuous.
Accounting for continuity of displacements )(sW and angle of deformation
)(s calculate the position of each inner point of segment )(sR j
i
, which is pre-
sented as the sum of initial position and calculated deformed position:
)()()( 1 snsWstAsR ii
j
i
j
i
. (8)
Thus, formula (8) is a main formula to determine the positions of all points
after each iteration. It may happen, that derived figure satisfy the requirements to
the smoothed contour and we can stop the calculations immediately. But if the
derived contour does not satisfy to the requirements, we have two options. First is
a trivial one. We can start again the procedure from the first iteration, where
0j
i iA B , but different value of rigidity iC can be chosen: the smaller it is, the
Application of beam theory for the construction of twice differentiable closed contours …
Системні дослідження та інформаційні технології, 2022, № 4 125
smoother contour will be. This option is applicable when the deviation of measured
points is small as compared with distance between them.
More complicated is the second option which requires the creation of addi-
tional refining procedures, and which is the main objective of our analysis. Con-
sider that first iteration is already performed at initial (big) values of iC , take
them to be of the same value and designate as SC . This results in derivation of
new positions of points iA . Connect these points, form new segments and derive
new angles of misalignments. Take other (smaller) values of sC and perform the
next iteration.
Important to evaluate whether the given value of sC is big or small. Evi-
dently the value of sC can be considered as a small one, when the calculated dis-
placements W are small as compared with segment length. Theory of beams [6]
states, that following property characterizes the dimensionless rigidity of spring,
EI
LC
C s
s 6
3
. The spring is rigid if 1sC , and is flexible if 1sC . Thus, we ini-
tially chose some approximate mean value of length of all segments, L , and then
we chose some initial big value of the rigidity, for example, 400sC . Then real
sC is calculated as
ss C
L
C
3
6
,
because 1EI .
To complete the preparation for the next iteration it is necessary to find the
preliminary force of the spring tension, which is characterized by some condi-
tional distance i . If consider i as the absolute distance between points iB
and iA
, then some collisions could occur. It may happen that some point iB
lays
on (or is very close to) the new contour, but is situated very far from related cal-
culated point iA
. In such treatment: a) the value of i could be big, thus the
large preliminary force will arise, although point iA
is very close to contour; b) it
is not possible to define the sign of i (“+” or “-”), which would lead to unpre-
dictable results at the next iteration.
Then, value of i is defined as the shortest distance from point iB
for both
segments 1i iA A
and 1i iA A
with accounting for their signs. These two distances
are designated as i1 and i2 , and are determined as: iiii nBA 11
; and
iiii nBA 2
. The smallest by module of them is chosen as i with accounting
of its sign, so i is taken with sign «+», if point iB is situated at the right side
from the respected segment and «-» otherwise.
Some cases of choosing the value of i are shown on Fig. 2.
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 126
REFINEMENT OF LENGTH AND CURVATURE AND IMAGINARY POINTS
Before j -th iteration we operate only by the positions of border points 1j
iA . The
main result of calculation at j -th iteration is position of each point s , where
0 is s , of the segment (8). Analyze the change of length of infinitely small
straight element s of the segment after deformation. Rewrite the expression (8)
with accounting for (7):
)()()( 111 sYnsXtAsR j
i
j
i
j
i
j
i
, (9)
where
))(sin)(()( ssWssX , )(cos)()( ssWsY .
These formulas give the position of each point s . Accounting for known
formula of differential geometry get the deformed length and curvature at each
point s . Write the auxiliary expressions which are derived by differentiation
of (9):
)()(cos)()(sin)(1)( ssxWssWsX ;
)()(sin)()(cos)()( sssWssWsY .
They allow to find elongation, )(s , (relative change of length) of each point s :
22 )()()( YX
s
s
s d
,
where ds is the deformed length of initial element s . The curvature, )(sd , of
the curve (9) in each point is given by known expression:
33
22 ))((
)()(
)(
¨¨¨¨
s
XYYX
YX
XYYX
sd
(10)
Bn-1
Bn+1
An
Bn
2
1
Bn+1
Bn+1
An
2
1
a b
Fig. 2. Some cases of finding the distances from control point A to two straight segments:
a — one distance is positive and other is negative; b — both distances are positive
Application of beam theory for the construction of twice differentiable closed contours …
Системні дослідження та інформаційні технології, 2022, № 4 127
Expand the components of numerator (10) with accounting for known dif-
ferential dependences (1):
)()(cos)(2)(sin)()(
¨
sMssssMsX
)(cos)())()((sin)( 2 sQsWsMssW ; (11)
)()(sin)(2)(cos)()(
¨
sMssssMsY
)(sin)())(()(cos)( 2 sQsWsMssW . (12)
So, expressions (10) together with (11) and (12) allow to find the real curva-
ture of curve (9).
Now introduce the notion of imaginary points. Theory of beams is based on
assumption that calculated angles are small, i.e., tgsin . If the number of
points iA is small, then misalignment angles are large (Fig. 1). Thus, calculated
angles are also large which lead to some inaccuracy. To decrease these angles of
misalignment it is suggested to introduce the imaginary support points. These
supports have zero rigidities 0iC . Nevertheless, the number of segments be-
comes larger and angles of misalignments become smaller. In details, this crucial
idea of the method will be illustrated on testing examples.
RECOVERY OF FIGURES FROM EXACTLY MEASURED POINTS
Example 1. Start with example when several points of the circle are given
exactly. Let we have four points )1,2( 111 yxB ; )1,2(2B ; )1,2(3 B ;
)1,2(4 B . Evidently, they are situated on the circle of radius 236.25 R ,
thus the curvature is equal to 4472.0 .
When all points are given exactly (imaginary points are not exact) there is no
necessity to perform the iteration procedure, because the result is obtained at
once. The fourth Conjugation equation is used in form: 01, iW .
The calculation results are shown on Fig. 3. Due to small number of input
points the calculated figure is not continuous. This relates to the tangent 1C and
curvature (moment) 2C continuity. The calculated values of moment (curvature)
are constant and equal to 5235.0 , which is 17% higher than accurate value
(Fig. 3, b). Note, that axis of abscise is related with the lengths of initial straight
segments, formed by 4 input points and the whole length is equal to 4+2+4+2=12.
The above values of 5235.0 is the formal solution by the beam theory. The
real curvatures are calculated by formulas (10). The graph of real curvatures is
shown on Fig. 3, c, which extremal values notably differ from exact and beam
ones.
To improve the results, employ the idea of imaginary points. Introduce one
imaginary point at the middle of each calculated graph section between two real
points (Fig. 3, a). Denote them as 21B , 32B , 43B , 14B . Determine their
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 128
coordinates. Connect consequently points 1B , 21B , 2B … 4B , 14B , 1B and get
the new graph for eight initial points (Fig. 4).
As we see the contour is more smooth, angular misalignments are almost in-
visible. The calculated beam curvatures are equal to 0.4773, which are 6.7%
higher than exact ones. Yet the extremal geometrical curvatures given by formula
(10) are still in 1.5 times higher than accurate value.
Therefore, insert additional 24 imaginary points – 3 points between the al-
ready used points – real and imaginary ones (Fig. 4). So, at the whole we get 4
real and 28 imaginary points. The results of calculation are shown on Fig. 5. The
beam curvatures coincide with exact one (Fig. 5, b). The real curvatures after 3rd
iteration are shown on Fig. 5, a. In this case they better correspond to the exact
ones and the difference does not exceed 2%.
One may get the false impression that the accuracy of reproduction of
calculated contour is related to the accuracy of preliminary placement of imagi-
nary points. To show that crucial is only the fact of their insertion rather than
place of placement, make the following test. Consider the contour obtained from
1 —
2 —
1
2
a b
Fig. 3. Recovery of circle from 4 exactly measured points given as the vertices of the
rectangle: a — calculated figure; b — beam and geometrical curvatures
1 —
2 —
1
2
a b
Fig. 4. Recovery of circle by four exact points and four imaginary ones: a – restored
graph; b – recalculated curvatures by formula (10)
Application of beam theory for the construction of twice differentiable closed contours …
Системні дослідження та інформаційні технології, 2022, № 4 129
32 points (4+28), Fig. 5, a. For convenience consequently renumerate them start-
ing from real point 1B . Artificially shift points N4, N14, and N26 outwardly, as
shown on Fig. 6, a. From these points, we will form an initial polygon, which is
the initial input geometry.
The calculated contours for some iterations are shown on Fig. 6. In particu-
lar, after first iteration the contour contains local loops, Fig. 6, b. After second
iteration the contour resemble a slightly oval contour, Fig. 6, c. The contour be-
come better with each subsequent iteration and after 6th iteration it is almost indis-
cernible from the ideal circle. After 9th iteration the correctly calculated curvatures
are very close to the exact ones and differ with them only by 1–2%. Thus, availability
of 32 points (real or imaginary) is almost enough to get the ideal circle. This
means, that in overage 360 / 32 12 (and lesser) angular misalignment can be
effectively smoothed by our modified beam approach.
Example 2. Consider the circle formed by unevenly placed points. In prac-
tice the measurements are often performed with some restrictions, when the avail-
able to measurements is only some segment of the circle. Set three points (Fig. 7),
namely )2/1,2/3( 111 yxB ; )1,0(2B ; )2/1,2/3(3B . Evidently these
points belong to the circle of radius 1, and curvature is also 1. Note, that these
points embrace only the 1/3 of the full circumference. Due to unevenness of their
placement, the angular misalignments between the straight segments are: between
the first and second ones – angle is 60 , between second and third - 120 , and
third and first ones – 120 . When the angle is larger than 90 , the sense of beam
theory is lost – angle does not only essentially differ from its tangent, but they
have the different sighs. Therefore, from the start insert only one imaginary point,
for example, )5,0(13 B . The results are shown on Fig. 7. Evidently, the contour
contains the loop and do not resemble the circle at all.
Consider the calculated contour Fig. 7, b as initial one, and insert between
the real points 1B and 2B and point 2B and point 3B 15 additional imaginary
points, also insert 26 points between the points 3B and point 13B , the same is
between 13B and 1B . The calculation is performed at several iterations, until the
a b
Fig. 5. Recovery of circle by 4 real and 28 imaginary points: a — calculated graph;
b — recalculated curvatures by formula (10)
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 130
stabilization of the geometry (Fig. 8). The derived geometry, which contains 3
real and 83 imaginary points, is very close to the ideal circle, Fig. 8, a. As to
beam curvatures they differ only by 0.1% from exact ones, while the geometrical
curvatures are slightly worse – the difference reach up to 0.3%.
a b
c d
e f
Fig. 6. Recovery of circle from 4 real and 28 imaginary points, three of which were es-
sentially shifted: a — initial placement of points; b — contour after 1st iteration; c —
after 2nd iteration; d — after 6th iteration; e — after 9th iteration; f — calculated by (10)
curvatures after 9th iteration
Application of beam theory for the construction of twice differentiable closed contours …
Системні дослідження та інформаційні технології, 2022, № 4 131
Example 3. Here we consider a more complicated figure – ellipse. In con-
trast to the circle, its curvature is not a constant. So, it is interesting to explore the
ability of the method to restore the figures with variable curvature. Use the equa-
tion of ellipse with respect to parameter , where the coordinates of any point are
given by equations: )(cos*2 x and )(sin*1 y . The curvature of ellipse is
given by the following expression:
3
2222 ))()(cos(
*)(
baa
ba
. (13)
Note, that in point 0 2)0(
2
b
a
, and value of
4
1
)2/(
2
a
b
. So,
the curvature changes in 8 times within the range of 90 degrees.
Generate 40 points (10 points for each quadrant), between which the curva-
ture changes proportionally, i.e., in 10 8k times. These points (their parametric
values of i ) are easily generated from equation (13). Fig. 9 shows the positions
Fig. 8. Recovery of circle from 3 real points and 83 imaginary ones: a — calculated con-
tour; b — beam and geometrical (10) curvatures
a b
Fig. 7. Recovery of the circle from 3 real points placed at the upper part of circle and one
imaginary point: a — input point; b — calculated contour with loop
a b
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 132
of 40 generated ellipse points and corresponding calculated contour and its beam
and geometrical curvatures. In general, we see a very good correspondence, with
the exception of points which lays on axis x , where the real curvature is the
largest. Here the deviation of geometrical curvature from the exact one at-
tains 10%. Of course, these results can be improved by taking more input points
in the vicinity of point 0 . Yet, in general, the results are very optimistic, even
for figure with quickly changing curvature.
RECOVERY OF THE CIRCLE FROM NOISY POINTS
Example 4. Consider again the ideal circle of radius 1. Take 40 evenly distributed
points on it. Then add the noise to each coordinate of point ( X and Y ) according
to uniform continuous distribution with random parameters ranged from lower
boundary 3.0a to upper boundary 3.0b . The noise is characterized by theo-
retical statistical deviance:
32
)( ab
theor
.
So, in our case 173.0theor .
The input random points are given in Table .Their sequence does not resem-
ble the ordered one, where each next enumerated point is placed in clockwise di-
rection from the previous one. So, their placement sometimes looks as chaotic
one, which complicates the calculations. The results of calculations are shown on
Fig. 10. A large number of closed loops are formed at first iteration. Then, with
decreasing of the spring rigidity their number decreases, and the reason is the
overlapping of the points which form the loops. The loops are completely
unraveled at 15th iteration when 473.0C . With subsequent iterations the con-
tour more and more resembles a perfect circle. The calculations are ceased at 40th
iteration when 51033.3 C .
Fig. 9. Recovery of ellipse from exactly placed discrete points: a — input points and
calculated contour; b — graph of exact curvature of ellipse and its calculated beam and
geometrical curvatures
a b
Application of beam theory for the construction of twice differentiable closed contours …
Системні дослідження та інформаційні технології, 2022, № 4 133
Introduce the notion of conditional empirical calculation deviance, emp ,
i.e., root mean square deviation of input points iB from the calculated contour,
which we approximately define by formula
Рис. 10. Recovery of circle from 40 noised points generated by uniform distribution law
with an extremal deviation equal to 30.0 : a — input points and contour at 1st iteration;
b — contour after 5th iteration, 66.21C ; c — after 12th iteration, 49.1C ; d — after
15th iteration, 47.0C ; e — after 40th iteration 51033.3 C ; f — the beam and geo-
metrical (10) curvatures after 40th iteration
a c
c d
fe
ba
dc
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 134
Generated 40 random points with respect initial 40 evenly chosen points on
the circle
N X Y N X Y N X Y N X Y
1 0.9616 0.0000 11 0.0727 -1.2507 21 -0.9969 0.0611 31 -0.0193 0.8941
2 0.7032 0.0773 12 -0.1389 -1.0679 22 -1.2485 0.3154 32 -0.0225 0.8435
3 0.9809 -0.4040 13 -0.5283 -0.7405 23 -0.9942 0.1106 33 0.3933 0.8832
4 0.8522 -0.4137 14 -0.4458 -0.9472 24 -1.1331 0.3298 34 0.4438 1.0902
5 0.7612 -0.6313 15 -0.7771 -1.0927 25 -1.0327 0.6022 35 0.5909 0.9511
6 0.6053 -0.7451 16 -0.5359 -0.8588 26 -0.6491 0.6211 36 0.6392 0.6346
7 0.4106 -0.6431 17 -0.5966 -0.8475 27 -0.7522 0.5364 37 0.9852 0.2956
8 0.5256 -0.8696 18 -0.8945 -0.1577 28 -0.6898 1.1809 38 0.9390 0.6324
9 0.1888 -0.6788 19 -0.7431 -0.0267 29 -0.4768 0.9159 39 0.7484 0.1707
10 0.0165 -0.9612 20 -1.2399 0.0237 30 -0.2465 0.9901 40 1.1081 0.2060
N
i
N
emp
2
1
. (14)
Calculate this value by formula (14) at the last (40th) iteration. Empirical
deviation is equal to 151.0emp , which is very close to the theoretical
deviance. Such good correspondence is due to the big number of input points, and
that conditional distance i reflects the essence of the distance to the contour.
Underline, that above example illustrates that attained empirical deviance at the
given iteration emp can be used as a condition of termination of smoothing
process, provided that theoretical deviance is known.
EXTRACTION OF SILHOUETTES FROM NOISY POINTS [4]
Example 5. The problem of recovery of silhouettes from noisy dense points was
considered in work [4]. Among other, this work is remarkable that it gives a lot of
sets of artificially generated random points from continuous silhouettes, yet the
original silhouettes were not provided. Unknown is also the principle of the ran-
dom points generation. In the title of respected files, which were supplemented to
work [4], there are some numerical values of errors which can be treated as devi-
ance of input points. Other problem with these data is the numeration of points.
Our method works with numerated points and does not change their numeration.
But as is shown in Example 4 when points are very dense noisy, the renumeration
is desirable. Yet, in this work we will not apply the renumeration procedure, to
show that our method is very effective even without it.
Consider first figure from work [4] — butterfly. Input noisy data are given in
the file (butterfly_2percent_noise.txt”), where 164 points are presented. The men-
tioned in the file name noise is given in percent. Due to that all pictures are given
in absolute coordinates which range approximately from 0.5 to 0.5 as for x
as for y , thus we assume that deviance was calculated relatively to the value of
0.5. Thus, we take that theoretical deviance is equal to 01.05.002.0theor .
Application of beam theory for the construction of twice differentiable closed contours …
Системні дослідження та інформаційні технології, 2022, № 4 135
The results of calculation are given on Fig. 11. Initial input points are
presented on Fig. 11, a. The results of calculation after 1st iteration are shown
on Fig. 11, b, where three local loops are presented, and the empirical deviance is
Fig. 11. Recovery of contour of butterfly based on input points given in [4]: a — initial
points; b — contour after 1st iteration; c — after 15th iteration, 64.1C ; d — after 20th
iteration, emp ≈ 0. 010 , 377.0C ; e — after 30th iteration, f — returning to the same
rigidity as at 20th iteration, emp ≈ 0. 010
a b
e f
c d
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 136
very small and equal to 00029.0 emp . After 15th iteration the contour still has
one small loop (at the left side of picture) and calculated deviance becomes
00672.0emp , which is less than assumed theoretical value. Interesting to no-
tice, that the contour doesn't look smooth enough. At 20th iteration ( )377.0C ,
the calculated value 01060.0emp , which is very close to the criterial value.
Yet the contour still contains one local loop; to unravel it perform the several
additional calculations. At 30th iteration 01378.0emp , which is larger than
theoretical one, which testifies about the oversmoothing of the contour, what is
subjectively visually confirmed. It is interesting to note, that we can return from
30th iteration’s rigidity to the 20th iteration’s rigidity (which is equal to
377.0C ). In this last case the calculated value of 01059.0emp , yet the local
loop has disappeared.
Consider the data for crab [4], (“crab_2percent_noise.txt”), Fig. 12, where
284 points are given. The theoretical deviance is taken to be 01.0theor . The
larger number of points might lead to the increase of the number of local loops at
first iterations. The results at first iterations are presented on Fig. 12, b, where
input points and calculated contour points almost coincide. The value of calcu-
lated deviance 00032.0 emp is very small due to large rigidity of supports, yet
contour has four local loops. At 15th iteration the contour still has some visual
misalignments, and the calculated deviance is equal to 01051.0emp , which is
close to the theoretical one. Besides, contour still has one loop. At 18th iteration
the calculated and theoretical deviances are almost the same, but contour still con-
tain the loop. At 30th iteration the calculated 01716.0emp , which is larger than
the theoretical one, and visually the contour looks like the oversmoothed one.
Therefore, we start to change the supports rigidity in inverse order. Fig. 12, f
shows the calculated contour when the rigidity 22.1C , which is the same as in
direct order 16th iteration. Here the value of 01049.0emp , which is very close
to the theoretical one. So, contour of Fig. 12, f can be considered as the good re-
sult of smoothing.
Consider the figure of dolphin [4] (“dolphin_2percent_noise.txt”), Fig. 13,
179 points, 01.0theor . There are 3 local loops at 1st iteration, Fig. 13, b. Calcu-
lated deviance after 15th iteration at 64.1C is equal to 0086.0emp , which is
slightly less than the theoretical one. At 18th iteration 0102.0emp and is close
to theoretical one. At 30th iteration the deviance 0165.0emp , which testifies
that contour is oversmoothed, and this is visually confirmed. Increasing the itera-
tion number (decreasing the rigidity) lead to additional oversmoothing. As example,
consider the contour obtained after 60th iteration at 5102 C , where
08902.0emp , which is one order higher than the theoretical one. Evidently, the
Application of beam theory for the construction of twice differentiable closed contours …
Системні дослідження та інформаційні технології, 2022, № 4 137
peculiarity of the method is that at very small number of rigidity it eventually
gives the perfect circle. So, the criteria of termination should be specified.
Fig. 12. Recovery of the contour of crab based on data of [4]: a — nitial points; b —
contour after 1st iteration; c — after 15th iteration; d — after 18th iteration, emp ≈ 0. 010 ;
e — after 30th iteration; f — reverse increasing of rigidity till the value as in direct
smoothing after 16th iteration, emp ≈ 0. 010
a b
c d
e f
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 138
a b
c d
e f
Fig. 13. Recovery of dolphin contour based on data of work [4]: a — input data; b — con-
tour after first iteration; c — 15th iteration, 0086.0emp ; d — 18th iteration, 0102.0emp ;
e — 30th iteration 0165.0emp ; f — 60th iteration, 08902.0emp
Application of beam theory for the construction of twice differentiable closed contours …
Системні дослідження та інформаційні технології, 2022, № 4 139
CONCLUSIONS
Based on the authors’ experience in the field of structural mechanics the princi-
pally new methods of smoothing the noisy data to get the continuous closed con-
tours is proposed. The following results are obtained:
Based on the theory of straight beams, which lays on discrete elastic sup-
ports with finite rigidity, the general governing equations are formulated. They
include 4 Connection equations for each straight beam segment and 4 Conjuga-
tion equations, which should “match” the end of previous segment with the be-
ginning of subsequent one. The last one among other serves to smooth the angle
of misalignment between two neighboring segments, which is attained by corre-
sponding requirements to the angular deformations of segments at their border.
The notion of imaginary points is suggested, which broke the segment on
two smaller one but do not envisage the insertion of the additional support be-
tween them. They are introduced when the angular misalignment between two
adjacent segments is large. Their availability is very instrumental in providing the
2C continuity of the smoothed contour.
The algorithm of refinement of calculated positions of the points of segment
is proposed. It accounts for by rotating the initial normal vector to the segment on
the calculated deformation angle in each point. This serves to provide the continu-
ity of the contour points. The iteration process of refinement of the contour which
consists in consequent process of the decreasing the support rigidities is proposed.
Its efficiency is confirmed to analysis of very dense and noisy input points, where
the local loops may occur at initial stages of algorithm.
The notion of experimental (calculated) statistical deviance from the initial
input points is suggested. It is shown that for attainment the visually best smooth-
ing this value should be close with the theoretical (generated) deviance of input
points. So, this value can be used for formulation of the criteria of formal termina-
tion of smoothing procedure.
REFERENCES
1. D.F. Rogers, An Introduction to NURBS With Historical Perspective. San Diego,
CA: Academic Press, 2001.
2. Mark S. Nixon and Alberto S. Aguado, Feature Extraction & Image Processing for
Computer Vision. Academic Press, 2013, 609 p. doi. 10.1016/C2011-0-06935-1.
3. T. Strutz, Data Fitting and Uncertainty: A Practical Introduction to Weighted Least
Squares and Beyond. Wiesbaden, Germany: Vieweg, 2010.
4. Stefan Ohrhallinger and Michael Wimmer, “StretchDenoise: Parametric Curve Re-
construction with Guarantees by Separating Connectivity from Residual Uncertainty
of Samples,” PG '18: Proceedings of the 26th Pacific Conference on Computer
Graphics and Applications: Short Papers, October 2018, pp. 1–4. Available:
https://doi.org/10.2312/pg.20181266
5. Ahlberg J. Harold, Edwin Norman Nilson, and Joseph Leonard Walsh, “The theory
of splines and their applications,” Mathematics in Science and Engineering, 1967.
6. Stephen P. Timoshenko, Strength of materials. Part 1: Elementary theory and prob-
lems, 1955.
7. D.G. Schweikert, “An interpolating curve using a spline in tension,” J. Math. Phys-
ics, 45, pp. 312–317, 1966.
I. Orynyak, D. Koltsov, O. Chertov, R. Mazuryk
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 140
8. P.H. Wagner, X. Luo, and K.A. Stelson, “Smoothing curvature and torsion with
spring splines,” Computer-Aided Design, vol.27, no. 8, pp. 615–626, 1995. doi:
10.1016/0010-4485(95)99798-D.
9. I. Orynyak, I. Lokhman, and A. Bohdan, “The Spring Splines Procedure with Pre-
scribed Accuracy for Determination of the Global (Pipe Centerline) as well as the
Local (Dent) Curvatures,” Proceedings of IPC 2012 9th International Pipeline Con-
ference, September 24–28, Calgary, Alberta, Canada, IPC2012-90127. doi:
10.1115/IPC2012-90127.
10. I.V. Orynyak, I.V. Lokhman, and A.V. Bogdan, “Determination of curve characteris-
tics by its discrete points measured with an error and its application to stress analysis
for buried pipeline,” Strength of Materials, 44(3), pp. 268–284, 2012. doi:
10.1007/s11223-012-9380-7.
11. M.A. Crisfield, “A consistent co-rotational formulation for non-linear, three-
dimensional, beam-elements,” Computer Methods in Applied Mechanics and Engi-
neering, vol. 81, issue 2, pp. 131–150, 1990. doi: 10.1016/0045-7825(90)90106-V.
12. I. Orynyak, R. Mazuryk, and A. Orynyak, “Basic (discontinuous) and smoothing up
(conjugated) solutions in transfer matrix method for static geometrically nonlinear
beam and cable in plane,” Journal of Engineering Mechanics, 146(5), 2020. doi:
10.1061/(ASCE)EM.1943-7889.0001753.
Received 21.05.2022
INFORMATIONON THE ARTICLE
Igor V. Orynyak, ORCID: 0000-0003-4529-0235, National Technical University of
Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, e-mail:
igor_orinyak@yahoo.com
Dmytro R. Koltsov, ORCID: 0000-0002-0396-7255, National Technical University of
Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, e-mail:
koltsovdd@gmail.com
Oleg R. Chertov, ORCID: 0000-0003-0087-1028, National Technical University of
Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, e-mail: chertov@i.ua
Roman V. Mazuryk, ORCID: 0000-0003-4309-824X, National Technical University
of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, e-mail:
r.mazuryk.ua@gmail.com
ЗАСТОСУВАННЯ ТЕОРІЇ БАЛОК ДЛЯ ПОБУДОВИ ПЛОСКИХ ДВІЧІ
ДИФЕРЕНЦІЙОВАНИХ ЗАМКНУТИХ КРИВИХ ЗА НЕТОЧНИМИ
ДИСКРЕТНИМИ ДАНИМИ / І.В. Ориняк, Д.Р. Кольцов, О.Р. Чертов, Р.В. Мазурик
Анотація. Згладжування дискретних точок, заміряних з певною похибкою,
має велике значення в різних технічних застосуваннях та комп’ютерній графі-
ці. Ідея роботи полягає в застосуванні методів теорії балок на пружних опорах.
Установлюються локальні системи координат для прямолінійних відрізків ба-
лок, де кути неспіввісності згладжуються відповідними умовами в рівняннях
спряження. Для наближення довжини отриманого контуру до довжини прямо-
лінійних балок уводиться поняття умовних точок, що розміщуються між точ-
ками замірів. Наводиться ряд прикладів реконструкції реальних контурів по
заміряних дискретних точках із заданою і невідомою похибками.
Kлючові слова: сплайн, пружна балка, опора, замкнутий контур, уявна точка,
неточні дані.
|
| id | journaliasakpiua-article-257192 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2025-07-17T10:27:49Z |
| publishDate | 2022 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/79/4d7213780761f6b11a817120ac516a79.pdf |
| spelling | journaliasakpiua-article-2571922023-05-21T20:04:38Z Application of beam theory for the construction of twice differentiable closed contours based on discrete noisy points Застосування теорії балок для побудови плоских двічі диференційованих замкнутих кривих за неточними дискретними даними Orynyak, Igor Koltsov, Dmytro Chertov, Oleg Mazuryk, Roman сплайн пружна балка опора замкнутий контур уявна точка неточні дані spline elastic beam spring support closed contour imaginary point noisy data The smoothing of measured noisy positions of discrete points has considerable significance in various industries and computer graphic applications. The idea of work consists of the employment of the technique of beam with spring supports. The local coordinates systems are established for beam straight line segments, where the initial angles between them are accounted for in the conjugation equations, which provide the angular continuity. The notions of imaginary points are introduced, the purpose of which is to approach the real length of the smoothed contour to the length of the straight chord. Several examples of closed denoised curve reconstruction from an unstructured and highly noisy 2D point cloud are presented. Згладжування дискретних точок, заміряних з певною похибкою, має велике значення в різних технічних застосуваннях та комп’ютерній графіці. Ідея роботи полягає в застосуванні методів теорії балок на пружних опорах. Установлюються локальні системи координат для прямолінійних відрізків балок, де кути неспіввісності згладжуються відповідними умовами в рівняннях спряження. Для наближення довжини отриманого контуру до довжини прямолінійних балок уводиться поняття умовних точок, що розміщуються між точками замірів. Наводиться ряд прикладів реконструкції реальних контурів по заміряних дискретних точках із заданою і невідомою похибками. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2022-12-27 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/257192 10.20535/SRIT.2308-8893.2022.4.10 System research and information technologies; No. 4 (2022); 119-140 Системные исследования и информационные технологии; № 4 (2022); 119-140 Системні дослідження та інформаційні технології; № 4 (2022); 119-140 2308-8893 1681-6048 en https://journal.iasa.kpi.ua/article/view/257192/270323 |
| spellingShingle | сплайн пружна балка опора замкнутий контур уявна точка неточні дані Orynyak, Igor Koltsov, Dmytro Chertov, Oleg Mazuryk, Roman Застосування теорії балок для побудови плоских двічі диференційованих замкнутих кривих за неточними дискретними даними |
| title | Застосування теорії балок для побудови плоских двічі диференційованих замкнутих кривих за неточними дискретними даними |
| title_alt | Application of beam theory for the construction of twice differentiable closed contours based on discrete noisy points |
| title_full | Застосування теорії балок для побудови плоских двічі диференційованих замкнутих кривих за неточними дискретними даними |
| title_fullStr | Застосування теорії балок для побудови плоских двічі диференційованих замкнутих кривих за неточними дискретними даними |
| title_full_unstemmed | Застосування теорії балок для побудови плоских двічі диференційованих замкнутих кривих за неточними дискретними даними |
| title_short | Застосування теорії балок для побудови плоских двічі диференційованих замкнутих кривих за неточними дискретними даними |
| title_sort | застосування теорії балок для побудови плоских двічі диференційованих замкнутих кривих за неточними дискретними даними |
| topic | сплайн пружна балка опора замкнутий контур уявна точка неточні дані |
| topic_facet | сплайн пружна балка опора замкнутий контур уявна точка неточні дані spline elastic beam spring support closed contour imaginary point noisy data |
| url | https://journal.iasa.kpi.ua/article/view/257192 |
| work_keys_str_mv | AT orynyakigor applicationofbeamtheoryfortheconstructionoftwicedifferentiableclosedcontoursbasedondiscretenoisypoints AT koltsovdmytro applicationofbeamtheoryfortheconstructionoftwicedifferentiableclosedcontoursbasedondiscretenoisypoints AT chertovoleg applicationofbeamtheoryfortheconstructionoftwicedifferentiableclosedcontoursbasedondiscretenoisypoints AT mazurykroman applicationofbeamtheoryfortheconstructionoftwicedifferentiableclosedcontoursbasedondiscretenoisypoints AT orynyakigor zastosuvannâteorííbalokdlâpobudoviploskihdvíčídiferencíjovanihzamknutihkrivihzanetočnimidiskretnimidanimi AT koltsovdmytro zastosuvannâteorííbalokdlâpobudoviploskihdvíčídiferencíjovanihzamknutihkrivihzanetočnimidiskretnimidanimi AT chertovoleg zastosuvannâteorííbalokdlâpobudoviploskihdvíčídiferencíjovanihzamknutihkrivihzanetočnimidiskretnimidanimi AT mazurykroman zastosuvannâteorííbalokdlâpobudoviploskihdvíčídiferencíjovanihzamknutihkrivihzanetočnimidiskretnimidanimi |