A Skeletonization Algorithm

The Purpose: To find medial axis of a 2D shape, the set of points where the ``fire lines'' meet.

The Algorithm:

• Step 1: Represent shape in binary form, initialize $k=0$.

  
  

  $$x_0[m,n]=\left\{ \begin{array}{ll} 1 & \mbox{if pixel $[m,n]... ...side the shape} \\ 0 & \mbox{otherwise} \end{array} \right.$$
  
  

• Step 2: Repeat the following until no more change can be made: $k=k+1$,

  for each $x_{k-1}[m,n]=k$, do $x_k[m,n]=min\{x_{k-1}[i,j] \}+1$, here $[i.j]$ is the four closest neighbors of $[m,n]$.

• Step 3: The skeleton is the set of points given below:
  
  $$\{ [m,n]\; \vert\; x_k[m,n]=max\{ x_k[i,j] \} \}$$
  
  

  

  The full 2D shape can be recostructed from the skeleton pixels as the union of all circules with center at $[m,n]$ and radius of $x[m,n]-1$.