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:
- Detect corners in both images using the Harris corner detector.
- Match corners using descriptors calculated by Squared Sum of Differences. Use cross-check and ratio-test validation to filter out unlikely matches.
- 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.
- 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.
- 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:
- Install the Python requirements.
- 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.