# What methods can be used to compute homography

I am trying to understand panorama stitching. I've come to a conclusion that homography is one of the fundamental parts in the process. Now I am trying to make sense of all the information from literature across the web concerning about solving for homography.

I've read about Direct Linear Transform, Least Squares method and RANSAC. However, from what I've read I'd say DLT and RANSAC are the methods to solve homography while Least Squares is just used as additional step in DLT when there are more than 4 correspondence points. Is this right? I feel like I have things mixed up.

• Hey, you should take a look at bachelor and master theses here. My generation (bachelors 2009/10, masters 2011/12) did a lot of things using homographies, you can probably find it described in multiple theses there: some of it is in English, some of it (mostly bachelor thesis) is in Croatian, but from what I see from your profile, you should be okay with that ;) (Disclaimer: some of what I linked to is my own old work) Don't have time to do a nice reply today, but if you get no reply till tomorrow, I'll try and write a complete answer. – penelope Nov 21 '13 at 15:43
• If you find an answer there, it would be nice to write it up here as an answer to your own question! For future readers. :-) – Peter K. Nov 21 '13 at 19:47

I've never actually done Panorama Stitching, but I was talking to people who were, and I was involved in a project where we had to estimate the homography for fine localization for visual navigation, so here it goes.

### Basic approach

Rough outline of the approach using RANSAC (you can read more of the approach in this Master thesis, page 12,13 - unfortunately, in Croatian):

• estimate pairs of corresponding points for two images $A$ and $B$ (lot of them) and get rid of the obviously bad correspondences

(detailed summary of a feature matching approach in my Master Thesis, pages 13-20 - In English)

• pick any four points for the initial estimate of homography $H$

(most details on the numerical methods used to estimate the homography can be probably be found in my Bachelor Thesis (in Croatian), but there should also be some details in this Master Thesis (Cro) and this one (Eng))

• project all points from the image $A$ onto the image $B$ using the first estimation of the homography $H$

• compare the projected points from $A$ to the actual points present in $B$ (using Euclidian distance)

• discard all the point pairs where the distance between projected point from $A$ and corresponding point from $B$ is greater than a threshold $t$ -- those points are outliers

• (this can be repeated several times, possibly with a more constrictive threshold $t$ every time, to get rid of more outliers)

• the points that are left are our population points

• using only the population points, do the final estimation of homography $H_{final}$ just from those points

Coincidentally, if you have the initial rough matching results, the rest of this is implemented in OpenCV, it's a function called findHomography and there is a good StackOverflow post on that. It includes RANSAC (and from what I can read from that post, Least Squares method should have a similar goal as RANSAC, but RANSAC gives better results).

If you need better estimates, you can find references for methods other than RANSAC in this Master thesis (Eng) - pure RANSAC approach is compared to something called MLESAC, and RANSAC coupled with Least Median of Squares method.

Suggestions on an efficient implementation of Homography estimate from points (presuming that you do not want to use OpenCV or some other available implementation) can be found in my Bachelor Thesis (Cro).

To estimate the initial (not-very-precise) pairs of correspondences, you should use matching methods. Those methods are based on:

1. detecting feature points

(there's a lot about that in this DSP question, and especially in this answer you will find a link to the current widely used framework for comparing feature detectors)

2. using appropriate feature descriptors

(nice info in this DSP question)

3. doing matching between those points and possibly some kind of filtering to further better the matches obtained

Matching a point from an image $A$, $x_{A}$ with a descriptor $d(x_{A})$ is usually done just by finding the point in the image $B$, $x_{B}$ with the most similar descriptor $d(x_{B})$ according to Euclidian distance.

The most simple (and surprisingly efficient) filtering method is to compare the distance from $d(x_{A})$ to the closest descriptor $d(x_{B_1})$ and second closest descriptor $d(x_{B_2})$. If $\frac{D_{eucl}(d(x_{A}), d(x_{B_1}))}{D_{eucl}(d(x_{A}),d(x_{B_2})}$ is greater than some coefficient $k \in [0,1]$ (typically $k = 0.6$), the match is rejected. First introduced by D.G. Lowe: Distinctive image features from scale-invariant keypoints.

Additional filtering can be done according to spatial arrangement of the corresponding points. One such interesting method was described in J. Sivic, A. Zisserman: Video Google: A Text Retrieval Approach to Object Matching in Videos.