How do I look for a match of a smaller 2D array inside a bigger 2D array?

Question

I was tasked with creating an image database, which has image objects of several types. Each image is consisted of a 2D array of pixels. I have been asked to create this method: MatchPattern (Image subimage, Image image): this function returns integer that represent how many times a subimage repeats into an image.

The code I have written is as follows:

public int MatchPattern(Image subimage, Image image) {
    if(image.getClass().equals(subimage.getClass())){
        int numOfMatches = 0;

        int imgWidth = image.getWidth();
        int imgHeight = image.getHeight();

        int subimgWidth = subimage.getWidth();
        int subimgHeight = subimage.getHeight();

        if (imgWidth < subimgWidth || imgHeight < subimgHeight)
            return 0;
        for (int i = 0; i < imgHeight; i++) {
            for (int j = 0; j < imgWidth; j++) {

                int subHeightIndex = 0;
                int subWidthIndex = 0;

                Pixel imagePix = image.getImg()[i][j];
                Pixel subimgPix = subimage.getImg()[subHeightIndex][subWidthIndex];

                if( (imagePix.compareTo(subimgPix)==0) && ((imgWidth-j)>=subimgWidth) && ((imgHeight-i)>=subimgHeight) ){
                    boolean matchFlag = true;
                    for (int k = 0; k < subimgHeight; k++) {
                        if(matchFlag == false)
                            break;
                        for (int l = 0; l < subimgWidth; l++) {
                            matchFlag = (image.getImg()[i+k][j+l] == subimage.getImg()[k][l]);
                            if (matchFlag == false)
                                break;
                        }
                    }
                    if(matchFlag == true)
                        numOfMatches++;
                }                
            }
        }
    return numOfMatches;   
    }
    return 0;

However, whenever I run the method, it always returns a num of matches equals to 0. Can anybody point me to the right direction? Thank you in advance.

why don't you do a simple `System.out.println` inside the `if` statement and see if control is going inside? Basically, go through the debugger and check where control is going and if it's not going where it's expected, then reflect why could this be...? etc. Eventually, you'll narrow down the problem and get to the cause of it. — Ousmane D., May 10 '17 at 00:38
suppose you refer following [post](http://stackoverflow.com/questions/297762/find-known-sub-image-in-larger-image) on the same issue. It may be helpful to find a better algorithum. also this [post](http://stackoverflow.com/questions/12598818/finding-a-picture-in-a-picture-with-java) and this [example](http://www.dreamincode.net/forums/topic/157963-finding-a-sub-image-in-a-larger-image/) — Rajith Pemabandu, May 10 '17 at 00:40
Aominè, I tried doing that, and none of System.out.println were printed... RajithPemabandu, thanks, I will check that out right now. ScaryWombat, I'm still relatively new to Java, as such I do not know how debuggers work. — Mahoufo, May 10 '17 at 00:43
@Mahoufo thus control is not going inside where it's expected hence I said to use a debugger which will help you see where things are going wrong and you'll spot it. — Ousmane D., May 10 '17 at 00:44
http://www.vogella.com/tutorials/EclipseDebugging/article.html — Scary Wombat, May 10 '17 at 00:48
to use a debugger to a very basic task that a programmer needs to know how to do. — Scary Wombat, May 10 '17 at 00:49
Okay, looks like I'll be studying debugging over the next few days. Thank you. Although, if a more immediate solution is present, I would extremely appreciate it. — Mahoufo, May 10 '17 at 00:53
If you use NetBeans or Eclipse or some other IDE, you will have a debugger ready to use. Basically, instead of 'running' your program you 'run it in debug mode', and you can set breakpoints by clicking on the line number you would like to stop on. The debugger will run your program and stop at the breakpoints you set. You can use the breakpoints to inspect the value of a variable, and you can step the debugger one line at a time to see how your program executes. It's very useful. — Matt, May 10 '17 at 01:14

Juan Bustamante · Answer 1 · 2017-05-10T12:27:30.000

Shouldn't "k" be compared to "subimgWidth" and "l" to "subimgHeight"?

Also, don't compare the pixels with "==", compare them with ".equals" or with ".compareTo", like you did on the other if statement.

There were a few other things wrong with the algorithm. I tested this with a few sample inputs, and it seems to work well:

   public int matchPattern(Image subimage, Image image)
   {
      int numOfMatches = 0;

      int imgWidth = image.getWidth();
      int imgHeight = image.getHeight();

      int subimgWidth = subimage.getWidth();
      int subimgHeight = subimage.getHeight();

      if (imgWidth < subimgWidth || imgHeight < subimgHeight)
      {
         return 0;
      }

      for (int i = 0; i <= imgWidth - subimgWidth; i++)
      {
         for (int j = 0; j <= imgHeight - subimgHeight; j++)
         {
            int subHeightIndex = 0;
            int subWidthIndex = 0;

            Pixel imagePix = image.getImg()[i][j];
            Pixel subimgPix = subimage.getImg()[subHeightIndex][subWidthIndex];

            if ((imagePix.compareTo(subimgPix) == 0) && ((imgWidth - j) >= subimgWidth) && ((imgHeight - i) >= subimgHeight))
            {
               boolean matchFlag = true;
               for (int k = 0; k < subimgWidth; k++)
               {
                  for (int l = 0; l < subimgHeight; l++)
                  {
                     matchFlag = 0 == (image.getImg()[i + k][j + l].compareTo(subimage.getImg()[k][l]));
                     if (!matchFlag)
                     {
                        break;
                     }
                  }
               }
               if (matchFlag)
               {
                  numOfMatches++;
               }
            }
         }
      }
      return numOfMatches;
   }

I fixed the comparison in the if statement, and I incremented subimgWidth and subimgHeight, but I'm still getting the same issue — Mahoufo, May 10 '17 at 01:05
@Mahoufo, you may want to edit your question so we can see how your code looks now. It’s very difficult to help with your code when we can only see an outdated version. — Ole V.V., May 10 '17 at 07:27
Try with the code I just uploaded. Overall, if you are not using an IDE, make sure you start using one. Eclipse is free. If you are already using an IDE, make sure you learn how to use the debugger. With an IDE and a debugger, you will be able to solve this problem in a few minutes. That's what everyone would do in this situation. — Juan Bustamante, May 10 '17 at 12:34

How do I look for a match of a smaller 2D array inside a bigger 2D array?

1 Answers1