Patch-based vs regularized flow

One equation, two unknowns

Optical flow looks for a vector $\mathbf{u}_i$ at every pixel such that $I_1(\mathbf{x}_i + \mathbf{u}_i) \approx I_0(\mathbf{x}_i)$. Summing the squared differences over all pixels gives

Each $\mathbf{u}_i$ has two components, so $n$ pixels have $2n$ unknowns, but only $n$ equations. Minimizing this alone is hopeless: almost any pixel of $I_1$ with the same brightness is a perfect match. Two ways out are compared here.

Patch-based flow

Assume that all pixels in a small window move by the same $\mathbf{u}$, and estimate it with Lucas–Kanade: linearize, solve $A^\top A\, \Delta\mathbf{u} = A^\top \mathbf{b}$ and repeat. The window around each pixel gives that pixel's vector. Whether this works depends on $A^\top A = \sum_i \nabla I_1 \nabla I_1^\top$, the same matrix as in the Harris detector:

• Textured window, two large eigenvalues: a clear optimum, the motion is found.
• Edge or stripes, one large eigenvalue: the error surface is a valley. Moving along the edge does not change the window, so only the component along the gradient, the normal flow, can be measured. This is the aperture problem, and the barber pole illusion is the same effect in human vision.
• Flat window, no large eigenvalue: no optimum at all, and no estimate.
• Repetitive pattern: the error surface has many equal minima, one per period, and the iteration ends in the nearest one, which need not be the right one.
• Motion boundaries: a window across the silhouette of an object mixes two motions, and parts of the background disappear behind the object (occlusion) or appear (disocclusion), so they have no match.

Here, eigen-directions with $\lambda < \tau$ are left out of the solution: an edge window gives the normal flow, and a flat window gives no vector.

Regularized flow

Instead of fixing the motion per window, add a term that penalizes differences between neighboring vectors:

$\|\nabla \mathbf{u}_i\|^2$ is the sum of the squared differences of $\mathbf{u}_i$ to its right and lower neighbors. Now the problem is well posed: where the image has texture, the data term decides; where it has none, the smoothness term fills in the motion from the surroundings. Along an edge, the data term fixes the normal component and the neighbors supply the other one.

The data term is linearized as in Lucas–Kanade, around the current flow $\mathbf{u}^0_i$: $I_1(\mathbf{x}_i + \mathbf{u}_i) - I_0(\mathbf{x}_i) \approx I_x u_i + I_y v_i + c_i$, with the gradient $(I_x, I_y)$ of $I_1$ at $\mathbf{x}_i + \mathbf{u}^0_i$ and $c_i = I_1(\mathbf{x}_i + \mathbf{u}^0_i) - I_0(\mathbf{x}_i) - I_x u^0_i - I_y v^0_i$. Setting the derivatives with respect to $u_i$ and $v_i$ to zero, with the mean $\bar{\mathbf{u}}_i$ of the $n$ neighbors held fixed, gives

Each vector is the average of its neighbors, corrected along the gradient by how badly that average fits the brightness. Repeating this for all pixels spreads information across the image one pixel per sweep, so filling a large flat region takes many iterations. Every 20 sweeps, the image is linearized again at the current flow.

The weight $\alpha$ sets the balance. A small $\alpha$ follows the data and keeps its noise and ambiguities; a large $\alpha$ gives smooth flow, but also smears the sharp change of motion at an object's silhouette into the background. The true flow, with its sharp boundaries, usually has a higher energy than the smooth result: the quadratic smoothness term prefers to blur boundaries.

Try this

• Compare the two flow images with the true flow. The patch-based flow is right on the textured card and the background, has no estimate in the middle of the flat card, the wrong color on the stripes and on the repetitive pattern.
• Click the center of each card and look at the error surface: a single dip on the texture, a valley on the stripes, a flat plateau on the flat card, and a grid of dips on the repetitive pattern.
• On the stripes, the patch-based vector is the normal flow: its direction is perpendicular to the stripes, not the direction in which the card moves.
• Set the iterations of the regularized flow to 0 and press Play: the flow first appears on the textured parts and then grows into the flat disk and across the stripes.
• Vary $\alpha$ from 0.003 to 1: at small values the flat disk is not filled in and the repetitive pattern keeps the wrong motion; at large values the cards blur into the background and the error near the boundaries grows.
• Change the window radius $r$: small windows leave more of the flat disk without an estimate and are noisier; large windows reach across motion boundaries and smear them.
• Move the cards by less than half a period of the repetitive pattern, e.g. (1, 0.6): now the patch-based flow finds the right minimum there too.
• Set the motion of the background equal to that of the cards: without motion boundaries, the regularized flow is right almost everywhere.
• Raise the noise and lower $\tau$: flat windows now give vectors, but they are noise.