5.1. Основные принципыСжатие видео основано на двух важных принципах. Первый это пространственная избыточность, присущая каждому кадру видеоряда. А второй принцип основан на том факте, что большую часть времени каждый кадр похож на своего предшественника. Это называется временная избыточность. Таким образом, типичный метод сжатия видео начинает с кодирования первого кадра с помощью некоторого алгоритма компрессии изображения. Затем следует кодировать каждый последующий кадр, находя расхождение или разность между этим кадром и его предшественником и кодируя эту разность. Если новый кадр сильно отличается от предыдущего (это происходит, например, с первым кадром последовательности), то его можно кодировать независимым образом. В литературе по сжатию видеоданных, кадр, кодируемый с помощью своего предшественника называется внутренним. В противном случае он называется внешним кадром. Сжатие видео, обычно, допускает частичную потерю информации. Кодирование кадра Если эта идея принимается, то возможно дальнейшее обобщение данной концепции внутренних кадров. Такой кадр можно кодировать с использованием одного из его предшественников, а также с помощью некоторого последующего кадра. Очевидно, кодер не должен использовать информацию, недоступную декодеру, но сжатие видео имеет определенные особенности, поскольку оно вовлекает большие объемы данных. Для зрителя не важно, если кодер работает медленно. Важно, чтобы декодер работал быстро. Обычно сжатые видеоданные записываются на жесткий диск или на DVD для дальнейшего воспроизведения. Кодер может затратить часы на кодирование, а декодер должен работать со скоростью, не меньшей, чем стандартная скорость смены кадров (довольно большое число кадров должно появиться на экране за секунду времени для нормального восприятия). Поэтому типичный видеодекодер работает в параллельном режиме, то есть, одновременно в работе находится несколько кадров. Имея это в виду, представим себе, что кодер кодирует кадр 2 с помощью кадров 1 и 3, а затем записывает сжатую информацию в выходной поток в последовательности 1, 3, 2. Декодер читает их в этом порядке, параллельно декодирует кадры 1 и 3, а потом декодирует кадр 2 на основе кадров 1 и 3. Конечно, эти кадры должны быть правильно помечены. Кадры, которые кодируются с применением прошлых и будущих кадров обозначаются буквой Предсказание кадров с помощью их предшественников имеет смысл, если движение объектов на картинке постепенно открывает фон изображения. Такие области могут быть лишь частично отображены на текущем кадре, а более подробная информация может быть получена из следующего кадра. Поэтому этот кадр является естественным кандидатом для предсказания этой области на текущем кадре. Идея кадров типа Для начала рассмотрим два интуитивных метода сжатия видео. Прореживание: Кодер выбирает кадры через одного и записывает их в сжатый поток. Это приводит к фактору сжатия 2. Декодер принимает кадры и дублирует их подряд два раза. Вычитание: Кадр сравнивается со своим предшественником. Если разница между ними мала (всего в нескольких пикселах), то кодер кодирует только эти отличающиеся пикселы, то есть, записывает в выходной поток три числа для каждого из отличающихся пикселов: его координаты и разность пикселов двух кадров. Если различие между кадрами велико, то в файл пишется текущий кадр в «сыром»» виде. Вариант с частичной потерей для метода вычитания анализирует величину расхождения пикселов. Если разность между двумя значениями меньше некоторого порога, то пикселы не считаются разными. Рис. 5.1. (а) Порядок кодирования. (b) Порядок отображения. Вычитание по блокам: Этот метод является развитием метода вычитаний. Изображение делится на блоки пикселов и каждый блок Компенсация движения: Просмотр любого фильма наводит на мысль, что разница между последовательными кадрами мала из-за движения на сцене, перемещения камеры или в силу обеих причин. Это свойство можно использовать для улучшения сжатия. Если кодер обнаружил, что часть В принципе, эта перемещающаяся часть может иметь любую форму. На практике мы ограничены блоками с равными сторонами (обычно это квадраты или прямоугольники). Кодер сканирует текущий кадр блок за блоком. Для каждого блока
и она называется вектором перемещения. На рис. 5.2 показан простой пример, на котором солнце и деревья движутся вправо (из-за перемещения видеокамеры), а ребенок перемещается влево (это движение сцены). Компенсация движения будет эффективной, если объекты просто перемещаются по сцене, но не удаляются, приближаются или поворачиваются. Существенное изменение освещения сцены от кадра к кадру также снижает эффективность этого метода. Обычно метод компенсации движения используется для сжатия с потерями. В следующих абзацах детально обсуждаются основные нюансы этого метода. Сегментация кадров: Текущий кадр разбивается на неперекрывающиеся равносторонние блоки. Блоки могут быть квадратными или прямоугольными. Во втором случае предполагается, что движение на экране происходит в основном по горизонтали, и тогда горизонтальные блоки уменьшают число векторов перемещения без ухудшения коэффициента сжатия. Размер блока очень важен, поскольку большие блоки уменьшают вероятность обнаружения совпадений, а маленькие блоки приводят к большому числу векторов перемещения. На практике применяются блоки, размеры которых являются степенями числа 2, например, 8 или 16; это упрощает программное обеспечение. Рис. 5.2. Компенсация движения. Порог поиска: Каждый блок Поиск блока: Эта процедура обычно занимает много времени, поэтому ее следует тщательно оптимизировать. Если Измерение расхождения: Это наиболее чувствительная часть кодера. Здесь необходимо выбрать наиболее близкий блок к исходному блоку Рис. 5.3. Область поиска. Средняя абсолютная разность (или средняя абсолютная ошибка) вычисляет среднее значение модуля разностей между пикселами
Для этого потребуется выполнить В этом месте можно задать законный вопрос: «Как может случиться, что некоторый блок текущего кадра не имеет подходящей похожей пары на предыдущем кадре?» Для ответа представим себе, что снимающая видеокамера движется слева направо. Новые объекты попадают в поле зрения камеры справа. Поэтому самый правый блок кадра может содержать объекты, которых не было на предыдущем кадре. Другой мерой расхождения может служить «среднеквадратическое отклонение», в формуле которого вместо функции взятия модуля стоит возведение в квадрат разности пикселов:
Функция ранжирования разностей пикселов PDC (pixel difference classification) определяет, сколько разностей Мера интегральной проекции вычисляется с помощью нахождения суммы строки блока
Методы подоптимального поиска: Такие методы делают поиск по части блоков среди всех Корректировка вектора перемещения: Если блок Этот шаг тоже достаточно продолжителен и может даже все испортить. Перемещение большинства объектов в кадре может быть медленным, гладким, но некоторые малые объекты могут двигаться быстро, скачкообразно. Подправленные векторы перемещения могут вступать в противоречие с векторами перемещения таких объектов и быть причиной ошибочно сжатых кадров. Кодирование векторов перемещения: Большая часть текущего кадра (возможно, половина его) может быть преобразована в векторы перемещения, поэтому кодирование этих векторов весьма актуально. Это кодирование должно быть без потерь. Два свойства векторов перемещения позволяют осуществить эффективное кодирование: (1) эти векторы коррелированны и (2) они имеют неравномерное распределение. При сканировании кадров блок за блоком оказывается, что прилегающие блоки обычно имеют близкие векторы перемещения. Кроме того векторы также не имеют любые направления. Они, как правило, направлены в одну, реже, в две стороны; значит, векторы распределены неравномерно. Не существует единого общего метода кодирования, который был бы идеальным для всех случаев. Обычно применяется арифметическое кодирование, адаптивное кодирование Хаффмана, а также различные префиксные коды. Все они работают достаточно хорошо и с близкой эффективностью. Вот еще два возможных метода с хорошей степенью сжатия: 1. Спрогнозировать вектор перемещения на основе его предшественников в той же строке и том же столбце текущего кадра. Вычислить разность между вектором-прогнозом и истинным вектором и закодировать его по Хаффману. Этот метод весьма важен. Он используется в MPEG-1 и в других алгоритмах сжатия. 2. Сгруппировать векторы перемещения в блоки. Если все векторы в блоке идентичны, то блок кодируется одним вектором. Все другие блоки кодируются как в пункте 1. Каждый кодированный блок начинается соответствующим идентификатором типа. Кодирование ошибки предсказания: Компенсация движения является сжатием с потерями, поскольку блок
|