Horn–Schunck method. Explanation of iterative solution

Question

I am reading this paper (explanation of Horn-Shunck method for finding optical flow) and trying to understand it. My stumbling block is obtainig solution of system of linear equations

I(x, y, t) - brightness of the image at point (x, y) at time t, alpha - just regularization coefficient, u and v - optical flow to find

Horn and Schunck proposed this iterative solution based on Gauss–Seidel method (page number nine in paper). But my math skill is not enough to understand how to obtain this formula

Can anyone explain me this solution?

P.S. Sorry for my poor english

Answer 1

The system has the structure $$ (α^2I+bb^T)x = α^2\bar x-\gamma b, ~~ x=\pmatrix{u\\v}, ~~ b=\pmatrix{I_x\\I_y}, ~~ γ=I_t. $$ Projection along $b$ gives $$ (α^2+|b|^2)(b^Tx)=α^2(b^T\bar x)-γ|b|^2 $$ and inserted back $$ α^2x=α^2\bar x-γ b-(b^Tx)b =α^2\bar x-\frac{γ(α^2+|b|^2)+α^2(b^T\bar x)-γ |b|^2}{α^2+|b|^2}b \\~\\ \implies x=\bar x-\frac{γ+(b^T\bar x)}{α^2+|b|^2}b $$ which corresponds to the second cited system.

This is still a fixed-point equation, as $\bar x$ is some average over $x$. If this is applied as fixed-point iteration to all locations first, followed by the computation of new averages, then the method corresponds to the Jacobi iteration. If the averages are always updated after the computation of new values at each location, then this corresponds to the Gauß-Seidel iteration.

Answer 2

Take a look at this. It explains the Gauss Seidel method https://www.math.ust.hk/~mamu/courses/231/Slides/CH07_3B.pdf

Answer 3

So uh... I'll try in a quick way, Sorry I don't have the time right now, I made a program using this method and that's what I got from doing it. The last part is an interative algorithm, the next value depends on the last iteration value.

$h(u,v)^k =(u^(k+1),v^(k+1)) = $is the flow vector on an specific point $(x_o,y_o,t_o) $

$\bar{h}=(\bar{u}^k,\bar{v}^k) = $ is the local average flow vector, including all neighbors like this for example \begin{matrix}\\ \frac{1}{12} && \frac{1}{6} && \frac{1}{12} \\ \frac{1}{6} && 0 && \frac{1}{6} \\ \frac{1}{12} && \frac{1}{6} && \frac{1}{12} \\ \end{matrix}

and $I_x = \frac{\partial I}{\partial x} = $ is the value of the derivative in the $I_x(x_o,y_o,t_o)$
Hope this helps!!!

after that you need to understand how the condition for stopping the interative algorithm.

Greetings from Brasil!