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

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

Система итерируемых функций (СИФ, Iterated functions system) – это средство получения фрактальных структур.

Аттрактор — это результат применения системы итерированных функций, (не всегда является фракталом).

Аффинные преобразования — это точечные взаимно однозначные отображения плоскости (пространства) на себя, при которых прямые переходят в прямые.

 

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

 

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

 

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

 

 

http://sernam.ru/d_19.php

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

 

Мы обратимся теперь к одному из наиболее замечательных и глубоких достижений в построении фракталов — системам итерированных функций. Математические аспекты были разработаны Джоном Хатчинсоном [23], а сам метод стал широко известен благодаря Майклу Барнсли [4] и другим. Подход на основе систем итерированных функций предоставляет хорошую теоретическую базу для математического исследования многих классических фракталов, а также их обобщений. Разработанная теория непосредственно используется при переходе к исследованию хаоса, связанного с фракталами.

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

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

 

 

 

Рис. 4.1. Построение ковра Серпинского с помощью детерминорованной СИФ

Построение ковра Серпинского в детерминированном алгоритме начинается с выбора компактного множества , например квадрата (рис. 4.1). Затем задаются аффинные преобразования так чтобы исходное множество  было преобразовано, как показано на втором шаге построения рис. 4.1. Это достигается путем выбора следующих трех преобразований:

,

,

и преобразование компактного множества  записывается в виде

.

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

.

Заметим, что все множество возможных построений определяется набором аффинных преобразований ,…, .

Обычно коэффициенты аффинного преобразования записываются в матрицу  размером  элементов:

,

которая полностью описывает фрактальное множество.

В рандомизированном алгоритме, который часто называют игрой в «Хаос», в качестве начального множества выбирают одну точку:

- начальная точка (с произвольными  координатами)

 или  или 

 

 или  или 

 

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

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

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

,

 

где  - матрица соответствующего аффинного преобразования. Очевидно, что .

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

- с коэффициентом сжатия ,

- с коэффициентом сжатия ,

- с коэффициентом сжатия .

Эти  отображений используются для построения одного сжимающего отображения .

Таким образом, системой итерированных функций (СИФ) называют совокупность введенных выше отображений вместе с итерационной схемой:

- компактное множество (произвольное)

,

,

,

Основная задача теории СИФ — выяснить, когда СИФ порождает предельное множество :

.

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

Основные математические идеи, необходимые для установления условий сходимости, уже были представлены. Если нам удастся показать, что Т является сжимающим отображением на метрическом пространстве (К.,Н), то мы сможем применить теорию сжимающих отображений. В этом случае аттрактор Е есть не что иное, как неподвижная точка отображения Т.

 

 

http://sernam.ru/d_21.php

21. Сжатие изображений с использованием СИФ

Из примеров построения фракталов видно, что получаемые таким образом изображения могут быть очень похожими на реальные. Например, с помощью фрактальной геометрии можно получать реалистичные изображения листьев, трав, деревьев, гор, рек и других природных объектов. Причем каждый раз при генерации фрактальных множеств (изображений) используется только матрица коэффициентов , содержащая коэффициенты сжимающих аффинных преобразований. Можно заметить, что объем данных, занимаемых элементами матрицы , как правило, много меньше объема сгенерированного изображения, даже если его записать в известных форматах gif, jpeg, tif и др. Таким образом, некоторые реалистичные изображения можно описать коэффициентами аффинных преобразований и генерировать аттрактор с любым масштабом. При таком подходе иногда удается получать довольно большие коэффициенты сжатия от 1:1000 до 1:10000. Кроме того, масштаб сгенерированных изображений с помощью СИФ может быть любым при сохранении хорошего визуального качества.

При сжатии изображений используют трехмерные сжимающие преобразования вида

.

Здесь третья координата  соответствует значению яркости отсчета изображения.

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

Рис. 2. Иллюстрация ранговой и доменной областей

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

.

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

В учебном варианте алгоритма, изложенном далее, сделаны следующие ограничения на области:

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

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

3. Все доменные блоки  — квадраты и имеют фиксированный  размер. Изображение равномерной  сеткой разбивается на набор  доменных блоков.

4. Доменные области берутся  “через точку” и по Х, и  по Y, что сразу уменьшает перебор в 4 раза.

5. При переводе доменной  области в ранговую поворот куба возможен только на 00, 900, 1800 или 2700. Также допускается зеркальное отражение. Общее число возможных преобразований (считая пустое) — 8.

6. Масштабирование (сжатие) по вертикали (яркости) осуществляется  в фиксированное число раз — в 0,75.

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

Например, для файла в градациях серого 256 цветов 512х512 пикселов при размере блока 8 пикселов аффинных преобразований будет 4096 (512/8x512/8). На каждое потребуется 3.5 байта. Следовательно, если исходный файл занимал 262144 (512х512) байт (без учета заголовка), то файл с коэффициентами будет занимать 14336 байт. Коэффициент архивации — 18 раз. При этом мы не учитываем, что файл с коэффициентами тоже может обладать избыточностью и архивироваться методом архивации без потерь, например LZW.

Отрицательные стороны предложенных ограничений:

1. Поскольку все области  являются квадратами, невозможно  воспользоваться подобием объектов, по форме далеких от квадратов (которые встречаются в реальных  изображениях достаточно часто.)

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

3. Алгоритм не сможет  воспользоваться подобием объектов  в изображении, угол между которыми не кратен 900.

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

Как видно из приведенного алгоритма, для каждого рангового блока делаем его проверку со всеми возможными доменными блоками (в том числе с прошедшими преобразование симметрии), находим вариант с наименьшей мерой L2 (наименьшим среднеквадратичным отклонением) и сохраняем коэффициенты этого преобразования в файл. Коэффициенты — это (1) координаты найденного блока, (2) число от 0 до 7, характеризующее преобразование симметрии (поворот, отражение блока), и (3) сдвиг по яркости для этой пары блоков. Сдвиг по яркости вычисляется как:

,

где rij — значения пикселов рангового блока (R), а dij — значения пикселов доменного блока (D). При этом мера считается как:

.

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

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

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

 

http://wiki.asoiu.com/index.php/Фрактальное_сжатие

Фрактальное сжатие

1 История возникновения  метода фрактального сжатия

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

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

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

5 Патенты

6 См. также

7 Ссылки

 

История возникновения метода фрактального сжатия

Понятия «фрактал» и «фрактальная геометрия» (fractus – состоящий из фрагментов, лат.) были предложены математиком Б. Мандельбротом в 1975 г. для обозначения нерегулярных, но самоподобных структур. Рождение фрактальной геометрии связывают с выходом в 1977 г. книги Б. Мандельброта «Фрактальная геометрия природы», в которой объединены в единую систему научные результаты учёных, работавших в период 1875-1925 гг. в этой области (Пуанкаре, Жюлиа, Кантор и др.).