Кодирование символов

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

Подробности

Родительская категория: Кодирование символов

Категория: Кодирование символов

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

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

Серия повторяющихся величин заменяется двумя: значением и количеством. Цепочка из n одинаковых байтов (при байт/пиксел) будет заменена двумя байтами. Хорошо кодируются изображения с большими областями постоянной закраски (из-под "рисовалок" типа PaintBrush).

Кодирование по Хаффману (Huffman, 1952)

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

Алгоритм LZW (Lempel-Ziv-Welch — 1984)

Используется в архиваторах. Подобно алгоритму Хаффмана, заменяет длинные последовательности более короткими, но не требует предварительно собирать статистику. Он формирует все более эффективную таблицу кодирования по мере продвижения по шифруемому массиву. Более "шумные" изображения кодируются хуже. Поэтому иногда рекомендуется подавить низкочастотной фильтрацией высокие пространственные частоты на изображении Типичные коэффициенты сжатия между 1:1 и 1:3, хотя иногда м.б. и 1:10. Этот алгоритм используется в графических форматах GIF и TIFF.

Арифметическое сжатие (1979...1989)

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

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

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

Алгоритм JPEG Joinnt Photographic Experts Group — комитет ISO

Метод сжатия включает следующие шаги:

1. Представление RGB преобразуется в представление YCbCr (формулы были даны ранее в этом тексте)
2. Выполняется дискретное косинусное преобразование для квадратных фрагментов изображения (обычно 8х8) отдельно для яркости и отдельно (с меньшей пространственной дискретностью) — для цветовых компонент.
3. Полученные коэффициенты округляются. Это позволяет представить их меньшим количеством битов (на этом этапе — основные потери. Коэффициенты при высоких частотах при этом могут оказаться нулевыми, тогда их можно отбросить.
4. Последовательность коэффициентов кодируется по Хаффману или алгоритмом арифметического кодирования.
5. При декодировании этапы выполняются в обратном порядке. Достижимые коэффициенты сжатия — 1:10...1:50 при ухудшающемся качестве.

Я(0,0)	Я(0,1)	Я(0,2)	...
Я(1,0)	Я(1,1)	Я(1,2)	...
Я(2,0)	Я(2,1)	...	...
...	...

--------------------->

--------------------->

F(0,0)	F(0,1)
F(1,0)	F(1,1)
F(2,0)	F(2,1)

MPEG — международный комитет Motion Pictures Expert ISO в 1993г

MPEG разработан международным комитетом Motion Pictures Expert и принят в окончательной редакции ISO только в 1993г. Хотя MPEG-стандарт определяет правила кодирования и декодирования цифровых потоков как изображений, так и связанного с ними звука, в этом материале мы остановимся только на изображении. Стандарт JPEG отличается от MPEG тем, что проводит независимое сжатие каждого кадра изображения.

Компрессия использует следующие основные идеи:

• Устранение временной избыточности видео, учитывающее тот факт, что в пределах коротких интервалов времени большинство фрагментов сцены оказываются неподвижными или незначительно смещаются по полю. На рисунке (см. рисунок ниже) показаны два соседних кадра из фильма Терминатор-2 и разностный кадр (кодируем разностный кадр).
• Устранение пространственной избыточности изображений подавлением мелких деталей сцены, несущественных для ее визуального восприятия человеком (цвет большинства точек неба одинаков — кодируем их одинаково).
• Использование более низкого цветового разрешения при YUV-представлении изображений (Y -яркость, U и V — цветоразностные сигналы). Установлено, что глаз менее чувствителен к пространственным изменениям оттенков цвета по сравнению с изменениями яркости. Повышение информационной плотности результирующего цифрового потока путем выбора оптимального математического кода для его описания (например, использование более коротких кодовых слов для наиболее часто повторяемых значений).

На первой ступени поток видео разделяется на кадры изображения:

• I (Intra) — независимо сжатые, опорные при восстановлении остальных изображений по их разностям;
• Р (predicted) — сжатые с использованием ссылки на одно изображение, содержащие разность текущего изображения с предыдущим I или Р с учетом смещений отдельных фрагментов;
• В (bidirertlonally predicted) — сжатые с использованием ссылки на два изображения, содержащие разность текущего изображения с предыдущим и последующим изображениями типов I или Р с учетом смещений отдельных фрагментов.

Изображения объединяются в группы (GОР Group Of Pictures), представляющие собой минимальный повторяемый набор последовательных изображений, которые могут быть декодированы независимо от других изображений в последовательности. 

Типичной является группа вида (I0 В1 B2 РЗ В4 В5 Р6 В7 В8 Р9 B10 В11) (I12 В13 В14 Р15 В16 В17 Р18...), в которой I-тип повторяется каждые пол-секунды. Обратим внимание, что в изображении РЗ основная часть фрагментов сцены предсказывается на основании соответствующих смещенных фрагментов изображения I0. Собственно кодированию подвергаются только разности этих пар фрагментов.

Аналогично Р6 строится на базе РЗ, Р9 — на базе Р6 и т.д. В то же время большинство фрагментов В4 и В2 предсказываются как полусумма смещенных фрагментов из I0 и РЗ, В4 и В5 — из РЗ и Р6, В7 и В8 — из Р6 и Р9 и т.д. В то же время В-изображения не используются для предсказания никаких других изображений.

Ясно, что точность кодирования должна быть максимальной для I, ниже — для Р, минимальной — для В. Установлено, что для типичных сцен хорошие результаты достигаются при отведении числа бит для I в 3 раза больше, чем для Р, и для Р в 2-5 раз больше, чем для В. Эти отношения уменьшаются для динамичных сцен и увеличиваются для статичных.

Отдельные изображения состоят из макроблоков. Макроблок — это основная структурная единица фрагментации изображения. Он соответствует участку изображения размером 16х16 пикселей. Именно для них определяются вектора смещения относительно I- или Р- изображений. В свою очередь каждый макроблок состоит из шести блоков, четыре из которых несут информацию о яркости Y, а по одному — определяют цветовые U- и V- компоненты. Каждый блок представляет собой матрицу 8х8 элементов. Блоки являются базовыми структурными единицами, над которыми осуществляются основные операции кодирования, в том числе, выполняется дискретное косинусное преобразование (DCT discrete cosine transform) и квантование полученных коэффициентов. Кодирование блоков похоже на кодирование в алгоритме JPEG.

Упрощенно процесса MPEG-кодирования сводится к следующему:

• На этапе предварительной обработки входной видеосигнал оцифровывается и форматируется согласно заданному размеру и цветовой выборке 2:1 (на каждые 2 Y-отсчета по горизонтали и вертикали приходится по одному U- и V-отсчету).
• После этого кодер осуществляет выбор структуры группы (она может меняться в процессе кодирования в зависимости от содержания видео и разрешенного объема передаваемой информации), задает типы всех изображений и, по необходимости, меняет их последовательность.
• Далее для I-изображений он осуществляет DCT каждого макроблока. Для Р- и В-изображений он сначала оценивает вектора смещения: по одному на макроблок для Р (для предсказания вперед) и по 2 — для В (вперед и назад).
• Затем, сравнивая число бит, необходимое для кодирования макроблока как в случае предсказания его значений на основе соответствующих макро- блоков из предыдущего (для Р) и последующего (для В) изображений, так и без оного предсказания, -кодер по каждому макроблоку принимает отдельное решение и осуществляет DCT либо собственных значений макро-блока, либо его разностных (относительно предсказанных) значений.
• После этого полученные коэффициенты DCT подвергаются квантованию с переменным шагом более высоким частотам задается больший шаг. В результате большинство высокочастотных коэффициентов принимают нулевые значения, что позволяет математически эффективно их кодировать. Изменяя масштаб квантования, кодер реализует компромисс между качеством кодированных изображений (тем хуже, чем больше масштаб) и объемом передаваемой информации (тем меньше, чем больше масштаб). Это особенно важно для систем с фиксированной пропускной способностью.
  Поскольку в видео информационная насыщенность изображений меняется со временем, то кодер должен постоянно отслеживать реальный объем передаваемых данных и оперативно менять масштаб квантования и, конечно, значения других параметров.
  Безусловно, этот процесс не может быть абсолютно точным, поэтому кодер (как и декодер) обладает буфером памяти, в который предварительно записывается переменный поток данных, и из которого этот поток передается с заданной скоростью.
  Чем больше размер этого буфера, тем большие изменения объема данных на изображение относительно среднего уровня допускаются. В стандарте буфер установлен как 327 680 бит (40 Кб), что при скорости 200 Кб/с соответствует 0,2 с.
  Таким образом, кодер должен следить за реальным состоянием буфера, не допуская его переполнения (часть данных 6удет потеряна) или недополнения (качество передаваемых изображений будет неоправданно низким).
  В результирующем потоке кодер должен передавать как собственно математически закодированные значения коэффициентов DCT, так и выбранные значения всех параметров кодировки (вид матрицы квантования и ее масштаб, тип предсказания макроблока и значения векторов смещения, структуру группы и т.д.).
• Декодеру остается сравнительно простая работа — принять в буфер и расшифровать (шифр задан стандартом) полученную информацию, осуществить обратные преобразования и отобразить полученное видео на мониторе.

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

Команды работы с изображением

Перечислим операции по обработке изображений, которые находят свое отражение в системах команд процессоров:

• побитовая обработка — команды побитовой обработки, часто называемые логическими командами, есть во всех процессорах;
• перенос блоков (двумерных фрагментов, обычно прямоугольных) — Transputer, графические сопроцессоры;
• аппаратное рисование примитивов: линии, прямоугольники, трапеции — графические сопроцессоры;
• поддержка shading и удаления невидимых — операции линейной интерполяции (i80860, MMX).

 

• < Назад