Jump to content

  • Log In with Google      Sign In   
  • Create Account


Quantifying Difference Between Two Images


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 phyitbos   Members   -  Reputation: 128

Like
0Likes
Like

Posted 03 October 2012 - 05:56 AM

Hi,

I am learning about genetic algorithms and my goal is to make a replica (similar at any rate) to the one shown in this YouTube video:

http://www.youtube.com/watch?v=dO05XcXLxGs

I need to be able to rate the "fitness" of my generated images. To do this, I need to compare them to a supplied picture, and was wondering what algorithm I should use to quantify the similarity (distance?) between the two images. I'm not familiar with algorithms in this category, so any insight would be very helpful! One that is simple to implement would be best, considering the goal of my project is the genetic algorithm and not comparing images, although a little learning never hurts Posted Image

Thanks in advance!

Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 11886

Like
3Likes
Like

Posted 03 October 2012 - 06:29 AM

The first idea is to treat the images as vectors in R^(height*width), with one component per pixel, and use Euclidean distance. There are more sophisticated measures that are closer to what humans perceive as being similar. They are usually based on the wavelet transform.

You can do something like reduce the resolution of the images to several different scales and add the corresponding Euclidean distances with some weights (I think that's what you would get with some of the wavelet methods if you were to use Haar wavelets).

#3 turch   Members   -  Reputation: 590

Like
1Likes
Like

Posted 03 October 2012 - 06:33 AM

The simplest way would be to
int weight = 0;

for each (testPixel)
{
	 weight += abs(originalPixel.r - testPixel.r);   // assuming each channel [0,255];
	 weight += abs(originalPixel.g - testPixel.g);
	 weight += abs(originalPixel.b - testPixel.b);
}

The lower the weight the better the match.

Edited by turch, 03 October 2012 - 06:34 AM.


#4 PolyVox   Members   -  Reputation: 708

Like
0Likes
Like

Posted 03 October 2012 - 08:49 AM

You might find the ImageMagick 'compare' tool useful. It has a number of metrics which you can use when comparing images: http://www.imagemagick.org/script/command-line-options.php#metric

#5 Lauris Kaplinski   Members   -  Reputation: 841

Like
1Likes
Like

Posted 05 October 2012 - 03:53 PM

You need at least some idea, what kind of similarity you want to use as the basis:
  • The easiest is simply sum color differences of individual pixels (like turch suggested)
  • Another is to find euclidean distance between MxN vectors (like Alvaro suggested)
  • Now you may want to punish big differences proportionally more - in that case you may want to square the absolute differences before before adding them
  • If you want to give less weight to high frequencies you should downsample images before comparing
  • If you are interested in human percievable difference, you should transform your image to YUV or similar colorspace
  • If you want to add more importance to shapes you may want to apply some edge-detection
And so on Posted Image
Lauris Kaplinski

First technology demo of my game Shinya is out: http://lauris.kaplinski.com/shinya
Khayyam 3D - a freeware poser and scene builder application: http://khayyam.kaplinski.com/

#6 L. Spiro   Crossbones+   -  Reputation: 12253

Like
1Likes
Like

Posted 06 October 2012 - 05:29 AM

The simplest way would be to

int weight = 0;

for each (testPixel)
{
	 weight += abs(originalPixel.r - testPixel.r);   // assuming each channel [0,255];
	 weight += abs(originalPixel.g - testPixel.g);
	 weight += abs(originalPixel.b - testPixel.b);
}

The lower the weight the better the match.

This is not the way to go and can in fact be very hurtful to the actual result.


What you want is to use MSE (mean squared error) if your goal is simply to compare qualities between different images, or PSNR (peak signal-to-noise-ratio) if you want to discretely quantify the differences between your images (in other words, calculating the MSE is part of determining the PSNR, and a higher MSE always results in a lower dB (the measurement for PSNR), so if your goal is simply to compare images to determine which is closer to the original than another, MSE is all that is needed, whereas if you want to quantify exactly how close using dB, you should continue on and calculate the PSNR, although even still this part is optional).

For MSE (all you probably really need), the pseudo code would be:
error = 0
for ( all Y ) {
	for ( all X ) {
		error += (src(X, Y) - copy(X, Y)) * (src(X, Y) - copy(X, Y))
	}
}
error /= (width * height)

This is applied to each channel separately, so you would have one error value for R, one for G, and one for B.

Then you apply perceptual weights to these error values based on how humans perceive light.

Common weights are:
(0.299f, 0.587f, 0.114f)
(0.212656f, 0.715158f, 0.072186f)
(0.3086f, 0.6094f, 0.082f)

Notice how they all add up to 1, and also how green is always weighted much higher than the rest. This is also why the 565 16-bit color format exists, because green is the most important color perceptually. For example, if it was instead red that was most important to us humans, the 16-bit color format would instead have been 655.


Your final total perceptually adjusted error would be (assuming weights of (0.212656f, 0.715158f, 0.072186f)):
redError * 0.212656f + greenError * 0.715158f + blueError * 0.072186f


This gets you a properly weighted perceptually adjusted error metric that allows you to determine how close you are to the original, and is simple to implement.


L. Spiro

Edited by L. Spiro, 06 October 2012 - 05:32 AM.

It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS