АВТОБИОГРАФИЯ   ЭЛЕКТРОННАЯ БИБЛИОТЕКА   ССЫЛКИ ПО ТЕМЕ  
ОТЧЕТ О ПОИСКЕ   АВТОРЕФЕРАТ

Фрактальное сжатие изображений. Алгоритм компрессии и декомпрессии. Результат реализации.

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

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

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

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

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

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

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

Алгоритм компрессии

Для наглядности алгоритма рассмотрено на примере изображение размером 16*16.

Шаг 1. Перевести цветное изображение в cерый. Для этого используем формулу(2.1):

(2.1)

Шаг 2. Разбиваем изображения на области, которые разбиваются так называемые ранговые блоки Rk, размером n*n, например 4*4. В данном случаи ранговые блоки - это квадраты(рис.2.2)

(2.2)

Рисунок 2.2 - Разбиение на ранги

Таким образом, для изображения 16*16 получим 16 ранговых блоков Rk, размером 4*4.

Шаг 3. Разбиваем изображения на доменные блоки Dt(рис.2.3), размером 2n*2n, то есть 8*8. Доменные блоки больше рангових в 2 или больше раз.

(2.3)

Рисунок 2.3 - Разбиение на доменны

Таким образом, для изображения 16*16 получим 4 доменных блока Dt, размером 8*8.

Шаг 4. Для каждого ранга Rk(от=1 ... 16) подбирается такой домен, который наилучшим образом превращается в этот ранг. Подбор осуществляется за схемой(рис.2.4). Для этого каждый с доменнов превращается несколькими разными способами. В базовой версии алгоритма проводится 4 поворота. После этого превращённый доменный блок сжимается к размерам рангового. После этого применяются формули 2.5 - 2.10.

(2.4)

Рисунок 2.4 - Схема нахождения наилучшего домена для каждого из рангов Rk (от=1...16)

Каждый пиксел превращённого домена меняется по формулам 2.5 - 2.10 с помощью коефициентов s(контрастность) и о(яркость). Дальше оцениваем схожесть этого домена(уже с изменёнными значениями пикселов по формуле 2.4) с рангом(наименьшее среднеквадратичного значения).

(2.5)

(2.6 - 2.10)

Из всех этих 16 показателей L2 находим минимальний и сохраняем в файл для этого рангового блока параметры, ответные этому L2. Таким образом, параметри наилучшего превращения для каждого ранга записуются в файл. Такими параметрами есть: координаты этого доменного блока; тип поворота доменного блока к; яркость о; контрастность s. Таким образом, таких наборов параметров будет 16 - то есть для каждого рангового блоко Rk (от = 1... 16).

Алгоритм декомпрессии

Шаг 1. Генерируем некоторое изображение(например, чорное) такого же размера, как и сжатое, например 16*16.

Шаг 2. Разбиваем изображения на ранговые блоки Rk(риc.2.5), размером n*n, например 4*4. Таким образом, для изображения 16*16 получим 16 ранговых блока Rk размером 4*4.

(2.5)

Рисунок 2.5 - Разбиение на ранги

Шаг 3. Разбиваем изображения на доменные блоки Dt(риc.2.6), размером 2n*2n, то есть 8*8. Таким образом, для изображения 16*16 получим 4 доменных блока Dt размером 8*8.

(2.6)

Рисунок 2.6 - Разбиение на доменны

Шаг 4. Считываем из сжатого файла все 16 наборов параметров: координаты доменного блока, тип поворота К, яркость О, контрастность S.

Шаг 5. Для каждого рангового блока, используя считанные с файла соответствующие параметры выполнить следующие действия: считанными координатами определить доменный блок Dt(t=1...4); преобразовать его в соответствии с типом преобразования; сжать доменный блок к размеру рангового, то есть в 2 раза; присвоить значениям пикселов данного рангового блока, расчитанные по формуле:

Результат реализации

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

Рисунок 2.7 - Результат реализации базового алгоритма

1.Шабаршин А.А "Введение во фракталы": М - 1998г