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