2.1.2.Глобальный анализ с помощью преобразования Хоуга.
Рассмотрим метод соединения граничных точек путем определения их расположения на кривой специального вида. Первоначально предполагая, что на плоскости ху образа дано п точек, требуется найти подпоследовательности точек, лежащих на прямых линиях. Одно из возможных решений состоит в построении всех линий, проходящих через каждую пару точек, а затем в нахождении всех подпоследовательностей точек, близких к определенным линиям. Задача, связанная с этой процедурой, заключается в нахождении п(п— 1)/2 ~ п2 линий и затем в осуществлении п[п(п—1)]/2 ~ п3 сравнений каждой точки со всеми линиями. Этот процесс трудоемок с вычислительной точки зрения за исключением самых простых приложений.
Данную задачу можно решить по-другому, применяя подход, предложенный Хоугом и называемый преобразованием Хоуга. Рассмотрим точку (х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 стремятся к бесконечности, если линия принимает вертикальное положение. Для устранения этой трудности используется нормальное представление прямой линии в виде
xcos+ysin=.
Это представление для построения таблицы собирающих элементов используется так же, как метод, изложенный выше, но вместо прямых линий мы имеем синусоидальные кривые в плоскости . Как и прежде, М точек, лежащих на прямой xcosi+уsini == i, соответствуют М синусоидальным кривым, которые пересекаются в точке (i, i) пространства параметров. Если используется метод возрастания и нахождения для него соответствующего , процедура дает М точек в собирающий элемент А (i, j), связанный с точкой (i, i).
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. В данном контексте под контуром понимается последовательность элементов контура.
|
