Lucas–Kanade

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

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

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

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

I_x(q₁)V_x + I_y(q₁)V_y = − I_t(q₁)

I_x(q₂)V_x + I_y(q₂)V_y = − I_t(q₂)

$\vdots$

I_x(q_n)V_x + I_y(q_n)V_y = − I_t(q_n)

где $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.

Это уравнение может быть записано в матричной форме Av = 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^TAv = A^Tb или

v = (A^TA) ^{− 1}A^Tb

где 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^TWAv = A^TWb

или

v = (A^TWA) ^{− 1}A^TWb

где W - диагональная матрица n×n, содержащая веса W_ii = 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)

• KLT: An Implementation of the Kanade–Lucas–Tomasi Feature Tracker
• [1]: Takeo Kanade

Примечания

• Dor's Image Processing Site, Mandatory site for IP algorithm developers, by Dor Barber. Tel Aviv University. Updated 31 December 2010.
• The image stabilizer plugin for ImageJ based on the Lucas–Kanade method
• Mathworks Lucas-Kanade Matlab implementation of inverse and normal affine Lucas-Kanade
• The French Aerospace Lab : GPU implementation of a Lucas-Kanade based optical flow
• Lucas-Kanade for the iPhone by Success Labs. A modified and enhanced port of the OpenCV lkdemo sample application to the iPhone.