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:


various grayscale histogram similarity / distance measures (correlation, intersection, $\chi^2$ distance, and Bhattacharyya distance) applied to both the entire images and the image quadrants,
Pearson's correlation coefficient between Haralick texture features,
Hamming distance between various image hashes (aHash, pHash, dHash), and
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.
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'));
I2=rgb2gray(imread('High1.png'));
I3=rgb2gray(imread('High2.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.