Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Фрактальный алгоритм

Идея метода

Фрактальное сжатие основано на том, что мы представляем изображение в более компактной форме - с помощью коэффициентов системы итерируе­мых функций (Iterated Function System - далее по тексту как IFS). Прежде чем рассматривать сам процесс архивации, разберем, как IFS строит изо­бражение, т. е. процесс декомпрессии.

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

Наиболее наглядно этот процесс продемонстрировал М. F. Barnsley в книге [22]. Там введено понятие "фотокопировальной машины", состоящей из экрана, на котором изображена исходная картинка, и системы линз, про­ецирующих изображение на другой экран (рис. 2.2):

■ линзы могут проецировать часть изображения произвольной формы в
любое другое место нового изображения;

■ области, в которые проецируются изображения, не пересекаются;
• линза может менять яркость и уменьшать контрастность;

■ линза может зеркально отражать и поворачивать свой фрагмент изо­бражения;

■ линза должна масштабировать (причем только уменьшая) свой фраг­мент изображения.

Лампа

.___ Исходное

/ изображение


Получаемое изображение

Рис. 2.2. Машина Барнсли

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

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

Наиболее известны два изображения, полученные с помощью IFS: тре­угольник Серпинского (рис. 2.3) и папоротник Барнсли (рис. 2.4).

Треугольник Серпинского задается тремя, а папоротник Барнсли - че­тырьмя аффинными преобразованиями (или, в нашей терминологии, "лин­зами"). Каждое преобразование кодируется буквально считанными байтами, в то время как изображение, построенное с их помощью, может занимать и несколько мегабайт.




Рис. 2.3. Треугольник Серпинского Рис 2.4. Папоротник Барнсли

Упражнение. Укажите в изображении 4 области, объединение которых покры­вало бы все изображение и каждая из которых была бы подобна всему изо­бражению (не забывайте о стебле папоротника).

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

Рис. 2.5. Самоподобные области изображения

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


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

Далее приводятся основные определения и теоремы, на которых базиру­ется фрактальная компрессия. Этот материал более детально и с доказа­тельствами рассматривается в [3] и [4].

Определение. Преобразование w: R1 -> Л2, представимое в виде где а, Ъ, с, d, e,f- действительные числа и (х у)еЯг- называется двумер­ным аффинным преобразованием.

Определение. Преобразование w: Л3 -» Д3, представимое в виде


w(x) = w



где a, b, c, d, e,f,p, q, r, s,t,u- действительные числа и (дс у z)eR3, на­зывается трехмерным аффинным преобразованием.

Определение. Пусть /:Х->Х - преобразование в пространстве X.

Точка xfeX, такая, что f(xf) = xf, называется неподвижной точкой (аттрактором) преобразования.

Определение. Преобразование /:Х->Х в метрическом пространстве

(X, d) называется сжимающим, если существует число S: 0 £ s < 1, такое, что

d(f(x),f(y))<s-d(x,y), V*,yeX.

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

Теорема. (О сжимающем преобразовании.) Пусть f: X -> X - сжи­мающее преобразование в полном метрическом пространстве (X, d). Тогда существует в точности одна неподвижная точка xf e X этого преобразования и для любой точки хеХ последовательность \f"(x):n = 0,1,2...} сходится к xf.

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

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

Пусть трехмерное аффинное преобразование w,: R3-> R3, записано в виде Y и определено на компактном подмножестве £>. декартова квадрата

[0...1]х[0...1] (мы пользуемся особым видом матрицы преобразования, чтобы уменьшить размерность области определения с R3 до R2). Тогда оно переве­дет часть поверхности S в область Л,, расположенную со сдвигом (ej) и по­воротом, заданным матрицей r. При этом, если интерпретировать значения функции 5(л:,^)е[0...1] как

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

Определение. Конечная совокупность W сжимающих трехмерных аффин­ных преобразований Wt, определенных на областях Dt, таких, что w,(Ј>,) = R, и J?,. r\Rj=<p V/ * j, называется системой итерируемых функций (IFS).

Системе итерируемых функций однозначно ставятся в соответствие не­подвижная точка- изображение. Таким образом, процесс компрессии за­ключается в поиске коэффициентов системы, а процесс декомпрессии - в проведении итераций системы до стабилизации полученного изображения (неподвижной точки IFS). На практике бывает достаточно 7-16 итераций. Области Ri в дальнейшем будут именоваться ранговыми, а области D, -доменными (рис. 2.6).

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

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

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

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

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

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

4. Доменные области берутся "через точку" и по I и по У, что сразу уменьшает перебор в 4 раза.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

for (all range blocks) {

min_distance = MaximumDistance;

R^j = image->CopyBlock(i, j) ;

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

current=KoopflMHaTH тек. преобразования;

D=image->CopyBlock(current);

}

}


current_distance = R_jj.L2distance(D) ; if(current_distance < min_distance) {

// Если коэффициенты best хуже: min_distance = current_distance; best = current; } }

// Next domain block Save_Coefficients_to_file(best);

// Next range block


Как видно из приведенного алгоритма, для каждого рангового блока де­лаем его проверку со всеми возможными доменными блоками (в том числе с прошедшими преобразование симметрии), находим вариант с наименьшей мерой L2 (наименьшим среднеквадратичным отклонением) и сохраняем ко­эффициенты этого преобразования в файл. Коэффициенты - это (1) коорди­наты найденного блока, (2) число от 0 до 7, характеризующее преобразова­ние симметрии (поворот, отражение блока), и (3) сдвиг по яркости для этой пары блоков. Сдвиг по яркости вычисляется как b для r-,j - значения пикселов рангового блока (К), a dy - значения пикселов доменного блока (D). При этом мера считается как

rf(tf,D) = ££(,;,+S-0.754,)2.

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

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

Часть программы

for (all range blocks)

for (all domain blocks) +

symmetry transformation

Вычисление q и d(R,D)

Число операций

4096 (=512/8-512/8)

492032 (=(512/2-8)* (512/2-8)*8)

> 3*64 операций"+"

> 2*64 операций "•"

Итог:

> 3* 128.983.236.608 операций "+"

> 2* 128.983.236.608 операций "•"

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

Схема алгоритма декомпрессии изображений

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

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

Прочитаем из файла коэффициенты всех блоков; Создадим черное изображение нужного размера; Until(изображение не станет неподвижным){

For(every range (R)){

D=image->CopyBlock(D_coord_for_R); For(every pixel[i,j) in the block{

Rij = Q.lSDij + g; } //Next pixel

} //Next block }//Until end

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

Как можно подсчитать, количество операций на 1 пиксел изображения в градациях серого при восстановлении необычайно мало (N операций сло­жения "+" и N операций умножения"-", где N - количество итераций, т. е. 7-16). Благодаря этому декомпрессия изображений для фрактального алго­ритма проходит быстрее декомпрессии, например, для алгоритма JPEG. В простой реализации JPEG на точку приходится 64 операции сложения "+" и 64 операции умножения "•". При реализации быстрого ДКП можно полу­чить 7 сложений и 5 умножений на точку, но это без учета шагов RLE, квантования и кодирования по Хаффману. При этом для фрактального ал­горитма умножение происходит на рациональное число, одно для каждого блока. Это означает, что мы можем, во-первых, использовать целочислен­ную рациональную арифметику, которая быстрее арифметики с плавающей точкой. Во-вторых, можно использовать умножение вектора на число - бо­лее простую и быструю операцию, часто закладываемую в архитектуру процессора (процессоры SGI, Intel MMX, векторные операции Athlon и т. д.)- Для полноцветного изображения ситуация качественно не изменяет­ся, поскольку перевод в другое цветовое пространство используют оба ал­горитма.

Оценка потерь и способы их регулирования

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

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

Характеристики фрактального алгоритма:

Степень сжатия: 2-2000 (задается пользователем).

Класс изображений: полноцветные 24 битовые изображения или изо-I бражения в градациях серого без резких переходов цветов (фотографии). | Желательно, чтобы области большей значимости (для восприятия) были ; более контрастными и резкими, а области меньшей значимости - некон-I трастными и размытыми.

Симметричность: 100-100 000.

Характерные особенности: может свободно масштабировать изо-\ бражение при разжатии, увеличивая его в 2-4 раза без появления "лест-; ничного эффекта". При увеличении степени компрессии появляется | "блочный" эффект на границах блоков в изображении.