Содержание к диссертации
Введение
ГЛАВА 1. Предварительные сведения из алгебры и теории быстрых алгоритмов дискретных ортогональных преобразований 15
1.1. Конечномерные алгебры 15
1.1.1. Матричное представление операций 19
1.1.2. Процедура удвоения Грассмана-Клиффорда 20
1.1.3. Сложность операций в гиперкомплексных алгебрах 21
1.1.4. Представление комплексных чисел в у-кодах 25
1.2. Быстрые алгоритмы дискретного преобразования Фурье 30
1.2.1. Декомпозиция Кули-Тьюки 30
1.2.1.1 Декомпозиция Кули-Тьюки "по основанию два" 30
1.2.3.3. Декомпозиция Кули-Тьюки "с расщеплением основания" (сплит-радикс алгоритм) 32
1.2.2. Декомпозиция многомерных ДПФ 32
1.2.3. Совмещенные алгоритмы ДПФ 34
1.3. Гиперкомплексные ДПФ вещественного сигнала 39
1.3.1. Кватернионное ДПФ вещественного сигнала 39
1.3.1.1. Алгоритм КДПФ с декомпозицией "по основанию два" 40
1.3.1.2. Алгоритм КДПФ с декомпозицией "по основанию четыре" 42
1.3.1.3. Алгоритм КДПФ "с расщеплением основания" 44
ГЛАВА 2. Исследование структуры используемых конечномерных алгебр 45
2.1. Четырехмерная коммутативно-ассоциативная гиперкомплексная алгебра 45
2.2. Арифметическая сложность операций в двумерной коммутативно-ассоциативной гиперкомплексной алгебре 49
2.3. Представления четырехмерной ассоциативно-коммутативной гиперкомплексной алгебры в у -кодах 52
2.4. Арифметическая сложность операций в у-кодах 54
2.5. Структура многомерных коммутативно-ассоциативных гиперкомплексных алгебр 56
2.6. Арифметическая сложность операций в многомерной коммутативно-ассоциативной гиперкомплексной алгебре 65
2.7. Представления в обобщенных у-кодах 69
2.8. Арифметическая сложность операций в обобщенных у -кодах 73
2.9. Выводы и результаты главы 2 74
3. Быстрые алгоритмы гиперкомплексного ДПФ 75
3.1. Алгоритмы двумерного гиперкомплексного ДПФ 75
3.1.1. Совмещенный алгоритм двумерного ГДПФ вещественного сигнала 76
3.1.1.1. Алгоритм двумерного ГДПФ гиперкомплексного сигнала "по основанию два" 79
3.1.1.2. Алгоритм двумерного ГДПФ гиперкомплексного сигнала "по основанию четыре" 84
3.1.1.3. Алгоритм двумерного ГДПФ гиперкомплексного сигнала "с векторным расщеплением" 87
3.1.2. Использование принципа симметрии гиперкомплексной алгебры при синтезе ГДПФ 92
3.1.2.1. Алгоритм двумерного ГДПФ вещественного сигнала "по основанию два" 92
3.1.2.2. Алгоритм двумерного ГДПФ вещественного сигнала "по основанию четыре" 95
3.1.3. Сравнительный анализ вычислительной сложности алгоритмов двумерного ГДПФ 97
3.3. Алгоритмы многомерного ГДПФ в алгебре B>d 102
3.3.1. Совмещенные алгоритмы многомерного ГДПФ вещественного сигнала 103
3.3.1. Алгоритм многомерного ГДПФ гиперкомплексного сигнал с декомпозицией "по основанию два" 106
3.3.2. Алгоритм многомерного ГДПФ гиперкомплексного сигнал с декомпозицией "по основанию четыре" 108
3.3.3. Алгоритм многомерного ГДПФ гиперкомплексного сигнала "с векторным расщеплением" 110
3.4. Алгоритм многомерного ГДПФ вещественного сигнала "по основанию три" 112
3.5. Сравнительный анализ вычислительной сложности алгоритмов 114
3.6 Результаты и выводы главы 3 116
Заключение 117
Список использованных источников 118
- Сложность операций в гиперкомплексных алгебрах
- Алгоритм КДПФ с декомпозицией "по основанию два"
- Структура многомерных коммутативно-ассоциативных гиперкомплексных алгебр
- Алгоритм двумерного ГДПФ гиперкомплексного сигнала "по основанию четыре"
Введение к работе
Целью работы является разработка вычислительно эффективных (быстрых) алгоритмов дискретных ортогональных преобразований со значениями спектра в гиперкомплексных алгебрах.
Актуальность темы. Историю быстрых алгоритмов обработки сигналов принято отсчитывать с 1965 г., когда Кули и Тьюки [118] опубликовали свой быстрый алгоритм вычисления дискретного преобразования Фурье (БПФ), хотя ранее Гуд (1960г.) и Томас (1963г.) опубликовали в практически незамеченных современниками работах [133, 151] свои быстрые алгоритмы дискретного преобразования Фурье, базирующиеся на несколько ином подходе. За время, прошедшее с первых публикаций, дискретный спектральный анализ стал одним из основных средств решения задач цифровой обработки сигналов, распознавания образов, машинного зрения, компьютерной оптики и т.д.
Разработке эффективных (быстрых) алгоритмов вычисления спектров различных дискретных преобразований посвящено большое количество публикаций, как у нас в стране, так и за рубежом [16, 18, 19, 20, 25, 26, 30, 34, 35,44-46, 52, 54, 58, 60, 68, 72-76, 84, 86, 95, 107-108, ПО, 116, 148, 152].
Значительный вклад в развитие общей теории дискретных преобразований и их быстрых алгоритмов внесли С.С. Агаян, Н.Н. Айзенберг, В.А. Власенко, В.Г. Лабунец, A.M. Крот, A.M. Трахтман, В.М. Чернов, Л.П. Ярославский, Р. Агарвал, Ш. Виноград, Г. Нуссбаумер, Ч. Рейдер и др.
Высокоэффективные алгоритмы конкретных преобразований, адаптированные к характеристикам применяемых вычислительных средств разработаны И.Е. Капориным, Е.Е. Тыртышниковым, A.M. Григоряном и другими исследователями [29,30, 37, 41, 64, 66, 67, 110, 121-123, 150, 153-156].
В настоящее время теория дискретных преобразований развивается, в основном, в следующих направлениях:
1) синтез параметрических семейств новых ортогональных базисов со структурой быстрых алгоритмов, инвариантной по отношению к той или иной принятой авторами концепции синтеза таких алгоритмов (кронекеровская факторизация, полиномиальные преобразования и т.п.) [48,50,51,78,80,87-88];
2) распространение идей и методов классического дискретного "комплексного" спектрального анализа на функции, определенные на группах и принимающие значения в алгебрах достаточно общего вида [6, 47,49,53,84,99-105, 112];
3) разработка новых конкретных алгоритмов, обладающих повышенной точностью и быстродействием, адекватных по структуре вычислений последним разработкам в области специализированных процессоров [2,3,4].
Настоящая работа относится к направлениям 2) и 3) развития теории дискретных ортогональных преобразований, перечисленным выше, и их быстрых алгоритмов. Необходимость рассмотрения дискретных ортогональных преобразований со значениями спектров в алгебрах, более общих, чем двумерная алгебра комплексных чисел (гиперкомплексных алгебрах) определяется в основном уже разработанными и перспективными приложениями таких преобразований к решению широкого круга задач информатики. Так, например:
1. Начиная с работ [131, 132, 136, 141, 142] началось активное применение идей псевдоевклидовой геометрии в теории распознавания образов, а также для моделирования и объяснения структурных свойств гипотетического видимого пространства. В работе В.Г.Лабунца [140] высказано мнение, поддерживающее идею Клейна о том, что геометрия -это изучение тех свойств объектов, которые остаются инвариантными под воздействием специфических групп преобразований. Представление данных в гиперкомплексных алгебрах Клиффорда позволило разработать новые методы распознавания инвариантов изображения в евклидовом и неевклидовом двумерном, трехмерном и n-мерном пространстве. Такие инварианты являются характерными именно для геометрических свойств изображений, в то время как классические "комплексные" спектральные методы ориентированы на анализ, в основном, "усредненных", "энергетических" свойств сигнала и малочувствительны к тонким геометрическим свойствам, которые и являются наиболее информативными.
2. В работах [92, 97, 130, 147] изучается возможность построения нейронных сетей в алгебре Клиффорда. В частности, рассматриваются многослойные перцептроны с описанием в терминах алгебры Клиффорда. С помощью полученных многослойных перцептронов строится аппроксимация комплекснозначной функции.
3. В работе [149] рассматривается приложения гиперкомплексного представления сигнала к сегментации текстур. В качестве практического применения демонстрируется использование кватернионной сегментации Габора для обнаружения дефектов на тканевых материалах. Свойством данного алгоритма является его слабая чувствительность к изменению освещенности и низкая вычислительная сложность.
4. В монографии Я.А. Фурмана [70] предложен способ распространения на кватернионные сигналы понятие авто- и взаимно корреляционных функций, согласованной фильтрации и т.д., что позволило с единых позиций рассматривать обработку как контуров, так и групповых точечных объектов, заданных на плоскости или в трехмерном пространстве.
Вышеприведенные примеры, относящиеся к различным прикладным задачам цифровой обработки сигналов, при решении которых явным или неявным образом используются гиперкомплексные структуры и дискретный спектральный анализ со значениями спектров в этих структурах, являются достаточной мотивацией для постановки указанной выше цели диссертационного исследования.
Основным объектом исследования диссертационной работы является дискретное ортогональное преобразование, имеющее в двумерном случае вид F(mljW2)=X IVvM .O a-l, (0.1) п\ =0 "2 0 27IE] / 2ЛЕ2/ где Wj=e N, w2=e N , вх,е2 - образующие элементы некоторой четырехмерной гиперкомплексной алгебры, а также его многомерные обобщения: Н ) = і /(vMftv) (0.2) 2ЛЄІ / где 11 = (/ ,..., ), v = (w1,...,wrf), (n,v) = n " 0;=e /лг / = {l,..., }, /є/ 8 ...,8 образующие элементы некоторой 2 -мерной гиперкомплексной алгебры.
Заметим, что классическое многомерное дискретное преобразование Фурье является частным случаем преобразования (0.2) при el=... = ed =i. Это позволяет утверждать, что с помощью преобразования (0.2) эффективно решается весь круг задач, цифровой обработки сигналов, для решения которых используется дискретное преобразование Фурье (быстрое вычисление дискретной свертки, фильтрация, компрессия сигналов и т.д.). В задачи диссертационного исследования не входит рассмотрение примеров решения подобных задач с помощью преобразований (0.2). Основной целью работы является разработка эффективной алгоритмической поддержки решения указанных задач с помощью новых преобразований (0.2) со значениями в тех гиперкомплексных алгебрах, для которых быстрые алгоритмы ГПДФ обладают минимальной вычислительной сложностью
Преобразование (0.1) для случая алгебры кватернионов [24, 134, 135] введено впервые в работе [84, 104] как вспомогательное преобразование. В работах [137-142, 149] преобразование применялось для решения прикладных задач, перечисленных выше в пп.1-4.
Следует отметить, что использование в цитированных работах некоммутативной алгебры кватернионов создает определенные вычислительные сложности, связанные именно с фактом некоммутативности алгебры кватернионов. В то же время, в работе [149] отмечено, что принципиальным свойством, определяющим эффективность применения преобразования (0.2), является не конкретная структура гиперкомплексной алгебры, а только существование в ней достаточного количества изоморфных копий комплексной алгебры, определяющих как структуру системы корней 8j,...,8 , так и структуру алгоритмов быстрого вычисления гиперкомплексных спектров F(\i)- Кроме того, реализация базовых операций в конечномерных алгебрах существенно зависит как от структуры алгебры, причем не только от ее размерности над основным (вещественным) полем, так и от выбора базиса алгебры, который может варьироваться с целью обеспечения минимальной вычислительной сложности аналогов быстрых алгоритмов "канонического" дискретного преобразования Фурье. Тем не менее, подробных исследований на тему выбора гиперкомплексной алгебры и базиса в ней для оптимальной с точки зрения вычислительной сложности реализации преобразований (0.1) и (0.2) к настоящему времени не проводилось.
Эти факторы и определяют в основном задачи диссертационного исследования.
Задачи диссертационной работы. 1. Определение структуры гиперкомплексных алгебр, в которых алгебраические операции реализуются посредством минимального числа вещественных операций.
2. Нахождение тривиально реализуемых автоморфизмов этих алгебр и синтез быстрых алгоритмов преобразований (0.1) и (0.2) "совмещенного" типа.
3. Определение базисов найденных алгебр, в которых представление параметров преобразований (0.1) и (0.2) обеспечивает снижение арифметической сложности алгоритмов вычисления преобразований "неканонических" длин (объемов), отличных от степени двойки.
Перечисленные задачи определяют структуру работы и содержание отдельных глав.
Краткое содержание диссертации. Диссертационная работа, содержащая 126 стр., состоит из введения, трех глав, заключения и списка использованной литературы, составляющего 158 наименований.
В первой главе приводятся необходимые сведения о конечномерных ассоциативных алгебрах и принципы декомпозиции многомерных "классических" комплексных ДПФ. В данной главе не содержится новых результатов, а включенные в нее сведения приводятся лишь для удобства ссылок и замкнутости изложения.
Во второй главе рассматривается четырехмерная ассоциативно-коммутативная гиперкомплексная алгебра (КГА). Строится эффективный способ вычисления операции умножения в данной алгебре (минимизируется количество вещественных умножений). Приводится сравнительный анализ вычислительной сложности умножения в КГА и в некоммутативной алгебре кватернионов, для которой такая сложность определена в работах [61, 62, 80, 102, 113-115]. Этот анализ показывает, что выбор коммутативной структуры в вычислительном плане оптимален по критерию количества вещественных операций, необходимых для реализации базовых алгебраических операций.
Показывается, что в четырехмерной КГА существуют четыре вычислительно тривиально реализуемых автоморфизма, что обеспечивает возможность синтеза "совмещенных" алгоритмов преобразования (0.1) для вещественного входного сигнала.
Рассматривается представление элементов четырехмерной КГА кодами, аналогичными кодам Гамильтона-Эйзенштейна [72, 74, 106]. Показано, что реализация автоморфизмов является тривиальной и приводит к циклическому сдвигу координат элемента. Оценена сложность арифметических операций, выполняемых в кодах. Результаты, полученные для четырехмерной ассоциативно-коммутативной гиперкомплексной алгебры, экстраполируются на многомерные КГА.
В третей главе синтезируются алгоритмы двумерного преобразования (0.1) (гиперкомплексного дискретного преобразования Фурье, ГДПФ) вещественного сигнала "по основанию два", "по основанию четыре" и "с векторным расщеплением", а также алгоритмы двумерного ГДПФ вещественного сигнала "по основанию три", с представлениям данных в у-кодах. Предложена методика экстраполяции разработанных подходов и методов на d-мерный случай (d 2). Производится сравнительный анализ вычислительной сложности синтезированных алгоритмов с их "кватернионными" и/или "клиффордовыми" аналогами.
Методы исследований. В диссертационной работе используются методы теории цифровой обработки сигналов и изображений, методы алгебры и математического анализа, методы синтеза быстрых алгоритмов дискретных преобразований, методы конечно-разностных схем, теории чисел.
Научная новизна работы. Перечисленные ниже результаты, полученные в диссертационной работе, являются новыми.
1. Решена задача определения структуры гиперкомплексной алгебры с минимальной (по критерию количества вещественных операций) сложностью реализации операций сложения и умножения элементов алгебры.
2. Доказана линейная (вместо квадратичной) связь размерности найденной алгебры с мультипликативной сложностью умножения.
3. Определены автоморфизмы КГА, генерирующие разрешимую систему уравнений в алгоритме совмещенного вычисления ГДПФ.
4. Доказан теорема об изоморфизме произвольной КГА, полученной методом Грассмана-Клиффорда, одной из двух конечномерных алгебр (прямой сумме только комплексных или только вещественных алгебр).
5. Предложена методика построения обобщенных у-кодов для представления элементов КГА и исследована арифметическая сложность операций при представлении данных в у-кодах.
6. Синтезированы алгоритмы двумерного ГДПФ вещественного сигнала по основанию два, четыре и с векторным расщеплением, а также алгоритмы двумерного ГДПФ вещественного сигнала по основанию три, с представлениям данных в у-кодах.
7. Предложена методика экстраполяции подходов и методов п. 6 на d - мерный случай ( d 2 ).
Практическая ценность работы. Практическая значимость работы состоит в том, что предложенные быстрые алгоритмы ГДПФ позволяют повысить скорость обработки данных при вычислительных затратах, сравнимых с вычислительными затратами стандартных ДПФ. Это, в свою очередь, открывает возможность использовать полученные алгоритмы для создания высокоэффективных программных и программно-аппаратных средств обработки изображений.
Реализация результатов работы. Все разработанные алгоритмы программно реализованы, произведен сравнительный анализ реального быстродействия.
Апробация работы. Основные результаты диссертации докладывались в 2001 году:
- на 2-ой международной конференции молодых ученых и студентов в Самаре;
- на X Всероссийской конференции "Математические методы распознавания
образов", Москва; в 2002 году:
- на 6-ой международной конференции "Распознавание образов и анализ изображений: Новые информационные технологии", Великий Новгород;
в 2003 году:
- на международном семинаре, посвященного 90-летию со дня рождения С.Н.Черникова, Екатеринбург.
Исследования по теме диссертационной работы выполнялись при поддержке РФФИ (Проекты №№ 00-01-00600, 03-01-00736) и Американского фонда гражданских исследований и развития (проект SA-014-02) в рамках российско-американской программы "Фундаментальные исследования и высшее образование".
Публикации, По теме диссертации опубликовано 8 работ. Работы [12, 13, 90] выполнены автором единолично. Работы [8-11, 89] написаны в соавторстве. В диссертацию включены только результаты, полученные соискателем лично. В тексте диссертации ссылки на работы автора помечены звездочками ( ).
Сложность операций в гиперкомплексных алгебрах
Для вычисления двумерного ДПФ можно использовать алгоритм Кули-Тьюки, применяя его сначала к каждой строке, а потом к каждому столбцу. Эта последовательность обосновывается перегруппировкой слагаемых в (1.23). Данный подход к декомпозиции БПФ называют построчно-столбцевым или каскадным.
Сложность вычисления ДПФ двумерного функции размера (NxN) С помощью каскадного алгоритма равна сложности одномерного ДПФ длины N2. У двумерного (іУхЛ )-ДПФ число "степеней свободы" (различных корней из единицы) равно iV, а не N , как у одномерного. Каскадный алгоритм фактически полностью "игнорирует" двумерную природу обрабатываемого массива и, очевидно, несмотря на простую структуру, не является наилучшим.
К настоящему времени разработано большое количество быстрых алгоритмов многомерных ДПФ, базирующихся на принципиально различных подходах: на факторизации матриц преобразований [5, 26, 68, 85, 86], на полиномиальных преобразованиях [16, 44, 60, 156, 157], на тензорной технике [26,47-54], на преобразовании Радона [30] и т.д. Несмотря на то, что арифметическая сложность таких алгоритмов существенно ниже, чем у простейшего построчно-столбцового алгоритма, сложная структура этих алгоритмов делает их весьма неудобными в реализации и использовании. Поэтому наиболее широкое распространение у пользователей получили различные модификации двумерного БПФ Кули-Тьюки: "по основанию два", "по основанию четыре", БПФ с векторным основанием (многомерное обобщение сплит-радикс БПФ) [84]. Несмотря на то, что арифметическая сложность таких "простых" алгоритмов несколько выше, их простая "однородная" структура является привлекательной для практического использования и аппаратной реализации.
Совмещенные алгоритмы одномерного ДПФ вещественных N - периодических последовательностей вида (1.16) подробно описаны [84, 85, 86]. В их основе лежит возможность получения дополнительных вычислительных преимуществ за счет избыточности представления вещественных чисел в комплексной арифметике. Данная избыточность заключается в том, что действительное число не есть частный случай комплексного числа. Строго говоря, двумерная алгебра С содержит только изоморфную копию одномерной алгебры действительных чисел, а именно алгебру
Игнорирование этого, казалось бы, малозначительного факта вынуждает производить вычисления с действительными числами как с "полноценными" комплексными. В то же время, учет этой "неполноценности" позволяет получить некоторые вычислительные преимущества. Представляя (1.16) в форме г(«) = /(2л) + ;./(2и + 1), можно свести вычисление преобразования (1.13) к вычислению дискретного Фурье-спектра Z(m) комплексной последовательности z(«) периода Jyl и некоторому (относительно небольшому) числу дополнительных вычислений, позволяющих найти по известному спектру Z[m) спектры F m) и F m) последовательностей f(2n) и /(2и + 1), с последующей реконструкцией полного спектра F[m). В самом деле, такая возможность следует из равенств
Выделение из Z(w) частичных спектров F0(m} и F m) обеспечивается наличием в алгебре комплексных чисел С двух автоморфизмов (тождественного и комплексного сопряжения), действующих на Ж тождественно, причем переход к комплексно-сопряженному числу при стандартной машинной реализации не требует дополнительных арифметических действий. В случае двумерного ДПФ, в частности, с реализацией быстрого алгоритма в простейшей построчно-столбцовой форме: применение описанного выше приема затруднительно из-за невещественности внутренних сумм в правой части соотношения (1.24). Кроме того, алгебра С не имеет достаточного числа автоморфизмов, позволяющих осуществить многократное совмещение по каждому из аргументов с возможностью последующего разделения спектров. Естественным обобщением идеи комплексного совмещения является вложение преобразуемого вещественного d мерного массива f(y) (v є Zd) в другие, отличные от алгебры С, алгебры с достаточным числом тривиально реализуемых автоморфизмов [84, 111, 127].
Алгоритм КДПФ с декомпозицией "по основанию два"
Как и в случае четырехмерной алгебры В2, операции в алгебре Вd и ее автоморфизмы как многомерной R-алгебры индуцируют преобразования ассоциированных обобщенных кодов. умножения (hg} можно посредством 3 вещественных умножений и 3(3rf-2 ) вещественных сложений. Доказательство. Заметим, что в обобщенных кодах также имеет место соотношение, аналогичное (2.50): где а,Р,а,Р є Brf. Тогда из (1.30) и замечания 1.1 следует, что умножение (hg) можно реализовать за 3 умножения и за 3 сложения обобщенных кодов размерности 2 . Получаем рекурсивный алгоритм вычисления умножения в обобщенных кодах, аналогичный синтезированному в параграфе 2.6. Суммируя сложность на каждом шаге, получаем, что умножение двух произвольных элементов алгебры В реализуется посредством 3 вещественных умножений и вещественных сложений, что и требовалось доказать. Следствие2.6. Пусть geB , /ієВ , где k d. Тогда умножение элементов g и h реализуется посредством 3 2 " вещественных умножений и 3-2 -(3 -2 ) вещественных сложений. 2.9. Выводы и результаты главы 2 1. Исследована арифметическая сложность операций в КГА; синтезированы алгоритмы с инвариантной сложностью умножения элементов произвольной под алгебры. 2. Доказана линейная (вместо квадратичной) связь размерности алгебры с мультипликативной сложностью умножения. 3. Определены автоморфизмы КГА, генерирующие разрешимую систему уравнений в схеме совмещенных вычислений ГДПФ. 4. Установлен изоморфизм алгебр, полученных методом Грассмана-Клиффорда, одной из двух конечномерных алгебр (прямой сумме только комплексных или только вещественных алгебр). 5. Предложен метод построения обобщенных у -кодов для представления элементов КГА и исследована арифметическая сложность реализации операций в у -представлении. В данной главе рассматривается синтез алгоритмов двумерного ГДПФ вещественного сигнала по "основанию два", "основанию четыре" и с "векторным расщеплением", а также алгоритмы двумерного ГДПФ вещественного сигнала по "основанию три" с представлениям данных в у-кодах. Предложена методика экстраполяции подходов и методов на d- мерный случай (d 2). Произведен анализ вычислительной сложности полученных алгоритмов в сравнении с их некоммутативными прототипами. а через (Р(т1,т2у) обозначен вектор компонент ГДПФ Переход от гиперкомплексного спектра (3.1) к комплексному спектру (3.2) осуществляется без дополнительных вещественных умножений и требует всего две операции вещественного сложения на отсчет. Заметим, что вычисление произведения по формуле (3.1) f(nltn2)w w ,f(nltn2)eR явно избыточно, так как вещественный сигнал /( ,) интерпретируется как элемент ГКА. Избавится от данной избыточности при вычислении F m ntj) можно, воспользовавшись одной из известных схем так называемого совмещенного вычисления спектров: 1) формирование вспомогательной гиперкомплексной функции и вычисление ее спектра с последующей реконструкцией искомого спектра (3.1) (аналог [80, 100]); 2) непосредственное использование соотношений симметрии ГДПФ вещественного сигнала при построении схем декомпозиции алгоритмов ГДПФ (аналог [114, 115]). Далее будут описаны оба способа.
Структура многомерных коммутативно-ассоциативных гиперкомплексных алгебр
Рассматривается представление элементов четырехмерной КГА кодами, аналогичными кодам Гамильтона-Эйзенштейна [72, 74, 106]. Показано, что реализация автоморфизмов является тривиальной и приводит к циклическому сдвигу координат элемента. Оценена сложность арифметических операций, выполняемых в кодах. Результаты, полученные для четырехмерной ассоциативно-коммутативной гиперкомплексной алгебры, экстраполируются на многомерные КГА.
В третей главе синтезируются алгоритмы двумерного преобразования (0.1) (гиперкомплексного дискретного преобразования Фурье, ГДПФ) вещественного сигнала "по основанию два", "по основанию четыре" и "с векторным расщеплением", а также алгоритмы двумерного ГДПФ вещественного сигнала "по основанию три", с представлениям данных в у-кодах. Предложена методика экстраполяции разработанных подходов и методов на d-мерный случай (d 2). Производится сравнительный анализ вычислительной сложности синтезированных алгоритмов с их "кватернионными" и/или "клиффордовыми" аналогами.
Методы исследований. В диссертационной работе используются методы теории цифровой обработки сигналов и изображений, методы алгебры и математического анализа, методы синтеза быстрых алгоритмов дискретных преобразований, методы конечно-разностных схем, теории чисел.
Научная новизна работы. Перечисленные ниже результаты, полученные в диссертационной работе, являются новыми. 1. Решена задача определения структуры гиперкомплексной алгебры с минимальной (по критерию количества вещественных операций) сложностью реализации операций сложения и умножения элементов алгебры. 2. Доказана линейная (вместо квадратичной) связь размерности найденной алгебры с мультипликативной сложностью умножения. 3. Определены автоморфизмы КГА, генерирующие разрешимую систему уравнений в алгоритме совмещенного вычисления ГДПФ. 4. Доказан теорема об изоморфизме произвольной КГА, полученной методом Грассмана-Клиффорда, одной из двух конечномерных алгебр (прямой сумме только комплексных или только вещественных алгебр). 5. Предложена методика построения обобщенных у-кодов для представления элементов КГА и исследована арифметическая сложность операций при представлении данных в у-кодах. 6. Синтезированы алгоритмы двумерного ГДПФ вещественного сигнала по основанию два, четыре и с векторным расщеплением, а также алгоритмы двумерного ГДПФ вещественного сигнала по основанию три, с представлениям данных в у-кодах. 7. Предложена методика экстраполяции подходов и методов п. 6 на d - мерный случай ( d 2 ). Практическая ценность работы. Практическая значимость работы состоит в том, что предложенные быстрые алгоритмы ГДПФ позволяют повысить скорость обработки данных при вычислительных затратах, сравнимых с вычислительными затратами стандартных ДПФ. Это, в свою очередь, открывает возможность использовать полученные алгоритмы для создания высокоэффективных программных и программно-аппаратных средств обработки изображений. Реализация результатов работы. Все разработанные алгоритмы программно реализованы, произведен сравнительный анализ реального быстродействия. Апробация работы. Основные результаты диссертации докладывались в 2001 году: - на 2-ой международной конференции молодых ученых и студентов в Самаре; - на X Всероссийской конференции "Математические методы распознавания образов", Москва; в 2002 году: - на 6-ой международной конференции "Распознавание образов и анализ изображений: Новые информационные технологии", Великий Новгород; в 2003 году: - на международном семинаре, посвященного 90-летию со дня рождения С.Н.Черникова, Екатеринбург. Исследования по теме диссертационной работы выполнялись при поддержке РФФИ (Проекты №№ 00-01-00600, 03-01-00736) и Американского фонда гражданских исследований и развития (проект SA-014-02) в рамках российско-американской программы "Фундаментальные исследования и высшее образование". Публикации, По теме диссертации опубликовано 8 работ. Работы [12, 13, 90] выполнены автором единолично. Работы [8-11, 89] написаны в соавторстве. В диссертацию включены только результаты, полученные соискателем лично. В тексте диссертации ссылки на работы автора помечены звездочками.
Алгоритм двумерного ГДПФ гиперкомплексного сигнала "по основанию четыре"
Значительный вклад в развитие общей теории дискретных преобразований и их быстрых алгоритмов внесли С.С. Агаян, Н.Н. Айзенберг, В.А. Власенко, В.Г. Лабунец, A.M. Крот, A.M. Трахтман, В.М. Чернов, Л.П. Ярославский, Р. Агарвал, Ш. Виноград, Г. Нуссбаумер, Ч. Рейдер и др.
Высокоэффективные алгоритмы конкретных преобразований, адаптированные к характеристикам применяемых вычислительных средств разработаны И.Е. Капориным, Е.Е. Тыртышниковым, A.M. Григоряном и другими исследователями [29,30, 37, 41, 64, 66, 67, 110, 121-123, 150, 153-156].
В настоящее время теория дискретных преобразований развивается, в основном, в следующих направлениях: 1) синтез параметрических семейств новых ортогональных базисов со структурой быстрых алгоритмов, инвариантной по отношению к той или иной принятой авторами концепции синтеза таких алгоритмов (кронекеровская факторизация, полиномиальные преобразования и т.п.) [48,50,51,78,80,87-88]; 2) распространение идей и методов классического дискретного "комплексного" спектрального анализа на функции, определенные на группах и принимающие значения в алгебрах достаточно общего вида [6, 47,49,53,84,99-105, 112]; 3) разработка новых конкретных алгоритмов, обладающих повышенной точностью и быстродействием, адекватных по структуре вычислений последним разработкам в области специализированных процессоров [2,3,4]. Настоящая работа относится к направлениям 2) и 3) развития теории дискретных ортогональных преобразований, перечисленным выше, и их быстрых алгоритмов. Необходимость рассмотрения дискретных ортогональных преобразований со значениями спектров в алгебрах, более общих, чем двумерная алгебра комплексных чисел (гиперкомплексных алгебрах) определяется в основном уже разработанными и перспективными приложениями таких преобразований к решению широкого круга задач информатики. Так, например: 1. Начиная с работ [131, 132, 136, 141, 142] началось активное применение идей псевдоевклидовой геометрии в теории распознавания образов, а также для моделирования и объяснения структурных свойств гипотетического видимого пространства. В работе В.Г.Лабунца [140] высказано мнение, поддерживающее идею Клейна о том, что геометрия -это изучение тех свойств объектов, которые остаются инвариантными под воздействием специфических групп преобразований. Представление данных в гиперкомплексных алгебрах Клиффорда позволило разработать новые методы распознавания инвариантов изображения в евклидовом и неевклидовом двумерном, трехмерном и n-мерном пространстве. Такие инварианты являются характерными именно для геометрических свойств изображений, в то время как классические "комплексные" спектральные методы ориентированы на анализ, в основном, "усредненных", "энергетических" свойств сигнала и малочувствительны к тонким геометрическим свойствам, которые и являются наиболее информативными. 2. В работах [92, 97, 130, 147] изучается возможность построения нейронных сетей в алгебре Клиффорда. В частности, рассматриваются многослойные перцептроны с описанием в терминах алгебры Клиффорда. С помощью полученных многослойных перцептронов строится аппроксимация комплекснозначной функции. 3. В работе [149] рассматривается приложения гиперкомплексного представления сигнала к сегментации текстур. В качестве практического применения демонстрируется использование кватернионной сегментации Габора для обнаружения дефектов на тканевых материалах. Свойством данного алгоритма является его слабая чувствительность к изменению освещенности и низкая вычислительная сложность. 4. В монографии Я.А. Фурмана [70] предложен способ распространения на кватернионные сигналы понятие авто- и взаимно корреляционных функций, согласованной фильтрации и т.д., что позволило с единых позиций рассматривать обработку как контуров, так и групповых точечных объектов, заданных на плоскости или в трехмерном пространстве. Вышеприведенные примеры, относящиеся к различным прикладным задачам цифровой обработки сигналов, при решении которых явным или неявным образом используются гиперкомплексные структуры и дискретный спектральный анализ со значениями спектров в этих структурах, являются достаточной мотивацией для постановки указанной выше цели диссертационного исследования. Заметим, что классическое многомерное дискретное преобразование Фурье является частным случаем преобразования (0.2) при el=... = ed =i. Это позволяет утверждать, что с помощью преобразования (0.2) эффективно решается весь круг задач, цифровой обработки сигналов, для решения которых используется дискретное преобразование Фурье (быстрое вычисление дискретной свертки, фильтрация, компрессия сигналов и т.д.). В задачи диссертационного исследования не входит рассмотрение примеров решения подобных задач с помощью преобразований (0.2). Основной целью работы является разработка эффективной алгоритмической поддержки решения указанных задач с помощью новых преобразований (0.2) со значениями в тех гиперкомплексных алгебрах, для которых быстрые алгоритмы ГПДФ обладают минимальной вычислительной сложностью Преобразование (0.1) для случая алгебры кватернионов [24, 134, 135] введено впервые в работе [84, 104] как вспомогательное преобразование. В работах [137-142, 149] преобразование применялось для решения прикладных задач, перечисленных выше в пп.1-4.
