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

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

□□34565 г2 Перегуда Евгений Станиславович

АЛГОРИТМЫ СОКРАЩЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ФРАКТАЛЬНОГО АНАЛИЗА В СИСТЕМАХ ОБРАБОТКИ ВИЗУАЛЬНЫХ ДАННЫХ

05.13.01 - Системный анализ, управление и обработка информации

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

п к ПРК 7ППЙ

у о <1 -■ - --

Хабаровск - 2008

003456572

Работа выполнена в Тихоокеанском государственном университете

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

Сай Сергей Владимирович

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

Графский Олег Александрович

кандидат технических наук, доцент Бахрушин Александр Петрович

Ведущая организация: Хабаровское отделение Института приклад-

ной математики ДВО РАН

Защита состоится «17» декабря 2008 г. в 14 часов на заседании диссертационного совета ДМ212.294.05 Тихоокеанского государственного университете по адресу: 680035, Россия, г. Хабаровск, ул. Тихоокеанская, 136, аудитория 315 л.

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

Автореферат разослан «14» ноября 2008 г.

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

Бурдинский И.Н.

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

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

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

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

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

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

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

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

Поставленная цель определила следующие основные задачи исследования:

1. Оценка сложности фрактального анализа на основе существующего алгоритма и математическое представление этапов анализа, имеющих

Наибольшую ВЫЧИСЛИхсллпул^ слилшисхь.

2. Разработка и исследование алгоритмов сокращения вычислительной сложности фрактального анализа на основе сокращения вычислительной сложности отдельных этапов алгоритма.

3. Разработка алгоритма фрактального анализа, реализующего разработанные алгоритмы сокращения вычислительной сложности.

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

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

Научная новизна работы заключается в следующих разработанных алгоритмах сокращения вычислительной сложности фрактального анализа:

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

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

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

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

5. Алгоритм быстрого построения аттрактора на основе применения «Игры Хаоса». В этом случае получают стохастический алгоритм построения фрактала.

Практическая ценность результатов работы заключается в следующем:

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

2. Разработанная программа, реализующая новый фрактальный алгоритм, позволяет выполнить фрактальный анализ изображения в 30-40 раз быстрее по сравнению с известными аналогами.

3. Результаты диссертационной работы были использованы при решении задач анализа подводных изображений в проектно-конструкторской деятельности Института проблем морских технологий ДВО РАН, а

{

также в учебном процессе Хабаровского института инфокоммуникации (ХФ СибГУТИ).

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

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

2. Алгоритм установления факта аффинного подобия между элементами изображения на базе свойств ядра ортогонального преобразования на примере ДКП.

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

4. Алгоритм быстрого построения аттрактора на основе применения «Игры Хаоса».

5. Быстрый алгоритм фрактального анализа и результаты его исследования в системах обработки визуальных данных.

Апробация результатов работы

Основные положения диссертационной работы были представлены на следующих НТК: Телевидение: передача и обработка изображений. Материалы 4-й международной конференции, Санкт-Петербург, 24-26 мая 2005; IEEE International Siberian Conference on Control and Communication (SIBCON-2005). Proceedings, Tomsk, Russia, October 21-22, 2005; Proceeding of The KOREA - RUSSIA Joint - Workshop 2006 on Signal Transmission, Processing, Sensor and Monitoring Systems, Khabarovsk, Russia, October 26 - 28, 2006; Материалы Седьмой Всероссийской научно-технической конференции, Улан-Удэ, 24-30 июля 2006; Материалы всероссийской научной конференции молодых ученых, Новосибирск, 07-10 декабря 2006 г., конкурс научных работ молодых ученых в области физики, математики и информационных технологий ТОГУ, 20 января 2007 г., X конкурс - конференция молодых ученых Хабаровского края, 8 февраля 2008 г.

Публикации и личный вклад автора

Основное содержание диссертационной работы отражено в _6_ печатных работах, в том числе: _2_ статьи, _3_ доклада на конференциях и _]_ свидетельство об официальной регистрации программы для ЭВМ. Пять работ опубликованы автором без соавторства, в том числе одна статья в издании, рекомендованном ВАК.

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

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 110 наименований, и _2_ приложений. Основная часть работы изложена на 145 страницах машинописного текста и содержит 51 рисунок и _3_ таблицы.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматривается обратная задача фрактального преобразования и применение ее решения для задачи анализа произвольного множества. В начале главы рассматривается математическое условие построения фракталов как континуума в полном метрическом пространстве. Представлено расширение алгоритма построения фракталов, разработанное Барнсли (Barnsley) и называемое системой итерированных функций (IFS). Исходя из данного алгоритма рассмотрена теорема о коллаже.

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

Кроме обзора теоретических исследований проблемы фрактального сжатия изображения в главе представлен обзор прикладных исследований и реализаций программных и аппаратных комплексов фрактального анализа изображений. Все разнообразие алгоритмов фрактального анализа изображений разделяют на четыре основных класса: вариант блочных IFS, вариант векторного квантования, аппроксимация вэйвлет поддеревьев коэффициентов вэйвлет-преобразования, кодирование сверткой элементов изображения. Такое разнообразие алгоритмов связано с тем, что фрактальные алгоритмы имеют NP - сложную природу и не могут быть выполнены за короткое, «полиномиальное» время. Поэтому большинство работ по исследованию фрактальных алгоритмов анализа изображений посвещено методам сокращения сложности вычислений.

Кроме общих сведений о фрактальных алгоритмах в главе приведены описания пяти алгоритмов и рассмотрены их особенности и недостатки. Первым из них приведен алгоритм Фишера. Данный алгоритм относится к классу блочных IFS алгоритмов и является одним из самых первых фрактальных алгоритмов анализа изображения, реализованный на практике и показавший достаточно высокую производительность, что определило именно данный алгоритм в качестве исходного во многих других исследовательских работах. Кроме общего описания данного алгоритма приведена его модификация посредством введения пространства свойств, описывающих ряд характеристик изображений. В модификации предложена кластеризация в данном пространстве свойств посредством самоорганизующейся нейронной сети, что позволяет сократить пространство поиска при установлении подобия. Третий алгоритм основан на поиске в векторном пространстве при использовании структуры k-d дерева. Таким образом, работа алгоритма сходна с работой электронных словарей и других аналогичных поисковых систем. Четвертым алгоритмом приведена гибридная схема, объединяющая стандартный алгоритм JPEG и упрощенный фрактальный алгоритм, основанный на векторном преобразовании. При этом фрактальная

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

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

Далее приводится обоснование выбора в качестве базового алгоритма для разработки алгоритмов ускорения рассмотренного алгоритма Фишера. Приводится указание того факта, что алгоритм фрактального анализа Фишера обеспечивает наилучшее качество аппроксимации. Более того, приводится оценка затрачиваемых операций умножения, сложения и вычитания. Эта оценка составляет три операции умножения, три операции сложения и одну операцию вычитания на один пиксель изображения. Следующее выражение позволяет рассчитать количество операций умножения на один пиксель, учитывая количество доменов Nd и количество преобразований на один домен NÀFf!N:

п =3-N -N

rl* J D AFFIN .

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

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

мов. Цель данной научной работы заключается в разработке методов сокращения данной вычислительной сложности.

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

В качестве отправной точки в поиске методов сокращения сложности рассматривают каждый ранговый и доменный блок как вектор Ли 3 соответственно в линейном векторном пространстве 91", где п-ИхЫ . количество пикселей в квадратном ранговом блоке со сторонами N. Преобразование из квадратного блока со стороной N в вектор длинной п - Л'2 может быть произведено путем построчного сканирования блока.

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

где 5 - масштабирующий коэффициент яркости; с!:] - значение яркости точки домена; о - смещение яркости; гя - значение яркости точки ранга; ||°|| - метрическое расстояние в линейном Евклидовом пространстве. Как видно, при переходе к векторному представлению происходит переход к векторным операциям: умножение вектора на скаляр, сложение вектора со скаляром и вычитание векторов. Данные операции применяют ко всем векторам, и оптимальным решением для уменьшения сложности является переход в линейное векторное ортогональное пространство. А так как постоянная яркости о одна для всего домена, лучше всего осуществить переход в ортогональное многовекторное Евклидово пространство с отдельной составляющей постоянной яркости. Итоговое выражение имеет следующий вид:

\е(а = || я-5 + 0- {1,1,1,1,...д}- Щ => ■ Ь + о • {1,0,0,0.....

где 3 - вектор доменного блока в ортогональном пространстве с Евклидовой метрикой; {1,0,0,0,...,0} . вектор средней яркости всего доменного блока; Л - вектор рангового блока в ортогональном пространстве с Евклидовой метрикой. Наличие отдельной средней яркости позволяет отделить постоянную, не изменяющуюся составляющую от других составляющих, несущих информацию о сложности изображения в пределах блока. Упрощенное выражение имеет следующий вид:

где З"'1 - вектор доменного блока в ортогональном пространстве с Евклидовой метрикой без постоянной составляющей, - вектор рангового блока в ортогональном пространстве с Евклидовой метрикой без постоянной составляющей.

Данное выражение описывает простое условие отклонения с одним неизвестным. Частным случаем является условие полного подобия, т.е. следующее условие ||£(б""1,ЯЛГ"1| = 0. Выражение в этом случае имеет вид простого линейного уравнения с одним неизвестным .у

5 ■ с/, - Гх =0

Исходя из условия полного подобия получаем следующее условие:

¿и-1 •

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

яГ1

.у =

д

N-1

_ Л/г02+г,2+... + г2

N-1

лЙ

Общее решение в этом случае имеет следующий вид: Я""1

1

Д

лм

-В^-Я

и-1

Я

N~ 1

Д

Я

N-1

Д

ЛМ

Я

N-1

Данное выражение можно упростить, если принять во внимание, что множитель метрики рангового блока '| постоянный при переборе доменов Д*"1 и данный множитель можно исключить из расчетов. В итоге выражение принимает следующий вид:

Д

дм

я

IV-1

Д

ЛГ—11

я

Дроби вида 1 и являются выражениями нормализации векторов домена и ранга в нормированном метрическом пространстве и имеют обозначения ф{р"~{) и соответственно. Выражение метрики отклонения имеет сле-

дующий вид:

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

операцию деления одного скаляра на другой. При этом только одна операция умножения на все пиксели. Третью операцию умножения исключают путем перехода от метрики в Евклидовом пространстве к метрике по абсолютному значению:

№

JV-l gN-l

=К +---+К-1

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

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

ЭСТ{у(х,у)) = ОСТ(г{х,(Я-\)-у))г

где ¥{Х'У) - прямое изображение, а У(х,(Ы-\)-у) . зеркально отраженное. Данное тождество имеет смысл только для четных коэффициентов ДКП. Таким образом, для изометрических аффинных преобразований одного изображения четные коэффициенты ДКП идентичны. Достаточно при этом проверить только четные коэффициенты на основе следующего выражения:

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

ЧЕТ

+ А<£

НЕЧЕТ

Но если условие коллажа для четных коэффициентов не выполняется, то и условие полного коллажа выполнятся не будет.

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

Третий алгоритм. Последним алгоритмом сокращения сложности является алгоритм выбора оптимального изометрического аффинного преобразования. Для этого используется неравномерное распределение энергии по коэффициентам ДКП. Данное свойство выражается в так называемом «Зигзаг» сканировании, хорошо известным из спецификации JPEG. Коэффициенты с младшими индексами формируют крупные, медленно изменяющиеся структуры на изображении. Коэффициенты со старшими индексами формируют небольшие, быстро изменяющиеся структуры. Закон изменений знаков старших и младших индексов одинаков. Но визуально заметными являются значения младших коэффициентов. Их вклад наиболее заметен. Исходя из этого достаточно, чтобы

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

Результатом реализации является сокращение времени анализа в 8 раз.

Быстрый алгоритм синтеза аттрактора. Математический аппарат теории фракталов гарантирует сходимость многократно примененного фрактального преобразования к точке устойчивости - аттрактору, близкому к исходному изображению. Существует алгоритм построения фрактального изображения (аттрактора) с помощью IFS. Это является прямым применением теоремы о сжимающих отображениях. Однако более перспективным является применение так называемой «Игры Хаоса». Данный алгоритм в своей реализации базируется на понятии «детерминированного хаоса». Алгоритм классического построения аттрактора выражается следующим уравнением:

где устанавливается простая линейная связь между двумя множествами и Ап. Данная связь описывается преобразованием W = {wl,w2>...,wv}. Итерация заканчивается, когда во множестве Л„ изменение значений яркости переходит в дробную часть. Для уменьшения числа итераций необходимо, чтобы дробная часть росла быстрее. Это условие выполняется при переходе от параллельного отображения Д, =w(4,-i) к последовательному обходу множества отображения W = {w„w2,...,wN} при прямой ссылке на самом множестве А„. Это можно представить в следующем виде:

Даже незначительное отклонение любой из переменных приведет к изменению всего множества А„. Данное решение называется хаотическим, так как для него характерны высокая чувствительность к начальным условиям и эволюция в пространстве AvA2,...,An, представляющаяся весьма «хаотичной». Таким образом, алгоритм синтеза становится стохастическим. Это выражается в том, что изменение перлдгса обхода рапгсз меняет токущ^ш шерацию (и ш время как в детерминированном алгоритме порядок обхода никак не влияет на текущую итерацию). Каждая новая комбинация обхода рангов в новом алгоритме создает уникальную итерацию, но все возможные комбинации всегда сходятся к аттрактору, являющемуся закодированным изображением.

Более быстрым является алгоритм на основе «Игры Хаоса», что позволяет реализовать простой и быстрый алгоритм синтеза фрактального множества. Оценка работы классического и стохастического алгоритмов фрактального синтеза представлена на рис. 1. Данная оценка сравнивает качество, определяемое РБ№1 (с!В), достигаемое при заданном количестве итераций. Для нового алгоритма достаточно четырех итераций, чтобы изображение стало практически неподвижным аттрактором, в то время как для классического алгоритма требуется шесть итераций. Преимущество нового алгоритма заключается в сокращении времени работы на 30%.

В результате оценочное сокращение времени фрактального анализа составляет от 30 до 40 и более раз, в зависимости от состава изображения.

--♦- Классический алгоритм

—■— Стохастический алгоритм

1-1-1-1-1-1-г

1 23456789 10 Количество иттераций

Рис. 1. Оценка работы классического и стохастического алгоритмов фрактального синтеза

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

1. Начало. Расчет количества ранговых и доменных блоков.

2. Разбиение изображения на блоки рангов и доменов.

3. Расчет коэффициентов ДКП ранговых и доменных блоков.

4. Этап проверки на обработку всех рангов. Если обработаны не все ранги, то обрабатываются оставшиеся. Если обработаны все ранги, то алгоритм прекращает свою работу.

5. Расчет метрики отклонения доменов и рангов для четных коэффициентов ДКП.

6. Выбор оптимального аффинного преобразования.

7. Расчет метрики отклонения доменов и рангов на основе нормированных коэффициентов ДКП.

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

жества {Б^ соотносят восемь ребер, определяемых восьмью аффинными преобразованиями ф = {1, 2, ...,8}. Граф состояний базового алгоритма Фишера представлен на рис. 2, где {Е(0,Д])} - множество отклонений метрик доменов от ранга, 1 - номер домена от 0 до М-1, ] - номер ранга от 0 до >1-1.

Ко 1^+1

-N-2

Я]

■N■1

Рис. 2. Граф - состояний базового алгоритма Фишера

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

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

Ко

/

/

/

/ {ЕСБОД^Зчет}

^{ЕРМ-Ь^+Очет}

{Е(Е>м-ьК)+1)нечет}

Рис. 3. Граф - состояний улучшенного алгоритма фрактального анализа

визуальных данных

При сравнении рис. 2 и 3 очевидна значительная разница между базовым алгоритмом Фишера и новым разработанным алгоритмом*--Наличие в новом алгоритме промежуточной вершины между двумя соседними вершинами - рангами - позволяет ввести элемент динамического программирования. Динамическое программирование реализуется в виде разработанного второго алгоритма сокращения вычислительной сложности. Третий алгоритм позволяет выбрать оптимальные нечетные коэффициенты домена. Таким образом, между соседними вершинами - рангами - каждому домену соответствует только одно ребро. Время перебора всех доменов сокращается как минимум в восемь раз. Первый алгоритм исключает три операции умножения и две операции сложения, что соответствует сокращению времени работы в три - четыре раза. Суммарное сокращение времени работы составляет 30-40 раз.

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

В начале главы описывается программа фрактального анализа визуальных данных.

Отдельно приводятся статистические исследования алгоритма Фишера. Данная статистика необходима для экспериментального сравнения разработанных алгоритмов с базовым алгоритмом Фишера. В качестве тестового было выбрано изображение «Lena» (рис. 4) и изображение «Пересечение» (рис. 5).

О

Рис. 5. «Пересечение»

В большинстве исследований графических алгоритмов именно изображение «Lena» с размерами 256*256 и 512x512 избирается в качестве тестирующего изображения. Для исключения субъективности восприятия качества использована такая широко распространенная мера качества как пиковое отношение сигнал/шум (PSNR).

При реализации алгоритмов сокращения вычислительной сложности на базе ДКП возникает проблема с ограничениями практических реализаций алгоритмов ДКП. Проблема заключается в том, что длина вектора данных должна быть равна 2", где п - целое положительное число. Таким образом, необходимо выбрать ранги фиксированных размеров указанной длины. Определим следующую серию размеров рангов: 16х16, 8x8, 4x4. Зависимость качества от рангов представлена на рис. 6.

Рис. 4. «Lena»

Качество

13 Качество

16x16 8x8 4x4

Размер рангов

Рис. 6. График Р8№1 для размеров рангов 16^16, 8x8, 4x4

Как видно из рис. 6 оптимальный размер ранга составляет 4x4.

Далее приводятся результаты статистических исследований. Данные исследования представлены в виде графика на рис. 7. На данном графике представлены две кривые: время выполнения программы на базе алгоритма Фишера (1) и время выполнения программы на базе разработанных алгоритмов (2).

Время выполнения

500

450

^ч 400

те =5 <40

1ПП

<и и 750

200

К - 150

а 65 100 •

50 -

I Л

V

Количество доменов

625 1024 2500 6889 15625 62000 Количество доменов

гии. /. 1 рафик времени выполнения программы на базе алгоритма Фишера (1) и времени выполнения программы на базе разработанных алгоритмов (2)

Рис. 8. График качества раОоты программы на базе алгоритма Фишера (1) и качества работы программы на базе разработанных алгоритмов (2)

Как видно из графика (см. рис. 7) эффективность разработанных алгоритмов значительно превосходит алгоритм Фишера (30-40 раз). Причем эта эффективность растет с увеличением числа доменов.

Кроме исследований сокращения времени работы приведены исследования качества. Исследования представлены в виде графика качества (рис. 8). На данном графике представлены две кривые: качество работы программы на базе алгоритма Фишера (1) и качество работы программы на базе разработанных алгоритмов (2). Как видно из графика (см. рис. 8) качество работы разработанных алгоритмов хуже, чем качество работы алгоритма Фишера. Это связано с тем, что в разработанных алгоритмах обработка данных производится в нормированном пространстве. При этом динамический диапазон ограничивается, что и приводит к небольшой неточности. Как видно из графика данная неточность невелика (не более 1-1,5 дБ), и визуально разница незаметна.

Кроме исследований времени работы алгоритмов и качества анализа, приведены исследования степени сжатия нового алгоритма фрактального анализа. Результаты сравнения качества сжатия от степени сжатия фрактального алгоритма и алгоритмов JPEG и JPEG2000 представлены в виде графиков на рис. 9

Степень сжатия

-*- Фрактал -»- JPEG -х- JPEG2000 -»- Фрактал -»- JPEG -х- JPEG2000 Рис. 9. Сжатие изображения «Lena» Рис. 10. Сжатие изображения

«Пересечение»

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

Результаты главы подтверждают обоснованность теоретических результатов, разработанных в теоретической части диссертации (гл. 2).

В заключении указано, что в результате выполненной работы получены следующие основные теоретические и экспериментальные результаты.

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

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

2. Выполнен выбор оптимального ортогонального преобразования. Доказано условие подобия для коэффициентов ДКП. Исходя из рассмотренного доказательства представлено условие установления факта подобия.

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

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

5. Реализована схема установления оптимального аффинного преобразования на основе периодичного закона распределения знаков коэффициентов ДКП.

6. Экспериментальное исследование быстродействия нового алгоритма фрактального анализа в системах обработки изображений по сравнению с базовым алгоритмом показало, что применение нового алгоритма позволяет повысить скорость обработки от 30 до 40 раз.

7. Разработан новый алгоритм построения фрактального аттрактора. Время его выполнения на 30% меньше, чем время выполнения алгоритма классического построения аттрактора фрактального преобразования.

8. При работе нового алгоритма достигается качество закодированного изображения, близкое к качеству кодирования базовым алгоритмом Фишера. Визуально это мало заметно, но в числовых значениях разница существует. Для нового алгоритма максимальное значение PSNR достигает 35,1 дБ, в то время как для базового алгоритма это значение составляет 35,9 дБ.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ

1. Pereguda Е. S. Acceleration of Algorithm of Fractal Image Compression / E. S. Pereguda // IEEE International Siberian Conference on Control and Communication (SIBCON-2005). Proceedings. - Tomsk: The Tomsk IEEE Chapter & Student Branch. Russia, Tomsk, October 21-22, 2005. - P. 159-162.

2. Pereguda E. S. Acceleration of Algorithm of Fractal Compression of Images / E. S. Pereguda // Proceeding of The KOREA - RUSSIA Joint - Workshop 2006 on Signal Transmission, Processing, Sensor and Monitoring Systems. - Khabarovsk, Russia, October 26 - 28,2006. - P. 46^*8.

3. Сай С. В., Перегуда Е. С. Методы сокращения объема вычислений в алгоритмах фрактального сжатия изображений / С. В. Сай, Е. С. Перегуда // Вестник Тихоокеанского государственного университета. - 2006. - №1. - С. 9-14.

4. Перегуда Е. С. Методы ускорения фрактальной обработки изображений / Е. С. Перегуда // Теоретические и прикладные вопросы современных информационных технологий: Материалы Всероссийской научно-технической конференции. - Улан-Удэ: Изд-во ВСГТУ, 2006. - С. 98-103.

5. Перегуда Е. С. Ускорение фрактального алгоритма в системах сжатия и передачи изображений / Е. С. Перегуда // Телекоммуникации. - 2007. - №6. -С. 2-7.

6. Архиватор цветного изображения на основе фрактального преобразования: Свидетельство об официальной регистрации программы для ЭВМ. ФГУП «Всероссийский научно-технический информационный центр». Зарегистрировано в национальном информационном фонде неопубликованных документов. Инвентарный номер ВНТИЦ № 50200600375, 2006.

Перегуда Евгений Станиславович

АЛГОРИТМЫ СОКРАЩЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ФРАКТАЛЬНОГО АНАЛИЗА В СИСТЕМАХ ОБРАБОТКИ ВИЗУАЛЬНЫХ ДАННЫХ

05.13.01 - Системный анализ, управление и обработка информации

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

Подписано в печать 12.11.08. Формат 60х84 1/16. Бумага писчая. Гарнитура Times New Roman. Печать цифровая. Печ. л. 1,1 _Тираж 100 экз. Заказ 271._

Отдел оперативной полиграфии издательства Тихоокеанского государственного университета 680035, г. Хабаровск, ул. Тихоокеанская 136.

ВВЕДЕНИЕ.

1. АЛГОРИТМЫ ФРАКТАЛЬНОГО АНАЛИЗА В ЗАДАЧАХ ОБРАБОТКИ

ВИЗУАЛЬНЫХ ДАННЫХ.

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

1.2. Фрактальный анализ визуальных данных в градациях яркости.

1.2.1. Расширение фрактального кодирования.

1.2.2. Операторная схема PIFS.

1.2.3. Существующие алгоритмы фрактального анализа визуальных данных.

1.3. Обоснование выбора базового алгоритма.

1.4. Применение фрактального анализа в широком спектре задач.

Выводы.

2. АЛГОРИТМЫ СОКРАЩЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ФРАКТАЛЬНОГО АЛГОРИТМА.

2.1. Алгоритм сокращения вычислительной сложности расчета метрического расстояния.

2.2. Алгоритм сокращения вычислительной сложности расчета аффинных преобразований.

2.3. Алгоритм сокращения вычислительной сложности перебора аффинных преобразований.

2.4. Анализ алгоритма фрактального декодирования.

2.4.1. Детерминированный алгоритм.

2.4.2. Алгоритм на основе «Игры Хаоса».

Выводы.

3. РАЗРАБОТКА УЛУЧШЕННОГО АЛГОРИТМА ФРАКТАЛЬНОГО АНАЛИЗА ВИЗУАЛЬНЫХ ДАННЫХ.

3.1. Разработка структурной схемы улучшенного алгоритма фрактального анализа визуальных данных.

3.2. Этап предобработки данных.

3.3. Расчет метрики отклонения.

3.3.1. Оценка подобия на основе сравнения четных коэффициентов ДКП.

3.3.2. Выбор оптимального аффинного преобразования на основе знакового распределения коэффициентов ДКП.

3.3.3. Расчет метрики отклонения домена и ранга на основе нормированных коэффициентов ДКП.

3.4. Новый алгоритм синтеза-декодирования аттрактора.

Выводы.

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ СОКРАЩЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ФРАКТАЛЬНОГО АНАЛИЗА.

4.1. Интерфейс программы фрактального анализа изображения.

4.2. Статистические исследования алгоритма Фишера.

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

4.4. Оценка степени сжатия нового алгоритма фрактального анализа.

4.5. Исследование сходимости изображения к аттрактору.

4.6. Исследование свойства масштабирования алгоритма фрактального анализа.

Выводы.

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

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

Применение фрактального анализа в обработке визуальных данных считается одной из перспективных областей применения фрактальной геометрии. В начале 80-х годов Майкл Барнсли выдвинул идею получения заранее заданного множества, интерпретируемого как изображение, в виде аттрактора хаотического процесса. Барнсли использовал специальную систему отображений, которые он назвал системой итерируемых функций. При этом целое изображение рассматривают как коллаж из уменьшенных копий его самого. Увеличивая такое изображение, мы будем наблюдать одну и ту же степень детализации независимо от разрешения. Это позволяет моделировать рост кристаллов, образование «вязких языков» на границе двух жидкостей, и тому подобные структуры обладающие глобальным самоподобием.

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

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

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

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

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

Поставленная цель определила следующие основные задачи исследования:

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

2. Разработка и исследование алгоритмов сокращения вычислительной сложности фрактального анализа на основе сокращения вычислительной сложности отдельных этапов алгоритма.

3. Разработка нового алгоритма фрактального анализа, реализующего разработанные алгоритмы сокращения вычислительной сложности.

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

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

Фурье, теории анализа алгоритма, теория матриц и математическая статистика.

Научная новизна работы заключается в следующих разработанных алгоритмах сокращения вычислительной сложности фрактального анализа:

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

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

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

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

5. Алгоритм быстрого построения аттрактора на основе применения «Игры Хаоса». В этом случае получают стохастический алгоритм построения фрактала.

Практическая ценность результатов работы заключается в следующем:

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

2. Разработанная программа, реализующая новый фрактальный алгоритм, позволяет выполнять фрактальный анализ изображения в 30 -40 раз быстрее по сравнению с известными аналогами.

3. Результаты диссертационной работы были использованы при решении задач анализа подводных изображений в проектно-конструкторской деятельности Института проблем морских технологий ДВО РАН, а также в учебном процессе в Хабаровского Института Инфокоммуникации (ХФ СибГУТИ).

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

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

2. Алгоритм установления факта аффинного подобия между элементами изображения на базе свойств ядра ортогонального преобразования на примере ДКП.

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

4. Алгоритм быстрого построения аттрактора на основе применения «Игры Хаоса».

5. Быстрый алгоритм фрактального анализа и результаты его исследования в системах обработки визуальных данных.

Апробация результатов работы.

Основные положения диссертационной работы были представлены на следующих НТК: Телевидение: передача и обработка изображений. Материалы 4-й международной конференции, Санкт-Петербург, 24-26 мая 2005; IEEE International Siberian Conference on Control and Communication (SIB-CON-2005). Proceedings, Tomsk, Russia, October 21-22, 2005; Proceeding of The KOREA - RUSSIA Joint - Workshop 2006 on Signal Transmission, Processing, Sensor and Monitoring Systems, Khabarovsk, Russia, October 26-28, 2006; Материалы Седьмой Всероссийской научно-технической конференции, Улан-Удэ, 24-30 июля 2006; Материалы всероссийской научной конференции молодых ученых, Новосибирск, 07-10 декабря 2006 г.; Конкурс научных работ молодых ученых в области физики, математики и информационных технологий, Тихоокеанский государственный университет, 10 декабря 2007 года; X краевой конкурс молодых ученых в области физико-математических наук, 20 января 2008 года.

Публикации н личный вклад автора.

Основное содержание диссертационной работы отражено в 6 печатных работах, в том числе: 2 статьи, 3 доклада на конференциях и JL свидетельство об официальной регистрации программы для ЭВМ. 5 работ опубликованы автором без соавторства, в том числе одна статья в издании, рекомендованном ВАК.

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

Структура и объем диссертации.

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

ЗАКЛЮЧЕНИЕ

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

В результате выполненной работы получены следующие основные теоретические и экспериментальные результаты:

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

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

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

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

5. Реализована схема установления оптимального аффинного преобразования на основе периодичного закона распределения знаков коэффициентов ДКП. Алгоритм выбора оптимального аффинного преобразования без перебора всех восьми преобразований позволяет достичь сокращения времени работы равным около 8 раз.

6. Экспериментальное исследование быстродействия нового алгоритма фрактального анализа в системах обработки изображений по сравнению с базовым алгоритмом Фишера показало, что применение новых алгоритмов сокращения вычислительной сложности позволяет повысить скорость фрактального анализа от 30 до 40 раз.

7. Разработан новый алгоритм синтеза-декодирования аттрактора фрактала на основе «детерминированного хаоса». В новом алгоритме достигается сокращение времени на 30%, по сравнению с распространенным детерминированным алгоритмом.

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

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

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

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

1. Цифровая обработка телевизионных и компьютерных изображений / Под ред. Ю. Б. Зубарева, В. П. Дворковича. М., 1997. - 216 с.

2. Александров П. С. Введение в теорию множеств и общую топологию / П. С. Александров. 2-е изд., стереотипное. - М.: Едиториал УРСС, 2004.-368 с.

3. Алимов Ш. А. Принцип сжатых отображений (Методы прикладного анализа) /Ш. А. Алимов. М.: Знание, 1983. - 64 с.

4. Бондаренко В. А., Дольников В. Л. Фрактальное сжатие изображений по Барнсли-Слоану / В. А. Бондаренко, В. Л. Дольников. // Автоматика и телемеханика. 1994. - №5. - С. 12-20.

5. Barnsley М. Fractals Everything / М. Barnsley. Academic Press, San Diego, 1988. - 160 p.

6. Barnsley M., Hurd L. Fractal Image Compression / M. Barnsley, L. Hurd. -AK Peters, Wellesley, 1993. 237 p.

7. Forte В., Vrscay E. R. Theory of Generalized Fractal Transforms / B. Forte, E. R. Vrscay // Technical Report 1834, Naval Ocean Systems Center. San Diego, March 11, 1996. - P. 227-235.

8. Forte В., Vrscay E. R. Inverse Problem Methods for Generalized Fractal Transforms / B. Forte, E. R. Vrscay // Technical Report 1834, Naval Ocean Systems Center. San Diego, March 11,1996. - P. 127-132.

9. Vrscay E. R. From Fractal Image Compression to Fractal-based Methods in Mathematics / E. R. Vrscay // Can. J. Elect. Сотр. Eng. 23, 1998. - No. 1-2.-P. 69-84.

10. Табор M. Хаос и интегрируемость в нелинейной динамике / М. Табор Пер. с англ. М.: Эдиториал УРСС, 2001. - 320 с.

11. Морозов А.Д. Введение в теорию фракталов / А.Д. Морозов. Москва-Ижевск: Институт компьютерных исследований, 2004. - 160 с.

12. Шредер М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая / М. Шредер. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2005. - 528 с.

13. Jacquin А. Е. "Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformation" / A. E. Jacquin // IEEE Trans, on Image Proc. -1996-Vol. 1, № 1. P. 18-30.

14. Jacquin A. E. Fractal image coding: A review / A. E. Jacquin // Proceeding of the IEEE 81,10. 1993. - P. 1451-1465.

15. Davis G. Implicit Image Models in Fractal Image Compression / G. Davis // Proc. of SPIE Conf. on Wavelet Applications in Signal and Image Processing IV. Denver, 1996. - P. 973-984.

16. Шабаршин А. А. Метод фрактального сжатия изображений / А. А. Ша-баршин // Научные школы УПИ-УГТУ, 1997. №1. - С. 70-82.

17. Dietmar Saupe, Raouf Hamzaoui, Hannes Hartenstein Fractal Image Compression. An Introductory Overview / S. Dietmar, H. Raouf, H. Hannes. -IEEE Computer Society Press, 1997. 472 p.

18. Ватолин Д., Ратушняк А., Смирнов M. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. / Д. Ватолин, А. Ратушняк, М. Смирнов. -М.: ДИАЛОГ-МИФИ, 2003. 384 с.

19. Wilson D. Fractal image compression / D. Wilson // Technical Report, Imperial College of Science, Technology & Medicine. University of London, 1988.-P. 572-583.

20. Davoine F., Bertin E., Chassery J.-M. An adaptive partition for fractal image coding / F. Davoine, E. Bertin, J.-M. Chassery // in NATO ASI Conf. Fractal Image Encoding and Analysis. Trondheim, July, 1995. - P. 238-257.

21. Boss R. D. Fractal-based image compression / R.D. Boss // Technical Report 1315, Naval Ocean Systems Center. San Diego, Sept. 1989. - P. 347-378.

22. Fisher F. Fractal Image Compression / F. Fisher. New York:Springer-Verlag, 1995.-483p.

23. Blanc-Talon J., Amram E. Recursive Histograms Comparison for Acceleration Fractal Image Compression, In International Conference on Image Processing / J. Blanc-Talon, E. Amram // Lansann. September, 1996. - P. 376-383.

24. Au О. C., Liou M. L., Ma L. K. Fast Fractal Encoding in Frequency Domain / О. C. Au, M. L. Liou, L. K. Ma // Image Communication. March, 1996. -Vol. 3.-P. 73-78.

25. Barthel K. U., Voye T. Adaptive Fractal Image Coding in the Frequency Domain / K. U. Barthel, T. Voye // Fractal Image Compression, Proc. NATO Advanced Study Institute Conf. on Fractal Image Encoding and Analysis. -Trondheim, April, 1998. P. 65-73.

26. Asgori S., Nguycu T. Q. Wavelet-Based Fractal Transforms for Image coding with no Search / S. Asgori, T. Q. Nguycu // PhD Thesis, University of Wisconsin-Madison. Wisconsin, May, 1997. - P. 75-81.

27. Barthel K. U., Voye T. Combining Wavelet and Fractal for 3-D Video coding / K. U. Barthel, T. Voye // PhD Thesis, Technical Universitat Berlin. -September, 1998. P. 84-97.

28. Barthel K., Brandau S. Zero tree Wavelet Coding Using Fractal Prediction / K. Barthel, S. Brandau // PhD Thesis, Technical Universitat Berlin. March, 1995.-P. 247-259.

29. Caso G., Kuo C.-C.J. Multiresolution analysis of fractal image compression / G. Caso, C.-C.J. Kuo // in NATO ASI Conf. Fractal Image Encoding and Analysis. Trondheim, July, 1995. - P. 166-178.

30. Roche S. J.-L., Dugelay R. Multi-resolution access control algorithm based on fractal coding / S. J.-L. Roche, R. Dugelay // PhD Thesis, Institut EURE-COM. May, 1996. - P. 325-338.

31. Axel van de Walle. Merging Fractal Image Compression and Wavelet Transform Methods / Axel van de Walle // Electronics Letters, 41. 1996. - P. 573-596.

32. Hartenstein H. Lossless fractal image compression by fast convolution / H. Hartenstein //Electronics Letters, 28. 1993. - P. 256-278.

33. Zeng W., Daly S., Lei S. An overview of the visual optimization tools in JPEG 2000 / W. Zeng, S. Daly, S. Lei // Signal Processing Image Communication 17, 2002. P. 163-179.

34. Breazu M., Toderean G. Region-Based Fractal Image Compression Using Deterministic Search / M. Breazu, G. Toderean // In Proc. of IEEE Transactions on Image Processing. February, 1996 - № 2. - P. 158-171.

35. Chasseiy J-M., Davoine F. Compression fractal partition by de Delaunay / J-M. Chassery, F. Davoine // In Proceedings ICIP-97 (IEEE International Conference on Image Processing). Lausanne, Switzerland. - September, 1997. - Vol. 2.-P. 125-132,

36. M. Ruhl and W. Pearlman. 1997. Optimal Fractal Coding Is NP-hard / M. Ruhl and W. Pearlman. // Proc. DCC'97 Data Compression Conference. -IEEE Computer Society Press. P. 261-270.

37. Прэтт У. Цифровая обработка изображений: В 2 кн. Кн. 2. / У. Прэтг. -М.: Мир, 1982.-480 с.

38. Прэтг У. Цифровая обработка изображений: В 2 кн. Кн. 1. / У. Прэтт. -М.: Мир, 1982- 312 с.

39. Шлихт Г. Ю. Цифровая обработка цветных изображений / Г. Ю. Шлихт. М.: ЭКОМ, 1997. - 336 с.

40. Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов / Д. Даджион, Р. Мерсеро. М.:Мир, 1988. - 488 с.

41. Hamzaoui R. Codebook Clustering by Self-Organizing Maps for Fractal Image Compression / R. Hamzaoui // Proc. NATO Advanced Study Institute

42. Conf. on Fractal Image Encoding and Analysis. Trondheim, July, 1995. -P.179-192.

43. Bogdan A., Meadows H. E. Kohonen neural network for image coding based on iteration transformation theory. / A. Bogdan, H. E. Meadows // Proc. ICIP-93 IEEE International Conference an Image Processing. Washington, D.C., 1993. - P. 378-393.

44. Kohonen T. The self-organizing map. / T. Kohonen // IEEE Proc. September, 1990. - Vol. 78. - P. 1443-1464.

45. Vences L., Rudomin Is. Fractal Compression of Single Images and Images Sequences using Genetic Algorithms / L. Vences, Is. Rudomin // IEEE Electronic Letters. -21st May, 1993. -№ 11. p. 378-392.

46. Wohlberg В. E., de Jager G. Fast image domain fractal compression by DCT domain block matching / В. E. Wohlberg, G. de Jager // Electronics Letters, 31.-1995.-P. 869-870.

47. Zhao Y., Yuan B. Image compression using fractals and discrete cosine transform / Y. Zhao, B. Yuan // Electronics Letters, 30. 1994. - P. 474475.

48. Zhang N., Yan B. Hybrid image compression method based on fractal geometry / N. Zhang, B. Yan // Electronics Letters, 30. 1994. - P. 406^108.

49. Шабаршин A.A. Трёхмерное фрактальное сжатие видеоинформации / А.А. Шабаршин // Научные школы УПИ-УГТУ, 1997. №1. - С. 83-89.

50. Kominek J. Algorithm for fast fractal image compression / J. Kominek // in Proceedings from ISBT/SPIE 1995 Symposium on Electronic Imaging: Science & Technology. Digital Video Compression: Algorithms and Technologies, 1995. - Vol. 2419. - P. 547-563.

51. Lepsey S., Oien G. E. Fast attractor image encoding / S. Lepsey, G. E. Oien // Fractal Image Compression: Theory and Application. Springer-Verlag, New York, 1994. - P. 174-203.

52. Bethel D. M., and Monro D. M. Optimum Parent Pruning in Fractal Compression / D. M. Bethel, and D. M. Monro // In Proceedings PCS'92 (International Picture Coding Symposium). Lausanne, Switzerland, March, 1992.-P. 46-68.

53. Hannah S. J., Jackson D. J. A hybrid fractal-LZW encoding technique for lossless image compression / S. J. Hannah, D. J. Jackson // in: Proceedings of the Thirty-Second Annual ACM Southeast Conference. March 17-18, 1994.-P. 233-240.

54. Dettmer R. Form and function Fractal based compression / R. Dettmer // IEE Review 38. - 1992. - P. 323-327.

55. Dony R. D., Vrseay E. R. IFS coding using an MPC network library / R. D. Dony, E. R. Vrseay // Can. J. Elect. Сотр. Eng. -1998. Vol. 23. - P. 227249.

56. Dudbridge F. Fast image coding by a hierarchical fractal construction / F. Dudbridge. Preprint, 1994. - 275 p.

57. Lin H. Fast pyramid search for perceptually lossless fractal image compression / H. Lin // Proc. ICIP-96 IEEE International Conference on Image Processing. Lausanne, September, 1996. - P. 372-405.

58. Saupe D. Fractal image compression via nearest neighbor search / D. Saupe // Proceeding DCC95 Data Compression Conference, J. A. Storer and M. Cohn (eds.). IEEE Сотр. Soc Press, March, 1995. - P. 179-209.

59. Wall L., Kinsner W. A fractal block coding technique employing frequency sensitive competitive learning / L. Wall, W. Kinsner // Proc. of IEEE Communications. Computers and Power, 1993. - P. 320-329.

60. Withers W. D. Newton's method for fractal approximation / W. D. Withers // Constructive Approximation, 5. 1989. -P.l 51-179.

61. Jackson D. J., Blom T. A parallel fractal image compression algorithm for hypercube multiprocessors / D. J. Jackson, T. Blom // Proceedings of the Thirty-Second Southeastern Symposium on System Theory. March 12-14, 1994.-P. 274-278.

62. Dedera L. A Parallel Approach to Image Decoding in the Fractal Image Block Coding Scheme / L. Dedera // PhD Thesis. Military Academy, 1996. - P. 337-368.

63. Barthel K. U., Voye T. Three dimensional fractal video coding / K. U. Barthel, T. Voye // Proc. ICIP-95 IEEE International Conference an Image Processing. - Washington, D.C., 1995. - P. 274-278.

64. Barakat M., Dugelay J.-L. Image sequence coding using 3-D I.F.S. / M. Ba-rakat, J.-L. Dugelay // Proc. ICIP-96 IEEE International Conference an Image Processing. Lausanne, Sept. 1996. - P. 69-105.

65. Dugelay J.-L., Sadoul J.-M., Barakat M. Moving picture fractal compression using I.F.S. A review / J.-L. Dugelay, J.-M. Sadoul, M. Barakat - Internal Report RR-95-018. - Eurecom, France, 1995. - 245 p.

66. Fu K. W., An О. C., Lion M. L. Very low bit rate fractal video coding by genetic algorithm / K. W. Fu, О. C. An, M. L. Lion // Proc. of 2nd TASTED/rSMM Int. Conf. on Distributed Multimedia Systems and Applications. Stanford, Aug. 1995. - P. 189-205.

67. Mazel D. S. Fractal Modeling of Time-Series Data / D. S. Mazel // PhD Thesis. Georgia Institute of Technology, 1991. - P. 129-143.

68. Saupe D., Hamzaoui R. A Guided Tour of the Fractal Image Compression Literature / D. Saupe, R. Hamzaoui // PhD Thesis. Universitat Freiburg, July, 1998. - 157 p.

69. Wohlderg В. E., de Jager G. On reduction of fractal image compression encoding time / В. E. Wohlderg, G. de Jager // PhD Thesis. University of Cape Town, May, 1992. - P. 157-179.

70. Bani-Eqbal B. Enhancing the speed of fractal image compression / B. Bani-Eqbal // Optical Engineering, 34(6). June, 1995. - P. 1705-1710.

71. Bani-Eqbal В. Speeding up fractal image compression, In Rabbani, M., Delp, E., J., and Raiala, S., A., editors, Still-Image Compression, Volume 2418 of SPIE Proceedings. San Jose, CA, USA, February, 1995. - P. 6774.

72. Barthel K. U., Voye T. and Noll P. Improved fractal image coding / K. U. Barthel, T. Voye and P. Noll // Proceedings PCS^93 (International Picture Coding Symposium). Lausanne, Switzerland, March, 1993. - P. 153-178.

73. Saupe D., Hamzaoui R. Complexity Reduction Methods for Fractal Image Compression / D. Saupe, R. Hamzaoui // Proceedings ICIP-97 (IEEE International Conference on Image Processing). Lausanne, Switzerland, September, 1997. - Vol. 2. - P. 163-167.

74. Davone F., Bertin E., Chassery J.-M. From rigidity to adaptive tessellations for fractal image compression: comparative studies / F. Davone, E. Bertin, J.-M. Chasseiy // Traitement du Signal. 1997. - №. 3. - P. 155-164.

75. Davone F., Chassery J.-M. Adaptive Delaunay Triangulation for Attractor Image Coding / F. Davone, J.-M. Chassery // Optical Engineering, 47. -June, 1996.-P. 1407-1411.

76. Денисенко A. H. Сигналы. Теоретическая радиотехника: справочное пособие / А. Н. Денисенко. -М.: Телеком, 2005. 704 с.

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

78. Трахтман А. М. Введение в обобщенную спектральную теорию сигналов / А. М. Трахтман. М.: Сов. Радио, 1972. - 257 с.

79. Saupe D. The Futility of Square Isometries in Fractal age Compression / D. Saupe // IEEE International Conference on Image Processing (IdP'96). -Lausanne, 1996. P. 368-392.

80. Ватолин Д. С. Алгоритмы сжатия изображений / Д. С. Ватолин. М.: Диалог-МГУ, 1999.-273 с.

81. Oien G. Е. Optimal Attractor Image Coding with Fast Decoder Convergence / G. E. Oien // PhD Thesis. The Norwegian Institute of Technology. -Trondheim, Norway, April, 1993. - P. 241-257.

82. Skarbek W. On Convergence of Affine Fractal Operators / Skarbek W. // Image Processing and Communications. 1993. - № 1. - P. 33-41.

83. Kominek J. Convergence of Fractal Encoded Image / J. Kominek // PhD Thesis. University of Waterloo. - Ontario, Canada, 1994. - P. 128-167.

84. Kim Ch-S., Kim R-Ch., Lee S-Uk. Novel fractal image compression method with non-iterative decoder / Ch-S. Kim, R-Ch. Kim, S-Uk. Lee // PhD Thesis. Seoul National University. - Seoul, 1995. - P. 35-57.

85. Htirtgen В., Simon S. F. On the problem of convergence in fractal coding schemes / B. Htirtgen, S. F. Simon // First IEEE International Conference on Image Processing ICIF94. Austin, Texas, USA. - Nov. 13 - 16, 1994. -P. 294-317.

86. Htirtgen B. Statistical evaluation of fractal coding schemes / B. Htirtgen // IEEE International Conference on Image Processing IdPx95. Washington, DC, USA. - Oct. 22 - 25,1995. - P. 172-195.

87. Hamzaoui R. Ordered decoding algorithm for fractal image compression / R. Hamzaoui // Technical Report 86, Institut fur Informatik, University of Freiburg. March, 1997. - P. 12-17.

88. Hamzaoui R., A new decoding algorithm for fractal image compression / R. Hamzaoui//Electronic letters, 32. 1996. - P. 1273-1274.

89. Линдли К. Практическая обработка изображений на языке Си. / К. Линдли. М.: Мир, 1996. - 560 с.

90. Шамис В. A. C-H-Builder 5. Техника визуального программирования. / В. А. Шамис. -М.: Нолидж., 2001. 248 с.

91. Шеферд Дж. Программирование на Microsoft Visual С++ .NET / Дж. Шеферд, Пер. с англ. М.: «Русская редакция», 2003. - 928 е.: ил.

92. Mannos J. L., Sakrison D. J. The Effects of a Visual Fidelity Criterion on the Encoding of Images/ J. L. Mannos, D. J. Sakrison // IEEE Trans. Inf. Theory, IT-20. July, 1974. - P. 573-592.

93. Сай С. В. Четкость цветного изображения в системах со сжатием визуальных данных. / С. В. Сай. Хабаровск: Изд-во Хабар, гос. техн. унта., 1999. -143 с.

94. Сай С. В. Анализ четкости цветных статических изображений в равно-контрастной системе координат / С. В. Сай // Цифровая обработка сигналов. 2002. - №1. - С. 175-186.

95. Сай С. В. Анализатор качества цветных изображений / С. В. Сай / Теоретические и прикладные вопросы современных информационных технологий // Труды 3-й Всероссийской научно-технической конференции. Улан-Удэ. - Август 01-04, 2002. - С. 257-278.

96. Сай С. В., Савенков И. В. Эффективность цифрового кодирования статических изображений методом вейвлет-преобразования / С. В. Сай, И. В. Савенков // Телекоммуникации. 2001. - № 4. - С. 12-18.1. Список публикаций автора

97. Сай С. В., Перегуда Е. С. Методы сокращения объема вычислений в алгоритмах фрактального сжатия изображений / С. В. Сай, Е. С. Перегуда // Вестник Тихоокеанского Государственного Университета. -2006.-№1.-С. 9-14.

98. Перегуда Е. С. Методы ускорения фрактального сжатия изображения / Е. С. Перегуда И НАУКА. ТЕХНОЛОГИИ. ИННОВАЦИИ // Материалы всероссийской научной конференции молодых ученых в 7-ми частях. Новосибирск: Изд-во НГТУ, 2006. Часть 1. С. 186-187.

99. Перегуда Е. С. Ускорение фрактального алгоритма в системах сжатия и передачи изображений / Е. С. Перегуда // Телекоммуникации 2007. — №6. - С. 2-7.