Splines as a tool for constructing efficient algorithms of a local linear transform
V.V. Myasnikov

Image Processing Systems Institute оf the RAS,
Samara State Aerospace University (SSAU)

Full text of article: Russian language.

Abstract:
This paper presents a particular solution of the generic synthesis problem of the efficient convolution algorithm when using splines to represent the finite impulse response (FIR). Taking into account all necessary conditions for strict efficiency of the induced algorithm, which were articulated in the previous paper [13] in the form of requirements to the non-homogeneous linear recurrence sequence (LRS) (that determines the readings of FIR), and with regard to obvious relationships between main characteristics of the spline and its representation in the form of LRS determined in the present paper, the use of splines is justified to solve the synthesis problem of the efficient algorithm. We present a convolution reduction (CR) model algorithm generated by an arbitrary spline with particular characteristics. Explicit expressions are given for computational complexity of the algorithm being generated for the cases of generalized and polynomial splines. When a set of splines is restricted with parameters (order-and-number of nodes), the upper and lower limits are given for computational complexity of the convolution algorithms caused by these splines. The MC-splines notion is introduced to define the splines, for which the value of complexity of implementation of the resulting algorithm achieves its lower limit. Examples of building the polynomial MC-splines are given.

Key words:
splines, linear recurrence sequence, convolution reduction, computational complexity.

Citation:
Myasnikov EV. Splines as a tool for constructing efficient algorithms of a local linear transform [In Russian]. Computer Optics 2007; 31(2): 52-68.

References:

  1. Ahlberg H, Nilson EN, Wolsh JL. The theory of splines and their applications [Russian translation]. Moscow: “Mir” Publisher, 1972; 318 p.
  2. Anderson JA. Discrete mathematics with combinatorics [in Russian]. Moscow: Williams Publishing House, 2004; 960 p.
  3. Blahut R. Fast algorithms for digital signal processing [in Russian]. Moscow: “Mir” Publisher, 1989; 448 p.
  4. Fast algorithms in digital image processing [In Russian]. Moscow: “Radio i svyaz’ ” Publisher, 1984; 224 p.
  5. Varichenko LB, Labunets VG, Rakov MA. Abstract algebraic systems and digital signal processing [In Russian]. Kiev: Naukova Dumka, 1986; 248 p.
  6. Gelfond AO. Calculation of finite differences [In Russian]. Moscow: “Nauka” Publisher, 1967; 375 p.
  7. Gold B, Rader Ch. Digital signal processing [in Russian]. Moscow: Soviet Radio, 1973; 367 p.
  8. Zavyalov YuS, Kvasov BI, Miroshnichenko VL. Methods of spline functions [In Russian]. Moscow: “Nauka” Publisher, 1980; 352 p.
  9. Kvasov BI. Methods of isogeometric spline approximation [In Russian]. Izhevsk: Regular and Chaotic Dynamics Scientific Publishing Center, Institute of Computer Science, 2006; 416 p.
  10. Mala S. Wavelets in signal processing [in Russian]. Moscow: “Mir” Publisher, 2005; 671 p.
  11. Vinogradov IM (ed.). Mathematical encyclopedia [In Russian]. Moscow: Soviet Encyclopedia, 1977; 1-5.
  12. Mirolyubov AA, Soldatov MA. Linear nonhomogeneous difference equations [In Russian]. Moscow: “Nauka” Publisher, 1986; 127 p.
  13. Myasnikov VV. On the synthesis of the efficient algorithm over the set of the convolution algorithms [In Russian]. Computer Optics 2006; 29: 78-117.
  14. Nussbaumer HJ. Fast Fourier transform and convolution algorithms [in Russian]. Moscow: “Radio i svyaz”, 1985; 248 p.
  15. Oppenheim AV, Schafer RW. Digital signal processing [in Russian]. Moscow: Svyaz, 1979; 416 p.
  16. Rabiner L, Gold B. Theory and application of digital signal processing [in Russian]. Moscow: “Mir” Publisher, 1978; 848 p.
  17. Stechkin SB, Subbotin YuN. Splines in numerical mathematics [In Russian]. Moscow: “Nauka” Publisher, 1976; 248 p.
  18. Tikhonov AN, Arsenin VYa. Methods for solving ill-posed problems [In Russian]. Moscow: “Nauka” Publisher,1979; 142 p.
  19. Yaroslavskiy LP. Introduction to digital image processing [In Russian]. Moscow: Soviet Radio, 1979; 312 p.
  20. Agarwal RP. Difference Equations and Inequality: Theory, Methods, and Applications, 2nd ed., rev. exp. New York: Marcel Dekker, 2000; 998 p.
  21. Glumov NI, Myasnikov VV, Sergeyev VV. Application of polynomial bases for image processing using sliding window. SPIE Image Processing and Computer Optics 1994; 2363: 40-49.
  22. Glumov NI, Myasnikov VV, Sergeyev VV. ParallelRecursive Local Image Processing and Polynomial Bases. Proceedings of the Third IEEE Inrernational Conference on Electronics, Circuits, and Systems ICECS’96. Rodos, Greece, 1996; 2: 696-699.
  23. Jordan Ch. Calculus of finite differences, 2nd ed. New York: Chelsea Publ. Co., 1950; 652 p.
  24. Kvasov BI. Local bases for generalized cubic splines. Rus. J. Numer. Anal. Math. Modeling 1996; 11: 223-246.
  25. Kvasov BI. GB-splines and their properties. Annals of Numerical Mathematics 1996; 3: 139-149.
  26. Lyche T. Discrete cubic spline interpolation. BIT 1976; 16: 281-290.
  27. Myasnikov VV. Construction of integer-value polynomials for recursive calculation of the convolution with FIR-filter. Proceedings of the 7th International Conference on Pattern Recognition and Image Analysis. St. Petersburg, 2004; 331-334.
  28. Myasnikov VV. On Recursive Computation of the Convolution of Image and 2-D Inseparable FIR-Filter. The 9th World Multi-Conference on Systemics, Cybernetics and Informatics. Orlando, Florida (USA), 2005; 268-272.

© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 332-56-22, факс: +7 (846 2) 332-56-20