Назад

ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ ГЕНЕРАЦИИ КАРТЫ ГЛУБИНЫ
ИЗОБРАЖЕНИЯ ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ DEPTH IMAGE BASED
RENDERING

Введение

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

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

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

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

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

Общая постановка проблемы

Одной из фундаментальных проблем стереозрения является установление точного соответствия между левым и правым изображением стереопары. Под соответствием понимается расстояние (диспаритет) между пикселями одного и того же объекта на левом и правом изображении. Проблемой при этом является относительно низкая скорость обработки изображений и установления этого соответствия для генерации карты глубины в системах Depth Image Based Rendering.

Цель работы

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

Построение карты глубины

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

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

Парную точку нужно искать на эпиполярной линии. Соответственно, для упрощения поиска, изображения выравнивают так, чтобы все эпиполярные линии были параллельны сторонам изображения (обычно горизонтальны). Более того, изображения выравнивают так, чтобы для точки с координатами (x0, y0) соответствующая ей эпиполярная линия задавалась уравнением x = x0, тогда для каждой точки соответствующую ей парную точку нужно искать в той-же строчке на изображении со второй камеры. Такой процесс выравнивания изображений называют ректификацией. Обычно ректификацию совершают путем ремештинга изображения и ее совмещают с избавлением от дисторсий.

После того как изображения ректифицированы, выполняют поиск соответствующих пар точек. Самый простой способ проиллюстрирован на рисунке 1 и состоит в следующем. Для каждого пикселя левой картинки с координатами (x0, y0) выполняется поиск пикселя на правой картинке. При этом предполагается, что пиксель на правой картинке должен иметь координаты (x0 — d, y0), где d — величина, называемая несоответствие/смещение. Поиск соответствующего пикселя выполняется путем вычисления максимума функции отклика, в качестве которой может выступать, например, корреляция окрестностей пикселей. В результате получается карта смещений.

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

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

Программные средства

Для реализации данной системы были изучены и использованы следующие программные средства: OpenCV – для работы с изображениями; OpenMP, OpenAcc, OpenGI и OpenCI – для распараллеливания вычислительных процессов.

OpenCV

OpenCV [2] (англ. Open Source Computer Vision Library, библиотека компьютерного зрения с открытым исходным кодом) — библиотека алгоритмов компьютерного зрения, обработки изображений и численных алгоритмов общего назначения с открытым кодом. Реализована на C/C++, также разрабатывается для Python, Java, Ruby, Matlab, Lua и других языков. Данная библиотека содержит большое количество библиотек, необходимых для работы с изображениями, в том числе здесь находятся алгоритмы для нахождения соответствия пикселей стереопары изображений и построения карт глубины.

OpenMP

OpenMP [3] (Open Multi-Processing) — открытый стандарт для распараллеливания программ на языках C, C++ и Фортран. Дает описание совокупности директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью.

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

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

OpenAcc

OpenACC [4] (от англ. Open Accelerators) — программный стандарт для параллельного программирования, разрабатываемый совместно компаниями Cray, CAPS, Nvidia и PGI. Стандарт описывает набор директив компилятора, предназначенных для упрощения создания гетерогенных параллельных программ, задействующих как центральный, так и графический процессор.

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

OpenGL

OpenGL [5] (Open Graphics Library) — спецификация, определяющая платформонезависимый (независимый от языка программирования) программный интерфейс для написания приложений, использующих двумерную и трёхмерную компьютерную графику.

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

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

Существует ряд библиотек, созданных поверх или в дополнение к OpenGL. Например, библиотека GLU, являющаяся практически стандартным дополнением OpenGL и всегда её сопровождающая, построена поверх последней, то есть использует её функции для реализации своих возможностей. Другие библиотеки, как, например, GLUT и SDL, созданы для реализации возможностей, недоступных в OpenGL. К таким возможностям относятся создание интерфейса пользователя (окна, кнопки, меню и др.), настройка контекста рисования (область рисования, использующаяся OpenGL), обработка сообщений от устройств ввода-вывода (клавиатура, мышь и др.), а также работа с файлами. Обычно каждый оконный менеджер имеет собственную библиотеку-расширение для реализации вышеописанных возможностей, например, WGL в Windows или GLX в X Window System, однако библиотеки GLUT и SDL являются кроссплатформенными, что облегчает перенос написанных приложений на другие платформы.

Библиотеки GLEW (The OpenGL Extension Wrangler Library) и GLEE (The OpenGL Easy Extension library) созданы для облегчения работы с расширениями и различными версиями OpenGL. Это особенно актуально для программистов в Windows, так как заголовочные и библиотечные файлы, поставляемые с Visual Studio, находятся на уровне версии OpenGL 1.1.

OpenCL

OpenCL [6] (англ. Open Computing Language — открытый язык вычислений) — фреймворк для написания компьютерных программ, связанных с параллельными вычислениями на различных графических и центральных процессорах, а также FPGA. В OpenCL входят язык программирования, который основан на стандарте языка программирования Си С99, и интерфейс программирования приложений. OpenCL обеспечивает параллелизм на уровне инструкций и на уровне данных и является осуществлением техники GPGPU. OpenCL является полностью открытым стандартом, его использование не облагается лицензионными отчислениями.

Цель OpenCL состоит в том, чтобы дополнить открытые отраслевые стандарты для трёхмерной компьютерной графики и звука OpenGL и OpenAL возможностями GPU для высокопроизводительных вычислений.

Оптимизация системы

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

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

Таким образом мы получаем набор из более простых и менее объемных структур, с которыми без проблем справится любой из стандартов для распараллеливания.

Выводы

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