# Filtering RANSAC Estimated Homographies

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...

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.

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.

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).

• The quadrilaterals displayed are just put in there. I am sure about the correspondences as the fit is very good. I have used normalized DLT algorithm suggested by Hartley & Zisserman and then used iterative refinement and guided matching as you mentioned. – Libor Apr 10 '12 at 16:59
• But the fit of the homography can not be that good as in the first picture there is two groups of points: ones at the apartment building (which are probably on a same plane) and the ones on the trees (which probably are not even on a same plane inside their own group). Are you sure you did not mean to use fundamental matrix? – buq2 Apr 10 '12 at 17:10
• The lines connect corresponding points and I checked them all - when the images are aligned, they all meet. When I exclude the bad matching image pairs, it results in a nice panorama. – Libor Apr 10 '12 at 17:17
• The images are made using a rotating camera, so it may seem that the planes change, but since the cameras rotate about optical centre, I am pretty sure the a homography is estimated. I can even compute focal length and rotation matrix from it. But the problem is somewhere else, a quirk in my software I have to find... – Libor Apr 10 '12 at 17:21
• Ahh, you did not include the information that there is no translation between the cameras. Then you are right and homography describes the transformation between the images. – buq2 Apr 10 '12 at 17:32