Thread: Sequential Labeling Algorithm

I am trying to implement the Sequential Labeling Algorithm, which looks at a binary image and assigns a label to each image.

Code:

int rows = im -> getNRows(); 
int cols = im -> getNCols();  
char labels[rows][cols];

// fill labels array
for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
	 labels[i][j] = '*'

for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++){
       	  int current_pixel = im -> getPixel(i,j);	
		  
     	  // 1 = white, 0 = black

	  // A == white pixel && D has label (was scanned) -> A gets same label as D
	  if ((current_pixel == 1) && (labels[i-1][j-1] != '*'))
              labels[i][j] = labels[i-1][j-1];	 
	
	  // A == white pixel && B has label (was scanned) -> A gets same label as B
	  if ((current_pixel == 1) && (labels[i][j-1] != '*'))
              labels[i][j] = labels[i][j-1];

	  // A == white pixel && C has label (was scanned) -> A gets same label as C
	  if ((current_pixel == 1) && (labels[i-1][j] != '*'))
              labels[i][j] = labels[i-1][j];	

	  // B or C have no labels (bec new shape encountered) -> A gets new label
	  if ((labels[i][j-1] == '*') || (labels[i-1][j] == '*')) 
	     labels[i][j] = 'a';

	// B and C have different labels -> A gets either label
	if (labels[i][j-1] != labels[i-1][j]) 
              labels[i][j] = labels[i][j-1];
     }


// print array into text file
for (int i = 0; i < rows; i++){
      for (int j = 0; j < cols; j++)
	cout << labels[i][j];
  cout << endl;
  }

The problem is that print out does not represent the binary image, instead I get a row of * folowed by row of a folowed by a row of * folowed by a row of a ...



More on the Algorithm:
http://books.google.com/books?id=jpX...2oNxcbaYhIfAyw
pg. 69 - 71

>> char labels[rows][cols];
Does that work? I'd've thought you'd have to use new here.

I don't know if it matters, but wouldn't you want an if-elseif-elseif-elseif chain, rather than going through each case (it's possible that label[i][j] would get set four times, and I'm not sure that's what you want).

Actually, I think I know what it might be. You're looping from i, j = 0 to the number of rows and stuff. But when you're checking the pixels you're looking at i-1, j-1, which in the first iteration is -1 so you're going out of bounds.

So any idea on how to fix this, also I hard coded that the label is a, I need to fix this since the idea is that every shape gets a new label (a,b,c,d...).

Is it posible to add someting to char to change it to the next one. a + ?? becomes b, b + ?? becomes c ...
something like incrementing a number

Originally Posted by Suchy

So any idea on how to fix this, also I hard coded that the label is a, I need to fix this since the idea is that every shape gets a new label (a,b,c,d...).

Is it posible to add someting to char to change it to the next one. a + ?? becomes b, b + ?? becomes c ...
something like incrementing a number

1. You should probably assume an "invisible" unmarked row & column to the top & left of your picture (so if you would check an invalid spot, assume unmarked and go on).

2. You can do ++ with a letter just like any other integral type.

Thanks, now I finaly get something like this when printing out the labels array

Code:

--------------------------------------------------------
---------------------------------------------------aaa--
--bbb----------------------------------------------aaa--
--bbbbb--------------------------------------------aaa--
--bbbbb-------------------------------------------aaaa--
--bbbbb-------------------------------------------aaaa--
--bbbbbb------------------------------------------aaaa--
--bbbbbb------------------------------------------aaaa--
--bbbbbb-----------------------------------------aaaaa--
--bbbbbb-----------------------------------------aaaaa--
--bbbbbbb----------------------------------------aaaaa--
--bbbbbbb---------------------------------------aaaaaa--
--bbbbbbbb--------------------------------------aaaaaa--
--bbbbbbbb-------------------------------------aaaaaaa--
--bbbbbbbbb------------------------------------aaaaaaa--
--bbbbbbbbb-----------------------------------aaaaaaaa--
--bbbbbbbbbb---------------------------------aaaaaaaaa--
--bbbbbbbbbbb--------------------------------aaaaaaaaa--
--bbbbbbbbbbb-------------------------------aaaaaaaaaa--
--bbbbbbbbbbbb-----------------------------aaaaaaaaaaa--
--bbbbbbbbbbbbb---------------------------aaaaaaaaaaaa--
--bbbbbbbbbbbbbb-------------------------aaaaaaaaaaaaa--
--bbbbbbbbbbbbbbbb----------------------aaaaaaaaaaaaaa--
--bbbbbbbbbbbbbbbbb-------------------cccaaaaaaaaaaaaa--
--bbbbbbbbbbbbbbbbbbb---------------dddcccaaaaaaaaaaaa--
--bbbbbbbbbbbbbbbbbbbbb-----------eeedddcccaaaaaaaaaaa--
--bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeedddcccaaaaaaaaaa--
--bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeedddcccaaaaaaaaa--
--bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeedddcccaaaaaaaa--
--bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeedddcccaaaaaaa--
--bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeedddcccaaaaaa--
--bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeedddcccaaaaa--
--bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeedddcccaaaa--
--bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeedddcccaaa--
--bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeedddcccaa--
--bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeedddccca--
--bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeedddccc--
--------------------------------------------------------

So what would be a way to turn all these different labels into 1, using a a second loop?

Well, the algorithm says that if you're in the case where upper neighbor and left neighbor are both labeled, but differently labeled, you need to "make a note" that they are the same. So you really just have to decide what data structures these "notes" are going to be. An associative array is probably the obvious answer, in the "I don't want to think about it" sense, but you may want to design your own that can handle multiple letters in the same equivalence class (like a through e in your example above).

If you do use an associative array, be sure to be careful about how you replace letters; for instance if you mark that b's should be replaced by a's, and then that c's should be replaced by b's, you need to make sure that c's actually end up as a's.

That part about "taking a note "in the book got me. So what should hash (associative array) contain?

I don't get that part, could you explain it little mor or give me na example.

Thanks for all the help

The obvious hash would be equivalent[left_label]=up_label (or something similar).