Рассматриваемый метод является механистическим и не может быть использован в реальных системах по причине того, что задача построения трехмерной сцены относится к задачам большой размерности.
Расстояние необходимо знать не только до объектов, но и до их фрагментов, только тогда восприятие будет объемным.
Для построения трехмерной сцены в автоматическом режиме должны быть разработаны математические методы и алгоритмы, обеспечивающие решение следующих задач:
· автоматическое выделение контуров объектов;
· автоматическая сегментация изображений (оптимизационная задача в экстремальной постановке);
· фрагментация изображений (связывание сегментов по цвету и интенсивности с учетом границ и расстояний).
Только после решения вышеперечисленных задач можно приступить к решению задачи автоматического построения трехмерной сцены на основе двух моноскопических изображений.
Выбор и обоснование алгоритма
Еще раз кратко перечислим этапы построения трехмерной сцены:
1. чтение 2-х изображений в трехмерную матрицу;
2. выделение границ на изображениях;
3. прослеживание контуров по границам;
4. конвергирование;
5. составление многослойной матрицы;
6. вывод на экран многослойной матрицы.
Очевидно, что составление программы на любом самом современном языке программирования высокого уровня для данного метода даже для ручной правки трехмерной сцены требует месяцы сложнейшей работы и есть большая вероятность того, что за кодом можно не уловить сути самои идеи.
Чтобы проверить метод и прочувствовать саму идею, а «не потеряться» в коде, было принято следующее решение.
Для первых 4-х этапов будем использовать математический пакет MathLab 7, который является мощнейшим инструментом для математических расчетов в любой области проектирования. Это позволит существенно сократить количество времени за счет того, что написание кода, который требуется для работы с изображениями, сводится к минимуму. В MathLab 7 имеются все необходимые функции для данных этапов.
Этап 5 и 6 будет выполнен в 3D-редакторе «3DViewer», который позволяет построить многослойную матрицу, т.е. получить трехмерную сцену из фрагментированных изображений.
Забегая вперед можно сказать, что появится еще один этап 7 – помещение фрагментов на соответствующие слои – ручная правка. Ручная правка необходима, потому что, как станет ясно в дальнейшем, на 5 этапе возникает большое количество ошибок. Этап 7 также можно выполнить в 3D-редакторе.
Сегментация в MATHLAB 7
Как уже было сказано, для сегментации на изображениях часто необходимо обнаружить границы объектов – участки изображения, в которых есть перепад яркости.
Вообще, существует сотни алгоритмов сегментации изображения, рассмотрим некоторые из них.
Функция BW=edge(I, method) предназначена для выделения границ на исходном полутоновом изображении I. Данная функция возвращает бинарное изображение BW такого же размера, как исходное I. Пиксель BW(r, с) равен 1, если пиксель I(r, с) принадлежит границе. Для обнаружения границ может использоваться несколько методов. Применяемый метод задается в параметре method в виде одной из следующих строк: 'sobel', 'prewitt', 'roberts', 'log', 'zerocross', 'canny'. Если параметр method при вызове функции опущен, то по умолчанию он полагается равным 'sobel'.
Для каждого из методов определения границ можно задать дополнительные параметры. Для этого используется одна из функций BW=edge(I, method, thresh), BW=edge(I, method, thresh, P), где параметр thresh задает порог для определения того, принадлежит ли пиксель к границе, а в параметре Р передаются настройки, специфичные для каждого из методов.
Если при вызове функции параметр thresh опущен, то значение порога выбирается автоматически. Получить значение порога можно, дополнительно определив выходной параметр thresh: [BW, thresh]=edge(I, method,...).
Рассмотрим использование функции edge для каждого из методов выделения границ.
Функция BW=edge(I, 'sobel', thresh) для определения границ использует фильтрацию исходного изображения I фильтром Собеля; пиксель считается относящимся к границе, если соответствующий ему пиксель результата фильтрации имеет значение, большее thresh. Для данного метода можно указать дополнительный параметр direction: BW=edge(I, 'sobel', thresh, direction), который определяет, какие границы будут обнаруживаться. Параметр direction может принимать значения: 'horizontal' – выделение горизонтальных границ; 'vertical' – выделение вертикальных границ; 'both' – выделение границ во всех направлениях (данное значение используется по умолчанию, когда параметр direction не определен).
Функция BW=edge(I, 'prewitt', thresh) для определения границ использует фильтрацию исходного изображения I фильтром Превита; пиксель считается относящимся к границе, если соответствующий ему пиксель результата фильтрации имеет значение, большее thresh. Для данного метода можно указать дополнительный параметр direction: BW=edge(I, 'prewitt', thresh, direction), который определяет, какие границы будут обнаруживаться. Возможные значения параметра direction описаны выше.
Функция BW=edge(I, 'roberts', thresh) для определения границ использует фильтрацию исходного изображения I фильтром Робертса; пиксель считается относящимся к границе, если соответствующий ему пиксель результата фильтрации имеет значение, большее thresh.
Функция BW=edge(I, 'log', thresh) для определения границ использует фильтрацию исходного изображения I фильтром лапласиан–гауссиана; пиксель считается относящимся к границе, если соответствующий ему пиксель результата фильтрации имеет значение, большее thresh. Для формирования маски фильтра используется функция fspecial с параметрами sigma=2 (среднеквадратичное отклонение) и n=ceil(sigma´3)´2+1 (размер маски). Параметр sigma можно задать в параметре функции edge: BW=edge(I, 'log', thresh, sigma).
Функция BW=edge(I, 'zerocross', thresh, h) для определения границ использует фильтрацию исходного изображения I линейным фильтром с маской h; пиксель считается относящимся к границе, если соответствующий ему пиксель результата фильтрации имеет значение, большее thresh.
Функция BW=edge(I, 'canny', thresh) использует для определения границ метод Канни. Это достаточно сложный метод, состоящий из большого числа этапов. Суть метода состоит в поиске локальных участков с перепадами яркости. Перепады яркости ищутся с помощью фильтрации по каждой из осей одномерным фильтром лапласиан–гауссиана (см. функцию fspecial). В методе Канни для классификации перепадов на "слабые" и "сильные" используется два порога - нижний и верхний. "Слабые" границы отмечаются в результирующем изображении, только если они соединены с "сильными". Для зашумленных изображений данный метод обеспечивает наилучшее обнаружение границ по сравнению с остальными методами функции edge, но требует существенно большего времени.
Параметр thresh может являться двухэлементным вектором. В этом случае первый элемент вектора задает значение нижнего порога, а второй элемент - значение верхнего порога. Если параметр thresh является скалярным значением, то thresh задает значение верхнего порога, а для нижнего порога используется значение 0.4´thresh. Если параметр thresh при вызове функции опущен или в качестве thresh передан пустой массив ([ ]), то значения порогов определяются автоматически.
В функцию BW=edge(I, 'canny', thresh, sigma) дополнительно передается параметр sigma, задающий среднеквадратичное отклонение распределения Гаусса, которое используется при формировании маски фильтра, выделяющего перепады яркости.
Почему ошибки
Если проанализировать полученный метод, то ошибки могут возникать на 2, 3 и 5 этапах. Т.е.:
2. выделение границ (фрагментация) на двух изображениях для каждой из трех составляющей цвета в отдельности;
3. прослеживание контуров по полученным границам;
5. помещение совпавших контуров на определенный слой матрицы действительной точности размерностью x´y´3´z (где z – это количество слоев, номер слоя определяется количеством пикселей на который было сдвинуто изображение на 4 этапе, это и есть расстояние от камер до объекта);
Для 2 этапа возможны следующие влияющие факторы: соотношение «сигнал-шум», что зависит от качества изображения.
Качество изображения зависит от освещенности объекта, расстояния до него, степени наведения резкости и т.п. Перечисленные параметры могут существенно изменяться в процессе наблюдения. Качество изображения существенно зависит также от разрешающей способности ПЗС-матрицы камер.
Также на фрагментацию влияет само содержание изображения. Например, можно не "увидеть" темный предмет на темном фоне. Тоже самое распространяется на все остальные цвета.
Для 3 этапа все ошибки "тянутся" из второго этапа.
Для 5 этапа ошибки "идут" из ранних этапов. К тому же добавляются новые. Определение расстояния от камер до объекта возможно только в области стереоклина. Точность измерения расстояния зависит от углового разрешения камер и всей оптоэлектронной системы в целом.
Также очень важными параметрами являются: стереобаза и угловое разрешение. Эти величины оказывают влияние на все этапы метода.
Блок-схема метода
 | ||||||||||||
 | ||||||||||||
| ||||||||||||
 | ||||||||||||
| ||||||||||||
 | ||||||||||||
| ||||||||||||
 | ||||||||||||
| ||||||||||||
 | ||||||||||||
| ||||||||||||
| ||||||||||||
|
МЕТОД ДЕЛОНЕ
СОДЕРЖАНИЕ
I. Постановка задачи
II. Описание базового алгоритма построения триангуляции Делоне
III. Описание модифицированного алгоритма
I. Постановка задачи
На плоскости заданы N точек. Соединить их непересекающимися отрезками таким образом, чтобы каждая область внутри выпуклой оболочки этого множества точек являлась треугольником. Граф триангуляции множества из N точек, являясь планарным, имеет, в соответствии с формулой Эйлера, не более 3N-6 рёбер и 2N-4 граней. Результатом решения задачи должен быть список треугольников, образующих триангуляцию.
Задача триангуляции возникает в методе конечных элементов и при интерполяции функции от двух переменных, когда заданы значения функции в N произвольным образом расположенных точках (Xi,Yi) и требуется аппроксимировать её в некоторой новой точке (X,Y). Процесс триангуляции заключается в выборе троек точек, которые будут образовывать грани. Для определения “качества” получаемой триангуляции было предложено немало критериев, включающих, в частности, максимизацию наименьшего угла или минимизацию полной длины рёбер. Выбор указанных условий объясняется их удобством для получения оценки ошибки интерполяции, а не тем, что они позволяют получить наилучшую триангуляцию.
Триангуляция множества точек может быть найдена за оптимальное время. Впервые задача построения подобной триангуляции была поставлена советским математиком Борисом Николаевичем Делоне в 1934 году.
Триангуляция Делоне — это множество не пересекающихся треугольников, в котором ни одна точка, не принадлежащая данному треугольнику, не попадает в окружность, описанную вокруг этого треугольника. Это означает, что образовавшиеся треугольники максимально приближаются к равносторонним.
Теорема. В рамках модели деревьев вычислений любой алгоритм, решающий задачу триангуляции, требует W(NlogN) операций в худшем случае.
II. Описание базового алгоритма триангуляции Делоне
Одно и то же множество можно триангулировать разными способами. Все алгоритмы построения триангуляции Делоне можно условно разделить на два класса: построение триангуляции по заданному набору точек и приведение уже отстроенной триангуляции к виду триангуляции Делоне. Нас изначально интересует только построение триангуляции Делоне на основе заданного набора точек. Поэтому рассмотрим, для начала, классический алгоритм построения триангуляции Делоне, который иногда называют декрементным.
Схема алгоритма:
- Выбор произвольной начальной точки (от выбора начальной точки результирующая триангуляция не зависит, триангуляция на данном множестве является однозначной с точностью до эквивалентных точек).
- Поиск второй ближайшей точки, соединяющий точки отрезок является исходной базой для дальнейших построений.
- Поиск в левой полуплоскости от базового отрезка точки, которая в совокупности с уже входящими в триангуляцию рёбрами не нарушает условие Делоне. Если в левой полуплоскости нет точек, попытка повторяется для правой полуплоскости. В соответствии с этим все рёбра, образующие триангуляцию можно разделить на три группы:
Ø Рёбра, которые не принадлежат триангуляции Делоне.
Ø Рёбра, которые принадлежат только одному треугольнику из построенной триангуляции, второй треугольник ещё не найден или ещё не обнаружено, что данное ребро принадлежит границе триангуляции, а также рёбра, являющиеся границей триангуляции, для которых неизвестен треугольник.
Ø Рёбра, образующие триангуляцию Делоне.
На этом этапе базовое ребро относится ко второму типу, так как для него неизвестен треугольник, которому он принадлежит.
- На следующем шаге определяется точка, образующая треугольник с текущим ребром, удовлетворяющий условию Делоне. Поиск нужных вершин всегда производится в левой полуплоскости относительно базового ребра. Вновь полученные рёбра из первой группы переходят во вторую (они обозначены толстыми линиями), то есть для них пока неизвестен второй треугольник или их принадлежность границе. Исходное ребро переходит в третью группу – является частью триангуляции Делоне. Если найти точку, удовлетворяющую условию Делоне невозможно, то ребро предполагается граничным.
- Процесс продолжается до тех пор, пока вершинами треугольников не будут закреплены все точки исходного множества. В конечном итоге триангуляция состоит из набора рёбер третьей группы.
Для работы классического алгоритма построения триангуляции, необходимо сделать два предположения относительно точек в наборе. Во-первых, чтобы вообще существовала триангуляция, полагается, что набор содержит, по крайней мере, три точки, и они – не коллинеарные. Во-вторых, для уникальности триангуляции Делоне необходимо, чтобы на одной описанной окружности лежало не более трёх точек из набора, так как, например, четыре точки на одной описанной окружности позволяют реализовать две различные триангуляции Делоне.
Рис. 1: Наращивание триангуляции Делоне. Рёбра, входящие в состав границы, выделены толстой линией
Недостатки данного алгоритма:
1. Это алгоритм класса n**2, так как требуется аналитическое сравнение каждой точки со всеми остальными.
2. Алгоритм использует постоянно вычисляемые тригонометрические функции, что резко замедляет процесс.
3. При исследовании взаимоотношения точек и базового отрезка сплошь и рядом возникают очень малые (стремящиеся к нулю) углы, и при использовании тригонометрических функций постоянно возникает опасность исчезновения порядка и деления на 0 в связи с ограниченной точностью представления данных в компьютере, эта ситуация требует постоянной дополнительной обработки.
4. Поскольку обработка идет до последней точки, то есть в границах правильной выпуклой оболочки, при очень частых квазилинейных ограничениях множества на границах области образуются треугольники с предельно малыми углами, что часто приводит к трудно обрабатываемым тупиковым ситуациям.
III. Описание модифицированного алгоритма построения триангуляции Делоне
Классический алгоритм построения триангуляции Делоне, основанный на полном переборе всех троек вершин, может быть значительно ускорен, если при построении учитывать свойства триангуляции как планарного графа. Например, если сумма углов при вершине достигла 360°, то эта вершина не может принадлежать более ни одному треугольнику (кроме уже отстроенных), и при дальнейшем переборе троек вершин данную вершину рассматривать не нужно. Исключать из повторного рассмотрения также нужно уже встречавшиеся “зоны неоднозначности“ – выше упоминавшиеся точки, лежащие на одной окружности при условии, что их больше трёх. Значительно ускорить алгоритм позволяет перенесение начальной точки построения в центр масс области и предварительная сортировка точек набора в порядке их удаления от центра масс.
Схема работы алгоритма:
1) Определяем центр масс заданной области и сортируем точки по увеличению расстояния относительно центра масс.
2) Перебираем комбинации точек по 3. Пусть {v1,v2,v3} – проверяемая на данной итерации комбинация точек, где точка v1 получена в первом цикле (по i), v2 – во втором (по j), а v3 – в третьем цикле (по k). Для исключения полного перебора всех комбинаций выполняем следующие действия:
a) В начале цикла по i проверяем сумму углов при выбранной точке. Если сумма углов треугольников, уже вошедших в триангуляцию, с вершиной v1 равна 360 градусов, то триангуляция не может содержать больше ни одного треугольника с данной вершиной, и можно сразу перейти к рассмотрению следующей тройки точек. То есть выполняется переход к следующей точке v1.
b) Аналогичная проверка делается в начале следующего цикла (по j) для точки v2.
c) Проверяем, пересекает ли образовавшийся отрезок v1-v2 хотя бы одно ребро текущей триангуляции. Если есть пересечение, то любой треугольник, содержащий ребро v1-v2 не входит в триангуляцию. И целую ветвь возможных комбинаций можно отбросить, выполнив переход к следующей точке v2.
d) Выбираем точку v3, проверяя соответствующую сумму углов триангуляции при v3.
e) Если выполнены успешно все проверки для вершин v1, v2, v3, то переходим к проверке выполнения условия Делоне по следующей схеме:
ü для треугольника {v1, v2, v3} находим центр и радиус описанной окружности;
ü проверяем точки входного множества на нахождение их внутри или на окружности, если найдены точки, лежащие на окружности и их больше трёх, то триангуляция может быть получена не единственным образом, поэтому будем называть такие окружности с точками – “зоной неоднозначности”, и заносить их радиусы в отдельный список;
ü если радиус описанной окружности текущего треугольника {v1, v2, v3} уже числится в списке “зон неоднозначности”, то, не делая дополнительных проверок, расширяем данную “зону неоднозначности”;
ü строим триангуляцию “зон неоднозначности” как выпуклого полигона “веером”.
f) Если условие Делоне выполнилось, то треугольник входит в триангуляцию. Определяем углы при его вершинах и дополняем ими суммы углов при соответствующих им входных точках.
g) Проверяем сумму углов при точке v1, так как возможно, что один из углов последнего отстроенного треугольника дополнил его до 360 градусов.