How do I merge the labels in connected component labeling

Question

Hi I have to find out how many objects I have in an image.

http://en.wikipedia.org/wiki/Connected-component_labeling

I need help with storing the equivalence between neighbours and also the second pass. This pass gives me 173 or so objects and is the first pass. I would like to store equivalences (when they occur) and then in the second pass to be able to just replace the corresponding equivalences with the lowest equivalent value.

Answer 1

The equivalence table can be implemented using a HashMap. Each time you find a label that is equivalent to another label, just add that relation to the hash map.

final Map<Integer, Integer> equivalenceTable = new HashMap<>();

So whenever you find two labels that are equal, just put them in the equivalence table.

private void storeEquivalence(final Integer label0, final Integer label1, final Map<Integer, Integer> table) {
  if (table.keySet().contains(label0)) {
    table.put(label1, table.get(label0));
  }
  else if (table.keySet().contains(label1)) {
    table.put(label0, table.get(label1));
  }
  else {
    table.put(label0, label1);
  }
}

So when you identify that region[x-1][y] and region[x][y-1] are equal, you should check if the labels are different (they should be) and update the equivalence table if the are by calling

 storeEquivalence(region[x-1][y], region[x][y-1], equivalenceTable);

Then in the second pass you simply replace each label that has a value in the equivalence table.

for (int x = 1; x < imageTwo.getWidth(); x++) {
  for (int y =1; y < imageTwo.getHeight(); y++) {
    if (equivalenceTable.keySet().contains(region[x][y])) {
      region[x][y] = equivalenceTable.get(region[x][y]);
    }  
  }
}