Tag Archives: matlab

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:

\begin{equation}
\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
\end{equation}

\( 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} \)

\begin{equation}
\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}
\end{equation}

\(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 \)

Finding homography matrix in Matlab between 4 pairs of points

Finding homography matrix in OpenCV between 4 pairs of points

 

Finding homography matrix in OpenCV between N pairs of points

Applying homography matrix in OpenCV



 

Finding Affine Transform with Linear Least Squares

\( \)

linear least squares is a method of fitting a model to data in which the relation between data and unknown paramere can be expressed in a linear form.
\( Ax=b\)
\( X^{*}= \underset{x}{\mathrm{argmin}}= \|Ax-b\|^{2} =(A^{T}A)^{-1}A^{T}b \)

And testing the code:

 

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

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:

0.Adding vlfeat to your Matlab workspace:

 

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.

 

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.