How fast can I compare an array of images?

Consider an image(image) as

Let's now split the image into several parts.

n=4;
imageparts = ImagePartition[image, ImageDimensions[image]/n];
len = Length@imageparts;

Now I would like to compare each part with the rest.

Table[ImageDistance[imageparts[[i, j]], imageparts[[k, l]]], {i, 1,
len}, {j, 1, len}, {k, 1, len}, {l, 1, len}]

This is a very slow and redundant approach. It compares each part with itself and the same two parts is compared twice (that's why redundant). Moreover, the technique iterates over the length 4 times.

How can I improve the speed while having the information about which two parts are compared to get the corresponding distance?

[Note: I have chosen the value of n as 4 just for illustration purpose. The actual value of n can be much larger and the real complexity arises then.]

The function that you are looking for is called DistanceMatrix:

img = Import["https://i.sstatic.net/g6RvB.png"];
parts = ImagePartition[img, ImageDimensions[img]/n];
dm = DistanceMatrix[Flatten[parts]];

The following gets the comparison between image (i1, j1) and (i2, j2) in the original matrix given by ImagePartition:

Part[dm, (i1 - 1) n + j1, (i2 - 1) n + j2]

where dm is the distance matrix and n is the number of columns in the original matrix.

A distance function can be specified in the following way:

df = ImageDistance[#, #2, DistanceFunction -> "MeanEuclideanDistance"] &;
DistanceMatrix[Flatten[parts], DistanceFunction -> df];
• In this result, please, where is the comparison between the subimage {1,3} and the one {2,2}? Commented Feb 5, 2018 at 20:31
• @JoséAntonioDíazNavas Thank you for pointing this out; that comparison was not included in the original answer, but I've fixed it now. Commented Feb 5, 2018 at 20:36
• Wow, even quite, quite faster than my approach, +1... Commented Feb 5, 2018 at 20:39
• @C.E. Can I set the DistanceFunction as MeanEuclideanDistance? Commented Feb 6, 2018 at 11:05
• @Majis I added an example of that to the answer. Commented Feb 6, 2018 at 17:21

I guess what you are looking for is Subsets. However, you can implement this with Table as well. Something like this should work:

distance[{{i_, j_}, {k_, l_}}] := ImageDistance[imageparts[[i, j]], imageparts[[k, l]]];

With[{pos = Flatten[Table[{i, j}, {i, len}, {j, len}], 1]},
{distance[#], #} & /@ Subsets[pos, {2}]
]

This gives you the 120 distances with the information which image-parts were compared.

First of all, we should create all the combinations avoiding to calculate ImageDistance of the image with itself, and twice for two images, as noted by OP. Thus :

n=4;
comparisons = Cases[Union[Tuples[Range[n], {2, 2}],
SameTest -> ((Reverse[#1] == #2) &)], {a_, b_} /; a != b]

Then, we can valuate the ImageDistance of all comparisons:

ImageDistance[Part[imageparts, #[[1, 1]], #[[1, 2]]],
Part[imageparts, #[[2, 1]], #[[2, 2]]]] & /@ comparisons

While the last calculation can be fast, it depends on the number of subimages. Bear in mind that creating the comparisons becomes sloppy when $n$ increases (in my old Intel I3 processor).

Use flatten arrays [[i*n+j]] and [[k*n+l]] instead of double indices and compare only if k*n+l>i*n+j. And use parallel table.

• That is a valid tip, quite minimal though. Could you provide full code / timings with ExampleData images for example?
– Kuba
Commented Feb 6, 2018 at 8:15