[KirosXannon]

Hello dream.in.code community,

I'm having a problem figuring out how to translate this algorithm into code. It's a programming project for class and I'm stuck on a particular section. It's called the 8-connected component algorithm and is part of an image processing class. Here's the basic idea:

We have a binary image made up of 1's and 0's. The task is to identify separate objects in the image and correctly label them differently. In order to do this, we use a three step algorithm.

The binary image is stored into a 2-D array. Scan the image from left-to-right and top-to-bottom.

If a pixel[i][j] > 0, there are 3 possible cases,

Case 1: a b c (sorry, x is supposed to be under b, and d is supposed to be under a, same with the others)
d x
where x is the specific pixel the 2D array is currently on, and the surrounding letters are what pixels you scan.

(For example, if x is pixel[i][j], then a = pixel[i-1][j-1], b = pixel[i-1][j], c = pixel[i-1][j+1] and d = pixel[i][j-1]

If a = b = c = d = 0, then you give that pixel a new label.(labels are just integers from 1 -> x)

Case 2: a b c
d x
Some of (a,b,c,d) != 0, but all the non-zeros are equal. In this case, you simply give pixel x the same label that a,b,c or d has because they are all the same.

Case 3: a b c
d x
Some of (a,b,c,d) != 0, but they may have different labels from each other. In this case, you take the minimum value of the label on them, and give the same one to pixel x.


This is all for the first pass. After labeling the entire image this way, you go onto the second pass where you scan the image from right-to-left and bottom-to-top, doing basically the same thing, but instead checking the other half of the "L" that makes up the square around pixel x. After the second pass, the third pass then scans the image once more and checks the equivalency table you would use to keep track of labels. As you go through the image, the purpose of giving the smallest label to the current pixel you're on is to then show that the higher values are equal to the smaller values. Basically by the end, it differentiates between unique objects, and whole, connected objects.



Now, onto the part I'm having trouble with. I'm finding it difficult with translating case 2 and case 3 into code.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;


public class Eight_CC {

	/**
	 * @param args
	 * @throws FileNotFoundException 
	 */
	public static void main(String[] args) throws FileNotFoundException {
		int rowNum = 60;
		int colNum = 60;
		int min = 0;
		int max = 1;
		int row = 0;
		int[] labelA = new int[16];
		int label = 0;
		//Array that stores the original image
		int[][] origArray = new int[rowNum][colNum];
		//Array that will store the updated image
		int[][] outImg = new int[rowNum][colNum];
		
		File file;
		Scanner scanner;
		
		file = new File("connected_input");
		
		scanner = new Scanner(file);
		scanner.nextLine();
		while(scanner.hasNextLine()){
			String line = scanner.nextLine();
			String token[] = line.split(" ");
			//Read the image from file
			for(int j = 0; j < token.length; j++){
				origArray[row][j] = Integer.parseInt(token[j]);
			}
			row++;
		}
		//Nested for loop to begin scanning from L-R and T-B
		for(int i = 0; i < rowNum; i++){
			for(int j = 0; j < colNum; j++){
				if(origArray[i][j] > 0){
					//case 1:
					if(origArray[i-1][j-1] == origArray[i-1][j] == origArray[i-1][j+1] == 
							origArray[i][j-1] == 0){
						label++;
						outImg[i][j] = label;
						labelA[label] = label;
					}
					//case 2:
					else if((origArray[i-1][j-1] > 0 || origArray[i-1][j] > 0 || 
							origArray[i-1][j+1] > 0|| 
							origArray[i][j-1]) > 0){ 
						//give it the same label as all of these
						outImg[i][j] = 
					}
					//case 3:
					else if(!(origArray[i-1][j-1] == origArray[i-1][j] == origArray[i-1][j+1] == 
							origArray[i][j-1])){
						//Do some comparison and find the smallest label and give it that.
					}
				}
					
			}
		}

	}

}

origArray[][] is the 2D array that takes the base binary image that's read from a file using Scanner. A second 2D array stores the updating image with the labels on the object locations. For example, you would see one object as "11111" filled in, while another may be "2222" or "33333333" as a shape on the picture. Label is an array because you have to keep track of what numbers are equivalent to the others so you know which shapes are connected.

This section right here displays the code for case 2:

else if((origArray[i-1][j-1] > 0 || origArray[i-1][j] > 0 || 
							origArray[i-1][j+1] > 0|| 
							origArray[i][j-1]) > 0){ 
						//give it the same label as all of these
						outImg[i][j] = 
					}

I figured out how to check to make sure at least one of the values in the locations to check is not equal to 0, but I'm at a loss on how to translate the sentence "If all non-zero values are equal" into a boolean statement. It has to do two things, it has to check to make sure that at least one of the surrounding locations is not equal to zero, then it has to make sure that all of the non-zero values are equal. Case 3 is also the same, except it has to check to see if the non-zero values are different.

Also, I know some people will probably mention this, but it does have to check to make sure that they're different on the first pass even though it's binary because I also have to do this with an image supposing it's not binary, and instead made up of different numbers for the "solid" object locations. Also, the labels will be different on the second pass.


Oh, this is also unrelated to the current algorithmic problem, but for some reason this line

if(origArray[i-1][j-1] == origArray[i-1][j] == origArray[i-1][j+1] == 
							origArray[i][j-1] == 0){

gives me a "the operator == is undefined for the argument type(s) boolean, int.

I've looked up and down the code and I'm not sure what's wrong. Same with the other if statements underneath the "if(origArray[i][j] > 0)". That one works perfectly fine, but the ones inside of that if statement do not.

I would appreciate any advice about how to code in case 2, and why I'm getting those operator undefined errors.

Attached is the image file I'm reading into the program.

Thank you.

Attached File(s)

•  connected_input.txt (7.04K)
  Number of downloads: 17

[KirosXannon]

If anything you really don't need to read through that entire summary, I just put it there in case it would help with understanding what I have to do.

I really just need to know how to translate "if a,b,c and d are not equal to zero, and all non-zero values are equal to each other" into code.

Thanks.

[Vinski]

KirosXannon, on 01 October 2012 - 07:15 AM, said:

...I really just need to know how to translate "if a,b,c and d are not equal to zero...

To check if a variable is not equal to zero, do this:

if(variable != 0){
   // Your code here.
}

KirosXannon, on 01 October 2012 - 07:15 AM, said:

...and all non-zero values are equal to each other" into code...

To check if integer variables equal to integer variables, do this:

if(variable1 == variable2){
   // Your code here.
}

But, it's different with strings; Here is the way to do it with strings:

if(string1.equals(string2)){
   // Your code here.
}

[KirosXannon]

Vinski, on 01 October 2012 - 07:40 AM, said:

KirosXannon, on 01 October 2012 - 07:15 AM, said:

...I really just need to know how to translate "if a,b,c and d are not equal to zero...

To check if a variable is not equal to zero, do this:

if(variable != 0){
   // Your code here.
}

KirosXannon, on 01 October 2012 - 07:15 AM, said:

...and all non-zero values are equal to each other" into code...

To check if integer variables equal to integer variables, do this:

if(variable1 == variable2){
   // Your code here.
}

But, it's different with strings; Here is the way to do it with strings:

if(string1.equals(string2)){
   // Your code here.
}

I understand how to check for all of those instances, but it's different because I don't know the value of the variables beforehand. a,b,c and d are unknown. Suppose only two of them are not zero, how do I check that the two that are non-zero are equal to each other? Also suppose that there's only one that's not equal to zero, how do I say as well that this is also fine and nothing needs to be checked because it's the only one that's not zero?

[Vinski]

KirosXannon, on 01 October 2012 - 07:47 AM, said:

I understand how to check for all of those instances, but it's different because I don't know the value of the variables beforehand. a,b,c and d are unknown. Suppose only two of them are not zero, how do I check that the two that are non-zero are equal to each other? Also suppose that there's only one that's not equal to zero, how do I say as well that this is also fine and nothing needs to be checked because it's the only one that's not zero?

First, make two integer arrays (which have 4 (<- number of variables) slots)) and then set first integer array's values to variables a, b, c and d. After that, make a for loop which scans through the array and if a number is not equal to zero, it puts the variable in the second array. When that is over, you scan through the second array and check if numbers are equal to each other. In code it would be something like this:

public static void main(String[] args) {
		int a = 0;
		int b = 7;
		int c = 0;
		int d = 9;
		int[] integers = {a, b, c, d};
		int[] notZeros = new int[4];
		
		for(int i = 0; i < integers.length; i++){
			if(integers[i] != 0)
				notZeros[i] = integers[i];
		}
		
		for(int i = 0; i < notZeros.length; i++){
			int current = integers[i];
			if(current == integers[0]){
				if(i != 0){
					// Your code.
				}else break;
			}
			
			if(current == integers[1]){
				if(i != 1){
					// Your code.
				}else break;
			}
			
			if(current == integers[2]){
				if(i != 2){
					// Your code.
				}else break;
			}
			
			if(current == integers[3]){
				if(i != 3){
					// Your code.
				}else break;
			}
		}
	}

Please excuse me. I've made a mistake there. This is the right way for the last for loop:

		for(int i = 0; i < notZeros.length; i++){
			int current = notZeros[i];
			if(current == notZeros[0]){
				if(i != 0){
					// Your code.
				}else break;
			}
			
			if(current == notZeros[1]){
				if(i != 1){
					// Your code.
				}else break;
			}
			
			if(current == notZeros[2]){
				if(i != 2){
					// Your code.
				}else break;
			}
			
			if(current == notZeros[3]){
				if(i != 3){
					// Your code.
				}else break;
			}
		}

I'm so sorry, but I cannot edit my posts for some reason. I accidently put else break at the end of each if statement. This could also be done in an easier way. Argh, I failed a bit.

Anyway, just remove that else break;.

[KirosXannon]

Vinski, on 01 October 2012 - 08:14 AM, said:

KirosXannon, on 01 October 2012 - 07:47 AM, said:

I understand how to check for all of those instances, but it's different because I don't know the value of the variables beforehand. a,b,c and d are unknown. Suppose only two of them are not zero, how do I check that the two that are non-zero are equal to each other? Also suppose that there's only one that's not equal to zero, how do I say as well that this is also fine and nothing needs to be checked because it's the only one that's not zero?

First, make two integer arrays (which have 4 (<- number of variables) slots)) and then set first integer array's values to variables a, b, c and d. After that, make a for loop which scans through the array and if a number is not equal to zero, it puts the variable in the second array. When that is over, you scan through the second array and check if numbers are equal to each other. In code it would be something like this:

public static void main(String[] args) {
		int a = 0;
		int b = 7;
		int c = 0;
		int d = 9;
		int[] integers = {a, b, c, d};
		int[] notZeros = new int[4];
		
		for(int i = 0; i < integers.length; i++){
			if(integers[i] != 0)
				notZeros[i] = integers[i];
		}
		
		for(int i = 0; i < notZeros.length; i++){
			int current = integers[i];
			if(current == integers[0]){
				if(i != 0){
					// Your code.
				}else break;
			}
			
			if(current == integers[1]){
				if(i != 1){
					// Your code.
				}else break;
			}
			
			if(current == integers[2]){
				if(i != 2){
					// Your code.
				}else break;
			}
			
			if(current == integers[3]){
				if(i != 3){
					// Your code.
				}else break;
			}
		}
	}

Please excuse me. I've made a mistake there. This is the right way for the last for loop:

		for(int i = 0; i < notZeros.length; i++){
			int current = notZeros[i];
			if(current == notZeros[0]){
				if(i != 0){
					// Your code.
				}else break;
			}
			
			if(current == notZeros[1]){
				if(i != 1){
					// Your code.
				}else break;
			}
			
			if(current == notZeros[2]){
				if(i != 2){
					// Your code.
				}else break;
			}
			
			if(current == notZeros[3]){
				if(i != 3){
					// Your code.
				}else break;
			}
		}

I'm so sorry, but I cannot edit my posts for some reason. I accidently put else break at the end of each if statement. This could also be done in an easier way. Argh, I failed a bit.

Anyway, just remove that else break;.

Godd I feel stupid now it was such a simple solution. Thank you for your help!

[Vinski]

You're welcome.