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

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

 PDF, 1096 kB

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

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

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

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)

Литература:

  1. Агаян С.С. Успехи и проблемы быстрых ортогональных преобразований // Распознавание, классификация, прогноз. – М.: Наука, 1990. В.3. С. 146-214.
  2. Андерсон Дж.А. Дискретная математика и комбинаторика: Пер. с англ. // М.: ИД »Вильямс», 2004. - 960 с.
  3. Ахмед Н., Рао К. Р. Ортогональные преобразования при обработке цифровых сигналов // М.: Связь, 1980. 248 с.
  4. Баранов С. Н., Домарацкий А. Н., Ласточкин Н. К., Морозов В. П. Процесс разработки программных изделий // М.: Наука. Физматлит, 2000. 176 с.
  5. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов // М.: Мир, 1989. - 448 с.
  6. Быстрые алгоритмы в цифровой обработке изображений. Под ред. Т.С. Хуанга // М.: Радио и связь, 1984. 224 с.
  7. Вариченко Л.В., Лабунец В.Г., Раков М.А. Абстрактные алгебраические системы и цифровая обработка сигналов // Киев: Наукова думка, 1986. 248 с.
  8. Виттих В.А., Сергеев В.В., Сойфер В.А. Обработка изображений в автоматизированных системах научных исследований // М.: Наука, 1982. 214 с.
  9. Власенко В.А., Лапа Ю.М., Ярославский Л.П. Методы синтеза быстрых алгоритмов свёртки и спектрального анализа сигналов // М.: Наука, 1990. 180 с.
  10. Гельфонд А.О. Исчисление конечных разностей. Изд. 3-е, испр // М.: Наука, 1967. 375 с.
  11. Голд Б., Рэйдер Ч. Цифровая обработка сигналов // М.: Советское Радио, 1973. 367 с.
  12. Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. Справочник. Цифровая обработка сигналов // М.: Радио и связь, 1985. 312 с.
  13. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: Пер. с англ. // М.: Мир, 1998. 703 с.
  14. Журавлев Ю.И. Непараметрические задачи распознавания образов // Кибернетика, №6, 1976.
  15. Журавлев Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть I // Кибернетика, 1977. No. 4. С. 5–17.
  16. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. М.: Наука, 1978. № 33. С. 5–68.
  17. Кобер В.И., Овсеевич И.А. Использование информационной избыточности сигналов для снижения вычислительных затрат на их обработку // Радиотехника, 1999. № 5. С. 13-16.
  18. Лабунец В.Г. Алгебраическая теория сигналов и систем: Быстрое многомерное преобразование Фурье. - Свердловск: Изд-во Урал. ун-та, 1989. 196 с.
  19. Лабунец В.Г. Единый подход к алгоритмам быстрых преобразований // Применение ортогональных методов при обработке сигналов и анализе систем. Свердловск: УПИ, 1980. С. 4-14.
  20. Марков А.А., Нагорный Н.М. Теория алгоритмов. – М.: Наука, 1984. 432 с.
  21. Математическая энциклопедия: под редакцией Виноградова И.М. // Т. 1-5, 1977.
  22. Миролюбов А.А., Солдатов М.А. Линейные однородные разностные уравнения // М.: Наука, 1981. 208 c.
  23. Миролюбов А.А., Солдатов М.А. Линейные неоднородные разностные уравнения // М.: Наука, 1986. 127 c.
  24. Мясников В.В. Четные полиномиальные базисы для обработки изображений фильтрами с осесимметричными импульсными характеристиками // Автометрия, No 1, 1996. С. 80-87.
  25. Мясников В.В. Рекурсивный алгоритм вычисления свертки изображения с неразделимым двумерным полиномиальным КИХ-фильтром // Компьютерная оптика, В.26, 2004. C. 80-82.
  26. Мясников В.В. О рекурсивном вычислении свертки изображения и двумерного неразделимого КИХ- фильтра // Компьютерная оптика, 2005. Выпуск 27. C. 117-122.
  27. Никольский С.М. Курс математического анализа. Т.1. 3-е изд., перераб. и доп. // М.: Наука, 1989. 464 c.
  28. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления свёрток // М.: Радио и связь, 1985. 248 с.
  29. Оппенгеймер А.В., Шафер Р.В. Цифровая обработка сигналов: Пер. с англ. // М.: Связь, 1979. 416 с.
  30. Рабинер Л, Гоулд Б. Теория и применение цифровой обработки сигналов: Пер. с англ. // М.: Мир, 1978. 848 стр.
  31. Раудин П.В. Быстрые алгоритмы ДПФ для разреженных входных или выходных данных // 3-я ИКсийская конф. по распознаванию образов и анализу изображений (РОАИ-97). Н.Новгород, 1997. Ч.1. C. 243-247.
  32. Сергеев В.В. Параллельно-рекурсивные КИХ- фильтры для обработки изображений // Компьютерная оптика. 1992. No.10-11. C.186–201.
  33. Сойфер В.А., Храмов А.В. Класс спектрально-рекуррентных алгоритмов оценивания полей // Тезисы доклада 5-го Международного симпозиума по теории информации. Москва; Тбилиси, 1979. Ч.2.
    С. 136-138.
  34. Трахтман А.М., Трахтман В.А. Основы теории дискретных сигналов на конечных интервалах // М.: Советское радио, 1975. 208 с.
  35. Хемминг Р.В. Цифровые фильтры: Пер. с англ. // М.: Советское радио, 1980. 224 с.
  36. Холл М. Комбинаторика: Пер. с англ. // М.: Мир, 1970, 424 с.
  37. Чернов В.М. Арифметические методы синтеза быстрых алгоритмов дискретных преобразований // Диссертация на соискание ученой степени доктора физико-математических наук по специальности 05.13.17 «Теоретические основы информатики». Самара: Институт систем обработки изображений РАН, 1998. 277 с.
  38. Чернов А.В. Быстрое рекурсивное вычисление значений одномерных и двумерных конечных сверток // Компьютерная оптика. 2002. № 25. С.190-197.
  39. Ярославский Л.П. Введение в цифровую обработку изображений // М.: Сов. радио, 1979. 312 с.
  40. Ярославский Л.П. О возможности параллельной и рекурсивной организации цифровых фильтров // Радиотехника, 1984. N 3. С.87-91.
  41. Ярославский Л.П. Цифровая обработка сигналов в оптике и голографии. Введение в цифровую оптику // М.: Радио и связь, 1987. 296 с.
  42. Agarwal R.P. Difference Equations and Inequality: Theory, Methods, and Applications, 2nd ed., rev. exp. // New York: Marcel Dekker, 2000. 998 p.
  43. 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.
  44. Glumov N.I., Myasnikov V.V., Sergeyev V.V. Parallel-Recursive Local Image Processing and Polynomial Bases // Proceedings of the Third IEEE Inrernational Conference on Electronics, Circuits, and Systems ICECS’96. Rodos, Greece, 1996. Vol.2. P.696-699.
  45. Gupta A., Rao K.R. A fast recursive algorithm for the discrete sine transform // IEEE Transactions on Acoustic, Speech and Signal Processing, 1990. Vol. ASSP-38, No.3. P. 553-557.
  46. Hatamian M. A real-time two-dimensional moment generating algorithm and its single chip implementation // IEEE Trans. on Acoustic, Speech and Signal Processing, 1986. Vol. ASSP-34. No.3. P.546-553.
  47. Hou H.S. A fast recursive algorithm for computing the discrete cosine transform // IEEE Transactions on Acoustic, Speech and Signal Processing, 1987. Vol. ASSP-35. No.10. pp.1455-1461.
  48. Jagerman D. Difference Equations with Applications to Queues // New York: Marcel Dekker, 2000. 246 p.
  49. Jain A.K., Jain J.R. Partial differential equations and finite difference methods in image processing. Раrt II - Image restoration // IEEE Transactions on Automatic Control. Vol.AC-23, 1978. P.817-834.
  50. Jain A.K. Partial differential equations and finite difference methods in image processing. Раrt I - Image representation // J. Optimiz. Theory and Appl. 1977. Vol. 23. P. 65-91.
  51. Jordan Ch. Calculus of finite differences, 2nd ed. // New York: Chelsea Publ. Co., 1950. 652 p.
  52. Kober V. A fast recursive algorithm for sliding sine transform // Electronics Letter, 2002. Vol. 38. No.25. Р. 1747-1748.
  53. Kober V., Yaroslavsky L.P. Use of signal redundancy for reduction of signal processing computational time // Proceedings of Seminar on Digital Image Processing in Medicine, Remote Sensing and Visualization of Information. Riga, 1992. P. 7-9.
  54. Kober V., Ovseyevich I.A., Yaroslavsky L.P. Information redundancy of signals: a way to save processing time // Pattern Recognition and Image Analysis, 1993. Vol.3, No. 1. P.15-18.
  55. Li B. High-Order Moment Computation of Grey-Level Images // IEEE Trans. on Image Processing, 1995. Vol. 4. No. 4. P.502-505.
  56. Myasnikov V.V. A Recursive Algorithm for Computing the Convolution of an Image with a Two-Dimensional Indecomposable Polynomial FIR Filter // Pattern Recognition and Image Analysis, 2005. Vol. 15, No. 1.
    P. 260-263.
  57. Myasnikov V.V. Methods for Designing Recursive FIR Filters // Proceedings of International Conference “Computer Vision and Graphics” (ICCVG 2004). Warsaw, Poland, 2004. Springer. P. 845-850.
  58. Myasnikov V.V. Construction of Integer-Value Polynomials for Recursive Calculation of the Convolution with FIR-Filter // Тезисы 7-й Международной конференции «International Conference on Pattern Recognition and Image Analysis». Санкт-Петербург, 2004. P. 331-334.
  59. Myasnikov V.V. Recursive Algorithm of Calculation the Convolution of Image and Inseparable 2-D Polynomial FIR-Filter // Тезисы 7-й Международной конференции «International Conference on Pattern Recognition and Image Analysis», Санкт-Петербург, 2004. P. 327-330.
  60. Myasnikov V.V. 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. P.268-272.
  61. Vitkus R.Y., Yaroslavsky L.P. Recursive algorithms for local adaptive linear filtration // in: Mathematical Research., Eds.: Yaroslavsky L.P., Rosenfeld A. and Wilhelmi W. Academy Verlag, Berlin, 1987. P.34-39.
  62. Yaroslavsky L.P., Kober V. Redundancy of signals and transformations and computational complexity of signal processing // Proceedings of IEEE Conference on Pattern Recognition. Jerusalem, 1994. P.164-166.
  63. Zakaria M.F. et al. Fast algorithm for the computation of moment invariants // Pattern Recognition, 1987. Vol.20, No.6, P. 634-643.

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