Filtering RANSAC Estimated Homographies

Question

I am using RANSAC algorithm for homography estimation between pairs of images taken with cameras which do not have any translation between them (pure rotation and change of scale/zoom). It works well in half of the cases. The correct output looks like this:

The red lines are filtered correspondences and the quadrilaterals illustrate how the homography distorts perspective.

Sometimes, however, many bad cases happen, like these:

I already have a simple test in the RANSAC loop. It makes a simple quadrilateral (a unit square) and transforms it with sample transform. Then it looks whether the transform kept its convexity.

Still, however, bunches of concave quadrilaterals come out.

Do you have any idea how to properly test the homography, if it behaves "nicely" and filter out the incorrect solutions?

I found some code where they test that none of the three transformed points are colinear. But this does not seem sufficient as it will not filter out deltoids and other "invalid" quadrilaterals...

Answer 1

There is an interesting paper on this topic: http://link.springer.com/chapter/10.1007%2F978-3-642-17691-3_19#

The paper describes a method to filter out some wrong correspondences before computing homographies in the RANSAC algorithm.

Answer 2

There is a problem in checking whether the homography is OK.

The algorithm for checking correct homographies may interest someone, so I will write it down here:

1) Create a quadrilateral $ABDC$ with vertex coordinates (in homogenous coordinates):

$$\begin{eqnarray} A:& (-w/2,-h/2, 1.0) \\ B:& (w/2,-h/2, 1.0) \\ C:& (-w/2,h/2, 1.0) \\ D: &(w/2,h/2, 1.0) \end{eqnarray}$$

where $w,h$ are width and height of the image, respectively. If the whole image frame (a rectangle) is transformed to convex quadrilateral, than any convex quadrilateral within it will also be transformed "neatly".

2) Create transformed quadrilateral $A'B'D'C'$ in which every vertex is transformed using the computed homgraphy (e.g. $C'=HC$ ). From now on, all points will be converted to non-homogenous coordinates.

3) Compute vectors $\vec{u}$, $\vec{v}$ for parametric representation of diagonals:

$$\begin{eqnarray}d_{1} :& A+(D-A)s =A+ \vec{u}s \\ d_{2} :& B + (C-B)t=B+\vec{v}t \end{eqnarray}$$

The intersection of diagonal comes from $d_{1}=d_{2}$:

$$t=\frac{1}{d}\left[(B_{y}-A_{y})\vec{u}_{x} - (B_{x}-A_{x})\vec{u}_{y}\right]$$

$$s=\frac{1}{d}\left[(A_{x}-B_{x})\vec{v}_{y} - (A_{y}-B_{y})\vec{v}_{x}\right]$$

Then the convex quadrilateral satisfies $s,t \in (0,1)$.

In practice, one can introduce a fudge factor to avoid not only non-convex and degenerate quadrilaterals, but also near-degenerate ones, like when three points are near colinear. So the test can be modified such that $s,t \in (\lambda, 1.0-\lambda)$, where lambda is a small number (e.g. $\lambda=0.01$).

Older problem, fixed in the above algorith:

I found the problem here - having a certain homography, the test can pass for a smaller quadrilateral, but not for the larger one. This is why some "ill" homographies passed through.

The green square represents a source image, the orange is a transformed one. As you can see, the left hand one is convex, but starts deforming as the source is larger:

Finally even larger source yield non conver quadrilateral:

I made a mistake with scaling. The points in homogenous coordinates $(x,y,w)$ were scaled in $x$ and $y$ direction, but in $w$. This is why the same transform produced different quadrilaterals.

I have corrected the algorithm accordingly.

Answer 3

If you have estimated the homography as $x_i \sim Hx_i^'$ and you calculate the model error as $\sum_{j=1\dots n}\|x_j - Hx_j^'\|$ you may face problems when the estimated planes are almost perpendicular. You can increase the robustness by estimating another homography $H^'$ such that $x^' = H^'x$ and calculating the model error as $\sum_{j=1\dots n}\|x_j - Hx_j^'\| + \|x_j^' - H^'x\|$.

See Hartley and Zisserman - Multiple View Geometry on Computer Vision chapter 4.2 and especially 4.2.3 and equation (4.8).