Реферат: Техническое зрение роботов

Рас­смотрим метод соединения граничных точек путем определения их расположения на кривой специального вида. Первоначально п редполагая, что на плоскости ху образа дано п точек, тре буется найти подпоследовательности точек, лежащих на прямых линиях. Одно из возможных решений состоит в построении всех линий, проходящих через каждую пару точек, а затем в нахож­дении всех подпоследовательностей точек, близких к определен­ным линиям. Задача, связанная с этой процедурой, заключается в нахождении п(п— 1)/2 ~ п² линий и затем в осуществлении п [п(п— 1)]/2 ~ п ³ сравнений каждой точки со всеми линиями. Этот процесс трудоемок с вычислительной точки зрения за ис­ключением самых простых приложений.

Данную задачу можно решить по-другому, применяя подход, предложенный Хоугом и называемый преобразованием Хоуга . Рассмотрим точку (х _i y _i ) и общее уравнение прямой ли­нии у: = аx _i + b_i . Имеется бесконечное число линий, проходящихчерез точку(х _i y_i ), но все они удовлетворяют уравнению у:= аx _i +b_i при различных значениях а и b. Однако, если мы за­пишем это уравнение в виде b = -х_i а + y_i и рассмотрим пло­скость а b (пространство параметров), тогда мы имеем уравне­ние одной линии для фиксированной пары чисел (х _i y_i ). Более того, вторая точка (х _j , у _j ) также имеет в пространстве пара­метров связанную с ней линию, которая пересекает другую ли­нию, связанную с точкой (х_i y_i ) в точке (а', b’), где значения а' и b’— параметры линии, на которой расположены точки(х_i y_i )и (х_j , у _j ) в плоскости ху. Фактически все точки, расположен­ные на этой линии, в пространстве параметров будут иметь ли­нии пересечения в точке (а', b’) .

Вычислительная привлекательность преобразования Хоуга заключается в разделении пространства параметров на так на­зываемые собирающие элементы , где (a_макс , а_мин ) и (b_макс , b_{м ин} )—допустимые величины параметров линий. Собирающий элементA (i, j) соответствует площади, связанной с ко­ординатами пространства параметров (а _i , b_j ). Вначале эти эле менты считаются равными нулю. Тогда для каждой точки (x_k , у _k ) в плоскости образа мы полагаем параметр а равным каж­дому из допустимых значений на оси а и вычисляем соответст­вующее b, используя уравнение b = - х _k + y _k Полученное значение b затем округляется до ближайшего допустимого зна­чения на оси b. Если выбор a_р приводит к вычислению b _q , мы полагаем А( р, q) == А( р, q) + 1. После завершения этой про­цедуры значение М в элементеA (i, j) соответствует М точкам в плоскости xy, лежащим на линииy= a_i x+b. Точность рас­положения этих точек на одной прямой зависит от числа раз­биений плоскости аb. Отметим, что, если мы разбиваем ось а на К частей, тогда для каждой точ­ки(x_k , у _k ) мы получаем К зна­чений b, соответствующих К воз­можным значениям а. Посколь­ку имеется п точек образа, про­цесс состоит из пК вычислитель­ных операций. Поэтому приве­денная выше процедура линейна относительно п и имеет меньшее число вычислительных опера­ций, чем процедура, описанная выше, если К<= п.

Проблема, связанная с пред­ставлением прямой линии урав­нением у = ах + b, состоит в том, что оба параметра а и b стремятся к бесконечности, если линия принимает вертикаль­ное положение. Для устранения этой трудности используется нормальное представление прямой линии в виде

xc os q +y sin q = b .

Это представление для построения таблицы собирающих элементов используется так же, как метод, изложенный выше, но вместо прямых линий мы имеем синусоидальные кривые в плоскости q r . Как и прежде, М точек, лежащих на прямойxcos q _i +у sinq _i == r _i , соответствуют М синусоидальным кривым, кото­рые пересекаются в точке (q _i ,r _i ) пространства параметров. Если используется метод возрастания q и нахождения для него соот­ветствующего r , процедура дает М точек в собирающий элемент А (i, j), связанный с точкой (q _i ,r _i ).

2.1.3.Глобальный анализ с помощью методов теории графов.

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

Сначала дадим несколько простых определений. Граф G= (N, А) представляет собой конечное, непустое множество вершин N вместе с множеством А неупорядоченных пар различ­ных элементов из N. Каждая пара из А называется дугой.

Граф, в котором дуги являются направленными, называется на­правленным графом. Если дуга выходит из вершины n _i , к вер­шине п _j , тогда п _j называется преемником вершины n_i . В этом случае вершинаn _i называется предшест венником вершины п _j . Процесс идентификации преемников каждой вершины назы­вается расширением этой вершины. В каждом графе опреде­ляютс я уровни таким образом, чтобы нулевой уровень состоял из единственной вершины, называемой начальной, а последний уровень—из вершин, называемых целевыми. Каждой дуге (n _i п _j ) приписывается стоимость c( n _i п _j ). Последовательность вер­шин п 1, n2, ..., nk , где каждая вершинаni является преемником вершиныri -1, называется путем отn _i к п _k , а стоимость пути определяется формулой

.

Элемент контура мы определим как границу между двумя пик­селами р и q . В данном контексте под контуром пони­мается последовательность элементов контура.

2.2.Определение порогового уровня

Понятие порогового уровня (порога) тест вида

Т = Т [х, у, р (х, у), f (х, у)],

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

так что пикселы вg(x, у), имеющие значение 1, соответствуют объектам, а пикселы, имеющие значение 0, соответствуют фону. В уравнении предполагается, что интенсивность объек­тов больше интенсивности фона. Противоположное условие по­лучается путем изменения знаков в неравенствах.

2.2.1.Глобальные и локальные пороги.

Если значение Т в уравне­нии зависит только от f(x, у), то, порог называется глобальным. Если значение Т зависит как от f(x, у), так и от р(х, у), порог называется локальным. Если, кроме того, Т зависит от пространственных координат х а у, в этом случае он называется динамическим порогом.

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

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

2.2.2.Выбор оптимального порога.

Часто рассматривают гисто­г рамму, состоящую из суммы значений функции плотности ве­ роятности. В случае бимодальной гистограммы аппро ксимирую­щая ее функция дается уравнением

p(z)= P1p1(z)+P2p2( z),

где интенсивность z— случайная переменная величина,p1( z) и p2 (z)— функции плотности вероятности, a P1 иP2 – априорные вероятности. В данном случае априорные вероятности означают появление двух видов уровней интенсивности на образе. Полная гистограмма может быть аппроксимирована суммой двух функций плотности вероятности. Если известно, что объект состоит из светлых пиксе­лов и они занимают 20 % площади образа, тоPi == 0,2 . Необхо­димо, чтобы

Р1 +Рг =1 .

В данном случае это означает, что на остальную часть образа приходится 80 % пикселов фона. Введем две следующие функции отz:

d1(z)= P1p1( z),