MOTION ESTIMATION BASED ON A TENSOR APPROACH

Abstract

The author considers the approach to motion estimation using a pointed tensor and present an algorithm for construction of optical flow. The software for the experimental studies is developed.

Full Text

Информация о движении в видеопоследовательности может быть использована в разных областях: сжатия видео, в системах видеонаблюдения, при реализации интерфейса между человеком и компьютером, в системах анализа дорожного трафика и т. д. В данной статье будет рассматриваться метод оценки движения, основанный на тензорном подходе. 0 0 0 36 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Анализ последовательных кадров приводит к пространственно-временному набору изображений с двумя пространственными и одним временным измерением. При движении в видеопоследовательности структуры с определенной ориентацией в наборе кадров происходит ее трансформация. Например, точка в линию, направление которой напрямую связано с ее смещением. Мощным инструментом представления локальной ориентации является ориентированный тензор. Тензорный подход относится к методам, основанным на уравнении оптического потока - стандартном уравнении в частных производных, используемом в физике для описания процессов переноса различных сред: и получим dtF + v-VF = S . (1) 2 e(v) = | w(х — х') [Vgrv] йх'. (3) a = | w(х — х' )айх'. (4) є(v) = ^VgTv]^ = (vTVgVgTv). (5) Из предположения, что скорость v постоянна в окрестности м>(х - х'), следует, что значение v можно вынести из-под знака интеграла: є = v v = vT Jv, (6) где dtF - производная по времени; VF - пространственный градиент функции. В уравнении (1) под переносимой средой понимается яркость изображения F, а член S в правой части моделирует источник, определяющий изменения яркости, не сводимые лишь к пространственному движению. Задача состоит в определении поля векторов движения (1) на основе знания о сигнале яркости в двух соседних кадрах. Например, за вектор движения можно принять вектор, минимизирующий правую часть уравнения (1) по всей площади макроблока. Если представить вычисления в матричном виде, то для вычисления векторов движения можно использовать тензорную алгебру. При тензорном подходе последовательность кадров представляется в виде единой трехмерной структуре [1-3]. Смещение значения интенсивности этой структуры внутри последовательности изображений дает структуру, которая направлена вдоль временной оси пространственно-временного объемного изображения. Запишем уравнение оптического потока в векторной форме [4]: VgT v = 0, (2) где Vg - пространственно-временной градиент функции интенсивности; v = (Д хь А х2, At)T - смещение интенсивности во времени, от кадра к кадру. Из выражения (2) следует, что градиент Vg ортогонален вектору смещения v. Введем функцию стоимости, определенную для окрестности м>(х - х') с центром в точке x, для которой ищется вектор смещения и в которой он постоянен: где J - произведение пространственно-временного градиента самого на себя, представляющее симметричный трехмерный структурный тензор: (gxgx) {gxgy) {gxgt) {gxgy) {gygy) {gygt) . (7) _(gxgt) {gygt) {gtgt) _ Элементы J определяются как ю Jpq = (gpgq) = I w(х — х''gpgqйх', (8) —ю где gp, p є {х, y, t}, определяет частную производную по координате p. Исходя из ограничения ||v|| = 1, воспользуемся методом Лагранжа и минимизируем составленную функцию L(v,X): T T (9) L(v, X) = vT Jv + X(1 — vT v). Параметр Лагранжа X выбирается таким образом, чтобы все производные L(v, X) по всем трем координатам v были равны нулю: SL(v,X) dv. ■ = 2^ Jlkvk — 2Xv, = 0, i є {1,2,3}. (10) Представим уравнение в виде линейной системы уравнений Jv = Xv. (11) Таким образом, задача минимизации сводится к задаче поиска собственных значений симметричной матрицы J. После минимизации формула (6) принимает вид T T (12) є = vT Jv = vT Xv = X, Для решения задачи поиска оптического потока необходимо найти такой вектор v, который минимизирует функцию стоимости є(у), и наложить ограничение ||v|| = 1 для исключения нулевых значений вектора v. Сделаем следующую замену: который показывает, что минимум є определяется собственным вектором матрицы тензора J, соответствующим минимальному собственному значению X. Вначале необходимо построить тензор по формуле (7), элементы которого вычисляются по формуле (8). Для практического применения интеграл заменяют на взвешенную или простую сумму, например для окрестности (2W + 1)x(2wy + 1) точки x = (х, y, t)T: i=х+ wx j=y+Wy = Z X ®ijgpgq. (13) i=х—W j = y — Wy Здесь gp, p є {х, y, t}, задает частную производную по координате p, ra,j- - вес соответствующей точки. Пространственные производные по х и y для точки x определяются соответствующими операторами Собела, k 37 Математика, механика, информатика Шарра или другими. Временная производная является разностью между текущим и следующим значениями интенсивности в точке x: = Л(х y'— It—1( х y'. (14) v= (16) структуры перемещается на расстояние между каждым кадром, равное в 3D v = Структурный тензор содержит внутреннюю информацию о распределении яркости в пределах локальной пространственно-временной окрестности. В трехмерной пространственно-временной структуре путем анализа ранга структурного тензора, который получается из числа ненулевых собственных значений, могут быть выделены и определены четыре различных класса [5]. Первый класс - это класс постоянной яркости. В этом случае ранг (J) = 0 и все собственные значения вектора смещения, т. е. все частные производные вдоль главных осей, равны нулю: X1 = X2 = X3 = 0. Таким образом, распределение яркости остается постоянным в U, и нет движения, которое мы можем оценить. Этот класс можно отличить по сумме всех собственных значений, которая равна следу J0: 3 trace(J ') = trace(J) = X J pp, i где trace (J) - след структурного тензора, который можно обнаружить, сравнивая его с порогом: trace(J) < t, (15) перед нахождением собственных значений. Для этих точек поиск собственных значений может быть полностью пропущен, а порог t выбирается исходя из уровня шума видеопоследовательности. Второй класс возникает, если ранг (J) = 1 и структуры изображения имеют пространственную ориентацию и движутся с постоянной скоростью. Если пространственно-временная структура проста, т. е. направлена вдоль одной линии и только одно из собственных значений больше нуля: X1 > 0, X2 = X3 = 0, то возникает проблема апертуры, которая заключается в следующем. Если движущаяся линейная структура наблюдается через небольшое отверстие, то единственное смещение, которое может быть определено, является компонентой, перпендикулярной к структуре (рис. 1). Окрестности, помеченные как P, содержат изображения простых локальных структур и для них можно оценить только нормаль смещения. Окрестности же, обозначенные как L, не являются простыми и для них можно определить истинное смещение. Теперь вычислим нормаль движения к линейной структуре. Для этого рассмотрим локальную линейную структуру, движущуюся с компонентой смещения V1 У (17) Рис. 1. Проблема апертуры при оценке движения Вектор v называют пространственно-временным вектором смещения. Этот вектор находится в постоянной трехмерной плоскости, которая появилась при движении линейной структуры, т. е. v является собственным вектором ориентированного тензора и его собственное значение равно 0. Поскольку сигнал в этом случае является локально простым, то соответствующий ориентированный тензор имеет ранг 1. Если X1 является наибольшим собственным значением соответствующего нормализованного собственного вектора Єї = то можно считать, что e1 и v перпендикулярны: V^1 + V2X2 + хэ = 0. (18) В связи с проблемой апертуры это будет единственным вариантом представления вектора смещения v. С другой стороны, если e1 спроецировать на пространственные измерения, то тогда результирующий вектор n будет иметь вид х х и являться вектором-нормалью к двумерной линейной структуре сигнала. Следовательно, вектор m 1 — х2 по двумерному изображению. Если смещение происходит в единицу времени на каждый кадр в последовательности, то это означает, что любая точка линейной перпендикулярный к вектору n, указывает направление вдоль двумерной линейной структуры. Если вектор v представлен нормалью к смещению, то это означает, что векторы m и v перпендикулярны: T v m = V^2 - V2Xl. (19) n 38 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Комбинируя формулы (18) и (19), получим (20) V V2 У х1 + х2 V х2 У Отметим, что для нахождения оценки смещения здесь нужно не истинное смещение линейной структуры, а нормаль к компоненте истинной скорости. Третий класс определяется для ранга (J) = 2. В этом случае структура пространственного распределения яркости движется с постоянной скоростью и проблемы апертуры не возникает. Пространственновременная окрестность состоит из вытянутой структуры, в которой только один собственный вектор имеет нулевое собственное значение: Xi, X2 > 0, X3 = 0. Как и в случае движения линейной структуры, вектор смещения v может быть выведен вместе с соответствующим пространственно-временным вектором смещения v' по формулам (16) и (17). В этом случае есть два перпендикулярных собственных вектора е1 и e2, оба с ненулевыми собственными значениями. Очевидно, что v перпендикулярен e1 и e2: v ю е3 = х Vа 2 У Следовательно, вектор смещения v определяется как 1 v= (21) Vа 2 У Это смещение оценивает истинное смещение точки. Четвертый класс возникает при ранге (J) = 3, когда тензор не представляет очевидного линейного движения, структура яркости показывает изменения во всех направлениях и все собственные значения вектора смещения больше нуля: X1, X2, X3 > 0, т. е. в этом случае вектор движения определить нельзя. Для отнесения тензора к определенному классу при X1 > X2 > X3 > 0 можно использовать следующие метрики [6]: - trace( J) < t - для первого класса; Xi — X 2 - Со = X1 X 2 — X 3 X1 - для второго класса; - для третьего класса; X1 - для четвертого класса. Отметим, что 0 < ck < 1 и с1 + с2 + с3 = 1. Эти метрики могут быть использованы для классификации трехмерного ориентированного тензора. В большинстве практических реализаций, однако, нулевой класс необходим для тех случаев, когда разница между самым большим и вторым по величине значением является слишком малой. Общий подход к оценке локального смещения на двумерном изображении можно сформулировать следующим образом: а) последовательность изображений рассматривается как трехмерный сигнал и для каждой локальной пространственно-временной окрестности оцениваются структуры, соответствующие трехмерному ориентированному тензору; б) тензор относится к одному из четырех классов; — если тензор отнесен ко второму классу, то вычисляется соответствующая нормаль движения; — если тензор отнесен к третьему классу, то вычисляется соответствующий вектор движения; — если тензор отнесен к первому или четвертому классу, то вектор смещения принимается равным нулю. Для реализации данного алгоритма было создано программное обеспечение (ПО), в котором алгоритмы оценки были реализованы на языке программирования С++, а интерфейс - на языке программирования C#. Это ПО позволяет загружать видеофайлы или последовательности изображений и выделять движущиеся объекты и строить для них оптический поток. Оптический поток, построенный на нескольких кадрах, был визуализирован в виде векторов (рис. 2). Рис. 2. Оптический поток объекта на кадрах с 2 по 30 с шагом 2 X 3 С 3 х 3 39 Математика, механика, информатика 200 <"Э CL £ ec 550 И e; ^00 о s > о LO 0 0 -Тензорный подход ■Метод Лукаса-Канаде 50 100 150 250 Кадрь^00 Рис. 3. Сравнительная оценка ориентации вектора смещения зоо 350 Для проведения исследований использовалась база видеопоследовательностей Object Tracking and Classification in and Beyond the Visible Spectrum [7]. В ходе экспериментов было выявлено, что тензорный подход по скорости работы сопоставим с методом Лукаса-Канаде, но при этом обладает большей чувствительностью в оценке и лучше определяет ориентацию вектора смещения (рис. 3). С помощью тензорного подхода легче фильтровать ложные срабатывания, что делает его более устойчивым к шуму. Таким образом, в данной статье рассмотрен тензорный подход к оценке движения и сформулирован общий алгоритм, который позволяет построить оптический поток для выбранных точек кадра. Разработано программное обеспечение, реализующее данный подход и проведено его сравнение с методом Лукаса-Канаде. Сравнение показало, что по скорости работы рассматриваемый подход сравним с методом Лукаса-Канаде, но обладает большей чувствительностью к оценке ориентации вектора смещения, что характеризует его как более точный.