Принципы фрактального сжатия изображений

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

С точки зрения машинной графики, фрактальная геометрия незаменима при генерации сложных неевклидовых объектов, образы которых весьма похожи на природные, и когда требуется с помощью нескольких коэффициентов задать линии и поверхности очень сложной формы. Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения   Существует большое разнообразие фракталов. Потенциально наиболее полезным видом фракталов являются фракталы на основе системы итеративных функций (Iterated Function System – IFS). Метод IFS применительно к построению фрактальных изображений, изобретённый большим их знатоком Майклом Барнсли (Michael Barnsley) и его коллегами из Технологического института шт. Джорджия (Georgia Institute of Technology), базируется на самоподобии элементов изображения и заключается в моделировании рисунка несколькими меньшими фрагментами его самого. Специальные уравнения позволяют переносить, поворачивать и изменять масштаб участков изображения; таким образом, что эти участки служат компоновочными блоками остальной части картины.

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

IFS-фракталы имеют одно  вполне реальное и полезное  применение: с их помощью можно  сжимать большие растровые изображения  до долей их нормальных размеров. Это утверждение следует из  теоремы Банаха о сжимающих преобразованиях (также известной как Collage Theorem) и является результатом работы исследователя Технологического института шт. Джорджия Майкла Барнсли в области IFS. Вооружившись этим выводом, он ушёл из института, запатентовал своё открытие и основал компанию Iterated Systems Incorporated. О своём достижении он рассказал миру в журнале Byte за январь 1988 г. Однако там отсутствовали какие-либо сведения о решении обратной задачи: как по заданному изображению найти аффинные преобразования. К тому моменту у этой задачи не было даже намёка на решение. В статье Барнсли было показано несколько реалистичных фрактальных изображений, но все они были созданы вручную.

В идеале хотелось бы уметь находить для любого изображения систему аффинных преобразований (IFSM), воспроизводящую изображение с заданной точностью. Однако решение находилось немного в стороне. Первым нашёл его именно студент Барнсли, Арно Жакан (Arnaud Jacquin). Предложенный метод получил название «Система итерируемых кусочно-определённых функций» (Partitioned Iterated Function System – PIFS). Согласно этой схеме, отдельные части изображения подобны не всему изображению, а только его частям.

Типовая схема фрактального сжатия

Схема компрессии выглядит так: изображение R разбивают на кусочки ri, называемые ранговыми областями. Далее для каждой области ri находят область di и преобразование wi такие, что выполняются следующие условия:

di по размерам больше ri.

wi (ri) имеет ту же форму, размеры и положение, что и ri.

Коэффициент u преобразования wi должен быть меньше единицы.

Значение должно быть как можно меньше.

Первые три условия означают, что отображение wi будет сжимающим. А в силу четвёртого условия кодируемое изображение R и его образ W (R) будут похожи друг на друга. В идеале R = W(R). А это означает, что наше изображение R и будет являться неподвижной точкой W. Именно здесь используется подобие различных частей изображения (отсюда и название – «фрактальная компрессия»). Как оказалось, практически все реальные изображения содержат такие похожие друг на друга, с точностью до аффинного преобразования, части.

Таким образом, для компрессии изображения W нужно:

Разбить изображение на ранговые области ri (непересекающиеся области, покрывающие все изображение).

Для каждой ранговой области ri найти область di (называемую доменной), и отображение wi, с указанными выше свойствами.

Запомнить коэффициенты аффинных преобразований W, положения доменных областей di, а также разбиение изображения на домены.

Соответственно, для декомпрессии изображения нужно будет:

Создать какое-то (любое) начальное изображение R0.

Многократно применить к нему отображение W (объединение wi).

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

Основная сложность метода

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

На данный момент известно достаточно большое количество алгоритмов оптимизации перебора, возникающего при фрактальном сжатии, поскольку большинство статей, исследовавших алгоритм были посвящены этой проблеме, и во время активных исследований (1992—1996 года) выходило до 300 статей в год. Наиболее эффективными оказались два направления исследований: метод выделения особенностей (feature extraction) и метод классификации доменов (classification of domains).

Оптимизация алгоритма компрессии

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

Для снижения вычислительных затрат можно предпринять следующие меры: Исследовать доменную область не полностью, а с некоторым шагом. Это также позволит увеличить степень сжатия, но скажется на качестве изображения. Искать не лучшую доменную область, а удовлетворяющую некоторому E. Хотя это может значительно увеличить скорость сжатия, но такой приём так же может значительно снизить качество результирующего изображения. В данном случае качество в значительной степени зависит от адекватности метрики различия между изображениями. При поиске доменной области подвергать преобразованию не доменную область, а ранговую. Для этого удобно хранить 8 вариантов ранговых областей с различными преобразованиями. При этом в результирующий файл нужно записать обратное преобразование. Для всех преобразований, кроме двух, обратным является само это преобразование. Для поворота на 90° и 270° необходимо записать поворот на 270° и 90° соответственно. Это значительно сократит вычислительные затраты, но также значительно увеличатся затраты оперативной памяти. Для поиска доменной области можно использовать не перебор, а какой-либо из алгоритмов условной нелинейной глобальной оптимизации, такой, как алгоритм моделирования отжига или генетический алгоритм. В этом случае будет всего три варьируемых параметра (координаты доменной области и номер аффинного преобразования), а целевой функцией – среднеквадратичное отклонение доменной области от ранговой.

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

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

Патенты

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

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

 

http://www.hardline.ru/8/68/764/

Введение во фракталы

 

Шабаршин А.А., http://algorithms.da.ru

 

Содержание

 

Понятие "фрактал"

Классификация фракталов

2.1 Геометрические фракталы 

2.2 Алгебраические фракталы 

2.3 Стохастические фракталы 

Системы итерируемых функций

Библиографический список

 

1. Понятие "фрактал"

Понятия фрактал и фрактальная геометрия, появившиеся в конце 70-х, с середины 80-х прочно вошли в обиход математиков и программистов. Слово фрактал образовано от латинского fractus и в переводе означает состоящий из фрагментов. Оно было предложено Бенуа Мандельбротом в 1975 году для обозначения нерегулярных, но самоподобных структур, которыми он занимался. Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта `The Fractal Geometry of Nature'. В его работах использованы научные результаты других ученых, работавших в период 1875-1925 годов в той же области (Пуанкаре, Фату, Жюлиа, Кантор, Хаусдорф). Но только в наше время удалось объединить их работы в единую систему.

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

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

Определение фрактала, данное Мандельбротом, звучит так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому" [3].

 

2. Классификация фракталов

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

 

2.1 Геометрические фракталы

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

 

 Рис 1. Построение триадной кривой Кох.

 

Рассмотрим один из таких фрактальных объектов - триадную кривую Кох [3]. Построение кривой начинается с отрезка единичной длины (рис.1) - это 0-е поколение кривой Кох. Далее каждое звено (в нулевом поколении один отрезок) заменяется на образующий элемент, обозначенный на рис.1 через n=1. В результате такой замены получается следующее поколение кривой Кох. В 1-ом поколении - это кривая из четырех прямолинейных звеньев, каждое длиной по 1/3. Для получения 3-го поколения проделываются те же действия - каждое звено заменяется на уменьшенный образующий элемент. Итак, для получения каждого последующего поколения, все звенья предыдущего поколения необходимо заменить уменьшенным образующим элементом. Кривая n-го поколения при любом конечном n называется предфракталом. На рис.1 представлены пять поколений кривой. При n стремящемся к бесконечности кривая Кох становится фрактальным обьектом [3].

 

 Рис 2. Построение "дракона" Хартера-Хейтуэя.

Для получения другого фрактального объекта нужно изменить правила построения. Пусть образующим элементом будут два равных отрезка, соединенных под прямым углом. В нулевом поколении заменим единичный отрезок на этот образующий элемент так, чтобы угол был сверху. Можно сказать, что при такой замене происходит смещение середины звена. При построении следующих поколений выполняется правило: самое первое слева звено заменяется на образующий элемент так, чтобы середина звена смещалась влево от направления движения, а при замене следующих звеньев, направления смещения середин отрезков должны чередоваться. На рис.2 представлены несколько первых поколений и 11-е поколение кривой, построенной по вышеописанному принципу. Предельная фрактальная кривая (при n стремящемся к бесконечности) называется драконом Хартера-Хейтуэя [3].

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

 

2.2 Алгебраические фракталы

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

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

 Рис 3. Множество Мандельброта.

В качестве примера рассмотрим множество Мандельброта (см. pис.3 и рис.4). Алгоритм его построения достаточно прост и основан на простом итеративном выражении:

Z[i+1] = Z[i] * Z[i] + C,

где Zi и C - комплексные переменные. Итерации выполняются для каждой стартовой точки C прямоугольной или квадратной области - подмножестве комплексной плоскости. Итерационный процесс продолжается до тех пор, пока Z[i] не выйдет за пределы окружности радиуса 2, центр которой лежит в точке (0,0), (это означает, что аттрактор динамической системы находится в бесконечности), или после достаточно большого числа итераций (например 200-500) Z[i] сойдется к какой-нибудь точке окружности. В зависимости от количества итераций, в течении которых Z[i] оставалась внутри окружности, можно установить цвет точки C (если Z[i] остается внутри окружности в течение достаточно большого количества итераций, итерационный процесс прекращается и эта точка растра окрашивается в черный цвет).