- Скелетонизация
-
Скелетонизация
Рассматриваемый алгоритм принимает на вход только чёрно-белое изображение, на котором чёрный пиксел имеет значение 1, белый - 0. Теперь рассмотрим сам алгоритм скелетонизации. В своей основе это улучшение метода Distance transform.
Алгоритм скелетонизации
В алгоритме используется два буфера cpdata и pdata, каждый элемент буферов принимает значения от 0 до 255. В pdata загружается чёрно-белое изображение, состоящее только из нулей и единиц. Копируется pdata в cpdata. Алгоритм состоит из двух этапов, каждый этап выполняется дважды (пометка "x2").
1.( x2 ) Циклы модифицированного алгоритма Distance Transform 1.1 Distance Transform 1.2 Обнулить pdata 1.3 Выполнять Flip пока не останутся в cpdata только "0" и "1".
2.( x2 ) Окончательное утоньшение (в буфере cpdata)
// Проверка связности для каждого пиксела в буфере и обнуление пиксела, если он не нарушает связности области вокруг этого пиксела.
Для каждого [i,j], для которого cpdata[i,j]==1 выполнить: {
// Вычислить p и q; // 012 // 7x3 - порядок обхода по кругу 8-связанной окрестности пиксела cpdata[i,j] // 654
p={число паттернов "10" при круговом обходе 8-связанной окрестности пиксела cpdata[i,j]}; q={число "1" в 8-связной окрестности пиксела cpdata[i,j]}; Если ((p==1) и (q>2)) то cpdata[i,j]=0; };
Теперь подробнее шаги 1.1 и 1.3 первого этапа алгоритма
1.1 Distance Transform 1.1.1 //Пусть min - функция минимума из двух чисел. Для каждого элемента изображения(пиксела) [i,j] в буфере cpdata выполнить: { Если (cpdata[i,j]!=0) то cpdata[i,j]=min(min(cpdata[i,j-1],cpdata[i,j+1]),min(cpdata[i-1,j],cpdata[i+1,j]))+1 иначе cpdata[i,j]=0; }; 1.1.2 Выполнять 1.1.1 пока есть изменившие своё значение пиксели в буфере cpdata.
1.3 Метод Flip Для каждого [i,j] выполнить: { Если (cpdata[i,j]==1) то pdata[i,j]=1; Если (число соседних (в 8-связной окрестности пиксела cpdata[i,j]) "1" равно 2 и число соседних "0" не равно 6) то pdata[i,j]=0; Если (cpdata[i,j]>1) то pdata[i,j]=cpdata[i,j]-1; }; Копирование pdata в cpdata.
Теперь в cpdata остаётся результат скелетонизации исходного изображения.
Wikimedia Foundation. 2010.