Русская Википедия:Алгоритм Лукаса — Канаде
Алгоритм Лукаса — Канаде — широко используемый в компьютерном зрении дифференциальный локальный метод вычисления оптического потока.
Основное уравнение оптического потока содержит две неизвестных и не может быть однозначно разрешено. Алгоритм Лукаса — Канаде обходит неоднозначность за счет использования информации о соседних пикселях в каждой точке. Метод основан на предположении, что в локальной окрестности каждого пикселя значение оптического потока одинаково, таким образом можно записать основное уравнение оптического потока для всех пикселей окрестности и решить полученную систему уравнений методом наименьших квадратов.[1][2]
Алгоритм Лукаса — Канаде менее чувствителен к шуму на изображениях, чем поточечные методы, однако является сугубо локальным и не может определить направление движения пикселей внутри однородных областей.
Описание алгоритма
Предположим, что смещение пикселей между двумя кадрами невелико. Рассмотрим пиксель p, тогда, по алгоритму Лукаса — Канаде, оптический поток должен быть одинаков для всех пикселей, находящихся в окне с центром в p. А именно, вектор оптического потока <math>(V_x,V_y)</math> в точке p должен быть решением системы уравнений
- <math>\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}</math> где
- <math>q_1,q_2,\dots,q_n</math> — пиксели внутри окна,
- <math>I_x(q_i),I_y(q_i),I_t(q_i)</math> — частные производные изображения <math>I</math> по координатам x, y и времени t, вычисленные в точке <math>q_i</math>.
Это уравнение может быть записано в матричной форме:
- <math>A v = b</math>,
где
- <math>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} </math>
Полученную переопределенную систему решаем с помощью метода наименьших квадратов. Таким образом, получается система уравнений 2×2:
- <math>A^T A v=A^T b</math>,
откуда
- <math> \mathrm{v}=(A^T A)^{-1}A^T b</math>,
где <math>A^T</math> — транспонированная матрица <math>A</math>. Получаем:
- <math>\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} </math>
Взвешенное окно
В методе наименьших квадратов все n пикселей <math>q_i</math> в окне оказывают одинаковое влияние. Однако логичнее учитывать более близкие к p пиксели с большим весом. Для этого используется взвешенный метод наименьших квадратов,
- <math>A^T W A v=A^T W b</math>
или
- <math> \mathrm{v}=(A^T W A)^{-1}A^T W b</math>
где <math>W</math> — диагональная матрица n×n, содержащая веса <math>W_{i i} = w_i</math>, которые будут присвоены пикселям <math>q_i</math>. Получаем следующую систему уравнений:
- <math>\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} </math>
В качестве весов <math>w_i</math> обычно используется нормальное распределение расстояния между <math>q_i</math> и 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
- ↑ B. D. Lucas and T. Kanade (1981), An iterative image registration technique with an application to stereo vision. Шаблон:Wayback Proceedings of Imaging Understanding Workshop, pages 121--130
- ↑ Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences Шаблон:Webarchive (doctoral dissertation)
