Алгоритмы архивации без потерь

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

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% поднять степень компрессии (рис. 5.5):

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

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

На практике для хранения таблицы используется такое же быстрое, как в случае списков, но более компактное по памяти решение - хэш-таблица. Таблица состоит из 8192 (2¹³) элементов. Каждый элемент содержит <код предыдущей подстроки; добавленный символ; код этой строки>. Ключ для поиска длиной в 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-битные коды), мы получим лучшую степень сжатия.

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

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

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

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

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

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

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

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

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

Каждая строка изображения сжимается независимо. Мы считаем, что в нашем изображении существенно преобладает белый цвет, и все строки изображения начинаются с белой точки. Если строка начинается с черной точки, то мы считаем, что строка начинается белой серией с длиной 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>, или, согласно таблице, 00110101 10 0110010100101101 0000100 (разные коды в потоке выделены для удобства). Этот код обладает свойством префиксных кодов и легко может быть свернут обратно в последовательность длин серий. Легко подсчитать, что для приведенной строки в 569 бит мы получили код длиной в 33 бита, т.е. степень сжатия составляет примерно 17 раз.

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

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

Таблица кодов завершения (табл. 5.1)

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

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

JBIG

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

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

Lossless JPEG

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

Заключение

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

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

Вопросы для самоконтроля