Basic SFM implementation "from scratch", using only basic linear algebra support from numpy. Based on the Challenge Question in section 4.8 in Introduction to Autonomous Mobile Robots, Second Edition .

The implemented algorithm follows the following steps.

Given: two images of the same scene taken from slightly different perspectives. Then:

1. Detect corners in both images using the Harris corner detector.
2. Match corners using descriptors calculated by Squared Sum of Differences. Use cross-check and ratio-test validation to filter out unlikely matches.
3. Estimate a most likely Essential Matrix from the set of remaining matches. The estimation uses RANSAC with the Eight-Point Algorithm as model fitter and the Symmetric Epipolar Distance as model scorer.
4. Decompose the Essential Matrix into rotation and translation, extracting a single possible solution using the cheriality check. Filter out matches which fail the cheirality check.
5. Triangulate and visualize the 3D position of remaining matches.

Example illustration of feature matches which were left inliers after running RANSAC: The small blue markers show the Harris corners. Matching features are connected by colored lines.

• GNU Make 4.1+
• Python 3.10 - install requirements.txt

To run a demo on a predefined dataset:

1. Install the Python requirements.
2. Invoke make demo.

Note: On Mac OS the default make version is too old, please install a modern version using brew install. The new version will be available under the gmake alias.

Besides the Autonomous Mobile Robots book, I used several other sources to implement the various steps of the vision pipeline.

• Wikipedia
• University of Edinburgh
• Hartley, Richard; Andrew Zisserman (2004). Multiple view geometry in computer vision (2nd ed.). Cambridge, UK.

• Mohammed E Fathy; Ashraf Saad Hussein; Mohamed F. Tolba. Fundamental Matrix Estimation: A Study of Error Criteria