MattG MattG - 11 days ago 6
Java Question

Connected components labelling of point objects over estimating number of objects

I am trying to implement the 8 connectivity connected components labelling algorithm over an image where certain points are highlighted to identify regions of connected highlighted points.

My code seems to be working except that the amount of objects is massively overestimated, for example in an image where 500 points are highlighted it might say that there are 2000 objects.

My code so far (for the first pass of the algorithm) is:

public int[][] connectedComp(int[][] array){ // Connected Compoent Labling method
int nextlabel = 1;
for(int v =y1; v<y1 + height;v++){
for(int u = x1;u<x1 + width;u++){
if(array[v][u]==1){
for (int j=-1; j<=1; j++){
for (int i=-1; i<=1; i++){
if(v+j>=0 && u+i>=0){
if(array[v+j][u+i]>0){

array[v][u]= nextlabel;
}
else{
array[v][u] = nextlabel++;
}
}
}
}
}
}
}
return array;
}


X1 and Y1 are the starting coordinates of the ROI I am interested in and width and height are the dimensions of said ROI.

Can anyone see what might be causing this?

Edit

I changed my code to only compare the pixels I had already visited and also changed the structure slightly. It works better now, if not perfectly.

Here is the updated code:

public int[][] connectedComp(int[][] array){ // Connected Compoent Labling method
int nextlabel = 1;
for(int v =y1; v<y1 + height;v++){
for(int u = x1;u<x1 + width;u++){
if(array[v][u]==1){
if(v-1>=0 && u-1>=0){
if(array[v-1][u-1]!=0){
array[v][u]= nextlabel;
}
if(array[v-1][u]!=0){
array[v][u]= nextlabel;
}
if(array[v-1][u+1]!=0){
array[v][u]= nextlabel;
}
if(array[v][u-1]!=0){
array[v][u]= nextlabel;
}
else{
array[v][u] = nextlabel++;
}
}
}
}
}
return array;
}

Answer

I think your problem is in your inner loop.

Lets say you have a single pixel that is surrounded by zeros

for (int j=-1; j<=1; j++)
{
   for (int i=-1; i<=1; i++)
   {
      if(v+j>=0 && u+i>=0)
      {
         if(array[v+j][u+i]>0)
         {
            array[v][u]= nextlabel;
         }
         else{
            array[v][u] = nextlabel++;
         }
      }
   }
}

for all of you inner loop you will keep increasing the label because the pixel is surrounded by zeros. So if nextlabel = someValue in the begining of the loop in the end it will be equal to someValue + 9.

Comments