00001
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
00030
00031
00032
00033
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
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 }