4. Базовая техника компрессии

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

4.1. Кодирование без потерь

Run-length кодирование: В алгоритмах, реализующий данный тип кодирования, строка повторяющихся символов заменяется символом и числом его повторений. Например, строка “abaaaabbbbbbb” заменится на строку “a1b1ba4b7”.

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

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

Работа указанных алгоритмов, в общем случае, организуется в два прохода. На первом проходе строится дерево (словарь), позволяющее произвести операцию кодирования. На втором проходе непосредственно выполняется само кодирование.

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

4.2. Кодирование с потерями

4.2.1. Предикативное кодирование

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

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

Ясно, что поскольку разница между данными намного меньше, чем сами данные, то можно достичь значительного уменьшения объема от оригинала. Качество кодирования сильно зависит от правильной работы предсказателя и от скорости изменения входного сигнала. Данная техника наиболее применима для аудио и видео кодирования, где каждый последующее значение сильно похоже на предыдущее (PCM, DPCM, ADPCM).

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

4.2.2.Кодирование с использованием преобразований

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

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

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

Коэффициенты получившейся частотной матрицы делятся на соответствующий элемент из матрицы квантования (Q-table). Каждый элемент матрицы квантования является весовым коэффициентом для соответствующего элемента из частотной матрицы (т.е. отвечает за качество проработки, отвечает за «вклад» конкретного элемента).

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

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

Рисунок 2. Схема кодирования с использованием преобразований