Image Comparison with Java (Part I)

It was several years ago, when I had the idea for image comparison. Then the chosen language had been C# because the features of DirectX. As it happens with such ideas they got put aside. Today I revisited the idea and made some discoveries:

• I changed form Windows to Linux, so a .Net based language may not be optimal
• DirectX is not portible as is OpenGL
• Java provides now functionality for image processing
• With the upcoming version 7 of the JDK, Java gets excellent OpenGL support

Therefore I would like to outline the ideas a bit further.

The idea of image comparison is to

1. define a metric to specify the similarity of two pictures. Ideally this would be a simple number. This leaves us with few information if the pictures are unequal. E.g. the pictures may be identical but different in size or they are stored in different file formats.
2. define an algorithm that can compare two images and create a metric as described above.

Consider theese examples:

The pictures are identical. The text in the black border can be ommitted since we want to analyse the picture. For the same reason the black border can be ommited. The text may be helpful for tagging the image. You can envision an application that uses logic clauses to derive „truth“:

• Picture A and picture B are identical.
• Picture B shows the Oracle Headquater
• Therefore picture A shows the Oracle Headquater

Now consider this further image:

Is this image equal to the above? No there is more in the foreground. Are the above pictures a subset of this one? Hard to tell. Visual inspection says picture A is a subset of picture C. If that is true then the algorithm should result in something like „Picture A is a subset of picture C“. This defines that the comparison of the appropriate section in C with A results in equality.
Testing for equality is not that hard. We can simply compare every pixel of the image. To to that we follow the divide and conquer principle in segmenting the picture down to the level of a pixel which is easy to compare.
Before implementing several things should be taken into account.

• Due to compression identical pixels are not exactly identical. Therefore the pixel should be compared by liklyness of a hue range.
• It may suffice the check randomized sections of the image instead of the whole image

In the case of picture A and B this should produce pretty good results.
Another aproach is described by Sanjaya Wijeratne in his article Compare Images for Similarity using Java Advanced Imaging API That article bases its ideas on Rafael Santos unfinished Java Image Processing Cookbook. The algorithm described there to compare images is based on this article from the Xerox Research Center in Paolo Alto from September 2002. This algorithm produces mixed results:

• Equal and similar and even some dissimilar images compute to the same distance value.
• For a small number of images the algorithm is fast
• For large amounts images the performance is bad. It is of O(n2). Effectively it should be O(n2)/2 because the distance computed from A to B is equal as the distance from B to A. Therefore it would be easy to compute all distances from A to all other images and when computing the difference from any other image to A just look up the value. This produces a large amount of data that cannot be stored in memory. I tried different variants but could not come up with one that efficient processing wise as well as the storage space.
• The algorithm is bad for scaling. Each image must be processed. To compute the distance two images are compared. A better solution would be to compute some kind of metric or description of the image and compare these. These descriptions could be stored. Since the computation of the metric is the expensive part such an algorithm would run in O(n). The comparison would still be O(n2) but without the time consuming part of data-extraction.