Это следующий важный блок алгоритмов программы. На этом этапе производится выделение особых точек, а также обход контура образа, с построением топологического кода, т. е. последовательности индексов и номеров особых точек в порядке обхода, а также выделением некоторых других геометрических характеристик для распознавания.
Автором было рассмотрено четыре алгоритма выделения контура [12], которые описываются только иностранными авторами и не опубликованы в русскоязычной литературе. Кроме того, автором был разработан эффективный алгоритм выделения контура. Он является модификацией алгоритма кругового обзора (Radial Sweep, [13]).
Итак, пусть мы находимся в начальной точке образа, выбор которой определим позже. Согласно некоторому алгоритму, будем переходить с одной точки образа на другую. Набор точек, по которым мы пройдем, и будут образовывать внешний контур образа или границу.
Введем понятие направления входа в точки границы при обходе контура. Пусть направлением входа считается та точка, из которой мы пришли в текущую. Очевидно, что направление будет задавать одна из соседних точек.
Опишем алгоритм перехода из текущей граничной точки в следующую. Каждый раз будем заново перенумеровывать соседние точки, начиная с точки следующей по часовой стрелке после точки направления входа. Таким образом, точка направления входа будет всегда иметь последний номер, номер 8. Затем будем просматривать точки, начиная с 1 по 8, и переходить на черную точку образа с наименьшим номером.
Если за основу взять нумерацию соседних точек по Муру (как и в алгоритме скелетизации, см. рис. 1), то функции преобразования к этой нумерации, будет выглядеть следующим образом:
|
function nn(n,d:Byte):Byte; begin Result:=(n+d) mod 8; If Result=0 then Result:=8; end; |
Где n – номер просматриваемой точки в текущей нумерации, определяемой направлением входа, а d – номер точки направления входа в нумерации соседних точек по Муру.
Функция преобразования нового номера, полученной точки направления входа ns, к нумерации по Муру dd
будет выглядеть так:
|
function dd(ns:Byte):Byte; begin Result:=(ns+4) mod 8; If Result=0 then Result:=8; end; |
Функции преобразования номеров были получены аналитически, путем построения всех наборов текущих номеров и точек направлений входа. Опишем основную логику перехода от текущей граничной точки к следующей:
|
n:=0; Repeat Inc(n); ns:=nn(n,d); Until Pattern[xx(ns),yy(ns)]<>clWhite; x:=xx(ns); y:=yy(ns); {Отмечаем точку (x,y) граничной и проверяем на особость} d:=dd(ns); |
Пример работы данного алгоритма показан на рис. 2.
Рис. 2. Пример работы алгоритма выделения контура
Теперь возникает вопрос, как проверить, является ли точка особой? Оказывается нам не достаточно подсчитать количество соседних точек. Индекс точки определяется функцией A, введенной выше. Другими словами, функция A(x,y) – это количество линий, выходящих из точки (x,y). Используя это определение, мы можем считать точку особой, если A≠2.
Loading ...