Первая страница / Теория / Сжатие данных /

Сжатие изображений без потерь

Голосование: 5, 4

Введение

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

Классы изображений

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

  • Изображения с палитрой
  • Изображения без палитры

В первом случае в пикселях хранится номер цвета в палитре; во втором — значение цвета. Изображения могут быть цветными (в какой-то системе цветопредставления), а могут быть в градациях серого. В случае цветного изображения в пикселях хранится непосредственно информация о цвете. Например, для системы RGB в пикселях хранятся три значения насыщенности — для красной, зеленой и синей компонент цвета. Для изображения в градациях серого значение пикселя соответствует яркости точки.

Требования к алгоритмам сжатия

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

  • Высокая степень компрессии. Степенью компрессии называется отношение размера исходного файла к размеру сжатого.
  • Высокая скорость компрессии. Заметим, что данное требование чаще всего противоречит предыдущему. Интуитивно понятно, что чем больше времени будет производиться анализ изображения, тем лучше будет произведено сжатие.
  • Высокая скорость декомпрессии. Достаточно универсальное требование, то есть важное во многих приложениях. Стоит заметить, что существуют приложения, в которых данное требование не критично.
  • Возможность масштабировать изображение. Имеется в виду, насколько легко изменяются размеры изображения. Существуют алгоритмы, позволяющие изменять линейные размеры изображения во время процесса декомпрессии.
  • Возможность показывать изображение в низком разрешении, используя только начало изображения. Данное требование актуально при передаче изображений по сетям. В случае, когда пересылка изображения занимает достаточно большое время, возникает необходимость корректно показать так называемое «preview», передав только часть изображения. Такую возможность поддерживает формат GIF при чересстрочном просмотре.
  • Устойчивость к ошибкам. Данное требование означает локальность нарушений в изображении при потере или порче фрагмента файла. Устойчивость к ошибкам важна в алгоритмах, используемых при широковещании, то есть при передаче данных сразу нескольким адресам. Понятно, что в таком случае невозможно использовать протокол передачи, который бы повторно запрашивал данные в случае сбоя. Также отметим, что требование устойчивости к ошибкам противоречит требованию к высокой степени сжатия, так как возникает необходимость вводить дополнительную информацию в поток. Вещание видеоряда — яркий пример, в котором требование устойчивости к ошибкам критично. Было бы весьма неприятно, если бы однократный сбой приводил к прекращению показа всех последующих кадров.
  • Учет специфики изображений. Имеется в виду более высокая скорость и/или степень компрессии для заранее определенного типа изображений.

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

Обход плоскости

Большинство алгоритмов сжатия данных принимают на вход одномерный массив (вектор). Растровое изображение изначально представляет собой двумерный массив (набор точек на плоскости). Для преобразования двумерного массива в одномерный используются различные методы обхода плоскости. Возникает вопрос, зачем нужны различные методы, когда можно просто записать строки одну за другой? Такой подход имеет право на жизнь, но, используя другие способы преобразования, можно добиться более эффективного сжатия. Рассмотрим некоторые методы обхода плоскости.

Построчный обход

Простейший вид обхода. Строки записываются в результирующий массив одна за другой.

1 2 3 4 5 6
7 8 9101112
131415161718
192021222324

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

Аналогично можно совершать обходы столбцами и столбцами с разворотами.

Обход змейкой (зигзаг-сканирование)

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

1 2 6 71415
3 5 8131621
4 912172022
101118192324

Обход полосами

Чаще всего этот обход выгоднее (в смысле степени сжатия) в случае, когда области двумерного массива не равномерно распределены по одномерному массиву, а сосредоточены в нем компактно. В таком случае можно применить метод обхода полосами. Этот метод похож на обход строками, но в данном случае «строки» становятся шире, то есть, обход совершается полосами шириной N. Пример такого обхода для случая N = 2:

1 3 5 7 911
2 4 6 81012
131517192123
141618202224

Заметим, что если N = 1, то получается обход строками.

Обход полосами с разворотами

Модификация обхода полосами напоминает модификацию, которая уже выполнялась для обхода строками. Разворачиваются как столбцы внутри полос, так и направления четных полос. Таким образом, в обходе отсутствуют разрывы.

1 4 5 8 9
2 3 6 710
1918151411
2017161312

Некоторые алгоритмы сжатия

Рассмотрим теперь некоторые алгоритмы компрессии, которые используются при сжатии изображений. Подробнее про эти и некоторые другие алгоритмы этой области можно прочитать в [1] и [2].

Групповое сжатие (RLE)

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

abbbbzzzzddaaaaaffffuu

После применения группового сжатия эта последовательность будет преобразована в:

1a4b4z2d5a4f2u

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

Рассмотрим одну из популярных реализаций группового сжатия PackBits (впервые была предложена компанией Apple для сжатия bitmap данных на Apple MacIntosh). Предполагая, что значения пикселей являются 8-битными данными, PackBits кодирует регулярные величины двумя байтами. Первый байт содержит число n, находящееся в диапазоне [−127..−1], второй байт содержит значение, которое повторяется −n + 1 раз. Неповторяющиеся величины, такие как «djlrf», предваряются 1-байтовым стартовым кодом m, соответствующим уменьшенной на 1 длине последовательности, то есть, длина последовательно неповторяющихся величин будет равна m + 1 (для «djlrf» m будет равно 4). Повторяющиеся последовательности так же, как и последовательности неповторяющихся величин, не могут быть больше 128 символов, а следовательно, при большей длине должны быть разбиты на составляющие последовательности.

NB! Обычно сжатие не переходит из одной строки развертки в другую.

Процесс декомпрессии интуитивно понятен. Последовательно просматриваем сжатую последовательность, действуя по следующему алгоритму:

  1. Считываем текущий байт (k), длина (l) последовательности устанавливается в значение |k| + 1. Если число k отрицательно, то выполняется второй шаг, иначе происходит переход на третий шаг.
  2. l штук текущего байта записываются на выход.
  3. l байт из сжатой последовательности записываются на выход.
  4. Если последовательность не закончилась, то возвращаемся к первому шагу.

Несложно показать, что время работы алгоритма (как компрессии, так и декомпрессии) пропорционально O(n).

Групповое кодирование используется во многих форматах bitmap, например, в MacPaint, TIFF, PCX.

Алгоритм Хаффмена (Huffman D., 1952)

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

Рассмотрим, например, последовательность

bcacdbebebeedceecef

в ней есть шесть уникальных величин. Частоты, с которыми они появляются, равны соответственно:

a:1 b:4 c:4 d:2 e:7 f:1

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

Двоичное дерево для кодирования Хаффмена

Наиболее редко используемые значения в данном примере — «a» и «f», поэтому они становятся первой парой; «a» присваивается 0-ая ветвь, а «f» 1-ая. Это означает, что 0 и 1 будут младшими битами кодов для «a» и «f» соответственно, а остальные биты будут получены из дерева по мере его построения.

Затем частоты этих символов суммируются. У получившейся пары частота равна двум. Поскольку теперь 2 является наименьшей частотой, то эта пара объединяется с «d» (также имеющей частоту 2). Исходной паре присваивается 0-ая ветвь, а «d» 1-ая. Таким образом, код для «a» заканчивается на 00, для «f» — на 01, а для «d» заканчивается на 1 и при этом будет на 1 бит короче, чем для «a» и «f». В данном алгоритме также помогает разобраться визуализатор [4].

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

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

Оценим время работы данного алгоритма. Для сжатия получаем: O(L + N * log(N) + L * log(N)), где L — количество символов в тексте, N — количество возможных символов. O(L) — это время, требуемое на сбор статистики. O(N * log(N)) — время, уходящее на построение дерева. O(L * log(N)) — время, уходящее непосредственно на кодирование.

Для разархивации время будет пропорционально O(L * log(N)).

LZW

Алгоритм LZW, получивший название по первым буквам имен разработчиков (Lempel A., Ziv J., 1977; Welch T., 1984), осуществляет сжатие файла за счет повторяющихся цепочек символов. Новая цепочка символов, встречающаяся в файле, заносится в таблицу, при этом ей присваивается некоторый код. Если такая цепочка еще раз встретится в файле, вместо нее в выходной файл выводится ее код.

То есть, алгоритм сжатия выглядит следующим образом:


 1 initTable();                                 // Инициализируем таблицу 256-ю символами ASCII.
 2 currentString := "";                         // Инициализируем текущую строку пустой строкой.
 3 while (входной поток не пуст)   
 4     с := readNextByte();                     // Считываем следующий символ из входного файла.
 5     if (inTable(currentString + c))          // Проверяем наличие в таблице комбинации 
                                                   текущая строка+символ (под "+" имеется в виду конкатенация строк).
 6         currentString := currentString + c;  // Возможно, в таблице содержится более крупная цепочка, 
                                                   начинающаяся с данной, поэтому присоединяем символ к строке.
 7     else                                     // текущая строка+символ не в таблице,
 8                                                 но текущая строка при этом таблице. 
 9         code := codeInTable(currentString);  // Получаем код текущей строки в таблице.
10         writeInOutput(code);                 // Выводим код в выходной файл.
11         addToTable(currentString + c);       // Добавляем комбинацию текущая строка+символ в таблицу.
12         currentString := c;                  // Текущая строка теперь - последний считанный из потока символ
                                                   (все, что было считано до него, уже выведено в выходной файл).
13 code := codeInTable(currentString);          // После выхода из цикла текущая строка не пуста,
                                                   ее код тоже нужно вывести в выходной файл.
14 writeInOutput(code);                         // Выводим код в выходной файл.

Функция initTable() инициализирует таблицу всеми возможными строками единичной длины, например, символами ASCII. При этом понятно, что размер каждого из хранящихся в таблице кодов превышает байт, так как все они больше 256. При выполнении функции addToTable() кроме записи строки в таблицу выполняется проверка переполнения таблицы. В случае переполнения в выходной поток записывается код очистки (clearCode). Затем происходит очистка таблицы при помощи функции initTable().

Пример (также смотрите [5]):

Пусть мы сжимаем строку ababcaba.

  1. Текущая строка пустая.
  2. Считываем символ a. Строка a (пустая строка + a) есть в таблице.
    Текущая строка := a.
  3. Считываем символ b. Строки ab (a + b) нет в таблице.
    Добавляем ab в таблицу с кодом 256, выводим в выходной поток 97 (код a).
    Текущая строка := b.
  4. Считываем символ a. Строки ba (b + a) нет в таблице.
    Добавляем ba в таблицу с кодом 257, выводим в выходной поток 98 (код b).
    Текущая строка := a.
  5. Считываем символ b. Строка ab (a + b) есть в таблице.
    Текущая строка := ab.
  6. Считываем символ c. Строки abc (ab + c) нет в таблице.
    Добавляем abc в таблицу с кодом 258, выводим в выходной поток 256 (код ab).
    Текущая строка := c.
  7. Считываем символ a. Строки ca (c + a) нет в таблице.
    Добавляем ca в таблицу с кодом 259, выводим в выходной поток 99 (код c).
    Текущая строка := a.
  8. Считываем символ b. Строка ab (a + b) есть в таблице.
    Текущая строка := ab.
  9. Считываем символ a. Строки aba (ab + a) нет в таблице.
    Добавляем aba в таблицу с кодом 260, выводим в выходной поток 256 (код ab).
    Текущая строка := a.
  10. Входной файл закончился. Выводим в выходной поток 97 (код a).
    Выходной файл выглядит следующим образом: 97 98 256 99 256 97.

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

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


 0 initTable();                                    // Инициализируем таблицу 256-ю символами ASCII.
 1 if (входной поток не пуст)
 2     code := readCode();                         // Считываем код из входного потока.
 3     code := old_code;                       
 4     writeString(stringFromTable(code));         // Записываем в выходной поток строку с кодом code.
 5 while (входной поток не пуст)
 6     code := readCode();                         // Считываем код из входного потока
 7     if (code = clearCode)                       // clearCode - код очистки таблицы. Если мы уверены,
 8                                                    что при кодировании мы не вышли за пределы первой таблицы,
 9                                                    эта проверка не нужна.
10         initTable();
11         code := readCode();
12     if (inTable(code))                          // Проверяем, есть ли в таблице строка с кодом code.
13         writeString(stringFromTable(code));     // Записываем в выходной поток строку с кодом code.
14         addToTable(stringFromTable(old_code) +
15             firstChar(stringFromTable(code)));  // Добавляем в таблицу новую строку. Функция firstChar() возвращает
16                                                    первый символ строки.
17         old_code := code;
18     else                                        // Исключительная ситуация, при которой новый код еще не занесен в таблицу.
19                                                    Возникает в случае, если при компрессии в таблицу было занесено сочетание
20                                                    СТРОКА+СИМВОЛ, а потом во входном файле встречается
21                                                    последовательность СТРОКА+СИМВОЛ+СТРОКА+СИМВОЛ+СТРОКА.
22         outString := stringFromTable(old_code) +
23             firstChar(stringFromTable(old_code)));
24         writeString(outString);
25         addToTable(outString);
26         old_code := code;

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

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

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

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

В среднем, LZW сжимает файлы в 4 раза.

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

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

В качестве примера рассмотрим несколько форматов графических файлов. Более подробную информацию об этих и других форматах можно найти в [3].

PCX

Один из самых старых и широко используемых форматов. Современные версии поддерживают полноцветные изображения (24-битовые цвета) и реализуются либо в качестве палитры, имеющей 256 цветов, либо как полный 24-битовый RGB с размерами изображений до 64000×64000 пикселей. Сжатие осуществляется с помощью метода группового кодирования (RLE).

Формат используется, в основном, для сжатия изображений с большими областями одного цвета. Это обусловлено методом сжатия.

TIFF

TIFF — Tag Image File Format (формат изображения с признаками). Достаточно компактный формат, хорошо сжимающий черно-белые и цветные изображения, а также изображения в градациях серого. Такое разнообразие хорошо сжимаемых изображений объясняется тем, что формат поддерживает различные алгоритмы сжатия, такие как:

  • Групповое сжатие и сжатие по Хаффмену
  • Сжатие LZW

GIF

GIF — Graphics Interchange Format (формат взаимообмена графикой). Широко распространенный формат, использующий для сжатия алгоритм LZW. К преимуществам данного формата можно отнести поддержку 24-битного цвета, реализованную в виде палитры из 256 цветов, а также возможность создания анимированных изображений и прозрачных областей. Недостатком является ограниченность палитры 256-ью цветами.

Литература

  1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: ДИАЛОГ МИФИ, 2002.
  2. Семенюк В.В. Экономное кодирование дискретной информации. — СПб: СПб ГИТМО (ТУ), 2001.
  3. Климов А.С. Форматы графических файлов. — К.: НИПФ «ДиаСофт Лтд.», 1995.

Визуализаторы

  1. Рябов A. Построение дерева Хаффмена (2005)
  2. Вишняков С. Алгоритм сжатия LZW (2005)

Кочелаев Дмитрий, Вишняков Сергей


Булат / 2005-04-30 21:12:11

Обратите, пожалуйста, внимание! В статье что-то много орфографических и пунктуационных ошибок. Вот лишь некоторые примеры: <...>

Спасибо за ваши замечания! Авторам статьи рекомендовано вновь просмотреть текст и срочно устранить недочеты.

P.S. Размещена исправленная версия статьи.

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий