Быстрое преобразование Фурье и вейвлетные разложения

Дискретное преобразование Фурье (ДПФ) играет фундаментальную роль в цифровой обработке сигналов и изображений. В этих областях вычисление ДПФ является массовой операцией, а потому требует наличия быстрых и эффективных алгоритмов его реализации. Впрервые алгоритм быстрого вычисления ДПФ для сигнала, размерность которого равна степени двойки, был предложен Кули и Тьюки в 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−269 и частично грант 98−01−196).

1. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989.

2. Голубов Б. И., Ефимов A.B., Скворцов В. А. Ряды и преобразования Уолша. М., 1987.

3. Кирушев В. А. Быстрый алгоритм сжатия изображений. // Вестник молодых ученых. Сер. Прикладная математика и механика. 1997. № 1. С. 4−10.

4. Левкович-Маслюк JT. Дайджест вейвлет-анализа в двух формулах и 22 рисунках. // Компьютерра, 1998, № 8(236), С. 31−37.

5. Макклеллан Дж. X., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1983.

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

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

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

9. Петухов А. П. Дискретные периодические всплески. // Алгебра и анализ. 1996. Т. 8. Вып. 3. С. 151−183.

10. Петухов А. П. Периодические всплески. // Матем. сборник. 1997. Т. 188. № 10. С. 69−74.

11. Спиридонов В. Самоподобие, всплески и квазикристаллы. // Компьютерра, 1998, № 8(236), С. 38−45.

12. Трахтман А. М., Трахтман В. А. Основы теории дискретных сигналов на конечных интервалах. М.: Советское радио, 1975.

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

14. Холл М. Комбинаторика. М., 1970.

15. S. Barash, Ya’acov Ritov. Logarithmic Pruning of FFT Frequencies. J/ IEEE Transactions on Signal Processing. 1993. Vol. 41. № 3. P. 1398−1400.

16. Beylkin G., Coifman R., and Rokhlin V. Fast wavelet transforms and numerical algorithms I. // Communications on Pure and Applied Mathematics, 1991. Vol 44. № 2. P. 141−183.

17. Chui C. An Introduction to Wavelets. Academic Press, Boston, 1992.

18. Cody Mac A. The fast wavelet transform. //Dr. Dobb’s Journal, April 1992, 17(4) :44.

19. Cody Mac A. The wavelet packet transform, j/ Dr. Dobb’s Journal, April 1994, 19(4) :44.

20. Cohen A., Daubechies I., Feauveau J.-C. Biorthogonal Bases of Compactly Supportted Wavelets. // Comm. Pure Appl. Math. 1992. V. 45. № 5. P. 485−560.

21. Coifman R., Meyer Y., Wickerhauser M. Adapted waveform analysis, wavelet-packets and applications, (j Proceedings of ICIAM'91. Philadelphia, 1992, P. 41−50.

22. Cooley J. W., Tukey J. W. An algorithm for the machine calculation of complex Fourier series. // Math. Comput. 1965. Vol. 19. № 90. P. 297−301.

23. Daubechies I. Orthonormal bases of compactly supported wavelets. // Comm. Pure Appl. Math. 1988. V. 41. № 7. P. 909 996.

24. Daubechies I. Ten lectures on wavelets. Philadelphia, 1992.

25. Mallat S. A theory for multiresolution signal decomposition: the wavelet representation. // IEEE Trans, on Patt. Anal, and Mach. Intell., July 1989, P. 674−693.

26. Mallat S. Review of multifrequency channel decompositions of images and wavelet models. // IEEE Trans, of Acoustic Speech and Signal Processing, Dec. 1989.

27. Mallat S. Multiresolution approximation and wavelet orthonormal bases of L2(M). // Trans. Amer. Math. Soc. 1989. Vol. 315. P. 67−89.

28. Mallat S. A wavelet tour of signal processing. Acad. Press., 1998.

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

30. Meyer Y. Ondelettes. Paris, 1990.

31. Meyer Y. Wavelets: Algorithms and Applications. SIAM, Philadelphia, 1993.

32. Meyer Y. Wavelets, vibration and scalings. CRM monograph series, V. 9. AMS. 1998.

33. Skopina M. Discrete Wavelet Fourier Transform. / Proceedings of the 3rd St. Petersburg Workshop on Simulation. St. Petersburg. 1998. P. 384−387.

34. Strang G. Wavelets and dilation equations: a brief introduction. // SIAM Review. 1989. Vol. 31. № 4. P. 614−627.

35. Strang G., Nguyen T. Wavelets and Filter Banks. Wellesley-Cambridge Press, 1996.

36. Sweldens W. Wavelets, Signal Compression and Image Processing. // Wavelets and their Applications in Computer Graphics. SIGGRAPH'95 Course Notes. P. 107−122.

37. Sweldens W., Schroder P. Building your own wavelets at home. Wavelets in Computer Graphics. ACM SIGGRAPH Course Notes. 1996. P. 15−87.

38. Walker J. C. Fourier Analysis and wavelet analysis. // Notices of Amer. Math. Soc. 44(6), 1997. 658.

39. Walsh J. L. A closed set of normal orthogonal functions. // Amer. J. Math. 1923. Vol. 45. P. 5−24.

40. Wickerhauser M. V. Adapted Wavelet Analysis. AK Peters, 1994.

41. Zheludev V. A. Periodic splines, spline harmonic analysis and wavelets. // Proceedings of the Workshop. Israil, 1993.

42. Zheludev V. A. On Signal Processing by Wavelet Packets. / Proceedings of the 3rd St. Petersburg Workshop on Simulation. St. Petersburg. 1998. P. 388−389.

43. Proc. IEEE, 1996, Vol. 84, № 4.44. http://www.wavelet.org/45. http://mathsoft.com/wavelets.html