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

Вычислительная привлекательность преобразования Хоуга заключается в разделении пространства параметров на так на­зываемые собирающие элементы , где (aмакс, амин) и (bмакс, bмин)—допустимые величины параметров линий. Собирающий элемент A (i, j) соответствует площади, связанной с ко­ординатами пространства параметров (аi, bj). Вначале эти элементы считаются равными нулю. Тогда для каждой точки (xk, уk) в плоскости образа мы полагаем параметр а равным каж­дому из допустимых значений на оси а и вычисляем соответст­вующее b, используя уравнение b = -хk + yk Полученное значение b затем округляется до ближайшего допустимого зна­чения на оси b. Если выбор aр приводит к вычислению bq, мы полагаем А(р, q) ==А(р, q) + 1. После завершения этой про­цедуры значение М в элементе A (i, j) соответствует М точкам в плоскости xy, лежащим на линии y=aix+b. Точность рас­положения этих точек на одной прямой зависит от числа раз­биений плоскости аb. Отметим, что, если мы разбиваем ось а на К частей, тогда для каждой точ­ки (xk, уk) мы получаем К зна­чений b, соответствующих К воз­можным значениям а. Посколь­ку имеется п точек образа, про­цесс состоит из пК вычислитель­ных операций. Поэтому приве­денная выше процедура линейна относительно п и имеет меньшее число вычислительных опера­ций, чем процедура, описанная выше, если К<= п.

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

xcosq+ysinq=b.

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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