Main Page   Modules   Class Hierarchy   Compound List   File List   Compound Members   Related Pages   Examples  

ConnectedComponents.cpp

00001 /* Copyright (c) 2001 C. Grigorescu */
00002 
00003 #include <stdio.h>
00004 #include <math.h>
00005 #include "ByteImage.h"
00006 #include "IntImage.h"
00007 #include "ConnectedComponents.h"
00008 
00009 int ConnectedComponents(IntImage &img, CONN_TYPE connectivity, IntImage &out)
00010 {
00011   out = img;
00012   int nr_comp = ConnectedComponents(out, connectivity);
00013   return (nr_comp);
00014 }
00015 
00016 int ConnectedComponents(ByteImage &img, CONN_TYPE connectivity, IntImage &out)
00017 {
00018   out.makeImage(img.getWidth(), img.getHeight());
00019   for (int i=0;i<img.getHeight();i++)
00020     for (int j=0;j<img.getWidth();j++)
00021       out[i][j] = img[i][j];
00022   int nr_comp = ConnectedComponents(out, connectivity);
00023   return (nr_comp);                                                             
00024 }
00025 
00026 int ConnectedComponents(IntImage &img, CONN_TYPE connectivity = FOUR)
00027 {
00028   /* 
00029   Computes "Connected Components" using Tarjan's Union-Find algorithm;
00030   the result is returned in the same buffer as gray_level image with values
00031   equal to the label of the component.
00032 
00033   Returns: the number of connected components */
00034 
00035   int l, p, r, curlab=1;
00036   int i, j, n_up, n_left, n_right;
00037   int lab[img.getSize()];
00038   int *pixels = img.getPixels();
00039 
00040   /* Start Tarjan's algorithm */
00041   int w = img.getWidth();
00042   int h = img.getHeight();
00043 
00044   for (i=0; i<h; i++)
00045     for (j=0; j<w; j++){
00046       if (pixels[i*w+j] >= 0) {
00047       p = pixels[i*w+j];
00048       l = i*w+j;
00049       lab[l] = l;
00050       
00051       n_up = i-1;
00052       if ((n_up >= 0) && (pixels[n_up*w+j] == p))
00053         Union(l, n_up*w+j, lab);
00054       
00055       n_left = j-1;
00056       if ((n_left >= 0) && (pixels[i*w+n_left] == p))
00057         Union(l, i*w+n_left, lab);
00058       
00059       n_right = j+1;
00060       if (connectivity == EIGHT) {
00061         if ((n_right < w) && (n_up >= 0) && 
00062             (pixels[n_up*w+n_right] == p))
00063           Union(l, n_up*w+n_right, lab);
00064         if ((n_left >= 0) && (n_up >= 0) && 
00065             (pixels[n_up*w+n_left] == p))
00066           Union(l, n_up*w+n_left, lab);
00067       }
00068     }      
00069       else
00070         lab[i*w+j] = 0;
00071     }
00072   for (i=0; i<h; i++)
00073     for (j=0; j<w; j++){
00074       r = lab[i*w+j];
00075       if (r == i*w+j) {
00076         pixels[i*w+j] = curlab;
00077         lab[i*w+j] = curlab++;
00078       } else { 
00079         lab[i*w+j] = lab[r];
00080         pixels[i*w+j] = lab[r];
00081       }
00082     }
00083   return (curlab-1);
00084 }
00085 
00086 int Root(int r, int *lab, int size_x, int size_y)
00087 {
00088   int p;
00089 
00090   p = lab[(r/size_x)*size_x+(r%size_x)];
00091   while (p != r) {
00092     r = p;
00093     p = lab[(r/size_x)*size_x+(r%size_x)];
00094   }
00095   return p;
00096 }
00097  
00098 int FindRoot(int r, int *lab)
00099 {
00100   if ( r != lab[r] )
00101     lab[r] = FindRoot(lab[r], lab);
00102   return lab[r];
00103 }
00104 
00105 void Union(int x, int y, int *lab)
00106 {
00107   int r0, r1;
00108   r0 = FindRoot(x, lab);
00109   r1 = FindRoot(y, lab);
00110   if (r0 > r1)  
00111     lab[r0] = r1;
00112   else 
00113     lab[r1] = r0;
00114 }