Что такое optical flow и в чём разница между методами Lucas-Kanade и Farneback?

Question

Accepted Answer

Что такое optical flow

Optical flow (оптический поток) — вектор смещения для каждого пикселя между двумя последовательными кадрами. Описывает, в каком направлении и на сколько пикселей переместилась каждая точка изображения. Применяется для анализа движения, трекинга объектов, стабилизации видео, сжатия видео и вычисления скорости объектов.

Два подхода: разреженный и плотный поток

Разреженный (sparse) — вычисляется только для выбранных ключевых точек. Алгоритм Lucas-Kanade.
Плотный (dense) — вектор смещения для каждого пикселя. Алгоритм Farneback.

Lucas-Kanade: разреженный поток

Предполагает, что пиксели в небольшой окрестности (окно) движутся одинаково. Решает систему линейных уравнений методом наименьших квадратов. Реализован через cv2.calcOpticalFlowPyrLK.

import cv2
import numpy as np

cap = cv2.VideoCapture("video.mp4")
ret, old_frame = cap.read()
old_gray = cv2.cvtColor(old_frame, cv2.COLOR_BGR2GRAY)

# Детекция начальных точек (Shi-Tomasi)
feature_params = dict(maxCorners=200, qualityLevel=0.3,
                      minDistance=7, blockSize=7)
p0 = cv2.goodFeaturesToTrack(old_gray, mask=None, **feature_params)

# Параметры Lucas-Kanade
lk_params = dict(
    winSize=(15, 15),
    maxLevel=2,  # пирамида 3 уровня
    criteria=(cv2.TERM_CRITERIA_EPS | cv2.TERM_CRITERIA_COUNT, 10, 0.03)
)

while True:
    ret, frame = cap.read()
    if not ret or p0 is None:
        break

    frame_gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)

    # Трекинг точек
    p1, status, error = cv2.calcOpticalFlowPyrLK(
        old_gray, frame_gray, p0, None, **lk_params
    )

    # Только успешно отслеженные точки
    good_new = p1[status == 1]
    good_old = p0[status == 1]

    for new, old in zip(good_new, good_old):
        a, b = new.ravel().astype(int)
        c, d = old.ravel().astype(int)
        cv2.arrowedLine(frame, (c, d), (a, b), (0, 255, 0), 2)

    old_gray = frame_gray.copy()
    p0 = good_new.reshape(-1, 1, 2)

cap.release()

Farneback: плотный поток

Аппроксимирует окрестность каждого пикселя полиномом второго порядка, сравнивает коэффициенты между кадрами. Вычисляет вектор смещения для каждого пикселя. Медленнее Lucas-Kanade, но даёт полную карту движения. Реализован через cv2.calcOpticalFlowFarneback.

import cv2
import numpy as np

cap = cv2.VideoCapture("video.mp4")
ret, prev = cap.read()
prev_gray = cv2.cvtColor(prev, cv2.COLOR_BGR2GRAY)

while True:
    ret, curr = cap.read()
    if not ret:
        break

    curr_gray = cv2.cvtColor(curr, cv2.COLOR_BGR2GRAY)

    # flow.shape = (H, W, 2) — (dx, dy) для каждого пикселя
    flow = cv2.calcOpticalFlowFarneback(
        prev_gray, curr_gray,
        flow=None,
        pyr_scale=0.5,    # масштаб пирамиды
        levels=3,          # уровней пирамиды
        winsize=15,        # размер окна усреднения
        iterations=3,      # итерации на каждом уровне
        poly_n=5,          # размер пикселя полиномиальной экспансии
        poly_sigma=1.2,    # дисперсия гауссиана
        flags=0
    )

    # Визуализация через HSV
    mag, ang = cv2.cartToPolar(flow[..., 0], flow[..., 1])
    hsv = np.zeros_like(prev)
    hsv[..., 1] = 255
    hsv[..., 0] = ang * 180 / np.pi / 2
    hsv[..., 2] = cv2.normalize(mag, None, 0, 255, cv2.NORM_MINMAX)
    bgr = cv2.cvtColor(hsv, cv2.COLOR_HSV2BGR)

    cv2.imshow("Dense Flow", bgr)
    if cv2.waitKey(30) & 0xFF == ord('q'):
        break

    prev_gray = curr_gray

cap.release()
cv2.destroyAllWindows()

Сравнение методов

Lucas-Kanade: быстрый, подходит для realtime трекинга небольшого числа точек, требует предварительной детекции ключевых точек, плохо справляется с большими смещениями.
Farneback: плотный, даёт полную карту движения, медленнее (~10-20 FPS на CPU для Full HD), лучше для анализа общего движения в сцене.

Подводные камни

Lucas-Kanade теряет точки — status-массив содержит 0 для потерянных точек. Без фильтрации по status получите мусорные координаты.
Пирамида (maxLevel) нужна для больших смещений — при быстром движении без пирамиды алгоритм расходится. Увеличьте maxLevel до 3-4.
Farneback не работает на статичных сценах — шум камеры создаёт ненулевой поток; нужно пороговое отсечение по величине mag.
poly_sigma должна соответствовать poly_n — для poly_n=5 используйте poly_sigma=1.1–1.2, для poly_n=7 — poly_sigma=1.5. Несоответствие даёт размытый поток.
Предположение о яркостном постоянстве — оба метода предполагают, что яркость пикселя не меняется между кадрами. Изменение освещения или быстрая экспозиция нарушают это допущение.
Граничные артефакты в Farneback — края кадра имеют неполные окна усреднения и дают менее точный поток; обрезайте граничную полосу при анализе.

Что такое optical flow и в чём разница между методами Lucas-Kanade и Farneback?