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

 

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

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

г.

Вcтупление

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

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

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

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

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

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

GPS - Global Positioning System,

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

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

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

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

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

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

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

ПП - перспективной проекции,- сингулярного разложения матриц,

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

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

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

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

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

Содержание

Введение

. Общая часть

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

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

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

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

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

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

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

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

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

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

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

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

.2.1 Метод SIFT

.2.2 Метод SURF

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.6 Результат

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

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

Заключение

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

Приложение А

Введение

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

Задача восстановления и распознавания трехмерных сцен в настоящее время интенсивно разрабатывается большим числом исследователей и организаций. Область применения этих алгоритмов также чрезвычайно широка. Это задачи навигации роботов и управления автомобилем [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Обоснование необходимости разработки программного комплекса

Местоположение самолёта на местности сейчас определяет спутниковая система навигации <#"justify">1.2Постановка задачи

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

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

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

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

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

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

.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], который вычисляется следующим образом:

, 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", основанные на факторизации матриц. Оправданием такого выбора являются следующие достоинства этой группы методов:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 - отношение большего изгиба к меньшему,

тогда

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.2 Метод SURF

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

Метод ищет особые точки с помощью матрицы Гессе <#"233" src="doc_zip29.jpg" />

Рис.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):

Благодаря введению в систему величины zf, метод восстановления трёхмерных координат точек объекта, основанный на МОП - приближении, работает объективно лучше, чем метод с применением ортографической проекции, поскольку появилась возможность восстановить не только форму объекта, но и расстояние до него. Это обусловлено тем фактом, что линейный масштаб изображения изменяется обратно пропорционально расстоянию z:

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

Построение, соответствующее приближению параперспективной проекции, отличается от построения в МОП - приближении только направлением проецирования на воображаемую плоскость, в данном случае оно происходит параллельно направлению на ЦМ точек объекта (рис. 2.3.5). Ранее было показано, что ППП - приближение соответствует более аккуратному разложению 1/zfp в ряд Тейлора, то есть этот вариант линейного приближения даст лучшую точность восстановления формы объекта, чем все рассмотренные ранее.

Рис. 2.3.5 Параперспективная проекция в двумерном пространстве

Из аналитической геометрии известно, что проекция точки, заданной вектором p на плоскость с нормалью n, в направлении r, описывается следующим уравнением:

здесь d - расстояние до плоскости из начала СК. На изображении f, каждая точка объекта sp проецируется в направлении вектора (c-tf) соединяющего ЦМ точек объекта с началом КСК, на плоскость, которую мы зададим нормалью kf, и расстояние из начала СК d=(c,kf), здесь c - луч, соединяющий начало МСК с ЦМ точек объекта. Воспользовавшись уравнением (2.3.21), получаем:

Подставляя полученные sfp в уравнения для приближения масштабируемой проекции (2.3.17), получим:

Поместим начало МСК в ЦМ точек объекта:

С учетом (2.3.24), система (2.3.23) приобретает вид (2.3.19):

Для случая параперспективного приближения, ограничения на орты КСК, выглядят следующим образом:

Переписывая (2.3.25) в матричной форме, получаем:

Где

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

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

В модели перспективной проекции (ПП) лучи идут именно так, как это происходит в реальности, то есть по прямой (см. рис. 2.3.6).

Рис. 2.3.6 Перспективная проекция в двумерном пространстве

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

Где

В настоящий момент существует несколько методов решения точной задачи. Все они сводятся к переопределённой нелинейной задаче наименьших квадратов в переменных движения и формы. В качестве иллюстрации, рассмотрим метод решения точной задачи, предложенный в[39].

Предлагается минимизировать ошибку:

Из ортов КСК формируется матрица вращения, как функция трёх углов ?f, ?f, ?f:

Таким образом, мы имеем 6 параметров, отвечающих за движение камеры: xf, yf, zf, ?f, ?f, ?f, и 3 параметра, характеризующие форму сцены: sp=[sp1, sp2, sp3]. Уравнения (2.3.29) определяют переопределённую систему 2FP уравнений для 6F+3P неизвестных, и мы можем минимизировать ошибку (2.3.31), учитывая (2.3.32). Задаваясь начальными значениями переменных, в методе предлагается итерационно уточнять их. Однако, для того, чтобы пользоваться техникой решения нелинейных задач методом наименьших квадратов, необходимо на каждом шагу итерации создавать и обращать матрицу размером (6F+3P)Ч(6F+3P). При достаточно больших F, P, задача минимизации будет просто неразрешима в силу слишком большого числа переменных. Поэтому предлагается использовать специфическую структуру уравнений, решая их отдельно для переменных движения и формы. Сначала мы фиксируем переменные формы, и находим решение уравнений, минимизирующее ошибку (т.е. предлагается решать F систем уравнений с 6 неизвестными). При этом, минимизация производится независимо по каждой переменной движения. Затем фиксируем переменные движения, и минимизируем ошибку по переменным формы (т.е., решаем P систем с тремя неизвестными). Итерации необходимо производить до тех пор, пока ? не достигнет своего минимального значения. Таким образом, сложность задачи была существенно понижена, и она стала разрешимой.

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

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

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

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

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

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

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

Сформируем из координат {(ufp, vfp): f=1..F, p=1..P} матрицу измерений W размера 2F x P:

Каждая строка матрицы W содержит координаты точек (ufp, vfp), относящиеся к определённому кадру последовательности, а каждый столбец, - те же величины для конкретной точки, присутствующей на всех изображениях. Тогда выражение (2.3.33) можно переписать в матричной форме:

где M - матрица движения (ориентации камер) размера 2F x 3, S - матрица формы (точки на объекте), размера 3 x P, T - вектор трансляций камер (положение камер в пространстве), размера 2F x 1, формируемые следующим образом:

Поместим начало МСК в ЦМ точек объекта (2.3.10):

Заметим, что вектор T можно получить построчным суммированием элементов матрицы W:

тогда дальше будем работать с матрицей W*:

Поскольку матрица W* представима в виде произведения матрицы M размера 2F x 3 и матрицы S размера 3 x P, её ранг не может быть больше 3. В настоящей работе выполнение факторизации ранга 3 матрицы W, производилось посредством сингулярного разложения матриц (SVD):

здесь U, V - ортогональные матрицы, а ? = diag(?1,…,?n), n = min(2F, P), ?1,…,?n - сингулярные числа матрицы W. Упорядочим все сингулярные значения по убыванию, и выберем из матрицы ? верхнюю подматрицу размера 3 x 3, значениями которой будут 3 максимальных сингулярных числа, соответствующих основным компонентам матрицы W. Тогда, выбирая из матриц U и V подматрицы из строк, соответствующих трем наибольшим сингулярным числам, получаем аппроксимацию к матрице W. Понятно, что такое разложение не единственно, поскольку межу матрицами M ) и S) всегда можно вставить произведение прямой и обратной матриц Q ранга 3, ничего при этом не изменив, тогда можно записать:

Здесь М и S подразумевают истинные матрицы движения и формы.

получим следующие системы уравнений для приближений для нахождения матрицы Q:

Где значения и соответствуют таблице 2.3.2. (см. также табл. 2.3.1)

Таблица 2.3.2

В данной работе системы (2.3.41) решались методом наименьших квадратов (МНК) с применением SVD.

Неоднозначность восстановления формы сцены связана с тем, что в задачу легко можно внести знаковую неоднозначность, заменив матрицу Q на следующую матрицу:

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

Неоднозначность в третьем знаке связана с тем, что во всех рассмотренных нами линейных приближениях, глубиной объекта по сравнению с расстоянием до него пренебрегают (происходит так называемое "уплощение" сцены). Как следствие, это приводит к неоднозначности восстановления формы сцены S и движения камер M.

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

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

Поскольку метод точный, он описывается уравнеиями (2.3.39), в которых мы полагаем g постоянным для всех кадров.

Перепишем (2.3.44) в виде, используя уже встречавшуюся замену zf на zf:

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

Т.е. матрица W представлена в виде двух слагаемых, первое из которых, W1, соответствует введённой ранее матрице измерений, а второе, W2, зависит от W1, sp, kf, и имеет смысл поправки на перспективные искажения:

Как было показано ранее, ранг правой части (2.3.45) всегда равен 3, поэтому предлагается по итерациям подбирать параметр ?, используя известные с предыдущего шага значения sp, kf, таким образом, чтобы сохранить равенство рангов обоих частей (2.3.45). Итак, система уравнений (2.3.45) может быть решена итерациями, путём уточнения поправочной матрицы.

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

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

Алгоритм.

. Полагаем в (2.3.46) Номер итерации q=0, параметр ?=0, W(0):=W1, W2(0):=0.

. Решаем систему уравнений, описывающую МОП-приближение:

(q) = M(q)S(q) + T(q)

. Полагаем теперь: q:=q+1.

. Вычисляем поправочную матрицу:

(q)=W2(q)(M(q-1), S(q-1), T(q-1))

. Находим коэффициент ?(q), подбирая его таким, чтобы ранг матрицы W(q) оставался равным 3, то есть надо искать:

где ?1, ?4 - это первое и четвёртое сингулярные значения матрицы W(q). Диапазон изменения параметра ?(q) определяется из условия:

. Обновляем матрицу

(q)=W1+?(q)W2(q)

7. Переходим к п.2, если не выполняется условие выхода:

|?(q - 1)- ?(q).| < ?,

где значение ? выбирается достаточно малым.

. Устраняем неоднозначность знака глубины сцены:

. Выравниваем МСК по СК, связанной с одной из камер.

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

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

.1.1 Построение моделей для генерации синтетических данных

В среде 3d Max была построены модели для генерации синтетических данных:

)Модель, представляющая собой куб, и движение камеры происходило по двум оси.

)Модель, представляющая собой прямоугольный параллелепипед, движение камеры свободно происходило по трём осям.

)Модель, представляющая собой две пирамиды и параллелепипед, разных высот.

Во всех трёх случаях камера было ориентирована на объект.

Первая модель представлена на рисунке 3.1

Рис.3.1 Модель «Куб»

Модель представляет собой куб со стороной 5 ед. На модель наложена текстура «Кирпич». Характеристические точки выбирали и сопровождали вручную без использования алгоритма. Точки были выбраны на верхней и фронтальной гранях куба. На рисунке они отмечены красным цветом. Камера во всех снимках серии была направлена на объект. Движение камеры происходило сверху вниз в вертикальной плоскости проходящеё через центр куба.

Вторая модель представлена на рисунке 3.3.

Рис.3.3 Модель «Брусок»

Модель представляет собой параллелепипед со сторонами 8х6х16. На модель также наложили текстуру «Кирпич». Точки были выбраны на трёх наблюдаемых плоскостях. На рисунке они отмечены красным цветом. Камера двигалась во всех трёх плоскостях.

Третья модель представлена на рисунке 3.5.

Рис. 3.5 Трёхмерная сцена

Рис.3.6 Движение камеры

Модель представляет собой набор примитивов - две пирамиды и параллелепипед. Высота одной пирамиды больше высоты параллелепипеда в два раз, а в свою очередь высота параллелепипеда больше в два раза маленькой пирамидки. Характерные точки взяты на вершинах примитивов, всего 18, по 5 у пирамид,8 на параллелепипеде. Камера был направлена в центр модели и двигалась по кругу, для того чтобы сохранить неизменность фокуса. Траектория движения камеры представлена на рисунке 3.6 оранжевым цветом. Серия снимков представлена на рисунке 3.7.

Первую модель будем использовать для анализа влияния на алгоритм изменения фокусного расстояния.

Вторая модель укажет влияние на результат свободного движения камеры.

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

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

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

Входными параметрами программы являются имена файлов в формате *.txt:

. Файл с матрицей W, размера [2F,P], нормализованной.

. Файл с вектором g, размера [F,1], т.е. с фокусом. В простейшем случае - вектор из единиц. Подразумевает возможность произведения съемки с различными фокусами, однако пока итерационный алгоритм не был обобщен на многомерный случай.

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

Будем обозначать координаты точек модели в КСК вектором xp, а координаты восстановленных точек в восстановленной КСК, - вектором sp, и смещение камеры - вектором t.

Переход от одних координат к другим, осуществляется следующим преобразованием:

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

Условия минимума:

в последнем равенстве подразумевается производная по параметрам матрицы R. Распишем подробнее (3.8):

Отбрасывая в (3.10) все постоянные члены, и учитывая, что R - матрица поворота, то есть , получаем:

Отсюда получаем явные выражения для ?,t:

Поскольку мы ищем решение задачи в МСК с началом в ЦМ точек объекта:

то формулы (3.12) упрощаются.

Выпишем слагаемые в ?, зависящие от R:

Далее действуем следующим образом: из условия, находим матрицу R:

затем, зная R, находим масштабный множитель ? и вектор трансляций камер t по формулам (3.13).

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

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

где sf - восстановленная матрица формы , sf0 - эталонная матрица формы

Ось находим как средний вектор смещения восстановленных координат относительно истинных:

где tf - восстановленная позиция камеры, tf0 - эталонная позиция камеры.

Теперь проекции смещений восстановленных камер относительно истинных на эту ось и дадут нам искомую погрешность, которую мы берем в отношении к минимальному расстоянию до камеры:

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

Рис.3.4.1 Модель «Куб»

Рис.3.4.2 Результат работы алгоритма

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

? = 0.508

EZ= 1.654=0.673

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

Рис.3.4.3 Модель «Брусок»

Рис.3.4.4 Результат работы алгоритма

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

?=1.809

EZ=8.507=4.51

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

Рис.3.4.5 Модель рельефа местности

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

Рис.3.4.6 Результат работы алгоритма

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

Рис.3.4.7 Результат работы алгоритма. Вид сбоку.

Номер точкиВысота эталонной моделиВысота восстановленной моделиНевязки165.910,09(1,5%)200.070,07300.150,15400.10,1500.050,05644.10,1(2,2%)743.890,11(2,7%)843.870,13(3,2%)943.950,05(1,2%)1000.20,21100.140,141200.10,1130-0.010,011421.950,05(2,5%)1500.010,011600.040,04170-0.020,021800.020,02

Суммарная погрешность определения высоты: 0.08.

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

Рис.3.5.1 Реальное изображение

Рис.3.5.2 Результат работы алгоритма

На серии изображении, первое из которой представлено на рисунке, взяты характеристические точки (на рисунке отмечены красным цветом). Результат работы алгоритма представлен на рисунках , , . Проведя анализ получившейся карты высот, можно сделать вывод, что дом, отмеченный на рисунке зеленым, имеет высоту 26,25 м. Дом, отмеченный синим, в два раза выше первого, высота примерно 51 м. Кран (на рисунке желтый овал) имеет высоту 44 метра.

3.6 Результат

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

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

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

.1 Определение целесообразности разработки алгоритмов и программных продуктов

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

Внедрение программного комплекса позволит значительно повысить точность ориентирования на местности в зимний период.

Функциональные характеристикиЕдиница измеренияВеличина функциональных характеристикЗначимость характеристиканалогновый вариантПростота использования-660,08Точность-580.3Ресурсная и временная экономичность-670.1Надежность-570.2Сопровождаемость-690.1Защищённость-760.12Способность к взаимодействию-690.1Таблица 4.1 Функциональные характеристики алгоритмов и ПП

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

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

Индекс технического уровня проектируемого изделия

где , - уровень i-й функционально-технической характеристики соответственно нового (проектируемого) и базового (аналогичного) изделий;

- значимость i-й функционально-технической характеристики качества изделия; - количество рассматриваемых функционально-технических характеристик.

Рассчитаем индекс технического уровня:

.

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

,

где Кв - коэффициент влияния.

Примем Кв=0.25. Тогда индекс технического уровня равен:=1.352*1.25=1.69.

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

4.1 Определение трудоемкости и затрат на создание алгоритмов и ПП

Основой для определения затрат на создание алгоритмов и программных продуктов является показатель трудоемкости работ.

Структура затрат труда на создание подсистемы мониторинга конкурсного цикла представлена в таблице 4.2.

Таблица 4.2 Структура трудовых затрат по стадиям (этапам) НИР

№ п/пНаименование стадии (этапа) работДоля работ на стадии (этапе) в общем объеме работ, %1.Анализ предметной области и изучение средств разработки52.Изучение программируемой задачи23.Анализ методов решения задачи54.Составление структурных схем алгоритмов ПП75.Технико-экономическое обоснование выбора варианта алгоритма ПП46.Уточнение и доработка выбранного варианта алгоритма ПП107.Составление ПП248.Отладка ПП309.Испытание и анализ работы ПП в реальных условиях810Составление технической документации5ИТОГО:100

При использовании технологии баз данных, общая трудоёмкость программирования определяется согласно формуле (4.5):

где:

КОФ - коэффициент, учитывающий затраты на оформление эксплутационной документации по разработанному ПП ();

КВН - коэффициент внедрения, учитывающий затраты на экспериментальные расчёты и приём ПП в эксплуатацию ();ВВ - базовое значение трудоёмкости программирования ввода сообщений из БД;Р - базовое значение трудоёмкости программирования расчётов;ВЫВ - базовое значение трудоёмкости программирования вывода сообщений, форм документов;ВВ, mВЫВ - число соответственно вводимых и выводимых анализируемых характеристик объектов, сообщений из БД, форм документов;- коэффициент, характеризующий сложность входного контроля;- фактор, учитывающий объём обрабатываемых данных;

? - фактор, учитывающий сложность алгоритма.

Примем следующие значения коэффициентов:

КОФ=1.4;

КВН=1.1;ВВ =0.1;Р =0.6;ВЫВ =0.2;ВВ =50;ВЫВ =75;=2.5;=0.6;

? =0.5.

Подставляя эти значения в формулу (4.5), получим значение общей трудоёмкости:

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

Таблица 4.3. Перечень исполнителей

Категория исполнителейЧисло исполнителейЗарплата (руб./месяц)Часовые тарифные ставки, руб.Начальник отдела130000170Инженер11600091Программист11600091

Часовые ставки разработчиков определены исходя из длительности рабочего дня - 8 часов и числа рабочих дней в месяце - 22.

?но= 30000/(22*8)=170

?и= 16000/(22*8)=91

?пр= 16000/(22*8)=91

Расчет заработной платы на основе трудоемкости соответствующих стадий работ (таблица 4.2) производится по следующей формуле:

где k - количество этапов;

Тэi - трудоемкость i-го этапа;

, -средняя часовая тарифная ставка оплаты работ i-го этапа.

Размер премии составляет 10% от заработной платы.

Результаты расчетов приведены в таблице 4.4.

Таблица 4.4 Расчет заработной платы

Стадия (этап)Трудо- ёмкость, чел.-ч.ИсполнителиЧасовая ставка, р.Средняя часовая ставка, рЗаработная плата, рЗаработная плата с учётом премии, рДолжностьЧис-лен-ность181.25Начальник отдела117013010562.511618.75Инженер191232.5Инженер191912957.53253.25Программист191381.25Программист191917393.758133.1254113.75Программист1919110351.2511386.375565Инженер1919159156506.5Программист1916162.5Программист1919114787.516266.257390Программист1919135490390398487.5Программист1919144362.548798.759130Инженер191911183013013Программист1911081.25Начальник отдела11701179506.2510456.875Инженер191Программист191ИТОГО:153156.25168471.87

Затраты на создание ПП определяются по следующим статьям расходов:

1.Материалы;

2.Специальное оборудование;

.Заработная плата основных исполнителей;

.Отчисления на единый социальный налог основных исполнителей (26,2%);

.Накладные расходы;

.Прочие расходы.

При разработке ПП предполагается использовать:

Канцелярские товары стоимостью 1000 руб.

Картридж для принтера стоимостью 2800 руб.;

Флеш накопитель стоимостью 400 руб.

Общая сумма расходов на материалы составит:мат. = 4200 руб.

Затраты на специальное оборудование рассчитываются по формуле:

,

где - стоимость покупки оборудования;

- процент занятости оборудования (60%).

Данные по стоимости оборудования приведены в таблице 4.5.

Таблица 4.5

№ п/пСостав оборудованияКоличествоПервоначальная стоимостьОбщая стоимость1ПЭВМ Pentium VI320000600002Принтер15000500065000

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

Затраты на зарплату основных исполнителей равны сумме затрат на каждой стадии и составляют ЗППП = 153156.25руб.

Расчет отчислений в ЕСН ведется по формуле:

где ЗПЗП - заработная плата основных исполнителей;

%СФ - ставка налога (26,2%).

Накладные расходы (на научно-техническую информацию) - 3000 руб.

Таблица 4.6 Структура затрат на создание ПП

№ п/пНаименование элементов и статей затратЗатраты, руб.Удельный вес, %1Материалы420042Специальное оборудование7800143Заработная плата основных исполнителей153156.25604Отчисления на единый социальный налог основных исполнителей40126175Накладные расходы30006Прочие расходы4004ИТОГО208682,25100

4.3 Оценка экономической эффективности

Для оценки экономической эффективности создаваемых алгоритмов и ПП, необходимо выяснить механизм их действия на экономические показатели и на основании этого вычислить годовой экономический эффект. Внедрение разрабатываемого программного комплекса приведёт к повышению качества работы. Тогда показатель годового экономического эффекта будет вычисляться по формуле (4.14):

,

где:

- индекс технического уровня нового варианта реализации системы;

, - годовые эксплутационные затраты в информационной системе по базовому и новому варианту.

Индекс технического уровня был вычислен в первом пункте работы (см. формулу 4.4.). 1,69

Годовые эксплуатационные затраты при выполнении работы информационной системой включают:

·Затраты на оплату труда персонала, обслуживающего ИС ();

·Отчисления на единый социальный налог ();

·Страховые социальные расходы на производственный травматизм ();

·Амортизационные отчисления ();

·Затраты на электроэнергию для решения комплекса задач ();

·Затраты на текущий ремонт ();

·Затраты на технические носители информации () ;

·Накладные расходы по эксплуатации ().

Далее представлены формулы для расчёта всех составляющих годовых эксплутационных затрат.

. Затраты на оплату труда персонала, обслуживающего ИС, вычисляются согласно формуле (4.15):

где:

- коэффициент использования мощности ИС для решения комплекса задач с применением анализируемого ПП в соответствующем году;

где:

- машинное время, используемое в течение года для реализации данного ПП, час.;

- годовой эффективный фонд времени работы вычислительной техники, час.;

- среднегодовая численность персонала j-ой профессиональной группы (чел.);

- месячный оклад персонала j-й профессиональной группы (руб.);

- коэффициент дополнительной заработной платы;

- коэффициент премиальных выплат.

4.4 Выводы

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

1)Определена целесообразность разработки подсистемы.

Получено значение индекса технического уровня J=1.69.

2)Определена трудоемкость и затраты на создание подсистемы.

Общая трудоёмкость tПР БДО=1625 чел.-час.

Материальные затраты составили 208682,25 руб.

) Определены уровень экономической эффективности и срок окупаемости системы.

Уровень экономической эффективности составил ЕПП=0.86

Срок окупаемости затрат на создание системы составит 9 месяца.

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

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

Характеристика помещения

Рабочее помещение имеет следующие характеристики:

Комната прямоугольный формы(длина - 3 м, ширина - 5 м). Высота - 4м.

Площадь помещения 15 м2, объем - 60 м2 . Количество рабочих мест в помещении, оснащенные ПЭВМ - 3.

Площадь - 5 кв.м на одного работающего, объем - 20 кубометра на одного работающего, что соответствует норме согласно САНПИН 2.2.2/2.4.1340-03 для пользователей ПЭВМ с ВДТ на базе плоских дискретных экранов (жидкокристаллические, плазменные).

Характеристика технических средств

Помещение оснащено следующими техническими средствами:

. Тремя персональными компьютерами:

системный блок (U = 220В, L = 35 дБА, P = 650Вт);,

монитор (ЖК), U = 220 В, P = 35Вт);

клавиатура (U = 5В, P = 1 Вт);

манипулятор мышь (U = 5В, P = 1Вт).

Время работы аппаратуры составляет 9 часов в день.

. Одним лазерным принтером (U = 220В, L = 40 дБА, P = 130Вт).

Время работы принтера составляет 9 минут в день.

. Одним сканером (U = 220В, L = 30 дБА, P = 130Вт).

Время работы сканера составляет 9 минут в день.

В помещении имеется окно размером 2м, через которое осуществляется естественное освещение.

Искусственное освещение осуществляется с помощью трех светильников с четырьмя люминесцентными лампами.

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

Схема производственного помещения представлена на рисунке 1.

Рис. 1 Схема производственного помещения

Анализ условий труда в отделе обработки изображений Микроклимат.

Вычислительная техника является источником существенных тепловыделений, что может привести к повышению температуры и снижению относительной влажности в помещении. В помещениях, где установлены компьютеры, должны соблюдаться определенные параметры микроклимата, соответствующие ГОСТ 12.1.005-88 [2].

Согласно ГОСТ 12.1.005-88 работа в офисе по энергозатратам относится к категории работ 1а. в соответствии с которой должны соблюдаться требования из таблиц 2.

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

Таблица 2. Фактические и оптимальные величины показателей микроклимата производственного помещения

Период годаТемпература воздуха, °СОтносительная влажность воздуха, %Скорость движения воздуха, м/сфактич. значениеоптим. значениефактич. значениеоптим. значениефактич. значениеоптим. значениеХолодный2322-245040 - 600,10,1Теплый2423-255540 - 600,10,1

Обогрев помещения осуществляется с помощью центральных отопительных приборов - батарей. Для подачи свежего воздуха используется кондиционирование. В отделе обработки информации используется Кондиционер Samsung AW05M0YEB

Технические характеристики:

? Тип: оконный

? Производительность (Охлаждение) (БТЕ/ч): 5200

? Производительность (Охлаждение) (Ккал/ч): 1310

? Производительность (Охлаждение) (кВт): 1.52

? Управление: механическое

? Энергоэффективность (Охлаждение): 9.0

? Номинальное напряжение: 220-240V/50/1

? Удаление влаги (л/ч): 0.7

? Производительность (м3/час): 228

? Потребляемая мощность (Охлаждение) (Вт): 580

? Рабочий ток (Охлаждение) (A): 2.5

? Габаритные размеры (ШхВхГ) (мм): 424*325*321

? Масса, нетто (кг): 18.5

Освещенность

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

Требования к освещённости рабочего места определяются СНиП 23-05-95 в соответствии, с которым при данных параметрах - размер объекта: очень высокой точности (от 0.15 до 0.30); разряд зрительной работы II; подразряд зрительной работы - в; контраст объекта: большой; характеристика фона: средний; при системе комбинированного освещения - всего En = 1500 Лк, в том числе от общего En = 200 Лк. Искусственное освещение в отделе обработки информации осуществлено в виде комбинированной системы с использованием люминесцентных источников света. Для освещения помещения отдела обработки информации используется светильники NC-2АС418С (Пассат). Лампы ЛБ-18, которыми оснащены светильники, не осуществляют требуемую освещённость. Освещенность на поверхности стола в зоне размещения рабочего документа составляет менее 200 лк. Установлены светильники местного освещения для подсветки документов.

Шум

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

Электроопасность

Помещение отдела обработки изображений по опасности поражения электрическим током можно отнести к 1 классу, т.е. это помещение без повышенной опасности (сухое, беспыльное, с нормальной температурой воздуха, непроводящими полами). Для источника питания на рабочем месте используется сеть переменного тока напряжением 220 В, частотой 50 Гц. Допустимое напряжение для аварийного режима и временем воздействия свыше 1 секунды 20В. На рабочем месте программиста из всего оборудования металлическим является корпус системного блока компьютера, а источником поражения электрическим током может быть источник питания. Используются системные блоки класса защиты 1, в которых рабочая изоляция и элемент для заземления, провод с заземляющей жилой для присоединен к системе заземления.

В качестве защиты от поражения электрическим током в отделе обработки изображений используется естественное и искусственное заземление. В нашем отделе используется схема из 12 заземлителей длиной L = 10м. Согласно "правилам устройства электроустановок", в электроустановках напряжением до 1000 В и потребляемой мощностью более 100 КВт сопротивление заземлительного устройства должно быть не более 4 Ом, в нашем случае 1,408 Ом.

Электромагнитное излучение

Электромагнитные поля, характеризующиеся напряженностями электрических и магнитных полей, наиболее вредны для организма человека. Переменные электромагнитные поля, которые создаются блоком питания и всей электрической схемой, ЖК монитор излучает так же, как и ЭЛТ.

Таблица 3. Нормативные и фактические значения электромагнитных полей

Основной факторНормативное значениеФактическое значениеНапряженность электромагнитного поля по магнитной составляющей на расстоянии 50 см от поверхности видеомонитора, А/М0.3 А/М0.24 А/МНапряженность электромагнитного поля по электрической составляющей на расстоянии 50 см от поверхности видеомонитора, В/М10 В/М8 В/МНапряженность электростатического поля, кВ/мНе более 20 кВ/м15 кВ/мНапряженность электромагнитного поля на расстоянии 50 см вокруг ВДТ по электрической составляющей (в диапазоне частот 5Гц/2 - 400кГц)Не более 25 В/м/2.5 В/м20 В/м/2.5 В/мПлотность магнитного потока в диапазоне частот 5 Гц - 2 кГц/2-400кГц; нТл250нТл/25 нТл200нТл/20 нТлПоверхностный электростатический потенциал, В600 В500 В

Пожароопасность

Рассматриваемое помещение отдела по пожарной опасности относится к категории В3(см. таблица 4), поскольку в нем находятся твердые горючие и трудногорючие вещества и материалы (книги, документы, мебель, оргтехника и т.д.) способные при взаимодействии с огнем гореть без взрыва. В нём на видном месте располагается «План эвакуации людей при пожаре», имеется система пожарной сигнализации, а также находятся углекислотные огнетушители ОУ-3(2 шт.), способные как эффективно справляться с пламенем, так и оставлять в сохранности электрооборудование.

Таблица 4. Категории помещения

Древесина:кр =13,9 кВт X м-2=120кг

Слоистый пластик qкр =15,4 кВт X м-2=100кг=13,9*120+15,4*100=1668+1540=3208 МДж*кг-1=3208/15=213МДж*м-2

Следовательно помещёние относится к категории В3.

Основные источники возникновения возгорания:

короткие замыкания;

перегрузки;

повышение переходных сопротивлений в электрических контактах;

перенапряжение;

возникновение токов утечки.

Эргономические факторы

Требования к рабочему месту определяются в соответствии с ГОСТ 12.2.033-78.

Высота над уровнем пола рабочей поверхности, за которой работает оператор, составляет 720 мм. Желательно, чтобы рабочий стол оператора при необходимости можно было регулировать по высоте в пределах 680 - 780 мм. Размеры поверхности стола 1600 х 1000 кв. мм. Под столом имеется пространство для ног с размерами по глубине 650 мм. Рабочий стол оператора также имеет подставку для ног, расположенную под углом 15° к поверхности стола. Длина подставки 400 мм, ширина - 350 мм. Удаленность клавиатуры от края стола должна быть не более 300 мм, что обеспечит оператору удобную опору для предплечий. Расстояние между глазами оператора и экраном видеодисплея составляет 75 см.

Рабочий стул сотрудника снабжен подъемно-поворотным механизмом. Высота сиденья регулируется в пределах 400 - 500 мм. Глубина сиденья составляет не менее 400 мм, а ширина - 450 мм. Высота опорной поверхности спинки 300 мм, ширина - 380 мм. Угол наклона спинки стула к плоскости сиденья изменяется в пределах 90 - 110°.

В соответствии с требованиями СанПин 2.2.2/2.11.1340-03[5] рабочее место программиста соответствует установленным стандартам.

Психофизиологические факторы

Работа оператора в отделе отработки изображений относится в группе 3 по напряженности трудового процесса.

К психофизиологическим вредным факторам относятся:

. Физические нагрузки (статические и динамические)

. Физиологически недостаточная двигательная активность (гиподинамия).

. Монотонность труда

. Перегрузка отдельных систем и органов

. Нервно-психические перенапряжения (эмоциональное, умственное)

Визуальные характеристики мониторов Samsung SyncMaster p2250, которые установлены у всех сотрудников, приведены в таблице 8.

Таблица 8. Визуальные характеристики рабочего монитора

Наименование фактораДействительное значениеДопустимое значение (СанПиН 2.2.2/2.4.1340-03)Размер экрана по диагонали59.9 смне менее 31 смУдаленность экрана55 смне менее 50 смУгол наблюдения80 градне менее 30 градРегулировка положения экрана по наклонуот -40 до 40 от -15 до 15 градЧастота обновления изображения75 Гц не менее 75 ГцЯркостный контраст1000:1 3:1Яркость знака300кд/м2 не менее 35 кд/м2

Расчетная часть

Установленные в настоящий момент лампы ЛБ - 18 не осуществляют требуемой освёщенности отдела обработки изображений, поэтому нужно рассчитать необходимый световой поток от лампы и выбрать оптимальную для освещёния лампу.

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

где Ен освещенность в соответствии с нормами, в нашем случае для комбинированной системы освещения 200Лк;площадь помещения, 15м2;коэффициент запаса, 1,6;коэффициент неравномерности освещенности по помещению,1,1количество ламп в светильниках, 12шт.

- коэффициент использования светового потока- зависит от геометрии помещения, коэффициента отражения потолка и стен, типа светильника.

Геометрия помещения учитывается индексом помещения

где a и b - длина и ширина помещения, м; h -расчетная высота (высота подвеса над расчетной поверхностью), м.п=(5*3)/3*8=0.83

Для освещения помещения отдела обработки информации используется светильники NC-2АС418С (Пассат)

Таблица 4. Коэффициенты использования светового потока

Заключение

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

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

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

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

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

В экономической части рассчитан срок окупаемости затрат на создание системы. Он составит 9 месяца.

Литература

[1] S. M. Smith and J. M. Brady. Susan: New approach to low-level image processing. Journal of computer vision, 23(1):45--78, May 1997.

[2] A. Broggi M. Bertozzi and S. Castelluccio. A real-time oriented system for vehicle detection. Journal of Systems Architecture, 1996.

[3] M. Watanabe S. K. Nayar and M. Noguchi. Real-time focus range sensor. Technical report, Department of Computer Science, Columbia University, New York, USA, June 1994. CUCS-028-94.

[4] J. Krieger U. Schonfeldt and T. Behnke. Electrical subsystem of the high resolution stereo camera for mars express.

[5] B. K. P. Horn. Shape from Shading: A Method for Obtaining the Shape of a Smooth Opaque Object from One View. PhD thesis, Massachusets Institute of technology, 1970.

[6] A. Pentland. Shape information from shading: a theory about human perception. In In Proceedings of International Conference on Computer Vision, pages 404--413, 1988.

[7] Ping-Sing Tsai and Mubarak Shah. Shape from shading using linear approximation. Image and Vision Computing, 12(8):487--498, October 1994.

[8] Ping-Sing Tsai and Mubarak Shah. Shape from shading with variable albedo. Optical Engineering, pages 121--1220, April 1998.

[9] Y. Xiong and S. Shafer. Depth from focusing and defocusing. #"justify">[10] Ф. П. Васильев. Численные методы решения экстремальных задач: Учебное пособие для вузов. - М.:Наука, ГРФМЛ, 1988.

[12] A. Pentland. A new sense for depth of field. In IEEE Transactions on PAMI, volume 4, pages 523--531, 1987.

[13] V. Roberto A. Fusiello and E. Trucco. Experiments with a new area-based stereo algorithm. In International Conference on Image Analysis and Processing, Florence, 1997.

[14] S.T. Bernard. A stochastic approach to stereo vision. In Proc. 5th National Conference AI., pages 676--680, Philadelphia, Pensylvania, August 1986.

[15] Sebastien Roy and Ingemar J. Cox. A maximum-flow formulation of the n-camera stereo correspondence problem. In IEEE. Proc. of Int. Conference on Computer Vision.

[16] J. E. Cryer Ping-Sing Tsai and Mubarak Shah. Integration of shape from shading and stereo. Pattern Recognition., 28(7):1033--1043, 1995.

[17] Takeo Kanade Mei Han. Scene reconstruction from multiple uncalibrated views. Technical report, The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, January 2000. CMU-RI-TR-00-09.

[18] Chetverikov D. and Zsolt Szabo. A simple and efficient algorithm for detection of high curvature points in planar curves. In Proc. 23rd Workshop of the Austrian Pattern Recognition Group, pages 175--184, 1999.

[19] Ramesh V., Bedekar A. S., Haralick R.M. and Zhang X. A bayesian corner Вetector: Theory and performance evaluation. Proceedings of 1994 ARPA Image Understanding Workshop, pages 703--715, 1994.

[20] C. J. Poelman and T. Kanade. A paraperspective factorization method for shape and motion recovery. Technical report, Shool of Computer Science, Carnegie Mellon University., Pittsburgh, PA 15213, December 1993. CMU-CS-93-219.

[21] J. Costeria and T. Kanade. A multi-body factorization method for motion analysis. Technical report, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, September 1994. CMU-CS-TR-94-220.

[22] C. Tomasi and T. Kanade. Shape and motion from image streams: a factorization method (orthographic method). Technical report, Shool of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, 1992.

[23] T. Morita and T. Kanade. A sequantual factorization method for recovering shape and motion from image streams. Proceedings of 1994 ARPA Image Understanding Workshop, 2:1177--1188, November 1994.

[24] Takeo Kanade Carlo Tomasi. Shape and motion from image streams: a factorization method - part 3. Detection and tracking of point features. Technical report, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, April 1991. CMU-CS-91-132.

[25] Н. В. Янова, Д.В. Юрин. Итеративный алгоритм восстановления трехмерных сцен, движения и фокусного расстояния камеры в перспективной проекции, основанный на факторизации матриц. - В сб. Труды конференции. 12-я Международная конференция по Компьютерной графике и Машинному зрению ГрафиКон2002 - стр. 123-129. Нижний Новгород, 2002.

[26] Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. - М.: МЦНМО, 2001.

[27]. Бобков Н.И., Голованова Т.В. «Охрана труда на ВЦ: методические указания к дипломному проектированию», М.: Изд-во МАИ, 1991. - 28 с.: ил.

[28]. ГОСТ 12.1.005-88 Общие санитарно-гигиенические требования к воздуху рабочей

[29]. ГОСТ 12.1.003-83. Шум. Общие требования безопасности

[30]. СанПиН 2.2.2.542-96 Требования к электромагнитным полям дисплея

[31]. ГОСТ Р 50923-96. Дисплеи.

[32]. ГОСТ 12.1.058-82 - Предельно допустимые уровни напряжения и тока прикосновения.

[33]. ГОСТ Р 52324-2005. Эргономические требования к работе с визуальными дисплеями, основанными на плоских панелях. Часть 2. Эргономические требования к дисплеям с плоскими панелями.

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

Больше работ по теме: