Scanline matching cost, interactive stereo demo

Search along the scanline

Stereo correspondence is a search problem: for a pixel in the left image, find the pixel in the right image that shows the same scene point. In a rectified pair, it lies on the same row, at $x_R = x_L - d$ with a disparity $d \ge 0$ . So for each pixel, compare it with every pixel on the same row up to a largest disparity and pick the best.

Comparing single intensities does not work: many pixels on the row have almost the same value, and noise decides which one wins. Instead, compare windows around the pixels, with the same costs as for motion estimation:

E_\text{SSD}(d) = \sum_{i} \left[ I_L(x_i, y_i) - I_R(x_i - d, y_i) \right]^2

E_\text{NCC}(d) = \frac{\sum_i [I_L(x_i, y_i) - \bar I_L][I_R(x_i - d, y_i) - \bar I_R]}{\sqrt{\sum_i [I_L(x_i, y_i) - \bar I_L]^2}\, \sqrt{\sum_i [I_R(x_i - d, y_i) - \bar I_R]^2}}

SSD is minimized, NCC is maximized. NCC subtracts the mean and divides by the contrast of both windows, so it also works when the two cameras see the scene with a different exposure. Here, the SSD is averaged over the window so that window sizes can be compared.

When the minimum is unclear

Textureless regions: all windows on the flat panel look alike, the cost is flat, and noise picks the winner.
Repetitive patterns: the stripes repeat every 6 px along the row, so the cost has a minimum every 6 px of disparity.
Occlusions: background just left of a near object is hidden in the right image, and no candidate is correct.

Window size

A small window gives detail: it can follow small objects and stays close to depth edges, but it contains little structure, so noise and ambiguity make it fail more often. A large window averages noise away and resolves more ambiguities, but it blurs depth edges, because near a boundary it contains parts at two different depths. Adapting the window size to the image content gives better results than any fixed size.

Hierarchical correspondence

A full search costs one window comparison per candidate disparity, for every pixel. On an image pyramid, every level halves the disparities: the full range is searched only on the coarsest, small level, and each finer level only checks a few disparities around twice the estimate from the level above. This is faster and handles large disparity ranges, such as outdoor scenes with near and far objects, as long as the coarse level does not pick the wrong minimum.

Try this

With the default pixel on the textured box, both curves have one clear minimum at $d^* = 16$ . In the intensity plot, the two rows overlap where the box is.
Click in the middle of the flat panel at the bottom right: the cost is almost flat, and the minimum jumps when you change the noise.
Click on the stripes at the bottom left: the small window shows minima 6 px apart. Make the large window wider than the stripes block, so it includes the edges: one minimum now stands out.
Click on the background just left of the box, around (20, 50): it is occluded, and no disparity fits well.
Click near the edge of the disk: the large window, which also covers background, finds a disparity between the two, or the background one.
Set the brightness of the right image to 1.4: SSD gets worse everywhere, NCC hardly changes.
Pick a pixel on the disk ( $d^* = 24$ ) and use 1, 2 and 3 pyramid levels: with 3 levels, 14 comparisons replace 29. On the stripes, the coarse level blurs the stripes away and has to rely on the edges of the block.