Image comparison system

[agent]

I'm working on a program that will allow you to compare two images to determine how different or similar they are. It does so by averaging large areas of the image and maintaining a high-accuracy for the averaged pixels' colors. (I scale R, G, B, and A to UInteger before averaging them and keep them there when comparing.)

It seems to work well, but its got a few hacks that I'm not really proud of, but can't think of any way to remove. It also seems horribly inefficient.

The only thing I'm any sort of proud of in it, really, is the PixelArray class that pins a byte array to the same location as a Bitmap class. (Editing the array affect the bitmap and vice versa.)

What I'm looking for is someone to evaluate my code and tell me that I'm not crazy and that things can actually be improved without a complete re-write from scratch. Any suggestions for additional features would be helpful.

Design goals include the ability to serialize the generated signature (the ColorIArray class, already possible) and add some form of multi-threading and a progress callback mechanism so I can add a progress bar when generating signatures for huge images or with huge numbers of datapoints.

The code is throughly commented. You'll need a few images, preferably larger than 20,20 to test this with.

[dee-u]

Hhhmmmm... I think I did a binary compare of the two images if they are the same or not, it seemed to work for me.

[agent]

I'm comparing for similar images, not exact matches. Need to quantify the differences.

Hhhmmmm... I think I did a binary compare of the two images if they are the same or not, it seemed to work for me.

[TOQ4]

Don't understand how you use average to define discrimination....

XOR & SUM is one way, Difference and SQAURE SUM IS ANOTHER; Some use DIFF followed by AAD (Absolute average deviation).

Does the code only have to be fast; what is a difference and what is no difference in the image... how do you want to rate color vs intensity...?

Sorry lots of questions???? :)

[agent]

Don't understand how you use average to define discrimination....

XOR & SUM is one way, Difference and SQAURE SUM IS ANOTHER; Some use DIFF followed by AAD (Absolute average deviation).

Does the code only have to be fast; what is a difference and what is no difference in the image... how do you want to rate color vs intensity...?

Sorry lots of questions???? :)


What this code is doing is splitting the image into segments, and averaging the segments with high precision. The values are then stored in an array which constitutes an image signature.

To quantify the differences, the absolute differences between each element in the array are added up and then divided by the number of elements to give us the average difference between the two images. It doesn't take into account intensity or color intentionally, but, because all of the math is per-colorchannel, similar colors would tend to have a smaller difference than dissimilar colors thus affecting the average difference by a smaller amount.

I've since re-written the classes from scratch and will be putting up the new one in a different thread (once I'm done documenting it).

[TOQ4]

So if I try to understand you have lots of images, want to compress them such that when you now have a new image you compress it and compare it with the compressed version of other images to find most similar ones?

Image NxM dimensions to Image eg 8x8 (in your case probably 8x8x3 ; 3 = R,G,B )....

Am I making sense? Is this what you want to do?

Like this?
http://research.microsoft.com/~mariuszj/ICIP00Hash.pdf


TQv

[TOQ4]

So I read and tried your code - don't know if it does what it's supposed to do; I'm a bit new to VB2005 but will get a hang of it soon...

One off trial:
1. I Loaded two images that I subjectively say are similar...; I adjust dissimilarity to 20% - then they are judged as not the same
2. Then I loaded two subjectively different images, used same threshold and got judgment same (equal)!

I know there must be a perfectly logical explanation for this....

Images used step1: Dock, Humpback Wale
Images used step2: Grean Sea Turtle, Humpback Wale
(Vista Sample images)

I would suggest normalizing each image to a fixed width/height. This is just drawing with GDI or similar probably fastest way to reduce data... Median is a lot better than average but a lot slower… Then I would trade off a longer signature for precision in average unless U whant to do a real HASH.

Approach 1:
For image matrix X build a model, e.g. PCA / FT / Wavelets or other...
Now asses if other image fits space of X. When you build your PC model you don't have to be so picky on the absolute maximum descriptiveness in each factor - then you can probably process a 64x64 point image in less than 1 second... resulting in a maybe 64*8 vales; you could also find info on two way PCA on the net. I would do a 2 directional model - row and column permutation (rotate the image 90deg). All of this will be a long computation at least n^2...

Approach 2:
Characterize image by histograms; for each image cell... histograms are fast to compute; they disclose something about relative intensity distribution; concatenate to a vector and use these as signatures for the image. Now compute a correlation or RMS value to each library vector...

Permute the library on it-self to find proper scale of difference… or set a definition e.g. black, grey, white and chessboard

I guess one could set up a challenge for this:

Build a function that:
"Lists / Displays images similar to a library of images"
1. Add remove images to a library
2. Assess sameness of a given image to the library (fast)
3. Determine if a "perfect" match exists (may require original image)
4. "Whatever function you may feel is beneficial"

We need a set of images for development:
10 X Shapes (smiles’?)
10 X Faces
10 X Fingerprints

1000 or more images for final judgment day!

Maybe even a challange between VB6 / VS2005 / C ? I would suggest any coding language is allowed as long as it dosn't invalidate some stipulated rules...

Anyone up for this!? TOQ4

[agent]

I rewrote this from scratch. It uses the same idea, but I doubt that the signatures produced are compatible. The code is much more efficient and now supports being run in its own thread (and can report progress and can also be canceled).

This is the version I'm planning to use in the image comparison software I mentioned earlier.

I'm especially looking to improve the accuracy of the algorithm.

There is a known bug in that the last row of data points seems to have less than 100% opacity, even working from a starting image that has 100% opacity throughout. (You can use the ToBitmap method of the signature to understand what I mean or you can analyze the datapoints.)

...And best of all... I finally finished the documentation on how to use the code. Also, the all-important CreateSignature function is thoroughly commented.

You can see how I compare the two signatures within the Difference method.

[TOQ4]

Still don't have a clear picture on what you really want to do.

Do you really want to treat Alpha as an image information plane? I would multiply alpha into R,G and B, to de-leverage the point proportional to the Alpha value....

Back to finding similar images:
- have you found average over area to work!?
- You have chosen 500x500 points rather than 20x20, why? (maybe I read the code wrong)

Still I would suggest to:
- Transform image into a vector
- Compute an uncertainty to this vector by applying image transformation that you want to accept - Contrast / Gamma / Blur...
- Test on a small but distinct change in the image that you want to detect as not the same image.

You say you want to "Improve the accuracy" - what do you mean?

For speed you should move this out of inner x loop in CreateSignature:
If BackgroundWorker IsNot Nothing Then
If BackgroundWorker.CancellationPending Then
handle.Free()
Return
End If

End If


TOQ

[agent]

The goal here is two-fold: I want to match an image to a thumbnail of the same image and match (with a larger margin of difference) an image to the same image with a logo or text added.

I used more datapoints in this one because it causes the return value to more closely represent the actual quantified difference (in other words, comparing an image with 75% difference (i.e. comparing 3 black pixels and a white one to four white pixels) should return 0.75 * UInteger.MaxValue = 3,221,225,471)

I put the cancel code inside the main loop so that the code can be canceled by the user in a more responsive manner. This is especially important when dealing with larger size images.

This signature system is designed to overlook small (but distinct) differences. Why? Because it's supposed to ignore text, logos, jpeg artifacts, etc. which are all small, but distinct differences. We're worried about overall difference.

[TOQ4]

Now I have a clear picture and I would...

For speed:

1. Sorry but for speed still remove thread cancel checking out of inner loop; if it takes a long time to compute 4 sums we would have serious computing problems... (It’s the time to compute one pixel line within one cell I’m talking about!, my guess is << 1ms)

2. I would make a one dimensional array of the image; this is significantly faster access...

3. I would expect JIT optimization to work much better using temps and shorter inner loop; I would try:


for y=cellY*Width*Height to cellY*Width*Height step Width*4
for x=y+cellX*Width to y+cellX*Width+Width-1 step 4
B+=bits(x)
next
for x=y+cellX*Width+1 to y+cellX*Width+Width-1 step 4
G+=bits(x)
next
for x=y+cellX*Width+2 to y+cellX*Width+Width-1 step 4
R+=bits(x)
next
for x=y+cellX*Width+3 to y+cellX*Width+Width-1 step 4
A+=bits(x)
next
'
' Here thread cancel exit
next

' The 1000 is your quantization or precision factor - numerical accuracy as you asked for
data(cellY,cellX).A=1000*A/(width*height)

This should optimize nicely!

Alternative2 inner loop:
for x=y+cellX*Width to y+cellX*Width+Width-1
B+=bits(x): x+=1
G+=bits(x): x+=1
R+=bits(x): x+=1
A+=bits(x)
next

or3:
for x=y+cellX*Width to y+cellX*Width+Width-1 step 4
B+=bits(x)
G+=bits(x+1)
R+=bits(x+2)
A+=bits(x+3)
next


4. You don't really need i+=1, or? at the end it is Width*Height

For detection:

1. Artifact JPEG removal
- Really precise is to use some kind of removal filter; should be able to find something on the net...
- An alternative is a mean filter! This is however also computationally intensive... much more than simple sums
- Poor mans alternative is scale down image / since you are already scaling down you can just adjust above "1000" precision factor to e.g. 0.1 (loosing numerical precision)

2. “Local deviations from the ideal” (e.g. Logo imprint)
- Here you need an inverse distribution on difference, Square Sum ( poor behaviour on few deviations from the ideal ), AAD( not so bad statistically difficult ), Sign ( very very very robust )!

Detection:
Ryx denotes data(y,x).R …
RGBA denotes possible source of image; rgba denotes image investigated

Absolute signal to noise ratio where A is image information:
[Ryx + ryx + Gyx + gyx + Byx + byx + Ayx + ayx] / (1 + 2 * [|Ryx - ryx| + |Gyx - gyx| + |Byx - byx| + |Ayx - ayx|])

Absolute signal to noise ratio where A is image information discloser:
Pre-multiply RGByx*ayx / 255 and rgbyx*ayx / 255
Note that I use ayx for RGB as well as rgb; because what isn’t visible in the image to be compared shouldn’t be compared with the possible source!

[Ryx + Gyx + Byx + ryx + gyx + byx] / (1 + 2 * [|Ryx - ryx| + |Gyx - gyx| + |Byx - byx|])

In these cases a high number means equal – reverse left and right hand side for opposite.

Dealing with local difference:
Here I would use median! If we assume that our prescalers and filters small imperfections then we need to do a local S/N!

Assume we have 10x10 (100) numbers of S/N then we would sort them all and say we exclude x lowest from the final S/N! the x lowest to exclude is then equal to in how many cells I allow a deviation where as the rest has to mach.

To be more stringent to matching I would pick number x lowest + 1 to identify S/N in this way the n’th lowest number is our minimum S/N!

“Imperative” is:
a. Solution deals with small imperfections by absolute average over area
b. Solution deals with small imperfections by truncation (scaler)
c. Solution deals with local deviations by allowing n local deviations

For effective solution a & b can be combined to produce a faster code.

- So lots of words - sorry if its messy, i'm not native english speaking..., I will be flying to Chicago on Saturday perfect time to code something and test on all my hard drive images.

I have a nice phrase that i tend to reuse, what we all are looking for and are asked to do, is robust stuff "robust code, robust methods etc.".
ROBUST = CAPABILITY TO COMPLETE A TASK WITH MANY SMALL DEVIATIONS FROM THE IDEAL, OR FEW LARGE DEVIATIONS FROM THE IDEAL.

Are my inputs helpfull? Do you want some code from me?

TOQ4

[agent]

My hard drive managed to get itself formated last night (drives will be drives...).

Anyway, I'll have to wait until I'm done attempting to recover the data before I can reinstall the IDE and pick up where I left off.

I like your ideas, by the way, but I won't be able to test them for a bit.