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

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

Рассматриваемый алгоритм принимает на вход только чёрно-белое изображение, на котором чёрный пиксел имеет значение 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 остаётся результат скелетонизации исходного изображения.