11 Replies Latest reply: Nov 16, 2009 4:46 PM by YoungWinston RSS

    How can I improve performance (image searching)

    807580
      Hello,

      My program makes many calls to a method that compares two images. It does this by using nested for-loops (one for x-pixel and one for y-pixel) to search through a BufferedImage image and use getRGB() to compare pixel-by-pixel to see if the two images are the same.

      I've added a little bit of "optimisation" that first compares the central 5-pixles (the 5 pixels in an "X" shape in the middle of each image), and will only continue to search pixel-by-pixel if those are shown to be the same.

      Of course, both searches (the optimisation-pre-search and the pixel-by-pixel search) will quit out of the loops and return false as soon as one non-matching pixel is found.

      The problem is that it has to do this millions of times. For every single pixel in the source image, it has to go through one-by-one and compare, starting with the "optimised" speedy-compare and then moving on.
        • 1. Re: How can I improve performance (image searching)
          807580
          Well. We don't really know what you're doing here and that's probably useful information. Like are you really just trying to compare two images or are you looking for images inside images or is this for a game or what.

          But I guess my answer would be to calculate checksums of some sort for that central bit and cache that somewhere.
          • 2. Re: How can I improve performance (image searching)
            807580
            Perhaps some threading will help too. In the end if you have to search a lot of images you have to search a lot of images.
            • 3. Re: How can I improve performance (image searching)
              EJP
              Call the getRGB() method overload that returns an int[] and compare the arrays. Cuts out millions of method invocations.
              • 4. Re: How can I improve performance (image searching)
                807580
                ejp wrote:
                Call the getRGB() method overload that returns an int[] and compare the arrays. Cuts out millions of method invocations.
                Thanks.

                That sounds like it might be helpful ... but I'm having problems actually doing it. I've checked out the API and it's a bit confusing. I don't know what it's talking about when it's talking about pre-allocated arrays and scanlines and stuff.

                This is what I'm trying as an experiment:-
                 int[] nullArray = null;
                        int[] first =  img.getRaster().getPixels(0, 0, (int)img.getWidth()-1, (int)img.getHeight()-1, nullArray);
                        int[] second = img.getRaster().getPixels(0, 0, (int)img.getWidth()-1, (int)img.getHeight()-1, nullArray);
                
                 if (first == second ) {
                            System.out.println("same");
                        }
                But it keeps coming up as false. The nullArray is a "An optionally pre-allocated int array" whatever that means.

                The getRGB method in BufferedImage seems even more confusing:-
                public int[] getRGB(int startX,
                                    int startY,
                                    int w,
                                    int h,
                                    int[] rgbArray,
                                    int offset,
                                    int scansize)
                • 5. Re: How can I improve performance (image searching)
                  EJP
                  >  if (first == second ) {
                  System.out.println("same");
                  }
                  But it keeps coming up as false.
                  That's because the array references are different. It's a pointless test. You still have to compare the array contents. But iterating over a local array is zillions of times faster than iterating calling methods.
                  The nullArray is a "An optionally pre-allocated int array" whatever that means.
                  Seems perfectly clear to me, anyway you can pass null.
                  >
                  The getRGB method in BufferedImage seems even more confusing:
                  It's explained in the Javadoc. Just pass zero for offset and scansize.
                  • 6. Re: How can I improve performance (image searching)
                    800581
                    ejp wrote:
                    That's because the array references are different. It's a pointless test. You still have to compare the array contents. But iterating over a local array is zillions of times faster than iterating calling methods.
                    Would be cleaner to use [Arrays.equals(int[] array1, int[] array2)|http://java.sun.com/javase/6/docs/api/java/util/Arrays.html#equals%28int[],%20int[]%29] instead.
                    • 7. Re: How can I improve performance (image searching)
                      EJP
                      Instead of what? I don't remember suggesting any specific implementation.
                      • 8. Re: How can I improve performance (image searching)
                        807580
                        ejp wrote:
                        It's explained in the Javadoc. Just pass zero for offset and scansize.
                        I tried that and get a null pointer exception.


                        Anyway ... am I correct in understanding that it is faster to include the comparison code in one place (i.e. in the initial method call) instead of putting it into a separate method (i.e. compareArrays(ar1, ar2) ) and calling that?

                        Edited by: GallahJava on Nov 5, 2009 1:21 PM
                        • 9. Re: How can I improve performance (image searching)
                          800581
                          Try this:
                          public static boolean areImagesIdentical(File file1, File file2) throws IOException {
                                    // Safe to do this?
                                    if(file1.getAbsolutePath().equals(file2.getAbsolutePath())) {
                                         System.out.println("files are same - same path");
                                         
                                         return true;
                                    }
                                    
                                    if(file1.length() != file2.length()) {
                                         System.out.println("files are different, different file size");
                                         
                                         return false;
                                    }
                                    
                                    BufferedImage image1 = ImageIO.read(file1);
                                    BufferedImage image2 = ImageIO.read(file2);
                                    
                                    if(image1.getHeight() != image2.getHeight() || image1.getWidth() != image2.getWidth()) {
                                         System.out.println("files are different, different height or width");
                                         
                                         return false;
                                    }
                                    
                                    // Take 10 pixels from anywhere in each image
                                    for(int i=0; i<10; i++) {
                                         int x = (int) (Math.random() * image1.getWidth());
                                         int y = (int) (Math.random() * image1.getHeight());
                                         
                                         if(image1.getRGB(x, y) != image2.getRGB(x, y)) {
                                              return false;
                                         }
                                    }
                          
                                    int[] image1AllRGBs = image1.getRGB(0, 0, image1.getWidth(), image1.getHeight(), null, 0, image1.getWidth());
                                    int[] image2AllRGBs = image2.getRGB(0, 0, image2.getWidth(), image2.getHeight(), null, 0, image2.getWidth());
                          
                                    return Arrays.equals(image1AllRGBs, image2AllRGBs);
                               }
                          • 10. Re: How can I improve performance (image searching)
                            807580
                            But iterating over a local array is zillions of times faster than iterating calling methods.
                            Ehh... you would think that intuitively, but... not always true. Keep in mind that the int[] getRGB() method has to actually copy the RGB values, one at a time, from the array in the BufferedImage to your array. Then, you have to run the array comparison.

                            Suppose the very first pixel in each image is different. If you just used the getRGB method that grabs only one pixel at a time, you can abort immediately after comparing the first pixels without doing any more work. If you used the int[] getRGB method to get all of the pixels, you just wasted a whole lot of time.

                            Obviously, if the very last pixel in each image is the only pixel that's different, it's pretty likely that all of the getRGB method invocations would certainly create a lot of unnecessary overhead. In which case, you're right.

                            Also, using the getRGB method for one pixel at a time, you get a bit more flexibility if you don't need to compare the images EXACTLY. You could randomly check 1000 pixels, for example... but... don't do this since random number generation is also expensive. However, you could check every 10th pixel or whatever if you just wanted.

                            So, the answer is, I really don't know the BEST or fastest way to compare BufferedImages. If someone could tell me, that would be AWESOME. For now, I'll still to comparing each pixel using the getRGB method, terminating as soon as a pixel difference is found. For applications where the images are only going to differ by a few pixels, and those pixels tend to be toward the bottom of the image, use int[] getRGB. Or, start the comparison searching the image bottom-up.
                            • 11. Re: How can I improve performance (image searching)
                              YoungWinston
                              GallahJava wrote:
                              My program makes many calls to a method that compares two images. It does this by using nested for-loops (one for x-pixel and one for y-pixel) to search through a BufferedImage image and use getRGB() to compare pixel-by-pixel to see if the two images are the same.
                              Can you create a trusted checkdigit for your images? If so, it would provide you with a fair bit of information:
                              1. It could tell you if either of the images has changed since the last time you checked.
                              2. It could also (perhaps with some other property, such as size) tell you (with a good degree of comfort) if the two images are, in fact the same.

                              Note I say "trusted". A checkdigit here is similar to a hashcode, so it had better be a good 'un. But, given that, you have two major issues eliminated.

                              Winston

                              Edited by: YoungWinston on Nov 16, 2009 2:46 PM