2
$\begingroup$

I'm working on a real-time implementation of Lucas-Kanade for optical flow. However, the SVD decomposition to do achieve the least square method to reduce the error seems to take too much time.

A brief explanation of the algorithm can be accessed here Lucas Kanade algorithm

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ One might try using conjugate gradients in the case computing matrix factorizations like the SVD for one's problem is too computationally involving. This being said the computational complexity for each of these methods is in general $O(N^3)$. $\endgroup$
    – Josiah Park
    Commented Oct 29, 2018 at 11:55
  • $\begingroup$ I would recommend to try qr-factorization e.g. by using Gram-Schmidt orthogonalization. $\endgroup$
    – user35593
    Commented Oct 29, 2018 at 21:29
  • 1
    $\begingroup$ @user35593 Why GS instead of Householder? $\endgroup$
    – Federico Poloni
    Commented Nov 28, 2018 at 23:52

2 Answers 2

Reset to default
1
$\begingroup$

Aren't the matrices in Lucas-Kanade tall and skinny? A Nx2 solve regardless of method should be fast; maybe you're computing a full SVD when you should be doing a reduced one instead?

Improve this answer
$\endgroup$
0
1
$\begingroup$

In practice, the fastest direct method is normal equations $A^TAx=A^Tb$ + exploiting symmetry to compute $A^TA$ + Cholesky to solve the resulting linear system. It scales like $mn^2 + o(mn^2)$ for an $m\times n$ matrix $A$ with $m\gg n$, when most other algorithms cost $2mn^2$, and it is faster even in the case $m\approx n$. However, it may be dramatically unstable, especially if the value of that minimum norm is small.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .