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

$\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$ Oct 29, 2018 at 11:55
  • $\begingroup$ I would recommend to try qr-factorization e.g. by using Gram-Schmidt orthogonalization. $\endgroup$
    – user35593
    Oct 29, 2018 at 21:29
  • 1
    $\begingroup$ @user35593 Why GS instead of Householder? $\endgroup$ Nov 28, 2018 at 23:52

2 Answers 2

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?

$\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.

$\endgroup$

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.