Good metric for qualitatively comparing image patches 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):




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




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!
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.