Sequential Labeling Algorithm

This is a discussion on Sequential Labeling Algorithm within the C++ Programming forums, part of the General Programming Boards category; I am trying to implement the Sequential Labeling Algorithm, which looks at a binary image and assigns a label to ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Location
    Kansas City
    Posts
    76

    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

  2. #2
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,262
    >> char labels[rows][cols];
    Does that work? I'd've thought you'd have to use new here.

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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).

  4. #4
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,262
    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.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Location
    Kansas City
    Posts
    76
    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

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Suchy View Post
    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.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Location
    Kansas City
    Posts
    76
    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?

  8. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    2,020
    Quote Originally Posted by twomers View Post
    >> char labels[rows][cols];
    Does that work? I'd've thought you'd have to use new here.
    If I recall correctly, this is a compiler extension.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Location
    Kansas City
    Posts
    76
    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

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    The obvious hash would be equivalent[left_label]=up_label (or something similar).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sequential file program
    By needhelpbad in forum C Programming
    Replies: 80
    Last Post: 06-08-2008, 01:04 PM
  2. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21