Connected Component Labeling

Connected Component Labeling

Connected Component Labeling (CCL) is one of the important stages for many image analysis systems.

CCL is the component separation process for binary images (there is only two colors, 1 for black and 0 for white or wise verse). This method scans the image and groups adjacent pixels according to connection property. If every group expresses a shape, there are shapes as many as groups. After grouping adjacent pixels, groups are painted varied colors expressing the difference.

Samples for CCL

(a) (b)

Figure 1. (a) original binary image, (b) connected components painted in different color

(a) (b)

Figure 2. (a) original binary image, (b) connected components

(a) (b)

Figure 3. (a) original binary image, (b) connected components

C Source Code

Below there is only connected component labeling procedure. The complete program can be found here. Note that this procedure is little buggy. If you want to use it please be careful.

int Connected_Com_Label(long **img_data, long width, long height)
{
   long i, j, k, z, max, used_num[256]={0};
   long mx, pix[9];

   // prepare to binary image format
   for(i=0;i<height;i++)
   {
               for(j=0;j<width;j++)
               {
                          if (img_data[i][j] == 255)
                                      img_data[i][j] = 0;
                          else
                                      img_data[i][j] = 1;
               }
   }

   z = 0;
   max = 2;
   for(i=1;i<height-1;i++)
   {
      for(j=1;j<width-1;j++)
      {
          pix[0] = img_data[i][j];
          pix[1] = img_data[i-1][j];
          pix[2] = img_data[i-1][j+1];
           pix[3] = img_data[i][j+1];
          pix[4] = img_data[i+1][j+1];
          pix[5] = img_data[i+1][j];
          pix[6] = img_data[i+1][j-1];
          pix[7] = img_data[i][j-1];
          pix[8] = img_data[i-1][j-1];
          if (pix[0] == 1)
          {
             // find maximum of pixeles.
             mx = 0;
             for(k=1;k<9;k++)
             {
               if (pix[k] > mx)
                  mx = pix[k];
             }
             if (mx == 1) // if neighbours are equal to ONE, set
                          // it to max and increase max by ONE
             {
                  img_data[i][j] = max;
                  max++;
             }
             else
             {
                pix[0] = 0;
                QuickSort(pix,0, 8);
                k=8;
                while((k>0) && (pix[k] != 1))
                   k--;
                if (k < 8)
                   img_data[i][j] = pix[k+1];
                else
                   img_data[i][j] = pix[k];
             }
         }
     }
   }

   k = 0;
   for(i=0;i<height;i++)
   {
      for(j=0;j<width;j++)
      {
        mx = img_data[i][j];
        if (mx > 0)
        {
          if (not_in_array(mx, used_num, k))
          {
             used_num[k] = mx;
             k++;
          }
        }
      }
   }

   for(i=0;i<height;i++)
   {
      for(j=0;j<width;j++)
      {
         if (img_data[i][j] == 10)
            img_data[i][j] = 0;
         else if (img_data[i][j] == 9)
            img_data[i][j] = 25;
         else if (img_data[i][j] == 8)
            img_data[i][j] = 50;
         else if (img_data[i][j] == 7)
            img_data[i][j] = 75;
         else if (img_data[i][j] == 6)
            img_data[i][j] = 100;
         else if (img_data[i][j] == 5)
            img_data[i][j] = 125;
         else if (img_data[i][j] == 4)
            img_data[i][j] = 100;
         else if (img_data[i][j] == 3)
            img_data[i][j] = 150;
         else if (img_data[i][j] == 2)
            img_data[i][j] = 200;
         else if (img_data[i][j] == 1)
            img_data[i][j] = 225;
         else
            img_data[i][j] = 255;
      }
   }

   return 0;
}

References

[1] Robert Fisher, Simon Perkins, Ashley Walker, Erik Wolfart, “HYPERMEDIA IMAGE PROCESSING REFERENCE”, http://www.dai.ed.ac.uk/HIPR2/, 2002.

[2] Jung-Me Park, Carl G. Looney, Hui-Chuan Chen, “Fast Connected Component Labeling Algorithm Using A Divide and Conquer Technique”.