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

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

Каспарьян Михаил Суренович

Дискретные ортогональные преобразования сигналов,

определенных на самоподобных областях

05.13.17 - Теоретические основы информатики

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук 1 Ч ОКТ 2015

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего образования «Самарский государственный аэрокосмический университет имени академика СП. Королёва (национальный исследовательский университет)» и в федеральном государственном бюджетном учреждении науки Институте систем обработки изображений Российской академии наук.

Научный руководитель:

доктор физико-математических наук Чернов Владимир Михайлович

Официальные оппоненты:

Визильтер Юрий Валентинович, доктор физико-математических наук, старший научный сотрудник федеральное государственное унитарное предприятие «Государственный научно-исследовательский институт авиационных систем», начальник лаборатории компьютерного машинного зрения;

Лабунец Валерий Григорьевич, доктор технических наук, профессор, федеральное государственное автономное образовательное учреждение высшего профессионального образования «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина», заведующий кафедрой теоретических основ радиотехники.

Ведущая организация:

Федеральное государственное бюджетное учреждение науки Вычислительный центр им. А. А. Дородницына Российской академии наук, Москва.

Защита состоится 20 ноября 2015 г. в 12:00 часов на заседании диссертационного совета Д 212.215.07, созданного на базе федерального государственного автономного образовательного учреждения высшего образования «Самарский государственный аэрокосмический университет имени академика СП. Королева (национальный исследовательский университет)», по адресу: 443086, г. Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке и на сайте федерального государственного автономного образовательного учреждения высшего образования «Самарский государственный аэрокосмический университет имени академика СП. Королева (национальный исследовательский университет)», http://www.ssau.ru/resources/disjjrotection/kaspariyan/.

Автореферат разослан 22 сентября 2015 г.

Учёный секретарь

диссертационного совета Д 212.215.07 доктор технических наук, профессор

ущггалоои^^ И.В. Белоконов

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

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

Актуальность темы

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

1. Аппарат ДОП позволяет выделить набор определенных стандартных операций, из которых, как из готовых блоков, можно строить алгоритмы для решения широкого класса задач.

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

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

4. Базисные функции некоторых ортогональных преобразований для определенных классов сигналов являются близкими к базисным функциям преобразования Карунена-Лоэва (ПКЛ). Например, базисные функции ДКП для многих сигналов, описываемых моделями стационарных случайных процессов, близки к базисным функциям ПКЛ.

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

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

7. ДОП позволяют решать ряд задач вычислительной математики, физики и информатики. Историю быстрых алгоритмов обработки сигналов принято отсчитывать с 196S г., когда Кули и Тьюки опубликовали свой быстрый алгоритм вычисления дискретного преобразования Фурье, хотя ранее Гуд (I960 г.) и Томас (1963 г.) опубликовали в практически незамеченных современниками работах свои быстрые алгоритмы дискретного преобразования Фурье, базирующиеся на несколько ином подходе.

За время, прошедшее с первых публикаций, дискретный спектральный анализ стал одним из основных средств решения задач цифровой обработки сигналов, распознавания образов, машинного зрения, компьютерной оптики и т.д. Разработке эффективных (быстрых) алгоритмов вычисления спектров различных дискретных преобразований посвящено большое количество публикаций, как у нас в стране, так и за рубежом (Ахмед, Блейхут, Брейсуэлл, Вариченко, Лабунец, Лаппа, Ярославский, Дагман, Кухарев, Cizek, Sipp, Van Loan, Winograd). Значительный вклад в развитие общей теории дискретных преобразований и их быстрых алгоритмов внесли С.С. Агаян, H.H. Айзенберг, В.А. Власенко, В.Г. Лабунец, A.M. Крот, А.М. Трахтман, Л.П. Ярославский, Р. Агарвал, Ш. Виноград, Г. Нуссбаумер, Ч. Рейдер и др. Высокоэффективные алгоритмы конкретных преобразований, адаптированные к характеристикам применяемых вычислительных средств разработаны И.Е. Капориным, Е.Е. Тыртышниковым, А.М. Григоряном и другими исследователями (Гречишников, Григорян, Капорин, Wang, Sorensen).

До последнего времени наиболее известными общими подходами являлись метод кроне-керовской факторизации матриц ДОП (Крот, Власенко, Лаппа, Трахтман, Ярославский) и метод полиномиальных преобразований (Блейхут, Крот, Нуссбаумер, Winograd).

Первый из них опирается на известную теорему Гуда : если матрица ДОП представима в виде кронекеровской степени некоторой матрицы, то она представима и в виде обычной матричной степени некоторой «слабозаполненной» матрицы. К сожалению, отсутствие общих теорем о кронекеровской факторизации матриц ограничивает возможности этого метода, по существу, классификацией алгоритмов, синтезированных независимыми методами.

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

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

- редукция Кули-Тьюки для (р — простое число);

- редукция Гуда-Томаса для (Р, Ц — взаимно простые числа);

- редукция Рейдера для (р — простое число);

- методы «совмещенного» вычисления ДОП вещественных сигналов.

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

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

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

На наш взгляд, в теории ДОП можно выделить три основные проблемы, а именно:

1) для данного класса сигналов подобрать наилучшее ДОП, позволяющее решать те или иные задачи ЦОС, в частности, для задачи сжатия таким преобразование является преобразование Карунена-Лоэва, которое не обладает быстрыми алгоритмами в общем случае, поэтому на практике предпочтение отдается пусть не оптимальным, но по крайней мере тем, которые можно быстро вычислять;

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

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

В диссертационной работе рассматриваются только вторая и третья задачи.

Актуальность первой задачи именно к задаче обработки сигналов, связана с тем, что первоначальный энтузиазм, вызванный появлением первых работ, посвященных фракталам - объектам, которые в классических учебниках математического анализ фигурировали лишь в качестве «патологических» контрпримеров к теоремам («ковёр Серпинского», «сапог Шварца» и т.п.) постепенно пошёл на убыль. Между тем, самоподобные, ветвящиеся структуры/объекты на изображениях достаточно типичны и естественны. Эта естественность может объективно определяться как спецификой предметной области, так и субъективными визуальным восприятием или моделью наблюдений.

Именно такие структуры характерны, например, для наномасштабных изображений натурных образцов, для обработки которых приходится использовать традиционный, но всё же паллиативный, математический аппарат цифрового спектрального анализа: дискретные спектральные методы, хорошо зарекомендовавшие себя при обработке и анализе изображений, ориентированы, прежде всего, на применение к изображениям, определенным на прямоугольных областях. Хотя исследователя очень часто интересуют спектральные характеристики объекта, а не «объекта на фоне». В частности, особое место занимают изображения, для которых особенности психофизиологического восприятии человеком порождают оптические иллюзии из-за наличия фона, формирующего в сознании неадекватную интерпретацию изображения. Между тем, даже при наличии априорной информации именно о «ветвистом», «самоподобном» характере анализируемого объекта, его спектральная специфика может быть учтена только при предварительном «вырезании» этого объекта из малоинформативного (для анализа именно данного объекта) прямоугольного изображения с естественными для такого подхода искажениями спектральных характеристик.

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

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

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

Как известно, дискретное преобразование Фурье (ДПФ) содержит в показателях экспонент билинейную форму, осуществляющую спаривание исходного пространства, на котором определён сигнал, и сопряжённого. Широко известный алгоритм Кули-Тьюки (БПФ) при его реализации осуществляет пространственное или частотное «прореживание» индексов входного или выходного сигнала. В случае преобразования длины, равной степени двойки, эти прореживания могут быть охарактеризованы значением младшего или старшего бита в представлении входных/выходных индексов в обычной двоичной системе счисления. В предлагаемом подходе входные/выходные индексы суть элементы многомерной решетки целых элементов того или иного кольца алгебраических чисел, представленных в т.н. «канонической системе счисления», КСС (т.е. системе счисления, основанием которой являются не «обычное» целое рациональное, а целое алгебраическое число). При такой интерпретации структурные особенности быстрых алгоритмов сохраняются, но возникают дискретные ортогональные преобразования с базисными функциями, отличными от экспонент, фигурирующих в ДПФ.

в задачи блочного кодирования (сжатия) информации широко применяется дискретное косинусное преобразование (ДКП). которое можно характеризовать, как сдвинутое по номеру входящего аргумента преобразование, чем достигается большая длина блока преобразования, в результате чего, в задаче блочного кодирования краевые эффееты, т.е. эффект «Гиббса», выносится за пределы рассматриваемого блока. В общем случае, задача исследования таких сдвинутых си-кус/косинусных преобразований была поставлена С.С. Агаяном, хотя целесообразность рассмотрения этой задачи была анонсирована Ярославским. В цитированной работе С.С. Агаяна решены частные случаи этой задачи при ограниченном выборе параметра сдвига как в частотной, так и во

временной области. е

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

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

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

2 Синтез и исследование быстрых алгоритмов вычисления новых преобразовании.

3 Синтез новых «сдвинутых синус-косинусных» преобразований и получение аналитических условий их ортогональности и биортогональности, синтез быстрых алгоритмов их вычисления.

Мртпяы игглрлований -ее

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

^яучиая новизна работы

1. Введены и исследованы два новых класса дискретных ортогональных преобразовании:

- преобразования, определенные на самоподобных областях;

- «сдвинутые синус-косинусные» преобразования с условиями ортогональности и биортогональности.

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

3. Для введенных преобразований синтезированы быстрые алгоритмы их вычисления. Практическая значимость РабоТЫ

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

?аТошТо"емеди™ртации поддерживались фантами: РФФИ: 12-01-00822-а «Дискретные ортогональные преобразования для предфрактальных областей», 13-01-97С07-р_поволжье_а «Новые математические методы и алгоритмы спектральной обработки цифровых нано- и микроизображений». Работы прошли апробацию на конференциях: «Интеллектуализация обработки информации - ИОИ 2012», «2nd International Eurasian Conference on Mathematical Sciences and

Applications (IECMSA-2013)». Публикации

По темё диссертации опубликовано 6 работ. Из них 4 работы опубликованы в изданиях, определённых в перечне ведущих рецензируемых научных журналов и изданий ВАК Министерства образования и науки РФ.

Структура диссертации

Диссертация состоит из трех разделов, заключения, списка литературы из 69 наименований; изложена на 105 страницах машинописного текста, содержит 17 рисунков.

б

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

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

2. Быстрые алгоритмы вычисления таких преобразований.

3. Доказательство аналитических условий ортогональности и биортогональности базисов «сдвинутых синус-косинусных» преобразований.

4. Синтез матричного алгоритма быстрого вычисления «сдвинутого синус-косинусного» преобразования.

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

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

Дискретное преобразование Фурье

■v-!

х И = = 0.1,-^-1,

л=0

Дискретное преобразование Уолша-Адамара

*=0

Дискретное преобразование Виленкина-Крестенсона

Х(т) = 'Х/(л)ехр{—¿¡/уп, 1, т = ■О.1.—,ЛГ-1.

-Л [ V ы ]

Дискретное косинусное преобразование.

Г_(п+У2)т

N

Так же приводятся краткие сведения о быстрых алгоритмах вычисления вышеприведённых преобразований.

Рассматриваются дискретные синус-косинусные преобразования вида:

A»(n) = A(m)cos[^ao('"+a.)("+a2)j+B(m)sin^a0(m+a,)(n+aJ)j.

Синтезируются новые быстрые алгоритмы вычисления таких преобразований.

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

Системы счисления с основаниями отличными от натуральных чисел рассматривались во многих работах. Так в известной монографии Д. Кнута «Искусство программирования» приводятся примеры позиционных систем счисления с мнимыми основаниями: «мнимочетверичная» система с основанием 2/, «мнимодвоичная» система с основанием и бинарная система счисления с основанием У-1. Так же, системы счисления с основаниями, отличными от натуральных чисел, рассматривались в работах Джильберта (Gilbert).

Разрозненные результаты в области «нестандартных» систем счисления были объединены венгерскими математиками под руководством Катай. В данном разделе рассматриваются результаты, которые были получены в работах (Katai, Kovacs). Приведём краткие сведения о канонических системах счисления (КСС) в мнимых квадратичных поля. Определение 1. Пусть Q^Vc/) есть квадратичное поле:

= {г = а + b-Jd-а, Ь е d - целое число, свободное от квадратов.

Если для элемента = = а + е «З(^) норма и след есть целые числа,

[Ц

Тг(=)=(а+ьЛ)+(а-ьЛ), (2)

то элемент называется целым алгебраическим элементом поля «З(^). Целые элементы образуют решётку на комплексной плоскости.

Определение 2. Целое алгебраическое число а = А + Л называется основанием канонической системы счисления в кольце целых элементов поля , если любой целый элемент этого по-

ля однозначно представим в форме конечной суммы

н->

-а',

иJ га

Пара {а, Л'} называется канонической системой счисления (КСС) в кольце целых элементов

поля

В работе рассматривается только случай ¿<0, то есть мнимые квадратичные поля. Приведём несколько примеров канонических систем счисления с различными нормами. Пример 1. Пусть №>™(<х) = 2, тогда в силу (3) N = {0,1} ■ Существует ровно три мнимых квадратичных поля для ¿ = -1,-2,-3, в кольцах целых элементов которых существует бинарные КСС, а именно:

кольцо целых гауссовых чисел 2(|)е«2(/) с основаниями, равными а = -1±/;

, г-ч / г\ -1 + /Ч/7 кольцо §1/4/7 )е<Ц;Ч/7] с основаниями, равными а=--—-,

кольцо §(;ч/2)еИЗ(ь/2) с основаниями, равными а = ±1-Д ■ Пример 2. При Ыогт(а) = 1 существуют следующие мнимые квадратичные поля, в кольцах целых элементов которых существуют семеричные канонические системы счисления, а именно: поле 0>(/'7б) с основанием а = -1±ь/б;

ЛГ\ -5±Ф

поле (¡)^\/3] соснованием а =---,

, г-\ -З±ь/П>

поле <0|К/191 соснованием а =----.

Если в формуле (3) к фиксировано, то множество элементов, представимых к - членной суммой, представляет собой ограниченное множество на комплексной плоскости, которое будем называть' к - фундаментальной областью, примеры таких областей изображены на рисунке 1.

Рисунок 1 - Фундаментальные области при ¿ = 6,а = 3 • к = 10, а--1+К/2,

к = 16, а = -1+к

Оттенки серого цвета на приведённых рисунках подчёркивают самоподобный «характер» ¿-фундаментальных областей при растущем к.

В работе БгаЬо) приводится классификационная теорема для КСС в мнимых квадратичных полях, устанавливающая явную связь между параметрами а. Теорема 1.

(а) Пусть ¿2-2, (1* 1(пюс14). Пара {а,Л'} является канонической системой счисления в кольце тогда и только тогда, когда о = А ±-1^, 0 2 -2А <Л:-с/>2;Ле2.

(б) Пусть ¿<,-2,. Пара {а,М} является канонической системой счисления в кольце тогда и только тогда, когда а = Ве2 инечётное.

Запишем дискретное преобразование Фурье длины Ы = р', реЫ, р>\ вформе:

Л'(т) = Хх(л)£(л.т),

(4)

0 = {0,1,2,-,ЛГ-1},

где £(л) = ехр j-^^j, а под п-т понимается обычное умножение.

ДПФ определяется следующими условиями: 1) £(0) = 1;

2) E{p+q)- Е(р)Е(д); (5)

3) значениями, которые Е{п) принимает на множестве

Так же заметим, что для ДПФ справедливы равенства: Е(р') = 1, = ехр j-^7"

£(2n) = {£'(n)}2. Описанные выше условия и равенства помогаю строить быстрые алгоритмы вычисления ДПФ.

Если использовать в качестве отсчетов не целые числа, а элементы из квадратичного кольца

S(V?), которые были описаны выше, с соответствующим основанием системы счисления а, то

условия и равенства (5) не будут выполняться. Поэтому будем искать комплекснозначные базисные функции преобразования

X(m)=Ylx(n)A,(n-m),meDl (6)

неф

где D, - I- фундаментальная область КСС для s(r\/<7J с основанием а, удовлетворяющие условиям:

1) Л,(0)=1 = Л,(а'),

2) Л,(р+д)-Л,(р)Л,(д), (7)

3> *■<**)—{зад}-

Теорема 2 (об ортогональности базисных функций фрактального ДПФ).

Пусть а -основание канонической системы счисления с JVbrm(a) ä 2, множество

dh-=x>y -"у б{<и-,ЛЫя(а)-1} ■

I

- (-фундаментальная область КСС, функция Л,(л) = ехр{С, •х+С, -л}, где

1 Norm[a')(a-â.y

С,=-

-2 л / а'

Шгт(а'У{а-а)

Тогда система функций {Л, (от ■ п) = ехр {С, • п■ m+Сг ■ п ■ m}; m е D,} является ортогональной.

Доказанная теорема позволяет утверждать что преобразование (6) является ортогональным, а это значит, что существует обратное преобразование. Теперь дадим более формальное определение данному виду преобразований.

Определение 3. Пусть а - основание КСС в мнимых квадратичных полях, D, - г-фундаментальная область, Л, (и) = ехр {С, -п+С2 •«}, где

2-П-/-5'

с, ■

Worm(a')-(a-a)' -2nia'

Ыогт(а')(а-а)

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

Х{т) = %х(п)А,(пт),теЦ. (8)

На рисунке 2 представлено графическое представление некоторых базисных функций преобразования (8).

Определение 4. Пусть а - основание КСС в мнимых квадратичных полях, О, - (фундаментальная область. Л, (л) = ехр{С,-п+Сг п), где

2-11-1-а'

С,= С,=

ЛЪгто^а'^а-а) -2-jwa'

Norm(a')(a-a)

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

вид

<")=тг-V^ Ех(т)Л< (»"'). « 6 А-

Norm[a )„ец

ÊÊIÊmÈ

(9)

Шт ШШШ

Рисунок 2 - Действительные части базисных функций ДФПФ.

Пусть а - основание КСС в мнимых квадратичных полях, Д - (-фундаментальная область, Ыогт{а) = 2, тогда фрактальным преобразованием Уолша-Адамара называется преобразование вида

('->

■*"(«> = Е \те°, ■

пеП,

(10)

где п = а', пк е Вх и т = ^тк ак, тк еО,.

¿ей ¿=0

На рисунке 3 представлено графическое представление некоторых базисных функций преобразования (10).

Рисунок 3 - Действительные части базисных функций ФПУА для КСС а = -1+;.

Определение 5. Пусть а - основание КСС в мнимых квадратичных полях, - (р-д)-фундаментальная область. Тогда фрактальное преобразование Виленкина-Крестенсона будет иметь вид:

1 -

Х(т) =

(н)

где

*=0 *=0 Определение 6. Пусть а - основание КСС в мнимых квадратичных полях, £>я - (р-д)-

фундаментальная область. Тогда обратным фрактальное преобразование Виленкина-Крестенсона будет иметь вид:

где

Пользуясь тем, что

Х(т)= £ *(л)Л„] \,теОп,

МП„ )

«-1

]пк ар>, пкеИр и т = -а'',

(12)

2ЛГ

2Ы

2 N

определим базисные функции фрактального аналога ДКП, связанные с базисными функциями фрактального ДПФ тем же образом, что и классическое ДКП связано с классическим ДПФ:

АСаУ4(цдс) = |(лм(и-(*+Р)) + Лм(».-(* + Р)))

Вычисление параметра р является одной из задач, которая решается в диссертации. Было установлено, что

а'"-2а'+1 Р= 2(а-1)

Определение 7. Фрактальным дискретным косинусным преобразованием (ФДКП) называется преобразование:

*(т) = А.(т) (13)

ЛЕС,

где тей,Д(т)-нормирующий коэффициент: Х(ш) =

---,т+те0(то<1а*)

\ Шгт{а)*

I--—Г,т+ги*0((^а')

уШгт(а)

Определение 8. Обратным фрактальным дискретным косинусным преобразованием (ОФДКП) называется преобразование:

х{т)=^Х{пуХ(п)-АС05к (п,т), [14)

пЕ^

где теСк, Х(п) - нормирующий коэффициент:

—-^и + и^ОСтода*)

^ Иогт(а)'

I--—г,л+л*0(тоаа*)

ММ?гт(а)

Принцип построения быстрых алгоритмов для вычисления ФДПФ схож с принципами синтеза быстрых алгоритмов для обычного ДПФ, которые были описаны в первой главе диссертации. Декомпозиция Кули-Тьюки с нормой Ыогт(а) = 2.

N

Сумма в (8) может быть представлена в виде двух сумм длины —:

Х{т) = £х(ая)Лн(^ш)+Л,(И) £*((а+1)л)Л4_,(Пт) =

= ЛГ0(«я)+Л4 (")-*! ("). теОы

где Х0 (т), Х,(т) - спектры длины у от «четных» и «нечетных» элементов последовательности х(п), под «четными» элементами понимаются элементы, номера которых в остатке отделения на а дают ноль, а под «нечетными» те, номера которых в остатке от деления на а дают единицу. Таким образом, ФДПФ на области £>, сведено к двум преобразованиям фрактального Фурье на

V N

облает Д., и к у дополнительным умножениям на Л,(т) с учетом — -периодичности спек-

тра Х(т). Вычисление его второй половины выполняется без дополнительных умножений по формуле

.V (ш+а4"1) = X, (т)+Л, (ш+а'"') .V, (ш) = Х0 (ш) - Л, (т) Л', (и), те . [16] Мультипликативная М$(Ы) и аддитивная сложность такого алгоритма определя-

ется выражениями:

Мсе (Ы) й |N1^ N~N. 4М * 10ёг Л'-1N.

(17)

Декомпозиция Кули-Тьюки с нормой Шгт(а) = 4.

Аналогичным образом строится алгоритм ФБПФ по основанию а с нормой равной 4 при /У = 4'. Сумма в (8) разбивается на четыре части:

Х{т)= (пт) + Л,(т) £ *((а + 1)п)Лм(лт) +

+Л,(2т) ^д:((а+2)«)Л,.,(п-т) + Л,(Зт) ^ л:((а+3)«)Л,.,(г.-т)+= (18)

= Хи (га) + Л, (т) X, (т)+Л, (2т) (т)+Л, (Зт) (т), т е О,., Соотношение (18) редуцирует вычисление ФДПФ (8) к вычислению четырех ФДПФ на областях и к дополнительным умножениям на Л4(/т),» = 1,2,3. Так как Л4(ш+а'~') = /,

Л1(т+2а1м) = -1, Лк (т+За'"1) =/ и при стандартном машинном представлении комплексных чисел умножения на степени мнимой единицы I являются тривиальными, значения спектра при вычисляются без дополнительных умножений следующим образом: (.Х{т)

Л-(т+ам) Х(т + 2а'-')

'I I I Г Г ^(«П

1 I -1 -/ А* (»)*.(">)

1-1 1-1 Л, (2«) *,(<»)

-1 К

, т б Д.,

Оценки вычислительной сложности такого алгоритма имеют вид:

(19)

(20)

Декомпозиция Кули-Тьюки с нормой М>ля(а) й; 2.

Пусть а- основание КСС, £>4 - ¿-фундаментальная область, N = Иогт{а)к, преобразование входной последовательности *(л) определено соотношением (8). Тогда при теО,_, спектр Х(т) может быть представлен в виде:

{Х(т) Х{т+а>А)

Х(т+2ак-')

^(л1 + (М>г/я(а)-1)ам)

(I 1

1 У

1 у1

11 у-'

V2!'-')

Х„(т)) Д >(т)Х,(т) Ак{2т)Хг{т)

.(21)

где Х1 (т) (у' = 0,!,---,Л'огт(а)-1) - ФДПФ на области £)м:

Н = Е (тп),

(22)

Т = Л,(ам).

Третья глава диссертации посвящен обобщенным синус-косинусным преобразованиям. Данный вид преобразований был введен Агаяном и базисные функции данного преобразования имеют вид

Аж(п) = А(т)со5^а0(ш + а1)(п+аг)Ув(т)5т^-|а0(т + о[1)(п+аг^

Однако функции можно представить в более удобном для рассмотрения виде

А„(п) = /<(т)ехР^а0(т+а1)(п+а:)^+Я(т)ехр^а0(т+а1)(п+ос2)^

Теорема 3 (О классе ортогональных базисов). Пусть

НОД(М,а)-\, бе К и выполняется условие согласованности

у+2г 1 № Л2 / Л 4 (а-1) 2 2 а У А1 4 2а6еЖ,

/ А1

21 2 к А2

с = приЬ = -, /б 2, ~4г = ехр(ум), 4а 2 л

тогда система функций (л, (п)}^ ортогональна.

Из соотношений теоремы 3 можно получить как известные преобразования, например преобразование Хартли или преобразования Вонга, так и новые преобразования.

Для преобразования Хартли, например, коэффициент а равен единице, ¿ = / = 0, А = 1+».

Ниже представлены примеры новых ортогональных базисов, полученных с помощью теоремы 1. Пример 3. Пусть

•ЖЯ'ЗЬШ

где НОД(Ы, 9) = 1, тогда система функций {й,}^ будет ортонормированной.

Пример 4. (косинусное преобразование). Пусть

«НН5НН)

ЫЯ-1

^ будет ортонормированнои.

Пример 5. (синусное преобразование). Пусть

где ИОД{N,9) = 1, тогда система функций ^ будет ортонормированной.

Теорема 4. (О классе биортогональных базисов). Пусть

Ая(П) = 4схр[^(/,+б)[Я+1]]+В,ехр^(р + 6)(л+1^ (23)

и

(Я) = 4, «Яф^^+Р)[„+1 (24)

Р+Ь = 1, Рфь и коэффициенты /¡¡, л2, В, и в2 связаны соотношением

4^ехр(га'(6-Р))+яДехр(-га(б-р)) = 0, тогда системы функций ^ биортогональны.

Пример 6. (биортогональное косинусное преобразование). Пусть

и

«м-ЛНтНИ)} <м

тогда система функций |яр) ^ биортогональна системе функций ^ .

Пример 7. (биортогональное синусное преобразование). Пусть

и

тогда система функций {Л,}^ биортогональна системе функций {й*}

Теорема 5. Пусть

А, (я) = 4Л1 (&»+«)(«+Р))+*Л ((р+а)(Л+р))

Р = -^—а -основание канонической системы счисления, а-6 = 0, а+6#О(тоё 1) и выполняется условие

1л,¥2+В,А* О, = 0,

тогда системы функций {A,)p=0 ортогональны.

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

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

2 Представляется перспективным применение синус-косинусных преобразовании при анализе гиперспектральных данных. В силу неизотропности трехмерных данных в этом случае (две координаты пространственные, одна «спектральная»), возможно использование трехмерных базисов - покоординатных произведений одномерных синус-косинусных базисов с различными параметрами.

ПуЯдикяпии по теме диссертации

Статьи в изданиях, входящих в перечень ВАК:

1 Каспарьян М.С. Дискретные ортогональные преобразования на фундаментальных областях канонических систем счисления / М.С Каспарьян, В.М. Чернов // Компьютерная оптика. - 2013. -Т. 37, N2 4. - С. 484-487.

2 Каспарьян, М.С Фрактальные дискретные косинусные преобразования на предфрактальных областях, ассоциированных с фундаментальными областями канонических систем счисления /

М.С Каспарьян//Компьютерная оптика.-2014.-Т. 38, №1.-С. 148-153.

3 Каспарьян, М.С Обобщённые дискретные ортогональные синус-косинусные преобразования / М.С Каспарьян // Компьютерная оптика. - 2014. - Т. 38, № 4. - С 881-885.

4 Каспарьян, М.С. Дискретные косинусные преобразования на развертках предфрактальных областей / М.С Каспарьян // Вестник Адыгейского государственного университета. Сер.: Естественно-математические и технические науки. - 2013. - Вып. 4. - С. 149-153

Материалы и тезисы конференций, статьи в сборниках: 1 Каспарьян М С, Чернов В.М. Дискретные ортогональные преобразования на предфрактальных областях / М.С. Каспарьян // Сборник докладов 9-ой Международной конференции «Интеллектуализация обработки информации - ИОИ 2012»: г. Будва, Республика Черногория, 1622 сентября 2012.-С. 335-338.

2. Kasparyan, М. Discrete cosine transform on pre-fractal domains / M. Kasparyan, V. Chernov // 2nd International Eurasian Conference on Mathematical Sciences and Applications (IECMS A-2013). - P. 431.

Подписано в печать 8.09.2015. Формат 60x84/16. Бумага ксероксная. Печать оперативная. Объем -1,25 усл. печ. л. Тираж 100 экз. Заказ №105 Отпечатано в типографии издательства «Инсома-пресс» 443080, г. Самара, ул. Сапфировой, 110А, оф. 22А, тел. 222-92-40, E-mail: insoma@bk.ru