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

• Автор: Перегуда, Евгений Станиславович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Хабаровск
• Количество страниц: 158 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

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

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

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

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

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

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

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. Исследование свойства масштабирования алгоритма фрактального анализа
Выводы.
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Личный вклад автора в публикациях заключается в исследовании фрактального алгоритма, разработки методов сокращения сложности алгоритма и их реализации в виде программного обеспечения. Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 0 наименований, и _2_ приложений. Основная часть работы изложена на 5 страницах машинописного текста и содержит рисунок и _3_ таблицы. Визуальные данные могут быть представлены как множество точек в некотором пространстве X. Таким образом, монохромное изображение может быть рассмотрено как множество элементов в пространстве X - Я2, где II -множество целых действительных чисел. Изображение в градациях яркости в этом случае является множеством элементов в пространстве X = К В этом случае элементы являются точками на поверхности в пространстве Л3 [1]. Основой рассматриваемой системы анализа является создание динамической системы проекций IV, которые проецируют точки из множества X на другие точки в этом же множестве X. Пространство X имеет метрик}' с1(х,у) - функция расстояния между двумя любыми точками в пространстве X. Г:Х->Х. Метрика пространства является фундаментальным понятием при фрактальном анализе. Пространство X может быть пространством компактного множества Я2 (для случая монохромных изображений) или пространством компактного множества Я3 (изображения в градациях яркости). В данном пространстве любая последовательность сходится к точке в данном пространстве. Более того, X может также быть выбрано как пространство функций, определенных на единичном квадрате, или пространство функций, определенных на единичном интервале, в зависимости от размерности пространства. Сжимающая проекция является проекцией, которая перемещает любые две соседние точки в пространстве X ближе друг к другу, чем было до применения данной проекции. Свойства сжимающего преобразования описываются теоремой о неподвижной точке [3]. Реализацией выражения (1. Барнсли (Barnsley) [4, 5, 6, 7] система итерированных функций. Wi имеет сжатие -у,. Если определить множество В&Н(х) в пространстве X с метрикой Хаусдорфа, тогда это множест во проецируется через к,- на другое множество /? Таким образом, IFS вызывает преобразование W от Н(х) к Н{х). Jw{b). Преобразование W(. Хаус-дорфа на пространствеН(х) со сжатием s, где s = max{s,}. Тогда можно сказать, что IFS имеет сжатие s. W(A)= А. Эта фиксированная точка и является аттрактором IFS. YimW(n){B)= А. Таким образом, если мы в начале берем любое компактное подмножество X и применяем к нему итеративно преобразование Ж, то, в конце концов, оно сходится к аттрактору IFS. Это можно рассматривать как-то, что информация об аттракторе заключается в преобразовании IFS. На основе сходимости преобразования 1FS к аттрактору выводится теорема о коллаже. А состоит из объединений уменьшенных копий самого себя. Поэтому W(A) называют коллажом, покрывающим А. Теорема коллажа имеет следующий вид. Определим / как изображение (более строго, как точку в пространствеX ). Определил! А и преобразованием fVQ, которое определяет IFS, и если Щ. A,f)<~-d(w(f),f). Это неравенство устанавливает, что если можно найти множество преобразований, которые приводят к коллажу, достаточно близкому к оригинальному изображению, то тогда аттрактор полученного преобразования IFS будет также близок к закодированному изображению. Это и есть главное условие, которое определяет простую задачу для поиска хорошего коллажа из множества проекций {»vX,, которые необходимо рассчитать для каждого изменения в выбранной проекции [8, 9]. Таким образом, определяется условие поиска оптимума для задачи фрактальной обработки изображения. Очевидно, что при условии сжимаемости преобразования выбор конкретного преобразования достаточно велик []. Но выбор преобразования для практического применения должен также основываться на простоте и эффективности реализации. Чаще всего на практике предлагается использовать аффинные преобразования. Аффинные преобразования могут осуществлять поворот, перемещение и масштабирование [, ].