c++ - Lucas-Kanade 算法的计算复杂度是多少？

Question

在时间复杂度的大 O 表示法中，在 OpenCV（C++）中实现的 Lucas-Kanade 光流计算的复杂度是多少？你是怎么推断出来的？

谢谢！

Answer 1

假设扭曲参数n的数量为 ，其中的像素数量T为N。Lucas-Kanade 算法每次迭代的总计算成本为. 您可以从Lucas-Kanade 20 Years On: A Unifying Framework: Part 1 - 2.4中找到此类信息和讨论。

ps：我不知道 OpenCV 实现的计算复杂度。但是，为了合理起见，它应该与上述相同。

Answer 2

基于 OpenCV github 和Lucas-Kanade 20 Years On: A Unifying Framework: Part 1 - 2.4中的信息，我可以说：

(x, y)在使用带有 Lucas-Kanade 的光流的 2D 跟踪算法中，如 opencv 所述 n等于2和N是帧上的像素数量，(height*width)例如在我的研究（精子跟踪）中，我使用n=2（2D 跟踪）和T=788*388.

正如我在第 178 行看到的那样，这是针对每个功能完成的for( size_t ptidx = 0; ptidx < npoints; ptidx++)。

对于O(N*n^2 + n^3)一项功能和F功能也是如此O(F*N*n^2 + F*n^3)。