Распознавание объектов в видеопотоке. видеопоток. Метод и алгоритмы поиска объекта в видеопотоке
 Скачать 3.84 Mb.
|
|
2.3 Выбор процедуры нахождения ключевых точек и вычисления дескрипторов Согласно требованию к системе, алгоритм должен быть основан на поиске ключевых точек объекта. Проведенные исследования показали, что метод ASIFT является наиболее устойчивым к рассмотренным критериям. ASIFT основан на методе SIFT, у которого существует быстродейственный аналог – метод SURF. 61 На рисунке 2.8 представлен пример обнаружения объекта методами ASIFT, SIFT и SURF. Метод ASIFT является наиболее устойчивым к рассмотренным критериям, но обладает высокой вычислительной сложностью. Алгоритм ASIFT есть усложнение метода SIFT, позволяющее достичь устойчивости ко всем аффинным преобразованиям благодаря моделированию изменений наклона камеры. Согласно построенной функциональной модели генерацию изменений наклона камеры осуществляет функция A12, тем самым метод ASIFT становится избыточным по нахождению особых точек. В SIFT ключевой точкой считается локальный экстремум в масштабируемом пространстве разности гауссиан. В быстродейственном аналоге – методе SURF [52] ключевой точкой является локальный экстремум детерминанта матрицы Гессе. На практике алгоритм SURF выделяет меньше ключевых точек на изображении объекта, но имеет высокую скорость обработки кадра по сравнению с методом SIFT [53]. Для быстрого нахождения ключевых точек и вычисления дескрипторов за основу предложено использовать метод SURF. Учитывая построенную функциональную модель, устойчивость к масштабированию в системе достигается за счёт выполнения функции A13 над изображением искомого объекта, поэтому метод SURF модернизирован: поиск ключевых точек выполняется только на одной октаве. В связи с этим вычислительная сложность модернизированного метода уменьшается в s раз (см. таблицу 1.1), где s – количество октав. 62 Рисунок 2.8 – Пример обнаружения объекта методами ASIFT, SIFT, SURF 2.4 Алгоритмы и методы нахождения пересечения дескрипторов Для нахождения пересечения двух дескрипторных множеств на сегодняшний день активно используются следующий подходы: метод RANSAC; алгоритм Куна – Манкреса. 63 2.4.1 RANSAC RANSAC – это общий метод, который используется для оценки параметров модели на основании случайных выборок. При сопоставлении модель представляет собой матрицу преобразования (гомография). На входе алгоритма имеется два множества дескрипторов. Схема работы RANSAC состоит из многократного повторения трех этапов: 1. Выбор точек и построение параметров модели. Из входных множеств дескрипторов выбираются случайным образом без повторений наборы фиксированного размера. На основании полученных наборов строится матрица преобразования. 2. Проверка построенной модели. Для каждого дескриптора изображения объекта находится проекция на текущем кадре и выполняется поиск наиболее близкого дескриптора из множества дескрипторов текущего кадра. Дескриптор помечается как выброс, если расстояние между проекцией и соответствующим дескриптором текущего изображения больше некоторого порога. 3. Замещение модели. После проверки всех точек проверяется, является ли построенная модель лучшей среди набора предшествующих моделей. В результате применения RANSAC строится наилучшая матрица гомографии. Вычислив перспективную проекцию набора дескрипторов изображения объекта, достаточно выполнить проход по всем соответствиям, полученным в процессе перебора, и проверить, является ли соответствующий дескриптор текущего кадра достаточно близким к проекции дескриптора изображения объекта. Если не является, то пара отбрасывается [54]. Согласно [55] для одной модели вычислительная сложность составит O(n), однако на практике результаты являются не приемлимыми для использования за счёт большого количества возможных ошибок [56]. Существуют модификации метода RANSAC. Например, алгоритм Джи-Линкейджа и алгоритм адаптации ядра, позволяющие находить пары с меньшим количеством ошибок, но обладающие вычислительной сложностью O(n 2 ) [56]. Алгоритм масштабно 64 сжатого вектора Фишера с RANSAC (SCFV-RANSAC) [57] аналогичным образом засчёт дополнительной обработки набора дескрипторов для сопоставления имеет меньше количество ошибок. 2.4.2 Алгоритм Куна-Манкреса Задачу сопоставления дескрипторов можно представить в виде задачи о назначениях. Интерпретируем в графовый вид. Пусть параметры масок (дескрипторы) – вершины графа, а значения меры схожести вершин – рёбра этого графа. Сложность оригинального алгоритма составляет O(n 4 ). Для решения задачи методом Куна-Манкреса необходимо добавить новые виртуальные вершины графа, которые будут бесконечно удалены от других вершин. Тогда K n,n [W] – взвешенный граф с долями X и Y. Выходом метода является множество ребер оптимального паросочетания P в данном графе. Метод Куна – Манкреса можно представить в виде следующих последовательных опереций: 1. Задать в K n,n [W] произвольную допустимую разметку f и найти подграф равенств G W,f 2. Венгерским алгоритмом найти максимальное паросочетание P в графе G W,f и множество F свободных относительно P вершин доли X. 3. Если F = 0, закончить работу. 4. Найти все чередующиеся цепи в графе G W,f , начинающиеся в F, положить S и T равными множеству всех вершин доли X (соответственно, доли Y), встретившихся в этих цепях. 5. Если в T нет свободных вершин, положить , \ min i j i j ij x S y Y T f x f y w , где f(x) = f(x) − ∆ для всех x ∈ S, f(y) = f(y) + ∆ для всех y ∈ T, найти новый граф G W,f и вернуться на шаг 4. 65 6. Увеличить P, перекрасив найденную увеличивающую цепь, и вернуться на шаг 3 [58]. 2.4.3 Алгоритм ограничения области поиска объекта в кадре Алгоритм ограничения области поиска объекта оценивает масштаб изображения объекта по дескрипторам ключевых точек по следующей схеме: 1. Найти для каждой ключевой точки кадра ближайшее соответствие из набора проективно искажённых изображений образца. 2. Убрать из дальнейшего рассмотрения ключевые точки кадра, имеющие значение меры близости ниже порога Thr. 3. Для каждой оставшейся ключевой точки кадра построить прямоугольную область. Координаты выделенной области на изображении определяются по координатам соответствующей ключевой точки на искажённом изображении образца. 4. Из множества ключевых точек для дальнейшего анализа оставить только те, прямоугольные области которых имеют площади пересечений с другими прямоугольными областями меньше, чем половина площади прямоугольной области рассматриваемой ключевой точки. Более подробно алгоритм представлен в виде блок-схемы на рисунках 2.9 и 2.10, построенных согласно стандарту ЕСПД 19.701-90 «Схемы алгоритмов, программ, данных и систем» [60], где Thr – порог меры близости дескрипторов. 66 Рисунок 2.9 – Блок-схема алгоритма ограничения области поиска объекта в кадре Мера близости между дескрипторами кадра и изображением образца вычисляется по коэффициенту Бхаттачария [59]: 1 0 , n i i i p a b где a, b – векторы размерности n, p – мера близости, 0,1 p Предложенный алгоритм имеет меньше вычислительную сложность, чем алгоритмы RANSAC и Куна-Манкреса. Однако недостатком такого подхода является определение значения порога Thr. 67 Рисунок 2.10 – Блок-схема процесса удаления прямоугольных областей поиска объекта 2.5 Алгоритм идентификации области изображения Алгоритм идентификации должен определять, является ли область на кадре изображением или частью изображения объекта. Для этого алгоритм должен найти параметры окна на кадре по найденным областям, полученными на основании сопоставления локальных признаков изображения – ключевых точек. Пусть алгоритм идентификации находит объект эллиптическим окном. В алгоритме предлагается использовать метод, основанный на глобальном свойстве изображения. Одной из самых распространённых глобальных характеристик 68 является цветовая гистограмма [61]. Цветовая гистограмма вычисляется быстро, однако при вычислении, не учитывается пространственное расположение пикселей. Предлагается значения цвета точек вносить с определённым весом: чем ближе точка к центру окна, тем больше её вес. Это необходимо и для того, чтобы небольшие смещения окна приводили к небольшим изменениям ошибки сопоставления. Такому условию соответствует ядро Епонечникова [62]: 2 1 , 1 0, 1 x x K x x Таким образом, цвет пикселя x будет внесён в цветовую гистограмму с определённым весом K(x). В основу идентификации объекта предлагается использовать технику Mean Shift [63]. Mean Shift основан на поиске максимума плотности вероятности некоторой функции, которая описывает дискретные данные. Для локализации объекта предлагается использовать градиентный спуск. В качестве критерия схожести предлагается использовать коэффициент Бхаттачария [59]. 2.5.1 Градиентный спуск Градиентный спуск применяется для решения задачи нахождения локального минимума [64]. Предлагается использовать четырёхпараметрический поиск окна изображения объекта (см. рисунок 2.11) [65]. Для устойчивого процесса идентификации к незначительным изменениям цвета и для уменьшения размера гистограммы производится квантование значений цветовой гистограммы. 69 Рисунок 2.11 – Четырёх параметрическая модель поиска Четырёх параметрический поиск окна изображения объекта методом градиентного спуска состоит из следующих шагов: 1. Задать ρ th (минимальное значение порога схожести), i max (максимальное количество итераций), w 0 и h 0 (длины полуосей эллипса). 2. Вычислить нормированный вектор частот значений интенсивностей (гистограмму) hist 0 в эллиптической области (x 0 , y 0 , w 0 , h 0 ). 3. Вычислить меру схожести при помощи коэффициента Бхаттачария: 0 0 , refb b b B hist hist где hist ref – гистограмма изображения объекта для поиска, b – шаг гистограммы, b B 4. i = 1. 5. Пока ρ i-1 < ρ th и i < i max выполнить: 5.1 Вычислить градиент gradρ i-1 : 70 1 1 1 1 1 , , , i i i i i grad x y w h 5.2 Вычислить k i-1 : 1 1 1 1 1 1 2 1 1 , , , i i i i i i i x y w h k grad 5.3 Вычислить величину шага: 1 1 , , , i i i i i i x k r w h d y g a 5.4 Изменить параметры эллипса: 1 1 1 1 , , , , , , , , , i i i i i i i i i i i i x x y w h y w h y w h x 5.5 Рассчитать относительную гистограмму hist i эллиптической области , , , i i i i x y w h 5.6 Вычислить меру схожести ρ i : i refb ib b B hist hist 5.7 i = i + 1, перейти на шаг 5. 6. Стоп. Начальные значения w 0 и h 0 берутся из параметров рассматриваемой области P, полученной после алгоритма ограничения области поиска объекта в кадре. Цветовая гистограмма вычисляется по цветоразностным компонентам U и V цветового пространства YUV [66]: 0.14713 0.28886 0.436 128 0.615 0.51499 1.0001 128 U R G B V R G B , где R, G, B – 8-ми битные значения цвета. Такая гистограмма имеет меньше размер в отличие от гистограммы, состоящией из трёх компонентов пространства RGB и такая гистограмма устойчивее к изменению яркостной составляющей на изображении [66]. Градиентный спуск, применённый для определения параметров четырёхпараметрической модели, имеет вычислительную сложность O(n 2 ) [67]. Как только в методе идентификации значение критерия соответствия цветовой 71 гистограммы становится выше определённого порога ρ th , либо количество итераций превышено максимального значения i max , процесс идентификации прекращается. Изображение объекта считается найденным на кадре, если превышено минимальное значение порога схожести ρ th 2.6 Алгоритм поиска объекта в видеопотоке Декомпозиция функции поиска объекта в видеопотоке позволяет описать алгоритм поиска: 1. Вычислить параметры изображения объекта для поиска. 1.1 Создать набор Q ref проективно искажённых изображений объектаY ref 1.2 Найти ключевые точки изображений объекта для поиска: 0 1 , , l Kref Kref Kref 1.3 Вычислить дескрипторы ключевых точек Kref изображений объекта: 0 0 0 1 1 1 0 1 m k k m Dref Dref Dref Dref Dref , где Dref – матрица значений дескриторов объекта, i j Dref – j-ое значение i-ого дескриптора, m – размер дескриптора, k – количество дескрипторов. 1.4 Вычислить цветовую гистограмму изображения объекта: 0 1 , , ref ref ref n H H H 2. Пока i < N max выполнить: 2.1 Найти ключевые точки i-ого кадра: 0 1 , , i i i m K K K 2.2 Вычислить дескрипторы ключевых точек i-ого кадра: 0 1 , , i i i m D D D 2.3 Сравнить дескрипторы i D кадра со строками матрицы Dref и выбрать отклоняющиеся выше определённого порога Thr. 72 2.4 Найти набор прямоугольных областей P i на кадре алгоритмом ограничения области поиска объекта. 2.5 Пока j < Sp i выполнить: 2.5.1 Проверить область i j P на наличие изображения объекта четырёх параметрическим градиентным спуском. 2.5.2 Если мера схожести гистограмм ниже порога ρ th , делать: 2.5.2.1 j: = j + 1, перейти на шаг 2.5. 2.5.3 Иначе делать: 2.5.3.1 Выделить прямоугольным окном изображение объекта и сохранить кадр. 2.5.3.2 i: = i + 1, перейти на шаг 2. 3. Стоп. На рисунке 2.12 представлен разработанный алгоритм более подробно в виде блок-схемы. На рисунке 2.13 представлена функция вычисления дескрипторов на проективно искажённых изображениях объекта. Блок-схемы построены согласно стандарту ЕСПД 19.701-90 «Схемы алгоритмов, программ, данных и систем» [60]. Функция преобразования изображения I{R, G, B} в полутоновое изображение Y взята из рекомендации BT.601 [66], [68]: 0.299 0.587 0.114 Y R G B , где R, G, B – матрицы цветности изображения I красного, зелёного и синего цвета соответственно. SURF ищет ключевые точки в масштабе до 10 раз. Предлагается масштабировать изображение образца до 20 раз с шагом равным 2 в связи с тем, что ключевые точки вычисляются только на одном масштабе. Согласно [2] потребуется 6 значений долготы и 3 значения широты для генерации изменений наклона камеры. SURF устойчив к поворотам до 30º [69], следовательно, предлагается использовать 12 значений коэффициентов изменения угла поворота с шагом 30º. 73 Таким образом, общее количество проективно-искажённых изображений составит 20·6·3·12 + 1 = 4321 штука. Рисунок 2.12 – Блок-схема алгоритма поиска объекта в видеопотоке |