Coarse-to-fine alignment

Lucas–Kanade only sees a few pixels far: when a window moves farther than the size of its structures, the linearization points the wrong way. Shrinking both images shrinks the motion too. Estimate it on a small, blurred copy first, refine the estimate level by level up to full resolution, and compare with Lucas–Kanade on the full images alone.

Frame I0I_0 click to select the window
Frame I1I_1 estimates u0,u1,…\mathbf{u}_0, \mathbf{u}_1, \dots true u∗\mathbf{u}^* (×) level 0 only
Pyramid of I0I_0 and error surfaces E(l)(u)E^{(l)}(\mathbf{u}) of the window, ±16\pm 16 px window estimates true u∗\mathbf{u}^* (×) black = smallest error, all surfaces over the same displacements of level 0
Window at gray = zero error outside I1I_1
I0(l)(xi)I_0^{(l)}(\mathbf{x}_i)
I1(l)(xi+u(l))I_1^{(l)}(\mathbf{x}_i + \mathbf{u}^{(l)})
error eie_i
Distance to the truth ∣uk−u∗∣|\mathbf{u}_k - \mathbf{u}^*| coarse to fine level 0 only in pixels

Why large motions are hard

Lucas–Kanade estimates the motion u\mathbf{u} of a window by minimizing E(u)=∑i[I1(xi+u)−I0(xi)]2E(\mathbf{u}) = \sum_i [I_1(\mathbf{x}_i + \mathbf{u}) - I_0(\mathbf{x}_i)]^2, replacing the image with its tangent plane at the current estimate. The tangent only describes the image over about the size of its structures. If the window moved farther than that, the gradient does not know where it went, and the steps run into the nearest local minimum of EE. The error surface of level 0 shows this: the dark dip at the true shift is surrounded by others.

A full search would find a large motion, but its cost grows with the square of the search range, and it is limited to the grid. Both problems are solved by looking at the images at a coarser scale first.

The image pyramid

Each level of the pyramid is the previous one, low-pass filtered and subsampled by a factor of 2:

I(l)(x)=I~(l−1)(2x),I~=Gσ∗II^{(l)}(\mathbf{x}) = \tilde I^{(l-1)}(2\mathbf{x}), \qquad \tilde I = G_\sigma * I

The filter removes the frequencies that the smaller image cannot hold. Without it, fine patterns alias into structures that are not in the scene. Every level has a quarter of the pixels of the one below, so the whole pyramid is only a third larger than the image.

A displacement of u\mathbf{u} pixels at full resolution is only u(l)=u/2l\mathbf{u}^{(l)} = \mathbf{u} / 2^l pixels at level ll. The window keeps its size in pixels, so at level ll it covers 2l2^l times as much of the scene, and its structures are coarse. Measured in pixels of the full image, the basin of convergence grows by a factor of 2 per level, as the error surfaces show.

Coarse to fine

The estimation starts at the coarsest level LL with u=0\mathbf{u} = 0, or with a short full search, which is cheap since the image is small. Its result is passed down to the next finer level, where coordinates are twice as large, as the initial guess:

u0(l−1)=2 u^(l)\mathbf{u}^{(l-1)}_0 = 2\, \hat{\mathbf{u}}^{(l)}

At every level, a few Lucas–Kanade steps only have to correct the small error of the coarser estimate, which lies well within the basin of convergence, and they add the detail the coarser level could not see. At level 0, the estimate reaches subpixel accuracy. Within each level, both images are smoothed slightly, as in the Lucas–Kanade demo, so that full steps do not overshoot at sharp edges.

Limits

Try this