Cost Volume

A cost volume stores, for every pixel of a reference image, how well it matches each of a set of candidate correspondences in another image. It is the shared core of classical stereo matching, multi-view stereo, and many deep networks for stereo and optical flow estimation.

Definition

A cost volume is a tensor of matching costs, or of similarities, between the pixels of one image and candidate corresponding pixels in another, indexed by pixel position and by a hypothesis: a disparity in rectified stereo, a 2D displacement in optical flow, or a depth in multi-view stereo. Scharstein and Szeliski call the stereo version a disparity space image, a function over $(x, y, d)$ that usually holds the cost of the match implied by each disparity.

Intuition

In a rectified stereo pair, the match of a left-image pixel lies on the same row of the right image, between zero and some maximum disparity to its left. Writing its dissimilarity to every candidate on that row into a list, for every pixel, stacks the lists into a box with two image axes and one disparity axis. A slice at fixed disparity is dark (low cost) wherever surfaces lie at that disparity.

For a textured pixel the list has one sharp minimum. In a blank wall it is flat, along a repeated pattern it has several equal minima, and at an occluded pixel the true match does not exist at all. The volume makes these ambiguities explicit, so later stages can resolve them using the neighbors’ costs.

Formal Definition

Stereo volumes

For a rectified pair with left (reference) image $I_L$ and right image $I_R$, a left pixel $(x, y)$ with disparity $d$ corresponds to the right pixel $(x - d, y)$. With $D$ candidate disparities, the cost volume is

$$C(x, y, d) = \rho\big(I_L, I_R; \, x, y, d\big), \qquad d \in \{0, \dots, D-1\}, \qquad C \in \mathbb{R}^{H \times W \times D},$$

where $\rho$ is a matching cost computed from a window $\mathcal{N}$ of offsets $(i, j)$ around the pixel. The sum of absolute and the sum of squared differences are

$$C_\text{SAD}(x, y, d) = \sum_{(i, j) \in \mathcal{N}} \big| I_L(x + i, y + j) - I_R(x + i - d, y + j) \big|,$$ $$C_\text{SSD}(x, y, d) = \sum_{(i, j) \in \mathcal{N}} \big( I_L(x + i, y + j) - I_R(x + i - d, y + j) \big)^2.$$

With a single-pixel window they reduce to pixel-wise absolute or squared differences, which a separate aggregation step then sums. Zero-mean normalized cross-correlation removes the window means $\mu_L, \mu_R$ and divides by the standard deviations $\sigma_L, \sigma_R$:

$$\text{NCC}(x, y, d) = \frac{1}{|\mathcal{N}|} \sum_{(i, j) \in \mathcal{N}} \frac{\big(I_L(x + i, y + j) - \mu_L\big)\big(I_R(x + i - d, y + j) - \mu_R\big)}{\sigma_L \, \sigma_R}.$$

NCC is a similarity in $[-1, 1]$, so it is used as a cost in the form $1 - \text{NCC}$. The census transform replaces each pixel $\mathbf{p}$ by a bit string $\xi(\mathbf{p})$ with one bit per neighbor $\mathbf{q}$, set when $I(\mathbf{q}) < I(\mathbf{p})$; the cost is the Hamming distance between bit strings,

$$C_\text{census}(x, y, d) = \operatorname{Hamming}\big(\xi_L(x, y), \, \xi_R(x - d, y)\big).$$

These costs and their robustness to brightness changes are discussed under brightness constancy.

Learned volumes compare feature maps $\mathbf{f}_L, \mathbf{f}_R \in \mathbb{R}^{H \times W \times F}$ produced by a shared network. A correlation volume stores the dot product, a similarity that is higher for better matches:

$$S(x, y, d) = \frac{1}{F} \big\langle \mathbf{f}_L(x, y), \, \mathbf{f}_R(x - d, y) \big\rangle .$$

A concatenation volume keeps both feature vectors and leaves the comparison to later layers:

$$V(x, y, d) = \big[ \, \mathbf{f}_L(x, y) \, ; \, \mathbf{f}_R(x - d, y) \, \big] \in \mathbb{R}^{2F}, \qquad V \in \mathbb{R}^{H \times W \times D \times 2F}.$$

Optical flow volumes

In optical flow the match can move in any direction, so the hypothesis is a 2D displacement $(u, v)$. A local volume searches a square window of radius $R$:

$$C(x, y, u, v) = \rho\big(I_1, I_2; \, x, y, u, v\big), \qquad |u|, |v| \le R, \qquad C \in \mathbb{R}^{H \times W \times (2R+1) \times (2R+1)}.$$

An all-pairs volume compares every pixel of $I_1$ with every pixel of $I_2$, giving $C \in \mathbb{R}^{H \times W \times H \times W}$; its construction and multi-scale pooling in RAFT are described in the RAFT article.

Reading out a correspondence

The simplest readout is winner-take-all: each pixel takes the hypothesis with the lowest cost,

$$d^*(x, y) = \arg\min_{d} \, C(x, y, d).$$

A differentiable alternative, the soft argmin of Kendall et al., turns negated costs into a probability distribution over disparities and returns its expectation:

$$\hat d(x, y) = \sum_{d=0}^{D-1} d \cdot \sigma_d\big(-C(x, y, \cdot)\big), \qquad \sigma_d(\mathbf{z}) = \frac{e^{z_d}}{\sum_{d'} e^{z_{d'}}},$$

which yields sub-pixel estimates and lets a network be trained end to end through the volume.

Properties

• Memory and computation scale with the number of hypotheses. A stereo volume has $HWD$ entries, a local flow volume $HW(2R+1)^2$, and an all-pairs volume $(HW)^2$. For a $1242 \times 375$ stereo pair with 192 disparities, a full-resolution scalar volume already holds about 89 million values, about 360 MB in 32-bit floats. A concatenation volume at quarter resolution with 48 disparity levels and 64 channels holds a similar number. This is why deep methods build volumes on downsampled feature maps.
• Search range against resolution. Larger motions need a larger range, which grows the volume and adds more chances for a wrong minimum. Downsampling extends the range cheaply but loses fine structure. Coarse-to-fine schemes and RAFT’s pooled correlation pyramid are two answers to this trade-off.
• Raw costs are ambiguous. Pixel-wise costs have many near-equal minima in weak texture and repetitive regions. Aggregating costs over a neighborhood, separately for each hypothesis, suppresses noise, but large windows blur depth discontinuities, the edge-fattening effect seen in the example below.
• Winner-take-all is local and discrete. It ignores neighboring decisions and returns integer hypotheses unless followed by sub-pixel refinement, for example by fitting a parabola to the costs around the minimum.
• Uniform disparity is not uniform depth. For focal length $f$ and baseline $B$, depth is $Z = fB/d$, so evenly spaced disparities sample depth finely near the camera and coarsely far away.
• Occlusions have no correct entry. A pixel visible in only one image has no true match. A left-right consistency check, which compares the disparities computed with each image as reference, is the usual way to flag such pixels.

Examples

Classical stereo

Scharstein and Szeliski observed that dense stereo algorithms perform subsets of four steps: matching cost computation, cost aggregation, disparity computation or optimization, and disparity refinement. In this taxonomy the cost volume is the data structure the first three steps operate on. Local methods aggregate costs over a window and pick the winner; global methods add a smoothness term and minimize an energy over the whole disparity map with dynamic programming, graph cuts, or similar optimizers.

Semi-global matching (SGM), introduced by Hirschmüller, sits between the two. It approximates a global energy, with a small penalty $P_1$ for disparity changes of one and a larger penalty $P_2$ for larger jumps, by one-dimensional dynamic programming along paths from several directions, usually eight or sixteen. For each direction $\mathbf{r}$ it computes

$$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 \pm 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),$$

sums the path costs into an aggregated volume $S(\mathbf{p}, d) = \sum_\mathbf{r} L_\mathbf{r}(\mathbf{p}, d)$, and takes the winner at each pixel. The original method used mutual information as its matching cost. Its running time is linear in the number of pixels and disparities, and it has been widely applied, from aerial mapping to driver assistance.

Deep stereo

Žbontar and LeCun’s MC-CNN learned only the first step of the classical pipeline: a convolutional network trained to tell matching from non-matching patches supplies the matching cost, followed by cross-based cost aggregation, SGM, a left-right check, and refinement. Its fast variant is a Siamese network whose features are computed once per pixel and compared by cosine similarity, so filling the whole volume needs only one forward pass per image plus dot products.

GC-Net (Kendall et al., 2017) made the whole pipeline learnable. It builds a concatenation volume of size height × width × disparities × features, regularizes it with 3D convolutions over the height, width, and disparity dimensions, and regresses disparity with the soft argmin. The authors found that concatenated features worked better than subtracted features or a distance metric, reasoning that the network can then learn absolute feature representations rather than only relative ones. PSMNet (Chang and Chen, 2018) kept the concatenation volume and added spatial pyramid pooling to the features and a stacked hourglass 3D network for regularization.

Deep optical flow

FlowNetC (Dosovitskiy et al., 2015) introduced a correlation layer that compares two feature maps by dot products. To keep the 4D result tractable, it limits the maximum displacement, strides over positions and displacements, and arranges displacements as channels: FlowNetC searches up to 20 feature-map pixels in each direction, sampling every second displacement, which gives $21 \times 21 = 441$ channels. PWC-Net (Sun et al., 2018) builds a partial cost volume at each level of a feature pyramid after warping the second image’s features by the upsampled flow, with a small search range per level, as described under coarse-to-fine estimation. RAFT returns to the full all-pairs volume at one-eighth resolution, about 50 million entries for a $1024 \times 436$ Sintel frame (padded to $1024 \times 440$), and pools it into a pyramid sampled around the current estimate.

Multi-view stereo

Plane-sweep stereo generalizes the disparity axis to depth: for each depth hypothesis, the source images are warped onto a plane at that depth in front of the reference camera and compared with the reference image. MVSNet (Yao et al., 2018) does this with learned features and differentiable homography warping, building the volume on the reference camera’s frustum. To accept any number of views, it combines the warped feature volumes by their variance, regularizes the result with 3D convolutions, and regresses a depth map.

Practical Example

The code builds a synthetic rectified pair (a textured background at disparity 5, a foreground rectangle at disparity 14), fills an $H \times W \times D$ volume with pixel-wise absolute differences, aggregates it with square windows, and reads out disparities by winner-take-all. Accuracy is measured over pixels visible in both images and within 4 pixels of the foreground’s left and right edges.

import numpy as np
from scipy import ndimage

rng = np.random.default_rng(0)
H, W, D = 120, 160, 24            # image size and number of candidate disparities
d_bg, d_fg = 5, 14                # true disparities of background and foreground
top, bot, a, b = 30, 90, 60, 110  # foreground rectangle in left-image coordinates

# Random textures for the two layers, wide enough to sample at x + d.
bg = ndimage.gaussian_filter(rng.random((H, W + D)), 1.0)
fg = ndimage.gaussian_filter(rng.random((H, W + D)), 1.0)
x = np.arange(W)

# Left image and its ground-truth disparity: left pixel (x, y) matches right pixel (x - d, y).
left = bg[:, x].copy()
left[top:bot, a:b] = fg[top:bot, a:b]
gt = np.full((H, W), d_bg)
gt[top:bot, a:b] = d_fg

# Right image: background shifted by d_bg, foreground drawn over it shifted by d_fg.
right = bg[:, x + d_bg].copy()
right[top:bot, a - d_fg:b - d_fg] = fg[top:bot, a:b]

noise = 0.01
left = left + noise * rng.standard_normal(left.shape)
right = right + noise * rng.standard_normal(right.shape)

# Cost volume C[y, x, d] = |I_L(x, y) - I_R(x - d, y)|, infinite where x - d leaves the image.
C = np.full((H, W, D), np.inf)
for d in range(D):
    C[:, d:, d] = np.abs(left[:, d:] - right[:, :W - d])
print("cost volume shape:", C.shape, f"({C.nbytes / 1e6:.1f} MB as float64)")

# Valid pixels: away from the borders, and visible in the right image.
occluded = np.zeros((H, W), bool)
occluded[top:bot] = ((x - d_bg) >= a - d_fg) & ((x - d_bg) < b - d_fg) & (gt[top:bot] == d_bg)
valid = ~occluded
valid[:, :D + 6] = False
valid[:6], valid[-6:], valid[:, -6:] = False, False, False
edge = ndimage.binary_dilation(gt != np.roll(gt, 1, axis=1), iterations=4) & valid

for win in [1, 5, 11, 21]:
    # Aggregation: sum the costs over a win x win window, separately for every disparity.
    agg = ndimage.uniform_filter(np.where(np.isinf(C), 1e3, C), size=(win, win, 1), mode="nearest")
    disp = agg.argmin(axis=2)  # winner-take-all
    err = np.abs(disp - gt)
    print(f"window {win:2d}x{win:<2d}: exact {np.mean(err[valid] == 0):6.1%}, "
          f"near edges {np.mean(err[edge] == 0):6.1%}, mean error {err[valid].mean():.2f} px")

# The cost profile of one foreground pixel after 5x5 aggregation.
agg5 = ndimage.uniform_filter(np.where(np.isinf(C), 1e3, C), size=(5, 5, 1), mode="nearest")
profile = agg5[60, 85]
print("pixel (85, 60): best d =", profile.argmin(),
      "| cost at d = 13, 14, 15:", np.round(profile[13:16], 3),
      "| median cost:", round(float(np.median(profile)), 3))

Output:

cost volume shape: (120, 160, 24) (3.7 MB as float64)
window  1x1 : exact  31.4%, near edges  32.2%, mean error 4.71 px
window  5x5 : exact  98.7%, near edges  92.3%, mean error 0.10 px
window 11x11: exact  98.9%, near edges  94.2%, mean error 0.10 px
window 21x21: exact  98.5%, near edges  88.4%, mean error 0.13 px
pixel (85, 60): best d = 14 | cost at d = 13, 14, 15: [0.046 0.012 0.039] | median cost: 0.088

Winner-take-all on pixel-wise costs recovers the exact disparity at only 31% of pixels, because with noise a single intensity matches many candidates almost equally well. Aggregating over a $5 \times 5$ window raises this to about 99%, and the profile of the foreground pixel shows the sharp minimum that aggregation produces: its cost at the true disparity is less than a third of its neighbors’ and about a seventh of the median. The largest window still does well inside surfaces but loses accuracy near the foreground’s edges, where its windows straddle both surfaces and mix costs from two disparities.

Common Misconceptions

• “A cost volume is a correlation volume.” Correlation is one way to fill it. Volumes may hold costs, where lower is better, or similarities, where higher is better, and concatenation volumes hold feature vectors rather than scalar scores.
• “The minimum of the raw cost profile is the answer.” Only where the profile has one sharp minimum; otherwise aggregation, SGM, or 3D convolutions must resolve it, and a larger search range adds more false minima.
• “Deep networks replaced the cost volume.” Many influential stereo, flow, and multi-view stereo networks, from MC-CNN and FlowNetC to MVSNet and RAFT, are built around one; they learned the matching cost and the regularization rather than removing the volume.

Where It Is Used

• Stereo matching and depth estimation, in classical pipelines and learned networks.
• Optical flow, from FlowNetC to RAFT and its successors, as surveyed in optical flow estimation.
• Multi-view stereo, in classical and learned plane-sweep methods.
• Dense matching, where detector-free methods compare all pairs of coarse feature positions between two images before refining the matches, as described under feature matching.
• Block matching in video coding, which evaluates a sum of absolute differences over candidate displacements for each block.