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

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

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

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

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

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

$\{\begin{array}{l}{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}$${\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 <!--\; \dots \; -->,q_n$$q_{1},q_{2},\dots ,q_{n}$  — пиксели внутри окна,

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

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

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

откуда

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

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

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

или

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

где $W$$W$  — диагональная матрица n×n, содержащая веса $W_{ii}=w_i$$W_{ii}=w_{i}$ , которые будут присвоены пикселям $q_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$$w_{i}$  обычно используется нормальное распределение расстояния между $q_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