admin, Author at Robotics with ROS

Open source Structure-from-Motion and Multi-View Stereo tools with C++

Leave a Comment / C++, Computer Vision, Image Processing, Linear Algebra, Tutorials / admin

Structure-from-Motion (SFM) is genuinely an interesting topic in computer vision, Basically making 3D structure from something 2D is absolutely mesmerizing 🙂 There two open source yet very robust tools for SFM, which sometimes compiling them might be complicated, here I will share my experience with you. 1)VisualSFM Prerequisite: 1)Glew Download the glew from SF at http://glew.sourceforge.net/. Do NOT get it from Github as […]

Open source Structure-from-Motion and Multi-View Stereo tools with C++ Read More »

Computing OpticalFlow with OpenCV

1 Comment / C++, Computer Vision, Tutorials / admin

There are two main approaches for computing optical flow, computing optical flow for all pixel or computing optical flow for corners. 1. Computing optical flow for all pixel 2. Computing optical flow for corners

Computing OpticalFlow with OpenCV Read More »

Finding Relative Between Frames

RANSAC Algorithm parameter explained

2 Comments / Machine Learning, Matlab, Tutorials / admin

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

3 Comments / C++, Computer Vision, Image Processing, Linear Algebra, Matlab, Tutorials / admin

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 Homography Matrix using Singular-value Decomposition and RANSAC in OpenCV and Matlab Read More »

Finding Affine Transform with Linear Least Squares

3 Comments / Computer Vision, Image Processing, Linear Algebra, Tutorials / admin

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

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

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:

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];

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:')

tform = affine2d(M');

[x,y]=transformPointsForward(tform,p1(:,1),p1(:,2));

[x,y];

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

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

Leave a Comment / C++, Machine Learning, Matlab, Tutorials / admin

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.

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];
}

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];

}

The minimum number of coins from the set {1,3,4} to sum up value of 12 is:
3

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

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];
}

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];

}

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

maximum sum on a path from the upper-left corner to the lower-right corner is:

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.

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 );
}

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 );

}

The Levenshtein distance between saturday and sunday is:
3

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

Leave a Comment / C++, Computer Vision, Image Processing, Matlab, Tutorials / admin

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

1 Comment / Computer Vision, Image Processing, Machine Learning, Tutorials / admin

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

3 Comments / Python, Tutorials / admin

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

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 »

Cookie	Duration	Description
cookielawinfo-checbox-analytics	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checbox-functional	11 months	The cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checbox-others	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-necessary	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-performance	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy	11 months	The cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.