This is a reimplementation of the Semi-Global Matching algorithm using numpy. Both a python script and jupyter notebook is provided implementing SGM. The notebook provides visualizations and explanations for each step in the process.
SGM is a popular classic depth estimation algorithm, known for having good accuracy and speed. Newer stereo depth estimation models like madnet-deep-stereo-with-keras have much higher accuracy, but need to be trained first and require more compute during inference. This makes SGM and excellent option for resource constrained situations.
The Semi-Global Matching algorithm was first introduced by Heiko Hirschmuller in his 2005 paper "Stereo Processing by Semi-Global Matching and Mutual Information". This work built upon earlier stereo matching techniques and introduced a novel approach to reduce the computational complexity while maintaining good accuracy.
The SGM algorithm is an extension of global matching methods that use dynamic programming. It differs from traditional global methods by considering paths in multiple directions (typically 8 directions) rather than just horizontal or vertical paths, which helps to better handle occlusions and textureless regions.
Key contributions of the SGM approach include:
- Efficient cost aggregation using multi-directional path searching
- Reduced computational complexity compared to full global methods
- Improved handling of discontinuities in disparity maps
- Good balance between accuracy and speed
The algorithm has since become a standard baseline for stereo matching evaluation and is widely used in both academic research and practical applications, particularly in robotics and computer vision systems where real-time performance is crucial.
All you need to run the SGM algorithm are a pair of rectified stereo images. Stereo pair examples from the Middlebury dataset are provided for you (cones, figures and teddy). If you would like to review the algorithms accuracy you need groundtruth disparities.
If you would like to use your own stereo images and your stereo camera doesn't provide rectified stereo pairs, then you can calibrate your stereo camera using the methods shown in this repo: stereo-camera-calibration.
If you would like to try more advanced deep learning stereo depth estimation techinques check out madnet-deep-stereo-with-keras.
The python packages needed are shown in the requirements.txt.
The SGM algorithm follows the following process to achieve the depth estimation prediction. Head over to the sgm_numpy_notebook if you would like to see how its done in code.
- The SGM process starts with a pair of rectified stereo images.
- The stereo pair is converted to grayscale.
- A Gaussian blur filter is applied to smooth the images.
- The census transform is then applied to the images.
- The Hamming distance is applied to the census values to calculate the cost volume.
- A cost aggregation technique is applied to remove the noise from the cost volume.
- A median blur filter is applied to remove the streaking.
- Optional: The disparity can then be converted to colour to see the depth better. Red indicates closer and blue further away.
- Previous SMG Implementation in Python, by David-Alexandre Beaupre.
- (SGM) Stereo Processing by Semi-Global Matching and Mutual Information, by Heiko Hirschmuller.
- (Census) Nonparametric Local Transforms for Computing Visual Correspondence, by R Zabih and J Woodfill.
- stereo-camera-calibration by Christian Orr