ЛекцииММ2 (Курс электронных лекций), страница 7

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

На практике используются его разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее "адаптивно", т.е. в процессе архивации/разархивации. Эти приемы избавляют от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG.

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

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

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

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

Для кодировки символа компрессор находит путь от корня дерева к листу символа. Предположим, что компрессор хочет закодировать букву s. Он начинает с листа, соответствующего букве s, и переходит в родительский узел, отмечая при этом, по какой ветви он про шел (по 0 или по 1). Он продолжает идти вверх по дереву, пока не достигнет корня. Список ветвей в обратном порядке описывает путь от корня до s: это и есть код Хаффмана для этого символа.

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

Чтобы декодировать, декомпрессор берет код и обрабатывает его в обратном порядке. Это значит, что он начинает с корня дерева. Если первый бит кода равен 1, то декомпрессор идет от корня в узел по ветви 1. Он продолжает чтение битов и проход по ветвям, пока не достигнет листа; символ в листе и есть декодированный символ.

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

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

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

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

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

Компрессор присоединяет символ к ветви 1 корня, оставляя пустой лист на ветви 0. Затем он посылает этот символ в декомпрессор как буквальный код ASCII, и декомпрессор выполняет точно такое же действие над своим деревом.

Для каждого символа, прочитанного после этого, компрессор выполняет следующие шаги. Вначале он проверяет, находится ли код в кодовом дереве. Если код есть, компрессор выдает его так же, как и в случае статического сжатия. Если же нет, он посылает код для пустого листа. Затем он посылает новый символ как буквальный код ASCII. Наконец, компрессор добавляет два кода, один для нового пустого листа на ветви 0, и один - для нового кода ветви 1. Когда дерево заполнится, т.е. когда в нем будут все символы, компрессор просто изменяет последний пустой лист на последний символ.  Программа декомпрессии может делать уточнения в своем дереве, потому что у нее имеется в точности то же самое дерево, что и у компрессора. Когда она принимает код пустого листа, она читает следующий код из сжатых данных как литерал ASCII. Затем декомпрессор применяет для изменения дерева ту же программу, какую использовал и компрессор.

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

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

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

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

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

В отличие от LZW-алгоритма JPEG-кодирование является кодированием с потерями. Сам алгоритм кодирования базируется на очень сложной математике, но в общих чертах его можно описать так:    

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

Схема YUV использует три компоненты, Y – яркость (может быть использована как чёрно – белое изображение), U – голубизна, V – краснота. Перевод из RGB осуществляется по схеме:

Y = 0.299R + 0.587G + 0.114B

U = 0.1687R - 0.3313G + 0.5B

V = 0.5R - 0.1187G + 0.0813B

Это преобразование, в принципе, не имеет потерь, но на практике вводится ошибка округления, обусловленная необходимостью округления результата до целого. Так как глаз человека более чувствителен к первой компоненте, чем к двум другим, то в JPEG допускает дискретизацию различных компонент с различной частотой. Наиболее общий случай – использование одной выборки U и V для четырёх выборок Y. Это позволяет сохранять лишь 50% используемого объёма при практически неизменном качестве изображения. Технология дискретизации, при которой некоторые компоненты оцифровываются с меньшей частотой, чем другие, называется поддескритизацией.

К значениям пикселей применяется формула, названная дискретным косинусоидальным преобразованием (Discrete Cosine Transform - DCT). DCT переводит матрицу значений пикселей 8х8 в матрицу значений амплитуд такой же размерности, соответствующую определенным частотам синусоидальных колебаний. Левый верхний угол матрицы соответствует низким частотам, а правый нижний - высоким.

Дискретное косинусоидальное преобразование (DCT) превращает массив данных интенсивности в массив данных частоты, который содержит информацию о том, как быстро изменяется интенсивность. В JPEG применяется DCT для квадратов 8*8 данных о пикселях для каждого компонента цвета. Точки в каждом блоке нумеруются от (0,0) в верхнем левом до (7,7) в нижнем правом углах. F(x,y) есть значение данных в точке (x,y). Создаётся новый блок по формуле:

Обратное преобразование имеет вид:

По физическому смыслу преобразование сводится к представлению изображения в виде суммы (ко)синусоидальных гармоник (волн). Значения F определяют амплитуды гармоник, u,v – их частоты. F(u,v) указывает на степень изменения величин для каждой из множества частот. Значение F(0,0) указывает что уровень значения не изменился, F(7,7) определяет наиболее быстрое изменение величины в обоих направлениях. Более высокие частоты “отвечают” за передачу более “тонких” деталей изображения.

Для блоков 8*8 выходные данные на 4 бита длиннее входных. Отличие интенсивностей от частот в том, что медленные изменения гораздо заметнее, чем быстрые, так что данные низкой частоты более важны, чем высокой для восстановления изображения.

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

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

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

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