Одним из способов распознавания объектов на изображении является структурный подход, основанный на построении скелета объектов, то есть утончения полутоновых объектов с целью дальнейшей быстрой и качественной обработкой изображения.
Под скелетом понимается набор простых примитивов (линии, дуги, точки), которые получаются в результате утончения границ объекта. Основным предназначением любого алгоритма скелетизации является максимальное утончение всех линий на бинарном изображении, что приводит к получению скелета, в котором все линии имеют толщину в один пиксель. Фактически скелет является представлением формы фигуры, упрощает её дальнейший анализ.
Основная идея алгоритма Зонга-Суня заключается в том, что на каждом шаге, пробегая по изображения рамкой 3x3, проверяется принадлежность каждого пикселя к границе заданной связной области. Если условия проверки выполняются, то пиксель удаляется из области. Скелетизация изображения реализуется за несколько проходов. За один проход снимаются все граничные пиксели. Данный проход повторяется пока на изображении не останется скелет границы.
Рассмотрим матрицу следующего вида, где Pi — это яркость i-го пикселя.
Рис.1. − Матрица пикселей
Шаг 1. Удаление пикселя Pi происходит, если выполняются следующие условия:
1) 2 <= P2 + P3 + P4 + P5 + P6 + P7 + P8 + P9 <= 6 (см. листинг 1)
2) S(P1) = 1(см. листинг 2)
3) P2 * P4* P6 = 0
4) P4 * P6* P8 = 0
Здесь S(P1) — количество найденных последовательностей 01 в последовательности P2, P3, P4, P5, P6, P7, P8, P9, P2, то есть для удаления пикселя, вокруг него должен существовать только один переход от нуля к единице, если A равно 1, то удаляем (см. листинг 2).
Листинг 1. Функция проверки количества ненулевых соседей.
int count = 0;
if (s[x - 1][y]) count++;
if (s[x - 1][y + 1]) count++;
if (s[x - 1][y - 1]) count++;
if (s[x][y + 1]) count++;
if (s[x][y - 1]) count++;
if (s[x + 1][y]) count++;
if (s[x + 1][y + 1]) count++;
if (s[x + 1][y - 1]) count++;
Листинг 2. Функция проверки количества переходов.
bool p2 = s[x][y - 1];
bool p3 = s[x + 1][y - 1];
bool p4 = s[x + 1][y];
bool p5 = s[x + 1][y + 1];
bool p6 = s[x][y + 1];
bool p7 = s[x - 1][y + 1];
bool p8 = s[x - 1][y];
bool p9 = s[x - 1][y - 1];
int A =
Convert.ToInt32((!p2 && p3)) + Convert.ToInt32((!p3 && p4)) +
Convert.ToInt32((!p4 && p5)) + Convert.ToInt32((!p5 && p6)) +
Convert.ToInt32((!p6 && p7)) + Convert.ToInt32((!p7 && p8)) +
Convert.ToInt32((!p8 && p9)) + Convert.ToInt32((!p9 && p2));
После применения первого шага удаляются все пиксели на правой и нижней части границы. Чтобы удалить пиксели на верхней и левой границе, применим второй шаг алгоритма:
Шаг 2:
1) 2 <= P2 + P3 + P4 + P5 + P6 + P7 + P8 + P9 <= 6 (см. листинг 1)
2) S(P1) = 1(см. листинг 2)
3) P2 * P4* P8 = 0
4) P2 * P6* P8 = 0
Если после применения алгоритма удален хотя бы один пиксель, то выполняется повторный проход по изображению. Повторение происходит до тех пор, пока в результате работы программы количество удаленных пикселов не окажется равным нулю.
На рисунке 2 приведен результат применения алгоритма Зонга-Суня.
Рис.2. Изображение до и после применения алгоритма Зонга-Суня