Semi-global matching (SGM) is a computer vision algorithm for the estimation of a dense disparity map from a rectified stereo image pair, introduced in 2005 by Heiko Hirschmüller while working at the German Aerospace Center. Given its predictable run time, its favourable trade-off between quality of the results and computing time, and its suitability for fast parallel implementation in ASIC or FPGA, it has encountered wide adoption in real-time stereo vision applications such as robotics and advanced driver assistance systems.
Problem Pixelwise stereo matching allows to perform real-time calculation of disparity maps by measuring the similarity of each pixel in one stereo image to each pixel within a subset in the other stereo image. Given a rectified stereo image pair, for a pixel with coordinates ( x , y ) {\displaystyle (x,y)} the set of pixels in the other image is usually selected as { ( x ^ , y ) | x ^ ≥ x , x ^ ≤ x + D } {\displaystyle \{({\hat {x}},y)|{\hat {x}}\geq x,{\hat {x}}\leq x+D\}} , where D {\displaystyle D} is a maximum allowed disparity shift. A simple search for the best matching pixel produces many spurious matches, and this problem can be mitigated with the addition of a regularisation term that penalises jumps in disparity between adjacent pixels, with a cost function in the form
E ( d ) = ∑ p D ( p , d p ) + ∑ p , q ∈ N R ( p , d p , q , d q ) {\displaystyle E({\boldsymbol {d}})=\sum _{p}D(p,d_{p})+\sum _{p,q\in {\mathcal {N}}}R(p,d_{p},q,d_{q})}
where D ( p , d p ) {\displaystyle D(p,d_{p})} is the pixel-wise dissimilarity cost at pixel p {\displaystyle p} with disparity d p {\displaystyle d_{p}} , and R ( p , d p , q , d q ) {\displaystyle R(p,d_{p},q,d_{q})} is the regularisation cost between pixels p {\displaystyle p} and q {\displaystyle q} with disparities d p {\displaystyle d_{p}} and d q {\displaystyle d_{q}} respectively, for all pairs of neighbouring pixels N {\displaystyle {\mathcal {N}}} . Such constraint can be efficiently enforced on a per-scanline basis by using dynamic programming (e.g. the Viterbi algorithm), but such limitation can still introduce streaking artefacts in the depth map, because little or no regularisation is performed across scanlines. A possible solution is to perform global optimisation in 2D, which is however an NP-complete problem in the general case. For some families of cost functions (e.g. submodular functions) a solution with strong optimality properties can be found in polynomial time using graph cut optimization, however such global methods are generally too expensive for real-time processing.
Algorithm
… excerpt ends here. Continue reading the full article.
