Semi-Global Matching (SGM)

Semi-global matching (SGM) computes a dense disparity map from a rectified stereo pair by approximately minimizing a global energy: a matching cost per pixel plus penalties for disparity changes between neighbors. It runs one-dimensional dynamic programming along straight paths from several directions into every pixel and sums the results. Hirschmüller introduced it in 2005 and described it in full in a 2008 journal paper. Its accuracy at object borders, linear running time, and regular structure made it widely used, from aerial mapping to driver assistance; OpenCV ships a variant as StereoSGBM. Stereo matching places it among other stereo methods.

Problem

Pixel-wise matching costs are ambiguous: with noise or weak texture, a wrong disparity often costs less than the right one. Window aggregation assumes constant disparity inside the window and blurs object borders. Global methods add a smoothness term and minimize over the whole image, but minimizing even the simple Potts energy is NP-hard (Boykov, Veksler, and Zabih, 2001), and most top-ranked global methods of the time took from 20 seconds to over a minute per image pair. Dynamic programming minimizes such an energy exactly along one scanline in polynomial time, but rows optimized independently produce horizontal streaks. SGM keeps the pixel-wise cost and the global energy and replaces the 2D minimization with many cheap 1D ones.

Inputs and Outputs

• Input: two images with known epipolar geometry, a disparity range, and the penalties $P_1$ and $P_2$. Hirschmüller’s formulation only needs a function that traces the epipolar line of each pixel, so it also works on pushbroom images that cannot be rectified; most implementations assume rectified images.
• Output: a sub-pixel disparity map for the base image, with pixels that fail a left–right check marked invalid.

Intuition

Along one image row, dynamic programming finds the cheapest path through the cost volume when a path pays the matching cost at every pixel, a small fee for a one-step disparity change, and a larger fee for a jump. SGM computes such path costs along rows, columns, and diagonals ending at every pixel, giving each pixel a smoothed opinion about every disparity from each direction. Summing the directions spreads evidence from textured areas into ambiguous ones from all sides, without favoring one direction as scanline methods do. Only the path costs are kept, not the paths.

Algorithm

1. Matching cost. Compute a pixel-wise cost $C(\mathbf{p}, d)$ for every base-image pixel and disparity, filling an $H \times W \times D$ volume.
2. Path aggregation. For each direction $\mathbf{r}$ (8 or 16 of them), start at the image border and traverse the image, computing the path cost $L_\mathbf{r}(\mathbf{p}, d)$ from the previous pixel’s costs with the recurrence below.
3. Summation. Add the path costs of all directions into $S(\mathbf{p}, d)$.
4. Disparity selection. At each pixel take the disparity with the lowest $S$ (winner-take-all) and refine it to sub-pixel precision with a parabola through the costs at $d - 1$, $d$, and $d + 1$.
5. Second map. Compute the match image’s disparity map, either from the same $S$ along the epipolar line or, slightly better, by repeating steps 1–4 with the images swapped.
6. Consistency check. Filter both maps with a $3 \times 3$ median and invalidate base-image pixels whose disparity differs by more than one from the disparity of their match.

Optional post-processing in the 2008 paper removes small isolated disparity segments and interpolates invalidated pixels.

Mathematical Formulation

Following the 2008 paper, the base image is $I_b$, the match image $I_m$, and $D$ the disparity image, with $D_\mathbf{p}$ the disparity at pixel $\mathbf{p}$. The energy is

$$E(D) = \sum_\mathbf{p} \Big( C(\mathbf{p}, D_\mathbf{p}) + \sum_{\mathbf{q} \in N_\mathbf{p}} P_1 \, \mathrm{T}\big[|D_\mathbf{p} - D_\mathbf{q}| = 1\big] + \sum_{\mathbf{q} \in N_\mathbf{p}} P_2 \, \mathrm{T}\big[|D_\mathbf{p} - D_\mathbf{q}| > 1\big] \Big),$$

where $N_\mathbf{p}$ is the neighborhood of $\mathbf{p}$ and $\mathrm{T}[\cdot]$ is 1 when its argument is true and 0 otherwise. The small penalty $P_1$ lets disparity change by one between neighbors, which accommodates slanted and curved surfaces. The constant penalty $P_2$ charges every larger jump the same, however large, so true discontinuities stay affordable.

Along a path in direction $\mathbf{r}$, the cost of reaching pixel $\mathbf{p}$ at disparity $d$ is

$$L_\mathbf{r}(\mathbf{p}, d) = C(\mathbf{p}, d) + \min\Big( L_\mathbf{r}(\mathbf{p} - \mathbf{r}, d), \; L_\mathbf{r}(\mathbf{p} - \mathbf{r}, d - 1) + P_1, \; L_\mathbf{r}(\mathbf{p} - \mathbf{r}, d + 1) + P_1, \; \min_i L_\mathbf{r}(\mathbf{p} - \mathbf{r}, i) + P_2 \Big) - \min_k L_\mathbf{r}(\mathbf{p} - \mathbf{r}, k).$$

Without the last term, this is the energy $E(D)$ minimized along one path. The subtracted minimum is the same for every $d$, so it does not change which disparity wins; it only bounds the values by $C_\text{max} + P_2$. The aggregated cost is

$$S(\mathbf{p}, d) = \sum_\mathbf{r} L_\mathbf{r}(\mathbf{p}, d), \qquad D_\mathbf{p} = \arg\min_d S(\mathbf{p}, d).$$

The recurrence does not enforce the ordering or visibility constraints of classical scanline dynamic programming, which paths off the epipolar line cannot express; Hirschmüller likens it to the scanline optimization of Scharstein and Szeliski (2002). Occlusions are instead detected by the left–right check: with $\mathbf{q}$ the match of $\mathbf{p}$ under $D_{b\mathbf{p}}$, the disparity is kept if $|D_{b\mathbf{p}} - D_{m\mathbf{q}}| \le 1$ and set invalid otherwise.

Matching costs

SGM works with any pixel-wise cost. The 2008 paper uses either the sampling-insensitive absolute difference of Birchfield and Tomasi or a cost based on mutual information (MI), which models the joint distribution of corresponding intensities and so tolerates complex radiometric differences. MI needs a disparity map to estimate that distribution, so it is computed hierarchically (HMI), starting from a random map at 1/16 resolution; Hirschmüller estimated the theoretical overhead at about 14%. The census transform of Zabih and Woodfill (1994), compared by Hamming distance, became a common alternative: in Hirschmüller and Scharstein’s (2009) evaluation of matching costs under radiometric changes, census had the best and most robust overall performance.

Parameters

• $P_1$ and $P_2$, with $P_2 \ge P_1$. A larger $P_2$ removes more noise but smooths across real discontinuities. Both are in the units of the matching cost, and one setting rarely suits every scene.
• Adaptive $P_2$. Because depth edges usually coincide with intensity edges, the paper sets $P_2 = P_2' / |I_{b\mathbf{p}} - I_{b\mathbf{q}}|$ for neighboring base-image pixels, still keeping $P_2 \ge P_1$, so jumps are cheaper where the image has an edge.
• Number of paths. The paper requires at least 8 and recommends 16 for good coverage of the image; the extra directions are realized by alternating one horizontal or vertical step with one diagonal step.
• Disparity range $D$, which sets memory and run time.

Complexity

Each pixel is visited once per path at $O(D)$ cost, since the previous pixel’s minimum is computed once and reused for every $d$, so the time is $O(WHD)$. Memory is also $O(WHD)$: the paper stores $C$ and $S$ as 16-bit $W \times H \times D$ arrays, scaling costs to 11 bits so that the sum over 16 paths, at most $16(C_\text{max} + P_2)$, cannot overflow. Hirschmüller reported 1.8 seconds for the Middlebury Teddy pair on a 2.2 GHz Opteron, with the aggregation in SSE2 instructions, and processed images too large for memory in overlapping tiles.

The recurrence uses only additions, comparisons, and minimums in a regular pattern, which suits parallel hardware. Ernst and Hirschmüller (2008) implemented SGM with mutual information on a GPU. Gehrig, Eberli, and Meyer (2009) implemented an 8-path variant with a zero-mean SAD cost on an FPGA for driver assistance and reported 25 Hz on a $680 \times 400$ region of $750 \times 480$ images, with up to 128 disparities and less than 3 W of power.

Implementation

The example builds a noisy random-dot stereogram, a background at disparity 3 and a raised square at disparity 10 carrying a $12 \times 12$ textureless patch, and compares winner-take-all on single-pixel absolute differences with winner-take-all after aggregation along 2, 4, and 8 directions. A pixel is bad when its disparity is off by more than one; occluded pixels and the left border are excluded.

import numpy as np

rng = np.random.default_rng(0)
H, W, D = 64, 96, 16
d_bg, d_sq = 3, 10                  # disparities of background and raised square
top, bot, a, b = 16, 48, 36, 76     # square in left-image coordinates

# Random-dot stereogram: left pixel (x, y) shows the same point as right pixel (x - d, y).
bg = rng.random((H, W + D))
sq = rng.random((H, W + D))
sq[26:38, 50:62] = 0.5              # a textureless patch on the square
x = np.arange(W)
left = bg[:, x].copy()
left[top:bot, a:b] = sq[top:bot, a:b]
right = bg[:, x + d_bg].copy()
right[top:bot, a - d_sq:b - d_sq] = sq[top:bot, a:b]
gt = np.full((H, W), d_bg)
gt[top:bot, a:b] = d_sq
left += 0.1 * rng.standard_normal(left.shape)
right += 0.1 * rng.standard_normal(right.shape)

# Pixel-wise matching cost C(p, d) = |I_L(x, y) - I_R(x - d, y)|.
C = np.full((H, W, D), 1.0)
for d in range(D):
    C[:, d:, d] = np.abs(left[:, d:] - right[:, :W - d])

def path_cost(C, dx, dy, P1, P2):
    """L_r for direction r = (dx, dy), Eq. (13) of Hirschmüller (2008)."""
    L = np.zeros_like(C)
    def step(Lprev, Cp):
        m = Lprev.min(axis=-1, keepdims=True)
        up = np.pad(Lprev, [(0, 0), (1, 1)], constant_values=np.inf)
        best = np.minimum.reduce([Lprev, up[:, :-2] + P1, up[:, 2:] + P1,
                                  np.broadcast_to(m + P2, Lprev.shape)])
        return Cp + best - m
    if dy == 0:                     # horizontal path: sweep columns
        xs = range(W) if dx > 0 else range(W - 1, -1, -1)
        prev = None
        for xi in xs:
            L[:, xi] = C[:, xi] if prev is None else step(L[:, prev], C[:, xi])
            prev = xi
    else:                           # vertical or diagonal path: sweep rows
        ys = range(H) if dy > 0 else range(H - 1, -1, -1)
        prev = None
        for yi in ys:
            if prev is None:
                L[yi] = C[yi]
            else:
                src = np.clip(x - dx, 0, W - 1)    # predecessor column p - r
                Lp = L[prev][src]
                Lp[(x - dx < 0) | (x - dx >= W)] = 0  # path starts at the border
                L[yi] = step(Lp, C[yi])
            prev = yi
    return L

def sgm(C, dirs, P1=0.1, P2=0.6):
    return sum(path_cost(C, dx, dy, P1, P2) for dx, dy in dirs)

dirs8 = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1)]
occ = np.zeros((H, W), bool)        # background hidden behind the square in the right image
occ[top:bot] = (x - d_bg >= a - d_sq) & (x - d_bg < b - d_sq) & (gt[top:bot] == d_bg)
valid = ~occ
valid[:, :D] = False                # no full disparity range near the left border
flat = np.zeros((H, W), bool)
flat[26:38, 50:62] = True

for name, S in [("WTA on raw costs", C),
                ("SGM, 2 paths (L-R)", sgm(C, dirs8[:2])),
                ("SGM, 4 paths", sgm(C, dirs8[:4])),
                ("SGM, 8 paths", sgm(C, dirs8))]:
    disp = S.argmin(axis=2)         # winner-take-all on the (aggregated) costs
    bad = np.abs(disp - gt) > 1
    print(f"{name:20s} bad pixels: all {bad[valid].mean():6.1%}, "
          f"textureless patch {bad[flat].mean():6.1%}")

Output:

WTA on raw costs     bad pixels: all  69.6%, textureless patch  70.1%
SGM, 2 paths (L-R)   bad pixels: all   5.5%, textureless patch  25.0%
SGM, 4 paths         bad pixels: all   2.0%, textureless patch  16.7%
SGM, 8 paths         bad pixels: all   1.8%, textureless patch   4.9%

With single-pixel costs and this much noise, winner-take-all gets most pixels wrong. The two horizontal paths alone, which amount to scanline optimization, cut the error to 5.5%, but the textureless patch is reached only from its left and right edges and a quarter of it stays wrong. Vertical and diagonal paths bring in evidence from more sides: with 8 paths, 1.8% of all pixels and 4.9% of the patch are bad. The example omits sub-pixel refinement and the left–right check; the stereo matching example demonstrates the latter.

OpenCV’s StereoSGBM

OpenCV’s cv::StereoSGBM (4.x) is a documented modification of Hirschmüller’s algorithm. It matches blocks rather than single pixels (blockSize = 1 restores pixels), uses the Birchfield–Tomasi cost on a clipped horizontal derivative of the image, plus a down-weighted intensity term, instead of mutual information, and adds a uniqueness test, quadratic sub-pixel interpolation, speckle filtering, and a left–right check (disp12MaxDiff). The default MODE_SGBM makes a single pass over the image and aggregates 5 directions; MODE_HH runs the full two-pass algorithm with 8 directions at the cost of $O(W H D)$ memory. P1 and P2 are given in the units of the block cost, and OpenCV’s sample uses $8$ and $32$ times the number of channels times blockSize². Output disparities are fixed-point values scaled by 16, as described under disparity.

Properties and Behavior

• Sharp borders. Because the cost is pixel-wise and the smoothness term is the only coupling between pixels, SGM avoids the blurring of object borders and fine structures that window aggregation causes.
• Sub-pixel accuracy. In the Middlebury comparison of October 2006, Hirschmüller reported SGM and its variant C-SGM among the best methods at a 1-pixel error threshold and the best at 0.5 pixels, which he attributed to their sub-pixel accuracy.
• Not a true minimizer. The result is not the minimum of $E(D)$ and depends on the set of directions.

Limitations

• Streaking. Summing independent 1D optimizations leaves characteristic low-amplitude streaks along the path directions (Facciolo, de Franchis, and Meinhardt, 2015).
• Large textureless regions. When an untextured background surrounds a foreground object or touches the image border, paths entering from different surfaces disagree and the discontinuity becomes fuzzy; Hirschmüller added an intensity-consistent post-processing step for this case.
• Slanted surfaces. It follows from the energy that SGM favors fronto-parallel surfaces: a slanted surface, such as the road ahead of a car, becomes a staircase of integer disparities that pays $P_1$ at every step, so penalties high enough to suppress noise also flatten it.

Variants

• More global matching (MGM). Facciolo, de Franchis, and Meinhardt (2015), building on an interpretation of SGM as min-sum belief propagation, let each path step also draw on the neighboring pixel of the previous scanline, so each directional cost depends on a quadrant of the image rather than a line. They reported a five-fold reduction of SGM’s energy gap to reference optimizers and the removal of its streaks, with little computational overhead.
• Learned penalties. SGM-Nets (Seki and Pollefeys, 2017) predict the penalties from an image patch and its position with a convolutional network, separately for positive and negative disparity changes.
• Learned aggregation. GA-Net (Zhang et al., 2019) includes a semi-global aggregation layer, described as a differentiable approximation of SGM, inside an end-to-end network as a cheaper alternative to stacks of 3D convolutions.
• Learned costs. MC-CNN (Žbontar and LeCun, 2016) replaces the hand-crafted matching cost with a learned patch comparison and keeps SGM in its post-processing.
• Multiple views. The 2008 paper matches the base image against each further image separately and fuses the disparity maps.