Five point algorithm for essential matrix, 1 year later …

In 2011, some time around April, I had a motorcycle accident which left me with a broken right hand. For the next few weeks I was forced to take public transport to work, *shudder* (it takes me twice as long to get to work using Melbourne’s public transport than driving). I killed time on the train reading comic books and academic papers. One interesting one I came across was Five-Point Algorithm Made Easy by Hongdong Li and Richard Hartley for calculating the essential matrix using five points (minimum). Now here is something you don’t see everyday in an academic paper title, ‘easy’. I’ve always be meaning to get around to learning the five-point algorithm and this one boasts an easier implementation than David Nister’s version. Seemed like the perfect opportunity to try it out, I mean how hard could it be? Well …

Over one year later of on and off programming I finally finished implementing this damn algorithm! A fair bit of time was spent on figuring out how to implement symbolic matrices in C++. I was up for using existing open source symbolic packages but found that they all struggled to calculate the determinant of a 10×10 symbolic matrix of polynomials. If you do the maths, doing it the naive way is excruciatingly slow, at least in the orders of 10 factorial. I ended up writing my own simple symbolic matrix class. I also wrote a Maxima and PHP script to generate parts of the symbolic maths step into C++ code, fully expanded out in all its glory. The end result is a rather horrendous looking header file with 202 lines of spaghetti code (quite proud of that one actually).

The second major road black was actually a one liner bug in my code. I was doing the SVD of a 5×9 matrix in OpenCV. By default OpenCV’s SVD doesn’t do the full decomposition for Vt unless you tell it to eg. cv::SVD svd(F, cv::SVD::FULL_UV). So I was using the 5×9 version of Vt instead of 9×9 to grab the null basis, which was incorrect.

It was quite a hellish journey, but in the end I learnt something new and here’s the code for you all to enjoy.


Last update: 25th August 2013

5point-0.1.5.tar.gz (requires OpenCV)

5Point-Eigen-0.1.5.tar.gz (requires Eigen)

The OpenCV and Eigen version produce identical output. The Eigen version was ported by Stuart Nixon. The file 5point.cpp in the Eigen version has a special #ifdef ROBUST_TEST that you can turn on to enable a more robust test against outliers. I have not thoroughly test this feature so it is turned off by default.

Given 5 or more points, the algorithm will calculate all possible essential matrix solutions and return the correct one(s) based on depth testing. As a bonus it even returns the 3×4 projection matrix. The whole process takes like 0.4 milliseconds on my computer. There’s a lot of room for speed improvement using more efficient maths. David Nister’s paper list some improvements in the appendix.

Python port of rigid_transform_3D.m and first impression using Numpy

As part of my Python learning, Numpy in particular, I’ve ported rigid_transform_3D.m to Python. You can download it from at the bottom of the page.

My first impression of using Numpy to port the Matlab script hasn’t been too thrilling. The syntax isn’t as a nice to use as Matlab/Octave. The choice between using an array or matrix type have different trade offs. If I use an array (as recommended by the short answer) I can’t use the * to perform a standard matrix multiplication, a bit annoying to say the least. Indexing a matrix is slightly different compared to Matlab, for example A[0:3] means elements 0,1,2 but not 3 (not a big deal). Another problem I found was trying to do an outer product using dot(A, A.T) or dot(A.T, T), which returned a scalar value instead of a matrix. It seems arrays don’t make a distinction between row/column vector. The solution was to explicitly use the numpy.outer function.

Other than those small pet peeves (so far), I haven’t come across anything show stopping yet. I guess I have to tell myself that Python is a general purpose scripting language, unlike Matlab/Octave which was designed with matrices being the fundamental data type.

Preview of SfM + texture mapping

A few people in the past have expressed interest in texture mapping the point clouds from SfM. I said I probably won’t get around to writing software for it, even though I’ve done it before. Guess what? I’ve back flipped and have decided to do it! Here’s a sneak preview …

The pipeline is as follows:

RunSFM -> Meshlab -> TextureMesh (new program I wrote) -> ViewMesh (custom viewer)

The Meshlab step is a manual process, but can be automated using their server program. The output mesh is a custom, but easy to read, text format. I haven’t looked around for any standardised format.

More details to come in the following days. First, I need to package up the software, write instructions and a guide on how to use Meshlab.