Accuracy of dense optical flow

Question

Currently I am learning dense optical flow by myself. To understand it, I conduct one experiment. I produce one image using Matlab. One box with a given grays value is placed under one uniform background and the box is translated two pixels in x and y directions in another image. The two images are input into the implementation of the algorithm called TV-L1. The generated motion vector outer of the box is not zero.

• Is the reason that the gradient outer of the box is zero?
• Is the values filled in from the values with large gradient value?

In Horn and Schunck's paper, it reads

In parts of the image where the brightness gradient is zero, the velocity estimates will simply be averages of the neighboring velocity estimates. There is no local information to constrain the apparent velocity of motion of the brightness pattern in these areas.

and

The progress of this filling-in phenomena is similar to the propagation effects in the solution of the heat equation for a uniform flat plate, where the time rate of change of temperature is proportional to the Laplacian.

Is it not possible to obtain correct motion vectors for pixels with small gradients? Or the experiment is not practical. In practical applications, this doesn't happen.

Answer 1

It's normal and due to your test setup.

Let's try to understand a bit. The algorithm is trying to minimize an objective function defined as:

$$ F(u, I_0, I) = \int \| I - I_0(u(x)) \|_1 + \lambda \| \nabla u \|_ dx, $$

where $I_0$ and $I$ are the images, $x$ is an image point (ie a pixel) and $I_0(u)$ a shortcut for "$I_0$ as remapped using the optical flow $u$". The first term is the data term (because it binds the result $u$ to the observed images) and the second is the regularization constraint on the shape of $u$ (the total variation TV in this case).

Let's ignore the regularization term for now. The registration in the data term can be obviously minimized by an optical flow field $u$ which is null everywhere, except for the pixels that belong to the edges of your box. For these pixels, the best solution is a translation that moves them to the nearest box edge in the new image.

So far, so good? Well, not anymore if we consider now the regularization term. The TV constraint will penalize solutions where neighbouring pixels have different optical flow values. This means that our current solution is going to have a high score (bad!) because the optical flow will vary around the box edge pixels. A much better solution with respect to TV is to get a constannt flow field ($\nabla u$ becomes null, and the regularization term evaluates to 0).

Joining both constraints (registration and regularization), we see that we need a solution flow field that:

1. brings the box edge pixels to the new box position
2. is as-constant-as-possible everywhere.

A solution fulfilling both constraints is a constant flow corresponding to the box translation: inside and outside of the box the values are constant so any flow vector works, and for box edges this is the best optical flow vector. In that case, the objective function does even evaluate to 0 (no registration error, TV is 0 too).

How to avoid this behaviour?

You can avoid this behaviour by using some random noise texture to fill your background and box. In that case, the registration constraint will force the flow to be near 0 on the background (the actual solution will depend on the $\lambda$ parameter). And obviously, this won't happen in "real life" applications because of sensor noise, small scene movements, textures...

In practice, you should generate 2 images filled with random noise, for example Gaussian noise, and preferably using different statistics (mean and variance):

• the first image will have the size of your test image. Let's call it the background. It is the texture of the immovable part of your test image;
• the second image should have the size of your box. Let's call it the object. It is the texture of your moving target.

Note that both images shouldn't be modified after creation: the textures are random, but they are not dynamic. If they are dynamic then there would be additional reasons (other than object motion) for their appearance to change.

You can create your test images by pasting the object layer on top of the background at the desired position. if you test only with integer displacements, you don't even have to take care of interpolation of any kind.

Answer 2

Building on the answer by sansuiso, the non-zero flow outside the box is due to the regularization (gradient) term, which causes smearing. This is a known weakness of the classic Horn & Schunck approach.

A common remedy is to make the $\lambda$ parameter spatially variable, and allow it to go to zero at edges between (piecewise-constant) motion regions. This can be done automatically by using a robust error metric on the gradient term. For example using an $L_1$ norm instead of an $L_2$ norm will give a median-filter smoothing instead of a moving-average.

For some examples see Wedel et al. (2009) and Sun et al. (2010).