Disparity map

Matching every pixel on its own gives a disparity map full of errors wherever a window is ambiguous. Scanline stereo matches a whole row at once: it looks for the cheapest consistent assignment of left to right pixels, with a penalty for every pixel left unmatched. Compare both with the true disparities, and look at one row's path through all possible matches.

Left image click to select a row
True disparity d∗d^* bright = near, black = d=0d = 0 hidden in the right image
Window matching best disparity per pixel
Scanline stereo best path per row unmatched (occluded)
All matches of row : cost C(x,d)C(x, d), dark = similar windows left pixel xx to the right, disparity dd upwards best path true disparities

Window matching

The simplest disparity map takes, for every pixel, the disparity with the lowest window cost along its row, as in the scanline matching cost demo. Every pixel decides alone. Where the window is ambiguous, on the flat panel, the stripes or next to depth edges, neighboring pixels pick unrelated disparities, and the map becomes noisy. A larger window helps there but rounds off the corners of objects and widens them at depth edges.

Scanline stereo as a shortest path

Instead of matching pixels one by one, match a whole row coherently. Put the pixels of the left row along one axis and those of the right row along the other. A path from the first to the last pixel of both rows describes one assignment for the whole row, and every step is one of three moves:

A change of disparity needs occlusion steps, since the path must leave one diagonal and join another, so κ\kappa also acts as a penalty for depth jumps. The path keeps the order of the pixels: what is left of something in one image is left of it in the other. Dynamic programming finds the cheapest path in time proportional to the number of pixels times the number of disparities. Above, the path is drawn over the costs with xx and dd as axes: a match moves to the right, an occlusion up or down.

Stereo as energy minimization

The path minimizes an energy with two parts, which describe a good stereo correspondence:

E=∑matchesC(x,d)⏟match quality+κ⋅#occlusions⏟smoothnessE = \underbrace{\sum_\text{matches} C(x, d)}_\text{match quality} + \underbrace{\kappa \cdot \#\text{occlusions}}_\text{smoothness}
  1. Match quality: each pixel should find a good match in the other image.
  2. Smoothness: neighboring pixels should usually have about the same disparity.

Every row is optimized on its own, so nothing ties a row to the rows above and below. Where the data is weak, as on the flat panel, neighboring rows choose different paths and the map shows horizontal streaks. Dynamic programming cannot optimize a full 2D grid of pixels; coherent 2D solutions need other energy minimization methods, such as graph cuts or belief propagation.

Try this