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- […]
RANSAC Algorithm parameter explained Read More »
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 &
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
int c[]={1,3,4}; // value of coins int k=3; //number of cpins that we have /* The d[20] array is for memorization, for instance if we computed f_coin_problem_memo(3), we put this value in d[3] and we don't compute it again, we just use d[3] instead of f_coin_problem_memo(3) */ int d[20]; int f_coin_problem_memo(int x) { if (x < 0) return 1e9; if (x == 0) return 0; if (d[x]) return d[x]; int u = 1e9; int u_old = 1e9; for (int i = 0; i < k; i++) { u_old=u; u = std::min(u, f_coin_problem_memo(x-c[i]) +1); } d[x] = u; return d[x]; } |
|
1 2 |
The minimum number of coins from the set {1,3,4} to sum up value of 12 is: 3 |
2)The most (least) costly path on a grid (dynamic time warping).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
finding a path in an n × n grid from the upper-left corner to the lower-right corner. We are only allowed to move right or down. 1,1 1,2 .... 1,X 2,1 2,2 .... 2,X . . . Y,1 Y,2 .... Y,X 3 7 9 2 7 9 8 3 5 5 1 7 9 8 5 3 8 6 4 10 6 3 9 7 8 */ int grid[5][5]={{3,7, 9, 2, 7},{9, 8, 3 ,5 ,5},{1, 7 ,9 ,8 ,5},{3, 8, 6 ,4 ,10},{6, 3 ,9 ,7 ,8}}; int memo[5][5]{{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1}}; std::vector<int>x_solution,y_solution; int f_paths_in_grid(int y,int x) { if((x==0)&& (y==0)) { memo[y][x]=grid[0][0]; } else if (x==0) { if(memo[y][x]<0) { memo[y][x] =f_paths_in_grid(y-1,x) +grid[y][x]; } } else if(y==0) { if(memo[y][x]<0) { memo[y][x]=f_paths_in_grid(y,x-1) +grid[y][x]; } } else if(memo[y][x]<0) { memo[y][x]=std::max(f_paths_in_grid(y,x-1) ,f_paths_in_grid(y-1,x) )+grid[y][x]; } return memo[y][x]; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
maximum sum on a path from the upper-left corner to the lower-right corner is: 67 3|10|19|21|28| --------------- 12|20|23|28|33| --------------- 13|27|36|44|49| --------------- 16|35|42|48|59| --------------- 22|38|51|58|67| --------------- |
3)Levenshtein edit distance.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
int LevenshteinDistance(std::string s, std::string t ) { int cost; /* base case: empty strings */ if (s.length() == 0) return t.length(); if (t.length() == 0) return s.length(); /* test if last characters of the strings match */ if (s.at(s.length()-1) == t.at(t.length()-1) ) cost = 0; else cost = 1; /* return minimum of delete char from s, delete char from t, and delete char from both */ return std::min( std::min(LevenshteinDistance(s.substr(0, s.size()-1 ),t ) + 1,LevenshteinDistance(s , t.substr(0, t.size()-1 )) + 1 ) , LevenshteinDistance(s.substr(0, s.size()-1 ), t.substr(0, t.size()-1 )) + cost ); } |
|
1 2 |
The Levenshtein distance between saturday and sunday is: 3 |
4)Seam Carving. I have written a tutorial on that
Examples of Dynamic Programming with C++ and Matlab Read More »
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
Peak Signal-to-Noise Ratio (PSNR) in Image using OpenCV and Matlab Read More »
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.
Creating Hybrid Image with Matlab Read More »
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 |
run('<path_to_vlfeat>/toolbox/vl_setup') |
1.Detect key points and extract descriptors. In the image below you can see some SIFT key
Stitching image using SIFT and Homography Read More »
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 the Netherlands and now you like to know how much they are different. Two commonly used method
Analytic distance metric for Gaussian mixture models Read More »
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
Lucas–Kanade method optical flow with MATLAB Read More »
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
%% Creating signal Fs=1000; %Sampling fresquncy T_inc=1/Fs; %Time increament T_measure=1.5; %Duration of measurment time=0:T_inc:T_measure - T_inc; %Vector contains sampling time L=length(time); %Lenght of signal %% Sum of a 60Hz and 120 Hz sinusoidal f1=120; f2=60; phi1=1.5; phi2=2.4; amplitude1=1.5; amplitude2=2.2; y=amplitude1*sin(2.*pi.*f1*time+phi1) + amplitude2*sin(2.*pi.*f2*time+phi2); |
Getting Fourier transform of the signal:
|
1 |
signal_FFT=fft(y,L); |
|
1 2 3 |
signal_FFT=fft(y,L)/L; amplitude=2*abs( signal_FFT(1: floor(L/2) +1) ); frequency=Fs/2*linspace(0,1, floor(L/2) +1); |
Displaying Adjusted Frequencies of signal with Fast Fourier transform Read More »