автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Быстрые алгоритмы гиперкомплексного дискретного преобразования Фурье

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

АЛИЕВ Марат Вячеславович

Быстрые алгоритмы гиперкомплексного дискретного преобразования Фурье

Специальность 05.13.17 - Теоретические основы информатики

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

САМАРА-2004

Рабата выполнена в Самарском государственном аэрокосмическом университете имени академика С.П.Королева и в Институте систем обработки изображений РАН

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

В.М.Чернов

Официальные оппоненты: доктор физико-математических наук,

профессор А.И. Жданов

кандидат физико-математических наук, доцент В.П. Цветов

Ведущее предприятие: Научный совет по комплексной проблеме

"Кибернетика" РАН (г.Москва)

Защита состоится " и MQ.1t 2004 г. в /О часов на заседании диссертационного совета Д 212.215.07 при Самарском государственном аэрокосмическом университете имени академика С.П.Королева по адресу: 443086, Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке университета.

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

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

И.В.Белоконов

г

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Историю быстрых алгоритмов обработки сигналов принято отсчитывать с 1965 г., когда Кули и Тьюки опубликовали свой быстрый алгоритм вычисления дискретного преобразования Фурье (БПФ), хотя ранее Гуд (1960г.) и Томас (1963 г.) опубликовали в практически незамеченных современниками работах свои быстрые алгоритмы дискретного преобразования Фурье, базирующиеся на несколько ином подходе. За время, прошедшее с первых публикаций, дискретный спектральный анализ стал одним из основных средств решения задач цифровой обработки сигналов, распознавания образов, машинного зрения, компьютерной оптики и т.д.

Разработке эффективных (быстрых) алгоритмов вычисления спектров различных дискретных преобразований посвящено большое количество публикаций, как у нас в стране, так и за рубежом. Значительный вклад в развитие общей теории дискретных преобразований и их быстрых алгоритмов внесли С.С. Агаян, Н.Н. Айзенберг, В.А. Власенко, В.Г. Лабунец, А.М. Крот, А.М. Трахтман, В.М.Чернов, Л.П. Ярославский, R.C. Agarval, S. Winograd, H.J. Nussbaumer, C.M. Rader и др. Высокоэффективные алгоритмы конкретных дискретных ортогональных преобразований, адаптированные к характеристикам применяемых вычислительных средств, разработаны И.Е. Капориным, Е.Е. Тыртышниковым, A.M. Григоряном и другими исследователями. В настоящее время теория дискретных преобразований развивается, в основном, в следующих направлениях:

1) синтез параметрических семейств новых ортогональных базисов со структурой быстрых алгоритмов, инвариантной по отношению к той или иной принятой авторами концепции синтеза таких алгоритмов (кронекеровская факторизация, полиномиальные преобразования и т.п.);

2) распространение идей и методов классического дискретного "комплексного" спектрального анализа на функции, определенные на группах и принимающие значения в алгебрах достаточно общего вида;

3) разработка новых конкретных алгоритмов, обладающих повышенной точностью и быстродействием, адекватных по структуре вычислений последним разработкам в области специализированных процессоров.

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

Перечислим некоторые примеры таких приложений.

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

рическим свойствам, которые и

«1ЙЙГ

г гивными.

C-flMtpftrpr ОЭ НХ>у»г

• В работах Г. Джорджио (G.Georgiou, 1992), Д.П. Персона (J.K. Pearson, 1994), П. Арена (P. Arena, 1996), С. Бухгольца (S. Buchholz, 2001) изучается возможность построения нейронных сетей в алгебре Клиффорда. В частности, рассматриваются многослойные перцептроны с описанием в терминах алгебр Клиффорда. С помощью полученных многослойных перцептронов строится аппроксимация комплекснозначной функции.

• В работе Т. Бюлова (Th. Bulow) и Г. Зоммера (G.Sommer, 1997) рассматриваются приложения гиперкомплексного представления сигнала к сегментации текстур. В качестве практического применения демонстрируется использование кватерни-онной сегментации Габора для обнаружения дефектов на тканевых материалах. Свойством данного алгоритма является его слабая чувствительность к изменению освещенности и низкая вычислительная сложность.

• В монографии ЯЛ. Фурмана (2002) предложен способ распространения на ква-тернионные сигналы понятие авто- и взаимно корреляционных функций, согласованной фильтрации и т.д., что позволило с единых позиций рассматривать обработку как контуров, так и групповых точечных объектов, заданных на плоскости или в трехмерном пространстве.

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

Целью диссертации является разработка вычислительно эффективных (быстрых) алгоритмов дискретных ортогональных преобразований со значениями спектра в гиперкомплексных алгебрах.

Основным объектом исследования диссертационной работы является дискретное ортогональное преобразование, имеющее в двумерном случае вид:

где w, = е , w2 = е ^, ъх, е2 ^ = е2 = -l) - образующие элементы некоторой

четырехмерной гиперкомплексной алгебры, а также его многомерные обобщения:

= ^ Z o/(vMftv), (2)

ГДе ц = (т,..........mä= 0,1.....ЛГ-1, = П«»^.О/= « ^./е/,

а - образующие элементы некоторой -мерной гиперком-

плексной алгебры.

Преобразования (1) и (2) будем называть далее гиперкомплексным дискретным преобразованием Фурье (ГДПФ)

Заметим, что классическое многомерное дискретное преобразование Фурье является частным случаем преобразования .(2) при Ej =... = Zj = /еС. Это позволяет утверждать, что с помощью преобразования (2) эффективно решается весь круг задач

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

Преобразование (1) для случая алгебры кватернионов введено впервые в работе В.МЛернова (1993) как вспомогательное преобразование. В последующих работах разных авторов (МА.Чичева (1995), Т.Бюлов (Th.Bulow, 1997), М. Фелсберг (М. Felsberg, 1999), Г. Зоммер (G. Sommer, 1997)) преобразование применялось для решения прикладных задач.

Следует отметить, что использование в указанных выше работах некоммутативной алгебры кватернионов создает определенные вычислительные сложности, связанные именно с фактом некоммутативности этой алгебры. В то же время отмечено (Т. Бюлов и др., 2001), что принципиальным свойством, определяющим эффективность применения преобразования (2), является не конкретная структура гиперкомплексной алгебры, а только существование в ней достаточного количества изоморфных копий комплексной алгебры, определяющих как структуру системы корней так и структуру алгоритмов быстрого вычисления гиперкомплексных спектров .F(n). Кроме того, реализация базовых операций в конечномерных алгебрах существенно зависит как от структуры алгебры, причем не только от ее размерности над основным (вещественным) полем, так и от выбора базиса алгебры, который может варьироваться с целью обеспечения минимальной вычислительной сложности аналогов быстрых алгоритмов "канонического" дискретного преобразования Фурье. Тем не менее, подробных исследований на тему выбора гиперкомплексной алгебры и базиса в ней для оптимальной с точки зрения вычислительной сложности реализации преобразований (1) и (2) к настоящему времени не проводилось.

Эти факторы и определяют задачи диссертационного исследования.

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

2. Нахождение тривиально реализуемых автоморфизмов этих алгебр и синтез быстрых алгоритмов преобразований (1) и (2) "совмещенного" типа.

3. Определение базисов найденных алгебр, в которых представление параметров преобразований (1) и (2) обеспечивает снижение арифметической сложности алгоритмов вычисления преобразований "неканонических" длин (объемов), отличных от степени двойки.

Перечисленные задачи определяют структуру работы и содержание отдельных

глав.

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

Научная новизна работы. Перечисленные ниже результаты, полученные в дис-

сертациошюй работе, являются новыми.

1. Решена задача нахождения гиперкомплексной алгебры (коммутативной гиперкомплексной алгебры, КГА) с минимальной (по критерию количества вещественных операций) сложностью реализации операций сложения и умножения элементов алгебры.

2. Доказана линейная (вместо квадратичной) связь размерности алгебры с мультипликативной сложностью умножения.

3. Определены автоморфизмы КГА, генерирующие разрешимую систему уравнений в алгоритме совмещенного вычисления ГДПФ.

4. Доказан теорема об изоморфизме произвольной КГА, полученной методом Грассмана-Клиффорда, одной из двух конечномерных алгебр (прямой сумме только комплексных или только вещественных алгебр).

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

6. Синтезированы алгоритмы двумерного ГДПФ вещественного сигнала по основанию два, четыре и с векторным расщеплением, а также алгоритмы двумерного ГДПФ вещественного сигнала по основанию три, с представлениям данных в у* кодах.

7. Предложен метод экстраполяции подходов и методов п. 6 на d -мерный случай

Практическая значимость работы. Практическая значимость работы состоит в том, что предложенные быстрые алгоритмы ГДПФ позволяют повысить скорость обработки данных при вычислительных затратах, сравнимых или меньших с вычислительными затратами стандартных ДПФ. Это, в свою очередь, открывает возможность использовать полученные алгоритмы для создания высокоэффективных программных и программно-аппаратных средств обработки изображений.

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

Апробация работы. Основные результаты диссертации докладывались на 2-ой международной конференции молодых ученых и студентов (Самара; 2001г.); на X Всероссийской конференции "Математические методы распознавания образов" (Мо-сква,2001г), на 6-ой международной конференции "Распознавание образов и анализ изображений: Новые информационные технологии", (Великий Новгород,2002 г.), на международном семинаре, посвященного 90-летию со дня рождения С.Л.Черникоза, (Екатеринбург, 2003)

Исследования по теме диссертационной работы выполнялись при поддержке РФФИ (Проекты №№ 00-01-00600,03-01-00736) и Американского фонда гражданских исследований и развития (проект SA-014-02) в рамках российско-американской программы "Фундаментальные исследования и высшее образование".

Публикации. По теме диссертации опубликовано 8 работ. Работы [4, 6, 8] выполнены автором единолично. Работы [1-3, 5,7] написаны в соавторстве. В диссертацию включены только результаты, полученные соискателем лично.

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

На защиту выносятся:

1. Решение задачи определения гиперкомплексной алгебры с минимальной (по критерию количества вещественных операций) сложностью реализации операций сложения и умножения элементов алгебры.

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

3. Доказательство возможности синтеза совмещенных быстрых алгоритмов ГПДФ, как следствие существования достаточного числа явно описанных автоморфизмов КГА.

4. Классификационная теорема для КГА, полученных методом Грассмана-Клиффорда.

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

6. Методы синтеза алгоритмов ¿-мерных ГДПФ вещественного сигнала "по основанию два", "по основанию четыре" и "с векторным расщеплением", а также алгоритмы ГДПФ вещественного сигнала "по основанию 3" с представлениям данных в у-кодах.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

1.1. В диссертационной работе рассматриваются только конечномерные ассоциативные алгебры W над полем действительных чисел, то есть D -мерные векторные пространства над полем R с базисом £q,...,и операцией умножения элементов

Л = (ло.....TlD-i). g = KgeV/ по правилу:

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

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

пространства вида

причем хотя бы одно из чисел р/ равно (-1), то есть алгебра В содержит хотя бы одну подалгебру, изоморфную С.

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

ной арифметике. Данная избыточность заключается в том, что действительное число не есть частный случай комплексного числа, а является элементом "изоморфной копии" одномерной алгебры действительных чисел, а именно алгебры С0 ={а + (Ы; а е К}. Игнорирование этого факта вынуждает производить вычисления с действительными числами как с "полноценными" комплексными. В то же время, учет этой "неполноценности" позволяет получить некоторые вычислительные преимущества. Естественным обобщением идеи комплексного совмещения является вложение преобразуемого вещественного ё- мерного массива в другие, отличные от алгебры С, алгебры с достаточным числом тривиально реализуемых автоморфизмов. В диссертационной работе описывается общая методика синтеза таких алгоритмов в случае произвольной алгебры.

Во второй главе рассматривается четырехмерная коммутативная гиперкомплексная алгебра (КГА). Строится эффективный алгоритм умножения в данной алгебре (минимизируется количество вещественных умножений). Приводится сравнительный анализ вычислительной сложности умножения, полученной в данной работе, в КГА и в её антикоммутативном аналоге алгебре кватернионов, полученных ранее в работах М. В. Першиной, М. А. Чичевой (1995), который показывает, что выбор коммутативной структуры в вычислительном плане оптимален по критерию количества вещественных операций, необходимых для реализации базовых алгебраических операций.

Показывается, что в КГА существует по крайне мере четыре тривиально реализуемых автоморфизма, что обеспечивает возможность синтеза "совмещенных" алгоритмов преобразования (0.1) для вещественного входного сигнала.

Рассматривается представление элементов четырехмерной КГА кодами, аналогичными кодам Гамильтона-Эйзенштейна (В.М.Чернов, 1994). Показано, что реализация автоморфизмов является тривиальной и приводит к циклическому сдвигу координат элемента. Оценена сложность арифметических операций, выполняемых в кодах. Результаты, полученные для четырехмерной коммутативной гиперкомплексной алгебре экстраполируются на многомерные КГА. Сформулируем наиболее важные результаты главы.

2.1. Рассматривается четырехмерной алгебры

В2 = {А = Л, + Г)2е1 + ^г +Т14е1е2; Л]. Л2.Лз.т14 6 к}

с определяющими соотношениями Б^ = е^ — — 1, £¡63 = £2Е1> (Е1Е2)2 = ^ для умножений базисных элементов получаемую на втором шаге процедуры удвоения Грассмана-Клиффорда, которая изоморфна прямой сумме двух алгебр комплексных чисел В2 = С + С. Для нее определены четыре автоморфизма, генерирующие разрешимую систему уравнений для реконструкции спектра в алгоритме совмещенного вычисления двумерного ГПДФ вещественного сигнала. Найденные автоморфизмы являются оптимальными в вычислительном отношении, так как не требуют для реализации нетривиальных вычислительных операций.

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

Лемма 2.4. Пусть /г ="Г|о +т11е1 "*"т12е2 +т1зе1Е2 и^=^0 + ^1е1 + ^2Е2+?ЭЕ1Е2» Т0ГДа умножение произвольных элементов алгебры В2 может быть реализовано с помощью шести вещественных умножений и четырнадцати сложений.

Следствие 2.1. Умножение элемента алгебры В2 на комплексное число требует шести вещественных умножений и шести сложений.

В таблице 2.1 приведено сравнение арифметической сложности умножения элементов алгебры В2 (последняя строка таблицы) и арифметической сложности умножения элементов алгебры кватернионов Н, полученной в работе М.Л. Чичсвой (1995).

Таблица 2.1.

Первый Сомножитель Н Второй сомножитель С Необходимое число умножений Необходимое число сложений Суммарная сложность умножения

6 6 12

в, С 6 б 12

н н 9 15 24

н н 8 28 36

' " Зв * ■ 6 ' 14

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

2.3. Как показано в ряде работ (В.М. Чернов (1994) и др.) для синтеза быстрых

алгоритмов дискретного преобразования Фурье длины ЛТ = 3Р, />е№ предпочтительней использовать представление комплексных чисел и кватернионов в так называемых циклотомических кодах ( - кодах). В диссертации доказана возможность аналогичного представления и для элементов алгебры В 2.

Лемма 2.5. Для любого существуют единственные элементы

1о.Л1.Л2.Лз такие, что справедливо представление (представление в у-кодах):

л = (ло71 +01271 +ЛзЮ?2>

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

2.4. Вышеописанные результаты для алгебры В2 экстраполируются на случай высших размерностей.

Определение 2.3. Коммутативной гиперкомплексной алгеброй В^ будем называть -мерную Я -алгебру £ базисом:

л=Ще?', «<=0,1; /={1,..,^ , (4)

где б® =1, е{ = е,- , и следующим законом умножения базисных элементов простран-Лемма 2.9. Пусть ® - поразрядное сложение по модулю 2:

где Г = (а!.....аа), т = (а',,...,а^); Г,теГ; а;,а}=0,1; /б/. Пусть функция

равенством

определена равенством /^(/,T) = aiaJ, /е/, а функция Ч'.ТхТ—>{—1,1} равенством = Р/= {—1,1}. Тогда правила умноже-

<е/

ния базисных элементов Л можно записать в следующем виде:

EtEr=4>(t,ï)Ei(Bz, Vt.xeT.

(5)

Следствие 2.2. Если существует teТ такое, что Et =—1, тогда в алгебре В^

содержится ровно элементов, квадрат которых равен (-1).

Классификация алгебр Bj описывается доказанной в диссертации теоремой.

Теорема 2.1. Для любого </£1 существует только две неизоморфных 2^ мерных алгебры с операциями, определенными соотношением (5) и базисом Л, определенного в соотношении (4):

Bj S.R + R4-... + R., В^=С + С + ... + С,

где знак 4- означает прямую сумму алгебр.

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

Теорема 12. Пусть y.TxT-ï {-1,1} : Ч/(У>0 = . Тогда множество из 2d

I е/

отображений: OjiBj таких, что оДх)=ХсЛС(Л0^/» где Х=(с0.....c2d-l)£®<i'

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

Теорема 2.3. Умножение двух произвольных элементов в алгебре В^ можно

,¿-1

вещественных умножений и

{Ad-l)-2'

d-1

вещест-

реализовать посредством 3*2' венных сложений.

Следствие 2.4. Пусть АеВ^,ГДе к<с1, тогда умножение элементов g

,¿-1 ________________________________.. !л и

и h реализуется посредством 3-2 ~ вещественных умножений и (4-к —1)-2 " вещественных сложений.

Следствие 2.5. Пусть £еВ]£, ЛеВ^, где к <«/,,. Тогда умножение элементов g

и h реализуется посредством 2d вещественных умножений и к-1? вещественных сложений.

2.6. В работе рассмотрена также экстраполяция результатов п.2.3. на многомерный случай.

В третей главе синтезируются алгоритмы двумерного преобразования (1) (гиперкомплексного дискретного преобразования Фурье, ГДПФ) вещественного сигнала "по основанию два", "по основанию четыре" и "с векторным расщеплением", а также алгоритмы двумерного ГДПФ вещественного сигнала "по основанию три", с представлениям данных в -кодах. Предложен метод экстраполяции разработанных под-

и

ходов и методов на d-мерный случай ^ >2). Производится сравнительный анализ вычислительной сложности синтезированных алгоритмов с их "кватернионными" и/или "клиффордовыми" аналогами.

Заметим, что вычисление произведений /("^Яг)'»^'^!^''2 при /(и^Г^еК В формуле (1) явно избыточно, так как вещественный сигнал /(^»Лг) интерпретируется как "общий" элемент ГКА. Избавиться от данной избыточности при вычислении можно, воспользовавшись алгоритмом совмещения, который возможно реализовать двумя способами:

1) формирование вспомогательной гиперкомплексной функции и вычисление ее спектра с последующей реконструкцией искомого спектра (1);

2) непосредственное использование соотношений симметрии ГДПФ вещественного

сигнала при построении схем декомпозиции алгоритмов ГДПФ.

В диссертации анализируются оба способа и синтезируются аналоги двумерных ДПФ "по основанию два", "по основанию четыре" и "с векторным расщеплением". В диссертации получены аналитические оценки сложности синтезированных алгоритмов. Так как далее эти оценки представлены в общем виде для алгебр произвольной размерности, то ниже, в таблицах 3.1. и 3.2, приводятся только некоторые численные результаты, следующие из этих оценок для двумерного ГПДФ.

Таблица 3.1.

Вычислительная сложность быстрых алгоритмов (БА) двумерного ГПДФ при N = 2'

к БА "по основанию два" БА "по основанию четыре" БА "с векторным расщеплением"

умножений сложений умножений сложений умножений сложений

8 32 384 32 384 72 440

16 416 2464 308 2324 416 2528

32 2816 13568 1952 12448 2432 12288

64 15872 69120 10688 62400 12032 60544

128 81920 335872 54272 300032 59648 279680

Таблица 3.2.

Относительная вычислительная сложность (БА) двумерного ГПДФ при N = 2*

к БА "по основанию 2" БА "по основанию 4" БА "с векторным расщеплением"

умножений сложений умножений сложений умножений сложений

8 0,5 6 0,5 6 1,125 6,875

16 1,625 9,625 1 ДОЗ 125 9,078125 1,625 9,875

32 2,75 13,25 1,90625 12,15625 2,375 12

64 3,875 16,875 2,609375 15,23438 2,9375 14,78125

128 5 20,5 3,3125 18,3125 3,640625 17,07031

На рис.3.4 -3.6 эти результаты представлены диаграммами.

Рис. 3.6. Относительная общая сложность двумерного ГДПФ. (На диаграммах FQFT - сложность кватернионного ДПФ работы G. Sommer и T.Bulow(2001)).

Аналогичные результаты получены и для алгоритмов двумерного ГДПФ вещественного сигнала с декомпозицией "по основанию 3". Несмотря на то, что наиболее важным для приложений в области цифровой обработки сигналов является случай двумерного ГДПФ, в диссертации исследуются и анализируются также многомерные обобщения Г П Д Ф.

Введем обозначения для характеристик сложности алгоритмов:

м:

d.h

- мультипликативная сложность многомерного ГДПФ для гиперком-плсксной функции,

- аддитивная сложность алгоритма многомерного ГДПФ гиперком-плсксной функции,

• С/'^ЛГ''! - общая сложность алгоритма многомерного ГДПФ гиперкомплексной функции.

Нижний индекс ,5 означает по какому основанию производится декомпозиция^ обозначает декомпозицию по смешанному).

Алгоритм многомерного ГДПФ гиперкомплексного сигнала с декомпозицией "по основанию 2":

M('h (лГ*) S ~ (2rf -1)/^ log2 N + o(Nd ),

d.2d+l-2dA +

-0,5^-Nd logj N+o{Nd^,

(лг</) < [а • 2м -2*- 1о§2 N+о^у

Алгоритм многомерного ГДПФ гиперкомплексного сигнала с декомпозицией "по основанию 4":

Алгоритм многомерного ГДПФ гиперкомплексного сигнала "с векторным расщеплением":

(tf= Iog3 N + ¿»(лг*),

Алгоритм мт_ ' 3_v '_анию 3 :

4d+1-10 .d

Gd(Nd) = ?—p?-Ndlog3N + o(Nd).

Пусть характеристики

Mds'h(Nd)/ ^"И/ _G?>h(Nd)/

обозначают отношение вычислительных сложностей разработанных алгоритмов и соответствующих сложностей наилучшего из известных алгоритмов для некоммутативных алгебр Клиффорда - мультипликативная, аддитивная и общая сложность алгоритма работы G. Sommer, M. Felsberg (1999, 2001), соответственно.

Таблица 3.3

Сравнительные вычислительные характеристики двумерных ГПДФ

И а Р

5 = 2 (п. 3.1.1.1.) £ = 0,5625 29 — = 1,8125 16 19 — = 1,1875 16

5 = 4 (п. 3.1.1.2.) — = 0,3515625 128 209 —=1,6328125 128 127 — = 0,9921875 128

S = V (п. 3.1.1.3.) — = 0,3214285... 28 4 = 1,25 4 — = 0,78571... 14

Таблица 3.4

Сравнительные вычислительные характеристики d -мерных ГДПФ

И а 0

5 = 2 (н. 3.3.1.) 3 »- 2-d «| = 2,67 «0,8

5 = 4 (п. 3.3.2.) 3 «- 2-d «|=2,33 »0,7

J = V (п. 3.3.3.) 3 »- 4 d и —= 0,25 4 «0,25

ЗАКЛЮЧЕНИЕ

Перечислим наиболее важные выводы, следующие из диссертационного исследования.

1. Использование коммутативных гиперкомплексных алгебр как области значений спектра дискретных ортогональных преобразований позволяет существенно снизить сложность быстрых алгоритмов ГПДФ по сравнению с их "некоммутативными" прототипами (кватернионное ГПДФ, клиффордово ГПДФ).

2. В отличие от "некоммутативных11 прототипов, быстрые алгоритмы ГПДФ со значениями в КГА имеют невозрастающую мультипликативную сложность как функцию размерности.

3. Для ГПДФ возможен синтез эффективных алгоритмов "нетрадиционных11 линейных размеров, отличных от степени двойки, за счет выбора базисных элементов алгебры, согласованного со структурой быстрых алгоритмов.

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

лительную сложность алгоритмов примерно на 30% при снижении мультипликативной сложности примерно в три раза.

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

1. Алиев М.В., Чичева МЛ. Дискретные ортогональные преобразования с биэкспо-ненциальным базисом //Тезисы докладов 2-ой международной конференции молодых ученых и студентов, Часть1, Самара, 2001, с.18.

2. Алиев МБ., Чернов В.М., Чичева МЛ. Дискретные ортогональные преобразования с мультиэкспоненциальным базисом //Тезисы докладов X Всероссийской конференции "Математические методы распознавания образов", Москва, 2001, с. 5-6.

3. Алиев М.В., Чичева МЛ. Алгоритмы двумерного ДПФ с представлением данных в алгебре гиперкомплексных чисел / в кн. Алгебра и линейная оптимизация: Труды международного семинара, посвященного 90-летию со дня рождения СНЛерникова. Екатеринбург: УрО РАН, 2002. с. 18-26.

4. Алиев М.В. Синтез алгоритмов двумерного ДПФ в гиперкомплексной алгебре // Труды 6-ой международной конференции "Распознавание образов и анализ изображений: Новые информационные технологии", Великий Новгород, 2002, с.11-15.

5. Aliev M.V., Chernov V.M. Two-dimensional FFT-like algorithms with overlapping //Optical Memory and Neural Networks (Information Optics), v.l 1, no.l, 2002 p.29-38.

6. Алиев М.В. Быстрые алгоритмы многомерного ДПФ вещественного сигнала с представлением данных в коммутативно-ассоциативных алгебрах //Компьютерная оптика, № 24, 2002. - с. 130-136.

7. Алиев М.В., Чичева МЛ. О параллельных алгоритмах вычисления гиперкомплексного дискретного преобразования Фурье. //Информационный бюллетень Ассоциации математического программирования №10, Екатеринбург, УрО РАН. Тезисы докладов 12-ой Всероссийской конференции "Математическое программирование и приложения", 2003, с.24-25.

8. Aliev М. V. Synthesis ofTwo-Dimensional DFT Algorithms in the Hypercomplex Algebra //Pattern Recognition and Image Analysis, Vol. 13, No. 1,2003 p. 61-63.

№ -573 5

Подписано в печать 19.03.2004 Формат 60x84 1/16 Объем 1,0 усл. печ. л. Тираж 100 экз.

Отпечатано с готовых оригинал-макетов

Перечень сокращений и основных обозначений.

ВВЕДЕНИЕ.

ГЛАВА 1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ ИЗ АЛГЕБРЫ И ТЕОРИИ БЫСТРЫХ АЛГОРИТМОВ ДИСКРЕТНЫХ ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ.

1.1. Конечномерные алгебры.

1.1.1. Матричное представление операций.

1.1.2. Процедура удвоения Грассмана-Клиффорда.

1.1.3. Сложность операций в гиперкомплексных алгебрах.

1.1.4. Представление комплексных чисел в у -кодах.

1.2. Быстрые алгоритмы дискретного преобразования Фурье.

1.2.1. Декомпозиция Кули-Тьюки.

1.2.1.1 Декомпозиция Кули-Тьюки "по основанию два".

1 Г.! ? „'т • ••!'?т .•*. ванию четыре".

1.2.3.3. Декомпозиция Кули-Тьюки "с расщеплением основания" (сплит-радикс алгоритм).

1.2.2. Декомпозиция многомерных ДПФ.

1.2.3. Совмещенные алгоритмы ДПФ.

1.3. Гиперкомплексные ДПФ вещественного сигнала.

1.3.1. Кватернионное ДПФ вещественного сигнала.

1.3.1.1. Алгоритм КДПФ с декомпозицией "по основанию два".

1.3.1.2. Алгоритм КДПФ с декомпозицией "по основанию четыре".

1.3.1.3. Алгоритм КДПФ "с расщеплением основания".

ГЛАВА 2. ИССЛЕДОВАНИЕ СТРУКТУРЫ ИСПОЛЬЗУЕМЫХ

КОНЕЧНОМЕРНЫХ АЛГЕБР.

2.1. Четырехмерная коммутативно-ассоциативная гиперкомплексная алгебра.

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

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

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

2.5. Структура многомерных коммутативно-ассоциативных гиперкомплексных алгебр.

2.6. Арифметическая сложность операций в многомерной коммутативно-ассоциативной гиперкомплексной алгебре.

2.7. Представления в обобщенных у - кодах.

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

2.9. Выводы и результаты главы 2.

3. БЫСТРЫЕ АЛГОРИТМЫ ГИПЕРКОМПЛЕКСНОГО ДПФ.

3.1. Алгоритмы двумерного гиперкомплексного ДПФ.

3.1.1. Совмещенный алгоритм двумерного ГДПФ вещественного сигнала.

3.1.1.1. Алгоритм двумерного ГДПФ гиперкомплексного сигнала по основанию два".

3.1.1.2. Алгоритм двумерного ГДПФ гиперкомплексного сигнала по основанию четыре".

3.1.1.3. Алгоритм двумерного ГДПФ гиперкомплексного сигнала с векторным расщеплением".

3.1.2. Использование принципа симметрий гиперкомплексной алгебры при синтезе ГДПФ.

3.1.2.1. Алгоритм двумерного ГДПФ вещественного сигнала "по основанию два".

3.1.2.2. Алгоритм двумерного ГДПФ вещественного сигнала "по основанию четыре".

3.1.3. Сравнительный анализ вычислительной сложности алгоритмов двумерного ГДПФ.

3.2. Алгоритм двумерного ГДПФ вещественного сигнала с декомпозицией "по основанию три".

3.3. Алгоритмы многомерного ГДПФ в алгебре Е»^.

3.3.1. Совмещенные алгоритмы многомерного ГДПФ вещественного сигнала.

3.3.1. Алгоритм многомерного ГДПФ гиперкомплексного сигнал с декомпозицией "по основанию два".

3.3.2. Алгоритм многомерного ГДПФ гиперкомплексного сигнал с декомпозицией "по основанию четыре".

3.3.3. Алгоритм многомерного ГДПФ гиперкомплексного сигнала "с векторным расщеплением".

3.4. Алгоритм многомерного ГДПФ вещественного сигнала "по основанию три".

3.5. Сравнительный анализ вычислительной сложности алгоритмов.

3.6 Результаты и выводы главы 3.

Целью работы является разработка вычислительно эффективных (быстрых) алгоритмов дискретных ортогональных преобразований со значениями спектра в гиперкомплексных алгебрах.

Актуальность темы. Историю быстрых алгоритмов обработки сигналов принято отсчитывать с 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, 110, 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{Щ,т2)= £ ]Г /("1 ,n2)w^,0<mbm2<N-l, (0.1) и1=0п2=0

27IEj 2ле2/ где w}=e /N, w2=e , cl582 ~ образующие элементы некоторой четырехмерной гиперкомплексной алгебры, а также его многомерные обобщения:

00= Z /(v)^(n,v) (0.2) nx,.,nd= 0

2nZj / где ц = (тx,.,md), v = (wl,.,wd), = ' / = {1,.,йГ}, е/

8образующие элементы некоторой 2d-мерной гиперкомплексной алгебры.

Заметим, что классическое многомерное дискретное преобразование Фурье является частным случаем преобразования (0.2) при е{ =. = zd = i. Это позволяет утверждать, что с помощью преобразования (0.2) эффективно решается весь круг задач, цифровой обработки сигналов, для решения которых используется дискретное преобразование Фурье (быстрое вычисление дискретной свертки, фильтрация, компрессия сигналов и т.д.). В задачи диссертационного исследования не входит рассмотрение примеров решения подобных задач с помощью преобразований (0.2). Основной целью работы является разработка эффективной алгоритмической поддержки решения указанных задач с помощью новых преобразований (0.2) со значениями в тех гиперкомплексных алгебрах, для которых быстрые алгоритмы ГПДФ обладают минимальной вычислительной сложностью

Преобразование (0.1) для случая алгебры кватернионов [24, 134, 135] введено впервые в работе [84, 104] как вспомогательное преобразование. В работах [137-142, 149] преобразование применялось для решения прикладных задач, перечисленных выше в пп.1-4.

Следует отметить, что использование в цитированных работах некоммутативной алгебры кватернионов создает определенные вычислительные сложности, связанные именно с фактом некоммутативности алгебры кватернионов. В то же время, в работе [149] отмечено, что принципиальным свойством, определяющим эффективность применения преобразования (0.2), является не конкретная структура гиперкомплексной алгебры, а только существование в ней достаточного количества изоморфных копий комплексной алгебры, определяющих как структуру системы корней так и структуру алгоритмов быстрого вычисления гиперкомплексных спектров F(^i). Кроме того, реализация базовых операций в конечномерных алгебрах существенно зависит как от структуры алгебры, причем не только от ее размерности над основным (вещественным) полем, так и от выбора базиса алгебры, который может варьироваться с целью обеспечения минимальной вычислительной сложности аналогов быстрых алгоритмов "канонического" дискретного преобразования Фурье. Тем не менее, подробных исследований на тему выбора гиперкомплексной алгебры и базиса в ней для оптимальной с точки зрения вычислительной сложности реализации преобразований (0.1) и (0.2) к настоящему времени не проводилось.

Эти факторы и определяют в основном задачи диссертационного исследования.

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

2. Нахождение тривиально реализуемых автоморфизмов этих алгебр и синтез быстрых алгоритмов преобразований (0.1) и (0.2) "совмещенного" типа.

3. Определение базисов найденных алгебр, в которых представление параметров преобразований (0.1) и (0.2) обеспечивает снижение арифметической сложности алгоритмов вычисления преобразований "неканонических" длин (объемов), отличных от степени двойки.

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

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

ЗАКЛЮЧЕНИЕ

Перечислим наиболее важные на наш взгляд выводы, следующие из диссертационного исследования.

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

2. Использование коммутативных алгебр как области значений спектра этих преобразований позволяет существенно снизить сложность быстрых алгоритмов ГПДФ по сравнению с их "некоммутативными" прототипами (кватернионное ГПДФ, клиффордово ГПДФ).

3. В отличие от "некоммутативных" прототипов, быстрые алгоритмы ГПДФ со значениями в КГА имеют невозрастающую мультипликативную сложность как функцию размерности.

4. Для ГПДФ возможен синтез эффективных алгоритмов "нетрадиционных" линейных размеров, отличных от степени двойки, за счет выбора базисных элементов алгебры, согласованного со структурой быстрых алгоритмов.

5. В практически важном для обработки изображений случае двумерного ГПДФ использование КГА вместо алгебры кватернионов позволяет снизить общую вычислительную сложность алгоритмов примерно на 30% при снижении мультипликативной сложности примерно в три раза.

1. Автоморфизмы классических групп. Сб. переводов с англ. и франц.-М.: Мир, 1976.-264 с.

2. Агаян С. С. Оптимальные алгоритмы быстрых ортогональных преобразований и их реализация на ЭВМ //Кибернетика и вычислительная техника.- М.: Наука, 1986.- вып. 2.- с. 231-301.

3. Агаян С.С., Геворкян Д.З. Сложность и параллельные алгоритмы дискретных ортогональных преобразований //Кибернетика и выч. техника. М: Наука, 1988. - Вып 4. - с.124-169.

4. Агаян С.С., Баядан Г.Л., Геворкян Д.З. Вопросы устойчивости суммирования ортогональных рядов и вычисления линейных преобразований //Кибернетика и выч. техника. М: Наука, 1990. - Вып 5. -с.132-168.

5. Айзенберг Н.Н.,Семирот М.С. Цифровая обработка сигналов на конечных группах //Применение ортогональных методов при обработке сигналов и анализе систем.- Свердловск, 1980. Вып. 1. - с.96-105.

6. Алгебра и теория чисел (с приложениями). Избранные доклады семинара Н.Бурбаки. Сб. статей. Перев. с франц. и англ.-М.: Мир, 1987.-271 с.

7. Алиев М.В., Чичева М.А. Дискретные ортогональные преобразования с биэкспоненциальным базисом //Тезисы докладов 2-ой международной конференции молодых ученых и студентов, Часть1, Самара, 2001, с. 18.

8. Алиев М.В., Чернов В.М., Чичева М.А. Дискретные ортогональные преобразования с мультиэкспоненциальным базисом //Тезисы докладов X Всероссийской конференции "Математические методы распознавания образов", Москва, 2001, с. 5-6.

9. Алиев М.В. Синтез алгоритмов двумерного ДПФ в гиперкомплексной алгебре // Труды 6-ой международной конференции "Распознавание образов и анализ изображений: Новые информационные технологии", Великий Новгород, 2002, с. 11-15.

10. Алиев М.В. Быстрые алгоритмы многомерного ДПФ вещественного сигнала спредставлением данных в коммутативно-ассоциативных алгебрах //Компьютерная оптика, № 24, 2002. с. 130-136.

11. Арнольд И.В. Теория чисел: Пособие для ин-тов М.: Учпедгиз Наркомпроса РСФСР, 1939.-286с.

12. Атья М., Макдональд И. Введение в коммутативную алгебру. Перев. с англ.-М.: Факториал Пресс, 2003.-144 с.

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

14. Березин Ф.А. Введение в алгебру и анализ с антикоммутирующими переменными. М., Издательство МГУ, 1983.

15. Блейхат Р. Э. Алгебраические поля, обработка сигналов, контроль ошибок //ТИИЭР, 1985. т.73. - №5. - с.30-53.

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

17. Брейсуэлл Р. Преобразование Хартли. М.: Мир, 1990. - 175с.

18. Бурлаков М.П. Клиффордовы структуры на многообразиях // Итоги науки и техники. Современная математика и ее приложения. М.: ВИНИТИ, 1995. Т. 30: Геометрия 3, с. 205-257.

19. Бухбиндер И.Л. Знакомство с суперматематикой //Соросовский Образовательный Журнал. 1998, № 8, с. 115-120.

20. Бухштаб А.А. Теория чисел -2-е, испр. изд. М.: Просвещение, 1966.-384с.

21. Ван дер Варден Б.Л. Алгебра. М.: Наука, 1976. 648с.

22. Вариченко JI. В., Лабунец В. Г., Раков М. А. Абстрактные алгебраические системы и цифровая обработка сигналов. Киев: Наукова думка, 1986.247c.

23. Власенко В. A., JIanna Ю. М., Ярославский Л. П. Методы синтеза быстрых алгоритмов свертки и спектрального анализа сигналов. М.: Наука, 1990. - 180с.

24. Гельфанд И.М. Лекции по линейной алгебре 5-е, испр. изд. - М.: Добросвет, 1998.-319с.

25. Гельфонд А.О. Исчисление конечных разностей. М: Наука, 1967. - 375с.

26. Гречишников А. И. Модифицированные алгоритмы БПФ с уменьшенным числом операций умножения //Радиотехника и электроника, 1983. т.28. -№1. - с.195-197.

27. Григорян A.M. Алгоритм вычисления двумерного дискретного преобразования Фурье с произвольными порядками //Журнал выч. матем. иматем. физ., 1991. т.31. - №10. - с.1576-1581.

28. Гроссман И., Магнус В. Группы и их графы. М.: Мир, 1971.

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

30. Дэвенпорт Высшая арифметика. М., Наука, 1965. 176 с.

31. Задирака В.К. Теория вычисления преобразования Фурье. Киев: Наукова думка, 1983.

32. Залманзон Л. А. Преобразования Фурье, Уолша, Хаара и их применения в управлении, связи и других областях. М.: Наука, 1989. - 494с.

33. Зарисский О., Самюэль П. Коммутативная алгебра, т.1. Перев. с англ. М.: ИЛ, 1963.-373 с.

34. Иваненко В.Г. Рекуррентное вычисление дискретного преобразования Фурье. М.: МИФИ, 1987. Препр.014-87. - 16с.

35. Ивлев Д.Д. О двойных числах и их функциях // Математическое просвещение. М.: Изд-во физ.-мат. лит., 1961. Вып. 6, с. 197-203.

36. Ильин В.А., Позняк Э.Г. Линейная алгебра: Учеб. Для ВУЗов 4-ое изд. -М: Физматлит, 1999 - 296 с.

37. Кантор И.Л., Солодовников А.С. Гиперкомплексные числа. М.: Наука, 1973. 144 с.

38. Кецарис А. А. Основания математической физики. М.: Ассоциация независимых издателей, 1997.-280 с.

39. Капорин И. Е. Новый алгоритм быстрого преобразования Фурье.

40. Журнал вычислительной математики и математической физики, т. 20, № 4, 1980.-с. 1054-1058.

41. Кострикин А. И. Введение в алгебру. Основы алгебры. М.: Наука, 1994. -318 с.

42. Крот A.M., Минервина Е.Б. Синтез алгоритмов дискретного преобразования Фурье для действительных последовательностей на основе полиномиальной алгебры //РЭ, 1987. -т.22. №6. - с.1217-1229.

43. Крот A.M. Дискретные модели динамических систем на основе полиномиальной алгебры. Минск: Навука i тэхшка, 1990. - 311 с.

44. Кухарев Г. А., Шмерко В. П., Зайцева Е. Н. Алгоритмы и систолические процессоры для обработки многозначных данных. Минск: Навука i тэхшка, 1990. - 296 с.

45. Лабунец В.Г. Обобщенные и быстрые преобразования Фурье на произвольной конечной абелевой группе //Гармонический анализ на группах в абстрактной теории систем. Свердловск, 1976. - с.24-43.

46. Лабунец В. Г. Единый подход к алгоритмам быстрых преобразований //Применение ортогональных методов при обработке сигналов и анализе систем. Свердловск: УПИ, 1980. - с.4-14.

47. Лабунец В. Г. Теоретико-числовые преобразования над полями алгебраических чисел //Применение ортогональных методов при обработке сигналов и анализе систем. Свердловск: УПИ, 1981. - с.44-54.

48. Лабунец В. Г. Фурье-подобные преобразования //Применение ортогональных методов при обработке сигналов и анализе систем. -Свердловск: УПИ, 1981. с.4-14.

49. Лабунец В.Г. Колмогоров Г.С. Стратегии настройки многопараметрических преобразований //Применение ортогональных методов при обработке сигналов и анализе систем. Свердловск: УПИ, 1983. - с.4-26.

50. Лабунец В. Г. Алгебраическая теория сигналов и систем: Цифровая обработка сигналов. Красноярск: Изд-во Красноярск, ун - та, 1984. - 244 с.

51. Лабунец В. Г. Функции с двойной ортогональностью в обобщенном гармоническом анализе //Цифровые методы в управлении, радиолокации и связи. Свердловск: УПИ, 1986. - с.4-15.

52. Лабунец В. Г. Алгебраическая теория сигналов и систем. Свердловск: Изд-во УрГУ, 1989. - 196с.

53. Ланкастер П. Теория матриц. М.: Наука, 1978. 280 с.

54. Ленг С. Алгебра. М.: Мир, 1965. 564с.

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

56. Математическая энциклопедия, М., «Советская энциклопедия», 1979, т.2.

57. Мельников О. В., Ремесленников В. Н., Романьков В. А. и др. Общая алгебра. /Под ред. Скорнякова И. А., т. 1. М.:Наука, 1990. - 592с.

58. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. М.: Радио и связь, 1985. - 248с.

59. ПершинаМ. В., ЧичеваМ. А. Декомпозиция двумерного ДПФ с представлением данных в алгебре кватернионов. //Компьютерная оптика, № 14-15, Часть 2, 1995. с. 13-21.

60. Понтрягин Л.С. Обобщения чисел. М.: Наука, 1986. 120 с.

61. Сергеев В.В., Усачев А.В. Новый алгоритм быстрого преобразования Хартли //Компьютерная оптика, 1990. Вып. 7. - с.66-67.

62. Сильвестров В.В. Системы чисел //Соросовский Образовательный Журнал. 1998, № 8, с. 121-127.

63. Судаков Ю.А. Алгоритм быстрого преобразования Фурье с минимальным числом умножений //Радиотехника и электроника, 1990. т.35. - №6. -с. 1260-1266.

64. Судаков Ю.А. Формы минимального алгоритма быстрого преобразования Фурье //Радиотехника и электроника, 1992. т.37. - №1. - с.117-125.

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

66. Фаддеев Д.К. Лекции по алгебре. М.: Наука, 1984.

67. Фурман Я.А., Кревецкий А.В., Передреев А.К. Введение в контурный анализ; приложения к обработке изображений и сигналов. Под ред. Фурмана А.Я. М.: ФИЗМАТЛИТ, 2002. - 592 с.

68. Чернов В.М. Двумерные дискретные ортогональные преобразования с рекуррентным базисом //Научное приборостроение, 1993. т.З. - №1.с.110-115.

69. Чернов В.М. Реализация теоретико-числовых преобразований в кодах, порожденных избыточными системами счисления //Электронное моделирование, 1993. т.15. - №4. - с.33-37.

70. Чернов В.М. Алгоритмы дискретного преобразования Фурье с представлением данных в полях алгебраических чисел //Автоматика и выч. техника, 1994. №4. -с.64-69.

71. Чернов В.М. Алгоритмы дискретных ортогональных преобразований, реализуемые в кодах Гамильтона Эйзенштейна //Проблемы передачи информации, 1995. - т.31. - №3. - с.38-46.

72. Чернов В.М. Новый алгоритм дискретного преобразования Фурье по основанию пять //Компьютерная оптика, 1995. №14-15. - ч.2. - с.4-12.

73. Чернов В.М. О сложности алгоритмов дискретных ортогональных преобразований в расщепленной арифметике //Тезисы докладов 7-ой Всесоюзной конференции "Математические методы распознавания образов (ММРО-7)". Звенигород, 1995, - с.61.

74. Чернов В.М. Об иерархии групповых алгебр, связанной с параметризацией быстрых алгоритмов дискретных ортогональных преобразований //Доклады Академии наук, 1997. т.357. - №3. - с.317-319.

75. Чернов В.М., Першина М.В. Реализация дискретных преобразований с представлением данных в избыточных системах счисления //Методы и средства обработки сложной графической информации: Тезисы докладов

76. Всесоюзной конференции. Нижний Новгород: Нижегородский госуниверситет, 1991. - с.82.

77. Чернов В.М., Чернов А.В. О классах преобразований изображений, представимых вращениями в алгебре Клиффорда // Тезисы докладов 8-ой Всесоюзной конференции "Математические методы распознавания образов (ММРО-8)". -М., 1997. с.119.

78. Чернов В.М., Чернов А.В. О классах преобразований изображений, представимых вращениями в алгебре Клиффорда. Доклады Академии наук, т.357, N 3, 1997, с.119.

79. Чернов В.М., Чичева М.А. Алгебро-арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований. В книге "Методы компьютерной обработки изображений" (под ред.В.А.Сойфера), М.:Наука., 2001, с. 301-384.

80. Ярославский JI. П. Введение в цифровую обработку изображений. М.: Советское радио, 1979. - 312с.

81. Ярославский JI. П. Цифровая обработка сигналов в оптике и голографии: введение в цифровую оптику.- М.: Радио и связь, 1987. 297с.

82. Agayan S.S., Grigoriyan A.M. Discrete unitary transfer- mations and their relation to covering of fundamental periods (Part 1) //Pattern Recogn. and Image Analysis, 1993. V.4. - № 1. - pp. 16-23.

83. Agayan S.S., Grigoriyan A.M. Discrete unitary transfor- mations and their relation to covering of fundamental periods (Part 11) //Pattern Recogn. and Image Analysis, 1993. V.4. - №1. - pp.24-31.

84. Aliev M.V., Chernov V.M. Two-dimensional FFT-like algorithms with overlapping //Optical Memory and Neural Networks (Information Optics), v.ll, no. 1,2002 p.29-38.

85. Aliev M. V. Synthesis of Two-Dimensional DFT Algorithms in the Hypercomplex Algebra //Pattern Recognition and Image Analysis, Vol. 13, No. 1,2003 p. 61-63.

86. Allenby, R.B.J.T., Rings, Fields and Groups: An Introduction to Abstract Algebra, 2nd edition, 1991.

87. Arena P., Fortuna L., Re R., and Xibilia M.G. Multilayer perceptrones to approximate comlex valued functions. Neural Systems, 6:435-446, 1995.

88. Bouguezal S., Chikouche D., Khellaf A. An Efficient Algorithm for the Computation of the Multidimensional Discrete Fourier Transform //Multidimensional Systems and Signal Processing, pp. 275-304, 10 (3) July1999.

89. Boyer, Carl В. , revised by Merzbach, Uta C., A History of Mathematics, 2nd edition, 1991.

90. Briggs W.L., Van Henson E. The DFT: An owner's manual for the discrete Fourier transform. -SIAM, 1995. 434p.

91. Brigham E.O. The Fast Fourier Transform and its Applications //Prentice Hall, Englewood Cliffs, NJ, 1988.

92. Buchholz S. Algebraische Einbettungen Neuronaler Netze. Master's thesis, Cognitive Systems Group, Inst, of Сотр. Sci., Univ. of Kiel, Germany, 1997.

93. Buchholz S. In G. Sommer, editor, Geometric Computing with Clifford Algebra. Springer-Verlag, Heidelberg, pp. 187-207, 2001.

94. Buelow T. Global and Local Hypercomplex Spectral Signal Representations for Image Processing and Analysis. PhD thesis, Christian-Albrechts-University of Kiel, 1999.

95. Buelow Т., Sommer G. Algebraically extended representations of multidimensional signals //Proc. SCIA'97. Lappeenranta, Finland, 1997. - pp.559566.

96. Buelow Г., Sommer G. Das Konzepi einer zweidimensionale Phase unter Vervendung einer algebraisch erweiteren Signalrepresentation //19. DAGM Simposium Muster- erkennung.-Braunschweig, 1997. S.351-358.

97. Buelow Т., Sommer G. Multi-dimensional signal processing using an algebraically extended signal representation //Proc. AFPAC'97. Kiel, Germany, 1997. - Springer, - LNCS 1315. - pp.148-163.

98. Buelow Т., Felsberg M., Sommer G. Non-commutative hypercomplex Fourier transforms of multidimensional signals. In G. Sommer, editor, Geometric Computing with Clifford Algebra. Springer-Verlag, Heidelberg, pp. 187-207, 2001.

99. Chernov V.M. Non-Archimedian Normalized Fields and Algorithms for Two-Dimensional Discrete Fourier Transform // Pattern Recogn. and Image Analysis, 1991. V.l. - №4. - pp.426-429.

100. Chernov V.M. Fast algorithms of discrete orthogonal transforms for data represented in cyclotomic fields //Pattern Recogn. and Image Analysis, 1993. -V.3. -pp.455-458.

101. Chernov V.M. A metric unified treatment of two- -dimensional FFT //Proc.of ICPR'96.-Vienna, 1996. V.2. - Track B. - pp.662-669.

102. Chernov V.M. Algorithms, relalizable in Hamilton-Eisenstein codes, for two-dimensional discrete orthogonal transforms. Problem Inform. Transmission, No. 3., pp. 228-235, 1996.

103. Chernov V.M. Chess algorithms of the two-dimensional discrete Fourier transform //Pattern Recogn. and Image Analysis, 1996. V.6.- №1. - p. 189.

104. Chernov V.M. Vector-radix FFT with splitting the radix of fractional order //Proc. of the 10th Scandinavian Conference on Image Analysis (SCIA'97). -Lappeenranta, Finland, 1997. V.2. -pp.551-558.

105. O.Chernov V.M., Bayro-Corrochano E. Clifford models of image transforms. //Pattern Recognition and Image Analysis. V.8, N 2, pp. 272-273, 1998.

106. Chernov V., Buelow Т., Felsberg M. Synthesis of fast algorithms for discrete Fourier-Clifford transform //Pattern Recognition and Image Analysis, V.8, N 2, pp. 274-275, 1998.

107. Chernov V.M. Clifford algebras are group algebras projections. In: E.Bayro-Corrochano, G.Sobczyk (Eds) Advanches in Geometric Algebra with Applications in Science and Engineering.-Birkhauser, Boston, pp. 467-482, 2001.

108. Chernov V.M. Discrete Stockes theorem and multidimensional DFTs //The 4-th Open Russian-German Workshop "Pattern Recogn. and Image Analysis". -Extended abstract. pp.40-44.

109. Chichyeva M.A. Algorithms of discrete cosine transform with data representation in Eisenstein's codes //Image Proc. and Commun., 1996. V.2. -№4. - pp.53-60.

110. Chichyeva M A., Pershina M. V. On various schemes of 2D-DFT decomposition with data representation in the quaternion algebra. //Image Processing and Com^iuriWtiori^ Institute of TelecornmnmVations Bydgoszcz, Poland, Vol. 2, No. 1, pp. 13-20 , 1996.

111. Chichyeva M. A. Synthesis of fast algorithms of two-dimensional discrete cosine transforms based on quaternion algebra. //Pattern Recognition and Image Analysis, Vol. 8, No. 2, pp. 280-282, 1998.

112. Cizek V. Discrete Fourier transforms and their applications. -A.Hilger Publ., 1986.- 14 lp.

113. Clifford W. Preliminary Scetch of Biquaternions. Proc. of London Math. Soc., Vol IV, pp. 381-393, 1873.

114. Cooley J.W., Tukey J.W. An Algorithm for the Machine Computation of Complex Fourier Series //Math. Сотр., 1965. №19. - p. 297-301.

115. Dubois E., Venetsanopoulos A.N. A new algorithm for the radix3 FFT //IEEE Trans., 1978. -ASSP-26. №3, - pp.222-225.

116. Dubois E., Venetsanopoulos A.N. The generalized discrete Fourier transform in ring of algebraic integers //IEEE Trans., 1980. ASSP-28. - №2. - pp. 169-175.

117. Duhamel L., Hollman H. Split-radix FFT algorithm //Electron Lett., 1984. -V.20. №17 - p. 14-16.

118. Duhamel P. Implementation of split-radix FFT algorithm for complex, real, and real-symmetric data //IEEE Trans., 1984. ASSP-34. - V.34. - №2. - pp.285295.

119. Duhamel P., Vetterli M. Fast Fourier Transforms: A Tutorial review and a state of theart //Signal Processing, Vol. 19, No. 4, pp. 259-299, April 1990.

120. Ell T.A. Quaternion-Fourier transform for analysis of 2-dimensional linear time-invariant partial- differential systems //Proc. of the 32th IEEE Conf. on Decision and Control, 1993. V.l-4. -pp. 1830-1841.

121. Felsberg M., Buelow Т., Sommer G., Chernov V.M. Fast Algorithms of Hypercomplex Fourier Transforms. In: G.Sommer (Eds) Geometric Computing with Clifford Algebras. Springer-Verlag, pp. 231-254, 2000.

122. Felsberg M., Sommer G. Fast algorithms for the hypercomplex Fourier transforms //In 2nd International Workshop on Transforms and Filters Banks, Brandenburg an der Havel, pp. 295-302, 2000.

123. Felsberg ML, Buelow Т., Sommer G. Commutative hypercomplex Fourier transforms of multidimensional signals. In G. Sommer, editor, Geometric Computing with Clifford Algebra. Springer-Verlag, Heidelberg, pp. 209-229, 2001.

124. Felsberg M., Sommer G. The structure multivector. In L. Dorst, C. Doran and J. Lasenby, editors, Applications of Geometric Algebra in Computer Science and Engineering, pp. 437-446. Proc. AGACSE 2001, Cambridge, UK, Birkhauser Boston, 2002.

125. Georgiou G. and Koutsougeras C. Complex domain backpropagation. IEEE Trans. Circ. And Syst. II, 39:330 334, 1990.

126. Gibson J.J. Optical motions and transformations as stimuli for visual perception. Psych. Rev., 64(5):288 295, 1957.

127. Gibson J.J. The Ecological Approach to Visual Perception. Houghton Mifflin Company, 1979.

128. Good I.J. The interaction algorithm and practical Fourier analysis //J.Royal Stat. Soc., 1958. V.B-20. - pp.361-372.

129. Grassmann H. Der Opt der Hamilton4 schen Quatemionen in der Ausdehnungslehre. Mathematische Annalen, 12:357, 1877.

130. Hamilton W.R. Lectures on Quaternions. Dublin, 1853.

131. Kienle G. Experiments concerning the non-Euclidian structure of the visual space. Bioastronautics., 4:386 400, 1964.

132. Kosheleva O., Cabrera S.D., Gibson G.A., Koshelev M. Fast implementations of fuzzy arithmetic operations using fast Fourier transform (FFT) //Fuzzy Sets and Systems, No. 2, pp. 269-277, 1997.

133. Labunets E.V. Group-Theoretical Methods in Image Recognition. Technical report, LiTH-ISY-R-1855. Linkoping University, 1996.

134. Labunets E.V. Labunets V.G., and Greutzburg R. Fast factorial trigonometrical transform. In Second Workshop on Transforms and Filterbanks, Brandenburg, 1999.

135. Labunets E.V. Labunets V.G., Egiazarian K., and Astola J. Hypercomplex moments application in invariant image recognition. In Int. Conf. On Image Processing 98, pages 256-261, 1998.

136. Luneburg R.K. Metric methods in binocular visual perception. Studies and Essays. Courant Anniv., 1:215 239,1948.

137. Luneburg R.K. The metric methods in binocular visual space. J. Opt. Soc. Amer., 40(10):627 642, 1950.

138. Lasenby, A.N., Doran, C.J.L. and Gull, S.F. (1996). Lectures in Geometric Algebra, In: W. E. Baylis, Ed., Cliord (Geometric) Algebras with Applications to Physics, Mathematics and Engineering, Birkhouser, Boston, 256 p.

139. Lee Y.-Y., Lo P.-C. Real-time implementation of the split-radix FFT An algorithm to efficiently construct local butterfly modules //Signal Processing, Vol. 71, No. 3, pp. 291-299, 1998.

140. Liu G., Wang Q., Liu S.B. A three-dimensional thermomechanical asperity contact model for two nominally flat surfaces in contact, to appear in ASME Journal of Tribology, Vol. 123, pp. 595-602, 2001.

141. Lo P.-C., Lee Y.-Y. Real-time implementation of the moving FFT algorithm //Signal Processing, Vol. 79, No. 3, pp. 251-259,1999.

142. Pearson J.K. Clifford Networks. PhD thesis, Univ. of Kent, 1994.

143. Sipp F., Wade W.R., Simon P. Walsh series: An introduction to the dyadic harmonic analysis. A. Hilger Publ., 1990. - 528p.

144. Sorensen H. V., Heideman M. Т., Burrus C. S. On computing the split-radix FFT//IEEE Trans., 1986. ASSP-34. - №1. - p. 152-156.

145. Thomas L. H. Using a Comhuter to Solve Problems in Physics, in Applications and of Digital Computer //Ginn and Co. Boston, Mass. - 1963.

146. Van Loan C. Computational frameworks for the fast Fourier transform. -SI AM, 1992. 273p.

147. Wang Z. Fast algorithms for the discrete W transform and for the discrete Fourier transform /ЯЕЕЕ Trans., 1984. ASSP-32. - №4. - p.803-816.

148. Winograd S. On Computing the Discrete Fourier Transform //Proc. Nat. Acad. Sci. USA, 1976. V.73. - p.1005-1006.

149. Winograd S. On the Discrete Fourier Transform //Math. Сотр., 1978. №32. -pp. 175-199.

150. Winograd S. Arithmetic complexity of computations. SLAM, 1980. - 93p.

151. Yamamoto S. Effective implementations of multi-dimensional radix-2 FFT //Computer Physics Communications, Vol. 125 ,pp. 1-7, 2000.