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

Сапкт-Пстсрбургский Государственный электротехнический университет

«ЛЭТИ»

'[иХ

На правах рукописи

Казаков Борис Борисович

Комбинированные алгоритмы оперативного

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

05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации па соискание ученой степени кандидата технических наук

Санкт-Петербург ■ 2009

003488366

Работа выполнена в Санкт-Петербургском государственном электротехническом университете «ЛЭТИ».

Научный руководитель:

кандидат технических паук, доцент,

Ивановский Сергей Алексеевич, доктор технических паук, профессор,

Куприянов Михаил Степанович, кандидат технических паук, доцент,

Макулов Василий Борисович. Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А.Бопч-Брусвича.

Официальные оппоненты:

Ведущая организация:

Защита состоится 23 декабря 2009 г. в .19_ часов па заседании совета по

защите докторских и кандидатских диссертаций Д 212.238.01 при Санкт-Петербургском государственном электротехническом университете «ЛЭТИ», расположенном по адресу: 197370, Санкт-Петербург, улица Профессора Попова, дом 5.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного электротехнического университета.

Автореферат разослан

Ученый секретарь совета по защите докторских и кандидатских диссертаций, к.т.н., доцент

М. Г. Пантелеев

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Методы исследований базируются па методах организации вычислитель-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание работы

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

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

В работе сделано предположение, что видеопоследовательность Э представляет собой последовательность видеокадров (II, 1г, • • • Дк), зарегистрированных через равные промежутки времени Д£ = 1. Каждый видеокадр описывается в виде массива данных I размерности (р х q). Интенсивность кадра в точке с координатами х = (х,у)т равна 1(х) = 1(х,у). Дискретные точки видеокадра будем называть пикселями.

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

где для частных производных использованы обозначения ^ = V/ =

(I П & = 1 & = 1

У1*'¿у)'Ох ±х'Оу .V

Пусть для заданной окрестности П(х) определено преобразование множества точек окрестности Е П(х)} в вектор Ъ = (21,221'■• ,г„,)т и обратно: {ху|ху € П(х)} Ъ — (21, 22, ■ ■., гт)т .

Введем вектор Н = ^/(21)^/(22), • • • , ^71{гт))т размера (га х 2) и вектор В = —(/4(2), /((22), • • • , размера (ттгх 1). Тогда оценка оптического потока по методу наименьших квадратов получается минимизацией функционала:

||е||* = Л = (Ш-В)тШ(Ш-В), (1)

где — весовая матрица, определяемая окрестностью. Такая оценка соответствует локальному методу оценивания оптического потока, в отличие

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

Методы вычисления оптического потока подвержены так называемой

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

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

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

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

(а) Исходное поле оптического потока (Ь) Сглаженное поле оптического потока

Рис. Г. Результат медианной фильтрации поля оптического потока

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

Первая модификация основана на методах решения некорректных задач и сводится к добавлению регуляризующей компоненты a2 ||f|| к минимизируемому функционалу:

Jr = (В - Hf) Г W (в - Hf) + a2 ||f ||, (2)

при ЭТОМ |н-н|| < Д.Цв-вЦ < J, ||н-н| < h, (B-H/)Tw(B-H/) < р.

Здесь Н,В — измеряемое значения, Н, В — истинные.

Тогда значение а подбирается из соотношения а. — (3 • &-1(Н7Н), где fc(HJ Н) — число обусловленности матрицы HJ Н. /3 глобальная константа, которая вычисляется па основе анализа остаточных невязок функционала (2), анализа характеристик точности h и S.

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

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

Метод RB G2 G3 HYD U2 из YOS

Исходный алг. 23.31 19.65 20.96 24.65 46.69 35.99 12

Медианный 22.32 18.4 19.47 22.2 45.92 33.87 11.01

Регуляризоваппый 15.31 8.16 12.83 10.35 28.18 8.75 10.15

Комбинированный 14.92 7.62 12.46 10.47 26.7 12.35 8.2

Таблица 1: Интегральная ошибка вычисленного оптического потока для предложенных модификаций алгоритма.

модификаций.

Эффективность разработанного комбинированного алгоритма вычисления оптического потока подтверждена сравнением точности вычисленного оптического потока с использованием предложенных модификаций и без их использования. При этом использовались стандартные видеопоследовательности, разработанные в 200G году группой американских ученых (Black и другие) для сравнения точности вычисления оптического потока различными методами. Результаты сравнения приведены в таблице В среднем ошибка вычисления потока уменьшилась па 48%.

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

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

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

В работе было предложено использовать мультипликативный и морфо-

Пропущенные объекты

Ложные объеты

2 4 6 8 10 12 14 16 1В 20 22 1 3 5 7 9 11 13 15 17 19 21 23 Номер кадра

Номер кадра

Рие. 2: Количество ложных и пропущенных объектов в зависимости от способа формирования поля признаков (МУЛЬТ — мультипликативный алгоритм вычисления поля признаков, МОРФ — морфологический алгоритм вычисления поля признаков).

логический подход к формированию поля признаков. Исследование алгоритмов па модельной видеопоследовательности показало, что при использовании морфологически сформированного поля признаков и пирамидального алгоритма сегментации достигается максимальная устойчивость выделения движущихся объектов. В мультипликативном подходе поле признаков С вычис-лястя, как С = I® где ® обозначает поточечное умножение двух изображений. Морфологический подход использует последовательность морфологических операций эрозии, реконструирования, девальтации, реконструирования для получения поля признаков. На рис. 2 показано сравнение двух алгоритмов формирования поля признаков. При использовании морфологического алгоритма формирования поля признаков частоты пропусков объектов и появления ложных объектов существенно снизились.

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

Задача 1: слежение за объектами в видеопоследовательности, полученной от следящей видеокамеры в условиях сильного зашумлепия кадров. Характеристики шума в этой последовательности затрудняют визуальную локализацию объектов оператором. В качестве априорных данных задаются начальные координаты объекта в плоскости кадра хх = и проекция вектора скорости объекта па плоскость кадра VI = (ух1,угл)т. Также задай начальный радиус объекта Их = (Яхь Дух). Причем К мало по сравнению со скоростью перемещения. Локальный оптический поток в данных условиях не отражает движение объекта, поэтому его нельзя использовать для выделения без дополнительной обработки.

Поэтому для выделения объекта предлагается использовать следующую

поел едо в лтел ь пост ь до й ста и й:

xn = x„_i + v„_i — F„_i,

х„ = xn + max^ (fi(I„_i, x„_i) * fi(I„, х,,)) [dx,dy], (dx,dy)

где (iii * fi2) [dx, dy] - £ EyLrty^lx, y)ih[x+dx, y+dy] кросс

корреляция двух окрестностей fij и Fn_i — средний вектор оптического

потока, по всему полю изображения, xn, v„........координаты и скорость объекта

в момент времени п.

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

Для вычисления оптического потока в таких условиях предлагается компенсировать изменения освящения, вызванные вспышками объекта. Пусть 1„ = 2Л (I„_i, f„_a). Если 1п(х) - 1„(х) > г, то изменения освещения при переходе от n-1-ro к n-ому кадру необходимо компенсировать. Для этого предлагается вычислить аппроксимацию добавочной освещенности сЛ = I,, — 1„. Исследования показали, что если имеется информация о центрах ''вспышек",

то импульсное изменение освещенности можно моделировать в виде функции

N

dl(x) = ^W,;6i>(||x — С; ||) , (3)

i'=l

где ф(г) = 1/у (г/е)" + 1 - радиальная базисная функция, а сумма 3 -разложение на радиальные базисные функции. Для определения параметров к;,; обычно используют метод наименьших квадратов, а для определения с,; можно использовать имеющуюся априорную информацию о координатах вспышек или построить искусственную нейронную сеть.

В четвертой главе описывается программная инструментальная систс-ма(ИС) визуального исследования алгоритмов. Анализ существующих средств показал целесообразность создания собственной комбинированной визуальной инструментальной системы модификации и исследования алгоритмов па основе языка Python. Основными целями при этом было обеспечить: 1) удобное тестирование и анализ алгоритмов; 2) простоту модификации алгоритмов; 3) наглядное представление алгоритмов: 4) высокую скорость выполнения алгоритмов; 5) унифицированный адаптируемый пользовательский интерфейс; G) возможность исследования реализации алгоритмов па графическом процессоре.

Рис. 3: Диаграмма алгоритма

Алгоритм в инструментальной системе представлен в виде диаграммы, которая представляет собой модифицированный информационный граф. Блоки соответствуют операциям над элементами, а связи описывают поток данных между блоками. Поведение блока в свою очередь может быть описано или другой диаграммой, или текстом программы па языке Python. Возможность интерактивного определения алгоритма поведения блока с помощью скрипта определяет ключевое отличие комбинированного средства от целиком визуальных средств программирования. Каждый блок имеет набор входных и набор выходных параметров. Связь между двумя блоками определяет соответствие значения выходного параметра одного блока входному параметру другого блока. Выполнение диаграммы состоит из последовательности выполнения блоков. При этом порядок выполнения определяется связями между блоками. Инструментальная система поддерживает режим «ленивых вычислений», т.е. при выполнении диаграммы выполняются только тс операторы, значения результатов которых интересуют пользователя. Пример визуальной диаграммы показан на рис. 3.

Представление алгоритма в виде диаграммы позволяет организовать вычисления таким образом, что после внесения необходимых изменений не изменившиеся части диаграммы/алгоритма не псревычисляются, а вычисляются только блоки с изменившимися данными.

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

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

вапия графических процессоров CUDA.

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

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

Сравнение скорости вычислений с некоторыми современными алгоритмами вычисления оптического потока показано в таблице 2. Все вычисления проводились на графическом ускорителе (NVIDIA GTX 275). TVL1 — глобальный вариационный метод, Humbcr-Ll — модифицированный TVL1 метод, в которым метрика TV заменена на метрику Н1 для более точного определения границ объектов, комбинированный — предложенный в работе метод. Методы TVL1 и Humbcr-Ll описаны в первой главе диссертации.

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

размер изображения TVL1 Hnmbcr-Ll Комбинированный

512 х 512 5.3 1.3 121

1024 х 1024 1.3 0.25 32

2048 х 2048 0.33 0.05 8

Таблица 2: Скорость вычисления оптического потока различными алгоритмами^ кадрах/сек)

метод RBW GV2 GV3 Hydr U2 из yos

комбинированный 14.92 7.62 12.46 10.47 26.7 12.35 8.2

TVL1 11.41 4.12 10.75 14.85 23.35 18.77 4.74

Humber-Ll 7.18 2.14 5.14 6.17 15.9 7.42 2.32

Таблица 3: Сравнение разработанного алгоритма с современными глобальными алгоритмами вычисления оптического потока по величине интегральной ошибки

ученых (Black и другие) для сравнения точности вычисления оптического потока различными методами.

Анализ результатов измерений, представленный в таблицах 1, 2, 3 показывает, что при использовании комбинированного метода вычисления оптического потока ошибка вычислений уменьшается на 48% по сравнению с локальным дифференциальным методом, и увеличивается па 138% по сравнению с глобальными методами. При этом скорость работы разработанного метода приблизительно в 20 раз превышает скорость работы глобальных методов вычисления оптического потока, и почти не уступает иемодифицироваппым локальным методам.

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

В заключении сформулированы основные научные и практические результаты, полученные автором.

Основные результаты работы

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

2. Разработан алгоритм выделения объектов па основе разработанного алгоритма вычисления оптического потока.

3. Разработаны два алгоритма выделения объектов в осложненных условиях съемки: а) в условиях сильного зашумления видеокадров, б) в условиях импульсного изменения яркости.

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

5. Разработана программная инструментальная система визуального исследования и испытания алгоритмов обработки больших объемов видеоданных.

Опубликованные научные работы по теме диссертации в изданиях, определенных ВАК

1. Ивановский, С. А. Методы семантического сжатия последовательностей изображений, полученных с оптико-электронных измерительных средств / С. А. Ивановский, Б. Б. Казаков, А. Е. Лозицкий // Известия Санкт-Петербургского государственного электротехнического университета

«ЛЭТИ». Сер. «Информатика, управление и компьютерные технологии». - 200G. - Вып. 3. - С. 15-20

2. Казаков, Б. Б. Эффективные методы выделения движения объектов в последовательности изображений / Б. Б. Казаков, С. А. Ивановский // Научпо-тсхничсскис ведомости Санкт-Петербургского государственного политехнического университета. Сер. Информатика. Телекоммуникации. Управление. — 2009 — Вып. 5. — С. 55 — GO

и в других научных изданиях

3. Казаков Б. Б. Методы предварительной обработки и сегментации, ориентированные па сжатие последовательностей полутоновых изображений / Б. Б. Казаков, С. А. Ивановский, А. Е. Лозицкий // Известия Санкт-Петербургского государственного электротехнического университета «ЛЭТИ». Сер. «Информатика, управление и компьютерные технологии». - 2007. - Вып. 1. - С. 10-17

4. Казаков Б. Б. Программная система сегментации изображений / Б. Б. Казаков // Сборник трудов конференции молодых ученых. Сер. «Информационные технологии» — 2009. — Вып. G. — с. 694-G99

5. Казаков, Б. Б. Программное средство выделения подвижных объектов па неподвижных изображениях. / Б. Б. Казаков // Технологии Microsoft в теории и практике программирования: Материалы межвузовского конкурса - конференции студентов аспирантов и молодых учёных Северо-Запада. — 2007. — С. 39 — 40

Подписано в печать 16.11.2009 г. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 1414.

Отпечатано в ООО «Издательство "ЛЕМА"»

199004, Россия, Санкт-Петербург, В.О., Средний пр., д.24, тел./факс: 323-67-74 e-mail: izd_lema@mail.ru http://www.Iemaprint.ru

Введение

Глава 1. Обзор методов выделения движения.

1.1. Постановка задачи.

1.2. Основные обозначения

1.3. Глобальные методы.

1.4. Локальные методы

1.5. Мультимасштабный подход

1.6. Фазовый метод вычисления оптического потока.

1.7. Выводы.

Глава 2. Алгоритмы вычисления оптического потока.

2.1. Регуляризованное вычисление оптического потока

2.2. Применение медианного фильтра в мультимасштабном вычислении оптического потока.

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

2.4. Выводы.

Глава 3. Выделение движущихся объектов с использованием оптического потока.

3.1. Выделение движущихся объектов как задача сегментации

3.2. Комбинированные алгоритмы сегментации.

3.3. Выделение объектов в затрудненных условиях съемки.

3.4. Выводы.

Глава 4. Программная инструментальная система визуальной разработки и испытания алгоритмов

4.1. Анализ существующих инструментальных систем

4.2. Примеры диаграмм разработанной программной инструментальной системы.

4.3. Описание выполнения диаграммы.

4.4. Результаты разработки визуальной программной инструментальной системы.

Глава 5. Параллельная реализация алгоритмов выделения объектов

5.1. Анализ алгоритмов вычисления оптического потока

5.2. Разработка параллельной реализации алгоритма медианной фильтрации изображений

5.3. Оценка скорости выполнения комбинированного алгоритма вычисления оптического потока.

5.4. Выводы.

Глава 6. Экспериментальное исследование комбинированных алгоритмов.

6.1. План экспериментального исследования комбинированного алгоритма вычисления оптического потока.

6.2. Результаты экспериментального исследования комбинированного алгоритма вычисления оптического потока

6.3. План экспериментального исследования алгоритмов выделения движущихся объектов .'.

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

6.5. Сравнение комбинированного алгоритма вычисления оптического потока с глобальными алгоритмами.

6.6. Оценка скорости выполнения разработанных алгоритмов выделения движущихся объектов.

6.7. Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

Например, в [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% по сравнению с локаль

Скорость вычисления оптического потока

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

1. J1. Шапиро, Дж. Стокман. Компьютерное зрение. М.: БИНОМ. . Лаборатория знаний, 2009. Р. 752.

2. Enkelmann W. Obstacle detection by evaluation of optical flow fields from image sequences // Image and Vision Computing. 1991. Vol. 9, no. 3. Pp. 160-8.

3. DeSouza G. N., Как A. C. Vision for Mobile Robot Navigation: A Survey // IEEE Trans. Pattern Anal. Mach. Intell. 2002. Vol. 24, no. 2. Pp. 237-267.

4. Д. Форсайт, Ж. Понс. Компьютерное зрение. Современный подход. Издательский дом «Вильяме», 2004. Р. 928.

5. Б. Яне. Цифровая обработка изображений. Техносфера, 2007.

6. Zhang Y. Advances in Image and Video Segmentation // IRM Press. 2006.

7. Viitaniemi V., Laaksonen J. Techniques for Image Classification, Object Detection and Object Segmentation // Visual08. 2008. Pp. xx-yy.

8. Lucas B. D., Kanacle T. An Iterative Image Registration Technique with an Application to Stereo Vision. 1981. Pp. 674-679.

9. Beauchemin S., Barron J. The Computation of Optical-Flow // Surveys. 1995. — September. Vol. 27, no. 3. Pp. 433-467.

10. Horn В. K. P., Schunck B. G. Determining Optical Flow // ARTIFICAL INTELLIGENCE. 1981. Vol. 17. Pp. 185-203.

11. Horn В., Schunck B. Determining Optical Flow: A Retrospective // AI. 1993. — January. Vol. 59, no. 1-2. Pp. 81-87.12. ho Kim Y., Martinez A. M., Как A. C. Robust motion estimation under varying illumination // Image and Vision Computing. 2005. Vol. 23.

12. Elad M., Teo P., Hel Or Y. On the Design of Filters for Gradient-Based Motion Estimation // JMIV. 2005.-November. Vol. 23, no. 3. Pp. 345-365.

13. HauBecker H. W., Fleet D. J. Computing Optical Flow with Physical Models of Brightness Variation.

14. Bruhn A. Variational Optic Flow Computation: Accurate Modelling and Efficient Numerics: Ph.D. thesis / Saarland University. 2006.

15. BARRON J. L., FLEET D. J., BEAUCHEMIN S. S. Performance of optical flow techniques // International Journal of Computer Vision. 1994. no. 12. Pp. 43-77.

16. Liu H., hong Hong T., Herman M., Camus T. Accuracy vs. Efficiency Trade-offs in Optical Flow Algorithms. 1996.

17. Simoncelli E. P. Design Of Multi-Dimensional Derivative Filters //In First International Conference on Image Processing. 1994. Pp. 790-793.

18. Bruhn A., Weickert J., Feddern C. et al. Real-time optic flow computation with variational methods //In CAIP 2003. Springer, 2003. Pp. 222-229.

19. Aubert G., Deriche R., Kornprobst P. Computing Optical Flow via Variational Techniques // SIAM Journal on Applied Mathematics. 1999. Vol. 60, no. 1. Pp. 156-182.

20. Alvarez L., Deriche R., Papadopoulo T., Sanchez J. Symmetrical Dense Optical Flow Estimation with Occlusions Detection // International Journal of Computer Vision. 2007. — dec. Vol. 75, no. 3. Pp. 371-385.

21. Corpetti T., MÉmin e., Pérez P. Dense Estimation of Fluid Flows // IEEE Trans. Pattern Anal. Mach. Intell. 2002. Vol. 24, no. 3. Pp. 365-380.

22. Zach C., Pock T., Bischof H. A duality based approach for realtime tv-11 optical flow // In Ann. Symp. German Association Patt. Recogn. 2007. Pp. 214-223.

23. Pock T., Unger M., Cremers D., Bischof H. Fast and exact solution of Total Variation models on the GPU // CVGPU08. 2008. Pp. 1-8.

24. Wedel A., Pock T., Zach C. et al. An Improved Algorithm for TV-LI Optical Flow. 2009. Pp. 23-45.

25. Brandt A., Israeli M., Siegel A. et al. Multigrid Solution of an Elliptic Boundary-Value Problem with Integral Constraints. 1997.

26. Alvino C., Tannenbaum A., Yezzi A., Curry C. Multigrid Computation of Rotationally Invariant Non-Linear Optical Flow // ICIP05. 2005. Pp. Ill: 1296-1299.

27. Konrad J., Dubois E. Multigrid Bayesian Estimation of Image Motion Fields Using Stochastic Relaxation // ICCV88. 1988. Pp. 354-362.

28. Bruhn A., Weickert J., Kohlberger T., Schnorr C. A Multigrid Platform for Real-Time Motion Computation with Discontinuity-Preserving Variational Methods // Int. J. Comput. Vision. 2006. Vol. 70, no. 3. Pp. 257-277.

29. A.Bruhn, J.Weickert. Towards Ultimate Motion Estimation: Combining Highest Accuracy with Real-Time Performance //In Proc. 10th International Conference on Computer Vision, Vol. 1. IEEE Computer Society Press, 2005. Pp. 749-755.

30. Amiaz T., Kiryati N. Dense Discontinuous Optical Flow via Contour-Based Segmentation // ICIP. 2005. Pp. Ill: 1264-1267.

31. Amiaz T., Lubetzky E., Kiryati N. Coarse to over-fine optical flow estimation // PR. 2007. September. Vol. 40. Pp. 2496-2503.

32. Brox T., Bruhn A., Papenberg N., Weickert J. High Accuracy Optical Flow Estimation Based on a Theory for Warping // ECCV. 2004. Pp. Vol IV: 25-36.

33. Papenberg N., Bruhn A., Brox T. et al. Highly Accurate Optic Flow Computation with Theoretically Justified Warping // Int. J. Comput. Vision. 2006. Vol. 67, no. 2. Pp. 141-158.

34. Brox T., Weickert J. Nonlinear Matrix Diffusion for Optic Flow Estimation // DAGM. 2002. P. 446 ff.

35. Weickert J., Schnorr C. Variational Optic Flow Computation with a Spatio-Temporal Smoothness Constraint // J. Math. Imaging Vis. 2001. Vol. 14, no. 3. Pp. 245-255.

36. Zimmer H., Bruhn A., Weickert J. et al. Complementary Optic Flow. // EMMCVPR / Ed. by D. Cremers, Y. Boykov, A. Blake, F. R. Schmidt. Vol. 5681 of Lecture Notes in Computer Science. Springer, 2009. Pp. 207-220.

37. Werlberger M., Trobin W., Pock T. et al. Anisotropic Huber-Ll Optical Flow // Proceedings of the British Machine Vision Conference (BMVC). London, UK: 2009. — September, to appear.

38. Lempitsky V., Roth S., Rother C. FusionFlow: Discrete-Continuous Optimization for Optical Flow Estimation // 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'08). Anchorage, USA: 2008, — June.

39. Glocker B., Paragios N., Komodakis N. et al. Optical flow estimation with uncertainties through dynamic MRFs // CVPR. 2008.

40. Weber J., Malik J., Devadas S., Michel P. Robust Computation of Optical Flow in a Multi-Scale Differential Framework // International Journal of Computer Vision. 1994. Vol. 14. Pp. 12-20.

41. Alvarez L., Weickert J., Sanchez J. A Scale-Space Approach to Nonlocal Optical Flow Calculations // Scale Space. 1999. Pp. 235-246.

42. Alvarez L., Weickert J., Sánchez J. Reliable Estimation of Dense Optical Flow Fields with Large Displacements // International Journal of Computer Vision. 2000. Vol. 39, no. 1. Pp. 41-56.

43. Battiti R., Amaldi E., Koch C. Computing optical flow across multiple scales: an adaptive coarse-to-fine strategy // International Journal of Computer Vision. 1991. Vol. 6, no. 2. Pp. 133-145.

44. Black P., M. J. Anandan. The Robust Estimation of Multiple Motions: Parametric and Piecewise-Smooth Flow Fields // COMPUTER VISION AND IMAGE UNDERSTANDING. 1996. Vol. 63, no. 1. Pp. 75-104.

45. Anandan P. A Computational Framework and an Algorithm for the Measurement of Visual Motion // International Journal of Computer Vision. 1989. Vol. 2, no. 3. Pp. 283-310.

46. Black M. J., Anandan P. Robust dynamic motion estimation over time // IEEE Proceedings of Computer Vision and Pattern Recognition. 1991. — jun. Pp. 296-302.

47. Black M. J. Recursive Non-Linear Estimation of Discontinuous Flow Fields // ECCV. 1994. Pp. A: 138-145.

48. Black M. J., Yacoob Y., Ju S. X. Recognizing Human Motion using Parameterized Models of Optical Flow // Motion-Based Recognition. 1997. P. Chapter 11.

49. Black M. J., Jepson A. Estimating Optical Flow in Segmented Images using Variable-order Parametric Models with Local Deformations // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1996. Vol. 18. Pp. 972-986.

50. Hsu S., Anandan P., Peleg S. Accurate Computation of Optical Flow by Using Layered Motion Representations. 1994.

51. Cremcrs D., Soatto S. Motion Competition: A Variational Approach to Piecewise Parametric Motion Segmentation // International Journal of Computer Vision. 2005. — may. Vol. 62, no. 3. Pp. 249-265.

52. Bruhn A., Weickert J., Schnorr C. Lucas/Kanade meets Horn/Schunck: combining local and global optic flow methods // Int. J. Comput. Vision. 2005. Vol. 61, no. 3. Pp. 211-231.

53. Simoncelli E. P. Bayesian Multi-scale Differential Optical Flow // IEEE Workshop on Image and Multidimensional Signal Processing. 1993. Pp. 128-129.

54. Castro E. D., Morandi C. Registration of Translated and Rotated Images Using Finite Fourier Transforms // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1987.-sep. Vol. PAMI-9, no. 5. Pp. 700-703. Fourier Transforms.

55. Castro E. D., Morandi C. Registration of Translated and Rotated Images Using Finite Fourier Transforms // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1987.-sep. Vol. PAMI-9, no. 5. Pp. 700-703. Fourier Transforms.

56. Heitz F., Bouthemy P. Multimodal Estimation of Discontinuous Optical Flow using Markov Random Fields // IEEE Trans. Pattern Anal. Mach. Intell. 1993. Vol. 15, no. 12. Pp. 1217-1232.

57. Blunsden E. L. A. S., Ipab R. B. F. Hidden markov models for optical flow analysis //in crowds. International Conference on Pattern Recognition. 2006. Pp. 1-460.

58. Dibos F. R. F. Moving objects segmentation using optical flow estimation // in Workshop on Mathematics and Image Analysis. 2004.

59. Brox Т., Bruhn A., Weickert J. Variational Motion Segmentation with Level Sets // ECCV. 2006. Pp. I: 471-483.62. Étienne Mémin, Pérez P., P'erez P. Joint Estimation-Segmentation of Optic Flow // In ECCV'98. 1998.

60. Memin E., Pérez P. Dense Estimation and Object-Based Segmentation of the Optical Flow with Robust Techniques. 1998.

61. Galic S., Loncaric S., Tesla E. N. Spatio-Temporal Image Segmentation Using Optical Flow and Clustering Algorithm.

62. Vidal R., Ravich A. Optical flow estimation and segmentation of multiple moving dynamic textures // In CVPR. 2005. Pp. 516-521.

63. Werlberger M., Trobin W., Pock T. et al. Anisotropic Huber-Ll Optical Flow // Proceedings of the British Machine Vision Conference (BMVC). London, UK: 2009. — September.

64. А. Альберт. Регрессия, псевдоинверсия и рекуррентное оценивание. Москва Наука.Физматлит., 1977.

65. Luettgen М. R., Karl W. С., Willsky A. S. Efficient Multiscale Regularization with Applications to the Computation of Optical Flow // IEEE Transactions on image processing. 1993. Vol. 3. Pp. 41-64.

66. Simoncelli E. P. Course-to-fine Estimation of Visual Motion // IEEE Eighth Workshop on Image and Multidimensional Signal Processing. 1993.

67. Zhang Y. Advances in Image and Video Segmentation // IRM Press. 2006.

68. Meyer F., Beucher S. Morphological Segmentation // Journal of Visual Communication and Image Representation. 1990. — September. Vol. 1, no. 1. Pp. 21-46.

69. Meyer F. Topographic Distance and Watershed Lines // Signal Processing. 1994. — July. Vol. 38, no. 1. Pp. 113-125.

70. Grosky W., Jain R. A Pyramid-Based Approach to Segmentation Applied to Region Matching // IEEE Trans. Pattern Analysis and Machine Intelligence. 1986. — September. Vol. 8, no. 5. Pp. 639-650.

71. Adams R., Bischof L. Seeded Region Growing // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1994. Vol. 16, no. 6. Pp. 641-647.

72. Pratt W. K. Digital Image Processing: PIKS Scientific Inside. Wiley-Interscience, 2007.

73. HauBecker H. W., Fleet D. J. Computing Optical Flow with Physical Models of Brightness Variation // IEEE Trans. Pattern Analysis and Machine Intelligence. 2001. Vol. 23. Pp. 661-673.

74. В. П. Дьяконов. Matlab R2006/2007/2008. Simulink 5/6/7. Основы применения. Солон-Пресс, 2008.

75. P. Гонсалес, Р.Вудс, С. Эддинс. Цифровал обработка изображений в среде MATLAB . Техносфера, 2006.

76. Валерий Очков. Mathcad 14 для студентов и инженеров. Русская версия. БХВ-Петербург, 2009.

77. Алексеев Е.Р., Чеснокова О.В., Рудченко Е.А. Scilab: Решение инженерных и математических задач . Бином. Лаборатория знаний, 2008.

78. John W. Eaton. Gnu Octave Manual . Network Theory Ltd., 2008.

79. Питер Блюм. LabVIEW. Стиль программирования. ДМК-Пресс, 2008.

80. Ю. В. Визильтер, С. Ю. Желтов, В. А. Князь, А. Н. Ходарев, А. В. Моржин. Обработка и анализ цифровых изображений с примерами на LabVIEW и IMAQ Vision. ДМК-Пресс, 2008.

81. Дж. Дэбни, Т. Харман. Simulink 4. Секреты мастерства. Бином. Лаборатория знаний, 2003.

82. Che S., Boyer М., Meng J. et al. A performance study of general-purpose applications on graphics processors using CUDA //J. Parallel Distrib. Comput. 2008. Vol. 68, no. 10. Pp. 1370-1380.

83. NVIDIA. NVIDIA CUDA Programming Guide 2.0. 2008.

84. NVIDIA. NVIDIA CUDA С Programming Best Practices Guide 2.0. 2008.

85. Ryoo S., Rodrigues С. I., Stone S. S. et al. Program optimization space pruning for a multithreaded gpu // CGO ,/ Ed. by M. L. Soffa, E. Duesterwald. ACM, 2008. Pp. 195-204.

86. Zach C., Pock Т., Bischof H. A Duality Based Approach for Realtime TV-LI Optical Flow // Pattern Recognition (Proc. DAGM). Heidelberg, Germany: 2007. Pp. 214-223.

87. Т. Кормен, Ч. Лейзерсон, P. Ривест, К. Штайи . Алгоритмы: построение и анализ. Вильяме, 2007.

88. Huang Т., Yang G., Tang G. A Fast Two-Dimensional Median Filtering Algorithm // ASSP. 1979. —February. Vol. 27. Pp. 13-18.

89. Optimizing parallel reductiion in cuda. 2007.

90. Tzeng S., Wei L.-Y. Parallel white noise generation on a GPU via cryptographic hash // I3D '08: Proceedings of the 2008 symposium on Interactive 3D graphics and games. New York, NY, USA: ACM, 2008. Pp. 79-87.

91. Weiss B. Fast median and bilateral filtering // ACM Trans. Graph. 2006. Vol. 25, no. 3. Pp. 519-526.

92. Black M. J., Anandan P. The robust estimation of multiple motions: parametric and piece-wise-smooth flow fields // Comput. Vis. Image Underst. 1996. Vol. 63, no. 1. Pp. 75-104.

93. Mémin É., Pérez P. Dense estimation and object-based segmentation of the optical flow with robust techniques // IEEE Transactions on Image Processing. 1998. Vol. 7, no. 5. Pp. 703-719.

94. Roth S., Black M. J. On the Spatial Statistics of Optical Flow // Int. J. Comput. Vision. 2007. Vol. 74, no. 1. Pp. 33-50.

95. Baker S., Scharstein D., Lewis J. P. et al. A Database and Evaluation Methodology for Optical Flow // ICCV. IEEE, 2007. Pp. 1-8.