Распознавание объектов в видеопотоке. видеопоток. Метод и алгоритмы поиска объекта в видеопотоке
 Скачать 3.84 Mb.
|
|
Алгоритм сопоставления После того как для каждой особенности на паре изображений рассчитаны дескрипторы можно непосредственно приступить к сопоставлению особенностей. Существует множество вариантов алгоритмов сопоставления особенностей по их дескрипторам. Приведём один из них [27]. Обозначим наборы особых точек первого и второго изображения A={a i , i=1..n}, B={b i , i=1..m}, а их дескрипторы D A ={D A,i , i=1..n}, D B ={D B,i , i=1..m}. Будем считать что дескрипторы – вектора столбцы. Для каждой точки первого изображения H[i θ ]=H[i θ ]+Aw найти точку второго изображения b i , такую что j=arg min k (f(D A,j , D B,k )), f(D 1 , D 2 )=(D 1 –D 2 )K –1 (D 1 –D 2 ) T , где K – матрица ковариации дескриптора. Обычно считают что дескриптор – случайная величина с многомерным нормальным распределением. При этом мера f соответствует расстоянию Махаланобиса. Если значение f(D A,i , D B,j ) превосходит значение некоторого порога f thr , следует отбросить данное соответствие. Значение порога сильно зависит от дескрипторов, которые используются для сопоставления. 21 Все пары соответствующих точек следует упорядочить, используя некоторую меру качества. Как меру качества можно использовать неоднозначность соответствия, предложенную в [28], которая имеет следующий вид: , , , , , , , , , min A i B j A i B j A i B j f D D Amb D D f D D k j Чем меньше значение меры Amb, тем более качественным является соответствие. Выбрать необходимо N первых (самых качественных) соответствий. Scale-Invariant Feature Transform (SIFT) Идея метода SIFT сводится к следующему: нахождение изображение объекта через уникальные локальные признаки объекта. Метод SIFT можно разделить на следующие этапы: определение локальных особенностей (точек интереса или ключевых точек); локализация особенностей; вычисление ориентаций особенностей; описание локальных особенностей через дескриптор; сопоставление дескрипторов. Для определения особенностей используется Гауссово масштабируемое пространство. Построение масштабируемого пространства представляет операцию разложения исходного сигнала в семейство постепенно сглаживаемых, упрощающихся версий сигнала, удовлетворяющих требованиям линейности, инвариантности к сдвигу, к масштабу и обладающих свойством полугруппы и положительности [29]. Доказано, что гауссово масштабируемое пространство является линейным, инвариантным к сдвигу, к масштабу, не смещающим локальные экстремумы [30]. В методе SIFT область на изображении является особенной, если она является локальным экстремумом в масштабируемом пространстве (пирамиде) разности гауссиан. На этапе определения характерных 22 точек строятся пирамиды гауссианов и разности гауссианов (DoG – Difference of Gaussian): , , , , , L x y G x y I x y , где L – значение гауссиана в точке с координатами (x, y), σ – радиус размытия, G – гауссово ядро, I – значение исходного изображения, * – операция свертки. Гауссово ядро вычисляется по следующей формуле: 2 2 2 2 2 1 , , e 2 x y G x y , Разность гауссиан DoG вычисляется следующим образом: , , , , , , D x y L x y k L x y , где k – коэффициент изменения радиуса размытия σ. После вычисления разности гауссиан происходит передискретизация исходного изображения: уменьшается частота дискретизации в 2 раза по вертикали и горизонтали. Затем над уменьшенным изображением вычисляют разности гауссиан. Таким образом, строится пирамида разности гауссиан до тех пор, пока размеры изображения не будут меньше определённого порога по ширине или по высоте, либо пока передискретизация не произведётся максимально допустимое количество раз R. После построения пирамиды находятся экстремумы путём сравнения каждой точки с восьмью соседями на текущем изображении DoG (если такие имеются) и с девятью соседями изображений DoG выше и ниже в пирамиде (см. рисунок 1.2) [9]. Этап построения масштабируемого пространства можно описать при помощи уравнения теплопроводности: 2 u a u t , где u = u(t, x), t R, x R n , Δ – оператор Лапласа по x, a > 0, u(t, x) – температура среды в точке x в момент времени t [31]. В случае Гауссово масштабируемого пространства получается следующее уравнение: 23 ∂L σ = σ 2 ∆L, где L(x, y, 0) = I(x, y). После аппроксимации производной ∂L σ получается следующая формула: 2 , , , , 1 L x y k L x y k L , где k – шаг изменения масштаба σ. Таким образом, для моделирования изображения в некотором масштабе необходимо найти разность гауссиан. Рисунок 1.2 – Процесс нахождения локальных особенностей После определения особенностей производится локализация и проверка особенностей на контрастность и на принадлежность к границе между областями изображения, т. е. исключаются из дальнейшего рассмотрения особенности, которые имеют контрастность ниже определённого порога и которые находятся на линейной протяжённой границе между цветовыми объектами (см. рисунок 1.3). 24 Рисунок 1.3 – Примеры особенностей, исключаемых из рассмотрения Вначале этапа локализации определяются координаты ключевых точек с субпиксельной точностью, для этого аппроксимируется функция DoG многочленом Тейлора второго порядка в найденном экстремуме [32]: 2 2 1 2 T T D D D x D x x x x x , где x – смещение, x = (x, y, σ). Вычислив производную и приравняв равенство к нулю, получим экстремум ˆ x : 2 1 2 ˆ D D x x x Если смещение ˆ x больше, чем 0.5, то это означает, что экстремум лежит ближе к другой точке выборки. В этом случае точка выборки изменяется, и выполняется интерполяция заново для изменённой точки. Итоговое смещение ˆ x добавляется к месту точки, чтобы получить интерполированную оценку для расположения экстремума. После вычисления экстремума с субпиксельной точностью, вычисляется значение DoG в точке ˆ x : 1 ˆ ˆ 2 T D D x D x x Значение ˆ D x сравнивается с граничным значением D min = 1. Если min ˆ D x D , то особенность считается с малой контрастностью и извлекается из дальнейшего рассмотрения. Проверка особенностей на принадлежность к границе между областями изображения осуществляется через вычисление матрицы Гессе H: 25 xx xy xy yy D D H D D Пусть Tr(H) – след матрицы, Det(H) – определитель матрицы H, тогда точка исключается из дальнейшего рассмотрения, если имеет большой изгиб α вдоль границы и малый β в перпендикулярном, тогда: xx yy Tr H D D , 2 xx yy xy Det H D D D Точка извлекается из дальнейшего рассмотрения, если не удовлетворяет условию: 2 2 1 Tr H r Det H r , где r = α / β. Для нахождения ориентации ключевой точки вычисляются направления и величины градиентов в окне с радиусом 3σ в центре особенности: 2 2 , 1, 1, , 1 , 1 m x y L x y L x y L x y L x y , 1 , 1 , 1 , tan 1, 1, L x y L x y x y L x y L x y , где m – величина градиента, θ – направление градиента. После вычисления направлений градиентов строится гистограмма направлений Hist, состоящая из 36 компонент: w k = m(x, y) * G(x, y,1.5σ), где направление градиента выбирается из ближащего направления k гистрограммы Hist, w k – вес градиента в точке (x, y) для k-ой компоненты Hist. Направление особенности находится в промежутке, покрываемом максимальной компонентой гистограммы Hist. Максимальное значение и два соседние значения интерполируются параболой, точка максимума параболы берётся в качестве направления особенности. Если в гистограмме есть ещё компоненты со 26 значениями не меньше 80% от максимального направления, то они аналогично интерполируются и дополнительные направления добавляются к ключевой точке. После определения ориентации поворачивают окно с радиуом 3σ в центре особенности в направление ориентации – этим достигается инвариантность относительно поворота. Затем вся область в окне делится на 16 квадратных одинаковых блока (4×4), в которых вычисляются гистограммы направлений (см. рисунок 1.4). Рисунок 1.4 – Построение дескриптора размерностью 2 2 8 Дескриптор особенности состоит из полученных гистограмм. Размерность дескриптора оригинального метода SIFT составляет 4 4 8 = 128 элементов. После описания дескриптора через вектор, состоящего из 128 элементов, дескриптор нормализуется. Affine-Scale-Invariant Feature Transform (ASIFT) Метод ASIFT является усложнением метода SIFT и является полностью аффинно-инвариантным методом засчёт моделирования всех изменениий угла наклона камеры. Цифровое изображение I можно разложить на составляющие по следующей формуле: 1 2 cos sin 0 cos sin sin cos 0 1 sin cos t t I H R T R , 27 где – определитель матрицы I, R 1 , R 2 – повороты, φ ∈ [0, π), T t – наклон, t > 1. Геометрическое представление аффинной декомпозиции представлено на рисунке 1.5. Рисунок 1.5 – Геометрическое представление аффинной декомпозиции Угол θ предлагается изменять по геометрической прогрессии: 1, a, a 2 , …, a n , где n = 5, a = 2 , аугол φ для каждого наклона изменять по арифметической прогрессии: 0, b/t, …, kb/t, где b ≃ 72° и kb / t < 180°. На каждой смоделированной картинке находятся ключевые точки с дескрипторами методом SIFT. Все найденные дескрипторы сравниваются с дескрипторами оригинального изображения [2]. Speed Up Robust Feature (SURF) Метод SURF является аналогом метода SIFT. Метод ищет ключевые точки и строит описание найденных ключевых точек через дескрипторы особенностей. Ключевая точка в SURF – это локальный экстремум детерминанта матрицы Гессе. Для двумерного случая детерминант матрицы Гессе определяется следующим образом: 2 2 2 2 2 2 det f f f H x y x y , где H – матрица Гессе, f(x,y) – функция изменения градиента. На рисунке 1.6 показаны фильтры компонент D xx , D yy , D xy матрицы Гессе H размером 9x9. Метод SURF использует аппроксимацию этих фильтров, изображённых на рисунке 1.7. 28 Такие фильтры устойчивы к вращению и их можно эффективно вычислить при помощи интегральной матрицы. Слева направо: D xx , D yy , D xy . Серый регион соответствует значению 0. Рисунок 1.6 – Фильтры компонент D xx , D yy , D xy матрицы Гессе Детерминант матрицы Гессе для фильтров, изображённых на рисунке 1.7 вычисляется по следующей формуле: 2 det 0,9 approx xx yy xy H D D D , где коэффициент 0,9 взят на основании результатов в [33]. Гессиан инвариантен относительно поворота, но не относительно масштаба, поэтому используются фильтры с разным масштабом для определения гессианов. Слева направо: D xx , D yy , D xy . Серый регион соответствует значению нуля, белый – плюс один, чёрный – минус два (на третьем фильтре минус один). Рисунок 1.7 – SURF фильтры компонент D xx , D yy , D xy , Dxy матрицы Гессе Для определения ориентации особенности используются фильтры Хаара (см. рисунок 1.8), размеры которых равны 4s, где s – масштаб особой точки. Значения вейвлета Хаара dX и dY для каждой точки умножаются на значение гауссианы с центром в особой точке и сигмой равной 2,5s. Благодаря такому взвешиванию, отсеиваются случайные помехи на далёких расстояниях от ключевой точки. Затем 29 при помощи углового окна выбирается направление особенности, при котором длина суммарного вектора для попавших в окно точек будет максимальна. Чёрные области соответствует значению -1, белые +1. Рисунок 1.8 – SURF фильтры компонент D xx , D yy , D xy матрицы Гессе Для вычисления дескриптора особенности формируется прямоугольная область (квадрат) вдоль приоритетного направления размера 20s, где s – масштаб в котором была найдена особенность. Квадрат разбивается на 16 квадратных подобластей, в каждом из которых берется регулярная сетка 5x5. В каждой подобласти вычисляется градиент, с помощью фильтра Хаара. Размер фильтра Хаара берется равным 2s. Рисунок 1.9 – Поведение величин dX , dX , dY , dY при различных ситуациях После нахождения 25 точечных градиент подобластей, вычисляются четыре величины: dX , dX , dY , dY . На рисунке 1.9 приведены примеры поведений этих величин для разных участков изображений. В случае, когда область однородна, то все коэффициенты относительно малы. Для вертикальных 30 повторяющихся полосок все величины кроме dX малы. В случае увеличения яркости вдоль оси x, величины dX , dX имеют большие значения относительно dY , dY Таким образом, для 16 областей получается 64 значения величин, которые и являются компонентами дескриптора. Все значения величин взвешиваются на гауссиану, с центром в особой точке и с сигмой 3,3 s. Методы ASIFT, SURF и SIFT на сегодняшний день являются базовыми методами поиска ключевых точек на изображении. Существует огромное количество модификаций этих методов, уменьшающие ошибки поиска для определённого класса задач. Например, метод MODS соотносит корректно от 5 до 20% больше ключевых точек по сравнению с методом ASIFT [34]. В таблице 1.1 представлены вычислительные сложности методов SIFT, ASIFT и SURF cогласно исследованиям [35], [36], [2], где N 2 – размер изображение, накотором осуществляется поиск, w – размер окна функции Гаусса, s – количество октав, x – количество точек в окрестности для вычисления ориентации, k – количество проективно искажённых изображений. Таблица 1.1 – Вычислительная сложность методов SIFT, ASIFT, SURF Метод Вычислительная сложность ASIFT O(k(sw 2 +x 2 )N 2 ) SIFT O((sw 2 +x 2 )N 2 ) SURF O(sN 2 ) Существуют ряд работ по объединению различных детекторов ключевых точек для уменьшения ошибки поиска [37], однако при этом увеличиваются вычислительные затраты. Таким образом, к достоинствам методов поиска особенных точек можно отнести их высокую устойчивость к масштабированию, к незначительному повороту изображения объекта для поиска; к недостаткам можно отнести |