ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ РОССИЙСКОЙ ФЕДЕРАЦИИ
Воронежский государственный технический университет
Л. Н. Никитин

Алгоритмы сжатия изображений и стандарты цифрового кодирования

Воронеж 2007

ББК 32.884
Никитин Л. Н. Алгоритмы сжатия изображений и стандарты цифрового кодирования: Учеб. пособие Воронеж: Воронеж. гос. техн. ун-т, 2007. 84с.
В учебном пособии рассмотрены наиболее перспективные алгоритмы сжатия изображений, и основные форматы сжатия видеоданных, структура, виды и способы записи DVD.

Учебное пособие соответствует требованиям Государственного образовательного стандарта высшего профессионального образования по направлению 201210 «Проектирование и технология производства электронных средств». Предназначено для студентов 4, 5 курсов дневной и заочной форм обучения.

Табл.9., Изоб.22., Гист.2., Библ.11.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ 4

1. Алгоритмы сжатия изображений 5

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

1.2. Алгоритмы сжатия без потерь 6

1.2.1 Алгоритм RLE 6

1.2.2 Алгоритм LZW 8

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

1.2.4. JBIG 22

1.2.5. Lossless JPEG 22

1.3. Алгоритмы сжатия с потерями 23

1.3.1. Проблемы алгоритмов сжатия с потерями 23

1.3.2. Алгоритм JPEG 24

1.3.3. Фрактальный алгоритм 29

1.3.4. Рекурсивный (волновой) алгоритм 38

Подведение итогов 40

1.4. Алгоритмы сжатия видеоизображения 42

1.4.1. Частотно-полосные преобразования 42

1.4.2. Применение частотно-полосных преобразований

для сжатия видео 44

1.4.3. Адаптивная пред- и постфильтрация 45

1.4.4. Особенности архитектуры текущего поколения видеокодеков 46

1.4.5. Стандарт Н264 47

2. Форматы сжатия видео семейства MPEG 49

2.1. Международный стандарт кодирования с информационным

сжатием MPEG-2 51

2.1.1. Компрессия видеоданных 55

2.1.2. Кодируемые кадры 57

2.1.3. Компенсация движения 59

2.1.4. Дискретно-косинусное преобразование 60

2.1.5. Профессиональный профиль стандарта MPEG-2 61

3. DVD-Video 63

3.1. Структура DVD –дисков и принцип записи 65

3.2. Видео на DVD 70

3.3. Звук на DVD 71

ПРИЛОЖЕНИЕ. Таблицы сравнения алгоритмов 74

Сжатие двухцветного изображения 74

Сжатие 16-цветного изображения 75

Сжатие изображения в градациях серого 76

Сжатие полноцветного изображения 78

Использованная литература 80

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

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

Теоретические основы методов сжатия информации были заложены в конце сороковых годов, когда была опубликована статья Клода Шеннона (Claude Shannon) "Математическая теория коммуникаций". В ней впервые было сформулировано положение о том, что энтропия любого блока информации равна вероятности его появления во всем массиве данных. Соответственно, наиболее часто повторяющиеся блоки являются и наиболее "избыточными" (redundant) и могут быть представлены в более сжатом виде.

1. Алгоритмы сжатия изображений
1.1. Классы изображений
Статические растровые изображения представляют собой двумерный массив чисел. Элементы этого массива называют пикселами (от английского pixel — picture element). Все изображения можно подразделить на две группы — с палитрой и без нее. У изображений с палитрой в пикселе хранится число — индекс в некотором одномерном векторе цветов, называемом палитрой. Чаще всего встречаются палитры из 16 и 256 цветов.

Изображения без палитры бывают в какой-либо системе цветопредставления и в градациях серого (grayscale). Для последних значение каждого пиксела интерпретируется как яркость соответствующей точки. Встречаются изображения с 2, 16 и 256 уровнями серого. Одна из интересных практических задач заключается в приведении цветного или черно-белого изображения к двум градациям яркости, например, для печати на лазерном принтере. При использовании некой системы цветопредставления каждый пиксел представляет собой запись (структуру), полями которой являются компоненты цвета. Самой распространенной является система RGB, в которой цвет представлен значениями интенсивности красной (R), зеленой (G) и синей (B) компонент. Существуют и другие системы цветопредставления, такие, как CMYK, CIE XYZccir60-1 и т.п. Ниже мы увидим, как используются цветовые модели при сжатии изображений с потерями.

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

Рассмотрим следующие примеры неформального определения классов изображений:

1. 
   Класс 1. Изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом. Плавные переходы цветов отсутствуют. Примеры: деловая графика — гистограммы, диаграммы, графики и т.п.
   
2. 
   Класс 2. Изображения, с плавными переходами цветов, построенные на компьютере. Примеры: графика презентаций, эскизные модели в САПР, изображения, построенные по методу Гуро.
   
3. 
   Класс 3. Фотореалистичные изображения. Пример: отсканированные фотографии.
   
4. 
   Класс 4. Фотореалистичные изображения с наложением деловой графики. Пример: реклама.
   

Развивая данную классификацию, в качестве отдельных классов могут быть предложены некачественно отсканированные в 256 градаций серого цвета страницы книг или растровые изображения топографических карт. (Заметим, что этот класс не тождественен классу 4). Формально являясь 8- или 24-битными, они несут даже не растровую, а чисто векторную информацию. Отдельные классы могут образовывать и совсем специфичные изображения: рентгеновские снимки или фотографии в профиль и фас из электронного досье.

Достаточно сложной и интересной задачей является поиск наилучшего алгоритма для конкретного класса изображений.

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

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

Initialization(...);
do {
    byte = ImageFile.ReadNextByte();
    if(является счетчиком(byte)) {
        counter = Low6bits(byte)+1;
        value = ImageFile.ReadNextByte();
        for(i=1 to counter)
            DecompressedFile.WriteByte(value)
        }
    else {
        DecompressedFile.WriteByte(byte)
} while(ImageFile.EOF());
В данном алгоритме признаком счетчика (counter) служат единицы в двух верхних битах считанного файла:

Рис. 1 – Схема работы алгоритма RLE (1-ый вариант)

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

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

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

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

Initialization(...);
do {
    byte = ImageFile.ReadNextByte();
    counter = Low7bits(byte)+1;
    if(если признак повтора(byte)) {
        value = ImageFile.ReadNextByte();
        for (i=1 to counter)
        CompressedFile.WriteByte(value)
    }
    else {
    for(i=1 to counter){
        value = ImageFile.ReadNextByte();
        CompressedFile.WriteByte(value)
    }
    CompressedFile.WriteByte(byte)
} while(ImageFile.EOF());
Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта:

Рис. 2 – Схема работы алгоритма RLE (2-ой вариант)

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

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

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

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

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

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

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

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

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

Функция InitTable() очищает таблицу и помещает в нее все строки единичной длины.
InitTable();
CompressedFile.WriteCode(СlearCode);
CurStr=пустая строка;
while(не ImageFile.EOF()){ //Пока не конец файла
    C=ImageFile.ReadNextByte();
    if(CurStr+C есть в таблице)
        CurStr=CurStr+С;//Приклеить символ к строке
    else {
        code=CodeForString(CurStr);//code-не байт!
        CompressedFile.WriteCode(code);
        AddStringToTable (CurStr+С);
        CurStr=С; // Строка из одного символа
    }
}
code=CodeForString(CurStr);
CompressedFile.WriteCode(code);
CompressedFile.WriteCode(CodeEndOfInformation);
Функция InitTable() инициализирует таблицу строк так, чтобы она содержала все возможные строки, состоящие из одного символа. Например, если мы сжимаем байтовые данные, то таких строк в таблице будет 256 (“0”, “1”, ... , “255”). Для кода очистки (ClearCode) и кода конца информации (CodeEndOfInformation) зарезервированы значения 256 и 257. В рассматриваемом варианте алгоритма используется 12-битный код, и, соответственно, под коды для строк нам остаются значения от 258 до 4095. Добавляемые строки записываются в таблицу последовательно, при этом индекс строки в таблице становится ее кодом.

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

Пример:

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

• 
  “45” — есть в таблице;
  
• 
  “45, 55” — нет. Добавляем в таблицу <258>“45, 55”. В поток: <45>;
  
• 
  “55, 55” — нет. В таблицу: <259>“55, 55”. В поток: <55>;
  
• 
  “55, 151” — нет. В таблицу: <260>“55, 151”. В поток: <55>;
  
• 
  “151, 55” — нет. В таблицу: <261>“151, 55”. В поток: <151>;
  
• 
  “55, 55” — есть в таблице;
  
• 
  “55, 55, 55” — нет. В таблицу: “55, 55, 55” <262>. В поток: <259>;
  

Последовательность кодов для данного примера, попадающих в выходной поток: <256>, <45>, <55>, <55>, <151>, <259>.

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

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

Алгоритм декомпрессии, осуществляющий эту операцию, выглядит следующим образом:
code=File.ReadCode();
while(code != СodeEndOfInformation){
    if(code = СlearСode) {
        InitTable();
        code=File.ReadCode();
        if(code = СodeEndOfInformation)
            {закончить работу};
        ImageFile.WriteString(StrFromTable(code));
        old_code=code;
    }
    else {
        if(InTable(code)) {
            ImageFile.WriteString(FromTable(code));
            AddStringToTable(StrFromTable(old_code)+
            FirstChar(StrFromTable(code)));
            old_code=code;
        }
        else {
            OutString= StrFromTable(old_code)+
            FirstChar(StrFromTable(old_code));
            ImageFile.WriteString(OutString);
            AddStringToTable(OutString);
            old_code=code;
        }
    }
}

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

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

Рис. 4 – Зависимость стрепени компрессии от разрядности кодов

входного потока

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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