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

1.2.6 Поиск отверстий объекта  методом морфологического водораздела

 

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

- точки локального минимума;

- точки, находящиеся на склоне, т.е. с которых вода скатывается в один и тот же локальный минимум;

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

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

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

а) Исходное изображение.

б) Рельефное представление.

в) Первая стадия заполнения.

г) Вторая стадия заполнения.

Рисунок 1.13.

 

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

На рисунке 1.14 показвается процесс заполнения локальных минимумов «водой».

а) Результат дальнейшего заполнения.

б) Начало слияния двух бассейнов

(между ними строится  короткая перегородка).

в) Перегородки большей длины.

г) Окончательные линии водоразделов

(результат сегментации).

Рисунок 1.14.

 

На рисунке 1.14а вода поднимается, соответственно, заполняются левый и правый внутренние бассейны. По мере дальнейшего подъема воды в какой-то момент эти два бассейна должны будут слиться; первые признаки этого показаны на рисунке 1.14б. Здесь, во избежание слияния правого и левого внутренних бассейнов при повышении уровня воды, строится короткая перегородка, состоящая из одиночных пикселей. Это явление становится более выраженным по мере того, как вода продолжает подниматься, что демонстрируется на рисунке 1.14в. На этом рисунке прослеживается более длинная перегородка между бассейнами, а также еще одна перегородка в правой верхней части правого бассейна. Последняя была строится, чтобы предотвратить слияние этого бассейна с областью, соответствующей фону. Этот процесс продолжается до тех пор, пока уровень заполнения водой не достигнет того, который соответствует максимальной яркости в исходном изображении. Заключительный набор перегородок соответствует линиям водораздела, которые и представляют собой искомый результат сегментации. Для рассматриваемого примера этот результат показан на рисунке 1.14г темной линией шириной в один пиксель, наложенной на исходное изображение. Отмечается то важное свойство, что линии водоразделов образуют связный путь, тем самым, определяя непрерывные границы между областями.

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

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

а) Два частично заполненных  бассейна на (n-1)-ом шаге заполнения.

б) n-ый шаг заполнения, при котором два бассейна сливаются  вместе.

в) Примитив, используемый в операции дилатации.

г) Результаты дилатации  и построения перегородки.

Рисунок 1.15.

 

Начальные сведения о построении перегородок  с помощью дилатации иллюстрируется на рисунке 1.15. На рисунке 15а показываются участки двух бассейнов на (n-1) - ом шаге заполнения, а на рисунке 1.15б те же участки на следующем, n - ом шаге. Происходит слияние этих двух бассейнов, и, следовательно, должна быть построена перегородка, препятствующая данному событию. Для согласования с системой обозначений, которая будет принята далее, обозначим через M1 и M2 множества точек, соответствующие локальным минимумам двух рассматриваемых бассейнов. Через Cn-1(M1) и Cn-1(M2) обозначим множества точек, покрытых водой в этих бассейнах на (n-1)-ом шаге заполнения. Эти два множества показаны черным цветом на рисунке 1.15а.

Пусть C[n-1] — объединение двух последних  множеств. На рисунке 1.15a имеется две компоненты связности, а на рисунке 15б - только одна, охватывающая две прежние компоненты связности (обозначены пунктирными линиями). Тот факт, что две компоненты связности превратились в одну, указывает, что на n-ом шаге заполнения произошло слияние двух бассейнов в один. Обозначим через q образовавшуюся единую связную компоненту. Заметим, что две компоненты, имевшиеся на шаге n-1, можно выделить из множества q одной операцией И q∩C[n-1]. Отметим также, что все точки, соответствующие отдельному бассейну, образуют одну компоненту связности.

Допустим, к каждой компоненте связности  на рисунке 1.15а применяется операция дилатации по примитиву, показанному на рисунке 1.15в, с соблюдением двух условий:

- применение дилатации должно  ограничиваться множеством q (это  значит, что центр примитива может  располагаться только в точках q);

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

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

Пусть M1,M2,…,MR — множества точек  координатной плоскости, соответствующие  локальным минимумам поверхности g(x,y). Обозначим через C(Mi) множество  точек бассейна, отвечающего локальному минимуму Mi (напомним, что точки любого бассейна образуют компоненту связности). Обозначения min и mах будем использовать для указания наименьшего и наибольшего значений изображения, g(x,y). Наконец, запись T[n] означает множество точек (s,t), для которых g(s,t)<n, т.е.

T[n]={(s,t)|g(s,t)<n}      (11)

С геометрической точки зрения, T[n] есть множество точек, в которых  поверхность g(x,y) лежит ниже плоскости g(x,y)=n.

При заполнении рельефа водой уровень  поднимается в виде целочисленных дискретных приращений от n=min+1 до, n=max+1. В процессе подъема воды на любом шаге и алгоритму необходимо знать число точек, лежащих ниже уровня воды. Вообразим, что все точки множества T[n] (т.е. которые лежат ниже плоскости g(x,y)=n) отмечены черным цветом, а все остальные — белым. Тогда при произвольном (n- ом) шаге подъема уровня воды, рассматриваемая трехмерная поверхность в проекции на плоскость ху может быть представлена двоичным изображением, в котором черные точки соответствуют точкам исходной функции, лежащим ниже плоскости g(x,y)=n. Такая интерпретация весьма полезна для понимания последующего изложения.

Пусть Cn(Mi) обозначает множество точек  бассейна с локальным минимумом Mi, которые оказались залитыми водой  на шаге n. С учетом вышесказанного, Cn(Mi) можно рассматривать как двоичное изображение, задаваемое соотношением

Cn(Mi)=C(Mi)∩T[n].                                                        (1.25)

Другими словами, Cn(Mi)=1 в тех точках (x,y), для которых одновременно выполняется (x,y)ÎC(Mi) и (x,y)ÎT[n] в остальных точках изображения Cn(Mi)=0. С помощью операции (24) пересечения на n-ом шаге подъема уровня воды выделяется та часть двоичного изображения T[n], которая относится к локальному минимуму Mi.

Пусть теперь C[n] — объединение залитых водой частей всех бассейнов на шаге n

Тогда C[max+1] есть объединение всех имеющихся бассейнов

Можно показать, что при работе алгоритма никогда не происходит удаления элементов из множеств Cn(Mi) и T[n]. Таким образом, при увеличении и число элементов этих множеств либо возрастает, либо остается неизменным. Следовательно, C[n-1] является подмножеством C[n]. Согласно равенствам (24) и (25), C[n] также является подмножеством T[n], а значит, C[n-1] также есть подмножество T[n]. Отсюда следует важный результат: каждая компонента связности множества C[n-1] содержится ровно в одной связной компоненте множества T[n].

Алгоритм нахождения линий водораздела  начинается с инициализации C[min+1]=T[min+1]. После этого алгоритм выполняется  рекуррентно, предполагая на n-ом шаге множество C[n-1] уже построенным. Для получения множества C[n] из множества C[n-1] применяется следующая процедура. Пусть Q[n] — множество компонент связности множества T[n]. Тогда для каждой связной компоненты qÎQ[n] есть три возможности:

- q∩C[n-1] — пустое множество;

- q∩C[n-1] содержит единственную компоненту  связности множества C[n-1];

- q∩C[n-1] содержит более одной  компоненты связности множества  C[n-1].

Способ построения C[n] по C[n-1] зависит  от того, какое из этих трех условий имеет место. Условие (а) означает, что встретился новый локальный минимум (начинается наполнение нового бассейна); в этом случае для построения множества C[n] компонента q добавляется к C[n- 1]. Условие (б) имеет место, когда q лежит внутри бассейна некоторого локального минимума; в этом случае для построения множества C[n] компонента q также добавляется к C[n-1]. Условие (в) возникает, когда встретились точки гребня, разделяющего два или более бассейна. В этом случае дальнейший подъем воды привел бы к слиянию этих бассейнов, поэтому внутри связной компоненты q должна быть построена перегородка (или перегородки, если объединяется более двух бассейнов), не позволяющая бассейнам слиться вместе. Как объяснялось в предыдущем разделе, перегородку толщиной в один пиксель при необходимости можно построить, применяя к множеству q∩C[n-1] операцию дилатации по примитиву 3x3, заполненному единицами, и затем ограничивая результат дилатации точками множества q.

Эффективность описанного алгоритма  можно повысить, используя только те значения n, которые соответствуют уровням яркости, встречающимся в изображении g(x,y). Эти значения, как и величины min и max, можно определить по гистограмме изображения g(x,y).[7]

1.2.7 Построение модели октодерева  объекта

 

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

Представление трехмерного объекта  в форме октодерева является расширением  подобной двухмерной схемы представления, называемыми кодированием в форме квадродерева (quadtree). Квадродеревья генерируются последовательным делением двухмерной области (обычно квадрата) на квадранты. Каждый узел квадродерева имеет четыре элемента данных — по одному на каждый квадрант области (рисунок 1.16).

Рисунок 1.16 - Квадратная область на плоскости ху, разделенная на нумерованные квадранты, и соответствующий узел квадродерева с четырьмя элементами данных

 

Если все точки квадранта  имеют одинаковый цвет (однородный квадрант), этот цвет указывается в соответствующем элементе данных узла. Кроме того, в элементе данных устанавливается метка, определяющая, что квадрант однородный. Если, например, все точки в квадранте 2 на рисунке 1.16 черного цвета, код красного цвета помещается в элемент данных 2 этого узла. В противном случае квадрант неоднородный, и он делится на подквадранты, как показано на рисунке 1.17. Элемент данных в узле, соответствующем квадранту 2, теперь помечает квадрант как неоднородный и хранит указатель на следующий узел квадродерева.

 

 

 

 

Рисунок 1.17 - Квадратная область плоскости ху с двумя уровнями деления на квадранты и соответствующее представление в форме квадродерева

 

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