Быстрое преобразование Фурье и вейвлетные разложения тема автореферата и диссертации по математике, 01.01.07 ВАК РФ



^ ц 0

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Третьяков Алексей Андреевич

БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ВЕЙВЛЕТНЫЕ РАЗЛОЖЕНИЯ

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 1998 г.

Работа выполнена на кафедре исследования операций

математико-механического факультета Санкт-Петербургского государственного университета

Научный руководитель — доктор физико-математических наук, профессор Малоземов Василий Николаевич

Официальные оппоненты — доктор физико-математических наук, профессор Демьянович Юрий Казимирович,

кандидат технических наук Цветков Кирилл Юрьевич

Ведущая организация — Санкт-Петербургский Государственный Электротехнически!! Университет

на заседании диссертационного совета Д 063.57.30 по защите диссертаций на соискание ученой степени доктора физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Петродворец, Библиотечная пл., д. 2, математико-механический факультет, ауд. 4526

С диссертацией можно ознакомиться в научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, г. Санкт-Петербург, Университетская наб.. 7/9.

Защита состоится

часов

Автореферат разослан "

1998 г.

Ученый секретарь диссертационного совета, доцент

Ю. А. Сушков

Общая характеристика работы

Актуальность темы. Дискретное преобразование Фурье (ДПФ) Тц сопоставляет сигналу х сигнал X = Ту (х) с компонентами

= ЕЙ1 к е Ж, где = ехр(27п/Л0.

Оно играет фундаментальную роль в цифровой обработке сигналов и изображений. В 1965 году Кули и Тьюки был предложен алгоритм быстрого вычисления ДПФ для сигнала, размерность которого равна степени двойки.

Новым аппаратом обработки сигналов различной природы является кратномасштабный анализ, основанный на вейвлетах (всплесках), ставших широко известными после работ И. Добеши конца восьмидесятых и начала девяностых годов. Суть его заключается в возможности одновременного анализа временной и частотной компонент сигнала и рассмотрения их с разной степенью подробности (в разном масштабе).

Вейвлетная теория — новая область чистой и прикладной математики, активно развиваемая за рубежом в последние десять лет. Успехи этого направления столь существенны, что говорят о "вей-влетной революции". Это связано с простотой построения основанных на всплесках алгоритмов, а также широтой их приложений в самых разных областях, среди которых сжатие информации, распознавание образов и многое другое.

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

Цель работы.

1) Установить более тесную связь вейвлетной теории с классиче-

ским дискретным гармоническим анализом.

2) Построить на базе классического дискретного гармонического анализа ортогональные вейвлетные базисы.

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

Научная новизна. В диссертации получены следующие основные результаты.

1) Построены рекуррентные последовательности ортогональных базисов в пространстве дискретных периодических сигналов, соответствующие прореживанию по времени и частоте.

2) Установлено, что в процессе реализации алгоритма Кули-Тьюки вычисляются коэффициенты некоторых вейвлетных разложений (в частности, разложения по базису Хаара).

3) Построены рекуррентные последовательности ортогональных базисов в евклидовом пространстве, размерность которого равна степени двойки; указана перестановка, переводящая финальный базис в дискретный базис Уолша.

4) Полученные в пунктах 1) 3) результаты перенесены на двумерный случай.

5) Разработан алгоритм и составлена программа для сжатия изображений на основе дискретного преобразования Уолша. Проведены вычисления по обработке фотографий размером 512 х 512 пикселов в 256 градациях серого цвета.

Практическая ценность. Результаты диссертации могут быть использованы при цифровой обработке сигналов и изображений различной природы.

Апробация работы и публикации. По результатам диссертации сделаны доклады на семинарах кафедры исследования операций и кафедры вычислительной математики мат-мех факультета

СПбГУ, на Санкт-Петербургском городском семинаре по всплескам и их приложениям, на третьем международном семинаре по моделированию (Санкт-Петерб}фг 28 июня - 3 июля 1998 года). По теме диссертации опубликовано пять работ.

Структура и объем работы. Диссертация состоит из введения, двух глав, разбитых на 12 параграфов, и списка литературы. Объем диссертации — 102 страницы. Список литературы насчитывает 45 наименований. В диссертации имеется б рисунков и 2 таблицы.

Содержание работы

Во введении дан краткий исторический обзор и сформулированы основные результаты диссертации.

Глава I посвящена построению вейвлетных разложений одномерных сигналов на основе ДПФ и ДГ1У.

В §1-2 построены рекуррентные последовательности ортогональных базисов в пространстве дискретных периодических сигналов, соответствующие прореживанию по частоте и времени.

Пусть N = 2"; Ns = N/2', As = 2s"1, где s e 1 : n; SN{k) ~ единичный iV-периодический импульс; rev — операция двоичной инверсии.

В случае прореживания по частоте построение происходит так:

Й>(*)=Ы--*0, ke.o-.N-i-, ц.(т + 2/Д.) = \\fi.-i(m + 2/Д,) + + (21 + 1)Д.)],

fis{m + (21 + 1)Д.) = i[ps_i(m + 21Аа) - (т + (21 + 1)Д,)],

где I € 0 : Ns - 1, т € 0 : Д8 - 1, s — 1,2, ...,п.

В случае прореживания по времени построение ведется по формулам

ц0(k) = SN(--k), k е 0:N-1;

Vs(2mNs +/) = (2 mNs + I) + ((2m + 1 )N. + /)],

M(2m + l)Ns + l) = i[p._l(2mNa + l)-uffl2m)ii.-i((2m + l)Nl + l)], где I 6 0 : Ns- 1, m £0 : Д* ~ 1, s= 1.2 ,...,n.

В обоих случаях получены разложения промежуточного базиса \fisik',110 базису нулевого уровня, состоящего из сдвигов единичного импульса. Для прореживания по времени это выглядит так:

1 2Д.-1 в }=0

где I € 0 : Л^ - 1, М € 0 : 2А, - 1, 5 € 0 : п. В случае прореживания по частоте имеем следующее:

где I £ 0 : Лге - 1, М £ 0 : 2Д, - 1, я € 0 : п.

В §3 на основе последовательности промежуточных базисов, соответствующих варианту прореживания по частоте, построено дискретное преобразование Хаара. Выведены расчетные формулы декомпозиции и реконструкции. Указано, что они являются частным случаем (некоторой выборкой) соответствующих формул алгоритма Кули-Тьюки быстрого вычисления ДПФ.

В §4 на основе последовательности промежуточных базисов алгоритма Кули-Тыоки с прореживанием по времени построено простое вейвлетиое преобразование дискретных периодических сигналов, отличное от преобразования Хаара. В определенном смысле предложенное преобразование связано с преобразованием Хаара так же, как алгоритм Кули-Тьки с прореживанием по времени связан с алгоритмом Кули-Тьюки с прореживанием по частоте. Выведены расчетные формулы декомпозиции и реконструкции. Указано, что они являются частным случаем (некоторой выборкой) соответствующих формул алгоритма Кули-Тьюки.

В §5 дается общее описание идеи адаптивной обработки дискретны?: периодических сигналов на базе алгоритма Кули-Тьюки с прореживанием по времени и частоте. Поясняется, как на основе промежуточных базисов этого алгоритма могут быть построены вей-влег-пакеты, существенно расширяющие возможности цифровой обработки сигналов. При этом важно, что мы остаемся в рамках классического дискретного гармонического анализа.

б

В §6 построены две рекуррентные последовательности базисов в евклидовом пространстве, размерность которого равна степени двойки, и изучены их свойства. Обе последовательности начинаются с базиса, состоящего из единичных ортов, и заканчиваются базисом Уолша, элементы которого, однако, плохо упорядочены. Указана перестановка, переводящая полученный базис в упорядоченный по количссву перемен знака базис Уолша. Отмечено, что алгоритмы построения этих последовательностей являются "упрощением" алгоритмов построения промежуточных базисов в алгоритме Кули-Тьюки с прореживанием по времени и частоте. Дается матричная трактовка этого построения. На ее основе доказывается независимость результата от варианта прореживания. Отмечается, что на базе этих последовательностей могут быть сформированы вейвлет-пакеты, применимые для обработки непериодических сигналов.

§7 посвящен решению задачи быстрого вычисления компонент ДПФ, индексы которых равны нулю или степени двойки. Такая выборка и соответствующее ей преобразование названы логарифмическим ДПФ (ЛДПФ). На основе алгоритма Кули-Тьюки с прореживанием по частоте построен алгоритм быстрого ЛДПФ. Доказана его эффективность и посчитано количество арифметических операций при его реализации.

Во второй главе результаты первой перенесены на случай двумерных сигналов, называемых иногда изображениями.

В §1 вводится двумерное ДПФ. Описываются двумерные варианты алгоритма Кули-Тьюки с прореживанием по времени и частоте. Приводится их новое обоснование на основе построения соответствующих рекуррентных последовательностей ортогональных базисов.

В §2 строится вейвлетное разложение Хаара пространства изображений. Описывается формальное построение его базиса на основе тензорного произведения с использованием соответствующих закономерностей в одномерном случае, а также неформальные соображения, приводящие к этому же результату. Выводятся формулы декомпозиции и реконструкции.

В §3 строится двумерный аналог вейвлетного разложения пространства сигналов в случае прореживания по времени. Описыва-

ется формальное построение его базиса на основе тензорного произведения с использованием соответствующих закономерностей в одномерном случае, а также неформальные соображения, приводящие к этому же результату. Выводятся формулы декомпозиции и реконструкции.

В §4 описываются двумерные варианты быстрого преобразования Уолша с прореживанием по времени и частоте. Приводится их обоснование на основе построения соответствующих рекуррентных последовательностей ортогональных базисов.

§5 посвящен сжатию изображений на основе двумерного дискретного преобразования Уолша. Он содержит детальное описание всех этапов алгоритма сжатия и иллюстрирующие его примеры.

Основное содержание диссертации опубликовано в работах:

Третьяков А. А. Быстрое вычисление логарифмического дискретного преобразования Фурье. // Вестник молодых ученых. Сер. Прикладная математика и механика. 1997. № 1. С. 20-25.

Малоземов В. Н., Третьяков А. А. Новый подход к алгоритму Кули-Тьюки . // Вестн. С.-Петербург, ун-та. Сер. 1. 1997. Вып. 3 (№ 15). С. '57-60.

Малоземов В. Н., Третьяков А. А. Алгоритм Кули-Тьюки и дискретное преобразование Хаара. // Вестн. C'.-Петербург. ун-та. Сер. 1. 1998. Вып. 3 (№15). С. 31-34.

Малоземов В. Н., Певный А. В., Третьяков А. А. Быстрое, aeil-влетное преобразование дискретных периодических сигналов и изображений. // Проблемы передачи информации. 1998. Том 34. Вып. 2. С. 77-85.

Malozemov V. N., Tretyakov А. А. The Cooley-Tukey algorithm and wavelet expansions. / Proceedings of the 3rd St. Petersburg Workshop on Simulation. St. Petersburg. 1998. P. 372-375.

Работа выполнена при финансовой поддержке РФФИ (грант 96-01-00269 и частично грант 98-01-00196).

ЛР № 040815 от 22.05.97.

Подписано к печати У .11.1998 г. Объем 1 п. л. Тираж 100 экз. Заказ 525.

НИИ химии СПбГУ.

Отпечатано в отделе оперативной полиграфии НИИХ СП6ГУ.

198904, Санкт-Петербург, Старый Петергоф, Университетский пр 2.

1 : М-1/631

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Третьяков Алексей Андреевич

БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ВЕЙВЛЕТНЫЕ РАЗЛОЖЕНИЯ

01.01.07 — вычислительная математика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель — доктор физико-математических наук, профессор В. Н. Малоземов

Санкт-Петербург 1998 г.

Содержание

Введение 4

Глава I. Вейвлетные разложения сигналов. 13

§1. Новый подход к алгоритму Кули-Тьюки с прореживанием по частоте...................... 14

§2. Новый подход к алгоритму Кули-Тьюки с прореживанием по времени..................... 22

§3. Алгоритм Кули-Тьюки и дискретное преобразование

Хаара............................. 28

§4. Алгоритм Кули-Тьюки и быстрое вейвлетное преобразование дискретных периодических сигналов...... 34

§5. Адаптивная обратка сигналов (общая идея)....... 45

§6. Секционирование, ортогональность и перестановки. . 47 §7. Быстрое логарифмическое дискретное преобразование Фурье............................. 58

Глава II. Вейв летные разложения двумерных сигналов (изображений). 66

§1. Быстрое двумерное дискретное преобразование Фурье. 66

§2. Быстрое дискретное преобразование Хаара пространства изображений...................... 72

§3. Быстрое вейвлетное преобразование дискретных периодических изображений................. 77

§4. Быстрое двумерное дискретное преобразование Уолша. 81 §5. Примеры сжатия изображений на основе быстрого преобразования Уолша..................... 89

Литература 98

Введение

Дискретное преобразование Фурье (ДПФ) играет фундаментальную роль в цифровой обработке сигналов и изображений. В этих областях вычисление ДПФ является массовой операцией, а потому требует наличия быстрых и эффективных алгоритмов его реализации. Впрервые алгоритм быстрого вычисления ДПФ для сигнала, размерность которого равна степени двойки, был предложен Кули и Тьюки в 1965 году [22]. Позже появились быстрые алгоритмы ДПФ для сигналов других размерностей [1, 5]. Одним из вычислительных подходов к ним служит матричная факторизация. Другой подход связан с вычислением значений полинома, коэффициенты которого суть компоненты исходного сигнала, в точках единичной окружности.

Новым аппаратом обработки сигналов различной природы является кратномасштабный анализ, основанный на вейвлетах (всплесках), ставших широко известными после работ И. Добеши [23, 24]. Суть его заключается в возможности одновременного анализа временной и частотной компонент сигнала и рассмотрения их с разной степенью подробности (в разном масштабе).

Вейвлетная теория - новая область чистой и прикладной математики, активно развиваемая за рубежом в последние десять лет [17, 28, 30, 31, 35, 40]. Успехи этого направления столь существенны, что говорят о "вейвлетной революции". Это связано с простотой построения основанных на всплесках эффиктивных алгоритмов, таких например как описанные в [16, 18, 31, 32, 37], а также широтой их приложений в самых разных областях, среди

которых сжатие информации, распознавание образов и многое другое [36, 21, 26, 31, 42].

Еще одним подтверждением термина "вейвлетная революция" и актуальности этой темы может служить обилие публикаций у нас и за рубежом, вышедших и выходящих в последние время по вейвлетам и кратномасштабному анализу. Среди них следует выделить работы [4, 9, 10, 11, 20, 21, 25, 27, 34, 41, 38, 33] как наиболее полно отражающие основные направления развития этой науки. Всплескам посвящены целые номера известных журналов [43]. Есть даже электронный журнал Wavelet Digest [44], а также специальные страницы на популярных математических сайтах в сети Internet [45], посвященные вейвлетам, что свидетельствует о большом интересе к ним.

Одним из наиболее перспективных направлений развития вей-влетной науки является построение так называемых вейвлет-па-кетов. В основанных на них адаптивных алгоритмах обработки сигналов базис, по которому раскладывается сигнал, строится непосредственно в процессе самого разложения с учетом особенностей данного сигнала. Это существенно расширяет возможности обработки сигналов, позволяя проводить более гибкий и тонкий анализ. Как примеры работ этого направления можно привести работы [19, 21, 40].

Целью диссертационной работы является:

1) Установить более тесную связь вейвлетной теории с классическим дискретным гармоническим анализом.

2) Построить на базе классического дискретного гармониче-

ского анализа ортогональные вейвлетные базисы.

Приведем краткий обзор содержания диссертации. Работа состоит из двух глав, разбитых на двенадцать параграфов, шести рисунков, двух таблиц и списка литературы.

В первой главе предлагается и развивается идея нового подхода к алгоритму Кули-Тьюки быстрого вычисления ДПФ [7], связанного с построением рекуррентных последовательностей ортогональных базисов в пространстве дискретных периодических сигналов. На этой основе строятся вейвлетные разложения указанного пространства. Описывается идея адаптивной обработки сигналов на базе классического дискретного гармонического анализа. Показывается, что теже идеи могут быть применены к преобразованию Уолша [2, 12, 39]. Предлагается эффективный алгоритм вычисления "логарифмической" выборки компонент ДПФ.

В первом параграфе первой главы вводится ДПФ, описывается алгоритм Кули-Тьюки с прореживанием по частоте и приводится его обоснование с точки зрения нового подхода. Рекур-рентно строятся базисы, промежуточные между базисом из сдвигов единичного импульса и экспоненциальным базисом. Устанавливается их ортогональность. Формулы пересчета коэффицен-тов разложения сигнала по этим базисам суть формулы алгоритма Кули-Тьюки с прореживанием по частоте.

Во втором параграфе описывается алгоритм Кули-Тьюки с прореживанием по времени и приводится его обоснование с позиции, изложенной выше. Рекуррентно строятся промежуточные базисы, соответствующие этому случаю. Устанавливаются их свойства. Формулы пересчета коэффицентов разложения сигнала

по этим базисам суть формулы алгоритма Кули-Тьюки с прореживанием по времени.

В третьем параграфе на основе последовательности промежуточных базисов алгоритма Кули-Тьюки с прореживанием по частоте построено дискретное преобразование Хаара для дискретных периодических сигналов. Выведены расчетные формулы декомпозиции и реконструкции. Указано, что они являются частным случаем (некоторой выборкой) соответствующих формул алгоритма Кули-Тьюки.

В четвертом параграфе на основе последовательности промежуточных базисов алгоритма Кули-Тьюки с прореживанием по времени построено простое вейвлетное преобразование дискретных периодических сигналов, отличное от преобразования Хаара. В определенном смысле предложенное преобразование связано с преобразованием Хаара так же, как алгоритм Кули-Тьки с прореживанием по времени связан с алгоритмом Кули-Тьюки с прореживанием по частоте. Выведены расчетные формулы декомпозиции и реконструкции. Указано, что они являются частным случаем (некоторой выборкой) соответствующих формул алгоритма Кули-Тьюки.

В пятом параграфе дается общее описание идеи адаптивной обработки дискретных периодических сигналов на базе алгоритма Кули-Тьюки с прореживанием по времени и частоте. Поясняется, как на основе промежуточных базисов этого алгоритма могут быть построены вейвлет-пакеты, существенно расширяющие возможности цифровой обработки сигналов. При этом важно, что мы остаемся в рамках классического дискретного гармонического

анализа.

В шестом параграфе построены две рекуррентные последовательности базисов в евклидовом пространстве, размерность которого равна степени двойки, и изучены их свойства. Обе последовательности начинаются с базиса, состоящего из единичных ортов, и заканчиваются базисом Уолша [2, 12, 39], элементы которого, однако, плохо упорядочены. Указана перестановка, переводящая полученный базис в упорядоченный по количесву перемен знака базис Уолша. Отмечено, что алгоритмы построения этих последовательностей являются "упрощением" алгоритмов построения промежуточных базисов в алгоритме Кули-Тьюки с прореживанием по времени и частоте. Дается матричная трактовка этого построения. На ее основе доказывается независимость результата от варианта прореживания. Отмечается, что на базе этих последовательностей могут быть сформированы вейвлет-пакеты, применимые для обработки непериодических сигналов.

Седьмой параграф посвящен решению задачи быстрого вычисления компонент ДПФ, индексы которых равны нулю или степени двойки. Такая выборка и соответствующее ей преобразование названы логарифмическим ДПФ (ЛДПФ). На основе алгоритма Кули-Тьюки с прореживанием по частоте построен алгоритм быстрого ЛДПФ. Доказана его эффективность и посчитано количество арифметических операций при его реализации. Эта часть работы является детальной разработкой идеи, описанной в [15].

Во второй главе результаты первой перенесены на случай двумерных сигналов, называемых иногда изображениями. Показано,

что этот перенос может быть сделан как на основе тензорного произведения, так и без него, опираясь лишь на природу самих изображений. Описаны двумерные варианты алгоритма Кули-Тьюки с прореживанием по времени и частоте и дискретного преобразования Уолша. Построены рекуррентные последовательности промежуточных базисов указанных двумерных алгоритмов. На основе этих последовательностей построены вейвлетные разложения пространства дискретных изображений. Замечено, что соответствующие им вейвлетные преобразования реализуются в ходе выполнения двумерного алгоритма Кули-Тьюки. На основе двумерного преобразования Уолша описан алгоритм сжатия изображений (фотопортретов на неярком фоне) и приведены примеры такой обработки.

В первом параграфе второй главы вводится двумерное ДПФ. Описываются двумерные варианты алгоритма Кули-Тьюки с прореживанием по времени и частоте. Приводится их новое обоснование на основе построения соответствующих рекуррентных последовательностей ортогональных базисов.

Во втором параграфе строится вейвлетное разложение Хаара пространства изображений. Описывается формальное построение его базиса на основе тензорного произведения с использованием соответствующих закономерностей в одномерном случае, а также неформальные соображения, приводящие к этому же результату. Выводятся формулы декомпозиции и реконструкции.

В третьем параграфе строится двумерный аналог вейвлетного разложения пространства сигналов в случае прореживания по времени. Описывается формальное построение его базиса на основе

тензорного произведения с использованием соответствующих закономерностей в одномерном случае, а также неформальные соображения, приводящие к этому же результату. Выводятся формулы декомпозиции и реконструкции.

В четвертом параграфе описываются двумерные варианты быстрого преобразования Уолша с прореживанием по времени и частоте. Приводится их обоснование на основе построения соответствующих рекуррентных последовательностей ортогональных базисов.

Пятый параграф посвящен сжатию изображений на основе двумерного дискретного преобразования Уолша. Он содержит детальное описание всех этапов алгоритма сжатия и иллюстрирующие его примеры. Эта часть диссертации аналогична работе [3], где в основе алгоритма сжатия лежит дискретное преобразование Хаара.

На защиту выносятся следующие основные результаты:

1) Построены рекуррентные последовательности ортогональных базисов в пространстве дискретных периодических сигналов, соответствующие прореживанию по времени и частоте.

2) Установлено, что в процессе реализации алгоритма Кули-Тьюки вычисляются коэффициенты некоторых вейвлетных разложений (в частности, разложения по базису Хаара).

3) Построены рекуррентные последовательности ортогональных базисов в евклидовом пространстве, размерность которого

равна степени двойки; указана перестановка, переводящая финальный базис в дискретный базис Уолша.

4) Полученные в пунктах 1)-3) результаты перенесены на двумерный случай.

5) Разработан алгоритм и составлена программа для сжатия изображений на основе дискретного преобразования Уолша. Проведены вычисления по обработке фотографий размером 512 х 512 пикселов в 256 градациях серого цвета.

Основные результаты диссертации опубликованы в работах :

Третьяков А. А. Быстрое вычисление логарифмического дискретного преобразования Фурье. // Вестник молодых ученых. Сер. Прикладная математика и механика. 1997. № 1. С. 20-25.

Малоземов В. Н., Третьяков А. А. Новый подход к алгоритму Кули-Тьюки . // Вестн. С.-Петербург, ун-та. Сер. 1. 1997. Вып. 3 (№ 15). С. 57-60.

Малоземов В. Н., Третьяков А. А. Алгоритм Кули-Тьюки и дискретное преобразование Хаара. // Вестн. С.-Петербург, унта. Сер. 1. 1998. Вып. 3 (№15). С. 31-34.

Малоземов В. Н., Певный А. Б., Третьяков А. А. Быстрое вейвлетное преобразование дискретных периодических сигналов и изображений. // Проблемы передачи информации. 1998. Том 34. Вып. 2. С. 77-85.

Malozemov V. N., Tretyakov А. А. The Cooley-Tukey algorithm and wavelet expansions. / Proceedings of the 3rd St. Petersburg Workshop on Simulation. St. Petersburg. 1998. P. 372-375.

Автор приносит искреннюю благодарность своему научному руководителю профессору В. Н. Малоземову за помощь в постановке задач и анализе результатов, а также внимание и заботу в течении всего времени работы над диссертацией.

Работа выполнена при финансовой поддержке РФФИ (грант 96-01-00269 и частично грант 98-01-00196).

Глава I

Вейвлетные разложения сигналов

ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ

Систематически будут использоваться следующие обозначения: Ж, С — множества соответственно целых, вещественных и

комплексных чисел; к : ] — множество целых чисел от к до ] включительно; 71, N — 2", Л^ = N/2* и А« = 25-1 — натуральные числа ; ин = ехр(27гг/'Ы) = со8(27г/Аг) + гвт(27т/М) — корень степени из единицы (по формуле Муавра = 1); С/у — линейное пространство сигналов — комплекснозначных

^-периодических последовательностей х = ] Е

(х,у) = Х^^о1 х{з)у(з) — скалярное произведение сигналов жиг/;

сигналы х,у называются ортогональными, если (х,у) = 0; |Н| = (ж,х)1/2 = ^^^"о11ЖС?)|2) — норма сигнала х; &ы{з) — единичный Ж-периодический импульс — сигнал, равный единице при ] = 0, ±2Ж, ... и равный нулю при остальных ] Е Ъ.

Лемма. Любой сигнал х допускает представление

N-1

хО) = ^2х(к)5ми-к), ¿еж. (о)

к=0

Доказательство. Указанное равенство достаточно проверить при 3 £ 0 : N — 1. Поскольку при Е 0 : N — 1 выполняется

неравенство \j — к\ ^ N— 1, то S^(j — k) — 0 при к ф j и —&) = 1 при к = j. Учитывая это, получаем

N-1

Y^x(k)SN(j - к) = x(j).

к=о

Лемма доказана.

§ 1. Новый подход к алгоритму Кули-Тьюки с прореживанием по частоте.

В 1965 году Кули и Тьюки предложили быстрый алгоритм вычисления дискретного преобразования Фурье (ДПФ) Tn '• Сдт —> Сjv, сопоставляющего сигналу х сигнал X = J~n{%) с компонентами

N-1

Х(*0 = *eZ, (1.1)

i=o

для N = Т [22] .

Одним из его вариантов является быстрое преобразование Фурье (БПФ) с прореживанием по частоте. Для его описания нам потребуется перестановка reverse (сокращенно rev). Число j € 0 : 2п — 1 можно записать в двоичном коде, содержащем п двоичных разрядов. Перестановка reverse сопоставляет числу j число rev(j), двоичный код которого равен перевернутому двоичному коду числа j. С ее помощью формулы БПФ с прореживанием по частоте могут быть записаны так:

xQ(j)=x(rev(j)), j Е 0 : iV — 1; (1.1а)

xs(m+2lAs) =

= (т + 21&8) + (т + (21 + 1)Дв), (1.16)

жв(т + (2/ + 1)Дв) =

= х8-1(т + 21А8) - (т + (21 + 1)Дв). (1.1с)

Здесь I 6 0 : ^ - 1, гаеО:А8-1, в = 1,2,..., п. На выходе этого алгоритма получаем

хп(к)=Х(к), кеО:Х-1.

Приведем новое обоснование алгоритма, связанное с построением последовательности ортогональных базисов в пространстве

С*.

С одной стороны, произвольный сигнал х может быть представлен как линейная комбинация линейно независимых сдвигов единичного ^-периодического импульса по формуле (0). Вместе с тем по формуле обращения для ДПФ [5]

N-1

= ¿ег,

к=0

где коэффициенты Х(к) вычисляются по формуле (1.1). Таким образом, можно считать, что дискретное преобразование Фурье обеспечивает переход от разложения сигнала х по базису к разложению по базису Построим некоторую последовательность промежуточных базисов {¡¿8(к;, в = 0,1, ...,п. Сигнал как элемент пространства С^ будем обозначать ^8(к). Положим

¡¿0(к)=дм(--к), кв 0:ЛГ-1; (1.2а)

fis(m+2lAs) =

= ±[/ie_i(m + 21 Ав) + + (21 + 1)AS)], (1.26)

ц8(т+(21+\)А8) =

= ¡[fis-i(m + 21 As) - + (2/ + 1)AS)]. (1.2c)

Здесь I G 0 : iVs — 1, m G 0 : As — 1, s = 1,2, ...,n. Лемма. Справедливо равенство

1 2Дв-1

/xs(M + 2/Дв) = од- E M<Z + 2lAs)u^{q\ (1.3)

s 9=0

где I G 0 : iVs - 1, M G 0 : 2AS - 1, s G 0 : n.

Доказательство. При s = 0 формула (1.3) тривиальна. При s = 1 формулы (1.26), (1.2с) принимают вид

/ц(2/) = 1) + /10(2/ + 1)], I G 0 : Nx - 1;

/Л(21 + 1) = |[/i0(20 - /¿0(21 + 1)], I G 0 : iVi - 1. Это соответствует (1.3), если учесть, что

rev(l) _ N/2 _ -iV — -

Сделаем индукционный переход от s — 1 к s. Для этого нам потребуются легко проверяемые свойства описанной выше перестановки reverse: при q G 0 : As — 1

Ns + rev(g) = rev(As + q), (1.4)

Asrev(g) = 0 mod 2n (1.5)

Поясним их, считая, что s ^ 2.

s?

Пусть q G 0 : As — 1. Тогда

q = qi2s~2 + • • ■ + gs-221 + gs-i, qk G {0,1};

As