Гармонический анализ на базе дискретного преобразования Ахмеда-Рао

До 1970;х годов основным инструментом дискретного гармонического анализа являлось дискретное преобразование Фурье [2, 7, 18, 38]. В 1980;х годах стали больше уделять внимания другим ортогональным преобразованиям, таким как преобразование Уолша, Хаара, Виленкина—Крестенсона, дискретное косинусное и т. п. [1, G, 8, 11, 35]. Для всех указанных преобразовании были разработаны быстрые алгоритмы.

Одним из источников быстрых ортогональных преобразований является матричная факторизация — представление матрицы ортогонального преобразования в виде произведения слабозанолненных матриц. Эффективные расчётные формулы получаются путем использования индексной техники, когда при умножении разреженной матрицы на вектор убираются все операции с нулевыми элементами матриц. В последние годы был разработан новый подход к быстрым ортогональным преобразованиям. В работах [19, 20, 25, 2G] результаты промежуточных вычислений интерпретируются как коэффициенты разложения по некоторым ортогональным базисам. В пространстве дискретных периодических сигналов при длине периода, равной степени двойки, построены рекуррентные последовательности ортогональных базисов, имеющих блочную структуру. В каждом блоке сигналы различаются лишь сдвигом аргумента. Из блоков, принадлежащим разным базисам рекуррентной последовательности, формируются обобщённые вейвлетные базисы. Это значительно расширяет возможности цифровой обработки сигналов. В работе [27] с аналогичных позиций проанализировано дискретное преобразование Уолша, а в [21, 28] — дискретное преобразование Виленкина—Крес-тенсона.

В диссертационной работе рассматривается дискретное преобразование Ахмеда-Рао. В отличии от традиционной ситуации, когда для получения быстрого алгоритма разложения сигнала фактори-зуется известная матрица ортогонального преобразования, а базисные функции выражены явно, в монографии [1] реализован обратный подход. Дискретное преобразование Ахмеда-Рао задаётся в виде произведения разреженных матриц, а свойства базисных сигналов нужно вывести из свойств матриц, входящих в факторизацию.

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

§ 1. Изучить структуру и фундаментальные свойства базисов Ахмеда-Рао.

§ 2. Построить быстрые алгоритмы декомпозиции и реконструкции сигналов и изображений по базисам Ахмеда-Рао.

§ 3. Разработать соответствующее программное обеспечение.

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

В первом параграфе вводится терминология и описываются основные объекты дискретного гармонического анализа. Дается определение и основные свойства перестановки reverse. Приводятся необходимые свойства кронекерова произведения матриц.

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

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

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

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

В шестом параграфе результаты параграфов 3−4 перенесены на двумерный случай. Описаны двумерные варианты быстрого преобразования Лхмеда-Рао, связанного с прореживанием, но времени и с прореживанием, но частоте. Описан алгоритм обработки как черно-белых, так и цветных изображений, являющийся алгоритмом сжатия с потерями. Приведены примеры такой обработки. Этот параграф диссертации во многом аналогичен работе [13], где в основе алгоритма сжатия лежит быстрое преобразование Хаара. Следует отметить также большое количество литературы по сжатию и обработке изображений [3, 33, 41, 42].

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

§ 1. В пространстве дискретных N-периодических сигналов построены рекуррентные последовательности ортогональных базисовприводящих к обобщенному базису Ахмеда-Рао.

§ 2. Получен явный вид функций из обобщенного базиса и указаны условия их ортогональности.

§ 3. Для функций из серии дискретных базисов Ахмеда-Рао, включающей базисы Фурье и Уолша, получено более простое явное представление и рассмотрен вопрос об их частоте.

§ 4. Реализован алгоритм сжатия изображений па основе преобразования Ахмеда-Рао.

Основные результаты диссертации опубликованы в работах [14, 16, 15, 17, 39].

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

1. Ахмед Н., Рао К. Р. Ортогональные преобразования при обработке цифровых сигналов. М.: Снизь, 1980.

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

3. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. М.: ДИАЛОГ-МИФИ, 2002.

4. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления, М.: Наука, 1984.

5. Воробьев В. И., Грибунин В. Г. Теория и практика вейвлет-преобразования. СПб: ВУС, 1999.G. Голубов Б. И., Ефимов А. В., Скворцов В. А. Ряды м преобразования Уолша. М.: Наука, 1987.

6. Гольденберг Л. М., Матюшкин Б. Д., Поляк М. Н. Цифровая обработка сигналов. М.: Радио и связь, 1985.

7. Дагман Э. Е., Кухарев Г. А. Быстрые дискретные ортогональные преобразования. Новосибирск: Наука, 1983.

8. Добепш И. Десять лекций по вейвлетам. М.: РХД, 2001.

9. Дьяконов В. П. Всйвлсты. От теории к практике. М.: COJIOH-Р, 2002.

10. Залманзон J1.A. Преобразования Фурье, Уолта, Хаара и их применение в управлении, связи и других областях. М.: Наука, 1989.

11. Зеленков А. В. Быстрое преобразование спектра сигнала из базиса функций Уолиш в базис дискретных экспоненциальных функции // Радиотехника и электроника. 1977. JV93. С. 552−5G5.

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

13. Коровкин А. В., Малозёмов В.II. Базисы Ахмсда-Рао // Мат. заметки. 2004. Т.75. Вып. 6. С. 834−840.

14. Коровкин Л. В. Обобщённое дискретное преобразование Ахмеда-Рао // Вестник молодых учёных. Сер. «Прикладная математика и механика». 2003. Л" «2. С. 33−41.

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

16. Малоземов В. П., Машарский С. М. Основы дискретного гармонического анализа. СПб.: НИИММ, 2003.

17. Малоземов В. Н., Машарский С. М. Формула Глассмапа, быстрое преобразование Фурье и вейвлетные разлоо1сения // Труды Санкт-Петербургского математического общества. Т.9. 2001. С. 97−119.

18. Малоземов В. П., Машарский С. М. Обобщенные вейвлетные базисы, связанные с дискретным преобразованием Виленкина-Крсстенсона // Алгебра и анализ. 2001. Т.13. Вып.1. С. 111−157.

19. Малоземов В. Н., Машарский С. М. Сравнительное изучение двух вейвлетных базисов // Проблемы передачи информации. 2000. Т. 30. Выи. 2. С. 27−37. •.

20. Малоземов В. Н., Машарский С. М. Хааровскис спектры дискретных сверток j/ Журн. вычисл. мат. и матем. физ. 2000. Т. 40. jV6. С. 954−9G0.

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

22. Малоземов В. Н., Третьяков А. А. Секционирование, ортогональность и перестановки // Вестн. С-Петербург. ун-та. Сер.1. 1999. Вын.1 (Ш). С. 16−21.

23. Машарский С. М. Гармонический анализ па базе дискретного преобразования Вилснкина-Крсстснсона Диссертация на соискание ученой степени кандидата физико-математических наук. СПбГУ, 2001.

24. Новиков JI. В. Спектральный анализ сигналов в базисе всйвле-тов II Научное приборостроение. 2000. Т. 10. № 3. С. 57−64.

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

26. Smith S. The Scientist and Engineer’s Guide to Digital Signal Processing. Califirnia Technical Publ., 1999.