Tag Archives: linear algebra

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

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 to seems to have some problems.

2)SiftGPU

Prerequisite:

Install DevIl Image library

open makefile and enable siftgpu_enable_cuda

now go to bin directory and libsiftgpu.so to your vsfm bin directory

VSFM

you can see the some of my results here:

Note: if you don’t have cuda or Nvidia driver you can use your CPU but then you have to limit your file image size and sift binary should be available in your vsfm/bin directory.

Download http://www.cs.ubc.ca/~lowe/keypoints/siftDemoV4.zip and make it and copy the sift binary to vsfm/bin.

2)Colmap

The installation fo this one is almost straightforward except you need the latest version of Ceres Solver (do not use the one binary package from Ubuntu they are old and they won’t work). So download and make and install the Ceres Solver using the following:

Now in the colmap CMakeList.txt add the following line:

just before “find_package(Ceres REQUIRED)”

and now you can make and install it. You can see some of my results here:

In the next post, I will show you how can you do that in OpenCV.

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:

 

Roll, pitch, yaw using Eigen and KDL Frame

 

From Eigen documentation:

If you are working with OpenGL 4×4 matrices then Affine3f and Affine3d are what you want.
Since Eigen defaults to column-major storage, you can directly use the Transform::data()  method to pass your transformation matrix to OpenGL.

construct a Transform:

or like this:

But note that unfortunately, because of how C++ works, you can not do this:

and with KDL Frame: