Малистов А.С., кандидат технических наук, заместитель руководителя отдела ЗАО «ЭЛВИС-НеоТек»
ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ ДЛЯ ОБНАРУЖЕНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ КОМПЬЮТЕРНЫМИ ВИДЕОСИСТЕМАМИ
Задача сопоставления объектов между кадрами является важной и значимой в компьютерном зрении. В этой статье мы рассматриваем подход, основанный на теории графов. Представлен обзор нескольких алгоритмических методов теории графов для решения задачи построения траекторий.
Ключевые слова: теория графов, обнаружение движущихся объектов, компьютерные видеосистемы.
APPLICATIONS OF GRAPH THEORY IN COMPUTER VISION FOR MOVING OBJECTS DETECTION
An important and significant problem in computer vision, and in particular in motion detection, is to determine object correspondence over a set of video frames. In this paper, graph based approach is presented. We present an overview of a number of graph theoretic methods for solving tracking problem.
Keywords: graph theory, moving object detection, computer video systems.
При распознавании динамических объектов компьютерными видеосистемами возникает
важная задача построения траекторий. В каждый дискретный момент времени t= 1,Г алгоритмы выделения движения, получая на вход очередной кадр видеоизображения, распознают некоторое количество подвижных областей {Тр/^} где t = 1, „„,77l(t). В общем случае количество подвижных областей ?7L(fa) и в разные моменты времени ф может быть различным.
Траектория - это последовательность областей г^^, ц = такая, что tt < £j
для f < j. Момент времени t j называется моментом появления объекта, ^ 1 - моментом исчезновения. Траектория задаёт некоторый динамический объект А, который существует в некоторых кадрах из промежутка [ij/t^j- Чтобы выделить динамические объекты, необходимо для заданного набора подвижных областей R = } построить оптимальное множество траекторий таким образом, чтобы каждая область была включена хотя бы в одну из траекторий. Чтобы определить понятие оптимальности, сформулируем задачу в терминах теории графов. Рассмотрим ориентированный граф & = (К, £), каждая вершина тг^ £ V которого будет взаимнооднозначно сопоставлена области движения г^ R В граф G могут входить только такие ребра в = % /tr. X для которых (то есть можно соединять только те области движения, которые могут войти в траекторию). Сопоставим каждому ребру е некоторый вес > 0- Граф G является -дольным графом: множество его
вершин можно разбить на Т непересекающихся подмножеств V^ = j', вершины ко-
торых не соединяются рёбрами. Обозначим множество путей в графе Р = и сопоставим каждому пути -р Р вес ftp > 0.
Задача о построении траекторий формулируется следующим образом. Для ориентированного Г-дольного графа G = (V, Е, Р, О^Д )* ^ = ^ U — UFr требуется найти подмножество вершинно-независимых путей Р' -tz Р максимального суммарного веса. Вершинная независимость путей означает, что каждая вершина может принадлежать только одному пути. Вершины, не принадлежащие ни одному из путей, рассматриваем как траектории нулевой длины.
Алгоритм решения задачи о построении траекторий, даже если он и существует, очень трудоёмок, так как на вход алгоритма необходимо подать веса всех возможных путей графа С, а их число Р растёт по степенному закону от количества долей в -дольном графе С Чтобы упростить задачу, введём ограничение на веса путей. Пусть путь р содержит последовательно ребра р = ¡.Щ) Весом пути будем считать сумму весов каждого из рёбер, которые входят в путь: у^ = + -■ ■ 4- И1^. Тогда задачу построения траекторий можно
свести к задаче о максимальном взвешенном паросочетании в двудольном графе. Действительно, рассмотрим в графе С два подграфа и включает в себя все доли графа С с первой по (Г — 1)-ую и соответствующие рёбра, а ^ - это двудольный граф из и и соответствующих рёбер. Если известно оптимальное подмножество путей Р. в С., то решение для С строится продолжением Р. рёбрами, полученными при решении задачи для графа • Задача о построении траекторий в совпадает с задачей о максимальном взвешенном паросочетании. Паросочетанием в графе называется произвольное множество его рёбер такое, что каждая вершина графа инцидентна не более чем одному ребру из этого множества.
Задача о максимальном взвешенном паросочетании (ЗМВП) формулируется следующим образом. Для заданного взвешенного графа О = (К, Е) с весами рёбер > 0, 8 € Е, требуется найти подмножество рёбер максимального веса №"(£'') такое, что никакие два ребра из Е' не имеют общих концевых вершин (под весом паросочетания понимается сумма весов рёбер, входящих в него).
Существуют три частных случая ЗМВП: можно рассматривать задачу для двудольных графов, для случая единичных весов (поиск паросочетания максимальной мощности) или для обоих ограничений. Хронологически задача о максимальном (невзвешенном) паросочетании сначала рассматривалась на двудольных графах, для которых имеется большое количество приложений. Одним из самых простых алгоритмов, которые решают задачу о максимальном паросочетании является венгерский метод. Он впервые появился в работах Кёнига (1916, 1931, 1936) и Эгервари (1931). Прилагательное венгерский в этом контексте было впервые использовано Куном (1955), который сформулировал эту процедуру в терминах прямо-двойственной линейной программы. Венгерский метод может быть практически реализован как для невзвешенных графов, так и для графов с приписанными рёбрам весами за О^1^) шагов.
Более быстрый алгоритм построения паросочетания в двудольном невзвешенном графе предложен Хопкрофтом и Карпом в 1971 году. Они доказали, что при применении их алгоритма результат получается за шагов. Однако Галил [1] в 1983 году показал, что этот алгоритм работает еще быстрее - оценка числа шагов есть особенно эффективен он в случае графов с небольшим числом ребер (так называемых разреженных графов). До этого в 1980 году Микали и Вазирани предложили алгоритм нахождения паросочетания максимальной мощности в произвольном графе, также имеющий сложность Обзор методов поиска максимального паросочетания сделан в [1], кроме того, некоторые методы описаны в монографиях [2, 3].
ЗМВП является естественным обобщением задачи о максимальном паросочетании на случай произвольных весов. Один из наиболее популярных алгоритмов построения максимального взвешенного паросочетания - алгоритм Эдмондса, подробно описанный в [2, 3], сложность которого оценивается как 0{\,г4) Изменив в алгоритме Эдмондса некоторые детали и использовав более тонкие методы оценивания, в 1976 году Габов улучшает его до 0( 71'). Для разреженных графов в 1982 году Габов, Галил и Микали предлагают более эф-
фективный алгоритм со сложностью Он создан путем соединения прямо-
двойственного метода с некоторой «изящной настройкой» структуры данных. На сегодняшний день наиболее быстрый алгоритм построения паросочетания в двудольном взвешенном графе принадлежит Габову [4] и выполняется за время О (VE -+- V* Lag If)
Как было указано выше, построение максимально взвешенного паросочетания в двудольном графе позволяет решить задачу построения траекторий для случая, когда весовая функция пути линейно зависит от весов ребер. Недавно было представлено несколько субоптимальных алгоритмов, разработанных Робертом Коллинзом [5, 6], которые приближенно решают задачу построения траекторий для некоторых случаев нелинейной зависимости веса пути от входящих в него ребер.
ЛИТЕРАТУРА
1. Galil Z. Efficient algorithms for finding maximal matching on graphs // Lect. Notes Comput. Sci, 1983. - Vol. 159. - pp. 90-113.
2. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.
3. Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981.
4. Gabow H.N. Data structures for weighted matching and nearest common ancestors with linking, Proc. of the First Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, New York, 1990, pp. 434-443.
5. R. Collins. Multitarget data association with higher-order motion models. IEEE Conference on Computer Vision and Pattern Recognition, 2012.
6. A. Butt and R Collins. Multi-target tracking by Lagrangian relaxation to min-cost network flow. IEEE Conference on Computer Vision and Pattern Recognition, 2013.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.