Программные продукты и системы

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

Эволюция алгоритмов преобразования частоты кадров прошла несколько этапов. Первыми методами были повторение кадров и временное усреднение, имеющие массу недостатков [1, 2]. Прорывом стало появление методов, основанных на интерполяции скомпенсированных кадров [3]. С середины 90-х гг. прошлого века исследования проводились по трем основным направлениям: постобработка векторов движения, маскирование артефактов и обработка наложений. В последнее время стали появляться алгоритмы, объединяющие полученные по ним результаты [4].

Описанный в статье алгоритм основан на результатах исследований, достигнутых авторами по указанным направлениям. Найден оригинальный подход к постобработке векторного поля и маскированию артефактов. Результаты по обработке наложений можно найти в [5].

Общая схема алгоритма

Кадры исходной видеопоследовательности обрабатываются итеративно. На каждой итерации считывается очередной кадр и вычисляются все интерполированные кадры (ИК) между текущей парой опорных кадров. Под текущей парой понимаются кадры t и t-1 (рис. 1).

Оценка движения (ОД) выполняется в двух направлениях таким образом, что на каждой итерации алгоритма доступны 4 векторных поля (ВП):  и , где – ВП из кадра t1 в кадр t2. Алгоритм ОД подробно описан в [6] и имеет следующие основные особенности:

·     для каждого блока кадра вычисляется один вектор;

·     ВП имеет иерархическую структуру (квадродерево), размер блоков меняется от 4´4 до 32´32 пикселя. Блоки меньшего размера используются на краях движущихся объектов и в областях со сложным движением для повышения точности ВП.

Вычисление ИК выполняется с использованием компенсации движения с перекрытием блоков [7]. При этом значение яркости  в каждой точке p кадра вычисляется методом усреднения скомпенсированных кадров [3]:  , , где t – коэффициент, определяющий положение ИК во времени; vp – вектор движения, вычисленный в точке p ИК.

Мера доверия векторам движения

Центральное место в разработанном алгоритме занимает мера доверия (МД) векторам движения.

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

Значения данной меры можно интерпретировать следующим образом: чем больше значение Mb, тем выше точность найденного вектора. Первая компонента C1 меры зависит от ошибки компенсации Eb вектора в блоке b:

, ,

,

,

,

где Rb – отношение адаптивного порога  к ошибке компенсации Eb; чем меньше ошибка компенсации, тем точнее найден вектор и тем больше Rb; cE – корректирующий коэффициент, варьируя который, удобно выбирать требуемый уровень приемлемых ошибок компенсации; ,  – нижняя и верхняя границы изменения адаптивного порога соответственно; (Summ of Ab­solute Differences – SAD)  – соотношение, используемое для вычисления ошибок компенсации Eb между блоками размера S´S с координатами верхнего левого угла p1 и p2 из кадров t1 и t2 соответственно.

Адаптивный порог вычисляется на основе текстурности Cb блока b:

, .

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

Вторая компонента C2 меры определяется характеристикой ВП в локальной окрестности текущего блока. Для ее вычисления строится набор векторов, который включает в себя векторы из блоков минимального размера, расположенных на границе с текущим блоком. Пример схемы расположения таких блоков для формирования набора векторов для случая размеров блоков 8´8–32´32 приведен на рисунке 2. После формирования набора векторов вторая компонента меры вычисляется как , где nb – число векторов в наборе, которые близки к вектору из блока b (например, по метрике L2); Nb – общее число векторов в наборе.

На рисунке 3 приведен график зависимости C1(Rb). Отрицательные значения C1 при малых значениях Rb нужны для того, чтобы компенсировать положительные значения w2×C2, тем самым приближая результирующее значение МД к нулю. Это необходимо для того, чтобы МД для векторов с очень большой ошибкой компенсации и высоким значением C2 не принимала высоких значений. Векторы такого рода должны считаться неверно найденными, и значения меры для них должны быть небольшими.

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

 , где Tc – пороговое значение для Cb, то есть блоки со значением Cb>Tc считаются сильнотекстурированными.

Иерархическая фильтрация ВП

Иерархическая фильтрация выполняется в три этапа.

1.   Поиск плохих блоков. Блок считается плохим, если МД вектора в нем ниже порога.

2.   Улучшение векторов для плохих блоков.

a)  Построение набора векторов-кандидатов (НВК) и выбор вектора с максимальным значением МД в нем. Если максимальное значение МД Mmax выше порога, признак «плохой» обнуляется для текущего блока, обработка переходит к следующему плохому блоку.

b)  Если Mmax меньше порога и размер текущего блока больше минимального, блок разбивается на 4 подблока и для каждого из них производится поиск лучшего вектора по алгоритму этапа (а). Разбиение блоков принимается в случае, если среднее значение МД 4 векторов подблоков выше Mmax, в противном случае в качестве финального вектора текущего блока выбирается вектор с МД Mmax, и разбиение отклоняется. В случае принятия разбиения для каждого из подблоков с МД ниже порога выполняются этапы a) и b).

3.   Поиск плохих блоков. Этот этап идентичен первому и выполняется для ВП, полученного на шаге 2.

НВК (из шага 2a) для блока b с координатами (x, y) на примере фильтрации ВП  (после ОД назад) формируется из следующих векторов:

·     вектора с МД выше порога из всех подблоков блока b векторных полей ,  и ;

·     вектора с МД выше порога из всех примыкающих к b подблоков из ВП  (рис. 4).

Построение НВК для случая фильтрации ВП  (после ОД вперед) аналогично.

Вычисление ВП ИК производится в два этапа: инициализация ВП и фильтрация ВП.

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

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

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

1.   Поиск плохих блоков ИК минимального размера. Для выявления плохих блоков, по аналогии с иерархической фильтрацией, используется МД векторам.

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

Если МД найденного вектора ниже порога и данный блок лежит в области наложений, производится обработка наложения по алгоритму из [5]. Иначе в качестве результирующего выбирается лучший вектор из сформированного НВК, блок остается плохим.

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

4.   Сглаживание векторного поля ИК в областях высокой концентрации плохих блоков. Для каждого блока b ИК, в окрестности которого число плохих блоков выше порога, результирующий вектор вычисляется как среднее векторов в локальной окрестности: , где O(b) – окрестность блока b; card{O(b)} – число блоков в O(b).

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

Набор векторов-кандидатов из шага 2 для каждого блока минимального размера, лежащего внутри заданного блока максимального размера (далее – макроблока), состоит из следующих векторов:

·     вектора из 9 блоков минимального размера с МД выше порога из ВП , лежащих на предыдущем кадре в окне 3´3 с центром в блоке, расположенном в той же позиции, что и текущий блок минимального размера на ИК;

·     вектора из ВП ИК блоков минимального размера, прилегающих к текущему макроблоку (см. рис. 2).

Результаты

Для проверки эффективности разработанного метода было проведено визуальное сравнение с методом ORCMI [4], а также объективное сравнение с методами усреднения скомпенсированных кадров и динамической медианы [3]. В тестовый набор были включены следующие стандартные последовательности с разрешением 352´288: bus, football, foreman, mobile, stefan и table.

Визуальное сравнение проводилось с результатами, представленными в работе [4]. Сравнение показало, что наибольшая разница заметна в областях наложений на последовательностях foreman и table. Различия в обработке наложений объясняются тем фактом, что обработка этих областей производится блоками 4´4 в разработанном алгоритме, в то время как в алгоритме 4 обработка наложений осуществляется на пиксельном уровне. Поэтому области наложений шириной несколько пикселей могут быть правильно обработаны алгоритмом 4, в отличие от разработанного алгоритма, который адаптирован для обработки наложений шириной в несколько блоков 4´4.

Для объективного сравнения использовалась стандартная для алгоритмов данного класса методика. Исходные последовательности прореживались в два раза, а затем производилось двукратное увеличение частоты кадров. Полученные интерполированные кадры затем сравнивались с исходными с помощью метрики PSNR яркостной компоненты (Y-PSNR). Значения метрики усреднялись по всем ИК каждой тестовой последовательности. Результаты данного сравнения представлены в таблице. В последнем столбце таблицы приве- дена разница между результатом предложенного метода и методом усреднения скомпенсированных кадров.

Важно заметить, что цифры, указанные в таблице, нельзя напрямую сравнивать с результатами из работы [4]. Вероятно, авторы использовали последовательности после преобразования цветовых пространств, что привело к получению средних значений PSNR, ниже результата разработанного метода, в то время как ожидаемый результат метода ORCMI должен быть примерно на 1дБ выше результата предложенного алгоритма, поскольку в нем используется более плотное поле векторов (пиксельное) и обработка наложений производится попиксельно. Очевидно, что такое улучшение качества достигается при значительном повышении вычислительной сложности алгоритма.

Результат объективного сравнения

В заключение отметим, что авторами предложен новый алгоритм для преобразования частоты кадров видеопотока. Разработанный алгоритм продемонстрировал визуальное качество, лишь немного уступающее методу [4], являясь при этом значительно более вычислительно эффективным. Средняя скорость обработки последовательностей тестового набора на компьютере с процессором Intel Core2 Duo Penryn 2.2 ГГц для реализации разработанного метода составляет 80 кадров/сек.

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

Литература

1.   Lagendijk R.L. and Sezan M.I. Motion compensated frame rate conversion of motion pictures, in Proc. of the IEEE International Conference on Acoustics, Speech, and Signal Processing, San Francisco, CA, USA, March 1992, vol. 111, pp. 453–456.

2.   Hilman K., Park H.W. and Kim Y. Using motion compensated frame-rate conversion for the correction of 3:2 pulldown artifacts in video sequences. IEEE TCSVT, 2000, vol. 10, no. 6, pp. 869–877.

3.   Ojo O.A. and de Haan G. Robust motion-compensated video upconversion, in Proc. IEEE Transactions on. Consumer Electronics, 1997, vol. 43, no. 4, pp. 1045–1056.

4.   Zhang Y.-X., Wang W.-D., Liu P., Yao Q.-D. Frame rate up-conversion using multiresolution critical point filters with occlusion refinement, in Journal of Zhejiang University, 2008, vol. 12, pp. 1621–1630.

5.   Гришин С.В., Симонян К.А., Ватолин Д.С. Алгоритм вычисления параметров наложений для задачи преобразования частоты кадров цифровых видеосигналов // Новые информационные технологии в автоматизированных системах: матер. 12 науч.-практич. сем. М.: Московский гос. ин-т электроники и матем. 2009. С. 19–29.

6.   Симонян К., Гришин С., Ватолин Д. Адаптивный метод оценки движения в видео: сб. статей молодых ученых фак-та ВМиК МГУ. Вып. 5. М., 2008. С. 112–119.

7.   Orchard M.T. and Sullivan G.J. Overlapped block motion compensation: An estimation-theoretic approach, IEEE Trans. Image Process., 1994. vol. 3, no. 5, pp. 693–699.