Алгоритм Лукаса

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

Основное уравнение оптического потока содержит две неизвестных и не может быть однозначно разрешено. Алгоритм Лукаса—Канаде обходит неоднозначность за счет использования информации о соседних пикселях в каждой точке. Метод основан на предположении, что в локальной окрестности каждого пикселя значение оптического потока одинаково, таким образом можно записать основное уравнение оптического потока для всех пикселей окрестности и решить полученную систему уравнений методом наименьших квадратов.^[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)

Ссылки

• KLT: An Implementation of the Kanade-Lucas-Tomasi Feature Tracker
• 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.