Как ускорить вычисление оптического потока алгоритмом Лукаса-Канаде?

#cpp #opencv #opencv_faq

В OpenCV имеется реализация алгоритма Лукаса-Канаде с использованием пирамид изображений.
Работает относительно быстро и, в целом, скоростью своей обязана тому, что вычисляет
оптический поток не между всеми пикселями предыдущего и следующего кадров, а исключительно
в отношении точек интереса. Но если последних оказывается слишком много, то скорость
может быть и снижена, причём довольно существенно.

Имеется ли возможность увеличить производительность, не ограничивая количество точек
интереса?
    

Ответы

Ответ 1

Для вычисления оптического потока алгоритмом Лукаса-Канаде с использованием пирамиды
изображений используется функция:

void calcOpticalFlowPyrLK(
    InputArray prevImg,
    InputArray nextImg,
    InputArray prevPts,
    InputOutputArray nextPts,
    OutputArray status,
    OutputArray err,
    Size winSize = Size(21,21),
    int maxLevel = 3,
    TermCriteriacriteria = TermCriteria(TermCriteria::COUNT + TermCriteria::EPS,
30, 0.01),
    int flags = 0,
    double minEigThreshold = 1e-4)


Но интерес при решении задачи ускорения представляют лишь два её первых аргумента,
в качестве которых традиционно подаются матрицы исходных изображений. Проблема заключается
в том, что при каждом вызове calcOpticalFlowPyrLK(), последняя "молча" выполнит построение
пирамид изображений для каждого из кадров: предыдущего и следующего.

Получается, что на каждой межкадровой итерации вызова алгоритма, когда т.н. следующий
кадр уже будет отмечен как предыдущий, а его место в качестве следующего займёт новый
кадр, случится очевидный перерасход ресурсов. Оно и понятно, для вновь предыдущего
кадра пирамида изображений уже вычислялась, была использована, но не была сохранена.
В итоге, для каждой последующей межкадровой итерации производится повторное построение
пирамиды изображений для одного из кадров в кадровой последовательности.

Непосредственно построением пирамиды изображений для последующего её использования
в вычислении оптического потока занимается функция buildOpticalFlowPyramid(). Именно
её прозрачно и вызывает calcOpticalFlowPyrLK() для каждого из кадров. Тем не менее,
результат работы buildOpticalFlowPyramid(), как это недвусмысленно указано в справке,
может быть задействован в calcOpticalFlowPyrLK() как поданый на вход извне вместо обычных
изображений.

Рассмотрим два примера использования calcOpticalFlowPyrLK().

Традиционный:

cv::Mat prv_mat, nxt_mat;

while(true) {
    if(prv_mat.empty()) {
        prv_mat = readNewFrame();
        if(prv_mat.empty()) break;

        continue;
    }

    nxt_mat = readNewFrame();
    if(nxt_mat.empty()) break;

    // Вычисляем оптический поток.
    cv::calcOpticalFlowPyrLK(prv_mat, nxt_mat, ...);

    // Используем его.
    ...

    // Меняем матрицы местами, чтобы текущий "следующий" кадр
    // стал в новой итерации "предыдущим".
    std::swap(prv_mat, nxt_mat);
}


При использовании данного подхода на каждой итерации в while(true) {...} создание
пирамиды изображений будет производиться для каждого кадра, т.е. два раза.

Подход с использованием внешнего вызова buildOpticalFlowPyramid():

std::vector prv_pyr, nxt_pyr;

while(true) {
    if(prv_pyr.empty()) {
        cv::Mat mat = readNewFrame();
        if(mat.empty()) break;

        // Строим пирамиду изображений для кадра.
        cv::buildOpticalFlowPyramid(mat, prv_pyr, ...);

        continue;
    }

    cv::Mat mat = readNewFrame();
    if(mat.empty()) break;

    // Строим пирамиду изображений для нового кадра.
    cv::buildOpticalFlowPyramid(mat, nxt_pyr, ...);

    // Вычисляем оптический поток.
    cv::calcOpticalFlowPyrLK(prv_pyr, nxt_pyr, ...);

    // Используем его.
    ...

    // Меняем вектора местами, чтобы текущая "следующая" пирамида
    // стала в новой итерации "предыдущей".
    std::swap(prv_pyr, nxt_pyr);
}


При использовании данного подхода на каждой итерации в while(true) {...} создание
пирамиды изображений будет производиться только для одного кадра, т.е. один раз. Скорость
работы алгоритма может увеличиться в отдельных случаях в два раза.