Алгоритм скелетизации Зонга-Суня (Zhang-Suen)

Один из методов утоньшения линий на изображении.

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

Такой растровый скелет является весьма удобным для векторизации.

Скелетизация изображения, как правило, реализуется за несколько проходов. За один проход снимаются все граничные пиксели. Данный проход повторяется пока на изображении не останутся "не удаляемые" пиксели.

Рассмотрим алгоритм скелетизации Зонга-Суня.

Введем следующую матрицу:

P9	P2	P3
P8	P1	P4
P7	P6	P5

Данная матрица попиксельно накладывается на изображение таким образом, чтобы P1 поочередно совмещался со всеми пикселями изображения (там где это возможно). Стоит уточнить, что белый пиксель на изображении имеет значение 0, а черный 1.

Каждый проход по изображению состоит из двух подитераций.

Подитерация 1:

Пиксель P1 можно удалить если выполняются следующие условия:

1) 2 <= P2+P3+...+P8+P9 <=6

2) S(P1) = 1

3) P2*P4*P6 = 0

4) P4*P6*P8 = 0

где S(P1) - количество найденных последовательностей 01 в последовательности P2, P3, P4, P5, P6, P7, P8, P9, P2. Т.е. для удаления пикселя, вокруг него должен существовать только один переход от нуля к единице.

В данном случае удаляются все пиксели на юго-восточной границе и северо-западные угловые пиксели. Чтобы удалить пиксели на северо-западной границе и юго-восточные угловые пиксели, необходимо выполнить еще одну выше описанную подитерацию заменив пункты 3 и 4 на следующие:

3) P2*P4*P8 = 0

4) P2*P6*P8 = 0

Если после полного прохода по изображению были удалены какие-либо пиксели, то необходимо повторить проход. Такое повторение должно быть до тех пор, пока во время прохода не будет удален ни один пиксель.

Скелетизация Зонга-Суня относиться к классу параллельных алгоритмов, поскольку для корректной работы алгоритма, обработанные данные (информация об удаленных пикселях) должны заноситься в отдельный массив, который предохранят от возможности рекурсивного удаления пикселей.

Исходники:
    Delphi (2007)
    C