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

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

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

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

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

Предположим, что смещение пикселей между двумя кадрами невелико. Рассмотрим пиксель 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}$.

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

$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^{T}Av=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}WAv=A^{T}Wb$

или

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

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

См. также

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

Ссылки

• 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