Good metric for qualitatively comparing image patches

Question

I am trying to "match" little square patches in an image. At first glance, it seems reasonable to simply do a Euclidean distance style comparison of two of these arrays to get a "similarity" measure. This works fine in many cases (the "best" patch (lowest value) according to this metric looks very much like the query patch). However, there are many cases in which this produces a very bad match. For example, take these two patch pairs:

Two patches of a brick wall, score 134 (this is the sum of the components of the average absolute pixel difference):

Target Patch http://daviddoria.com/Uploads/PatchPairs/1/target_patch.png

One patch of a brick wall, one patch of grass, score 123!

http://daviddoria.com/Uploads/PatchPairs/2/source_patch.png http://daviddoria.com/Uploads/PatchPairs/2/source_patch.png http://daviddoria.com/Uploads/PatchPairs/2/target_patch.png http://daviddoria.com/Uploads/PatchPairs/2/target_patch.png

To a human, "clearly" the grass does not match the brick, but this metric says otherwise. The problem is just in the local statistical variation.

If I use something like a histogram comparison, I completely lose all spatial information - e.g. if a patch is grass on the top and brick on the bottom, it would match exactly to a patch with grass on the bottom and brick on the top (again, another "obviously wrong" match).

Is there a metric which somehow combines both of these ideas into a reasonable value that will evaluate to "similar" for Pair 1 above, but not also be similar for my example of a patch and its vertical mirror?

Any suggestions are appreciated!

Answer 1

The essential idea is: There is nothing wrong with color information- it is just insufficient. So best thing is to combine multiple feature sets.

You can try multiple features to resolve this ambiguity. As far as feature set is concerned you can use following:

1. Color (something like MPEG7's dominant color) OR Color Historgram
2. Texture (either in the form of Filter bank response) OR
3. Edge histograms

As a primary comparison, i would first like to make distinction between pure brick patch vs. pure grass patch. For this, color is definitely the most potential element.

Combining features to make more robust classification

I would use a dominant color ( uses but not the only one) or key color and form the clusters. See where the cluster heads lie;

If the cluster heads both are within expected areas, the class is usually easy to detect, if the they fall into gray area, then the class belongs there. If it falls in gray area, another feature is required.

Sameway, you can independently classify using Texture matrix and then combine both the scores to ensure that results makes sense.

Dealing with spatial problems

Specifically when you realize that the patches can have parts of it which are half bricks and half grass. I think you don't need any more additional features or different matric. This can be handled in two ways.

1. Keep multiple membership patch as different classes. For example, apart from birck-only class and grass-only class, you can also have half-brick-half-grass-vertical and half-brick-half-grass-horizontal as total four classes. This can be easily classified using the clustering method we discussed earlier.

2. Add multi scale classification For example, given the patch being in a gray area, you can divide the patch two parts i.e. left vs. right. Same way you can also divide top vs. bottom. Now you can apply identical classification for this "half part". Ideally the above listed feature should allow you to make it scalable to compare a feature similarity between full part (for example dominant color can be same irrespective of size) or yo might have to resize it.

Adding more classes (as in part 1) or more levels (as in part 2) will be straight forward; the upper limit will come by two factors - either any additional division will no longer add any value to classification or that excessive noise will introduce ambiguity in the classification effectively. This is where you stop.

Answer 2

To start with, 2 images and 3 measurements are not exactly enough to ascertain any kind of statistical model which in terms can be used to define the optimal comparison metric.

I think you could start to have a look at texture recognition papers for methods and clues. It is an active field.

For what it is worth, I ran a couple of perceptual hashing functions (DCT and Random Projection based) tests and did a little trial with the so called SIFT descriptor. These functions can separate inter and intra class distances, although from 3 images it is impossible to conclude anything.

Code on github.