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

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

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

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

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

${\displaystyle {\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}}}$

где

${\displaystyle q_{1},q_{2},\dots ,q_{n}}$ — пиксели внутри окна,

${\displaystyle I_{x}(q_{i}),I_{y}(q_{i}),I_{t}(q_{i})}$ — частные производные изображения ${\displaystyle I}$ по координатам x , y и времени t , вычисленные в точке ${\displaystyle q_{i}}$ .

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

${\displaystyle Av=b}$ ,

где

${\displaystyle 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:

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

откуда

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

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

${\displaystyle {\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 пикселей ${\displaystyle q_{i}}$ в окне оказывают одинаковое влияние. Однако логичнее учитывать более близкие к p пиксели с большим весом. Для этого используется взвешенный метод наименьших квадратов,

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

или

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

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

${\displaystyle {\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}}}$

В качестве весов ${\displaystyle w_{i}}$ обычно используется нормальное распределение расстояния между ${\displaystyle q_{i}}$ и p .

См. также

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

Примечания

Ссылки

• , by Dor Barber. Tel Aviv University. Updated 31 December 2010.
• based on the Lucas-Kanade method
• Matlab implementation of inverse and normal affine Lucas-Kanade
• GPU implementation of a Lucas-Kanade based optical flow