Распознавание объектов в видеопотоке. видеопоток. Метод и алгоритмы поиска объекта в видеопотоке
 Скачать 3.84 Mb.
|
|
Структура и объем работы. Диссертация изложена на 135 страницах, содержит 47 рисунков, 14 таблиц, и состоит из введения, четырех разделов, заключения, списка литературы, включающего 84 наименования, 3 приложений. 11 1 Анализ методов и алгоритмов обнаружения объекта и слежения за объектом в видеопотоке 1.1 Классификация методов и алгоритмов обнаружения объекта и слежения за объектом в видеопотоке Видеоаналитика – технология, использующая методы компьютерного зрения для автоматизированного получения различных данных на основании анализа последовательности изображений, поступающих с видеокамер в режиме реального времени или из архивных записей [1]. Под задачей обнаружения динамических объектов понимается задача обнаружения и выделения изменяющихся участков изображения в последовательности кадров [19]. Соответственно, под обнаружением определённого объекта понимается выбор одного или нескольких обнаруженных динамических объектов, которые имеют некоторые схожие признаки с заданным объектом поиска. Признаки выбираются согласно алгоритму. Трекингом (от англ. tracking – слежение) называется определение местоположения движущегося объекта (нескольких объектов) во времени с помощью камеры [20]. Методы обнаружения и слежения можно разбить на следующие группы: — детерминированные методы; — вероятностные методы; — нейросетевые методы; — комбинированные методы. В этих методах объект слежения в последовательности кадров воспринимается по-разному: объект с неизменяющимися, либо с изменяющимися признаками. 1.2 Детерминированные методы Детерминированные методы выдают уникальный и предопределённый результат для заданных входных данных. Детерминированные методы 12 рассматривают объект слежения, как объект с неизменяющимися признаками. Эти методы можно разделить на группы: методы поиска оптического потока, методы поиска особенных точек и методы поиска по шаблону. Методы поиска оптического потока основаны на вычислении разреженного оптического потока. Эти методы строят векторное поле скоростей выделенных точек (пикселей изображения). Методы поиска особенных точек основаны на вычислении характерных особенностей на изображении и на нахождении соответствия между ними в видеопоследовательности. Методы поиска по шаблону не имеют этапа обучения (методы без учителя [21]). Эти методы вычисляют набор признаков на одном заданном изображении с объектом для поиска. Методы поиска по шаблону имеют сложный этап обнаружения объекта. 1.2.1 Методы поиска по шаблону В методах поиска по шаблону используются детекторы особенностей. Детекторы обнаруживают особенные, отличительные участки изображения. Можно выделить самые распространённые детекторы – это детекторы рёбер, детекторы углов, детекторы окружностей. Методы поиска по шаблону применяют в основном в качестве вспомогательных методов, так как эти методы позволяют обнаружить некоторые геометрические примитивы (прямая, круг, прямоугольник), а как их сравнивать на изображениях – это отдельная задача. Для сопоставления обнаруженных участков изображения может применяться алгоритм сопоставления дескрипторов особенностей, в котором особенными точками будут каждые точки найденных примитивов. Детектор прямых линий С точки зрения детектора прямых линий преобразование можно представить как суммирование яркостей точек на контурном изображении вдоль 13 всевозможных направлений. Направления однозначно задаются перпендикулярными им векторами, проведёнными из центра картинной плоскости. Вектора задаются в полярной системе координат длинной и углом с вертикалью. На выходе преобразования получается функция, зависящая от двух аргументов угла и расстояния. По значениям функции можно определить количество точек, лежащих вдоль определённой прямой линии. Первый этап предполагает выделение контуров. На втором этапе происходит суммирование яркостей точек вдоль прямой, которая задается углом и длиной. Результатом суммирования по всем прямым линиям является двумерная функция, зависящая от угла и расстояния. Полученная функция не несёт информации о расположении отрезков на линии, она лишь говорит, что он есть, поэтому, в дополнение к описанным операциям, потребуется реализация алгоритма локализации отрезка на прямой. К достоинствам преобразования следует отнести высокую надёжность детектирования прямых линий. Разрывы контурной линии вдоль прямой оказывают незначительное влияние на работу алгоритма. К недостаткам следует отнести необходимость проведения операции нахождения контуров, поиска областей пересечения траекторий отдельных точек в многомерном пространстве параметров и необходимость дополнительных алгоритмов, для локализации отрезков на найденных прямых линиях. Детекторы углов Один из первых алгоритмов предложил Бедет [22]. Он определяет положения углов по максимумам определителя Гессиана от функции яркости изображения: H=I xx I yy +I xy 2 Этот метод работает хорошо с углами равными 90. И так, как в методе используются вторые производные от функции яркости, то результат сильно подвержен влиянию шума. В свою очередь Форстнер [23] предложил детектор 14 углов, использующий только первые производные от функции яркости, и определил углы, как локальные максимумы: 2 2 2 2 2 , , x y x y x y I I I I F x y I I где чёрточки над переменными обозначают среднее значение в некоторой области точки (x,y). Недостатком детекторов углов, использующих компоненты градиента яркости, является то, что определение самих компонент градиента основано на дифференциальных масках, моделях горизонтального и вертикального контрастного перепадов. Они плохо работают в местах расположения углов, т. к. маска предполагает, что контрастный перепад может быть продлён по прямой до бесконечности. Детекторы окружностей Очевидным методом нахождения окружностей на изображении является прослеживание кривизны контурных линий. Али Айдари Рад и др. предложили алгоритм быстрого поиска окружностей на изображении [24], используя противоположную направленность пары векторов градиента, лежащих на противоположных концах окружности, а также тот факт, что их базы лежат на прямой параллельной им [25]. Метод превосходит по скорости метод Хука для поиска окружностей и является более устойчивым к наличию шума типа «соль и перец» (шум в виде случайных белых и чёрных точек). Методы поиска по шаблону позволяют обнаружить некоторые геометрические примитивы на изображении. Процесс обнаружения быстр по скорости, но алгоритм сопоставления примитивов может быть очень вычислительно сложным, потому что необходимо учитывать взаимное расположение примитивов на изображении с объектом на изображении, на котором осуществляется поиск. 15 Таким образом, детерминированные методы воспринимают объект с практически неизменяющимися свойствами в видеопоследовательности, методы основаны на обнаружении графических примитивов: точка, прямая, круг... Методы являются вычислительно сложными, имеют большую популярность в настоящее время благодаря своему качеству обнаружения. 1.2.2 Методы поиска оптического потока Методы поиска оптического потока основываются на вычислении направления характерных участков изображения. В этих методах процесс обнаружения делится на два этапа: вычисление векторного поля скоростей и определение смещения объекта. Метод Лукаса–Канаде Метод Лукаса–Канаде – локальный метод вычисления оптического потока, имеющего линейную вычислительную сложность. Основное уравнение оптического потока содержит две неизвестных и не может быть однозначно разрешено. Метод Лукаса–Канаде обходит неоднозначность за счет использования информации о соседних пикселях в каждой точке. Метод основан на предположении, что в локальной окрестности каждого пикселя значение оптического потока одинаково. Рассмотрим пиксель p, тогда, по методу Лукаса–Канаде, оптический поток должен быть одинаков для всех пикселей, находящихся в окне с центром в точке p. А именно, вектор оптического потока (V x , V y ) в точке p определяется по формуле: 1 2 2 i x i i x i y i i x i t i x i i i y i y i t i i x i y i i y i i i i I q I q I q I q I q V V I q I q I q I q I q , где q 1 , q 2 ,…, q n – пиксели внутри окна, I x (q i ), I y (q i ), I t (q i )– частные производные изображения I по координатам x, y и времени t, вычисленные в точке q i , ω i – вес, 16 присвоенный пикселу q i . В качестве весов ω i обычно используется нормальное распределение расстояния между q i и p [26]. Метод Лукаса–Канаде является сугубо локальным и не может определить направление движения пикселей внутри однородных областей. Некоторые изображения могут давать вырожденную матрицу A, для которой не может быть найдена обратная матрица, соответственно для таких изображений невозможно определить смещение. На сегодняшний день метод Лукаса–Канаде имеет множество модификаций. В методе Томаси–Канаде движением считается смещение и рассчитывается путём итеративного решения построенной системы линейных уравнений. Метод Ши– Томаси–Канаде учитывает аффинные искажения. Метод Джин–Фаваро–Соатто учитывает аффинные изменения освещённости. 1.2.3 Методы поиска особенных точек Алгоритм работы методов поиска особенных точек можно разделить на два этапа: обнаружение особенных точек, сопоставление особенных точек. Для сопоставления обнаруженных особенностей используются дескрипторы особенностей. Дескриптор особенности – вектор числовых характеристик окрестности особенности D(x) = [f 1 (w(x))...f n (w(x))], где w(x) – некоторая окрестность точки x, а f(w 1 ,w 2 ) – мера, используемая для сравнения окрестностей особых точек. При сопоставлении особенностей, для принятия решений о том, соответствуют ли друг другу особенности или нет, сравниваются именно дескрипторы особенностей. Метод Харриса–Лапласа Метод Харриса–Лапласа находит особенные точки на изображении. Классический метод Харриса–Лапласа не устойчив к масштабированию объектов на изображении, метод не находит особые точки при сильном изменении 17 масштаба. Опишем метод Харриса–Лапласа, учитывающий масштабирование объектов на изображении. 1. Для начала необходимо вычислить значения адаптированной к масштабированию функции Харриса для масштабов σ n = ξ n ·σ 0 H(x, 1 , D ) = det(μ(x, 1 , D )) + 0.04·trace 2 (μ(x 1 , D )), 2 , , 1 1 1 1 2 , , , , где , , , , , 0.7. , , x norm D xy norm D D n D x norm D y norm D L x L x x g s s L x L x 2. Количество слоев и значение шага масштаба ξ следует выбирать в зависимости от того, насколько большим может быть изменение масштаба между двумя изображениями. 3. Для каждого уровня масштаба найти локальные максимумы вычисленной функции Харриса, это и есть особые точки для данного масштаба изображения. Обычно таким образом получается достаточно много точек и часть из них можно отбросить. Например, можно отбросить все точки, для которых значение функции Харриса не превосходит некоторого значения H thr , т.к. максимумы с небольшим значением функции Харриса менее устойчивы. 4. Для каждой найденной таким образом особенности установить, достигается ли в ней максимум функции LoG(x,σ n ) = |L xx,norm (x,σ n ) + L yy,norm (x,σ n )| по переменной n, т.е. LoG(x,σ n–1 ) < LoG(x,σ n ), LoG(x,σ n+1 ) < LoG(x,σ n ). Если локальный максимум не достигается, либо значение функции не превосходит порога LoG thr , то точка отбрасывается. 5. Все оставшиеся точки являются особенностями изображения, с каждой точкой ассоциирован масштаб σ n , на котором она была обнаружена [27]. Инвариантный дескриптор к изменению масштаба При использовании scale–space детектора особенностей добиться инвариантности к изменению масштаба очень просто. Для этого достаточно перед вычислением дескриптора провести нормировку в соответствии с локальным масштабом особенности, например, если с особенностью ассоциирован масштаб 18 2, то окрестность особенности следует масштабировать с коэффициентом 0,5 и т.д. Если дескриптор состоит из выражений, в которых используются исключительно нормированные производные, то масштабировать окрестность не обязательно. Достаточно рассчитывать значения производных для значения масштаба σ, который ассоциирован с особенностью. Инвариантный дескриптор к повороту Самый простой метод добиться инвариантности к повороту при сопоставлении особенностей – использовать дескрипторы, компоненты которых инварианты к повороту. Все производные в выражении – нормированные производные. Серьезным недостатком этого метода является то, что в дескрипторе нельзя использовать компоненты, которые не инвариантны к повороту, а число операторов, которые инвариантны к повороту, и при этом применимы на практике, ограничено. Еще одни способ добиться инвариантности к повороту – предварительно нормировать окрестность точки особым образом, чтобы скомпенсировать поворот, и лишь потом вычислять дескрипторы для особенности. Для того чтобы нормировать окрестность по повороту требуется оценить т.н. ориентацию особенности (см. рисунок 1.1). Существует много методов оценки локальной ориентации особенности, все они так или иначе используют направление векторов градиентов в окрестности особенности. Рисунок 1.1 – Окрестность особой точки. Красным указаны направления градиентов, а синим показана ориентация особенности [27] 19 Разделим множество углов от 0 до 360 градусов, например, на 36 одинаковых участков, каждый по 10 градусов. Каждому из участков сопоставим ячейку в гистограмме H. Для каждой точки x 0 из некоторой окрестности a особенности необходимо вычислить фазу и модуль вектора градиента grad(x 0 ,∂) = (L x,norm (x, 0 ,∂) L y,norm (x, 0 ,∂)), , , ,0, ,0, y norm x norm L x L x , A = |grad(x 0 ,∂)|, H[i θ ] = H[i θ ] +Aw, где i θ – индекс ячейки, которая соответствует фазе градиента, а w – вес точки x 0 . В качестве веса можно использовать, например, w = 1 (это простейший случай), но более качественных и устойчивых результатов оценки удаётся добиться при использовании, в качестве веса, значения Гауссиана с центром в точке a. После этого для каждой точки окрестности особенности в качестве ориентации особенности следует выбрать φ=i·10°, где i – индекс элемента гистограммы с наибольшим значением. Затем необходимо повернуть особенность на угол (−φ) вокруг центра особенности. К сожалению, для некоторой части особенностей ориентация оценивается неверно (обычно 10–20%) и дескрипторы этих особенностей оказываются абсолютно непригодны к сопоставлению. Именно это является основным недостатком данного подхода. Инвариантный дескриптор к изменению освещенности Для того чтобы сделать дескриптор инвариантным к изменению освещенности нужно для начала ввести модель этого изменения. Обычно применяют т. н. аффинную модель, которая подразумевает, что значения пикселей окрестности при изменении освещенности меняется по следующему закону: Î = a·I(x) + b. Это модель не очень точно соответствует действительности и реально процессы, происходящие в пикселях при изменении освещенности намного сложнее, но в силу того, что особенности локальны и имеют небольшой 20 размер такой модели более чем достаточно. Учитывая принятую модель можно использовать следующий алгоритм, устраняющий влияние освещенности на значение пикселей в окрестности особенности: 0 , mean mean result I w x I w x I w x mean I w x I w x std I w x , где mean(I(w(x))) и std(I(w(x))) обозначают выборочное среднее и среднее квадратичное отклонения в окрестности w, I mean (w(x)) – окрестность, скомпенсированная по переносу, а I result – результирующая окрестность, скомпенсированная по освещенности. Именно по особенности I result следует вычислять дескриптор особенности, чтобы добиться инвариантности к изменениям освещенности. Также можно составлять дескриптор из функций, которые инвариантны к аффинным изменениям освещенности. |