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

Технологии Сжатия Видео

Существуют несколько основных технологий, реализованных в различных кодеках AVI. Например, Indeo 3.2 и Cinepak используют векторную квантизацию, международные стандарты MPEG-1, MPEG-2, MPEG-4, H.261 и H.263 - комбинацию дискретного косинус- преобразования и компенсацию движения. Некоторые из кодеков последнего поколения основаны на дискретном преобразовании элементарной волны (Discrete Wavelet Transform or DWT ). Другие технологии включают алгоритм рекурсивного сжатия изображения, разработанный кампанией Iterated Systems.

1. СЖАТИЕ БЕЗ ПОТЕРЬ

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

2. СЖАТИЕ С ПОТЕРЯМИ

Часть информации теряется в процессе сжатия. Принцип сжатия с потерями основан на ограниченных возможностях человеческого зрения.

СЖАТИЕ С ПРОЦЕНТНЫМИ ПОТЕРЯМИ

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

СЖАТИЕ С ЕСТЕСТВЕННЫМИ ПОТЕРЯМИ

При использовании JPEG, MPEG и других форматов компрессии видео с потерями изображение часто повреждается больше, чем при сжатии с процентными потерями, однако, видео все еще остается приемлемым для человеческого восприятия. Если сжатие и декомпрессия в процессе преобразования повреждают изображение, аналогично естественным повреждениям, то зрение не будет сильно “протестовать”.

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

СЖАТИЕ С НЕЕСТЕСТВЕННЫМИ ПОТЕРЯМИ

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

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

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

Последовательное кодирование длины (ПКД)

Кодек, использующий последовательное кодирование длины - Microsoft RLE (MRLE)

ПКД также используется, для кодирования коэффициентов DCT в блоках дискретного косинус - преобразования, которые входят в реализацию форматов MPEG, H.261, H.263, и JPEG.

Особенности:

  1. Хорошо подходит для черно-белых или 8 разрядных графических изображений, таких как кадры анимации.
  2. Не подходит для естественных изображений с высоким разрешением.

КРАТКОЕ ОПИСАНИЕ

ПКД кодирует последовательность пикселей одинакового цвета (например, черного или белого) как одиночное ключевое слово. Так, например, последовательность пикселей:

77 77 77 77 77 77 77

может быть закодирована как

7 77 (семь 77).

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

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

 

 

Векторная квантизация

Кодеки, использующие векторную квантизацию: Indeo 3.2, Cinepak.

Indeo и Cinepak работают с YUV представлением цвета.

Особенности:

  1. Процесс кодирования в вычислительном отношении интенсивен и не может быть выполнен в реальном времени без специализированных аппаратных средств.
  2. Быстрый процесс декодирования.
  3. Появление блочных артефактов при высоком сжатии.

КРАТКОЕ ОПИСАНИЕ

При векторной квантизации изображение делится на блоки (4x4 пикселя для Indeo и Cinepak). Как правило, некоторые блоки подобны другим блокам, хотя обычно, они не идентичны. Кодер идентифицирует класс подобных блоков и заменяет их на "универсальный" блочный представитель, составляет поисковую таблицу коротких двоичных кодов к "универсальным" блокам. Как правило, самые короткие двоичные коды представляют наиболее общие классы блоков в изображении. При векторной квантизации (VQ) декодер использует поисковую таблицу, чтобы транслировать приблизительное изображение, составленное из "универсальных" блоков согласно поисковой таблице.

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

 

Дискретное косинус преобразование (ДКП)

Кодеки, использующие дискретное косинус преобразование:

- Motion JPEG

- Editable MPEG

- MPEG-1

- MPEG-2

- MPEG-4

- H.261

- H.263

- H.263+

Особенности:

  1. Появление блочных артефактов при высоком сжатии.
  2. Излом острых граней. Случайное размытие в острых граней.
  3. Большие требования к вычислительным мощностям.

КРАТКОЕ ОПИСАНИЕ

ДКП - широко используемое преобразование при сжатии изображения. Двумерное ДКП применяется к блокам 8*8 пикселей.

Человеческий глаз менее чувствителен к высоким компонентам частоты изображения, представленного более высокими коэффициентами ДКП. Больший коэффициент квантования обычно применяется к этим более высоким компонентам частоты. Фактическая стандартная матрица квантования (матрица 64 коэффициентов квантования, один для каждого из 64 коэффициентов ДКП) в JPEG стандарте имеет более высокие коэффициенты квантования для более высокой частоты коэффициенты ДКП. Квантуемые коэффициенты ДКП- тогда выполняемая длина, закодированная как коды переменной длины, которые указывают некоторое число нулевых коэффициентов, сопровождаемых ненулевым коэффициентом. Например, код выполняемой - длины мог бы указывать 4 нулевых коэффициента, сопровождаемые ненулевым коэффициентом уровня 2. Короткие коды переменной длины (например 0110) используются для общих комбинаций, последовательностей из нулей и уровней ненулевого коэффициента. Более длинные коды переменной длины (например 0000001101) используются для менее общих комбинаций, последовательностей из нулей и уровней ненулевого коэффициента. Таким образом, существенное сжатие изображения возможно. ДКП матрица NxN, строки которой - функции косинуса:

где

N - число выборок в блоке

Дискретное преобразование элементарной волны (DWT- Discrete Wavelet Transform)

Кодеки, использующие DWT:

- VDOWAVE VDONET'S

- VxTreme

- Intel Indeo 5.x

- Intel Indeo 4.x

Особенности:

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

КРАТКОЕ ОПИСАНИЕ

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

Простым примером DWT является Haar преобразование элементарной волны:

Входной сигнал - x [n] (ряд выборок, индексированных по n).

Haar НПФ (среднее число двух последовательных выборок):

Haar ВПФ (различие двух последовательных выборок):

Заметим, что:

Последовательности вывода g [n] и h [n] содержат избыточную информацию. Их можно разложить на две последовательности, опустив четные или нечетные члены, после чего все еще возможно воспроизведение первоначального входного сигнала x[n]. Обычно опускаются нечетные выборки. Входной сигнал x [n] может быть воспроизведен полностью по

и т.д.

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

Грубое приближение иногда называется основным уровнем, а добавление деталей - уровнем расширения. Вывод ФВЧ h [n], может подаваться на другую пару фильтров.

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

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

Алгоритмы, основанные на DWT позволяют добиться лучших результов, чем ДКП. В последнее время, DWT становится все более популярным.

Контур - основанное кодирование изображения.

Примером контур - основанного кодирования изображения может служить Crystal Net's Surface Fitting Method (SFM). Стандарт MPEG-4 также включает некоторые идеи, связанные с контур - основанным кодированием изображения.

КРАТКОЕ ОПИСАНИЕ

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

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

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

Контур - основанное кодирование - одна из новейших технологий сжатия изображений (май 1999г.). Выявление контуров остается нерешенной задачей.

Достигая более высокого сжатия, контур - основанное кодирование изображения может обходить проблемы, с которыми сталкиваются ДКП (JPEG, MPEG, H.261, H.263, DV, и т.д.) и DWT (Intel Indeo, VDONet VDOWave, и т.д.).

 

Кодирование разности кадров

Кодек, использующий кодирование разности кадров - Cinepak.

 

Особенности:

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

КРАТКОЕ ОПИСАНИЕ

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

Разности кадров кодируются при помощи алгоритмов сжатия неподвижных изображений (DWT, ДКП). Ключевые кадры сжимаются независимо от предыдущих, что ограничивает накопленные ошибки и делает возможным поиск в пределах потока видео. Например, в широко используемом кодеке Cinepak ключевой кадр устанавливается каждые 15 кадров.

 

Компенсация движения (КД)

Кодеки, использующие КД:

- ClearVideo (RealVideo) Fractal Video Codec от Iterated Systems

- VDOWave от VDONet

- VxTreme

- MPEG-1,2, и 4

- H.261

- H.263

- H.263+

Особенности:

  1. Сжатия видео выше, чем при кодировании разности кадров.
  2. Стадия кодирования алгоритма КД в вычислительном отношении интенсивна.
  3. Схема КД, используемая в международных стандартах MPEG, H.261, и H.263 работает лучше всего для сцен с ограниченным движением.

 

КРАТКОЕ ОПИСАНИЕ

Стандарты MPEG-1, MPEG-2, MPEG-4, H.261 и H.263, основанные на ДКП, используют КД, Iterated Systems ClearVideo (Real Video), VDOWave и VxTreme's - различные формы КД. Метод КД, используемый в MPEG, H.261 и H.263, работает только для переводного движения, т.е. для объектов, перемещающихся поперек фона или панорамирования камеры, но практически не работает для вращения объектов, изменения их размеров или увеличения камеры (см. ниже). Существуют и альтернативные формы КД, обрабатывающие вращательное движение, масштабирование, искажение и другие виды движения в сцене.

Распознавание объектов - нерешенная проблема в обработке изображения. При сжатии, изображение делится на блоки (16x16 пикселей в MPEG-1). Для каждого блока кодируется вектор движения, указывающий на блок в предыдущем или следующем кадре, который схож с кодируемым блоком. Блок ссылки может совпадать с исходным (отсутствие движения) или отличаться от него (движение). Кодеку не требуется распознавать присутствие шара или другого объекта. Он лишь сравнивает блоки пикселей в декодированном кадре и кадре ссылки.

Сжатие достигается путем пересылки или сохранения только вектора движения вместо значений пикселей для полного блока. Кодированные ("предсказанные") блоки формируют декодируемый кадр. Блоком ссылки может быть любой 16x16 блок пикселей в кадре ссылки, который больше всего схож с кодированным блоком. Кадр ссылки должен быть декодирован до начала декодирования текущего кадра. Однако, кадр ссылки не обязательно должен идти перед текущим декодируемым кадром. Фактически, кадром ссылки может быть будущий кадр. MPEG учитывает это через так называемый B (двунаправленный предсказанный) кадр.

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

Для блока или блоков, содержащих перемещающийся шар, векторы движения будут не нулевыми, указывая на блок в предыдущем (или будущем) кадре, который содержит шар. Перемещенный блок вычитается из текущего блока. Вообще, там будут оставлены некоторые ненулевые значения которые будут закодированы, используя ДКП, или DWT. В MPEG, векторы движения закодированы как коды переменной длины для большего сжатия. Процесс кодирования в данном случае называется Оценкой Движения.

Пример:

Четыре блока со связанными векторами движения (4, -4, 0, и 0). Верхний левый блок напоминает верхний правый блок в области ссылки (где шар был). Верхний правый блок напоминает верхнюю левую область в области ссылки. Более низкие левые и более низкие правые блоки были неизменны. В этом простом примере, вертикальное смещение нулевое и игнорируется. В этом простом примере, область может быть декодирована, используя один векторы движения. В большем количестве общих случаев, имеется ошибка между предсказанным кадром и текущим кадром. Эта ошибка кодирована, используя все еще схему сжатия изображения(образа) типа блока ДКП.

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