Распознавание объектов в видеопотоке. видеопоток. Метод и алгоритмы поиска объекта в видеопотоке
 Скачать 3.84 Mb.
|
|
2.7 Структурная модель На основании построенной функциональной модели можно определить основные модули системы: модуль вычисления вектора дескрипторов объекта; модуль вычисления гистограммы; модуль извлечения кадров; модуль вычисления вектора дескрипторов кадра; модуль поиска областей претендентов; модуль идентификации. На рисунке 2.14 представлена диаграмма основных компонентов системы. Модуль вычисления вектора дескрипторов объекта выполняет функции A11, A12, 75 A13, A14, A15, A16, представленные в IDEF0-диаграммах. Модуль извлечения кадров выполняет функции A31, A32, A33, кадры из которого поступают в модуль вычисления вектора дескриптора кадра и в модуль поиска областей претендентов. Функция A2 выполняется модулем вычисления гистограммы. Модуль вычисления вектора дескрипторов кадра выполняет функции A41, A42, A43. Модуль поиска областей претендентов реализует функции A51, A52, A53. Идентификатор выполняет функцию A6. Рисунок 2.14 – Структурная диаграмма Структуры модулей вычисления многомерной матрицы дескрипторов объекта, извлечения кадров, вычисления вектора дескрипторов кадра и поиска областей претендентов представлены в последующих подразделах. 2.7.1 Структура модуля вычисления вектора дескрипторов объекта На рисунке 2.15 представлена структура модуля вычисления вектора дескрипторов объекта. Модуль состоит из следующих элементов: 1. Полутоновый преобразователь. Выполняет функцию A11. 2. Преобразователь масштаба. Выполняет функцию A12. 3. Преобразователь наклона. Моделирует изменения наклона камеры на заданные углы. Реализует функцию A13. Модуль вычисления гистограммы Модуль вычисления вектора дескрипторов объекта Модуль поиска областей Модуль извлечения кадров Модуль вычисления вектора дескрипторов Идентификатор 76 4. Генератор поворота. Выполняет функцию A14. 5. Поисковик ключевых точек. Выполняет функцию A15. 6. Вычислитель дескрипторов. Выполняет функцию A16. Рисунок 2.15 – Структура модуля вычисления вектора дескрипторов объекта 2.7.2 Структура модуля извлечения кадра Структура модуля извлечения кадра представлена на рисунке 2.16. Модуль состоит из следующих элементов: 1. Демультиплексер. Выполняет A31 функцию демультиплексирования видеопотока из контейнера в сжатый формат видео. 2. Декодер. Выполняет A32 функцию декодирования сжатого формата видео. 3. Компонента выделения кадра. Выполняет A33 функцию выделения кадра из декодированного видеопотока. Рисунок 2.16 – Структура модуля извлечения кадра Преобразовател ь наклона Вычислитель дескрипторов Преобразователь масштаба Полутоновый преобразователь Поисковик ключевых точек Генератор поворота Демультиплексер Декодер Выделитель кадра 77 2.7.3 Структура модуля вычисления вектора ключевых точек кадра Структура модуля вычисления вектора ключевых точек кадра представлена на рисунке 2.17. Модуль состоит из следующих элементов: 1. Полутоновый преобразователь. Выполняет функцию A41. 2. Поисковик ключевых точек. Находит ключевые точки на кадре. Выполняет функцию A42. 3. Вычислитель дескрипторов. Вычисляет дескрипторы ключевых точек. Выполняет функцию A43. Рисунок 2.17 – Структура модуля вычисления вектора ключевых точек кадра 2.7.4 Структура модуля поиска областей претендентов Структура модуля поиска областей претендентов представлена на рисунке 2.18. Модуль состоит из следующих элементов: 1. Определитель пересечения дескрипторов. Выполняет функцию A51. 2. Кадровый фильтр. Пропускает кадр с определённым номером, полученным из определителя пересечения дескрипторов. Выполняет функцию A52. 3. Определитель областей. Выполняет функцию A53. Полутоновый преобразователь Поисковик ключевых точек Вычислитель дескрипторов 78 Рисунок 2.18 – Структура модуля поиска областей претендентов 2.8 Выводы 1. Функциональный анализ системы поиска объекта показал, что в структуре программной системе должны быть включены в качестве базовых функций следующие: нахождение ключевых точек; вычисление дескрипторов ключевых точек; нахождение общих ключевых точек по дескрипторам; идентификация кадра на предмет наличия изображения объекта. 2. Алгоритм поиска объекта должен строиться на основе вычисления дескрипторов, так как такой подход позволяет избежать влияния проективных искажений. 3. Для увеличения скорости работы алгоритма необходимо перед началом поиска подвергнуть изображение объекта проективными искажениями для нахождения ключевых точек и вычисления дескрипторов объекта. 4. Для повышения вероятности обнаружения дескрипторный поиск ключевых точек необходимо дополнить шагом сравнения цветовых гистограмм. Определитель пересечения дескрипторов Кадровый фильтр Определитель областей 79 3 Проектирование и реализация программы поиска объекта в видеопотоке Описанные в разделе 2 функции и структурные элементы системы позволяют провести проектирование этой системы. Диаграммы построены с помощью языка UML [70]. 3.1 Проектирование классов системы Структурная модель позволяет перейти к описанию классов системы, к описанию взаимосвязей. Для детального описания предметной области добавлены следующие элементы: область; ключевая точка; кадр. На рисунке 3.1 представлена диаграмма классов системы. Структура классов полностью согласуется со структурной моделью системы. 3.2 Сценарии работы системы Функциональная модель системы позволяет определить основные сценарии функционирования: инициализация изображения объекта; поиск кадров объекта в видеопотоке. 80 Рисунок 3.1 – Диаграмма классов системы 81 Для иллюстрации событий, связывающих внешних исполнителей с системой, в языке UML существуют специальные обозначения, позволяющие создавать диаграммы последовательностей, являющиеся отправной точкой для проектирования взаимодействия объектов [71]. Построенная диаграмма классов позволяет описать выделенные сценарии. В следующих подразделах представлены диаграммы последовательностей сценариев функционирования. 3.2.1 Сценарий инициализации изображения объекта На рисунке 3.2 представлен сценарий инициализации изображения объекта. Вектор дескрипторов ключевых точек объекта вычисляется параллельно с вычислением гистограммы изображения. Вычислитель вектора дескрипторов объекта генерирует трёхмерную матрицу проективно искажённых полутоновых изображений образца при помощи преобразователя масштаба, преобразователя наклона, генератора поворота и полутонового преобразователя. Вычисленная гистограмма передаётся в идентификатор, а вектор дескрипторов объекта – в поисковик областей претендентов. Инициализация изображения объекта завершается после получения сообщения об установки дескрипторов объекта и значений гистограммы. 3.2.2 Сценарий поиска кадров объекта в видеопотока На рисунке 3.3 представлен сценарий поиска кадров объекта видеопотоке. Входной видеопоток поступает в демуксер для извлечения закодированного видео из контейнера. Демуксированное видео поступает в декодер для представления видео в набор байт, который поступает в выделитель кадра. Согласно параметрам, пока выделитель кадра успешно извлекает из последовательности декадированных байт кадр, выполняется процесс поиска объекта в видеопотоке. Полученный кадр передаётся в вычислитель ключевых точек кадра и в поисковик области претендентов. Вычислитель ключевых точек кадра преобразует кадр в полутоновое изображение, на котором осуществляет поиск ключевых точек с 82 вычислением дескрипторов. Если ключевые точки найдены, то поисковик ключевых точек передаёт ключевые точки вычислителю дескрипторов. Если вектор дескрипторов кадра не является пустым, то дескрипторы передаются поисковику областей предендентов для нахождения общих дескрипторов P с дескрипторами изображения поискового объекта. Если пересечение дескрипторов является не пустым множеством (P≠{0}), то это множество отправляется определителю областей и подаётся информация о номере кадра кадровому фильтру, который пропускает соответствующий кадр в идентификатор. Из определителя областей поступают области кадра в идентификатор. Если объект локализуется на кадре, то идентификатор сохраняет текущий кадр. 83 Рисунок 3.2 – Сценарий инициализации изображения объекта 84 Рисунок 3.3 – Сценарий поиска кадров объекта в видеопотоке 85 3.3 Реализация программы поиска объекта в видеопотоке Спроектированные классы и взаимодействия системы позволяют осуществить реализацию программы поиска объекта в видеопотоке. Реализация программы должна удовлетворять требованиям к программе и соответствовать построенным функциональной и структурной моделям. Далее описываются технологии разработки программы для эффективного выполнения поиска объекта. 3.4 Описание технологий Программа работает в двух режимах согласно описанным сценариям работы системы: режим инициализации изображения объекта; режим поиска кадров объекта в видеопотоке. Поиск кадров с изображением объекта в видеопотоке требует гораздо большего количества выполнения вычислительных операций, чем инициализация изображения объекта. Реализация программной системы должна быть ориентирована на эффективное использование вычислительных ресурсов для удовлетворения требования к скорости обработки. Предлагается использовать следующие технологии: конвейерная обработка данных; пакетная обработка данных; CUDA для параллельных вычислений в видеокарте. Конвейерная архитектура позволит выполнять обработку видео кадров одновременно на всех компонентах системы [72]. Тем самым уменьшая среднее время обработки кадра до максимального времени обработки одного из компонентов системы. В идеальном разбиении на n компонент время обработки кадров практически уменьшится в n раз. 86 Решение об отсутствии объекта на кадре может быть принято на этапе определения пересечения дескрипторов кадра и изображения объекта, поэтому предлагается выделять больше вычислительных ресурсов операциям поиска ключевых точек, вычисления дескрипторов, определения пересечения дескрипторов. Для минимизации времени поиска объекта в видеопотоке предлагается реализовать основные функции с использованием пакетной обработки данных: технология SSE2 (Streaming SIMD Extensions 2). Её назначение – повысить эффективность операций со 128-разрядными данными в формате плавающей точки с двойной точностью и с целочисленными данными [73]. Все современные процессоры поддерживают технологию SSE2, в отличие от технологий SSE4, AVX и AVX2. Для оптимального использования ресурсов предлагается при наличии видеокарты с поддержкой технологии CUDA использовать вычислительные ресурсы видеокарты. CUDA – это архитектура параллельных вычислений от NVIDIA, позволяющая существенно увеличить вычислительную производительность благодаря использованию GPU (графических процессоров). [74]. На основании результатов вычисления алгоритмической сложности модифицированного метода SURF, процесс поиска ключевых точек требует большое количество вычислительных операций и является легко распараллеливаемым в отличии процесса вычисления дескриптора. Пусть поиск ключевых точек осуществляется в видеокарте при её наличии. Тогда для операции вычисления дескриптора будет отдаваться больше процессорных вычислительных ресурсов. На рисунке 3.4 представлена диаграмма развёртывания. Представленная диаграмма развёртывания позволяет увеличивать экземпляры компонент при увеличении количества вычислительных ресурсов засчёт интерфейсов взаимодействия между компонентами, которые управляют доступом на запись и чтение необходимой информации для обмена. 87 Рисунок 3.4 – Диаграмма развёртывания 88 Для реализации программ использованы следующие программные средства: — языки программирования C++ и Assembler с использованием SSE2. — библиотека OpenCV 2.4 содержит функции демуксирования, декодирования видеопотока, вычисление SURF дескрипторов, алгоритм RANSAC [16]. — набор инструментов CUDA SDK. — операционная система Microsoft® Windows 7. — среда разработки: Microsoft® Visual Studio 2010. — система контроля версий: Tortoise SVN. Копия свидетельства о регистрации программы «Object tracking PS» [75] (программа слежения за объектом в видеопотоке) представлена в Приложении Б. 3.5 Выводы На основе проведенных исследований можно сделать следующие выводы: 1. Для реализации программы поиска объекта на изображении и повышения скорости обработки кадров необходимо использовать конвейерную обработку данных; пакетную обработка данных, CUDA для параллельных вычислений в видеокарте и объектно-ориентированное программирование. 2. Разработанный набор классов с выделенными методами позволяет полностью реализовать все функции системы. 3. Спроектированная структура компонентов предоставляет возможность разворачивать программную систему на все доступные процессоры, включая видеопроцессор. 89 4 Тестирование системы Реализованная программа позволяет осуществить автоматическое тестирование разработанного алгоритма поиска объекта в видеопотоке с использованием текстового формата вывода результатов обнаружения. Необходимо разработать схему тестирования и написать исполняемые скрипты для проведения тестов. 4.1 Схема проведения тестирования Согласно поставленным требованиям система должна быть инвариантна к проективным преобразованиям, устойчива к шуму и находить объект в видеопотоке в режиме реального времени, поэтому предлагается исследовать каждую программу на удовлетворение этим требованиям. Для этого подготавливаются тесты с видеопотоками, на которых изображение определённого объекта подвергается проективным преобразованиям. В качестве сравнения результатов тестирования с аналогами используются готовые решения от Vuforia [14], Kudan AR [15] и реализации методов SURF, ASIFT совместно с методом RANSAC. В тестированиях предлагается использовать метрику ROC [76] для численного измерения качества нахождения объекта в видеопотоке различными методами. ROC-кривая имеет особую популярность в области анализа классификаций и отображает зависимость доли верно классифицированных положительных событий в общем числе положительных событий от доли неверно классифицированных отрицательных событий в общем числе отрицательных событий, поэтому на графике точка (0;1) соответствует идеальному классификатору. Для построения ROC-кривых необходимо вычислить: — сумму истинно-положительных значений (true-positive, TP), — сумму ложно-положительных значений (false-positive, FP), — сумму истинно-отрицательных значений (true-negative, TN), 90 — сумму ложно-отрицательных значений (false-negative, FN). TP, FP, FN, TN определяются по следующим формулам 4.1, 4.2, 4.3, 4.4. j i i j Th TP (4.1) 1 j i i j Th FP (4.2) j i i j Th FN (4.3) 1 j i i j Th TN (4.4) График ROC-кривой есть график зависимости доли истинно-положительных значений (TPR, формула 4.5) от доли ложно-положительных значений (FPR, формула 4.6) [77]. i i i i TP TPR TP FN (4.5) i i i i FP FPR FP TN (4.6) Численный показатель площади под ROC кривой (AUC) определяется по формуле 4.7 [76]. 1 1 1 2 i i i i i AUC TPR TPR FPR FPR (4.7). Программная система работает эффективно, если использует все предоставленные аппаратно-программные средства в течение всего времени работы. В качестве критериев эффективности предлагается вычислять среднюю загрузку процессоров и среднюю загрузку процессоров на обработку видеопоследовательности в секунду. Средняя загрузка процессоров вычисляется по следующей формуле: 1 0 1 n i i L CPU n , где n – количество процессоров, CPU i – средний процент загрузки i-ого процессора в секунду. 91 Средняя загрузка процессоров на обработку видеопоследовательности в секунду вычисляется по формуле: s L L T , где L s – средняя загрузка процессоров, T – время выполнения программы на обработку видеопоследовательности. Чем ближе значение L s к 0, тем дольше по времени необходимо использовать вычислительных ресурсов для обработки видеопоследовательности. Схема тестирования приведена на рисунке 4.1. Тест содержит изображение объекта для поиска, специально подготовленный видеопоток и информацию о номерах кадров с изображением объекта. Выполнение теста осуществляется одним реализованным методом специальной программой. Результат выполнения теста – значение вычисленной метрики. Задача скрипта – получить результат метрики по выходным данным отработанной программы на определённом видеофайле с изображением объекта с использованием информации об ожидаемых результатах (список номеров кадров видеофайла с изображением объекта). Рисунок 4.1 – Схема проведения тестирования По знанию системы тестирование производится «чёрного ящика» через специальные интерфейсы взаимодействия с программой [79]. Для проведения тестирования написан скрипт на языке python [80]. Скрипт выполняет |