The Construction of Images Using Minimal Spline

Abstract

Tasks of data compression, transmission, subsequent recovery 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

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 second order, the polynomial integro-differential splines, the trigonometric integrodifferential splines. These splines are characterized by the fact that the approximation 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 basic 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.

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 ∈ C3[a, b]. We use the approximation for u(t) in the form ( 1 ) where ωj (t), ωj+1(t), ωj+2(t) we determine from the system u(x) = u(x), u(x) = ϕi(x), i = 1, 2, 3.

e Here ϕi(x), i = 1, 2, 3, is Chebyshev system on [a, b], ϕi ∈ C3[a, b]. 2.1

Right polynomial splines In polynomial case we take ϕi(x) = xi−1, So we have from ( 2 ) ( 2 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ωj (t) = (t − tj+1) (t − tj+2) , ωj+1(t) = (tj − tj+1) · (tj − tj+2)

(t − tj ) (tj+1 − tj ) · (tj+1 − tj+2) (t − tj+2) , ( 3 ) ωj+2(t) =

(t − tj ) (tj+2 − tj ) · (tj+2 − tj+1) (t − tj+1) .

We obtain for t ∈ [tj , tj+1] the estimation of the error of the approximation by the polynomial splines ( 1 ), ( 3 ) – ( 4 ): |ue(t) − u(t)| ≤ K1h3ku000k[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 ):

ωj (t) = ωj+1(t) = ωj+2(t) = sin(t/2 − tj+1/2) sin(t/2 − tj+2/2) sin(tj /2 − tj+1/2) · sin(tj /2 − tj+2/2)

, sin(t/2 − tj /2) sin(t/2 − tj+2/2) sin(tj+1/2 − tj /2) · sin(tj+1/2 − tj+2/2)

sin(t/2 − tj /2) sin(t/2 − tj+1/2) 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:

|ue(t) − u(t)| ≤ K2h3ku0 + u000k[tj,tj+2], K2 > 0, t ∈ [tj , tj+1]. 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: u(t) = u(tj )wj (t) + u(tj+1)wj+1(t) + e u(t)dt wj<1>(t), t ∈ [tj , tj+1], ( 8 ) where ωj (t), ωj+1(t), wj<1>(t) we determine from the system ( 2 ). (9) (10) (11) (12)

(−tj + t)(3t − tj − 2tj+2) , (tj − tj+1)(tj − 3tj+1 + 2tj+2)

6(−tj+1 + t)(−tj + t) (tj − tj+2)2(tj − 3tj+1 + 2tj+2) .

u(t)dt ≈ (tj+2 − tj)(u(tj) + 4u(tj+1) + u(tj+2))/6.

We can use in ( 8 ) the next formula: We obtain |ue(t) − u(t)| ≤ K3h3ku000k[tj,tj+2], K3 > 0, t ∈ [tj, tj+1]. 3.2 Integro-differential right trigonometrical splines

In trigonometric case we have

A3

B3 wj(t) = , wj+1(t) =

A4 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: 3.1 Integro-differential right polynomial splines

In polynomial case we have

wj(t) =

A1 (tj − tj+2)(tj − tj+1)(tj − 3tj+1 + 2tj+2) , A1 = (−tj+1+t)(3tj+2t+3ttj −6tj+1t−2tj2−2tjtj+2−2tj2+2+3tj+1tj+2+3tj+1tj), tj+2 Z tj It = u(t)dt = u(tj−1) 2h cos(h) − 2 sin(h) − u(tj) −2h cos(h) + sin(h) + h + cos(h) − cos(2h) cos(h) − 1 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).

Constructing approximation on the plane 4.1

Piecewise linear set of parametric spline Let function u be such that u ∈ C2[a, b].

We build the approximation of u(t) in the form u˜(t) = −A (u(tj ) − u(tj+1)) + u(tj ), A = t − tj , tj+1 − tj (14) Here t ∈ [tj , tj+1], j = 0, . . . , n − 1. We can obtain for t ∈ [tj , tj+1] |ue(t) − u(t)| ≤ K0h2ku00k[tj,tj+1], K0 = 0.125.

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 coordinates (xi, yi). Then we can construct the next approximations:

x˜(t) = −A (x(tj ) − x(tj+1)) + x(tj ), y˜(t) = −A (y(tj ) − y(tj+1)) + y(tj ), where A = (t − tj )/(tj+1 − tj ), if t ∈ [tj , tj+1]. The error of the approximation on the plain is the next: R(t) = p|x˜(t) − x(t)|2 + |y˜(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 ∈ C3[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), y˜(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˜ = (x(t), ye(t)), with the e 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. 1 0.5 0 –0.5 –1 1 0 0.5 –0.5 –1 –0.5 0.5 1 –1 –0.5 0.5 1 1 0.5 –0.5 –1 1 0 0.5 –0.5 –1

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. Coordinates 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. 4 3.5 3 2.5 2 2 4 3.5 3 2.5 2 2 4

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 kernelbased lagrangian nowcasting technique . IEEE Transactions on Geoscience and Remote 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 automated 3D design and manufacturing for spiral-type free-form models in an interactive 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)