Сплайны как средство построения эффективных алгоритмов локального линейного преобразования
Мясников В.В.

Институт систем обработки изображений РАН, Самара, Россия,
Самарский государственный аэрокосмический университет им. С.П. Королева, Самара, Россия

Аннотация:
В работе рассматривается частное решение общей задачи синтеза эффективного алгоритма вычисления свертки, возникающее при использовании сплайнов для представления конечной импульсной характеристики (КИХ). Исходя из необходимых условий строгой эффективности индуцированного алгоритма, которые были сформулированы в предыдущей работе [13] в виде требований к неоднородному ЛРС (определяющему отсчеты КИХ), и установленной в настоящей работе явной связи между основными характеристиками сплайна и его представлением в виде ЛРС, приведено обоснование использования сплайнов для решения задачи синтеза эффективного алгоритма. Представлен алгоритм модели CR вычисления свертки, порождаемый произвольным сплайном с конкретными характеристиками. Приведены явные выражения для вычислительной сложности порождаемого алгоритма для случаев обобщенных и полиномиальных сплайнов. При ограничении множества сплайнов параметрами (порядок-число узлов) приведены верхние и нижние границы для вычислительной сложности порождаемых этими сплайнами алгоритмов вычисления свертки. Введено понятие МС-сплайнов, как сплайнов, для которых величина сложности реализации порождаемого ими алгоритма достигает своей нижней границы. Приведены примеры построения полиномиальных МС-сплайнов.

Литература:

  1. Алберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения. – М.: Мир, 1972. – 318 с.
  2. Андерсон Дж.А. Дискретная математика и комбинаторика. – М.: ИД "Вильямс", 2004. – 960 с.
  3. Блейхут Р. Быстрые алгоритмы цифровой обработки сиг-налов. – М.: Мир, 1989. – 448 с.
  4. Быстрые алгоритмы в цифровой обработке изображений. – М.: Радио и связь, 1984. – 224 с.
  5. Вариченко Л.В., Лабунец В.Г., Раков М.А. Абстрактные алгебраические системы и цифровая обработка сигналов. – Киев: Наукова думка, 1986. – 248 с.
  6. Гельфонд А.О. Исчисление конечных разностей. – М.: Наука, 1967. – 375 с.
  7. Голд Б., Рэйдер Ч. Цифровая обработка сигналов. –М.: Со-ветское Радио, 1973. – 367 с.
  8. Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л. Методы сплайн-функций. – М.: Наука, 1980. – 352 с.
  9. Квасов Б.И. Методы изогеометрической аппроксимации сплайнами. – М.: Ижевск: НИЦ «Регулярная и хаотическая динамика», Институт компьютерных исследований, 2006. – 416 с.
  10. Мала С. Вейвлеты в обработке сигналов. – М.: Мир, 2005. – 671 с.
  11. Математическая энциклопедия: под редакцией Виноградова И.М. – М.: Советская энциклопедия, 1977. – Т. 1-5,
  12. Миролюбов А.А., Солдатов М.А. Линейные неоднородные разностные уравнения. – М.: Наука, 1986. – 127 c.
  13. Мясников В.В. Эффективный алгоритм над множеством алгоритмов вычисления свертки // Компьютерная оптика, 2006. Вып. 29. – С. 78-117.
  14. Нуссбаумер Г. Быстрое преобразование Фурье и алгорит-мы вычисления свёрток // М.: Радио и связь, 1985. 248 с.
  15. Оппенгеймер А.В., Шафер Р.В. Цифровая обработка сиг-налов. – М.: Связь, 1979. – 416 с.
  16. Рабинер Л, Гоулд Б. Теория и применение цифровой обра-ботки сигналов. – М.: Мир, 1978. –848 стр.
  17. Стечкин С.Б., Субботин Ю.Н. Сплайны в вычислительной математике. – М.: Наука, 1976. – 248 с.
  18. Тихонов А.Н., Арсенин В.Я. Методы решения некоррект-ных задач. – М.: Наука, 1979. – 142 с.
  19. Ярославский Л.П. Введение в цифровую обработку изоб-ражений. – М.: Сов. радио, 1979. – 312 с.
  20. Agarwal R.P. Difference Equations and Inequality: Theory, Methods, and Applications, 2nd ed., rev. exp. //New York: Marcel Dekker, 2000. – 998 p.
  21. 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.
  22. 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.
  23. Jordan Ch. Calculus of finite differences, 2nd ed. // New York: Chelsea Publ. Co., 1950. 652 p.
  24. Kvasov B.I. Local bases for generalized cubic splines // Rus. J. Numer. Anal. Math. Modeling, 1996. – Vol. 11. – P. 223-246.
  25. Kvasov B.I. GB-splines and their properties // Annals of Nu-merical Mathematics, 1996. – Vol. 3. – P. 139-149.
  26. Lyche T. Discrete cubic spline interpolation. – BIT, 1976. – Vol. 16. – P. 281-290.
  27. 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.
  28. 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
© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846 2) 332-56-22, факс: +7 (846 2) 332-56-20