RU2182727C2

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

Info

Publication number: RU2182727C2
Application number: RU2000119205/09A
Authority: RU
Inventors: А.В. Дворкович; В.П. Дворкович; А.Ю. Соколов
Original assignee: Дворкович Александр Викторович; Дворкович Виктор Павлович; Соколов Александр Юрьевич
Priority date: 2000-07-20
Filing date: 2000-07-20
Publication date: 2002-05-20
Also published as: GB0019508D0; GB2365246A

Abstract

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

Description

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

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

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

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

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

, для которого норма SAD имеет наименьшее значение, принимается за искомый вектор. Векторы движения ищутся методом полного перебора в некоторой ограниченной окрестности: min<V_x, V_y<max. Предполагая, что размер этой окрестности равен ±N пикселов по координатам х и у, получим для числа операций, необходимых для определения вектора движения одного макроблока размером 16х16 пикселов, величину порядка 3•256 (2N+1)². На один пиксел макроблока количество операций составляет 3•(2N+1)², что уже при N=15 (значения векторов движения в пределах ±15 точек) составляет значительную величину более 10³ операций/пиксел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В дальнейшем настоящее изобретение будет более подробно раскрыто посредством более подробного описания способа анализа векторов движения деталей в динамических изображениях устройств, реализующих заявляемый способ, а также поясняющих чертежей, на которых:
Фиг. 1-а изображает блок-схему устройства для реализации способа поиска векторов движения деталей в динамических изображениях;
Фиг. 1-б изображает блок-схему еще одного устройства для реализации способа поиска векторов движения деталей в динамических изображениях, предусматривающего пространственную передискретизацию исходного изображения и предварительный поиск векторов движения по отношению к передискретизованному изображению;
Фиг. 2 приведены текущий (а) и опорный кадры (б) видеопоследовательности "Сад цветов";
Фиг. 3 иллюстрирует увеличенное изображения одного макроблока (а) из последовательности "Сад цветов", на примере которого излагаются предлагаемые способы поиска векторов движения, и (б) участка опорного кадра, соответствующего макроблоку (а);
Фиг. 4 иллюстрирует рельеф (а) и цифровые значения (б) сигнала яркости выбранного макроблока;
Фиг. 5-11 изображают таблицы уровней пикселов выбранного макроблока, иллюстрирующие алгоритм выбора опорных точек в способе поиска векторов движения;
Фиг. 12-14 изображают векторы движения, рассчитанные согласно предлагаемому способу поиска векторов;
Фиг. 15 изображает векторы движения, расчитанные согласно эталонному способу поиска векторов движения;
Фиг. 16 изображает таблицу результатов кодирования последовательности "Сад цветов" в рамках стандарта MPEG-2, иллюстрирующую эффективность предлагаемых способов поиска векторов движения;
Фиг. 17-18 изображают таблицы значений отсчетов выбранного макроблока, иллюстрирующие алгоритм выбора опорных точек в способе поиска векторов движения;
Фиг. 19 приведены векторы движения, рассчитанные по заявляемому способу поиска векторов;
Фиг. 20-21 изображают таблицы результатов кодирования последовательности "Сад цветов" в рамках стандарта MPEG-2, иллюстрирующие эффективность способа поиска векторов движения.

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

Блок-схема устройства, изображенная на фиг.1-б, содержит подключенные ко входу 1 параллельно блок синхронизации 2 и последовательно соединенные аналого-цифровой преобразователь 3, схему выделения 4 сигнала яркости, последовательно соединенные блок передискретизации 5, блок памяти 6 текущего кадра и блок памяти 7 опорного кадра, подключенные к выходам блока памяти текущего кадра последовательно соединенные блок памяти 8 текущего макроблока, блок переупорядочивания 9 пикселов макроблока и вычислитель 10 положений и уровней характерных пикселов макроблока, первые выходы которого соединены с блоком памяти 11 уровней выбранных пикселов, а вторые входы - через сумматор 12 ко входам управления блока памяти опорного кадра 6, выходы которого через блок памяти 13 уровней пикселов сравнения подключены к первым входам блока 13 попиксельного вычитания уровней характерных пикселов текущего и опорного кадров, вторые входы которого подключены ко вторым выходам блока памяти 11, а выходы - к блоку суммирования 15 модулей, выходы которого параллельно подключены к блоку сравнения сумм 16 и блоку вычисления 17 минимальной суммы и текущих векторов движения, вторые входы блока сравнения сумм 16 подключены к выходам блока 17, а выходы - непосредственно ко входам управления блока 15 и через счетчик перемещений 18 ко второму входу сумматора 12, вторые выходы блока 17 подключены через блок памяти 19 векторов движения к блоку памяти текущего кадра 21, вторые выходы блока 19 соединены параллельно с дополнительными входами блока 17 и счетчика 18, выходы блока синхронизации 2 соединены со входами управления блоков 3 и 4, а также через блок управления 20 со входами синхронизации работы блоков 6-19 устройства, блока памяти опорного кадра 21, вход которого подключен к выходу схемы выделения сигнала яркости 4, блока памяти опорного кадра 22, один вход которого подключен к выходу блока памяти текущего кадра 21, а другой к выходу сумматора 25, блока памяти уровней пикселов сравнения 23, вход которого подключен к блоку памяти опорного кадра 22, блока памяти макроблоков 24, вход которого подключен к выходу блока памяти опорного кадра 21, сумматора 25, один вход которого подключен к выходу блока памяти макроблока 24, а другой к выходу счетчика перемещений 27, блока попиксельного вычитания 26, один вход которого подключен к выходу блока памяти уровней пикселов сравнения 23, а другой к блоку памяти уровней всех пикселов 29, счетчика перемещений 27, один вход которого подключен к блоку 31 памяти векторов движения, а другой к блоку сравнения сумм 30, блока суммирования модулей 28, один вход которого подключен к выходу блока попиксельного вычитания 26, а другой к выходу блока сравнения сумм 30, блока памяти уровней всех пикселов 29, вход которого подключен к блоку памяти макроблока 24, блока сравнения сумм 30, один вход которого подключен к блоку суммирования модулей 28, блока памяти векторов движения 31, вход которого подключен к блоку вычисления минимальной суммы и текущих векторов движения 32 и блока вычисления минимальной суммы и текущих векторов движения 32, вход которого подключен к выходу блока памяти векторов движения 31, а другой к выходу блока суммирования модулей 28.

Сущность предлагаемого способа вычисления векторов движения состоит в следующем. Изложение предлагаемого способа иллюстрируется на примере анализа вектора движения одного из макроблоков динамического изображения (фиг.2). На фиг. 3а приведена в увеличенном масштабе часть изображения текущего кадра в увеличенном масштабе с обведенным макроблоком, вектор движения которого определяется в зоне опорного кадра, изображенной на фиг.3б. Макроблок имеет размер 16х16 пикселов, зона поиска движения - 64х64 пиксела. На фиг.3б обозначено положение смещенного макроблока в опорном кадре.

В случае использования стандартного метода поиска вектора движения в указанной зоне поиска требуется использование вычислительной мощности в 3•49²= 7203 операций на каждый пиксел макроблока. Рельеф сигнала яркости макроблока изображен на фиг. 4а, а на фиг.4б приведены цифровые значения пикселов этого макроблока.

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

Существуют различные предлагаемые способы выбора опорных пикселов. В соответствии с одним из заявляемых способов выбора опорных пикселов все пикселы макроблока переупорядочивают по строкам в порядке возрастания их значений (фиг.5). После переупорядочивания производят выбор пикселов с номерами столбцов х={1, 6, 11, 16} (фиг.6). После выбора столбцов производят переупорядочивание выбранных пикселов по столбцам в порядке возрастания значений (фиг.7). После переупорядочивания по столбцам производят конечный выбор опорных пикселов с номерами строк у={1, 6, 11, 16} (фиг.8). При выборе опорных пикселов их координаты запоминают в исходном макроблоке, выбранные опорные пикселы обозначены подчеркиванием (фиг.4-8).

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

Для поиска вектора движения

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

В способе поиска векторов движения для выбора опорных пикселов необходимо выполнить порядка

обращений к одному пикселу макроблока, где М - число опорных пикселов (в данном случае М=16), для поиска вектора движения с использованием (2) необходимо выполнить порядка

операций. При окне поиска N> 10 количество операций, необходимых для поиска опорных пикселов пренебрежимо мало по сравнению с числом операций, необходимых для вычисления суммы (2) и поиска вектора движения. Поэтому в способе достигается ускорение поиска векторов приблизительно в 256/М=16 раз.

Эффективность предложенного способа поиска векторов движения характеризуется фиг.12-16. На фиг.12-13 показаны векторы движения. На фиг.15 показаны векторы движения, полученные стандартным эталонным алгоритмом с использованием всех пикселов макроблока (1). Как видно из фиг.12-15, векторы движения в большинстве совпадают. Чтобы дать количественную оценку предложенного способа, рассмотрим результаты кодирования динамической последовательности кадров (фиг.16) в рамках стандарта MPEG-2 (ISO/IEC 13818-2. Information Technology - Generic Coding of Moving Pictures and Associated Audio Information. Part 2: Video./ Ed.l JTS I/SC 29, 1994) с использованием предложенного способа. Поскольку в рамках стандарта возможно использование векторов движения с точностью до половинных значений пикселов, рассмотрим два случая кодирования - без уточнения полученных векторов по предложенным способам и с уточнением в пределах +/-0.5 пиксела с использованием интерполяции между пикселами. Для уточнения будем использовать контрольную сумму (1) со всеми 256 пикселами макроблока. Уточнение векторов до половины пиксела требует порядка 3•9=27 дополнительных операций на каждый пиксел. Как следует из анализа результата кодирования (фиг.16), предложенные способы дают существенное ускорения поиска векторов движения (в 16 раз при 16 опорных точках), при этом коэфициент сжатия ухудшается не более 1-3% в случае использования точности векторов до 0.5 пиксела и 4-10% при точности векторов в один пиксел.

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

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

Здесь F^(d) (х, у) - значение пиксела после передискретизации. В соответствии с (3) отсчеты пикселов макроблока, приведенного на фиг.3-4, после передискретизации будут иметь значения, показанные на фиг.17.

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

Для поиска вектора движения

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

В процессе минимизации (4) в окне поиска +/- (N/2) пикселов определяют К векторов V1d, V2d, V3d,...,VKd, дающих наименьшие значения SAD1d:
Min=SAD1d(V1d)≤SAD1d(V2d)≤SAD1d(V3d)... (5)
После нахождения наилучших векторов V1d, V2d, V3d,..., VKd, соответствующих передискретизованным опорному и текущему кадрам, значение векторов увеличивают в отношение разрешений исходного и передискретизованного кадров, в данном случае в 2 раза. Далее в небольшой окрестности (например, +/- 1 пиксел) от каждого из полученных значений векторов (2•V1d, 2•V2d, 2•V3d,..., 2•VKd) производят минимизацию контрольной суммы (1) и определяют наилучший вектор движения, обеспечивающий минимум (1). Данный вектор принимается за конечный вектор движения макроблока в случае использования точности векторов 1 пиксел.

При использовании точности векторов движения, равной половине пиксела, как это, например, используется в стандарте MPEG-2, последний найденный выше вектор уточняется с использованием (1) в окрестности +/- 0,5 пиксела своего значения либо сразу в малых окрестностях (например, +/- 1 пиксел) векторов 2•V1d, 2•V2d, 2•V3d,..., 2•VKd с точностью до 0,5 пиксела.

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

где Z - отношение исходного и передискретизованного разрешений (в данном случае Z=2) или

на пиксел в кадре исходного разрешения. Уточнение векторов движения в окрестности каждого из найденных векторов занимает небольшое количество операций порядка 3K(2•1+1)² на пиксел в кадре исходного разрешения, где К - число наилучших векторов, и не зависит от N. При небольших К≤3 и N>10 последним числом можно пренебречь. В этом случае ускорение по сравнению с эталонным способом полного перебора составляет

Дополнительно скорость анализа векторов движения макроблоков можно улучшить согласно изобретению за счет определенного подбора вычисления контрольной суммы SAD1 или SAD1d. Для этого вычисляют среднее значение выбранных пикселов макроблока

Затем вычисляют модули разностей
X(x,y) = |F(x,y,t)-F_ср|,
где (х, у) - координаты выбранных точек в соответствующих участках макроблока,
и контрольную сумму (2) вычисляют последовательно по координатам (х, у), для которых величины Х(х, у) располагаются в убывающей последовательности.

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

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

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

Эффективность предлагаемого способа анализа движения по способу с использованием предварительной передискретизации изображения иллюстрируется на фиг.19-20. На фиг.19 приведены векторы движения, полученные с использованием наилучшего способа выбора опорных пикселов при К=3, а на фиг.20 приведены результаты кодирования тестовых динамической последовательности кадров в рамках стандарта MPEG-2 (К=1, 2 и 3).

Из таблицы на фиг.20 следует, что предлагаемый способ при Z=2 уступает по коэффициенту сжатия наилучшему эталонному способу перебора по всем пикселам не более 1% уже при К=2 и 3 и превосходит рассмотренные выше способы, не использующие передискретизацию (фиг.19). При этом коэффициент ускорения анализа движения по сравнению с эталонным способом составляет 64 раза при Z=2.

Заметим, что в предлагаемом способе фильтрация (по уравнению 3) улучшает результат. Например, если бы передискретизация проводилась без фильтрации, а только за счет прореживания по формуле
F^(d) (x, y)=F(2x, 2y), (7)
то результат по коэффициенту сжатия был бы хуже на 1-2% (фиг.20).

Устройство для реализации предложенного способа анализа векторов движения без использования фильтрации работает следующим образом.

Предположим, на вход 1 устройства (фиг.1-а) поступает аналоговый сигнал изображения, например полный цветовой телевизионный сигнал стандартных систем SECAM, PAL или NTSС. С входа этот сигнал подается параллельно на блок синхронизации 2, выделяющий соответствующие сигналы и обеспечивающий формирование импульсов дискретизации, и на аналого-цифровой преобразователь АЦП 2, в котором дискретные отсчеты сигнала преобразуются в цифровой код, поступающий на схему выделения сигнала яркости 4, устраняющую цветовые поднесущие из полного цветового телевизионного сигнала. Выделение сигнала яркости необходимо, поскольку в соответствии со стандартами MPEG анализ движения деталей изображения осуществляется только при использовании яркостной компоненты изображения. Синхронизация работы схемы 4 осуществляется также дискретизирующими импульсами, поступающими с блока синхронизации 2.

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

Выходы блока 5 соединены со входами блока памяти макроблока 7, анализ движения которого производится. В этом блоке запоминаются значения рельефа сигнала яркости макроблока 16х16 пикселов. После вычисления вектора движения 1-го макроблока, соответствующего левому верхнему углу изображения, в память этого блока вводится рельеф сигнала яркости следующего за ним макроблока. Отсчет номера макроблока осуществляется обычно слева направо и сверху вниз.

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

Далее уровни сигналов яркости в рассчитанной пиксельной последовательности запоминаются в блоке памяти 10, а их координаты (х, у) через сумматор 11 поступают на вход управления блока памяти опорного кадра 6, обеспечивая запись в блоке 12 памяти уровней пикселов сравнения уровней пикселов с координатами
(x-V_0X-V_x,y-V_0Y-V_y),
где (V_0X, V_0Y ) - координаты начального вектора смещения, которые определяются, например, из результатов оценки движения соответствующих макроблоков в предыдущем кадре или из иных соображений или задаются равными нулю,
(V_x, V_y) - координаты текущего вектора смещения макроблока, при изменении которых производится анализ контрольной суммы разностей модулей уровней выбранных пикселов в макроблоке и пикселов в опорном кадре.

С блоков памяти 10 и 12 в указанной выше последовательности значения соответствующих уровней пикселов поступают на блок попиксельного вычитания 13 и с его выхода - на блок суммирования модулей 14. Блоки 13 и 14 совместно реализуют операцию, определяемую соотношением (2).

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

При вычислении суммы для начального вектора движения эта сумма запоминается в блоке 16 и становится опорной для последующих расчетов. По окончании расчета суммы при нулевом векторе (V_x, V_y ) блок сравнения 15 выдает команду на изменение координат вектора движения в счетчик перемещений 17 и обнуление результатов суммирования в блок 14.

В счетчике 17 формируется вектор (- V_0X-V_x,-V_0Y-V_y), который затем суммируется в схеме 11 с текущими значениями координат выбранных характерных пикселов макроблока. Полученные координаты определяют запись уровней яркости соответствующих пикселов из блока 6 в блок 12, и процесс анализа вектора движения продолжается до тех пор, пока не найден будет истинный вектор движения макроблока.

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

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

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

Работа устройства для реализации предложенного способа анализа векторов движения с использованием пространственной передискретизации изображения (фиг. 1-б) обусловлена работой блоков 1-5, обеспечивающих дискретизацию аналогового сигнала и описанных выше работы блока управления 20, работы блока передискретизации 5, работы вычислителя векторов уменьшенного разрешения (блоки 6-19) и работы вычислителя векторов конечного разрешения в (блоки 21-32). Работа вычислителя векторов уменьшенного разрешения аналогична работе устройства на фиг.1-а. Отличие заключается в том, что блоки 6-19 работают с уменьшенным разрешением кадра, соответственно макроблоки имеют размер 8х8 пикселов. Кроме того, результатом работы вычислителя векторов уменьшенного разрешения является несколько наилучших векторов, которые подаются на вход вычислителя векторов для конечного разрешения. Для вычисления наилучших векторов в блоке 17 запоминают несколько наилучших контрольных сумм и соответствующих им векторов движения. В сумматоре 25 значения векторов движения увеличиваются в отношение исходного и передискретизованного разрешений и добавляются к координатам смещения в опорном кадре с использованием счетчика перемещений 27. Работа вычислителя векторов конечного разрешения (блоки 21-31) также аналогична работе блоков 5-18 на фиг.1-а за исключением того, что в устройстве отсутствуют блоки переупорядочивания и вычисления положений опорных пикселов, так как на этапе уточнения векторов конечного разрешения используются все пикселы каждого макроблока.

Claims

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

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

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

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

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

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