Компьютерная Графика и Мультимедиа Сетевой журнал

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

Содержание

1. Введение
2. Постановка задачи
3. Обзор существующих методов преобразования частоты кадров
   1. Frame Repetition
   2. Linear Interpolation
   3. MCI (Motion Compensated Interpolation)
   4. Motion Adaptive FRC
   5. Fast Block-Based MCI
   6. Low-cost FRC
   7. Non-linear MCI
   8. FRC using Phase Correlation ME
   9. FRC using Global Motion Estimation
   10. FRC using Optical Flow Motion Estimation
4. Литература

Введение

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

Как известно, изображение на экранах, использующих ЭЛТ, формируется за счет свечения люминофора, нанесенного на фронтальную поверхность трубки. Люминофор начинает светиться при попадании на него электронов, вылетающих из специальной пушки. За счет поворота пушки, луч электронов возможно позиционировать в любую точку экрана, вызвав ее свечение. Изображение на экране формируется по строкам, путем вращения электронной пушки в вертикальном (для перехода между строками изображения) и горизонтальном (для перехода между соседними пикселями в строке) направлениях. Стандарт телевещания 30-х годов (используемый сейчас) описывает способ <чересстрочной> прорисовки кадров - для формирования изображения, вместо засветки всех строк кадра, поочередно прорисовываются только четные или нечетные строки - поля. Это позволило при использовании ЭЛТ того времени (с низкой частотой вертикальной развертки), кроме всего прочего, достичь частоты обновления экрана равной 50Гц. Таким образом, видео сигнал транслируется полями с частотой 50Гц.

В настоящее время стали широко доступны телевизоры и мониторы, поддерживающие частоту вертикальной развертки 100Гц, причем в данном случае речь идет о прогрессивной развертке, когда кадр перерисовывается полностью, а не по полям. Существует множество алгоритмов деинтерлейсинга, позволяющих преобразовать последовательность полей в последовательность кадров. Однако на выходе таких алгоритмов, в лучшем случае, частота следования кадров равна 50Гц, в то время как требуется 100fps (frame per second). Решить данную проблему позволяют т.н. алгоритмы FRC (Frame Rate Conversion), задачей которых является изменение разрешения видео во времени. При использовании алгоритма FRC увеличивающего частоту смены кадров вдвое, возможно из 50fps получить 100fps.

Другое применение методов FRC - для преобразования между стандартами телевещания, используемыми в разных странах. Как известно, частота 50Гц в ТВ-сигнале была выбрана равной частоте электротока в сети. Поэтому, частота смены полей в ТВ-сигнале в США равна 60Гц. Таким образом, после алгоритма деинтерлейсинга в этих случаях имеем 50 и 60fps соответственно. Для корректного преобразования видео из одного формата в другой следует использовать FRC.

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

Другое применение преобразования частоты кадров - при декомпрессии видео данных. При кодировании видео на низких битрейтах многие видео кодеки уменьшают разрешение данных не только в пространстве, но и во времени. Иначе говоря, вместо кодирования исходных 30fps, частота кадров может быть уменьшена до 20fps. Это означает, что 1 из каждых 3 кадров исходной видео последовательности не будет закодирован. Однако при воспроизведении видео на стороне декодера весьма желательно иметь исходную частоту кадров. Для этого необходим механизм восстановления. Также ПЧК может быть использовано при восстановлении поврежденных кадров.

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

 

Постановка задачи

Исходными данными является видео последовательность - поток кадров, следующих с заданной частотой, например 50fps. Задача алгоритма FRC - сконструировать видеопоследовательность, имеющую иную частоту кадров, например 100fps. Изменение частоты смены кадров в данном случае достигается за счет изменения числа кадров в видео потоке.

Существуют методы FRC, предназначенные как для увеличения, так и для уменьшения частоты кадров. Методы первой группы могут иметь различные коэффициенты изменения временного разрешения, как то: 1:2, 5:6, 2:3 и т.д.

Рассмотрим постановку задачи двукратного увеличения частоты кадров (см. рис 1). Введем некоторые обозначения:

Тогда входной видео поток можно представить в виде:

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

 

Обзор существующих методов преобразования частоты кадров

Frame Repetition

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

Учитывая введенные выше обозначения, преобразованный поток в случае 2x FRC представим в виде:

Linear Interpolation

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

В случае двукратного увеличения частоты кадров выходной поток запишется в виде:

MCI (Motion Compensated Interpolation)

Существенное повышение качества достигается при использовании алгоритмов, адаптированных к движению. Адаптация, в данном, случае заключается в вычислении и обработке информации о движении. Такая оценка может осуществляться несколькими методами. Обычно используются методы, основанные на проверке соответствия блоков (BMA-методы) [1-4]. По причине использования информации о движении данные методы получили название Motion Compensated Interpolation (интерполяция скомпенсированных кадров). В таких методах FRC информация о движении используется для того, чтобы позиционировать все движущиеся объекты на новых кадрах на нужный момент времени согласно их скорости. При этом движение передается значительно более плавно по сравнению с предыдущими двумя методами. Однако при использовании MCI методов возникает проблема при появлении или исчезновении объектов на кадре, такие области называются <наложениями> (occlusions) или covered/occluded regions (покрытые непокрытые области). Схема работы MCI методов изображена на рис. 2.

Motion Adaptive FRC

В [1] описан метод увеличения частоты кадров в полтора раза. Описанный метод распределения интерполированных кадров во времени позволяет использовать все исходные кадры в преобразованной последовательности при выполнении делений только на степень двойки, что значительно облегчает аппаратную реализацию. Однако при использовании данного метода нарушается временной интервал между исходными кадрами, что проявляется в появлении артефакта, называемого jerkiness (<рывки в движении>). Вектора движения вычисляются отдельно для каждого пикселя изображения. Для оценки движения предлагается алгоритм, основанный на использовании набора кандидатов векторов движения, как первоначального приближения. Скомпенсированный кадр вычисляется с точностью полпикселя в предположении о равномерности и прямолинейности движения между опорными кадрами. Однако не описывается метода обработки <наложений>, что является основой любого алгоритма ПЧК.

Fast Block-Based MCI

В [2] описывается метод, предназначенный для восстановления пропущенных кадров на стороне декодера H.263. Интерполированные кадры вычисляются с использованием гибридной схемы, по которой адаптивно выбирается метод интерполяции: либо повторение кадров, либо интерполяция скомпенсированных кадров. Поле векторов, полученное на выходе декодера, используется для вычисления векторов для каждого пикселя. Такое преобразование осуществляется с использованием модели деформации блоков, что позволяет избежать появления <блочности> на скомпенсированном кадре. Для повышения точности процедуры компенсации движения используется схема сегментации объектов, позволяющая определить позиции двигающихся областей. Также описывается адаптивная схема выбора пропускаемых кадров, предназначенная для использования на стороне кодера.

Low-cost FRC

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

Non-linear MCI

Метод интерполяции скомпенсированных кадров, описанный в [4], предназначен для использования на стороне декодера стандарта ITU-T H.263, который описывает М-кадры (motion frames) в потоке. Данный метод также не требует предположения о равномерности и прямолинейности движения между опорными кадрами, однако информация о <нелинейных векторах> движения сохраняется видео кодером в М кадрах и используется при декодировании. На основе поля векторов движения, полученного на выходе декодера, с использованием 6-параметрической аффинной модели вычисляются вектора движения для каждого пикселя.

FRC using Phase Correlation ME

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

FRC using Global Motion Estimation

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

FRC using Optical Flow Motion Estimation

В [7] для вычисления векторов движения используется алгоритм оценки оптического потока (Optical Flow Estimation Algorithm). Для обработки наложений предлагается схема использования меток полей (Label Field). Такая схема дает хорошие результаты, однако вычисление меток полей требует наличие информации об интерполируемом кадре, что ограничивает применение данного метода использованием на стороне декодера.

Литература

1. R. Castagno, P. Haavisto, G. Ramponi, "A Method for Motion Adaptive Frame Rate Up-Conversion". IEEE Transactions on circuits and Systems for Video Technology, Vol 6, No. 5, October 1996.
2. Tien-ying Kuo, JongWon Kim and C.-C. Jay Kuo, "Motion-Compensated Frame Interpolation Scheme for H.263 Codec". Proc. ISCAS 99, May 1999. 27.
3. Emilio Antunez, "Low-cost Temporal Interpolation of Video Frames". Image Communication II, May 27, 2002.

   Shan Liu, JongWon Kim and C.-C. Jay Kuo, "Non-Linear Motion-Compensated Interpolation for Low Bit Rate Video", in SPIE Proceeding of International Symposium on Optical Science, Engineering, and Instrumentation, Applications of Digital Image Processing XXIII, San Diego, CA, July, 2000

4. G.M.X. Fernando and D.W. Parker, "Motion Compensated Display Conversion", in Proc. 2nd Int. Workshop on HDTV, I'Aquila, Italy, Feb. 1988.
5. Sanjeev Kumar, Mainak Biswas and Truong Q Nguyen, "Global Motion Estimation in Frequency and Spatial Domain", IEEE International Conference on Speech, Acoustics, and Signal Processing, March 19-23, 2004
6. Ravi Krishnamurthy, John W. Woods and Piere Moulin, "Frame Interpolation and Bidirectional Prediction of Video using Compactly-Encoded Optical Flow Fields and Label Fields", IEEE Trans. Circ. Syst. Video Tech, Vol. 9, No. 5, pp. 713-726, Aug. 1999
Дополнительная информация
Ссылка: 
Сергей Гришин, Дмитрий Ватолин. Обзор методов преобразования частоты кадров видео. Компьютерная графика и мультимедиа. Выпуск №4(2)/2006. http://cgm.computergraphics.ru/content/view/111
Выпуск: 
Выпуск №4(2)/2006