# Finding Homography Matrix using Singular-value Decomposition and RANSAC in OpenCV and Matlab



Solving a Homography problem leads to solving a set of homogeneous linear equations such below:

\left(
\begin{array}{ccccccccc}
-x1 & -y1 & -1 & 0 & 0 & 0 & x1*xp1 & y1*xp1 & xp1\\
0 & 0 & 0 & -x1 & -y1 & -1 & x1*yp1 & y1*yp1 &  yp1\\
-x2 & -y2 & -1 & 0 & 0 & 0 & x2*xp2 & y2*xp2 & xp2\\
0 & 0 & 0 & -x2 & -y2 & -1 & x2*yp2 & y2*yp2 & yp2\\
-x3 & -y3 & -1 & 0 & 0 & 0 & x3*xp3 & y3*xp3 & xp3\\
0 & 0 & 0 & -x3 & -y3 & -1 & x3*yp3 & y3*yp3 & yp3\\
-x4 & -y4 & -1 & 0 & 0 & 0 & x4*xp4 & y4*xp4 & xp4\\
0 & 0 & 0 & -x4 & -y4 & -1 & x4*yp4 & y4*yp4 & yp4\\
\end{array}
\right) *H=0

$$H^{*} \underset{H}{\mathrm{argmin}}= \|AH\|^{2}$$ subject to $$\|H\|=1$$

We can’t use least square since it’s a homogeneous linear equations (the other side of equation is 0 therfore we can’t just multyly it by the psudo inverse). To solve this problem we use Singular-value Decomposition (SVD).

For any given matrix $$A_{M{\times}N}$$

\underbrace{\mathbf{A}}_{M \times N} = \underbrace{\mathbf{U}}_{M \times M} \times \underbrace{\mathbf{\Sigma}}_{M\times N} \times \underbrace{\mathbf{V}^{\text{T}}}_{N \times N}

$$U$$ is an $${M\times M}$$ matrix with orthogonal matrix (columns are eigen vectors of A).
$$\Sigma$$ is an $${M\times N}$$ matrix with non-negative entries, termed the singular values  (diagonal entries are eigen values of A).
$$V$$ is an $${N\times N}$$ orthogonal matrix.

$$H^{*}$$ is the last column of $$V$$

# Stitching image using SIFT and Homography

This Matlab tutorial I use SIFT, RANSAC, and homography to find corresponding points between two images. Here I have used vlfeat to find SIFT features.

Full code is available at my GitHub repository

Major steps are:

1.Detect key points and extract descriptors. In the image below you can see some SIFT key points and their descriptor.

2.Matching features:

3.Pruning features

In this step, I only took first k top matches.

number_of_top_matches_to_select=90;

4.Estimating transformation using RANSAC

I used RANSAC to estimate the transformation.

5.Compute optimal transformation

Finally, I used the least square method to find the affine transformation between two images.