5
\$\begingroup\$

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

    }
}
\$\endgroup\$
8
\$\begingroup\$

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

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – trueCamelType Mar 11 '14 at 0:44
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Claudiordgz Mar 11 '14 at 1:28
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.