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

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

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

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

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

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

См. также

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

Примечания

1. B. D. Lucas and T. Kanade (1981), An iterative image registration technique with an application to stereo vision. Архивная копия от 17 января 2009 на Wayback Machine Proceedings of Imaging Understanding Workshop, pages 121--130
2. Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences Архивировано 11 июня 2007 года. (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