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

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

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

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

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

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

Используемые далее термины.

Термину Макроблок (macroblock) телевизионного изображения для стандарта MPEG-2 можно найти определение, например, в Словаре терминов «Телевидение и радиовещание», авторы В.А.Хлебородов, П.П.Олиференко / под редакцией проф. М.И.Кривошеева - «Эра», г.Жуковский, 1999, с.21, 76.

Размеры макроблоков могут быть различными (16×16, 8×8 пикселов). (См., например, Mandal M.K., Chan E., Panchanathan S. "Multiresolution Motion Estimation Techniques for Video Compression", Optical Engineering, vol.35, no 1, pp.128-136, Jan., 1996).

Термину Вектор движения (Motion Vector) дано определение, например, в статье K.R.Rao, J.J.Hwang, "Techniques and Standards for Image, Video and Audio Coding", 1996, Prentice-Hall PTR, ISBN 0-13-309907-5.

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

Наиболее простым и точным является способ поиска векторов движения макроблоков на основе алгоритма полного перебора (K.R.Rao, J.J.Hwang, "Techniques and Standards for Image, Video and Audio Coding", 1996, Prentice-Hall PTR, ISBN 0-13-309907-5).

Для поиска вектора движения рассматривается норма разницы сигналов яркости двух макроблоков в текущем и опорном кадрах SAD со сдвигом на вектор движения:

Здесь F - значение яркости, (х, у) - пространственные координаты точки в кадре, t - временной индекс кадра, суммирование производится по всем точкам макроблока. Значение для которого норма SAD имеет наименьшее значение, принимается за искомый вектор. Векторы движения ищутся методом полного перебора в некоторой ограниченной окрестности:

-A<V _x,V_y<A.

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

Более эффективным способом анализа векторов движения с точностью до пикселя является способ (А.В.Дворкович, В.П.Дворкович, Ю.Б.Зубарев, А.Ю.Соколов, Патент РФ № 2137194 «Способ анализа векторов движения деталей в динамических изображениях»), включающий преобразование последовательности кадров изображений в цифровую форму, запоминание дискретных отсчетов яркости текущего и соседнего по времени (опорного) кадров, разбиение текущего кадра на макроблоки и поиск вектора движения каждого из макроблоков текущего кадра относительно опорного кадра посредством минимизации по рассматриваемому множеству векторов движения контрольной суммы данного макроблока, являющейся суммой норм попиксельной разности уровней в текущем и опорных кадрах, причем упомянутая контрольная сумма вычисляется с учетом вектора движения, то есть при сопоставлении в соответствие пикселов в текущем макроблоке пикселам в области поиска в опорном кадре, сдвинутым относительно положения пикселов текущего макроблока на предполагаемый вектор движения, взятый с обратным знаком.

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

Наиболее близким по технической сущности является способ (ISO/IEC 14496-10. ITU-T Recommendation H.264, Женева, 2008), в котором осуществляется поиск векторов движения с точностью до долей пиксела, причем промежуточные точки получают путем линейной интерполяции, в результате чего значения вычисленных отсчетов могут существенно отличаться от истинных значений, что, в свою очередь, ведет к снижению точности получаемых данных.

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

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

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

2) осуществление двумерного дискретного преобразования Фурье (ДПФ) над расширенным макроблоком опорного кадра;

3) изменение получившейся матрицы коэффициентов Фурье добавлением в нее нулевых коэффициентов, соответствующих значениям пространственных частот, превышающих граничные частоты исходного макроблока, в таком количестве, при котором измененная матрица оказывается в N раз больше первоначальной по соответственным пространственным размерам, и по строкам, и по столбцам;

4) осуществление обратного двумерного БПФ над измененной матрицей, в результате которого получается передискретизированный опорный макроблок с числом дискретных отсчетов в N раз больше по строкам и по столбцам, содержащий истинные значения уровней изображения в промежуточных точках отсчетов, получившихся между исходными пикселами при увеличении пространственного разрешения в N раз по горизонтали и вертикали;

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

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

На фиг.1 изображена блок-схема устройства для реализации заявляемого способа поиска векторов движения деталей в динамических изображениях.

На фиг.2 приведены примеры текущего (а) и опорного кадров (б) из видеопоследовательности "Сад цветов".

На фиг.3 в качестве примера приведены:

- фиг.3а - матрица расширенного макроблока размером 4×4 пиксела из опорного кадра, изображенного на фиг.2б;

- фиг.3б - матрица текущего макроблока размером 2×2 пиксела из текущего кадра, изображенного на фиг.2а;

- фиг.3в - изображение огибающей поверхности расширенного опорного макроблока.

На фиг.4 приведены:

- фиг.4а - матрица коэффициентов БПФ опорного расширенного макроблока;

- фиг.4б - измененная матрица коэффициентов БПФ опорного макроблока, расширенная в 4 раза по строкам и в 4 раза по столбцам;

- фиг.4в - матрица передискретизированного макроблока;

- фиг.4г - изображение огибающей поверхности передискретизированного опорного макроблока.

На фиг.5 приведена структурная схема расширения двумерной матрицы коэффициентов Фурье, осуществляемого при передискретизации опорного макроблока.

На фиг.6 приведен пример разностных кадров при компенсации движения с использованием целочисленного вектора движения (а) и вектора движения, вычисленного с точностью до ¹/₄ пиксела (б).

Устройство, изображенное на фиг.1, содержит подключенные к входу сигнала динамического изображения 1 последовательно соединенные аналого-цифровой преобразователь 2, блок памяти сигнала яркости текущего кадра 3 и блок памяти опорного кадра 4, подключенный к выходу блока памяти сигнала яркости текущего кадра блок памяти текущего макроблока 5, и подключенный к выходу блока памяти опорного кадра 4 блок памяти области поиска движения 6. Выходы блоков 5 и 6 подключены к входам блока анализа движения с точностью до пиксела 7, выход которого, а также второй выход блока памяти 6 области поиска движения соединен с блоком памяти расширенного опорного макроблока 8, к выходу которого подсоединены последовательно соединенные блок Дискретного Преобразования Фурье 9, блок расширения спектра Фурье (добавления нулевых коэффициентов) 10, блок Обратного Дискретного Преобразования Фурье 11 и блок уточненного анализа движения 12, ко второму входу которого подсоединен второй выход блока памяти 5 текущего макроблока, а к третьему входу - выход целочисленных векторов движения блока 7. Информация об уточненных векторах движения подается на выход устройства 13. Функционирование устройства регулируется блоком управления 14.

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

Сигнал динамического изображения со входа устройства 1 (фиг.1) через аналого-цифровой преобразователь (АЦП) 2 поступает на блок сигнала яркости текущего кадра 3 и через него на блок памяти опорного (например, предыдущего) кадра 4. Положим, что в блоках 3 и 4 помещены кадры изображений, приведенные на фиг.2а и фиг.2б соответственно. Через блок памяти текущего макроблока 5 и памяти области поиска движения 6 дискретные отсчеты соответствующих пикселов поступают на блок анализа движения с точностью до пиксела 7, в котором с использованием стандартного способа осуществляется нахождение вектора движения с точностью до целого числа пикселов.

Далее происходит этап уточнения найденного вектора движения.

В блоке памяти расширенного опорного макроблока 8 осуществляется увеличение на один пиксел со всех четырех сторон макроблока опорного кадра для получения области поиска уточненного вектора движения путем считывания нужных данных из блока 6.

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

SAD=(|133-132|+|133-117|+|42-24|+|116-171|)=1+16+18+55=90

На фиг.3в приведено изображение огибающей поверхности данного расширенного опорного макроблока.

Преобразование пространственного разрешения матрицы отсчетов поясняется сначала на примере обработки одномерной последовательности действительных отсчетов {х₀, x₁, х_К-1}, K - четное число:

дискретное преобразование Фурье данной последовательности определяется соотношением:

u=0, K-1,

где

Последовательности действительных и мнимых коэффициентов Фурье (при четном К) соответственно равны:

ReF_u={Re F₀, Re F₁, Re F_K/2-1, Re F_k/2, Re F_K/2+1 , Re F_K-1};

ImF_u={0, Im F₁, Im F_K/2-1, 0, Im F_K/2+1, Im F_K-1}.

При этом согласно свойствам БПФ:

Re F_K-k=Re F_k , а Im F_K-k=-Im F_k, k=1, K/2-1,

так что имеем:

ReF _u={Re F₀, Re F₁, Re F_K/2-1, Re F_K/2, Re F_K/2-1 , Re F₁};

lmF_u={0, Im F₁, Im F_K/2-1, 0, -Im F_K/2-1, -Im F₁}.

Разделив центральный коэффициент F_K/2, соответствующий граничной частоте, на два и добавив между ними нули в количестве K(N-1)-1, получаем:

To есть сформированный спектр содержит в N раз больше отсчетов, чем исходный.

Передискретизированную последовательность {у₀, у₁, у_NK-1} можно получить, применив обратное преобразование Фурье:

k=0, NK-1

где ,

причем у_Nk=x_k, а число отсчетов на заданном интервале увеличилось в N раз.

В случае двумерных данных ДПФ приводит к следующим соотношениям:

где

причем везде u=0 K-1, v=0 K-1.

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

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

В блоке ДПФ (блок 9 фиг.1) производится операция Фурье-преобразования расширенного макроблока, полученного с выхода блока 8.

Алгоритм этих преобразований поясняется на фиг.4 и в общем виде также на фиг.5.

Матрица коэффициентов спектра Фурье расширенного макроблока приведена на фиг.4а. Расширение матрицы из фиг.4а нулевыми коэффициентами спектра Фурье (осуществляемое блоком расширения спектра Фурье 10 фиг.1) приведено на фиг.4б. После обратного ДПФ матрицы фиг.4б (данная операция осуществляется в блоке обратного дискретного преобразования Фурье 11 схемы фиг.1) воспроизводится множество отсчетов передискретизированного расширенного опорного макроблока, как показано на фиг.4в, а его огибающая поверхность изображена на фиг.4г. В общем виде пространственная структура расширения макроблока иллюстрирована на фиг.5а, его ДПФ - на фиг.5(б, в), а результата передискретизации - на фиг.5г. Заметим, что размеры физического соответствия исходного расширенного (фиг.5а) и передискретизированного (фиг.5г) макроблоков остаются неизменными.

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

F1_ij =F0_ij при i<n/2, j<n/2;

F1 _{i+n·(N-1)j+n·(N-1)}=F0_ij при i>n/2, j>n/2;

F1_i+n·(N-1)j=F0 _ij при i>n/2, j<n/2;

F1_ij+n·(N-1) =F0_ij при i<n/2, j>n/2;

F1 _n/2j=F1_{n/2+n·(N-1)j}=0.5·F0_n/2j при j<n/2;

F1_{n/2j+n·(N-1)}=F1 _{n/2+n·(N-1)j+n·(N-1)}=0.5·F0_n/2j при j<n/2;

F1_in/2=F1_{in/2+n·(N-1)} =0.5·F0_{i n/2} при i<n/2;

F1 _{i+n·(N-1)n/2}=F1_{i+n·(N-1)n/2+n·(N-1)} =0.5·F0_in/2 при i<n/2;

F1 _{n/2 n/2}=F1_{n/2 n/2+n·(N-1)}=F1_{n/2+n·(N-1) n/2}=F1_{n/2+n·(N-1) n/2+n·(N-1)}=0.25·F0 _{n/2 n/2};

F1_ij=0 при n/2<i<n/2+n·(N-1) или n/2<j<n/2+n·(N-1),

где F0_ij и F1_ij - коэффициенты Фурье двумерного ДПФ над расширенным макроблоком опорного кадра до и после передискретизации соответственно, n - размер расширенного макроблока (и матрицы его коэффициентов ДПФ) опорного кадра по горизонтали и по вертикали, n·N - размер расширенного макроблока (и матрицы его коэффициентов ДПФ) опорного кадра по горизонтали и вертикали после передискретизации.

Таким образом, при осуществлении обратного двумерного ДПФ над сформированной матрицей создается передискретизированный опорный макроблок.

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

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

При этом контрольная сумма попиксельной разности равна:

SAD=(|133-132|+|133-133|+|42-42|+|116-106|)=1+0+0+10=11.

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

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

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

На Фиг.1 представлена блок-схема устройства для реализации заявляемого способа.

На Фиг.2 представлен пример текущего (а) и опорного (б) кадров из видеопоследовательности «Сад цветов».

На Фиг.3 представлен пример текущего и расширенного опорного макроблока.

На Фиг.4 представлен пример преобразования матрицы коэффициентов БПФ расширенного опорного макроблока.

На Фиг.5 представлен пример схемы расширения двумерной матрицы коэффициентов Фурье, осуществляемого для передискретизации опорного макроблока.

На Фиг.6 представлены разностные кадры при компенсации движения с использованием целочисленного вектора движения (а) и вектора движения, вычисленного с точностью до ¹/ ₄ пиксела (б).

Перечень позиций

(Фиг.1 - Блок-схема устройства для реализации заявляемого способа)

1. Сигнал динамического изображения

2. Аналого-цифровой преобразователь (АЦП)

3. Блок памяти сигнала яркости текущего кадра

4. Блок памяти опорного кадра

5. Блок памяти текущего макроблока

6. Блок памяти области поиска движения

7. Блок анализа движения с точностью до пиксела

8. Блок памяти расширенного опорного макроблока

9. Блок дискретного преобразования Фурье

10. Блок расширения спектра Фурье

11. Блок обратного дикретного преобразования Фурье

12. Блок уточненного анализа движения

13. Векторы движения с точностью до долей пиксела