МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

С. О. БОГДАНОВ

МЕТОДИЧЕСКОЕ ПОСОБИЕ

«ПРЕДСТАВЛЕНИЕ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ В ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКЕ»

Часть 3

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

МОСКВА 1998

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

Проведем небольшой расчет. Допустим, у нас есть небольшое цветное изображение размером 10 на 12 сантиметров (приблизительно 4 на 5 дюймов), которое мы хотим хранить в компьютере и при необходимости распечатывать с фотографическим качеством, а это означает реальный цвет (true color) и разрешение 300 dpi. Когда изображение будет оцифровано, оно примет размеры 1200 на 1500 пикселей и, поскольку каждый пиксель будет кодироваться тремя байтами, займет 5,2 Мбайт памяти. Если же мы хотим предоставить эту картинку для публикации в книге, журнале или любом другом полноцветном печатном издании, то нам придется сохранить ее в цветовой модели CMYK, а это увеличит ее объем до 6,9 Мбайт.

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

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

Наиболее распространенными на сегодняшний день в области компьютерной графики алгоритмами сжатия статических изображений являются LZW, RLE и JPEG. Рассмотрим их более подробно.

Групповое кодирование

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

Этот алгоритм имеет несколько реализаций. К ним относятся, например, RLE и PackBits. PackBits получил распространение на компьютерах Apple Macintosh. Работая с 8-битными данными, алгоритм производит кодирование с помощью двух байтов. Первый байт содержит число n из диапазона -127...-1 такое, что -n+1 равно числу повторений. Второй байт содержит повторяющуюся величину. Если встречается неповторяющаяся последовательность, то в первом байте будет содержаться значение m из диапазона 0...127, соответствующее уменьшенной на единицу длине этой последовательности, а сама она в неизменном виде будет записана дальше.

Метод Хаффмана (CCITT Group 3)

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

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

а:1 b:3 c:3 d:2 e:9 f:l

Для формирования минимального кода для каждого используется двоичное дерево (рис. 11). Алгоритм объединяет вместе элементы, появляющиеся наименее часто. Их частоты складываются, и затем такая пара рассматривается как один элемент. Процесс продолжается до тех пор, пока все элементы не объединятся в пары.

В этом примере наиболее редко встречаются величины а и f, поэтому они становятся первой парой и будут иметь наиболее длинные коды. Младший бит этих кодов будет являться 0 для а и 1 — для f. Старшие биты этих кодов будут получены из дерева по мере его построения.

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

И сходной паре присваивается ветвь 0, a d — ветвь 1. Следовательно, код для а будет заканчиваться на 00, для f — на 01, а для d — на 1 (и будет короче на 1 разряд). Дерево продолжает строиться аналогичным образом, пока в него не войдут все величины, в том числе наиболее часто встречающиеся.

Рис. 11. Двоичное дерево Хаффмана

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

LZW

Очень популярным сегодня является алгоритм Лемпела-Зива-Вельча — LZW (Lempel-Ziv & Welch), для подавляющего большинства изображений гарантирующий сжатие в 2 — 3 раза. Он имеет огромное множество модификаций и применяется не только в машинной графике. В отличие от схемы Хаффмана алгоритму LZW не требуется перед кодированием создавать таблицу кодов. Начиная с простой таблицы, алгоритм в ходе работы формирует все более эффективную. Идея алгоритма заключается в поиске повторяющихся последовательностей, и при этом длина кода не зависит от частоты появления соответствующей величины.

LZW начинает с таблицы с одним элементом кода для каждой возможной величины данных; например, 256 элементов для 8-битных данных. Затем алгоритм добавляет в таблицу данные для каждого уникального сочетания величин, которое удается обнаружить.

Рассмотрим последовательность ababaaacaaaad. Пусть каждая буква представляет собой 2-битную величину. Начальная таблица шифратора и дешифратора для данного примера будет выглядеть следующим образом:

а:00 b:01 с: 10 d:ll

LZW ищет самую длинную последовательность, которую может распознать, и сохраняет в таблице объединение ее со следующим символом. В начале алгоритм находит первую величину а и распознает ее. Затем он проверяет последовательность ab и не распознает ее. Тогда он выдает код 000 для а, как распознанной величины, и добавляет новый вход в таблицу для нераспознанной последовательности аb. Таблица шифрования принимает следующий вид:

а:000 b:001 c:010 d:011 ab:100

Шифратор остановился на величине b, он добавляет к ней следующую и обнаруживает, что получившаяся последовательность ba не распознается. Алгоритм выдает код 001 для b, и продолжает шифрование.

Теперь начинается «хороший» этап. Алгоритм ищет, начиная с а, самую длинную распознаваемую последовательность. Такой последовательностью является ab, для которой выдается код 100. Это означает, что 4-битная последовательность оказалась замененной 3-битной. Продолжая перебор, алгоритм будет пополнять таблицу все новыми входами, а это позволит заменять кодами все более длинные последовательности. На рисунке 12 приводится алгоритм кодирования LZW на языке Си. Процедура распаковки данных происходит аналогично, хотя и несколько сложнее (рис. 13).

Сжатие с потерями. JPEG

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

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

В связи с бурным ростом в последние годы средств мультимедиа, Internet-технологий, цифрового фото и видео широкое распространение получил алгоритм JPEG (Joint Photographic Experts Group), разработанный Объединенной Группой Экспертов по Фотографии Международной Организации Стандартизации (ISO).

I* — сжатие — */

InitializeStringTable();

Г = пустая строка;

for для каждого символа в файле {

К = GetNextCharacter();

if (Г + К в таблице строк) {

Г = Г + К; /* объединение строк */

} else{

WriteCode(CodeFromString(Г));

AddTableEntry(Г + K);

Г = К;

}

} /* конец цикла */ WriteCode(CodeFromString(Г)); WriteCode(EndOfInformation);

Рис. 12. Алгоритм сжатия данных методом LZW

/* — распаковка — */

InitializeTable();

Code = GetNextCode();

WriteString(StringFromCode(Code));

OldCode = Code;

while ((Code=GetNextCode())!=EoiCode) {

if (IsInTable(Code)) {

WriteString(StringFromCode(Code));

AddStringToTable(

StringFromCode(OldCode)+

FirstChar(StringFromCode(Code)));

OldCode = Code;

}

else{

OutString = StringFromCode(OldCode)+

FirstChar(StringFromCode(OldCode));

WriteString(OutString);

AddStringToTable(OutString);

OldCode = Code;

}

}

Рис. 13. Алгоритм декомпрессии LZW

Алгоритм JPEG имеет много вариаций, но все они в целом исходят из одной общей схемы. В начале графическая информация разделяется на цветовой (chroma) и яркостной (luminance) каналы, чтобы использовать преимущества того, что человеческий глаз допускает уменьшение разрешение для цвета. Переход к цветовой модели YCbCr происходит по следующим формулам:

Y = 0,299R + 0.587G + 0,114В

Cb = 0,1687R - 0,3313G + 0,5В

Cr = 0,5R - 0,4187G + 0,0813B

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

Следующий шаг — применение к каждому из каналов дискретного косинусоидального преобразования (Discrete Cosine Transform, DCT), после чего индивидуальные пиксели перестают существовать. JPEG допускает дискретизацию различных компонент с различной частотой. Поскольку человеческий глаз значительно менее чувствителен к изменениям цвета, нежели к изменениям яркости, то, как правило, используют одну выборку Сb и Сr для каждых четырех выборок Y. Это в два раза уменьшает объем файла (6 выборок вместо 12) практически без потерь качества при восприятии изображения.

JPEG разбивает все изображение на блоки размером 8x8 пикселей. Точки в каждом блоке нумеруются от (0,0) в левом верхнем углу до (7,7) в правом нижнем. К каждому такому блоку применяется двумерное дискретное косинусоидальное преобразование (DCT), которое превра­щает информацию об интенсивности цвета f(x,x), в пространственные частоты F(u,v), указывающие на то, насколько быстро эти интенсивности изменяются для каждой из частот.

,