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

On recursive computation of the convolution of an image
with a two-dimensional inseparable FIR filter

V.V. Myasnikov 1, 2
1Image Processing Systems Institute of RAS
2Samara State Aerospace University (SSAU)

 PDF, 124 kB

Pages: 117-122.

Full text of article: Russian language.

Abstract:
The paper proposes a method for constructing an algorithm for the recursive calculation of the convolution of an image and a two-dimensional filter with an inseparable finite impulse response (FIR). This method is based on the representation of the final impulse response of the filter through vertical and horizontal recurrence relations. Each of the recurrence relations leads to a semi-recursive procedure for calculating the convolution of the image and the two-dimensional FIR filter. In turn, each of these semi-recursive procedures consists of two parts. The first part of the procedure is a recursive relation designed to recalculate the values in the procedure, and the second part is the non-recursive calculation of convolutions at the boundaries of the impulse response. In order to move from the developed semi-recursive procedure to a completely recursive algorithm for computing the desired convolution, a special statement is proved in the paper. This statement shows that if the impulse response of the target filter satisfies the recurrence relations both vertically and horizontally, then all the additional impulse responses involved in the calculation of convolutions at the borders of the FIR filter correspond to the same recurrence relations. This statement allows to modify the resulting procedure into a fully recursive algorithm for calculating the convolution of the image and the two-dimensional inseparable FIR filter. The paper also provides estimates of the computational complexity of the proposed recursive algorithm, shown by the number of arithmetic operations.

Keywords:
FIR filter, inseparable finite impulse response, recurrence relations, recursive algorithm.

Citation:
Myasnikov VV. On recursive computation of the convolution of an image with a two-dimensional inseparable FIR filter. Computer Optics 2005; 27: 117-122.

Acknowledgements:
This work was supported by the Russian-American program "Basic Research and Higher Education" (BRHE) and a grant from the President of the Russian Federation No. НШ-1007.2003.01.

References:
  1. Blahut RE. Fast algorithms for digital signal processing. Reading, Wokingham: Addison-Wesley; 1985. ISBN: 978-0-201-10155-3.
  2. Dudgeon DE, Mersereau RM. Multidimensional digital signal processing. Cliffs: Prentice-Hall Inc; 1984. ISBN: 978-0-13-227638-2.
  3. Yaroslavsky LP. The possibility of parallel and recursive organization of digital filters. Radiotekhnika 1984; 3: 87-89.
  4. Sergeev VV. Parallel-recursive FIR-filters for image processing [In Russian]. Computer Optics 1992; 10-11: 186-201.
  5. Chernov AV. Fast recursive computation 1D and 2D finite convolution. Proc 7th Int Conf Pattern Recogn Image Anal (St. Petersburg, Russia) 2004: 1001-1004.
  6. 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.
  7. Glumov NI, Myasnikov VV, Sergeyev VV. Parallel-recursive local image processing and polynomial bases. Proc 3rd Int Conf on Electronics, Circuits, and Systems 1996: 696-699. DOI: 10.1109/ICECS.1996.584457.
  8. Myasnikov VV. Methods for designing recursive FIR filters. In Book: Wojciechowski K, Smolka B, Palus H, Kozera RS, Skarbek W, Noakes L, eds. Computer Vision and Graphics. Computational Imaging and Vision, Vol 32. Dordrecht: Springer; 2004: 845-850. DOI: 10.1007/1-4020-4179-9_123.
  9. Myasnikov VV. Recursive algorithm of calculation the convolution of image and inseparable 2-D polynomial FIR-filter. Proc 7th Int Conf Pattern Recogn Image Anal (St. Peterburg, Russia) 2004: 327-330.
  10. Lidl R, Niederreiter H. Finite fields. Cambridge: Cambridge University Press; 1997. ISBN: 978-0-521-39231-0.
  11. Myasnikov VV. On the solution of the recurrent equation used for the FIR-filter implementation. Proc 2nd IASTED Int Multi-Conf on Automation, Control, and Information Technology – Signal and Image Processing 2005; 2005: 158-163.
  12. Ifeachor EC, Jervis BW. Digital signal processing: A practical approach. 2nd ed. Cliffs: Prentice-Hall Inc; 2001. ISBN: 978-0-201-59619-9. .

© 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