Гармонический анализ на базе дискретного преобразования Ахмеда-Рао тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Коровкин, Александр Владимирович

• Коровкин, Александр Владимирович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Коровкин, Александр Владимирович

Введение

§1. Предварительные сведения.

§2. Базисы Ахмеда-Рао.

§3. Быстрое преобразование Ахмеда-Рао, связанное с прореживанием по частоте.

§4. Быстрое преобразование Ахмеда-Рао, связанное с ирореживанием но времени.

§5. Обобщенное преобразование Ахмеда-Рао.

§G. Примеры сжатия изображений на основе преобразования

Ахмеда-Рао.

Введение диссертации (часть автореферата) на тему «Гармонический анализ на базе дискретного преобразования Ахмеда-Рао»

До 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].

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

Список литературы диссертационного исследования кандидат физико-математических наук Коровкин, Александр Владимирович, 2004 год

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.