WikiSort.ru - Не сортированное

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

Основное уравнение оптического потока содержит две неизвестных и не может быть однозначно разрешено. Алгоритм Лукаса — Канаде обходит неоднозначность за счет использования информации о соседних пикселях в каждой точке. Метод основан на предположении, что в локальной окрестности каждого пикселя значение оптического потока одинаково, таким образом можно записать основное уравнение оптического потока для всех пикселей окрестности и решить полученную систему уравнений методом наименьших квадратов.^[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.

См. также

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

Примечания

Ссылки

• 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
• Lucas-Kanade for the iPhone (недоступная ссылка) by Success Labs. A modified and enhanced port of the OpenCV lkdemo sample application to the iPhone.