Комбинированные алгоритмы оперативного выделения движущихся объектов в последовательности видеокадров на основе локального дифференциального метода вычисления оптического потока

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

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

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

При этом решаются разнообразные задачи: обнаружение объектов, сопровождение объектов (слежение за объектами), идентификация и распознавание объектов, определение параметров, траекторий и характерных особенностей движения.

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

Как правило, уже на основе определения характеристик выделенных областей решаются задачи обнаружения, слежения, идентификации, распознавания и т. п.

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

• обзорные (как правило, патрульного типа), которые расположены и «нацелены» в пространстве в фиксированном положении;

• следящие, у которых область (направление) наблюдения следует за перемещением объектов.

Сочетание разнообразия сюжетов динамической сцены и типов устройств наблюдения порождает множество задач. Не претендуя на исчерпывающую полноту, перечислим некоторые важные особенности этих задач.

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

В некоторых задачах движется множество объектов, причем иногда это движение имеет синхронный характер и тогда говорят о множественных объектах.

Например, в [1]выделены некоторые простые, но важные общие ситуации:

• неподвижная камера, один движущийся объект, постоянный (по времени) фон (возможно, включающий неподвижные объекты),.

• неподвижная камера, несколько*движущихся объектов, постоянный фон,.

• движущаяся камера, относительно постоянный фон,.

• движущаяся камера, несколько движущихся объектов.

Задачи, возникающие в ситуации 1, решаются, например, в охранных и пропускных системах. Ситуация 2 характерна для задач слежения за множеством людей в ограниченном пространстве (производственные и иные помещения, поле для спортивных игр), при наблюдении за транспортным потоком на заданном участке магистрали и т. п. В ситуации 3, как правило, интерес представляют не столько особенности наблюдаемой сцены, сколько особенности самого процесса наблюдения (перемещения или изменения фокусировки камеры и т. п.). Ситуация 4 не предполагает даже относительного постоянства фона. Например, фон может образовываться плотной группировкой движущихся элементов сцены. Примером может служить задача управления мобильным роботом [2, 3] в транспортном потоке.

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

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

При решении задачи выделения объектов важно определить, какие пиксели следует распознавать для выделения, а какие игнорировать. Получение представления данных, в котором эта задача решена, обычно называют [5] сегментацией, группировкой, перцептивной организацией, сборкой и т. п.

Термин сегментация достаточно широк и обычно связывается с идеей компактного представления полезного содержимого объекта.

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

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

Известны методы сегментации [5−7] на основе анализа пикселей, на основе анализа областей, на основе анализа контуров и на основе моделей. Мы будем ориентироваться на методы сегментации на основе анализа областей. При этом признаки для сегментации могут формироваться как из характеристик движения (поле скоростей), так и из «статических» характеристик кадра (например, яркости).

Содержательно будем считать, что интересующий нас движущийся объект — это область кадра, в которой скорость перемещения каждого пикселя незначительно отличается от средней скорости всей области как целого. На границе движущегося объекта имеется неоднородность по величине и направлению вектора скорости. Этот подход будет уточнен далее в главу 3.

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

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

Для вычисления оптического потока наиболее часто используются локальные и глобальные дифференциальные алгоритмы. Локальные дифференциальные алгоритмы позволяют достаточно быстро вычислить оптический поток, но точность полученного ОП в некоторых случаях является недостаточной для устойчивого выделения движущихся объектов. Глобальные методы вычисления ОП являются более точными, но их вычислительная сложность не позволяет их использовать в некоторых задачах реального времени.

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

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

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

Основные задачи работы:

• Разработка алгоритма вычисления оптического потока, позволяющего вычислять оптический поток в режиме реального времени за счет параллельной обработки и обладающего свойством устойчивости (робаст-ности) относительно возмущений входных данных.

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

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

• Разработка параллельной программной реализации алгоритмов на графическом ускорителе.

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

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

Научная новизна работы состоит в следующем:

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

• Разработка эффективных комбинированных алгоритмов выделения движущихся объектов на основе совместного анализа оптического потока и статических признаков отдельного кадра.

• Параллельное представление и программная реализация разработанного алгоритма вычисления оптического потока, ориентированное на выполнение на графическом процессоре.

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

• Смешанное визуально-текстовое представление алгоритмов, интерактивная коррекция и организация вычислительного процесса в программной инструментальной системе реализации и испытания алгоритмов обработки видеокадров.

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

12 многих задачах: при сжатии и передаче видеоинформации, в робототехнике и стереозрении, в задачах идентификации личности.

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

На защиту выносятся следующие основные результаты и положения:

• Комбинированный мультимасштабный регуляризованный устойчивый алгоритм вычисления оптического потока.

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

• Параллельная реализация разработанных алгоритмов.

• Программная инструментальная система визуальной реализации и испытания алгоритмов обработки видеоданных.

Внедрение работы. Результаты работы были использованы в НИР, проводимой в ОАО «НИЦ ЭТУ», и использованы в учебном процессе кафедры МО ЭВМ СПбГЭТУ «ЛЭТИ».

Апробация работы Основные положения, результаты исследований и выводы, содержащиеся в диссертационной работе, обсуждались в широком кругу специалистов, ученых и разработчиков систем слежения в УНИЦ ПСКС «ЛЭТИ», на конференциях ППС СПбГЭТУ «ЛЭТИ», а также на научно-технических конференциях:

• «Технологии Microsoft в теории и практике программирования», г. Санкт-Петербург, 2007 г.

• VI Всероссийская межвузовская конференция молодых ученых, г. Санкт-Петербург, 2009 г.

• «Технические средства противодействия террористическим и криминальным взрывам», г. Санкт-Петербург, 2009 г.

• «Информационно-измерительное обеспечение полигонных (космодром-ных) испытаний вооружения и военной техники», г. Великий Новгород, 28−30 июня 2006 г.

Публикации. По теме диссертации опубликованы 5 научных работ, из них 3 — статьи, 2 — работы в материалах конференций. 2 статьи опубликованы в журналах, входящих в перечень ведущих периодических изданий (ВАК).

6.7. Выводы.

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

Анализ результатов проделанных в главе экспериментов показывает, что при использовании комбинированного метода вычисления оптического потока интегральная ошибка потока уменьшается на 48% по сравнению с локаль.

Скорость вычисления оптического потока Глоблль^й М1 ямбинироеэнный тпсЛапьный Н1И.

Рис. 6.13. Скорость обработки видеопоследовательности на графическом ускорителе (в кадрах/сек) некоторыми методами вычисления оптического потока ными дифференциальными методами и увеличивается на 148% по сравнению с глобальными методами. При этом скорость работы разработанного алгоритма приблизительно в 20 раз превышает скорость работы глобальных методов вычисления оптического потока.

Разработанный комбинированный алгоритм позволяет существенно снизить число пропускаемых объектов в процессе выполнения алгоритма выделения движущихся объектов. В первом анализируемом случае среднее число пропущенных объектов в кадре снизилось с 0.22 до 0, а во втором случае с 0.6 до 0.17.

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

Заключение

.

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

Требования высокой производительности определили класс используемых алгоритмов. Были предложены 2 модификации, позволяющие повысить точность вычисления оптического потока локальным дифференциальным методом. Первая модификация заключается в использовании медианного фильтра с большим радиусом. Использование медианного фильтра для корректировки поля оптического потока уже предлагалось ранее, однако в данной работе используется другая интерпретация медианного фильтра: медианный фильтр выступает аналогом сглаживающего члена, присутствующего в глобальных методах вычисления ОП. По этой причине если в других работах для фильтрации используется окно радиусом 3×3 или 5×5, то в этой работе предлагается использовать окно порядка 15×15 или 25×25.

Вторая модификация основана на методах решения некорректных задач. К минимизируемому функционалу предлагается добавить регуляризующий член. Выбор коэффициента регуляризации базируется на оценках неточности вычислений матрицы градиента Н, вектора производных по времени В, оценки скорости перемещения, а также обратно пропорционален числу обусловленности матрицы НТН.

Эффективность разработанных модификаций была подтверждена сравнительным анализом локальных дифференциальных алгоритмов с использованием предложенных модификаций и без. Для проведения анализа использовались стандартные модельные видеопоследовательности, разработанные группой американских ученых в 2006 году. Аналнз результатов показал, что разработанные модификации в среднем па 48% уменьшают ошибку измерения вектора оптического потока для данных модельных последовательностей. По сравнению с одними из наиболее точных на сегодняшний день разработанные алгоритмы увеличивают ошибку в среднем на 138%. Достигнутая точность оказалось достаточной для разработки комбинированных алгоритмов выделения движущихся объектов в видеопоследовательностях.

Требования к быстродействию разрабатываемых алгоритмов чрезвычайно сузило класс рассматриваемых алгоритмов сегментации. На основе алгоритма вычисления ОП было разработано 4 алгоритма выделения движущихся объектов, отличающиеся друг от друга по способу формирования поля признаков и способу выделения объектов. Для их сравнительного анализа были разработаны характерные модельные последовательности, имеющие характеристики реальных последовательностей (освещенности, уровню шума, размеров присутствующих объектов, скорость перемещения). В качестве измеряемых характеристик использовалось количество пропущенных и ложных объектов, характеризующих общую устойчивость выделения объектов. Разработанный комбинированный алгоритм позволяет существенно снизить число пропускаемых объектов в процессе выполнения алгоритма выделения движущихся объектов. В первом анализируемом случае среднее число пропущенных объектов в кадре снизилось с 0.22 до 0, а во втором случае с 0.6 до 0.17.

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

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

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

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

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

В результате, поставленная в диссертационной работе задача была успешна решена.