(29) * << * >> * Russian * English * Content * All Issues

On the synthesis of the efficient algorithm under the set of convolution algorithms

V.V. Myasnikov1,2
1Image Processing Systems Institute of RAS 

2Samara State Aerospace University (SSAU) 


Pages: 78-117.

Abstract:
The paper deals with the problem of development of an efficient algorithm designed for the purpose of linear convolution calculation. To develop the desired algorithm, a closure of a predetermined set of algorithms is introduced according to the model (transformation), and it represents a new set of algorithms. The algorithm with the best computational characteristics of all the closure is called an induced algorithm. The induced algorithm, by construction, uses not only the most appropriate subset of algorithms of the original set, but also the characteristics of the processed signal with impulse response for the purpose of calculating the convolution. In this paper a number of theorems is proved that establish necessary and sufficient conditions for the efficiency and strict efficiency of the induced algorithm. Similar theorems are proved for a practically important case when the algorithms of the main classes are chosen as the initial set: the algorithm of direct calculation of convolution; algorithms built on the basis of discrete orthogonal transformations (FFT type); and recursive convolution calculation algorithms (recursive filters). A general description of the method for the development an efficient algorithm on the basis of the theoretical results obtained, is provided. A detailed algorithmic description of the procedures that implement the individual steps of the proposed method is presented. Several well-known convolution calculation algorithms are presented, which are particular solutions to the problem of the development of an efficient algorithm.

Keywords:
Convolution Algorithm, linear convolution, induced algorithm, discrete orthogonal transformation, recursive filters

Citation:
Myasnikov VV. On the Synthesis of the Efficient Algorithm under the Set of Convolution Algorithms. Computer Optics 2006; 29: 78-117.

Acknowledgements:
This work was supported by:
• Russian Foundation for Basic Research (RFBR), project No. 06-01-00616-a;
• Fund of assistance to domestic science;
• The Ministries of Education and Science of the Russian Federation, the Government of the Samara Region and the American Foundation for Civil Research and Development (CRDF Project SA-014-02) within the framework of the Russian American program “Basic Research and Higher Education” (BRHE).

References:

  1. Agayan SS. Successes and problems of fast orthogonal transformations [In Russian]. In Book: Recognition, classification, forecast. Mathematical methods and their application. Moscow: "Nauka" Publisher; 1990; 3: 146-214.
  2. Anderson JA. Discrete mathematics with combinatorics. Prentice Hall; 2001. ISBN: 978-0-13-086998-2.
  3. Ahmed N, Rao KR. Orthogonal transforms for digital signal processing. Berlin, Heidelberg, New York: Springer-Verlag; 1975. ISBN: 978-0-387-06556-4.
  4. Baranov SN, Domaratskii AN, Lastochkin NK, Morozov VP. Software development process [In Russian]. Moscow: "Fizmatlit" Publisher; 2000. ISBN: 5-02-015564-0.
  5. Blahut RE. Fast algorithms for digital signal processing. Boston, MA: Addison-Wesley Longman Publishing Co Inc; 1985. ISBN: 978-0-201-10155-3.
  6. Huang TS, ed. Two-dimensional digital signal processing II. Transforms and median filters. Berlin, Heidelberg, New York: Springer-Verlag; 1981. ISBN: 978-0-412-54470-5.
  7. Varichenko LV, Labunetc VG, Rakov MA. Abstract algebraical structures and digital signal processing [In Russian]. Kiev: "Naukova Dumka" Pablisher; 1986.
  8. Vittih VA, Sergeev VV, Soifer VA. Processing images in the automated systems of scientific research [In Russian]. Moscow: "Nauka" Publisher; 1982.
  9. Vlasenko VA, Lapa YuM, Yaroslavskii LP. Methods of synthesis of fast convolution algorithms and spectral analysis of signals [In Russian]. Moscow: "Nauka" Publisher; 1990. ISBN: 5-02-006674-5.
  10. Gelfond AO. Calculus of finite differences [In Russian]. 3th ed. Moscow: "Nauka" Publisher; 1967.
  11. Gold B, Rader ChM. Digital processing of signals. New York: McGraw-Hill Book Company; 1969. ISBN: 978-0-07-023642-4.
  12. Goldenberg LM, Matushkin BD, Polyak MN. Digital signal processing [In Russian]. Handbook. Moscow: "Radio i Svyaz" Publisher; 1985.
  13. Graham RL, Knuth DE, Patashnik O. Concrete mathematics: A foundation for computer science. New York: Addison-Wesley Professional; 1994. ISBN: 978-0-201-55802-9.
  14. Guravlev YuI. Nonparametric pattern recognition tasks [In Russian]. Cybernetics 1976; 6: 93-103.
  15. Guravlev YuI. Correct algebras over sets of incorrect (heuristic) algorithms. Part I [In Russian]. Cybernetics 1977; 4: 5-17.
  16. Guravlev YuI. On the algebraic approach to solving problems of recognition or classification [In Russian]. Problemy Kibernetiki 1978; 33: 5-68.
  17. Kober VI, Ovseevich IA. Using information redundancy of signals to reduce the computational cost of processing them [In Russian]. Radioengineering 1999; 5: 13-16.
  18. Labunets VG. Algebraic theory of signals and systems: Fast multidimensional Fourier transform [In Russian]. Sverdlovck: Ural University Publisher; 1989. ISBN: 5-7525-0037-0.
  19. Labunets VG. Unified approach to fast conversion algorithms [In Russian]. In Book: Using orthogonal methods in signal processing and system analysis. Sverdlovck: "UPI" Publisher; 1980.
  20. Markov AA, Nagorny NM. The theory of algorithms. Dordrecht, Boston, London: Kluwer Academic Publishers; 1988. ISBN: 978-90-277-2773-2.
  21. Vinogradov IM, ed. Mathematical encyclopedia: In 5 volumes. Moscow: "Sovetskaya Enciklopedia" Publisher; 1977-1985.
  22. Mirolubov AA, Soldatov MA. Linear homogeneous difference equations [In Russian]. Moscow: "Nauka" Publisher; 1981.
  23. Mirolubov AA, Soldatov MA. Linear inhomogeneous difference equations [In Russian]. Moscow: "Nauka" Publisher; 1986.
  24. Myasnikov VV. Even polynomial bases for image processing filters with axisymmetric impulse response [In Russian]. Avtometriya 1996; 1: 80-87.
  25. Myasnikov VV. Recursive algorithm for calculating image convolution with an inseparable two-dimensional polynomial FIR filter [In Russian]. Computer Optics 2004; 26: 80-82.
  26. Myasnikov VV. On recursive computation of the convolution of an image with a two-dimensional inseparable FIR filter. [In Russian]. Computer Optics 2005; 27: 117-122.
  27. Nikolsky SM. A course in mathematical analysis: Volume 1. Мoscow: "Mir" Publishers; 1977.
  28. Nussbaumer HJ. Fast Fourier transform and convolution algorithms. 2nd ed. Berlin, Heidelberg: Springer-Verlag; 1982. ISBN: 978-0-387-11825-3.
  29. Oppenheim AV, Schafer RW. Digital signal processing. Englewood Cliffs, NJ: Prentice Hall Inc; 1975. ISBN: 978-0-13-214635-7.
  30. Rabiner LR, Gold B. Theory and application of digital signal processing. Englewood Cliffs, NJ: Prentice Hall Inc; 1975. ISBN: 978-0-13-914101-0.
  31. Raudin PV. Fast DFT algorithms for sparse input or output [In Russian]. Proc ROAI-97 1997: 1: 243-247.
  32. Sergeev VV. Parallel recursive FIR image processing filters [In Rusian]. Computer Optics 1992; 10-11: 186-201.
  33. Soifer VA, Khramov AG. Class of spectral-recurrent field estimation algorithms [In Rusian]. Abstracts of the Report of the 5th International Symposium on Information Theory 1979; 2: 136-138.
  34. Trachtmann AM, Trachtmann VA. Fundamentals of the discrete signals' theory of the finite intervals [In Russian]. Moscow: "Sovetskoe Radio" Publisher; 1975.
  35. Hamming RW. Digital filtres. 3rd ed. Mineola, New York: Dover Publications Inc; 1989. ISBN: 978-0-486-65088-3.
  36. Hall M. Combinatorial theory. John Wiley & Sons Inc; 1975. ISBN: 978-0471002284.
  37. Chernov VM. Arithmetic methods for the synthesis of fast discrete transformation algorithms [In Russian]. The thesis for the Doctor’s degree in Physics and Mathematics. Samara: 1998.
  38. Chernov AV. Fast recursive calculation of one-dimensional and two-dimensional final convolutions [In Russian]. Computer Optics 2003; 25: 190-197.
  39. Yaroslavsky LP. Digital image processing. An introduction. Berlin, Heidelberg: Springer-Verlag; 1985. ISBN: 978-3-642-81931-5.
  40. Yaroslavsky LP. The possibility of parallel recursive organization of digital filters. Radio Engineering 1984; 39(2): 71-75.
  41. Yaroslavsky LP. Digital signal processing in optics and holography. Introduction to digital optics [In Russian]. Moscow: "Radio i Svyaz" Publisher; 1987.
  42. Agarwal RP. Difference equations and inequality: Theory, methods, and applications. 2nd ed. New York: Marcel Dekker; 2000. ISBN: 978-0-8247-9007-3.
  43. Glumov NI, Myasnikov VV, Sergeyev VV. Application of polynomial bases for image processing using sliding window. Proc SPIE 1994; 2363: 40-49. DOI: 10.1117/12.199649.
  44. Glumov NI, Myasnikov VV, Sergeyev VV. Parallel-recursive local image processing and polynomial bases. Proc 3rd IEEE Int Conf Electron, Circuits, and Systems ICECS’96 1996; 2: 696-699. DOI: 10.1109/ICECS.1996.584457.
  45. Gupta A, Rao KR. A fast recursive algorithm for the discrete sine transform. IEEE Transactions on Acoustic, Speech and Signal Processing 1990; 38(3): 553-557. DOI: 10.1109/29.106875.
  46. Hatamian M. A real-time two-dimensional moment generating algorithm and its single chip implementation. IEEE Transactions on Acoustic, Speech and Signal Processing 1986; 34(3): 546-553. DOI: 10.1109/TASSP.1986.1164853.
  47. Hou HS. A fast recursive algorithm for computing the discrete cosine transform. IEEE Transactions on Acoustic, Speech and Signal Processing 1987; 35(10): 1455-1461. DOI: 10.1109/TASSP.1987.1165060.
  48. Jagerman D. Difference equations with applications to queues. New York: CRC Press; 2000. ISBN: 978-0-8247-0388-2.
  49. Jain AK, Jain JR. Partial differential equations and finite difference methods in image processing. Раrt II – Image restoration. IEEE Trans Automat Contr 1978; 23(5): 817-834. DOI: 10.1109/TAC.1978.1101881.
  50. Jain AK. Partial differential equations and finite difference methods in image processing. Раrt I – Image representation. J Optimiz Theory and Appl 1977; 23(1): 65-91. DOI: 10.1007/BF00932298.
  51. Jordan Ch. Calculus of finite differences. 2nd ed. New York: Chelsea Publisher Co; 1950.
  52. Kober V. Fast recursive algorithm for sliding sine transform. Electron Lett 2002; 38(25): 1747-1748. DOI: 10.1049/el:20021098.
  53. Kober VI, Yaroslavsky LP. Use of signal redundancy for reduction of signal processing computational time. Proc 3rd Int Seminar on Digital Image Processing in Medicine, Remote Sensing and Visualization of Information 1992: 99-101.
  54. Kober V, Ovseyevich IA, Yaroslavsky LP. Information redundancy of signals: a way to save processing time. Pattern Recognit Image Anal 1993; 3(1): 15-18.
  55. Li B. High-order moment computation of grey-level images. IEEE Trans Image Process 1995; 4(4): 502-505. DOI: 10.1109/83.370680.
  56. Myasnikov VV.A recursive algorithm for computing the convolution of an image with a two-dimensional indecomposable polynomial FIR filter. Pattern Recognit Image Anal 2005; 15(1): 260-263.
  57. Myasnikov VV. Methods for designing recursive FIR filters. Proc Int Conf “Computer Vision and Graphics” (ICCVG 2004)  2004: 845-850.
  58. Myasnikov VV. Construction of integer-value polynomials for recursive calculation of the convolution with FIR-filter. Theses 7thInt Conf «International Conference on Pattern Recognition and Image Analysis» 2004: 331-334.
  59. Myasnikov VV. Recursive algorithm of calculation the convolution of image and inseparable 2-D polynomial FIR-filter // Theses 7th Int Conf «International Conference on Pattern Recognition and Image Analysis» 2004: 327-330.
  60. 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 2005: 268-272.
  61. Vitkus RY, Yaroslavsky LP. Recursive algorithms for local adaptive linear filtration. In Book: Yaroslavsky LP, Rosenfeld A, Wilhelmi W, eds. Mathematical research. Berlin: Academy Verlag, 1987: 34-39.
  62. Yaroslavsky LP, Kober V. Redundancy of signals and transformations and computational complexity of signal processing. Proc 12th IAPR International Conference on Pattern Recognition 1994; 2: 164-166. DOI: 10.1109/ICPR.1994.577147.
  63. Zakaria MF, Vroomen LJ, Zsombor-Murray PJA, van Kessel JMHM. Fast algorithm for the computation of moment invariants. Pattern Recognit 1987; 20(6): 634-643. DOI: 10.1016/0031-3203(87)90033-1.