Stereo Processing by Semiglobal Matching and Mutual Information

Semi-global matching (SGM) was introduced by Heiko Hirschmüller of the German Aerospace Center (DLR), Institute of Robotics and Mechatronics, in “Accurate and Efficient Stereo Processing by Semi-Global Matching and Mutual Information” at the 2005 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). The full description, “Stereo Processing by Semiglobal Matching and Mutual Information”, appeared in IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI) in February 2008; it describes the method of the 2005 paper together with a 2006 extension, so this article treats them as one publication. The paper matches single pixels with a mutual-information cost and approximates a two-dimensional smoothness energy by summing one-dimensional optimizations along paths from many directions, in time linear in the number of pixels and disparities. The semi-global matching article covers the method as used today.

Problem

The journal paper frames dense stereo through the four-step taxonomy of Scharstein and Szeliski (2002). It names object borders, fine structures, occlusions, weak or repetitive texture, and radiometric differences as the hard cases, and adds that applications often need speed, for real time or for large or numerous images.

The methods of the time traded these goals against each other. Local methods aggregate costs over a window at constant disparity and pick the cheapest disparity, which is fast but blurs object borders and fine structures, a problem that shaped windows reduce but cannot remove. Global methods minimize a data term plus a smoothness term over the whole image. Hirschmüller notes that almost all top-ranked methods on the Middlebury test images (Tsukuba, Venus, Teddy, and Cones) were global, and that most took from more than 20 seconds to more than a minute per pair. Scanline dynamic programming was efficient but produced streaks, because rows were optimized independently. Common costs, such as absolute differences, were sensitive to radiometric changes. Mutual information (MI) handles complex radiometric relations, but the per-pixel form of Kim, Kolmogorov, and Zabih (2003) was computed iteratively within graph cuts, which would slow down a non-iterative method.

Hirschmüller’s own setting added two requirements: aerial pushbroom images have curved epipolar lines and cannot be rectified in general, and a single such image can exceed a billion pixels.

Contribution

The 2005 abstract names two main contributions: a hierarchical calculation of MI-based matching that is almost as fast as intensity-based matching, and an approximation of a global cost that runs in time linear in the number of pixels and disparities. It also covers occlusion detection, sub-pixel disparities, and an extension to multi-baseline stereo, with a runtime of about one second on typical images.

• Pixel-wise cost. The paper drops the assumption of constant disparity inside a window and matches individual pixels, so borders are not blurred by aggregation. The MI cost follows Kim et al.’s per-pixel form, computed hierarchically (HMI) so that each resolution level supplies the disparity map the next level needs to estimate the joint histogram.
• Semi-global aggregation. The smoothness energy, with a small penalty $P_1$ for disparity changes of one and a larger $P_2$ for bigger jumps, is optimized along one-dimensional paths and the path costs are summed at each pixel, which the paper calls “the new idea of aggregating matching costs in 1D from all directions equally”.
• Consistency checking and sub-pixel refinement. Disparities are computed for both images and compared to detect occlusions and mismatches, then refined by fitting a parabola to neighboring costs.
• No rectification requirement. Matching only needs a function that traces each pixel’s epipolar line, so unrectified pushbroom images are handled directly.

Method

Beyond the core of cost, aggregation, and a checked winner-take-all, the 2008 paper adds optional steps:

• Multi-baseline matching: the base image is matched against each further image separately, and the disparity maps are fused by a weighted mean of the values near the per-pixel median.
• Disparity refinement: removal of small isolated disparity segments, intensity-consistent disparity selection for foreground objects in front of untextured background, and interpolation of invalid pixels that treats occlusions and mismatches differently.
• Huge images: overlapping tiles sized to fit main memory, plus external tiles that can be processed on different computers, with the disparity range narrowed from the coarser hierarchical level.
• Fusion of disparity images by orthographic projection onto a common plane when the camera centers lie roughly in a plane, as in aerial imaging, taking the median per cell.

What changed between 2005 and 2008

The journal paper names three parts as previously unpublished: the tiling extension for almost arbitrarily large images, the orthographic fusion of disparity images, and an extensive evaluation of the MI-based cost. Intensity-consistent disparity selection and the discontinuity-preserving interpolation were the two extensions of a separate CVPR 2006 paper on consistent SGM; the journal paper calls the configuration with the former C-SGM and reports results for both SGM and C-SGM. The Middlebury evaluation was also redone: the journal paper uses views 2 and 6 of the multi-view sets, following the protocol of the newer Middlebury evaluation and differing from the 2005 paper.

Results

Middlebury. The journal paper reproduces the upper part of the Middlebury table from October 2006. At the standard 1-pixel error threshold, SGM and C-SGM were among the best performing algorithms, with C-SGM better because it recovers untextured background. At 0.5 pixels both were the top-performing methods, which Hirschmüller attributes to better sub-pixel accuracy. With the aggregation coded in SSE2 instructions, the Teddy pair took 1.8 seconds for SGM and 2.7 seconds for C-SGM on a 2.2 GHz Opteron, much faster than most methods in the comparison.

Radiometric robustness. Under global scaling, gamma changes, and different scaling of the two image halves applied to the right images, Birchfield–Tomasi matching broke down quickly while MI and HMI stayed nearly constant; a vignetting-like fall-off hurt MI and HMI more but still much less. On Scharstein’s Art images, HMI was nearly unaffected by different exposures and less affected than Birchfield–Tomasi by different lighting. On Teddy, HMI took 1.8 seconds against 1.5 for Birchfield–Tomasi and 4 for iterative MI, so Hirschmüller recommended HMI for all stereo matching.

Aerial reconstruction. Two examples show the method at scale:

• UltraCam frame images of Graz, provided by Vexcel Imaging: 45 images of 86 megapixels at 8 cm per pixel, disparity ranges up to 2,000 pixels, each image matched against six neighbors in about 5.5 hours on one CPU, with 22 CPUs running in parallel, followed by orthographic fusion into a digital surface model.
• Airborne HRSC pushbroom images of Ettal. The High Resolution Stereo Camera was built by DLR’s Institute of Planetary Research for mapping Mars on ESA’s Mars Express; the paper uses its airborne version, at 15–20 cm per pixel. A cluster of 40 CPUs processed 400 km² at 20 cm per pixel in three to four days, and more than 20,000 km² in one year.

Both aerial results are shown as renderings, without comparison to ground truth.

Impact

SGM’s practical appeal was accuracy at borders at near-local runtime, with a regular structure and robustness to radiometric change. In a 2011 retrospective, Hirschmüller reports that it had been re-implemented by many researchers and companies, describes DLR’s cluster processing of aerial and satellite images, and reports that in a comparison on HRSC images of Mars from Mars Express, SGM performed as well as methods specially tuned for that data.

Its regular arithmetic made hardware implementations practical. Ernst and Hirschmüller (2008) ran SGM with MI on a GPU. Gehrig, Eberli, and Meyer (2009) at Daimler, citing the 2005 paper, chose SGM as the most efficient of the top-performing Middlebury methods and put it on an FPGA for driver assistance, at 25 Hz with less than 3 W; the 2011 retrospective reports this implementation in use at Daimler. OpenCV’s StereoSGBM is, by its source comment, a variation of the 2008 paper that matches blocks rather than pixels. MC-CNN (Žbontar and LeCun, 2016) kept SGM in its post-processing behind a learned matching cost.

Limitations

• Untextured background. The paper notes that summing paths that see different surfaces makes discontinuities fuzzy around foreground objects in front of untextured walls; C-SGM’s post-processing is a targeted repair for indoor scenes, not a change to the energy.
• Memory. Cost and aggregation arrays of size $W \times H \times D$ can exceed main memory even for 1-megapixel images with disparity ranges of several hundred pixels, which is why tiling was needed.
• Limits of mutual information. MI models one radiometric mapping per image. Hirschmüller and Scharstein’s (2009) evaluation found census the most robust cost overall, and the 2011 retrospective summarizes it as showing that MI degrades with local radiometric changes such as vignetting and shadows, and adds that MI’s joint histogram becomes too sparse for 12- or 16-bit images.
• Evaluation. The quantitative comparison rests on four small indoor Middlebury pairs, a limitation Hirschmüller himself raised in 2011.

What Came After

Later implementations often kept the aggregation but not the MI cost. Gehrig, Eberli, and Meyer (2009) replaced it with a small-window zero-mean SAD cost, citing MI’s sensitivity to vignetting, and the 2011 retrospective describes DLR’s GPU implementation as supporting both MI and census and its FPGA implementations as using census. Later research addressed the approximation itself, its streaking and its bias toward fronto-parallel surfaces, and learned its penalties or embedded it in networks; these variants are covered in the semi-global matching article. The stereo matching article places SGM among local, global, and learned approaches.