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

Формула изобретения

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

- выполняют начальный расчет четырех векторных полей движения с помощью алгоритма вариационного оптического потока;

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

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

- выполняют ретуширование движения в областях окклюзии.

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

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









где - область изображения, E - минимизируемая энергия, u(x)=(u ₁(x), u₂(x)) - поле движения, w(x) - поле, связанное с изменением освещенности, ^L и ^C - параметры, регулирующие значимость пикселя данных для яркостного и цветового каналов соответственно, и - параметр, управляющий регуляризацией изменения освещенности, E_s - энергия гладкости, которая возрастает при локальном изменении u и w, ^LI₁, ^LI ₂ - это компоненты яркости текущего и последующего кадров соответственно, ^CI₁, ^CI ₂ - цветовые компоненты текущего и последующего кадров соответственно.

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

(n)= _coarsest, n>n_ramp



где n - уровень пирамиды (нулевое значение n означает самый точный уровень и, следовательно, самую высокую разрешающую способность), - параметр регуляризации как функция от n, n_ramp яляется начальной точкой линейной пилообразной функции; а параметры _coarsest и _finest определяют начальное и конечное значение .

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



где s (I₁(x), x, dx) - ненормализованные нелокальные веса, k_c - параметр, который управляет характером нелокальных весов, I₁ (х) - изображение текущего кадра, х - вектор координат текущего пикселя изображения, x+dx - определяет координаты пикселя из локального окружения.

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

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



где u₂₃ - движение из текущего кадра в последующий кадр, u₃₂ - обратное движение, и - порог для детекции окклюзии.

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

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

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

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

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

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

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

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

- выполняют ретуширование кластера.

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



где - область изображения, u₂₃ (х), и u₂₁ (х) - векторные поля движения, М( , х) - движение, предсказанное моделью с параметрами в точке х изображения, и k - параметр, который взвешивает дисперсию несовпадения, J - функция оценки.

16. Способ по п.14, отличающийся тем, что упомянутое ретуширование кластера включает в себя:

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

назначение номера кластера согласно следующему уравнению:



где - область локального окружения; I₁ (х, y) - пиксель текущего изображения с координатами х, y; С (х, y) - индекс кластера пикселя с координатами х, y; W_x,y(k) - вес кластера k для пикселя с координатами х, y; - параметр, управляющий значимостью цветового подобия текущего и соседнего пикселей.

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

- осуществляют выбор загороженных и кластеризованных пикселей;

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

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

Описание изобретения к патенту

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

Термин «окклюзия» применяется в ситуации, когда один объект загораживает другой объект. В случаях окклюзии становится затруднительно отличить один объект от другого. Оптический поток представляет собой видимое движение яркостных образов в сцене изображения. Алгоритмы, которые обычно используются для вычисления оптического потока для последовательности изображений, являются полезными для применения в различных приложениях, включая преобразование 2D видео в 3D. Робастные вариационные подходы показали наиболее точные результаты при решении проблемы оптического потока. Алгоритмы расчета движения оптического потока страдают, главным образом, от трех основных проблем: нетекстурированные области, окклюзии и мелкие объекты.

Из уровня техники известны и другие подходы к решению проблемы окклюзии, в частности, в работе Werlberger, Pock, Bischof, "Motion Estimation with Non-Local Total Variation Regularization" [1] предложена унифицированная вариационная схема для решения данной проблемы. Этот способ основан на нелокальной полной регуляризации, которая позволила встроить процесс низкоуровневой сегментации в вариационную модель. Вопреки наиболее распространенным подходам, которые исходят из концепции постоянства линеаризованной яркости (часто называемого уравнением оптического потока), в данной работе предлагается использовать разложение в ряд Тэйлора второго порядка элемента данных, что позволяет использовать более сложные элементы данных, такие как нормализованная взаимная корреляция.

В работе A.Chambolle, Т.Pock A first-order primal-dual algorithm for convex problems with applications to imaging [2] предложен прямо двойственный алгоритм первого порядка для метода выпуклой оптимизации с приложениями по расчету движения оптического потока. Этот алгоритм сходится с показателем 0(1/N) для прямо двойственной задачи разрыва. Этот показатель сходимости является оптимальным для проблем выпуклой оптимизации с известной схемой. Предложенный алгоритм может быть изменен для получения показателя конвергенции 0(1/N² ) для проблем, у которых наблюдается некоторая регулярность в первичной или в двойственной цели, и является линейно сходящимся (0(1/e^N) для проблем сглаживания. Прямо двойственный алгоритм может быть достаточно просто адаптирован к расчету движения оптического потока, он прост в применении и может быть эффективно ускорен на оборудовании с параллельным выполнением инструкций, в частности, на графических процессорах (GPUs).

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

Американский патент US 7522749 [3] описывает технику расчета оптического потока между изображениями конкретной сцены с сегментацией изображений. Это предусматривает, в первую очередь, определение начальной сегментации изображений и расчет начального оптического потока для каждого сегмента каждого изображения и его соседнего изображения или изображений. Уточненный расчет оптического потока выполняют для каждого сегмента каждого изображения из исходной сегментации данного изображения и исходного оптического потока сегментов данного изображения. Затем сегментацию каждого изображения уточняют на основе последнего из предыдущих расчетов оптического потока для каждого сегмента этого изображения. Этот процесс может продолжиться в повторяющемся режиме дальнейшего уточнения расчетов оптического потока для изображений, используя их соответствующие последние расчеты оптического потока, до тех пор, пока заданное число итераций не будет выполнено.

Американский патент US 7043058 [4] утверждает, что видимые артефакты в изображениях, созданные путем обработки изображения на основе векторных карт движения, могут быть минимизированы путем применения одного или нескольких способов коррекции векторной карты. Вообще, набор векторов движения изменяется путем выбора одной или более частей изображения. Векторы, соответствующие одной или более отобранных частей, модифицируются. Различные операции по обработке изображения, такие как интерполяция с компенсированным движением, могут быть выполнены с использованием измененного набора векторов движения.

Американская патентная заявка US 20060228002 [5] описывает способ расчета оптического потока между изображениями сцены и сегментацией изображений. Этот способ предусматривает, в первую очередь, расчет исходной сегментации изображений, и расчет исходного оптического потока для каждого сегмента каждого изображения и его соседнего изображения или изображений. Уточненный расчет оптического потока вычисляется для каждого сегмента каждого изображения из исходной сегментации данного изображения и исходного оптического потока сегментов данного изображения. Затем сегментация каждого изображения уточняется на основе последнего из предыдущих расчетов оптического потока для каждого сегмента этого изображения. Этот процесс может продолжаться в режиме итераций путем дальнейшего уточнения расчетов оптического потока для изображений на основе соответствующих последних расчетов сегментации с последующим уточненным расчетом сегментации каждого изображения, используя их соответствующие последние расчеты оптического потока до тех пор, пока заданное число повторений не будет выполнено.

Американская патентная заявка US 20100124361 [6] описывает способ и систему для определения области оптического потока между парой изображений. Каждая пара изображений разбивается на пирамиды изображений путем использования «фактора неоктавной пирамиды». Пару разбитых таким образом изображений преобразуют в масштабе первой пирамиды в представления второй производной, исходя из предположения, что градиент яркости пикселей в паре разбитых изображений является константой. Осуществляют расчет дискретных производных представлений вторых производных изображения. Процедуру расчета оптического потока применяют к дискретным производным для получения области необработанного оптического потока. Область необработанного оптического потока масштабируется «фактором неоктавной пирамиды». Вышеназванные шаги повторяются в отношении пары изображений при другом масштабе пирамиды до тех пор, пока все масштабы пирамиды не будут охвачены для получения области окончательного оптического потока, причем расчеты пространственно-временного градиента деформируются предыдущим расчетом необработанного оптического потока.

Американский патент US 7142600 [7] описывает способ, при котором объект в видеопоследовательности отслеживается масками объекта, сгенерированными для кадров, принадлежащих данной последовательности. Большие различия между текущим кадром и следующим кадром свидетельствуют о наличии подозрительных областей, которые могут быть затенены в следующем кадре. Векторы движения в объекте сгруппированы, используя алгоритм K-средних. Векторы движения средней точки кластера сравниваются со средним вектором движения каждой подозрительной области. Когда различия движения являются маленькими, подозрительную область считают частью объекта и удаляют от маски объекта как окклюзию. Большие различия между предшествующим кадром и текущим кадром означают наличие подозрительных недавно обнаруженных областей. Средний вектор движения каждой подозрительной области сравнивается с векторами движения средней точки кластера. Если различия движения являются маленькими, эта подозрительная область добавляется к маске объекта в качестве дисокклюзии.

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

окклюзии;

избыточное сглаживание;

неопределенность в нетекстурированных областях (проблема апертуры);

временная (темпоральная) несогласованность.

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

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

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

- выполняют начальный расчет четырех векторных полей движения с помощью алгоритма вариационного оптического потока;

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

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

- выполняют ретуширование движения в областях окклюзии.

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

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

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

E(x, u(x)),w(x)= _x ^L ·^LE_D(x, u(x))·w(x)+c ·^CE_D(x, u(x))+E_S ,

;

где - область изображения, Е - минимизируемая энергия, u(x)=(u ₁(x), u₂(x)) - поле движения, w(x) - поле, связанное с изменением освещенности, ^L и ^C - параметры, регулирующие значимость пиксела данных для яркостного и цветового каналов соответственно, и - параметр, управляяющий регуляризацией изменения освещенности. E_s -энергия гладкости, которая возрастает при локальном изменении u и w, ^LI₁, ^LI ₂ - это компоненты яркости текущего и последующего кадров соответственно, ^CI₁, ^CI ₂ - цветовые компоненты текущего и последующего кадров соответственно.

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

(n)= _coarsest, n>n_ramp

, n n_ramp

где n - уровень пирамиды (нулевое значение n означает самый точный уровень и, следовательно, самую высокую разрешающую способность), - параметр регуляризации как функция от n, n_ramp яляется начальной точкой линейной пилообразной функции. Параметры _coarsest и _finest определяют начальное и конечное значение .

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

;

где s (I₁(x), x, dx) - ненормализованные нелокальные веса, k_c - параметр, который управляет характером нелокальных весов, I₁ (x) - изображение текущего кадра, x - вектор координат текущего пикселя изображения, x+dx - определяет координаты пикселя из локального окружения.

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

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

где u₂₃ - движение из текущего кадра в последующий кадр, u₃₂ - обратное движение, и - порог для детекции окклюзии.

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

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

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

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

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

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

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

обнаружение подмножества пикселей, подходящих заданной аффинной модели, при помощи модифицированного стабильного метода оценки параметров модели на основе случайных выборок (метода RANSAC см. http://www.ai.sri.com/pubs/files/836.pdf) [9] с использованием векторных полей прямого движения, векторных полей обратного движения, карты окклюзии прямого движения и карты окклюзии обратного движения;

ретуширование кластера.

Согласно заявленному изобретению с помощью упомянутого адаптивного способа RANSAC оценивают несовпадение модели движения в соответствии со следующим уравнением:

где - область изображения, u₂₃(x) и u₂₁ (x) - векторные поля движения, М( , x) - движение, предсказанное моделью с параметрами 9 в точке x изображения, и k - параметр, который взвешивает дисперсию несовпадения, J - функция оценки.

Согласно заявленному изобретению упомянутое ретуширование кластера включает в себя:

выбор векторов движения, не принадлежащих какому-либо кластеру;

назначение номера кластера согласно следующему уравнению:

C(x,y)=argmax(W_x,y(k);

где - область локального окружения; I₁(x,y) - пиксель текущего изображения с координатами x, y; C(x,y) - индекс кластера пикселя с координатами x, y; W_x,y(k) - вес кластера k для пикселя с координатами x, y; - параметр, управляющий значимостью цветового подобия текущего и соседнего пикселей.

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

выбор загороженных и кластеризованных пикселей,

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

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

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

- изобретение обеспечивает преобразование двумерного видео в трехмерное (2D в 3D);

- применена пересегментация движения, основанная на расчете аффинных моделей вместо сегментации, основанной на интенсивности;

- сегментация движения выполняется путем анализа прямого и обратного движения и окклюзии;

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

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

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

Фиг.1 описывает основные шаги для расчета движения и исправления окклюзии.

Фиг.2 описывает поток информации согласно изобретению. Фиг.3 Демонстрирует схему расчета пирамиды оптического потока.

Фиг.4 иллюстрирует связь незаполненных участков (дыр) движения с окклюзиями.

Фиг.5 описывает шаги заявляемого алгоритма (избыточной) кластеризации движения.

Фиг.6 описывает основные шаги ретуширования окклюзии.

Фиг.7 объясняет подробно шаг 601, касающийся ретуширования прямого и обратного движения.

Фиг.8 - пример, поясняющий, как работает заявляемое изобретение.

Заявляемое изобретение может быть представлено последовательностью шагов, необходимых для формирования карты движения с исправленными окклюзиями. На Фиг.1 представлена блок-схема функционирования способа согласно заявляемому изобретению. Фиг.2 демонстрирует поток данных, соответствующий алгоритму по Фиг.1. Начальный этап способа состоит в выполнении расчета движения с помощью вариационного алгоритма оптического потока (101, 204, 205), который использует три кадра, а именно, текущий кадр 202, предыдущий кадр 201 и следующий кадр 203 для расчета четырех векторных полей движения: прямого движения («вперед») от предыдущего к текущему кадру 206, обратного движения («назад») от текущего кадра к предыдущему кадру 207, прямого движения от текущего кадра к следующему кадру 208 и обратного движения от следующего кадра к текущему кадру 209.

На следующем шаге 102 алгоритм детекции окклюзии 210, 211 формирует карты 213 окклюзии для прямого движения и карты 212 для обратного движения. Используя вычисленные карты окклюзии, данные о текущем кадре, о прямом и обратном движении, выполняется кластеризация 103, 214 на основе объединенной аффинной модели движения «вперед-назад». Результатом этих шагов являются карта сегментации для текущего кадра 216 и расчитанные аффинные модели для каждого из сегментов 217. Число сегментов определяется автоматически и имеет тенденцию к формированию пересегментированной карты движения.

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

Далее приводится более детальное описание каждого шага, представленного на Фиг.1.

Расчет оптического потока. Вариационный подход используется для начального двухкадрового оптического потока. Этот подход оптимизирует функционал, который взвешивает ошибку значений спроецированного пикселя изображения и гладкость полученной области движения. Задача вариационной минимизации имеет вид (1) и решается на нескольких дискретных сетках согласно пирамидальной схеме, приведенной на Фиг.3. Выражение E_D ограничивает ошибку соответствия данных изображения из изображения I₁ 301 в изображение I₂ 302. Выражение E_S ограничивает ошибку негладкости решения.

Результаты, а также стабильность решения (1) в высшей степени зависят от выбора функции ошибки и ее параметров. Заявляемый вариант реализации изобретения предусматривает оптимизацию двух различных вариационных формулировок оптического потока, которые описаны ниже. Схема пирамиды на входе имеет изображения 201 и 202. Блок 203 выполняет цветовое преобразование в цветовое пространство Y'CbCr. Цветовое пространство Y'CbCr отделяет канал яркости от каналов цветности и делает каналы более статистически независимыми. Преобразование Y'CbCr описано в ITU R Recommendation ВТ 601 [10] и широко используется в сжатии видеосигналов (например, MPEG).

где - область изображения, x=(x₁, x₂ ) - координаты, I₁(x) и I₂(x) - изображения, и (x)=(u₁(x), u₂(x)) - рассчитанное поле векторов движения, и - параметр регуляризации, который управляет компромиссом между гладкостью и (x) и условием постоянства яркости.

Структура пирамиды, которая создается на шаге 304, является обычным подходом компьютерного зрения к решению проблемы различного масштабирования элементов в изображениях. В описанном варианте реализации сформированы пирамиды 305 и 306. Пирамидой для одного входящего изображения является набор изображений с уменьшающейся разрешающей способностью. Решающими параметрами при создании пирамиды являются разрешающая способность самого высокого уровня, межуровневый коэффициент уменьшения разрешения, число уровней и способ изменения размеров вместе с параметрами сглаживания или устранения контурных неровностей. Центральным блоком при расчете оптического потока является блок 308, который представляет собой итеративный алгоритм для решения задачи оптического потока, сформулированной в общем виде в (1) на единственном уровне разрешающей способности. На шаге 309 найденное поле движения преобразуется в более высокое разрешение, а найденные векторы умножаются на межуровневый коэффициент изменения разрешения. Способ билинеарного изменения размеров используется для того, чтобы изменить размер кадра между уровнями, поскольку он имеет сглаживающие свойства. После решения этой задачи получают поле 310 векторов движения оптического потока с самым высоким уровнем. Чтобы получить более высокое качество поля движения на верхнем уровне, параметр регуляризации изменяется между уровнями пирамиды. На более грубых уровнях предпочтение отдается выявлению очевидного движения на входящих изображениях, несмотря на более зашумленные векторы движения. С другой стороны, применение способа расчета движения требует наличия областей гладкого движения для успешного преобразования 2D в 3D. Следовательно, векторы движения должны быть сглажены на более высоких уровнях с изменением параметра как функции уровня пирамиды. Изменение параметра должно быть постепенным, чтобы не создавать слишком больших нестабильностей в численном решении уравнения (1). Приемлемая форма (n) представлена как (2), и приемлемые результаты получаются, если _coarsest в 2-3 раза превышает _finest и n_ramp определяет уровень, который составляет от 1/2 до 1/3 наибольшего разрешения.

(n)= _coarsest, n>n_ramp

, n n_ramp

;

E(x, u(x)),w(x)= _x ^L ·^LE_D(x, u(x))·w(x)+c ·^CE_D(x, u(x))+E_S ,

;

(n)= _coarsest, n>n_ramp

, n n_ramp

(n)= _coarsest, n>n_ramp

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

Алгоритм полного вариационного оптического потока на основе использования двух цветовых каналов. Более простой, но более быстрый алгоритм оптического потока основан на регуляризации с 5 использованием ограничительных условий для оптического потока и дискретной полной вариации. Точная формула приведена в (3). В качестве компромисса между точностью и длительностью вычисления используются два цветовых канала (Y' и Cr из цветового пространства Y'CbCr) вместо трех.

где - область отображения, Е - минимизируемая энергия, и (x)=(u ₁(x), u₂(x)) - поле движения, w(x) - поле, связанное с изменением освещенности, ^L и ^C - параметры, регулирующие значимость пиксела данных для яркостного и цветового каналов соответственно, и - параметр регуляризации изменения освещенности. E _s - энергия гладкости, которая увеличивается при локальных изменениях u и w, ^LI₁, ^LI ₂ - это компоненты яркости текущего и последующего кадров соответственно, ^CI₁, ^CI ₂ - цветовой компонент текущего и последующего кадров соответственно.

Оптимизация для (3) выполняется с использованием алгоритма чередующихся направлений, описанного в [2].

Алгоритм полного вариационного оптического потока, основанный на использовании двух цветовых каналов с элементом нелокальной гладкости. Более совершенный алгоритм оптического потока использует то же самое ограничение оптического потока, как ранее описанный, отличие состоит в элементе гладкости, который использует нелокальные веса для повышения четкости границ движения в полученном поле движения. Формула для энергии является такой же, как и (1), за исключением компоненты Eg, которая приведена как (4).

где - окружение нелокального элемента (например, квадрат 5х5 с (0,0) в середине), s(I₁(x), x, dx), и s_n (I₁, x, dx) являются соответственно ненормализованным и нормализованным нелокальными весами, k_s, и k _c - параметры, которые управляют характером нелокальных весов.

Особый способ взвешивания для быстрого вычисления нелокального оптического потока. В первоначальной формулировке нелокального элемента гладкости, описанного в (4), размер локального окна определяет число весов и двойственных переменных на каждый пиксель изображения. Таким образом, например, если размер окна 5×5, то для каждого пикселя изображения в памяти должны храниться 25 двойственных переменных и 25 весов. Учитывая, что все эти переменные используются в каждой итерации оптимизации оптического потока, необходим большой объем памяти и вычислительных ресурсов. Это особенно замедляет вычисления в случае реализации на архитектурах SIMD с относительно малой пропускной способностью по памяти. Для решения этой проблемы заявляемый вариант реализации изобретения предусматривает применение особой техники вычисления нелокальных весов, которая описана в следующем уравнении:

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

Детекция окклюзии. Результат оптического потока является неточным в тех областях, которые закрыты объектами переднего плана сцены, или в пикселях изображения, которые выходят за кадр изображения. В принципе, не представляется возможным определить правильное движение таких пикселей, потому что они видны только на одном изображении. Желательно идентифицировать такие области окклюзии. В заявляемом изобретении процедура детекции окклюзии основана на предположении о том, что движение незагороженных пикселей из Кадра 3 в Кадр 2 согласно схеме из Фиг.2 позволяет идентифицировать, какие области покрыты видимыми пикселями из Кадра 3. Все области, которые не покрыты, называются незаполненными местами (дырами) движения и считаются окклюзиями. Однако не известно, какие пиксели загорожены движением от Кадра 3 в Кадр 2. Неправильное движение пикселей окклюзии может заполнить область окклюзии в Кадре 2. Для устранения случайного перекрытия пикселей из окклюзии используется описанная ниже проверка «вперед-назад».

Для вычисления «дыр» движения импользуют обратное билинейное преобразование, основанное на субпиксельном поле движения из Кадра 3 в Кадр 2. Сумма билинейных коэффициентов для пикселя из Кадра 2 сопоставляется с пороговым значением. Упрощенное одномерное объяснение выявления окклюзии для трех кадров приведено на Фиг.4. Объект 401 движется из Кадра 1 405 через Кадр 2 406 в Кадр 3 407. Векторы движения 402 формируют билинейные (для одномерного линейного случая) коэффициенты 403, которые суммируются и сравниваются с пороговым значением. Выявленные окклюзии отмечено крестиками 404.

Проверка «вперед-назад» основана на факте, что следуя движению из Кадра 2 в Кадр 3 с последующим обратным движением из Кадра 3 в Кадр 2, должен произойти возврат к исходной позиции, как описано неравенством (6). Этот подход хорошо коррелируется с результатами «дыр» движения, но из-за необходимости обеспечивать соответствие между прямым и обратным полями движения, он является более чувствительным к ошибкам получаемого оптического потока.

где u₂₃ - движение из Кадра 2 в Кадр 3, u₃₂ - движение из Кадра 3 в Кадр 2, и - порог для детекции окклюзии.

Оба шага детекции окклюзии в поступательном движении из Кадра 2 в Кадр 3 легко применимы к детекции обратных окклюзии из Кадра 2 в Кадр 1.

Кластеризация движения. Цель кластеризации движения состоит в том, чтобы распознать области изображения, которые движутся совместно. В заявляемом изобретении применяют совместную кластеризацию прямого и обратного движения в трехкадровой схеме, представленной на Фиг.2. Между Кадрами 201, 202, 203 вычисляют четыре поля векторов движения 206, 207, 208 и 209 с использованием вариационного оптического потока. На основе четырех полей движения выполняют расчет прямых 213 и обратных 213 окклюзии. Согласно Фиг.5 сначала, используя модифицированный метод RANSAC (стабильный метод оценки параметров модели на основе случайных выборок) 502, идентифицируют области со стабильным прямым и обратным движением. Модель подобия, описанная как (7), используется для идентификации кластеров движения. Это является существенным для решения проблемы окклюзии. Концепция такого подхода основывается на том факте, что окклюзия, проявляющаяся при движении в одном направлении, обычно не проявляется при обратном движении. Область кластера, где взаимное соответствие движения сохраняется, распространяется в области окклюзии, если направление движения в области окклюзии соответствует 503. Области, отмеченные как окклюзии в обоих направлениях движения, не кластеризуются, однако возможно частично решить эту проблему посредством ретуширования кластеризации, основанного на информации от цветного изображения.

где u₁, u₂ - векторы движения, x₁, x₂ - координаты исходной точки, t₁, t₂ - смещение, R - ортонормаль матрицы поворота 2×2, и s - коэффициент масштабирования.

Алгоритм RANSAC [9] - это недетерминированный метод подгонки модели, заключающийся в том, что случайно выбирается минимальное множество точек, которые определяют модель, и рассчитывается, сколько точек действительно соответствует данной модели. Для того, чтобы обнаружить точки-погрешности, алгоритм использует некоторый порог ошибки. Заявляемое изобретение предназначено для видео материала общего характера. В этом случае не представляется возможным установить единственный порог. Для решения данной задачи в описываемом варианте реализации используется особый вид RANSAC. Сначала, в соответствии с заявляемым способом, оценивают модели прямого и обратного движения путем суммирования функций Гаусса от ошибок соответствия модели, как показано в (8). Для этой оценки необходим также параметр k, который играет роль предпочтительной дисперсии. Однако вполне приемлемые результаты получаются даже в случае, когда у всех кластеров дисперсия избыточная. После проведения оценки, производят анализ гистограммы несовпадения для того, чтобы найти первую моду несоответствия. Поиск первого локального минимума производят в сглаженной гистограмме, потому что первые локальные минимумы в несглаженной гистограмме слишком чувствительны к шуму. Пиксели, имеющие ошибку соответствия ниже чем трехкратное стандартное отклонение первой моды, считаются пикселями, принадлежащими одному кластеру.

где - область отображения, u₂₃(x), и u₂₁ (x) - поля движения, М( , x) - движение, предсказанное моделью с параметрами в точке x изображения, и k - параметр, который взвешивает дисперсию несоответствия, J - функция оценки, более высокие значения обозначают лучшего кандидата.

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

где - область локального окружения; I₁(x,y) - пиксель текущего изображения с координатами x, y; C(x, y) - индекс кластера пикселя с координатами x, y; W_x,y(k) - вес кластера k для пикселя с координатами x, y; - параметр, управляющий значимостью цветового подобия текущего и соседнего пикселей.

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

Ретуширование окклюзии. Последний шаг называется ретушированием окклюзии и предназначен для получения конечных карт движения с исправленными окклюзиями. Фиг.6 объясняет подробности шага 104, который, в свою очередь, состоит из двух шагов: ретуширование прямого и обратного движения 601 и билатеральная фильтрация движения 602. Результатом функционирования блоков 101-103 являются: карты движения, карты окклюзии, карта кластера и оценки аффинных моделей. Расчетное движение в обнаруженных областях окклюзии содержит неправильные векторы, которые надлежит заменить более подходящими векторами движения. В рассматриваемом варианте реализации изобретения замена векторов движения в областях окклюзии более подходящими осуществляется путем ретуширования движения. Для ретуширования движения могут использоваться различные подходы. Подход, используемый в заявляемом изобретении, представлен на Фиг.7. Этот подход заключается в том, что выполняют сканирование всех векторов прямого движения 208, чтобы проверить, принадлежит ли вектор движения области окклюзии (701) путем использования карты окклюзии 213, затем проверяют, принадлежит ли вектор движения некоторому сегменту на карте сегментации 216. Если вектор движения не загорожен или загорожен, но не принадлежит какому-либо сегменту, то его оставляют без изменений. Если вектор движения загорожен и принадлежит какому-то сегменту, то он заменяется другим вектором движения, вычисленным путем интерполяции движения сегмента с помощью аффинной модели 215. Последовательность тех же шагов применяется для карты обратного движения 207.

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

Фиг.8 иллюстрирует функционирование изобретения на примере. На основе трех входных кадров 801, 802, 803 вычисляют начальные прямое (805) и обратное (804) векторные поля движения. Как можно увидеть, прямое поле движения имеет большую область окклюзии. На основе начальных карт движения, вычисляют карты сегментации 807, карты окклюзии прямого движения 806 и карты окклюзии обратного движения 808. На основе карт окклюзии и сегментации формируют новые карты движения 809, 810 с исправленными окклюзиями.

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