Алгоритмы и методы поиска событий в видеопотоке

Введение
В наше время наблюдается постоянный рост объема обрабатываемой информации. Однако, с увеличением объемов информации, становится все труднее с ней работать, кроме того, появляются новые виды информации, эффективных алгоритмов обработки которой еще не существует. К таким видам информации можно отнести и видеопоток. Еще сравнительно недавно, количество предприятий, постоянно в своей работе использующих видеоинформацию было мало, также как и объем этой информации, однако наблюдается тенденция как к увеличению объемов видеоинформации, так и к увеличению спектра ее применения. С увеличением объемов видеоинформации, отражающей реальные события, происходящие в мире, соответственно увеличивается и время на ее обработку и анализ. Кроме этого, довольно часто, видеоинформация содержит события, для анализа которых требуется привлечение высокооплачиваемых специалистов, способных грамотно и квалифицированно охарактеризовать подобные события. В связи с этим возникает проблема: «Как можно уменьшить временные и материальные затраты, для того чтобы проанализировать видеоинформацию, полученную из различных источников, таких как телевидение, интернет, или домашнее видео?» Для решения данной проблемы необходимо представить видеопоток в виде графической базы данных, и построить такой алгоритм поиска событий, при выполнении которого ЭВМ будет автоматически находить, и анализировать события, содержащиеся в этом потоке. Заметим, что выполнение подобного преобразования может усложниться, в случае, если анализ необходимо проводить в реальном времени, например, одновременно с трансляцией изображения по телевидению. В данном случае, время, отведенное на выполнение алгоритма поиска событий, должно быть ограничено, и, соответственно, увеличены требования к производительности ЭВМ.

Актуальность
Данная работа решает актуальную задачу, состоящую в развитии имеющихся идей решения проблемы распознавания событий в видеопотоке и использования распознавания в прикладных задачах. В данной работе получит дальнейшее развитие идея, состоящая в отслеживании происходящих в видеопотоке событий при помощи вычитания текущего и базового кадров.

Цель и задачи работы:
Цель – изучив имеющиеся методы решения задачи распознавания событий в видеопотоке указать на их недостатки и предложить методы их устранения. Задача работы – увеличить быстродействие метода, основанного на вычитании кадров, с возможным увеличением требуемой для решения задачи оперативной памяти.

Предполагаемая научная новизна и практическая ценность:
Разрабатываемая система видеомониторинга футбольного матча должна быть в состоянии отслеживать перемещения игроков в ходе матча, а также давать статистику по отдельным игрокам. Усовершенствованию будет подвергнут метод выделения фигур игроков – каждый кадр предполагается разделять на два, содержащих, соответственно игроков разных команд, что позволит уменьшить количество конфликтных ситуаций и ускорить работу программы.

Национальные исследования и разработки:
Задача обнаружения движущихся объектов была поставлена довольно давно, но в силу своей специфики она до сих пор не имеет однозначного решения. Во-первых, условия обнаружения могут быть различны. Например, если иметь дело с бинарным чёрно-белым изображением, то задача существенно упрощается по сравнению со случаем, когда на вход поступают полноцветные растры с плавными переходами цвета от одного оттенка к другому. Изображение может поступать со статично расположенной камеры, таким образом, все кадры будут иметь приблизительно одинаковый фон с возможными отличиями уровня освещения. С другой стороны, камера, расположенная на движущемся объекте, может снимать другой, неподвижный относительно неё объект. Уровень шума может существенно варьировать. Природные явления, такие, как дождь, снег, туман, ветер и т.д. могут вносить заметный элемент колебаний в изначально неподвижную сцену. Всё это делает алгоритмы, отлично работающие в одних условиях, совершенно непригодными для других. От алгоритмов обнаружения и анализа движения обычно требуется устойчивость работы в широком диапазоне существенно различающихся внешних условий. В общем случае требования к подобным алгоритмам выглядят следующим образом.

1. Низкая вычислительная сложность и работа в реальном времени.
2. Устойчивое обнаружение в разное время суток при наличии искусственного освещения.
3. Устойчивая работа в любое время года при любых погодных условиях.

Рассмотрим подробнее инструментарий, который планируется использовать при разработке приложения:

Межкадровая разность
Вычисление межкадровой разности является очень распространённым методом первичного обнаружения движения, после выполнения которого, вообще говоря, уже можно сказать, присутствует ли в потоке кадров движение. Однако, видеокадры должны быть предварительно обработаны перед вычислением разности между ними. Алгоритм вычисления межкадровой разности двух кадров для случая обработки цветного видео в формате RGB выглядит следующим образом:

1. На вход алгоритма поступают два видео кадра, представляющие собой две последовательности байт в формате RGB.
2. Производится вычисление попиксельных межкадровых разностей.
3. Для каждого пикселя вычисляется среднее значение между значениями трёх компонент цвета.
4. Среднее значение сравнивается с заданным порогом. В результате сравнения формируется двоичная маска.

Таким образом, на выходе алгоритма формируется двоичная маска, одному элементу которой соответствуют три компоненты цвета соответствующего пикселя исходных двух кадров. Единицы в маске располагаются в областях, где, возможно, присутствует движение, однако на данном этапе могут быть и ложные срабатывания отдельных элементов маски, ошибочно установленных в 1. В качестве двух входных кадров могут использоваться два последовательных кадра из потока, однако возможно использование кадров с большим интервалом, например, равным 1-3 кадра. Чем больше такой интервал, тем выше чувствительность детектора к мало подвижным объектам, которые испытывают лишь крайне малый сдвиг за один кадр и могут отсекаться, будучи отнесёнными к шумовой составляющей изображения.
Недостатком такого метода является фиксация шума аппаратуры при регистрации данных. Шум неизбежно появляется при работе любой из современных камер, поэтому с ним необходимо бороться отдельно.
Достоинством данного метода является простота и нетребовательность к вычислительным ресурсам. Метод широко применялся ранее по причине того, что в распоряжении разработчиков не было достаточных вычислительных мощностей. Трудоёмкость алгоритма имеет порядок O(n) и осуществляется всего за один проход, что очень важно для растров большой размерности.

Базовый кадр
Описывая метод межкадровых попиксельных разностей с построением маски движения, в качестве двух входных кадров мы задавали либо два соседних кадра, либо два кадра, взятых с небольшим интервалом. Однако использование этого метода оставляет возможность вычислять разность с некоторым кадром, который бы содержал исключительно неподвижные области фона (базовый кадр). Такой подход дал бы нам существенное увеличение вероятности обнаружить любой объект, как самый медленный, так и быстрый, причём именно в той точке, в которой он находился в данный момент. Иначе данный метод называется методом вычитания или сегментации фона.
Работа метода полностью аналогична работе алгоритма межкадровой разности с той лишь разницей, что разность вычисляется между текущим и базовым кадром. Большой проблемой здесь является способ построения базового кадра, поскольку он должен обладать несколькими свойствами:

• Если кадр представляет собой кадр реального изображения, он должен минимально отстоять по времени от текущего кадра.
• Если базовый кадр подготавливается искусственно, он должен содержать минимальное количество движущихся элементов, иначе неизбежны ложные срабатывания на объекты, которых на текущем кадре уже нет, однако базовый кадр содержит какие-то их элементы.
• Минимальный уровень шума. Перед обновлением базового кадра необходимо проводить фильтрацию.

Существует два подхода к построению базового кадра.
Первый основан на кумулятивном его накоплении с использованием всех кадров потока. При таком способе построения базовый кадр неизбежно содержит элементы движущихся объектов, однако при вычислении разности между текущим и базовым кадром различия в интенсивности соответствующих пикселей, принадлежащих движущемуся объекту, всё же являются значительным и позволяют обнаружить движение. Плюсом такого способа является его простота. Однако при вычислении разности необходимо использовать дополнительные методы шумоподавления, поскольку порог сравнения при построении маски движения в данном случае не может быть высоким (в силу специфики базового кадра). В противном случае движение будет просто упущено, а при небольших значениях порога маска движения будет неизбежно фиксировать большое количество пикселей шума.
Второй подход выглядит более интеллектуальным, поскольку при его использовании базовый кадр строится исключительно из неподвижных областей, взятых с каждого из текущих кадров. Для этого на входе алгоритма необходимо иметь выходные данные детектора движущихся объектов от обработки предыдущего кадра. Используя эту информацию, алгоритм помечает области, где на предыдущем кадре были обнаружены движущиеся объекты, после чего при попиксельном копировании текущего кадра в базовый пиксели помеченных областей пропускаются. Таким образом, базовый кадр никогда не содержит никаких элементов движущихся объектов, что достигается ценой сравнительно небольшого усложнения алгоритма.
Возможен и третий подход, основанный на обновлении базового кадра текущим в те моменты, когда на текущем кадре нет движения. Однако в силу очень ограниченной применимости такого подхода (лишь для случаев малоподвижных сцен, когда само по себе движение в кадре – исключительный случай) мы его не рассматриваем.

Математическая морфология
Математическая морфология представляет собой анализ изображения с точки зрения его формы. Работа алгоритмов, основанных на применении данного подхода, связана с выполнением над изображением ряда преобразований, изменяющих форму объектов, содержащихся на изображении. Математическая морфология применяется в различных системах, имеющих дело с обработкой изображений, на разных этапах и для достижения различных целей:

• улучшение визуальных характеристик изображения (яркость, контрастность и пр.)
• восстановление испорченных изображений, например, реставрация фотоснимков.
• обнаружения контуров.
• снижение уровня шума.

Операции математической морфологии могут производиться над цветными, чёрно-белыми изображениями и изображениями в оттенках серого. Для этих трёх случаев формально они определяются несколько по-разному. Рассмотрим случай бинарных чёрно-белых растров. Такой выбор сделан по той причине, что применение операций математической морфологии на данном этапе преследует цель дополнительной фильтрации шума в маске движения. Поскольку маска движения представляет собой растр, состоящий из нулей и единиц, нам достаточно ограничиться рассмотрением именно случая работы с бинарными изображениями.
В основе базовых операций математической морфологии для бинарных изображений лежат операции из теории множеств. Для начала рассмотрим две операции: расширение (dilation) и эрозию (erosion). Действие операции расширения заключается в увеличении площади объекта, эрозии – наоборот, в её уменьшении. Величина и способ изменения площади объекта зависит от выбора структурирующего элемента. Структурирующий элемент представляет собой матрицу небольшой размерности (обычно 3х3), а его действие аналогично действию ядра свёртки в операциях свёртки.
На основе расширения и эрозии определяются ещё две операции. Это открытие (opening) и закрытие (closing).
Из большого числа операций математической морфологии понадобится лишь операция открытия, применение которой позволит дополнительно отфильтровать шум в двоичной маске движения.
Трудоёмкость алгоритма близка к трудоёмкости алгоритма свёртки и для небольшого размера структурирующего элемента, аналогично случаю с ядром свёртки небольшой размерности, имеет порядок O(n).

Выделение объектов
Определим понятие объекта с точки зрения детектора движения. Оно будет несколько отличаться от того, что человек привык понимать под объектом, воспринимая глазом окружающие его предметы.
Выделяя объекты на изображении, человеческий глаз работает в связке с головным мозгом, который на текущий момент уже хранит достаточно информации о типах, форме, линейных размерах, цвете и прочих характеристиках, присущих тем или иным объектам, с которыми человек сталкивался ранее. Таким образом, наряду с выделением объектов сцены, человеческий мозг выполняет процедуру их распознавания, поэтому человек без труда различает известные ему объекты. Работа по выделению объектов детектором движения, основанным на алгоритме вычисления попиксельных разностей между кадрами, начинается с анализа маски движения. Реальным объектам в ней обычно соответствуют пиксели (или минзоны), которые образуют связные группы, поэтому логично определить объект с точки зрения детектора движения как группу связных пикселей в маске движения. Такому объекту соответствуют несколько параметров:

1. Линейные размеры минимального прямоугольника (в дальнейшем просто прямоугольник), который можно описать около пикселей группы.
2. Координаты (x,y) центральной точки прямоугольника. Будем считать данную точку центральной точкой объекта.
3. Количество пикселей, входящих в группу.
4. Область маски движения, лежащая внутри прямоугольника.
5. Область текущего кадра, лежащая внутри прямоугольника.

   Поскольку детектор обнаруживает только движущиеся объекты, эта группа пикселей и соответствующий ей объект с поступлением на вход детектора новых кадров будут испытывать смещение, поэтому кроме параметров, перечисленных выше, можно ввести ещё несколько:

6. Вектор, описывающий направление и скорость движения объекта.
7. Массив, содержащий координаты центра объекта на предыдущих кадрах.
8. Время жизни объекта, измеряемое в количестве кадров.

Выделение объектов происходит при последовательном обходе пикселей маски движения. Если в маске движения обнаружена единица, запускается процедура поиска пикселей, связных с данным, которым также соответствуют единицы в маске движения. Найденные пиксели помечаются, чтобы избежать повторного их обнаружения. Алгоритм поиска может быть рекурсивным или волновым.
Алгоритм рекурсивного поиска представляет собой простую процедуру, на вход которой поступает текущий пиксель. Внутри процедуры для всех соседей данного пикселя осуществляется проверка, соответствует ли каждому из них единица в маске движения и не является ли он уже принадлежащим какому-либо объекту. Если соседний пиксель проходит проверку, то он становится текущим и для него рекурсивно запускается процедура поиска. Соседи пикселя могут выбираться по принципу 4-связности или 8-связности. В первом случае проверяется 4 соседа, располагающихся выше, ниже, слева и справа от текущего пикселя. Во втором случае проверка затрагивает все 8 пикселей маски окружающих текущий пиксель.
Недостатком рекурсивного поиска является возможное переполнение стека при рекурсивном вызове процедуры поиска. Вероятность переполнения здесь велика, поскольку максимально возможное количество рекурсивных вызовов (в случае, если единицы будут заполнять всю маску движения) может достигать величины, близкой количеству пикселей.
Для случаев обработки изображений с высоким разрешением, например, 640х480 пикселей, процедура поиска может рекурсивно вызываться порядка 300 тысяч раз. Обычно эта величина на несколько порядков меньше, однако чтобы гарантировано избежать переполнения стека, рекомендуется ограничивать возможный размер объекта, а значит и глубину рекурсии, сверху или использовать волновой алгоритм поиска.
Волновой метод получил такое название по той причине, что каждая из итераций его работы напоминает волну, поднявшуюся на поверхности воды от упавшего в неё камня.
Волны расходятся от точки падения камня радиально в виде концентрических окружностей. Аналогичным образом происходит обход пикселей маски и в алгоритме волнового поиска. Из точки, где расположен текущий пиксель (первый найденный пиксель, которому соответствует единица в маске движения), запускается волна во всех направлениях, число которых зависит от выбранного типа связности (4-связный, 8-связный). Для всех пикселей, которые достигаются волной в текущей итерации, производится проверка условий наличия единицы в маске движения и отсутствия пометки о вхождении в другой объект. Все пиксели, успешно прошедшие проверку, заносятся в массив. На следующей итерации волна запускается из всех пикселей, содержащихся в массиве. Массив очищается, и в него заносятся пиксели, вновь достигнутые волной. Все обработанные пиксели помечаются как вошедшие в текущую группу. При реализации данного алгоритма удобно иметь массив переменной длины для помещения в него пикселей волны на текущей итерации, либо заранее вычислять максимально допустимый размер этого массива.
Волновой поиск идёт одновременно во всех возможных направлениях, определяемых выбранным типом связности, что существенно сокращает количество итераций поиска и затраты памяти на хранение промежуточных результатов между итерациями. Алгоритм выполняется до тех пор, пока на очередном шаге массив содержит хотя бы один пиксель, из которого запускается новая волна.

Функция корреляции
Функция взаимной корреляции двух изображений – функция, показывающая степень корреляции двух изображений. Обычно она используется для вычисления степени похожести областей на разных кадрах. Эта функция должна давать единственный максимум только для случая двух одинаковых изображений. Очень часто используется нормализованная функция взаимной корреляции. Максимальным значением функции при полном совпадении первого растра с прямоугольником на втором растре будет единица.
Алгоритмы, использующие функцию корреляции, работают следующим образом.
Сначала они находят несколько значений функции, различным образом накладывая на один растр прямоугольник, взятый с другого растра. Затем из полученных значений выбирают максимальное. Если наилучшее значение достаточно близко к единице, значит, на первом растре обнаружен именно тот объект, который попал в «коррелирующий» прямоугольник, взятый на втором растре. Степень близости значения функции корреляции к единице – параметр, выбирая значение которого, можно добиться оптимального соотношения количества ошибок ложного обнаружения и необнаружения вообще.

Трассирование
Термин трассирование подразумевает отслеживание движущегося объекта и значений его параметров в течение всего времени его пребывания в кадре. При правильном трассировании объекта появляется возможность просмотра траектории движения объекта с любым уровнем детализации (с точностью до кадра, до 3, 5 и т.д. кадров). Такая возможность обеспечивается сохранением положения центральной точки объекта на каждом из кадров в специальном массиве, который введен для этой цели при определении параметров для каждого из движущихся объектов. Алгоритмы, трассирующие движущиеся объекты, не должны путать один объект с другим, терять объект, если он остановился на небольшой промежуток времени или скрылся за каким-либо препятствием (например, человек, скрывшийся за деревом), а потом появился вновь. Для этих целей великолепно подходит применение нормализованной функции взаимной корреляции, описанной в предыдущем параграфе. Она помогает сравнить объект с одного из предыдущих кадров с объектом, обнаруженным на вновь полученном кадре и сделать вывод об их похожести. Даже если объект, который можно было посчитать исчезнувшим после того, как он пропал за каким-либо препятствием, перестал обнаруживаться, применяя алгоритм вычисления функции корреляции можно обнаружить его снова на одном из последующих кадров и продолжить трассировку, взяв параметры объекта в момент его последнего обнаружения и скорректировав их по текущему кадру. Это очень важно для построения неразрывной траектории движения. При вычислении функции корреляции с целью обнаружения на текущем кадре объекта, обнаруженного ранее, используются только те пиксели изображения, которым в маске движения соответствуют единицы. В противном случае в формулу для вычисления функции корреляции могут попасть значения цветов пикселей, лежащих внутри прямоугольной области, но за пределами объекта, а эти пиксели совсем не обязательно должны коррелировать друг с другом, следовательно, значение функции корреляции в этом случае уменьшится. А если оно станет меньше выбранного порога похожести, алгоритм может ошибочно посчитать данную прямоугольную область растра непохожей на объект, с которым производится сравнение, даже если на самом деле это не так.
Очевидно, что вычислять функцию корреляции для двух объектов не имеет смысла, если линейные размеры соответствующих им прямоугольников существенно различаются, поскольку и так очевидно, что это разные объекты. Также бессмысленно, например, искать в правом нижнем углу текущего кадра объект обнаруженный в левом верхнем углу предыдущего кадра, поскольку никакой интересующий нас объект не может за такое короткое время так существенно изменить своё местоположение. Такие допущения могут существенно сократить затраты на трассирование, в общем случае включающие вычисление функции корреляция каждого объекта с каждым - O(n2). Кроме того, для объекта, испытавшего крайне малое смещение на соседних кадрах можно вообще не вычислять значения функции корреляции. Ведь ещё до выполнения данной операции становится очевидным, что два отпечатка в одной и той же области маски движения на соседних кадрах принадлежат одному и тому же объекту.

Полученные на данном этапе результаты описаны на рисунке 1.