Методы сжатия данных: Сжатие изображений
Алгоритмы архивации без потерь

Алгоритм RLE

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

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

Алгоритм декомпрессии при этом выглядит так:

Initialization(...);
do {
    byte = ImageFile.ReadNextByte();
    if(является счетчиком(byte)) {
        counter = Low6bits(byte)+1;
        value = ImageFile.ReadNextByte();
        for(i=1 to counter)
            DecompressedFile.WriteByte(value)
        }
    else {
        DecompressedFile.WriteByte(byte)
} while(ImageFile.EOF());

В данном алгоритме признаком счетчика (counter) служат единицы в двух верхних битах считанного файла:

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

Упражнение: Составьте алгоритм компрессии для первого варианта алгоритма RLE.

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

Вопрос для самоконтроля: Предложите два-три примера “плохих” изображений для алгоритма RLE. Объясните, почему размер сжатого файла больше размера исходного файла.

Данный алгоритм реализован в формате PCX. См. пример в приложении.

Второй вариант алгоритма

Второй вариант этого алгоритма имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл.

Алгоритм декомпрессии для него выглядит так:

Initialization(...);
do {
    byte = ImageFile.ReadNextByte();
    counter = Low7bits(byte)+1;
    if(если признак повтора(byte)) {
        value = ImageFile.ReadNextByte();
        for (i=1 to counter)
        CompressedFile.WriteByte(value)
    }
    else {
    for(i=1 to counter){
        value = ImageFile.ReadNextByte();
        CompressedFile.WriteByte(value)
    }
    CompressedFile.WriteByte(byte)
} while(ImageFile.EOF());

Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта:

Как можно легко подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем варианте), в худшем увеличивает на 1/128. Средние показатели степени компрессии данного алгоритма находятся на уровне показателей первого варианта.

Упражнение: Составьте алгоритм компрессии для второго варианта алгоритма RLE.

Похожие схемы компрессии использованы в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.

Характеристики алгоритма RLE:

Коэффициенты компрессии: Первый вариант: 32, 2, 0,5. Второй вариант: 64, 3, 128/129. (Лучший, средний, худший коэффициенты)

Класс изображений: Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику.

Симметричность: Примерно единица.

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


Алгоритм LZW

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

Алгоритм LZ

Существует довольно большое семейство LZ-подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек. Один из достаточно простых вариантов этого алгоритма, например, предполагает, что во входном потоке идет либо пара <счетчик, смещение относительно текущей позиции>, либо просто <счетчик> “пропускаемых” байт и сами значения байтов (как во втором варианте алгоритма RLE). При разархивации для пары <счетчик, смещение> копируются <счетчик> байт из выходного массива, полученного в результате разархивации, на <смещение> байт раньше, а <счетчик> (т.е. число равное счетчику) значений “пропускаемых” байт просто копируются в выходной массив из входного потока. Данный алгоритм является несимметричным по времени, поскольку требует полного перебора буфера при поиске одинаковых подстрок. В результате нам сложно задать большой буфер из-за резкого возрастания времени компрессии. Однако потенциально построение алгоритма, в котором на <счетчик> и на <смещение> будет выделено по 2 байта (старший бит старшего байта счетчика — признак повтора строки / копирования потока), даст нам возможность сжимать все повторяющиеся подстроки размером до 32Кб в буфере размером 64Кб.

При этом мы получим увеличение размера файла в худшем случае на 32770/32768 (в двух байтах записано, что нужно переписать в выходной поток следующие 215 байт), что совсем неплохо. Максимальный коэффициент сжатия составит в пределе 8192 раза. В пределе, поскольку максимальное сжатие мы получаем, превращая 32Кб буфера в 4 байта, а буфер такого размера мы накопим не сразу. Однако, минимальная подстрока, для которой нам выгодно проводить сжатие, должна состоять в общем случае минимум из 5 байт, что и определяет малую ценность данного алгоритма. К достоинствам LZ можно отнести чрезвычайную простоту алгоритма декомпрессии.

Упражнение: Предложите другой вариант алгоритма LZ, в котором на пару <счетчик, смещение> будет выделено 3 байта, и подсчитайте основные характеристики своего алгоритма.

Алгоритм LZW

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

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

Функция InitTable() очищает таблицу и помещает в нее все строки единичной длины.

InitTable();
CompressedFile.WriteCode(СlearCode);
CurStr=пустая строка;
while(не ImageFile.EOF()){ //Пока не конец файла
    C=ImageFile.ReadNextByte();
    if(CurStr+C есть в таблице)
        CurStr=CurStr+С;//Приклеить символ к строке
    else {
        code=CodeForString(CurStr);//code-не байт!
        CompressedFile.WriteCode(code);
        AddStringToTable (CurStr+С);
        CurStr=С; // Строка из одного символа
    }
}
code=CodeForString(CurStr);
CompressedFile.WriteCode(code);
CompressedFile.WriteCode(CodeEndOfInformation);

Как говорилось выше, функция InitTable() инициализирует таблицу строк так, чтобы она содержала все возможные строки, состоящие из одного символа. Например, если мы сжимаем байтовые данные, то таких строк в таблице будет 256 (“0”, “1”, ... , “255”). Для кода очистки (ClearCode) и кода конца информации (CodeEndOfInformation) зарезервированы значения 256 и 257. В рассматриваемом варианте алгоритма используется 12-битный код, и, соответственно, под коды для строк нам остаются значения от 258 до 4095. Добавляемые строки записываются в таблицу последовательно, при этом индекс строки в таблице становится ее кодом.

Функция ReadNextByte() читает символ из файла. Функция WriteCode() записывает код (не равный по размеру байту) в выходной файл. Функция AddStringToTable() добавляет новую строку в таблицу, приписывая ей код. Кроме того, в данной функции происходит обработка ситуации переполнения таблицы. В этом случае в поток записывается код предыдущей найденной строки и код очистки, после чего таблица очищается функцией InitTable(). Функция CodeForString() находит строку в таблице и выдает код этой строки.

Пример:

Пусть мы сжимаем последовательность 45, 55, 55, 151, 55, 55, 55. Тогда, согласно изложенному выше алгоритму, мы поместим в выходной поток сначала код очистки <256>, потом добавим к изначально пустой строке “45” и проверим, есть ли строка “45” в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “45” есть в таблице. Далее мы читаем следующий символ 55 из входного потока и проверяем, есть ли строка “45, 55” в таблице. Такой строки в таблице пока нет. Мы заносим в таблицу строку “45, 55” (с первым свободным кодом 258) и записываем в поток код <45>. Можно коротко представить архивацию так:

  • “45” — есть в таблице;
  • “45, 55” — нет. Добавляем в таблицу <258>“45, 55”. В поток: <45>;
  • “55, 55” — нет. В таблицу: <259>“55, 55”. В поток: <55>;
  • “55, 151” — нет. В таблицу: <260>“55, 151”. В поток: <55>;
  • “151, 55” — нет. В таблицу: <261>“151, 55”. В поток: <151>;
  • “55, 55” — есть в таблице;
  • “55, 55, 55” — нет. В таблицу: “55, 55, 55” <262>. В поток: <259>;
Последовательность кодов для данного примера, попадающих в выходной поток: <256>, <45>, <55>, <55>, <151>, <259>.

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

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

Алгоритм декомпрессии, осуществляющий эту операцию, выглядит следующим образом:

code=File.ReadCode();
while(code != СodeEndOfInformation){
    if(code = СlearСode) {
        InitTable();
        code=File.ReadCode();
        if(code = СodeEndOfInformation)
            {закончить работу};
        ImageFile.WriteString(StrFromTable(code));
        old_code=code;
    }
    else {
        if(InTable(code)) {
            ImageFile.WriteString(FromTable(code));
            AddStringToTable(StrFromTable(old_code)+
            FirstChar(StrFromTable(code)));
            old_code=code;
        }
        else {
            OutString= StrFromTable(old_code)+
            FirstChar(StrFromTable(old_code));
            ImageFile.WriteString(OutString);
            AddStringToTable(OutString);
            old_code=code;
        }
    }
}

Здесь функция ReadCode() читает очередной код из декомпрессируемого файла. Функция InitTable() выполняет те же действия, что и при компрессии, т.е. очищает таблицу и заносит в нее все строки из одного символа. Функция FirstChar() выдает нам первый символ строки. Функция StrFromTable() выдает строку из таблицы по коду. Функция AddStringToTable() добавляет новую строку в таблицу (присваивая ей первый свободный код). Функция WriteString() записывает строку в файл.

Замечание 1. Как вы могли заметить, записываемые в поток коды постепенно возрастают. До тех пор, пока в таблице не появится, например, в первый раз код 512, все коды будут меньше 512. Кроме того, при компрессии и при декомпрессии коды в таблице добавляются при обработке одного и того же символа, т.е. это происходит “синхронно”. Мы можем воспользоваться этим свойством алгоритма для того, чтобы повысить степень компрессии. Пока в таблицу не добавлен 512 символ, мы будем писать в выходной битовый поток коды из 9 бит, а сразу при добавлении 512 — коды из 10 бит. Соответственно декомпрессор также должен будет воспринимать все коды входного потока 9-битными до момента добавления в таблицу кода 512, после чего будет воспринимать все входные коды как 10-битные. Аналогично мы будем поступать при добавлении в таблицу кодов 1024 и 2048. Данный прием позволяет примерно на 15% поднять степень компрессии:

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

Заметим также, что реально нам достаточно хранить в таблице только пару <код предыдущей подстроки, добавленный символ>. Этой информации вполне достаточно для работы алгоритма. Таким образом, массив от 0 до 4095 с элементами <код предыдущей подстроки; добавленный символ; список ссылок на строки, начинающиеся с этой строки> решает поставленную задачу поиска, хотя и очень медленно.

На практике для хранения таблицы используется такое же быстрое, как в случае списков, но более компактное по памяти решение — хэш-таблица. Таблица состоит из 8192 (213) элементов. Каждый элемент содержит <код предыдущей подстроки; добавленный символ; код этой строки>. Ключ для поиска длиной в 20 бит формируется с использованием двух первых элементов, хранимых в таблице как одно число (key). Младшие 12 бит этого числа отданы под код, а следующие 8 бит под значение символа.

В качестве хэш-функции при этом используется:

Index(key)= ((key >> 12) ^ key) & 8191;

Где >> — побитовый сдвиг вправо (key >> 12 — мы получаем значение символа), ^ — логическая операция побитового исключающего ИЛИ, & логическое побитовое И.

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

Подсчитаем лучший и худший коэффициенты компрессии для данного алгоритма. Лучший коэффициент, очевидно, будет получен для цепочки одинаковых байт большой длины (т.е. для 8-битного изображения, все точки которого имеют, для определенности, цвет 0). При этом в 258 строку таблицы мы запишем строку “0, 0”, в 259 — “0, 0, 0”, ... в 4095 — строку из 3839 (=4095-256) нулей. При этом в поток попадет (проверьте по алгоритму!) 3840 кодов, включая код очистки. Следовательно, посчитав сумму арифметической прогрессии от 2 до 3839 (т.е. длину сжатой цепочки) и поделив ее на 3840*12/8 (в поток записываются 12-битные коды), мы получим лучший коэффициент компрессии.

Упражнение: Вычислить точное значение лучшего коэффициента компрессии. Более сложное задание: вычислить тот же коэффициент с учетом замечания 1.

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

Упражнение: Составить алгоритм генерации таких цепочек. Попробовать сжать полученный таким образом файл стандартными архиваторами (zip, arj, gz). Если вы получите сжатие, значит алгоритм генерации написан неправильно.

В случае, если мы постоянно будем встречать новую подстроку, мы запишем в выходной поток 3840 кодов, которым будет соответствовать строка из 3838 символов. Без учета замечания 1 это составит увеличение файла почти в 1.5 раза.

LZW реализован в форматах GIF и TIFF.

Характеристики алгоритма LZW:

Коэффициенты компрессии: Примерно 1000, 4, 5/7 (Лучший, средний, худший коэффициенты). Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб.

Класс изображений: Ориентирован LZW на 8-битные изображения, построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке.

Симметричность: Почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.

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


Алгоритм Хаффмана

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

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

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

Определение. Пусть задан алфавит 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 :

a1B1,
a2B2,
. . .
arBr

Это соответствие называют схемой и обозначают через 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 алфавитного кодирования

a1B1,
. . .
arBr

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

Для каждой схемы можно ввести среднюю длину 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].

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

На практике используются его разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее “адаптивно”, т.е. в процессе архивации/разархивации. Эти приемы избавляют нас от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG и в рассмотренном ниже алгоритме CCITT Group 3.

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

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

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

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

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


Алгоритм Хаффмана с фиксированной таблицей CCITTGroup 3

Близкая модификация алгоритма используется при сжатии черно-белых изображений (один бит на пиксел). Полное название данного алгоритма CCITT Group 3. Это означает, что данный алгоритм был предложен третьей группой по стандартизации Международного Консультационного Комитета по Телеграфии и Телефонии (Consultative Committee International Telegraph and Telephone). Последовательности подряд идущих черных и белых точек в нем заменяются числом, равным их количеству. А этот ряд, уже в свою очередь, сжимается по Хаффману с фиксированной таблицей.

Определение: Набор идущих подряд точек изображения одного цвета называется серией.Длина этого набора точек называется длиной серии.

В таблице, приведенной ниже, заданы два вида кодов:

  • Коды завершения серий — заданы с 0 до 63 с шагом 1.
  • Составные (дополнительные) коды — заданы с 64 до 2560 с шагом 64.
Каждая строка изображения сжимается независимо. Мы считаем, что в нашем изображении существенно преобладает белый цвет, и все строки изображения начинаются с белой точки. Если строка начинается с черной точки, то мы считаем, что строка начинается белой серией с длиной 0. Например, последовательность длин серий 0, 3, 556, 10, ... означает, что в этой строке изображения идут сначала 3 черных точки, затем 556 белых, затем 10 черных и т.д.

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

Алгоритм компрессии выглядит так:

for(по всем строкам изображения) {
    Преобразуем строку в набор длин серий;
    for(по всем сериям) {
        if(серия белая) {
            L= длина серии;
            while(L > 2623) { // 2623=2560+63
                L=L-2560;
                ЗаписатьБелыйКодДля(2560);
            }
            if(L > 63) {
                L2=МаксимальныйСостКодМеньшеL(L);
                L=L-L2;
                ЗаписатьБелыйКодДля(L2);
            }
            ЗаписатьБелыйКодДля(L);
            //Это всегда код завершения
        }
        else {
            [Код аналогичный белой серии,
            с той разницей, что записываются
            черные коды]
        }
    }
    // Окончание строки изображения
}

Поскольку черные и белые серии чередуются, то реально код для белой и код для черной серии будут работать попеременно.

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

((<Б-2560>)*[<Б-сст.>]<Б-зв.>(<Ч-2560>)*[<Ч-сст.>]<Ч-зв.>)+

[(<Б-2560>)*[<Б-сст.>]<Б-зв.>]

Где ()* — повтор 0 или более раз, ()+.— повтор 1 или более раз, [] — включение 1 или 0 раз.

Для приведенного ранее примера: 0, 3, 556, 10... алгоритм сформирует следующий код: <Б-0><Ч-3><Б-512><Б-44><Ч-10>, или, согласно таблице, 001101011001100101001011010000100 (разные коды в потоке выделены для удобства). Этот код обладает свойством префиксных кодов и легко может быть свернут обратно в последовательность длин серий. Легко подсчитать, что для приведенной строки в 569 бит мы получили код длиной в 33 бита, т.е. коэффициент сжатия составляет примерно 17 раз.

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

Изображение, для которого очень выгодно применение алгоритма CCITT-3. (Большие области заполнены одним цветом).

Изображение, для которого менее выгодно применение алгоритма CCITT-3. (Меньше областей, заполненных одним цветом. Много коротких “черных” и “белых” серий).

Заметим, что единственное “сложное” выражение в нашем алгоритме: L2=МаксимальныйДопКодМеньшеL(L) — на практике работает очень просто: L2=(L>>6)*64, где >> — побитовый сдвиг L влево на 6 битов (можно сделать то же самое за одну побитовую операцию & — логическое И).

Упражнение: Дана строка изображения, записанная в виде длин серий — 442, 2, 56, 3, 23, 3, 104, 1, 94, 1, 231, размером 120 байт ((442+2+..+231)/8). Подсчитать коэффициент компрессии этой строки алгоритмом CCITT Group 3.

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

Таблица кодов завершения:

Длина 
серии
Код белой 
подстроки
Код черной 
подстроки
  Длина 
серии
Код белой 
подстроки
Код черной 
подстроки
0 00110101 0000110111   32 00011011 000001101010
1 00111 010   33 00010010 000001101011
2 0111 11   34 00010011 000011010010
3 1000 10   35 00010100 000011010011
4 1011 011   36 00010101 000011010100
5 1100 0011   37 00010110 000011010101
6 1110 0010   38 00010111 000011010110
7 1111 00011   39 00101000 000011010111
8 10011 000101   40 00101001 000001101100
9 10100 000100   41 00101010 000001101101
10 00111 0000100   42 00101011 000011011010
11 01000 0000101   43 00101100 000011011011
12 001000 0000111   44 00101101 000001010100
13 000011 00000100   45 00000100 000001010101
14 110100 00000111   46 00000101 000001010110
15 110101 000011000   47 00001010 000001010111
16 101010 0000010111   48 00001011 000001100100
17 101011 0000011000   49 01010010 000001100101
18 0100111 0000001000   50 01010011 000001010010
19 0001100 00001100111   51 01010100 000001010011
20 0001000 00001101000   52 01010101 000000100100
21 0010111 00001101100   53 00100100 000000110111
22 0000011 00000110111   54 00100101 000000111000
23 0000100 00000101000   55 01011000 000000100111
24 0101000 00000010111   56 01011001 000000101000
25 0101011 00000011000   57 01011010 000001011000
26 0010011 000011001010   58 01011011 000001011001
27 0100100 000011001011   59 01001010 000000101011
28 0011000 000011001100   60 01001011 000000101100
29 00000010 000011001101   61 00110010 000001011010
30 00000011 000001101000   62 00110011 000001100110
31 00011010 000001101001   63 00110100 000001100111

Таблица составных кодов:


Длина 
серии
Код белой 
подстроки
Код черной 
подстроки
  Длина
серии
Код белой 
подстроки
Код черной 
подстроки
64 11011 0000001111   1344 011011010 0000001010011
128 10010 000011001000   1408 011011011 0000001010100
192 01011 000011001001   1472 010011000 0000001010101
256 0110111 000001011011   1536 010011001 0000001011010
320 00110110 000000110011   1600 010011010 0000001011011
384 00110111 000000110100   1664 011000 0000001100100
448 01100100 000000110101   1728 010011011 0000001100101
512 01100101 0000001101100   1792 00000001000
совп. с белой 
576 01101000 0000001101101   1856 00000001100
— // —
640 01100111 0000001001010   1920 00000001101
— // —
704 011001100 0000001001011   1984 000000010010
— // —
768 011001101 0000001001100   2048 000000010011
— // —
832 011010010 0000001001101   2112 000000010100
— // —
896 011010011 0000001110010   2176 000000010101
— // —
960 011010100 0000001110011   2240 000000010110
— // —
1024 011010101 0000001110100   2304 000000010111
— // —
1088 011010110 0000001110101   2368 000000011100
— // —
1152 011010111 0000001110110   2432 000000011101
— // —
1216 011011000 0000001110111   2496 000000011110
— // —
1280 011011001 0000001010010   2560 000000011111
— // —
Если в одном столбце встретятся два числа с одинаковым префиксом, то это опечатка.

Этот алгоритм реализован в формате TIFF.

Характеристики алгоритма CCITT Group 3

Коэффициенты компрессии: лучший коэффициент стремится в пределе к 213.(3), средний 2, в худшем случае увеличивает файл в 5 раз.

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

Симметричность: Близка к 1.

Характерные особенности: Данный алгоритм чрезвычайно прост в реализации, быстр и может быть легко реализован аппаратно.


JBIG

Алгоритм разработан группой экспертов ISO (Joint Bi-level Experts Group) специально для сжатия однобитных черно-белых изображений [5]. Например, факсов или отсканированных документов. В принципе, может применяться и к 2-х, и к 4-х битовым картинкам. При этом алгоритм разбивает их на отдельные битовые плоскости. JBIG позволяет управлять такими параметрами, как порядок разбиения изображения на битовые плоскости, ширина полос в изображении, уровни масштабирования. Последняя возможность позволяет легко ориентироваться в базе больших по размерам изображений, просматривая сначала их уменьшенные копии. Настраивая эти параметры, можно использовать описанный выше эффект “огрубленного изображения” при получении изображения по сети или по любому другому каналу, пропускная способность которого мала по сравнению с возможностями процессора. Распаковываться изображение на экране будет постепенно, как бы медленно “проявляясь”. При этом человек начинает анализировать картинку задолго до конца процесса разархивации.

Алгоритм построен на базе Q-кодировщика [6], патентом на который владеет IBM. Q-кодер, так же как и алгоритм Хаффмана, использует для чаще появляющихся символов короткие цепочки, а для реже появляющихся — длинные. Однако, в отличие от него, в алгоритме используются и последовательности символов.


Lossless JPEG

Этот алгоритм разработан группой экспертов в области фотографии (Joint Photographic Expert Group). В отличие от JBIG, Lossless JPEG ориентирован на полноцветные 24-битные или 8-битные в градациях серого изображения без палитры. Он представляет собой специальную реализацию JPEG без потерь. Коэффициенты сжатия: 20, 2, 1. Lossless JPEG рекомендуется применять в тех приложениях, где необходимо побитовое соответствие исходного и декомпрессированного изображений. Подробнее об алгоритме сжатия JPEG см. следующий раздел.


Заключение

Попробуем на этом этапе сделать некоторые обобщения. С одной стороны, приведенные выше алгоритмы достаточно универсальны и покрывают все типы изображений, с другой — у них, по сегодняшним меркам, слишком маленький коэффициент архивации. Используя один из алгоритмов сжатия без потерь, можно обеспечить архивацию изображения примерно в два раза. В то же время алгоритмы сжатия с потерями оперируют с коэффициентами 10-200 раз. Помимо возможности модификации изображения, одна из основных причин подобной разницы заключается в том, что традиционные алгоритмы ориентированы на работу с цепочкой. Они не учитывают, так называемую, “когерентность областей” в изображениях. Идея когерентности областей заключается в малом изменении цвета и структуры на небольшом участке изображения. Все алгоритмы, о которых речь пойдет ниже, были созданы позднее специально для сжатия графики и используют эту идею.

Справедливости ради следует отметить, что и в классических алгоритмах можно использовать идею когерентности. Существуют алгоритмы обхода изображения по “фрактальной” кривой, при работе которых оно также вытягивается в цепочку; но за счет того, что кривая обегает области изображения по сложной траектории, участки близких цветов в получающейся цепочке удлиняются.

Вопросы для самопроверки

  1. На какой класс изображений ориентирован алгоритм RLE?
  2. Приведите два примера “плохих” изображений для первого варианта алгоритма RLE, для которых файл максимально увеличится в размере.
  3. На какой класс изображений ориентирован алгоритм CCITT G-3?
  4. Приведите пример “плохого” изображения для алгоритма CCITT G-3, для которого файл максимально увеличится в размере. (Приведенный в характеристиках алгоритма ответ не является полным, поскольку требует более “умной” реализации алгоритма.)
  5. Приведите пример “плохого” изображения для алгоритма Хаффмана.
  6. Сравните алгоритмы сжатия изображений без потерь.
  7. В чем заключается идея когерентности областей?
Вы можете не портить глаза (и сделать приятное авторам), если купите бумажный вариант книги! Заказать его можно, например, в магазине Озон.

Книга в формате PDF (Acrobat Reader): Внимание! Выложенный на странице HTML вариант раздела 2 не полностью соответствует тексту книги. По возможности пользуйтесь PDF вариантом.

Обнаруженные ошибки

Раздел 1. МЕТОДЫ СЖАТИЯ БЕЗ ПОТЕРЬ
  • Глава 1. Кодирование источников данных без памяти
    • Разделение мантисс и экспонент
    • Канонический алгоритм Хаффмана
    • Арифметическое сжатие
    • Нумерующее кодирование
    • Векторное квантование
  • Глава 2. Кодирование источников данных типа "аналоговый сигнал"
    • Линейно-предсказывающее кодирование
    • Субполосное кодирование
  • Глава 3. Словарные методы сжатия данных
    • Идея словарных методов
    • Классические алгоритмы Зива-Лемпела
    • Другие алгоритмы LZ
    • Формат Deflate
    • Пути улучшения сжатия для методов LZ
    • Архиваторы и компрессоры, использующие алгоритмы LZ
    • Вопросы для самопроверки
    • Литература
    • Список архиваторов и компрессоров
  • Глава 4. Методы контекстного моделирования
    • Классификация стратегий моделирования
    • Контекстное моделирование
    • Алгоритмы PPM
    • Оценка вероятности ухода
    • Обновление счетчиков символов
    • Повышение точности оценок в контекстных моделях высоких порядков
    • Различные способы повышения точности предсказания
    • PPM и PPM*
    • Достоинства и недостатки PPM
    • Компрессоры и архиваторы, использующие контекстное моделирование
    • Обзор классических алгоритмов контекстного моделирования
    • Сравнение алгоритмов контекстного моделирования
    • Другие методы контекстного моделирования
    • Вопросы для самопроверки
    • Литература
    • Список архиваторов и компрессоров
  • Глава 5. Преобразование Барроуза-Уилера
    • Введение
    • Преобразование Барроуза-Уилера
    • Методы, используемые совместно с BWT
    • Способы сжатия преобразованных с помощью BWT данных
    • Сортировка, используемая в BWT
    • Архиваторы, использующие BWT и ST
    • Заключение
    • Литература
  • Глава 6. Обобщенные методы сортирующих преобразований
    • Сортировка параллельных блоков
    • Фрагментирование
  • Глава 7. Предварительная обработка данных
    • Препроцессинг текстов
    • Препроцессинг нетекстовых данных
    • Вопросы для самопроверки
    • Литература
    • Выбор метода сжатия
Раздел 2. МЕТОДЫ СЖАТИЯ ИЗОБРАЖЕНИЙ Раздел 3. МЕТОДЫ СЖАТИЯ ВИДЕОДАННЫХ
  • Глава 1. Введение
    • Основные понятия
    • Требования приложений к алгоритму
    • Определение требований
    • Обзор стандартов
  • Глава 2. Базовые технологии сжатия видео
    • Описание алгоритма компрессии
    • Общая схема алгоритма
    • Использование векторов смещений блоков
    • Возможности по распараллеливанию
    • Другие пути повышения степени сжатия
  • Глава 3. Стандарты сжатия видео
    • Motion-JPEG
    • MPEG-1
    • H.261
    • H.263
    • MPEG-2
    • MPEG-4
    • Сравнение стандартов
    • Вопросы для самопроверки
  • Литература
  • Ссылки на программы и реализации алгоритмов
  • Указатель терминов

Вы можете не портить глаза (и сделать приятное авторам), если купите бумажный вариант книги! Заказать его можно, например, в магазине Озон.

Книга в формате PDF (Acrobat Reader): Внимание! Выложенный на странице HTML вариант раздела 2 не полностью соответствует тексту книги. По возможности пользуйтесь PDF вариантом.

Обнаруженные ошибки