Horn–Schunck method

The Horn–Schunck method of estimating optical flow is a global method which introduces a global constraint of smoothness to solve the aperture problem (see Lucas Kanade method for further description).

A global energy function is sought to be minimized, this function is given as:

$f=\int ((\nabla I\cdot {\vec {V}}+I_{t})^{2}+\alpha (|\nabla V_{x}|^{2}+|\nabla V_{y}|^{2}+|\nabla V_{z}|^{2})){{\rm {d}}x{\rm {d}}y{\rm {d}}z}$

where $\nabla I={\begin{bmatrix}I_{x}\\I_{y}\\I_{z}\end{bmatrix}}$ are the derivatives of the image intensity values along the x,y, and z dimensions, $I_{t}$ is the derivative in the t (time-) direction, ${\vec {V}}$ is the optical flow vector with the components $V_{x},V_{y},V_{z}$. The parameter $\alpha$ is a regularization constant. Larger values of $\alpha$ lead to a smoother flow. This function can be solved by calculating the Euler–Lagrange equations corresponding to the solution of the above equation. These are given as follows:

$I_{x}(I_{x}V_{x}+I_{y}V_{y}+I_{z}V_{z}+I_{t})-\alpha \Delta V_{x}=0$

$I_{y}(I_{x}V_{x}+I_{y}V_{y}+I_{z}V_{z}+I_{t})-\alpha \Delta V_{y}=0$

$I_{z}(I_{x}V_{x}+I_{y}V_{y}+I_{z}V_{z}+I_{t})-\alpha \Delta V_{z}=0$

where $\Delta$ denotes the Laplace operator so that $\Delta ={\frac {\partial ^{2}}{\partial x^{2}}}+{\frac {\partial ^{2}}{\partial y^{2}}}+{\frac {\partial ^{2}}{\partial z^{2}}}$.

Solving these equations with Gauss–Seidel for the flow components $V_{x},V_{y},V_{z}$ gives an iterative scheme:

$V_{x}^{k+1}={\frac {\Delta V_{x}^{k}-{\frac {1}{\alpha }}I_{x}(I_{y}V_{y}^{k}+I_{z}V_{z}^{k}+I_{t})}{{\frac {1}{\alpha }}I_{x}^{2}}}$

$V_{y}^{k+1}={\frac {\Delta V_{y}^{k}-{\frac {1}{\alpha }}I_{y}(I_{x}V_{x}^{k}+I_{z}V_{z}^{k}+I_{t})}{{\frac {1}{\alpha }}I_{y}^{2}}}$

$V_{z}^{k+1}={\frac {\Delta V_{z}^{k}-{\frac {1}{\alpha }}I_{z}(I_{x}V_{x}^{k}+I_{y}V_{y}^{k}+I_{t})}{{\frac {1}{\alpha }}I_{z}^{2}}}$

where the superscript k+1 denotes the next iteration, which is to be calculated and k is the last calculated result.

One simple way to obtain $\Delta V_{i}$ is:

$\Delta V_{i}(p)={\frac {1}{4}}\sum _{N(p)}V_{i}(N(p))-V_{i}(p)$

where N(p) are the four direct neighbors of the pixel p.

An alternative algorithmic implementation based upon the Jacobi method is given as:

$V_{x}^{k+1}={\overline {V_{x}^{k}}}-{\frac {I_{x}(I_{x}{\overline {V_{x}^{k}}}+I_{y}{\overline {V_{y}^{k}}}+I_{z}{\overline {V_{z}^{k}}}+I_{t})}{\alpha ^{2}+I_{x}^{2}+I_{y}^{2}+I_{z}^{2}}}$

$V_{y}^{k+1}={\overline {V_{y}^{k}}}-{\frac {I_{y}(I_{x}{\overline {V_{x}^{k}}}+I_{y}{\overline {V_{y}^{k}}}+I_{z}{\overline {V_{z}^{k}}}+I_{t})}{\alpha ^{2}+I_{x}^{2}+I_{y}^{2}+I_{z}^{2}}}$

$V_{z}^{k+1}={\overline {V_{z}^{k}}}-{\frac {I_{z}(I_{x}{\overline {V_{x}^{k}}}+I_{y}{\overline {V_{y}^{k}}}+I_{z}{\overline {V_{z}^{k}}}+I_{t})}{\alpha ^{2}+I_{x}^{2}+I_{y}^{2}+I_{z}^{2}}}$

where ${\overline {V_{i}^{k}}}$ refers to the average of $V_{i}^{k}$ in the neighborhood of the current pixel position.

Advantages of the Horn–Schunck algorithm include that it yields a high density of flow vectors, i.e. the flow information missing in inner parts of homogeneous objects is filled in from the motion boundaries. On the negative side, it is more sensitive to noise than local methods.

References

• Horn, B.K.P. and Schunck, B.G., "Determining optical flow." Artificial Intelligence, vol 17, pp 185-203, 1981.