Advanced image comparison for screenshots taken from webpage

[jonaskilian]

I've done some screenshot comparison with ImageMagick. Works fine pixel-by-pixel but when I move image areas to different positions, the compare tool won't notice.
I wonder if there're even more sophisticated algorithms available like spotting matching image regions even if they appear at different positions?

My examples for clarification:
http://www.molyb.org/confluence/display/molyb/Screenshot+comparison

Thanks Jonas

[fmw42]

I've done some screenshot comparison with ImageMagick. Works fine pixel-by-pixel but when I move image areas to different positions, the compare tool won't notice.
I wonder if there're even more sophisticated algorithms available like spotting matching image regions even if they appear at different positions?

My examples for clarification:
http://www.molyb.org/confluence/display ... comparison

Thanks Jonas

Normalized Cross Correlation Matching will match a small image to some region in a larger image. However, this is typically done with Fourier Transforms. Convert to frequency domain (FFT), match images, get correlation surface and find the location of the brightest point. The value in the correlation surface tells you how good the match was at that point.

Unfortunately IM does not have built in support for FFT. I have been trying to work on that, but have reached a set back. See

http://www.fmwconcepts.com/misc_tests/F ... index.html
viewtopic.php?f=1&t=12333
viewtopic.php?f=2&t=12151

However, I do have a unix script that does this but require IM Q16 HDRI and Sean Burke's IMFFT with the FFTW delegate library.

Here are two example:

[anthony]

Note that this only works for image with the same scale and rotation.

there is also a IM core library pixel comparision rouitine that I saves but have not seen any further reference to. This just does direct comparisions (convolved compare) without using FFT, and may need some fuzzy matching (FFT is superior)

I give no gurantees, and I have not tried to use it myself, just saved it for future reference (like now).

though if you do trying I'd love to here any feedback you have.

Code: Select all

/*
**
** Locate a sub-image within a larger image
**
** We added IsImageSimilar() to ImageMagick 6.2.8-4 Beta if anyone wants to
** take a look at the solution to locating coordinates of a sub-image within
** another image.  It works in all colorspaces and accounts for image masks.
** Below a test program for IsImageSimilar().  Compile with:
**
** Cristy     July 2006
**
** Compile with:
**   cc `Magick-config --cflags --cppflags` \
**       -o locate_subimage locate_subimage.c \
**       `Magick-config --ldflags --libs`
**
** Note this takes one image, and crops an area from that image then
** tries to find where that sub-image is located within the original.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <magick/MagickCore.h>

int main(int argc,char **argv)
{
  ExceptionInfo
    *exception;

  Image
    *crop_image,
    *image;

  ImageInfo
    *image_info;

  long
    x,
    y;

  RectangleInfo
    region;

  if (argc != 2)
    {
      (void) fprintf(stdout,"Usage: %s image image\n",argv[0]);
      exit(0);
    }
  InitializeMagick(*argv);
  exception=AcquireExceptionInfo();
  image_info=CloneImageInfo((ImageInfo *) NULL);
  (void) strcpy(image_info->filename,argv[1]);
  image=ReadImage(image_info,exception);
  if (exception->severity != UndefinedException)
    CatchException(exception);
  if (image == (Image *) NULL)
    exit(1);
  region.width=100;
  region.height=100;
  region.x=100;
  region.y=100;
  crop_image=CropImage(image,&region,exception);
  x=0;
  y=0;
  IsImageSimilar(image,crop_image,&x,&y,exception);
  printf("%ld %ld\n",x,y);
  image=DestroyImageList(image);
  image_info=DestroyImageInfo(image_info);
  exception=DestroyExceptionInfo(exception);
  DestroyMagick();
  return(0);
}

[jonaskilian]

Trying to locate the following subimage of 244x174 pixels inside a big one (1024x1917 pixels) using IsImageSimilar worked for me.



$ /usr/bin/time -v ./locate_subimage2 1_molyScreenshot-456.png subimage-1.png
717 460
Command being timed: "./locate_subimage2 1_molyScreenshot-456.png subimage-1.png"
User time (seconds): 20.84
System time (seconds): 0.05
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:20.91
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 0
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 5016
Voluntary context switches: 2
Involuntary context switches: 44
Swaps: 0
File system inputs: 16
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

Note that the location 717, 460 was found correctly in ~ 20 seconds.

[fmw42]

Trying to locate the following subimage of 244x174 pixels inside a big one (1024x1917 pixels) using IsImageSimilar worked for me.



$ /usr/bin/time -v ./locate_subimage2 1_molyScreenshot-456.png subimage-1.png
717 460
Command being timed: "./locate_subimage2 1_molyScreenshot-456.png subimage-1.png"
User time (seconds): 20.84
System time (seconds): 0.05
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:20.91
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 0
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 5016
Voluntary context switches: 2
Involuntary context switches: 44
Swaps: 0
File system inputs: 16
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

Note that the location 717, 460 was found correctly in ~ 20 seconds.

It would be nice is someone would turn this into a command line function for IM! I think there have been a number of request for image matching in the archives and I think this would be a useful addition to IM

[magick]

Easy enough to do with a naive fuzzy pixel match. How do you envision this being implemented? One thought is to use the compare program. If the image is smaller than the reference image it looks for the subimage within the image and returns offset and metric. With -fuzz the subimage would not need to matches exactly and how much the subimage differs from the reference image is captured in the metric output.

[fmw42]

Easy enough to do with a naive fuzzy pixel match. How do you envision this being implemented? One thought is to use the compare program. If the image is smaller than the reference image it looks for the subimage within the image and returns offset and metric. With -fuzz the subimage would not need to matches exactly and how much the subimage differs from the reference image is captured in the metric output.

That would certainly be one approach, namely to report the "best" or closest match simply to the terminal. This is the most useful result.

Another option might still use compare, but would return the metric pixel-by-pixel as an image (when the two images are of different sizes). Each pixel result corresponds to the metric result from the offset of the smaller image with respect to the larger image. This approach has more information in that it shows whether there are other close matches (size of bright area or other bright areas --- I guess it might be dark areas and low values for a match for some metrics). That would be similar to the normalized cross correlation examples I have shown above. It would also be nice if it returned the best match information (location and metric) to the terminal as well.

Both approaches are useful, if that is possible to do. Conceivably it is just a matter of whether you specify null: or an image for the output from compare. You probably have the metric image stored internally any way and hopefully it is just a matter of saving it to an output image.

compare -metric rmse largeimage smallimage null: returns the one best match location and metric value

compare -metric rmse largeimage smallimage metricimage returns the image of the pixel-by-pixel metric value for each possible offset between the small image and the larger image.

I am not quite sure how -fuzz comes into this. Perhaps I misunderstand and you are simply talking about using an average fuzzy color difference in place of the compare metric for comparing the smaller image with each possible subimage of the larger image. In this case, a choice of just a best match location and smallest average fuzzy color difference value or an image of average fuzzy color difference values for each offset would still be appropriate and useful.

[magick]

This feature is already working in our development area. Look for a patch that you can test in the Subversion trunk by sometime this weekend.

[fmw42]

This feature is already working in our development area. Look for a patch that you can test in the Subversion trunk by sometime this weekend.

Thanks. I will have to wait for a beta as I have not worked out the details of getting things from the subversion.

Did you implement both approaches that I suggested above?

Can you provide me with an example command line of how to use it (for either/both approaches)?


Fred

[magick]

The patch will be part of ImageMagick-6.5.0-8 Beta as well. We're not commenting on implementation just yet because the design is in flux.

[fmw42]

The patch will be part of ImageMagick-6.5.0-8 Beta as well. We're not commenting on implementation just yet because the design is in flux.

OK. Let me know when you have something for me to test and some description of the options and example command lines. You can send as private message if you want.

[magick]

The feature will be ready for testing in about an hour as ImageMagick-6.5.0-9 at ftp://magick.imagemagick.org/pub/ImageMagick/beta.

[fmw42]

When it is ready, let me know the syntax for the command line to use to test it. Thanks.

[fmw42]

I downloaded IM 6.5.0-9 beta as you suggested. But it does not yet appear to be working or I do not know the correct syntax. But the output from compare on two equal size images shows some changes to display the match coordinates, e.g.

compare -metric rmse rose: rose: null:
0 (0) @ 0,0


Tried comparing subsection of zelda image with the full image:

and




compare -metric rmse zelda3g.png zelda3g_32_27.png null:
compare: image size differs `zelda3g.png' @ compare.c/CompareImageChannels/153.

compare -fuzz 1% zelda3g.png zelda3g_32_27.png null:
compare: image size differs `zelda3g.png' @ compare.c/CompareImageChannels/153.

compare -metric rmse zelda3g_32_27.png zelda3g.png null:
compare: image size differs `zelda3g_32_27.png' @ compare.c/CompareImageChannels/153.

compare -fuzz 1% zelda3g_32_27.png zelda3g.png null:
compare: image size differs `zelda3g_32_27.png' @ compare.c/CompareImageChannels/153.


Am I testing prematurely?

[magick]

The code is templated but it needs more work. Perhaps by tomorrow evening.