# RANSAC Algorithm parameter explained

In this tutorial I explain the RANSAC algorithm, their corresponding parameters and how to choose the number of samples:

N = number of samples
e = probability that a point is an outlier
s = number of points in a sample
p = desired probability that we get a good sample
N =log(1-p) /log(1- (1- e) s )

ref: 1

# 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$$

# Examples of Dynamic Programming with C++ and Matlab

In this tutorial, I will give you examples of using dynamic programming for solving the following problems:

1)Minimum number of coins for summing X.

2)The most (least) costly path on a grid (dynamic time warping).

3)Levenshtein edit distance.

4)Seam Carving. I have written a tutorial on that here and the recursive part is in the following lines:

The examples are taken from “Competitive Programmer’s Handbook” written by Antti Laaksonen.

# Peak Signal-to-Noise Ratio (PSNR) in Image using OpenCV and Matlab



Peak signal-to-noise ratio (PSNR) shows the ratio between the maximum possible power of a signal and the power of the same image with noise. PSNR is usually expressed in logarithmic decibel scale.

$$MSE =1/m*n \sum_{i=0}^{m-1} \sum_{j=0}^{n-1} [ Image( i,j) -NoisyImage( i,j) ] ^2$$
$$PSNR =10* \log_{10} \Bigg(MAXI^2/MSE\Bigg)$$

MSE is Mean Square Error and MAXI is the maximum possible pixel value of the image. For instance if the image is uint8, it will be 255.

Ref [1],[2], [3], 4

# Creating Hybrid Image with Matlab

In this tutorial, I’m gonna show you how to create hybrid images . Basically, you need to filter your first image with high pass filter and the second image with a low pass filter and then add theses two images. The following code shows how to do that. The full code is available at my GitHub.

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

# Analytic distance metric for Gaussian mixture models

In many applications, you need to compare two or more data sets with each other to see how much they are similar or different. For instance, you have measured the height of men and women in Japan and Netherlands and now you like to know how much they are different.



Two commonly used method for measuring distances are the Kullback-Liebler divergence and the Bhattacharyya distance.

KL divergence (Kullback-Liebler divergence) measures the difference between two probability distributions p and q.

\label{Kullback_Lieblerdivergence}
D
{KL}(p||q)=\int_{-\infty}^\infty p(x)\log\frac{p(x)}{q(x)} \,\mathrm{d}x

But it only works if your data is made of a single Gaussian and it is not applicable If your data is made of a mixture of Gaussians.

Sfikas et al [1]  have extended the Kullback Liebler divergence for GMM and proposed a distance metric using the values (\mu ,\Sigma,\pi ) for each one of the two distributions in the following form:

\label{analytical_Kullback_Lieblerdivergence}
C2(p||q)=-\log \large[ \frac{2\sum
{i,j}\pi{i}\pi{j}^{\prime} \sqrt{ \frac{|V{ij}|}{e^{k{ij}}|\sum{i}| |\sum{j}^{\prime}|} } }
{
\sum{i,j}\pi{i}\pi{j} \sqrt{ \frac{|V{ij}|}{e^{k{ij}}|\sum{i}| |\sum{j}|} }+
\sum
{i,j}\pi{i}^{\prime}\pi{j}^{\prime} \sqrt{ \frac{|V{ij}|}{e^{k{ij}}|\sum{i}^{\prime}| |\sum{j}^{\prime}|} }
}
\large]

Where:
\label{Kullback_Liebler_divergenceDetails1}
V
{ij}=(\Sigma{i}^{-1} +\Sigma{j}^{-1})^{-1}

and
\label{Kullback_Liebler_divergenceDetails2}
K
{ij}=\mu{i}^{T}\Sigma{i}^{-1}(\mu{i}-\mu{j}^{\prime})+\mu{j}^{\prime T}\Sigma{j}^{\prime -1}(\mu{j}^{\prime}-\mu{i})

Code in matlab:

Update: Here is a very nice interactive vizualiztaion of Kullback-Liebler divergence.

# Lucas–Kanade method optical flow with MATLAB

In this tutorial, I will show you how to estimate optical flow based on Lucas–Kanade method.  This project has the following scripts: Optical_flow_estimation, myFlow, myWarp, computeColor, flowToColor.

The myFlow does the main job, it gets two images and a window length (patch length) and a threshold for accepting the optical flow.  In the following, you see the myFlow.  You can uncomment figure function calls to see output result of each step. The other scripts are just for visualization. you can access the code and image in my Github repository.

 first image second image estimated optical flow color map of optical flow

# Displaying Adjusted Frequencies of signal with Fast Fourier transform

In this tutorial, I will show you how to get Fast Fourier transform of a signal and then correctly display the signal. Link to the code in my Github repository.

Signal in time domain

Getting Fourier transform of the signal:

The signal in frequency domain (Bins)

The signal in frequency domain consists of 60Hz and 120Hz.