Обоснование необходимости разработки программного комплекса. Обзор методов восстановления трёхмерных сцен. Общая структура алгоритма восстановления 3D сцен и сравнительный анализ его методов. Сравнительный анализ приближений и оценка его результатов.
Аннотация к работе
В настоящей работе дан обзор литературы по тематике восстановления трехмерных сцен. Разработана система восстановления трехмерных сцен по последовательности цифровых изображений. Установлено, что наиболее слабым местом текущего состояния системы является требование большого количества снимков в серии. И осуществлено исследование погрешностей восстановления в зависимости от ряда изменяемых параметров.1.3.1 Алгоритмы Shape from Shading 1.3.2 Алгоритмы Shape from Focus and Defocusing 1.3.3 Алгоритмы Shape from Stereo 1.3.4 Алгоритмы Shape from Motion 2.2.1 Метод SIFT3.2 Структура программы восстановления трехмерных сцен 3.3 Совмещение результатов восстановления с модельюОбеспечение условий труда в отделе обработки изображенийДля осуществления этой цели должны быть выполнены следующие задачи: 1) реализовать метод детектирования и сопровождения характеристический точек на серии изображений, 2) по характеристическим точкам восстановить трехмерная сцену, 3) построить карту высот, 4) визуализировать получившуюся сцену. Пусть сцена освещается плоскопараллельным пучком в направлении. где ? - угол между направлением на источник излучения и осью z (зенитный угол, slant of the illuminant), ?-угол между проекцией направления на источник излучения от объекта на плоскость xy и осью x (азимутальный угол, tilt of the illuminant). Действительно, пусть расстояние до точки объекта равно z, а фокусное расстояние объектива - f, тогда изображение этой точки будет резким только в случае, когда выполняется соотношение тонкой линзы: где L - расстояние от линзы до плоскости изображения. Достижимое этими методами пространственное разрешение сцены, вдоль оси камеры (оси z), может быть оценено, исходя из выражения для глубины резкости [20]: Здесь r - радиус входного зрачка объектива, ? - диаметр кружка в плоскости изображения, которым представляется точка объекта, в цифровых системах изображение можно считать резким, если ? меньше размера пикселя фоточувствительной матрицы. Между найденными на двух изображениях точками устанавливается взаимно однозначное соответствие путем вычисления корреляции фрагментов изображений в окрестности этих точек или, в случае сегментации, путем сравнения интегральных характеристик сегментов.В среде 3d Max была построены модели для генерации синтетических данных: 1) Модель, представляющая собой куб, и движение камеры происходило по двум оси. 2) Модель, представляющая собой прямоугольный параллелепипед, движение камеры свободно происходило по трем осям. 3) Модель, представляющая собой две пирамиды и параллелепипед, разных высот. Первая модель представлена на рисунке 3.1 Вторая модель представлена на рисунке 3.3.Программный комплекс предназначен для первичной обработки фотографий, сделанных со спутника или другого летательного аппарата, вычисления необходимых для восстановления 3D - сцены характеристик, визуализации восстановленной сцены и движение камеры. Функциональные характеристики, на основе которых мы будем сравнивать разрабатываемую и аналогичную системы, приведены в таблице 4.1. Индекс технического уровня больше 1, следовательно, можно сделать вывод, что разработка программного комплекса восстановление сцены методом факторизации матриц целесообразна. При использовании технологии баз данных, общая трудоемкость программирования определяется согласно формуле (4.5): где: КОФ - коэффициент, учитывающий затраты на оформление эксплутационной документации по разработанному ПП (); Подставляя эти значения в формулу (4.5), получим значение общей трудоемкости: Общая трудоемкость создания алгоритмов и ПП распределяется по основным стадиям работ в соответствии со структурой трудовых затрат, отраженной выше в таблице 4.2.Для оценки экономической эффективности программного комплекса было выполнено следующее: 1) Определена целесообразность разработки подсистемы. Получено значение индекса технического уровня J=1.69. 2) Определена трудоемкость и затраты на создание подсистемы.Площадь - 5 кв.м на одного работающего, объем - 20 кубометра на одного работающего, что соответствует норме согласно САНПИН 2.2.2/2.4.1340-03 для пользователей ПЭВМ с ВДТ на базе плоских дискретных экранов (жидкокристаллические, плазменные). В помещении имеется окно размером 2м, через которое осуществляется естественное освещение. Вычислительная техника является источником существенных тепловыделений, что может привести к повышению температуры и снижению относительной влажности в помещении. В помещениях, где установлены компьютеры, должны соблюдаться определенные параметры микроклимата, соответствующие ГОСТ 12.1.005-88 [2]. Согласно ГОСТ 12.1.005-88 работа в офисе по энергозатратам относится к категории работ 1а. в соответствии с которой должны соблюдаться требования из таблиц 2.Анализ литературных данных показал, что для эффективного восстановления трехмерных сцен и построения карт высот требуется интеграция различных методов. Сделан вывод о том, что в качестве основы такой интеграции, наиболее перспективными представляются методы, базирующиеся на ф
План
Содержание
Введение
1. Общая часть
1.1 Обоснование необходимости разработки программного комплекса
1.2 Постановка задачи
1.3 Обзор методов восстановления трехмерных сцен
1.3.1 Алгоритмы Shape from Shading
1.3.2 Алгоритмы Shape from Focus and Defocusing
1.3.3 Алгоритмы Shape from Stereo
1.3.4 Алгоритмы Shape from Motion
1.3.5 Экзотические методы
1.4 Сравнительный анализ методов восстановления 3D сцен
2. Система трехмерного зрения
2.1 Общая структура алгоритма восстановление 3D сцен
2.2 Обнаружение характеристических точек
2.2.1 Метод SIFT
2.2.2 Метод SURF
2.3 Восстановление 3D сцен по последовательности цифровых изображений методом факторизации матриц
3.2 Структура программы восстановления трехмерных сцен
3.3 Совмещение результатов восстановления с моделью
3.4 Оценка точности восстановления
3.4.1 Первая синтетическая модель
3.4.2 Вторая синтетическая модель
3.4.3 Третья синтетическая модель
3.5 Тестирование на реальных изображениях. Экономическая часть
5. Обеспечение условий труда в отделе обработки изображений3.1 Формирование входных данных
3.1.1 Построение моделей для генерации синтетических данных
В среде 3d Max была построены модели для генерации синтетических данных: 1) Модель, представляющая собой куб, и движение камеры происходило по двум оси.
2) Модель, представляющая собой прямоугольный параллелепипед, движение камеры свободно происходило по трем осям.
3) Модель, представляющая собой две пирамиды и параллелепипед, разных высот.
Во всех трех случаях камера было ориентирована на объект.
Первая модель представлена на рисунке 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: 1. Файл с матрицей W, размера [2F,P], нормализованной.
2. Файл с вектором 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
EXY=0.673
3.4.2 Вторая синтетическая модель
Рис.3.4.3 Модель «Брусок»
Рис.3.4.4 Результат работы алгоритма
На рисунке представлен результат работы представленного алгоритма. Каждая точка соответствует столбцу из матрицы формы, визуализированная по технологии OPENGL. По формулам, представленным выше, вычисляем значения погрешности: ?=1.809
EZ=8.507
EXY=4.51
3.4.3 Третья синтетическая модель
Рис.3.4.5 Модель рельефа местности
На рисунке представлен результат работы представленного алгоритма. Каждая точка соответствует столбцу из матрицы формы, визуализированная по технологии OPENGL. По формулам, представленным выше, вычисляем значения погрешности:
Рис.3.4.6 Результат работы алгоритма
В этом случае найдем не точность восстановления всех точек, а только высот, так как это более важный параметр для составления карты высот.
Рис.3.4.7 Результат работы алгоритма. Вид сбоку.
Номер точки Высота эталонной модели Высота восстановленной модели Невязки
1 6 5.91 0,09(1,5%)
2 0 0.07 0,07
3 0 0.15 0,15
4 0 0.1 0,1
5 0 0.05 0,05
6 4 4.1 0,1(2,2%)
7 4 3.89 0,11(2,7%)
8 4 3.87 0,13(3,2%)
9 4 3.95 0,05(1,2%)
10 0 0.2 0,2
11 0 0.14 0,14
12 0 0.1 0,1
13 0 -0.01 0,01
14 2 1.95 0,05(2,5%)
15 0 0.01 0,01
16 0 0.04 0,04
17 0 -0.02 0,02
18 0 0.02 0,02
Суммарная погрешность определения высоты: 0.08.
3.5 Тестирование на реальных изображениях
Рис.3.5.1 Реальное изображение
Рис.3.5.2 Результат работы алгоритма
На серии изображении, первое из которой представлено на рисунке, взяты характеристические точки (на рисунке отмечены красным цветом). Результат работы алгоритма представлен на рисунках , , . Проведя анализ получившейся карты высот, можно сделать вывод, что дом, отмеченный на рисунке зеленым, имеет высоту 26,25 м. Дом, отмеченный синим, в два раза выше первого, высота примерно 51 м. Кран (на рисунке желтый овал) имеет высоту 44 метра.Линейный метод факторизации матриц показал достаточную точность, но оказался чувствительным ко многим факторам, таким как точка, на которую ориентируется камера, угол к нормали, под которым располагается камера, по которой происходит выравнивание. Выравнивание по сильно отклоненной камере приводит к тому, что в результате совмещения эталона и результата они оказываются повернутыми друг относительно друга.
Таким образом, представленные алгоритмы имеют перспективы применения при восстановлении рельефа по кадрам, снятым со спутника, но требуют особого внимания к параметрам и четкой проработки нюансов линейных алгоритмов.
4. Экономическая часть
4.1 Определение целесообразности разработки алгоритмов и программных продуктов
Темой дипломного проекта является создание программного комплекса восстановление 3D - сцены методом факторизации матриц. Программный комплекс предназначен для первичной обработки фотографий, сделанных со спутника или другого летательного аппарата, вычисления необходимых для восстановления 3D - сцены характеристик, визуализации восстановленной сцены и движение камеры. А также с помощью вычисленных параметров ориентировать летательных аппарат в пространстве. Основанием для разработки является необходимость ориентировать ЛА в зимний период, так как другие алгоритмы определения местоположения плохо работают в этот период.
Внедрение программного комплекса позволит значительно повысить точность ориентирования на местности в зимний период.
Функциональные характеристики Единица измерения Величина функциональных характеристик Значимость характеристик аналог новый вариант
Простота использования - 6 6 0,08
Точность - 5 8 0.3
Ресурсная и временная экономичность - 6 7 0.1
Надежность - 5 7 0.2
Сопровождаемость - 6 9 0.1
Защищенность - 7 6 0.12
Способность к взаимодействию - 6 9 0.1
Таблица 4.1 Функциональные характеристики алгоритмов и ПП
Для обоснования целесообразности разработки программного комплекса необходимо сравнить его с существующего аналогичного алгоритмического комплекса, который мы примем в качестве базового.
Функциональные характеристики, на основе которых мы будем сравнивать разрабатываемую и аналогичную системы, приведены в таблице 4.1.
Индекс технического уровня проектируемого изделия где , - уровень i-й функционально-технической характеристики соответственно нового (проектируемого) и базового (аналогичного) изделий;
- значимость i-й функционально-технической характеристики качества изделия;
n - количество рассматриваемых функционально-технических характеристик.
Рассчитаем индекс технического уровня: .
Программный комплекс восстановление сцены не является конечным продуктом, это часть алгоритмического обеспечения летательного аппарата. Следовательно, необходимо учесть долю влияния программного комплекса на конечный результат функционирования всей системы ориентирования. В этом случае индекс технического уровня рассчитывается согласно формуле: ,
где Кв - коэффициент влияния.
Примем Кв=0.25. Тогда индекс технического уровня равен: J=1.352*1.25=1.69.
Индекс технического уровня больше 1, следовательно, можно сделать вывод, что разработка программного комплекса восстановление сцены методом факторизации матриц целесообразна.
4.1 Определение трудоемкости и затрат на создание алгоритмов и ПП
Основой для определения затрат на создание алгоритмов и программных продуктов является показатель трудоемкости работ.
Структура затрат труда на создание подсистемы мониторинга конкурсного цикла представлена в таблице 4.2.
Таблица 4.2 Структура трудовых затрат по стадиям (этапам) НИР
№ п/п Наименование стадии (этапа) работ Доля работ на стадии (этапе) в общем объеме работ, %
1. Анализ предметной области и изучение средств разработки 5
r - фактор, учитывающий объем обрабатываемых данных;
? - фактор, учитывающий сложность алгоритма.
Примем следующие значения коэффициентов: КОФ=1.4;
КВН=1.1;
ТВВ =0.1;
ТР =0.6;
ТВЫВ =0.2;
МВВ =50;
МВЫВ =75;
q=2.5;
r=0.6;
? =0.5.
Подставляя эти значения в формулу (4.5), получим значение общей трудоемкости:
Общая трудоемкость создания алгоритмов и ПП распределяется по основным стадиям работ в соответствии со структурой трудовых затрат, отраженной выше в таблице 4.2. По каждой стадии работ определим ее исполнителей и рассчитаем показатели оплаты труда. Для этого приведем в таблице 4.3. перечень исполнителей и на основании должностных окладов рассчитаем часовые тарифные ставки.
Таблица 4.3. Перечень исполнителей
Категория исполнителей Число исполнителей Зарплата (руб./месяц) Часовые тарифные ставки, руб.
Начальник отдела 1 30000 170
Инженер 1 16000 91
Программист 1 16000 91
Часовые ставки разработчиков определены исходя из длительности рабочего дня - 8 часов и числа рабочих дней в месяце - 22. ?но= 30000/(22*8)=170 ?и= 16000/(22*8)=91 ?пр= 16000/(22*8)=91
Расчет заработной платы на основе трудоемкости соответствующих стадий работ (таблица 4.2) производится по следующей формуле:
где k - количество этапов;
Тэі - трудоемкость i-го этапа;
, -средняя часовая тарифная ставка оплаты работ i-го этапа.
Размер премии составляет 10% от заработной платы.
Результаты расчетов приведены в таблице 4.4.
Таблица 4.4 Расчет заработной платы
Стадия (этап) Трудоемкость, чел.-ч. Исполнители Часовая ставка, р. Средняя часовая ставка, р Заработная плата, р Заработная плата с учетом премии, р
Должность Числен-ность
1 81.25 Начальник отдела 1 170 130 10562.5 11618.75
Инженер 1 91
2 32.5 Инженер 1 91 91 2957.5 3253.25
Программист 1 91
3 81.25 Программист 1 91 91 7393.75 8133.125
4 113.75 Программист 1 91 91 10351.25 11386.375
5 65 Инженер 1 91 91 5915 6506.5
Программист 1 91
6 162.5 Программист 1 91 91 14787.5 16266.25
7 390 Программист 1 91 91 35490 39039
8 487.5 Программист 1 91 91 44362.5 48798.75
9 130 Инженер 1 91 91 11830 13013
Программист 1 91
10 81.25 Начальник отдела 1 170 117 9506.25 10456.875
Инженер 1 91
Программист 1 91
ИТОГО: 153156.25 168471.87
Затраты на создание ПП определяются по следующим статьям расходов: 1. Материалы;
2. Специальное оборудование;
3. Заработная плата основных исполнителей;
4. Отчисления на единый социальный налог основных исполнителей (26,2%);
5. Накладные расходы;
6. Прочие расходы.
При разработке ПП предполагается использовать: - Канцелярские товары стоимостью 1000 руб.
- Картридж для принтера стоимостью 2800 руб.;
- Флеш накопитель стоимостью 400 руб.
Общая сумма расходов на материалы составит: Lmat. = 4200 руб.
Затраты на специальное оборудование рассчитываются по формуле: , где - стоимость покупки оборудования;
- процент занятости оборудования (60%).
Данные по стоимости оборудования приведены в таблице 4.5.
Таблица 4.5
№ п/п Состав оборудования Количество Первоначальная стоимость Общая стоимость
1 ПЭВМ Pentium VI 3 20000 60000
2 Принтер 1 5000 5000
65000
В разработке ПП принимают участие начальник отдела, инженер и программист. Начальник отдела несет ответственность за автоматизацию отдела, инженер осуществляет контроль правильности разработки, а программист выполняет работу по алгоритмизации и программированию автоматизированной системы.
Затраты на зарплату основных исполнителей равны сумме затрат на каждой стадии и составляют ЗППП = 153156.25руб.
Расчет отчислений в ЕСН ведется по формуле:
где ЗПЗП - заработная плата основных исполнителей;
%СФ - ставка налога (26,2%).
Накладные расходы (на научно-техническую информацию) - 3000 руб.
Таблица 4.6 Структура затрат на создание ПП
№ п/п Наименование элементов и статей затрат Затраты, руб. Удельный вес, %
1 Материалы 4200 4
2 Специальное оборудование 7800 14
3 Заработная плата основных исполнителей 153156.25 60
4 Отчисления на единый социальный налог основных исполнителей 40126 17
5 Накладные расходы 3000
6 Прочие расходы 400 4
ИТОГО 208682,25 100
4.3 Оценка экономической эффективности
Для оценки экономической эффективности создаваемых алгоритмов и ПП, необходимо выяснить механизм их действия на экономические показатели и на основании этого вычислить годовой экономический эффект. Внедрение разрабатываемого программного комплекса приведет к повышению качества работы. Тогда показатель годового экономического эффекта будет вычисляться по формуле (4.14): , где: - индекс технического уровня нового варианта реализации системы;
, - годовые эксплутационные затраты в информационной системе по базовому и новому варианту.
Индекс технического уровня был вычислен в первом пункте работы (см. формулу 4.4.). 1,69
Годовые эксплуатационные затраты при выполнении работы информационной системой включают: · Затраты на оплату труда персонала, обслуживающего ИС ( );
· Отчисления на единый социальный налог ( );
· Страховые социальные расходы на производственный травматизм ( );
· Амортизационные отчисления ( );
· Затраты на электроэнергию для решения комплекса задач ( );
· Затраты на текущий ремонт ( );
· Затраты на технические носители информации ( ) ;
· Накладные расходы по эксплуатации ( ).
Далее представлены формулы для расчета всех составляющих годовых эксплутационных затрат.
1. Затраты на оплату труда персонала, обслуживающего ИС, вычисляются согласно формуле (4.15):
где: - коэффициент использования мощности ИС для решения комплекса задач с применением анализируемого ПП в соответствующем году;
где: - машинное время, используемое в течение года для реализации данного ПП, час.;
- годовой эффективный фонд времени работы вычислительной техники, час.;
- среднегодовая численность персонала j-ой профессиональной группы (чел.);
- месячный оклад персонала j-й профессиональной группы (руб.);
- коэффициент дополнительной заработной платы;
- коэффициент премиальных выплат.Для оценки экономической эффективности программного комплекса было выполнено следующее: 1) Определена целесообразность разработки подсистемы.
Получено значение индекса технического уровня J=1.69.
2) Определена трудоемкость и затраты на создание подсистемы.
Общая трудоемкость ТПР БДО=1625 чел.-час.
Материальные затраты составили 208682,25 руб.
3) Определены уровень экономической эффективности и срок окупаемости системы.
Уровень экономической эффективности составил ЕПП=0.86
Срок окупаемости затрат на создание системы составит 9 месяца.
На основании полученных значений показателей можно сделать вывод, что разработка программного комплекса целесообразна и программный комплекс является экономически эффективным.
5. Обеспечение условий труда в отделе обработки изображений