=Paper=
{{Paper
|id=Vol-1452/paper2
|storemode=property
|title=Construction of Images Using Minimal Splines
|pdfUrl=https://ceur-ws.org/Vol-1452/paper2.pdf
|volume=Vol-1452
|dblpUrl=https://dblp.org/rec/conf/aist/BurovaB15
}}
==Construction of Images Using Minimal Splines==
https://ceur-ws.org/Vol-1452/paper2.pdf
The Construction of Images
Using Minimal Spline
Burova I.G. and Bezrukavaya O.V.
St. Petersburg State University, St. Petersburg, Russia,
i.g.burova@spbu.ru,
Abstract. Tasks of data compression, transmission, subsequent recov-
ery with a given accuracy are of great practical importance. In this paper
we consider a problem of constructing graphical information on a plane
with the help of a parametric defined splines with different properties.
Here we compare the polynomial and the trigonometric splines of the
first and the second order, the polynomial integro-differential splines,
the trigonometric integro-differential splines. We consider a compression
of the image to a relatively small number of points, and a restoration of
graphic information with the given accuracy.
Keywords Image Construction, Polynomial Splines, Trigonometrical
Splines, Integro-differential Splines, Interpolation
1 Introduction
Plotting functions by means of splines is widely used in practice [3–8]. Here we
compare the polynomial and the trigonometric splines of the first and the sec-
ond order, the polynomial integro-differential splines, the trigonometric integro-
differential splines. These splines are characterized by the fact that the approx-
imation of a function is constructed at each grid interval separately as a linear
combination of values of the functions in neighboring grid nodes and some ba-
sic functions (see [1, 2]). The image can be compressed to a small number of
points, which we call the control points (points of interpolation). The result of
the image compression has the form of the control points and information of the
applied basic splines. If it is necessary, the user can restore the image through
an appropriate algorithm.
2 Right polynomial, right trigonometric splines
Let n be natural number, a, b be real numbers, {tj } be ordered equidistant set
of nodes on [a, b], h = tj+1 − tj .
Let function u be such that u ∈ C 3 [a, b]. We use the approximation for u(t)
in the form
e(t) = u(tj )ωj (t) + u(tj+1 )ωj+1 (t) + u(tj+2 )ωj+2 (t), t ∈ [tj , tj+1 ],
u (1)
13
where ωj (t), ωj+1 (t), ωj+2 (t) we determine from the system
e(x) = u(x), u(x) = ϕi (x), i = 1, 2, 3.
u (2)
Here ϕi (x), i = 1, 2, 3, is Chebyshev system on [a, b], ϕi ∈ C 3 [a, b].
2.1 Right polynomial splines
In polynomial case we take ϕi (x) = xi−1 , So we have from (2)
(t − tj+1 ) (t − tj+2 ) (t − tj ) (t − tj+2 )
ωj (t) = · , ωj+1 (t) = · , (3)
(tj − tj+1 ) (tj − tj+2 ) (tj+1 − tj ) (tj+1 − tj+2 )
(t − tj ) (t − tj+1 )
ωj+2 (t) = · . (4)
(tj+2 − tj ) (tj+2 − tj+1 )
We obtain for t ∈ [tj , tj+1 ] the estimation of the error of the approximation
by the polynomial splines (1), (3) – (4): |e
u(t) − u(t)| ≤ K1 h3 ku000 k[tj ,tj+2 ] , K1 =
0.0642.
2.2 Right trigonometric splines
In trigonometric case we take ϕ1 = 1, ϕ2 = sin(x), ϕ3 = cos(x). So we have from
the system (2):
sin(t/2 − tj+1 /2) sin(t/2 − tj+2 /2)
ωj (t) = · , (5)
sin(tj /2 − tj+1 /2) sin(tj /2 − tj+2 /2)
sin(t/2 − tj /2) sin(t/2 − tj+2 /2)
ωj+1 (t) = · , (6)
sin(tj+1 /2 − tj /2) sin(tj+1 /2 − tj+2 /2)
sin(t/2 − tj /2) sin(t/2 − tj+1 /2)
ωj+2 (t) = · . (7)
sin(tj+2 /2 − tj /2) sin(tj+2 /2 − tj+1 /2)
The error of the approximation u(t) by (1), (5)–(7) is the next:
u(t) − u(t)| ≤ K2 h3 ku0 + u000 k[tj ,tj+2 ] , K2 > 0, t ∈ [tj , tj+1 ].
|e
3 Integro-differential splines
Integro-differential polynomial splines were invented by Kireev V.I [3]. The
way of constructing the nonpolynomial integro-differential splines is in [2]. The
integro-differential right spline of the third order has the form:
Z tj+2
e(t) = u(tj )wj (t) + u(tj+1 )wj+1 (t) +
u u(t)dt wj<1> (t), t ∈ [tj , tj+1 ], (8)
tj
where ωj (t), ωj+1 (t), wj<1> (t) we determine from the system (2).
14
3.1 Integro-differential right polynomial splines
In polynomial case we have
A1
wj (t) = , (9)
(tj − tj+2 )(tj − tj+1 )(tj − 3tj+1 + 2tj+2 )
A1 = (−tj+1 +t)(3tj+2 t+3ttj −6tj+1 t−2t2j −2tj tj+2 −2t2j+2 +3tj+1 tj+2 +3tj+1 tj ),
(−tj + t)(3t − tj − 2tj+2 )
wj+1 (t) = , (10)
(tj − tj+1 )(tj − 3tj+1 + 2tj+2 )
6(−tj+1 + t)(−tj + t)
wj<1> (t) = . (11)
(tj − tj+2 )2 (tj − 3tj+1 + 2tj+2 )
We can use in (8) the next formula:
Z tj+2
u(t)dt ≈ (tj+2 − tj )(u(tj ) + 4u(tj+1 ) + u(tj+2 ))/6.
tj
We obtain |e
u(t) − u(t)| ≤ K3 h3 ku000 k[tj ,tj+2 ] , K3 > 0, t ∈ [tj , tj+1 ].
3.2 Integro-differential right trigonometrical splines
In trigonometric case we have
A3 A4
wj (t) = , wj+1 (t) = , (12)
B3 B4
where
A3 = (cos(−tj+1 + tj ) − cos(tj+1 − tj+2 ) − tj+2 sin(t − tj+1 ) + tj sin(t − tj+1 ) −
cos(t − tj ) + cos(t − tj+2 )),
B3 = (cos(−tj+1 +tj )−cos(tj+1 −tj+2 )−tj+2 sin(−tj+1 +tj )+tj sin(−tj+1 +
tj ) − 1 + cos(tj − tj+2 )),
A4 = (cos(t − tj ) − cos(t − tj+2 ) + tj+2 sin(t − tj ) − tj sin(t − tj ) − 1 + cos(tj −
tj+2 )),
B4 = (cos(−tj+1 +tj )−cos(tj+1 −tj+2 )−tj+2 sin(−tj+1 +tj )+tj sin(−tj+1 +
tj ) − 1 + cos(tj − tj+2 )),
wj<1> (t) = (sin(t − tj+1 ) − sin(−tj+1 + tj ) − sin(t − tj ))/B5 , (13)
B5 = (cos(−tj+1 +tj )−cos(tj+1 −tj+2 )−tj+2 sin(−tj+1 +tj )+tj sin(−tj+1 +
tj ) − 1 + cos(tj − tj+2 )).
If we know only the values u(tj ), u(tj−1 ) = u(tj − h), u(tj+2 ) = u(tj + 2h),
then we can use in (8) the formula:
tZj+2
2h cos(h) − 2 sin(h) −2h cos(h) + sin(h) + h
It = u(t)dt = u(tj−1 ) − u(tj ) +
cos(h) − cos(2h) cos(h) − 1
tj
2 sin(h) cos(h) − h − sin(h)
+u(tj+2 ) + R1 .
− cos(h) − 1 + 2 cos2 (h)
It can be shown that R1 = 0, if u(t) = 1, sin(t), cos(t), and
It = (−(4/9)u(tj−1 ) + (5/3)u(tj ) + (7/9)u(tj+2 )) h + O(h3 ).
15
4 Constructing approximation on the plane
4.1 Piecewise linear set of parametric spline
Let function u be such that u ∈ C 2 [a, b].
We build the approximation of u(t) in the form
t − tj
ũ(t) = −A (u(tj ) − u(tj+1 )) + u(tj ), A = , (14)
tj+1 − tj
Here t ∈ [tj , tj+1 ], j = 0, . . . , n − 1. We can obtain for t ∈ [tj , tj+1 ]
u(t) − u(t)| ≤ K0 h2 ku00 k[tj ,tj+1 ] , K0 = 0.125.
|e
Consider the approximation of the curve on the plane using the linear splines.
Let n points z1 , z2 , . . ., zn are given on the plane. Suppose point zi has coordi-
nates (xi , yi ). Then we can construct the next approximations:
x̃(t) = −A (x(tj ) − x(tj+1 )) + x(tj ), ỹ(t) = −A (y(tj ) − y(tj+1 )) + y(tj ),
where A = (t − tj )/(tj+1 − tj ), ifpt ∈ [tj , tj+1 ]. The error of the approximation
on the plain is the next: R(t) = |x̃(t) − x(t)|2 + |ỹ(t) − y(t)|2 .
4.2 Minimal quadratic set of the right polynomial parametric
spline
Consider the approximation of the curve on the plane with the help of quadratic
splines (1), (3)–(4). Let functions x = x(t) and y = y(t) be such that x, y ∈
C 3 [a, b], x(tj ) is the value of x in the node tj , y(tj ) is the value of y in the node
tj . Then we can use the following formulas:
x̃(t) = ACx(tj ) − ABx(tj+1 ) + BCx(tj+2 ), ỹ(t) = ACy(tj ) − ABy(tj+1 ) +
BCy(tj+2 ) on [tj , tj+1 ], j = 1, . . . , n − 1, where A = (t − tj+2 )/(tj − tj+1 ),
B = (t − tj )/(tj+1 − tj+2 ), C = (t − tj+1 )/(tj − tj+2 ).
5 Numerical experiments
Let function z(t) = (x(t), y(t) be such that x(t) = sin(t), y(t) = cos(t). Suppose
we have zj = (x(j), y(j)), j = 1, 2, . . . , 9. We construct z̃ = (e
x(t), ye(t)), with the
help of splines (1), (3)–(4), (1), (5)–(7), (8), (9)–(11), (8), (12)–(13). The results
of application the splines (1), (3)–(4), and the splines (1), (5)–(7) are presented
on graphs 1a, 1b. The results of application the splines (8), (9)–(11), and the
splines (8), (12)–(13) are presented on graphs 2a, 2b.
Now we take x(t) = t − 2 sin(t), y(t) = 1 − 2 cos(t). The result of application
the trigonometric splines (1), (5)–(7) is presented on graph 3a. The result of
application the polynomial splines (8), (9)–(11) is presented on graph 3b.
16
(a) (b)
1 1
0.5 0.5
–1 –0.5 0.5 1 –1 –0.5 0 0.5 1
–0.5 –0.5
–1 –1
Fig. 1. Graphs of approximation by the minimal polynomial splines (1), (3)–(4): (a);
by the trigonometric splines (1), (5)–(7): (b)
(a) (b)
1 1
0.5 0.5
–1 –0.5 0 0.5 1 –1 –0.5 0 0.5 1
–0.5 –0.5
–1 –1
Fig. 2. Graphs of approximation by the right polynomial integro-differential splines
(8), (9)–(11): (a), by the right trigonometric integro-differential splines (8), (12)–(13):
(b)
6 Imaging of letters using a piecewise linear splines
Here we construct, compress and restore the image of the letters using splines.
For example, consider the construction and compression of the letter A. Co-
ordinates of points for the letter "A" zi , i = 1, 2, 3, 4, 5, we take in the form:
x[1]:=2:x[2]:=3:x[3]:=4:x[4]:=3.5:x[5]:=2.5:
y[1]:=2:y[2]:=4:y[3]:=2:y[4]:=3:y[5]:=3:
t[1]:=1:t[2]:=2:t[3]:=3:t[4]:=4:t[5]:=5:
Coordinates of points for the letter "E" zi , i = 1, 2, 3, 4, 5 are given as:
Figure 4a shows the letter "A" which is constructed with the help of the
control points: (2;2),(3;4),(4;2),(3.5;3), (2.5;3), and Fig. 4b shows the letter "E"
which is constructed with the help of the points: (4;4), (2;4), (2;3), (3;3), (2;3),
(2;2), (4;2) and the splines (14).
Each letter is given by a minimum number of the control points. For different
letters the number of control points is different. Now we can compress the image
and have only the control points and the information about the basis splines. We
can hold or send the information someone. The recipient can restor the letters
using the control points and information about the splines.
17
(a) (b)
3 3
2 2
1 1
0 5 10 15 20 25 30 0 5 10 15 20 25 30
–1 –1
Fig. 3. Graphs of the approximation x(t) = t − 2 sin(t), y(t) = 1 − 2 cos(t) by the
right trigonometric splines (1), (5)–(7): (a); by the right polynomial integro-differential
splines (8), (9)–(11): (b)
(a) (b)
4 4
3.5 3.5
3 3
2.5 2.5
2 2
2 2.5 3 3.5 4 2 2.5 3 3.5 4
Fig. 4. Plot of the letter "A" (the control points: (2;2),(3;4),(4;2),(3.5;3), (2.5;3)) (a).
Plot of the letter "E" (the control points: (4;4), (2;4), (2;3), (3;3), (2;3), (2;2), (4;2)): (b).
References
1. Burova I.G., Demyanovich Yu.K. Minimal Splines and theirs Applications. Spb.
(2010) (Russian).
2. Burova Irina. On Integro Differential Splines Construction. Advances in Applied
and Pure Mathematics. Proceedinngs of the 7-th International Conference on Finite
Differences, Finite Elements, Finite Volumes, Boundary Elements (F-and-B’14).
Gdansk. Poland. pp. 57–61 (May 15-17, 2014)
3. Kireev V.I., Panteleev A.V. Numerical methods in examples and tasks. M. 480 p.
(2008)(in Russian)
4. Ruzanski, E. P., Chandrasekar, V. Weather radar data interpolation using a kernel-
based lagrangian nowcasting technique. IEEE Transactions on Geoscience and Re-
mote Sensing. Vol. 53, Issue 6(1), pp. 3073–3083 (June 2015)
5. Mariani, M. C., Basu, K. Spline interpolation techniques applied to the study of
geophysical data. Physica A: Statistical Mechanics and its Applications. Vol. 428,
15. pp. 68–79 (June 2015)
6. Parker, W.D., Umrigar, C.J., Alfe, D., Petruzielo, F.R., Hennig, R.G., Wilkins,
J.W. Comparison of polynomial approximations to speed up planewave-based
quantum Monte Carlo calculations. Journal of Computational Physics. Vol. 287,
pp. 77–87 (April 05, 2015)
7. Tzivelekis, C.A., Yiotis, L.S., Fountas, N.A., Krimpenis, A.A. Parametrically au-
tomated 3D design and manufacturing for spiral-type free-form models in an inter-
active CAD/CAM environment. International Journal on Interactive Design and
Manufacturing. 10 p. (10 February 2015) (Articles not published yet)
8. Zavjalov Yu.S., Kvasov B.I., Miroshnichenko V.L. Metody spline-functions.
M.(1980) (Russian)
18