Jump to content
  • Advertisement
Sign in to follow this  

Measuring image similarity

This topic is 3084 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi! I am looking for an algorithm that let's me compare two images, and yields (ideally) one number for their similarity. The obvious thing would be sum of squared per pixel differences, which unfortunately are not suitable in my case. I need to compare two different compression method's quality to compression ratio, but those two work quite differently. One is just JPEG, which mostly draws it's compression from tolerating differences in colors, but leaving geometry mostly in place. The other also does introduce errors in colors, but works mostly by allowing slight errors in geometry, which are barely notable with respect to the subjective impression. Sum of squares is misleading here, because slightly shifted edges tend to result in rather large differences, yet the over all impression is barely biased. My difficulty hereby is to find a method that yields a measure for "impression", rather than a hard mathematical approach. I also tried a FFT analysis, but the second method also causes great differences in frequency, and even more so in phase space. As an example for what this second compressor roughly outputs: Consider two consecutive frames of a movie, where rather little action takes place. If the first is the original image, the second is about what the compressor will output. Objects in the image may shift slightly in an arbitrary manner, but only by very little. Yet I need to identify these as practically the same, but it needs to be able to rate JPEG quality a the same time so that I can really compare those two. Any ideas would be greatly appreciated!

Share this post


Link to post
Share on other sites
Advertisement
I would define first a constant which relates a displacement error to a color error. For example 1 pixel distance = 0.05 color distance (in the unit rgb cube or another color space). Lets call this 0.05 = c in the following.

Then you basically sum the squared color distances per pixel. But if you find a color distance that is larger than 0, you calculate the corresponding pixel distance (= color_distance / c) from it. Then you search a circular disc around your pixel for a pixel in the reference image that would yield a smaller error if you sum the pixel distance (times c) and the color distance. So, finally the error for that pixel is min(pixel_distance * c + color_distance) over a large enough circular area around each pixel. The radius of the disc you need to search can be estimated from the color_distance at the center as mentioned above (because a larger pixel_distance would yield a worse result anyway, even with identical color). You can even further optimize it, by incrementally increasing your search radius while calculating the maximum radius from your current best match.

Of course this technique does not perfectly measure all cases. If a straight line is turned into a zig-zag line this could be considered worse than just moving the line by one pixel. But this is the same for colors for the simple squared difference. A dithering pattern with positive and negative differences can be also worse than just a slight (but uniform) shift in color.

Share this post


Link to post
Share on other sites
That sounds quite promising, especially because it seems like a very stable approach for completely arbitrary contents!

I am now thinking of using a matrix (5x5, 7x7 or even 9x9) with distance-weights, multiply the color differences to the center pixel with it, and find the minimum in the resulting matrix. Slide this matrix over every pixel, suming up the results.
This sounds good enough to give it a try under real conditions! Thank you.

Edit: A small related question: How should I calculate the difference in color best? Per channel and then sum it up? If that, then absolutes or squares before summing channels up?

Share this post


Link to post
Share on other sites
This is what I came up with, and it seems to perform quite nicely so far. Thank you!

(FPColor := Single precision color class
RealMap := Bitmap consisting of FPColors)

private static double ColorDiff(FPColor c1, FPColor c2)
{
return Math.Sqrt((Sqr(c1.r-c2.r)+Sqr(c1.g-c2.g)+Sqr(c1.b-c2.b))/3.0);
}

public static double Compare(RealMap a, RealMap b, double distanceWeight)
{
double dw = distanceWeight;
double[,] weights = // 9x9 LUT := Sqrt((x-4)²+(y-4)²)*dw;


double result = 0;
for (int y=0; y<a.Height; y++)
{
for (int x=0; x<a.Width; x++)
{
double minDiff = Double.MaxValue;
double minWeight = Double.MaxValue;
double v = Double.MaxValue;
for (int y0=0; y0<9; y0++)
{
for (int x0=0; x0<9; x0++)
{
if (((x+x0-4)>=0) && ((x+x0-4)<a.Width) && ((y+y0-4)>=0) && ((y+y0-4)<a.Height))
{
double k = ColorDiff(a[x+x0-4, y+y0-4], b[x, y]);
if ((k.Equals(minDiff)) && (weights[x0, y0]<minWeight))
{
minWeight = weights[x0, y0];
v = k+weights[x0, y0];
}
else if (k<minDiff)
{
minDiff = k;
if (weights[x0, y0]<minWeight) minWeight = weights[x0, y0];
v = k+weights[x0, y0];
}
}
}
}
result += v;
}
}
return result / (a.Width*a.Height);
}



The hassle in the inner loop with minWeight is there, so that the center pixel rather than the upper left corner of the 9x9 matrix is chosen in an evenly colored area.
This looks a little confusing at first, but is neccessary because I first look for the smallest color difference, and THEN add the distance penalty, so that still the best color match is chosen, even if it has a large distance penalty to reflect shifted geometry better.

I currently chose the distance-weight as 1/Min(Width, Height), which seems a tad low. That'll be something to play with a little.


Best fishes,
Medium9

Share this post


Link to post
Share on other sites
That looks even better from the description, though after a quick look it seems that this method also could tend to penalize geometrical shifts more than I intended. But I'll have to take a much deeper look into that, most defenitely appreciated! Thanks!

Share this post


Link to post
Share on other sites
Are you looking to automate something, or is this for some sort of paper/table to list the merits of each method? If it's the latter, I can't see how any such metric would be useful in any case. That is, if I read it, I don't see how it would tell me anything useful except how some arbitrary scheme rates them.

In such a case, I think the best approach would be to have a bunch of people judge which one is the better one. Do a series of different images at different settings and of course double-blind etc

Share this post


Link to post
Share on other sites
It is the latter. I've spent quite some time trying different methods and tweaking parameters now, and I have to concur: So far no single algorithm managed to properly yield a quality-rating tuned to human perception suitable for the two methodically opposing compressions I try to compare here. At least not in a general case, which is what I would need.

The downside of this is, that this is for my bachelor thesis, and I now have to convince my professor that there seems to be no other way than actually letting humans rate the results, although he specifically asked for quality/compression comparisons with other common compressions and mine. But I guess I can make a proper statement after trying so many methods.

At the danger of landing at some method that takes more effort and time to implement than the actual subject of my thesis, I hereby rest my case :).
Thanks again to you all!

Share this post


Link to post
Share on other sites
Awesome! Well... not good in general, but if I can refecence existing papers of specialists, things will become a lot easier for me. The one you linked to nicely sums up what my desparation in the last days consisted of.

Next time, I may first search for "problems with X" before looking for concrete solutions ;-)

Thanks one more time!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!