0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Could you link the paper ? $\endgroup$ – Gilles Aug 19 '16 at 8:16
  • $\begingroup$ The link is: image.diku.dk/imagecanon/material/HornSchunckOptical_Flow.pdf. It is one of two classic papers on optical flow. $\endgroup$ – Jogging Song Aug 21 '16 at 3:54
  • $\begingroup$ More broadly, you may be interested in motion segmentation. Essentially, for your single-moving-object scenario a "smoothness prior" on the optical flow is relatively inappropriate. $\endgroup$ – GeoMatt22 Aug 22 '16 at 14:11
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Your reply is really valuable. I don't understand what some random noise texture means. Does it just mean noise? Do you mean noise can improve the result? I add some gaussian noise to the images. It seems it doesn't help. Maybe you means it should contain some textures in the images. So are textures very important for any practical applications? $\endgroup$ – Jogging Song Aug 21 '16 at 5:22
  • $\begingroup$ I remember that in the database for evaluating optical flow algorithms there is one sequence called Yosemite. The Yosemite sequence with cloudy sky usually cause larger error. Is the because the motion of the cloud is relatively complex? $\endgroup$ – Jogging Song Aug 21 '16 at 6:56
  • 1
    $\begingroup$ The problems on the sky come from the fact that it has a random motion. $\endgroup$ – sansuiso Aug 21 '16 at 7:58
  • $\begingroup$ What is the difference between random motion and random noise texture in your previous comment? From your website, I learn that you have published one paper Fast TV-L1 optical flow for interactivity. I have read the paper. It seems that the ceiling in the results are almost uniform. Is it possible to obtain accurate MVs for such regions? $\endgroup$ – Jogging Song Aug 22 '16 at 2:26
  • 1
    $\begingroup$ As far as I can remember, the comment from the Yosemite sequence creator was that the clouds were added afterwards in order to "give something visual" to be processed in that area by global algorithms (such as Horn-Schunk, which would be Tikhonov-L2, or your TV-L1). However the ground truth isn't known on this part, and their motion may be completely inconsistent with the motion in the sequence. $\endgroup$ – sansuiso Aug 22 '16 at 11:58
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thanks. I have read the two papers before. Actually the algorithm I used to produce dense optical flow is based on TV-L1 objective function. From sansuiso's answer, I realize that I can't obtain ground truth result because we can't get accurate motion vectors for pixels with small gradients and the motion vectors are produced by regularization term in the objective functions. Maybe the error in MVs is tolerant for practical applications. Currently I am planning to use dense optical flow for denoising images due to local motion between images. Does dense optical flow have other applications? $\endgroup$ – Jogging Song Aug 21 '16 at 5:41
  • 1
    $\begingroup$ Other applications: image alignment, video compression, video stabilization. I have not myself done any optical flow, but I have done TV denoising, essentially your equation with $u=0$. In that case, for $L_2$ regularization I get "diffusion", but for $L_1$ I get a piecewise constant approximation. So for me, the $L_1$ prevented the edge blurring seen in the $L_2$ approach. Results could depend on the regularization strength ($lambda$) and/or optimization method (I used iteratively reweighted least squares). $\endgroup$ – GeoMatt22 Aug 21 '16 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.