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

Дипломная работа

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

2010г.

Вcтупление

факторизация матрица проекция рельеф

В настоящей работе дан обзор литературы по тематике восстановления трёхмерных сцен.

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

Алгоритмы тестированы на синтетических данных. Для генерации последних, в программном пакете 3dmax были разработаны модели данных. И осуществлено исследование погрешностей восстановления в зависимости от ряда изменяемых параметров.

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

Краткий перечень сокращений

GPS - Global Positioning System,

ГЛОНАСС - Глобальная Навигационная Спутниковая Система,

DoG - Difference of Gaussian,

ППИ - передней плоскости изображения,

МСК - мировой системе координат,

ЦМ - центр масс,

ОП - ортографической проекции,

МОП - масштабируемой ортографической проекции,

ППП - параперспективной проекции,

ПП - перспективной проекции,

SVD - сингулярного разложения матриц,

МНК - методом наименьших квадратов,

НИР - научно - исследовательская работа,

ПЭВМ - персональная электронная вычислительная машина,

ЖК - жидкокристаллический монитор,

ЭЛТ - электроннолучевая трубка.

Содержание

Введение

1. Общая часть

1.1 Обоснование необходимости разработки программного комплекса

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

1.3 Обзор методов восстановления трёхмерных сцен

1.3.1 Алгоритмы Shape from Shading

1.3.2 Алгоритмы Shape from Focus and Defocusing

1.3.3 Алгоритмы Shape from Stereo

1.3.4 Алгоритмы Shape from Motion

1.3.5 Экзотические методы

1.4 Сравнительный анализ методов восстановления 3D сцен

2. Система трехмерного зрения

2.1 Общая структура алгоритма восстановление 3D сцен

2.2 Обнаружение характеристических точек

2.2.1 Метод SIFT

2.2.2 Метод SURF

2.3 Восстановление 3D сцен по последовательности цифровых изображений методом факторизации матриц

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

2.3.2 Математический вывод приближений

2.3.3 Геометрический смысл приближений

2.3.3.1 Приближение ортографической проекции

2.3.3.2 Приближение масштабируемой ортографической проекции

2.3.3.3 Приближение параперспективной проекции

2.3.3.4 Перспективная проекция

2.3.3.5 Сравнительный анализ приближений

2.3.4 Метод факторизации матриц

2.3.5 Итерационный метод решения 3D-задачи

3. Результаты

3.1 Формирование входных данных

3.2 Структура программы восстановления трехмерных сцен

3.3 Совмещение результатов восстановления с моделью

3.4 Оценка точности восстановления

3.4.1 Первая синтетическая модель

3.4.2 Вторая синтетическая модель

3.4.3 Третья синтетическая модель

3.5 Тестирование на реальных изображениях

3.6 Результат

4. Экономическая часть

5. Обеспечение условий труда в отделе обработки изображений

Заключение

Список литературы

Приложение А

Введение

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

Задача восстановления и распознавания трехмерных сцен в настоящее время интенсивно разрабатывается большим числом исследователей и организаций. Область применения этих алгоритмов также чрезвычайно широка. Это задачи навигации роботов и управления автомобилем [1], [2], [3], [4], предотвращение столкновений [5], лабораторные и промышленные системы измерения [6],[7]. Широкое приложение алгоритмы восстановления трехмерных сцен в последнее время находят также в аэрокосмической отрасли.

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

- "Shape from shading" - восстановление формы (глубины) сцены по одиночному изображению на основе анализа изменения яркости. Как правило, используется ламбертовская модель рассеяния света объектом;

- "Shape from from Focusing and Defocusing" - восстановление формы (глубины) сцены по набору изображений, снятых неподвижной камерой при различной степени расфокусировки (фокусировка на фрагменты сцены, расположенные на различном расстоянии от камеры);

- "Shape from Stereo" - восстановление формы (глубины) сцены из стерео пары изображений;

- "Shape from Motion" - восстановление формы сцены из последовательности изображений, снятых с разных позиций и в разные моменты времени (часто положения камеры тоже считаются неизвестными и восстанавливаются в ходе решения задачи);

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

1. Общая часть

1.1 Обоснование необходимости разработки программного комплекса

Местоположение самолёта на местности сейчас определяет спутниковая система навигации GPS -- обеспечивающие измерение времени и расстояния навигационные спутники; глобальная система позиционирования)или российский аналог ГЛОНАСС. Здесь главная проблема состоит в том, что эти системы контролируются военными учреждениями США и РОССИИ соответственно, то есть в случае военных действий использование этих систем на мирные цели может быть ограничено или прекращено совсем, системы могут быть уничтожены. Поэтому существует необходимость дублирование таких систем. В данной дипломной работе предлагается для определения местоположения самолёта в пространстве использовать систему, основанную на сравнение высоты полёта самолёта с известной картой высот. Траекторию полёта летательного аппарата предлагается находить из снимков, полученных на борту летательного аппарата, методом факторизации матриц. Он позволяет по фото или видео данным строить карту высот поверхности, над которой пролетает самолёт или другое летательное средство.

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

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

1) реализовать метод детектирования и сопровождения характеристический точек на серии изображений,

2) по характеристическим точкам восстановить трёхмерная сцену,

3) построить карту высот,

4) визуализировать получившуюся сцену.

1.3 Обзор методов восстановления трёхмерных сцен

1.3.1 Алгоритмы Shape from Shading

Алгоритмы этой группы были разработаны одними из первых в начале 1970-х [11] для восстановления формы трехмерной сцены на основе видеоизображения. Однако они не утратили актуальности и поныне, разработка новых подходов к решению задачи продолжается до настоящего времени. Входными данными для этих алгоритмов является единственное серое полутоновое изображение сцены. Они основаны на том обстоятельстве, что для ламбертовых поверхностей яркость в каждой точке не зависит от положения наблюдателя и пропорциональна косинусу угла между нормалью к поверхности и направлением на источник освещения. Математически задача описывается следующим образом. Выберем систему координат (x,y,z) так, чтобы плоскость xy была параллельна плоскости изображения, а ось z была направлена к наблюдателю. Тогда поверхность можно описать функцией возвышений Z(x,y). Вектор нормали к поверхности Z(x,y) тогда записывается в виде:

Здесь p и q - компоненты вектора градиента поверхности в направлении x и y соответственно. Пусть сцена освещается плоскопараллельным пучком в направлении.



где И - угол между направлением на источник излучения и осью z (зенитный угол, slant of the illuminant), ф-- угол между проекцией направления на источник излучения от объекта на плоскость xy и осью x (азимутальный угол, tilt of the illuminant). Тогда для изображения B(x,y) в предположении ламбертового рассеяния можно записать:

где A - освещенность, создаваемая источником излучения в плоскости xy, сL - альбедо поверхности для ламбертовского рассеяния. Уравнение (1.3) представляет собой нелинейное дифференциальное уравнение относительно Z(x,y) в частных производных с переменными коэффициентами (из-за B(x,y)). В случае неламбертовского рассеяния, правая часть (1.3) принимает более сложный вид. С учетом спекулярного рассеяния, наиболее общее выражение выглядит так [12]:

Здесь в = arccos([n,s]) - угол между нормалью к поверхности и биссектрисой угла между направлениями на источник освещения s и точку изображения b, у- ширина диффузной части спекулярного рассеяния (specular lobe), Иi, фi и Иr, фr - зенитный и азимутальные углы источника излучения и направления зрения (точки изображения) соответственно. Последнее слагаемое в (1.4}) отвечает за зеркальную компоненту спекулярного рассеяния (specular spike), которая отлична от нуля только в очень узком диапазоне углов в направлении зеркального отражения на малой плоской площадке, касательной к поверхности Z$ в точке (x,y). Одним из простейших методов является линейный метод Пентланда [13]. Уравнение (1.3) линеаризуется и, с учётом (1.1), принимает вид:

От обеих сторон берется преобразование Фурье. Тогда Фурье-образ поверхности Z может быть выражен в явном виде:

Путем взятия обратного преобразования Фурье, получается форма поверхности Z(x,y). Детальный обзор современных алгоритмов по этой тематике дан в [14]. В [15] дан сравнительный анализ погрешностей этих алгоритмов. Существуют алгоритмы, пригодные для поверхностей с законом рассеяния, отличным от ламбертовского [16],[17]. Основными недостатками алгоритмов "Shape from Shading" являются требования постоянства альбедо по всей сцене и априорного знания закона рассеяния (то есть двунаправленной функции рассеяния BDRF5), а также, потеря информации об абсолютных размерах и расстояниях. Однако, в ряде случаев, эти алгоритмы успешно использовались для решения практических задач, например для расчета формы Лунной поверхности на основе снимков. Достоинством таких алгоритмов является возможность получения результата на основании единственного изображения. Знание точных условий освещения, что характерно для изображений планет и астероидов, существенно облегчает задачу, и повышает точность результатов. Для безатмосферных небесных тел, в свою очередь, постоянство альбедо в пространстве, является типичным. Если условия освещения не известны, они могут быть восстановлены из самого изображения с помощью группы алгоритмов IDE (Illumination Direction Estimation), однако, в этом случае, приходится делать определенные допущения для статистических свойств поверхности, например, о равной вероятности уклонов поверхности для всех направлений, или локальной сферичности поверхности. В случае, когда допущения не соответствуют действительности, оценка направления освещения дает неверный результат, и приводит к неправильному восстановлению формы поверхности с помощью алгоритмов Shape from Shading. Иллюстрирующий пример приведен на рис. 1.1.

Рис. 1.1. Влияние направления освещения на восстановление формы объекта

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

Существуют методы, позволяющие в некоторых случаях применять алгоритмы типа "Shape from Shading" для сцен с неодинаковым альбедо, описанные, например [18]. В этой работе сначала оценивается величина альбедо с помощью локальных методов для каждой точки изображения, затем изображение сегментируется по величине альбедо, и значения пикселей исходного изображения делятся на средние значения альбедо по соответствующим сегментам, после чего используется обычный алгоритм восстановления формы для постоянного альбедо, равного единице. Использованный метод расчета альбедо [20] не работает для некоторых типов поверхности, в частности плоской. Очевидно, что для объекта с переменным альбедо общего вида не возможно восстановление формы по одному изображению. Так, например, изображение объекта, приведенное на рис. 1.1 (полусфера), и изображение фотографии этого объекта (плоскость), идентичны.

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

1.3.2 Алгоритмы Shape from Focus and Defocusing

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

где L -- расстояние от линзы до плоскости изображения. Так как для неплоского объекта расстояния от объектива до его различных точек разные, то оптическая система может быть наведена на резкость только для части точек объекта.

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



Здесь r - радиус входного зрачка объектива, Д - диаметр кружка в плоскости изображения, которым представляется точка объекта, в цифровых системах изображение можно считать резким, если Д меньше размера пикселя фоточувствительной матрицы. Заметим, что точность определения величины 1/z, определяется только свойствами оптической системы, и не зависит от z.

В [21] предлагается алгоритм для нахождения глубины сцены по фокусировке, отличающийся от ранее известных, существенно большей точностью. В качестве меры сфокусированности в точке изображения, выбиралась величина M2 [22],[23]:

с оператором градиента Собела [24], который вычисляется следующим образом:

X, Y берутся в обозначениях элементов окна для оператора Собела:



Практически выражение (1.9) вычислялось, как среднее по окну 40х40 пикселей от величин (1.10), посчитанных для каждой точки окна (i,j). Оператор Собела (1.10) вычисляется по окну 3х3, как показано в (1.12).

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

Рис. 1.2 Тестовое изображение для Shape from Defocus

1.3.3 Алгоритмы Shape from Stereo

По типу обрабатываемых особенностей, алгоритмы восстановления формы сцены на основании стереоизображений делятся на три класса: алгоритмы для геометрических особенностей, основанные на поиске характерных точек (feature-based approaches), алгоритмы для областей (area-based approaches) [27], а также смешанные алгоритмы (miscellaneous approaches) [28], [29], [30].

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

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

Существует несколько смешанных методов, таких как стохастический алгоритм Бернарда [28]. Этот метод плохо работает при недостатке пространственной структуры. Его суть заключается в вычислении карты смещений (disparity) для каждой точки изображения путем минимизации функционала, соответствующего критериям близких интенсивностей и гладкости:

где IL(i,j), IR(i,j) - значения пикселей левого и правого изображений, D(i,j) - карта смещений, л - константа, оператор ? вычисляет сумму абсолютных разностей между смещением D(i,j) и его 8 ближайшими соседями. Задача решается путем численного моделирования Монте-Карло.

Большинство алгоритмов группы "Shape from Stereo" находят только грубые детали формы объекта, особенно при недостатке пространственной структуры. В то же время, по сравнению с "Shape from Shading", пространственная локализация крупных деталей, особенно их ребер, и контрастных границ, происходит существенно точнее, а расстояния могут быть восстановлены в абсолютных величинах. Поэтому представляет интерес подход, изложенный в[31], который позволяет объединить эти два метода. Предложенный метод основан на модели человеческого зрения [32], которое выполняет ту же задачу. Представляя поверхность Z(x,y) в виде Фурье-образа FZ(u,v), математически этот метод может быть описан так:

где - Фурье-образы поверхностей, полученных из стерео, полутонов, и в результате их объединения. H(щ) -- высокочастотный фильтр из модели, предложенной в [32] Для зрительной системы человека б= 0.01, б),(vuFCZ),(vuFSTZ),(vuFSSZ0=0.2.

1.3.4 Алгоритмы Shape from Motion

В настоящее время, из всех методов реконструкции трехмерных сцен, алгоритмы восстановления сцены по изображениям, полученным с разных положений камеры, и в различные моменты времени, исследуются наиболее интенсивно [33], [34], [35]. При этом часто предполагается, что фокусное расстояние объектива неизвестно, или меняется от кадра к кадру. Кроме того, не редко, положения камеры на момент съемки каждого кадра также полагается неизвестным, и находится в ходе решения задачи реконструкции трехмерной сцены. Как правило, такие методы основываются на поиске характерных точек (feature points) на изображениях, в виде уголков или линий, а также на поиске соответствий между обнаруженными точками на последовательности кадров6, нахождении их пространственных позиций по принципу триангуляции, и построении аппроксимирующих поверхностей. Подробное изложение наиболее перспективных методов этой группы, основанных на факторизации матриц, будет приведено ниже в основной части настоящей работы. Отметим здесь лишь, что указанные методы не работают непосредственно с изображениями, а требуют на вход координаты характеристических точек изображений в пикселях, и наличие у каждой характеристической точки маркера (номера), причем, на всей последовательности изображений, одной и той же точке реальной сцены должен соответствовать одинаковый маркер.

Для нахождения характеристических точек существуют различные алгоритмы [1], [36], [37], [38]. Задача нахождения взаимно однозначного соответствия между характеристическими точками на различных изображениях обрабатываемой последовательности, обычно решается методами траекторного анализа и калмановской фильтрации [34].

Наиболее перспективными из этой группы являются методы, основанные на факторизации матриц [39], [40], [41], [42]. В [39] наиболее подробно освещаются основы метода и рассматриваются его детали. В [40] наиболее компактно и подробно описаны различные приближения. В [41] рассматривается применение метода в случае наличия движущихся объектов на сцене, и предлагается подход к определению числа таких объектов, и их разделению. В [42] предлагается модификация метода, не требующая предварительного накопления всех данных, но позволяющая уточнять модель по мере поступления новых данных, и отличающаяся лучшим быстродействием, и меньшими затратами вычислительных ресурсов. Однако, по-видимому, этот метод имеет ограниченное время непрерывной работы из-за переполнения плавающей арифметики, и накопления погрешностей, так как на каждом шаге получения новых данных, они добавляются к ковариационной матрице измерений, а никаких мер по предотвращению подобной ситуации не предлагается. В статье [39] упоминается подход к применению метода в тех случаях, когда не все характеристические точки видны на всех кадрах.

1.3.5 Экзотические методы

Среди методов восстановления трехмерных сцен по их оптическим цифровым изображениям, встречаются довольно необычные. Так, в [43] предлагается метод, основанный на учете влияния рассеяния и поглощения в атмосфере. Суть метода заключается в нахождении на изображении участков с предположительно похожими отражательными свойствами, и сопоставлении яркостей таких участков. Учитываются эффекты освещения рассеянным излучением от неба, яркость которого измеряется наведением камеры на участок неба, удаленный от направления на Солнце, или выделения на изображении участков, относящихся к поверхности, или небу. В случае тумана, за яркость "неба" принимается яркость сильно удаленных объектов, то есть невидимых сквозь туман. Индикатриса рассеяния считается симметричной относительно направления падения освещения. В статье приводятся некоторые результаты натурных экспериментов, точность измерения расстояний для приведенных результатов лежит в пределах от 2.7 до 15.9 процента, что для подобного метода представляется удивительно хорошим. Как справедливо отмечают авторы, этот метод имеет весьма ограниченную область применения, однако может служить дополнительным источником информации для мобильных роботизированных систем.

Другой интересный метод описан в статье [44]. Рассматривается одиночное цветное изображение. Выполняется сегментация не по цвето-яркостным и текстурным характеристикам, а по объектам, отличающимся трехмерной формой. Сначала выполняется обычная сегментация изображения по цветовому признаку, которая, в рамках поставленной задачи, является избыточной для раскрашенных объектов. Затем, для каждого такого сегмента строится набор гипотез, состоящих в его цвете, освещении (цветном или белом), форме (плоская или не плоская, что оценивается методами Shape from Shading, в частности методом [13]), пластик или метал (спекулярное отражение). Строится мера похожести формы границы между двумя сегментами. Так, если два граничащих сегмента представляют собой, различным образом окрашенные части одной поверхности, то на границе сегментов происходит скачок яркости (цвета), однако вдоль границы яркость точек изображения меняется согласованно. Из указанных гипотез о свойствах первичных сегментов и весов связей между ними, строится взвешенный мультиграф гипотез, описывающий сцену. Каждый сегмент представлен набором листьев графа, соответствующих различным гипотезам об этом сегменте. Приводятся таблицы совместимости гипотез для соседних листьев. Ребра мультиграфа соединяют листья, относящиеся только к разным соседствующим сегментам (таким образом, граф не имеет петель и не является псевдографом, но является мультиграфом, задача не заключается в выделении из него простого графа), веса ребер определяются на основе совместимости гипотез для соседних сегментов (листьев). Потом решается задача выбора подграфа с максимальным весом, и его редуцирования. Ценность предложенного подхода состоит в том, что это одна из не многих попыток интеграции разнородной информации, полезной для восстановления сцены, производящая не просто склейку фрагментов сцены, восстановленных различными методами, но и анализ возможности соседства таких фрагментов, их стыковку между собой. В том числе, предложенный подход может оказаться очень полезным в случае, когда какие-либо фрагменты сцены восстанавливаются ненадежно, и по-разному различными методами, - тогда анализ окружения и совместимости, дает подход к автоматическому выбору результата, который наилучшим образом вписывается в контекст - наиболее достоверной гипотезы. Последнее обстоятельство существенно, так как в реальных сценах даже глаз и мозг человека не всегда правильно интерпретируют наблюдения, несмотря на их сложность, и массу используемых дополнительных сведений и знаний. Примером тому могут служить приведенная выше иллюстрация к алгоритмам Shape from Shading, и успешное существование искусства иллюзионистов.

1.4 Сравнительный анализ методов восстановления 3D сцен

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

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

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

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

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

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

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

Для поверхностей, имеющих текстуру, зависимость текстур от масштаба, расстояния до объекта, степени регулярности текстур, движения объектов сцены, и имеющегося в распоряжении времени, могут использоваться методы "Shape from Stereo", "Shape from defocusing", или "Shape from Focusing", а также их комбинации. Для поверхностей, не имеющих текстуры, применимы методы типа "Shape from Shading". Здесь важно отметить два обстоятельства. Во-первых, применение этих методов к уточнению каркаса, полученного факторизацией, заменяет задачу интерполяции на задачу восстановления истинной формы сцены. Во-вторых, путем интерполяции из модели, полученной факторизацией, может быть выбрано начальное приближение для указанных уточняющих методов, наложены граничные условия, и привлечены дополнительные данные для повышения устойчивости таких методов, например средняя нормаль к участку поверхности, примерный диапазон, в котором варьируется расстояние от камеры до участка поверхности, выбор для запуска таких методов точки зрения, обеспечивающей лучшие условия для применения выбранных методов. Другим важным способом интеграции прочих методов с каркасной моделью, является их использование до выполнения очередного шага уточнения, и достраивания каркаса с целью предварительной оценки расстояний (для упрощения задачи траекторного анализа и устранения неоднозначностей при сопоставлении характеристических точек), выявления движущихся объектов (в том числе движущихся только в некоторые интервалы времени), обнаружения внезапных изменений сцены, и предотвращения столкновений мобильной системы с объектами сцены. Последнее для мобильных систем представляется особенно важным, причем выбор метода предотвращения столкновений существенно зависит от характера как сцены, так и самой мобильной системы. В первую очередь, это, разумеется, планирование движения, основываясь на каркасной модели.

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

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

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

2. Система трехмерного зрения

2.1 Общая структура алгоритма восстановление 3D сцен

В качестве алгоритма была выбрана группа алгоритмов, основанных, на факторизации матриц [39], [40], [46]. Основанием для такого выбора послужили следующие причины:

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

2. Возможность работы с нестационарными сценами [40].

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

4. Возможность выбора различных приближений, применимых в диапазоне расстояний до объекта от менее и порядка базы [46] (максимального движения камеры) до бесконечности [39].

5. Невысокая вычислительная сложность, обусловленная тем, что в решении используются не изображения, а только координаты характеристических точек.

В результате применения подходов [39], [40], [46] получаются трехмерные координаты некоторых точек объекта с высокой точностью, по которым может быть построена поверхность в виде сетки или меша [47-49], координаты и ориентация камер, и при наличии близких объектов фокусные расстояния камер.

Особенностью методов факторизации [39], [40], [46] является требование наличия всех сопровождаемых характеристических точек на всех кадрах последовательности, что не всегда возможно, как по причине их потери трэкером, так и из-за заслонения их объектом, например при круговом объезде объекта. Это вызывает необходимость введения в систему блока выбора перекрывающихся поднаборов характеристических точек и кадров, образующих плотные матрицы и блока сшивки фрагментов модели (меша).

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

Система реализована на языке C++ в независимом от операционной системы виде.

2.2 Обнаружение характеристических точек

В качестве детектора и трекера характеристических точек был выбран алгоритм SIFT и SURF

Постановка задачи обнаружения характеристических точек и прослеживания их по последовательности цифровых изображений подразделяется на два пункта:

1. Критерий выбора характеристических точек.

2. Алгоритм прослеживания выбранных точек по последовательности кадров.

2.2.1 Метод SIFT

Нахождение особых точек. Основным моментом в детектировании особых точек является построение пирамиды гауссианов (Gaussian) и разностей гауссианов (Difference of Gaussian, DoG). Гауссианом (или изображением, размытым гауссовым фильтром) является изображение

где L -- значение гауссиана в точке с координатами (x,y), а sigma -- радиус размытия. G -- гауссово ядро, I -- значение исходного изображения, * -- операция свертки.

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

После построения пирамид дело остаётся за малым. Будем считать точку особой, если она является локальным экстремумом разности гауссианов. Для поиска экстремумов будем использовать метод, схематично изображенный на рисунке 2.2.

Рис. 2.2 Поиск экструмумов

Если значение разности гауссианов в точке, помеченной крестиком, больше (меньше) всех значений в точках, помеченных кругляшками, то эта точка считается точкой экстремума.

В каждом изображении из пирамиды DoG ищутся точки локального экстремума. Каждая точка текущего изображения DoG сравнивается с её восьмью соседями и с девятью соседями в DoG, находящихся на уровень выше и ниже в пирамиде. Если эта точка больше (меньше) всех соседей, то она принимается за точку локального экстремума.

Уточнение особых точек

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

где D -- функция DoG, X = (x,y,sigma) -- вектор смещения относительно точки разложения, первая производная DoG -- градиент, вторая производная DoG -- матрица Гессе.

Экстремум многочлена Тейлора находится путем вычисления производной и приравнивания ее к нулю. В итоге получим смещение точки вычисленного экстремума, относительно точного

Все производные вычисляются по формулам конечных разностей. В итоге получаем СЛАУ размерности 3x3, относительно компонент вектора X.

Если одна из компонент вектора X^ больше 0.5*шаг_сетки_в_этом_направлении, то это означает, что на самом деле точка экстремума была вычислена неверно и нужно сдвинуться к соседней точке в направлении указанных компонент. Для соседней точки все повторяется заново. Если таким образом мы вышли за пределы октавы, то следует исключить данную точку из рассмотрения.

Когда положение точки экстремума вычислено, проверяется на малость само значение DoG в этой точке по формуле

Если эта проверка не проходит, то точка исключается, как точка с малым контрастом.

Если особая точка лежит на границе какого-то объекта или плохо освещена, то такую точку можно исключить из рассмотрения. Эти точки имеют большой изгиб (одна из компонент второй производной) вдоль границы и малый в перпендикулярном направлении. Этот большой изгиб определяется матрицей Гессе H. Для проверки подойдет H размера 2x2.

Пусть Tr(H) -- след матрицы, а Det(H) -- её определитель.

Пусть r -- отношение большего изгиба к меньшему,

тогда



Нахождение ориентации ключевой точки.

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

m -- величина градиента, theta -- его направление.

Направление ключевой точки найдем из гистограммы направлений O. Гистограмма состоит из 36 компонент, которые равномерно покрывают промежуток в 360 градусов, и формируется она следующим образом: каждая точка окна (x, y) вносит вклад, равный m*G(x, y, sigma), в ту компоненту гистограммы, которая покрывает промежуток, содержащий направление градиента theta(x, y).

Направление ключевой точки лежит в промежутке, покрываемом максимальной компонентой гистограммы. Значения максимальной компоненты (max) и двух соседних с ней интерполируются параболой, и точка максимума этой параболы берётся в качестве направления ключевой точки. Если в гистограмме есть ещё компоненты с величинами не меньше 0.8*max, то они аналогично интерполируются и дополнительные направления приписываются ключевой точке.

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

Рис 2.3 Дескриптор

Гистограммы в регионах вычисляются так же, как и гистограмма направлений с тремя небольшими но:

1. Каждая гистограмма так же покрывает участок в 360 градусов, но делит его на 8 частей

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

3. В качестве ещё одних весовых коэффициентов берутся коэффициенты трилинейной интерполяции.

Дескриптор ключевой точки состоит из всех полученных гистограмм. Как уже было сказано размерность дескриптора на рисунке 32 компоненты (2x2x8), но на практике используются дескрипторы размерности 128 компонент (4x4x8).

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

2.2.2 Метод SURF

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

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

Рис.2.4 Особые точки

Гессиан инвариантен относительно вращения. Но не инвариантен масштабу. Поэтому SURF использует разномасштабные фильтры для нахождения гессианов.

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

После нахождения ключевых точек, SURF формирует их дескрипторы. Дескриптор представляет собой набор из 64(либо 128) чисел для каждой ключевой точки. Эти числа отображают флуктуации градиента вокруг ключевой точки. Поскольку ключевая точка представляет собой максимум гессиана, то это гарантирует, что в окрестности точки должны быть участки с разными градиентами. Таким образом, обеспечивается дисперсия (различие) дескрипторов для разных ключевых точек.

Флуктуации градиента окрестностей ключевой точки считаются относительно направления градиента вокруг точки в целом (по всей окрестности ключевой точки). Таким образом, достигается инвариантность дескриптора относительно вращения. Размер же области, на которой считается дескриптор, определяется масштабом матрицы Гессе, что обеспечивает инвариантность относительно масштаба. Флуктуации градиента также считаются с помощью фильтра Хаара.

2.3 Восстановление 3D сцен по последовательности цифровых изображений методом факторизации матриц

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

Рассмотрим систему координат (if,, jf, kf), связанную с камерой, такую, что орт kf направлен вдоль оптической оси в направлении наблюдаемой сцены (см. рис.2.3.1).



Рис. 2.3.1 Постановка задачи для одной камеры

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

Введем понятие передней плоскости изображения (ППИ), которая расположена в плоскости z=l, где l - фокусное расстояние объектива. В дальнейшем будем считать, что изображение формируется на ППИ. Это не влияет на описание задачи в рамках геометрической оптики, однако, позволяет избавиться от несущественных знаков и усложнения, связанного с лишним преобразованием системы координат. Орты if,, jf направлены вдоль строки и столбца пикселей изображения, формируемого в ППИ камеры. Пусть на объекте находится точка p с координатами (x, y, z). Координаты ее изображения на ППИ обозначим (), тогда из подобия треугольников, выделенных на рисунке, можно записать:



Уравнения (2.3.1) устанавливают связь между измеряемыми на опыте значениями ,координатами точки объекта в трехмерном пространстве, и фокусным расстоянием камеры.

Рис. 2.3.2 Постановка задачи для F камер

Пусть имеется P точек на объекте, и F камер, или кадров, снятых при различных положениях камеры (см. рис. 2.3.2). Принадлежность величины к точке объекта p (point) будем обозначать индексом p. Индексом f (frame) будем обозначать величины, относящиеся к определенному кадру (камере и ее положению). Тогда уравнения (2.3.1) принимают вид:



Переходя к произвольной системе координат, и записывая (2.3.2) в векторной форме, получим:

Уравнения (2.3.3) являются основой для решения задачи восстановления трехмерной формы объекта. Рассмотрим их более подробно. При съемке объекта камерой, измеримыми являются величины , - всего 2FP величин. Неизвестными являются sfpu~fpv~p, tf, lf - т.е. 3P+3F+F=3P+4F величин, и F троек векторов (if,, jf, kf), на которые наложены ограничения ортонормированности:

Итого получаем (6-3)F=3F неизвестных величин. Таким образом, 2FP уравнений определяют 3P+7F неизвестных. Система уравнений (2.3.3) может быть разрешена относительно этих неизвестных в смысле метода наименьших квадратов, если выполняется условие 2FP>3P+7F, которое при достаточном количестве точек объекта и снятых кадров всегда справедливо. Минимальными значениями F, P являются следующие пары: (F=5,P=5), (F=12,P=4), (F=3,P=7).

Заметим, что количество неизвестных может быть уменьшено, если заданы дополнительные условия, например постоянство фокусного расстояние (отсутствие zoom-а), уменьшает число неизвестных на F-1. Из уравнений (2.3.1) видно, что размеры трехмерной сцены могут быть восстановлены только с точностью до масштабного коэффициента, поэтому для восстановления в абсолютных единицах, требуется знание какого-нибудь размера сцены, например, расстояния между двумя точками на объекте в трёхмерном пространстве, или же расстояния между двумя положениями камеры. Например, если заданы две камеры с одинаковыми фокусными расстояниями l, одинаково сориентированные, так что (if,, jf, kf) совпадают и известны их положения, в частности tfkf = tfjf = 0, t1if = -t2if = Ѕ d, то при P = 1 из уравнений (2.3.3) легко получить решение задачи восстановления трехмерных координат сцены на стереопаре изображений с известной базой d.

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

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

где a - положительный масштабный коэффициент, определяющий диапазон изменения величин; - размеры одного пикселя на фоточувствительной матрице в метрических единицах; N = max(Nx, Ny), где Nx, Ny - количество пикселей на изображении (разрешение по x,y соответственно); обычно, Nx>Ny. Перейдём к новым переменным:

где б - отношение разрешений по x и y (aspect ratio); величины Nnx, Nny - это координаты пикселя,(вычисляемые как расстояние от центра кадра), делённые на ширину изображения, - всегда в диапазоне



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

Далее будем полагать б=1. Значение нормировочного коэффициента a может быть существенным только для устойчивости и точности численных методов.

Перейдём к мировой системе координат (МСК). В ней координаты точки p задаются вектором sp, позиции камеры f - вектором tf, а её ориентация, - координатными ортами (if,, jf, kf), причём kf = [if, jf]. В итоге уравнения (2.3.8) приобретают вид:

2.3.2 Математический вывод приближений

Выберем начало МСК в центре масс (ЦМ) точек объекта:



Тогда z-координата центра масс на данном изображении в МСК:

И z-координата точки p выражается следующим образом

.

Выражение (2.3.9) перепишем в следующем виде, используя (2.3.12):

и разложим в ряд Тейлора с точностью до членов второго порядка малости по, переобозначив сумму на у:

Теперь, собирая члены при и tf:

Заметим, что нормирующий множитель не существенен, поскольку, как отмечалось в разделе 2.3.1, восстановление происходит с точностью до масштабного коэффициента. Выражение (2.3.16) соответствует приближению ортографической проекции (ОП) [41].

Ограничиваясь только предположением |sp|<<zf, и заменяя в (2.3.9) zfp на zf , что эквивалентно отбрасыванию в (2.3.14) всех слагаемых в сумме, кроме первого, приходим к приближению масштабируемой ортографической проекции (МОП) [39]:

Оставляя в разложении (2.3.15) только члены, линейные по sp:



получим приближение параперспективной проекции (ППП) [39]:

Введём новые обозначения:

Таблица 2.3.1



2.3.3 Геометрический смысл приближений

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

2.3.3.1 Приближение ортографической проекции

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

Рис. 2.3.3. Ортографическая проекция в двумерном пространстве

Из геометрии рис. 2.3.3 можно непосредственно получить выведенные нами ранее формулы 2.3.16:



Таким образом, ОП - приближение описывается линейными уравнениями. С одной стороны, это делает его привлекательным, но, в то же время, существенно ограничивает его применимость т.к. с его помощью невозможно восстановить расстояние до объекта. Кроме того, возникает неоднозначность в определении координаты z точек объекта, связанная с "уплощением" объекта в плоскости изображения.

2.3.3.2 Приближение масштабируемой ортографической проекции

В приближении масштабируемой ортографической проекции10 (рис. 2.3.4) все точки объекта сначала проецируются параллельно оптической оси камеры на воображаемую плоскость, проходящую через ЦМ точек объекта (на рис. 2.3.4 ЦМ совмещён с началом МСК). Понятно, что и в этом случае имеет место "уплощение" объекта, а следовательно, и неоднозначность в восстановлении знака глубины сцены.

Рис. 2.3.4 Масштабируемая ортографическая проекция в двумерном пространстве

Из этой модели получаем систему (2.3.17):