Keypoint Descriptor Matching: How to calculate a goodness-of-fit per template?

Question

I am not sure whether this belongs on stackoverflow or another stackexchange site - input very welcome here.

I have used python OpenCV to match a target image's BRISK keypoint descriptors to - in turn - three different templates.

What is a practical, robust, statistically-sound way to decide which template is the best-fitting one?

Right now I calculate the number of cv2.RANSAC inliers returned by cv2.findHomography (which incidentally doesn't return a goodness-of-fit statistic) and take the template that has the highest number.

I have looked at histograms of descriptor distances, which always seem to be gaussians centred (weirdly) at about 105 (units?).

https://en.wikipedia.org/wiki/Random_sample_consensus seems quite useful.

Guidance much appreciated - thanks!

Pore

Could you explain a bit more why you are not happy choosing the template with the highest inlier percentage? – Advice

@Advice Thanks for the question. I come from a Bayesian background, so it just seems a bit ad-hoc to me. Ideally I'd like to be able to do model selection i.e. quantify the difference in goodness-of-fit in terms of odds, and the inlier percentage doesn't give that. I am wondering about reprojection error, condition of H matrix etc. - findHomography must calculate a likelihood internally but does not return it. – Pore

Answer 1

This started as a comment but was getting a bit too long.

Indeed OpenCV computes the reprojection error internally and does not return it. But you could do the same by yourself once you obtain the homography, no? As a matter of fact the algorithm minimizes the sum of the reprojection error over all the points. A quite complete description of the process is in the OpenCV docs

Since you have the matches (hence the image coordinates of both source and template points). You can compute the average reprojection error, possibly only using points that are treated as inliers, for each of the templates and choose the lowest one.

From a similar answer on another site:

computed_pt = H * source_pt
error_pt = sqrt( (computed_pt.x - dst_pt.x)*(computed_pt.x - dst_pt.x) + (computed_pt.y - dst_pt.y)*(computed_pt.y - dst_pt.y) )

to compute the euclidean distance between the two points.

Advice

Thank you so much for this clear explanation. A couple of questions: (i) Is e.g. cv2.warpPerspective (or another?) equivalent to the first line (not that your line isn't easy enough as is)? And (ii) Since you have calculated the residual sum of squares, I can relate this to a chisq and hence calculate a Delta chisq for model selection, right? (But what to use for the noise sigma?) I'd love it if findHomography did output the likelihood at each iteration because then at least I could explore the shape of the surface... But probably overkill here. Thanks again – Pore

(cv2.perspectiveTransform() rather) – Pore

(i) It looks that cv2.perspectiveTransform does exactly what you expect. (ii) Unfortunately I am not an expert with chisq distribution so I am unable to help. All I can add is that maybe(?) sigma should be the std dev for feature extraction, which, although dependent from the extractor itself, as a rule of thumb you can assume ~0.5 pixel, not sure this is helpful though... – Advice

No problem at all - super grateful for your answer and the info - I will just test out the code and then hopefully will be in a position to accept the answer :) – Pore