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

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