Анализ методов и алгоритмов построения трёхмерных структур полученных с использованием различных оптических систем

Размещено на http://www.allbest.ru/

Анализ методов и алгоритмов построения трёхмерных структур полученных с использованием различных оптических систем

Е.О. Дорохова, Е.А.Семенищев

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

Ключевые слова: карта глубины, указатели глубины.

ANALYSIS OF METHODS AND ALGORITHMS FOR CONSTRUCTING THREE-DIMENSIONAL STRUCTURES OBTAINED USING DIFFERENT OPTICAL SYSTEMS

E.O.Dorokhova, E.A.Semenishev

Don State Technical University (DSTU), Shakhty, Russia

Don State Technical University (DSTU), Shakhty, Russia

Abstract. The article is devoted to the study of existing algorithms for creating depth maps for different scenes. In accordance with the pointers of depth, the algorithms are classified into the following 12 categories: binocular disparity, motion, defocusing, focus, silhouette, atmosphere scattering, shading, linear perspective, patterned texture, symmetric patterns, occlusion (curvature, simple transform) and statistical patterns. As a result, the advantages and disadvantages of the described methods, as well as their effective applications are identified.

Keywords: depth map, depth cues.

Введение

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

Классификация алгоритмов и их характреистики

Алгоритмы преобразования двумерных изображений (2D) в трёхмерные (3D) можно разделить на два класса: алгоритмы, основанные на использовании двух и более входных изображений, и алгоритмы, использующие в качестве входного одно неподвижное изображение.

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

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

карта глубина алгоритм фокус

(1)

где d = p_r - p_l - диспаратность, т.е. разница в положении сетчатки между соответствующими точками изображения, p_r и p_l - проекции точки P на правое и левое изображения соответственно, T - базовое расстояние, - фокусное расстояние.

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

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

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

Допустим, что существует только одно устойчивое движение V между камерой и сценой, и P - трехмерная точка в кадре отсчета камеры. Относительное движение V между P и камерой можно описать как:

, (2)

где H - вектор скорости преобразования; ? - угловая скорость камеры. Связь между глубиной 3D точки и ее движением в 2D отражена в основных уравнениях поля движения, которые объединяет в себе уравнение (2).

Данная группа методов формирует как плотную, так и разреженную карта глубины, обеспечивая абсолютное расстояние между камерой и просматриваемыми объектами. Высокая точность ее построения достигается алгоритмами, которые позволяют интегрировать несколько кадров из последовательностей изображений. Кроме того, данный алгоритм работает в режиме реального времени. К недостаткам следует отнести: чувствительность к шуму и необходимость отслеживать движения по длинной последовательности изображений или наложения дополнительных ограничений; эффективный диапазон глубины составляет менее 30 метров, требуется высокая вычислительная сложность. [1]

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

, (3)

где -расстояние между объективом и положением фокуса, s - расстояние между линзой и плоскостью изображения, - фокусное расстояние линзы, и k - константа, определяемая линзой системы.

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

Недостатки: необходимость знать внутренние параметры камеры за пределами фокусного расстояния, необходимость калибровки камеры. Кроме того, данный метод очень чувствителен к шуму и к изменениям интенсивности изображения. [4]

Для построения карты глубины для объектов находящихся в фокусе используется серия кадров, сделанных одной камерой, путем изменения расстояния между ней и объектами сцены. Пусть s - точка поверхности объекта. В ходе процесса регистрируются положения сцены при ее перемещении. Обозначим смещение как d_focused, при условии, что s максимально сфокусировано, и d_f - расстояние между ориентированной плоскостью и базовой плоскостью. Тогда значение глубины изображения s будет определяться как Z = d_f - d_focused.

Данный алгоритм формирует плотную карту глубины, вычисляя реальное расстояние между камерой и объектами. Он применим к закрытым сценам, объекты которых расположены близко к камере, относительная частота ошибок составляет 0,1%, когда объект находится на расстоянии 1,2 метра от камеры. Несмотря на это, алгоритм чувствителен к аберрациям системы линз, не имеет возможности реализации в реальном времени, а также с использованием одной камеры, высокие затраты на вычисление. [3]

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

Данный алгоритм хорошо работает с отражающими, прозрачными и полупрозрачными поверхностями, однако объекты переднего плана должны быть отличимы от фона. В результате работы будут восстановлены только разреженные значения глубины объектов переднего плана. Однако, метод требует точной калибровки камеры и большого количества входных изображений. Кроме того, несмотря на то что объем может быть точно восстановлен, получение текстур является невозможной задачей. [2]

Алгоритмы построения карты глубины из одного расфокусированного изображения работают с кадрам, полученными из фиксированного положения камеры и объекта. Изображение должно содержать одну область в фокусе и одну область вне фокуса. Зная радиус размытия и параметры камеры восстанавливается плотная карта глубины, вычисление которой основано на уравнении (3).Эффективный диапазон глубины не ограничен, однако полученная карта дает лишь относительное ее значение. Данный метод не подходит для изображений размытых текстур. Кроме того, не удается получить глубину в нетекстурированных областях.

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

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

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

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

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

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

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

Алгоритмы, основанные на атмосферном рассеянии, используют одно входное изображение. Рассеяние света является указателем глубины, который выигрывает от расстояния: чем дальше объект, тем больше эффект рассеяния. Однако его расчеты достаточно сложны. Путем численного интегрирования вычисляются оптические глубины и рассеяние света в точках, видимых через атмосферу. Данный алгоритм приводит к соотношению разности глубин между различными объектами, из которых можно получить карту разреженной глубины. Относительная частота повторения ошибок составляет 10% для открытых сцен. Эффективный диапазон глубины составляет от 900 до 8000 метров. [5]

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

Заключение

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

Благодарность

Работа поддержана Министерством образования и науки РФ в рамках постановления N 218 "О мерах государственной поддержки развития кооперации российских образовательных организаций высшего образования, государственных научных учреждений и организаций, реализующих комплексные проекты по созданию высокотехнологичного производства, в рамках подпрограммы "Институциональное развитие научно-исследовательского сектора" государственной программы Российской Федерации "Развитие науки и технологий" на 2013 - 2020 годы", (контракт №03.G25.31.0284).

Литература

1. Wei, Q. Converting 2D to 3D: A Survey, 2005. - 43 p.

2. Cheung, K.; Bakerand, S.; Kanade,T. Shape-From-Silhouette Across Time: Part I: Theory and Algorithms, 2005. - 51 p.

3. Nayar, S.K.; Nakagawa, Y. Shape from Focus, Pattern Analysis and Machine Intelligence, IEEE Transactions on Volume 16, Issue 8, 1994. Pp. 824 - 831.

4. Wong, K.T.; Ernst, F., Master thesis Single Image Depth-from-Defocus, Delft university of Technology & Philips Natlab Research, Eindhoven, The Netherlands, 2004.

5. Cozman, F.; Krotkov, E. Depth from scattering, IEEE Computer society conference on Computer Vision and Pattern Recognition, Proceedings, 1997. - Pp. 801-806.

6. Shimshoni, I.; Moses, Y.; Lindenbaumlpr, M. , Shape reconstruction of 3D bilaterally symmetric surfaces, Proceedings, International Conference on Image Analysis and Processing, 1999. - Pp. 76 - 81.

References

1. Wei, Q. Converting 2D to 3D: A Survey, 2005. - 43 p.

2. Cheung, K.; Bakerand, S.; Kanade,T. Shape-From-Silhouette Across Time: Part I: Theory and Algorithms, 2005. - 51 p.

3. Nayar, S.K.; Nakagawa, Y. Shape from Focus, Pattern Analysis and Machine Intelligence, IEEE Transactions on Volume 16, Issue 8, 1994. Pp. 824 - 831.

4. Wong, K.T.; Ernst, F., Master thesis Single Image Depth-from-Defocus, Delft university of Technology & Philips Natlab Research, Eindhoven, The Netherlands, 2004.

5. Cozman, F.; Krotkov, E. Depth from scattering, IEEE Computer society conference on Computer Vision and Pattern Recognition, Proceedings, 1997. - Pp. 801-806.

6. Shimshoni, I.; Moses, Y.; Lindenbaumlpr, M. , Shape reconstruction of 3D bilaterally symmetric surfaces, Proceedings, International Conference on Image Analysis and Processing, 1999. - Pp. 76 - 81.

Размещено на Allbest.ru