Software & Systems

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

Сегодня достаточно распространены созданные не по стандартам кодеки, такие как Windows Media, Real Media, QuickTime. С другой стороны, есть ряд компаний, реализовавших стандарты кодирования видео, например, MPEG-2, MPEG-4 SP, MPEG-4 ASP, MPEG-4 AVC (H.264), H.263. Наиболее известны и распространены кодеки стандартов MPEG-2 (вещание через спутник и DVD-диски) и MPEG-4 ASP (CD-диски, благодаря DivX Inc. и XviD). При этом новый стандарт кодирования видео H.264 [1] постепенно вытесняет предшествующие стандарты из-за более высокого качества.

При разработке стандартов кодирования видео одним из основных требований является повышение степени сжатия видео или повышение качества при той же степени сжатия. Это достигается за счет усложнения алгоритмов кодирования и понижения избыточности информации. Одним из направлений является разработка кодеков с использованием многокадровой компенсации движения [2] вместо одно- или двухкадровой. Так, например, видеокодеки последнего стандарта H.264 в процессе кодирования могут выбирать в качестве опорных кадры из множества предыдущих кадров, хранящихся в буфере. Такой подход повышает степень сжатия [3] за счет более точного нахождения опорного блока, но при этом увеличивает объем необходимой памяти и замедляет процесс кодирования из-за значительного увеличения области поиска.

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

Общая схема предлагаемого подхода

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

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

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

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

Построение панорамы

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

Итак, для того чтобы определить глобальное движение кадра относительно предыдущего, требуется вычислить параметры выбранной модели глобального движения для этих двух кадров. Пусть IТ(x, y), IП(x, y) – текущий и предыдущий кадры; SТ(x, y), SП(x, y) – область без движущихся объектов в текущем и предыдущем кадрах соответственно; P – множество возможных значений параметров; A(P) – модель глобального движения. Тогда параметры модели глобального движения p определяются по следующей формуле:

.

Как правило, области SТ и SП неизвестны, и вычислять параметры модели приходится другим путем.

В предлагаемом подходе глобальное движение определяется при помощи следующего алгоритма.

Шаг 1. Повторить N раз:

а)   выбрать псевдослучайным образом минимальное, необходимое для определения параметров модели глобального движения количество векторов из поля векторов движения;

б)  вычислить параметры модели по выбранным векторам;

в)   обновить гистограмму по каждому параметру модели глобального движения.

Шаг 2. При помощи алгоритма водораздела выделить пики гистограмм, лежащие выше заданного порога.

Шаг 3. Из значений параметров, соответствующих пикам, построить набор параметров-кандидатов.

Шаг 4. Выбрать параметры, на которых достигается минимум межкадровой разницы.

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

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

.

В проводившихся исследованиях использовалась модель глобального движения, описывающая аффинное искажение: .

Эта модель имеет шесть параметров. В алгоритме на шаге 1а для определения параметров модели требуются три вектора. При этом для определения параметров необходимо решить систему линейных уравнений: , i=1..3.

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

Для того чтобы на границе вставляемого кадра не было разрывов, используется алгоритм сглаживания. Если расстояние от пикселя текущего кадра до границы (края кадра или неопределенной области, оставшейся после фильтрации объектов) меньше заданной величины D и ему соответствует пиксель на панорамном изображении, новое значение пикселя на панорамном изображении определяется следующим образом: I¢ПИ=(1-w)×I¢ПИ+ +w×IT, ,

где IПИ, I¢ПИ  – старое и новое значения пикселя на панорамном изображении соответственно; IПИ – значение соответствующего пикселя в кадре; d – расстояние от пикселя текущего кадра до границы; w – весовой коэффициент.

Неизвестные области в панораме заполняются при помощи алгоритма пространственного заполнения [4].

На рисунке 2 приведен пример построения панорамного изображения. Рамкой обведено положение текущего кадра на панораме.

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

Результаты и дальнейшее развитие идеи

Если использовать предложенный подход как замену метода многокадровой компенсации движения с использованием буфера кадров, в случае прямого хранения кадров эффективность по памяти при использовании панорамы будет достигаться уже для двух и более опорных кадров. Так, для видеопотока разрешения CIF 352´288 и размера буфера 4 кадра необходимое количество памяти для полного хранения декодированных кадров составит порядка 1.2 Мб. В то время как при использовании панорамы с внешней областью в 16 пикселей размер памяти составит 370 Кб, при этом в ней будут содержаться все части аналогичных кадров из буфера.

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

Другим преимуществом предлагаемого подхода является возможность компенсации блоков, скрытых объектами на предыдущем кадре. На рисунке 3 приводится пример такого рода компенсации движения: в случае обычного поиска в предыдущем кадре будет найден похожий, но неверный блок, то есть не являющийся опорным для исходного блока, а при использовании построенной панорамы возможно найти опорный блок. Если же использовать буфер кадров для поиска предшествующего кадра с необходимым блоком, в буфере пришлось бы хранить 10–12 кадров, что привело бы к значительному расходу памяти. В качестве примеров возникновения такой задачи можно привести стандартные последовательности bus, stefan, coastguard и другие.

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

Предложенный алгоритм построения панорамы может использоваться не только для многокадровой компенсации движения, но и во всех алгоритмах обработки видео, где важна обработка на краях кадра, например, алгоритмы подавления дрожания кадра [5].

Литература

1.   Joint Video Team of ITU-T and ISO/IEC JTC 1. Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification (ITU-T Rec. H.264 ISO/IEC 14496-10 AVC), Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, JVT-G050, March 2003.

2.   Wiegand T., Sullivan G.J., Bjontegaard G. and Luthra A. Overview of the h.264/avc video coding standard, Circuits and Systems for Video Technology, IEEE Transactions on. 2003, vol. 13, № 7, pp. 560–576.

3.   Girod B. and Flierl M. Multi-Frame Motion-Compensated Video Compression for the Digital Set-Top Box, International Conference on Image Processing, Sept. 2002.

4.   Куликов Д., Ватолин Д. Метод пространственного заполнения испорченных областей видео при ошибках в работе кодека // Новые информационные технологии в автоматизированных системах: матер. Десятого науч.-практич. сем. М., 2007. С. 38–45.

5.   Стрельников К., Ватолин Д., Солдатов С. Новый метод подавления эффекта дрожания кадра в видео // Там же. С. 3–10.