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

Fast recursive computation 1D and 2D finite convolution

A.V. Chernov1,2
1Samara State Aerospace University

 PDF, 115 kB

Pages: 190-197.

The paper considers the problem of finding an optimal approximation of a finite impulse response by a linear recurrence relation (LRR) of a given order. Estimates of the convolution computation complexity for various classes of LRR are provided. An algorithm for decomposing an arbitrary two-dimensional impulse response into a sum of divisible impulse responses is considered, and a generalization of the approximation method for the two-dimensional case is provided.

2D finite, computation convolution, linear recurrence relation, LRR, arbitrary two-dimensional impulse, approximation method.

Chernov, A.V. Fast recursive computation 1D and 2D finite convolution. Computer Optics 2003; 25: 190-197.


  1. Oppenheim AV, Schafer RW. Digital signal processing. Pearson; 1975. 
  2. Sergeev VV. Parallel-recursive FIR-filters in image processing tasks. Radiotehnika 1990; 8: 38-41. 
  3. Sergeev VV. Parallel-recursive FIR-filters for image processing. Computer Optics 1992; 10-11: 186-201. 
  4. Yaroslavsky LP. On the possibility of parallel and recursive organization of digital filters. Radiotehnika 1984; 3: 87-91. 
  5. Glumov NI, Myasnikov VV, Sergeyev VV. Polynomial bases for image processing in a sliding window. Patt Recogn Image Anal 1994; 4: 408-413. 
  6. Hall M. Combinatorial theory. 2nd ed. New York: John Wiley and Sons Inc; 1983. 
  7. Gel’fond AO. Calculus of finite differences. Hindustan Publishing Company; 1971. 
  8. Cappelini V, Constantinidis AG, Emiliani PL. Digital filters and their applications. New York: Academic Press; 1978. 
  9. Soifer VA, ed. Methods of computer image processing. Moscow: "Fizmatlit" Publisher; 2001.

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: ko@smr.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20