ТЕХНОЛОГИИ ОЦЕНКИ ДВИЖЕНИЯ Российский патент 2014 года по МПК H04N19/557 G06T7/20 

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

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

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

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

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

Краткое описание чертежей

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

на фиг.1 показана схема примерного устройства;

на фиг.2 показана схема примерных кадров;

на фиг.3 показана блок-схема последовательности операций, представляющая примерные операции;

на фиг.4 показана схема примерного варианта осуществления;

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

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

Подробное описание изобретения

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

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

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

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

Источник 102 изображения обеспечивает значение пикселя для модуля 104 кодирования изображения. Более конкретно, на фиг.1 показано, что эти значения пикселя могут быть размещены в виде потока 122 сигнала, который представляет одно или больше изображений. Таким образом, поток 122 сигнала может содержать последовательность кадров или полей, имеющих множества значений пикселя. Каждый кадр/поле (также называемые изображениями) может соответствовать определенному времени или временному интервалу. В вариантах осуществления поток 122 сигнала является цифровым. В качестве альтернативы, поток 122 сигнала может быть аналоговым.

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

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

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

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

Модуль 104 кодирования изображения кодирует (например, сжимает) сигналы изображения, передаваемые в потоке 122 сигнала, для получения кодированного сигнала 124. Такое кодирование может выполняться в соответствии с одной или больше технологиями. Например, в модуле 104 кодирования изображения могут использоваться различные технологии сжатия для использования избыточности (например, пространственной избыточности и/или временной избыточности), присущей потоку 122 сигнала. Такие технологии могут включать в себя алгоритмы сопоставления блоков.

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

Модуль 106 оценки движения определяет вектор движения для блоков (например, макроблоков) в пределах изображений или кадров. В свою очередь, модуль 104 кодирования изображения может включать эти вектора движения в кодированный сигнал 124.

В вариантах осуществления модуль 104 кодирования изображения может соответствовать, например, одному или больше стандартам Экспертной группы по вопросам движущегося изображения (MPEG), такому как MPEG-2 и/или MPEG-4. Также, модуль 104 кодирования изображения, может соответствовать одному или больше стандартам, установленным Международным союзом электросвязи (ITU) Сектор стандартизации связи (ITU-T). Примеры таких стандартов включают в себя Н.261, Н.263, и Н.264. Однако варианты осуществления не ограничены этими примерами.

Как описано выше, модуль 104 кодирования изображения, генерирует кодированный сигнал 124 из исходного потока 122 сигнала. В свою очередь, устройство 100 может сохранять кодированный сигнал 122 на носителе информации (например, в запоминающем устройстве). Устройство 100 также может декодировать и выводить (например, отображать) кодированный сигнал 124. Кроме того, устройство 100 может передавать кодированный сигнал 124 в удаленное устройство через одну или больше сетей (не показаны). После приема удаленное устройство может сохранять, декодировать, и/или выводить (например, отображать) соответствующие изображения.

Устройство 100 может быть воплощено в различных устройствах, таких как переносное устройство или встроенная система. Примеры таких устройств включают в себя мобильные беспроводные телефоны, телефоны системы голос по IP (VoiP), персональные компьютеры (PC), карманные персональные компьютеры (PDA), и цифровые камеры. Кроме того, такая система также может быть воплощена в виде видеотелефонов наземной линии, в которых используются стандартные телефонные коммутируемые сети общего пользования (PSTN), телефонные линии цифровой сети с комплексными услугами (ISDN) и/или сети пакетной передачи данных (например, локальные вычислительные сети (LAN), Интернет и т.д.). Варианты осуществления, однако, не ограничиваются этими примерами.

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

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

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

"Сумма абсолютных различий" (SAD), получила широкое распространение и принята как основа (или как средство измерения) для определения векторов движения. Это связано с ее простотой и понятным воплощением. SAD может быть рассчитана как представлено ниже в Уравнении (1).

$$SAD\left(m,n\right)={\displaystyle \sum _{i=0}^{N\text{-}1}{\displaystyle \sum _{j=0}^{N\text{-}1}\left|current\left(i,j\right)\text{-reference}\left(\text{i}+\text{m}\text{, j}+\text{n}\right)\right|}}\left(1\right)$$

В Уравнении (1): m и n представляют смещение между текущим блоком и предыдущим опорным блоком в направлениях x и y, соответственно; current (i, j) представляет значение текущего изображения в положении i, j; и reference (i+m, j+n) представляет значение предыдущего изображения в положении i+m, j+n.

В соответствии с этим, SAD по Уравнению (1) обеспечивает набор значений для определенного блока. В частности Уравнение (1) представляет, что SAD представляет собой функцию вектора смещения (вектор смещения, имеющий компоненты m и n).

Алгоритм, называемый алгоритмом согласования полного блока поиска (FSBMA), обеспечивает простой способ выполнения оценки движения. Такой алгоритм подразумевает расчет SAD для каждого m и n в области поиска (также называется окном поиска), и выбора значений m и n, которые позволяют получить минимальное значение SAD как "наилучший" вектор движения. К сожалению, FSBMA требует большого объема расчетов.

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

Алгоритм последовательного устранения преодолевает проблему локального минимума. Также, этот алгоритм удобен для воплощения в виде аппаратных средств. Алгоритм последовательного воплощения, который является менее требовательным к объему вычислений, чем FSBMA, находит наилучшие минимальные вектора движения с "минимальной ошибкой". Алгоритм последовательного устранения основан на математическом неравенстве, предоставленном ниже, в Выражении (2).

$$\begin{array}{l}\text{SAD}\left(\text{m}\text{, n}\right)={\displaystyle \sum _{\text{i}=\text{0}}^{\text{N-1}}{\displaystyle \sum _{\text{j}=\text{0}}^{\text{N-1}}\left|\text{current}\left(\text{i}\text{, j}\right)\text{-reference}\left(\text{i}+\text{m}\text{, j}+\text{n}\right)\right|}}\ge \\ \left|{\displaystyle \sum _{\text{i}=\text{0}}^{\text{N-1}}{\displaystyle \sum _{\text{j}=\text{0}}^{\text{N-1}}\text{current}\left(\text{i}\text{, j}\right)\text{-}{\displaystyle \sum _{\text{i}=\text{0}}^{\text{N-1}}{\displaystyle \sum _{\text{j}=\text{0}}^{\text{N-1}}\text{reference}\left(\text{i}+\text{m}\text{, j}+\text{n}\right)}}}}\right|=\text{SSAD}\left(\text{m}\text{, n}\right)\left(\text{2}\right)\end{array}$$

Как показано в Выражении (2), SSAD (m, n) (подвыборка функции SAD) обеспечивает нижнюю границу для SAD (m, n). Кроме того, для данной точки SSAD (m, n) требует меньших расчетов, чем SAD (m, n). Таким образом, алгоритм последовательного устранения вначале рассчитывает SSAD (m, n) для заданной точки. Если рассчитанное значение SSAD (m, n) не позволяет получить требуемую нижнюю границу для соответствующего значения SAD (m, n) (то есть, если рассчитанное значение SSAD (m, n) не меньше, чем текущее известное минимальное значение SAD), то более объемные вычисления SAD (m, n) для этой точки пропускают.

Алгоритм называемый, алгоритмом глобального устранения, аналогичен алгоритму последовательного устранения, поскольку в нем также используется SSAD (m, n), как нижняя граница для SAD (m, n). Например, алгоритм глобального устранения рассчитывает SSAD (m, n) для ряда положений поиска (обозначенных целым числом P) и сортирует их так, как показано ниже в Выражении (3).

$$\left\{SSA{D}_0\le SSA{D}_1\le SSA{D}_2\le SSA{D}_{M\text{-}1}\le SSA{D}_M\le SSA{D}_{P\text{-}1}\le SSA{D}_P\right\}\left(3\right)$$

Затем, алгоритм глобального устранения находит наилучшее положение поиска M<<P с минимальными значениями SSAD. Эти положения поиска обозначены как (m_i, n_i) в Выражении (4), представленном ниже.

$$\left({\text{m}}_{\text{i}}{\text{, n}}_{\text{i}}\right)=\left\{\left(\text{m}\text{, n}\right)|\text{SSAD}\left(\text{m}\text{, n}\right)\le {\text{SSAD}}_{\text{M}}\right\}\left(\text{4}\right)$$

После того, как эти положения поиска будут идентифицированы, алгоритм глобального устранения рассчитывает SAD (m, n) для каждого из M положений поиска. Затем, идентифицируют положение с минимальной SAD среди M кандидатов. Это положение раскрывает вектора движения MV, в соответствии с Выражением (5), представленным ниже.

$$\text{MV}=\left\{\left(\text{u}\text{, ν}\right)|\text{SAD}\left(\text{u}\text{, ν}\right)\le \text{SAD}\left({\text{m}}_{\text{i}}{\text{, n}}_{\text{i}}\right)\text{, }\forall \text{i}<\text{M}\right\}\left(\text{5}\right)$$

Основной недостаток алгоритма глобального устранения состоит в том, что для него требуется сортировать значения SSAD (m, n) всех P точек поиска внутри поиска области. Таким образом, такой алгоритм может требовать объемных вычислений.

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

Алгоритм двухуровневого целого идентифицирует пороговое значение T, которое разделяет значение SSAD на первый и второй набор. Первый набор включает все SSAD (m, n) значения, которые меньше или равны T. В отличие от этого, второй набор включает в себя все значения SSAD (m, n), которые больше T.

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

Алгоритм двухуровневого целого обеспечивает высокую вероятность успеха при поиске "наилучшего" вектора движения. Выражение (6), представленное ниже, представляет критерии для точек в пределах первого набора (m_i, n_i). Также, Выражение (7) представляет, что количество точек в пределах первого набора может изменяться от М на величину Δ.

$$\left({\text{m}}_{\text{i}}{\text{, n}}_{\text{i}}\right)=\left\{\left(\text{m}\text{, n}\right)|\text{SSAD}\left(\text{m}\text{, n}\right)\le \text{T}\right\}\left(\text{6}\right)$$

$$\left|\left(m_i,n_i\right)\right|=M\pm \Delta (7)$$

Одна технология для поиска T включает в себя использование ограниченного диапазона поиска. Выражение (8) представляет, что этот ограниченный диапазон поиска имеет нижний предел T_min и верхний предел T_max.

$$T\in \left[T_{\min },T_{\max }\right]\left(8\right)$$

В вариантах осуществления T_min может быть выбрано как минимум всех значений SSAD, в то время как T_max может быть выбрано, как среднее значение всех значений SSAD. Эти варианты выбора представлены ниже в Выражениях (9) и (10).

$$T_{\max }=\frac{1}{P}{\displaystyle {\sum }_{i=0}^{P}SSAD\left(m_i,n_i\right)}\left(10\right)$$

Такой выбор T_max может быть основан, например, на неравенстве Маркова, в представленном Выражении (11).

$$P\left(\left|x\right|\ge a\right)\le \frac{E\left(\left|x\right|\right)}{a},a>0\left(11\right)$$

Например, M может быть выбрано таким образом, что оно составляет 10% от суммы P точек. Путем моделирования набора всех P значений SSAD как положительного случайного переменного значения X, имеющего дискретное однородное распределение, применение неравенства Маркова (подставление T вместо a) обеспечивает анализ Выражений (12) и (13). Этот анализ показывает, что среднее значение SSAD всех точек P обеспечивает соответствующую верхнюю границу для T (то есть, T_max).

$$P\left(\left|x\right|\ge T\right)=0.9\left(12\right)$$

$$0.9\le \frac{E\left(\left|x\right|\right)}{T}\to T\le \frac{E\left(\left|x\right|\right)}{0.9}\left(13\right)$$

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

В вариантах осуществления значения SAD и SSAD могут быть основаны на отдельных значениях пикселя. Однако, в дополнительных вариантах осуществления, значения SAD и SSAD могут быть основаны на суммах, соответствующих блокам пикселей. Пример такой технологии представлен на фиг.2.

В частности, на фиг.2 показана схема, представляющая текущий кадр 202, опорный кадр 204 и обрабатываемый опорный кадр 206. Текущий кадр 202 включает в себя микроблок 208. Этот микроблок представляет собой область в пределах текущего кадра 202, которая имеет ширину 16 пикселей на высоту 16 пикселей (16×16).

С целью расчета SAD и SSAD значения пикселей в пределах микроблоков могут быть скомбинированы для повышения эффективности расчетов. Например, множество подблоков 4×4 существует в пределах микроблока 208. Каждое из значений пикселей подблока суммируют для генерирования соответствующего значения для микроблока 208. Таким образом, микроблок 208 может быть представлен как массив размером 4×4 значений (то есть, значения для каждого подблока).

Этот принцип показан на фиг.2 в виде представления 220 с увеличением микроблока 206. В этом представлении, микроблок 208 показан как массив сумм размером 4×4. Каждая из этих сумм (представлено ниже в Выражении 14) представляет собой значение пикселя, суммарное для соответствующего подблока размером 4×4:

$${\displaystyle {\sum }_{i,j}^{4\times 4}x\left(i,j\right)}\left(14\right)$$

Таким образом, на основе технологии, значения SSAD макроблока 208, могут быть рассчитаны, как показано ниже в Выражении (15)

$$SSAD\left(m,n\right)={\displaystyle \sum _{j=1}^4{\displaystyle \sum _{i=1}^4\left|\Vert curren{t}_{i,j}^{4\times 4}\Vert \text{-}\Vert \text{reference}{\left(\text{m}\text{, n}\right)}_{i,j}^{4\times 4}\Vert \right|}}\le SA{D}^{16\times 16}\left(m,n\right);\left(15\right)$$

где: $$\Vert X_{i,j}^{4\times 4}\Vert ={\displaystyle {\sum }_{i,j}^{4\times 4}x\left(i,j\right)}$$

Варианты осуществления могут дополнительно улучшить эффективность расчета путем расчета значений пикселя подблока для всего опорного кадра. Эти расчеты выходят за пределы размера опорного кадра на размер используемого подблока. Например, на фиг.2 показан с увеличением опорный кадр 206, имеющий высоту H+4 и ширину W+4. В пределах этого увеличенного опорного кадра показано окно 210 поиска, в котором может быть выполнен поиск вектора движения.

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

Поток, показанный на фиг.3 подразумевает оценку векторов движения для микроблоков в пределах текущего изображения (кадра). Эти вектора движения основаны на опорном изображении (в кадре). На фиг.3 показано, что, в блоке 302, все суммы подблоков (например, подблок размером 4×4) рассчитывают для опорного изображения.

В блоке 304, выбирают микроблок в пределах текущего изображения. На основе такого выбора определяют значение нулевого смещения SAD в блоке 306. Такое значение SAD обозначено как минимальное значение SAD. Как обозначено блоком 308, операция переходит к блоку 316, если это значение SAD будет меньше, чем заданное выходное пороговое значение. В противном случае, операция переходит к блоку 310.

Множества значений SSAD рассчитывают в блоке 310. Это может содержать, например, расчет всех значений SSAD в пределах используемого окна поиска.

В блоке 312 определяют пороговое значение разделения. Это может содержать определение порогового значения T, как описано выше со ссылкой на Выражения (6)-(13).

На основе определенного порогового разделения идентифицируют M положений поиска. В соответствии с этим, в блоке 314, значения SAD рассчитывают для каждого из этих положений поиска. На основе этих значений SAD (и значения SAD нулевого смещения, определенного в блоке 306), минимальное значение SAD обновляют в блоке 316.

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

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

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

Варианты 400 воплощения могут включать в себя различные элементы. Например, на фиг.4 показано воплощение, включающее в себя носитель 402 сохранения, модуль 404 выбора блока, и модуль 406 расчета вектора. Эти элементы могут быть воплощены в аппаратных средствах, программных средствах или в любой их комбинации.

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

Модуль 404 выбора блока выбирает блок (например, макроблок), в пределах текущего изображения. Как обозначено на фиг.4, такой выбор приводит к тому, что индикатор 420 выбора передают в носитель 402 сохранения. На основе этого индикатора выбора носитель 402 сохранения обеспечивает данные для модуля 406 расчета вектора. В частности на фиг.4 представлен носитель 402 сохранения, предоставляющий данные 422 опорного изображения, данные 424 текущего изображения и данные 426 текущего изображения.

Модуль 406 расчета вектора рассчитывает вектор 438 движения для блока, выбранного модулем 402 выбора блока. Такой расчет может быть выполнен в соответствии с технологиями, описанными здесь. Как показано на фиг.4, модуль 404 расчета вектора включает в себя модуль 408 суммирования подблока, модуль 410 расчета SSAD, модуль 412 расчета SAD, модуль 414 определения порогового значения, модуль 416 минимального выбора и модуль 418 определения вектора движения. Как описано выше, эти элементы могут быть воплощены в аппаратных средствах, программных средствах или в любой их комбинации.

На фиг.4 показано, что модуль 408 суммирования подблока принимает данные 422 опорного изображения с носителя 402 сохранения. На основе этих данных, модуль 408 суммирования подблока рассчитывает суммы 427 подблока, которые передают в модуль 410 расчета SSAD и в модуль 412 расчета SAD.

Модуль 410 расчета SSAD принимает суммы 427 подблока и данные 424 текущего изображения. Из этой информации модуль 410 расчета SSAD рассчитывает значения 428 SSAD, как описано здесь. Такие значения SSAD могут соответствовать величинам смещениям в пределах окна поиска. Как показано на фиг.4, модуль 410 расчета SSAD передает значения 428 SSAD в модуль 414 определения порогового значения.

После приема этой информации модуль 414 определения порогового значения определяет пороговое значение разделения для значения SSAD. Например, модуль 414 определения порогового значения может определять T, как описано выше со ссылкой на Выражения (6)-(13). На основе этого определения, модуль 414 определения порогового значения возвращает пороговое значение 430 в модуль 410 расчета SSAD.

В ответ на это пороговое значение, модуль 410 расчета SSAD передает индикаторы 432 смещения в модуль 430 расчета SAD. Эти индикаторы соответствуют значениям SSAD, которые соответствуют пороговому значению 430. Таким образом, модуль 410 расчета SSAD может передать M±Δ индикаторы в модуль 412 расчета SAD.

На фиг.4 показано, что модуль 412 расчета SAD принимает данные 422 опорного изображения и данные 426 текущего изображения. На основе этой информации, модуль 412 расчета SAD рассчитывает значения SAD для каждого из индикаторов 432 смещения. Кроме того, как описано выше со ссылкой на фиг.3, модуль 412 расчета SAD может рассчитывать значение SAD нулевого смещения. Результаты этих расчетов передают в модуль 416 выбора минимума в качестве значений 434 SAD.

Модуль 416 выбора минимума сортирует значения 434 SAD и идентифицирует минимальное значение SAD. Исходя из этого, модуль 416 выбора минимума генерирует индикатор 436 смещения, соответствующий минимальному значению SAD. Как показано на фиг.4, этот индикатор передают в модуль 418 определения вектора движения. На основе индикатора 436 модуль 418 определения вектора движения определяет вектор 438 движения.

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

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

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

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

В блоке 508, определяют вектор движения на основе блока в текущем изображении и соответствующий блок.

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

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

На фиг.6 показано примерное воплощение 600, которое может быть включено в модуль 104 кодирования изображения. Такое воплощение может включать в себя различные элементы, такие как кодер 602, модуль 604 сохранения кадра и модуль 607 установки параметра. Однако, варианты осуществления не ограничены этими элементами.

Кодер 602 может использовать гибридную схему кодирования компенсирования движения, на основе преобразования. Варианты осуществления, однако, не ограничены этим примером. В таких схемах кодирования могут использоваться пространственные и временные избыточности для уменьшения количества данных, необходимых для представления изображения. Таким образом, кодер 602 может соответствовать, например, одному или больше стандартам Экспертной группы по вопросам движущегося изображения (MPEG), такому как MPEG-2 и MPEG-4. Также, кодер 602 может соответствовать одному или больше стандартам, установленным Международным союзом электросвязи (ITU), Сектор стандартизации связи (ITU-T). Примеры таких стандартов включают в себя H 261, H 263, и H 264.

На фиг.6 показано, что кодер 602 включает в себя прямой участок 605 и участок 606 реконструирования. Прямой участок 605 принимает несжатую информацию изображения и выводит эту информацию в кодированной (например, сжатой) форме. Однако, прямой участок 605 основан на участке 606 реконструирования для обеспечения предикативной информации, которая используется для кодирования.

Модуль 604 сохранения кадра сохраняет сигнал изображения, как кадры. Эти кадры могут быть приняты, например, из датчика изображения, такого как датчик 104 изображения. Кроме того, со ссылкой на фиг.4, модуль 204 сохранения кадра может обеспечивать свойства носителя 402 сохранения. Кроме того, модуль 604 сохранения кадра сохраняет реконструированные кадры, принятые из кодера 602. В соответствии с этим, модуль 604 сохранения кадра может включать в себя носитель сохранения, такой как запоминающее устройство. Примеры носителей сохранения представлены ниже.

И снова со ссылкой на кодер 602, на фиг.6 представлено, что его прямой участок 605 может включать в себя модуль 106 оценки движения по фиг.1. Кроме того, прямой участок 205, может включать в себя узел 610 комбинирования (например, различия), модуль 612 прямого преобразования, модуль 614 квантования, модуль 616 кодирования и может выбирать модуль 618 прогнозирования внутри кадра. Также, на фиг.6 показано, что участок 606 реконструирования может включать в себя модуль 620 компенсации движения, модуль прогнозирования 622 внутри кадра, модуль 624 маршрутизации, модуль 626 обратного квантования, модуля 628 обратного преобразования, модуль 630 комбинирования (например, суммирования) и фильтр 632 удаления блоков в цикле.

На фиг.6 представлено, что модуль 604 сохранения кадра представляет текущий кадр 650 (также показанный как F_n), для прямого участка 605. Кроме того, модуль 604 сохранения кадра представляет собой прямой участок 605 со ссылкой на кадр 652 (также показан на фиг.6, как F′_n-1). Однако, более чем один опорный кадр может быть представлен в качестве альтернативы. Кодер 602 обрабатывает эти кадры в единицах макроблоков, таких как области пикселей изображения, размером 16×16. (Однако, для кодирования с прогнозированием между кадрами, опорные кадры могут быть обработаны в форме областей с переменным размером). Например, на фиг.6 показан макроблок B_n, соответствующий текущему кадру F_n.

Кодер 602 может кодировать каждый из этих блоков в режиме прогнозирования внутри кадра или в режиме прогнозирования между кадрами. В каждом из этих режимов используется блок прогнозирования, который показан как P на фиг.6. Также, для каждого из этих режимов генерирования блок P прогнозирования основан на реконструированном кадре, который используется как опорный.

В режиме прогнозирования внутри кадра модуль 622 формирует блок P_intra прогнозирования из выборок в текущем кадре n, который был ранее кодирован, декодирован и реконструирован. Эти выборки показаны на фиг.6 как uF′_n. Прогнозирование внутри кадра может быть выполнено в соответствии с различными режимами. В соответствии с этим, модуль 618 выбирает один из этих режимов для каждого блока в пределах F_n, На основе этого выбора, модуль 622 прогнозирования внутри кадра генерирует блок P_intra прогнозирования.

В режиме прогнозирования между кадрами, модуль 620 выполняет блок P_inter прогнозирования, путем применения технологий прогнозирования с компенсированным движением из одного или больше опорного кадра (кадров). Например, на фиг.6 показан опорный кадр 652, который был ранее кодирован, и реконструированный кадр F′_n-1. Однако, два или больше кодированных и реконструированных кадра можно использовать как опорные кадры.

В режиме прогнозирования внутри кадра используется модуль 608 оценки движения и модуль 620 компенсации движения. Модуль 608 оценки движения выполняет оценку векторов движения для одного или больше блоков, в пределах текущего кадра F_n. Эти вектора движения основаны на соответствующих блоках, в пределах опорного кадра F′_n-1. В вариантах осуществления модуль 106 оценки движения может быть воплощен таким образом, как описано выше со ссылкой на фиг.4. Однако, как описано выше, модуль 204 сохранения кадра, в качестве альтернативы, может представлять свойства носителя 402 сохранения.

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

Как показано на фиг.6, модуль 624 маршрутизации выбирает либо P_inter или P_intra как блок P прогнозирования. Такой выбор может быть основан на характеристике кадра F_n и одном или больше других кадров. В свою очередь, узел 610 комбинирования вычисляет разность между текущим макроблоком B_n (который находится в пределах текущего кадра F_n), и макроблоком P прогнозирования. В результате этого получается остаточный макроблок D_n или макроблок разности. Модуль 612 прямого преобразования преобразует D_n (используя, например преобразование блока 4×4) в набор коэффициентов преобразования. В свою очередь, эти коэффициенты квантуют с помощью модуля 614 квантования с получением квантованных коэффициентов X. Эти квантованные коэффициенты передают в модуль 616 кодирования, который может изменять порядок и выполнять для них энтропийное кодирование.

В результате модуль 616 кодирования выводит поток 658 сжатой информации для макроблока B_n. В контексте фиг.1, поток 658 сжатой информации может быть включен в кодированный сигнал 124. Поток 658 сжатой информации может включать в себя кодированные коэффициенты, а также вспомогательную информацию для декодирования макроблока. Примеры такой вспомогательной информации могут включать в себя режим прогнозирования макроблока, размер этапа квантования, размер шага квантования, информацию вектора движения, описывающего, как в макроблоке была выполнена компенсация движения и т.д. Поток 658 может быть обработан различными способами. Например, поток 658 информации может быть передан в удаленное устройство и/или сохранен на носителе информации.

Как описано выше, участок 606 реконструирования может включать в себя модуль 620 компенсации движения, модуль 622 прогнозирования внутри кадра, модуль 624 маршрутизации, модуль 626 обратного квантования, модуль 628 обратного преобразования, модуль 630 комбинирования и фильтр 632 деблокирования.

Модуль 626 обратного квантования принимает коэффициенты X квантованного макроблока из модуля 614 квантования и выполняет их повторное масштабирование. Такие коэффициенты после повторного масштабирования передают в модуль 628 обратного преобразования, который выполняет обратное преобразование (например, обратное преобразование блока 4×4) по коэффициенту для получения макроблока Dn′ разности. Dn′ может не быть идентичным оригинальному макроблоку Dn разности. Это связано с искажениями, введенными модулем 614 квантования.

На фиг.6 показано, что макроблок Dn′ разности скомбинирован (например, суммирован) с макроблоком P прогнозирования для получения реконструированного макроблока uB′_n. Такой реконструированный макроблок представляет собой искаженную версию оригинального макроблока. Для уменьшения такого искажения применяют фильтр 632 устранения блоков исходного макроблока. Также, фильтр 632 устранения блоков реконструирует макроблоки в реконструированный кадр 654 (также показанный как F′_n).

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

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

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

Считываемый устройством носитель информации или изделие может содержать, например, любой соответствующий тип запоминающего модуля, запоминающего устройства, запоминающего изделия, носителя - запоминающего устройства, устройства накопителя, изделия накопителя, носителя накопителя и/или модуля накопителя, например, запоминающего устройства, съемного или несъемного накопителя информации, стираемого или нестираемого накопителя информации, накопителя с возможностью записи или с возможностью перезаписи, цифрового или аналогового накопителя, жесткого диска, гибкого диска, запоминающего устройства на компакт-диске (CD-ROM), компакт-диска с возможностью записи (CD-R), компакт-диска с возможностью перезаписи (CD-RW), оптического диска, магнитного носителя, магнитооптического носителя, съемных карт памяти или дисков различных типов цифрового универсального диска (DVD), магнитной ленты, кассеты или тому подобное. Инструкции могут включать в себя любой соответствующий тип кода, такой как код источника, компилированный код, интерпретированный код, исполнительный код, статический код, динамический код, зашифрованный код и т.п., воплощенные с использованием любого соответствующего высокого уровня и низкого уровня объектно-ориентированного, визуального, компилируемого и/или интерпретируемого языка программирования.

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

Например, описанные здесь технологии не ограничены использованием значений SSAD и значений SAD. Например, могут использоваться другие значения нижней границы измеренной ошибки и измеренные ошибки. Также, варианты осуществления не ограничены с использованием макроблоков размером 16×16 или подблоков размером 4×4. Кроме того, в вариантах осуществления могут использоваться различные технологии (кроме, основанных на неравенстве Маркова) для определения порогового значения разделения.

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

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

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

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

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

4. Способ по п.3, в котором множество положений кандидатов включает в себя положение нулевого смещения.

5. Способ по п.3, в котором каждая из измеренных ошибок представляет собой суммы значений абсолютных разностей (SAD).

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

7. Способ по п.6, в котором выбор порогового значения разделения содержит применение двоичного поиска для выбора порогового значения разделения.

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

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

10. Способ по п.6, в котором выбор порогового значения разделения содержит выбор порогового значения разделения таким образом, что количество положений, множества положений кандидатов, близки к требуемому значению.

11. Способ по п.1, дополнительно содержащий кодирование текущего изображения на основе, по меньшей мере, вектора движения.

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

13. Устройство по п.12, в котором каждое из значений нижней границы измеренной ошибки представляет собой сумму подвыборки значений абсолютной разности (SSAD).

14. Устройство по п.12, в котором каждая из измеренной ошибки представляет собой сумму значений абсолютной разности (SSAD).

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

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

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

18. Устройство по п.16, в котором каждая из измеренных ошибок представляет собой сумму значений абсолютных разностей (SAD).

19. Устройство по п.16, в котором модуль расчета вектора дополнительно определяет пороговое значение разделения.

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

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

22. Изделие по п.20, в котором каждое из значений нижней границы измеренной ошибки представляет собой сумму подвыборки значений абсолютной разности (SSAD).

23. Изделие по п.20, в котором каждая из измеренных ошибок представляет собой сумму значений абсолютной разности (SAD).

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