СПОСОБ ПОИСКА ВЕКТОРОВ ДВИЖЕНИЯ ДЕТАЛЕЙ В ДИНАМИЧЕСКИХ ИЗОБРАЖЕНИЯХ НА ОСНОВЕ ДВУМЕРНОГО ДИСКРЕТНОГО СПЕКТРАЛЬНОГО ПРЕОБРАЗОВАНИЯ Российский патент 2004 года по МПК H04N7/30 

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

Известно множество способов анализа векторов движения деталей в динамических изображениях. Наиболее простым и точным является способ поиска векторов движения макроблоков на основе алгоритма полного перебора (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). Согласно этому способу для поиска вектора движения V=(V_х, V_y) рассматривается норма разницы (SAD) сигналов яркости двух макроблоков в текущем и опорном (соседнем по времени) кадрах со сдвигом на вектор движения.

Здесь f - значение яркости, (x,y) - пространственные координаты точки в кадре, t - временной индекс текущего кадра, t-Δt - временной индекс опорного кадра, суммирование производится по всем точкам макроблока В.

Значение V, для которого норма SAD имеет наименьшее значение, принимается за искомый вектор. Векторы движения ищутся методом полного перебора в некоторой ограниченной окрестности: min<V_x,V_y < max.

В данном способе при поиске одного вектора движения макроблока 16×16 пикселов в окрестности размером ±N пикселов по координатам х и y требуется порядка 3·256·(2N+1)² операций. В пересчете на один пиксел макроблока требуется 3·(2N+1)² операций, что при области поиска в пределах ±16 (N=16) составляет достаточно значительную величину более 3000 операций/пиксел.

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

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

Наиболее близким по технической сущности к заявляемому техническому решению является способ поиска векторов движения деталей в динамических изображениях (Патент РФ №2182727 от 20.05.2002, G 06 K 9/00, G 06 T 7/20), включающий преобразование последовательности кадров изображений в цифровую форму, запоминание дискретных отсчетов пикселов текущего и соседнего по времени (опорного) кадров, разбиение текущего кадра на макроблоки и поиск вектора движения каждого из макроблоков текущего кадра относительно опорного кадра посредством минимизации по рассматриваемому множеству векторов движения контрольной суммы данного макроблока, являющейся суммой норм попиксельной разности уровней в текущем и опорном кадрах, причем среди множества пикселов каждого макроблока выбирают небольшое число пикселов, характеризующих рельеф значений макроблока, и упомянутую контрольную сумму вычисляют лишь по выбранным опорным пикселам, при этом координаты выбранных пикселов в макроблоке определяют с использованием значений всех пикселов макроблока.

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

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

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

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

Фиг.2 отображает среднее распределение энергии спектра дискретного косинусного преобразования 8×8 по его частотным коэффициентам.

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

Фиг.4(а) отображает сравнительные данные по качеству поиска и компенсации движения для блоков 8×8 пикселов между прямым способом (SAD) и методом на основе ДКП блоков 8×8 пикселов с различным числом коэффициентов для видеопоследовательности “Футбол”.

Фиг.4(б) отображает сравнительные данные по качеству поиска и компенсации движения для блоков 8×8 между прямым способом (SAD) и методом на основе ДКП 8×8 с различным числом коэффициентов для видеопоследовательности “Сад цветов”.

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

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

Рассмотрим в качестве примера двумерное дискретное косинусное преобразование.

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

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

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

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

Здесь F_cur - матрица коэффициентов ДКП блока в текущем кадре, F_ref - матрица коэффициентов ДКП блока (сдвинутого на вектор V={V_x,V_y) относительно позиции блока в текущем кадре) в опорном кадре, (х,y) -индексы спектральных коэффициентов в матрицах преобразования, суммирование производится по множеству индексов FmaxIndx, соответствующих нескольким максимальным по модулю коэффициентам матрицы F_cur. Значение V, для которого норма SAD_dct имеет наименьшее значение, принимается за искомый вектор. Векторы движения могут искаться как методом полного перебора в некоторой ограниченной окрестности: min <V_x, V_y< max, так и любым из известных быстрых методов поиска: иерархический, логарифмический, спиральный, ортогональный и др.

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

Реализация данного способа на векторном процессоре (Л1879ВМ1) позволяет сократить суммарное время поиска векторов движения с зоной поиска 32×32 по сравнению с обычным методом (на основе попиксельной разности двух макроблоков) в 4-5 раз для блоков размером 8х8 пикселов при использовании 8 из 64 коэффициентов ДКП.

В таблицах фиг.4 приводятся сравнительные данные по качеству поиска и компенсации движения для блоков 8х8 пиксилов между прямым способом (SAD) и методом на основе ДКП преобразования для двух тестовых видеопоследовательностей с различным числом используемых коэффициентов (DCT(8/64) - 8 коэффициентов из 64, DCT(16/64) - 16 из 64 и т.д.). Сравнение производилось между кадрами исходной последовательности и восстановленными кадрами по найденным векторам движения из соответствующих опорных кадров исходной последовательности. В таблице приведены количественные оценки по трем мерам: среднеквадратичная ошибка (КМ8Е), среднеабсолютная ошибка (МАЕ) и отношение сигнал/шум (PSNR).

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

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

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

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

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

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

С выхода блока 7 матрица яркостей блока поступает на вход двумерного спектрального преобразования 8.

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

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

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

По индексам, хранящимся в блоке 10, из блоков памяти коэффициентов 9 и 13 извлекаются N соответствующих спектральных компонент и подаются на вход блока 14.

В блоке 14 над ними производится вычисление суммы норм (контрольной суммы) поэлементных разностей по формуле

,

где F_cur - извлеченные коэффициенты из блока 9, F_cur - извлеченные коэффициенты из блока 13.

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

Найденный вектор движения текущего блока сохраняется в блоке 16 памяти векторов движения.

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

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

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