Image-grouping using bit matrices

Question

It might be easier to read the explanation of what I was trying to do, and implement it a completely different way, rather than go through the code. But the code does what I want it to do, just nowhere near any measurable efficiency.

This started off as an assignment that I got finished, but I know there has to be a decent amount of better ways to make this code work

The goal of this code is to take a matrices of 1's and 0's, and go through and any nodes (that are 1's) that are connected to the left, right, up, or down (no diagonals), to change to different numbers. Each group, the number goes up by one.

For example:

1 1 0 0 1 1 1
1 0 0 0 0 0 0
1 1 1 0 1 0 1
1 0 0 0 1 1 1
1 0 1 0 1 1 1
1 1 0 0 0 0 0
1 0 0 0 0 1 1 

would become:

2 2 0 0 3 3 3
2 0 0 0 0 0 0
2 2 2 0 4 0 4
2 0 0 0 4 4 4
2 0 5 0 4 4 4
2 2 0 0 0 0 0
2 0 0 0 0 6 6

Here is my semi-verbal explanation of what the code does:

What my current code does, is works through this in 2 phases. First it goes through and finds the first 1, and changes it to 2, and changes every number to the left and right of that (assuming they are 1's) to 2's. And continues to work its way through.

After that, it goes through again, and finds every 2, and changes each number to the left, right, and down from that 2, to a 2 also (if it's not 0). And repeats that until it finds no more numbers connected to a 2. Then increments, and does that to 3's, and so on.

I know there has to be a simple way to do this recursively, and I've tried, but it's been a pretty big failure for me. Any help or insight would be greatly appreciated.

package imagegrouping;
public class ImageGrouping {
 public static void main(String[] args) {
 int [][] originalMap = new int[][]{
 {1, 1, 0, 0, 1, 1, 1},
 {1, 0, 0, 0, 0, 0, 0},
 {1, 1, 1, 0, 1, 0, 1},
 {1, 0, 0, 0, 1, 1, 1},
 {1, 0, 1, 0, 1, 1, 1},
 {1, 1, 0, 0, 0, 0, 0},
 {1, 0, 0, 0, 0, 1, 1}
 };
 int currentNumber = 2;
 //loop for rows
 for(int i = 0; i < 7; i++)
 {
 //loop for columns
 for(int j = 0; j < 7; j++)
 {
 if(originalMap[i][j] == 1)
 {
 originalMap[i][j] = currentNumber;
 //check each number to right, if 1, make currentNumber
 for(int k = j+1; k < 7; k++)
 { 
 if(originalMap[i][k] == 1)
 {
 originalMap[i][k] = currentNumber;
 }
 else{break;}
 }//end checking right
 //check each number below, if 1, make currentNumber
 for(int l = i+1; l < 7; l++)
 {
 if(originalMap[l][j] == 1)
 {
 originalMap[l][j] = currentNumber;
 }
 else{break;}
 }//end checking below
 currentNumber++;
 }
 }//close loop for columns
 }//close loop for rows
 int changedNumber = 0;
 //int tempNumber = 2;
 for(int tempNumber = 2; tempNumber < 20; tempNumber++)
 {
 //start loop for rows
 for(int i = 0; i < 7; i++)
 {
 //start loop for columns
 for(int j = 0; j < 7; j++)
 {
 //find all tempNumbers, and check all around them to see if they have an adjacent node that should be the same number as them.
 if(originalMap[i][j] == tempNumber)
 {
 //if node is at top left corner, only check down and right to stay in bounds
 if(i == 0 && j == 0)
 {
 //check down
 checkDown(originalMap, i, j, changedNumber, tempNumber);
 //check right
 checkRight(originalMap, i, j, changedNumber, tempNumber);
 }
 //else if node is in bottom left corner, only check up and right, to stay in bounds
 else if(i == 6 && j == 0)
 {
 //check up
 checkUp(originalMap, i, j, changedNumber, tempNumber);
 //check right
 checkRight(originalMap, i, j, changedNumber, tempNumber);
 }
 //else if node is in bottom right corner, only check up and left, to stay in bounds
 else if(i == 6 && j == 6)
 {
 //check up
 checkUp(originalMap, i, j, changedNumber, tempNumber);
 //check left
 checkLeft(originalMap, i, j, changedNumber, tempNumber);
 tempNumber++;
 }
 //else if node is in top right corner only check left and bottom to stay in bounds
 else if(i == 0 && j == 6)
 {
 //check down
 checkDown(originalMap, i, j, changedNumber, tempNumber);
 //check left
 checkLeft(originalMap, i, j, changedNumber, tempNumber);
 }
 //else if any other case of node being on top row, don't check up, to stay in bounds
 else if(i == 0)
 {
 //might not need since first step goes through all downs.
 //check down
 checkDown(originalMap, i, j, changedNumber, tempNumber);
 //left
 checkLeft(originalMap, i, j, changedNumber, tempNumber);
 //check right
 checkRight(originalMap, i, j, changedNumber, tempNumber);
 }
 //else if node is on left line, don't check left, to stay in bounds
 else if(j == 0)
 {
 //check right
 checkRight(originalMap, i, j, changedNumber, tempNumber);
 //check up 
 checkUp(originalMap, i, j, changedNumber, tempNumber);
 //check down
 checkDown(originalMap, i, j, changedNumber, tempNumber);
 }
 //else if any node is on the right column, don't check right to stay in bounds
 else if(j == 6)
 {
 //check up
 checkUp(originalMap, i, j, changedNumber, tempNumber);
 //check down
 checkDown(originalMap, i, j, changedNumber, tempNumber);
 //check left
 checkLeft(originalMap, i, j, changedNumber, tempNumber);
 }
 //else if any node is on bottom row, don't check down, to stay in bounds
 else if(i == 6)
 {
 //check up
 checkUp(originalMap, i, j, changedNumber, tempNumber);
 //check left
 checkLeft(originalMap, i, j, changedNumber, tempNumber);
 //check right
 checkRight(originalMap, i, j, changedNumber, tempNumber);
 }
 //any other cases, check up down left right.
 else
 {
 //check up
 checkUp(originalMap, i, j, changedNumber, tempNumber);
 //down,
 checkDown(originalMap, i, j, changedNumber, tempNumber);
 //check left,
 checkLeft(originalMap, i, j, changedNumber, tempNumber);
 //check right
 checkRight(originalMap, i, j, changedNumber, tempNumber);
 }
 }
 }//end loop for columns
 }//end loop for rows
 }
 int finalSort = 2;
 int numberCheck = 0;
 for(int i = 0; i < 7; i++)
 {
 for(int j = 0; j < 7; j++)
 {
 if(originalMap[i][j] > finalSort && originalMap[i][j] != 0)
 {
 numberCheck = originalMap[i][j];
 for(int x = 0; x < 7; x++)
 {
 for(int y = 0; y < 7; y++)
 {
 if(originalMap[x][y] == numberCheck)
 {
 originalMap[x][y] = finalSort + 1;
 }
 }
 }finalSort++;
 }
 }
 }
 //print array
 printArray(originalMap);
 }
 //check right method
 public static void checkRight(int[][] originalMap, int i, int j, int changedNumber, int tempNumber)
 {
 if(originalMap[i][j+1] != tempNumber && originalMap[i][j+1] != 0)
 {
 //if the number below tempNumber == something besides tempNumber or 0, use changedNumber
 changedNumber = originalMap[i][j+1];
 //now find all changedNumbers, and change them to tempNumber
 for(int x = 0; x < 7; x++)
 {
 for(int y = 0; y < 7; y++)
 {
 if(originalMap[x][y] == changedNumber)
 {
 originalMap[x][y] = tempNumber;
 }
 }
 }
 }
 }
 //check left method
 public static void checkLeft(int[][] originalMap, int i , int j, int changedNumber, int tempNumber)
 {
 if(originalMap[i][j-1] != tempNumber && originalMap[i][j-1] != 0)
 {
 //if the number below tempNumber == something besides tempNumber or 0, use changedNumber
 changedNumber = originalMap[i][j-1];
 //now find all changedNumbers, and change them to tempNumber
 for(int x = 0; x < 7; x++)
 {
 for(int y = 0; y < 7; y++)
 {
 if(originalMap[x][y] == changedNumber)
 {
 originalMap[x][y] = tempNumber;
 }
 }
 }
 }
 }
 //Check up method
 public static void checkUp(int[][] originalMap, int i , int j, int changedNumber, int tempNumber)
 {
 if(originalMap[i-1][j] != tempNumber && originalMap[i-1][j] != 0)
 {
 //if the number below tempNumber == something besides tempNumber or 0, use changedNumber
 changedNumber = originalMap[i-1][j];
 //now find all changedNumbers, and change them to tempNumber
 for(int x = 0; x < 7; x++)
 {
 for(int y = 0; y < 7; y++)
 {
 if(originalMap[x][y] == changedNumber)
 {
 originalMap[x][y] = tempNumber;
 }
 }
 }
 }
 }
 public static void checkDown(int[][] originalMap, int i , int j, int changedNumber, int tempNumber)
 {
 if(originalMap[i+1][j] != tempNumber && originalMap[i+1][j] != 0)
 {
 //if the number below tempNumber == something besides tempNumber or 0, use changedNumber
 changedNumber = originalMap[i+1][j];
 //now find all changedNumbers, and change them to tempNumber
 for(int x = 0; x < 7; x++)
 {
 for(int y = 0; y < 7; y++)
 {
 if(originalMap[x][y] == changedNumber)
 {
 originalMap[x][y] = tempNumber;
 }
 }
 }
 }
 }
 //method to print array
 public static void printArray(int[][] myArray) {
 for(int x = 0; x < 7; x++)
 {
 for(int y = 0; y < 7; y++)
 {
 System.out.print(myArray[x][y]);
 System.out.print(" ");
 }
 System.out.print("\n");
 }
 }
}

Answer 1

I think your solution, and also the one proposed by Claudiordgz, are overkill.

You mentioned recursion in your question, and, recursion is the 'simple' solution to this problem.

problem description:

The goal of this code is to take a matrices of 1's and 0's, and go through and any nodes (that are 1's) that are connected to the left, right, up, or down (no diagonals), to change to different numbers. Each group, the number goes up by one

You can narrow this problem down in to four stages:

1. Set up a 'region counter', starting at 2
2. Scan the matrix for a 1
3. When you find a 1, recursively join it to all of it's 1-value neighbours, setting them all to the region-counter. You only need to look at 1-value'd neighbours.
4. When you have completed the recursive join, increment the region-counter, and continue scanning for 1's.

You do have a problem in your code that you have the 'magic-number' 7 embedded in your code. I have copied/pasted your code, and I have left the magic values in the printArray() method. Compare that with the other methods, and see how it can be done...

I have also split your main method in to different methods, so the logic is more discrete.

When you put it all together with a recursive method that 'handles' the out-of-bounds cases, it all looks pretty simple:

public class ImageGrouping {
 public static void main(String[] args) {
 int[][] originalMap = new int[][] {
 { 1, 1, 0, 0, 1, 1, 1 },
 { 1, 0, 0, 0, 0, 0, 0 },
 { 1, 1, 1, 0, 1, 0, 1 },
 { 1, 0, 0, 0, 1, 1, 1 },
 { 1, 0, 1, 0, 1, 1, 1 },
 { 1, 1, 0, 0, 0, 0, 0 },
 { 1, 0, 0, 0, 0, 1, 1 } };
 findGroups(originalMap);
 printArray(originalMap);
 }
 public static final void findGroups(int[][] map) {
 // step 1, set up the region count
 int regioncount = 2;
 // step 2, scan all cells of the map, looking for '1' values.
 for (int row = 0; row < map.length; row++) {
 for (int col = 0; col < map[row].length; col++) {
 if (map[row][col] == 1) {
 // step 3, recursively join 1-value cells.
 joinGroup(map, row, col, regioncount);
 // step 4, increment region count
 regioncount++;
 }
 }
 }
 }
 private static void joinGroup(int[][] map, int row, int col, int regioncount) {
 // expect the recursive calls to generate invalid co-ordinates.
 // ignore anything invalid.
 if (row < 0 || row >= map.length) {
 // illegal row.
 return;
 }
 if (col < 0 || col >= map[row].length) {
 // illegal col.
 return;
 }
 if (map[row][col] != 1) {
 // only join 1-value cells.
 return;
 }
 // set the group number.
 map[row][col] = regioncount;
 // check the neighbours...
 joinGroup(map, row - 1, col, regioncount);
 joinGroup(map, row + 1, col, regioncount);
 joinGroup(map, row, col - 1, regioncount);
 joinGroup(map, row, col + 1, regioncount);
 }
 // method to print array
 public static void printArray(int[][] myArray) {
 for (int x = 0; x < 7; x++) {
 for (int y = 0; y < 7; y++) {
 System.out.print(myArray[x][y]);
 System.out.print(" ");
 }
 System.out.print("\n");
 }
 }
}

In the recursive method, note how it expects there to be invalid values. This is a recursive technique that makes it the responsibility of the recursion to check it's bounds. The alternative is to check the bounds each time before you call the next recursive level. By doing it the way I suggest you can reduce the amount of code you write, but at the small expense of recursing one level more than you need to.

The output from the above code, when I run it, is:

2 2 0 0 3 3 3 
2 0 0 0 0 0 0 
2 2 2 0 4 0 4 
2 0 0 0 4 4 4 
2 0 5 0 4 4 4 
2 2 0 0 0 0 0 
2 0 0 0 0 6 6

• David Harkness: Oh so sorry! I meant to comment on the question. That's what I get for commenting on my phone. :)
• 200_success: That's basically the solution I came up with. I suggest renaming joinGroup() to floodFill().
• praiseHellRaiseDale: Beautiful, thanks for the help. I can't wait till coding that clearly and effectively comes more easily. I've read through it, and it all makes perfect sense. I have some practising to do.

Answer 2

Use the power of data structures...

Data Structure Power

Step one

You create a two different data structures consisting of pure indexes of your original matrix. On the first you create Objects that contain "pointers" (in your case references) to the top, left, right, and bottom elements.

Step two

Create a list of indexes of the elements that are not Zero every time the matrix changes. These indexes are also references.

Step three

The algorithm will change, here is some pseudocode

for(elements in idx_of_not_zero)
{
 if(1){ change_adjacent(+1);
}

In change adjacent you place the logic regarding the "if its two then don't change".

This will take more memory, but it will be faster.

Such is the tradeoff between memory and performance.

• praiseHellRaiseDale: As you can probably tell from the question, I'm a bit of a novice. I will try to implement this into code, and then ask further questions. But if anybody else has any ideas, feel free to throw them out there.
• Claudiordgz: It doesn't matter that you are a novice, you got an implementation going, that's an awesome step in the right direction. Data Structures are breadth and butter and getting into that subject too soon may harm your productivity. The fact that you are trying speaks wonders of what you are doing.

Answer 3

You can use a fairly simple algorithm for two-pass Connected component labeling