Содержание к диссертации
Введение
Глава 1. Современные модели, методы и алгоритмы компьютерного стереозрения 14
1.1. Компьютерное стереозрение с точки зрения
искусственноинтеллектуальных систем 14
1.2. Обзор существущих моделей, методов и алгоритмов компьютерного стереозрения 16
1.2.1. Математические модели компьютерного стереозрения 17
1.2.2. Способы получения стереоизображений 20
1.2.3. Классификация алгоритмов стереосопоставления 21
1.2.4. Методы и алгоритмы получения трёхмерных данных по карте глубины 24
1.3. Выводы о существующих моделях, методах и алгоритмах компьютерного стереозрения 25
Глава 2. Математическая модель компьютерного стереозрения 26
2.1. Модель копьютерного стереозерния 27
2.2. Выводы 35
Глава 3. Методы получения и анализа стереопотока 36
3.1. Задачи систем стереозрения реального времени 36
3.2. Метод синхронизации камер 37
3.3. Метод стереокалибровки камер 42
3.4. Метод ректификации изображений на основании данных стереокалибровки 45
3.5. Метод ректификации стереоизображений по сцене без калибровки камер 46
3.6. Цветовая калибровка изображений 60
3.7. Передача изображений 63
3.8. Модификации локальных алгоритмов стереосопоставление 71
3.8.1. Интегральные градиентные изображения 74
3.8.2. Оценка алгоритмов стереосопоставления 75
3.8.3. Пост-фильтрация диспаритетов 82
3.8.4. Выделение множества точек для построения модели 84
3.8.5. Применение GPGPU к задаче стереосопоставления 87
3.8.6. Выводы о модификациях локальных алгоритмов стереосопоставления 93
3.9. Трёхмерное моделирование по карте глубины 93
3.10. Подавление шумов 95
3.11. Выводы о методах получения и анализа стереопотока 98
4. Анализ и разработка программного комплекса 100
4.1. Архитектура системы 100
4.2. Характеристики производительности системы 108
4.3. Практические приложения распределённого программного комплекса компьютерного стереозрения 111
4.4. Выводы 112
Заключение 114
Список литературы 115
- Обзор существущих моделей, методов и алгоритмов компьютерного стереозрения
- Метод ректификации стереоизображений по сцене без калибровки камер
- Применение GPGPU к задаче стереосопоставления
- Практические приложения распределённого программного комплекса компьютерного стереозрения
Введение к работе
Актуальность темы. В настоящее время формирование и обработка стереоизображений являются одними из актуальных направлений научных и прикладных исследований. Практические разработки в области компьютерного стереозрения активно ведутся лабораториями всего мира; так в конце 2012 г. были опубликованы новые результаты исследований лабораторий School of electrical and computer engineering Университета Оклахомы (г. Норман, США), Video Processing Laboratory Университета Калифорнии (г. Сан-Диего, США), Intelligent system research group института исследований и технологии (г. Мадрид, Испания), Microsoft Research Cambridge (г. Кембридж, Великобритания). Информационные системы компьютерного зрения решают задачи контроля производства, безопасности, автоматизации документооборота, удалённого присутствия, представления информации и др. Алгоритмы компьютерного зрения используются для навигации мобильных роботов, беспилотных летательных аппаратов, автомобилей и т.д. Решение задач высокоскоростной обработки изображений является важным показателем производительности аппаратно-программных комплексов.
Несмотря на то, что практическому решению задач в области стереозрения уделяется существенное внимание, до сих пор математические модели и теоретические методы были разработаны лишь для этапов калибровки фото- и видеокамер и задач стереосопоставления. Осуществлялись попытки включить модуль машинного стереозрения в математическую модель решения прикладных задач. Во многих известных моделях получение стереопар и стереосопоставление трактуются как «чёрные ящики». Так, А.Ю. Кручинин рассматривает стереозрение как часть модели адаптивной системы для навигации подвижного робота, а формирование потока снимков осуществляет подсистема взаимодействия с объектом. Л.В. Паутовой была предложена математическая модель лишь для задачи стереовизуализации. Новые методы и алгоритмы стереоспоставления создаются ведущими лабораториями: группа под управлением Дж. Шоттона (Кембридж, Великобритания) предлагает подход к распознаванию поз человека по изображениям, группа Т. Канаде (Карнеги-Меллон, США) предлагает решения трекинга объектов в цилиндрических координатах в реальном масштабе времени.
Представленная диссертационная работа призвана восполнить пробел в этом классе методов и моделей: актуальным является создание математической модели, комплекса методов и алгоритмов, включающих ряд существующих разрозненных наработок в области компьютерного стереозрения, а также новые компоненты, описывающие синхронизацию потоков изображений и ректификацию изображений.
Разработка модели и методов захвата стереоизображений позволяет подойти к задаче получения стереопотока с точки зрения её программного воплощения. Это даёт возможность в процессе захвата стереоизображений реализовать адекватные существующим аппаратным комплексам программно-аппаратные системы с необходимым разрешением и частотой кадров минимальными техническими средствами, например, использованием ноутбука со встроенной и одной дополнительной web-камерой.
Диссертационная работа выполнена на кафедре цифровых технологий Воронежского государственного университета по НИР «Разработка новых методов обработки, хранения, передачи и защиты информации в информационно- коммуникационных системах» № ГР 01200956642 (2009-2010 гг.); «Разработка новых методов обработки, хранения и передачи информации в информационно- коммуникационных системах» № ГР 01201170666 (2011 г.) аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы».
Цель и задачи исследования. Цель работы - исследование и создание теоретических методов и алгоритмов анализа, подготовки и фильтрации изображений на основе модели информационных процессов получения и преобразования стереоизображений для систем компьютерного стереозрения.
Для достижения цели в работе решались следующие задачи:
-
Разработка модели стереозрения, совместимой с современными моделями и методами стереовизуализации, трёхмерной визуализации, алгоритмами стереоспоставления и стабилизации изображения, экспертными оценками методов синхронизации.
-
Создание комплекса методов получения стереопары: синхронизации потоков изображений, цветовой калибровки стереоизображений, ректификации изображений и передачи стереоизображений; фильтрации карты глубины; распараллеливания локальных алгоритмов стереосопоставления; генерации и визуализации пространственных данных. Исследование методов передачи стереоизображений по каналам связи.
-
Разработка и исследование алгоритмов анализа, подготовки и фильтрации изображений с камер и дальнометрических изображений в системах компьютерного стереозрения; алгоритмов формирования трёхмерных моделей по дальнометрическим изображениям и других алгоритмов, реализующих предложенные методы. Создание программного комплекса, реализующего предложенные алгоритмы получения, обработки и визуализации стереоизображений, особенностью которого является слабая связность модулей, кросс-платформенная реализация и ориентированность на параллельную обработку данных.
Объект исследования - данные в виде цифровых изображений и стереоизображений, получаемые от видеокамер, дальнометрические изображения, пространственные полигональные модели; предмет исследования - модель преобразования информации в системах стереозрения, методы фильтрации изображений и алгоритмы анализа цифровых и дальнометрических изображений.
Методы исследования. При выполнении работы использовались: методы математического и компьютерного моделирования, теории алгоритмов, теории вероятностей, параллельной и распределённой обработки данных, численные методы, методы визуального проектирования.
Новизна работы:
1. Создана и исследована единая расширяемая модель получения и обработки стереоизображений, совместимая с большинством современных разработок в сфере компьютерного зрения, дающая возможность использовать как существующие, так и вновь создаваемые методы и алгоритмы для реализации её частей. Предлагаемая модель допускает возможность параллельной независимой визуализации стереоизображений и трёхмерных моделей снимаемой сцены в реальном масштабе времени.
-
-
Разработаны: теоретический метод синхронизации потоков изображений с USB-камер, использующий особенности частотного распределения кадров и обеспечивающий необходимую точность синхронизации; оптимизационный теоретический метод ректификации стереопары по сцене без предварительной стереокалибровки камер на основе метода стабилизации видеопотока, преимуществом которого является полностью автоматический подход; теоретический метод фильтрации карты глубины, основанный на гипотезе Хенкеля о связности диспаритетов, предназначенный для исключения ошибок алгоритма стереосопоставления; теоретический метод построения полигональных моделей по упорядоченному множеству точек.
-
Созданы алгоритмы синхронизации потоков изображений с USB-камер; фильтрации карт диспаритетов на основе гипотезы Хенкеля; ректификации изображений с пары камер по сцене без стереокалибровки; формирования трёхмерных полигональных моделей для визуализации в реальном времени. Разработан кросс-платформенный распределённый комплекс программ, реализующий предложенные алгоритмы фильтрации карт диспаритетов, ректификации изображений и формирования трёхмерных полигональных моделей. Особенностью комплекса является слабая связность модулей и ориентированность на работу в реальном масштабе времени.
Практическая значимость результатов работы заключается в том, что созданные модель, методы, алгоритмы и программы можно использовать для создания, модификации и развития систем компьютерного стереозрения. Это достигается тем, что предлагаемые разработки реализуют модульную концепцию, а все алгоритмы рассчитаны на выполнения в реальном масштабе времени. Возможность замены модулей с учётом выбора платформы внедрения позволяет использовать компоненты систем в приложениях расширенной и виртуальной реальности, мобильных роботах и промышленных системах. Большинство систем компьютерного зрения решает конкретные задачи с использованием специально подобранного оборудования, в то время как предлагаемые подходы позволяют абстрагироваться от оборудования и программных зависимостей.
Область исследования - содержание диссертации соответствует Паспорту специальности 05.13.17 - «Теоретические основы информатики» (физико- математические науки), область исследований соответствует п. 2 «Исследование информационных структур, разработка и анализ моделей информационных процессов и структур»; п. 5 «Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечения; разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений»; п. 7 «Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил. Моделирование формирования эмпирического знания».
Реализация результатов исследования. Результаты диссертации в форме единой модели компьютерного стерезрения, метода и алгоритма фильтрации карт глубины, метода и алгоритма синхронизации USB-камер используются в учебном процессе Воронежского государственного университета при чтении спецкурсов, выполнении выпускных квалификационных и курсовых работ.
Основные результаты, выносимые на защиту:
-
-
-
Модель компьютерного стереозрения, включающая формирование стереопотока по потокам кадров с двух видеокамер, трёхмерную и стерео- визуализацию сцены по её изображениям, и результаты её исследования.
-
Теоретические методы: а) синхронизации потоков изображений с камер с USB- интерфейсом, основанный на статистической модели камеры и внесении корректирующих поправок; б) ректификации изображений без калибровки камер, базирующийся на подходе к стабилизации видео-потока и позволяющий производить ректификацию стереопотока, опираясь на изображения сцены; в) фильтрации карты глубины; г) построения полигональных моделей по упорядоченному множеству точек для трёхмерной визуализации снимаемых сцен в реальном масштабе времени.
-
Параллельные алгоритмы, реализующие методы: а) синхронизации изображений с USB-камер; б) ректификации изображений без калибровки камер; в) алгоритм фильтрации карт глубины; г) алгоритм формирования трёхмерной полигональной модели по облаку точек для визуализации в реальном масштабе времени. Комплекс программ для разработанных методов и алгоритмов, включающий: модуль захвата и синхронизации изображений, модуль ректификации изображений, модуль стерео- визуализации и модуль трёхмерной визуализации, особенностью которого является слабая связность модулей, кросс-платформенная реализация и ориентированность на параллельную обработку данных.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на XVII Всероссийской научно-методической конференции «Телематика'2010», г. Санкт-Петербург, 2010 г.; IX-XI международных научно-методических конференциях «Информатика: проблемы, методология, технологии», г. Воронеж, 2009-2011 гг.; Всероссийской научной конференции студентов и аспирантов «Молодые исследователи - регионам», г. Вологда, 2009 г., Всероссийской научной конференции «Современные проблемы математического моделирования, супервычислений и информационных технологий», г. Таганрог, 2012 г.
Публикации. Основные результаты диссертации опубликованы в 9 печатных изданиях [1-9], в том числе три [7-9] - из списка изданий, рекомендованных ВАК РФ.
Личный вклад автора. Основные результаты по теме диссертации получены лично автором. Постановки задач диссертации предложены научным руководителем. Разработка моделей информационных процессов и методов проводились совместно всеми соавторами работ, в которых они опубликованы, в том числе и автором. Проведение рассуждений и вывод аналитических соотношений при разработке моделей, методов и алгоритмов, обоснование моделей и методов, их исследование и практическая реализация в виде алгоритмов фильтрации, синтеза и обработки изображений, информационных структур и программ, проверка достоверности результатов, получение выводов и их интерпретация выполнены автором.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 102 наименований и 6 приложений. Объем диссертации составляет 144 страницы, включая 114 страниц основного текста, содержащего 44 рисунка и 2 таблицы.
Обзор существущих моделей, методов и алгоритмов компьютерного стереозрения
На настоящий момент существует большое число бесплатных программных решений в области компьютерного стереозрения [66]. Многие открытые программные модули, такие как библиотека Zitnick-Kanade [56], являются узко специализированными или экспериментальными. Адаптация подобных библиотек для новых задач компьютерного зрения подчас является нетривиальной, поэтому разработчики часто предпочитают самостоятельную реализации известных алогритмов и даже создании новых теоретических методов. В этом свете особняком стоит универсальная библиотека OpenCV, которая сейчас являются стандартом де-факто при разработке систем компьютерного зрения. Рассмотрим существующие решения в области моделей, методов, алгоритмов и реализованных программных комплексов компьютерного зрения.
В классических книгах по компьютерному зрению Д. Форсайт и Ж. Понс [96], а также Л. Шапиро и Дж. Стокман [44] рассмотривают актуальные на настоящий момент модели камер. Каждый из подходов учитывает только часть существующих в реальности искажений, которым подвержено изображение в оптической системе цифровой камеры. Искажения характерны для любой оптической системы, например, к ним относятся дисторсии и иные геометрические искажения, неоднородная светового потока и хроматическая дисторсия. Кроме того, поскольку проекционной поверхностью для снимаемой сцены является ПЗС-матрицы (прибор с зарядовой связью), то особенности её устройства привносят дополнительные искажения, к которым можно отнести неоднородность матрицы, блюминг («стекание» яркости в соседние пиксели), отсечение яркости, эффект дискретизации. Как правило, при моделировании камер ограничиваются моделями оптической системы. Наиболее простой моделью камеры является модель камеры обскуры [96]. В её основе лежит предположение, что линза обладает нулевой толщиной и кривизной, а значит, для нахождения проекции точки на плоскость изображения можно воспользоваться уравнением перспективной проекции. Для большинства практических задач данная модель является достаточной. Неприменимой она будет лишь для случаев существенных геометрических искажений, вносимых непосредственно оптической системой. Так, подобные искажения возникают при использовании специализированных камер (fish eye) или при съёмке близко расположенных объектов. В таких случаях применяется проективная модель камер, использующая математический аппарат, основанный на аффинном и проективном преобразованиях. Следует отметить, что несмотря на различные уравнения, лежащие в основе моделей, обе модели могут быть представлены одной системой уравнений, а модель камеры-обскуры может быть сведена к частному случаю проективной модели. Попытка формализовать понятие цифрового изображения сделана также в книге Л. Шапиро и Дж. Стокмана [44]. Так, в книге в противоположность аналоговому изображению, цифровое изображение представлено в виде дискретной функции, определённой на прямоугольной матрице [44]. В работе В. Крашенинникова [74] цифровые изображения рассматриваются как случайные поля, а изменение изображения во времени – как случайные процессы. Простейшая модель случайного поля как дискретной функции на прямоугольной сетке с единичным шагом, практически, полностью аналогична модели Л. Шапиро и Дж. Стокмана [44]. Также в работе [44] приводятся модели изображений с марковскими свойствами, в основе которых также лежит дискретная прямоугольная область определения поля. В. Крашенинников также рассматривает [74] волновые модели изображений. Наиболее интересными представляются предложенные в работе модели, описывающие изображения как векторные случайные поля. Данные модели наиболее точно могут представлять цветные изображения, получаемые с цифровых камер. Разработка модели последовательности изображений, получаемых с камеры, является важной задачей при создании систем компьютерного зрения реального времени. В упоминавшейся выше работе В. Крашенинникова [74] последовательность изображений трактуется как дискретная размерность случайного поля: два измерения совпадают с измерениями изображения, а третье измерение соответствует номерам изображений в последовательности. Слабостью данного представления является отсутствие возможности получить значение временного интервала между последовательными кадрами, а также синхронизировать последовательности изображений. Кроме того, практические исследования, представленные в данной работе, показали, что получение изображений с USB-камер не является периодическим процессом, поэтому существующие модели синхронизации периодических и квазипериодических колебаний для данного поцесса не могут быть применены. В качестве модели последовательности изображений, решающей обозначенные проблемы, можно рассматривать поток событий [68]. Поток событий описывает вероятностные характеристики наступления очередного события, при этом каждому событию ставится в соответствие момент его наступления. Важной особенностью модели потоков событий является знание об уже наступивших событиях: значения уже прошедших интервалов можно учитывать при рассчёте и корректировке статистических характеристик камеры. При этом следует учитывать свойство стационарности потока событий, исключающее возможность описать поток событий как марковский процесс. Отсутствие корреляций между последовательными межкадровыми интервалами позволяет непосредственно использовать их величину как фазовое пространство динамической системы камеры. Несмотря на то, что практическому решению задач в области стереозрения уделяется существенное внимание, до сих пор математический аппарат был разработан только для этапов калибровки камер и задач стереосопоставления. На настоящий момент существуют лишь попытки включить систему машинного стереозрения в математическую модель решения той или иной прикладной задачи в качестве модуля. В известных моделях получение стереопар и стереосопоставление рассматриваются как «чёрные ящики». Так, А.Ю. Кручинин рассматривает подсистему стереозрения как часть модели адаптивной системы стереозрения для подвижного робота [75]; внутренними параметрами системы он полагает алгоритмы стереосопоставления и их характеристики, входными – поток снимков (без конкретизации термина), выходными – трёхмерные модели пространства в совокупности с достоверностью и сложностью их формирования. Формирование потока снимков в предлагаемой модели осуществляет уже отдельная подсистема взаимодействия с объектом. Л.В. Паутовой [83] была предложена математическую модель только для смежной задачи стереовизуализации. Данная диссертационая работа призвана восполнить пробел в классе математических моделей, описывающих системы компьютерного стереозрения. В работе приводится расширяемая математическая модель компьютерного стерезрения, совместимая с большинством современных разработок в сфере компьютерного зрения, дающая возможность использовать как существующие, так и вновь создаваемые методы и алгоритмы для реализации её частей.
Метод ректификации стереоизображений по сцене без калибровки камер
В персональных системах стереозрения источником изображений могут быть камеры, установленные в мобильных телефонах, ноутбуках и др. [64].
Ниже предлагается специальный метод ректификации изображений по сцене без калибровки и взаимной калибровки камер, позволяющий конечному пользователю получить ректифицированный стерео-поток, например, подключив дополнительную веб-камеру к ноутбуку [86].
Метод стабилизации стереопотока как основа метода рект ификации. Предлагаемый метод является развитием и адаптацией методов стабилизации видеопотока [51; 65] к ректификации изображений.
Основой задачи стабилизации видеопотока является определение параметров перемещения камеры между последовательными кадрами или эквивалентная ей задача определения перемещения изображения.
Под перемещением изображения понимается набор необходимых трансформаций для превращения кадра в последующий. Как правило, рассматривается проекционная модель камеры или, в случае пренебрежения дисторсиями, вносимыми оптикой, модель камеры-обскуры.
В общей постановке задачи учитываются все шесть степеней свободы камеры: перемещения вдоль трёх осей декартовых координат, а также повороты вокруг этих осей [21]. Нахождение всех шести параметров перемещения является нетривиальной задачей, поэтому в модели применяются упрощения. Производится ограничение вариаций углов до малых значений (это позволяет примененять следствия первого замечательного предела и приводить задачу к линейной), а также исключаются некоторые степени свободы. Мы рассматриваем решение аналогичной задачи с учётом специфики стереозрения. В задаче стабилизации видеопотока в подавляющем большинстве случаев путь камеры между последовательными камерами невелик [12], в то время как в задаче калибровки стереобаза всегда относительно велика.
В предлагаемой модели плоскости изображения принимаются параллельными, то есть оптические оси камер считаются коллинеарными. Такое упрощение правомерно в рамках практических применений: например, при закреплении дополнительной камеры на крышке ноутбука. Следствием этого упрощения является исключение из рассмотрения двух поворотных степеней свободы. Ещё одно допущение делается в отношении угла поворота камеры вокруг оптической оси: мы будем считать его малым.
Декомпозиция и анализ задачи ректификации изображений без стереокалибровки. Рассмотрим математическое описание процесса трансформации изображения одной камеры в изображение другой с учётом принятых ограничений. В рамках модели четыре степени свободы можно трактовать как три преобразования вида Ж2 = Ж2 над точкой изображения реЖ2. Перемещение Т{р) вдоль осей, лежащих в плоскости изображения, можно описать единым вектором перемещения уо = (dx,dy)T\
Результатом решения задачи ректификации является набор величин рс, V0, , kx, ку. Все три преобразования являются линейными по отношению к точке, поэтому с точностью до коэффициентов могут производиться в любом порядке. В предлагаемом нами решении поиск параметров производится в последовательности 7i?Z.
Решение задачи ректификации изображений без стереокалибровки.
Основа решения задачи состоит из четырёх основных этапов, базируется на операциях с векторным полем перемещения точек и является задачей оптимизации (31) [79]. Линейность каждого из преобразований позволила разделить решение задачи на независимые этапы, каждый из которых также является задачей оптимизации. На первом этапе производится поиск и фильтрация точечных особенностей на изображении первой камеры. На втором этапе строится векторное поле перемещения точек и находятся параметры перемещения Т(р) (22). На третьем этапе вычисляются параметры трансформации R(p) (23) с учётом предварительной оценки координат точки рс. На последнем шаге определяются параметры преобразования Z(p) (24) и находятся поправки для координат точки рс. Основная часть решения может быть повторена несколько раз для достижения статистически удовлетворительных результатов.
Поиск точечных особенностей. В задаче стабилизации видеопотока применяется расчёт векторного поля перемещения точек изображения. Опорные точки поля находятся в узлах регулярной сетки. Для уменьшения вероятности некорректного определения перемещений мы предлагаем использовать в качестве опорных точки с максимальной дисперсией окрестности. Под дисперсией окрестности понимается дисперсия яркости пикселей в малой квадратной симметричной окрестности рассматриваемой точки [82]. Для того чтобы опорные точки были распределены относительно равномерно, применяем фильтрацию через регулярную сетку. Таким образом, на каждую ячейку регулярной сетки будет приходиться не более одной точечной особенности, как и в оригинальном методе, но каждая из них будет обладать локально максимальной дисперсией. Ячейки, внутри которых дисперсия окрестности точек не превышает заданный порог, будут «пустыми». Кроме того, для снижения вероятности ложных срабатываний поиск точечных особенностей производится с заданным отступом от края изображения, так как края изображения с первой камеры с высокой вероятностью будут отсутствовать на изображении со второй камеры и наоборот.
Применение GPGPU к задаче стереосопоставления
Технология GPGPU. Технология GPGPU (англ. General-purpose graphics processing units — «GPU общего назначения») – техника использования графического процессора видеокарты, который имеет дело с вычислениями только для компьютерной графики, чтобы выполнять расчёты в приложениях для общих вычислений, которые обычно проводит центральный процессор [32]. В настоящее время в связи с архитектурными особенностями видеокарт становится рациональным использовать графические процессоры для решения широкого класса задач. Даже неспециализированные интегрированные видеокарты, поставляемые в ноутбуки, иногда могут справляться с вычислительными задачами более эффективно, чем передовые пользовательские многоядерные центральные процессоры. Наиболее важной особенностью GPGPU является принцип SIMD (single input, multiple data – один поток команд, множественные данные), позволяющий одновременно производить однотипные вычисления над достаточно большим объёмом данных, достигая физического параллелизма в десятки и сотни (на специализированных видеокартах) потоков и логического параллелизма – в сотни и тысячи потоков. Ещё одной крайне важной особенностью GPU является предельная скорость обращения к оперативной памяти. Так скорость «общения» центрального процессора с RAM на два порядка меньше скорости обращения GPU к глобальной памяти видеокарты [32].
Исторически программирование для GPU было очень сложной задачей, так как программистам приходилось оперировать графическими абстракциями, такими как шейдер и текстура, для формализации задач, лежащих, в общем случае, вне области графических вычислений. Такое программирование использовало возможность OpenGL и Direct3D и называлось «шейдерным» [18]. В какой-то момент преимущества и недостатки вычислений на графических процессорах стали очевидными и были формализованы. Различные компании и группы компаний начали создавать абстрактный уровень, как совокупность программного интерфейса и средств разработки, который позволил бы приблизить написание кода, выполняемого на GPU, по форме к написанию кода для центральных процессоров. В 2007 году компания NVidia представила первую версию Cuda SDK, которая представляет собой средство разработки для современных (Cuda-compatible) видеокарт собственного производства, состоящее из специализированного драйвера для разработчиков, инструментов, библиотек, документации с примерами кода и собственного расширения языка Си (CUDA C) с упрощениями [32]. Расширения языка позволяет достаточно просто и быстро портировать существующие параллельные программы, либо создавать новые. В свою очередь, компания AMD представила аналогичную технологию для собственных видеокарт ATI – AMD FireStream [99]. Apple и Khronos Group в 2008 году положили начало развитию стандарта унифицированного доступа к вычислительным модулям OpenCL. Данный стандарт предполагает решение проблемы множественности конкурирующих технологий [5]. На настоящий момент оба ведущих производителя видеокарт поддерживают стандарт OpenCL, фактически, предоставляя через вызовы OpenCL доступ к своим нативным технологиям. Технология OpenCL является более универсальной с точки зрения аппаратного обеспечения, однако крайне непроста в изучении.
Для понимания преимущества, которые дают графические процессоры в вычислениях, следует обратиться к их архитектуре. Для графических процессоров характерна высокая степень параллелизма вычислений. Следует отметить и достаточно небольшой размер кэша и управляющего блока для каждого мультипроцессора, так как на кристалле это место отдано под вычислительные элементы (cache miss-oriented) [61]. GPU – это массивно-параллельный многоядерный процессор. Графический процессов состоит из мультипроцессоров (streaming multiprocessor, MP), каждый из которых содержит несколько скалярных процессоров (scalar processor, SP) и общую для них память. После появления видеокарт NVidia Fermi скалярные процессоры стали называться CUDA ядрами (CUDA core). Скалярные процессоры внутри одного мультипроцессора работают по принципу SIMD, и каждый из них может исполнять множество потоков. В GPU встроен собственный планировщик потоков, который управляет переключением между потоками в рамках MP и SP [87].
При рассмотрении особенностей архитектуры GPU также следует уделить внимание памяти. Несмотря на то, что память DRAM в GPU существенно быстрее оперативной памяти, графические карты содержат ещё несколько типов памяти, отличающихся скоростью и способом доступа:
device/global (глобальная) – общая для устройства;
shared (разделяемая) – общая для всех SP в одном MP;
constant cache – только чтение, общий для всех SP в одном MP; texture cache – только чтение, общий для всех SP в одном MP;
register (регистры) – (логически) эксклюзивны для SP;
local (локальная) – (логически) эксклюзивна для SP.
Чем «ближе» память находится к SP, тем быстрее осуществляется доступ к ней. Важным ограничением, о котором следует помнить при решении задач с использованием GPU, является слабая поддержка вычислений с плавающей точкой двойной точности. На современных графических платах это ограничение частично решено введением дополнительного модуля, отвечающего за подобные вычисления, однако до сих пор вычисления с двойной точностью на GPU являются очень дорогостоящей операцией.
Стерео-сопоставление на графическом процессоре. Рассмотрим полноцветный (т.е. учитывающий цветовые компоненты) локальный алгоритм стерео-сопоставления с фиксированным окном. Решение данной задачи имеет алгоритмическую сложность O(W W H wW wH), где W и H – ширина и высота изображения с пикселях соответственно, а wW и wH – ширина и высота окна сканирования с пикселях соответственно. Поскольку размер изображения является постоянным, то для квадратного окна алгоритм имеет квадратичную сложность O(wW2) (см. Рис. 34).
Особенностью данного класса алгоритмов является то, что сканирование может производиться параллельно и независимо, а результат каждого сканирования не влияет на соседние результаты. Воспользуемся этой особенностью локальных алгоритмов для увеличения его эффективности в многоядерной системе. В первую очередь, попробуем использовать возможности центрального процессора. Для этого применим технологию OpenMP, распараллелив задачу на все доступные ядра [59]. Для этого достаточно запустить компиляцию с ключом /openmp (для компилятора Microsoft Visual C++ Compiler), подключить заголовочный файл omp.h , а также для цикла по строкам изображений специфицировать параллельное выполнение следующей директивой:
Практические приложения распределённого программного комплекса компьютерного стереозрения
Предложенное программно-аппаратное решение является прототипом. Однако особенности реализации и формируемые в реальном времени данные могут применяться в широком спектре областей.
Распределённость системы в совокупности с работой в реальном масштабе времени делает её применимой для использования в мобильных автономных системах, таких как спасательные роботы и системы телеприсутствия. В качестве более широкого применения системы можно отметить мобильные приложения видео-конференций: было показано, что при использовании сетей 3G можно достичь производительности более 4 кадров в секунду при независимой передаче изображений и более 8 кадров в секунду – при передаче подготовленных анаглифных изображений с разрешением 640x480. Возможность формирования пространственных данных в реальном времени позволяет применять получаемые данные в системах дополненной и виртуальной реальности.
В главе представлены оригинальные алгоритмы, которые были реализованы в виде комплекса программ. Они основаны на предложенной математической модели формирования стереопотока по потокам кадров с двух камер, стереовизуализации и стереосопоставления и методах, рассмотренных в третьей главе. На 1-м этапе – формулирования требований к программному комплексу – определены роли пользователей системы: «конфигуратор модуля захвата», «пользователь модуля захвата» и «пользователь модуля визуализации». Функции системы распределены по модулям. На 2-м этапе – проектирования – в соответствии с решаемыми задачами сформирована иерархия основных классов. В модуль стереозахвата выделены пакеты захвата изрображений, калибровки и сетевого взаимодействия. На 3-м этапе – реализации – проводится алгоритмизация предложенных в третьей главе метода синхронизации потоков кадров с USB-камер и метода ректификации изображений по сцене без стереокалибровки камер.
В главе представлен алгоритм ректификации стереоизображений. Для алгоритма, созданного на основе оригинального метода, основной структурой данных является векторное поле – упорядоченное множество двумерных дискретных векторов, над которыми производятся преобразования перемещения, поворота и масштабирования. Для метода предложены два способа улучшения точности получаемых результатов. Первый из них исключает ошибочные векторы на векторном поле по завершении использования основной части метода, после чего нужно повторно выполнить основную часть метода. В алгоритме эта модификация представлена циклом с постусловием. Второй – основан на статистическом подходе к получаемым результатам: для одной и той же конфигурации камер производится несколько калибровок для различных сцен, после чего из выборки исключаются выбросы значений параметров, а результирующее значение рассчитывается как средняя величина независимых калибровок. Данный способ реализован в виде многопоточного выполнения независимых калибровок.
В главе было исследовано взаимодействие модулей программного комплекса при использовании каналов связи невысокой пропускной способности. Сделан вывод, что для передачи в реальном масштабе времени изображений (640 480, 8 fps), сжатых без потерь, допустимо использование проводныx протоколов связи (FastEthernet, FTTx, Gigabit Ethernet), а также беспроводных протоколов WiFi (802.11) и LTE; передача изображений в реальном масштабе времени, сжатых с потерями, возможна также по беспроводным протоколам третьего поколения (3G UMTS).
В главе представлен созданный программный комплекс, осуществляющий захват, передачу, стереосопоставление, анаглифную и трёхмерную визуализацию изображений сцены в реальном масштабе времени. Комплекс состоит из трёх основных приложений: сервера, стереовизуализатора и трёхмерного визуализатора. Приложение-сервер включает в себя программные модули захвата, синхронизации, цветовой калибровки и ректификации; оно написано на языке C# (.NET 4.0). Разработанные параллельные алгоритмы реализованы в серверном приложении с использованием механизмов многопоточности платформы .NET. Стереовизуализатор включает в себя функциональность раздельной и анаглифической визуализации стереопотока, а также визуализации сохранения карт глубины в реальном масштабе времени; приложение использует функциональность открытой библиотеки OpenCV. Модули анаглифической визуализации и визуализации карт глубины разработаны с использованием масштабируемой многопоточности. Трёхмерный визуализатор представляет собой модуль, отображающий полигональную модель, рассчитанную на основании карты глубины. Модуль реализован на кросс-платформенном расширении Java – языке Processing, предназначенном, в том числе, для быстрого прототипирования приложений двухмерной и трёхмерной визуализации. Программа–визуализатор позволяет по картам глубины и текстурным изображениям формировать в реальном масштабе времени трёхмерную модель сцены и управлять её отображением.
Похожие диссертации на Методы и алгоритмы анализа, передачи и визуализации данных в системах компьютерного стереозрения
-
-
-
