LucasKanade - Описание алгоритма

Интернет магазин китайских планшетных компьютеров

Компьютеры - LucasKanade - Описание алгоритма

12 мая 2011

Оглавление:
1. LucasKanade
2. Описание алгоритма

Предположим, что смещение пикселей между двумя кадрами невелико. Рассмотрим пиксель p, тогда, по алгоритму Лукаса - Канаде, оптический поток должен быть одинаков для всех пикселей, находящихся в окне с центром в p. А именно, вектор оптического потока в точке p должен быть решением системы уравнений

I_xV_x + I_yV_y = − I_t

$\vdots$

I_xV_x + I_yV_y = − I_t

где $q_1,q_2,\dots,q_n$ - пиксели внутри окна, I_x,I_y,I_t - частные производные изображения I по координатам x, y и времени t, вычисленные в точке q_i.

Это уравнение может быть записано в матричной форме Av = b, где

$A = \begin{bmatrix} I_x & I_y \\ I_x & I_y \\ \vdots & \vdots \\ I_x & I_y \end{bmatrix}, \quad\quad v = \begin{bmatrix} V_x\\ V_y \end{bmatrix}, \quad\quad b = \begin{bmatrix} -I_t\\ -I_t\\ \vdots \\ -I_t \end{bmatrix}$

Полученную переопределенную систему решаем с помощью метода наименьших квадратов. Таким образом, получается система уравнений 2×2

AAv = Ab или

v = Ab

где A - транспонированная матрица A. Получаем,

$\begin{bmatrix} V_x\\ V_y \end{bmatrix} = \begin{bmatrix} \sum_i I_x^2 & \sum_i I_xI_y \\ \sum_i I_xI_y & \sum_i I_y^2 \end{bmatrix}^{-1} \begin{bmatrix} -\sum_i I_xI_t \\ -\sum_i I_yI_t \end{bmatrix}$

Взвешенное окно

В методе наименьших квадратов все n пикселей q_i в окне оказывают одинаковое влияние. Однако логичнее учитывать более близкие к p пиксели с большим весом. Для этого используется взвешенный метод наименьших квадратов,

AWAv = AWb

или

v = AWb

где W - диагональная матрица n×n, содержащая веса W_ii = w_i, которые будут присвоены пикселям q_i. Поучаем следующую систему уравнений:

$\begin{bmatrix} V_x\\ V_y \end{bmatrix} = \begin{bmatrix} \sum_i w_i I_x^2 & \sum_i w_i I_xI_y \\ \sum_i w_i I_xI_y & \sum_i w_i I_y^2 \end{bmatrix}^{-1} \begin{bmatrix} -\sum_i w_i I_xI_t \\ -\sum_i w_i I_yI_t \end{bmatrix}$

В качестве весов w_i обычно используется нормальное распределение расстояния между q_i и p.

<<< Google Goggles

RANSAC >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие