Алгоритмические основы растровой графики

Алгоритмы сжатия изображений без потерь

Разбить на страницы
Показывать лекцию целиком

13.1. Необходимость сжатия изображений

Типичное изображение, полученное цифровой фотокамерой, имеет разрешение порядка 3000x2000, т.е. около 6 мегапикселей; для передачи цвета обычно используется 24 бита на пиксель. Таким образом, объем исходных данных составляет порядка 17 мегабайт. Для профессиональных устройств ввода изображений размер получаемого растра может быть значительно больше, а глубина цвета - достигать 48 бит на пиксель (см. лекцию 2). Соответственно, размер одного изображения может быть больше 200 мегабайт. Поэтому весьма актуальными являются алгоритмы сжатия изображений, или, иными словами, алгоритмы, которые позволяют уменьшить объем данных, представляющих изображение.

Существуют два основных класса алгоритмов:

  • A называется алгоритмом сжатия без потерь (англ. lossless compression), если существует алгоритм A-1 (обратный к A ) такой, что для любого изображения I A(I) = I1 и A-1(I1) = I. Изображение I задано как множество значений атрибутов пикселей; после применения к I алгоритма A получаем набор данных I1. Сжатие без потерь применяется в таких графических форматах представления изображений, как: GIF, PCX, PNG, TGA, TIFFВообще говоря, данный формат также поддерживает сжатие с потерями., множество собственных форматов от производителей цифровых фотокамер, и т.д.);
  • A называется алгоритмом сжатия c потерями (англ. lossy compression), если он не обеспечивает возможность точного восстановления исходного изображения. Парный к A алгоритм, обеспечивающий примерное восстановление, будем обозначать как A*: для изображения I A(I) = I1, A*(I1) = I2 и при этом полученное восстановленное изображение I2 не обязательно точно совпадает с I. Пара A, A* подбирается так, чтобы обеспечить большие коэффициенты сжатия и тем не менее сохранить визуальное качество, т.е. добиться минимальной разницы в восприятии между I и I2. Сжатие с потерями применяется в следующих графических форматах: JPEG, JPEG2000 и т.д.
    •

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

    13.2. Несуществование идеального алгоритма

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

    Утверждение 13.2.1. Не существует алгоритма, сжимающего без потерь любой набор данных.

    Существует 2N последовательностей размера N битов $$\left\{I_k \right\}_{k=1}^{2^N}$$ (будем рассматривать бит как минимальный носитель информации). Пусть найдется алгоритм A такой, что $$\forall k = 1, ..., 2^N, |A(I_k)| = M_k < |I_k|$$, где |I| - объем данных (длина последовательности). Пусть M = max Mk, тогда M < N. Существует 21 + 22 + ... + 2M последовательностей длины, меньшей или равной M. Но 21+22+...+2M = 2M+1-2 < 2N. Противоречие.

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

    13.3. Алгоритмы кодирования длины повторения (RLE)

    Этот тип алгоритмов (алгоритмы кодирования длины повторенияВ литературе часто встречается и другое название - групповое кодирование. ( RLEангл. Run Length Encoding )) базируется на простейшем принципе: будем заменять повторяющиеся группы элементов исходной последовательности на пару (количество, элемент), либо только на количество.

    RLE - битовый уровень

    Будем рассматривать исходные данные на уровне последовательности битов; например, представляющих черно-белое изображение. Подряд обычно идет несколько 0 или 1, и можно помнить лишь количество идущих подряд одинаковых цифр. Т.е. последовательности 0000 11111 000 11111111111 соответствует набор чисел количеств повторений 4 5 3 11. Возникает следующий нюанс: числа, обозначающие количество повторений, также надо кодировать битами. Можно считать, что каждое число повторений изменяется от 0 до 7 (т.е. можно закодировать ровно тремя битами), тогда последовательности 11111111111 можно сопоставить числа 7 0 4, т.е. 7 единиц, 0 нулей, 4 единицы. Для примера, последовательность, состоящая из 21 единицы, 21 нуля, 3 единиц и 7 нулей закодируется так: 111 000 111 000 111 111 000 111 000 111 011 111, т.е. из исходной последовательности, которая имеет длину 51 бит, получили последовательность длиной 36 бит.

    Идея этого метода используется при передаче факсов.

    RLE - байтовый уровень

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

    Будем разбивать входной поток на байты (буквы) и кодировать повторяющиеся буквы парой (количество, буква).

    Т.е. AABBBCDAA кодируем (2A) (3B) (1C) (1D) (2A). Однако могут встречаться длинные отрезки данных, где ничего не повторяется, а мы кодируем каждую букву парой (цифра, буква).

    Пусть у нас есть фиксированное число (буква) M (от 0 до 255 ). Тогда одиночную букву $$S \le M$$ можно закодировать ею самою, - выход = S, а если букв несколько или $$S : M < S \le 255$$, то выход = CS, где C > M, а C - M - количество идущих подряд букв S. Для примера приведем только алгоритм декодирования.

    // M - фиксированная граница
// считываем символы последовательно из входного потока
// in - вход - сжатая последовательность
// out - выход - разжатая последовательность
while( in.Read( c ) )
{
      if( c > M )
     {    // случай счетчика
           n = c - M;
           in.Read( c );
           for (i = 0;  i < n;  i++)
                 out.Write( c );
     }
     else // случай просто символа
          out.Write( c );
}

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

    Такая модификация данного алгоритма используется в формате PCX. Однако модификации данного алгоритма редко используются сами по себе, т.к. подкласс последовательностей, на которых данный алгоритм эффективен, относительно узок. Модификации алгоритма используются как одна из стадий конвейера сжатия (например в формате JPEG, см. раздел 14.4).

    13.4. Словарные алгоритмы

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

    Алгоритм LZ77

    Данный алгоритм (алгоритм LZ77Назван по именам авторов Абрахама Лемпеля (Abraham Lempel) и Якоба Зива (Jacob Ziv). Опубликован в 1977 году. ) был одним из первых, использующих словарь [55]. В качестве словаря используются N последних уже закодированных элементов последовательности. В процессе сжатия словарь-подпоследовательность перемещается ("скользит") по входящей последовательности. Цепочка элементов на выходе кодируется следующим образом: положение совпадающей части обрабатываемой цепочки элементов в словаре - смещение (относительно текущей позиции), длина, первый элемент, следующий за совпавшей частью цепочки. Длина цепочки совпадения ограничивается сверху числом n. Соответственно, задача состоит в нахождении наибольшей цепочки из словаря, совпадающей с обрабатываемой последовательностью. Если же совпадений нет, то записывается нулевое смещение, единичная длина и только первый элемент незакодированной последовательности - {0, 1, e}.

    Описанная выше схема кодирования приводит к понятию скользящего окна (англ. sliding window), состоящего из двух частей:

  • подпоследовательность уже закодированных элементов длины N - словарь - буфер поиска (англ. search buffer );
  • подпоследовательность длины n из цепочки элементов, для которой будет произведена попытка поиска совпадения - буфер предварительного просмотра (англ. look-ahead buffer).
    •

    В терминах скользящего окна алгоритм сжатия описывается так: если e1, . . . , ei - уже закодированная подпоследовательность, то ei-N+1, . . . , ei - суть словарь или буфер поиска, а ei+1, . . . , ei+n - буфер предварительного просмотра. Аналогично, задача состоит в поиске наибольшей цепочки элементов из буфера предварительного просмотра, начиная с элемента ei+1, совпадающей с цепочкой из буфера поиска - эта цепочка может начинаться с любого элемента $$e_k : i - N + 1 \le k \le i$$ и заканчиваться любым элементом $$e_l : k \le l \le i + n$$, т.е. выходить за пределы буфера поиска, вторгаясь в буфер предварительного просмотра. Естественно, что выходить за пределы скользящего окна нельзя. Пусть в скользящем окне найдена максимальная по длине совпавшая цепочка элементов ei-p, . . . , ei+q, тогда она будет закодирована следующим образом: {p+1, q+p+1, ei+p+q+2} - смещение относительно начала буфера предварительного просмотра (ei+1), длина совпавшей цепочки, элемент, следующий за совпавшей цепочкой из буфера предварительного просмотра. Если в результате поиска найдено два совпадения с одинаковой длиной, то выбирается ближайшее к началу буфера предварительного просмотра. После этого скользящее окно смещается на p + q + 2 элементов вперед, и процедура поиска повторяется.

    Выбор чисел N и n является отдельной важной проблемой, т.к. чем больше N и n, тем больше места требуется для хранения значений смещения и длины. Естественно, что время работы алгоритма также возрастает с ростом N и n. Отметим, что обычно N и n различаются на порядок.

    Приведем пример сжатия данным алгоритмом. Сожмем строку "TOBEORNOTTOBE" с параметрами N = 10 и n = 3:

    шаг скользящее окно макс. совпавшая цепочка выход
    1 ""+"TOB" T 0,1,T
    2 "T"+"OBE" O 0,1,O
    3 "TO"+"BEO" B 0,1,B
    4 "TOB"+"EOR" E 0,1,E
    5 "TOBE"+"ORN" O 3,1,R
    6 "TOBEOR"+"NOT" N 0,1,N
    7 "TOBEORN"+"OTT" O 3,1,T
    8 "TOBEORNOT"+"TOBE" TOB 9,3,E

    Если выделить для хранения смещения 4 бита, длины - 2 бита, а элементов - 8 бит, то длина закодированной последовательности (без учета обозначения конца последовательности) составит 4 x 8 + 2 x 8 + 8 x 8 = 112 бит, а исходной - 102 бита. В данном случае мы не сжали последовательность, а, наоборот, увеличили избыточность представления. Это связано с тем, что длина последовательности слишком мала для такого алгоритма. Но, например, рисунок кодового дерева Хаффмена на рис. 13.1, занимающий 420 килобайт дискового пространства, после сжатия имеет размер около 310 килобайт.

    Ниже приведен псевдокод алгоритма сжатия.

    // M - фиксированная граница
// считываем символы последовательно из входного потока
// in - вход - сжатая последовательность
// n - максимальная длина цепочки
// pos - положение в словаре, len - длина цепочки
// nelem - элемент за цепочкой, str - найденная цепочка
// in - вход, out - выход
// SlideWindow - буфер поиска
while( !in.EOF() ) //пока есть данные
{
     // ищем максимальное совпадение и его параметры
     SlideWindow.FindBestMatch( in, n, pos, len, nelem );
     // пишем выход: смещение, длина, элемент
     out.Write( pos );
     out.Write( len );
     out.Write( nelem );
     // сдвинем скользящее окно на len + 1 элементов
     SlideWindow.Move( in, len + 1 );
}

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

    Видно, что процесс декодирования значительно проще с вычислительной точки зрения.

    // n - максимальная длина цепочки
// pos - положение в словаре, len - длина цепочки
// nelem - элемент за цепочкой, str - найденная цепочка
// in - вход, out - выход
// Dict - словарь

while( !in.EOF() ) //пока есть данные
{
     in.Read( pos );
     in.Read( len );
     in.Read( nelem );
     if( pos == 0 )
     { //новый отдельный символ
          //удаляем из словаря первый (дальний) один элемент
          Dict.Remove( 1 );
          //добавляем в словарь элемент
          Dict.Add( nelem );
          out.Write( nelem );
     }
     else
     {
          //скопируем соответствующую строку из словаря
          str = Dict.Get( pos, len );
          //удалим из словаря len + 1 элементов
          Dict.Remove( len + 1 );
          //Добавляем в словарь цепочку
          Dict.Add( str + nelem );
          out.Write( str + nelem );
     }
}

    Данный алгоритм является родоначальником целого семейства алгоритмов, и сам по себе в изначальном виде практически не используется. К его достоинствам можно отнести приличную степень сжатия на достаточно больших последовательностях, быструю распаковку, а также отсутствие патентадокумент, обеспечивающий исключительное право эксплуатировать изобретение в течение известного времени (обычно 15-20 лет) на алгоритм. К недостаткам относят медленную скорость сжатия, а также меньшую, чем у альтернативных алгоритмов, степень сжатия (модификации алгоритма борются с этим недостатком). Сочетание алгоритмов Хаффмена (Huffman) (см. раздел 13.5) и LZ77 называют методом DEFLATEТак называется сжатие, а разжатие называется INFLATE (англ. DEFLATE - сдувать, INFLATE - надувать).. Метод DEFLATE используется в графическом формате PNG, а также в универсальном формате сжатия данных ZIP.

    Алгоритм LZW

    Данный алгоритм (алгоритм LZWАлгоритм назван по имени автора Терри Уэлч (Terry Welch) и названия исходного алгоритма LZ78 (также от имен Лемпеля и Зива). Он был опубликован в 1984 году. ) является модификацией другого метода от Абрахама Лемпеля (Abraham Lempel) и Якоба Зива (Jacob Ziv) - LZ78 [56]. Автор модификации - Терри Уэлч (Terry Welch) [51]. Словарь в данном алгоритме представляет собой таблицу, которая заполняется цепочками элементов по мере работы алгоритма. Причем во время декодирования словарь будет построен автоматически, следовательно, нет нужды хранить его вместе со сжатой последовательностью. Обычно таблица инициализируется так, что первые строчки заполнены всеми различными цепочками из одного элемента. В процессе сжатия отыскивается наиболее длинная цепочка, уже записанная в словарь. Каждый раз, когда новая цепочка элементов не найдена в словаре, она добавляется в словарь; при этом записывается код цепочки, для которой есть совпадение со словарем. В теории на размер таблицы не накладывается ограничений, однако ограничение на размер позволяет улучшить степень сжатия, т.к. накапливаются ненужные (возможно, более не встречающиеся) цепочки. Чем больше вхождений имеет таблица, тем больше информации нужно выделять для хранения кодов. Соответственно резервируется специальный код, обозначающий очистку таблицы (точнее, приведение ее к исходному состоянию).

    // elem - элемент, chain - цепочка элементов
// in - вход, out - выход
// Table - таблица цепочек
// Table.Find - возвращает код, соответствующий
// цепочке (0 иначе)

str = ""; // пустая цепочка
while( in.Read( elem ) ) // пока есть данные
{
     // проверяем, есть ли уже в таблице новая цепочка
     if( Table.Find( chain + elem ) )
     {   // есть
          // сохраним новую цепочку для будущих проверок
          chain = chain + elem;
     }
     else
     {   // нет
          // запишем код, соответствующий chain
          out.Write( Table.Find( chain ) );
          // добавляем в словарь
          Table.Add( chain + elem );
          chain = elem;
     }
}
//остается одна необработанная цепочка
out.Write( Table.Find( chain ) );

    Рассмотрим пример сжатия алгоритмом. Будем, как и в предыдущем пункте, сжимать строку "TOBEORNOTTOBE". Пусть таблица инициализирована 256 символами кода ASCII. Предполагаем, что таблица может содержать 512 вхождений, т.е. нам требуется хранить 9 бит для каждого кода; для удобства пусть исходный словарь выглядит так:

    строка код
    T 1
    O 2
    B 3
    E 4
    R 5
    N 6
    ... ...
    СLT 256

    Здесь CLT означает "очистить (инициализировать) таблицу".

  • самая длинная совпавшая цепочка - "T", выход - {1}, словарь:
    строка код
    T 1
    O 2
    B 3
    E 4
    R 5
    N 6
    ... ...
    СLT 256
    TO 257
  • самая длинная совпавшая цепочка - "O", выход - {2}, словарь имеет следующий вид:
    строка код
    ... ...
    OB 258
    Далее подобным образом в выход записывается последовательность {3}{4}{1}{5}{6}{2}, после этого
  • самая длинная совпавшая цепочка - "T", выход: {1}, словарь имеет следующий вид:
    строка код
    ... ...
    TO 257
    OB 258
    BE 259
    EO 260
    OR 261
    RN 262
    NO 263
    OT 264
    TT 265
  • самая длинная совпавшая цепочка - "TO", выход: {257}, словарь имеет следующий вид:
    строка код
    ... ...
    TOB 266
  • самая длинная совпавшая цепочка - "BE", выход: {259}.
    •

    В результате закодированная последовательность выглядит так: {CLT}{1}{2}{3}{4}{1}{5}{6}{2}{1}{257}{259} (обычно в начале закодированной последовательности записывают код очистки таблицы для упрощения декодера). Полученная последовательность имеет объем 108 бит (без учета обозначения конца последовательности), что больше, чем исходная ( 104 бита). В данном случае это обусловлено слишком малой длиной исходной последовательности. Однако уже упоминавшийся рис. 13.1 кодового дерева Хаффмена сжимается при помощи данного алгоритма с исходных 420 килобайт до 290 килобайт.

    // chain - цепочка незакодированных элементов
// in - вход, out - выход
// lcode, code - элемент закодированной последовательности
// Table - таблица цепочек
// Table.Get(code) - возвращает цепочку с кодом code
// Table.IsOccupied(code) - есть ли запись в словаре для code
// Firstelem(chain) - возвращает первый элемент цепочки

while( in.Read( code ) ) // пока есть данные
{
     if( code == CLT ) //прочитан код очистки таблицы?
    {    // да
          Table.Init();
          If ( !in.Read(code) ) break; // больше нет информации
          out.Write( Table.Find( code ) );
          lcode = code;
     }
     else
     {   // нет
          if( Table.IsOccupied( code ) )
         {
               out.Write( Table.Find( code ) );
               // заполняем словарь новой цепочкой
               Table.Add( Table.Find( lcode ) +
                                Firstelem(Table.Find( code ) ) );
               lcode = code;
          }
          else
          {    // code не имеет соответствующей цепочки
               chain = Table.Find( lcode ) +
                               Firstelem( Table.Find( lcode ) );
               out.Write ( chain ); // запишем цепочку
               Table.Add ( chain ); // и добавим в таблицу
               lcode = code;
          }
     }
}

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

    К достоинствам алгоритма можно отнести высокую степень сжатия и достаточно высокую скорость как сжатия, так и разжатия. К недостаткам до недавнего времени относили патентную защищенность алгоритма, однако с середины 2004 года этот недостаток не актуален.

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

    13.5. Алгоритмы статистического кодирования

    Алгоритмы статистического кодирования ставят в соответствие каждому элементу последовательности код так, чтобы его длина соответствовала вероятности появления элемента. Таким образом, сжатие происходит за счет замены элементов исходной последовательности, имеющих одинаковые длины (каждый элемент занимает одинаковое количество бит), на элементы разной длины, пропорциональной отрицательному логарифму от вероятности, т.е. элементы, встречающиеся чаще, чем остальные, будут иметь код меньшей длины. Согласно теореме Шеннона о кодировании источника без помех [5], оптимальная длина такого кода есть - logs p, где p - вероятность появления элемента во входной последовательности, а s - основание системы счисления, в которой представляется закодированный элемент (код элемента).

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

    Алгоритм ХаффменаHuffman coding. Автор алгоритма - Давид Хаффмен (David A. Huffman). Опубликован в 1952 году. использует особый вид представления элементов - префиксный код. Префиксный код - это код переменной длины, обладающий особым свойством - свойством префикса: менее короткие коды не совпадают с префиксом (начальной частью) более длинных. Такой код позволяет осуществлять взаимно-однозначное кодирование. Соответственно, требуется построить способ сжатия, использующий префиксный код и при этом обеспечивающий максимально возможную степень сжатия. Формализуем задачу.

    Дано на входе:

    Алфавит A = {a1, . . . , an}.

    Множество P = {p1, . . . , pn} - распределение вероятностей появления или таблица количеств элементов из A, pi = Prob(ai), $$1 \le i \le n$$. Далее $$p_i \in P$$ будем называть весом ai.

    Необходимо на выходе:

    Код (алфавит) H(A, P) = {h1, . . . , hn} - набор кодов (далее бинарных), так что hi = Code(ai), $$1 \le i \le n$$.

    Задача:

    Пусть $$S(H) = \sum_{i=1}^n p_i \cdot l(h_i)$$, где l(hi) - длина кода hi. S(H) - взвешенная длина пути (пояснение данного термина см. ниже).

    Требуется, чтобы H было оптимально, т.е.$$S(H) \le S(T) \quad \forall T(A, P).$$

    Алгоритм Хаффмена является решением данной задачи [36], [37].

    Построение набора кодов обычно осуществляется с помощью так называемых кодовых деревьев. Предположим, что используются бинарные коды, тогда дерево будет бинарным (в общем случае степень ветвления зависит от основания системы счисления представления кодов). Терминальные узлы дерева содержат сам элемент алфавита, его вес, ссылку на родительский узел (впрочем, это зависит от конкретной реализации). Внутренние узлы содержат сумму весов своих узлов-потомков, ссылку на узлы-потомки и, возможно, ссылку на родительский узел. Ребрам дерева сопоставляются ноль и единица, для левых и правых соответственно. Полностью достроенное дерево имеет n терминальных узлов и n - 1 внутренних. Совершая проход от корня до терминального узла и выписывая по пути 0 и 1 для встречающихся ребер, получим код элемента в терминальном узле.

    Теперь стал понятен смысл названия S(H), т.к. длина кода l(hi) суть длина пути от корня до соответствующей терминальной вершины.

    Опишем алгоритм построения кодового дерева Хаффмена.

  • Создать n терминальных узлов по числу элементов в алфавите. В каждый узел записать соответствующие веса.
  • Создать родительский узел и соединить с ним два свободных (т.е. не имеющих родителей) узла с минимальными весами, записав в него сумму весов непосредственных потомков.
  • Если количество свободных узлов больше одного, то перейти к пункту 2. Иначе данный узел - корень дерева Хаффмена.
    •

    Процесс сжатия заключается в замене каждого элемента входной последовательности его кодом. Сожмем следующую строку "TOBEORNOTTOBE".

  • Составим таблицу весов:
    элемент алфавита T O B E R N
    вес 3 4 2 2 1 1
  • Построим дерево Хаффмена (см. рис. 13.1):
  • проинициализируем дерево терминальными узлами,
  • создадим родительский узел N1 для узлов элементов "N" и "R" с весом 2 ;
  • создадим родительский узел N2 для узла элемента "E" и узла N1 с весом 4 ;
  • создадим родительский узел N3 для узлов элементов "Т" и "B" с весом 5 ;
  • создадим родительский узел N4 для узла элемента "O" и узла N2 с весом 8 ;
  • создадим родительский узел N5 для узлов N3 и N4 c весом 13.
    •
  • Проведем кодирование. Составим для удобства таблицу кодов:
    элемент алфавита T O B E R N
    код 10 00 11 010 0110 0111
    Следовательно, получим последовательность "10 00 11 010 00 0110 0111 00 10 10 00 11 010".

    • Полученная последовательность имеет длину 32 бита. Исходная, если считать алфавитом набор ASCII - 104 бита, если считать алфавитом только набор "TOBERN" - 39 бит.

    (рис 13.1) Пример дерева Хаффмена.

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

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

    Приведенный выше алгоритм является двухпроходным. Первый проход по изображению создает таблицу количеств (весов) элементов, а во время второго происходит кодирование. Существуют реализации алгоритма с фиксированной таблицей (CCITT Group 3 - используется для передачи факсимильных изображений). Часто бывает, что нам неизвестно априорное распределение вероятностей элементов алфавита, т.к. нам не доступна вся последовательность сразу. Или, например, желательно избавиться от необходимости хранить таблицу весов для декодирования. Соответственно, были предложены адаптивные модификации алгоритма Хаффмена.

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

  • На первом шаге строится обычное дерево Хаффмена, считая, что веса всех вершин равны (такое дерево будет упорядоченным в указанном выше смысле).
  • При поступлении очередного элемента выполняется следующее:
  • элемент кодируется;
  • увеличивается значение веса в соответствующем терминальном узле;
  • увеличиваются значения весов в соответствующих вершинах по пути от этого узла к корню;
  • если после этого упорядоченность дерева нарушена, то:
  • для такого узла ( А ) среди соседей справа ищется крайний узел ( Б ), вес которого меньше;
  • узлы А и Б меняются местами, при этом веса узлов на путях от переставленных до корня корректируются соответствующим образом;
    •
  • если дерево опять неупорядочено, то вновь выполняется предыдущий шаг.

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

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

    13.6. Арифметическое кодирование

    Классические статистические алгоритмы сопоставляют элементу кодируемой последовательности некий код. Алгоритмы арифметического кодирования кодируют сразу цепочку элементов в число-дробь $$f (0 \le f < 1)$$ [40]. При этом учитывается распределение вероятностей появления элементов в последовательности.

    Пусть a1, . . . , an - алфавит, все возможные одноэлементные цепочки; p1, . . . , pn - вероятности появления элементов (весов) ( pj = Prob(aj) ). Разобьем полуинтервал [0, 1) на n непересекающихся полуинтервалов I1, . . . , In, соответствующих элементам a1, . . . , an, причем длина Ij пропорциональна pj.

    Далее строится кодирующая дробь: производится построение системы вложенных полуинтервалов так, что каждый последующий полуинтервал занимает в предыдущем место, соответствующее положению элемента в исходном разбиении полуинтервала [0, 1).

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

  • считывание очередного элемента;
  • выбор соответствующего полуинтервала из разбиения текущего полуинтервала (на первом шаге - [0, 1) ).
    •

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

    // elem - элемент
// in - вход, out - выход
// cleft - текущая левая граница полуинтервала
// cright - текущая правая граница полуинтервала
// interv - массив границ в исходном разбиении

cleft = 0;
cright = 1;
while( in.Read( elem ) ) // пока есть данные
{
     // длина текущего полуинтервала
     d = cright - cleft;
     // вычислим границы нового полуинтервала
     cright = cleft + d*interv[elem].right;
     cleft = cleft + d*interv[elem].left;
}
// ищем дробь внутри [left, right)
frac = Between( left, right );
out.Write( frac );

    Сожмем следующую последовательность "TOBEORNOTTOBE".

  • Составим таблицу весов:
    элемент алфавита B E N O R T
    вес 2 2 1 4 1 3
  • Построим разбиение полуинтервала
  • На входе T, тогда правая граница полуинтервала будет $$\frac{10}{13}$$, левая - 1, длина - $$\frac{3}{13}$$ ;
  • На входе O, тогда правая граница полуинтервала будет $$\frac{145}{169}$$, левая - $$\frac{157}{169}$$, длина - $$\frac{12}{169}$$ ;
  • На входе B, тогда правая граница полуинтервала будет $$\frac{1885}{2197}$$, левая - $$\frac{1909}{2197}$$, длина - $$\frac{24}{2197}$$ ;
  • На входе E, тогда правая граница полуинтервала будет $$\frac{24553}{28561}$$, левая - $$\frac{24601}{28561}$$, длина - $$\frac{48}{2197}$$ ;
  • ...
  • На входе E, тогда правая граница полуинтервала будет $$\frac{260680817264869}{302875106592253}$$, левая - $$\frac{260680817375461}{302875106592253}$$, длина - $$\frac{110592}{302875106592253}.$$
    •
  • Двоичную дробь можно взять такую: 0.1101110001010110000001000000101, т.к. двоичная запись границ итогового полуинтервала следующая: левая - 0.1101110001010110000001000000100111010011000101101, правая - 0.1101110001010110000001000000101101100100100100001.

    • Закодированная последовательность имеет длину 31 бит. Исходная, если считать алфавитом набор ASCII - 104 бита, если считать алфавитом только набор "TOBERN" - 39 бит.

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

    // elem - элемент, in - вход, out - выход
// interv - массив границ в исходном разбиении
// frac - кодирующая дробь
// cleft - текущая левая граница полуинтервала
// cright - текущая правая граница полуинтервала
// nelem - количество элементов, закодированное дробью

i = nelem;
in.Read( frac );
while( i > 0 ) // пока надо декодировать
{
     // ищем элемент по дроби и разбиению полуинтервала
     elem = GetElem( interv, frac );
     out.Write( elem );
     // вычислим границы полуинтервала
     cright = interv[elem].right;
     cleft = interv[elem].left;
     // длина полуинтервала
     d = cright - cleft;
     // преобразуем дробь
     x = (x - cleft) / d;
     // отметим обработку очередного элемента
     i--;
}

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

    Арифметическое кодирование является почти оптимальным видом кодирования, т.е. дает коды, почти равные длинам оптимальных кодов из теоремы Шеннона. Однако такая эффективность достигается за счет больших вычислительных затрат. Существуют модификации алгоритма, использующие только операции сдвига и сложения без деления и умножения для ускорения процесса кодирования. К сожалению, практически все такие модификации защищены патентами. Часть этих патентов уже имеют истекший срок действия, другая часть - нет. Таким образом, по мере истечения сроков патентов эффективные реализации модификаций алгоритма арифметического кодирования будут вытеснять алгоритм Хаффмена в сферах, где производительность не является критичным требованием.

    Страницы:

    13.1. Необходимость сжатия изображений

    Типичное изображение, полученное цифровой фотокамерой, имеет разрешение порядка 3000x2000, т.е. около 6 мегапикселей; для передачи цвета обычно используется 24 бита на пиксель. Таким образом, объем исходных данных составляет порядка 17 мегабайт. Для профессиональных устройств ввода изображений размер получаемого растра может быть значительно больше, а глубина цвета - достигать 48 бит на пиксель (см. лекцию 2). Соответственно, размер одного изображения может быть больше 200 мегабайт. Поэтому весьма актуальными являются алгоритмы сжатия изображений, или, иными словами, алгоритмы, которые позволяют уменьшить объем данных, представляющих изображение.

    Существуют два основных класса алгоритмов:

  • A называется алгоритмом сжатия без потерь (англ. lossless compression), если существует алгоритм A-1 (обратный к A ) такой, что для любого изображения I A(I) = I1 и A-1(I1) = I. Изображение I задано как множество значений атрибутов пикселей; после применения к I алгоритма A получаем набор данных I1. Сжатие без потерь применяется в таких графических форматах представления изображений, как: GIF, PCX, PNG, TGA, TIFFВообще говоря, данный формат также поддерживает сжатие с потерями., множество собственных форматов от производителей цифровых фотокамер, и т.д.);
  • A называется алгоритмом сжатия c потерями (англ. lossy compression), если он не обеспечивает возможность точного восстановления исходного изображения. Парный к A алгоритм, обеспечивающий примерное восстановление, будем обозначать как A*: для изображения I A(I) = I1, A*(I1) = I2 и при этом полученное восстановленное изображение I2 не обязательно точно совпадает с I. Пара A, A* подбирается так, чтобы обеспечить большие коэффициенты сжатия и тем не менее сохранить визуальное качество, т.е. добиться минимальной разницы в восприятии между I и I2. Сжатие с потерями применяется в следующих графических форматах: JPEG, JPEG2000 и т.д.
    •

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

    13.2. Несуществование идеального алгоритма

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

    Утверждение 13.2.1. Не существует алгоритма, сжимающего без потерь любой набор данных.

    Существует 2N последовательностей размера N битов $$\left\{I_k \right\}_{k=1}^{2^N}$$ (будем рассматривать бит как минимальный носитель информации). Пусть найдется алгоритм A такой, что $$\forall k = 1, ..., 2^N, |A(I_k)| = M_k < |I_k|$$, где |I| - объем данных (длина последовательности). Пусть M = max Mk, тогда M < N. Существует 21 + 22 + ... + 2M последовательностей длины, меньшей или равной M. Но 21+22+...+2M = 2M+1-2 < 2N. Противоречие.

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

    13.3. Алгоритмы кодирования длины повторения (RLE)

    Этот тип алгоритмов (алгоритмы кодирования длины повторенияВ литературе часто встречается и другое название - групповое кодирование. ( RLEангл. Run Length Encoding )) базируется на простейшем принципе: будем заменять повторяющиеся группы элементов исходной последовательности на пару (количество, элемент), либо только на количество.

    RLE - битовый уровень

    Будем рассматривать исходные данные на уровне последовательности битов; например, представляющих черно-белое изображение. Подряд обычно идет несколько 0 или 1, и можно помнить лишь количество идущих подряд одинаковых цифр. Т.е. последовательности 0000 11111 000 11111111111 соответствует набор чисел количеств повторений 4 5 3 11. Возникает следующий нюанс: числа, обозначающие количество повторений, также надо кодировать битами. Можно считать, что каждое число повторений изменяется от 0 до 7 (т.е. можно закодировать ровно тремя битами), тогда последовательности 11111111111 можно сопоставить числа 7 0 4, т.е. 7 единиц, 0 нулей, 4 единицы. Для примера, последовательность, состоящая из 21 единицы, 21 нуля, 3 единиц и 7 нулей закодируется так: 111 000 111 000 111 111 000 111 000 111 011 111, т.е. из исходной последовательности, которая имеет длину 51 бит, получили последовательность длиной 36 бит.

    Идея этого метода используется при передаче факсов.

    RLE - байтовый уровень

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

    Будем разбивать входной поток на байты (буквы) и кодировать повторяющиеся буквы парой (количество, буква).

    Т.е. AABBBCDAA кодируем (2A) (3B) (1C) (1D) (2A). Однако могут встречаться длинные отрезки данных, где ничего не повторяется, а мы кодируем каждую букву парой (цифра, буква).

    Пусть у нас есть фиксированное число (буква) M (от 0 до 255 ). Тогда одиночную букву $$S \le M$$ можно закодировать ею самою, - выход = S, а если букв несколько или $$S : M < S \le 255$$, то выход = CS, где C > M, а C - M - количество идущих подряд букв S. Для примера приведем только алгоритм декодирования.

    // M - фиксированная граница
// считываем символы последовательно из входного потока
// in - вход - сжатая последовательность
// out - выход - разжатая последовательность
while( in.Read( c ) )
{
      if( c > M )
     {    // случай счетчика
           n = c - M;
           in.Read( c );
           for (i = 0;  i < n;  i++)
                 out.Write( c );
     }
     else // случай просто символа
          out.Write( c );
}

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

    Такая модификация данного алгоритма используется в формате PCX. Однако модификации данного алгоритма редко используются сами по себе, т.к. подкласс последовательностей, на которых данный алгоритм эффективен, относительно узок. Модификации алгоритма используются как одна из стадий конвейера сжатия (например в формате JPEG, см. раздел 14.4).

    13.4. Словарные алгоритмы

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

    Алгоритм LZ77

    Данный алгоритм (алгоритм LZ77Назван по именам авторов Абрахама Лемпеля (Abraham Lempel) и Якоба Зива (Jacob Ziv). Опубликован в 1977 году. ) был одним из первых, использующих словарь [55]. В качестве словаря используются N последних уже закодированных элементов последовательности. В процессе сжатия словарь-подпоследовательность перемещается ("скользит") по входящей последовательности. Цепочка элементов на выходе кодируется следующим образом: положение совпадающей части обрабатываемой цепочки элементов в словаре - смещение (относительно текущей позиции), длина, первый элемент, следующий за совпавшей частью цепочки. Длина цепочки совпадения ограничивается сверху числом n. Соответственно, задача состоит в нахождении наибольшей цепочки из словаря, совпадающей с обрабатываемой последовательностью. Если же совпадений нет, то записывается нулевое смещение, единичная длина и только первый элемент незакодированной последовательности - {0, 1, e}.

    Описанная выше схема кодирования приводит к понятию скользящего окна (англ. sliding window), состоящего из двух частей:

  • подпоследовательность уже закодированных элементов длины N - словарь - буфер поиска (англ. search buffer );
  • подпоследовательность длины n из цепочки элементов, для которой будет произведена попытка поиска совпадения - буфер предварительного просмотра (англ. look-ahead buffer).
    •

    В терминах скользящего окна алгоритм сжатия описывается так: если e1, . . . , ei - уже закодированная подпоследовательность, то ei-N+1, . . . , ei - суть словарь или буфер поиска, а ei+1, . . . , ei+n - буфер предварительного просмотра. Аналогично, задача состоит в поиске наибольшей цепочки элементов из буфера предварительного просмотра, начиная с элемента ei+1, совпадающей с цепочкой из буфера поиска - эта цепочка может начинаться с любого элемента $$e_k : i - N + 1 \le k \le i$$ и заканчиваться любым элементом $$e_l : k \le l \le i + n$$, т.е. выходить за пределы буфера поиска, вторгаясь в буфер предварительного просмотра. Естественно, что выходить за пределы скользящего окна нельзя. Пусть в скользящем окне найдена максимальная по длине совпавшая цепочка элементов ei-p, . . . , ei+q, тогда она будет закодирована следующим образом: {p+1, q+p+1, ei+p+q+2} - смещение относительно начала буфера предварительного просмотра (ei+1), длина совпавшей цепочки, элемент, следующий за совпавшей цепочкой из буфера предварительного просмотра. Если в результате поиска найдено два совпадения с одинаковой длиной, то выбирается ближайшее к началу буфера предварительного просмотра. После этого скользящее окно смещается на p + q + 2 элементов вперед, и процедура поиска повторяется.

    Выбор чисел N и n является отдельной важной проблемой, т.к. чем больше N и n, тем больше места требуется для хранения значений смещения и длины. Естественно, что время работы алгоритма также возрастает с ростом N и n. Отметим, что обычно N и n различаются на порядок.

    Приведем пример сжатия данным алгоритмом. Сожмем строку "TOBEORNOTTOBE" с параметрами N = 10 и n = 3:

    шаг скользящее окно макс. совпавшая цепочка выход
    1 ""+"TOB" T 0,1,T
    2 "T"+"OBE" O 0,1,O
    3 "TO"+"BEO" B 0,1,B
    4 "TOB"+"EOR" E 0,1,E
    5 "TOBE"+"ORN" O 3,1,R
    6 "TOBEOR"+"NOT" N 0,1,N
    7 "TOBEORN"+"OTT" O 3,1,T
    8 "TOBEORNOT"+"TOBE" TOB 9,3,E

    Если выделить для хранения смещения 4 бита, длины - 2 бита, а элементов - 8 бит, то длина закодированной последовательности (без учета обозначения конца последовательности) составит 4 x 8 + 2 x 8 + 8 x 8 = 112 бит, а исходной - 102 бита. В данном случае мы не сжали последовательность, а, наоборот, увеличили избыточность представления. Это связано с тем, что длина последовательности слишком мала для такого алгоритма. Но, например, рисунок кодового дерева Хаффмена на рис. 13.1, занимающий 420 килобайт дискового пространства, после сжатия имеет размер около 310 килобайт.

    Ниже приведен псевдокод алгоритма сжатия.

    // M - фиксированная граница
// считываем символы последовательно из входного потока
// in - вход - сжатая последовательность
// n - максимальная длина цепочки
// pos - положение в словаре, len - длина цепочки
// nelem - элемент за цепочкой, str - найденная цепочка
// in - вход, out - выход
// SlideWindow - буфер поиска
while( !in.EOF() ) //пока есть данные
{
     // ищем максимальное совпадение и его параметры
     SlideWindow.FindBestMatch( in, n, pos, len, nelem );
     // пишем выход: смещение, длина, элемент
     out.Write( pos );
     out.Write( len );
     out.Write( nelem );
     // сдвинем скользящее окно на len + 1 элементов
     SlideWindow.Move( in, len + 1 );
}

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

    Видно, что процесс декодирования значительно проще с вычислительной точки зрения.

    // n - максимальная длина цепочки
// pos - положение в словаре, len - длина цепочки
// nelem - элемент за цепочкой, str - найденная цепочка
// in - вход, out - выход
// Dict - словарь

while( !in.EOF() ) //пока есть данные
{
     in.Read( pos );
     in.Read( len );
     in.Read( nelem );
     if( pos == 0 )
     { //новый отдельный символ
          //удаляем из словаря первый (дальний) один элемент
          Dict.Remove( 1 );
          //добавляем в словарь элемент
          Dict.Add( nelem );
          out.Write( nelem );
     }
     else
     {
          //скопируем соответствующую строку из словаря
          str = Dict.Get( pos, len );
          //удалим из словаря len + 1 элементов
          Dict.Remove( len + 1 );
          //Добавляем в словарь цепочку
          Dict.Add( str + nelem );
          out.Write( str + nelem );
     }
}

    Данный алгоритм является родоначальником целого семейства алгоритмов, и сам по себе в изначальном виде практически не используется. К его достоинствам можно отнести приличную степень сжатия на достаточно больших последовательностях, быструю распаковку, а также отсутствие патентадокумент, обеспечивающий исключительное право эксплуатировать изобретение в течение известного времени (обычно 15-20 лет) на алгоритм. К недостаткам относят медленную скорость сжатия, а также меньшую, чем у альтернативных алгоритмов, степень сжатия (модификации алгоритма борются с этим недостатком). Сочетание алгоритмов Хаффмена (Huffman) (см. раздел 13.5) и LZ77 называют методом DEFLATEТак называется сжатие, а разжатие называется INFLATE (англ. DEFLATE - сдувать, INFLATE - надувать).. Метод DEFLATE используется в графическом формате PNG, а также в универсальном формате сжатия данных ZIP.

    Алгоритм LZW

    Данный алгоритм (алгоритм LZWАлгоритм назван по имени автора Терри Уэлч (Terry Welch) и названия исходного алгоритма LZ78 (также от имен Лемпеля и Зива). Он был опубликован в 1984 году. ) является модификацией другого метода от Абрахама Лемпеля (Abraham Lempel) и Якоба Зива (Jacob Ziv) - LZ78 [56]. Автор модификации - Терри Уэлч (Terry Welch) [51]. Словарь в данном алгоритме представляет собой таблицу, которая заполняется цепочками элементов по мере работы алгоритма. Причем во время декодирования словарь будет построен автоматически, следовательно, нет нужды хранить его вместе со сжатой последовательностью. Обычно таблица инициализируется так, что первые строчки заполнены всеми различными цепочками из одного элемента. В процессе сжатия отыскивается наиболее длинная цепочка, уже записанная в словарь. Каждый раз, когда новая цепочка элементов не найдена в словаре, она добавляется в словарь; при этом записывается код цепочки, для которой есть совпадение со словарем. В теории на размер таблицы не накладывается ограничений, однако ограничение на размер позволяет улучшить степень сжатия, т.к. накапливаются ненужные (возможно, более не встречающиеся) цепочки. Чем больше вхождений имеет таблица, тем больше информации нужно выделять для хранения кодов. Соответственно резервируется специальный код, обозначающий очистку таблицы (точнее, приведение ее к исходному состоянию).

    // elem - элемент, chain - цепочка элементов
// in - вход, out - выход
// Table - таблица цепочек
// Table.Find - возвращает код, соответствующий
// цепочке (0 иначе)

str = ""; // пустая цепочка
while( in.Read( elem ) ) // пока есть данные
{
     // проверяем, есть ли уже в таблице новая цепочка
     if( Table.Find( chain + elem ) )
     {   // есть
          // сохраним новую цепочку для будущих проверок
          chain = chain + elem;
     }
     else
     {   // нет
          // запишем код, соответствующий chain
          out.Write( Table.Find( chain ) );
          // добавляем в словарь
          Table.Add( chain + elem );
          chain = elem;
     }
}
//остается одна необработанная цепочка
out.Write( Table.Find( chain ) );

    Рассмотрим пример сжатия алгоритмом. Будем, как и в предыдущем пункте, сжимать строку "TOBEORNOTTOBE". Пусть таблица инициализирована 256 символами кода ASCII. Предполагаем, что таблица может содержать 512 вхождений, т.е. нам требуется хранить 9 бит для каждого кода; для удобства пусть исходный словарь выглядит так:

    строка код
    T 1
    O 2
    B 3
    E 4
    R 5
    N 6
    ... ...
    СLT 256

    Здесь CLT означает "очистить (инициализировать) таблицу".

  • самая длинная совпавшая цепочка - "T", выход - {1}, словарь:
    строка код
    T 1
    O 2
    B 3
    E 4
    R 5
    N 6
    ... ...
    СLT 256
    TO 257
  • самая длинная совпавшая цепочка - "O", выход - {2}, словарь имеет следующий вид:
    строка код
    ... ...
    OB 258
    Далее подобным образом в выход записывается последовательность {3}{4}{1}{5}{6}{2}, после этого
  • самая длинная совпавшая цепочка - "T", выход: {1}, словарь имеет следующий вид:
    строка код
    ... ...
    TO 257
    OB 258
    BE 259
    EO 260
    OR 261
    RN 262
    NO 263
    OT 264
    TT 265
  • самая длинная совпавшая цепочка - "TO", выход: {257}, словарь имеет следующий вид:
    строка код
    ... ...
    TOB 266
  • самая длинная совпавшая цепочка - "BE", выход: {259}.
    •

    В результате закодированная последовательность выглядит так: {CLT}{1}{2}{3}{4}{1}{5}{6}{2}{1}{257}{259} (обычно в начале закодированной последовательности записывают код очистки таблицы для упрощения декодера). Полученная последовательность имеет объем 108 бит (без учета обозначения конца последовательности), что больше, чем исходная ( 104 бита). В данном случае это обусловлено слишком малой длиной исходной последовательности. Однако уже упоминавшийся рис. 13.1 кодового дерева Хаффмена сжимается при помощи данного алгоритма с исходных 420 килобайт до 290 килобайт.

    // chain - цепочка незакодированных элементов
// in - вход, out - выход
// lcode, code - элемент закодированной последовательности
// Table - таблица цепочек
// Table.Get(code) - возвращает цепочку с кодом code
// Table.IsOccupied(code) - есть ли запись в словаре для code
// Firstelem(chain) - возвращает первый элемент цепочки

while( in.Read( code ) ) // пока есть данные
{
     if( code == CLT ) //прочитан код очистки таблицы?
    {    // да
          Table.Init();
          If ( !in.Read(code) ) break; // больше нет информации
          out.Write( Table.Find( code ) );
          lcode = code;
     }
     else
     {   // нет
          if( Table.IsOccupied( code ) )
         {
               out.Write( Table.Find( code ) );
               // заполняем словарь новой цепочкой
               Table.Add( Table.Find( lcode ) +
                                Firstelem(Table.Find( code ) ) );
               lcode = code;
          }
          else
          {    // code не имеет соответствующей цепочки
               chain = Table.Find( lcode ) +
                               Firstelem( Table.Find( lcode ) );
               out.Write ( chain ); // запишем цепочку
               Table.Add ( chain ); // и добавим в таблицу
               lcode = code;
          }
     }
}

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

    К достоинствам алгоритма можно отнести высокую степень сжатия и достаточно высокую скорость как сжатия, так и разжатия. К недостаткам до недавнего времени относили патентную защищенность алгоритма, однако с середины 2004 года этот недостаток не актуален.

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

    13.5. Алгоритмы статистического кодирования

    Алгоритмы статистического кодирования ставят в соответствие каждому элементу последовательности код так, чтобы его длина соответствовала вероятности появления элемента. Таким образом, сжатие происходит за счет замены элементов исходной последовательности, имеющих одинаковые длины (каждый элемент занимает одинаковое количество бит), на элементы разной длины, пропорциональной отрицательному логарифму от вероятности, т.е. элементы, встречающиеся чаще, чем остальные, будут иметь код меньшей длины. Согласно теореме Шеннона о кодировании источника без помех [5], оптимальная длина такого кода есть - logs p, где p - вероятность появления элемента во входной последовательности, а s - основание системы счисления, в которой представляется закодированный элемент (код элемента).

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

    Алгоритм ХаффменаHuffman coding. Автор алгоритма - Давид Хаффмен (David A. Huffman). Опубликован в 1952 году. использует особый вид представления элементов - префиксный код. Префиксный код - это код переменной длины, обладающий особым свойством - свойством префикса: менее короткие коды не совпадают с префиксом (начальной частью) более длинных. Такой код позволяет осуществлять взаимно-однозначное кодирование. Соответственно, требуется построить способ сжатия, использующий префиксный код и при этом обеспечивающий максимально возможную степень сжатия. Формализуем задачу.

    Дано на входе:

    Алфавит A = {a1, . . . , an}.

    Множество P = {p1, . . . , pn} - распределение вероятностей появления или таблица количеств элементов из A, pi = Prob(ai), $$1 \le i \le n$$. Далее $$p_i \in P$$ будем называть весом ai.

    Необходимо на выходе:

    Код (алфавит) H(A, P) = {h1, . . . , hn} - набор кодов (далее бинарных), так что hi = Code(ai), $$1 \le i \le n$$.

    Задача:

    Пусть $$S(H) = \sum_{i=1}^n p_i \cdot l(h_i)$$, где l(hi) - длина кода hi. S(H) - взвешенная длина пути (пояснение данного термина см. ниже).

    Требуется, чтобы H было оптимально, т.е.$$S(H) \le S(T) \quad \forall T(A, P).$$

    Алгоритм Хаффмена является решением данной задачи [36], [37].

    Построение набора кодов обычно осуществляется с помощью так называемых кодовых деревьев. Предположим, что используются бинарные коды, тогда дерево будет бинарным (в общем случае степень ветвления зависит от основания системы счисления представления кодов). Терминальные узлы дерева содержат сам элемент алфавита, его вес, ссылку на родительский узел (впрочем, это зависит от конкретной реализации). Внутренние узлы содержат сумму весов своих узлов-потомков, ссылку на узлы-потомки и, возможно, ссылку на родительский узел. Ребрам дерева сопоставляются ноль и единица, для левых и правых соответственно. Полностью достроенное дерево имеет n терминальных узлов и n - 1 внутренних. Совершая проход от корня до терминального узла и выписывая по пути 0 и 1 для встречающихся ребер, получим код элемента в терминальном узле.

    Теперь стал понятен смысл названия S(H), т.к. длина кода l(hi) суть длина пути от корня до соответствующей терминальной вершины.

    Опишем алгоритм построения кодового дерева Хаффмена.

  • Создать n терминальных узлов по числу элементов в алфавите. В каждый узел записать соответствующие веса.
  • Создать родительский узел и соединить с ним два свободных (т.е. не имеющих родителей) узла с минимальными весами, записав в него сумму весов непосредственных потомков.
  • Если количество свободных узлов больше одного, то перейти к пункту 2. Иначе данный узел - корень дерева Хаффмена.
    •

    Процесс сжатия заключается в замене каждого элемента входной последовательности его кодом. Сожмем следующую строку "TOBEORNOTTOBE".

  • Составим таблицу весов:
    элемент алфавита T O B E R N
    вес 3 4 2 2 1 1
  • Построим дерево Хаффмена (см. рис. 13.1):
  • проинициализируем дерево терминальными узлами,
  • создадим родительский узел N1 для узлов элементов "N" и "R" с весом 2 ;
  • создадим родительский узел N2 для узла элемента "E" и узла N1 с весом 4 ;
  • создадим родительский узел N3 для узлов элементов "Т" и "B" с весом 5 ;
  • создадим родительский узел N4 для узла элемента "O" и узла N2 с весом 8 ;
  • создадим родительский узел N5 для узлов N3 и N4 c весом 13.
    •
  • Проведем кодирование. Составим для удобства таблицу кодов:
    элемент алфавита T O B E R N
    код 10 00 11 010 0110 0111
    Следовательно, получим последовательность "10 00 11 010 00 0110 0111 00 10 10 00 11 010".

    • Полученная последовательность имеет длину 32 бита. Исходная, если считать алфавитом набор ASCII - 104 бита, если считать алфавитом только набор "TOBERN" - 39 бит.

    (рис 13.1) Пример дерева Хаффмена.

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

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

    Приведенный выше алгоритм является двухпроходным. Первый проход по изображению создает таблицу количеств (весов) элементов, а во время второго происходит кодирование. Существуют реализации алгоритма с фиксированной таблицей (CCITT Group 3 - используется для передачи факсимильных изображений). Часто бывает, что нам неизвестно априорное распределение вероятностей элементов алфавита, т.к. нам не доступна вся последовательность сразу. Или, например, желательно избавиться от необходимости хранить таблицу весов для декодирования. Соответственно, были предложены адаптивные модификации алгоритма Хаффмена.

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

  • На первом шаге строится обычное дерево Хаффмена, считая, что веса всех вершин равны (такое дерево будет упорядоченным в указанном выше смысле).
  • При поступлении очередного элемента выполняется следующее:
  • элемент кодируется;
  • увеличивается значение веса в соответствующем терминальном узле;
  • увеличиваются значения весов в соответствующих вершинах по пути от этого узла к корню;
  • если после этого упорядоченность дерева нарушена, то:
  • для такого узла ( А ) среди соседей справа ищется крайний узел ( Б ), вес которого меньше;
  • узлы А и Б меняются местами, при этом веса узлов на путях от переставленных до корня корректируются соответствующим образом;
    •
  • если дерево опять неупорядочено, то вновь выполняется предыдущий шаг.

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

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

    13.6. Арифметическое кодирование

    Классические статистические алгоритмы сопоставляют элементу кодируемой последовательности некий код. Алгоритмы арифметического кодирования кодируют сразу цепочку элементов в число-дробь $$f (0 \le f < 1)$$ [40]. При этом учитывается распределение вероятностей появления элементов в последовательности.

    Пусть a1, . . . , an - алфавит, все возможные одноэлементные цепочки; p1, . . . , pn - вероятности появления элементов (весов) ( pj = Prob(aj) ). Разобьем полуинтервал [0, 1) на n непересекающихся полуинтервалов I1, . . . , In, соответствующих элементам a1, . . . , an, причем длина Ij пропорциональна pj.

    Далее строится кодирующая дробь: производится построение системы вложенных полуинтервалов так, что каждый последующий полуинтервал занимает в предыдущем место, соответствующее положению элемента в исходном разбиении полуинтервала [0, 1).

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

  • считывание очередного элемента;
  • выбор соответствующего полуинтервала из разбиения текущего полуинтервала (на первом шаге - [0, 1) ).
    •

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

    // elem - элемент
// in - вход, out - выход
// cleft - текущая левая граница полуинтервала
// cright - текущая правая граница полуинтервала
// interv - массив границ в исходном разбиении

cleft = 0;
cright = 1;
while( in.Read( elem ) ) // пока есть данные
{
     // длина текущего полуинтервала
     d = cright - cleft;
     // вычислим границы нового полуинтервала
     cright = cleft + d*interv[elem].right;
     cleft = cleft + d*interv[elem].left;
}
// ищем дробь внутри [left, right)
frac = Between( left, right );
out.Write( frac );

    Сожмем следующую последовательность "TOBEORNOTTOBE".

  • Составим таблицу весов:
    элемент алфавита B E N O R T
    вес 2 2 1 4 1 3
  • Построим разбиение полуинтервала
  • На входе T, тогда правая граница полуинтервала будет $$\frac{10}{13}$$, левая - 1, длина - $$\frac{3}{13}$$ ;
  • На входе O, тогда правая граница полуинтервала будет $$\frac{145}{169}$$, левая - $$\frac{157}{169}$$, длина - $$\frac{12}{169}$$ ;
  • На входе B, тогда правая граница полуинтервала будет $$\frac{1885}{2197}$$, левая - $$\frac{1909}{2197}$$, длина - $$\frac{24}{2197}$$ ;
  • На входе E, тогда правая граница полуинтервала будет $$\frac{24553}{28561}$$, левая - $$\frac{24601}{28561}$$, длина - $$\frac{48}{2197}$$ ;
  • ...
  • На входе E, тогда правая граница полуинтервала будет $$\frac{260680817264869}{302875106592253}$$, левая - $$\frac{260680817375461}{302875106592253}$$, длина - $$\frac{110592}{302875106592253}.$$
    •
  • Двоичную дробь можно взять такую: 0.1101110001010110000001000000101, т.к. двоичная запись границ итогового полуинтервала следующая: левая - 0.1101110001010110000001000000100111010011000101101, правая - 0.1101110001010110000001000000101101100100100100001.

    • Закодированная последовательность имеет длину 31 бит. Исходная, если считать алфавитом набор ASCII - 104 бита, если считать алфавитом только набор "TOBERN" - 39 бит.

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

    // elem - элемент, in - вход, out - выход
// interv - массив границ в исходном разбиении
// frac - кодирующая дробь
// cleft - текущая левая граница полуинтервала
// cright - текущая правая граница полуинтервала
// nelem - количество элементов, закодированное дробью

i = nelem;
in.Read( frac );
while( i > 0 ) // пока надо декодировать
{
     // ищем элемент по дроби и разбиению полуинтервала
     elem = GetElem( interv, frac );
     out.Write( elem );
     // вычислим границы полуинтервала
     cright = interv[elem].right;
     cleft = interv[elem].left;
     // длина полуинтервала
     d = cright - cleft;
     // преобразуем дробь
     x = (x - cleft) / d;
     // отметим обработку очередного элемента
     i--;
}

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

    Арифметическое кодирование является почти оптимальным видом кодирования, т.е. дает коды, почти равные длинам оптимальных кодов из теоремы Шеннона. Однако такая эффективность достигается за счет больших вычислительных затрат. Существуют модификации алгоритма, использующие только операции сдвига и сложения без деления и умножения для ускорения процесса кодирования. К сожалению, практически все такие модификации защищены патентами. Часть этих патентов уже имеют истекший срок действия, другая часть - нет. Таким образом, по мере истечения сроков патентов эффективные реализации модификаций алгоритма арифметического кодирования будут вытеснять алгоритм Хаффмена в сферах, где производительность не является критичным требованием.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^