Изображение трехмерных объектов.
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Введение
1.1 Существующие подходы
2.6 Удаление лишних ребер
3. Разработка программы
3.1 Формат DXF
3.2 Формат входных данных
3.3 Выходные данные
3.4 Выбор средств разработки
3.5 Диаграмма классов
Заключение
Используемые источники
Приложение
Введение
Восстановление 3D моделей по их 2D проекциям является важным объектом исследования уже долгое время. В основном свое применение эта область исследования нашла в инженерном деле. До того как построить некоторую деталь, создаются ее различные чертежи и проекции. Для того чтобы получить более широкое представление о том, что получится в итоге, создается 3D модель, даже если этот процесс занимает значительное количество времени.
Наибольший прорыв в области восстановления 3D моделей совершили Wesley и Markowsky в своих работах , предложив использовать каркасную модель как промежуточный шаг процесса восстановления. На сегодняшний день они являются одними из самых известных исследователей в этой области, а их подход используется при разработке практически любого нового алгоритма восстановления 3D моделей.
Процесс восстановления, который включает в себя взаимодействие пользователя с системой, чаще всего занимает значительное количество времени, вследствие чего разрабатываются различные алгоритмы для автоматического восстановления 3D моделей. Эти алгоритмы могут быть разделены на два типа в зависимости от существующих подходов. На данных момент существует два основных похода к восстановление 3D моделей: метод отображения границ и метод конструктивной сплошной геометрии. Метод отображения границ состоит в работе с линиями (ребрами) и вершинами, в свою очередь метод конструктивной сплошной геометрии основан на работе с геометрическими примитивами, такими как куб или шар.
Можно выделить две основные стадии восстановления 3D объектов по проекциям: создание псевдокаркасной модели объекта (pseudo-wireframe) и создание объекта (solid). Псевдокаркасная модель состоит из набора вершин и ребер, соединяющих эти вершины. Она может содержать лишнюю, но в то же время более полную информацию об описываемом объекте. В отличие от каркасной модели, она может включать в себя «лишние» ребра, которые принадлежат описывающим ее проекциям (рис. 1) Одна псевдокаркасная модель может описывать большое количество 3D объектов (рис.2).
Рисунок 1 Три проекции октаэдра
Рисунок 2 (a) - псевдокаркасная модель октаэдра, (b, c, d) - возможные solid объекты, этой модели
При анализе существующих приложений, предоставляющих возможность работы с 3D моделями, было выделено несколько самых популярных решений: Autodesk 3DS Max, Autodesk Autocad, Kompas-3D, Matlab, Blender (табл. 1).
Сравнительная таблица существующих решений
|
Необходимость специальных знаний |
Восстановление каркасной модели |
Автоматическое выполнение функции |
Лицензия |
||||
|
Приложения |
|||||||
Основным недостатком всех перечисленных систем за исключением последней является их платное распространение. Кроме этого Kompas-3D и Blender не имеют функционала восстановления 3D моделей из 2D проекций.
Autocad широко используется в сфере инженерного проектирования, однако реализованная в этой программе система восстановления 3D моделей из проекций основана на взаимодействии пользователя с системой.
3DS Max является практически самой распространенной и широко используемой системой для работы с трехмерной графикой. Программа предоставляет возможность восстанавливать 3D модель по проекциям, однако имеет довольно сложный интерфейс, а так же работает только в операционной системе Windows.
Matlab - кроссплатформенный пакет программ, который как и Autocad широко используется в сфере инженерного проектирования. Кроме этого Matlab является высокоуровневым интерпретируемым языком программирования, поэтому для работы необходимы соответствующие знания языка.
Таким образом очевидна актуальность разработки свободно распространяемой программы восстановления каркасных 3D объектов по трем 2D проекциям для операционной системы OS X, которая была бы доступна для работы пользователю без специальной подготовки. Выбор операционной системы обуславливается тем, что из перечисленных приложений ее поддерживают только Autocad, Blender и Matlab. А эти приложения либо не предоставляют необходимой функциональности, либо требуют дополнительных знаний для работы с ними, либо не распространяются свободно.
Целью данной выпускной квалификационной работы является разработка программы восстановления каркасных 3D объектов, состоящих из многогранников, по 2D ортогональным проекциям для операционной системы OS X.
Для достижения цели работы необходимо решить следующие задачи:
1. Изучить существующие форматы представления инженерных чертежей;
2. Рассмотреть основные подходы в восстановлении 3D объектов по 2D проекциям;
3. Изучить существующие алгоритмы восстановления трехмерной модели по трем двухмерным ортогональным проекциям;
4. Разработать программу, принимающую на вход три 2D проекции (вид сверху, вид спереди, вид сбоку) в одном из базовых CAD форматов (DXF) и восстанавливающую корректную каркасную 3D модель заданного объекта на выходе.
5. Протестировать работу приложения при помощи известных примеров.
программа трехмерный восстановление ортогональный
1. Обзор существующих подходов и программных решений
1.1 Существующие подходы
1.1.1 Метод отображения границ
Одни из первых исследований в области восстановления 3D моделей по проекциям были проведены профессором Masanori Idesawa в 1973 году и были представлены в его работе “A system to generate a solid figure from three views” . Idesawa предложил способы восстановления трехмерных вершин, ребер и лицевых поверхностей для многогранных объектов. Кроме того, так как некоторый набор вершин и ребер (каркасная модель) может описывать несколько объектов, он предложи способ, как удалять “призрачные ” ребра для того чтобы в итоге получать уникальный объект. Сам предложенный алгоритм состоял в следующих шагах.
На вход программе подаются три проекции, которые представлены наборами вершин и ребер. Все вершины представляются в виде их координат x, y, z и порядковых номеров этих вершин. Пусть описывает вершину, тогда описывает набор вершин, которые соединяюются с ребрами. Если три или больше вершин находятся на одной прямой, они объединяются в группу. описывает группы, к которым принадлежит.
Точки в трехмерном пространстве описываются как
где - координаты i-го элемента списка вершин,
с - некоторая координата,
Количество вершин в,
Количество вершин в,
Количество вершин в.
Пусть () представляется комбинацией i, j, k так что выполняются условия. Тогда () образуют матрицы трехмерных вершин. Эти операции применяются в (1) ко всем комбинациям i, j, k. Условия выполняются следующим образом:
Если, тогда
Если, тогда,
Если, тогда
где - положительной число, обозначающее погрешность.
Пусть и - две разные вершины в V. , используются для обозначения i, j, k в. является элементом относительно., используются для обозначения i, j, k в. является элементом относительно. Далее обозначает k-ый элемент, который является элементом относительно. обозначает k-ый элемент, который является элементом относительно. Похожие переменные принимаются для плоскостей YZ и XZ.
Таким образом результатом следующих булевых операций является определение того, соединяются ли вершины и ребром:
При восстановлении лицевых поверхностей используются следующие правила.
a) Существует k лицевых поверхностей, содержащих вершину пересечения k ребер;
b) Ребро представляет собой границу двух лицевых поверхностей, а в списках их границ вершины этого ребра идут в разном порядке;
c) Граница лицевой поверхности замкнута.
Для начала необходимо используя эти правила найти грань, которая может быть уникально определена. Затем нужно провести поиск всех ребер на границе грани и сохранить эти ребра в список и отсортировать, чтобы они удовлетворяли правилу (b). В конце нужно отсортировать вершины ребер против часовой стрелки для внешней лицевой поверхности и по часовой стрелке для внутренней поверхности грани.
Это был один из первых подходов к восстановлению 3D объектов. Впоследствии алгоритмы, в которых происходит работа с ребрами, получили общее название Boundary representation (Метод отображения границ). Модели в методе отображения границ создаются при помощи топологии и геометрических объектов. Основными топологическими единицами являются: faces (лицевые грани, или поверхности), edges (ребра) и vertices(вершины). Face - это ограниченная часть поверхности, относящаяся в некоторому ребру, ребро - сторона грани. В 1980 году George Markowky, профессор университета Мэна, и Michael A. Wesley из исследовательского института IBM Томаса Уотсона в своей работе “Fleshing out Wireframes” предложили использовать псевдокаркасную модель как промежуточную стадию процесса восстановления 3D объекта. Эта работа до сих пор является основополагающей для разработки новых алгоритмов в рамках метода отображения границ.
1.1.2 Конструктивная сплошная геометрия
Первые исследования в рамках второго подхода к восстановлению 3D объектов по 2D проекциям были произведены Aldefel в 1983 году . На входе в программу принимаются три проекции, из которых считываются данные о примитивах. Aldefel описывает возможные связи между примитивами. Одной из основных связей является CONTACT(n, m), которая обозначает что n и m связаны хотя бы одной общений точкой. Петля - замкнутая кривая без самопересечения.
Шаг 1: Установить все отношения между примитивами, которые связаны связью CONTACT.
Шаг 3: Вычисление объема всех “открытых” петель и выбор петли P с максимальным объемом. Также случайным образом выбирается проекция, которая будет считаться базовым силуэтом.
Шаг 4: Предположим что P описывает базовый силуэт одного или нескольких объектов. Для того чтобы доказать или опровергнуть это, необходимо выполнить следующий алгоритм:
· Случайным образом выбирается проекция и в ней ищутся все прямоугольные силуэты, которые совпадают с P. Если таких силуэтов не найдено, выйти из алгоритма.
· В оставшейся проекции найти для каждого прямоугольный силуэт, совпадающие как с, так и с P. Если таких силуэтов не найдено, выйти из алгоритма.
· Проанализировать P и найти все примитивы, которые требуют наличия линий в одной или обеих проекциях (базовая проекция не учитывается).
· Для каждой пары () найти полный список линий, которые описываются их примитивами. Если операция прошла успешно, итоговый объект представлен объединением и списка линий, полученных на этом шаге.
Шаг 5: “Увеличить” петлю P, создав все петли, которые включают в себя петли, прилежащие к P, если их еще не существует. Добавить их в список, отметить новые зависимости, отметить новые петли как “открытые”, а P пометить как “закрытую”.
Шаг 6: Спроецировать полученные объекты на плоскости, чтобы определить, описываются ли они входными проекциями. Если это так, то на этом работа алгоритма завершается, в противном случае перейти к шагу 3.
Описанный алгоритм работает только для объектов равномерной толщины. Подход носит название Конструктивная сплошная геометрия (Constructive solid geometry | CSG), и его основной концепцией является возможность математического описания любых сложных объектов при помощи более простых. Простейшими телами в CSG являются примитивы - тела простой формы, такие как куб, сфера, цилиндр, призма. Более сложные объекты создаются при помощи применения булевых операций (объединение, пересечение, разность) к некоторому набору примитивов.
1.1.3 Восстановление сплошных тел по шести проекциям
Впоследствии Shum предложил алгоритм, в котором для восстановления 3D модели используются шесть проекций . Алгоритм не обрабатывает пунктирные линии на проекциях. На проекциях допускаются прямые линии и круги, а также многогранные объекты с гранями, ортогональными хотя бы к одной оси координат, и ортогональные цилиндры.
В начале работы проекции делятся на три группы смежных проекций и располагаются соответствующим образом друг относительно друга. В процессе инкрементального выдавливания один из контуров становится образующим, а второй - направляющим. Из шести проекций образуются три пары. Для того чтобы образующий контур и направляющий не были параллельны, следующие операции выдавливания не выполняются:, и т.д. , где f-front, R-rear, t - top, b - bottom, r- right, l- left. Кроме того, существует только шесть комбинаций пар проекций для процесса инкрементального выдавливания:
Инкрементальное выдавливание делится на три шага: сегментация образующих контуров в сегментные контуры, выдавливание толщины в направляющей проекции, совершение выдавливания.
В процессе инкрементального выдавливания учитываются только образующие контуры, внешние линии образующей грани. В начале находятся все точки поворота в направляющем контуре, затем они проецируются перпендикулярно на общую грань проекции. Эти точки используются для разделения образующего контура не несколько сегментных контуров. Результатом является матрица SGS:
где - i-ый сегментный контур,
n - количество сегментных контуров для выдавливания.
Расстояния между точками поворота вдоль направления выдавливания определяют толщину выдавливания: , где m - количество инкрементальных выдавливаний.
В процессе самого выдавливания все сегментные контуры соединяются с толщинами выдавливания для того чтобы сформировать примитивные solid-объекты. Булевая операция объединения примитивных solid-объектов затем создаст выдавленный solid.
В итоге для каждой пары проекций объединение всех примитивов создаст два выдавленных solid-объекта. К ним применяется операция пересечения, чтобы сформировать solid пересечения. Пересечение пересеченных solid-объектов для всех пар проекций создаст итоговый solid.
Как конструктивная сплошная геометрия, так и метод отображения границ используются для создания итоговых 3D объектов. Как правило, восстановление псевдокаркасной модели является этапом работы алгоритмов обоих подходов. Однако задачей работы является восстановления каркасных моделей из 2D проекций. Основной вклад в разработку алгоритма восстановления каркасной модели внесли Markowsky и Wesley. При разработке последующих алгоритмов именно их подход всегда используется при восстановлении каркасных моделей объектов. Поэтому именно этот алгоритм был выбран для разработки приложения.
2. Описание используемых алгоритмов
2.1 Извлечение 2D ортографической информации
Каркасная модель объекта строится по фронтальной проекции (FV - front view), боковой проекции - виду справа (SV - side view) и верхней проекции - вид сверху (TV - top view), которые подаются на вход программе в формате систем автоматизированного проектирования (САПР) DXF. Файл каждой проекции необходимо проанализировать и загрузить информацию о хранящихся в нем геометрических компонентах - вершинах и ребрах - в матрицы:
где - координаты вершины - начала ребра,
Координаты вершины - конца ребра,
n - количество ребер в проекции.
Каждое ребро задается координатами двух вершин, координаты одной вершины могут встречаться в описании несколько раз по количеству сходящих в ней ребер.
2.2 Разметка 2D граней и вершин
Для того чтобы уменьшить количество параметров, определяющих ребра, каждая вершина отмечается порядковым номером. Номера вершин будут описывать ребра вместо координат этих вершин. Кроме того, сами ребра также отмечаются порядковыми номерами. Таким образом для каждой проекции создаются матрицы и для хранения информации о вершинах и ребрах соответственно:
где - порядковый номер i-ой вершины,
Координаты i-ой вершины, i =1,2,…,k
k - количество вершин проекции.
где - объект типа «ребро», i = 1,2,…,n
Каждый объект типа «ребро» содержит4 следующую информацию:
где - порядковый номер ребра,
Порядковый номер вершины, определяющей начало ребра,
Порядковый номер вершины, определяющей конец ребра,
Тип ребра,
n - количество ребер проекции.
Таким образом, матрица вершин содержит порядковые номера вершин проекции и их координаты, а матрица ребер - порядковые номера ребер и порядковые номера вершин, определяющих эти ребра. Тип ребер предлагается запоминать для обработки пунктирных линий на проекции, которые обычно используются для обозначения ребер, находящихся не на лицевых гранях проекции.
Координаты вершин проекций могут значительно отличаться, поэтому для упрощения работы с ними предлагается сдвинуть каждую проекцию таким образом, чтобы она находилась в первом квадранте и хотя бы одна точка лежала на оси X и хотя бы одна точка лежала на оси Y. Для этого необходимо найти минимальную координату и минимальную координату вершин в каждой проекции. После этого необходимо выполнить следующую операцию для матриц каждой проекции:
где fv - элемент i-ой строки и второго столбца матрицы,
fv - элемент i-ой строки и третьего столбца матрицы.
Впоследствии ребра проекции будут сравниваться с ребрами каркасной модели. Так как одно ребро проекции может описывать большое количество ребер в каркасной модели, ребра проекции должны быть максимальной длины, а не множеством коротких отрезков, лежащих на одной прямой.
Рисунок 3 Вид сбоку
Например, на рисунке 3 представлена проекция некоторого объекта. В конечной матрице проекции не должно существовать несколько ребер, лежащих на одной прямой и пересекающихся в вершинах, таких как bc, cd и fg, gc. Если они были обнаружены, то оба ребра, лежащие на одной прямой, удаляются из, и добавляются ребра bd и fc соответственно.
2.3 Объединение граней и вершин
Для последующей работы с данными о проекциях необходимо создать две новых матрицы и для верхней и боковой проекции соответственно. После этого нужно выполнить следующие операции над новыми матрицами:
где rtv - элемент i-ой строки и третьего столбца матрицы (координата y),
rtv - элемент i-ой строки и четвертого столбца матрицы (координата z),
rsv - элемент i-ой строки и второго столбца матрицы (координата x),
rsv - элемент i-ой 4строки и четвертого столбца матрицы (координата z).
Предполагается, что проекции, полученные в начале работы программы из файлов, созданы в едином масштабе. Для упрощения работы с каркасной моделью необходимо перенести данные о проекциях из матриц вершин в общую матрицу вершин и из матриц ребер в матрицу ребер.
Данные о проекциях расположены в и последовательно, поэтому теперь легко можно провести перпендикуляры из всех вершин: по z для фронтальной проекции, по y вверх для верхней проекции и по x вправо для боковой проекции, - и добавить новые вершины в, а новые ребра в.
На этом этапе работы алгоритма часть ребер никак не связана между собой, а также существуют повторяющиеся ребра, поэтому нужно удалить повторяющиеся вершины из и заменить порядковые номера этих вершин в на соответствующие не удаленные. Кроме того, нужно удалить повторяющиеся ребра из.
2.4 Нахождение точек пересечения ребер
Перпендикуляры, проведенные на предыдущем шаге все еще никак между собой не связны, поэтому необходимо найти точки их пересечения. Заранее не известно, какие именно ребра пересекаются; для каждого ребра проверяются все остальные, еще не проверенные ребра, на предмет их пересечения. В этой проверке можно выделить четыре случая: ребра параллельны / находятся на одной прямой / скрещиваются (лежат в параллельных плоскостях) / пересекаются. Проверку нужно провести только на нахождение ребер на одной прямой и на пересечение.
2.4.1 Определение нахождения ребер на одной прямой
Уравнение прямой, проходящей через две точки, в трехмерном пространстве выглядит следующим образом:
где - координаты первой точки,
Координаты второй точки.
Так как проверяемые ребра (восстановленные перпендикуляры) параллельны хотя бы одной оси координат, в этой формуле будет происходить деление на ноль, во избежание этого нужно воспользоваться правилом пропорции:
Допустим, сравнивается ребро AB и ребро CD, если подставить в (2) вместо координаты вершины A, вместо координаты вершины B, а вместо поочередно координаты вершин C и D, и оба выражения будут выполняться, то ребра лежат на одной прямой.
В этом случае ребра могут не пересекаются. Если же ребра ab и cd пересекаются могут возникнуть пять ситуаций:
· ребра пересекаются в одной из существующих вершин (рис. 4);
Рисунок 4
· ребра совпадают, в этом случае второе ребро удаляется из;
· одна из вершин одного ребра находится на другом ребре, к примеру вершины ребер ab и cd расположены в следующем порядке: a c b d, в этом случае ребра ab и cd удаляются из, а новые ребра ac, cb и bd добавляются в матрицу (рис. 5);
Рисунок 5
· одно ребро находится внутри другого, но вершины не совпадают, в этом случае меньшее ребро удаляется из. Например на рис. 6 нужно удалить ребро ab;
Рисунок 6
· одно ребро находится внутри другого, и одна из вершин ребра ab совпадает с одной из вершин ребра cd, к примеру если a = c и вершины расположены в порядке: a=c, d, b (рис. 7), ребро ab удаляется из, а новое ребро db добавляется в матрицу.
Рисунок 7
2.4.2 Определение пересечения ребер
Две прямые AB и CD:
проходящие через точки, и, соответственно, пересекаются, если выполняется условие:
и если ранг этой матрицы равен двум. Иными словами для прямых AB и CD нужно найти такие коэффициенты u и v, что система из трех уравнений (3) имеет решение:
Определитель матрицы 3х3 считается по формуле (4):
Ранг матрицы равен количеству ненулевых строк в матрице ступенчатого вида. Для того чтобы привести матрицу к ступенчатому виду можно воспользоваться методом Гаусса, для этого введем элементарные преобразования матрицы:
I. Перестановка двух столбцов или строк матрицы;
II. Умножение элементов одной строки или столбца на одно и то же число, отличное от нуля;
III. Прибавление к элементами одной строки или столбца соответствующих элементов другой строки или столбца, умноженных на одно и то же число.
Для того чтобы привести матрицу к ступенчатому виду методом Гаусса необходимо выполнить следующие шаги:
1. Выбрать в первом столбце элемент, отличный от нуля (ведущий элемент). Если строка с ведущим элементов (ведущая строка) не первая, переставить ее на место первой строки (преобразование I типа). Если в первом столбце нет ведущего элемента, то продолжить поиск в оставшейся части матрицы. Нужно закончить преобразования если исключены все столбцы.
2. Разделить все элементы ведущей строки на ведущий элемент. Если строка последняя, то преобразования заканчиваются.
3. К каждой строке ниже ведущей строки прибавить ведущую строку, умноженное на такое число, что все элементы ниже ведущего элемента становятся равны нулю.
4. Исключив ведущую строку и ведущий столбец, перейти к пункту 1 для оставшейся части матрицы.
Если определитель равен нулю и ранг матрицы равен двум, систему уравнений (2) можно решить при помощи формул Крамера . Для решения системы из трех уравнений с двумя неизвестными достаточно двух уравнений, поэтому решение, использующее первое и второе уравнение будет иметь вид:
Если плоскость, в которой находятся пересекающиеся ребра, перпендикулярна плоскости XY, то D будет равен нулю. Аналогично плоскость пересечения может быть перпендикулярна плоскостям XZ и YZ. Поэтому для нахождения точки пересечения выбираем пару уравнений, где D не равен нулю. Таким образом, решение для первого и третьего уравнений:
Решение для второго и третьего уравнений:
В случае пересечения ребер возможны четыре случая:
· Прямые, определенные вершинами ребер пересекаются, но сами ребра не пересекаются;
· Ребра пересекаются в одной из их вершин. Если ребро ab пересекает cd в точке a (рис. 8), то cd удаляется из, а новые ребра ca и ad добавляются в список;
Рисунок 8
· Ребра пересекаются в новой вершине. Если ребро ab пересекает cd в некоторой точке m (рис. 9), ab и cd удаляются из, а новые ребра am, mb, cm, md добавляются в список;
Рисунок 9
· Ребра пересекаются двумя вершинами (рис. 10).
Рисунок 10
Таким образом в каркасную модель добавлены все ребра, ортогональные ко всем трем проекциям. Следующим шагом является добавление ребер, не ортогональных ни к одной проекции.
2.5 Создание не ортогональных ребер
Для того чтобы создать все возможные ребра не ортогональные ни к одной плоскости проекции, необходимо спроецировать вершины на каждую из плоскостей XY, XZ и YZ. Под проецированием понимается приравнивание к нулю одной из координат трехмерной вершины, Таким образом при проецировании на плоскость XY координата z приравнивается к нулю, при проецировании на XZ координата y приравнивается к нулю, при проецировании на YZ координата x приравнивается к нулю.
После этого для каждой вершины каркасной модели перебираются вершины соответствующей проекции (для XY, для XZ, для YZ). Для каждой i-ой вершины проекции выделяются координаты вершин, соответствующие плоскости, на которую модель спроецирована, которые соединяются ребрами с i-ой вершиной (соседних вершин). В каркасной модели создаются ребра, соединяющие i-ую вершину и все вершины с выделенными двухмерными координатами.
На рисунке 11 приведен пример проекций некоторого объекта (a,b,c) и результат, который был достигнут на момент выполнения шага 2.4.2.
Рисунок 11 (a) - фронтальная проекция, (b) - вид сверху, (c) - вид сбоку, (d) - текущая каркасная модель
На текущем этапе алгоритма необходимо восстановить реба FL и CO. Из модели видно, что для этого необходимо спроецировать модель на плоскость YZ (боковая проекция). В этом случае координаты y и z каждой вершины сравниваются с соответствующими координатами матрицы. К примеру вершина С по этим координатам равна вершине D проекции. Для вершины D находятся все вершины, которые соединяются ребрами с D. На проекции это вершины E, N, M. После этого в каркасной модели находятся все вершины, чьи координаты y и z (в данном случае) равны координатам y и z вершин E, N или M. Из проверяемой вершины C проводятся все возможные ребра к найденным вершинам, если таких ребер еще не существует. Таким образом в каркасную модель добавятся ребра CA, CE, CK, CM, CH, CO, CN (рис. 12).
Рисунок 12
Таким образом, необходимое ребро CO, которое не ортогональной ни одной проекции, было добавлено в список ребер. Все остальные ребра, скорее всего, не принадлежат всем проекциям и будут удалены на следующем шаге алгоритма. Такие операции производятся для каждой вершины модели, а так же для каждой проекции.
2.6 Удаление лишних ребер
На данном этапе выполнения алгоритма в псевдокаркасной модели существует большое количество ребер, не принадлежащих проекциям. Для того чтобы их удалить, необходимо спроецировать вершины на каждую из плоскостей XY, XZ и YZ и сравнить ребра) с, и соответственно. Если спроецированное ребро модели совпадает с одним из ребер соответствующей проекции, но не выходит за его пределы, оно остается в списке, в противном случае - удаляется.
В дополнение к алгоритму построения псевдокаркасной модели объекта по трем 2D проекциям, предложенному Markowsky и Wesley , в работе предлагается алгоритм обработки пунктирных линий, который можно использовать для несимметричных относительно центра проекций.
Изначально предполагается что объект, чья псевдокаркасная модель создается в ходе алгоритма, симметричен относительно центра, поскольку известны только три его проекции. На предыдущем шаге могли быть созданы ребра, которые принадлежат проекциям, но в итоговую каркасную модель не входят.
Рассмотрим возможность восстановления каркасных моделей несимметричных объектов. Предположим, что фигура симметрична только относительно двух плоскостей XY и YZ. Для каждого пунктирного ребра проекции создается список ребер из, которые совпадают с пунктирным ребром. Если удалять ребра на ближайшей и дальней гранях каждой плоскости, то может возникнуть ситуация, при которой на дальней грани удалятся нужные ребра. Поэтому предлагается для фронтальной проекции из получившихся списков удалять ребро с наименьшей координатой z. Для боковой проекции удалять ребро с наибольшей координатой x. Для верхней проекции удалять ребро с наибольшей координатой y.
Таким образом, из трех двумерных проекций в результате работы алгоритма получается псевдокаркасная модель с допущением, что на дальних гранях объекта могут сформироваться ребра, принадлежащие проекциям, но, возможно, не принадлежащие объекту. Пользователю предоставляется возможность интерактивного удаления лишних ребер.
3. Разработка программы
3.1 Формат DXF
DXF TM - открытый формат файлов для обмена данными между приложениями систем автоматизированного проектирования (САПР). Был создан для Autocad фирмой Autodesk и поддерживается практически всеми системами САПР на платформе PC. Наряду с форматом DWG является одним из самых распространенных форматов файлов для обмена графической информацией, однако DWG является закрытым форматом, тогда как для DXF Autodesk предоставляется бесплатную спецификацию . DXF формат содержит все информацию об изображении в виде маркированных данных. Это означает что различные данные обозначаются целыми числами.
Формат DXF состоит из семи следующих разделов (см. Приложение А рисунок 3):
· HEADER - содержит основную информацию о чертеже. К примеру, здесь может храниться название программы, в которой был создал файл, версия программы, максимальные и минимальные координаты в чертеже (см. Приложение А рисунок 4).
· CLASSES - содержит информацию об объявленных в приложении экземплярах классов, которые используются в разделах BLOCKS, ENTITIES и OBJECTS.
· TABLES - хранит массивы данных, такие как таблица слоев, таблица стилей, таблица типов линий (см. Приложение А рисунок 5).
· BLOCKS - хранит данные о примитивах, объединенных в блоки. Блок имеет уникальный идентификатор и название и может использоваться в разделе ENTITIES (см. Приложение А рисунок 7).
· ENTITIES - хранит данные о примитивах (см. Приложение А рисунок 6).
· OBJECTS - содержит данные о не графических объектах, которые используются в приложениях, написанных на AutoLISP и ObjectARX.
· THUMBNAILIMAGE - хранит изображение того, что находится на чертеже.
3.2 Формат входных данных
Входные данные представлены в виде файлов трех проекций: вид спереди, вид сверху, вид сбоку, - в формате DXF. Программе необходимо знать, какой проекцией является каждый из файлов, поэтому проекции должны иметь название “FV.dxf” или “fv.dxf”, “TV.dxf” или “tv.dxf”, “SV.dxf” или “sv.dxf” соответственно. Проекции должны быть описаны линиями. Важно отметить, что линии, находящиеся за пределами грани проекции должны быть обязательно описаны при помощи линии типа пунктир (рис. 13).
Рисунок 13 Проекции буквы «Т». (a) -вид сверху, (b) -вид спереди, (c) -вид сбоку
Программа распознает пунктирные линии, которые имеют подстроку «DASHED» в своем названии. Все остальные типы линий распознаются как обычные.
3.3 Выходные данные
В результате работы программы формируется каркасная 3D модель объекта, описанного тремя проекциями, полученными на входе в программу (рис. 14).
Рисунок 14 Результат работы программы. (a) - вид сверху, (b) - вид спереди, (c) - вид сбоку, (d) -получившаяся псевдокаркасная модель.
Так как итогом работы описанного алгоритма является псевдокаркасная модель, пользователь может сам выбрать и удалить лишние по его мнению ребра. В связи с этим реализованы функции “Отменить” и “Повторить” при помощи класса “NSUndoManager”.
3.4 Выбор средств разработки
В работе предлагается разработать приложение, работающее под операционной системой OS X. Ввиду этого в качестве языка разработки выбран объектно-ориентированный язык Objective C и среда разработки Xcode. Для работы с файлами формата DXF выбран фреймворк DXFReader . При анализе файла он возвращает массив примитивов, содержащихся в файле, и их данных. Для вывода проекций и каркасной модели на экран используются методы фреймворка “QuartzCore”.
3.5 Диаграмма классов
Рисунок 15 Диаграмма классов разрабатываемого приложения восстановления каркасных 3D объектов по 2D проекциям
Основным классом программы является “Document”, в нем создается объект класса “Wireframe” и вызывается метод “wire”, в котором происходит создание каркасной модели. Кроме того в “Document” происходит обработка работы пользовательского интерфейса. Все данные о проекциях и каркасной модели хранятся в экземпляре класса “Model”. Классы группы “Views” являются классами, обрабатывающими вывод на экран проекций и самой каркасной модели. “View1” выводит фронтальную проекцию, “View2” выводит верхнюю проекцию, “View3” выводит боковую проекцию, “ShowView” обрабатывает выводит на экран каркасной модели при помощи методов, которые будут описаны в следующем разделе. Класса группы “Operations” содержат классовые методы для работы с вершинами (класс “Vertices”) и ребрами (класс “Edges”), а также некоторые математические операции (класс “AAMath”).
3.6 Вывод на экран каркасной модели
При описании фигуры для вывода ее на экран используется матрица вершин A размером .
где - координаты x, y, z i-ой вершины,
n - количество вершин.
Четвертый элемент строки является однородной координатой k, и для однозначности принимается k=1. В ходе преобразований этот элемент изменяется и корректируется. Таким образом в однородных координатах каждая вершина представляется в виде
Для того чтобы в ходе преобразований получить реальные координаты, необходимо делить каждую строку матрицы A на четвертый элемент этой строки.
В программе реализованы такие преобразования трехмерной машинной графики как
· Повороты вокруг осей координат;
· Масштабирование по осям;
· Сдвиг вдоль осей координат.
Для выполнения соответствующего преобразования необходимо умножить матрицу A матрицу соответствующего преобразования.
Поворот вокруг оси Ox на угол представлен матрицей:
Поворот вокруг оси Oy на угол представлен матрицей:
Масштабирование по осям представлено матрицей:
где d - коэффициент масштабирования.
Сдвиг вдоль осей координат представлен матрицей:
где dx - коэффициент сдвига по оси Ox,
dy - коэффициент сдвига по оси Oy,
dz - коэффициент сдвига по оси Oz.
Стоит отметить, что после процесса восстановления фигура находится полностью в первом квадранте плоскости XZ (рис. 16).
Рисунок 16 Пример результата работы программы до вывода на экран
Для удобства работы с фигуры необходимо сдвинуть ее центр в начало координат, для этого нужно умножить матрицу A на матрицу,
На экран выводят только координаты x и y матрицы A. Так как в NSView центр координат находится в левой нижней точке окна, при выводе на экран для нормального отображения фигуры к каждой координате x прибавляется переменннная drawX, а к каждой координате y прибавляется переменная drawY. Изначально drawX равен половине ширины окна “ShowView”, а drawY равен половине высоты окна “ShowView”. Эти значения изменяются при изменении положения центра координат.
Заключение
В работе были решены следующие задачи:
· Изучены существующие форматы представления инженерных чертежей;
· Изучены существующие алгоритмы восстановления трехмерной каркасной модели по трем двухмерным ортогональным проекциям;
· Предложен алгоритм удаления лишних ребер на описанных проекциями лицевых поверхностях, обозначенных на проекциях пунктирными линиями;
· Разработано приложение, принимающее на вход три 2D проекции (вид сверху, вид спереди, вид сбоку) формата DXF и восстанавливающее корректную каркасную 3D модель заданного объекта на выходе.
Результатом работы является программа восстановления каркасных 3D объектов из 2D проекций для операционной системы OS X. В программе реализовано автоматическое создание псевдокаркасной модели, необходимую каркасную модель пользователь может получить при помощи удаления ненужных по его мнению ребер в полученной псевдокаркасной модели.
В дальнейшем планируется изучить алгоритмы восстановления solid объектов из 2D проекций и добавить этот функционал в программу. Также возможно изучение процесса восстановления трехмерных объектов по набору фотографий.
Используемые источники
1. Aldefeld, B. (1983). On automatic recognition of 3D structures from 2D representations. Computer Aided Design, 15(2), 59-72.
2. З?эзek, A. & Gьlesin, M. (2004). Reconstruction of 3D models from 2D orthographic views using solid extrusion and revolution. Journal of Materials Processing technology, 152, 291-298.
3. DXF Format . (n.d.). Retrieved February 10,2014, from http://www.autodesk.com/techpubs/autocad/acad2000/dxf/dxf_format.htm
4. Furferi, R., Governi, L., Palai, M., & Volpe, Y. (2011). 3D Model Retrieval from mechanical drawings analysis. International Journal of mechanics, 5(2), 91-99.
5. Governi, L. & Furferi, R. & Palai, M. & Volpe, Y. (2013). 3D geometry reconstruction from orthographic views: A method based on 3D image processing and data flitting. Computers in industry, 64, 1290-1300.
6. Idesawa, M. (1973). A system to generate a solid figure from three views. Bull JSME, 16, 216-225.
7. Lee, H. & Han, S. (2005). Reconstruction of 3D interacting solids of revolution from 2D orthographic views. Computer-Aided Design, 37, 1388-1398.
8. Markowsky, G. & Wesley, M. (1980). Fleshing out wireframes. IBM Journal of Research and Development, 24 (5), 582-597.
9. Shum, S. S. P., Lau, W. S., Yuen, M. M. F., & Yu, K. M. (1997). Solid reconstruction from orthographic opaque views using incremental extrusion. Computer Graphics, 26(6), 787-800.
10. SourceForge.net: DXFReader - Project Web Hosting - Open Source Software. (2009, February 22). Retrieved January 10, 2014, from http://dxfreader.sourceforge.net
11. Wesley, M.A. & Markowsky, G. (1981). Fleshing out projections, IBM Journal of Research and Development, 25 (6), 934-954.
12. Мальцев А. И. Основы линейной алгебры. -- Изд. 3-е, перераб., М.: «Наука», 1970. -- 400 c.
Приложение
Рисунок 1 Структура DXF файла
Рисунок 2 Структура секции HEADER в DXF файле
Рисунок 3 Структура секции TABLES в DXF файле
Рисунок 4 Структура секции ENTITIES в DXF файле
Рисунок. Структура секции BLOCKS в DXF файле
Размещено на Allbest.ru
...Подобные документы
Современные алгоритмы машинной графики. Алгоритмы построения изображения. Глобальная модель освещения Уиттеда. Выбор и обоснование языка и среды программирования. Вспомогательные классы свойств трехмерных объектов. Условия применения программы.
курсовая работа , добавлен 24.06.2009
Автоматизация проектно-конструкторских работ и применение программы AutoCAD для выполнения трехмерных чертежей. Возможность преобразования и редактирования моделей, получения плоских изображений деталей и адаптация системы к требованиям пользователя.
курсовая работа , добавлен 13.10.2010
Типология свойств объекта, его связей и моделей представления информации. Изображение предметной области в виде логических и физических моделей. Требования к системам баз данных. Достоинства трехуровневой архитектуры. Процесс идентификации объектов.
лекция , добавлен 19.08.2013
Основы программирования на языке VB.NET. Область применения трехмерных изображений. Форматы хранения пакетов инженерной графики. Преимущества трехмерного моделирования. Разработка программы по вращению трехмерных изображений на языках VB.NET и VRML.
курсовая работа , добавлен 11.03.2013
Определение понятия трехмерной компьютерной графики. Особенности создания 3D-объектов при помощи булевых операций, редактируемых поверхностей, на основе примитивов. Моделирование трехмерных объектов при помощи программного пакета Autodesk 3ds Max.
дипломная работа , добавлен 13.04.2014
Составление методического пособия пользователя для восстановления утраченной информации своими силами. Способы простого автоматического восстановления с помощью специализированных утилит и ручное восстановление памяти при помощи использования редакторов.
дипломная работа , добавлен 27.04.2010
Основные компоненты среды Delphi, используемые в программе для сжатия и восстановления файлов. Код программы, разбивка массива на промежутки. Проверка определенных элементов кодовых слов. Поиск кодовых слов в остатке. Результаты тестирования приложения.
курсовая работа , добавлен 19.12.2010
Исследование возможности применения 3D studio Max в процессе изучения дисциплины "Дооборудование и тюнинг автомобиля". Создание модели по проекциям куба. Использование новых ИТ на различных занятиях, ее преимущества перед стандартной системой обучения.
статья , добавлен 16.04.2012
Общий анализ технологического процесса, реализуемого агрегатом, целей и условий его ведения. Разработка структурной схемы объекта управления. Идентификация моделей каналов преобразования координатных воздействий. Реализация моделей и их адекватность.
курсовая работа , добавлен 29.09.2013
Этапы развития компьютерной графики. Общее понятие про трехмерную графику. Организация процесса построения проекции. Проволочная модель, отсечение нелицевых граней, вращение. Программная реализация построения изображения. Построение сложных моделей.
Задача восстановления трехмерной формы объекта или координат в пространстве широко распространена. Например, она постоянно возникает при использовании чертежей, являющихся ортографическими проекциями.
Рис. 3-48 Результат проецирования в примере 3-29.
Хорошо известен метод восстановления трехмерного объекта или координаты по двум или более представленным на чертеже видам (ортографическим проекциям). Метод же восстановления трехмерного координатного вектора по двум перспективным проекциям, например по двум фотографиям, не столь хорошо известен. Конечно, если метод пригоден для перспективных проекций, то он подходит также и для более простых ортографических проекций и фактически для всех рассмотренных в предыдущих разделах проекций. Как будет показано ниже, при наличии определенной дополнительной информации не надо иметь точную информацию о самом преобразовании.
Прежде чем рассматривать задачу в общем виде, обратимся к специальному случаю восстановления трехмерных координат точки по двум или более ортографическим проекциям. На рис. 3-49 представлены ортографические виды (проекции) спереди, справа и сверху. При определении трехмерных координат точки вид спереди дает значения координат и , вид справа - и , вид сверху - и , т.е.
.
Заметим, что для каждой координаты мы получаем два значения. В математике в подобном случае говорят, что на задачу наложены избыточные условия. Ведь надо найти только три независимые величины, тогда как известны шесть определяющих их условий (уравнений). Для любой измерительной системы в общем случае , , . Так как неизвестно, какое из значений верно, то наиболее разумным решением будет усреднить их.
Вернувшись теперь к восстановлению трехмерных координат по перспективным проекциям, напомним, что обобщенное перспективное преобразование представляется в виде матриц размера . Таким образом,
.
Рис. 3-49 Восстановление трехмерной формы по ортографическим проекциям.
Результаты могут быть спроецированы на двумерную плоскость, скажем на плоскость , с помощью
.
Объединение двух матриц дает
.
Полезно записать это преобразование в виде
. (3-71)
Заметим, что и - это координаты перспективной проекции на плоскость . Могли бы также использоваться проекции на плоскости или . Расписав в явном виде матричное уравнение (3-71), получим
Подставим значение из (3-72с) в уравнения (3-72а) и (3-72b):
По предложению Сазерленда эту пару уравнений можно рассматривать тремя разными способами. В первом предполагаются известными , , , . Тогда у нас есть два уравнения с двумя неизвестными и . Таким образом, эти уравнения можно использовать для непосредственного вычисления координат перспективной проекции. Именно этот подход применялся во всех предыдущих рассуждениях в данной главе.
При другом подходе полагаются известными , , . В этом случае получается два уравнения от трех неизвестных пространственных координат , , . Эту систему уравнений невозможно решить. Однако, если известны две перспективные проекции, скажем две фотографии, тогда уравнения (3-73) можно записать для обеих проекций. В результате получим
где верхние индексы 1 и 2 обозначают первую и вторую перспективные проекции. Заметим, что преобразования и не обязательно должны быть одинаковыми. Эти уравнения можно переписать в матричной форме
,
Уравнения (3-73) представляют четыре уравнения от трех неизвестных пространственных координат , , . Для нахождения решения матрица не может быть инвертирована, так как она не квадратная. Снова, как и в случае восстановления трехмерных координат по ортографическим проекциям, условия избыточны и, таким образом, задача может быть решена только в некотором усредненном или наиболее подходящем смысле.
Усредненное решение можно вычислить, вспомнив, что матрица, умноженная на свою транспонированную матрицу, является квадратной. Таким образом, умножив обе части уравнения (3-74) на , получим
.
Вычислив обратную матрицу , получим усредненное решение для , т.е.
. (3-75)
Если решения для нет, то наложенные условия избыточны и не существует единственного решения, обеспечивающего наименьшую ошибку. Этот метод иллюстрируется на примере.
|
Пример 3-30 Трехмерное восстановление Предположим, что обмеренные координаты
точки на одной перспективной проекции равны
Отметим, что последние две строки и должны быть переписаны, чтобы учесть тот факт, что является проецированием на плоскость . Тогда матрица
Решив
уравнение, получим |
и 
на другой. Первое преобразование
перспективной проекции является результатом поворота на вокруг оси и последующего
переноса на 2 единицы в отрицательном направлении оси . Точка проекции находится в
, а
результат проецируется на плоскость . Это действительно является
двуточечной перспективной проекцией. Второе преобразование является
результатом поворотов на вокруг каждой из осей , . Точка проекции
находится в ,
а результат проецируется на плоскость , т.е. является трехточечной
перспективной проекцией. Таким образом преобразования и 
и 
.
, т.е. центр единичного куба.В качестве третьего подхода к рассмотрению уравнений (3-73) отметим, что если известны координаты нескольких точек в объектном пространстве и на перспективной проекции, то можно найти элементы преобразования . Эти элементы впоследствии можно использовать для нахождения местоположения неизвестных точек, используя описанный выше второй метод. Чтобы показать это, перепишем (3-73) в виде. Таким образом, находится преобразование, породившее перспективную проекцию, например фотографию. Заметим, что в этом случае не требовалось никакой предварительной информации о преобразовании. Если, например, это были фотографии, то не требовалось знать ни о местоположении, ни об ориентации фотокамеры. В матричном виде система уравнений записывается в таком виде:
, (3-77)
где нижние индексы соответствуют точкам с известным местоположением. Уравнения (3-77) записываются в более компактном виде:
Так как уравнения (3-77) являются однородными уравнениями, то они содержат произвольный масштабный коэффициент. Следовательно, можно приравнять единице и нормализовать результирующее преобразование. Система сводится к 11 уравнениям или 5 1/2 точки. Если преобразование нормализовано, то последний столбец в переносится в правую часть и решается неоднородное матричное уравнение. Ниже приводится пример.
Подстановка этих результатов в матрицу дает
.
Процесс вывода трехмерной графической информации более сложный, чем соответствующий двумерный процесс. В двумерном случае просто задается окно в двумерном мировом координатном пространстве и поля вывода на двумерной видовой поверхности. В общем случае объекты, описанные в мировых координатах, отсекаются по границе видимого объема, а после этого преобразуются в поле вывода для дисплея. Сложность, характерная для трехмерного случая, возникает потому, что видовая поверхность не имеет третьего измерения.
Несоответствие между пространственными объектами и плоскими изображениями устраняется путем введения проекций, которые отображают трехмерные объекты на двумерной проекционной картинной плоскости (КП).
Рис. 3.44. Процесс вывода трехмерной графической информации
В процессе вывода трехмерной графической информации (рис. 3 .44.) мы задаем видимый объем (ВО) в мировом пространстве, проекцию на КП и поле вывода на видовой поверхности. В общем случае объекты, определенные в трехмерном мировом пространстве, отсекаются по границам трехмерного видимого объема и после этого проецируются. То, что попадает в пределы окна, которое само является проекцией видимого объема на картинную плоскость, затем преобразуется (отображается) в поле вывода и отображается на графическом устройстве.
Рис. 3.45. Картинная плоскость и определяющие ее параметры
Картинная плоскость определяется (рис. 3 .45.) некоторой точкой на плоскости, которую будем называть опорной точкой (ОТ) инормалью к картинной плоскости (НКП). КП может произвольным образом располагаться относительно проецируемых объектов, заданных в мировых координатах. Она может пересекать их, проходить впереди или позади объектов.
Для того чтобы задать окно, нам необходима система координат на КП, которую назовем системой координат UV . Началом ее служит ОТ. Направление осиV на КП определяетвектор вертикали (ВВ): проекция ВВ на КП совпадает с осьюV .
ОТ и два направления вектора НКП и ВВ определяются в правосторонней мировой системе координат. Имея на КП систему UV , можем задать минимальное и максимальное значенияU иV , определяющие окно (рис. 3 .46.).
Рис. 3.46. Окно вывода на картинной плоскости
Отметим, что окно не обязательно должно быть симметрично относительно ОТ.
Видимый объем частично определяется окном и ограничивает ту часть мирового пространства, которая будет спроецирована.
В случае центральной проекции ВО определяется также центром проекции (рис. 3 .47.). Этот параметр задается в мировых координатах относительно ОТ. ВО представляет собой неограниченную в одну сторону пирамиду, вершина которой находится в центре проекции, а боковые стороны проходят через окно.
Рис. 3.47. Видимый объем для центральной проекции
Точки, лежащие позади центра проекции, не включаются в ВО и, следовательно, не будут проецироваться.
Рис. 3.48. Видимый объем параллельной проекции
В случае параллельных проекций ВО определяется также направлением проецирования (рис. 3 .48.). Он представляет собой неограниченный параллелепипед, стороны которого параллельны направлению проецирования.
В общем случае направление проецирования может не совпадать с НКП.
В случае ортографических параллельных проекций (но не косоугольных) боковые стороны ВО перпендикулярны КП.
В некоторых случаях может потребоваться сделать ВО конечным (рис. 3 .49.- 3 .51.). Для этого задаются ПСП (передняя секущая плоскость) и ЗСП (задняя секущая плоскость).
Рис. 3.49. Усеченный ВО для центральной проекции
Рис. 3.50. Усеченный ВО для ортографической параллельной проекции
Рис. 3.51. Усеченный ВО для косоугольной параллельной проекции.
Нормаль НКП направлена относительно направления проецирования и также является нормалью к ПСП и ЗСП.
Здравствуйте, дорогие читатели.
В настоящее время в различных областях деятельности, в таких как производство, медицина, компьютерная графика, робототехника и техническое зрение активно используется трехмерное моделирование и прототипирование объектов реального мира. В связи с этим все более актуальным становится разработка 3d сканеров и камер, которые создают 3d модель регистрируемого объекта.
Немного истории
В 1999 году компания 3DVSystems, мировой лидер в области трехмерных видеоизображений, разработала видеокамеру ZCam c уникальной технологией измерения расстояния до объектов в режиме реального времени. Эта технология позволяла воспринимать и обрабатывать трехмерное изображение, будучи направленной на объект всего лишь с одной его стороны. В 2009 году Microsoft выкупил активы 3DVSystems и на базе ZCam начал разрабатываться контроллер для игровой приставки Xbox. В 2010 году Microsoft анонсировал всеми любимый Kinect - игровой контроллер, позволяющий управлять игрой своим телом. Компания Artec-group производит 3d-сканеры для оцифровывания формы объекта в режиме реального времени. Такие сканеры могут применяться в медицине, производстве и тюнинге автомобилей и создании спецэффектов в кино и видео играх.Рис.1. Пример использования алгоритмов в видео играх
0.Параллаксный метод регистрации 3d объектов
Системы регистрации трехмерных объектов могут быть построены на различных принципах, одним из которых является стереоскопический принцип. Стереоскопическая система состоит из двух камер, регистрирующих объект с разных, но не слишком сильно отличающихся ракурсов. На полученных изображениях определяются соответствующие точки (стереоотождествление). Затем, зная внутренние параметры камер стереопары, а также их взаимное расположение, можно определить трехмерные координаты точек объекта методом триангуляции . Несмотря на успехи последних лет, в решении данной задачи остается ряд вопросов, связанных с принципиальными ограничениями данного метода, в частности, со стереоотождествлением точек объектов, не обладающих ярко выраженной текстурой или имеющих большие нетекстурированные (однородные) области .
Рис.2. Пример стерео пары
Чтобы преодолеть эти недостатки стереоскопического метода, можно заменить одну из камер стереопары проектором и получить устройство регистрации трехмерных объектов, основанное на активном параллаксном принципе. Схема системы, построенной на данном принципе, показана на рисунке: на объект проецируется некоторая картина (структурированная подсветка), ее искажения, вызванные формой объекта, регистрируются камерой .
Рис.3. Принципиальная схема работы системы, построенной на активном параллаксном методе
1.Активный параллаксный метод регистрации трехмерных объектов
В настоящее время разработано множество различных вариантов картин для использования в системах структурированной подсветки, представляющих собой как серии изменяющихся картин (картины с временным мультиплексированием), так и неизменные картины с использованием различных вариантов цветовой кодировки . Временная кодировка использует последовательность черно-белых картин, как показано на рис.4, а. Идея этого метода состоит в том, чтобы кодировать положение пикселя на матрице проектора набором интенсивностей в последовательности проецируемых картин. Набор картин, показанный на рис. 2, а, использует «битовое» кодирование: набор двухцветных (черно-белых) картин представляет собой двоичный код, определяющий «номер» пикселя в строке. Помимо «битового» кодирования также используются другие методы двоичного кодирования (сдвиг бинарной картины, код Грея и другие ). Такой способ не чувствителен к цвету поверхности, позволяет кодировать каждый пиксель на матрице проектора, однако требует статичности положения объектаиз-за большого количества используемых картин.
Рис. 4. Картины, используемые для создания структурированной подсветки: а - с временным кодированием, б – с цветовым кодированием
Цветовая кодировка, пример которой показан на рис.4, б, использует только одну картину. Положение каждого пикселя однозначно кодируется значением цвета данного пикселя и нескольких его «соседей». При создании картины с цветовой кодировкой обычно стремятся получить минимальный размер окрестности (количество «соседей») пикселя, требуемый для однозначного восстановления, и минимальное количество различных цветов (для повышения надежности определения каждого цвета). Такими свойствами обладают M-последовательности или последовательности де Брёйна (de Brujin) . Преимуществом такого метода является возможность восстановления формы объекта всего лишь по одной картине, и как следствие, возможность регистрирования движущихся объектов. К недостаткам следует отнести чувствительность метода декодирования цветной картины к структуре регистрируемой поверхности и ее цвету.
2. Алгоритмы обработки зарегистрированных изображений
Используемая картина подсветки, показанная на рис.5, представляет собой 128 узких вертикальных полос шести цветов (трех основных – R, G, B, и трех дополнительных – C, M, Y), разделенных промежутками черного цвета. Последовательность цветов получена при помощи генератора М-последовательностей, сочетание из каждых 3 соседних полос встречается только один раз.Рис. 5. Используемая последовательность цветов
Алгоритм обработки изображений решает две основные задачи:
1. Детекцию полос на изображении и определение положения центральной линии для каждой полосы (выделение полос);
2. Определение цвета для каждого выделенного участка полосы (классификация по цветам).
3. Выделение центров полос
Алгоритмы выделения полос для различных картин подсветки с цветовым кодированием можно разделить на два типа: с выделением краев (edges) и с выделением пиков (peaks). Используемая картина подсветки содержит промежутки черного цвета и требует использования алгоритма второго типа. Для выделения полос на изображении можно использовать прямой метод поиска локальных максимумов, метод пересечения нулевой линии второй производной (детектор лаплассиана гауссиана (LoG)) или метод Канни (Canny) . Зарегистрированное изображение содержит три цветовых канала (R,G,B), поэтому для применения вышеупомянутых методов требуется или преобразование к одному каналу с использованием его для обработки, или объединение результатов выделения полос по нескольким каналам. После первичного выделения центров полос данными методами обычно производится субпиксельное уточнение координат максимумов или с использованием интерполяции параболой , или определением центра тяжести по нормализованным значениям в окрестности.В различных работах предложены следующие методы решения данной задачи: в работе использовался метод Канни (Canny) по яркостной составляющей (Y) после преобразования в цветовое пространство YCbCr; в работе использовался прямой метод поиска локальных максимумов вдоль линий сканирования по трем цветовым каналам R,G,B с последующим объединением результатов на этапе субпиксельного уточнения; в работе выделение центров полос осуществлялось по второй производной значения цвета (V) после преобразования в цветовое пространство HSV.
На рис.6 представлено изображение, зарегистрированное в темной комнате. В работе были рассмотрены реализации алгоритмов поиска максимумов и определения их цвета, работающие для изображения произведенного без сторонней засветки. Однако, при добавлении внешнего источника света, алгоритмы показывали неустойчивую работу.
Рис.6. Изображение, зарегистрированное в темной комнате без засветки
Для выбора оптимального цветового преобразования для выделения максимумов был проведен анализ сечений изображений, зарегистрированных в ходе проведения экспериментов, и оценена пригодность использования различных величин с точки зрения выбора надежных пороговых значений алгоритма. В работе были показаны значения различных величин: цветовых каналов R,G и B, среднего арифметического по трем данным каналам, яркостной составляющей (Y) после преобразования в YCbCr и значения цвета (V) после преобразования в HSV в сечении изображения объекта, перпендикулярном направлению проецируемых полос. Также, в работе был сделан вывод, что при использовании линейной комбинации цветов (R+G+B) чистые цвета сильно подавляются, и могут быть пропущены. По результатам анализа можно сделать вывод, что наиболее стабильную детекцию центров полос можно получить, используя значение цвета V.
Рис. 7. Значения различных величин в сечении изображения объекта, перпендикулярном направлению проецируемых полос.
В ходе выполнения работы в среде MatLab были реализованы алгоритмы выделения центров полос по значению цвета V и среднеквадратичного из каналов RGB с использованием прямого метода поиска локальных максимумов и метода, подобного методу Канни. При реализации прямого метода поиска максимумов были заданы два пороговых значения: – минимальное абсолютное значение в предполагаемом максимуме, – минимальное значение разности значений в предполагаемом максимуме и его «соседях». При реализации метода Канни на этапе немаксимального подавления вместо значений модуля градиента в первом случае используются непосредственно сами значения V, как в работе , а во втором случае-среднеквадратичное из RGB. Перед преобразованием изображения в цветовое пространство HSV к изображению был применен сглаживающий гауссов фильтр; для субпиксельного уточнения координат максимумов использовалась интерполяция параболой по строке изображения.
Для оценки результатов работы двух методов по различным цветовым каналам использовались изображения, зарегистрированные в ходе проведения экспериментов на стенде, использованном в работе . Характеристики использованных устройств и условий регистраций в ходе эксперимента подробно описаны в конце данной статьи.
Количественная оценка зависимости результатов детекции полос от используемого цветового канала (R+G+B, Y или V) производилась по изображениям объекта в виде гладкой белой плоскости («Плоскость») и гладкого белого объекта (гипсовый бюст Ленина, «Бюст»). Сравнивалось количество точек центров полос, обнаруженных алгоритмом при работе по рассматриваемому цветовому каналу изображения при подсветке картиной с цветными полосами, и количество точек центров полос, обнаруженных тем же алгоритмом при работе по каналу яркости Y изображения при подсветке картиной с белыми полосами. Значения порогов для каждого цветового канала были выбрано как, где максимальное значение для данного цветового канала в пределах рассматриваемого фрагмента изображения, – единая для всех каналов фиксированная величина. Результаты подтвердили сделанный ранее вывод о предпочтительном использовании значения цвета V.
Для оценки зависимости результатов детекции полос от используемого метода (прямой метод поиска локальных максимумов или метод Канни) использовались те же изображения. Количественная оценка в данном случае возможна только для объекта «Плоскость», поскольку для него можно определить «истинное» количество точек центров полос как произведение количества полос на количество строк изображения. Для обоих методов при детекции полос на плоском объекте по V был получен одинаковый максимальный результат. Для объекта «Бюст» возможно проведение качественной оценки, результаты детекции полос приведены на рис. 8. Видно, что метод Канни позволяет детектировать больше точек локальных максимумов при том же пороговом значении за счет использования «сильного» и «слабого» порогов, однако это преимущество незначительно. Основным преимуществом метода Канни является то, что выбранные точки уже связаны в фрагменты полос, что можно использовать далее на этапах классификации и декодирования для повышения общей надежности работы алгоритма.
Рис. 8. Результаты работы алгоритмов выделения полос: (а) прямой метод, (б) метод Канни
4 Классификация выделенных полос по цвету. Кластеризация
На данном этапе решается задача классификации выделенных точек-центров полос по цвету на 7 типов: 6 типов, соответствующим 6 используемым цветам и «неклассифицированные» точки, которые нельзя надежно соотнести ни с одним из используемых цветов. Для решения данной задачи можно применить ряд различных методов, среди которых можно выделить две группы: методы с фиксированными порогами и адаптивные методы.Рассмотрим возможные варианты решения этой задачи в различных цветовых пространствах: YCbCr и HSV, представленные в литературе. Классификация производится пороговым методом, пороговые значения выбраны заранее. Использование алгоритма кластеризации позволяет адаптировать алгоритм к изменению внешней освещенности и повысить надежность классификации при работе с цветными объектами.Рассмотрим алгоритмы кластеризации в цветовых пространствах YCbCr (по разностным компонентам Cb и Cr) и HSV (по насыщенности S и тону Н).
Алгоритм кластеризации состоит из двух повторяющихся действий:
Отнести каждую точку к кластеру, расстояние до центральной точки которого наименьшее из всех;
Используя текущее распределение точек по кластерам, определить среднее значение для каждого кластера и присвоить это значение центральной точке кластера.
Рис.9. Гистограмма полученная с белой плоскости
Рис.10. Влияние структуры объекта на качество гистограммы. Слева- гистограмма, полученная при обработке кадра с белым бюстом. Справа-гистограмма, полученная при обработке кадра с цветной игрушкой
Рис.11. Результаты кластеризации для белого объекта а, б - кластеризация в цветовом пространстве Cb-Cr; в, г - кластеризация в цветовом пространстве H-S
Принадлежность точки к кластеру показана цветом, расположение точек соответствует их координатам в плоскости CbCr (рис. 12, а) и в плоскости HS (рис. 12, б). Из рисунков видно, что алгоритм неверно классифицирует множество точек с низким значением насыщенности S. Причиной этой ошибки является метод расчета расстояния от точки до центра кластера, которое определяется без учета формы кластера. Для кластеризации в декартовом пространстве расстояние от точки до центра кластера без учета формы кластеров.
Данную проблему можно устранить при кластеризации по цветовому тону H и насыщенности S, и введения искусственного коэффициента анизотропии. В этом случае расстояние от произвольной точки до ближайшего кластера можно посчитать по формуле, где k < 1. Введение такой анизотропии позволит учесть «вытянутость» кластера вдоль S. На рисунке рис. 11, в, г приведены результаты кластеризации по значениям H и S при k = 1/3. Использован сдвиг по цветовому тону для сохранения целостности красного кластера.
Также на рисунках рис. 12, б, г можно заметить множество, которые нельзя с уверенностью отнести к какому либо из кластеров. Вводя пороговое значение по насыщенности S или по расстоянию до центра кластера можно выделить данные точки в кластер «неклассифицированных».
Рис.12 Результат работы алгоритмов выделения полос и кластеризации
Произведя декодировку получим трехмерное облако точек:
Рис.13. Восстановленное трехмерное облако точек для белого объекта
К сожалению, при добавлении слабого фона или текстуры вносятся нелинейные искажения и алгоритм перестает работать. О том, как боролись с фоном и делали алгоритм адаптивным - в следующей части.
Список литературы
1. Hartley R.I., Zisserman A. Multiple View Geometry. Cambridge, UK: Cambridge University Press, 2000.2. Scharstein D., Szeliski R.A taxonomy and evaluation of dense two frame stereocorrespondence algorithms // International Journal of Computer Vision. 2002. Vol. 47(1-3).
P. 7–42.
3. Salvi J., Pages J., Batlle J. Pattern codification strategies in structured light systems // Pattern Recognition. 2004. Vol. 37(4). P. 827–849.
4. Geng J. Structured-light 3d surface imaging: a tutorial // Advances in Optics and Photonics. 2011. Vol. 3. P. 128–160.
5. Сафрошкин М.А. Экспериментальные исследования параллаксного метода регистрации 3д объектов с цветным кодированием // Молодежный Научно Технический Вестник, 2013. URL: sntbul.bmstu.ru/doc/608517.html .
6. Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MatLab. М.: Техносфера, 2006.
7. Fechteler P., Eisen P. Adaptive color classification for structured light systems // Computer Vision and Pattern Recognition Workshops, 2008. CVPRW "08. IEEE Computer Society Conference. P. 1-7.
8. Fechteler P., Eisen P., Rurainsky J. Fast and High resolution 3D face scanning // Image Processing, 2007. ICIP 2007. IEEE International Conference. P. 81-847. V.K. De Wansa Wickramarante, V.V. Ryazanov, A.P. Vinogradov. Accurate reconstruction of 3D model of a human face using structured light // Pattern Recognition and Image Analysis, 2008. Vol. 18, No. 3, P. 442-446.
9. Xing Lu, Jung-Hong Zhou, Dong-Dong Liu, Jue Zhang, Application of color structured light pattern to measurement of large out-of-plane deformation // Acta-Mech. Sin(2011). Vol. 27(6). P. 1098-1104.
10. Permuter, H.; Francos, J.; Jermyn, I.H. A study of Gaussian mixture models of color and texture features for image classification and segmentation // Pattern Recognition, 2006. Vol. 39, No. 4, P. 695–706.6. Zhang Z. Flexible camera calibration by viewing a plane from unknown orientations // International Conference on Computer Vision, 1999. P. 666–673.
11. Zhang Z. Flexible camera calibration by viewing a plane from unknown orientations // International Conference on Computer Vision, 1999. P. 666–673.
12. Falcao G., Hurtos N., Massich J. Plane-based calibration of a projector-camera system // VIBOT Master, 2008.
13. V.K. De Wansa Wickramarante, V.V. Ryazanov, A.P. Vinogradov. Accurate reconstruction of 3D model of a human face using structured light // Pattern Recognition and Image Analysis, 2008. Vol. 18, No. 3, P. 442-446
Теги: Добавить метки
Загрузка...
