Метод Лукаса — Канаде

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

${\displaystyle I_{x}(q_{1})V_{x}+I_{y}(q_{1})V_{y}=-I_{t}(q_{1})}$

${\displaystyle I_{x}(q_{2})V_{x}+I_{y}(q_{2})V_{y}=-I_{t}(q_{2})}$

${\displaystyle \vdots }$

${\displaystyle I_{x}(q_{n})V_{x}+I_{y}(q_{n})V_{y}=-I_{t}(q_{n})}$

де ${\displaystyle q_{1},q_{2},\dots ,q_{n}}$ це пікселі всередині вікна, а ${\displaystyle I_{x}(q_{i}),I_{y}(q_{i}),I_{t}(q_{i})}$ це частинні похідні зображення ${\displaystyle I}$ за положенням за ${\displaystyle x,y}$ та часом ${\displaystyle 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 \quad v={\begin{bmatrix}V_{x}\\[10pt]V_{y}\end{bmatrix}}\quad \quad \quad b={\begin{bmatrix}-I_{t}(q_{1})\\[10pt]-I_{t}(q_{2})\\[10pt]\vdots \\[10pt]-I_{t}(q_{n})\end{bmatrix}}}$

Ця система має більше рівнянь ніж невідомих, і відтак є надвизначеною. Метод Лукаса — Канаде отримує компромісний розв'язок за допомогою принципу найменших квадратів. А саме, він розв'язує систему ${\displaystyle 2\times 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_{y}(q_{i})I_{x}(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}}}$

де середня матриця в цьому рівнянні це обернена матриця. Суми пробігають ${\displaystyle i}$ від ${\displaystyle 0}$ до ${\displaystyle n}$.

Матрицю ${\displaystyle A^{T}A}$ часто називають структурним тензором зображення в точці ${\displaystyle p}$.

Наведене вище просте розв'язання методом найменших квадратів надає однакової важливості всім ${\displaystyle n}$ пікселям ${\displaystyle q_{i}}$ у вікні. На практиці зазвичай краще надавати більшої ваги пікселям, ближчим до центрального пікселя ${\displaystyle p}$. Для цього використовують зважену версію рівняння найменших квадратів,

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

або

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

де ${\displaystyle W}$ це діагональна матриця ${\displaystyle n\times 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}}$ та ${\displaystyle p}$.

Для того, щоби рівняння ${\displaystyle A^{T}Av=A^{T}b}$ було розв'язним, ${\displaystyle A^{T}A}$ повинна бути невиродженою, або власні значення ${\displaystyle A^{T}A}$ повинні задовольняти ${\displaystyle \lambda _{1}\geq \lambda _{2}>0}$. Щоби уникнути проблеми шуму, зазвичай вимагають, щоби ${\displaystyle \lambda _{2}}$ було не надто малим. Також, якщо ${\displaystyle \lambda _{1}/\lambda _{2}}$ є занадто великим, це означає, що точка ${\displaystyle p}$ перебуває на ребрі, й цей метод страждає від проблеми вікна. Отже, умова належної праці цього методу полягає в тому, щоби ${\displaystyle \lambda _{1}}$ та ${\displaystyle \lambda _{2}}$ були достатньо великими, й мали подібний порядок величини. Це також є умовою й для виявляння кутів. Це спостереження також показує, що можливо легко сказати, який піксель підходить для методу Лукаса — Канаде, перевіривши одне зображення.

Одним з основних припущень цього методу є те, що рух є невеликим (наприклад, менше 1 пікселя між зображеннями). Якщо рух є великим і порушує це припущення, однією з методик є спершу знижувати роздільність зображення, а потім застосовувати метод Лукаса — Канаде.[3]

Щоби добиватися за допомогою цього методу відстежування руху, вектор потоку можливо застосовувати й перераховувати ітеративно, поки не буде досягнуто певного порогу близько нуля, після чого можливо припустити, що вікна об'єкту дуже близькі за схожістю.[1] Роблячи це для кожного наступного вікна відстежування, цю точку можливо послідовно відстежувати протягом кількох зображень, поки її або не буде затулено, або вона вийде з кадру.

Підхід найменших квадратів неявно припускає, що похибки в даних зображення мають гауссів розподіл з нульовим середнім. Якщо очікують, що вікно міститиме певний відсоток «викидів» (вкрай неправильних значень даних, що не слідують «звичайному» гауссовому розподілу похибок), можуть використовувати статистичний аналіз, щоби виявляти їх, і знижувати відповідно їхню вагу.

Метод Лукаса — Канаде сам по собі можливо використовувати лише коли вектор потоку зображення ${\displaystyle V_{x},V_{y}}$ між двома кадрами є достатньо малим, щоби виконувалося диференціальне рівняння оптичного потоку, що часто менше за відстань між пікселями. Коли вектор потоку може перевищувати це обмеження, як в узгоджуванні стереопар (англ. stereo matching) або реєстрації деформованих документів^{[уточнити термін]} (англ. warped document registration), метод Лукаса — Канаде все ж можливо застосовувати для уточнювання деякої грубої оцінки того ж, отриманої іншими засобами; наприклад, шляхом екстраполювання векторів потоку, обчислених з попередніх кадрів, або виконанням методу Лукаса — Канаде на зменшених версіях зображень. Насправді, крайній метод є основою популярного алгоритму зіставляння ознак Канаде — Лукаса — Томасі (КЛТ).

Подібну методику можливо застосовувати для обчислювання диференціальних афінних деформацій вмісту зображення.

• Оптичний потік
• Метод Горна — Шунка
• Алгоритм виявляння кутів Сі — Томасі
• Відстежувач ознак Канаде — Лукаса — Томасі

1. B. D. Lucas and T. Kanade (1981), An iterative image registration technique with an application to stereo vision. Proceedings of Imaging Understanding Workshop, pages 121--130 (англ.)
2. Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences (doctoral dissertation) (англ.)
3. J. Y. Bouguet, (2001) . Pyramidal implementation of the affine lucas kanade feature tracker description of the algorithm. Intel Corporation, 5. (англ.)

• Плагін стабілізування зображення для ImageJ на основі методу Лукаса — Канаде
• Mathworks Lucas-Kanade, втілення для Matlab оберненого та нормального афінного Лукаса — Канаде
• FolkiGPU: втілення на ГП оптичного потоку на основі ітеративного Лукаса — Канаде
• KLT: втілення відстежувача ознак Канаде — Лукаса — Томасі
• Takeo Kanade (англ.)
• Приклад мовою C++ з використанням алгоритму оптичного потоку Лукаса — Канаде
• Приклад мовою Python з використанням алгоритму оптичного потоку Лукаса — Канаде
• Приклад мовою Python з використанням відстежувача Лукаса — Канаде для зіставляння гомографії
• Швидкий приклад в MATLAB методу Лукаса — Канаде для показування оптичного потоку
• Швидкий приклад в MATLAB методу Лукаса — Канаде для показування векторів швидкостей об'єктів