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

Институт систем обработки изображений РАН, Самара, Россия,

Самарский государственный аэрокосмический университет, Самара, Россия

Аннотация:
Основной задачей настоящей работы является разработка нового класса вычислительно эффективных алгоритмов локального вейвлет-преобразования. Предполагается замена иерархической (пирамидально-рекурсивной) вычислительной конструкции, присущей известным алгоритму «с дырами» («algorithme a trous», М.Холшнайдер и др, 1989) [12] и алгоритму быстрого ортогонального вейвлет-преобразования (алгоритм С.Малла, 1987) [3,6,11], на (горизонтально-) рекурсивную, в которой вычисление коэффициентов вейвлет-преобразования производится для всех позиций вейвлета заданного масштаба последовательно, то есть в режима «скользящего окна». Замена иерархической вычислительной конструкции на горизонтально-рекурсивную позволяет рассмотреть задачу построения базисных вейвлетов, которые удовлетворяют требованиям рекурсивности. Эта задача в общем случае включает в себя ряд подзадач, связанных с анализом основных классов вейвлетов: базисных (материнских), двухпараметрических, каркасов (фреймов), R-вейвлетов, полуортогональных и ортогональных. Настоящая работа посвящена вопросу построения эффективных алгоритмов для наиболее простого класса базисных (материнских) вейвлетов, а также определения условий/ограничений на вейвлеты, при которых такие алгоритмы существуют. Приводятся примеры новых и известных вейвлетов, для которых существуют эффективные (рекурсивные) алгоритмы вычисления локального дискретного вейвлет-преобразования.

Литература:

Андерсон, Дж.А. Дискретная математика и комбинаторика / Дж.А. Андерсон - М.: ИД «Вильямс», 2004.
Гельфонд, А.О. Исчисление конечных разностей / А.О. Гельфонд - М.: Наука, 1967.
Добеши, И. Десять лекций по вейвлетам / И. Добеши - Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.
Завьялов, Ю.С. Методы сплайн-функций / Ю.С. Завьялов, Б.И. Квасов, В.Л. Мирошниченко - М.: Наука, 1980.
Копенков, В.Н. Быстрые алгоритмы локального дискретного вейвлет-преобразования с базисом Хаара / В.Н. Копенков, В.В. Мясников // Труды научно-технической конференции с международным участием «Перспективные информационные технологии в научных исследованиях, проектировании и обучении “ПИТ-2006”», Самара, 2006. - С. 113-118.
Малла, С. Вейвлеты в обработке сигналов / С. Малла - М.: Мир, 2005.
Мясников, В.В. Сплайны как средство построения эффективных алгоритмов локального линейного преобразования / В.В. Мясников // Компьютерная оптика, 2007. - Т. 31. - № 2. - С. 52-68.
Мясников, В.В. Эффективный алгоритм над множеством алгоритмов вычисления свертки / В.В. Мясников // Компьютерная оптика, 2006. - В. 29. - С. 78-117.
Нуссбаумер, Г. Быстрое преобразование Фурье и алгоритмы вычисления свёрток // Г. Нуссбаумер - М.: Радио и связь, 1985.
Петухов, А.П. Введение в теорию базисов всплесков. Учебное пособие // А.П. Петухов - СПб: Изд-во СПбГТУ, 1999.
Чуи, К. Введение в вейвлеты // К. Чуи - М.: Мир, 2001.
Holschneider, M. A real-time algorithm for signal analysis with help of the wavelet transform / M. Holschneider [and others] // Wavelets, Time-Frequency Methods and Phase Space, Chapter A. - Berlin: Springer-Verlag, 1989. P. 289-297.