|
Skeletonizing is one of the steps in text recognition applications. It is used to determine characteristics of an object to recognize a letter.
Tablo 1. A 3x3 matrix in the image
Skeletonizing Steps
Step 1
à  à  à  à 
Step 2
à à à  à 
Firstly Step 1 is applied for a pixel in original image matrix, whose origin is P1 in Table 1. If all conditions in Step 1 are satisfied, pixel P1 is copied to a temporary image matrix. Otherwise no information is passed to temporary image. Step 1 is repeated until all pixels are crossed over. Secondly Step 2 is applied to temporary image and satisfied pixels are copied to original image. Step 1 and Step 2 is applied repeatedly until no more conditions in Step 1 are satisfied.
 
(a) (b)  
(c) (d)
 
(e) (f) Figure 1. Binary images in (a), (c), (e) and skeleton of the image after (b) 10 iterations, (d) 10 iterations and (f) 35 iterations.
C Source Code Below there is only skeletonizing procedure. You can reach complete source code from here.
int Make_Skeleton(long width, long height, long max_color)
{
short cond_1, cond_2;
char File_Name[128];
unsigned char P1, P2, P3, P4, P5, P6, P7, P8, P9, NP1, SP1, x;
unsigned char c1, c2, c3, c4;
long i, j, k;
// prepare to binary image format
for(i=1;i<height;i++)
{
for(j=1;j<width;j++)
{
if (img_data[i][j] == 255)
s_tmp[i][j] = img_data[i][j] = 0;
else
s_tmp[i][j] = img_data[i][j] = 1;
}
}
// make the iskeleton of an image
k = 0;
cond_1 = 1; // erase counter for step 1
cond_2 = 2; // erase counter for step 2
while( (cond_1 != cond_2) && (k < step_count))
{
cond_2 = cond_1 = 0;
/////////////////////////////////
// Step 1 starts HERE ///////////
for(i=1;i<height-1;i++)
{
for(j=1;j<width-1;j++)
{
P1 = img_data[i][j];
P2 = img_data[i-1][j];
P3 = img_data[i-1][j+1];
P4 = img_data[i][j+1];
P5 = img_data[i+1][j+1];
P6 = img_data[i+1][j];
P7 = img_data[i+1][j-1];
P8 = img_data[i][j-1];
P9 = img_data[i-1][j-1];
// Condititon 1
NP1 = P2 + P3 + P4 + P5 + P6 + P7 + P8 + P9;
if ( (NP1 > 1) && (NP1 < 7))
c1 = 1;
else
c1 = 0;
// Condititon 2
c2 = 0;
if ( (P3 - P2) == 1)
c2++;
if ( (P4 - P3) == 1)
c2++;
if ( (P5 - P4) == 1)
c2++;
if ( (P6 - P5) == 1)
c2++;
if ( (P7 - P6) == 1)
c2++;
if ( (P8 - P7) == 1)
c2++;
if ( (P9 - P8) == 1)
c2++;
if ( (P2 - P9) == 1)
c2++;
if (c2 != 1) // c2 must be equal to 1.
c2 = 0;
else
c2 = 1;
// Condition 3
c3 = P2 * P4 * P6;
if (c3 == 1) // must be 0 to satisfy needs
c3 = 0; // so Step1 condition will not be true
else
c3 = 1; // yes. c3=0.
// Condition 4
c4 = P4 * ( P6 * P8);
if (c4 == 1) // must be 0 to satisfy needs
c4 = 0; // so Step1 condition will not be true
else
c4 = 1; // yes. c4=0.
if ( (c1 * c2 * c3 * c4) == 1 )
{
s_tmp[i][j] = 0; // erase it
cond_1++;
}
else
s_tmp[i][j] = P1;
}
}
// End of Step 1 ////////////////
/////////////////////////////////
/////////////////////////////////
// Step 2 starts HERE ///////////
for(i=1;i<height-1;i++)
{
for(j=1;j<width-1;j++)
{
P1 = s_tmp[i][j];
P2 = s_tmp[i-1][j];
P3 = s_tmp[i-1][j+1];
P4 = s_tmp[i][j+1];
P5 = s_tmp[i+1][j+1];
P6 = s_tmp[i+1][j];
P7 = s_tmp[i+1][j-1];
P8 = s_tmp[i][j-1];
P9 = s_tmp[i-1][j-1];
// Condititon 1
NP1 = P2 + P3 + P4 + P5 + P6 + P7 + P8 + P9;
if ( (NP1 > 1) && (NP1 < 7))
c1 = 1;
else
c1 = 0;
// Condititon 2
c2 = 0;
if ( (P3 - P2) == 1)
c2++;
if ( (P4 - P3) == 1)
c2++;
if ( (P5 - P4) == 1)
c2++;
if ( (P6 - P5) == 1)
c2++;
if ( (P7 - P6) == 1)
c2++;
if ( (P8 - P7) == 1)
c2++;
if ( (P9 - P8) == 1)
c2++;
if ( (P2 - P9) == 1)
c2++;
if (c2 != 1) // c2 must be equal to 1.
c2 = 0;
else
c2 = 1;
// Condition 3
c3 = P2 & ( P4 & P8);
if (c3 == 1) // must be 0 to satisfy needs
c3 = 0; // so Step1 condition will not be true
else
c3 = 1; // yes. c3=0.
// Condition 4
c4 = P2 & ( P6 & P8);
if (c4 == 1) // must be 0 to satisfy needs
c4 = 0; // so Step1 condition will not be true
else
c4 = 1; // yes. c4=0.
if ( (c1 & c2 & c3 & c4) == 1 )
{
img_data[i][j] = 0; // erase it
cond_2++; // increase by one
}
else
img_data[i][j] = P1;
}
}
// End of Step 2 ////////////////
/////////////////////////////////
// Write current step into file
Generate_File_Name(k, "step", File_Name);
for(i=1;i<height;i++)
{
for(j=1;j<width;j++)
{
if (img_data[i][j] == 1)
img_data[i][j] = 0;
else
img_data[i][j] = 255;
}
}
Put_PGM_Data(File_Name, width, height, max_color);
// Convert back to binary format
for(i=1;i<height;i++)
{
for(j=1;j<width;j++)
{
if (img_data[i][j] == 255)
img_data[i][j] = 0;
else
img_data[i][j] = 1;
}
}
k++;
}
// convert back to orijinal colors
for(i=1;i<height;i++)
{
for(j=1;j<width;j++)
{
if (img_data[i][j] == 1)
img_data[i][j] = 0;
else
img_data[i][j] = 255;
}
}
return 0;
}
References
[1] Arnaldo Florio, Francesco Berrilli, “A Skeletonizing Algorithm For Granulation And Supergranulation Cell Finding”, http://www.fisica.uniroma2.it/berrilli/soft.html, 1998, Italy.
|
Studies 
