# Reliably matching a degraded image with the original out of dozens of candidates

I have several collections contaning low-resolution captures of unevenly-lit presentation slides:

and thirty to sixty original high-resolution slide images:

How would you design a similarity measure between the low-resolution captures and the high-resolution slides that would nearly always give the highest score to the correct image pair (or, analogously, a distance measure that approaches zero only for the correct image pair)?

# Experimental setup

So far I tried a machine-learning solution to get a better feeling for how difficult the problem is. I assigned each image pair a feature vector consisting of:

1. various grayscale histogram similarity / distance measures (correlation, intersection, $\chi^2$ distance, and Bhattacharyya distance) applied to both the entire images and the image quadrants,
2. Pearson's correlation coefficient between Haralick texture features,
3. Hamming distance between various image hashes (aHash, pHash, dHash), and
4. Levenshtein distance between the image OCRs normalized by the maximum OCR length.

For the training part of a dataset, I take each feature vector $\vec x$, let $\vec a\vec x + q = 1$ for matching images and $\vec a\vec x + q = -1$ for non-matching images. Then I use linear regression to obtain $\vec a$ and $q$. Finally, for the test part of a dataset, I use $\vec a\vec x+q$ as a scoring function to retrieve a sorted list of high-resolution slides for each low-resolution capture and look at the rank of the correct result.

# Experimental results

With a small hand-annotated dataset, this is getting me the average rank of 6, which is better than random draws, but not nearly good enough for an application that would overlay the high-resolution slides over live capture; such an application will require an average rank that approaches 1. There is an opportunity for the application to be smart and only look at a small window of slides around the current slide, but it still needs to correctly guess the initial slide.

As you might expect, the feature vectors are also quite slow to compute (several seconds per a feature vector with a naive implementation on a higher-end quad-core laptop), which makes the solution unsiutable for a real-time application.

• Have you tries feature point matching methods, like sift? – MimSaad Sep 3 '17 at 16:39
• No, not yet. Do you think these would be well-suited for the task? – Witiko Sep 3 '17 at 21:46
• It is too much complex but definitely would work, but wait a minute, the images are just different in colour and size yes? I mean difference is just scale, i.e resolution (not rotation,...)? – MimSaad Sep 3 '17 at 21:53
• There is no rotation, although there will be some perspective distortion. – Witiko Sep 4 '17 at 0:17
• Ok then if images are basically the same except for their size I have idea to solve the problem. – MimSaad Sep 4 '17 at 9:06

Your question has many solutions which can be good or bad, so I am giving the solution I came up with, hope it is a good one. Since your images are only different in resolution and color I think the best way to compare them is to make their size the same and then to get rid of color and shading differences only compare their edges not the images themselves. This way, you can use comparison criteria that you've tried now independent of color and shading variations. I simply used sum of differences between two images in the code below and for the images you provided seems it works.

Through this code I try to give you an idea idea on how it is working:

I1=rgb2gray(imread('Low.png'));

[h,v]=size(I1);
I2=imresize(I2,[h,v]);
I3=imresize(I3,[h,v]);

d1=edge(I1,'log');
d2=edge(I2,'log');
d3=edge(I3,'log');

score1=sum(sum(abs(d1-d2)))
score2=sum(sum(abs(d1-d3)))


Some low pass filtering before calculating the scores might help.

• While using the edge information to abstract away the differences in color and lighting sounds like a step in the right direction, doing a simple image difference expects the images to be aligned, which they are not. It is curious that the above procedure works. – Witiko Sep 5 '17 at 12:39
• @Witiko , Actually that is why I asked if the difference is only in color and size. – MimSaad Sep 5 '17 at 13:06
• And, as I replied, there is some perspective distortion and the alignment is not perfect. However, I imagine that performing edge detection, segmenting the image (using, say, the watershed algorithm), and then comparing the results of the segmentation might lead to interesting results! – Witiko Sep 5 '17 at 13:11