Содержание к диссертации
Введение
1. Алгоритмы фрактального анализа в задачах обработки визуальных данных 9
1.1. Математический базис фрактального анализа визуальных данных 9
1.2. Фрактальный анализ визуальных данных в градациях яркости
1.2.1. Расширение фрактального кодирования 14
1.2.2. Операторная схема PIFS 17
1.2.3. Существующие алгоритмы фрактального анализа визуальных данных 21
1.3. Обоснование выбора базового алгоритма 42
1.4. Применение фрактального анализа в широком спектре задач 44
Выводы 48
2. Алгоритмы сокращения вычислительной сложности фрактального алгоритма 49
2.1. Алгоритм сокращения вычислительной сложности расчета метрического расстояния 49
2.2. Алгоритм сокращения вычислительной сложности расчета аффинных преобразований 56
2.3. Алгоритм сокращения вычислительной сложности перебора аффинных преобразований 66
2.4. Анализ алгоритма фрактального декодирования 69
2.4.1. Детерминированный алгоритм 70
2.4.2. Алгоритм на основе «Игры Хаоса» 72
Выводы 77
3. Разработка улучшенного алгоритма фрактального анализа визуальных данных 79
3.1. Разработка структурной схемы улучшенного алгоритма фрактального анализа визуальных данных 79
3.2. Этап предобработки данных 86
3.3. Расчет метрики отклонения
3.3.1. Оценка подобия на основе сравнения четных коэффициентов ДКП 90
3.3.2. Выбор оптимального аффинного преобразования на основе знакового распределения коэффициентов ДКП 93
3.3.3. Расчет метрики отклонения домена и ранга
на основе нормированных коэффициентов ДКП 95
3.4. Новый алгоритм синтеза-декодирования аттрактора 97
Выводы 100
4. Экспериментальные исследования разработанных алгоритмов сокращения вычислительной сложности фрактального анализа 101
4.1. Интерфейс программы фрактального анализа изображения 101
4.2. Статистические исследования алгоритма Фишера 105
4.3. Статистические исследования работы программы 110
4.4. Оценка степени сжатия нового алгоритма фрактального анализа... 117
4.5. Исследование сходимости изображения к аттрактору 122
4.6. Исследование свойства масштабирования алгоритма фрактального анализа 126
Выводы 129
Заключение 131
Список литературы
- Расширение фрактального кодирования
- Алгоритм сокращения вычислительной сложности перебора аффинных преобразований
- Расчет метрики отклонения
- Статистические исследования алгоритма Фишера
Введение к работе
Актуальность темы
Основные объекты фрактальной геометрии – фракталы – находят применение в компьютерном дизайне, в моделировании сложных нелинейных динамических процессов, в алгоритмах обработки информации и тому подобных задачах.
Применение фрактального анализа в обработке визуальных данных считается одной из перспективных областей применения фрактальной геометрии. При этом целое изображение рассматривают как коллаж из уменьшенных копий его самого. Увеличивая такое изображение, мы будем наблюдать одну и ту же степень детализации независимо от разрешения. Это позволяет моделировать рост кристаллов, образование «вязких языков» на границе двух жидкостей, и тому подобные структуры, обладающие глобальным самоподобием.
В последние два десятилетия крупнейшие научно-исследовательские организации по всему миру проводят активные теоретические и практические исследования фрактальных алгоритмов анализа и синтеза информации, но значительная вычислительная сложность фрактальных алгоритмов ограничивает широкое распространение результатов исследований.
Большую ценность представляют алгоритмы фрактального анализа, способные работать в режиме реального времени, однако большинство известных алгоритмов фрактального анализа требуют много времени для обработки визуальных данных. Ценность быстрого алгоритма фрактального анализа заключается в возможности выполнять его на персональных ЭВМ рядовых пользователей. Это позволит широко распространить фрактальные алгоритмы сжатия аудио, видео и статических изображений, способных сделать революцию в области мультимедиа.
Таким образом, разработка методов и алгоритмов фрактального анализа, способных обрабатывать данные за короткий промежуток времени с высоким качеством, является актуальной задачей и имеет как научный интерес, так и экономические перспективы.
Цель работы – исследование и разработка алгоритмов сокращения вычислительной сложности фрактального анализа в системах обработки визуальных данных, разработка нового алгоритма фрактального анализа и его практическая реализация.
Поставленная цель определила следующие основные задачи исследования:
-
Оценка сложности фрактального анализа на основе существующего алгоритма и математическое представление этапов анализа, имеющих наибольшую вычислительную сложность.
-
Разработка и исследование алгоритмов сокращения вычислительной сложности фрактального анализа на основе сокращения вычислительной сложности отдельных этапов алгоритма.
-
Разработка алгоритма фрактального анализа, реализующего разработанные алгоритмы сокращения вычислительной сложности.
-
Разработка программного обеспечения, реализующего разработанный алгоритм фрактального анализа и исследование его работы.
Методы исследования. Для решения поставленных задач были использованы как экспериментальные, так и теоретические методы исследования. В работе использованы методы теории фракталов, теории ортогональных рядов Фурье, теории анализа алгоритма, теория матриц и математическая статистика.
Научная новизна работы заключается в следующих разработанных алгоритмах сокращения вычислительной сложности фрактального анализа:
-
Алгоритм сокращения сложности фрактального анализа на основе применения операций ортогонализации и нормирования векторов к задаче расчета метрики отклонения двух областей изображения. Данный алгоритм позволяет сократить количество выполняемых математических операций в два раза.
-
Упрощенный алгоритм расчета масштабирующего коэффициента яркости, позволяющий исключить операцию свертки при расчете квадратичного приближения. Данный алгоритм позволяет сократить количество выполняемых математических операций в два раза.
-
Алгоритм сокращения сложности фрактального анализа на основе свойства инвариантности коэффициентов дискретно-косинусного преобразования (ДКП) всех восьми изометрических аффинных преобразований. При этом сравниваются коэффициенты, идентичные для всех восьми преобразований. Данное решение позволяет сократить количество выполняемых математических операций в восемь раз.
-
Алгоритм установления оптимального аффинного преобразования на основе периодичного закона распределения знаков коэффициентов ДКП с использованием свойств четности коэффициентов ДКП, позволяющий уменьшить количество операций сравнения. Данное решение позволяет сократить количество выполняемых математических операций в два раза.
-
Алгоритм быстрого построения аттрактора на основе применения «Игры Хаоса». В этом случае получают стохастический алгоритм построения фрактала.
Практическая ценность результатов работы заключается в следующем:
-
Разработанные алгоритмы установления факта подобия между отдельными элементами изображения, базирующиеся на свойстве ортогональности рядов Фурье и свойств четности ядра ДКП, представляют практическую ценность не только для задач фрактального анализа изображения, но и для различных задач распознавания.
-
Разработанная программа, реализующая новый фрактальный алгоритм, позволяет выполнить фрактальный анализ изображения в 30-40 раз быстрее по сравнению с известными аналогами.
-
Результаты диссертационной работы были использованы при решении задач анализа подводных изображений в проектно-конструкторской деятельности Института проблем морских технологий ДВО РАН, а также в учебном процессе Хабаровского института инфокоммуникации (ХФ СибГУТИ).
На защиту выносятся:
-
Алгоритм нормирования выражения подобия исходного изображения и фрактальной аппроксимации в ортогональном пространстве, основанный на работе с метрическим значением вектора.
-
Алгоритм установления факта аффинного подобия между элементами изображения на базе свойств ядра ортогонального преобразования на примере ДКП.
-
Алгоритм выбора оптимального изометрического аффинного преобразования, базирующийся на свойстве четности ядра ДКП, позволяющий сделать данный выбор на основе битового сравнения знаков коэффициентов ДКП.
-
Алгоритм быстрого построения аттрактора на основе применения «Игры Хаоса».
-
Быстрый алгоритм фрактального анализа и результаты его исследования в системах обработки визуальных данных.
Апробация результатов работы
Основные положения диссертационной работы были представлены на следующих НТК: Телевидение: передача и обработка изображений. Материалы 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 г., Х конкурс – конференция молодых ученых Хабаровского края, 8 февраля 2008 г.
Публикации и личный вклад автора
Основное содержание диссертационной работы отражено в 6 печатных работах, в том числе: 2 статьи, 3 доклада на конференциях и 1 свидетельство об официальной регистрации программы для ЭВМ. Пять работ опубликованы автором без соавторства, в том числе одна статья в издании, рекомендованном ВАК.
Личный вклад автора в публикациях заключается в исследовании фрактального алгоритма, разработке методов сокращения сложности алгоритма и их реализации в виде программного обеспечения.
Структура и объем диссертации
Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 110 наименований, и 2 приложений. Основная часть работы изложена на 145 страницах машинописного текста и содержит 51 рисунок и 3 таблицы.
Расширение фрактального кодирования
Данные пять характеристик формирую единый вектор свойств блока изображения. При анализе подобия необходимо найти метрику пространства свойств домена и ранга: d = hfrbYfJu\, м гДе /г[/] - этоу-я характеристика для рангового блока, fd\j] - этоу -я характеристика для доменного блока и Nf - количество характеристик (в данном случае Nf=5). В случае если метрика пространства свойств составит менее некоторого заранее заданного предела, то выполняют попиксельное сравнение ранга с данным доменом. Если попиксельное сравнение дает погрешность меньшую допустимой, то этот ранговый блок считается покрытым данным доменом с требуемым качеством. Такое решение позволяет значительно уменьшить вычислительную сложность. Поиск в пространстве свойств является распространенным решением, на основе которого разработано множество алгоритмов. Следующим шагом в ускорении чаще всего рассматривают различные приемы кластеризации доменов в пространстве свойств. Наиболее распространенное решение базируется на использовании самоорганизующихся нейронных сетей [42, 43] на основе работ Тьюво Кохо-нена по имитации способности мозга самоорганизовываться в соответствии с внешними раздражителями. Этот алгоритм носит название самоорганизующейся карты свойств [44]. Алгоритм Кохонена представляет собой разновидность нейронной сети, способной обучаться. Нейронные сети такого вида называются самоорганизующимися нейронными сетями.
Самоорганизующиеся нейронные сети характеризуются многомерным массивом, или решеткой узлов. С каждым узлом решетки связан весовой вектор пространства свойств. Каждый узел решетки представляет класс доменных блоков, поэтому желательно, чтобы общее количество узлов оставалось достаточно небольшим. На основе заданного множества доменов текущего изображения обучается данная нейронная сеть, и формируются значения векторов в узлах кластеризации. После обучения сети доменные блоки для данного изображения классифицируются путем сопоставления каждому из них весового вектора, самого близкого к ним в пространстве свойств. Таким образом, каждый узел решетки теперь имеет весовой вектор и связанный с ним список доменных блоков. Этот список доменных блоков принадлежит «классу», сопоставленному этому весовому вектору. Класс - это, по определению, множество всех изображений, более близких в пространстве свойств к данному весовому вектору, чем к какому-либо другому вектору в решетке. Когда вектор характеристик рангового блока поступает в сеть, точно также сопоставляется весовой вектор сети. Затем ранговый блок сравнивается с доменами, которые сопоставлены данному весовому вектору пространства свойств, а также с доменами, сопоставленными весовым векторам из ближайшей окрестности данного весового вектора в сети. Далее отслеживают минимальную на данный момент разность между характеристиками. Если новый домен в списке обеспечивает меньшую разность, чем заранее установленный предел, то выполняется полное попиксельное доменно-ранговое сопоставление.
Рассмотренный алгоритм достаточно эффективен и показывает хорошие результаты по сравнению с алгоритмом прямого перебора (алгоритм Фише 31 pa). Данный результат говорит о том, что различные алгоритмы эвристического анализа на основе анализа пространства свойств весьма эффективны, но сами алгоритмы кластеризации, классификации и принятия решения нельзя назвать высокопроизводительными. Рассмотренная сеть Кохонена при обучении требует многократного итерационного расчета состояния узлов, поэтому при большом количестве доменов время обучения сети может быть значительным. Алгоритмы классификации, основанные на нечетких множествах [45] или генетических концепциях [46], также имеют итерационный характер. Кроме вопроса о времени работы алгоритмов кластеризации, возникает вопрос о возможности построения простой реализации алгоритмов на аппаратном уровне. При выборе алгоритма эвристического поиска необходимо разработать быстрый, не итеративный алгоритм с возможностью простой аппаратной реализации.
Наличие в настоящий момент большого числа программных и аппаратных реализаций стандарта JPEG наводит на мысль использовать в алгоритмах фрактального анализа изображения уже существующие алгоритмы и приемы. Одним из вариантов является использование дискретно-косинусного преобразования (ДКП) для ускорения расчетов, как было предложено в работах Wohlberg, В. Е., de Jager, G. [47]. В этом случае домены и ранги перед операцией поиска подвергают ДКП. При этом производится представление блоков изображения в спектральном виде как векторов. Коэффициенты спектра заполняют вектор при «зигзаг» сканировании коэффициентов. Благодаря распределению энергии по спектру в векторе формируется неоднородное распределение значений векторов с концентрацией энергии в младших индексах. Это означает, что медленно изменяющиеся структуры концентрируют энергию в младших индексах. При рассмотрении применения восьми аффинных преобразований к блокам изображения в пространстве ДЕСП данные операции выражаются в виде изменения знака коэффициентов и простом транспонировании. Наличие в векторе доменов и рангов отдельных областей, соответствующих распределению энергии структур разных размеров, позво 32 ляет производить поэтапный поиск подобия на основе сравнения отдельных коэффициентов с различными уровнями заметности. Данное решение аналогично алгоритмам бинарной сортировки и поиска в дереве данных. Таким образом, вектор хранит многомерный ключ. Структура, позволяющая реализовать данный поиск, носит название k-d дерева Время прохода в данной структуре - 0(Nlog2N) для N доменных блоков. Когда ключи поиска организованы в порядке «зигзаг» сканирования, наблюдается быстрый спад значений от наибольшего к наименьшему значению ключа, что позволяет ускорить алгоритм поиска.
Другие преимущества ДКП представления заключаются в том, что:
1) объем памяти, требуемой для каждого обработанного доменного блока, может быть уменьшен применением матрицы нормализации, после которой значение каждого компонента может быть представлено уменьшенным числом бит;
2) поскольку метрика расстояния, как известно, может быть субоптимальной, в связи с неравномерностью распределения энергии, применение матриц квантования, разработанных для стандарта JPEG, позволит отбросить часть коэффициентов при сохранении качества поиска;
3) так как контрастность и яркость разделены посредством ДКП, контрастность может быстро оценена без дополнительных расчетов;
4) изометрические аффинные преобразования могут быть быстро применены к коэффициентам ДКП домена, потребуется только умножение на ±1, что позволяет выполнять их на аппаратном уровне.
Алгоритм имеет прямое отношение к методу k-d дерева, но использует бинарный поиск в векторе многоразмерных ключей в словарном порядке. Коэффициент постоянной составляющей и номер аффинного преобразования хранятся с каждым множеством коэффициентов. Данный алгоритм требует прохода по узлам дерева поиска и, соответственно, многократного принятия решения на основе операции сравнения.
Алгоритм сокращения вычислительной сложности перебора аффинных преобразований
Метрика отклонения Е,(Ц \Л"_1 определяет точность покрытия ранга текущим доменом. При условии полного подобия значение метрики ШД "1, "1! равно нулю. Это означает полное совпадение всех структур блоков. Данный факт нужно рассматривать как частный случай. Очевидно, что данный случай должен быть отправной точкой при рассмотрении всех остальных случаев. Приравняв значение метрики Ei(pv",,.RAr "lJ к нулю, получим следующее выражение: (i j -1! (2.2) где 0 - вектор с нулевым значением всех составляющих коэффициентов. Значения векторов домена и ранга известны. Данное выражение можно рассматривать как систему линейных уравнений с одной неизвестной s. Для упрощения задачи рассмотрим представление векторов доменов и рангов в виде матрицы значений коэффициентов ортогональных преобразований. Данное упрощение позволяет ввести в выражение псевдообратную матрицу: Ё -\ЙМ-1)=5 3 -RN l O s-D 1 =RN l s = RN-lx(5 1}. (2.3) Введение в расчет псевдообратной матрицы позволяет рассматривать условие метрики в следующем виде: E,{Df-\RN-l]\=: RN-lx{D?-1} -6Г -RN l = 0. Данное тождество будет иметь смысл только при полном подобии домена и ранга. В остальных случаях метрика будет больше нуля. В случае полного подобия расчет коэффициента контрастности s имеет следующий вид: s = ІР-1 x (З?-1} = s x 1 = JP-1 x ( -I)", где 1 - единичная матрица. Смысл псевдообратной матрицы заключается в аппроксимации домена значением ранга, исходя из условия получения единичной матрицы. При постановке вопроса о практической реализации сложность расчета псевдообратной матрицы препятствует прямому использованию выражения (2.3). Но, приняв во внимание природу псевдообратной матрицы, можно найти более простую аппроксимирующую функцию, удовлетворяющую условию Д.(Д _\Я"-1 = 0. Простым решением является рассмотрение выражения (2.2) в виде системы линейных уравнений с одной неизвестной s: s-dl—rl =0; Исходя из условия полного подобия, получаем следующее выражение:
При поиске общего решения, которое включало бы данный частный случай, необходимо перейти к статистической аппроксимации. Самой простой и эффективной можно считать среднеквадратичную аппроксимацию на основе метрики рангового и доменного блока. В этом случае имеем следующее выражение: \N-\ s = Уг12+г22+... + #&.1 D: N-\ dl+d22+... + d2N_x Данное выражение определяет масштабируемость энергии рангового и доменного блока и является среднеквадратичным значением коэффициентов. Данная аппроксимация дает точное значение для частного случая s Д "1 = R"-1 = (s-dj +(s-d2f +...+(s-dN_J = Общее решение в этом случае имеет следующий вид: R D: N-l SM-l \\Е. D. D \{ ГЛ"-1\ N-l N-l Dr-R ,N-1 = \\R N-l f?N l R1 N-l raJV-l (2.4) Данное выражение можно упростить, если принять во внимание, что множитель метрики рангового блока їй "1! постоянен при переборе доменов Д"-1 и данный множитель можно исключить из расчетов. В итоге, выражение (2.4) принимает следующий вид: 1фГ1Л»-1] = Б? 1 \5»-1 R\ N-l R D N-l Дроби вида и ,, и ІГ=—й являются выражениями нормализации векторов Ipf- l \\RN 1\\ домена и ранга в нормированном метрическом пространстве и имеют обозначения ф\р? 1) и ф\Ё" ) соответственно. Выражение метрики отклонения имеет следующий вид: [д.(4 «"ІНН - І
Операция нормализации применяется к векторам доменных и ранговых блоков только один раз и в дальнейшем могут использоваться только их нормированные значения. Переход от значений векторов с различной магнитудои метрики к нормированным значениям с одинаковой единичной магнитудои позволяет вычеркнуть из расчетов сравнение общей контрастности и оставить только распределение энергии векторов по коэффициентам. На основе данного подхода частный случай с идентичностью ранговых и доменных блоков также выполняется, и метрика отклонения ІШД Л "! равна нулю.
С ростом отклонения значений коэффициентов векторов доменов и рангов значение метрики также увеличивается.
При реализации выражения (2.5) появляется возможность отказаться от одной операции умножения на коэффициент контрастности s и одной операции сложения с коэффициентом смещения яркости о. При этом появляется также возможность упростить расчет коэффициента контрастности s в связи с тем, что для его расчета достаточно произвести только одну операцию деления метрической меры рангового блока на метрическую меру доменного блока. В этом случае используются метрические значения, ранее рассчитанные для операции нормализации. Данная операция деления выполняется только один раз, так как аффинные преобразования, связанные с перестановкой элементов блоков, не влияют на значения метрики вектора. Данный факт позволяет отказаться от использования еще одной операции умножения и сложения в выражении (1.8), связанной со сверткой элементов домена с элементами ранга.
Последняя операция умножения, часто повторяемая при расчете метрики, требуется при расчете метрического значения вектора Щ\б? \RN . Расчет метрического значения требует выполнения одной операции умножения на коэффициент вектора я,(Д"-,д"- =Л/«о+в,2+...+4-1. Данное выражение рассчитывает метрику в Евклидовом пространстве, но не является единственно возможным. Оптимальным, с точки зрения сокращения сложности, является использование выражения расчета метрики на основе абсолютного значения коэффициентов векторов:
Расчет метрики отклонения
Как рассматривалось ранее в главе 2, свойство четности ДКП позволяет производить анализ подобия на основе сравнения части коэффициентов. Как было представлено раннее, четные коэффициенты не меняют ни знака, ни своих значений. Данное свойство является полезным при выборе из множества аффинных преобразований. Ряды коэффициентов ДКП являются монотонными и имеют медленную сходимость. Это свойство полезно, так как позволяет говорить, что локальная область в окрестности четного коэффициента изменяется медленно. Небольшое отклонение между четными коэффициентами доменов и рангов позволяет ожидать также небольшого отклонения и их локальных областей.
Алгоритм оценки подобия на основе сравнения четных коэффициентов ДКП представлен на рисунке 3.7. Расчет метрики отклонения доменов и рангов для четных коэффициентов ДКП Алгоритм базируется на рассмотренном принципе установления подобия - сравнении только четных коэффициентов. Т.о., выражение [ (D"-1, " ! можно представить в следующем виде:
Определив заданное качество отклонения как є достаточно один раз произвести сравнение четных коэффициентов и сохранить результат в отдельной переменной А: Если факт подобия установлен, то при нахождении подходящего аффинного преобразования можно исключить операции сравнения четных коэффициентов. В этом случае выражение (3.1) имеет следующий вид:
Если условие (3.1) не выполняется, то не имеет значения расчет нечетных коэффициентов, потому что он уже не сможет обеспечить заданное качество є, и подобие не устанавливается.
Расчет переменной А производится в блоке 2. Оценка качества, представленного неравенством (3.1), производится в блоке ветвления по условию 3. В случае выполнения данного условия алгоритм заканчивает работу в блоке 4, при этом управление передается блоку 6 на рис. 3.1. В случае, если условие (3.1) не выполняется, алгоритм заканчивает работу в блоке 5, управление передается блоку 9 на рис. 3.1.
При условии, что четные коэффициенты составляют только четверть от всех коэффициентов, для установления факта подобия необходимо произвести расчет только четверти от требуемых операций, т.е. 25% операций. 3.3.2. Выбор оптимального аффинного преобразования на основе знакового распределения коэффициентов ДКП
Свойство четности ДКП, кроме возможности сокращения числа сравниваемых коэффициентов, дает возможность более простого и быстрого варианта установления подходящего аффинного преобразования. Кроме установления факта подобия, т.е. нахождения домена, который был бы «похожим» на ранг в каком-либо из восьми аффинных преобразований, существует требование установления идентичности, т.е. установления какого-либо из восьми аффинных преобразований, наиболее подходящего к данному домену.
Прямой перебор всех восьми преобразований для домена, который можно считать подходящим, занимает значительное время. Подходом в сокращении времени расчета является использование распределения знакового поля для установления факта подобия между восьмью аффинными преобразованиями. Знаковое распределение имеет периодический характер и независимо от значения частоты коэффициентов, но визуально заметными являются младшие коэффициенты. Их вклад наиболее заметен. Исходя из этого, достаточно того, чтобы знаковое распределение младших индексов рангового и доменного блока совпадало. Если такого совпадения нет, то ошибка отклонения будет значительна, в то время как для старших индексов, даже при несовпадении их знакового распределения, ошибка отклонения будет невелика, так как значения этих коэффициентов малы. На основе знакового распределения младших коэффициентов формируется трехразрядный двоичный код. Все его восемь состояний описывают восемь аффинных преобразований. Исходя из этого, работа разработанного алгоритма заключается в использовании прямого метода адресации - поиска номера аффинного преобразования в ячейке памяти, адресуемой трехразрядным двоичным кодом. Рассмотренный принцип реализован в алгоритме на рисунке 3.8.
Алгоритм выбора оптимального аффинного преобразования на основе свойств ДКП На рисунке 3.8 представлена последовательность обработки данных. В блоках 2 и 3 осуществляется выделение знакового бита из коэффициентов ДКП. Данная операция выполняется простым смещением 32-х разрядного числа на 31 разряд вправо. Для формирования трехразрядного числа полученные биты сдвигают на один разряд влево для коэффициента с индексом 2 и на два разряда влево для коэффициента с индексом 4. Для коэффициента с индексом 1 сдвиг влево не производится. Полученные числа складываются и образуют трехразрядный код.
В четвертом блоке производится расчет восьми аффинных преобразований для ранга. Данный расчет производится для каждого ранга только один раз для всех доменов. Указатели на области памяти, в которых хранятся все восемь аффинных преобразований рангов, сохраняются в целочисленном массиве. Данная операция производится в блоке 5. В шестом блоке производится поиск оптимального аффинного преобразования на основе трехразрядного кода.
Статистические исследования алгоритма Фишера
Предел сжатия у JPEG ограничивается сжатием до 120 раз. Для сравнения изображение «Пересечение» сжималось в формате .TIF, что обеспечило сжатие в 22 раза. Прямое сжатие с помощью архиватора ZIP обеспечило сжатие в 32 раза. Впечатляющий результат работы фрактального алгоритма для простого изображения «Пересечение» объясняется тем, что области с одинаковым значение пикселей и JPEG, и ТШ, и ZIP сжимают на основе теории информации. В то время как фрактальный алгоритм анализирует изображение и при наличии областей с одинаковым значением пикселей просто их исключает. Это отражает «интеллектуальность» фрактального алгоритма. При этом резкие переходы на границах формируются за счет того, что коэффициент сжатия яркости s может принимать значение до двух единиц, т.е. может усиливать контрастность границ.
Результаты сравнения эффективности сжатия нового фрактального алгоритма и ряда существующих алгоритмов сжатия позволяют говорить о том, что новый алгоритм эффективен для искусственно созданных изображений с большими одноцветными областями и резкими границами между ними.
Как рассматривалось в первой главе, выражение (1.10) указывает на сходимость любого первоначального изображения к аттрактору. Но очевиден
На изображении «Lena-І» существует область, отличающаяся от исходного изображения «Lena». На изображении «Lena-2» существует две области, отличающиеся от исходного изображения «Lena». На изображении «Rose» нет элементов, похожих на элементы исходного изображения «Lena». К трем исходным изображениям применяют закодированное преобразование изображения «Lena». Результат имеет следующий вид:
Как видно из рисунков 4.31, 4.32 и 4.33, чем больше отличий исходного изображения от закодированного, тем больше итераций необходимо произвести для получения изображения близкого к аттрактору. Для изображения «Lena-І» изображение, близкое к аттрактору, получается после трех итераций, для изображения «Lena-2» изображение, близкое к аттрактору, получается после четырех итераций, для изображения «Rose» изображение, близкое к аттрактору, получается после шести итераций. Также необходимо отметить, что, чем больше исходное изображение «похоже» на закодированное, тем более «похоже» изображение после первой итерации на исходное. Таким образом, для задачи распознавания достаточно провести только одну итерацию.
Данный результат подтверждает способность фрактальных алгоритмов распознавать структуры. При этом требуется только одна итерация.
Экспериментальные исследования показали применимость фрактальных алгоритмов как для задач сжатия изображения, так и для задач распознавания.
Рассмотренный в первой главе математический аппарат фрактального анализа и синтеза указывает на независимость коэффициентов фрактального анализа от размеров синтезируемого изображения. Исходя из этого, возможен синтез аттрактора фрактала размером больше, чем анализируемое изображение. Дополнительные точки синтезируются на основе строго установленных закономерностей подобия.
Для оценки качества масштабирования на основе фрактального анализа необходимо сравнить его результаты с другим алгоритмом масштабирования. Для этого выберем широко распространенный алгоритм билинейной интерполяции. В этом алгоритме дополнительные точки рассчитываются на основе квадрата пропорции яркости соседних точек. При этом важно отметить, что каждую точку окружают восемь соседних точек. Таким образом, билинейная интерполяция требует восемь операций умножения на одну новую точку. Построения аттрактора фрактала большего масштаба потребует меньше операций.
В качестве тестового изображения было выбрано изображение «Lena». На рисунке 4.34 выделен участок тестового изображения. Для сравнения качества приведем изображения данного участка при масштабировании билинейной интерполяцией и фрактальным анализом на рисунках 4.35 и 4.36 соответственно.
Выделенный уча- Рисунок 4.36. Выделенный уча сток при масштабировании с сток при масштабировании с билинейной интерполяцией. фрактальным анализом. При сравнении рисунков 4.35 и 4.36 можно сделать вывод о том, что фрактальное масштабирование способно создать изображение с лучшей контрастностью, чем алгоритм на основе интерполяции, но при этом заметны отдельные артефакты блочности. Это связано с тем, что размер ранговых блоков становятся равным 8 8. Для задачи фрактального масштабирования необходимо использовать ранговые блоки наименьших размеров.
В приложении А приведена статистика исследования времени работы и качества анализа базового алгоритма Фишера и нового алгоритма фрактального анализа, реализующего три новых алгоритма сокращения вычислительной сложности. Данные статистические исследования были произведены в контексте задачи разработки аппаратно-программного обеспечения необитаемых подводных аппаратов. Как видно из приложения А качество фрактального масштабирования заметно лучше качества билинейной интерполяции для различных изображений. Таким образом, можно сделать вывод, что фрактальное масштабирование дает лучшее качество, чем стандартные алгоритмы.
