АНАЛИЗ МЕТОДОВ ВЫДЕЛЕНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ НА ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЯХ С ШУМАМИ
В.А. Козлов, А.С. Потапов
УДК 004.932.2
АНАЛИЗ МЕТОДОВ ВЫДЕЛЕНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ НА ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЯХ С ШУМАМИ
В.А. Козлов, А.С. Потапов
Рассмотрены наиболее часто используемые методы выделения движущихся объектов применительно к видеопоследовательностям, полученным с бытовых камер в условиях присутствия шумов на изображениях. Выделены основные проблемы обработки таких видеопоследовательностей, описана невозможность применения классических методов и предложены пути улучшения качества выделения движущихся объектов. Ключевые слова: анализ движения, контур, выделение объектов, сегментация.
Введение
В последнее время при организации видеонаблюдения применяются преимущественно цифровые методы обработки и хранения информации. Цифровые технологии дают ряд преимуществ перед устаревшими методами аналоговой записи на пленку. Например, в среднем качестве средний жесткий диск может хранить объем информации, соответствующий видеозаписи в течение месяца, а также обеспечи-
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 3 (73)
39
АНАЛИЗ МЕТОДОВ ВЫДЕЛЕНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ …
вается быстрый доступ к любой части записи, что можно сделать из любой точки мира, если записывающий компьютер подключен к сети.
Компьютеры предоставляют широкие возможности по автоматической обработке изображений, которая все еще используются лишь в незначительной степени. Такие простые задачи, как выполнение записи только движений, имеют достаточно универсальные решения. Однако более сложные задачи, особенно из области компьютерного зрения, до сих пор не имеют общих решений, а предлагаемые алгоритмы, как правило, применимы только при соблюдении ряда условий и ограничений. В связи с этим на сегодняшний день данная область исследований представляет большой интерес как в научном, так и в прикладном плане. Одной из важных, но до конца не решенных подзадач является автоматическое выделение движущихся объектов, что является необходимым предварительным шагом при решении таких задач видеонаблюдения, как системы контроля доступа, удаление фона, ориентация роботов в пространстве, системы помощи водителям, распознавание лиц, облегчение восприятия сцены человеческим глазом и многих других.
В работе рассматривается вопрос выделения движущихся объектов на реальных видеопоследовательностях, полученных с бытовых видеокамер. Проведен сравнительный анализ существующих решений на базе методов выделения контура и области движущегося объекта, а также авторская модификация этих методов. Проанализировано быстродействие и качество результата в зависимости интенсивности шумов, типа сцены, характеристик захвата и оцифровки видео. Описаны трудности, возникающие при внедрении этих алгоритмов в реальные системы. Обосновывается несостоятельность существующих методов, предложены пути для улучшения качества результата, чтобы получить универсальный метод предварительной обработки информации в системах видеонаблюдения.
Подходы к выявлению движущихся объектов
Существует два основных класса методов выделения движущихся объектов: 1. путем анализа их границ (контуров); 2. путем анализа всей области объекта на кадрах [1–4].
Основной идеей методов первого класса является поиск отличий векторов оптического потока с последующим построением контуров движущихся объектов [1–4]. Методы второго класса, наоборот, основываются на группировании сходных векторов из оптического потока в области, которые подаются на выход алгоритма в качестве движущихся объектов [1–4]. Большинство классических методов анализируют не сами кадры видеопоследовательности, а оптический поток (поле видимых смещений пикселей изображений), построенный по этим кадрам.
Для сравнительного анализа построим данные методы на базе широко используемой в компьютерном зрении общедоступной библиотеки OpenCV, содержащей реализации для некоторых шагов исследуемых методов, таких как построение оптического потока, вычисление градиента и поиск контуров, а также простой и удобный интерфейс для работы с камерами и вывод результата на экран.
Для построения оптического потока будем использовать функции из библиотеки OpenCV, реализующие алгоритмы Хорна–Шанка (Horn–Schunck) [5, 6], Лукаса–Канадэ (Lucas–Kanade) [6, 7] и метод блочного сопоставления, описанный, в том числе, в работе [8], а также метод, разработанный авторами настоящей работы и представленный в [8].
Для построения контуров движущихся объектов будем выполнять следующие шаги: построение оптического потока одним из предложенных выше методов; вычисление градиента оптического потока; построение матрицы, каждая ячейка которой соответствует модулю градиента; нахождение контуров на основе бинаризованного поля модуля градиента.
Общая схема построения областей движущихся объектов будет включать следующие шаги: построение оптического потока одним из предложенных выше методов; сравнение вектора оптического потока в каждой точке кадра с векторами в соседних точках (срав-
нение ведется только с точками снизу и справа от текущей точки, поскольку сравнение с точками слева и сверху уже было выполнено при рассмотрении предыдущих точек); если векторы сходны, то точки объединяются в область или присоединяются к уже существующей области (для пометок областей их номера записываются в соответствующие ячейки кадра).
Таким образом, после однократного прохода по изображению получим разметку на области. В качестве функции похожести векторов оптического потока для рассматриваемых методов приемлемый результат дает использования следующего условия. Если модуль разности векторов меньше одной трети длины самого короткого, то вектора похожи. Данный критерий, хотя и выглядит эвристическим, дает хороший результат и является приемлемым при сравнении эффективности разных методов выделения движущихся объектов. Коэффициент эмпирически вытекает из спектра векторов оптического потока. Полное обоснование критерия и автоматический адаптивный выбор коэффициента предполагается получить в последующих работах.
40 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 3 (73)
В.А. Козлов, А.С. Потапов
Анализ характеристик методов выявления движущихся объектов
Проведем сравнение различных методов выявления движущихся объектов по критериям быстродействия, сложности реализации и качества достигаемого результата. Перечисленные характеристики важны, так как для обеспечения непрерывного видеонаблюдения требуется обработка изображений в масштабе реального времени. Однако достижение необходимого быстродействия не должно приводить к ухудшению вероятностей обнаружения объектов интереса. При всем этом для возможности легкого внедрения метода в любые проекты желательно иметь простую и очевидную реализацию.
Быстродействие. Основной вклад в вычислительную сложность рассматриваемых методов вносит вычисление оптического потока, так как даже линейные реализации имеют очень большой коэффициент. Все остальные шаги алгоритмов выделения движущихся объектов – группирование векторов, вычисление градиента, поиск контуров – требуют лишь нескольких операций на каждый пиксель изображения. Данные методы можно назвать весьма производительными, если не брать в расчет вычисление оптического потока, так как способ его вычисления зависит от поставленных задач, условий и целей. К тому же все современные компьютеры имеют несколько ядер, и оптический поток может независимо вычисляться на своем ядре, не мешая остальному анализу. При обработке каждого нового кадра на все прочие расчеты, кроме оптического потока, для стандартного размера кадра (VGA – 64×480) тратится не более 10–60 млн. тактов, что приблизительно равно 4–20 мс процессорного времени для ядра с частотой 3 ГГц. Производительность зависит от интенсивности и сложности движения на видеоряде, поэтому точную алгоритмическую сложность подсчитать не возможно. Например, для неподвижной сцены все алгоритмы дают быстрый ответ об отсутствии объектов, но чем больше в сцене мелких движений, тем больше ресурсов требуется для их поиска. Конечно же, например, для метода объединения областей несложно придумать кадры, оптический поток которых имеет шахматный порядок, и анализ таких кадров будет, как минимум, кубической сложности. Но на практике такое не встречается, а движущиеся объекты имеют сгруппированные области на видеокадрах. Эта сгруппированность сохраняется и для оптического потока, что позволяет его анализировать со скоростью, немного меньшей, чем линейная.
Таким образом, анализируемые методы применимы для использования на обычных компьютерах для обработки видео в реальном масштабе времени.
Сложности реализаций. Чем проще метод, тем сложнее в нем сделать неявную ошибку, и тем этот метод надежнее. Особенно это важно, когда метод встраивается как дополнительная функциональность в уже работающую систему.
Использование библиотеки OpenCV позволяет упростить реализацию методов путем написания кода сравнительно небольшого объема. Для всех сложных шагов использовались стандартные функции из библиотеки, что позволяет избежать возможных ошибок при самостоятельной реализации. Для связи сложных шагов производятся только простые операции (например, передача изображений), поэтому их реализация практически очевидна, и в ней сложно допустить ошибку.
Таким образом, анализируемые методы легко реализовать, а значит, они обладают высокой надежностью.
Качество. Рассмотренные методы являются приемлемыми по скорости работы, однако необходимо оценить качество получаемого результата. Проведем следующий эксперимент: на вход алгоритмам подадим видеоряд с бытовой видеокамеры. При стандартном комнатном освещении плавно проведем рукой перед камерой. Были опробованы как аналоговые камеры, для оцифровки сигнала которых использовались платы видеозахвата, так и различные WEB-камеры, которые подключаются к компьютеру через интерфейс USB и передают уже оцифрованный сигнал. В ходе экспериментов не выявлено существенных отличий выделяемых объектов в зависимости от использованной камеры. На рис. 1 для одного и того же видеоряда представлен результат работы алгоритмов поиска контура и объединения областей.
аб Рис. 1. Выделение движущейся руки на основе двух методов: поиск контуров (а); объединение областей (б)
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 3 (73)
41
АНАЛИЗ МЕТОДОВ ВЫДЕЛЕНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ …
Все сравниваемые методы дают сходный по качеству результат – алгоритмы выделили шумы как движущиеся объекты, что непригодно для дальнейшего использования. Следует заключить, что причина низкого качества результата обусловлена качеством построения оптического потока, поскольку данные методы на нем основаны.
Как подробно описано в [8], большинство алгоритмов построения оптического потока дают приемлемый результат только на искусственных и чистых кадрах, поэтому, получив на вход видео с шумами, они не обеспечивают желаемое качество выделения объекта. Все рассмотренные стандартные методы построения оптического потока очень чувствительны к уровню шумов, что отражается в найденных движущихся объектах. В ряде случаев алгоритмы вычисляют, что движется вся сцена, хотя на самом деле движения нет вообще, а на видео – равномерный шум. Также классические методы имеют сильные ограничения в допустимой скорости движения объектов – движения медленнее, чем один пиксель за кадр, не обнаруживаются вовсе. Разработанный в [8] авторский метод для построения оптического потока более помехоустойчив и способен выделять медленные движения, поэтому его использование для данной задачи дает приемлемое, но не идеальное в целом качество результата (рис. 2).
аб Рис. 2. Использование авторского метода на шаге построения оптического потока: вычисленный контур
(а); вычисленная область (б)
Как видно из рисунка, указанные ранее проблемы построения оптического потока переносятся на методы выделения движущихся объектов.
Выявленные проблемы
В основном все классические методы выделения движущихся объектов дают результат на основе анализа только двух последовательных кадров видеоряда, поскольку, как правило, используемый оптический поток строится на их основе. Это приводит к появлению таких проблем, как потеря медленных движений, зависимость от параметров захвата видео, отсутствие учета истории и особенностей искомых движений.
Например, если для камеры на улице захват видео производится со скоростью 8 кадров в секунду и кадры обладают высокой четкостью, то идущий вдалеке человек на уровне пикселей в каждом соседнем кадре имеет различное положение. Но, допустим, захват будет ускорен до 25 кадров в секунду, а размеры кадров маленькие. При этих условиях тот же идущий вдалеке человек, например, может изменять свое положение на уровне пикселей только каждые 4 кадра. Это приводит к большим интервалам между изменением положения. В результате алгоритм, эффективный в первом случае, даст не удовлетворительный результат во втором случае. Тем не менее, параметры захвата изменяются крайне редко, и обычно используется то, что дается по умолчанию. Стоит отметить, что во втором случае изменение положения происходит через 200 мс и, например, человеческий мозг осознает это как плавное и равномерное движение, вне зависимости от качества кадров и скорости их смены.
Таким образом, выбор условий съемки и настроек очень важны для многих алгоритмов. Отлично работая в одних условиях, почти все алгоритмы полностью перестают работать в других условиях.
Обычно алгоритмы не анализируют никакие закономерности естественных движений. Например, движение, которое появилось на двух или трех кадрах, скорее всего – шум, и выявлять его нет необходимости. То же самое можно сказать и про резкие движения вперед–назад, часто возникающие при съемках в затемненных условиях и связанные с особенностями захватывающей видеоаппаратуры. В таких условиях на видеокадрах присутствует большое количество шумов, и алгоритмы либо вообще перестают работать, либо указывают «перемещения» шумов. Тем не менее, практически всегда задача поиска движущихся объектов требует выделить движения настоящих объектов, а не формально указать движения пикселей на кадрах.
Обсуждение
На основе полученных выше результатов обоснована необходимость создания более универсального (по сравнению с существующими) алгоритма для выделения движущихся объектов в видеопоследовательности. Предположительно хороший результат должно дать использование идей из работы [8], но
42 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 3 (73)
В.А. Козлов, А.С. Потапов
примененных не к построению одного только оптического потока, а также и к задаче поиска движущихся объектов. Корневым отличием алгоритма должен стать анализ более чем двух кадров для получения решения на каждом отдельном кадре. Данная особенность должна быть использована для поиска закономерностей траектории объекта на группе смежных кадров и выявления медленных движений, а не потери объекта, если он остановился на нескольких кадрах. Должно присутствовать отсечение неестественных движений, которые в большинстве случаев являются шумом или событиями, которые не представляют интереса. Также алгоритм не должен зависеть от скорости смены кадров и одинаково хорошо работать в различных условиях.
При этом весь процесс должен быть связанным, а не строить решение по любым нескольким кадрам. На практике видеопоследовательность, в которой от алгоритма требуется найти движущиеся объекты, никогда не является случайной, а наоборот, она всегда представляет собой очень сильно связанные данные. Бессмысленно искать движущиеся объекты в последовательности изображений, в которых нет общих частей. Например, на записях камер видеонаблюдения всегда есть неизменный фон, на который можно опираться, чтобы получить устойчивость к шумам, которые присутствуют всегда при записи и оцифровке видеоматериала.
Таким образом, опираясь на хорошие результаты, полученные при анализе нескольких последовательных кадров для построения оптического потока в статье [8], можно предложить идеи для создания универсального метода выделения движущихся объектов. Анализ должен производиться на нескольких масштабах, и переход к более крупному изображению должен использовать результаты, полученные на предыдущем масштабе. Исходя из этого, должно происходить уточнение результата при детализации изображения. Для поиска решения должен использоваться просмотр нескольких соседних кадров, это даст возможность отследить медленные движения и проигнорировать шумы. Создание и детальное исследование этого метода будет выполнено в будущих работах авторов.
Заключение
Рассмотрены основные методы выделения движущихся объектов. Произведен их сравнительный анализ и проверено, что все они достаточно быстрые, чтобы использоваться в системах реального времени, а так же их не сложно реализовать и встроить в уже существующие проекты. Но выяснилось, что все классические методы практически невозможно использовать для анализа реальных видеопоследовательностей, полученных с бытовых камер, потому что методы не предполагают наличие шумов на кадрах. Предложены пути для решения этой проблемы. Ключевой особенностью станет использование более двух последовательных кадров для анализа и выдачи ответа на каждом отдельном кадре.
Работа выполнена при поддержке Министерства образования и науки и Совета по грантам Президента Российской Федерации (грант МД-2040.2010.9).
Литература
1. Лукьяница А.А. Цифровая обработка видеоизображений / А.А. Лукьяница, А.Г. Шишкин. – М.: АйЭс-Си Пресс, 2009. – 518 c.
2. Казаков Б.Б. Эффективные методы выделения движения объектов в последовательности изображений / Б.Б. Казаков // Научно-технические ведомости СПб ГПУ. Сер. Информатика. Телекоммуникации. Управление. – 2009. – Вып. 5. – С. 55–60.
3. Алпатов Б.А., Бабаян П.В. Методы обработки и анализа изображений в бортовых системах обнаружения и сопровождения объектов // Цифровая обработка сигналов. – 2006. – № 2. – С. 45–51.
4. Алпатов Б.А., Бабаян П.В. Выделение движущихся объектов в последовательности мультиспектральных изображений при наличии геометрических искажений // Вестник РГРТУ. – 2008. – Вып. 23. – С. 30–37.
5. Horn B.K.P., Schunck B.G. Determining optical flow // Artificial Intelligence. – 1981. – V. 17. – P. 185–203. 6. Bouguet J.Y. Pyramidal Implementation of the Lucas Kanade Feature Tracker Description of the algorithm //
OpenCV Documentation, Microprocessor Research Labs, Intel Corp, 2000. 7. Bruhn A., Weickert J., Schnorr C. Lucas/Kanade Meets Horn/Schunck: Combining Local and Global Optic /
// International Journal of Computer Vision 61. – 2005. – V. 3. – P. 211–231. 8. Козлов В.А. Помехоустойчивый метод построения оптического потока по нескольким кадрам // Оп-
тический журнал. – 2010. – Т. 77. – № 11. – C. 63–68.
Козлов Вадим Андреевич Потапов Алексей Сергеевич
– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, аспирант, vadikus@mail.ru
– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, доктор технических наук, профессор, pas.aicv@gmail.com
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 3 (73)
43
УДК 004.932.2
АНАЛИЗ МЕТОДОВ ВЫДЕЛЕНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ НА ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЯХ С ШУМАМИ
В.А. Козлов, А.С. Потапов
Рассмотрены наиболее часто используемые методы выделения движущихся объектов применительно к видеопоследовательностям, полученным с бытовых камер в условиях присутствия шумов на изображениях. Выделены основные проблемы обработки таких видеопоследовательностей, описана невозможность применения классических методов и предложены пути улучшения качества выделения движущихся объектов. Ключевые слова: анализ движения, контур, выделение объектов, сегментация.
Введение
В последнее время при организации видеонаблюдения применяются преимущественно цифровые методы обработки и хранения информации. Цифровые технологии дают ряд преимуществ перед устаревшими методами аналоговой записи на пленку. Например, в среднем качестве средний жесткий диск может хранить объем информации, соответствующий видеозаписи в течение месяца, а также обеспечи-
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 3 (73)
39
АНАЛИЗ МЕТОДОВ ВЫДЕЛЕНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ …
вается быстрый доступ к любой части записи, что можно сделать из любой точки мира, если записывающий компьютер подключен к сети.
Компьютеры предоставляют широкие возможности по автоматической обработке изображений, которая все еще используются лишь в незначительной степени. Такие простые задачи, как выполнение записи только движений, имеют достаточно универсальные решения. Однако более сложные задачи, особенно из области компьютерного зрения, до сих пор не имеют общих решений, а предлагаемые алгоритмы, как правило, применимы только при соблюдении ряда условий и ограничений. В связи с этим на сегодняшний день данная область исследований представляет большой интерес как в научном, так и в прикладном плане. Одной из важных, но до конца не решенных подзадач является автоматическое выделение движущихся объектов, что является необходимым предварительным шагом при решении таких задач видеонаблюдения, как системы контроля доступа, удаление фона, ориентация роботов в пространстве, системы помощи водителям, распознавание лиц, облегчение восприятия сцены человеческим глазом и многих других.
В работе рассматривается вопрос выделения движущихся объектов на реальных видеопоследовательностях, полученных с бытовых видеокамер. Проведен сравнительный анализ существующих решений на базе методов выделения контура и области движущегося объекта, а также авторская модификация этих методов. Проанализировано быстродействие и качество результата в зависимости интенсивности шумов, типа сцены, характеристик захвата и оцифровки видео. Описаны трудности, возникающие при внедрении этих алгоритмов в реальные системы. Обосновывается несостоятельность существующих методов, предложены пути для улучшения качества результата, чтобы получить универсальный метод предварительной обработки информации в системах видеонаблюдения.
Подходы к выявлению движущихся объектов
Существует два основных класса методов выделения движущихся объектов: 1. путем анализа их границ (контуров); 2. путем анализа всей области объекта на кадрах [1–4].
Основной идеей методов первого класса является поиск отличий векторов оптического потока с последующим построением контуров движущихся объектов [1–4]. Методы второго класса, наоборот, основываются на группировании сходных векторов из оптического потока в области, которые подаются на выход алгоритма в качестве движущихся объектов [1–4]. Большинство классических методов анализируют не сами кадры видеопоследовательности, а оптический поток (поле видимых смещений пикселей изображений), построенный по этим кадрам.
Для сравнительного анализа построим данные методы на базе широко используемой в компьютерном зрении общедоступной библиотеки OpenCV, содержащей реализации для некоторых шагов исследуемых методов, таких как построение оптического потока, вычисление градиента и поиск контуров, а также простой и удобный интерфейс для работы с камерами и вывод результата на экран.
Для построения оптического потока будем использовать функции из библиотеки OpenCV, реализующие алгоритмы Хорна–Шанка (Horn–Schunck) [5, 6], Лукаса–Канадэ (Lucas–Kanade) [6, 7] и метод блочного сопоставления, описанный, в том числе, в работе [8], а также метод, разработанный авторами настоящей работы и представленный в [8].
Для построения контуров движущихся объектов будем выполнять следующие шаги: построение оптического потока одним из предложенных выше методов; вычисление градиента оптического потока; построение матрицы, каждая ячейка которой соответствует модулю градиента; нахождение контуров на основе бинаризованного поля модуля градиента.
Общая схема построения областей движущихся объектов будет включать следующие шаги: построение оптического потока одним из предложенных выше методов; сравнение вектора оптического потока в каждой точке кадра с векторами в соседних точках (срав-
нение ведется только с точками снизу и справа от текущей точки, поскольку сравнение с точками слева и сверху уже было выполнено при рассмотрении предыдущих точек); если векторы сходны, то точки объединяются в область или присоединяются к уже существующей области (для пометок областей их номера записываются в соответствующие ячейки кадра).
Таким образом, после однократного прохода по изображению получим разметку на области. В качестве функции похожести векторов оптического потока для рассматриваемых методов приемлемый результат дает использования следующего условия. Если модуль разности векторов меньше одной трети длины самого короткого, то вектора похожи. Данный критерий, хотя и выглядит эвристическим, дает хороший результат и является приемлемым при сравнении эффективности разных методов выделения движущихся объектов. Коэффициент эмпирически вытекает из спектра векторов оптического потока. Полное обоснование критерия и автоматический адаптивный выбор коэффициента предполагается получить в последующих работах.
40 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 3 (73)
В.А. Козлов, А.С. Потапов
Анализ характеристик методов выявления движущихся объектов
Проведем сравнение различных методов выявления движущихся объектов по критериям быстродействия, сложности реализации и качества достигаемого результата. Перечисленные характеристики важны, так как для обеспечения непрерывного видеонаблюдения требуется обработка изображений в масштабе реального времени. Однако достижение необходимого быстродействия не должно приводить к ухудшению вероятностей обнаружения объектов интереса. При всем этом для возможности легкого внедрения метода в любые проекты желательно иметь простую и очевидную реализацию.
Быстродействие. Основной вклад в вычислительную сложность рассматриваемых методов вносит вычисление оптического потока, так как даже линейные реализации имеют очень большой коэффициент. Все остальные шаги алгоритмов выделения движущихся объектов – группирование векторов, вычисление градиента, поиск контуров – требуют лишь нескольких операций на каждый пиксель изображения. Данные методы можно назвать весьма производительными, если не брать в расчет вычисление оптического потока, так как способ его вычисления зависит от поставленных задач, условий и целей. К тому же все современные компьютеры имеют несколько ядер, и оптический поток может независимо вычисляться на своем ядре, не мешая остальному анализу. При обработке каждого нового кадра на все прочие расчеты, кроме оптического потока, для стандартного размера кадра (VGA – 64×480) тратится не более 10–60 млн. тактов, что приблизительно равно 4–20 мс процессорного времени для ядра с частотой 3 ГГц. Производительность зависит от интенсивности и сложности движения на видеоряде, поэтому точную алгоритмическую сложность подсчитать не возможно. Например, для неподвижной сцены все алгоритмы дают быстрый ответ об отсутствии объектов, но чем больше в сцене мелких движений, тем больше ресурсов требуется для их поиска. Конечно же, например, для метода объединения областей несложно придумать кадры, оптический поток которых имеет шахматный порядок, и анализ таких кадров будет, как минимум, кубической сложности. Но на практике такое не встречается, а движущиеся объекты имеют сгруппированные области на видеокадрах. Эта сгруппированность сохраняется и для оптического потока, что позволяет его анализировать со скоростью, немного меньшей, чем линейная.
Таким образом, анализируемые методы применимы для использования на обычных компьютерах для обработки видео в реальном масштабе времени.
Сложности реализаций. Чем проще метод, тем сложнее в нем сделать неявную ошибку, и тем этот метод надежнее. Особенно это важно, когда метод встраивается как дополнительная функциональность в уже работающую систему.
Использование библиотеки OpenCV позволяет упростить реализацию методов путем написания кода сравнительно небольшого объема. Для всех сложных шагов использовались стандартные функции из библиотеки, что позволяет избежать возможных ошибок при самостоятельной реализации. Для связи сложных шагов производятся только простые операции (например, передача изображений), поэтому их реализация практически очевидна, и в ней сложно допустить ошибку.
Таким образом, анализируемые методы легко реализовать, а значит, они обладают высокой надежностью.
Качество. Рассмотренные методы являются приемлемыми по скорости работы, однако необходимо оценить качество получаемого результата. Проведем следующий эксперимент: на вход алгоритмам подадим видеоряд с бытовой видеокамеры. При стандартном комнатном освещении плавно проведем рукой перед камерой. Были опробованы как аналоговые камеры, для оцифровки сигнала которых использовались платы видеозахвата, так и различные WEB-камеры, которые подключаются к компьютеру через интерфейс USB и передают уже оцифрованный сигнал. В ходе экспериментов не выявлено существенных отличий выделяемых объектов в зависимости от использованной камеры. На рис. 1 для одного и того же видеоряда представлен результат работы алгоритмов поиска контура и объединения областей.
аб Рис. 1. Выделение движущейся руки на основе двух методов: поиск контуров (а); объединение областей (б)
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 3 (73)
41
АНАЛИЗ МЕТОДОВ ВЫДЕЛЕНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ …
Все сравниваемые методы дают сходный по качеству результат – алгоритмы выделили шумы как движущиеся объекты, что непригодно для дальнейшего использования. Следует заключить, что причина низкого качества результата обусловлена качеством построения оптического потока, поскольку данные методы на нем основаны.
Как подробно описано в [8], большинство алгоритмов построения оптического потока дают приемлемый результат только на искусственных и чистых кадрах, поэтому, получив на вход видео с шумами, они не обеспечивают желаемое качество выделения объекта. Все рассмотренные стандартные методы построения оптического потока очень чувствительны к уровню шумов, что отражается в найденных движущихся объектах. В ряде случаев алгоритмы вычисляют, что движется вся сцена, хотя на самом деле движения нет вообще, а на видео – равномерный шум. Также классические методы имеют сильные ограничения в допустимой скорости движения объектов – движения медленнее, чем один пиксель за кадр, не обнаруживаются вовсе. Разработанный в [8] авторский метод для построения оптического потока более помехоустойчив и способен выделять медленные движения, поэтому его использование для данной задачи дает приемлемое, но не идеальное в целом качество результата (рис. 2).
аб Рис. 2. Использование авторского метода на шаге построения оптического потока: вычисленный контур
(а); вычисленная область (б)
Как видно из рисунка, указанные ранее проблемы построения оптического потока переносятся на методы выделения движущихся объектов.
Выявленные проблемы
В основном все классические методы выделения движущихся объектов дают результат на основе анализа только двух последовательных кадров видеоряда, поскольку, как правило, используемый оптический поток строится на их основе. Это приводит к появлению таких проблем, как потеря медленных движений, зависимость от параметров захвата видео, отсутствие учета истории и особенностей искомых движений.
Например, если для камеры на улице захват видео производится со скоростью 8 кадров в секунду и кадры обладают высокой четкостью, то идущий вдалеке человек на уровне пикселей в каждом соседнем кадре имеет различное положение. Но, допустим, захват будет ускорен до 25 кадров в секунду, а размеры кадров маленькие. При этих условиях тот же идущий вдалеке человек, например, может изменять свое положение на уровне пикселей только каждые 4 кадра. Это приводит к большим интервалам между изменением положения. В результате алгоритм, эффективный в первом случае, даст не удовлетворительный результат во втором случае. Тем не менее, параметры захвата изменяются крайне редко, и обычно используется то, что дается по умолчанию. Стоит отметить, что во втором случае изменение положения происходит через 200 мс и, например, человеческий мозг осознает это как плавное и равномерное движение, вне зависимости от качества кадров и скорости их смены.
Таким образом, выбор условий съемки и настроек очень важны для многих алгоритмов. Отлично работая в одних условиях, почти все алгоритмы полностью перестают работать в других условиях.
Обычно алгоритмы не анализируют никакие закономерности естественных движений. Например, движение, которое появилось на двух или трех кадрах, скорее всего – шум, и выявлять его нет необходимости. То же самое можно сказать и про резкие движения вперед–назад, часто возникающие при съемках в затемненных условиях и связанные с особенностями захватывающей видеоаппаратуры. В таких условиях на видеокадрах присутствует большое количество шумов, и алгоритмы либо вообще перестают работать, либо указывают «перемещения» шумов. Тем не менее, практически всегда задача поиска движущихся объектов требует выделить движения настоящих объектов, а не формально указать движения пикселей на кадрах.
Обсуждение
На основе полученных выше результатов обоснована необходимость создания более универсального (по сравнению с существующими) алгоритма для выделения движущихся объектов в видеопоследовательности. Предположительно хороший результат должно дать использование идей из работы [8], но
42 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 3 (73)
В.А. Козлов, А.С. Потапов
примененных не к построению одного только оптического потока, а также и к задаче поиска движущихся объектов. Корневым отличием алгоритма должен стать анализ более чем двух кадров для получения решения на каждом отдельном кадре. Данная особенность должна быть использована для поиска закономерностей траектории объекта на группе смежных кадров и выявления медленных движений, а не потери объекта, если он остановился на нескольких кадрах. Должно присутствовать отсечение неестественных движений, которые в большинстве случаев являются шумом или событиями, которые не представляют интереса. Также алгоритм не должен зависеть от скорости смены кадров и одинаково хорошо работать в различных условиях.
При этом весь процесс должен быть связанным, а не строить решение по любым нескольким кадрам. На практике видеопоследовательность, в которой от алгоритма требуется найти движущиеся объекты, никогда не является случайной, а наоборот, она всегда представляет собой очень сильно связанные данные. Бессмысленно искать движущиеся объекты в последовательности изображений, в которых нет общих частей. Например, на записях камер видеонаблюдения всегда есть неизменный фон, на который можно опираться, чтобы получить устойчивость к шумам, которые присутствуют всегда при записи и оцифровке видеоматериала.
Таким образом, опираясь на хорошие результаты, полученные при анализе нескольких последовательных кадров для построения оптического потока в статье [8], можно предложить идеи для создания универсального метода выделения движущихся объектов. Анализ должен производиться на нескольких масштабах, и переход к более крупному изображению должен использовать результаты, полученные на предыдущем масштабе. Исходя из этого, должно происходить уточнение результата при детализации изображения. Для поиска решения должен использоваться просмотр нескольких соседних кадров, это даст возможность отследить медленные движения и проигнорировать шумы. Создание и детальное исследование этого метода будет выполнено в будущих работах авторов.
Заключение
Рассмотрены основные методы выделения движущихся объектов. Произведен их сравнительный анализ и проверено, что все они достаточно быстрые, чтобы использоваться в системах реального времени, а так же их не сложно реализовать и встроить в уже существующие проекты. Но выяснилось, что все классические методы практически невозможно использовать для анализа реальных видеопоследовательностей, полученных с бытовых камер, потому что методы не предполагают наличие шумов на кадрах. Предложены пути для решения этой проблемы. Ключевой особенностью станет использование более двух последовательных кадров для анализа и выдачи ответа на каждом отдельном кадре.
Работа выполнена при поддержке Министерства образования и науки и Совета по грантам Президента Российской Федерации (грант МД-2040.2010.9).
Литература
1. Лукьяница А.А. Цифровая обработка видеоизображений / А.А. Лукьяница, А.Г. Шишкин. – М.: АйЭс-Си Пресс, 2009. – 518 c.
2. Казаков Б.Б. Эффективные методы выделения движения объектов в последовательности изображений / Б.Б. Казаков // Научно-технические ведомости СПб ГПУ. Сер. Информатика. Телекоммуникации. Управление. – 2009. – Вып. 5. – С. 55–60.
3. Алпатов Б.А., Бабаян П.В. Методы обработки и анализа изображений в бортовых системах обнаружения и сопровождения объектов // Цифровая обработка сигналов. – 2006. – № 2. – С. 45–51.
4. Алпатов Б.А., Бабаян П.В. Выделение движущихся объектов в последовательности мультиспектральных изображений при наличии геометрических искажений // Вестник РГРТУ. – 2008. – Вып. 23. – С. 30–37.
5. Horn B.K.P., Schunck B.G. Determining optical flow // Artificial Intelligence. – 1981. – V. 17. – P. 185–203. 6. Bouguet J.Y. Pyramidal Implementation of the Lucas Kanade Feature Tracker Description of the algorithm //
OpenCV Documentation, Microprocessor Research Labs, Intel Corp, 2000. 7. Bruhn A., Weickert J., Schnorr C. Lucas/Kanade Meets Horn/Schunck: Combining Local and Global Optic /
// International Journal of Computer Vision 61. – 2005. – V. 3. – P. 211–231. 8. Козлов В.А. Помехоустойчивый метод построения оптического потока по нескольким кадрам // Оп-
тический журнал. – 2010. – Т. 77. – № 11. – C. 63–68.
Козлов Вадим Андреевич Потапов Алексей Сергеевич
– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, аспирант, vadikus@mail.ru
– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, доктор технических наук, профессор, pas.aicv@gmail.com
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 3 (73)
43