способ блочной межкадровой компенсации движения для видеокодеков

Формула изобретения

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

Описание изобретения к патенту

Изобретение относится к области видеокодирования, в частности к оценке и компенсации движения в динамических изображениях.

Известен способ компенсации движения, в котором кадр разбивается на слои - группы блоков, объединенные по взаимному расположению [1]. Процедура компенсации движения заключается в поиске векторов перемещений. Каждый следующий слой использует векторы перемещений, найденные на предыдущем слое. Таким образом, последний слой использует наибольшее число векторов соседних блоков. Авторы ограничиваются тремя слоями. В качестве прогноза для первого слоя служит вектор глобального перемещения кадра. Для второго слоя прогнозом являются найденные векторы первого и, по возможности, второго слоев. Третий слой предсказывается по векторам со всех слоев. Каждый слой использует заранее определенный шаблон поиска.

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

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

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

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

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

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

На фиг.1 представлена предлагаемая пиксельная реализация шестиугольной формы блока.

На фиг.2 представлено разбиение изображения на шестиугольные формы блоков; горизонтальной ломаной линией показано формирование строк, формирование столбцов показано вертикальной линией.

На фиг.3 представлено распределение шестиугольных блоков по трем слоям; цифрами обозначен номер слоя.

На фиг.4 представлена маска для шестиугольной формы блоков.

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

- блок вмещается в прямоугольную область размером 8×10 пикселей;

- площадь блока составляет 64 пикселя и совпадает с площадью квадратного блока 8×8 пикселей - стандартного для многих алгоритмов компрессии изображения. Блоки индексируются по позициям в строке и столбце. По вертикали блоки располагаются строго друг под другом. По горизонтали - каждый нечетный блок располагается выше своего соседа на половину своего размера, а каждый четный, наоборот, располагается ниже своего соседа на ту же величину. Блоки, располагающиеся по вертикали и горизонтали, формируют столбцы и строки соответственно (фиг.2). Зная индекс блока по строке и столбцу, можно найти всех его соседей.

У каждого блока есть шесть соседей:

- два соседа слева и справа, индексы столбца которых на единицу меньше и на единицу больше индекса столбца текущего блока. Индекс строки этих соседей совпадает с индексом рассматриваемого блока;

- два соседа слева и справа с аналогичной индексацией, но располагающиеся на строку выше или ниже;

- два блока сверху и снизу. Их индексы столбца совпадают с индексом блока, а индекс строки на единицу больше и на единицу меньше индекса блока.

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

mod(i,3)+1,

где mod(i, 3) - операция получения остатка от деления числа i на 3.

Второй столбец имеет нумерацию блоков на единицу больше:

mod(i+1,3)+1.

Нумерация третьего столбца совпадает с нумерацией первого, четвертого столбца - со вторым и т.д. Пусть блок В имеет координаты (i,j) строки и столбца. Тогда номер слоя, к которому он относится, рассчитывается по формуле:

mod(i+mod(j,2)+С,3)+1,

где С - константа, от которой зависит начальное расположение слоев. Например, при С=1 получим, что блоки первой строки будут принадлежать только второму или третьему слою (нумерацию строк и столбцов следует начинать с нуля).

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

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

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

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

- ее коэффициенты не должны превышать единицы;

- при наложении соседних масок их сумма должна быть равна единице;

- ее коэффициенты не убывают при движении к ее центру;

- ее коэффициенты выбираются таким образом, чтобы обеспечивать максимальное качество восстановленного кадра.

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

Пусть матрица А - предполагаемая матрица, зависящая только от двух коэффициентов а и b:

Единицы соответствуют блоку, неотрицательные веса а и b меньше единицы, причем а< b. Очевидно, что произведение аb будет одновременно меньше и а, и b. Такая маска не является нормированной: она не удовлетворяет второму свойству.

Если сложить все соседние маски в том порядке, в каком они расположены на изображении, то получим матрицу суммы:

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

Поэлементно разделим исходную матрицу А на матрицу S:

Матрица А^* обладает всеми свойствами исходной матрицы А и, кроме того, является нормированной (второе свойство), в чем нетрудно убедиться, посчитав матрицу суммы.

Естественно, что маска удовлетворяет всем свойствам не при всех значениях а и b. В проведенных экспериментах использовалась маска, представленная на фиг.4 ( а=0.365, b=0.73).

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

Раскрытое изобретение может обеспечить высокую эффективность сжатия при низком уровне вычислительных затрат. При сравнении со стандартными способами, использующими традиционную квадратную форму блока, настоящее изобретение достигает приблизительно на 2% лучшую эффективность сжатия при одинаковом значении пикового отношения сигнала к шуму. Кроме того, сложность вычислений настоящего способа оказывается аналогичной сложности вычислений оценки движения на основе квадратных блоков. Изобретение может быть использовано в портативных устройствах, где ширина полосы типично ограничена 200-300 кбит/с, а размер видеокадра составляет QCIF или CIF.

Источники информации

1. Александров А.А., Коплович Е.А., Умняшкин С.В. Алгоритм видеокомпрессии на основе дискретного вейвлет-преобразования с трехслойной схемой кодирования векторов движения // Известия вузов. Электроника. - № 5. - 2008. - С.69-73.

2. Патент РФ № 2323541 - прототип.

3. Said, Amir; Pearlman, William A. (June 1996). "A new fast and efficient image codec based on set partitioning in hierarchical trees". IEEE Transactions on Circuits and Systems for Video Technology 6: 243-250. doi:10.1109/76.499834. ISSN 1051-8215.

4. Ричардсон Я. Видеокодирование. Н.264 и MPEG-4 - стандарты нового поколения. М.: Техносфера, 2005.