RU2381630C2

RU2381630C2 - Способ и устройство для определения качества соответствия блока

Info

Publication number: RU2381630C2
Application number: RU2005106280/09A
Authority: RU
Inventors: Рагхаван СУБРАМАНИЯН (US); Рагхаван СУБРАМАНИЯН; Бхаван ГАНДХИ (US); Бхаван ГАНДХИ
Original assignee: Моторола, Инк.
Priority date: 2002-08-06
Filing date: 2003-07-25
Publication date: 2010-02-10
Also published as: US20040028134A1; KR101018564B1; EP1574038A2; WO2004014060B1; MXPA05001448A; US7023921B2; AU2003256763A8; WO2004014060A3; KR20050056956A; AU2003256763A1; EP1574038A4; RU2005106280A; EP1574038B1; WO2004014060A2

Abstract

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

Description

ПРЕДШЕСТВУЮЩИЙ УРОВЕНЬ ТЕХНИКИ

Область техники, к которой относится изобретения

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

Уровень техники

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

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

Международные стандарты сжатия видеоизображения, такие как H.263, MPEG-2 и MPEG-4, обеспечивают возможность оценки движения на основе блока, обеспечивая синтаксис для описания векторов движения. Указанные стандарты не требуют конкретных алгоритмов оценки движения. В указанных стандартах сжатия оценка движения вычисляется на размере основного блока 16×16 пикселей, обозначенного как макроблок. Для оценки более малых областей изображения разрешается работать на размерах блока 8×8 пикселей.

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

Оценка движения с полным поиском (ОДПП, FSME) осуществляет полное сравнение блока в текущем кадре изображения с каждой позицией пикселя, размещенной внутри окна поиска ранее обработанного кадра. Добротность соответствия блока в каждой позиции пикселя определяется посредством измерения соответствующего ему расхождения. Обычной мерой расхождения, используемой показателями соответствия блока, является показатель суммы абсолютной разности (САР, SAD)

где B^c является блоком в текущем кадре изображения, а B^p является блоком в предыдущем кадре изображения. Индексы m и n индексируют пиксели внутри блока из N строк и М столбцов. Малое значение SAD соответствует хорошему соответствию блока, а большое значение SAD соответствует плохому соответствию блока. К сожалению, с увеличением окна поиска FSME становится недопустимым. Существует другая проблема для FSME, состоящая в том, что использование показателя SAD требует чрезмерного количества битов, требуемых для кодирования векторов движения, что приводит к не эффективности сжатия.

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

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

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

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

Фиг.1 - возможная блок-схема системы сжатия видеоизображения согласно одному варианту осуществления.

Фиг.2 - возможное изображение окрестности текущего макроблока согласно одному варианту осуществления.

Фиг.3 - возможная схема поиска, используемая в продолжение первой стадии предпочтительного варианта осуществления.

Фиг.4 - возможная схема поиска, используемая в режиме захвата в продолжение первой стадии предпочтительного варианта осуществления.

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

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

Фиг.7 - возможная блок-схема схемы оценки движения согласно одному варианту осуществления.

ПОДРОБНОЕ ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ

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

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

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

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

Фиг.1 - возможная блок-схема системы 100 сжатия видеоизображения для видеокодера согласно одному варианту осуществления. Система 100 сжатия видеоизображения может включать в себя схему 110 оценки движения по измененной сумме абсолютных разностей (ИСАР, MSAD), схему 115 компенсации движения, сумматор 120, схему 125 дискретного косинусного преобразования (ДКП, DCT), квантователь 130, кодер 135 кодирования с переменной длиной (поля записи) (КПЛ, VLC), обратный квантователь 140, схему обратного дискретного косинусного преобразования (ОДКП, IDCT) 145, другой сумматор 150 и схему 155 предыдущего кадра.

При действии вычисляется оценка движения для блоков данных изображения из текущего кадра изображения с использованием одного или большего количества обработанных ранее кадров изображения. Схема 110 оценки движения выводит вектор движения, соответствующий обрабатываемому блоку. Схема 115 компенсации движения, с использованием вычисленных векторов движения, формирует из предыдущего кадра блок предсказания. Сумматором 120 вычисляется разностное изображение посредством вычитания предсказанных данных изображения из текущего кадра изображения. Это разностное изображение преобразуется с использованием схемы 125 DCT. Тогда как схема 110 оценки движения и схема 115 компенсации движения служат для уменьшения временной избыточности между кадрами изображения, схема 125 DCT служит для уменьшения пространственной избыточности внутри кадра. Впоследствии квантователь 140 подвергает коэффициенты DCT уменьшению точности. Внося числовые потери, квантователь 140 усиливает сжатие. Затем квантованные коэффициенты DCT кодируются кодером 135 VLC и передаются в потоке битов сжатого видеоизображения вместе с векторами движения. Локальный контур восстановления состоит из обратного квантователя 140, IDCT 145 и сумматора 150. Обратный квантователь 140 восстанавливает коэффициенты DCT. IDCT 145 преобразовывает коэффициенты DCT обратно в пространственную область для формирования квантованного разностного изображения. Сумматор 150 вычисляет восстановленный кадр посредством суммирования данных, скомпенсированных по движению, с квантованным разностным изображением. Затем эти восстановленные данные сохраняются в схеме 155 предыдущего кадра для использования при обработке последующих кадров изображения.

Действие схемы 110 оценки движения с быстрым поиском, предсказывающим движение, может состоять из двух стадий. На первой стадии может быть выполнен малый поиск вокруг нескольких предсказателей вектора движения. Эти предсказатели вектора движения (ПВД, MVP) могут быть получены из других векторов движения (ВД, MV). Для исходных определений MV является разностью в координатах блока данных в текущем кадре данных изображения и блока данных в эталонном кадре, которому он соответствует. MV имеет две составляющих: X и Y. Значение MV описывается, как упорядоченная пара (X, Y). Предсказателями MVP являются вектора MV, которые, при выполнении нахождения соответствия, используются в качестве хорошего "приближения" наилучшего MV. Макроблоком (МБ, MB) является блок данных 16×16 внутри кадра видеоизображения. Без потери общности MB может также относиться к блокам данных различных размеров (например, 8×8, 4×8, 4×4,16×8 и т.д.).

Один предсказатель вектора движения может основываться на нулевом векторе движения. Предсказатель вектора движения, основанный на определенном векторе движения, может определять предсказатель вектора движения, как равный определенному вектору движения. Нулевой вектор движения является вектором движения с координатами (0,0). Второй предсказатель вектора движения может основываться на векторе движения в равноразмещенном макроблоке в предыдущем кадре.

Фиг.2 - возможная иллюстрация местоположения текущего макроблока и соседних макроблоков, используемых для определения дополнительных векторов движения. Соответственно третий предсказатель вектора движения может основываться на векторе движения макроблока слева от текущего макроблока. Четвертый предсказатель вектора движения может основываться на векторе движения макроблока сверху или над текущим макроблоком. Пятый предсказатель вектора движения может основываться на векторе движения макроблока справа и сверху от текущего макроблока. Шестой предсказатель вектора движения может основываться на векторе медианы движения третьего, четвертого и пятого предсказателей вектора движения. Этот предсказатель медианы вектора движения может вычисляться независимо для составляющих X и Y вектора движения.

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

THRESH1 = SAD1 + OFFSET,

где OFFSET может быть установлено номинально в 500,

где SAD1 задается уравнением

Здесь m и n являются индексами пикселя. М и N являются размерами блока. Для возможного макроблока М = N = 16. Общий вектор движения может быть определен также другими средствами, такими как датчики движения на видеокамерах, другими алгоритмами или любыми другими средствами для определения общего вектора движения.

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

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

Внутри малой области вокруг каждого MVP могут быть найдены все MV. Затем MV с самым низким показателем MSAD может быть выбран в качестве MV - кандидата для второй стадии. Показатель MSAD определен ниже.

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

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

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

THRESH2 = 4 · MMSADAVG,

MMSADAVG = Среднее всех MMSAD (т.е. показателей MSAD наилучших MV) предыдущего кадра.

В режиме захвата могут быть рассмотрены дополнительные MVP, как изображено на фиг.4. Например, может существовать 8 точек

(-12,0) (12,0) (0, -8) (0, 8) (-6, 4) (6, 4) (6, -4) (-6, -4)

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

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

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

На первой стадии, когда оценивается схема поиска вокруг MVP, для завершения поиска этого MVP может применяться критерий выхода, существующий ранее. Поиск может быть завершен, если MSAD, полученный для MV, превышает текущий минимум MSAD (MMSAD) на пороговое значение THRESH3, т.е. если (MSAD_i > (MMSAD + THRESH3)). Где MSAD_i является MSAD, полученной для MVP_i, MMSAD является минимумом всех значений MSAD, полученных до этой точки для текущего МB. В частности, это MSAD наилучшего MV. В предпочтительном варианте осуществления значение THRESH3 может быть выбрано около 768.

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

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

На второй стадии выбирается наилучший MV из первой стадии (т.е. тот, который дает низшую MSAD) и выполняется поиск вокруг этого MV. Например, поиск может выполняться по схеме, которая изображена на фиг.5. Схема поиска может начинаться из центра и может развертываться по спирали в последовательности, изображенной на фиг. 5 в виде последовательности чисел. Как только обнаруживается более хороший MV (т. е. MV, который дает более низкую MSAD), схема поиска центрируется заново вокруг нового MV, и спиралеобразная схема поиска начинается заново. Этот процесс продолжается, пока не удовлетворяется одно из 3 условий:

УСЛОВИЕ 1: MSAD ниже порогового значения THRESH4, заданного следующим образом

THRESH4 = A · Q + B,

где Q является размером шага квантования, используемым кодером для текущего MB, A и B являются константами. В предпочтительном варианте осуществления A = 8 и B = 0.

УСЛОВИЕ 2: на стадии 2 уже было рассмотрено максимальное количество кандидатов, N. В предпочтительном варианте осуществления N = 30.

УСЛОВИЕ 3: при M последних MV - кандидатах не происходит улучшения минимума MSAD (MMSAD). Здесь M является функцией от индекса позиции последнего MV - кандидата в спиралеобразной схеме поиска. Например, поиск начинается с индекса 0. Затем он развертывается по спирали вокруг точек 1, 2, 3, …. Всякий раз, при обнаружении лучшего MV, спиралеобразная схема поиска центрируется заново вокруг этого нового MV, и индекс еще раз начинается с 0. Этот индекс используется для определения значения M. В предпочтительном варианте осуществления М выбирается из набора значений {4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9} на основе индекса.

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

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

Показатель MSAD может быть существенной частью изобретения. Хотя показатель измененной суммы разностей дает предпочтительные результаты, любой показатель разности может взаимозаменяемо использоваться в каждом варианте осуществления настоящего изобретения, в котором требуется показатель суммы абсолютных разностей, показатель измененной суммы разностей или любой другой показатель разности. Кроме того, показатель MSAD особенно существенен для повышения эффективности всех систем видеокодера. В частности, для повышения эффективности показатель MSAD может заменять показатель SAD, показатель суммы квадратов или любой другой показатель в системе видеокодера. Например, показатель MSAD может использоваться в системе FSME, системе PMVFAST или любой другой системе видеокодера.

Показатель MSAD является функцией суммы абсолютных разностей (SAD), описанной выше, оцениваемого MV - кандидата и вектора движения предсказателя (PMV). PMV, в основном, используется видеокодером в продолжение кодирования итогового вектора движения. Итоговый вектор движения кодируется как разность относительно PMV, который отличен от MVP. Например, это может быть уникальный MV, определенный в стандартах H.261, H.263, MPEG-1, MPEG-2 и MPEG-4 для кодирования векторов движения. Как описано выше, SAD является показателем, используемым в классических алгоритмах оценки движения.

Для макроблока с заданным PMV и для вектора движения - кандидата MV, MSAD задается следующим образом

MSAD = SAD + Смещение,

где смещением является любое значение, основанное на показателе разности векторов движения между MV и PMV. Например,

MSAD = SAD + C · (|MV_X - PMV_X| + |MV_Y- PMV_Y|)

Согласно другому возможному варианту смещение может основываться на

C · ((MV_X-PMV_X)² + (MV_Y-PMV_Y)²),

где SAD является определенным ранее классическим показателем, используемым для соответствия блоков, MV_X и MV_Y являются составляющими X и Y вектора движения - кандидата, PMV_X и PMV_Y являются составляющими X и Y для PMV, а C является константой. В предпочтительном варианте осуществления C около 5. PMV, в основном, остается фиксированным для всех кандидатов в МB, в то время как MV изменяется.

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

MSAD для нулевого вектора движения, MV=(0,0), обрабатывается, как частный случай. Нулевой MV потенциально может привести к повышенной эффективности сжатия. Но это может произойти только, если результирующий макроблок кодируется в режиме "не кодированный" в стандартах H.261, H.263, MPEG-1, MPEG-2 и MPEG-4. Это можно учесть, смещая SAD в случае, где она ниже определенного порогового значения

If (SAD < THRESH5)

MSAD = SAD-THRESH6

Else

MSAD = SAD + C · (|PMV_X| + |PMV_Y|)

Endif

Обозначения C, PMV_X и PMV_Y описаны ранее.

THRESH5 = D·Q + E

THRESH6 = F,

где Q является размером шага квантователя. D, E и F являются константами. В предпочтительном варианте осуществления D около 128, E=0 и F около 100.

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

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

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

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

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

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

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

Фиг.6 - возможная блок-схема 600, иллюстрирующая действие схемы 110 оценки движения, согласно одному варианту осуществления. На этапе 610 блок-схема начинает действие. На этапе 620 схема 110 оценки движения определяет вектор движения предсказателя PMV. На этапе 630 схема 110 оценки движения определяет вектор движения MV - кандидат. На этапе 640 схема оценки движения вычисляет абсолютное значение разности между горизонтальными составляющими PMV и MV - кандидата. На этапе 650 схема 110 оценки движения вычисляет абсолютное значение разности между вертикальными составляющими PMV и MV - кандидата. На этапе 660 схема 110 оценки движения вычисляет смещение посредством умножения разности между составляющими PMV и MV - кандидата на константу. На этапе 670 схема 110 оценки движения вычисляет MSAD посредством суммирования смещения с показателем разности. На этапе 680 действие блок-схемы завершается.

Фиг.7 - возможная блок-схема схемы 100 оценки движения для быстрого поиска, предсказывающего движение, согласно одному варианту осуществления. В схему 110 оценки движения может входить вычислитель 710 показателя разности, вычислитель 720 смещения, вычислитель 730 MSAD и схема 740 определения вектора движения. Схемы действуют в соответствии с подобными им функциями, описанными в отношении блок-схемы 600.

Согласно другому связанному варианту осуществления способ быстрого поиска, предсказывающего движение, может быть выполнен в двух стадиях. На первой стадии может быть вычислено, как описано выше, 7 кандидатов MVP. Затем для каждого MVP все MV - кандидаты могут быть оценены в соответствии со схемой поиска фиг.3, и могут быть использованы критерии выхода для «вырывания» MVP или для входа в режим захвата. Затем (при действии) в режиме захвата может быть выполнен поиск вокруг MVP, изображенный на фиг.4 с использованием той же схемы поиска фиг. 3 и того же критерия выхода. Затем на второй стадии может быть выбран наилучший MV первой стадии и выполнен спиралеобразный поиск, изображенный на фиг.5. Каждый раз при обнаружении наилучшего соответствия спираль может центрироваться заново и возвращаться в исходное состояние, индекс может сбрасываться в ноль. В заключение процесс может продолжаться до обнаружения одного из трех критериев выхода.

Раскрытое изобретение может достигать высокой степени эффективности сжатия при невысокой сложности. Его сложность может быть аналогична сложности APDZS и PMVFAST. Однако достигаемое качество выше. По сравнению со стандартом алгоритма полного поиска, который является эталоном, принятым в промышленности, настоящее изобретение достигает эффективности сжатия, дающей приблизительно 0,6% улучшение для качества фиксированного видеоизображения. Это число было получено после усреднения по 24 различным видеосериям QCIF.

Одним применением для этого изобретения являются видеокодеры в реальном масштабе времени на переносных устройствах. Обычная ширина полосы частот такого кодированного видеоизображения находится в диапазоне от 32 кбит/с до 512 кбит/с, и обычным размером кадра изображения является применяемый в QCIF и CIF.

Способ этого изобретения предпочтительно реализуется на программируемом процессоре. Однако система 100 сжатия видеоизображения, схемы 110 оценки движения и других элементов могут быть реализованы также на универсальном или специализированном компьютере, программируемом микропроцессоре или микроконтроллере и периферийных элементах интегральной схемы, ASIC или другой интегральной схемы, аппаратной электронной или логической схеме, такой как схема дискретного компонента, программируемом логическом устройстве, таком как PLD, PLA, FPGA или PAL, или подобном устройстве. В основном любое устройство, на котором постоянно находится конечный автомат, может реализовать блок-схемы, изображенные на чертежах, и описанные способы могут использоваться для выполнения функций процессора этого изобретения.

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

Claims

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

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

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

4. Способ по п.3, в котором этап вычисления смещения на основе вектора движения-предсказателя и вектора движения-кандидата дополнительно включает в себя умножение показателя разности векторов движения между вектором движения-предсказателем и вектором движения-кандидатом на константу.

5. Способ по п.4, в котором константа равна приблизительно 5.

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

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

8. Способ по п.1, в котором вектором движения-кандидатом является один из нескольких векторов движения-кандидатов, оцениваемых для макроблока, и в котором вектор движения-предсказатель остается фиксированным для каждого. вектора движения-кандидата в макроблоке.

9. Способ по п.1, в котором показателем разности является показатель суммы абсолютных разностей.

10. Способ по п.1, в котором показателем разности является показатель суммы квадратов разностей.

11. Способ по п.1, в котором дополнительно определяют итоговый вектор движения на основании вектора движения-кандидата и выводят итоговый вектор движения.

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

13. Способ по п.12, в котором определяют итоговый вектор движения для использования на второй стадии системы видеокодера.

14. Способ по п.12, в котором показателем разности является по меньшей мере один из показателей-показатель суммы абсолютных разностей и показатель суммы квадратов разностей.

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

16. Способ по п.12, в котором этап определения схемы поиска дополнительно включает в себя определение схемы поиска, которая более распространена в горизонтальном направлении, чем в вертикальном направлении.

17. Способ по п.12, дополнительно выводят вектор движения на основании итогового вектора движения.

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

19. Устройство по п.18, в котором вычислителем показателя разности является по меньшей мере один из вычислителей-вычислитель суммы абсолютных разностей и вычислитель суммы квадратов разностей.

20. Устройство по п.18, в котором вычислитель смещения вычисляет смещение посредством определения показателя разности векторов движения между вектором движения-предсказателем и вектором движения-кандидатом.

21. Устройство по п.20, в котором вычислитель смещения дополнительно вычисляет смещение посредством умножения показателя разности векторов движения между вектором движения-предсказателем и вектором движения-кандидатом на константу.

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

23. Устройство по п.22, в котором вектором движения-кандидатом является один из нескольких векторов движения-кандидатов, оцениваемых для макроблока, и в котором вектор движения-предсказатель остается фиксированным для каждого вектора движения-кандидата в макроблоке.

24. Устройство по п.20, в котором вычислитель смещения дополнительно определяет показатель разности векторов движения между вектором движения-предсказателем и вектором движения-кандидатом посредством суммирования квадрата разности между горизонтальными координатами вектора движения-предсказателя и вектора движения-кандидата с квадратом разности между вертикальными координатами вектора движения-предсказателя и вектора движения-кандидата.

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

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

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

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