Алгоритм RLE

Первый вариант алгоритма

 

Данный алгоритм необычайно прост в реализации. Групповое кодирование - от английского Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем (как и в нескольких алгоритмах, описанных ниже) вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.

 

Соответственно оставшиеся 6 бит расходуются на счетчик, который может принимать значения от 1 до 64. Строку из 64 повторяющихся байтов мы превращаем в два байта, т.е. сожмем в 32 раза.

 

Алгоритм рассчитан на деловую графику - изображения с большими областями повторяющегося цвета.

 

Алгоритм LZW –метод словарей (сочетаний)

 

Название алгоритм получил по первым буквам фамилий его разработчиков - Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байт.

 

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

 

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

 

Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.

 

АЛГОРИТМ ХАФФМАНА

 

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

 

Для начала введем несколько определений.

 

Определение. Пусть задан алфавит Y ={a1, ..., ar}, состоящий из конечного числа букв. Конечную последовательность символов из Y

будем называть словом в алфавите Y , а число n — длиной слова A. Длина слова обозначается как l(A).

 

Пусть задан алфавит W , W ={b1, ..., bq}. Через B обозначим слово в алфавите W и через S(W ) — множество всех непустых слов в алфавите W .

 

Пусть S=S(Y ) — множество всех непустых слов в алфавите Y , и S' — некоторое подмножество множества S. Пусть также задано отображение F, которое каждому слову A, A? S(Y ), ставит в соответствие слово

 

B=F(A), B? S(W ).

 

Слово В будем назвать кодом сообщения A, а переход от слова A к его коду — кодированием.

 

Определение. Рассмотрим соответствие между буквами алфавита Y и некоторыми словами алфавита W :

 

a1 — B1,

a2 — B2,

. . .

ar — Br

 

Это соответствие называют схемой и обозначают через S . Оно определяет кодирование следующим образом: каждому слову  из S'(W )=S(W ) ставится в соответствие слово , называемое кодом слова A. Слова B1 ... Br называются элементарными кодами. Данный вид кодирования называют алфавитным кодированием.

 

Определение. Пусть слово В имеет вид

 

B=B' B"

 

Тогда слово B'называется началом или префиксом слова B, а B" — концом слова B. При этом пустое слово L и само слово B считаются началами и концами слова B.

 

Определение. Схема Sобладает свойством префикса, если для любых iи j(1?i, j? r, i? j) слово Bi не является префиксом слова Bj.

 

Теорема 1. Если схема Sобладает свойством префикса, то алфавитное кодирование будет взаимно однозначным.

 

Предположим, что задан алфавит Y ={a1,..., ar} (r>1) и набор вероятностей p1, . . . , pr появления символов a1,..., ar. Пусть, далее, задан алфавит W , W ={b1, ..., bq} (q>1). Тогда можно построить целый ряд схем S алфавитного кодирования

 

a1 — B1,

. . .

ar — Br

обладающих свойством взаимной однозначности.

 

Для каждой схемы можно ввести среднюю длину lср, определяемую как математическое ожидание длины элементарного кода:

— длины слов.

Длина lср показывает, во сколько раз увеличивается средняя длина слова при кодировании со схемой S .

 

Можно показать, что lср достигает величины своего минимума l* на некоторой Sи определена как

Определение. Коды, определяемые схемой S с lср= l*, называются кодами с минимальной избыточностью, или кодами Хаффмана.

 

Коды с минимальной избыточностью дают в среднем минимальное увеличение длин слов при соответствующем кодировании.

 

В нашем случае, алфавит Y ={a1,..., ar} задает символы входного потока, а алфавит W ={0,1}, т.е. состоит всего из нуля и единицы.

 

Алгоритм построения схемы S можно представить следующим образом:

 

Шаг 1. Упорядочиваем все буквы входного алфавита в порядке убывания вероятности. Считаем все соответствующие слова Bi из алфавита W ={0,1} пустыми.

 

Шаг 2. Объединяем два символа air-1 и air с наименьшими вероятностями pi r-1 и pi r в псевдосимвол a'{air-1 air} c вероятностью pir-1+pir. Дописываем 0 в начало слова Bir-1 (Bir-1=0Bir-1), и 1 в начало слова Bir (Bir=1Bir).

 

Шаг 3. Удаляем из списка упорядоченных символов air-1 и air, заносим туда псевдосимвол a'{air-1air}. Проводим шаг 2, добавляя при необходимости 1 или ноль для всех слов Bi, соответствующих псевдосимволам, до тех пор, пока в списке не останется 1 псевдосимвол.

 

Пример: Пусть у нас есть 4 буквы в алфавите Y ={a1,..., a4} (r=4), p1=0.5, p2=0.24, p3=0.15, p4=0.11 . Тогда процесс построения схемы можно представить так:

 

 

Производя действия, соответствующие 2-му шагу, мы получаем псевдосимвол с вероятностью 0.26 (и приписываем 0 и 1 соответствующим словам). Повторяя же эти действия для измененного списка, мы получаем псевдосимвол с вероятностью 0.5. И, наконец, на последнем этапе мы получаем суммарную вероятность 1.

 

Для того, чтобы восстановить кодирующие слова, нам надо пройти по стрелкам от начальных символов к концу получившегося бинарного дерева. Так, для символа с вероятностью p4, получим B4=101, для p3 получим B3=100, для p2 получим B2=11, для p1 получим B1=0. Что означает схему:

a1 — 0,

a2 — 11

a3 — 100

a4 — 101

Эта схема представляет собой префиксный код, являющийся кодом Хаффмана. Самый часто встречающийся в потоке символ a1 мы будем кодировать самым коротким словом 0, а самый редко встречающийся a4 длинным словом 101.

 

Для последовательности из 100 символов, в которой символ a1 встретится 50 раз, символ a2 — 24 раза, символ a3 — 15 раз, а символ a4 — 11 раз, данный код позволит получить последовательность из 176 бит (). Т.е. в среднем мы потратим 1.76 бита на символ потока.

 

Доказательства теоремы, а также того, что построенная схема действительно задает код Хаффмана, смотри в [10].

 

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

 

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

• Коэффициенты компрессии: 8, 1,5, 1 (Лучший, средний, худший коэффициенты).

 

• Класс изображений: Практически не применяется к изображениям в чистом виде. Обычно используется как один из этапов компрессии в более сложных схемах.

 

• Симметричность: 2 (за счет того, что требует двух проходов по массиву сжимаемых данных).

 

• Характерные особенности: Единственный алгоритм, который не увеличивает размера исходных данных в худшем случае (если не считать необходимости хранить таблицу перекодировки вместе с файлом).

 

C ПОТЕРЯМИ

 

JPEG — один из самых новых и достаточно мощных алгоритмов. Практически он является стандартом де-факто для полноцветных изображений [1]. Оперирует алгоритм областями 8х8, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого, при разложении матрицы такой области в двойной ряд по косинусам (см. формулы ниже) значимыми оказываются только первые коэффициенты. Таким образом, сжатие в JPEG осуществляется за счет плавности изменения цветов в изображении.

 

Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG — Joint Photographic Expert Group — подразделение в рамках ISO — Международной организации по стандартизации. Название алгоритма читается ['jei'peg]. В целом алгоритм основан на дискретном косинусоидальном преобразовании (в дальнейшем ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.

 

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

 

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

 

Как работает алгоритм

 

Итак, рассмотрим алгоритм подробнее. Пусть мы сжимаем 24-битное изображение.

 

Шаг 1.

 

Переводим изображение из цветового пространства RGB, с компонентами, отвечающими за красную (Red), зеленую (Green) и синюю (Blue) составляющие цвета точки, в цветовое пространство YCrCb (иногда называют YUV).

 

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

Упрощенно перевод из цветового пространства RGB в цветовое пространство YCrCb можно представить с помощью матрицы перехода:

 

 

Шаг 2.

 

Разбиваем исходное изображение на матрицы 8х8. Формируем из каждой три рабочие матрицы ДКП — по 8 бит отдельно для каждой компоненты.

 

Шаг 3.

 

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

 

 

Шаг 4.

 

Производим квантование. В принципе, это просто деление рабочей матрицы на матрицу квантования поэлементно. Для каждой компоненты (Y, U и V), в общем случае, задается своя матрица квантования q[u,v] (далее МК).

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

 

С квантованием связаны и специфические эффекты алгоритма. При больших значениях коэффициента gamma потери в низких частотах могут быть настолько велики, что изображение распадется на квадраты 8х8. Потери в высоких частотах могут проявиться в так называемом “эффекте Гиббса”, когда вокруг контуров с резким переходом цвета образуется своеобразный “нимб”.

 

Шаг 5.

 

Переводим матрицу 8x8 в 64-элементный вектор при помощи “зигзаг”-сканирования, т.е. берем элементы с индексами (0,0), (0,1), (1,0), (2,0)...

 

 

Таким образом, в начале вектора мы получаем коэффициенты матрицы, соответствующие низким частотам, а в конце — высоким.

 

Шаг 6.

 

Свертываем вектор с помощью алгоритма группового кодирования. При этом получаем пары типа (пропустить, число), где “пропустить” является счетчиком пропускаемых нулей, а “число” — значение, которое необходимо поставить в следующую ячейку. Так, вектор 42 3 0 0 0 -2 0 0 0 0 1 ... будет свернут в пары (0,42) (0,3) (3,-2) (4,1) ... .

 

Шаг 7.

 

Свертываем получившиеся пары кодированием по Хаффману с фиксированной таблицей.

 

Конвейер операций, используемый в алгоритме JPEG.

 

Существенными положительными сторонами алгоритма является то, что:

1. Задается степень сжатия.
2. Выходное цветное изображение может иметь 24 бита на точку.

Отрицательными сторонами алгоритма является то, что:

1. При повышении степени сжатия изображение распадается на отдельные квадраты (8x8). Это связано с тем, что происходят большие потери в низких частотах при квантовании, и восстановить исходные данные становится невозможно.
2. Проявляется эффект Гиббса — ореолы по границам резких переходов цветов.

 

 

ФРАКТАЛЬНЫЙ АЛГОРИТМ

 

Идея метода

 

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

 

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

 

Наиболее наглядно этот процесс продемонстрировал Барнсли в своей книге “Fractal Image Compression”. Там введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран:

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

 

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

 

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