Скелетизация

Для процесса скелетизации выберем алгоритм Зонга‑Суня [9]. Он является модификацией алгоритма Хилдича (Hilditch C. J., [10]), предложенного в 1969 году.

Рис. 1. Нумерация соседних точек

Введем нумерацию соседних точек так, как показано на рис. 1. Пусть xx(n) и yy(n) – функции получения координат соседней точки Pn
для текущей точки P(x,y). Используя данные функции, строится логическая функция P(n), которая будет принимать значение «истина», если соседняя точка Pn принадлежит образу, и «ложь» в противном случае. Кроме того, для текущей точки P(x,y), определим функции: A(P), которая будет показывать количество комбинаций 01, встречающихся в упорядоченном замкнутом множестве P1,…,P8,P1 и B(P), которая будет показывать количество ненулевых соседей P:

function A:Byte;

begin

Result:=0;

For i:=1 to 7 do

 If Not(P(i)) and P(i+1) then Result:=Result+1;

If Not(P(8)) and P(1) then Result:=Result+1;

end;

function B:Byte;

begin

Result:=0;

For i:=1 to 8 do If P(i) then Result:=Result+1;

end;

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

(1) 2£B(P)£6

(2) A(P)=1

(3) P(2)×P(4)×P(6)=0

(4) P(4)×P(6)×P(8)=0

Условие (1) гарантирует, что P находится на границе образа, и мы не удалим изолированные точки. Условие (2) гарантирует, что мы не разорвем скелет. Условия (3) и (4) позволяют нам удалить точки на юго‑восточной границе и северо‑западные угловые точки образа. (Точка P называется северной / восточной
/ южной / западной граничной точкой, если соседняя точка P2=0 / P4=0 / P6=0 / P8=0 соответственно. Юго‑восточной граничной точкой считать либо южную, либо восточную граничную точку; юго‑восточной угловой – одновременно и северную, и западную граничную точку. Другие подобные комбинации понимаются аналогично.) Для удаления точек образа на северо‑западной границе и юго‑восточных угловых точек условия (3) и (4) будут иметь следующий вид:

(3) P(2)×P(4)×P(8)=0

(4) P(2)×P(6)×P(8)=0

Выполнение шагов продолжается до тех пор, пока за оба шага не будет удалено ни одной точки:

Temp:=Pattern;

Repeat

Flag:=True;

 {Шаг 1. Удаление точек на Ю‑В границе и С‑З угловых точек.}

Pattern:=Temp;

 {Шаг 2. Удаление точек на С‑З границе и Ю‑В угловых точек.}

Pattern:=Temp;

Until Flag;

Реализация Шага 1 выглядит следующим образом:

For y:=1 to Height‑2 do

 For x:=1 to Width‑2 do

 begin

 If P(0) then

 If (B>=2) and (B<=6) and (A=1) and

(Not(P(2) and P(4) and P(6)) and Not(P(4) and P(6) and P(8))) then

 {Для Шага 2 эта строка будет иметь следующий вид:

(Not(P(2) and P(4) and P(8)) and Not(P(2) and P(6) and P(8)))}

 begin

Temp[x,y]:=clWhite;

Flag:=False;

end;

end;

Также существуют алгоритмы [11], основанные на других (нежели пять предыдущих) принципах построения непрерывного скелета бинарного изображения.

Похожие записи
  • Нет ничего похожего

Добавить комментарий