# Image-grouping using bit matrices

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");
}

}
}


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

• Oh so sorry! I meant to comment on the question. That's what I get for commenting on my phone. :) – David Harkness Mar 11 '14 at 5:25
• That's basically the solution I came up with. I suggest renaming joinGroup() to floodFill(). – 200_success Mar 11 '14 at 7:37
• 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. – trueCamelType Mar 11 '14 at 17:37

Use the power of data structures... ### 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)
{