Методы сжатия изображений

Методы сжатия изображений

2-е издание, исправленное

Ватолин Д.С.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Методы сжатия изображений/ Д.С. Ватолин - М.: Национальный Открытый Университет “ИНТУИТ”,
2016

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

(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Ватолин Д.С., 2007-2016

3

Определения. Аббревиатуры и классификации методов сжатия

Базовые определения

Бит - это “атом” цифровой информации: переменная, которая может принимать ровно
два различных значения:

“1” (единица, да, истина, существует)
“0” (ноль, нет, ложь, не существует)

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

Емкость для хранения бита можно представлять себе как небольшой “ящик” где-то в
пространстве-времени (в микросхеме, на магнитном/оптическом диске, линии связи) с
двумя возможными состояниями: полный - “1”, и пустой - “0”.

Данные - информация в цифровом виде.

Объем данных измеряется в битах, но может быть и рациональным числом, а не только
целым.

R-битный элемент - совокупность R битов - имеет 
 возможных значений-состояний.

Большинство источников цифровой информации порождает элементы одного размера
R. А в большинстве остальных случаев - элементы нескольких размеров: 
..

(например, 8, 16 и 32).

Байт - это 8-битный элемент: совокупность восьми битов.

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

Блок - конечная последовательность цифровой информации.

Поток - последовательность с неизвестными границами: данные поступают
маленькими блоками, и нужно обрабатывать их сразу, не накапливая. Блок последовательность с произвольным доступом, а поток - с последовательным.

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

Используют и такие пары терминов: компрессия/декомпрессия, кодирование/
декодирование, упаковка/распаковка.

4

Под просто сжатием будем далее понимать сжатие без потерь (lossless compression).

Сжатие с потерями (lossy compression) - это два разных процесса:

1. выделение сохраняемой части информации с помощью модели, зависящей от цели

сжатия и особенностей источника и приемника информации;

2. собственно сжатие, без потерь.

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

Конечную последовательность битов назовем кодом1) а количество битов в коде длиной кода.

Конечную последовательность элементов назовем словом, а количество элементов в
слове - длиной слова. Иногда используются синонимы: строка и фраза. В общем случае
слово построено из R-битных элементов, а не 8-битных. Таким образом, код - это слово
из 1-битных элементов.

Например, в блоке из 14-и элементов “кинчотсихыннад” одно слово длиной 14
элементов, два слова длиной 13, и так далее, 13 слов длиной 2 и 14 слов длиной 1.
Аналогично в блоке из семи битов “0100110” один код длиной 7 битов, два кода
длиной 6, и так далее, семь кодов длиной 1.

Символ - это “атом” некоторого языка (например, буквы, цифры, ноты, символы
шахматных фигур, карточных мастей). Во многих случаях под символом имеют в виду
R-битный элемент (обычно байт), однако элементы мультимедийных данных все-таки
не стоит называть символами: они содержат количественную информацию, а не
качественную.

“Качественными” можно называть данные, содержащие элементы-указатели на
символы внутри таблиц или указатели на ветви алгоритма (и таким образом
“привязанные” к некоторой структуре: таблице, списку, алгоритму и т.п.) А
“количественными” - множества элементов, являющиеся записями значений какихлибо величин.

ASCII (American Standard Code for Information Interchange - Американский
Стандартный Код для Обмена Информацией) каждому значению байта ставит в
соответствие символ. Но чтобы построить однозначное соответствие для всех
необходимых символов из множества национальных алфавитов народов мира,
требуется больше: по крайней мере 16 битов на символ (что и обеспечивает стандарт
Unicode ).

Множество всех различных символов, порождаемых некоторым источником,

5

называется алфавитом, а количество символов в этом множестве - размером алфавита.
Источники данных порождают только элементы, но физические источники
информации - символы или элементы.

Размер алфавита таблицы ASCII равен 
, а Unicode - 
. Это две самые

распространенные таблицы символов.

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

Можно говорить, что источник без памяти порождает “элементы”, а источник данных с
памятью - “слова”, поскольку во втором случае

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

В первом же случае имеем дело с перестановкой элементов, и рассматривать данные
как слова нет смысла.

Кавычки показывают, что это условные названия способов интерпретации входных
данных: “слова”, “элементы”, “биты”.

По традиции бинарный источник без памяти называют обычно “источник Бернулли”, а
важнейшим частным случаем источника данных с памятью является “источник
Маркова” (N-го порядка): состояние на i-ом шаге зависит от состояний на N
предыдущих шагах: i-1, i-2,…, i-N.

Третья важнейшая применяемая при сжатии данных математическая модель “аналоговый сигнал”:

данные считаются количественными;
источник данных считается источником Маркова 1-го порядка.

Если использовать модель “аналоговый сигнал” с N > 1, то при малых N эффективность
сжатия неизменна или незначительно лучше, но метод существенно сложнее, а при
дальнейшем увеличении N эффективность резко уменьшается.

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

Еще две важных характеристики алгоритма сжатия - объемы памяти, необходимые для

6

сжатия и для разжатия (для хранения данных, создаваемых и/или используемых
алгоритмом).

Названия и аббревиатуры методов

CM (Context Modeling) - Контекстное моделирование

DMC (Dynamic Markov Compression) - Динамическое марковское сжатие (является
частным случаем CM)

PPM (Prediction by Partial Match) - Предсказание по частичному совпадению (является
частным случаем CM)

LZ-методы - методы Зива-Лемпела, в том числе LZ77, LZ78, LZH и LZW

PBS (Parallel Blocks Sorting) - Сортировка параллельных блоков

ST (Sort Transformation) - Частичное сортирующее преобразование (является частным
случаем PBS)

BWT (Burrows-Wheeler Transform) - Преобразование Барроуза-Уилера (является
частным случаем ST)

RLE (Run Length Encoding) - Кодирование длин повторов

HUFF (Huffman Coding) - кодирование по методу Хаффмана

SEM (Separate Exponents and Mantissas) - Разделение экспонент и мантисс
(Представление целых чисел)

UNIC (Universal Coding) - Универсальное кодирование (является частным случаем
SEM)

ARIC (Arithmetic Coding) - Арифметическое кодирование

RC (Range Coding) - Интервальное кодирование (вариант арифметического)

DC (Distance Coding) - Кодирование расстояний

IF (Inverted Frequences) - “Обратные частоты” (вариант DC)

MTF (Move To Front) - “Сдвиг к вершине”, “Перемещение стопки книг”

ENUC (Enumerative Coding) - Нумерующее кодирование

FT (Fourier Transform) - Преобразование Фурье

DCT (Discrete Cosine Transform) - Дискретное Косинусное Преобразование, ДКП
(является частным случаем FT)

7

DWT (Discrete Wavelet Transform) - Дискретное Вэйвлетное Преобразование, ДВП

LPC (Linear Prediction Coding) - Линейно-Предсказывающее Кодирование, ЛПК (к
нему относятся Дельта-кодирование, ADPCM, CELP и MELP)

SC (Subband Coding) - Субполосное кодирование

VQ (Vector Quantization) - Векторное квантование

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

8

Методы сжатия без потерь

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

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

Точная связь между вероятностями и кодами установлена в теореме Шеннона о
кодировании источника, которая гласит, что элемент , вероятность появления
которого равняется 
, выгоднее всего представлять 
 битами. Если при

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

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

(1а)

Это значение также называется энтропией распределения вероятностей F или
энтропией источника в заданный момент времени.

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

соответственно, 
. Можно сказать, что источник находится в состоянии k,

которому соответствует набор вероятностей 
 генерации всех возможных

элементов 
. Поэтому среднюю длину кодов можно вычислить по формуле

(1б)

,

где 
 - вероятность того, что F примет k -ое значение, или, иначе, вероятность

нахождения источника в состоянии k.

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

9

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

каждого элемента  алфавита входной последовательности. В этом случае мы
оперируем оценкой 
 вероятности элемента .

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

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

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

Существует 
 различных файлов длины  битов, где 
 Если размер

каждого такого файла в результате обработки уменьшается хотя бы на 1 бит, то 
исходным файлам будет соответствовать самое большее 
 различающихся

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

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

Поэтому невозможен “вечный” архиватор, который способен бесконечное число раз
сжимать свои же архивы. “Наилучшим” архиватором является программа
копирования, поскольку в этом случае мы можем быть всегда уверены в том, что объем
данных в результате обработки не увеличится.

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

10