способ поиска векторов перемещений в динамических изображениях

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

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

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

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

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

Для многих технологий видеосжатия поиск векторов перемещения является ключевой технологией [1]. В классической реализации поиска векторов перемещения используется следующее: на вход процедуры поиска векторов перемещений поступают два кадра видеопоследовательности: предыдущий декодированный кадр и текущий кодируемый кадр. Каждый кадр представляет собой двумерный массив чисел, являющихся величиной яркости пикселей изображения. Кодируемый кадр разбивается на квадратные группы пикселей фиксированного размера - блоки. В современных системах видеокодирования принят размер блока, равный 8×8 или 16×16 пикселей. Для каждого блока кодируемого кадра по определенному алгоритму находится участок предыдущего декодированного кадра, который хорошо приближает обрабатываемый блок.

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

Чтобы проверить, насколько хорошо участок приближает обрабатываемый блок, вычисляется сумма абсолютных разностей величин яркости пикселей

где S - размер блока, F(x, y) - величина яркости пикселя с координатами (х, y) кодируемого кадра, F'(x, y) - величина яркости пикселя предыдущего декодированного кадра, V=(V_x, V_y) - проверяемый вектор перемещения.

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

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

Задача, решаемая данным изобретением, - качественное увеличение эффективности работы системы видеосжатия, особенно при низких битовых затратах, а также повышение ее производительности по сравнению с [2].

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

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

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

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

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

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

Общая схема способа видеокодирования приведена на фиг.1, где 1 - вход схемы сжатия, 2 - модуль сжатия изображений, 3 - мультиплексор потоков данных, 4 - модуль декодирования изображений, 5 - модуль поиска векторов перемещений, 6 - модуль вычисления разностного изображения, 7 - модуль сжатия векторов перемещений, 8 - выход схемы сжатия. На фиг.2 указана схема модуля поиска векторов перемещений, где 10 - вход модуля поиска векторов перемещений, 11 - модуль общей обработки входного кадра, 12 - модуль поиска глобального перемещения, 13 - выход модуля поиска векторов перемещений, 14 - модуль обработки блоков первого слоя, 15 - модуль обработки блоков второго слоя, 16 - модуль обработки блоков третьего слоя. На фиг.3 отражено разбиение опорного изображения на слои и распределение блоков изображения по слоям. На фиг.4 в зависимости от номера слоя показано расположение блоков, чьи векторы движения участвуют в построении прогноза вектора перемещения обрабатываемого блока. На фиг.5, 6, 7 указаны схемы поиска векторов перемещения для первого, второго и третьего слоев соответственно. На фиг.8 приведен пример весовой функции окна, применяемой при использовании блочной компенсации движения с перекрытием.

Способ поиска векторов перемещения осуществляется следующим образом. Видеокадр, для которого не нужно проводить поиск векторов перемещений (например, самый первый кадр видеопоследовательности), поступает на вход схемы сжатия 1, и далее на модуль сжатия изображений 2. Сжатое изображение поступает в мультиплексор 3 для формирования выходного потока сжатых данных, а также на декодирующий модуль 4 для получения опорного кадра. Очередной видеокадр, для которого необходимо провести поиск векторов перемещений, поступает на вход схемы сжатия 1 и оттуда на модуль поиска векторов перемещений 5, а также на модуль вычисления разностного изображения 6. На модули 5 и 6 также поступает опорный кадр, полученный от декодирующего модуля 4. Модуль поиска векторов перемещений 5 запрашивает у модуля сжатия векторов перемещений 7 статистику сжатия, необходимую ему для более точного выбора векторов перемещения. Найденные векторы перемещения поступают в модуль сжатия векторов перемещений 7 и далее в сжатом в виде в мультиплексор 3. Кроме того, найденные векторы перемещений вместе с опорным кадром поступают в модуль вычисления разностного изображения 6. Полученное разностное изображение поступает в модуль сжатия изображений 2. Сжатое разностное изображение вместе с закодированными векторами перемещений поступают в декодирующий модуль 4 для получения нового опорного кадра. Выходной поток сжатых данных выводится на выход схемы сжатия 8.

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

Для поиска векторов перемещений последовательно проводятся следующие действия. Очередной видеокадр поступает на вход модуля поиска векторов перемещений 10 и далее в модуль общей обработки 11, где разбивается на блоки фиксированного размера 8×8 пикселей, которые классифицируются по слоям в соответствии со схемой, показанной на фиг.3. Таким образом, на первом слое оказывается лишь четверть всех блоков, еще четверть оказывается на втором слое. Оставшаяся половина относится к третьему слою. Из блоков первого слоя путем прореживания в 4 раза отбирается часть блоков и отдается модулю поиска глобального перемещения 12. Результатом работы модуля поиска глобального перемещения является единственный вектор глобального перемещения, который отправляется на выход 13 модуля поиска векторов, а также на модуль обработки блоков первого слоя 14, где используется в качестве прогноза. Каждый прогнозный вектор задает положение центра шаблона поиска вектора движения обрабатываемого блока. Также для повышения производительности все найденные векторы перемещений передаются в модуль 14, чтобы сократить количество операций поиска. Далее на модуль обработки блоков первого слоя 14 поступают поочередно блоки этого слоя. Результатом работы является вектор перемещения для каждого из поступающих блоков. Полученные векторы перемещений для блоков первого слоя поступают на выход модуля 13, а также на модули обработки блоков второго слоя (15) и третьего слоя (16), где используются для построения прогноза. После этого блоки второго слоя поступают на модуль обработки блоков второго слоя 15. Результирующие векторы перемещений блоков второго слоя поступают на выход модуля 13, а также на модуль обработки блоков третьего слоя 16, где используются для построения прогноза. На заключительном этапе поиска векторов перемещений блоки третьего слоя поступают на модуль обработки блоков третьего слоя 16, результатом работы которого являются векторы перемещений, которые отправляются на выход модуля 13. Кроме того, необходимо отметить, что во все четыре модуля обработки 12, 14, 15 и 16 поступает опорный кадр, а в модули обработки 14, 15 и 16 поступает информация об эффективности сжатия отдельных векторов перемещений.

Одним из возможных вариантов работы системы сжатия является отключение более поздних блоков обработки и использование не вычисленных, а прогнозных векторов перемещения. Например, могут быть отключены блоки 15 и 16. Это ухудшает качество восстановленного кадра, однако позволяет передавать меньшее количество векторов в выходной поток, что приводит к улучшению характеристик кодека при крайне низких битовых затратах.

При поиске векторов перемещений степень отклонения компенсированного блока от искомого находится как S(V_x , V_y)=D(V_x, V_y)+ *R(V_x, V_y), где D(V_x, V_y) - сумма абсолютных разностей (1) (т.е. ошибка, вносимая при перемещении блока), R(V_x, V_y ) - количество бит, затрачиваемых на кодирование вектора перемещения (V_x, V_y), - варьируемый параметр.

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

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

На фиг.5 показан шаблон поиска векторов перемещений для блоков первого слоя. Для наиболее удаленных от центра шаблона векторов перемещения (зона 3) проверяется только каждый четвертый вариант вектора перемещения. Для наилучшего в терминах RD-критерия из найденных векторов дополнительно проверяются пропущенные окружающие 8 вариантов. Для векторов перемещений, находящихся в зоне 2, проверяется уже каждый второй вариант, и для наилучшего вектора производится дополнительная проверка оставшихся пропущенных четырех окружающих. Для наименьших векторов перемещения (зона 1) проверяется каждый из вариантов.

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

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

На фиг.6 показан шаблон поиска векторов для блоков второго слоя. Поиск проводится так же, как и для первого слоя, однако общий размер шаблона поиска меньше. На фиг.7 показан шаблон поиска векторов для блоков третьего слоя. В этой схеме поиска используется перебор 21 вектора наименьшей длины.

Разностное изображение имеет блочную структуру, поскольку является результатом применения алгоритма компенсации движения. На границах блоков перепады яркости соседних пикселей могут достигать существенных значений, что при использовании для последующего кодирования частотных преобразований приводит к высокочастотному «всплеску» коэффициентов преобразования и, как следствие, неэффективному сжатию изображения. Для устранения данного недостатка в предлагаемом изобретении при вычислении разностного кадра используется блочная компенсация движения с перекрытием. Ее применение позволяет сгладить резкие перепады яркости и повысить качество сжатия. Суть метода состоит в том, что после нахождения вектора движения блока 8×8 пикселей с помощью стандартной компенсации движения перемещению подвергается блок 16×16 пикселей с центром в обрабатываемом блоке. Перемещаемые пиксели интерполируются с пикселями других перемещенных блоков путем использования весовой функции окна. В качестве весовой функции окна может быть выбрана, например, функция , график которой показан на фиг.8.

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

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

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

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

1. Ричардсон Я. Видеокодирование. Н.264 и MPEG-4 - стандарты нового поколения // Издательство «Техносфера», 2005 г., 368 с.

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