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

Описание патента на изобретение RU2323541C2

Область техники

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

Предшествующий уровень техники

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПОРОГ1 = SAD1 + ОТКЛОНЕНИЕ,

где ОТКЛОНЕНИЕ может быть номинально установлено на 500,

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

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

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

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

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

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

Если после оценки первых шести векторов движения лучший ВД имеет значение метрики МСАР выше, чем пороговое значение ПОРОГ2, первый этап может переходить в режим захвата.

В предпочтительном варианте воплощения ПОРОГ2 определяется формулой:

ПОРОГ2 = 4* MMSADAVG,

MMSADAVG = Среднее из всех MMSAD(ММСАР) (т.е. значения МСАР лучшего ВД) предыдущего кадра.

В режиме захвата могут рассматриваться дополнительные параметры ПВД, такие как изображенные на Фиг.4. Например, эти 8 точек могут быть следующими:

(-12,0) (12,0) (0,-1) (0,9) (-6,4) (6,4) (6,-4) (-6,-4)

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

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

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

На первом этапе, когда устанавливается схема поиска вокруг параметра ПВД, может использоваться критерий раннего выхода, чтобы закончить поиск для этого параметра ПВД. Поиск может быть закончен, если значение МСАР, полученное для ВД, выше, чем текущий минимум МСАР (ММСАР) на пороговое значение ПОРОГ(ПОРОГ)3, т.е. если (МСАРi > (ММСАР + ПОРОГ3)). Где МСАРi - это МСАР, полученная для i-го параметра ПВД, ММСАР - это минимальное значение из всех значений МСАР, полученных до данного момента для текущего ВД. В частности, это значение МСАР для лучшего ВД. В предпочтительном варианте воплощения величина ПОРОГ3 может быть выбрана около 768.

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

Затем, среди всех ВД, перебираемых на первом этапе, выбирается ВД, который дает самое низкое значение метрики МСАР, и это становится точкой начала второго этапа.

На втором этапе выбирается лучший ВД из первого этапа (т.е. тот, который дает самое низкое значение МСАР) и выполняется поиск вокруг этого ВД. Например, поиск может выполняться по схеме, показанной на Фиг.5. Схема поиска может начаться с центра и раскручиваться по спирали в последовательности, изображенной на Фиг.5 в виде последовательности чисел. Как только лучший ВД найден (т.е. ВД, который дает самое низкое значение МСАР), схема поиска центрируется вокруг нового ВД и спиральная схема поиска начинается сначала. Этот процесс продолжается, пока не выполнено одно из трех условий:

УСЛОВИЕ 1: Значение МСАР ниже порогового значения ПОРОГ4, задаваемого формулой:

ПОРОГ4 = А *Q + B

Где Q - величина шага квантования, используемого кодером для текущего ВД, А и В - постоянные величины. В предпочтительном варианте воплощения А=8 и В=0.

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

УСЛОВИЕ 3: Нет улучшения в минимальном значении МСАР (ММСАР) в течение последних М возможных вариантов ВД. Здесь М - это функция индекса позиции последнего возможного варианта ВД в спиральной схеме поиска. Например, поиск начинается с индекса 0. Затем он раскручивается по спирали вокруг точек 1, 2, 3,... Как только находится лучший ВД, схема поиска по спирали центрируется вокруг этого нового ВД и индекс начинается с 0 снова. Этот индекс используется для определения значения М. В предпочтительном варианте воплощения М выбирается из набора величин {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} на основе индекса.

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

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

Метрика МСАР может быть предпочтительным признаком изобретения. Хотя метрика модифицированной суммы разностей дает предпочтительные результаты, любая метрика разности может использоваться в каждом варианте воплощения настоящего изобретения, требуя определения метрики суммы абсолютных разностей, метрики модифицированной суммы разностей или любой другой метрики разностей. Метрика МСАР является функцией суммы абсолютных разностей (САР), описанной выше, оцениваемого возможного варианта ВД, и вектора движения параметра прогнозирования (ВДП). ВДП как правило используется видеокодером во время кодирования окончательного вектора движения. Окончательный вектор движения кодируется как разность относительно ВДП, который отличается от ПВД. Например, это может быть однозначный ВД, определенный в рамках стандартов Н.261, Н.263, MPEG-1, MPEG-2 и MPEG-4 для целей кодирования векторов движения. САР - это метрика, используемая в классических алгоритмах оценки движения, как описано выше.

Для макроблока с данным ВДП и для возможного варианта вектора движения ВД МСАР определяется формулой:

МСАР = САР + Смещение,

где Смещение - это любая величина, основанная на метрике разности между ВД и ВДП. Например,

МСАР = САР + С* (| ВДх - ВДПх | + | ВДу - ВДПу|)

где САР - это классическая метрика, используемая для совпадающих блоков, определенных ранее, ВДх иВДу - это х и у составляющие возможного варианта вектора движения, ВДПх и ВДПу - это х и у составляющие ВДП, и С - постоянная величина. В предпочтительном варианте воплощения С приблизительно равно 5. ВДП, как правило, остается фиксированным для всех возможных вариантов в МБ, в то время как ВД изменяется.

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

МСАР для нулевого вектора движения, ВД = (0,0), рассматривается как особый случай. Нулевой ВД мог бы потенциально привести к повышенной эффективности сжатия. Но это может произойти только, если результирующий макроблок кодируется в «не кодируемом» режиме в рамках стандартов Н.261, Н.263, MPEG-1, MPEG-2 и MPEG-4.

Это может быть учтено путем смещения САР в случае, когда он ниже определенного порогового значения:

Если (САР < ПОРОГ5)

МСАР =САР - ПОРОГ6

Иначе

МСАР = САР + С*(|ВДПх| + |ВДПу|)

Конец если

С, ВДПх и ВДПу являются таковыми, как описано ранее.

ПОРОГ5 = D*Q +E

ПОРОГ6 = F

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

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

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

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

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

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

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

На Фиг.7 представлена схема 110 оценки движения на основе быстрого поиска прогнозируемого движения согласно возможному варианту воплощения. Схема 110 оценки движения может включать в себя блок 710 хранения параметра прогнозирования вектора движения, блок 710 определения схемы поиска, блок 730 поиска множества параметров движения и блок 740 определения окончательного вектора движения. Схема 110 оценки движения может также включать в себя блок 750 определения глобального вектора движения, блок 760 режима захвата, блок 770 завершения схемы и блок 780 вычисления модифицированной суммы абсолютных разностей. Указанные блоки работают согласно соответствующим им функциям, описанным выше.

Согласно еще одному варианту воплощения способ быстрого поиска прогнозируемого движения может осуществляться в два этапа. На первом этапе могут быть вычислены 7 возможных вариантов параметров ПВД, как описано выше. Затем, для каждого параметра ПВД могут быть оценены все возможные варианты ВД в соответствии со схемой поиска, показанной на Фиг.3, и могут использоваться критерии выхода для выхода из ПВД или перехода в режим захвата. Далее, в режиме захвата, может быть проведен поиск для и вокруг параметра ПВД, изображенного на Фиг.4 с использованием той же самой схемы поиска, как на Фиг.3, и того же критерия выхода. Затем, на втором этапе, может быть выбран лучший ВД из данных первого этапа и поиск может быть выполнен по спирали, как показано на Фиг.5. Спираль может быть центрирована заново и установлена в исходное состояние, индекс может быть установлен на ноль, как только обнаруживается лучшее согласование. Наконец, процесс может быть продолжен, пока не выполнится один из трех критериев выхода.

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

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

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

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

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

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

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

Похожие патенты RU2323541C2

название год авторы номер документа
СПОСОБ И УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КАЧЕСТВА СООТВЕТСТВИЯ БЛОКА 2003
  • Субраманиян Рагхаван
  • Гандхи Бхаван
RU2381630C2
СПОСОБ И УСТРОЙСТВО ДЛЯ АЛГОРИТМОВ ПРОТИВОСТОЯНИЯ ОШИБКАМ ПРИ БЕСПРОВОДНОЙ ПЕРЕДАЧЕ ВИДЕО 2007
  • Субраманиа Ситараман Ганапатхи
  • Уолкер Гордон Кент
  • Равииндран Виджаялакшми Р.
RU2404536C2
СПОСОБ ПОИСКА ВЕКТОРОВ ПЕРЕМЕЩЕНИЙ В ДИНАМИЧЕСКИХ ИЗОБРАЖЕНИЯХ 2011
  • Умняшкин Сергей Владимирович
  • Табориский Александр Евгеньевич
  • Александров Андрей Александрович
RU2487489C2
СПОСОБЫ И СИСТЕМЫ ЭКСПОНЕНЦИАЛЬНОГО РАЗБИЕНИЯ 2019
  • Калва, Хари
  • Фёрхт, Боривой
RU2788631C2
КОДЕР ИЗОБРАЖЕНИЯ И ДЕКОДЕР ИЗОБРАЖЕНИЯ, СПОСОБ КОДИРОВАНИЯ ИЗОБРАЖЕНИЯ И СПОСОБ ДЕКОДИРОВАНИЯ ИЗОБРАЖЕНИЯ 2012
  • Мория Йосими
  • Секигути Сунити
  • Сугимото Казуо
  • Ямада Йосихиса
  • Асаи Коутароу
  • Мураками Токумити
  • Идехара Юити
RU2506714C1
КОДЕР ИЗОБРАЖЕНИЯ И ДЕКОДЕР ИЗОБРАЖЕНИЯ, СПОСОБ КОДИРОВАНИЯ ИЗОБРАЖЕНИЯ И СПОСОБ ДЕКОДИРОВАНИЯ ИЗОБРАЖЕНИЯ, ПРОГРАММА КОДИРОВАНИЯ ИЗОБРАЖЕНИЯ И ПРОГРАММА ДЕКОДИРОВАНИЯ ИЗОБРАЖЕНИЯ И КОМПЬЮТЕРНО-СЧИТЫВАЕМЫЙ НОСИТЕЛЬ ЗАПИСИ, НА КОТОРОМ ЗАПИСАНА ПРОГРАММА КОДИРОВАНИЯ ИЗОБРАЖЕНИЯ, И КОМПЬЮТЕРНО-СЧИТЫВАЕМЫЙ НОСИТЕЛЬ ЗАПИСИ, НА КОТОРОМ ЗАПИСАНА ПРОГРАММА ДЕКОДИРОВАНИЯ ИЗОБРАЖЕНИЯ 2006
  • Мория Йосими
  • Секигути Сунити
  • Сугимото Казуо
  • Ямада Йосихиса
  • Асаи Коутароу
  • Мураками Токумити
  • Идехара Юити
RU2368095C1
ТЕХНОЛОГИИ ОЦЕНКИ ДВИЖЕНИЯ 2009
  • Букин Дов
RU2516220C2
БЫСТРОЕ ПРИНЯТИЕ РЕШЕНИЯ О ДЕЛЬТЕ ПАРАМЕТРА КВАНТОВАНИЯ МАКРОБЛОКА 2009
  • Е Янь
  • Карчевич Марта
  • Чэнь Пэйсун
RU2498523C2
КОДИРОВАНИЕ КАРТ ГЛУБИН ДВИЖЕНИЯ С ИЗМЕНЕНИЕМ ДИАПАЗОНА ГЛУБИНЫ 2012
  • Чэнь Ин
  • Карчевич Марта
RU2571511C2
ПРОСТРАНСТВЕННО-ВРЕМЕННОЕ ПРОГНОЗИРОВАНИЕ ДЛЯ ДВУНАПРАВЛЕНО ПРОГНОЗИРУЕМЫХ (В) ИЗОБРАЖЕНИЙ И ПРОГНОЗИРОВАНИЕ ВЕКТОРА ДВИЖЕНИЯ ДЛЯ КОМПЕНСАЦИИ ДВИЖЕНИЯ МНОЖЕСТВЕННЫХ ИЗОБРАЖЕНИЙ С ПОМОЩЬЮ ЭТАЛОНА 2003
  • Тоурапис Александрос
  • Ли Шипенг
  • Ву Фенг
RU2310231C2

Иллюстрации к изобретению RU 2 323 541 C2

Реферат патента 2008 года СПОСОБ И УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ ВЫСОКОКАЧЕСТВЕННОГО БЫСТРОГО ПОИСКА ПРОГНОЗИРУЕМОГО ДВИЖЕНИЯ

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

Формула изобретения RU 2 323 541 C2

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

Документы, цитированные в отчете о поиске Патент 2008 года RU2323541C2

RU 2182727 С2, 20.05.2002
RU 99103620 А, 10.03.2001
JP 2000278694 A, 06.10.2000
US 5557341 A, 17.09.1996
US 5488430 A, 30.01.1996
Походная разборная печь для варки пищи и печения хлеба 1920
  • Богач Б.И.
SU11A1
WO 9953438 A1, 21.10.1999
Способ термической обработки заготовок 1979
  • Нагорный Лев Константинович
  • Марьюшкин Лев Григорьевич
  • Прозоров Евгений Владимирович
SU863674A1

RU 2 323 541 C2

Авторы

Субраманиян Рагхаван

Гандхи Бхаван

Даты

2008-04-27Публикация

2003-07-25Подача