Министерство образования и науки РФ

Государственное образовательное учреждение

высшего профессионального образования

«Тверской государственный университет»

Факультет прикладной математики и кибернетики

Кафедра информационных технологий

МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ

Специальность: Информационные технологии в управлении и принятии решений

Направление: 010400Информационные технологии

Тема: «Построение трехмерной модели поверхности по изображению»

Тверь - 2011г.

Оглавление:

Введение………………………………………………………………………...3

1. Модель освещения …………………………………………………………..4

2.Получение исходных данных……………………………………………….6

3.Алгоритм……………………………………………………………………...9

3.1 Вычислениекарты нормалей……………………………………………..10

3.2 Вычислениекарты высот…………………………………………………14

4. Программа…………………………………………………………………..19

5. Тестирование………………………………………………………………..31

Заключение…………………………………………………………………….39

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

Введение

3D-сканер - устройство, анализирующее физический объект и на основе полученных данных создающее его 3D-модель (трехмерная модель). В современном мире существует несколько видов 3D-сканеров. Ниже приведены некоторые самые популярные из них [3]:

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

2. Бесконтактные 3D-сканеры

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

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

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

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

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

Это может быть полезно в спелеологии. С помощью такого 3D-сканера можно будет изучать поверхность стен пещеры. Замерять изменения рельефа в течение продолжительного периода времени.

Задача заключается в следующем. У нас есть некоторая неровная поверхность, например, из белого камня. И нам нужно узнать её рельеф, то есть построить 3D-модель поверхности. При этом окружающая среда не создает никакого освещения.

1. Модель освещения.

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

Освещенность произвольно взятой точки P, появившуюся из-за источника света в общем случае будем вычислять по уравнению Фонга [10]:

ambient = Ka,

diffuse = Kd * cos(N, L),

specular = Ks * pow(cos(R, V), Ns),

intensity = ambient + amp * (diffuse + specular).

Здесь использованы следующие обозначения:

На рисунке 1.1 показано расположение векторов для точки P объекта.

Рис. 1.1.

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

Данная модель является одновременно простой и приближенной к реальному миру, что делает её очень привлекательной для использования.

Цвет объекта в освещенной точке P определяется по следующей формуле:

С = intensity * Ca.

Где Ca – цвет освещенной точки при intensity = 1, назовем такой цвет абсолютным. Для описания цвета будем использовать аддитивную цветовую модель RGB (аббревиатура английских слов Red, Green, Blue — красный, зелёный, синий). Для этого цвет будем представлять в виде вектора из 3-х элементов {Red, Green, Blue}, где каждая составляющая обозначает интенсивность красного, зеленого и синего цветов соответственно. Интенсивность цвета будем измерять в диапазоне от 0 до 1.

2.Получение исходных данных

Для того чтобы построить карту высот, нам понадобятся:

1. 3 специальные фотографии поверхности объекта;

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

Для того чтобы сделать фотографии, нам понадобятся:

1. Фотоаппарат;

2. Параллельный источник света;

3. Устройство для измерения направления света относительно камеры (далее будем его называть сокращенно УИНС);

4. Темное помещение;

5. Исследуемая поверхность.

Теперь рассмотрим каждую деталь подробнее.

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

Рис. 2.1.

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

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

Рис 2.2.

Построим систему координат XYZ. Ось Z будет смотреть в камеру. Ось Y будет идти сверху вниз, а ось X будет идти слева направо относительно получаемого изображения в камере, как показано на рисунке 2.2. Далее для построения 3D модели я буду использовать именно эту систему координат. Заметим, что это левосторонняя система координат.

Для вычислений нам понадобиться вектор направления света относительно камеры, для этого будим использовать устройство для измерения направления света (УИНС) показанное на рисунке 2.3. Это устройство слегка напоминает солнечные часы.

Рис. 2.3.

Устройство состоит из белого квадрата и гвоздя (H) перпендикулярно вбитого в него. На белом квадрате нарисован отрезок (B), длина которого совпадает с длиной вбитого гвоздя, то есть H = B.

Далее, когда будет установлен свет и камера, нужно поместить это устройство перед камерой так, чтобы белый квадрат был параллелен плоскости камеры, а гвоздь смотрел в камеру. Затем сфотографировать УИНС.

На получившейся фотографии гвоздь должен быть точкой. Пусть B – длинна метки на фотографии, а S = {Sx, Sy} – двухмерный вектор тени. Тогда с помощью этого снимка мы можем определить направление света в системе координат XYZ.

Пусть вектор U = {0, 0, B} – гвоздь в масштабе фотографии, так как высота гвоздя H равна длине метки B по построению, W = {Sx, Sy, 0}.

L = U + W

Так как нам не интересна длина вектора L, нормируем его.

Из этого следует, что вектор L – вектор обратного направление света в системе координат XYZ.

Затем нужно сфотографировать саму поверхность.

3.Алгоритм

Исходные данные получены, теперь нужно их обработать. Фотографии можно представить в виде матрицы с высотой Height и шириной Width, в ячейках которой записаны трехмерные вектора {Red, Green, Blue}, где Red, Green и Blue – интенсивность красного, зеленого и синего цветов соответственно. Как мы уже договорились, интенсивность цвета измеряется в диапазоне от 0 до 1.

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

Gray = 0.11 * Blue + 0.30 * Red + 0.59 * Green;

Где Gray – полученный серый цвет в диапазоне от 0 до 1. Проделаем вычисления для каждой ячейки матрицы, в результате чего получим новую матрицу.

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

Gray = Pa * intensity

Где Pa – это абсолютный цвет в рассматриваемой ячейке, а intensity – суммарная освещенность.

Напомню, что суммарная освещенность пикселя вычисляется по формуле:

intensity = ambient + amp * (diffuse + specular);

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

intensity = Ka + amp * (Kd * cos(N, L) + Ks * pow(cos(R, V), Ns))

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

Пусть поверхность обладает малым Ks (коэффициент отражения), как правило, такая поверхность обладает большим Kd (коэффициент рассеяния). В идеале Ks стремиться к нулю, а Kd к единице.

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

intensity = amp * Kd * cos(N, L)

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

Gray = Pa * amp * Kd * cos(N, L)

Пусть A – интенсивность серого (Gray) цвета в ячейке матрицы фотографии. Тогда наше равенство можно записать в следующем виде

A = Pa * amp * Kd * cos(N, L)

Эта формула нам понадобиться для построения карты нормалей.

3.1. Вычисление карты нормалей

И так, поставим задачу. Нам дано 3 фотографии, которые мы конвертировали в серые тона. При этом все три сняты с одного ракурса, поэтому можно сопоставить эти изображения так, чтобы Pa (абсолютный цвет пикселя в серых тонах) и Kd были одинаковыми для всех, то есть если рассматривать соответствующие ячейки полученных матриц, то эти коэффициенты будут одинаковые.

Для каждой фотографии нам дан единичный вектор направления света. Пусть это будет L1, L2 и L3. Замечу, что для удобства он направлен от точки к источнику света. На рисунке 3.1.1 изображено сечение точки объекта в виде цилиндра. Как видно верхняя плоскость цилиндра находится под некоторым углом к плоскости камеры. Эта точка эквивалентна некоторой точке на фотографии. Тогда Pa – абсолютный цвет этого цилиндра. V – противоположный вектор направления камеры. N – нормаль к верхней плоскости цилиндра. Нам нужно найти вектор N.

Можно считать, что вектора Li единичные (где i = 1, 2, 3), не совпадают и не лежат все в одной плоскости, что следует из начальных условий.

Из выше упомянутых формул получаем, что цвет пикселя равен:

Ai = Pa * amp * Kd * cos(N, Li), для i = 1, 2, 3.

Где Ai интенсивность серого цвет на соответствующей фотографии.

Пусть dot(I, J) – скалярное произведение векторов I и J. Тогда справедливо следующее равенство:

dot(Li, N) = cos(Li,N), для i = 1, 2, 3. [3.1.1]

Запишем по-другому:

dot(Li, N) = Lix*Nx + Liy*Ny + Liz*Nz, для i = 1, 2, 3.

Любой трех мерный вектор V = {x, y, z} я буду представлять в виде {Vx, Vy, Vz}, где Vx – координата по оси OX, Vy – по оси OY, а Vz – по оси OZ.

Рис. 3.1.1.

Теперь выразим cos(N, Li):

cos(N, Li) = Ai / (Pa * amp * Kd), для i = 1, 2, 3. [3.1.2]

Подставляем [3.1.1] в [3.1.2] и получаем следующее:

dot(Li, N) = Ai / (Pa * amp * Kd), для i = 1, 2, 3. [3.1.3]

Составим матрицу M и вектор T:

, .

Равенство [3.1.3] запишем в векторном виде:

M*N=T / (Pa * amp * Kd),

Для упрощения введем коэффициент K:

К = Pa * amp * Kd

В результате получаем следующее равенство:

M *N =T / K. [3.1.4]

Так как вектора Li единичные, не совпадают и не лежат в одной плоскости, значит можно найти обратную матрицу M^-1. Тогда из формулы [3.1.4] N можно выразить следующим образом:

N = M^-1 *T / K

N * K = M^-1 *T

Так как нас интересует только направление вектора N. То мы можем опустить коэффициент K. А после расчетов нормировать вектор N. В идеальном случае вектор N будет единичным, то есть коэффициент K = 1, и в данных нет погрешности.

Данные расчеты нужно проделать для каждой ячейки матрицы. В результате у нас получиться карта нормалей.

Далее покажу геометрический смысл расчетов. Углы между нормалью и векторами Li дают коническую поверхность (где вектор Li является высотой). Возьмем сечение в виде окружности у каждого конуса, таким образом, чтобы расстояние от точки O было равно длине вектора Li (то есть единице). На рисунке 3.1.2 видно, что эти окружности пересекаются в одной точке.

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

Рис. 3.1.2.

Расчет погрешности происходит с помощью подстановки результата в исходное уравнение и вычитания исходных данных:

E = M * N - T

Где E – вектор погрешности. В идеале должен стремиться к 0.

Преимущество такого алгоритма в том, что он работает очень быстро. Достаточно посчитать один раз обратную матрицу, затем каждый вектор T трансформировать с помощью нее. Если по каким-то причинам "мощность" источника света будет разной на 3 фотографиях, то в данной формуле достаточно умножить результат на вектор {amp1, amp2, amp3} и опять нормировать. Алгоритм не зависит от абсолютного цвета поверхности и от такой характеристики поверхности как коэффициент рассеяния, то есть в каждой точке поверхности, данные коэффициенты могут быть разными.

Затем по карте нормалей строиться карта высот.

Рис. 3.1.3.

3.2. Вычисление карты высот

Возьмем сетку с точками на плоскости XY, как показано на рисунке 3.2.1. Пусть между соседними точками расстояние равно единице, то есть расстояние между точками вдоль оси X и вдоль оси Y равно единице. Для каждой точки укажем ее Z координату равную нулю. Размер сетки равен размеру карты нормалей полученной в предыдущей главе. Для каждой точки сетки укажем нормаль из карты нормалей. На рисунке 3.2.2 показан пример сечение сетки.

Рис. 3.2.1.

Рис. 3.2.2.

С помощью нормалей можно определить изменение высоты между соседними точками на сетке. Далее эту высоту будем называть «дельтой». Возьмем точку A. Пусть N – нормаль для этой точки. Пусть BC = Nz, AC = Nx, то есть возьмем проекции на ось OZ и ось OX. В результате получится прямоугольный треугольник ABC. Достроим прямоугольный треугольник UHA, таким образом, что HA = BC, UH = AC, как показано на рисунке 3.2.3. Пусть точка D лежит на одной прямой вместе сточками H, A и C. Расстояние между D и A равно единице.

Рис. 3.2.3.

Точки D и A находятся на нашей сетке. Нам нужно найти размер отрезка VD, который и является дельтой высот между точками D и A вдоль оси OX. Треугольник VDA перпендикулярный и подобен треугольнику UHA. Составим пропорцию:

VD / UH = DA / HA.

Выразим VD:

VD = DA * UH / HA = UH / HA = AC / BC.

Так как DA = 1 по построению. Пусть Dx это дельта высот между смежными точками вдоль оси OX, то ее можно выразить через N:

Dx = Nx / Nz.

Аналогично считаем Dy (дельту высот вдоль оси OY):

Dy = Ny / Nz.

Рассчитаем дельту высот для каждой точки сетки. Таким образом, что Dx точки P будет означать изменение высоты до правой точки, а Dy – изменение высоты до нижней точки.

Рассмотрим точки P1, P2, P3 и P4 как показано на рисунке 3.2.4.

Рис. 3.2.4.

Возьмем A, B, C и D как дельты высот между P1 и P2, P2 и P4, P1 и P3, P3 и P4 соответственно. В идеальных условиях должно выполняться следующее равенство:

A + B = C + D.

Из-за погрешности это равенство не выполняется. Поэтому для коррекции дельт высот я использую следующий итеративный метод.

Одна итерация состоит из двух проходов по сетке. Пусть точки P1, P2, P3 и P4 составляются ячейку сетки. Тогда первый проход корректирует все четные ячейки четной строки и нечетные ячейки для нечетной строки. Второй проход работает наоборот, он корректирует все нечетные ячейки для четной строки и четные ячейки для нечетной строки. На рисунке 3.2.5 заштрихованы ячейки для первого прохода.

Рис. 3.2.5.

Коррекция ячейки осуществляется следующим образом. Сначала рассчитываем коэффициент коррекции K:

U = A +B;

W = C + D;

K = (U - W) / 4;

Затем корректируем дельты:

A = A – K;

B = B – K;

C = C + K;

D = D + K;

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

Таким образом, с каждой итерацией дельты высот выравниваются. Заметим, что за одну итерацию взаимодействуют только две ячейки, то есть одна ячейки влияет на 4 граничные ячейки. За N итераций ячейка окажет влияние на ячейки в радиусе N. Поэтому рекомендуется делать max (Height, Width) итераций, где Height – высота фотографии, Width- ширина фотографии, max- функция взятия максимума от двух переменных.

Теперь надо вычислить координату Z для каждой точки. Координату Z будем называть высотой точки. Для этого возьмем нулевую точку, в которой высота будет равна нулю. Пусть она будет в верхнем левом углу. Тогда можно определить высоту смежных точек прибавляя дельту высот. Используя Dx, построим высоты для всех точек относительно нулевой вдоль оси OX. На рисунке 3.2.6 показано получившееся сечение высот. Затем, используя Dy, построим высоты для всех точек вдоль оси OY.

Рис. 3.2.6.

Для этого используем следующие формулы:

T[0,0].Z = 0;

T[x,0].Z = T[x-1,0].Z + T[x-1,0].Dx;

T[0,y].Z = T[0,y-1].Z + T[0,y-1].Dy;

Для всех x = 1,…,Width-1;

y = 1,…,Height-1

Где T – это сетка, а оператор [i,j] берет ячейку сетки с координатой i по оси OX и координатой j по оси OY. Оператор «.» берет элемент ячейки. Z – высота ячейки.

Затем, проходя точки построчно, вычислим для них высоту по следующей формуле:

A = T[x-1, y].Z + T[x-1, y].Dx;

B = T[x, y-1].Z + T[x, y-1].Dy;

T[x, y].Z = (A + B) / 2;

Для всех x = 1,…,Width-1;

y = 1,…,Height-1

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

4. Программа

Программа состоит из 5 модулей. Один исполняемый файл и четыре динамические библиотеки. Два модуля разработаны полностью мною, а оставшиеся три это бесплатные сторонние библиотеки. Программа создана в Microsoft Visual Studio 9 (интегрированная среда разработки программного обеспечения и ряд других инструментальных средств от компании Microsoft).

Рис. 4.1.

На рисунке 4.1. показано как модули взаимодействуют друг с другом. Теперь рассмотрим подробнее сторонние библиотеки:

«FreeImage.dll» - свободная библиотека для поддержки графических форматов, таких как PNG, BMP, JPEG, TIFF и других. Поддерживает многопоточность и платформы Win32, Linux и Mac OS X. Она написана на языке C++. Предоставляет единый интерфейс для работы с данными в фотографии. Также позволяет делать простейшие операции над изображениями, такие как обрезание, масштабирование, инвертирование и другие.

«FreeImageNET.dll» - свободная библиотека, работающая с библиотекой «FreeImage.dll». Предоставляет удобный интерфейс для языка C#. Используется в моей программе для двух целей. Первое это открытие большого разнообразия форматов файлов, в которые сохраняют фотографий. И второе это получение данных фотографии в едином формате.

«OpenGL.dll» - свободная библиотека, работающая с открытой графической библиотекой «OpenGL». Предоставляет удобный интерфейс для языка C#. «OpenGL» - спецификация, определяющая независимый от языка программирования кросс-платформенный программный интерфейс для написания приложений, использующих двумерную и трёхмерную компьютерную графику. С помощью этой библиотеки я рисую трех мерное изображение отсканированной поверхности.

Я разработал два модуля «ScannerLib.dll» и «SurfaceScanner.exe». Первый модуль это библиотека, в которой реализована вся математика построение карты высот по фотографиям. Второй модуль это исполняемый файл, который предоставляет интерфейс для пользователя, работает с библиотекой «ScannerLib.dll», а также с другими сторонними библиотеками. Теперь рассмотрим эти два модуля более подробно.

«ScannerLib.dll» - библиотека, написанная на языке C++ [5]. Изначально код приспособлен для компилирования и выполнения в операционной системе Windows, но легко конвертируется под другие операционные системы. Так как в этой библиотеке реализованы алгоритмы построение карты высот по фотографиям, её можно использовать в других приложениях или написать свою собственную оболочку для работы с ней.

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

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

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

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

На четвертом этапе строиться карта высот.

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

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

Карта высот представляется в виде матрицы. В каждой ячейке записана высота в диапазоне от 0 до 1. Вместе с картой высот предоставляется отношение высоты к стороне.

Рассмотрим классы этой библиотеки.

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

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

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

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

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

FScanner – это основной класс библиотеки. Содержит матрицу из FScannerCeil и вектор FScannerImage. В нем реализованы все алгоритмы построения карты высот из фотографий. При прохождении очередного этапа алгоритма данные в ячейках матрицы соответственно заполняются.

Контекстом сканера является указатель на объект FScanner в памяти библиотеки. В файле «WinMain.cpp» описан интерфейс работы со сканером. В файле «FColor.h» описаны алгоритмы конвертации цвета.

Рис. 4.2.

Второй модуль это исполняемый файл (программа). Называется «SurfaceScanner.exe». Она написана на языке C# [7]. Работает в операционной системе Windows и требует установленную платформу «.NET Framework» версии 2.0 или выше, которая, как правило, есть на всех современных машинах использующих Windows. Если потребуется, то код можно будет немного изменить и компилировать с помощью компилятора «Mono», что позволит запускать приложение на других операционных системах тоже. Программа является удобной графической оболочкой для работы с библиотекой «ScannerLib.dll». Интерфейс программы использует слова на английском языке, так как английский язык считается международным. При этом C# поддерживает словари, с помощью которых легко сделать реализацию программы на других языках.

На рисунке 4.2 показано главное окно приложения. Далее рассмотрим интерфейс программы.

Работой с проектом («Project»). Для удобной работы с фотографиями в программе нужно создавать проекты. В проекте хранятся настройки текущей конфигурации. Проект состоит из набора фотографий и направление света для каждой фотографии. В нем надо указать прямоугольник, в котором будут производиться расчеты.

Кнопка «New» создает новый проект. При этом сбрасываются все текущие настройки проекта.

Кнопка «Open» открывает окно, в котором надо выбрать файл проекта. Файл проекта это XML (eXtensible Markup Language – расширяемый язык разметки) документ, в котором указаны пути к фотографиям на вашем компьютере, направление света для каждой фотографии и прямоугольник, в котором будут производиться расчеты.

Кнопка «Save» открывает окно, в котором надо указать файл. В этот файл будет сохранен текущий проект.

Так как проект сохраняется в виде XML документа, то его можно редактировать с помощью любого текстового редактора.

Чтобы указать прямоугольник, нужно ввести 4 значение в поле «Rect: {X, Y, Width, Height}» через пробел. Числа должны быть целыми. Вводить их нужно в следующей последовательности: отступ с лева (координата X), отступ сверху (координата Y), ширина (Width), высота (Height). А затем нажать кнопку «Apply». Эти поля заполняются автоматически при добавлении новых растровых изображений (фотографий). При этом ширина и высота берется из ширины и высоты картинки, а отступ равен нулю.

Кнопка «Addimages» открывает окно выбора фотографий, которые будут добавлены в проект. Программа поддерживает 3 основных формата картинок: «*.bmp» - Bitmap Picture, «*.jpg» - Joint Photographic Experts Group , «*.png» - Portable Network Graphics. И другие форматы, которые поддерживает библиотека «FreeImage».

Редактирование данных.

Кнопка «Next» выбирает фотографии для редактирования. При нажатии на нее второй раз, выбирается следующая фотография. Выбор фотографий замкнут по кругу. Под фотографией есть меню под заголовком «Image». В нем есть информации о картинке и возможность редактировать направление света. «Path:» - путь к файлу, «Direct:» - направление света, «Id:» - уникальный идентификатор картинки.

Для выбранной фотографии можно настроить направление света. Для этого есть три способа:

1) Напрямую указать значения вектора. Для этого надо ввести координаты X, Y, Z в поля «DirectX», «DirectY» и «DirectZ» соответственно. Затем нажать кнопку «Apply», которая находиться под полями ввода. Данные считаются, полученный вектор нормируется и запишется в поле направление света.

2) Указать направление света в углах Эйлера, относительно камеры. Для этого надо ввести угол X и угол Y в градусах в поля «AngleX» и «Angle Y» соответственно. Затем нажать кнопку «Apply», которая находиться под полями ввода.

3) Указать направление света с помощью УИНС. Для этого надо ввести длину метки в поле «Magnitude:» и направление вектора тени (X,Y) в поле «VectorX:» и «VectorY:» соответственно. Затем нажать кнопку «Apply», которая находиться под полями ввода.

Чтобы измерить длину метки и направление вектора тени можно воспользоваться кнопкой «Meter».

Кнопка «Meter» открывает окно, в котором в масштабе 1 к 1 выводиться текущая картинка. В окне, с помощью правой кнопкой мыши можно перемещать картинку, то есть двигать ее. С помощью левой кнопкой мыши можно прочертить красный отрезок. Когда вы отпустите левую кнопку мыши, появится окно, например, как показано на рисунке 4.3.

Рис. 4.3.

В нем будут описаны: длина отрезка в пикселях («Magnitude:»), и 2 составляющие получившегося из отрезка вектора («VectorX:» и «VectorY») тоже в пикселях. Вам нужно будет найти на картинке метку, измерить ее длину. Затем найти на картинке тень и найти ее направление. Для нахождения направления тени нужно проводить линию с центра УИНС (гвоздя). Эти данные можно ввести в указанные поля выше и таким образом задать направление света.

Выполнение расчетов («Work»). Когда картинки подобраны, направление света определено для каждой из них и указан прямоугольник, в котором будут проходить расчеты, можно запускать вычислительный механизм. Здесь начинается работа с библиотекой «ScannerLib».

Кнопка «CreateCS» создает контекст сканера в динамической библиотеке. Затем добавляет туда все имеющиеся картинки в проекте, а взамен получает уникальные идентификаторы для каждой картинки. Соответствует первому этапу работы библиотеки «ScannerLib».

Кнопка «CreateNormal» создает карту нормалей. Для этого надо в поле «Ids:» указать уникальные идентификаторы картинок. Всего их должно быть 3 и картинки должны быть разные. Указываются они через пробел в целых числах, как правило, начиная с нуля. Затем по карте нормалей, строит дельты высот. Соответствует второму этапу работы библиотеки.

Кнопка «CorrectNormal» корректирует дельты высот. Количество итераций задается в поле «Times:». Это целое число большее нуля. Соответствует третьему этапу работы библиотеки. Так как этот процесс может быть долгим, то при его запуске появляется индикатор загрузки. Он показан на рисунке 4.4. Процесс коррекция дельт высот ресурсоемкий, поэтому он происходит в отдельном потоке, в результате чего нет эффекта зависания программы. Но любые действия с ней блокируются.

Рис. 4.4.

Кнопка «CreateHeight» создает карту высот по дельтам высот. Соответствует четвертому этапу работы библиотеки.

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

Вывод результатов («View»). Далее приведен список методов для представления результатов программы. Методы запускаются при нажатии на элемент списка «View».

Метод «Gray» открывает окно «View» с серым изображением сканируемой картинки. Для этого вам нужно выбрать текущую картинку, и убедиться что контекст сканера создан.

Окно «View» содержит меню и картинку. Картинка масштабируется в зависимости от размера окна. В меню есть 2 кнопки. Первая «Save» - позволяет сохранить текущую картинку в формате «*.bmp» (Bitmap Picture). Вторая «Exit» - закрывает текущее окно. После открытия, окна «View» не зависят от дальнейших действий пользователя. Например, можно построить карту нормалей в одном проекте, открыть ее карту, затем открыть другой проект, построить в нем карту нормалей и открыть карту уже из нового проекта. Таким образом, можно на глаз сравнивать полученную информацию.

Рис. 4.4.

Рис. 4.5.

Метод «NormalMap» открывает окно «View» с картой нормали (рисунок 4.4). Карта нормалей представляется в виде растрового изображения. Размер изображения равен размеру сетки нормалей полученной в результате выполнения алгоритма. Цвет пикселя по его нормали вычисляется по следующей формуле:

Red = (n.X+1) / 2;

Green = (n.Y+1) / 2;

Blue = (n.Z+1) / 2;

Где n – вектора нормали. Red, Green, Blue – составляющие цветовой модели RGB. Данное представление карты нормалей используется в большинстве современных приложений. Такое представление карты нормалей сложно понимать на глаз, поэтому я разработал альтернативный метод, который рассмотрю далее.

Метод «NormalDxy» открывает окно «View» с картой нормали (рисунок 4.5). Карта нормалей тоже представляется в виде растрового изображения, но алгоритм кодировки нормали в цвет пикселя другой. Для этого я использую только 2 координаты вектора нормали.

S = sqrt(n.X*n.X + n.Y*n.Y);

Angle = arccos(n.Y / S);

RGB = HSLtoRGB(H, S, 0.5);

Где sqrt – функция, вычисляющая квадратный корень. Arccos – функция, вычисляющая арксинус угла. H –тон. S – насыщенность. Angle – угол, направление нормали в плоскости OXY. HSLtoRGB – функция от 3 аргументов, преобразующая тон, насыщенность и светлоту в цвет из модели RGB. В данном случаи светлота равна 0.5. HSL (Hue, Saturation, Lightness) – цветовая модель, в которой цветовыми координатами являются тон, насыщенность и светлота. Тон определяется характером распределения излучения в спектре видимого света, причём, главным образом, положением пика излучения, а не его интенсивностью и характером распределения излучения в других областях спектра. Таким образом, на данной карте хорошо видно направление нормалей, а значит направление изменения рельефа. Серый пиксель означает, что нормаль смотрит на нас. А цветной пиксель означает, что в этой точке идет спуск и цвет указывает направление. Но в этом методе сложно определить силу наклона, для этого я добавил следующий метод.

Рис. 4.6.

Метод «NormalDz» открывает окно «View» с картой нормали (рисунок 4.6). Карта нормалей представляется в виде растрового изображения, где цвет отображает силу изменения поверхности. Если цвет черный, то поверхность гладкая. Чем более оранжевый цвет, тем более мощный наклон в этой точке. Так же с помощью данной карты нормалей можно найти точки, которые смотрят в противоположном направлении. Эти точки будут рисоваться синим цветом. Таких точек не должно быть, если они есть, значит что-то не так во входных данных.

Рис. 4.7.

Метод «Error» открывает окно «View» с картой погрешности. Карта погрешности представляется в виде растрового изображения. Серый цвет означает, что погрешности нет. Любое отклонение показывает нам проблемы с исходными данными.

Метод «Height» открывает окно «View» с картой высот (рисунок 4.7). Карта высот представляется в виде растрового изображения. Чем белее пиксель, тем точка к нам ближе, чем чернее пиксель, тем точка от нас дальше. Самая белая точка ближе всего к нам, самая черная точка – дальше всего от нас.

Метод «SaveRAW» открывает окно, в котором надо указать файл. В этот файл будет сохранена карта высот. Карта высот сохраняется в формате RAW 16 bit, то есть высота занимает в памяти 16 бит, и имеет значения от 0 до 65535. Вся высоты нормируются в этом диапазоне таким образом, что самая нижняя точка имеет высоту 0, а самая высокая имеет высоту 65535. Остальные высоты имеет высоту пропорциональную этим двум.

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

Имея эти данные можно с легкость построить карту высот в любом редакторе.

Рис. 4.8.

Метод «Height 3D» открывает окно «GLForm» с картой высот (рисунок 4.8) [1]. С помощью библиотеки «OpenGL» в этом окне рисуется трех мерная модель поверхности. Поверхность можно вращать, масштабировать и менять угол обзора. По карте высот строиться сетка треугольников, вершины которых это ячейки из карты высот. В каждой вершине треугольника определяется его нормаль. Нормаль определяется по двум соседним точкам. Она нужна чтобы освещение поверхности было корректным. Как и окно «View», это окно может существовать независимо от выбранного проекта.

5. Тестирование.

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

Рис. 5.1.

На рисунке показано трех мерное изображение поверхности, созданное с помощью 3ds Max. Как видно, оно имеет возвышенности и впадины. Данная поверхность рассеивала свет с коэффициентом 1 и отражала свет с коэффициентов 0. Был установлен параллельный источник света, интенсивностью 1. Камера была установлена перпендикулярно плоскости поверхности. Таким образом, были созданы идеальные условия для создания фотографий поверхности.

Рис. 5.2.

Рис. 5.3.

Рис. 5.4.

Затем меняя направление света, были сделаны 3 изображения (фотографии). Они показаны на рисунках 5.2, 5.3, 5.4. Сторона выпуклости, нормаль которой параллельна направлению света, более яркая.

Полученные данные передадим на вход программе. Результат можно увидеть на рисунках 4.4, 4.5, 4.6, 4.7, 4.8 из предыдущей главы. Как видно, результаты очень похожи с изначальной поверхностью.

Рис. 5.4.

Теперь раскрасим поверхность. Для этого возьмем текстуру, показанную на рисунке 5.4. Затем получим три новых изображения. Но результат не измениться. Так как было сказано ранее, цвет поверхности не влияет на результат.

Рис. 5.5.

Теперь возьмем более сложную поверхность. Она показана на рисунке 5.5. Как видно, здесь неровные края, а некоторые выпуклости пересекаются. Затем построим исходные данные для программы.

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

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

Рис. 5.6.

Рис. 5.7.

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

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

Для этого возьмем цилиндр. Он имеет круг в сечении. Нарисуем его в 3dsmax. Положим цилиндр на бок и сделаем три фотографии. На рисунке 5.8 показано то, что видит камера.

Рис. 5.8.

Рис. 5.9.

Занесем данные в сечении цилиндра в MSExcel. Затем сравним полученные данные с графиком окружности, который выглядит так:

Y = sqrt(1-X*X)

Где sqrt – функция извлечения квадратного корня.

Рис. 5.10.

На рисунке 5.9. представлено наложение графика окружности и графика высот в сечении получившейся модели цилиндра. При совмещении границ, графики совпали.

Разница между значениями представлена на рисунке 5.10. Как видно, погрешность составляет не больше чем 0.004.

Данная погрешность рассчитана в идеальных условиях. То есть в идеальных условиях получаемая поверхность практически идентичная изначальной. Погрешность появляется лишь из-за способа представления входных данных. Например, если взять изображение, в котором цвет хранится в диапазоне от 0 до 65535, то погрешность станет еще меньше. Для этого можно использовать формат TIFF для представления фотографий.

Теперь перейдем к примерам из жизни. Как было рассказана в предыдущих главах, я сделал устройство УИНС, источник параллельного света. Взял фотоаппарат и штатив. Для экспериментов мне дали камень из пещеры.

На рисунке 5.11 показан один из снимков сделанных мною. Для каждого снимка было определено направление света. На рисунке 5.12 показана фотографии устройства УИНС по которому было определено направление света.

Рис. 5.11.

Рис. 5.12.

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

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

Рис. 5.13.

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

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

Заключение

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

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

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

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

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

Зависимость погрешности от количества фотографий. Например, делать расчеты из 3 и более фотографий. А возможно построения карты нормалей, во время съемки объекта в режиме реального времени.

Все это увеличит точность и сделает данную технологию более полезной.

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

[1] Евченко А.И. OpenGL и DirectX: программирование графики. Для профессионалов. - СПб.: Питер, 2006.

[2] Кормен Т. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. – М. : Издательский дом «Вильямс», 2007.

[3]Либерти Дж. С++ за 21 день. – СПб.: Питер, 2003.

[4] Ошкин Д. «To be 3D or not to be…». 2007.

URL: http://www.cadmaster.ru/magazin/articles/cm_40_3d_scan.html

[5] Страуструп Б. Язык программирования С++, 3 издание. 2004 г.

[6]Фень Юань. Программирование графики для Windows. – СПб.: Питер, 2002.

[7] Шилдт Г. Полный справочник по C#. – М. : Издательский дом «Вильямс», 2004.

[8] Lyon F. «Phong Shading Reformulation for Hardware Renderer Simplification». 1993.

URL: http://dicklyon.com/tech/Graphics/Phong_TR-Lyon.pdf

[9] Fausto B., Holly E. «The 3D Model Acquisition Pipeline». 2002.

URL: http://www1.cs.columbia.edu/~allen/PHOTOPAPERS/pipeline.fausto.pdf

[10] Phong B. T. «Illumination for computer generated pictures». Communications of ACM 18 (1975).