Coarse-to-Fine Estimation

Coarse-to-fine estimation solves a correspondence problem first on heavily downsampled copies of the images, where motions are small, and then refines the answer at successively finer resolutions. It lets methods that are valid only for motions of about a pixel, such as the Lucas–Kanade and Horn–Schunck methods, recover displacements of tens of pixels. It is standard in classical optical flow estimation, stereo matching, and image registration, and survives in modified form in flow networks.

Purpose

Differential methods linearize brightness constancy around the current estimate, which holds only while the displacement is small compared with the scale of the image structure. On texture a few pixels wide, a single linear step fails beyond a pixel or two, and iterating with warping helps only while the starting point is near the correct solution. Matching methods face a related problem: a large search range is expensive and, in repetitive texture, ambiguous.

Halving the resolution halves every displacement measured in pixels and removes fine texture, so at a coarse enough level the motion is small and the energy landscape is smooth. Each coarse solution initializes the next level, where only a small correction is needed, which extends the range of motion and makes the non-convex minimization less likely to settle in a wrong local minimum.

When to Use It

Use it when motion exceeds the range of the underlying estimator (about a pixel for a linearized step, or the search range of a matching cost), when the motion field is smooth at coarse scales, as with camera motion and large objects, and when a small search at every level is cheaper than a large one at full resolution.

It helps little when motion is already small, as in high-frame-rate video, and fails when small objects move further than their own size (see Pitfalls). It is unnecessary when large displacements are handled another way, such as long-range matching or an all-pairs cost volume.

How It Works

Number the levels $\ell = 0, \dots, L - 1$, with $\ell = 0$ the original images and $\ell = L - 1$ the coarsest.

1. Build pyramids. For each frame, repeatedly smooth with a low-pass filter and subsample by 2 in each direction, as in Burt and Adelson’s Gaussian pyramid. Smoothing first prevents aliasing.
2. Initialize at the coarsest level. Set $\mathbf{w}^{L-1} = \mathbf{0}$, or use a prior such as the previous frame’s flow scaled down.
3. Estimate. At level $\ell$, warp the second image by the current estimate, $\tilde{I}_1^{\ell}(\mathbf{x}) = I_1^{\ell}\big(\mathbf{x} + \mathbf{w}^{\ell}(\mathbf{x})\big)$, and estimate a residual flow $\delta\mathbf{w}^{\ell}$ between $I_0^{\ell}$ and $\tilde{I}_1^{\ell}$. The residual is small, so the linearized constraint applies. Update $\mathbf{w}^{\ell} \leftarrow \mathbf{w}^{\ell} + \delta\mathbf{w}^{\ell}$, and repeat the warp-and-estimate step a few times.
4. Propagate to the next finer level. Upsample the flow field to the resolution of level $\ell - 1$ and multiply the vectors by 2, since one pixel at level $\ell$ spans two pixels at level $\ell - 1$:

$$\mathbf{w}^{\ell - 1}(\mathbf{x}) = 2\, \mathbf{w}^{\ell}\!\left(\tfrac{\mathbf{x}}{2}\right).$$

5. Repeat steps 3 and 4 until level 0, whose flow is the result.

If the estimator at each level recovers motions up to $d_{\max}$, a pyramid with $L$ levels recovers motions up to about $(2^{L} - 1)\, d_{\max}$ at full resolution: with four levels, roughly 15 times the single-level range. Bouguet states this gain in his description of the pyramidal Lucas–Kanade tracker, written at Intel.

Brox et al. (2004) gave the scheme a theoretical basis: minimizing a variational energy whose data term is not linearized, with nested fixed-point iterations, leads to an outer loop of warping steps, and embedding that loop in a coarse-to-fine strategy helps it avoid poor local minima.

How to Apply It

• Number of levels. Choose enough levels that the largest expected motion, divided by $2^{L-1}$, falls within the per-level range, but stop before the coarsest image loses its structure. Bouguet suggests a top level of 2 to 4 for typical images; for 640 × 480 images, level 4 is only 40 × 30 pixels.
• Downsampling factor. A factor of 2 is standard. Variational methods often downsample more gently, with more levels, so each correction is smaller, at higher cost.
• Smoothing. Blur before subsampling with a Gaussian or binomial kernel. Too little blur aliases fine texture; too much removes the structure the coarse level needs.
• Warping. Warp with bilinear or bicubic interpolation, and mask pixels that warp outside the image out of the data term.
• Upsampling the flow. Bilinear upsampling is the default but blurs motion boundaries; edge-aware or learned upsampling, such as RAFT’s, preserves them better.

Example

A dense Lucas–Kanade estimator that refines a flow field by warping, run once at full resolution and once on a four-level pyramid. Both use 20 warp-and-estimate iterations in total.

import numpy as np
from scipy import ndimage

rng = np.random.default_rng(0)
size = 256
# Periodic, smoothed random texture; its features are a few pixels wide.
texture = ndimage.gaussian_filter(rng.standard_normal((size, size)), sigma=2, mode="wrap")


def warp(image, flow):
    """Sample image at x + w(x): brings the second frame back onto the first."""
    y, x = np.mgrid[0:image.shape[0], 0:image.shape[1]].astype(float)
    coords = [y + flow[..., 1], x + flow[..., 0]]
    return ndimage.map_coordinates(image, coords, order=1, mode="nearest")


def refine(I0, I1, flow, iterations=5, window=4.0):
    """Dense Lucas-Kanade: repeatedly warp I1 and solve for a small flow increment."""
    for _ in range(iterations):
        I1w = warp(I1, flow)
        Iy, Ix = np.gradient((I0 + I1w) / 2)
        It = I1w - I0
        # Gaussian-weighted sums over a local window (the structure tensor).
        S = lambda a: ndimage.gaussian_filter(a, window)
        a, b, c = S(Ix * Ix), S(Ix * Iy), S(Iy * Iy)
        p, q = -S(Ix * It), -S(Iy * It)
        det = a * c - b * b + 1e-9
        flow = flow + np.stack([(c * p - b * q) / det, (a * q - b * p) / det], axis=-1)
    return flow


def pyramid(image, levels):
    """Gaussian pyramid: blur, then keep every second pixel."""
    out = [image]
    for _ in range(levels - 1):
        out.append(ndimage.gaussian_filter(out[-1], 1.0)[::2, ::2])
    return out  # out[0] is full resolution, out[-1] the coarsest level


def coarse_to_fine(I0, I1, levels):
    P0, P1 = pyramid(I0, levels), pyramid(I1, levels)
    flow = np.zeros(P0[-1].shape + (2,))
    for level in reversed(range(levels)):
        if flow.shape[:2] != P0[level].shape:
            # Upsample to the finer grid and double the vectors: 1 px here is 2 px there.
            h, w = P0[level].shape
            flow = 2.0 * np.stack(
                [ndimage.zoom(flow[..., k], (h / flow.shape[0], w / flow.shape[1]), order=1)
                 for k in range(2)], axis=-1)
        flow = refine(P0[level], P1[level], flow)
    return flow


def mean_epe(flow, true_flow, margin=32):
    err = np.linalg.norm(flow - true_flow, axis=-1)
    return err[margin:-margin, margin:-margin].mean()


for u, v in [(0.8, -0.5), (3.0, -2.0), (10.3, -6.2)]:
    # Second frame: texture moved by (u, v), so I1(x + w) = I0(x).
    I1 = ndimage.shift(texture, (v, u), order=3, mode="grid-wrap")
    true_flow = np.broadcast_to([u, v], (size, size, 2))
    single = refine(texture, I1, np.zeros((size, size, 2)), iterations=20)
    multi = coarse_to_fine(texture, I1, levels=4)
    print(f"true w = ({u:5.1f}, {v:5.1f})   single-scale EPE: {mean_epe(single, true_flow):6.3f}"
          f"   4-level pyramid EPE: {mean_epe(multi, true_flow):6.3f}")

# A small, fast object: the background moves 1 px, a square object moves 12 px.
patch = ndimage.gaussian_filter(rng.standard_normal((size, size)), sigma=2, mode="wrap")
for side in [8, 48]:
    I0 = texture.copy()
    I1 = ndimage.shift(texture, (0, 1), order=3, mode="grid-wrap")
    I0[100:100 + side, 100:100 + side] = patch[:side, :side]
    I1[100:100 + side, 112:112 + side] = patch[:side, :side]
    flow = coarse_to_fine(I0, I1, levels=4)
    inside = flow[102:98 + side, 102:98 + side]  # object interior in the first frame
    print(f"{side:2d} px object moving 12 px: mean estimated u = {inside[..., 0].mean():5.2f}"
          f"   EPE = {np.linalg.norm(inside - [12.0, 0.0], axis=-1).mean():5.2f}")

Output:

true w = (  0.8,  -0.5)   single-scale EPE:  0.046   4-level pyramid EPE:  0.027
true w = (  3.0,  -2.0)   single-scale EPE:  0.046   4-level pyramid EPE:  0.004
true w = ( 10.3,  -6.2)   single-scale EPE: 12.773   4-level pyramid EPE:  0.025
 8 px object moving 12 px: mean estimated u = -0.04   EPE = 12.39
48 px object moving 12 px: mean estimated u = 10.85   EPE =  1.62

At full resolution, iterating with warping copes with a 3-pixel shift on this texture, whose features are a few pixels wide, but not with a shift of about 12 pixels, which the pyramid recovers to a few hundredths of a pixel. The last two lines show the classic failure: an 8-pixel object moving 12 pixels shrinks to a single pixel at the coarsest level, its estimated motion stays near zero, and the finer levels cannot recover it. A 48-pixel object with the same motion is found, with the remaining error concentrated along its blurred boundaries.

Variants

• Hierarchical matching. Anandan (1989) matched image patches by sum of squared differences on a Laplacian pyramid, attached confidence measures derived from the shape of the matching surface, and propagated displacements from coarse to fine.
• Hierarchical parametric estimation. Bergen et al. (1992) estimated parametric models, such as affine and planar motion, as well as general flow, by coarse-to-fine refinement with warping, an approach widely used in direct image alignment.
• Pyramidal Lucas–Kanade. Bouguet’s tracker runs iterative Lucas–Kanade at each level of a pyramid with a fixed window size, passing the guess $2(\mathbf{g}^{\ell} + \mathbf{d}^{\ell})$ to the next finer level, where $\mathbf{g}^{\ell}$ is the guess received at level $\ell$ and $\mathbf{d}^{\ell}$ the residual estimated there. A small window, good for accuracy, can then track motions much larger than itself (feature tracking).
• Coarse-to-fine variational warping. Variational methods in the line of Brox et al. (2004) minimize the full energy at every level, initialized from the level below.
• Learned feature pyramids. PWC-Net (Sun et al., 2018) applies the scheme to learned features instead of pixels. At each level it warps the second frame’s features with the upsampled flow and builds a cost volume over a search range of only 4 pixels; its authors note that even 2 pixels per level covers motions of up to about 200 pixels at input resolution.
• Single-resolution refinement. RAFT (Teed and Deng, 2020) deliberately avoids the cascade. It keeps one flow field at one-eighth resolution and updates it iteratively, looking up a correlation volume pooled to several scales: the multi-scale idea survives in the correlations, but the estimate is never passed from coarse to fine.

Best Practices

• Multiply the flow vectors by the upsampling factor, not just resample the field.
• Use robust penalties in the data term so that occluded pixels at coarse levels do not corrupt the initialization.
• Filter the flow between levels, for example with a median filter, to remove isolated errors before they propagate.
• Initialize from the previous frame’s flow in video, which reduces the range the pyramid must cover.

Pitfalls

• Small, fast objects disappear. A structure smaller than about $2^{L-1}$ pixels is blurred away at the coarse levels where its motion would have to be found. Its pixels start from a wrong estimate, typically close to the motion of their surroundings, and the finer levels see too large a residual to correct. PWC-Net’s authors call these objects a conundrum for the coarse-to-fine approach, and the failure motivated adding descriptor matches to the variational energy (Brox and Malik, 2011).
• Errors propagate. Every finer level starts from the coarser estimate, so a mistake at a coarse level, near a motion boundary or in an occluded region, is inherited. Teed and Deng cite this, with missed small, fast objects, as a limitation of the cascade.
• Blurred boundaries. Coarse levels mix the motions of neighboring surfaces, and bilinear upsampling spreads the mix.
• Aliasing. Subsampling without enough smoothing turns fine, repetitive texture into false patterns.

Evidence and Impact

Anandan’s hierarchical matching and the model-based framework of Bergen et al. established coarse-to-fine processing in motion estimation by the early 1990s, and variational flow methods relied on it for the next two decades. PWC-Net’s authors describe the coarse-to-fine variational approach as the most popular framework for optical flow, and their network showed that pyramid, warping, and cost-volume design remains effective with learned features.

Its limitations are equally well documented. RAFT’s single-resolution design, which on release gave the best published results on Sintel and KITTI, showed that a pyramid of the estimate is not needed for large motions when long-range correlations are available. Outside optical flow, it remains common in stereo matching, medical image registration, and direct visual odometry.