Semi-global matching

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 ${\displaystyle (x,y)}$ the set of pixels in the other image is usually selected as ${\displaystyle \{({\hat {x}},y)|{\hat {x}}\geq x,{\hat {x}}\leq x+D\}}$, where ${\displaystyle D}$ is a maximum allowed disparity shift.[1]

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

${\displaystyle E({\boldsymbol {d}})=\sum _{p}D(p,d_{p})+\sum _{p,q\in {\mathcal {N}}}R(p,d_{p},q,d_{q})}$

where ${\displaystyle D(p,d_{p})}$ is the pixel-wise dissimilarity cost at pixel ${\displaystyle p}$ with disparity ${\displaystyle d_{p}}$, and ${\displaystyle R(p,d_{p},q,d_{q})}$ is the regularisation cost between pixels ${\displaystyle p}$ and ${\displaystyle q}$ with disparities ${\displaystyle d_{p}}$ and ${\displaystyle d_{q}}$ respectively, for all pairs of neighbouring pixels ${\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.[4]

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.[5]

Illustration of the cost accumulation pattern when computing two-pass SGM with eight directions.

The idea behind SGM is to perform line optimisation along multiple directions and computing an aggregated cost ${\displaystyle S(p,d)}$ by summing the costs to reach pixel ${\displaystyle p}$ with disparity ${\displaystyle d}$ from each direction. The number of directions affects the run time of the algorithm, and while 16 directions usually ensure good quality, a lower number can be used to achieve faster execution.[6] A typical 8-direction implementation of the algorithm can compute the cost in two passes, a forward pass accumulating the cost from the left, top-left, top, and top-right, and a backward pass accumulating the cost from right, bottom-right, bottom, and bottom-left.[7] A single-pass algorithm can be implemented with only five directions.[8]

The cost is composed by a matching term ${\displaystyle D(p,d)}$ and a binary regularisation term ${\displaystyle R(d_{p},d_{q})}$. The former can be in principle any local image dissimilarity measure, and commonly used functions are absolute or squared intensity difference (usually summed over a window around the pixel, and after applying a high-pass filter to the images to gain some illumination invariance), Birchfield–Tomasi dissimilarity, Hamming distance of the census transform, Pearson correlation (normalized cross-correlation). Even mutual information can be approximated as a sum over the pixels, and thus used as a local similarity metric.[9] The regularisation term has the form

${\displaystyle R(d_{p},d_{q})={\begin{cases}0\quad &d_{p}=d_{q}\\P_{1}&|d_{p}-d_{q}|=1\\P_{2}&|d_{p}-d_{q}|>1\end{cases}}}$

where ${\displaystyle P_{1}}$ and ${\displaystyle P_{2}}$ are two constant parameters, with ${\displaystyle P_{1}<P_{2}}$. The three-way comparison allows to assign a smaller penalty for unitary changes in disparity, thus allowing smooth transitions corresponding e.g. to slanted surfaces, and penalising larger jumps while preserving discontinuities due to the constant penalty term. To further preserve discontinuities, the gradient of the intensity can be used to adapt the penalty term, because discontinuities in depth usually correspond to a discontinuity in image intensity ${\displaystyle I}$, by setting

${\displaystyle P_{2}=\max \left\{P_{1},{\frac {{\hat {P}}_{2}}{|I(p)-I(q)|}}\right\}}$

for each pair of pixels ${\displaystyle p}$ and ${\displaystyle q}$.[10]

The accumulated cost ${\displaystyle S(p,d)=\sum _{r}L_{r}(p,d)}$ is the sum of all costs ${\displaystyle L_{r}(p,d)}$ to reach pixel ${\displaystyle p}$ with disparity ${\displaystyle d}$ along direction ${\displaystyle r}$. Each term can be expressed recursively as

${\displaystyle L_{r}(p,d)=D(p,d)+\min \left\{L_{r}(p-r,d),L_{r}(p-r,d-1)+P_{1},L_{r}(p-r,d+1)+P_{1},\min _{i}L_{r}(p-r,i)+P_{2}\right\}-\min _{k}L_{r}(p-r,k)}$

where the minimum cost at the previous pixel ${\displaystyle \min _{k}L_{r}(p-r,k)}$ is subtracted for numerical stability, since it is constant for all values of disparity at the current pixel and therefore it does not affect the optimisation.[6]

The value of disparity at each pixel is given by ${\displaystyle d^{*}(p)=\operatorname {argmin} _{d}S(p,d)}$, and sub-pixel accuracy can be achieved by fitting a curve in ${\displaystyle d^{*}(p)}$ and its neighbouring costs and taking the minimum along the curve. Since the two images in the stereo pair are not treated symmetrically in the calculations, a consistency check can be performed by computing the disparity a second time in the opposite direction, swapping the role of the left and right image, and invalidating the result for the pixels where the result differs between the two calculations. Further post-processing techniques for the refinement of the disparity image include morphological filtering to remove outliers, intensity consistency checks to refine textureless regions, and interpolation to fill in pixels invalidated by consistency checks.[11]

The cost volume ${\displaystyle C(p,d)}$ for all values of ${\displaystyle p=(x,y)}$ and ${\displaystyle d}$ can be precomputed and in an implementation of the full algorithm, using ${\displaystyle D}$ possible disparity shifts and ${\displaystyle R}$ directions, each pixel is subsequently visited ${\displaystyle R}$ times, therefore the computational complexity of the algorithm for an image of size ${\displaystyle W\times H}$ is ${\displaystyle O(WHD)}$.[7]

The main drawback of SGM is its memory consumption. An implementation of the two-pass 8-directions version of the algorithm requires to store ${\displaystyle W\times H\times D+3\times W\times D+D}$ elements, since the accumulated cost volume has a size of ${\displaystyle W\times H\times D}$ and to compute the cost for a pixel during each pass it is necessary to keep track of the ${\displaystyle D}$ path costs of its left or right neighbour along one direction and of the ${\displaystyle W\times D}$ path costs of the pixels in the row above or below along 3 directions.[7] One solution to reduce memory consumption is to compute SGM on partially overlapping image tiles, interpolating the values over the overlapping regions. This method also allows to apply SGM to very large images, that would not fit within memory in the first place.[12]

A memory-efficient approximation of SGM stores for each pixel only the costs for the disparity values that represent a minimum along some direction, instead of all possible disparity values. The true minimum is highly likely to be predicted by the minima along the eight directions, thus yielding similar quality of the results. The algorithm uses eight directions and three passes, and during the first pass it stores for each pixel the cost for the optimal disparity along the four top-down directions, plus the two closest lower and higher values (for sub-pixel interpolation). Since the cost volume is stored in a sparse fashion, the four values of optimal disparity need also to be stored. In the second pass, the other four bottom-up directions are computed, completing the calculations for the four disparity values selected in the first pass, that now have been evaluated along all eight directions. An intermediate value of cost and disparity is computed from the output of the first pass and stored, and the memory of the four outputs from the first pass is replaced with the four optimal disparity values and their costs from the directions in the second pass. A third pass goes again along the same directions used in the first pass, completing the calculations for the disparity values from the second pass. The final result is then selected among the four minima from the third pass and the intermediate result computed during the second pass.[13]

In each pass four disparity values are stored, together with three cost values each (the minimum and its two closest neighbouring costs), plus the disparity and cost values of the intermediate result, for a total of eighteen values for each pixel, making the total memory consumption equal to ${\displaystyle 18\times W\times H+3\times W\times D+D}$, at the cost in time of an additional pass over the image.[13]

• 3D reconstruction
• Computer stereo vision
• Structure from motion

• Hirschmüller, Heiko (2005). "Accurate and efficient stereo processing by semi-global matching and mutual information". IEEE Conference on Computer Vision and Pattern Recognition. pp. 807–814.
• Hirschmuller, Heiko (2007). "Stereo processing by semiglobal matching and mutual information". IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. 30 (2): 328–341. doi:10.1109/TPAMI.2007.1166. PMID 18084062.
• Hirschmüller, Heiko (2011). "Semi-global matching-motivation, developments and applications". Photogrammetric Week. Vol. 11. pp. 173–184.
• Hirschmüller, Heiko; Buder, Maximilian; Ernst, Ines (2012). "Memory efficient semi-global matching". ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. 3: 371–376. Bibcode:2012ISPAn..I3..371H. doi:10.5194/isprsannals-I-3-371-2012.
• Kim, Junhwan; Kolmogorov, Vladimir; Zabih, Ramin (2003). "Visual correspondence using energy minimization and mutual information". Proceedings of the Ninth IEEE International Conference on Computer Vision. pp. 1033–1040.
• Spangenberg, Robert; Langner, Tobias; Rojas, Raúl (2013). "Weighted semi-global matching and center-symmetric census transform for robust driver assistance". International Conference on Computer Analysis of Images and Patterns. pp. 34–41.

• "Stereo vision". Archived from the original on 2019-01-01.