Journal of Multimedia Information System

Korea Multimedia Society

J Multimed Inf Syst 5(1):63-66

eISSN: 2383-7632

DOI: https://doi.org/10.9717/JMIS.2018.5.1.63

Section D

Brief Paper: The Use of The Spectral Properties of Basis Splines in Problems of Signal Processing

Zaynidinov Hakim Nasiritdinovich¹, MirzayevAvaz Egamberdievich², Khalilov Sirojiddin Panjievich³^,^*

¹Computer Engineering Dept., Tashkent University of Information Technologies, Uzbekistan, kh.surajiddin@gmail.com

²Computer Engineering Dept., Tashkent University of Information Technologies, Uzbekistan, kh.surajiddin@gmail.com

³Computer Engineering Dept., Tashkent University of Information Technologies, Uzbekistan, kh.surajiddin@gmail.com

^*Corresponding Author: Xalilov Sirojiddin Panjiyevich, Tashkent, Tel: +99893-792-99-00, suraj_24@mail.ru

© Copyright 2018 Korea Multimedia Society. This is an Open-Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/4.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Received: Mar 05, 2018 ; Revised: Mar 12, 2018 ; Accepted: Mar 21, 2018

Published Online: Mar 31, 2018

Abstract

In this work, the smoothing and the interpolation basis splines are analyzed. As well as the possibility of using the spectral properties of the basis splines for digital signal processing are shown. This takes into account the fact that basic splines represent finite, piecewise polynomial functions defined on compact media.

Keywords: Splines; Spectral properties; Polynomial functions

I. THEORY EVALUATION

In the 60-80-ies of the XX century polynomial splines the whole degree m [1,9] are wide spread to solve problems of approximation of continuous functions. Denote a spline function of one variable x as S_m(x) (one-S-spline). Such a spline is based on the grid nodes x_i located at the axis of abscissa (i=0,1, …, n):

a = x 0 < x 1 < … < x n − 1 < x n = b,

(1)

and has the following properties[1]:

Continuity on any closed interval [a,b] together with their derivatives up to some order p.
The matching polynomial of the same degree m on each interior interval [x_i,x_i+1] the interval [a,b]:

S m (x) = P m,i (x) = a o,i + a 1, i (x − x i) + a 2, i (x − x i) 2 + … + a m,i (x − x i) m

(2)

The difference d=m−p is called the defect of the spline. One should distinguish between interpolation and smoothing splines. Construction of the interpolation splines of degree m ≥ 2 is connected with the need of solving SLAE, in which connection the edge (boundary) conditions have an important role in algorithms for computing the coefficients.

In tasks of reproduction of experimental data dependences of the measurement results are known only approximately. With a large amount of data usually require complex recovery algorithms and valuable time resources. To rich our destination smoothing splines are having important role. They can be built in accordance with different criteria of approximation, e.g. by minimizing function of the form[2,5,7]:

J (S) = ∑ i = 0 n a i (S (x i) − f (x i)) 2 + a ∫ b b (S " (x)) 2 d x,

(3)

And

J (a, S) = a ∫ b a | d y d x y s (x) | 2 d x + ∑ ​ ​ (S (x i) − f (x i)) 2,

(4)

where α_i, α are positive numbers. In these formulas, the sum of squared deviations of the spline from the function values at the nodes is combined with the degree of smoothness [1,8,9].

In the theory of approximation by splines the fundamental importance is the concept of the basis as system of base functions. If the grid of nodes is set (1), then on an interval [a,b] any S-spline of degree m of the defect d=1 can be represented as a sum of basis splines (B-splines) with weight factors coefficients bi:

f (x) ≅ S m (x) = ∑ i = − m n + m + 1 b i B m, i (x),

(5)

where splines B_m,i represent a finite, piecewise polynomial functions, moreover, are defined on compact media. They must satisfy the following conditions:

$B m,i (x) = 0 in x e (x i, x i + m + 1);$
$B m,i (x) > 0 in x є (x i, x i + m + 1);$
$∫ b b B m, i (l ¯) d l ¯ = ∫ x i x i + m + 1 B m, i (l ¯) d l ¯ = 1.$

B-splines are different from zero on the intervals of length (m+1) h and are linearly independent on [a,b]. To approximate the function off(x)by a sequence of B-splines, it requires to insert additional nodes in the amount of 2m (m nodes on the left and the same number of nodes on the right) outside the interval [a, b].

B-spline of any degree m ≥ 1 is constructed according to a recursive convolution formula [1]:

B m + 1 (x) = B m (x) * B 0 (x) = ∫ − ∞ ∞ B m (l ¯) B 0 (x − l ¯) d l ¯ .

(6)

If the distances between adjacent nodes of the spline are the same, i.e.x_i+1−x_i=h = const. Here, h value is the step of approximation (interpolation) for an equal mesh. We give analytical expressions for b-splines of small degrees of odd (1st and 3rd) in the vicinity of the origin x=0 at equally spaced nodes with the step h=1:

For b-spline of the 1st degree (medium - cut [−1,1]):

B i (x) = {x − 1, i f x є [− 1, 0]; 1 − x, i f x є [1 − x]; 0, i f x e [− 1, 1];

(7)

For b-spline of the 3rd degree (media - cut [−2,2]):

B 3 (x) = {0, i f x > 2; (2 − x) 3 6, i f [1 ≤ x ≤ 2]; 1 + 3 (1 − x) + 3 (1 − x) 2 − 3 (1 − x) 2 6, i f [0 ≤ x ≤ 1]; B 3 (− x) .

(8)

Graphics of sequences of B-splines of these two degrees are shown in Figure 1.

Fig. 1. Sequences of B-splines.

Download Original Figure

Matrix systems of linear algebraic equations (SLAE) needed to calculate the b-coefficients of the interpolation cubic spline is obtained tridiagonal with dominant main diagonal. It is nonspecial and the computational process of obtaining coefficients is stable. The system of equations also can be solved by using Thomas method [9]. The corresponding matrix to obtain the coefficients of the smoothing spline contains of five diagonals. The systems of equations with such matrices are also easily solved by Thomas method. Along with such options in the theory of splines, so-called “local” smoothing (averaging) algorithms are worked out, that do not require the solution of SLAE of high orders, which leads to a reduction of processing time of the original data sets [8,9]. The required amount of computation is only slightly dependent on the number of mesh nodes and determined almost only by the degree of the spline. It turns out much smaller than in the interpolation, and the results are characterized by only a marginal loss in accuracy. For cubic splines the convergence of the process of approximation to an accurate result for each step is estimated as O(h⁴).

Examples of local smoothing formulas for calculating the b-coefficients for interior points of the interval (a,b) are [1,4,6,7]:

For splines of the 3rd degree:

- averaging three values of the function f(x):

b i = 16 (− f i − 1 + 8 f i − f i + 1);

(9)

- averaged over five values:

b i = 136 (f i − 2 − 10 f i − 1 + 54 f i − 10 f i + 1 + f i + 2)

(10)

For splines of the 5th degree:

- averaged over five values:

b i = 1240 (13 f i − 2 − 122 f i − 1 + 438 f i − 122 f i + 1 + 13 f i + 2)

(11)

Such formulas retain the properties of smoothness of the approximating spline and the same order of convergence, interpolation and approximation. The coefficients do not depend on values of functions, quite remote from the current node number. They have a symmetrical appearance, but it is valid only for interior points of the interval. The coefficients for the boundary and neighboring samples are determined by separate interpolation formulas. You may also need extra nodes outside the segment. For example, the formula of three values (9) for the coefficients of cubic B-splines can be complemented with expressions for the boundary points [6]:

{b i − 1 = 6 f i − 4 b i − b i + 1; i = 0.1; b i + 1 = 6 f i − 4 b i − b i + 1; i = n − 1, n .

(12)

Transform of FurieB-splines of any degree m result of the formula in the following form [5]:

F m (ω) = A h (sin (ω h 2) ω h / 2) m + 1

(13)

where A – amplitude b-spline.

Graphics of modules of spectral density of B-splines of the first and third degrees are shown in Figure 2.

Fig. 2. Spectral density of B-splines of the first and third degrees.

Download Original Figure

B-splines represent a natural system of basic functions, with which can be created the entire reasonableness, the necessary length of discrete samples of continuous signals. First, they have their own internal grid nodes. Secondly, analytical expressions for their spectral characteristics, represented by the formula (13), have many similarities with the expression for a General member sinc(x) of the cardinal number (1.1) which was used in the theory of communication by V. A. Kotelnikov and Claude Shennon in obtaining the main theorem of samples. The difference lies in that for fixing the sample zeroes are allocated ω_c=π/h frequency response functions F_m(ω), but not zero of cardinal number, and that the degree m of the transcendental function can be greater than unity. Theoretically, the functions of the frequency argument in the formula (13) are defined and not equal to zero in the entire x-axis except for a countable set of points.

The main difference, not counting the exponent m ≥ 1, is that a continuous variable can be the frequency ω and the discrete values of h steps are\ automatically recorded, as an essential principle of the theory of splines as finite basis elements, i.e. the arrangement of their nodes. And exactly the same as f(x,ω)=sinc(x,ω), the functions F_m(ω) theoretically have an infinite number of zeros.

Let’s use the above formula (5) for the spectral energy:

E = 1 2 π ∫ − ∞ ∞ (F (ω)) 2 d ω,

(14)

and apply the equality of Parseval for continuous signals [9]:

E = ∫ − ​ T T f 2 (x) d x = 1 π ∫ 0 ∞ F 2 (ω) d ω

(15)

We also use the term “energy E_εon the level ε”. It means the value of the energy integral for functions integral with square, characterized by the value ε of the total energy of the signal.

Between different types of spectral energy in the frequency domain there is a close correlation:

E = 1 π ∫ 0 ∞ (F 2 (ω)) d ω ≅ 1 π ∫ 0 ∞ (F a s (ω)) 2 d ω = E a s .

(17)

The spectra F(ω) and F_as(ω) due to the finiteness of both signals and elements of the basis are infinite. Energy of a finite sequence of B-splines defined on a compact media is terminal. This energy as a function of frequency, can be divided into two parts – low frequency E_Lf(ω)and high frequency E_hf(ω), which consists of two components:

(1 π) ∫ 0 ∞ (F a s (ω)) 2 d ω = (1 π) ∫ 0 ω c (F a s (ω)) 2 d ω + (1 π) ∫ ω c ∞ (F a s (ω)) 2 d ω .

(18)

The boundary frequency between the low and high frequency part of the energy spectrum, as in the previous chapter, you can designate itω_c. Then we can use a theorem of mathematical analysis, which is known as the theorem on integral inequalities [3]:

Theorem 1.1.

If f and g are integral and satisfy the inequality f(x) ≤on [a,b], then

∫ b b f (x) d x ≤ ∫ a b g (x) d x .

(19)

Apply it to assess the share of the high energy part of the spectrum E_hf(ω) compared with the total energy of the signal. You will get a sequence of transformations [4,6,8]:

E h f (ω) = ε E = (1 π) ∫ ω c ∞ K 1 h 2 ∫ ω c ∞ (sin (ω h 2) ω h 2) 2 m + 2 d ω ≤ K 1 h 2 ∫ ω c ∞ (2 ω h) d ω,

(20)

where K1 – coefficient depending on the number of knots of the spline, i.e. the length of the discrete samples of the signal f(x).

The integral on the right side (20), refers to the number of table integrals and is easily calculated in quadrature. In the result we get estimation for high-frequency energy:

ε E ≤ K 1 h 2 ∫ ω c ∞ (2 ω h) m + 2 d ω = 2 m + 2 K 1 (2 m + 1) π 2 m + 1 h .

(21)

From this expression, it can be concluded that the energy of high frequency part of the spectrum of a sequence of B-splines approximating signal is proportional to the step size of the sampling multiplier, dependent on the degree of the spline.

V. CONCLUSION

The material presented shows that when solving problems in the theory of signal counts, methods of spline-functions with compact support can give definite advantages over a theory using the principle of finite spectrum. The principle of the finiteness of signal carriers is at the forefront, which leads to the infiniteness of the spectra and requires detailed estimates of the accuracy of calculations of the energy characteristics.

The advantage of the method of finite basis functions, in contrast to the practice of interpolation approximations considered in applications of the theory of functions with finite spectrum, is the ability to restore signals according to various criteria - like interpolation and quadratic functional minimization criteria and others

REFERENCES

[1].

С.Ф.Свиньин. Базисные сигналы в теории отчётов. СПб.: Наука, 2003,-118с

[2].

Сергиенко А. Цифровая обработка сигналов. - CПб.: Питер, 2003. – 604 с.

[3].

Соболь И.М. Многомерные квадратурные формулы и функции Хаара . - М.: Наука, 1969. - 288 с..

[4].

Солонина А.И., Улахович Д.А., Яковлев Л.А. Алгоритмы и процессоры цифровой обработки сигналов. – СПб.: БХВ – Петербург, 2001, -276 с.

[5].

Сюзев В.В. Спектральный анализ в базисах функций Хаара // Вестник МГТУ им. Н.Э. Баумана. Сер. «Приборостроение». 20011, №2, С. 48-67.

[6].

Толстых Г.Д. Сверх быстро действующее спектральное преобразование по функциям Хаара. Известия ВУЗов. Радиоэлектроника. - 1979 - N7, С. 86-89.

[7].

Трахтман А.М., Трахтман В.А. Основы теории дискретных сигналов на конечных интервалах. - М.: Сов.радион, 1975. - 208 с

[8].

Zaynidinov H.N NazirovaE.ShZaynutdinova M.B, Methods of reconstructing signals based on multivariate splineEuropean Journal of Computer Science and Information Technology Vol.3, No.2, pp.52-59, May 2015 Published by European Centre for Research Training and Development UK.

[9].

Zaynidinov H.N Madhusudan Singh Dhananjay Singh Polynomial Splines for Digital Signal and Systems (Монография на англиском языке) LAMBERT Academic publishing, Germany, 2016.