Алгоритм Лукаса — Канаде

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Лукаса—Канаде — широко используемый в компьютерном зрении дифференциальный локальный метод вычисления оптического потока.

Основное уравнение оптического потока содержит две неизвестных и не может быть однозначно разрешено. Алгоритм Лукаса—Канаде обходит неоднозначность за счет использования информации о соседних пикселях в каждой точке. Метод основан на предположении, что в локальной окрестности каждого пикселя значение оптического потока одинаково, таким образом можно записать основное уравнение оптического потока для всех пикселей окрестности и решить полученную систему уравнений методом наименьших квадратов.[1][2]

Алгоритм Лукаса—Канаде менее чувствителен к шуму на изображениях, чем поточечные методы, однако является сугубо локальным и не может определить направление движения пикселей внутри однородных областей.


Описание алгоритма[править | править вики-текст]

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

\begin{cases}
I_x(q_1) V_x + I_y (q_1) V_y = -I_t(q_1)\\
I_x(q_2) V_x + I_y (q_2) V_y = -I_t(q_2)\\
...\\
I_x(q_n) V_x + I_y (q_n) V_y = -I_t(q_n)\\
\end{cases}

где

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

Это уравнение может быть записано в матричной форме:

A v = b,

где

A = \begin{bmatrix}
I_x(q_1) & I_y(q_1) \\[10pt]
I_x(q_2) & I_y(q_2) \\[10pt]
\vdots  & \vdots  \\[10pt]
I_x(q_n) & I_y(q_n) 
\end{bmatrix},
\quad\quad
v = 
\begin{bmatrix}
V_x\\[10pt]
V_y
\end{bmatrix},
\quad\quad
b = 
\begin{bmatrix}
-I_t(q_1)\\ [10pt]
-I_t(q_2)\\ [10pt]
\vdots \\[10pt]
-I_t(q_n)
\end{bmatrix}

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

A^T A v=A^T b,

откуда

	\mathrm{v}=(A^T A)^{-1}A^T b,

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

\begin{bmatrix}
V_x\\[10pt]
V_y
\end{bmatrix} 
=
\begin{bmatrix}
\sum_i I_x(q_i)^2       & \sum_i I_x(q_i)I_y(q_i) \\[10pt]
\sum_i I_x(q_i)I_y(q_i) & \sum_i I_y(q_i)^2 
\end{bmatrix}^{-1}
\begin{bmatrix}
-\sum_i I_x(q_i)I_t(q_i) \\[10pt]
-\sum_i I_y(q_i)I_t(q_i)
\end{bmatrix}

Взвешенное окно[править | править вики-текст]

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

A^T W A v=A^T W b

или

	\mathrm{v}=(A^T W A)^{-1}A^T W b

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

\begin{bmatrix}
V_x\\[10pt]
V_y
\end{bmatrix} 
=
\begin{bmatrix}
\sum_i w_i I_x(q_i)^2      & \sum_i w_i I_x(q_i)I_y(q_i) \\[10pt]
\sum_i w_i I_x(q_i)I_y(q_i) & \sum_i w_i I_y(q_i)^2      
\end{bmatrix}^{-1}
\begin{bmatrix}
-\sum_i w_i I_x(q_i)I_t(q_i) \\[10pt]
-\sum_i w_i I_y(q_i)I_t(q_i)
\end{bmatrix}

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. B. D. Lucas and T. Kanade (1981), An iterative image registration technique with an application to stereo vision. Proceedings of Imaging Understanding Workshop, pages 121--130
  2. Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences (doctoral dissertation)

Ссылки[править | править вики-текст]