Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


5.1. Основные принципы

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

Сжатие видео, обычно, допускает частичную потерю информации. Кодирование кадра , с помощью его предшественника  вносит определенные искажения. Затем кодирование кадра  на основе кадра  добавляет еще большее искажение. Даже при использовании сжатия без потерь, это может привести к потере некоторых битов данных. То же может случиться при передаче файла или после долгого хранения ленты на полке. Если кадр  потерял некоторые биты, то все последующие кадры будут иметь искажения вплоть до следующего внешнего кадра. Это приводит к нежелательному накапливанию ошибок. Поэтому необходимо регулярно использовать внешние кадры при кодировании последовательного видеоряда, а не только в его начале. Внешние кадры обозначаются символом , а внутренние кадры - символом  (от «предсказанный»).

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

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

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

Идея кадров типа  настолько полезна, что большинство кадров сжимается с помощью этого приема. Итак, мы имеем дело с кадрами трех типов: ,  и . Кадр  кодируется независимо от всех остальных кадров. Кадр  кодируется на основе кадров  или . Наконец, кодирование кадра типа  использует предыдущий кадр и следующий кадр типа  или . На рис. 5.1а показан пример последовательности кадров в том порядке, в котором они генерируются кодером (и входом декодера). На рис. 5.lb отображена последовательность кадров, которая поступает на выход декодера и отображается на экране дисплея. Ясно, что кадр с номером 2 должен быть отображен ранее кадра 5. Следовательно, каждый кадр должен иметь две метки, а именно, время кодирования и время отображения.

Для начала рассмотрим два интуитивных метода сжатия видео.

Прореживание: Кодер выбирает кадры через одного и записывает их в сжатый поток. Это приводит к фактору сжатия 2. Декодер принимает кадры и дублирует их подряд два раза.

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

284.jpg

Рис. 5.1. (а) Порядок кодирования. (b) Порядок отображения.

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

Компенсация движения: Просмотр любого фильма наводит на мысль, что разница между последовательными кадрами мала из-за движения на сцене, перемещения камеры или в силу обеих причин. Это свойство можно использовать для улучшения сжатия. Если кодер обнаружил, что часть  предыдущего кадра, как одно целое, переместилась в новое положение на текущем кадре, то  можно сжать, записав следующие три компонента: предыдущее местоположение, новое местоположение и информацию о границе области . Следующее обсуждение метода компенсации движения позаимствовано из [Manning 98].

В принципе, эта перемещающаяся часть может иметь любую форму. На практике мы ограничены блоками с равными сторонами (обычно это квадраты или прямоугольники). Кодер сканирует текущий кадр блок за блоком. Для каждого блока  на предыдущем кадре делается поиск тождественного блока  (если сжатие без потерь) или близкого блока (если сжатие с потерями). Если такой блок найден, то кодер записывает разность между его прошлым и настоящим положением. Эта разность имеет вид

,

и она называется вектором перемещения. На рис. 5.2 показан простой пример, на котором солнце и деревья движутся вправо (из-за перемещения видеокамеры), а ребенок перемещается влево (это движение сцены).

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

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

286.jpg

Рис. 5.2. Компенсация движения.

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

Поиск блока: Эта процедура обычно занимает много времени, поэтому ее следует тщательно оптимизировать. Если  - текущий блок текущего кадра, то необходимо сделать поиск совпадающего или близкого к нему блока на предыдущем кадре. Обычно этот поиск делается в небольшой области (называемой областью поиска) вокруг , которая задается с помощью параметров максимального смещения  и . Эти параметры определяют максимальное допустимое расстояние по горизонтали и вертикали в пикселах между  и его копией на предыдущем кадре. Если блок  - это квадрат со стороной , то область поиска состоит из  пикселов (рис 5.3), по которым можно построить  различных, частично перекрывающихся квадратов размера 6x6. Значит, число возможных блоков-кандидатов в этой области пропорционально .

Измерение расхождения: Это наиболее чувствительная часть кодера. Здесь необходимо выбрать наиболее близкий блок к исходному блоку . Эта процедура должна быть простой и быстрой, но, вместе с тем, надежной.

287.jpg

Рис. 5.3. Область поиска.

Средняя абсолютная разность (или средняя абсолютная ошибка) вычисляет среднее значение модуля разностей между пикселами  блока  и пикселами  блока-кандидата  по формуле

.

Для этого потребуется выполнить  операций вычитания, столько же операций взятия модуля числа и одной операции деления. Эта величина вычисляется для каждого из  блоков-кандидатов для нахождения блока с наименьшим отклонением от блока  (обозначим его )/ Если это отклонение меньше заданного порога, то блок  выбирается в качестве похожей пары для блока . В противном случае такой пары нет, и блок  необходимо кодировать без компенсации движения.

В этом месте можно задать законный вопрос: «Как может случиться, что некоторый блок текущего кадра не имеет подходящей похожей пары на предыдущем кадре?» Для ответа представим себе, что снимающая видеокамера движется слева направо. Новые объекты попадают в поле зрения камеры справа. Поэтому самый правый блок кадра может содержать объекты, которых не было на предыдущем кадре.

Другой мерой расхождения может служить «среднеквадратическое отклонение», в формуле которого вместо функции взятия модуля стоит возведение в квадрат разности пикселов:

.

Функция ранжирования разностей пикселов PDC (pixel difference classification) определяет, сколько разностей  меньше, чем заданное число .

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

.

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

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

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

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

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

1. Спрогнозировать вектор перемещения на основе его предшественников в той же строке и том же столбце текущего кадра. Вычислить разность между вектором-прогнозом и истинным вектором и закодировать его по Хаффману. Этот метод весьма важен. Он используется в MPEG-1 и в других алгоритмах сжатия.

2. Сгруппировать векторы перемещения в блоки. Если все векторы в блоке идентичны, то блок кодируется одним вектором. Все другие блоки кодируются как в пункте 1. Каждый кодированный блок начинается соответствующим идентификатором типа.

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

 



<< ПредыдущаяОглавлениеСледующая >>