(27) 19 * << * >> * Русский * English * Содержание * Все выпуски

О РЕКУРСИВНОМ ВЫЧИСЛЕНИИ СВЕРТКИ ИЗОБРАЖЕНИЯ И ДВУМЕРНОГО НЕРАЗДЕЛИМОГО КИХ-ФИЛЬТРА
Мясников В.В.
Институт систем обработки изображений РАН,
Самарский государственный аэрокосмический университет

 PDF, 401 kB

Страницы: 117-122.

Язык статьи: Русский.

Аннотация:
В работе предлагается метод построения алгоритма рекурсивного вычисления свертки изображения и двумерного фильтра с неразделимой конечной импульсной характеристикой (КИХ). Этот метод основан на представлении конечной импульсной характеристики фильтра через вертикальные и горизонтальные рекуррентные соотношения. Каждое из рекуррентных соотношений приводит к полу-рекурсивной процедуре вычисления свертки изображения и двумерного КИХ-фильтра. В свою очередь, каждая из этих полу-рекурсивных процедур состоит из двух частей. Первая часть процедуры представляет собой рекурсивное соотношение, предназначенное для пересчета значений в процедуре, а вторая часть - нерекурсивное вычисление сверток на границах импульсной характеристики. Для перехода от полученной полу-рекурсивной процедуры к полностью рекурсивному алгоритму вычисления искомой свертки в работе доказывается специальное утверждение. Это утверждение показывает, что если импульсная характеристика искомого фильтра удовлетворяет рекуррентным соотношениям и по вертикали и по горизонтали, тогда все дополнительные импульсные характеристики, с которыми производится вычисление сверток на границах КИХ- фильтра, удовлетворяют тем же рекуррентным соотношениям. Данное утверждение позволяет модифицировать полученную процедуру в полностью рекурсивный алгоритм вычисления свертки изображения и двумерного неразделимого КИХ-фильтра. В работе также приводятся оценки вычислительной сложности предложенного рекурсивного алгоритма, выражаемые числом арифметических операций.

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 twodimensional inseparable FIR filter. Computer Optics 2005; 27: 117-1226.

Acknowledgments:
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

Литература:

  1. Blahut R.E. Fast Algorithms for Digital Signal Processing // Reading, Wokingham: Addison-Wesley, 1985.
  2. Dudgeon D.E., Mersereau R.M. Multidimensional Digital Signal Processing // Prentice-Hall, Inc., Cliffs, 1984.
  3. Ярославский Л.П. О возможности параллельной и рекурсивной организации цифровых фильтров // Радиотехника, No. 3, 1984, стр. 87-91.
  4. Сергеев В.В., Параллельно-рекурсивные КИХ- фильтры для обработки изображений // Компьютерная оптика, 1992. No.10-11, с.186–201.
  5. Chernov A.V. Fast Recursive Computation 1D and 2D Finite Convolution // Proceedings of 7th International Conference on Pattern Recognition and Image Analysis: New Information Technologies, St.Peterburg, Russia, 2004. P.1001-1004.
  6. Glumov N.I. , Myasnikov V.V. , Sergeyev V.V. Application of polynomial bases for image processing using sliding window // SPIE, Image Processing and Computer Optics, 1994. Vol.2363, P.40-49.
  7. Glumov N.I. , Myasnikov V.V. , Sergeyev V.V. Parallel- Recursive Local Image Processing and Polynomial Bases // Proceedings of the Third IEEE International Conference on Electronics, Circuits, and Systems ICECS’96, Rodos, Greece, 1996. P.696-699
  8. Myasnikov V.V. Methods for Designing Recursive FIR Filters // 7-th International Conference on Computer Vision and Graphics (ICCVG-2004), Warsaw, Poland, Springer, 2004. P.845-850.
  9. Myasnikov V.V. Recursive algorithm of calculation the convolution of image and inseparable 2-D polynomial FIR-filter // Proc. of 7th Int. Conf. on Pattern Recognition and Image Analysis: New Information Technologies,
    St.Peterburg, Russia, 2004. P.327-330.
  10. Lidl R. and Niederreiter H. Finite Fields // 2-nd Edition, Cambridge University Press, Cambridge, 1997.
  11. Myasnikov V.V. On the solution of the recurrent equation used for the FIR-filter implementation // The IASTED International Conference on Signal and Image Processing (ACITSIP 2005), Novosibirsk, Russia, June 20-24, 2005 (printing).
  12. Ifeachor E.C., Jervis B.W. Digital Signal Processing: A Practical Approach // Prentice-Hall, Inc., Cliffs, 2002.

© 2009, IPSI RAS
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: journal@computeroptics.ru; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20