В наше время наблюдается постоянный рост объема обрабатываемой информации. Однако, с увеличением объемов информации, становится все труднее с ней работать, кроме того, появляются новые виды информации, эффективных алгоритмов обработки которой еще не существует. К таким видам информации можно отнести и видеопоток. Еще сравнительно недавно, количество предприятий, постоянно в своей работе использующих видеоинформацию было мало, также как и объем этой информации, однако наблюдается тенденция как к увеличению объемов видеоинформации, так и к увеличению спектра ее применения. С увеличением объемов видеоинформации, отражающей реальные события, происходящие в мире, соответственно увеличивается и время на ее обработку и анализ. Кроме этого, довольно часто, видеоинформация содержит события, для анализа которых требуется привлечение высокооплачиваемых специалистов, способных грамотно и квалифицированно охарактеризовать подобные события. В связи с этим возникает проблема: "Как можно уменьшить временные и материальные затраты, для того чтобы проанализировать видеоинформацию, полученную из различных источников, таких как телевидение, интернет, или домашнее видео?" Для решения данной проблемы необходимо представить видеопоток в виде графической базы данных, и построить такой алгоритм поиска событий, при выполнении которого ЭВМ будет автоматически находить, и анализировать события, содержащиеся в этом потоке. Заметим, что выполнение подобного преобразования может усложниться, в случае, если анализ необходимо проводить в реальном времени, например, одновременно с трансляцией изображения по телевидению. В данном случае, время, отведенное на выполнение алгоритма поиска событий, должно быть ограничено, и, соответственно, увеличены требования к производительности ЭВМ.
Задача поиска событий в видеопотоке изображений может быть сформулирована следующим образом. В качестве начальных данных задается видеоизображение B, в котором отснята последовательность событий происходящих в реальном времени. Необходимо построить алгоритм, получающий из последовательности В последовательность позиций игроков в каждый момент времени во время матча.
Стандартизация и активное внедрение высокоскоростных интерфейсов передачи данных, таких как USB и IEEE1394, позволяют посредством дешевых мультимедиа-видеокамер передавать огромные потоки видеоданных со скоростями адекватными человеческому восприятию.
Для соответствующей скорости передачи кадров видеоизображения необходимы и быстрые программные средства их обработки. В настоящее время разработано множество библиотек с алгоритмами быстрой обработки изображений. Разработчиком одной их таких библиотек является корпорация Intel, которая бесплатно распространяет библиотеку Image Processing Library (IPL), реализующую следующие популярные функции.
Развитие программного инструментария для мультимедийных задач существенно упрощает применение различной сложности алгоритмов видеокоррекции. Все самые последние достижения в области программирования Plug'n'Play устройств и создания универсальных драйеров вошли в последнюю разработку Microsoft - набор библиотек для разработки мультимедиа приложений DirectX. Этот инструмент формирует высокоуровневый абстрактный слой над аппаратным обеспечением видеообработки и моделью драйверов Windows, тем самым освобождая разработчика от реализации механизмов получения видеоданных и вывода их на монитор. Разработчик получает доступ непосредственно к линейной области памяти, в которой хранится текущий кадр видеоизображения, все что необходимо сделать - наложить на этот кадр разработанный IPL-фильтр, обо всем остальном позаботится DirectX.
Все операции по обработке потоков видео и аудиоданных реализует библиотека DirectShow, подмножество DirectX, которая раньше носила название технологии Microsoft ActiveMovie. Физически DirectShow представляет собой библиотеки COM-компонентов, для использования которых, а также расширения путем создания собственных фильтров, необходимы минимальные знания о технологии COM (Component Object Model) и умение программировать на C++ или Visual Basic.
Основным кирпичиком приложения, использующего DirectShow, является так называемый фильтр, который производит единственную операцию над мультимедиа потоком, например, фильтр чтения из файла, фильтр видеозахвата с видеокамеры, фильтры декодирования (MPEG), фильтры вывода на видео или звуковую карту. Все эти фильтры контролирует менеджер (Filter Graph Manager) - высокоуровневый компонент, который управляет потоком данных между фильтрами. Фильтры стыкуются в графы (узлы), обеспечивая таким образом каналы для потоков видеоданных от видеокамеры до монитора вашего ПК. Фильтры разделяются на следующие категории: фильтры-источники (source), фильтры-преобразователи (transform) и фильтры воспроизведения (renderer). Фильтры первой и последней категории стандартны и для большинства задач можно использовать уже готовые фильтры из DirectShow.
В библиотеке реализован специальный объект для захвата видеоданных (Capture Graph Builder). Он автоматически формирует граф с использованием вашего преобразующего фильтра и выбирает подходящие фильтры для захвата видеоизображения и вывода его на экран монитора. С помощью функций этого объекта можно параметризовать фильтр захвата видеоданных новыми размерами кадра, глубиной цвета, частотой смены кадров, а также размерами вырезаемой области изображения, то есть фактически без потери производительности можно фильтровать произвольную область изображения.
Можно построить дерево фильтров произвольной структуры, например, для одновременного вывода обработанного видеоизображения на экран монитора и сохранения в файл. Для нас же особенный интерес представляют фильтры-преобразователи, с помощью которых можно обрабатывать кадры видеоизображения. В DirectX разработка собственных фильтров сопряжена с некоторыми проблемами за-за завышенных требований к знаниям разработчика алгоритма фильтрации. Для более глубокого понимания происходящих процессов, необходимы начальные знания в разработке COM-объектов и самой технологии OLE.
В работе [1] авторами рассматривается система индексирования и поиска видеоданных.
В связи с большим объемом видеофайлов для организации эффективного поиска данных с удовлетворительными показателями полноты и точности, а также для обеспечения быстрого предоставления пользователю релевантной информации имеет смысл индексировать каждый фильм не как единое целое, а как последовательность логически самостоятельных частей - видеофрагментов [2]. Задача сводится к определению границ видеофрагментов, они могут быть связаны с точками монтажа, изменением положения снимающей камеры и т.п. Временное сегментирование может выполняться путем автоматического анализа изображения, соответствующие приемы известны [3, 4].
Авторами доклада разработан алгоритм, основанный на сравнении цветовых гистограмм соседних кадров для выделения тех кадров, на которых происходит значительное изменение видеоизображения. Граница фрагментов считается обнаруженной, если разница гистограмм между рассматриваемыми кадрами выше некоторого абсолютного порога и одновременно в определенное число раз превышает среднее значение разницы гистограмм соседних кадров, посчитанное от начала выделяемого фрагмента до текущего кадра (относительный порог).
Результаты сегментирования, разумеется, сильно зависят от выбора параметров. Они установлены эмпирически для достижения приемлемых результатов с точки зрения минимизации числа ошибок, связанных с обнаружением ложной границы и пропуском действительной. Текущие значения подобраны так, чтобы ложные обнаружения встречались примерно на порядок чаще, чем пропуск переходов. Вызвано это тем, что на "двойном" видеофрагменте невозможно корректно вычислить характеристики движения, что является одной из главных целей временного сегментирования. Для тестирования программы использовались видеофильмы, взятые из различных источников, разного качества. На тестовом множестве программа не пропускает границы фрагментов для цветных видеофильмов и мультфильмов, для черно-белых фильмов процент пропущенных границ составляет 3-4%. Ложные обнаружения границ фрагментов для различных видеофильмов не превышают 12%.
После того как видеопоток разбивается на фрагменты, из них выделяются для исследования ключевые стоп-кадры. Стратегия извлечения представительных стоп-кадров из каждого выделенного фрагмента может быть очень простой [5], например: если фрагмент короче секунды, берется один центральный кадр, для более длинных фрагментов берется по одному в секунду. Для каждого выделенного кадра вычисляются с целью индексирования визуальные примитивы: цветовые гистограммы, характеристики формы и цвета объектов изображения, измерения текстуры; для этого применяются те же методы, что и для анализа статичных изображений. Кроме того, представляется важным индексировать фрагмент также характеристиками движения камеры/сцены и движения объектов, определяемыми на основании оптического потока, вычисленного по совокупности кадров видеофрагмента [3].
Для видеофрагмента, содержащего некоторые объекты в движении, можно вычислить направление и величину скорости движения в каждой точке кадра - известны разные алгоритмы вычисления оптического потока [6]. Авторами доклада реализован дифференциальный метод расчета оптического потока (метод минимума градиента [7]), который опирается на вычисление пространственно-временных производных интенсивности. В его основе два предположения: а) при движении объекта интенсивность составляющих его точек не изменяется; б) гладкое изменение значения скорости от точки к точке. Эти посылки приводят к системе линейных уравнений, которую авторы метода предлагают решать итерационным методом. Итеративное вычисление оптического потока выполняется нами на основании всех кадров фрагмента для более точного определения скоростей. (Итерация связана с временным шагом.) За счет доработки оригинального метода удалось добиться вычисления достаточно точных значений скоростей без существенного искажения формы и размеров движущихся объектов.
Сложные данные о движении, полученные после вычисления оптического потока, должны быть приведены к простой и пригодной для индексирования и поиска форме. В работе [5] излагается возможный способ решения проблемы. Авторами [1] предлагаются новые характеристики, вычисляемые исходя из средних скоростей в квадрантах изображения. Алгоритмы могут использоваться для вычисления как глобальных, так и локальных характеристик видео: они применяются для всего изображения, а также отдельно для каждой прямоугольной области, содержащей движущийся объект.
Программа позволяет выделять значительные по размеру движущиеся объекты на основании предположения о близкой направленности скоростей соседних точек объекта. Для выделенных областей рассматриваются минимальные охватывающие их прямоугольники. Помимо их размеров и расположения, вычисляется средний модуль скорости по всем точкам, принадлежащим объекту (для обеспечения возможности поиска видеофрагментов с требуемой интенсивностью движения объекта), и вычисляются средние значения скорости в четырех квадрантах области (для определения типа движения). В качестве дальнейшего этапа исследований рассматривается задача определения траектории движения объектов и простейших происходящих с объектами событий (пространственно-временное взаимодействие и т. п.).
После обработки объектов исследуются глобальные характеристики движения, для чего вычисляются средние значения вектора скорости в квадрантах изображения и средняя интенсивность движения сцены (без учета скоростей выделенных объектов).
Программой производится многоуровневая классификация видеофрагментов по типу движения на основании средних скоростей в квадрантах анализируемого изображения:
Выбирается наиболее близкая схема движения, определяющая для каждого квадранта одно из 8 основных направлений движения (с точностью до 45 градусов) или же отсутствие существенного движения. Первый вид классификации: схожими считаются фрагменты с одинаковыми идентификаторами их схемы движения. Несмотря на простоту, данная методика соответствует семантике многих реальных запросов. В частности, распознаваемы характерные функции камеры (приближение, удаление, сдвиг). Например, постепенному переходу к крупному плану будет соответствовать движение от центра к углам во всех четвертях.
Идея - разбиение всего множества фильмов на два класса: с выраженным общим направлением движения и без него. С человеческой точки зрения, в первый тип попадают фрагменты с крупным планом и движущимся центральным объектом, а также эпизоды, снятые движущейся камерой, или с движением фона. Во второй - все остальные фрагменты. Естественно, для фрагментов с доминирующим движением целесообразно хранить не только сам факт его наличия, но и направление, а также число квадрантов с этим направлением.
Поддерживается разбиение на набор классов, каждый из которых образован поворотом схемы с базовым идентификатором вокруг своей оси на 0 (базовая схема), p /2, p и 3p /2. Семантически класс соответствует некому целостному движению, показанному с разных сторон. Полностью сохраняются все типичные видеоэффекты.
Предложенная классификация обеспечивает разносторонний поиск видеофрагментов. При таком подходе запрос может задавать для искомого видеофрагмента: тип движения сцены или объекта - например, вращение или поступательное движение - с помощью полностью или частично определенной схемы движения, наличие некоторого доминирующего направления, количество квадрантов с ненулевыми скоростями, а также степень интенсивности движения. Понятие эквивалентности схем с точностью до поворотов позволит определять в запросе относительную схему движения.
Назначение данных разработки - обеспечение эффективного доступа к электронным хранилищам изображений и видеофильмов, сформированным на базе коллекций архивов, музеев, библиотек, а также частных коллекций, созданию которых способствует растущая популярность цифровых фотоаппаратов и кинокамер.
Одной из наиболее качественных на данный момент является система "Pro-Trainer" от компании "Sports Motion", предназначенная для обработки и анализа тренерами и другими профессионалами спортивных состязаний. Основными характерными чертами данной системы являются:
Функциональность - система "Pro-Trainer" имеет все функции, которые могут понадобится любому тренеру или инструктору от любительского спорта вплоть до профессионала олимпийского уровня.
Результативность - с помощью системы "Pro-Trainer" можно существенно облегчить поиск того изъяна в движениях, который мешает максимально использовать потенциал спортсмена или больного для скорейшего выздоровления.
Легкость в использовании - системы "Pro-Trainer" специально смоделированы так, чтобы их было легко научиться использовать.
Гибкость - системы работают для любого вида спорта и связанных с движением приложений, даже применимы для биомеханических исследований.
Применимость не только для спорта - системы "Pro-Trainer" также широко применяются в больничных учреждениях для реабилитации больных и травмированных спортсменов. Это возможно благодаря наличию таких функций, как определение траектории движения, углов между частями тела и наличие стоп-кадра.
Мультикамерный режим -системы поддерживают вид до четырех камер, так что изображение можно видеть под разными углами одновременно. Видео с каждой камеры показывается в отдельной части окна.
Стоп-кадр и замедленная съемка - 60 кадров в секунду, так что изображение не расплывается и нет никаких неясных моментов.
Возможность рисования прямо на кадрах дает тренеру, инструктору или терапевту сделать кадры более наглядными для последующего объяснения или анализа. Есть также функция блокнота, которая позволяет снабжать каждый кадр пояснениями.
Ясность и детализация - с помощью "Pro-Trainer" можно увидеть малейшие движения рук, ног, изменение наклона тела и т.д., и всё это будет ясно видно на каждом кадре с четкими деталями.
Таким образом, система "Pro-Trainer" совмещает в себе использование новейших достижений в анализе видеопотоков с простотой и легкостью освоения и использования системы. При разработке система "Pro-Trainer" использовались как возможности библиотек DirectShow для анализа и обработки изображений, так и собственные библиотеки. Все это приводит к универсальности системы, которую можно использовать практически для любого вида спорта.
Также стоит отметить, что алгоритмы обнаружения событий в видеопотоке оказали сильное влияние на развитие автоматизированных систем видеонаблюдения. Одной из наиболее совершенных систем интеллектуального анализа видеоданных является IVMD 1.0 (Intelligent Video Motion Detector), предназначенный для автоматизированной обработки видеоданных по различным алгоритмам и обнаружения несанкционированных событий в зоне наблюдения. Кроме мощного аппарата анализа видеопотока, система также снабжена удобным графическим интерфейсом, позволяющим настраивать каждую зоны детектирования индивидуально в зависимости от ее чувствительности. Также применяется корректировка перспективных искажений с использованием настройки трехмерной 3D-сетки. Кроме того, применятся метод калибровки изображений с камеры для точного измерения размеров объекта. Детектирование осуществляется с учетом размера и скорости объекта. Для этого используется специальный фильтр. В качестве критерия тревоги также возможны направления движения (в определенную сторону или двунаправленное движение), а также статистические данные движения объекта (количество каких-либо действий, удовлетворяющих установленным критериям).
IVMD имеет функцию адаптации к внешним условиям, таким как снег, дождь, падающие листья и т.д. Технология детектирования основана на поэтапной обработке изображений: сначала оценивается изменение пикселов, затем анализируется текстура изображения и лишь потом оценивается реальное движение объекта в кадре.
Все движущиеся объекты высвечиваются на изображении в зависимости от того, должна ли быть включена тревога в соответствии с заданными критериями или нет. "Желтые" движущиеся объекты не вызывают срабатывание тревоги, "красные"- тревога..
Дополнительно, каждая зона детектирования, представлена в системе собственным информационным битом, и все зоны комбинируются в общую тревогу движения. Каждый бит тревоги представлен в графическом что позволяет разграничивать тревоги по приоритетам (приоритетные зоны или приоритетные критерии), а также создавать различные сценарии получения общей тревоги.
Система может отслеживать такие характеристики объектов, как размер объекта, скорость объекта, вхождение, нахождение внутри и покидание зоны, настройка времени задержки и повторного срабатывания, назначение направления и угла движения для входа и покидания активной зоны (независимо для каждого случая), перекрестное сравнение кадров с опорным кадром по заданному количеству фрагментов опорного кадра.
Все это делает систему IVMD одной из наиболее совершенных автоматизированных систем видеонаблюдения.
Задача обнаружения движущихся объектов была поставлена довольно давно, но в силу своей специфики она до сих пор не имеет однозначного решения.
Во-первых, условия обнаружения могут быть различны. Например, если иметь дело с бинарным чёрно-белым изображением, то задача существенно упрощается по сравнению со случаем, когда на вход поступают полноцветные растры с плавными переходами цвета от одного оттенка к другому. Изображение может поступать со статично расположенной камеры, таким образом, все кадры будут иметь приблизительно одинаковый фон с возможными отличиями уровня освещения. С другой стороны, камера, расположенная на движущемся объекте, может снимать другой, неподвижный относительно неё объект.
Уровень шума может существенно варьировать. Природные явления, такие, как дождь, снег, туман, ветер и т.д. могут вносить заметный элемент колебаний в изначально неподвижную сцену. Всё это делает алгоритмы, отлично работающие в одних условиях, совершенно непригодными для других.
От алгоритмов обнаружения и анализа движения обычно требуется устойчивость работы в широком диапазоне существенно различающихся внешних условий. В общем случае требования к подобным алгоритмам выглядят следующим образом.
Рассмотрим подробнее алгоритмы обнаружения движущихся объектов:
Вычисление межкадровой разности является очень распространённым методом первичного обнаружения движения, после выполнения которого, вообще говоря, уже можно сказать, присутствует ли в потоке кадров движение. Однако, видеокадры должны быть предварительно обработаны перед вычислением разности между ними.
Алгоритм вычисления межкадровой разности двух кадров для случая обработки цветного видео в формате RGB выглядит следующим образом:
Таким образом, на выходе алгоритма формируется двоичная маска, одному элементу которой соответствуют три компоненты цвета соответствующего пикселя исходных двух кадров. Единицы в маске располагаются в областях, где, возможно, присутствует движение, однако на данном этапе могут быть и ложные срабатывания отдельных элементов маски, ошибочно установленных в 1. В качестве двух входных кадров могут использоваться два последовательных кадра из потока, однако возможно использование кадров с большим интервалом, например, равным 1-3 кадра. Чем больше такой интервал, тем выше чувствительность детектора к мало подвижным объектам, которые испытывают лишь крайне малый сдвиг за один кадр и могут отсекаться, будучи отнесёнными к шумовой составляющей изображения.
Недостатком такого метода является фиксация шума аппаратуры при регистрации данных. Шум неизбежно появляется при работе любой из современных камер, поэтому с ним необходимо бороться отдельно.
Достоинством данного метода является простота и нетребовательность к вычислительным ресурсам. Метод широко применялся ранее по причине того, что в распоряжении разработчиков не было достаточных вычислительных мощностей. Трудоёмкость алгоритма имеет порядок O(n) и осуществляется всего за один проход, что очень важно для растров большой размерности.
Описывая метод межкадровых попиксельных разностей с построением маски движения, в качестве двух входных кадров мы задавали либо два соседних кадра, либо два кадра, взятых с небольшим интервалом. Однако использование этого метода оставляет возможность вычислять разность с некоторым кадром, который бы содержал исключительно неподвижные области фона (базовый кадр). Такой подход дал бы нам существенное увеличение вероятности обнаружить любой объект, как самый медленный, так и быстрый, причём именно в той точке, в которой он находился в данный момент. Иначе данный метод называется методом вычитания или сегментации фона.
Работа метода полностью аналогична работе алгоритма межкадровой разности с той лишь разницей, что разность вычисляется между текущим и базовым кадром. Большой проблемой здесь является способ построения базового кадра, поскольку он должен обладать несколькими свойствами:
Существует два подхода к построению базового кадра.
Первый основан на кумулятивном его накоплении с использованием всех кадров потока. При таком способе построения базовый кадр неизбежно содержит элементы движущихся объектов, однако при вычислении разности между текущим и базовым кадром различия в интенсивности соответствующих пикселей, принадлежащих движущемуся объекту, всё же являются значительным и позволяют обнаружить движение. Плюсом такого способа является его простота. Однако при вычислении разности необходимо использовать дополнительные методы шумоподавления, поскольку порог сравнения при построении маски движения в данном случае не может быть высоким (в силу специфики базового кадра). В противном случае движение будет просто упущено, а при небольших значениях порога маска движения будет неизбежно фиксировать большое количество пикселей шума.
Второй подход выглядит более интеллектуальным, поскольку при его использовании базовый кадр строится исключительно из неподвижных областей, взятых с каждого из текущих кадров. Для этого на входе алгоритма необходимо иметь выходные данные детектора движущихся объектов от обработки предыдущего кадра. Используя эту информацию, алгоритм помечает области, где на предыдущем кадре были обнаружены движущиеся объекты, после чего при попиксельном копировании текущего кадра в базовый пиксели помеченных областей пропускаются. Таким образом, базовый кадр никогда не содержит никаких элементов движущихся объектов, что достигается ценой сравнительно небольшого усложнения алгоритма.
Возможен и третий подход, основанный на обновлении базового кадра текущим в те моменты, когда на текущем кадре нет движения. Однако в силу очень ограниченной применимости такого подхода (лишь для случаев малоподвижных сцен, когда само по себе движение в кадре - исключительный случай) мы его не рассматриваем.
Математическая морфология представляет собой анализ изображения с точки зрения его формы. Работа алгоритмов, основанных на применении данного подхода, связана с выполнением над изображением ряда преобразований, изменяющих форму объектов, содержащихся на изображении.
Математическая морфология применяется в различных системах, имеющих дело с обработкой изображений, на разных этапах и для достижения различных целей:
Операции математической морфологии могут производиться над цветными, чёрно-белыми изображениями и изображениями в оттенках серого. Для этих трёх случаев формально они определяются несколько по-разному. Рассмотрим случай бинарных чёрно-белых растров. Такой выбор сделан по той причине, что применение операций математической морфологии на данном этапе преследует цель дополнительной фильтрации шума в маске движения. Поскольку маска движения представляет собой растр, состоящий из нулей и единиц, нам достаточно ограничиться рассмотрением именно случая работы с бинарными изображениями.
В основе базовых операций математической морфологии для бинарных изображений лежат операции из теории множеств. Для начала рассмотрим две операции: расширение (dilation) и эрозию (erosion). Действие операции расширения заключается в увеличении площади объекта, эрозии - наоборот, в её уменьшении. Величина и способ изменения площади объекта зависит от выбора структурирующего элемента.
Структурирующий элемент представляет собой матрицу небольшой размерности (обычно 3х3), а его действие аналогично действию ядра свёртки в операциях свёртки.
На основе расширения и эрозии определяются ещё две операции. Это открытие (opening) и закрытие (closing).
Из большого числа операций математической морфологии понадобится лишь операция открытия, применение которой позволит дополнительно отфильтровать шум в двоичной маске движения.
Трудоёмкость алгоритма близка к трудоёмкости алгоритма свёртки и для небольшого размера структурирующего элемента, аналогично случаю с ядром свёртки небольшой размерности, имеет порядок O(n).
Определим понятие объекта с точки зрения детектора движения. Оно будет несколько отличаться от того, что человек привык понимать под объектом, воспринимая глазом окружающие его предметы.
Выделяя объекты на изображении, человеческий глаз работает в связке с головным мозгом, который на текущий момент уже хранит достаточно информации о типах, форме, линейных размерах, цвете и прочих характеристиках, присущих тем или иным объектам, с которыми человек сталкивался ранее. Таким образом, наряду с выделением объектов сцены, человеческий мозг выполняет процедуру их распознавания, поэтому человек без труда различает известные ему объекты.
Работа по выделению объектов детектором движения, основанным на алгоритме вычисления попиксельных разностей между кадрами, начинается с анализа маски движения. Реальным объектам в ней обычно соответствуют пиксели (или минзоны), которые образуют связные группы, поэтому логично определить объект с точки зрения детектора движения как группу связных пикселей в маске движения. Такому объекту соответствуют несколько параметров:
Поскольку детектор обнаруживает только движущиеся объекты, эта группа пикселей и соответствующий ей объект с поступлением на вход детектора новых кадров будут испытывать смещение, поэтому кроме параметров, перечисленных выше, можно ввести ещё несколько:
Выделение объектов происходит при последовательном обходе пикселей маски движения. Если в маске движения обнаружена единица, запускается процедура поиска пикселей, связных с данным, которым также соответствуют единицы в маске движения. Найденные пиксели помечаются, чтобы избежать повторного их обнаружения. Алгоритм поиска может быть рекурсивным или волновым.
Алгоритм рекурсивного поиска представляет собой простую процедуру, на вход которой поступает текущий пиксель. Внутри процедуры для всех соседей данного пикселя осуществляется проверка, соответствует ли каждому из них единица в маске движения и не является ли он уже принадлежащим какому-либо объекту. Если соседний пиксель проходит проверку, то он становится текущим и для него рекурсивно запускается процедура поиска. Соседи пикселя могут выбираться по принципу 4-связности или 8-связности. В первом случае проверяется 4 соседа, располагающихся выше, ниже, слева и справа от текущего пикселя. Во втором случае проверка затрагивает все 8 пикселей маски окружающих текущий пиксель.
Недостатком рекурсивного поиска является возможное переполнение стека при рекурсивном вызове процедуры поиска. Вероятность переполнения здесь велика, поскольку максимально возможное количество рекурсивных вызовов (в случае, если единицы будут заполнять всю маску движения) может достигать величины, близкой количеству пикселей.
Для случаев обработки изображений с высоким разрешением, например, 640х480 пикселей, процедура поиска может рекурсивно вызываться порядка 300 тысяч раз. Обычно эта величина на несколько порядков меньше, однако чтобы гарантировано избежать переполнения стека, рекомендуется ограничивать возможный размер объекта, а значит и глубину рекурсии, сверху или использовать волновой алгоритм поиска.
Волновой метод получил такое название по той причине, что каждая из итераций его работы напоминает волну, поднявшуюся на поверхности воды от упавшего в неё камня.
Волны расходятся от точки падения камня радиально в виде концентрических окружностей. Аналогичным образом происходит обход пикселей маски и в алгоритме волнового поиска. Из точки, где расположен текущий пиксель (первый найденный пиксель, которому соответствует единица в маске движения), запускается волна во всех направлениях, число которых зависит от выбранного типа связности (4-связный, 8-связный). Для всех пикселей, которые достигаются волной в текущей итерации, производится проверка условий наличия единицы в маске движения и отсутствия пометки о вхождении в другой объект. Все пиксели, успешно прошедшие проверку, заносятся в массив. На следующей итерации волна запускается из всех пикселей, содержащихся в массиве. Массив очищается, и в него заносятся пиксели, вновь достигнутые волной. Все обработанные пиксели помечаются как вошедшие в текущую группу. При реализации данного алгоритма удобно иметь массив переменной длины для помещения в него пикселей волны на текущей итерации, либо заранее вычислять максимально допустимый размер этого массива.
Волновой поиск идёт одновременно во всех возможных направлениях, определяемых выбранным типом связности, что существенно сокращает количество итераций поиска и затраты памяти на хранение промежуточных результатов между итерациями. Алгоритм выполняется до тех пор, пока на очередном шаге массив содержит хотя бы один пиксель, из которого запускается новая волна.
Функция взаимной корреляции двух изображений - функция, показывающая степень корреляции двух изображений. Обычно она используется для вычисления степени похожести областей на разных кадрах. Эта функция должна давать единственный максимум только для случая двух одинаковых изображений. Очень часто используется нормализованная функция взаимной корреляции.
Алгоритмы, использующие функцию корреляции, работают следующим образом.
Сначала они находят несколько значений функции, различным образом накладывая на один растр прямоугольник, взятый с другого растра. Затем из полученных значений выбирают максимальное. Если наилучшее значение достаточно близко к единице, значит, на первом растре обнаружен именно тот объект, который попал в "коррелирующий" прямоугольник, взятый на втором растре. Степень близости значения функции корреляции к единице - параметр, выбирая значение которого, можно добиться оптимального соотношения количества ошибок ложного обнаружения и необнаружения вообще.
Термин трассирование подразумевает отслеживание движущегося объекта и значений его параметров в течение всего времени его пребывания в кадре. При правильном трассировании объекта появляется возможность просмотра траектории движения объекта с любым уровнем детализации (с точностью до кадра, до 3, 5 и т.д. кадров). Такая возможность обеспечивается сохранением положения центральной точки объекта на каждом из кадров в специальном массиве, который введен для этой цели при определении параметров для каждого из движущихся объектов. Алгоритмы, трассирующие движущиеся объекты, не должны путать один объект с другим, терять объект, если он остановился на небольшой промежуток времени или скрылся за каким-либо препятствием (например, человек, скрывшийся за деревом), а потом появился вновь. Для этих целей великолепно подходит применение нормализованной функции взаимной корреляции, описанной в предыдущем параграфе. Она помогает сравнить объект с одного из предыдущих кадров с объектом, обнаруженным на вновь полученном кадре и сделать вывод об их похожести. Даже если объект, который можно было посчитать исчезнувшим после того, как он пропал за каким-либо препятствием, перестал обнаруживаться, применяя алгоритм вычисления функции корреляции можно обнаружить его снова на одном из последующих кадров и продолжить трассировку, взяв параметры объекта в момент его последнего обнаружения и скорректировав их по текущему кадру. Это очень важно для построения неразрывной траектории движения.
При вычислении функции корреляции с целью обнаружения на текущем кадре объекта, обнаруженного ранее, используются только те пиксели изображения, которым в маске движения соответствуют единицы. В противном случае в формулу для вычисления функции корреляции могут попасть значения цветов пикселей, лежащих внутри прямоугольной области, но за пределами объекта, а эти пиксели совсем не обязательно должны коррелировать друг с другом, следовательно, значение функции корреляции в этом случае уменьшится. А если оно станет меньше выбранного порога похожести, алгоритм может ошибочно посчитать данную прямоугольную область растра непохожей на объект, с которым производится сравнение, даже если на самом деле это не так.
Очевидно, что вычислять функцию корреляции для двух объектов не имеет смысла, если линейные размеры соответствующих им прямоугольников существенно различаются, поскольку и так очевидно, что это разные объекты. Также бессмысленно, например, искать в правом нижнем углу текущего кадра объект обнаруженный в левом верхнем углу предыдущего кадра, поскольку никакой интересующий нас объект не может за такое короткое время так существенно изменить своё местоположение. Такие допущения могут существенно сократить затраты на трассирование, в общем случае включающие вычисление функции корреляция каждого объекта с каждым - O(n2). Кроме того, для объекта, испытавшего крайне малое смещение на соседних кадрах можно вообще не вычислять значения функции корреляции. Ведь ещё до выполнения данной операции становится очевидным, что два отпечатка в одной и той же области маски движения на соседних кадрах принадлежат одному и тому же объекту.
Разрабатываемую систему можно разделить на три модуля: модуль обработки видеоинформации, модуль анализа кадров и модуль построения визуальной модели.
Первый модуль решает задачу перевода имеющейся видеоинформации в графическую базу, хранящуюся на жестком диске компьютера. Следует заметить, что для того, чтобы графическая база занимала на жестком диске компьютера меньше места, чем имеющаяся видеоинформация необходимо применять алгоритмы сжатия графической информации с потерями.
Второй модуль решает задачу обработки кадров, выбора из всего видеопотока уже представленного в виде графической базы, требуемых нам событий. То есть происходит удаление всех частей изображения, не несущих важной для нас информации.
Третий модуль решает задачу построения по выделенным отдельным событиям траекторий и закономерностей перемещения интересующих нас объектов.
Алгоритм выделения перемещающихся объектов основан на последовательном вычитании кадров, содержащих различные моменты съемки. В результате получаем выделенные перемещающиеся объекты. Однако, у этого метода есть недостаток - получаем вместо каждого объекта две его копии - та месте прежней позиции и на месте новой позиции объекта. Поэтому, в разрабатываемом приложении будет использоваться алгоритм вычитания из базового кадра. Базовый кадр - это кадр, снятый с того же самого объекта, но без движущихся объектов.
Алгоритм:
Приведем участок программы, выполняющий вычитание двух изображений, приводящее к выделению движущихся объектов
void OnSub()
{
int i,j;
int r,g,b;
for(i=0;i<Head.Height;i++)
for(j=0;j<Head.Width;j++)
{
r=abs(GetRValue(BitMap[i][j])-GetRValue(BitMap1[i][j]));
g=abs(GetGValue(BitMap[i][j])-GetGValue(BitMap1[i][j]));
b=abs(GetBValue(BitMap[i][j])-GetBValue(BitMap1[i][j]));
if(r<eps && g<eps && b<eps) BitMap[i][j]=RGB(255,255,255);
}
BmpO=1;
Invalidate();
}
Подводя итог вышесказанному, следует отметить, что, хотя и имеется большое количество разработанных алгоритмов, отрасль все еще является плохо исследованной. При разработке системы будут учитываться большинство имеющихся методов, необходимых для обнаружения движения, выделения объектов и построения их траекторий.