Теорема. (О сжимающем преобразовании)

Пусть в полном метрическом пространстве (Х, d). Тогда существует в точности одна неподвижная точка этого преобразования и для любой точки , последовательность сходится к .

Более общая формулировка этой теоремы гарантирует нам сходимость.

Определение. Изображением называется функция S, определенная на единичном квадрате и принимающая значения от 0 до 1 или

Пусть трехмерное аффинное преобразование , записано в виде

и определено на компактном подмножестве декартова квадрата [0..1]x[0..1]. Тогда оно переведет часть поверхности S в область , расположенную со сдвигом (e,f) и поворотом, заданным матрицей

.

При этом, если интерпретировать значение S как яркость соответствующих точек, то она уменьшится в p раз (преобразование обязано быть сжимающим) и изменится на сдвиг q.

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

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

Построение алгоритма

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

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

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

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

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

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

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

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

Эти ограничения позволяют:

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

2) Очень компактно представить данные для записи в файл. Нам требуется на каждое аффинное преобразование в IFS:

· два числа для того, чтобы задать смещение рангового блока. Если мы ограничим входные изображения размером 512х512, то достаточно будет по 8 бит на каждое число.

· три бита, для того, чтобы задать преобразование симметрии при переводе рангового блока в доменный.

· 7-9 бит, для того, чтобы задать сдвиг по яркости при переводе.

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

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

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

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

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

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

Такова плата за скорость компрессиии за простоту упаковки коэффициентов в файл.

Сам алгоритм упаковки сводится к перебору всех доменных блоков и подбору для каждого соответствующего ему рангового блока. Ниже приводится схема этого алгоритма.

for (all domain blocks) {

min_distance = MaximumDistance;

Dij= image->CopyBlock(i,j);

for (all range blocks) { // С поворотами и отр.

current=Координаты текущего преобразования;

R=image->CopyBlock(current);

current_distance = Dij.L2distance(R);

if(current_distance < min_distance) {

// Если коэффициенты best хуже:

min_distance = current_distance;

best = current;

}

Save_Coefficients_to_file(best);

} //Next range

} //Next domain

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

,

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

_.

Мы не вычисляем квадратного корня из L₂ меры и не делим ее на n поскольку данные преобразования монотонны и не помешают нам найти экстремум, однако мы сможем выполнять на две операции меньше для каждого блока.

Посчитаем количество операций, необходимых нам для сжатия изображения в градациях серого 256 цветов 512х512 пикселов при размере блока 8 пикселов:

Таким образом нам удалось уменьшить число операций алгоритма компрессии до вполне вычисляемых (пусть и за несколько часов) величин.

Поиск по сайту: