Finding Relative Between Frames
Finding Relative Between Frames Read More »
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-
RANSAC Algorithm parameter explained Read More »
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 &
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 \)
|
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 »
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.
|
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) 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
Peak Signal-to-Noise Ratio (PSNR) in Image using OpenCV and Matlab Read More »
Seam Carving Algorithm for Content-Aware Image Resizing with Matlab Code
Seam carving is an algorithm for resizing images while keeping the most prominent and conspicuous pixels in the image. The important pixels in an image are usually those who are located over horizontal or vertical edges, so to throw away some pixels we first find horizontal and vertical edges and store their magnitude as pixel
Seam Carving Algorithm for Content-Aware Image Resizing with Matlab Code Read More »
Populating directed graph in networkx from CSV adjacency matrix
|
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 |
import pandas as pd import networkx as nx import matplotlib.pyplot as plt import csv def make_label_dict(labels): l = {} for i, label in enumerate(labels): l[i] = label return l input_data = pd.read_csv('data/adjacency_matrix.csv', index_col=0) #print input_data.head print input_data.values G = nx.Graph(input_data.values) with open('data/adjacency_matrix.csv', 'r') as f: d_reader = csv.DictReader(f) headers = d_reader.fieldnames #print headers labels=make_label_dict(headers) #print labels edge_labels = dict( ((u, v), d["weight"]) for u, v, d in G.edges(data=True) ) pos = nx.spring_layout(G) nx.draw(G, pos) nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels) nx.draw(G,pos,node_size=500, labels=labels, with_labels=True) plt.show() |
Populating directed graph in networkx from CSV adjacency matrix Read More »
Drawing graphs in Python with networkx
|
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
import networkx as nx import matplotlib.pyplot as plt G=nx.Graph() ###########################Adding nodes########################### G.add_node(1) G.add_nodes_from([2,3,4]) #Add an nbunch: iterable container of nodes (e.g. a list, set, graph, file, etc..) H=nx.path_graph(1) #G now contains the nodes of H as nodes of G. G.add_nodes_from(H) #Graph of Graph #G.add_node(H) G.add_node("b") # adds node "behnam" G.add_nodes_from("behnam") # adds 6 nodes: 'b','e' ,'h', 'n', 'a','m' ###########################Adding edges########################### G.add_edge(1, 4) edge_2_3=(2,3) G.add_edge(*edge_2_3) # unpack edge tuple with * #An edge can be associated with any object x using G.add_edge(n1,n2,object=x). edge_2_4=(2,4,{'weight':3.1415}) G.add_edge(*edge_2_4) G.add_edge(1, 2, weight=4.7 ) G.add_weighted_edges_from([(3,4,0.125)]) ###########################Accessing nodes,edges and neighbors########################### print 'Nodes' print G.nodes() print 'List of edges' print G.edges() print 'Neighbors' print G.neighbors(1) #Accessing edges print 'Accessing edges' print G[3] print G[4] print G[4][2]['weight'] for (u,v,d) in G.edges(data='weight'): if d>0.5: print('(%d, %d, %.3f)'%(u,v,d)) ###########################Adding attributes to nodes########################### G.add_node(1, time='5pm') print G.node[1] G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})]) ###########################Multigraphs########################### #allow you to add the same edge twice, possibly with different edge data. MG=nx.MultiGraph() MG.add_weighted_edges_from([(1,2,.5), (1,2,.75), (2,3,.5)]) MG.degree(weight='weight') GG=nx.Graph() for n,nbrs in MG.adjacency_iter(): for nbr,edict in nbrs.items(): minvalue=min([d['weight'] for d in edict.values()]) GG.add_edge(n,nbr, weight = minvalue) print 'shortest path from 1 to 3' print nx.shortest_path(GG,1,3) ###########################Graph operations########################### #subgraph(G, nbunch) - induce subgraph of G on nodes in nbunh #union(G1,G2) - graph union #disjoint_union(G1,G2) - graph union assuming all nodes are different #cartesian_product(G1,G2) - return Cartesian product graph #compose(G1,G2) - combine graphs identifying nodes common to both #complement(G) - graph complement #create_empty_copy(G) - return an empty copy of the same graph class #convert_to_undirected(G) - return an undirected representation of G #convert_to_directed(G) - return a directed representation of G ###########################Ploting Graphs ########################### #nx.draw_spectral(G) #nx.draw_circular(G) #nx.draw_random(G) pos=nx.spring_layout(G) # positions for all nodes nx.draw_networkx_labels(G,pos,font_size=20,font_family='sans-serif') nx.draw(G,pos) plt.show() |
Drawing graphs in Python with networkx Read More »
Hierarchical Clustring in python
Hierarchical Clustering is a method of clustering which build a hierarchy of clusters. It could be Agglomerative or Divisive. Agglomerative: At the first step, every item is a cluster, then clusters based on their distances are merged and form bigger clusters till all data is in one cluster (Bottom Up). The complexity is \( O (n^2log(n) ) \). Divisive: At the beginning,
Hierarchical Clustring in python Read More »
