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

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

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

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

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

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

$\{\begin{array}{c}{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{array}$

где

$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=\left[\begin{array}{cc}{I}_x(q_1)& I_y(q_1)\\ I_x(q_2)& I_y(q_2)\\ ⋮& ⋮\\ I_x(q_n)& I_y(q_n)\end{array}\right],v=\left[\begin{array}{c}{V}_x\\ V_y\end{array}\right],b=\left[\begin{array}{c}-I_t(q_1)\\ [10pt]-I_t(q_2)\\ [10pt]⋮\\ -I_t(q_n)\end{array}\right]$

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

$A^{T}Av=A^{T}b$,

откуда

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

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

$\left[\begin{array}{c}{V}_x\\ V_y\end{array}\right]={\left[\begin{array}{cc}\sum _i{I}_x(q_i{)}^2& \sum _i{I}_x(q_i)I_y(q_i)\\ \sum _i{I}_x(q_i)I_y(q_i)& \sum _i{I}_y(q_i{)}^2\end{array}\right]}^{-1}\left[\begin{array}{c}-\sum _i{I}_x(q_i)I_t(q_i)\\ -\sum _i{I}_y(q_i)I_t(q_i)\end{array}\right]$

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

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

$A^{T}WAv=A^{T}Wb$

или

$\mathrm{v}=(A^{T}WA{)}^{-1}{A}^{T}Wb$

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

$\left[\begin{array}{c}{V}_x\\ V_y\end{array}\right]={\left[\begin{array}{cc}\sum _i{w}_i{I}_x(q_i{)}^2& \sum _i{w}_i{I}_x(q_i)I_y(q_i)\\ \sum _i{w}_i{I}_x(q_i)I_y(q_i)& \sum _i{w}_i{I}_y(q_i{)}^2\end{array}\right]}^{-1}\left[\begin{array}{c}-\sum _i{w}_i{I}_x(q_i)I_t(q_i)\\ -\sum _i{w}_i{I}_y(q_i)I_t(q_i)\end{array}\right]$

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

См. также

• Оптический поток
• Визуальная одометрия

Ссылки

• 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