Horn–Schunck method

From Wikipedia, the free encyclopedia

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, It is the derivative in the t (time-) direction, \vec{V} is the optical flow vector with the components Vx,Vy,Vz. The parameter α is a regularization constant. Larger values of α 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:

\Delta V_x - \frac{1}{\alpha} I_x(I_xV_x+I_yV_y+I_zV_z+I_t) = 0
\Delta V_y - \frac{1}{\alpha} I_y(I_xV_x+I_yV_y+I_zV_z+I_t) = 0
\Delta V_z - \frac{1}{\alpha} I_z(I_xV_x+I_yV_y+I_zV_z+I_t) = 0

where Δ denotes the Laplace operator so that \Delta V_x = \frac{\partial}{\partial x}\frac{\partial V_x}{\partial x},\; \Delta V_y = \frac{\partial}{\partial y}\frac{\partial V_y}{\partial y},\; \Delta V_z = \frac{\partial}{\partial z}\frac{\partial V_z}{\partial z}.

Solving these equations with Gauss–Seidel for the flow components Vx,Vy,Vz gives an iterative scheme:

V_x^{k+1}=\frac{\Delta V_x^k - \frac{1}{\alpha}I_x(I_yV_y^k+I_zV_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_xV_x^k+I_zV_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_xV_x^k+I_yV_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. ΔVi can be obtained as:

ΔVi = ∑ Vi(N(p)) − Vi(p)
N(p)

where N(p) are the six 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.

[edit] References