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 &
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 \)
|
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 51 52 53 54 55 56 57 58 59 60 61 |
function M= affine_least_square(x0,y0, x1,y1, x2,y2, xp0,yp0, xp1,yp1, xp2,yp2) % This function finds the affine transform between three points % an affine transformation with a 3x3 affine transformation matrix: % % [M11 M12 M13] % [M21 M22 M23] % [M31 M32 M33] %Since the third row is always [0 0 1] we can skip that. % [x0 y0 1 0 0 0 ] [M11] [xp0] % [0 0 0 x0 y0 1 ] [M12] [yp0] % [x1 y1 1 0 0 0 ] [M13] [xp1] % [0 0 0 x1 y1 1 ] * [M21] = [yp1] % [x2 y2 1 0 0 0 ] [M22] [xp2] % [0 0 0 x2 y2 1 ] [M23] [yp2] % A * X = B %A -> 6x6 %X -> 6x1 in fact %X=A\B A=[x0 y0 1 0 0 0 ; 0 0 0 x0 y0 1 ; x1 y1 1 0 0 0 ; 0 0 0 x1 y1 1 ; x2 y2 1 0 0 0;0 0 0 x2 y2 1]; B=[xp0; yp0; xp1; yp1; xp2 ; yp2 ]; % X=A\B; % this is what we need but accroding to https://www.mathworks.com/matlabcentral/newsreader/view_thread/170201 %The following is better: X=pinv(A)*B; M11 =X(1,1); M12 =X(2,1); M13 =X(3,1); M21 =X(4,1); M22 =X(5,1); M23 =X(6,1); M=[ M11 M12 M13; M21 M22 M23; 0 0 1]; end |
And testing the code:
|
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 51 52 53 54 55 56 57 58 59 60 61 62 63 |
clc; clear all; %This is a simple test that project 3 point with an affine trasnform and %then tries to find the transformation: % tform.T and M' should be equal %Points are located at: x0=0; y0=0; x1=1; y1=0; x2=0; y2=1; p1=[x0,y0; x1,y1; x2,y2]; %We rotate them (a roll-rotation around Z axes) theta degree, first %building the rotation matrix theta=24; A11=cosd(theta); A12=-sind(theta); A21=sind(theta); A22=cosd(theta); %Translation part Tx=1; Ty=2; tform = affine2d([A11 A12 0; A21 A22 0; Tx Ty 1]); fprintf('3x3 transformation matrix:') tform.T [x,y]=transformPointsForward(tform,p1(:,1),p1(:,2)); fprintf('transformed points:') [x,y] xp0=x(1,1); yp0=y(1,1); xp1=x(2,1); yp1=y(2,1); xp2=x(3,1); yp2=y(3,1); %finding the tranformation matrix from set of points and their respective %transformed points: M=affine_least_square(x0,y0, x1,y1, x2,y2, xp0,yp0, xp1,yp1, xp2,yp2); fprintf('3x3 affine transformation matrix from least_squares:') M' tform = affine2d(M'); [x,y]=transformPointsForward(tform,p1(:,1),p1(:,2)); [x,y]; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
3x3 transformation matrix: ans = 0.9135 -0.4067 0 0.4067 0.9135 0 1.0000 2.0000 1.0000 transformed points: ans = 1.0000 2.0000 1.9135 1.5933 1.4067 2.9135 3x3 affine transformation matrix from least_squares: ans = 0.9135 -0.4067 0 0.4067 0.9135 0 1.0000 2.0000 1.0000 |
Finding Affine Transform with Linear Least Squares Read More »
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 »
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 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 »
