Естественные и технические науки, № 6, 2013 Малистов А.С., кандидат технических наук, заместитель руководителя отдела ЗАО «ЭЛВИС-НеоТек» ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ ДЛЯ ОБНАРУЖЕНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ КОМПЬЮТЕРНЫМИ ВИДЕОСИСТЕМАМИ Задача сопоставления объектов между кадрами является важной и значимой в компьютерном зрении. <...> Представлен обзор нескольких алгоритмических методов теории графов для решения задачи построения траекторий. <...> Keywords: graph theory, moving object detection, computer video systems. важная задача построения траекторий. <...> В каждый дискретный момент времени где чае количество подвижных областей для может быть различным. <...> Момент времени называется моментом появления объекта, ходимо для заданного набора подвижных областей При распознавании динамических объектов компьютерными видеосистемами возникает алгоритмы выделения движения, получая на вход очередной кадр видеоизображения, распознают некоторое количество подвижных областей и . <...> Траектория задаёт некоторый динамический объект , который существует в некоторых кадрах из промежутка . <...> Чтобы выделить динамические объекты, необпостроить оптимальное множество траекторий таким образом, чтобы каждая область была включена хотя бы в одну из траекторий. <...> Чтобы определить понятие оптимальности, сформулируем задачу в терминах теории графов. <...> Рассмотрим ориентированный граф , каждая вершина которого будет взаимнооднозначно сопоставлена области движения гут входить только такие ребра , для которых вершин можно разбить на непересекающихся подмножеств торых не соединяются рёбрами. <...> Обозначим множество путей в графе вим каждому пути вес . <...> Задача о построении траекторий формулируется следующим образом. <...> Для ориентированного T-дольного графа подмножество вершинно-независимых путей требуется найти максимального суммарного веса. <...> Вершинная независимость путей означает, что каждая вершина может принадлежать только одному пути. <...> Вершины, не принадлежащие ни одному <...>