Какова вычислительная сложность алгоритма Лукаса-Канаде?
В нотации big-O для усложнения времени, сколько будет сложность вычисления оптического потока Лукаса-Канаде, реализованного в OpenCV (C ++)? И как ты это сделал?
Спасибо!
Решение
Предположим, что число параметров деформации n и количество пикселей в T является N, Общая вычислительная стоимость каждой итерации алгоритма Лукаса-Канаде составляет 
. Вы можете найти такую информацию и обсуждение от Лукас-Канаде 20 лет спустя: объединяющая структура: часть 1 — 2,4.
PS: я понятия не имею о вычислительной сложности реализации OpenCV. Но, чтобы быть разумным, это должен быть таким же, как указано выше.
Другие решения
На основе OpenCV GitHub и информации в Лукас-Канаде 20 лет спустя: объединяющая структура: часть 1 — 2,4 Я могу сказать, что:
В алгоритме 2D отслеживания (x, y) используя оптический поток с Lucas-Kanade как заявлено 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),