Detecting garbage homographies from findHomography in OpenCV?

Question

I'm using findHomography on a list of points and sending the result to warpPerspective.

The problem is that sometimes the result is complete garbage and the resulting image is represented by weird gray rectangles.

How can I detect when findHomography sends me bad results?

Cutoff

Answer 1

There are several sanity tests you can perform on the output. On top of my head:

1. Compute the determinant of the homography, and see if it's too close to zero for comfort.
2. Even better, compute its SVD, and verify that the ratio of the first-to-last singular value is sane (not too high). Either result will tell you whether the matrix is close to singular.
3. Compute the images of the image corners and of its center (i.e. the points you get when you apply the homography to those corners and center), and verify that they make sense, i.e. are they inside the image canvas (if you expect them to be)? Are they well separated from each other?
4. Plot in matlab/octave the output (data) points you fitted the homography to, along with their computed values from the input ones, using the homography, and verify that they are close (i.e. the error is low).

A common mistake that leads to garbage results is incorrect ordering of the lists of input and output points, that leads the fitting routine to work using wrong correspondences. Check that your indices are correct.

Stylistic

Could anyone explain 2. condition further? How can i compute SVD and and verify that the ratio of the first-to-last singular value is sane with OpenCV? – Shanan

opencv.willowgarage.com/documentation/cpp/… pass NO_UV, as you are only interested in the singular values. Then compute ratio (condition number) of the first to last singular value. See also, for an explanation of the condition number: books.google.com/… – Stylistic

@Franco thanks for your great answer. I have a final question in the book it says "a matrix is singular if the condition number is infinite, and ill-conditioned if it is too large." So when you are saying "check if condition number is sane" you mean it is not infinite or not too large. My confusion starts here, what is too large, is there a fixed number or is there a calculation for it? I have tried to google it and someone asked same question but haven't got any useful answer yet. – Shanan

Depends on the machine precision for the numeric type you are using (it's in the sentence right past the one you quote). For IEEE-741 double-precision floating point, 10^15 is about as high as you want to go. – Stylistic

Actually i read that sentence however my test cases show that some big condition number but way smaller than 10^15 gives bad results(garbage homography matrix) so i was hoping to find out a smaller threshold for condition number. – Shanan

The numbers in the matrix are meaningless in themselves, what matters is the reprojection error. Set a threshold so that, for your application, the error is less than a pixel. – Stylistic

Can you explain your first point a little more? Why would a determinant value close to 0 would mean a bad homography? I calculate homography accuracy using hg_acc= float(np.sum(status)) / len(status) where H, status = cv2.findHomography(p1, p2, HMETHOD, 10). And I found out that hg_acc could be between 85-90%, and yet the determinant value would vary from 0.07 to ~5000. – Mantel

An exactly singular matrix means that points in one 2D image are mapped to a less-than-2D subspace in the other image (a line, a point), i.e. the estimated homography would be warping the image into nothing. A nearly singular matrix is indicative of a rather extreme warp. Given that you are (usually) doing arithmetic with limited precision, the accuracy of the estimated mapping is likely to be quite bad. – Stylistic

@FrancescoCallari thanks for that. I understood most of it, and kinda had to google what a singular matrix was (forgot all basic math :( ). So what you're saying is kinda this: math.stackexchange.com/a/166028. Also, one more question: What do negative values in homography matrix mean for the quality of the homography? That it's overly warped? Thanks. – Mantel

No special meaning whatsoever - e.g. translations can go left or right, very precisely too ;-) – Stylistic

@FrancescoCallari I am getting singular value 3.23563e+06 determinant of homography 0.00281106, and the output I am getting is very bad. Is this because of H matrix. or maybe because I am using only 5-6 features for H calculation. – Sarsen

Answer 2

Understanding the degenerate homography cases is the key. You cannot get a good homography if your points are collinear or close to collinear, for example. Also, huge gray squares may indicate extreme scaling. Both cases may arise from the fact that there are very few inliers in your final homography calculation or the mapping is wrong.

To ensure that this never happens:
1. Make sure that points are well spread in both images.
2. Make sure that there are at least 10-30 correspondences (4 is enough if noise is small).
3. Make sure that points are correctly matched and the transformation is a homography.

To find bad homographies apply found H to your original points and see the separation from your expected points that is |x2-H*x1| < Tdist, where Tdist is your threshold for distance error. If there are only few points that satisfy this threshold your homography may be bad and you probably violated one of the above mentioned requirements.

Boric

Answer 3

But this depends on the point-correspondences you use to compute the homography... Just think that you are trying to find a transformation that maps lines to lines (from one plane to another), so not any possible configuration of point-correspondences will give you an homography that creates nice images. It is even possible that the homography maps some of the points to the infinity.

Immovable

Mapping points to infinity means that there are some points at infinity since findHomography() function minimizes the right metrics (sum of squared coordinate differences). In short, Homography is first approximated through a linear algorithm (DLT) which minimizes the error in parameters, which is sub-optimal; its output is used as a guess for a non-linear solution (Levenberg-Marquardt algorithm) that minimizes a correct metrics - the sum of squared coord. differences; If the guess is inaccurate, the algorithm diverges and got stuck in local minima, which produces incorrect solution. – Boric