Введение
Основной сложностью при работе с видео являются большие объемы дискового пространства, необходимого для хранения даже небольших фрагментов. Причем даже применение современных алгоритмов сжатия не изменяет ситуацию кардинально. При записи на один компакт-диск "в бытовом качестве", на него можно поместить несколько тысяч фотографий, примерно 10 часов музыки и всего полчаса видео. Видео "телевизионного" формата 720х576 пикселов 25 кадров в секунду в системе RGB требует потока данных примерно в 240 Мбит/сек (т.е. 1.8 Гб в минуту). При этом традиционные алгоритмы сжатия изображений, ориентированные на отдельные кадры, не спасают ситуации, поскольку даже при уменьшении потока в 10 раз он составляет достаточно большие величины.
В результате подавляющее большинство сегодняшних алгоритмов сжатия видео являются алгоритмами с потерей данных. При сжатии используется несколько типов избыточности:
Когерентность областей изображения - малое изменение цвета изображения в соседних пикселах (свойство, которое эксплуатируют все алгоритмы сжатия изображений с потерями).
Избыточность в цветовых плоскостях - используется большая важность яркости изображения для восприятия.
Подобие между кадрами - использование того факта, что на скорости 25 кадров в секунду, как правило, соседние кадры изменяются незначительно.
Первые два пункта знакомы вам по алгоритмам сжатия графики. Использование подобия между кадрами в самом простом и наиболее часто используемом случае означает кодирование не самого нового кадра, а его разности с предыдущим кадром. Для видео типа "говорящая голова" (передача новостей, видеотелефоны), большая часть кадра остается неизменной, и даже такой простой метод позволяет значительно уменьшить поток данных. Более сложный метод заключается в нахождении для каждого блока в сжимаемом кадре наименее отличающегося от него блока в кадре, используемом в качестве базового. Далее кодируется разница между этими блоками. Этот метод существенно более ресурсоемкий.
Основные понятия
Определимся с основными понятиями, которые используются при сжатии видео. Видеопоток характеризуется разрешением, частотой кадров и системой представления цветов. Из телевизионных стандартов пришли разрешения в 720х576 и 640х480, и частоты в 25 (стандарты PAL или SECAM ) и 30 (стандарт NTSC ) кадров в секунду. Для низких разрешений существуют специальные названия CIF - Common Interchange Format, равный 352х288 и QCIF - Quartered Common Interchange Format, равный 176х144. Поскольку CIF и QCIF ориентированы на крайне небольшие потоки, то с ними работают на частотах от 5 до 30 кадров в секунду.
Требования приложений к алгоритму
Для алгоритмов сжатия видео характерны большинство тех же требований приложений, которые предъявляются к алгоритмам сжатия графики, однако есть и определенная специфика:
Произвольный доступ - подразумевает возможность найти и показать любой кадр за ограниченное время. Обеспечивается наличием в потоке данных так называемых точек входа - кадров, сжатых независимо (т.е. как обычное статическое изображение). Приемлемым временем поиска произвольного кадра считается 1/2 секунды.
Быстрый поиск вперед/назад - подразумевает быстрый показ кадров, не следующих друг за другом в исходном потоке. Требует наличия дополнительной информации в потоке. Эта возможность активно используется всевозможными проигрывателями.
Показ кадров фильма в обратном направлении. Редко требуется в приложениях. При жестких ограничениях на время показа очередного кадра выполнение этого требования может резко уменьшить степень сжатия.
Аудио-визуальная синхронизация - самое серьезное требование. Данные, необходимые для того, чтобы добиться синхронности аудио и видео дорожек, существенно увеличивают размер фильма. Для видеосистемы это означает, что, если мы не успеваем достать и показать в нужный момент времени некий кадр, то мы должны уметь корректно показать, например, кадр, следующий за ним. Если мы показываем фильм без звука, то можно позволить себе чуть более медленный или более быстрый показ. Во времена сравнительно несовершенного немого кино кадры шли настолько неравномерно, насколько неравномерно крутил ручку камеры оператор. Показ без звука фильма, снятого столь несовершенными методами, воспринимается нормально даже при условии, что частота показываемых кадров постоянна (и герои фильма то передвигаются карикатурно быстро, то медленно). Однако смотреть фильм (например, боевик), в котором видеосистема не успевает за звуком - становится мучением.
Устойчивость к ошибкам - требование, обусловленное тем, что большинство каналов связи ненадежны. Испорченное помехой изображение должно быстро восстанавливаться. Требование достаточно легко удовлетворяется необходимым числом независимых кадров в потоке. При этом также уменьшается степень сжатия, так как на экране 2-3 секунды (50-75 кадров) может быть одно и то же изображение, но мы будем вынуждены нагружать поток независимыми кадрами.
Время кодирования/декодирования. Во многих системах (например, видеотелефонах) общая задержка на кодирование-передачу-декодирование должна составлять не более 150 мс. Кроме того, в приложениях, где необходимо редактирование, нормальная интерактивная работа невозможна, если время реакции системы составляет более 1 секунды.
Редактируемость. Под редактируемостью понимается возможность изменять все кадры так же легко, как если бы они были записаны независимо.
Масштабируемость - простота реализации концепции "видео в окне". Мы должны уметь быстро изменять высоту и ширину изображения в пикселах. Масштабирование способно породить неприятные эффекты в алгоритмах основанных на ДКП (дискретном косинусном преобразовании). Корректно реализовать эту возможность для MPEG на данный момент можно, пожалуй, лишь при достаточно сложных аппаратных реализациях, только тогда алгоритмы масштабирования не будут существенно увеличивать время декодирования. Интересно, что масштабирование достаточно легко осуществляется в так называемых фрактальных алгоритмах. В них, даже при увеличении изображения в несколько раз, оно не распадается на квадраты, т.е. отсутствует эффект "зернистости". Если необходимо уменьшать изображение (что, хоть и редко, но бывает нужно), то с такой задачей хорошо справляются алгоритмы, основанные на wavelet преобразовании (см. описание JPEG-2000).
Небольшая стоимость аппаратной реализации. При разработке хотя бы приблизительно должна оцениваться и учитываться конечная стоимость. Если эта стоимость велика, то даже при использовании алгоритма в международных стандартах, производители будут предлагать свои, более конкурентоспособные, алгоритмы и решения. На практике это требование означает, что алгоритм должен реализовываться небольшим набором микросхем.
Упражнение: Покажите, что требования произвольного доступа, быстрого поиска, показа в обратном направлении, аудио-визуальной синхронизации и устойчивости к ошибкам противоречат условию высокой степени сжатия потока.
Описанные требования к алгоритму противоречивы. Очевидно, что высокая степень сжатия подразумевает архивацию каждого последующего кадра с использованием предыдущего. В то же время требования на аудио-визуальную синхронизацию и произвольный доступ к любому кадру за ограниченное время не дают возможности вытянуть все кадры в цепочку. И, тем не менее, можно попытаться прийти к некоторому компромиссу. Сбалансированная реализация, учитывающая систему противоречивых требований, может достигаться на практике за счет настроек компрессора при сжатии конкретного фильма.
Определение требований
Под процедурой определения требований, предъявляемых к алгоритму, понимается уяснение классов программного и аппаратного обеспечения, на которые он ориентирован и, соответственно, выработка требований к нему.
Носители информации, на которые ориентирован алгоритм:
DVD-ROM - сравнительно низкая стоимость, очень высокая плотность записи информации делают его наиболее перспективным устройством для хранения оцифрованного видео.
CD-ROM - низкая стоимость при высокой плотности записи информации делают его наиболее привлекательным устройством для хранения оцифрованного видео. К недостаткам относится сравнительно малый объем, однако диск обладает рекордно низким отношением стоимости диска к объему.
Жесткий диск - наиболее быстрое и гибкое устройство, обладающее очень малым временем поиска, что необходимо для некоторых приложений. Однако он имеет высокое соотношение стоимости диска к объему.
Перезаписываемые оптические диски - одно из наиболее перспективных устройств, способных сочетать в себе достоинства CD-ROM (низкая себестоимость хранения информации, большой объем, произвольный доступ) и жесткого диска (возможность перезаписи).
Компьютерные сети (как глобальные, так и локальные). Характеризуются возможностью быстро получать практически неограниченные объемы информации. К недостаткам сетей, с которыми борются так называемые технологии QoS (Quality of Service - гарантированное качество сервиса), относятся возможные задержки пакетов, и произвольное изменение пропускной способности канала.
Программное обеспечение, использующее видео-компрессию, можно подразделить на две группы - симметричное и асимметричное.
Асимметричные приложения предъявляют серьезные требования к декодеру (как правило, по времени и памяти), но для них безразличны затраты ресурсов при кодировании. Примером являются различные мультимедиа энциклопедии, путеводители, справочники, игры и просто фильмы. При такой постановке задачи появляется возможность применить сложные алгоритмы компрессии, позволяющие получить большую степень сжатия данных.
Симметричные приложения предъявляют одинаково жесткие требования на время, память и другие ресурсы, как при кодировании, так и при декодировании. Примерами такого рода приложений могут служить видеопочта, видеотелефон, видеоконференции, редактирование и подготовка видеоматериалов.
Обзор стандартов
В 1988 году в рамках Международной Организации по Стандартизации ( ISO ) начала работу группа MPEG (Moving Pictures Experts Group) - группа экспертов в области цифрового видео ( ISO-IEC/JTC1/SC2/WG11/MPEG ). Группа работала в направлениях, которые можно условно назвать MPEG-Video - сжатие видеосигнала в поток со скоростью до 1,5 Мбит/сек, MPEG-Audio - сжатие звука до 64, 128 или 192 Кбит/сек на канал и MPEG-System - синхронизация видео и аудио потоков [8.1]. Нас в основном будут интересовать достижения MPEG-Video, хотя очевидно, что многие решения в этом направлении принимались с учетом требований синхронизации.
Как алгоритм, MPEG имеет несколько предшественников. Это, прежде всего, универсальный алгоритм JPEG. Его универсальность означает, что JPEG показывает неплохие результаты на широком классе изображений.
Если быть более точным, то стандарт MPEG, как и другие стандарты на сжатие, описывает лишь выходной битовый поток, неявно задавая алгоритмы кодирования и декодирования. При этом их реализация перекладывается на программистов-разработчиков. Такой подход открывает широкие горизонты для тех, кто желает оптимально реализовать алгоритм для конкретного вычислительного устройства (контроллера, ПК, распределенной вычислительной системы), операционной системы, видеокарты и т.п. [8.2]. При специализированных реализациях могут быть учтены весьма специфические требования на время работы, расход памяти и качество получаемых изображений. Алгоритмы сжатия видео весьма гибки и зачастую для разных подходов к реализации, можно получить существенную разницу по качеству видео, при одной и той же степени сжатия. Более того - для одного и того же сжатого файла с помощью разных алгоритмов декодирования можно получить существенно различающиеся по визуальному качеству фильмы. Зачастую "простая" реализация
стандарта дает дергающий видеоряд с хорошо заметными блоками, в то время как программы известных производителей проигрывают этот же файл вполне плавно и без бросающейся в глаза блочности. Эти нюансы необходимо хорошо себе представлять, когда речь заходит о сравнении разных различных стандартов.
В сентябре 1990 был представлен предварительный стандарт кодирования MPEG-1. В январе 1992 работа над MPEG-1 была завершена, и начата работа над MPEG-2, в задачу которого входило описание потока данных со скоростью от 3 до 10 Мбит/сек [8.3]. Практически в то же время была начата работа над MPEG-3, который был предназначен для описания потоков 20-40 Мбит/сек. Однако вскоре выяснилось, что алгоритмические решения для MPEG-2 и MPEG-3 принципиально близки и можно безболезненно расширить рамки MPEG-2 до потоков в 40 Мбит/сек. В результате работа над MPEG-3 была прекращена. MPEG-2 был окончательно доработан к 1995 году.
В 1991 группой экспертов по видеотелефонам ( EGVT ) при Международном консультативный комитет по телефонии и телеграфии ( CCITT ) предложен стандарт видеотелефонов px64 Кbits. Запись рх64 означает, что алгоритм ориентирован на параллельную передачу оцифрованного видеоизображения по р каналам с пропускной способностью 64 Кбита/сек. Таким образом, захватывая несколько телефонных линий, можно получать изображение вполне приемлемого качества. Одним из главных ограничений при создании алгоритма являлось время задержки, которое должно было составлять не более 150 мс. Кроме того, уровень помех в телефонных каналах достаточно высок, и это, естественно, нашло отражение в алгоритме. Можно считать, что рх64 Kbits - предшественник MPEG-а для потоков данных менее 1,5 Мбит/сек и специфического класса видео.
В группе при CMTT (совместный комитет при CCITT и CCIR - International Consultative Committee on bRoadcasting ) работы были направлены на передачу оцифрованного видео по выделенным каналам с высокой пропускной способностью и радиолиниям. Соответствующие стандарты Н21 и Н22 ориентированы на 34 и 45 Мбит/сек, и сигнал передается с очень высоким качеством.
MPEG-4 изначально был задуман как стандарт для работы со сверхнизкими потоками. Однако в процессе довольно долгой подготовки стандарт претерпел совершенно революционные изменения и сейчас собственно сжатие с низким потоком входит в него как одна составная часть, причем достаточно небольшая по размеру. Например, сам формат сегодня включает в себя такие вещи, как синтез речи, рендеринг изображений и описания параметров визуализации лица на стороне программы просмотра.
Разработка MPEG-7 была начата в 1996. Собственно к алгоритмам сжатия видео этот стандарт имеет еще меньшее отношение, чем MPEG-4, поскольку его основная задача заключается в описании контента и управлении им. Описание MPEG-7 выходит за рамки это книги.
Параллельно все это время существовали форматы Motion-JPEG и недавно появившийся Motion-JPEG2000, предназначенные в основном для удобства обработки сжатого видео. Рассмотрим основные стандарты и лежащие в их основе алгоритмы поподробнее.
Базовые технологии сжатия видео
Описание алгоритма компрессии
Технология сжатия видео в MPEG распадается на две части: уменьшение избыточности видеоинформации во временном измерении, основанное на том, что соседние кадры, как правило, отличаются не сильно, и сжатие отдельных изображений.
Для того чтобы удовлетворить противоречивым требованиям и увеличить гибкость алгоритма, рассматривается четыре типа кадров:
I-кадры - кадры сжатые независимо от других кадров ( I-Intra pictures ),
P-кадры - сжатые с использованием ссылки на одно изображение ( P-Predicted ),
B-кадры - сжатые с использованием ссылки на два изображения ( B-Bidirection ),
DC-кадры - независимо сжатые с большой потерей качества (используются только при быстром поиске).
I-кадры обеспечивают возможность произвольного доступа к любому кадру, являясь своеобразными входными точками в поток данных для декодера. P-кадры используют при архивации ссылку на один I- или P-кадр, повышая тем самым степень сжатия фильма в целом. B-кадры, используя ссылки на два кадра, находящихся впереди и позади, обеспечивают наивысшую степень сжатия. Сами в качестве ссылки использоваться не могут. Последовательность кадров в фильме может быть, например, такой: IBBPBBPBBPBBIBBPBB... Или, если мы не экономим на степени сжатия, такой (рис. 8.1):
(рис 8.1) I-кадры - независимо сжатые (I-Intrapictures), P-кадры - сжатые с использованием ссылки на одно изображение (P-Predicted), B-кадры - сжатые с использованием ссылки на два изображения (B-Bidirection)Частота I-кадров выбирается в зависимости от требований на время произвольного доступа и надежности потока при передаче через канал с ошибками. Соотношение P- и B-кадров подбирается, исходя из требований к величине компрессии и ограничений декодера. Как правило, декодирование B-кадров требует больше вычислительных мощностей, однако позволяет повысить степень сжатия. Именно варьирование частоты кадров разных типов обеспечивает алгоритму необходимую гибкость и возможность расширения. Понятно, что для того, чтобы распаковать B-кадр, мы должны уже распаковать те кадры, на которые он ссылается. Поэтому для последовательности IBBPBBPBBPBBIBBPBB кадры в фильме будут записаны так: 0**312645..., где цифры - номера кадров, а звездочкам соответствуют либо В-кадры с номерами -1 и -2, если мы находимся в середине потока, либо пустые кадры (ничего), если мы в начале фильма. Подобный формат обладает достаточно
большой гибкостью и способен удовлетворять самым различным наборам требований.
Одним из основных понятий при сжатии нескольких изображений является понятие макроблока. При сжатии кадр из цветового пространства RGB переводится в цветовое пространство YUV. Каждая из плоскостей сжимаемого изображения ( Y, U, V ) разделяется на блоки 8x8, с которыми работает ДКП. Причем плоскости U и V, соответствующие компоненте цветности берутся с разрешением в два раза меньшим (по вертикали и горизонтали), чем исходное изображение. Таким образом, мы сразу получаем сжатие в два раза, пользуясь тем, что глаз человека хуже различает цвет отдельной точки изображения, чем ее яркость (подробнее об этих преобразованиях смотрите в описании алгоритма JPEG ). Блоки 8x8 группируются в макроблоки. Макроблок - это группа из четырех соседних блоков в плоскости яркостной компоненты Y (матрица пикселов 16x16 элементов) и два соответствующих им по расположению блока из плоскостей цветности U и V.
Таким образом, кадр разбивается на независимые единицы, несущие полную информацию о части изображения. При этом размер изображения должен быть кратен 16.
Отдельные макроблоки сжимаются независимо, т.е. в B-кадрах мы можем сжать макроблок конкретный как I-блок, P-блок со ссылкой на предыдущий кадр, P-блок со ссылкой на последующий кадр и, наконец, как В-блок.
Алгоритм сжатия отдельных кадров в MPEG похож на соответствующий алгоритм для статических изображений - JPEG. Если говорить коротко, то сам алгоритм сжатия представляет собой конвейер преобразований. Это дискретное косинусное преобразование исходной матрицы 8x8, квантование матрицы и вытягивание ее в вектор v11,v12,v21,v31,v22,...,v88 (зигзаг-сканирование), сжатие вектора групповым кодированием и, наконец, сжатие по алгоритму Хаффмана.
Общая схема алгоритма
В целом весь конвейер преобразований можно представить так:
Подготовка макроблоков. Для каждого макроблока определяется, каким образом он будет сжат. В I-кадрах все макроблоки сжимаются независимо. В P-кадрах блок либо сжимается независимо, либо представляет собой разность с одном из макроблоков в предыдущем опорном кадре, на который ссылается P-кадр.
Перевод макроблока в цветовое пространство YUV. Получение нужного количества матриц 8х8.
Для P-блоков и B-блоков производится вычисление разности с соответствующим макроблоком в опорном кадре.
ДКП
Квантование.
Зигзаг-сканирование.
Групповое кодирование.
Кодирование Хаффмана.
При декодировании весь конвейер повторяется для обратных преобразований, начиная с конца.
Использование векторов смещений блоков
Простейший способ учитывать подобие соседних кадров - это вычитать каждый блок сжимаемого кадра из соответствующего блока предыдущего. Однако более гибким является алгоритм поиска векторов, на которые сдвинулись блоки текущего кадра по отношению к предыдущему. Для каждого блока в изображении мы находим блок близкий по некоторой метрике (например, по сумме квадратов разности пикселей) в предыдущем кадре в некоторой окрестности текущего положения блока. Если минимальное расстояние по выбранной метрике с блоками в предыдущем кадре больше выбранного порога - блок сжимается независимо (рис. 8.2).
(рис 8.2) Таким образом, вместе с каждым блоком в поток теперь сохраняются координаты смещения максимально похожего блока в предыдущем I- или P-кадре, либо признак того, что данные сжаты независимо. Эти координаты задают вектор смещения блока ( motion vector ). В ситуациях, когда камера наезжает на объект или дает панораму, использование векторов смещений блоков позволяет значительно уменьшить амплитуду разности кадров, и как следствие - значительно поднять степень сжатия.
Если мы проанализируем реальные фильмы, то окажется, что часто блок сдвигается не на кратное число пикселов, а, например, на 10.4 пиксела (камера быстро движется вправо, план съемки сдвигается равномерно и проходит полный кадр размером 352х240 за 1.35 секунды). При этом оказывается, что для повышения степени сжатия выгодно строить 4 области поиска векторов смещений: исходную, сдвинутую на полпиксела по горизонтали, сдвинутую на полпиксела по вертикали и сдвинутую на полпиксела по горизонтали и по вертикали (по диагонали), которые строятся с помощью достаточно быстрых алгоритмов билинейной или кусочно-линейной аппроксимации. Этот прием также позволяет уменьшить разность между блоками и повысить степень сжатия при минимальной дополнительной информации, которую надо сохранять в файл (плюс 2 бита на каждый блок). Правда строить аппроксимированные блоки придется и при декомпрессии, однако это сравнительно дешевая по времени операция, которая весьма незначительно увеличивает общее время декомпрессии.
Также надо понимать, что алгоритм поиска оптимальных векторов смещения заключается, вообще говоря, в переборе. Существуют различные методы уменьшения этого перебора, и настройки видео-кодеков, регулирующие скорость сжатия нередко варьируют именно параметры метода перебора.
Возможности по распараллеливанию
Даже беглый взгляд на этот обобщенный алгоритм позволяет заметить, что он сравнительно легко распараллеливается. Изображение 320х288 содержит 330 макроблоков, которые можно кодировать и декодировать независимо. Каждый макроблок, в свою очередь, содержит шесть блоков данных для ДКП. Распараллелить ДКП очень важно, так как, не считая поиска векторов смещения, это самая медленная операция. Заметим также, что остальные преобразования легко конвейеризуются. В результате мы получаем параллельно-конвейерную схему обработки потока видеоданных.
Достаточно заманчиво выглядит возможность распараллелить обработку различных кадров, но здесь мы сталкиваемся со сложностями. Как правило, компрессор строится таким образом, чтобы после сжатия изображение подвергалось обратным преобразованиям. Таким образом, мы получаем кадр с потерями и архивируем остальные кадры, отталкиваясь от него. Это позволяет не накапливать ошибки, получаемые еще при квантовании. Таким образом, если на экране между кадрами наблюдались большие изменения, и качество изображения пришлось понизить, то при стабилизации изображения качество быстро повышается практически до качества исходного видеоряда. Неприятный эффект, порождаемый этим приемом, заключается в том, что появляется мерцание отдельных точек (или областей) изображения, значение цвета в которых округляется то в большую, то в меньшую сторону.
При распаковке наши возможности по параллельной обработке различных кадров достаточно ограничены, поскольку велика зависимость между кадрами в потоке (велик процент P- и B-кадров ).
Другие пути повышения степени сжатия
Описанный выше алгоритм в целом крайне близок большинству применяемых сейчас на практике алгоритмам сжатия видео. Однако новые (или хорошо забытые старые) идеи появляются ежегодно. Если для алгоритмов сжатия без потерь можно говорить о росте степени сжатия на 1% в год (относительно предыдущего года) для достаточно большого тестового массива данных, то для алгоритмов сжатия видео речь обычно идет о 3-5% прибавки степени сжатия для достаточно большого видеофрагмента при том же визуальном качестве.
Однако старое доброе "правило рычага", изобретенное еще Архимедом, соблюдается и здесь. И если с одной стороны повышается степень сжатия, то с другой стороны приходится пройти, прилагая ту же силу, гораздо больший путь. В данном случае растет сложность программы и падет скорость работы, как при компрессии, так и при декомпрессии.
Перечислим основные пути повышения степени сжатия:
Изменение алгоритма сжатия I-кадров. Выше приведен алгоритм, основанный на ДКП. Сегодня все чаще используются алгоритмы, основанные на вэйвлетах (см. описание JPEG-2000).
Изменение алгоритма сжатия без потерь. Выше приведен алгоритм, использующий сжатие по алгоритму Хаффмана. Однако недавно закончился основной патент на арифметическое сжатие (дающее преимущество 2-15%) и, соответственно, все чаще используется именно оно.
Изменение алгоритма работы с векторами смещения блоков. Подбор векторов смещений блоков по наименьшему среднеквадратичному смещению не является оптимальным. Cуществуют алгоритмы, дающие лучший результат при некоторых дополнительных затратах времени при сжатии.
Применение обработки коэффициентов. Можно пытаться получить больше информации об изображении из сохраненных коэффициентов. Например, возможно быстрое сравнение коэффициентов после ДКП в соседних блоках и их усреднение по достаточно сложным алгоритмам. Этот прием заметно снижает количество артефактов вносимых в изображение ДКП, при этом допуская реализацию, работающую в реальном времени.
Применение обработки получающихся кадров. Известная беда алгоритмов сжатия изображений - неизбежная "блочность" (хорошо заметные границы макроблоков). В принципе существуют алгоритмы, работающие с кадров совсем без применения блоков (даже без векторов смещения блоков), но такой подход пока не оправдывает себя ни по степени сжатия, ни по скорости работы декодера. Однако можно построить достаточно быстрые алгоритмы постобработки, которые достаточно аккуратно уберут видимые границы между блоками, не внося существенных помех в само изображение. Существуют также алгоритмы, устраняющие на лету эффект Гиббса (см. описание JPEG) и т.п. Таким образом, существенно улучшается визуальное качество изображения. Это также означает, что можно повысить степень сжатия при том же визуальном качестве.
Улучшение алгоритмов масштабирования изображений. Как правило, видео на компьютере просматривают во весь экран. При этом даже применение очень простого и быстрого кусочно-линейного масштабирования способно кардинально снизить скорость проигрывания ролика. То есть примитивная операция масштабирования изображения будет работать заметно дольше, чем сложный алгоритм декодера. Однако скорости современных компьютеров быстро растут и те алгоритмы, что вызывали падение скорости до 7 кадров в секунду на Celeron-300 дают живое видео - больше 30 кадров на P4-1200 (начинает использоваться расширенный набор команд и т.п.). Т.е. появляется возможность использовать более сложные и качественные алгоритмы масштабирования на весь экран, получая более высокое качество, чем для использовавшейся ранее билинейной интерполяции (в большинстве видеокарт реализованной аппаратно).
Применение предварительной обработки видео. Если мы хотим получить достаточно высокую степень сжатия, то можно заранее предсказать, что в нашем изображении пострадают высокие частоты. Оно станет сглаженным, пропадут многие мелкие детали. При этом, как правило, появляются дополнительные артефакты в виде полосок, ореолов у резких границ, волн. Значительно повысить качество изображения после кодирования позволяет предобработка с удалением высоких частот. При этом существуют алгоритмы, обрабатывающие поток таким образом, что визуально качество изображения не изменяется, однако после декодера мы получаем существенно более качественное изображение.
Выше перечислены лишь отдельные направления работ. Фактически за 90-е годы изменения и улучшения коснулись всех модулей алгоритма, построенного по классической схеме. Свою лепту в этот процесс вносят также производители микропроцессоров и в особенности Intel. Процессоры, начиная с P4, специально предназначены для обработки потоковых данных. Особенности архитектуры процессора (в частности небольшой по сравнению с процессорами AMD кэш первого уровня), дают значительное преимущество одним алгоритмам и делают неэффективными другие. Однако общее совершенствование алгоритмов сжатия видео идет очень быстро и в ближайшее время можно ожидать только увеличения скорости появления новых разработок.
Motion-JPEG
Motion-JPEG (или M-JPEG ) является наиболее простым алгоритмом сжатия видео. В нем каждый кадр сжимается независимо алгоритмом JPEG. Этот прием дает высокую скорость доступа к произвольным кадрам, как в прямом, так и в обратном порядке следования. Соответственно легко реализуются плавные "перемотки" в обоих направлениях, аудио-визуальная синхронизация и, что самое главное - редактирование. Типичные операции JPEG сейчас поддерживаются на аппаратном уровне большинством видеокарт и данный формат позволяет легко оперировать большими объемами данных при монтаже фильмов. Независимое сжатие отдельных кадров позволяет накладывать различные эффекты, не опасаясь, что взаимное влияние соседних кадров внесет дополнительные искажения в фильм.
Характеристики Motion-JPEGПоток, разрешение (сжатие): Поток и разрешение произвольные, сжатие в 5-10 раз
Плюсы: Обеспечивает быстрый произвольный доступ. Легко редактировать поток. Низкая стоимость аппаратной реализации.
Минусы: Сравнительно низкая степень сжатия.
MPEG-1
Алгоритм MPEG-1 в целом соответствует описанной выше общей схеме построения алгоритмов сжатия.
Характеристики MPEG-1Поток, разрешение: 1.5 Мбит/с, 352х240х30, 352х288х25
Плюсы: Сравнительно прост в аппаратной реализации, содержит преобразования, поддерживаемые на аппаратном уровне большим количеством видеокарт.
Минусы: Невысокая степень сжатия. Малая гибкость формата.
H.261
Стандарт H.261 специфицирует кодирование и декодирование видеопотока для передачи по каналу p*64 Кбит, где p=1..30. В качестве канала может выступать, например, несколько телефонных линий.
Входной формат изображения - разрешения CIF или QCIF в формате YUV (CCIR 601) частота кадров от 30 fps и ниже. Используется уменьшение разрешения в 2 раза для компонент цветности.
В выходной поток записываются два типа кадров: INTRA - сжатые независимо (соответствуют I-кадрам ) и INTER - сжатые со ссылкой на предыдущий кадр (соответствуют Р-кадрам ). В передаваемом кадре не обязательно присутствуют все макроблоки изображения, если блок изменился незначительно передавать его обычно нет смысла. Сжатие в INTRA кадрах осуществляется по схеме сжатия отдельного изображения. В INTER кадрах производится аналогичное сжатие разности каждого передаваемого макроблока с "наиболее похожим" макроблоком из предыдущего кадра (компенсация движения). Для сглаживания артефактов ДКП предусмотрена возможность применения размытия внутри каждого блока 8x8 пикселей. Стандарт требует, чтобы INTRA кадры встречались в потоке не реже чем через каждые 132 INTER кадра (чтобы не накапливалась погрешность кодирования и была возможность восстановиться в случае ошибки в потоке).
Степень сжатия зависит в основном от метода нахождения "похожих" макроблоков в предыдущем кадре, алгоритма решения передавать ли конкретный макроблок, выбора способа кодирования каждого макроблока ( INTER/INTRA ) и выбора коэффициентов квантования результатов ДКП. Ни один из перечисленных вопросы стандартом не регламентируются, оставляя свободу для построения собственных оптимальных алгоритмов.
Характеристики H.261Поток, разрешение: p*64 Кбит, p=1..30, CIF или QCIF
Плюсы: Прост в аппаратной реализации.
Минусы: Невысокая степень сжатия. Ограничения на формат.
H.263
Данный стандарт является расширением, дополнением и значительным усложнением H.261. Он содержит "базовый" стандарт кодирования, практически не отличающийся по алгоритмам сжатия от H.261, плюс множество опциональных его расширений. Кратко перечислим наиболее важные отличия:
Использование арифметического кодирования вместо кодов Хаффмана. Дает возможность на 5-10% повысить степень сжатия.
Возможность задания векторов смещения, указывающих за границы изображения. При этом граничные пиксели используются для предсказания пикселей вне изображения. Данный прием усложняет алгоритм декодирования, но позволяет значительно улучшить изображение при резкой смене плана сцены.
Возможность задания вектора смещения для каждого блока 8x8 в макроблоке, что в ряде случаев существенно увеличивает сжатие и снижает блочность изображения.
Появление B-кадров, которое позволяет увеличить степень сжатия, за счет усложнения и увеличения времени работы декодера.
Поддержка большого числа форматов входных видеоданных: sub-QCIF, QCIF, CIF, 4CIF, 16CIF и отдельно настраиваемые. Основное отличие от более универсальных форматов заключается в адаптации для нескольких фиксированных разрешений, что позволяет делать менее универсальные, но более быстрые процедуры обработки кадров. Построенный таким образом декодер работает несколько быстрее.
Компенсация движения с субпиксельной точностью. Возможность сдвинуть блок на полпиксела также увеличивает степень сжатия, но увеличивает время работы декодера.
Особый режим сжатия INTRA макроблоков со ссылкой на соседние макроблоки в обрабатываемом кадре, особый режим квантования и специальная таблица Хаффмана для улучшения сжатия I-кадров в ряде случаев.
Сглаживание границ блоков декодированного изображения для уменьшения эффекта "блочности". Зачастую при резком движении в кадре при сжатии алгоритм оказывается вынужден повысить степень квантования блоков после ДКП чтобы уложиться в отведенный на передачу битовый поток. При этом в кадре возникают хорошо вам знакомые по JPEG блоки размером 8х8. Как показала практика, "сращивание" границ, когда крайние пикселы блоков сдвигают по яркости так, чтобы уменьшить разницу, позволяет зачастую заметно повысить визуальное качество фильма.
Изменение разрешения и деформирование базового кадра, использующегося в качестве базового при сжатии.
Различные режимы квантования и кодирования по Хаффману.
Характеристики H.263Поток, разрешение: 0.04-20 Мбит/c, sub-QCIF, QCIF, CIF, 4CIF, 16CIF и отдельно настраиваемые разрешения.
Плюсы: Алгоритм H.263 также как H.261 допускает быструю аппаратную реализацию, однако при этом позволяет добиться большей степени сжатия при том же качестве. Поддерживает сжатие звука.
Минусы: По количеству заложенных идей находится между MPEG-2 и MPEG-4.
MPEG-2
Как уже говорилось, MPEG-2 занимается сжатием оцифрованного видео при потоке данных от 3 до 10 Мбит/сек. Многое в нем заимствовано из формата CCIR-601. CCIR-601 представляет собой стандарт цифрового видео с размером передаваемого изображения 720х486 при 60 полукадрах в секунду. Строки изображения передаются с чередованием, и два полукадра составляют кадр. Этот прием нередко применяют для уменьшения мерцания. Хроматические каналы ( U и V в YUV ) передаются размером 360х243 60 раз в секунду и также чередуются уже между собой. Подобное деление называется 4:2:2. Перевод из CCIR-601 в MPEG-I прост: надо поделить в 2 раза яркостную компоненту по горизонтали, поделить поток в 2 раза во временном измерении (убрав чередование), добавить вторую хроматическую компоненту и выкинуть "лишние" строки, чтобы размер по вертикали делился на 16. Мы получим поток YUV кадров размером 352х240 с
частотой 30 кадров в секунду. Здесь все просто.
Проблемы начинаются, когда появляется возможность увеличить поток данных и довести качество изображения до CCIR-601. Это не такая простая задача, как кажется. Проблема состоит в чередовании полукадров во входном формате. Тривиальное решение - работать с кадрами 720х486 при 30 кадрах в секунду, как с обычным видео. Этот путь приводит к неприятным эффектам при быстром движении объектов на экране. Между двумя исходными полукадрами 720х243 сдвиг становится заметным, а т.к. наш кадр формируется из исходных полукадров через строку, то при сжатии происходит размывание движущегося объекта. Виновно в этом эффекте ДКП, и как-то исправить ситуацию, не уменьшив степени сжатия видео, или не потеряв в визуальном качестве нельзя. Достаточно распространенным является применение "деинтерлейсинга" (от английского deinterlacing - удаление чередования строк). Эта операция позволяет удалить чередование, смещая четные строки в одном направлении, а нечетные в другом, пропорционально
относительному движению объекта в данной области экрана. В результате мы получаем визуально более качественное изображение, но несколько более длительную предобработку перед сжатием.
Другим решением является архивация четных и нечетных кадров в потоке CCIR-601 независимо. При этом мы, конечно, избавимся от артефактов, возникающих при быстром движении объектов, но существенно уменьшим степень сжатия, т.к. не будем использовать важнейшей вещи - избыточности между соседними кадрами, которая очень велика.
Характеристики MPEG-2Поток, разрешение: 3-15 Мбит/c, универсальный
Плюсы: Поддержка достаточно серьезных звуковых стандартов Dolby Digital 5.1, DTS, высокая универсальность, сравнительная простота аппаратной реализации.
Минусы: Недостаточная на сегодня степень сжатия, недостаточная гибкость.
MPEG-4
MPEG-4 кардинально отличается от принимаемых ранее стандартов. Рассмотрим наиболее интересные и полезные нововведения.
Расчет трехмерных сцен и работа с синтетическими объектами. В состав декодера MPEG-4 как составная часть входит блок визуализации трехмерных объектов ( Animation Framework eXtension - AFX - то, что в просторечии называют данными для трехмерного движка). Те, кто кодировал видео, знают, сколько проблем доставляют титры и вообще любые накладываемые поверх фильма объекты (логотипы, заставки и т.п.). Если хорошо выглядит основной план - будут подпорчены накладываемые объекты, если хорошо смотрятся они - будет низкой общая степень сжатия. В MPEG-4 предлагается решить проблему кардинально. Накладываемые объекты рассчитываются отдельно и накладываются потом. Кроме того, можно использовать видеопоток даже как текстуру, накладываемую на поверхности рассчитываемых объектов. Такая гибкая работа с трехмерными объектами позволяет существенно поднять степень сжатия при заметно лучшем качестве изображения. Более того - никто не мешает делать видеоролики вообще без живого
видео, а состоящие только из рассчитанных (синтетических) объектов. Размер их описания будет в разы меньше, чем размер аналогичных фильмов, сжатых просто как поток кадров. Кстати, отдельно в стандарте предусмотрена работа со "спрайтами" - статическими изображениями, накладываемыми на кадр. При этом размер спрайта может быть как совсем маленький (логотип канала в уголке экрана), так и превышать размер кадра и "прокручиваться" (т.е. в качестве "спрайта" может быть задан фон, а небольшие видео-объекты, например, голову диктора, будут на него накладывать). Это дает значительную гибкость при создании MPEG-4 фильмов и позволяет заметно уменьшить объем кодируемой информации.
Объектно-ориентированная работа с потоком данных. Теперь работа с потоком данных становится объектно-ориентированной. При этом данные могут быть живым видео, звуковыми данными, синтетическими объектами и т.д. Из них создаются сцены, этими сценами можно управлять. Для простых смертных при этом мало что изменится, однако для программистов объектная среда означает кардинальное упрощение работы с возникающими сложными структурами.
Помещение в поток двоичного кода "С++ подобного" языка BIFS. С помощью BIFS в поток добавляются описания объектов, классов объектов и сцен. Также на нем можно менять координаты, размеры, свойства, поведение и реакцию объектов на действия пользователя. В свое время Flash был назван революцией 2D графики в Интернете. Аналогичный прорыв в области видео совершает MPEG-4.
Активная зрительская позиция. Как было замечено выше, BIFS позволяет задавать реакцию объектов сцены на действия пользователя. Потенциально возможно удаление, добавление или перемещение объектов, ввод команд с клавиатуры. Событийная модель заимствована из развивавшегося уже долгое время языка моделирования виртуальной реальности VRML. Для тех, кто играл в написанные на VRML игры, очевидно, что в MPEG-4 будет совершенно реально создавать "квест"-подобные (и не только) игры. Широчайший простор открывается для создания обучающих и развлекательных программ. Представляете, скачиваете из Интернета один файл, который сразу в себе содержит все, что необходимо для небольшого курса лекций, причем вы можете прослушать его, видя говорящую голову преподавателя, или отключив его, можете увеличить фрагменты ("спрайты") с материалами. А в конце - пройти короткий тест на понимание предмета. Кстати - в стандарте предусмотрено обработка
команд на стороне сервера, т.е. программа-просмотрщик может отослать данные на сервер и получить оттуда оценку. Отличие от предыдущих стандартов революционное.
Синтезатор лиц и фигур. В стандарт заложен интерфейс к модулю синтеза лиц и фигур. Например, в файле сохраняются ключевые данные о профиле лица и текстуры лица, а при записи фильма сохраняются только коэффициенты изменения формы. Для передач типа новостей, этот прием позволяет в десятки раз сократить размер файла при замечательном качестве.
Синтезатор звуков и речи. Помимо синтеза лиц в стандарт MPEG-4 также заложены алгоритмы синтеза звуков, и даже речи(!).
Улучшенные алгоритмы сжатия видео. В стандарте предусмотрены блоки, отвечающие за потоки 4.8-65Кбит/с с прогрессивной разверткой и большие потоки с поддержкой чересстрочной развертки. Для передачи по ненадежным каналам возможно использование помехоустойчивых методов кодирования (за счет незначительного увеличения объема передаваемых данных резко снижается вероятность искажения изображения). При передаче видео с одновременным просмотром заложена возможность огрубить изображение, если декодер из-за ограничений канала связи не успевает получить всю информацию. Всего в стандарт заложено 3 уровня детализации. Эта возможность позволит легко адаптировать алгоритм для трансляций видео по сети.
Поддержка профилей на уровне стандарта. Понятно, что реализация всех возможностей стандарта превращает декодер в весьма сложную и большую конструкцию. При этом далеко не для всех приложений необходимы какие-то сложные специфические функции (например, синтез речи). Создатели стандарта поступили просто: они оговорили наборы профилей, каждый из которых включает в себя набор обязательных функций. Если в фильме записано, что ему для проигрывания необходим такой-то профиль и декодер этот профиль поддерживает, то стандарт гарантирует, что фильм будет проигран правильно.
Выше кратко перечислены некоторые отличия MPEG-4 от предыдущих стандартов. Надо отметить, что на момент создания стандарта острой потребности в описанных выше вещах еще не было. Иначе говоря, мы имеем дело с хорошо продуманной работой по формированию стандарта, которая была закончена к тому времени, как в нем возникла первая необходимость.
Создателями MPEG-4 учтен опыт предшественников (в частности VRML ), когда слишком раннее появление стандарта и отсутствие в нем механизма профилей серьезно подорвало его массовое применение. Будем надеяться, что массовому применению MPEG-4 такие проблемы не грозят.
Характеристики MPEG-4Поток, разрешение: 0,0048-20 Мбит/c, поддерживаются все основные стандарты видеопотоков.
Плюсы: Поддержка достаточно прогрессивных звуковых стандартов, высокая степень универсальности, поддержка новых технологий (различные виды синтеза звука и изображения).
Минусы: Высокая сложность реализации.
Сравнение стандартов
Систематизируем стандарты (табл. 8.1) и их характеристики (табл. 8.2)
| Название |
Год |
Разрешение и поток |
Аудио |
Применение |
|---|
| MPEG-1 |
1992 |
352х240х30,
352х288х25,
1.5 Мбит/с |
MPEG-1 Layer II |
VideoCD первого
поколения |
| H.261 |
1993 |
352х288х30,
176х144х30,
0,04-2 Мбит/c (px64 Кбит/с, где p от 1 до 30) |
— |
Аппаратно реализованные кодеки, видеоконференции |
| MPEG-2 |
1995 |
Универсальный,
3-15 Мбит/c |
MPEG-1 Layer II,
Dolby Digital 5.1, DTS |
DVD |
| H.263 |
1998 |
sub-QCIF, QCIF, CIF, 4CIF, 16CIF и настраиваемые особо |
Поддерживается |
Аппаратно реализованные кодеки, видеотелефоны, видеоконференции |
| MPEG-3
не принят |
1993-95 |
Телевидение высокой четкости,
20-40 Мбит/c |
|
HDTV |
| MPEG-4 |
1999 |
Универсальный,
0,0048-20 Мбит/c |
MPEG-1 Layer II,
MPEG-1 Layer III,
Dolby Digital 5.1, DTS |
VideoCD второго
поколения |
| Название |
За счет чего достигается сжатие |
Дополнительные возможности |
|---|
| MPEG-1 |
ICT, DCT |
|
| H.261 |
ICT, DCT, MC |
Передача потока данных по р-каналам с пропускной способностью 64Кбит (телеконференции по нескольким телефонным линиям). |
| MPEG-2 |
ICT, DCT, MC |
|
| MPEG-4 |
ICT, Wavelet, MC, спрайты, объекты с прозрачным фоном, 3d-рендеринг |
Встроенный язык описания BIFS, синтезатор речи, функции анимации лиц, 3D-рендеринг и т.д. |
Вопросы для самоконтроля
Какие параметры надо определить, прежде чем сравнивать два алгоритма сжатия видео?
Приведите примеры ситуаций, когда архитектура компьютера дает преимущества тому или иному алгоритму сжатия видео.
Какими свойствами видеопотока мы можем пользоваться, создавая алгоритм сжатия? Приведите примеры.
Что такое аудио-визуальная синхронизация? Почему выполнение ее требований значительно снижает степень сжатия?
Назовите основные требования к алгоритмам сжатия видео.
Что такое I-кадры, P-кадры?
Приведите примеры программно-аппаратной реализации алгоритмов сжатия видео (повседневные и достаточно новые).
Приведите примеры областей использования видео НЕ критичных к требованию "устойчивости к ошибкам".
Введение
Основной сложностью при работе с видео являются большие объемы дискового пространства, необходимого для хранения даже небольших фрагментов. Причем даже применение современных алгоритмов сжатия не изменяет ситуацию кардинально. При записи на один компакт-диск "в бытовом качестве", на него можно поместить несколько тысяч фотографий, примерно 10 часов музыки и всего полчаса видео. Видео "телевизионного" формата 720х576 пикселов 25 кадров в секунду в системе RGB требует потока данных примерно в 240 Мбит/сек (т.е. 1.8 Гб в минуту). При этом традиционные алгоритмы сжатия изображений, ориентированные на отдельные кадры, не спасают ситуации, поскольку даже при уменьшении потока в 10 раз он составляет достаточно большие величины.
В результате подавляющее большинство сегодняшних алгоритмов сжатия видео являются алгоритмами с потерей данных. При сжатии используется несколько типов избыточности:
Когерентность областей изображения - малое изменение цвета изображения в соседних пикселах (свойство, которое эксплуатируют все алгоритмы сжатия изображений с потерями).
Избыточность в цветовых плоскостях - используется большая важность яркости изображения для восприятия.
Подобие между кадрами - использование того факта, что на скорости 25 кадров в секунду, как правило, соседние кадры изменяются незначительно.
Первые два пункта знакомы вам по алгоритмам сжатия графики. Использование подобия между кадрами в самом простом и наиболее часто используемом случае означает кодирование не самого нового кадра, а его разности с предыдущим кадром. Для видео типа "говорящая голова" (передача новостей, видеотелефоны), большая часть кадра остается неизменной, и даже такой простой метод позволяет значительно уменьшить поток данных. Более сложный метод заключается в нахождении для каждого блока в сжимаемом кадре наименее отличающегося от него блока в кадре, используемом в качестве базового. Далее кодируется разница между этими блоками. Этот метод существенно более ресурсоемкий.
Основные понятия
Определимся с основными понятиями, которые используются при сжатии видео. Видеопоток характеризуется разрешением, частотой кадров и системой представления цветов. Из телевизионных стандартов пришли разрешения в 720х576 и 640х480, и частоты в 25 (стандарты PAL или SECAM ) и 30 (стандарт NTSC ) кадров в секунду. Для низких разрешений существуют специальные названия CIF - Common Interchange Format, равный 352х288 и QCIF - Quartered Common Interchange Format, равный 176х144. Поскольку CIF и QCIF ориентированы на крайне небольшие потоки, то с ними работают на частотах от 5 до 30 кадров в секунду.
Требования приложений к алгоритму
Для алгоритмов сжатия видео характерны большинство тех же требований приложений, которые предъявляются к алгоритмам сжатия графики, однако есть и определенная специфика:
Произвольный доступ - подразумевает возможность найти и показать любой кадр за ограниченное время. Обеспечивается наличием в потоке данных так называемых точек входа - кадров, сжатых независимо (т.е. как обычное статическое изображение). Приемлемым временем поиска произвольного кадра считается 1/2 секунды.
Быстрый поиск вперед/назад - подразумевает быстрый показ кадров, не следующих друг за другом в исходном потоке. Требует наличия дополнительной информации в потоке. Эта возможность активно используется всевозможными проигрывателями.
Показ кадров фильма в обратном направлении. Редко требуется в приложениях. При жестких ограничениях на время показа очередного кадра выполнение этого требования может резко уменьшить степень сжатия.
Аудио-визуальная синхронизация - самое серьезное требование. Данные, необходимые для того, чтобы добиться синхронности аудио и видео дорожек, существенно увеличивают размер фильма. Для видеосистемы это означает, что, если мы не успеваем достать и показать в нужный момент времени некий кадр, то мы должны уметь корректно показать, например, кадр, следующий за ним. Если мы показываем фильм без звука, то можно позволить себе чуть более медленный или более быстрый показ. Во времена сравнительно несовершенного немого кино кадры шли настолько неравномерно, насколько неравномерно крутил ручку камеры оператор. Показ без звука фильма, снятого столь несовершенными методами, воспринимается нормально даже при условии, что частота показываемых кадров постоянна (и герои фильма то передвигаются карикатурно быстро, то медленно). Однако смотреть фильм (например, боевик), в котором видеосистема не успевает за звуком - становится мучением.
Устойчивость к ошибкам - требование, обусловленное тем, что большинство каналов связи ненадежны. Испорченное помехой изображение должно быстро восстанавливаться. Требование достаточно легко удовлетворяется необходимым числом независимых кадров в потоке. При этом также уменьшается степень сжатия, так как на экране 2-3 секунды (50-75 кадров) может быть одно и то же изображение, но мы будем вынуждены нагружать поток независимыми кадрами.
Время кодирования/декодирования. Во многих системах (например, видеотелефонах) общая задержка на кодирование-передачу-декодирование должна составлять не более 150 мс. Кроме того, в приложениях, где необходимо редактирование, нормальная интерактивная работа невозможна, если время реакции системы составляет более 1 секунды.
Редактируемость. Под редактируемостью понимается возможность изменять все кадры так же легко, как если бы они были записаны независимо.
Масштабируемость - простота реализации концепции "видео в окне". Мы должны уметь быстро изменять высоту и ширину изображения в пикселах. Масштабирование способно породить неприятные эффекты в алгоритмах основанных на ДКП (дискретном косинусном преобразовании). Корректно реализовать эту возможность для MPEG на данный момент можно, пожалуй, лишь при достаточно сложных аппаратных реализациях, только тогда алгоритмы масштабирования не будут существенно увеличивать время декодирования. Интересно, что масштабирование достаточно легко осуществляется в так называемых фрактальных алгоритмах. В них, даже при увеличении изображения в несколько раз, оно не распадается на квадраты, т.е. отсутствует эффект "зернистости". Если необходимо уменьшать изображение (что, хоть и редко, но бывает нужно), то с такой задачей хорошо справляются алгоритмы, основанные на wavelet преобразовании (см. описание JPEG-2000).
Небольшая стоимость аппаратной реализации. При разработке хотя бы приблизительно должна оцениваться и учитываться конечная стоимость. Если эта стоимость велика, то даже при использовании алгоритма в международных стандартах, производители будут предлагать свои, более конкурентоспособные, алгоритмы и решения. На практике это требование означает, что алгоритм должен реализовываться небольшим набором микросхем.
Упражнение: Покажите, что требования произвольного доступа, быстрого поиска, показа в обратном направлении, аудио-визуальной синхронизации и устойчивости к ошибкам противоречат условию высокой степени сжатия потока.
Описанные требования к алгоритму противоречивы. Очевидно, что высокая степень сжатия подразумевает архивацию каждого последующего кадра с использованием предыдущего. В то же время требования на аудио-визуальную синхронизацию и произвольный доступ к любому кадру за ограниченное время не дают возможности вытянуть все кадры в цепочку. И, тем не менее, можно попытаться прийти к некоторому компромиссу. Сбалансированная реализация, учитывающая систему противоречивых требований, может достигаться на практике за счет настроек компрессора при сжатии конкретного фильма.
Определение требований
Под процедурой определения требований, предъявляемых к алгоритму, понимается уяснение классов программного и аппаратного обеспечения, на которые он ориентирован и, соответственно, выработка требований к нему.
Носители информации, на которые ориентирован алгоритм:
DVD-ROM - сравнительно низкая стоимость, очень высокая плотность записи информации делают его наиболее перспективным устройством для хранения оцифрованного видео.
CD-ROM - низкая стоимость при высокой плотности записи информации делают его наиболее привлекательным устройством для хранения оцифрованного видео. К недостаткам относится сравнительно малый объем, однако диск обладает рекордно низким отношением стоимости диска к объему.
Жесткий диск - наиболее быстрое и гибкое устройство, обладающее очень малым временем поиска, что необходимо для некоторых приложений. Однако он имеет высокое соотношение стоимости диска к объему.
Перезаписываемые оптические диски - одно из наиболее перспективных устройств, способных сочетать в себе достоинства CD-ROM (низкая себестоимость хранения информации, большой объем, произвольный доступ) и жесткого диска (возможность перезаписи).
Компьютерные сети (как глобальные, так и локальные). Характеризуются возможностью быстро получать практически неограниченные объемы информации. К недостаткам сетей, с которыми борются так называемые технологии QoS (Quality of Service - гарантированное качество сервиса), относятся возможные задержки пакетов, и произвольное изменение пропускной способности канала.
Программное обеспечение, использующее видео-компрессию, можно подразделить на две группы - симметричное и асимметричное.
Асимметричные приложения предъявляют серьезные требования к декодеру (как правило, по времени и памяти), но для них безразличны затраты ресурсов при кодировании. Примером являются различные мультимедиа энциклопедии, путеводители, справочники, игры и просто фильмы. При такой постановке задачи появляется возможность применить сложные алгоритмы компрессии, позволяющие получить большую степень сжатия данных.
Симметричные приложения предъявляют одинаково жесткие требования на время, память и другие ресурсы, как при кодировании, так и при декодировании. Примерами такого рода приложений могут служить видеопочта, видеотелефон, видеоконференции, редактирование и подготовка видеоматериалов.
Обзор стандартов
В 1988 году в рамках Международной Организации по Стандартизации ( ISO ) начала работу группа MPEG (Moving Pictures Experts Group) - группа экспертов в области цифрового видео ( ISO-IEC/JTC1/SC2/WG11/MPEG ). Группа работала в направлениях, которые можно условно назвать MPEG-Video - сжатие видеосигнала в поток со скоростью до 1,5 Мбит/сек, MPEG-Audio - сжатие звука до 64, 128 или 192 Кбит/сек на канал и MPEG-System - синхронизация видео и аудио потоков [8.1]. Нас в основном будут интересовать достижения MPEG-Video, хотя очевидно, что многие решения в этом направлении принимались с учетом требований синхронизации.
Как алгоритм, MPEG имеет несколько предшественников. Это, прежде всего, универсальный алгоритм JPEG. Его универсальность означает, что JPEG показывает неплохие результаты на широком классе изображений.
Если быть более точным, то стандарт MPEG, как и другие стандарты на сжатие, описывает лишь выходной битовый поток, неявно задавая алгоритмы кодирования и декодирования. При этом их реализация перекладывается на программистов-разработчиков. Такой подход открывает широкие горизонты для тех, кто желает оптимально реализовать алгоритм для конкретного вычислительного устройства (контроллера, ПК, распределенной вычислительной системы), операционной системы, видеокарты и т.п. [8.2]. При специализированных реализациях могут быть учтены весьма специфические требования на время работы, расход памяти и качество получаемых изображений. Алгоритмы сжатия видео весьма гибки и зачастую для разных подходов к реализации, можно получить существенную разницу по качеству видео, при одной и той же степени сжатия. Более того - для одного и того же сжатого файла с помощью разных алгоритмов декодирования можно получить существенно различающиеся по визуальному качеству фильмы. Зачастую "простая" реализация
стандарта дает дергающий видеоряд с хорошо заметными блоками, в то время как программы известных производителей проигрывают этот же файл вполне плавно и без бросающейся в глаза блочности. Эти нюансы необходимо хорошо себе представлять, когда речь заходит о сравнении разных различных стандартов.
В сентябре 1990 был представлен предварительный стандарт кодирования MPEG-1. В январе 1992 работа над MPEG-1 была завершена, и начата работа над MPEG-2, в задачу которого входило описание потока данных со скоростью от 3 до 10 Мбит/сек [8.3]. Практически в то же время была начата работа над MPEG-3, который был предназначен для описания потоков 20-40 Мбит/сек. Однако вскоре выяснилось, что алгоритмические решения для MPEG-2 и MPEG-3 принципиально близки и можно безболезненно расширить рамки MPEG-2 до потоков в 40 Мбит/сек. В результате работа над MPEG-3 была прекращена. MPEG-2 был окончательно доработан к 1995 году.
В 1991 группой экспертов по видеотелефонам ( EGVT ) при Международном консультативный комитет по телефонии и телеграфии ( CCITT ) предложен стандарт видеотелефонов px64 Кbits. Запись рх64 означает, что алгоритм ориентирован на параллельную передачу оцифрованного видеоизображения по р каналам с пропускной способностью 64 Кбита/сек. Таким образом, захватывая несколько телефонных линий, можно получать изображение вполне приемлемого качества. Одним из главных ограничений при создании алгоритма являлось время задержки, которое должно было составлять не более 150 мс. Кроме того, уровень помех в телефонных каналах достаточно высок, и это, естественно, нашло отражение в алгоритме. Можно считать, что рх64 Kbits - предшественник MPEG-а для потоков данных менее 1,5 Мбит/сек и специфического класса видео.
В группе при CMTT (совместный комитет при CCITT и CCIR - International Consultative Committee on bRoadcasting ) работы были направлены на передачу оцифрованного видео по выделенным каналам с высокой пропускной способностью и радиолиниям. Соответствующие стандарты Н21 и Н22 ориентированы на 34 и 45 Мбит/сек, и сигнал передается с очень высоким качеством.
MPEG-4 изначально был задуман как стандарт для работы со сверхнизкими потоками. Однако в процессе довольно долгой подготовки стандарт претерпел совершенно революционные изменения и сейчас собственно сжатие с низким потоком входит в него как одна составная часть, причем достаточно небольшая по размеру. Например, сам формат сегодня включает в себя такие вещи, как синтез речи, рендеринг изображений и описания параметров визуализации лица на стороне программы просмотра.
Разработка MPEG-7 была начата в 1996. Собственно к алгоритмам сжатия видео этот стандарт имеет еще меньшее отношение, чем MPEG-4, поскольку его основная задача заключается в описании контента и управлении им. Описание MPEG-7 выходит за рамки это книги.
Параллельно все это время существовали форматы Motion-JPEG и недавно появившийся Motion-JPEG2000, предназначенные в основном для удобства обработки сжатого видео. Рассмотрим основные стандарты и лежащие в их основе алгоритмы поподробнее.
Базовые технологии сжатия видео
Описание алгоритма компрессии
Технология сжатия видео в MPEG распадается на две части: уменьшение избыточности видеоинформации во временном измерении, основанное на том, что соседние кадры, как правило, отличаются не сильно, и сжатие отдельных изображений.
Для того чтобы удовлетворить противоречивым требованиям и увеличить гибкость алгоритма, рассматривается четыре типа кадров:
I-кадры - кадры сжатые независимо от других кадров ( I-Intra pictures ),
P-кадры - сжатые с использованием ссылки на одно изображение ( P-Predicted ),
B-кадры - сжатые с использованием ссылки на два изображения ( B-Bidirection ),
DC-кадры - независимо сжатые с большой потерей качества (используются только при быстром поиске).
I-кадры обеспечивают возможность произвольного доступа к любому кадру, являясь своеобразными входными точками в поток данных для декодера. P-кадры используют при архивации ссылку на один I- или P-кадр, повышая тем самым степень сжатия фильма в целом. B-кадры, используя ссылки на два кадра, находящихся впереди и позади, обеспечивают наивысшую степень сжатия. Сами в качестве ссылки использоваться не могут. Последовательность кадров в фильме может быть, например, такой: IBBPBBPBBPBBIBBPBB... Или, если мы не экономим на степени сжатия, такой (рис. 8.1):
(рис 8.1) I-кадры - независимо сжатые (I-Intrapictures), P-кадры - сжатые с использованием ссылки на одно изображение (P-Predicted), B-кадры - сжатые с использованием ссылки на два изображения (B-Bidirection)Частота I-кадров выбирается в зависимости от требований на время произвольного доступа и надежности потока при передаче через канал с ошибками. Соотношение P- и B-кадров подбирается, исходя из требований к величине компрессии и ограничений декодера. Как правило, декодирование B-кадров требует больше вычислительных мощностей, однако позволяет повысить степень сжатия. Именно варьирование частоты кадров разных типов обеспечивает алгоритму необходимую гибкость и возможность расширения. Понятно, что для того, чтобы распаковать B-кадр, мы должны уже распаковать те кадры, на которые он ссылается. Поэтому для последовательности IBBPBBPBBPBBIBBPBB кадры в фильме будут записаны так: 0**312645..., где цифры - номера кадров, а звездочкам соответствуют либо В-кадры с номерами -1 и -2, если мы находимся в середине потока, либо пустые кадры (ничего), если мы в начале фильма. Подобный формат обладает достаточно
большой гибкостью и способен удовлетворять самым различным наборам требований.
Одним из основных понятий при сжатии нескольких изображений является понятие макроблока. При сжатии кадр из цветового пространства RGB переводится в цветовое пространство YUV. Каждая из плоскостей сжимаемого изображения ( Y, U, V ) разделяется на блоки 8x8, с которыми работает ДКП. Причем плоскости U и V, соответствующие компоненте цветности берутся с разрешением в два раза меньшим (по вертикали и горизонтали), чем исходное изображение. Таким образом, мы сразу получаем сжатие в два раза, пользуясь тем, что глаз человека хуже различает цвет отдельной точки изображения, чем ее яркость (подробнее об этих преобразованиях смотрите в описании алгоритма JPEG ). Блоки 8x8 группируются в макроблоки. Макроблок - это группа из четырех соседних блоков в плоскости яркостной компоненты Y (матрица пикселов 16x16 элементов) и два соответствующих им по расположению блока из плоскостей цветности U и V.
Таким образом, кадр разбивается на независимые единицы, несущие полную информацию о части изображения. При этом размер изображения должен быть кратен 16.
Отдельные макроблоки сжимаются независимо, т.е. в B-кадрах мы можем сжать макроблок конкретный как I-блок, P-блок со ссылкой на предыдущий кадр, P-блок со ссылкой на последующий кадр и, наконец, как В-блок.
Алгоритм сжатия отдельных кадров в MPEG похож на соответствующий алгоритм для статических изображений - JPEG. Если говорить коротко, то сам алгоритм сжатия представляет собой конвейер преобразований. Это дискретное косинусное преобразование исходной матрицы 8x8, квантование матрицы и вытягивание ее в вектор v11,v12,v21,v31,v22,...,v88 (зигзаг-сканирование), сжатие вектора групповым кодированием и, наконец, сжатие по алгоритму Хаффмана.
Общая схема алгоритма
В целом весь конвейер преобразований можно представить так:
Подготовка макроблоков. Для каждого макроблока определяется, каким образом он будет сжат. В I-кадрах все макроблоки сжимаются независимо. В P-кадрах блок либо сжимается независимо, либо представляет собой разность с одном из макроблоков в предыдущем опорном кадре, на который ссылается P-кадр.
Перевод макроблока в цветовое пространство YUV. Получение нужного количества матриц 8х8.
Для P-блоков и B-блоков производится вычисление разности с соответствующим макроблоком в опорном кадре.
ДКП
Квантование.
Зигзаг-сканирование.
Групповое кодирование.
Кодирование Хаффмана.
При декодировании весь конвейер повторяется для обратных преобразований, начиная с конца.
Использование векторов смещений блоков
Простейший способ учитывать подобие соседних кадров - это вычитать каждый блок сжимаемого кадра из соответствующего блока предыдущего. Однако более гибким является алгоритм поиска векторов, на которые сдвинулись блоки текущего кадра по отношению к предыдущему. Для каждого блока в изображении мы находим блок близкий по некоторой метрике (например, по сумме квадратов разности пикселей) в предыдущем кадре в некоторой окрестности текущего положения блока. Если минимальное расстояние по выбранной метрике с блоками в предыдущем кадре больше выбранного порога - блок сжимается независимо (рис. 8.2).
(рис 8.2) Таким образом, вместе с каждым блоком в поток теперь сохраняются координаты смещения максимально похожего блока в предыдущем I- или P-кадре, либо признак того, что данные сжаты независимо. Эти координаты задают вектор смещения блока ( motion vector ). В ситуациях, когда камера наезжает на объект или дает панораму, использование векторов смещений блоков позволяет значительно уменьшить амплитуду разности кадров, и как следствие - значительно поднять степень сжатия.
Если мы проанализируем реальные фильмы, то окажется, что часто блок сдвигается не на кратное число пикселов, а, например, на 10.4 пиксела (камера быстро движется вправо, план съемки сдвигается равномерно и проходит полный кадр размером 352х240 за 1.35 секунды). При этом оказывается, что для повышения степени сжатия выгодно строить 4 области поиска векторов смещений: исходную, сдвинутую на полпиксела по горизонтали, сдвинутую на полпиксела по вертикали и сдвинутую на полпиксела по горизонтали и по вертикали (по диагонали), которые строятся с помощью достаточно быстрых алгоритмов билинейной или кусочно-линейной аппроксимации. Этот прием также позволяет уменьшить разность между блоками и повысить степень сжатия при минимальной дополнительной информации, которую надо сохранять в файл (плюс 2 бита на каждый блок). Правда строить аппроксимированные блоки придется и при декомпрессии, однако это сравнительно дешевая по времени операция, которая весьма незначительно увеличивает общее время декомпрессии.
Также надо понимать, что алгоритм поиска оптимальных векторов смещения заключается, вообще говоря, в переборе. Существуют различные методы уменьшения этого перебора, и настройки видео-кодеков, регулирующие скорость сжатия нередко варьируют именно параметры метода перебора.
Возможности по распараллеливанию
Даже беглый взгляд на этот обобщенный алгоритм позволяет заметить, что он сравнительно легко распараллеливается. Изображение 320х288 содержит 330 макроблоков, которые можно кодировать и декодировать независимо. Каждый макроблок, в свою очередь, содержит шесть блоков данных для ДКП. Распараллелить ДКП очень важно, так как, не считая поиска векторов смещения, это самая медленная операция. Заметим также, что остальные преобразования легко конвейеризуются. В результате мы получаем параллельно-конвейерную схему обработки потока видеоданных.
Достаточно заманчиво выглядит возможность распараллелить обработку различных кадров, но здесь мы сталкиваемся со сложностями. Как правило, компрессор строится таким образом, чтобы после сжатия изображение подвергалось обратным преобразованиям. Таким образом, мы получаем кадр с потерями и архивируем остальные кадры, отталкиваясь от него. Это позволяет не накапливать ошибки, получаемые еще при квантовании. Таким образом, если на экране между кадрами наблюдались большие изменения, и качество изображения пришлось понизить, то при стабилизации изображения качество быстро повышается практически до качества исходного видеоряда. Неприятный эффект, порождаемый этим приемом, заключается в том, что появляется мерцание отдельных точек (или областей) изображения, значение цвета в которых округляется то в большую, то в меньшую сторону.
При распаковке наши возможности по параллельной обработке различных кадров достаточно ограничены, поскольку велика зависимость между кадрами в потоке (велик процент P- и B-кадров ).
Другие пути повышения степени сжатия
Описанный выше алгоритм в целом крайне близок большинству применяемых сейчас на практике алгоритмам сжатия видео. Однако новые (или хорошо забытые старые) идеи появляются ежегодно. Если для алгоритмов сжатия без потерь можно говорить о росте степени сжатия на 1% в год (относительно предыдущего года) для достаточно большого тестового массива данных, то для алгоритмов сжатия видео речь обычно идет о 3-5% прибавки степени сжатия для достаточно большого видеофрагмента при том же визуальном качестве.
Однако старое доброе "правило рычага", изобретенное еще Архимедом, соблюдается и здесь. И если с одной стороны повышается степень сжатия, то с другой стороны приходится пройти, прилагая ту же силу, гораздо больший путь. В данном случае растет сложность программы и падет скорость работы, как при компрессии, так и при декомпрессии.
Перечислим основные пути повышения степени сжатия:
Изменение алгоритма сжатия I-кадров. Выше приведен алгоритм, основанный на ДКП. Сегодня все чаще используются алгоритмы, основанные на вэйвлетах (см. описание JPEG-2000).
Изменение алгоритма сжатия без потерь. Выше приведен алгоритм, использующий сжатие по алгоритму Хаффмана. Однако недавно закончился основной патент на арифметическое сжатие (дающее преимущество 2-15%) и, соответственно, все чаще используется именно оно.
Изменение алгоритма работы с векторами смещения блоков. Подбор векторов смещений блоков по наименьшему среднеквадратичному смещению не является оптимальным. Cуществуют алгоритмы, дающие лучший результат при некоторых дополнительных затратах времени при сжатии.
Применение обработки коэффициентов. Можно пытаться получить больше информации об изображении из сохраненных коэффициентов. Например, возможно быстрое сравнение коэффициентов после ДКП в соседних блоках и их усреднение по достаточно сложным алгоритмам. Этот прием заметно снижает количество артефактов вносимых в изображение ДКП, при этом допуская реализацию, работающую в реальном времени.
Применение обработки получающихся кадров. Известная беда алгоритмов сжатия изображений - неизбежная "блочность" (хорошо заметные границы макроблоков). В принципе существуют алгоритмы, работающие с кадров совсем без применения блоков (даже без векторов смещения блоков), но такой подход пока не оправдывает себя ни по степени сжатия, ни по скорости работы декодера. Однако можно построить достаточно быстрые алгоритмы постобработки, которые достаточно аккуратно уберут видимые границы между блоками, не внося существенных помех в само изображение. Существуют также алгоритмы, устраняющие на лету эффект Гиббса (см. описание JPEG) и т.п. Таким образом, существенно улучшается визуальное качество изображения. Это также означает, что можно повысить степень сжатия при том же визуальном качестве.
Улучшение алгоритмов масштабирования изображений. Как правило, видео на компьютере просматривают во весь экран. При этом даже применение очень простого и быстрого кусочно-линейного масштабирования способно кардинально снизить скорость проигрывания ролика. То есть примитивная операция масштабирования изображения будет работать заметно дольше, чем сложный алгоритм декодера. Однако скорости современных компьютеров быстро растут и те алгоритмы, что вызывали падение скорости до 7 кадров в секунду на Celeron-300 дают живое видео - больше 30 кадров на P4-1200 (начинает использоваться расширенный набор команд и т.п.). Т.е. появляется возможность использовать более сложные и качественные алгоритмы масштабирования на весь экран, получая более высокое качество, чем для использовавшейся ранее билинейной интерполяции (в большинстве видеокарт реализованной аппаратно).
Применение предварительной обработки видео. Если мы хотим получить достаточно высокую степень сжатия, то можно заранее предсказать, что в нашем изображении пострадают высокие частоты. Оно станет сглаженным, пропадут многие мелкие детали. При этом, как правило, появляются дополнительные артефакты в виде полосок, ореолов у резких границ, волн. Значительно повысить качество изображения после кодирования позволяет предобработка с удалением высоких частот. При этом существуют алгоритмы, обрабатывающие поток таким образом, что визуально качество изображения не изменяется, однако после декодера мы получаем существенно более качественное изображение.
Выше перечислены лишь отдельные направления работ. Фактически за 90-е годы изменения и улучшения коснулись всех модулей алгоритма, построенного по классической схеме. Свою лепту в этот процесс вносят также производители микропроцессоров и в особенности Intel. Процессоры, начиная с P4, специально предназначены для обработки потоковых данных. Особенности архитектуры процессора (в частности небольшой по сравнению с процессорами AMD кэш первого уровня), дают значительное преимущество одним алгоритмам и делают неэффективными другие. Однако общее совершенствование алгоритмов сжатия видео идет очень быстро и в ближайшее время можно ожидать только увеличения скорости появления новых разработок.
Motion-JPEG
Motion-JPEG (или M-JPEG ) является наиболее простым алгоритмом сжатия видео. В нем каждый кадр сжимается независимо алгоритмом JPEG. Этот прием дает высокую скорость доступа к произвольным кадрам, как в прямом, так и в обратном порядке следования. Соответственно легко реализуются плавные "перемотки" в обоих направлениях, аудио-визуальная синхронизация и, что самое главное - редактирование. Типичные операции JPEG сейчас поддерживаются на аппаратном уровне большинством видеокарт и данный формат позволяет легко оперировать большими объемами данных при монтаже фильмов. Независимое сжатие отдельных кадров позволяет накладывать различные эффекты, не опасаясь, что взаимное влияние соседних кадров внесет дополнительные искажения в фильм.
Характеристики Motion-JPEGПоток, разрешение (сжатие): Поток и разрешение произвольные, сжатие в 5-10 раз
Плюсы: Обеспечивает быстрый произвольный доступ. Легко редактировать поток. Низкая стоимость аппаратной реализации.
Минусы: Сравнительно низкая степень сжатия.
MPEG-1
Алгоритм MPEG-1 в целом соответствует описанной выше общей схеме построения алгоритмов сжатия.
Характеристики MPEG-1Поток, разрешение: 1.5 Мбит/с, 352х240х30, 352х288х25
Плюсы: Сравнительно прост в аппаратной реализации, содержит преобразования, поддерживаемые на аппаратном уровне большим количеством видеокарт.
Минусы: Невысокая степень сжатия. Малая гибкость формата.
H.261
Стандарт H.261 специфицирует кодирование и декодирование видеопотока для передачи по каналу p*64 Кбит, где p=1..30. В качестве канала может выступать, например, несколько телефонных линий.
Входной формат изображения - разрешения CIF или QCIF в формате YUV (CCIR 601) частота кадров от 30 fps и ниже. Используется уменьшение разрешения в 2 раза для компонент цветности.
В выходной поток записываются два типа кадров: INTRA - сжатые независимо (соответствуют I-кадрам ) и INTER - сжатые со ссылкой на предыдущий кадр (соответствуют Р-кадрам ). В передаваемом кадре не обязательно присутствуют все макроблоки изображения, если блок изменился незначительно передавать его обычно нет смысла. Сжатие в INTRA кадрах осуществляется по схеме сжатия отдельного изображения. В INTER кадрах производится аналогичное сжатие разности каждого передаваемого макроблока с "наиболее похожим" макроблоком из предыдущего кадра (компенсация движения). Для сглаживания артефактов ДКП предусмотрена возможность применения размытия внутри каждого блока 8x8 пикселей. Стандарт требует, чтобы INTRA кадры встречались в потоке не реже чем через каждые 132 INTER кадра (чтобы не накапливалась погрешность кодирования и была возможность восстановиться в случае ошибки в потоке).
Степень сжатия зависит в основном от метода нахождения "похожих" макроблоков в предыдущем кадре, алгоритма решения передавать ли конкретный макроблок, выбора способа кодирования каждого макроблока ( INTER/INTRA ) и выбора коэффициентов квантования результатов ДКП. Ни один из перечисленных вопросы стандартом не регламентируются, оставляя свободу для построения собственных оптимальных алгоритмов.
Характеристики H.261Поток, разрешение: p*64 Кбит, p=1..30, CIF или QCIF
Плюсы: Прост в аппаратной реализации.
Минусы: Невысокая степень сжатия. Ограничения на формат.
H.263
Данный стандарт является расширением, дополнением и значительным усложнением H.261. Он содержит "базовый" стандарт кодирования, практически не отличающийся по алгоритмам сжатия от H.261, плюс множество опциональных его расширений. Кратко перечислим наиболее важные отличия:
Использование арифметического кодирования вместо кодов Хаффмана. Дает возможность на 5-10% повысить степень сжатия.
Возможность задания векторов смещения, указывающих за границы изображения. При этом граничные пиксели используются для предсказания пикселей вне изображения. Данный прием усложняет алгоритм декодирования, но позволяет значительно улучшить изображение при резкой смене плана сцены.
Возможность задания вектора смещения для каждого блока 8x8 в макроблоке, что в ряде случаев существенно увеличивает сжатие и снижает блочность изображения.
Появление B-кадров, которое позволяет увеличить степень сжатия, за счет усложнения и увеличения времени работы декодера.
Поддержка большого числа форматов входных видеоданных: sub-QCIF, QCIF, CIF, 4CIF, 16CIF и отдельно настраиваемые. Основное отличие от более универсальных форматов заключается в адаптации для нескольких фиксированных разрешений, что позволяет делать менее универсальные, но более быстрые процедуры обработки кадров. Построенный таким образом декодер работает несколько быстрее.
Компенсация движения с субпиксельной точностью. Возможность сдвинуть блок на полпиксела также увеличивает степень сжатия, но увеличивает время работы декодера.
Особый режим сжатия INTRA макроблоков со ссылкой на соседние макроблоки в обрабатываемом кадре, особый режим квантования и специальная таблица Хаффмана для улучшения сжатия I-кадров в ряде случаев.
Сглаживание границ блоков декодированного изображения для уменьшения эффекта "блочности". Зачастую при резком движении в кадре при сжатии алгоритм оказывается вынужден повысить степень квантования блоков после ДКП чтобы уложиться в отведенный на передачу битовый поток. При этом в кадре возникают хорошо вам знакомые по JPEG блоки размером 8х8. Как показала практика, "сращивание" границ, когда крайние пикселы блоков сдвигают по яркости так, чтобы уменьшить разницу, позволяет зачастую заметно повысить визуальное качество фильма.
Изменение разрешения и деформирование базового кадра, использующегося в качестве базового при сжатии.
Различные режимы квантования и кодирования по Хаффману.
Характеристики H.263Поток, разрешение: 0.04-20 Мбит/c, sub-QCIF, QCIF, CIF, 4CIF, 16CIF и отдельно настраиваемые разрешения.
Плюсы: Алгоритм H.263 также как H.261 допускает быструю аппаратную реализацию, однако при этом позволяет добиться большей степени сжатия при том же качестве. Поддерживает сжатие звука.
Минусы: По количеству заложенных идей находится между MPEG-2 и MPEG-4.
MPEG-2
Как уже говорилось, MPEG-2 занимается сжатием оцифрованного видео при потоке данных от 3 до 10 Мбит/сек. Многое в нем заимствовано из формата CCIR-601. CCIR-601 представляет собой стандарт цифрового видео с размером передаваемого изображения 720х486 при 60 полукадрах в секунду. Строки изображения передаются с чередованием, и два полукадра составляют кадр. Этот прием нередко применяют для уменьшения мерцания. Хроматические каналы ( U и V в YUV ) передаются размером 360х243 60 раз в секунду и также чередуются уже между собой. Подобное деление называется 4:2:2. Перевод из CCIR-601 в MPEG-I прост: надо поделить в 2 раза яркостную компоненту по горизонтали, поделить поток в 2 раза во временном измерении (убрав чередование), добавить вторую хроматическую компоненту и выкинуть "лишние" строки, чтобы размер по вертикали делился на 16. Мы получим поток YUV кадров размером 352х240 с
частотой 30 кадров в секунду. Здесь все просто.
Проблемы начинаются, когда появляется возможность увеличить поток данных и довести качество изображения до CCIR-601. Это не такая простая задача, как кажется. Проблема состоит в чередовании полукадров во входном формате. Тривиальное решение - работать с кадрами 720х486 при 30 кадрах в секунду, как с обычным видео. Этот путь приводит к неприятным эффектам при быстром движении объектов на экране. Между двумя исходными полукадрами 720х243 сдвиг становится заметным, а т.к. наш кадр формируется из исходных полукадров через строку, то при сжатии происходит размывание движущегося объекта. Виновно в этом эффекте ДКП, и как-то исправить ситуацию, не уменьшив степени сжатия видео, или не потеряв в визуальном качестве нельзя. Достаточно распространенным является применение "деинтерлейсинга" (от английского deinterlacing - удаление чередования строк). Эта операция позволяет удалить чередование, смещая четные строки в одном направлении, а нечетные в другом, пропорционально
относительному движению объекта в данной области экрана. В результате мы получаем визуально более качественное изображение, но несколько более длительную предобработку перед сжатием.
Другим решением является архивация четных и нечетных кадров в потоке CCIR-601 независимо. При этом мы, конечно, избавимся от артефактов, возникающих при быстром движении объектов, но существенно уменьшим степень сжатия, т.к. не будем использовать важнейшей вещи - избыточности между соседними кадрами, которая очень велика.
Характеристики MPEG-2Поток, разрешение: 3-15 Мбит/c, универсальный
Плюсы: Поддержка достаточно серьезных звуковых стандартов Dolby Digital 5.1, DTS, высокая универсальность, сравнительная простота аппаратной реализации.
Минусы: Недостаточная на сегодня степень сжатия, недостаточная гибкость.
MPEG-4
MPEG-4 кардинально отличается от принимаемых ранее стандартов. Рассмотрим наиболее интересные и полезные нововведения.
Расчет трехмерных сцен и работа с синтетическими объектами. В состав декодера MPEG-4 как составная часть входит блок визуализации трехмерных объектов ( Animation Framework eXtension - AFX - то, что в просторечии называют данными для трехмерного движка). Те, кто кодировал видео, знают, сколько проблем доставляют титры и вообще любые накладываемые поверх фильма объекты (логотипы, заставки и т.п.). Если хорошо выглядит основной план - будут подпорчены накладываемые объекты, если хорошо смотрятся они - будет низкой общая степень сжатия. В MPEG-4 предлагается решить проблему кардинально. Накладываемые объекты рассчитываются отдельно и накладываются потом. Кроме того, можно использовать видеопоток даже как текстуру, накладываемую на поверхности рассчитываемых объектов. Такая гибкая работа с трехмерными объектами позволяет существенно поднять степень сжатия при заметно лучшем качестве изображения. Более того - никто не мешает делать видеоролики вообще без живого
видео, а состоящие только из рассчитанных (синтетических) объектов. Размер их описания будет в разы меньше, чем размер аналогичных фильмов, сжатых просто как поток кадров. Кстати, отдельно в стандарте предусмотрена работа со "спрайтами" - статическими изображениями, накладываемыми на кадр. При этом размер спрайта может быть как совсем маленький (логотип канала в уголке экрана), так и превышать размер кадра и "прокручиваться" (т.е. в качестве "спрайта" может быть задан фон, а небольшие видео-объекты, например, голову диктора, будут на него накладывать). Это дает значительную гибкость при создании MPEG-4 фильмов и позволяет заметно уменьшить объем кодируемой информации.
Объектно-ориентированная работа с потоком данных. Теперь работа с потоком данных становится объектно-ориентированной. При этом данные могут быть живым видео, звуковыми данными, синтетическими объектами и т.д. Из них создаются сцены, этими сценами можно управлять. Для простых смертных при этом мало что изменится, однако для программистов объектная среда означает кардинальное упрощение работы с возникающими сложными структурами.
Помещение в поток двоичного кода "С++ подобного" языка BIFS. С помощью BIFS в поток добавляются описания объектов, классов объектов и сцен. Также на нем можно менять координаты, размеры, свойства, поведение и реакцию объектов на действия пользователя. В свое время Flash был назван революцией 2D графики в Интернете. Аналогичный прорыв в области видео совершает MPEG-4.
Активная зрительская позиция. Как было замечено выше, BIFS позволяет задавать реакцию объектов сцены на действия пользователя. Потенциально возможно удаление, добавление или перемещение объектов, ввод команд с клавиатуры. Событийная модель заимствована из развивавшегося уже долгое время языка моделирования виртуальной реальности VRML. Для тех, кто играл в написанные на VRML игры, очевидно, что в MPEG-4 будет совершенно реально создавать "квест"-подобные (и не только) игры. Широчайший простор открывается для создания обучающих и развлекательных программ. Представляете, скачиваете из Интернета один файл, который сразу в себе содержит все, что необходимо для небольшого курса лекций, причем вы можете прослушать его, видя говорящую голову преподавателя, или отключив его, можете увеличить фрагменты ("спрайты") с материалами. А в конце - пройти короткий тест на понимание предмета. Кстати - в стандарте предусмотрено обработка
команд на стороне сервера, т.е. программа-просмотрщик может отослать данные на сервер и получить оттуда оценку. Отличие от предыдущих стандартов революционное.
Синтезатор лиц и фигур. В стандарт заложен интерфейс к модулю синтеза лиц и фигур. Например, в файле сохраняются ключевые данные о профиле лица и текстуры лица, а при записи фильма сохраняются только коэффициенты изменения формы. Для передач типа новостей, этот прием позволяет в десятки раз сократить размер файла при замечательном качестве.
Синтезатор звуков и речи. Помимо синтеза лиц в стандарт MPEG-4 также заложены алгоритмы синтеза звуков, и даже речи(!).
Улучшенные алгоритмы сжатия видео. В стандарте предусмотрены блоки, отвечающие за потоки 4.8-65Кбит/с с прогрессивной разверткой и большие потоки с поддержкой чересстрочной развертки. Для передачи по ненадежным каналам возможно использование помехоустойчивых методов кодирования (за счет незначительного увеличения объема передаваемых данных резко снижается вероятность искажения изображения). При передаче видео с одновременным просмотром заложена возможность огрубить изображение, если декодер из-за ограничений канала связи не успевает получить всю информацию. Всего в стандарт заложено 3 уровня детализации. Эта возможность позволит легко адаптировать алгоритм для трансляций видео по сети.
Поддержка профилей на уровне стандарта. Понятно, что реализация всех возможностей стандарта превращает декодер в весьма сложную и большую конструкцию. При этом далеко не для всех приложений необходимы какие-то сложные специфические функции (например, синтез речи). Создатели стандарта поступили просто: они оговорили наборы профилей, каждый из которых включает в себя набор обязательных функций. Если в фильме записано, что ему для проигрывания необходим такой-то профиль и декодер этот профиль поддерживает, то стандарт гарантирует, что фильм будет проигран правильно.
Выше кратко перечислены некоторые отличия MPEG-4 от предыдущих стандартов. Надо отметить, что на момент создания стандарта острой потребности в описанных выше вещах еще не было. Иначе говоря, мы имеем дело с хорошо продуманной работой по формированию стандарта, которая была закончена к тому времени, как в нем возникла первая необходимость.
Создателями MPEG-4 учтен опыт предшественников (в частности VRML ), когда слишком раннее появление стандарта и отсутствие в нем механизма профилей серьезно подорвало его массовое применение. Будем надеяться, что массовому применению MPEG-4 такие проблемы не грозят.
Характеристики MPEG-4Поток, разрешение: 0,0048-20 Мбит/c, поддерживаются все основные стандарты видеопотоков.
Плюсы: Поддержка достаточно прогрессивных звуковых стандартов, высокая степень универсальности, поддержка новых технологий (различные виды синтеза звука и изображения).
Минусы: Высокая сложность реализации.
Сравнение стандартов
Систематизируем стандарты (табл. 8.1) и их характеристики (табл. 8.2)
| Название |
Год |
Разрешение и поток |
Аудио |
Применение |
|---|
| MPEG-1 |
1992 |
352х240х30,
352х288х25,
1.5 Мбит/с |
MPEG-1 Layer II |
VideoCD первого
поколения |
| H.261 |
1993 |
352х288х30,
176х144х30,
0,04-2 Мбит/c (px64 Кбит/с, где p от 1 до 30) |
— |
Аппаратно реализованные кодеки, видеоконференции |
| MPEG-2 |
1995 |
Универсальный,
3-15 Мбит/c |
MPEG-1 Layer II,
Dolby Digital 5.1, DTS |
DVD |
| H.263 |
1998 |
sub-QCIF, QCIF, CIF, 4CIF, 16CIF и настраиваемые особо |
Поддерживается |
Аппаратно реализованные кодеки, видеотелефоны, видеоконференции |
| MPEG-3
не принят |
1993-95 |
Телевидение высокой четкости,
20-40 Мбит/c |
|
HDTV |
| MPEG-4 |
1999 |
Универсальный,
0,0048-20 Мбит/c |
MPEG-1 Layer II,
MPEG-1 Layer III,
Dolby Digital 5.1, DTS |
VideoCD второго
поколения |
| Название |
За счет чего достигается сжатие |
Дополнительные возможности |
|---|
| MPEG-1 |
ICT, DCT |
|
| H.261 |
ICT, DCT, MC |
Передача потока данных по р-каналам с пропускной способностью 64Кбит (телеконференции по нескольким телефонным линиям). |
| MPEG-2 |
ICT, DCT, MC |
|
| MPEG-4 |
ICT, Wavelet, MC, спрайты, объекты с прозрачным фоном, 3d-рендеринг |
Встроенный язык описания BIFS, синтезатор речи, функции анимации лиц, 3D-рендеринг и т.д. |
Вопросы для самоконтроля
Какие параметры надо определить, прежде чем сравнивать два алгоритма сжатия видео?
Приведите примеры ситуаций, когда архитектура компьютера дает преимущества тому или иному алгоритму сжатия видео.
Какими свойствами видеопотока мы можем пользоваться, создавая алгоритм сжатия? Приведите примеры.
Что такое аудио-визуальная синхронизация? Почему выполнение ее требований значительно снижает степень сжатия?
Назовите основные требования к алгоритмам сжатия видео.
Что такое I-кадры, P-кадры?
Приведите примеры программно-аппаратной реализации алгоритмов сжатия видео (повседневные и достаточно новые).
Приведите примеры областей использования видео НЕ критичных к требованию "устойчивости к ошибкам".
