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

У комп'ютернім зорі, ме́тод Лу́каса — Кана́де (англ. Lucas–Kanade method, також алгори́тм Лу́каса — Кана́де) — це широко вживаний диференціальний метод оцінювання оптичного потоку, розроблений Брюсом Д. Лукасом та Такео Канаде. Він спирається на припущення, що в локальному околі розгляданого пікселя цей потік є суттєво сталим, і розв'язує базові рівняння оптичного потоку для всіх пікселів у цьому околі методом найменших квадратів.

Поєднуючи інформацію з кількох сусідніх пікселів, метод Лукаса — Канаде часто здатен розв'язувати притаманну невизначеність рівняння оптичного потоку. Він також менш чутливий до шуму в зображенні, ніж поточкові методи. З іншого боку, оскільки це суто локальний метод, він не здатен надавати інформацію про потік всередині однорідних областей зображення.

Принцип

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

$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})$

$\vdots$

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

де $q_{1},q_{2},\dots ,q_{n}$ це пікселі всередині вікна, а $I_{x}(q_{i}),I_{y}(q_{i}),I_{t}(q_{i})$ це частинні похідні зображення $I$ за положенням за $x,y$ та часом $t$, оцінювані в точці $q_{i}$ у поточний момент часу.

Ці рівняння може бути записано в матричному вигляді $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 \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}}$

Ця система має більше рівнянь ніж невідомих, і відтак є надвизначеною. Метод Лукаса — Канаде отримує компромісний розв'язок за допомогою принципу найменших квадратів. А саме, він розв'язує систему $2\times 2$

$A^{T}Av=A^{T}b$ або

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

де $A^{T}$ це транспонування матриці $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_{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}}$

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

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

Зважене вікно

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

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

або

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

де $W$ це діагональна матриця $n\times n$, що містить ваги $W_{ii}=w_{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}$ зазвичай встановлюють як гауссову функцію відстані між $q_{i}$ та $p$.

Умови та методики використання

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

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

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

Втілення та розширення

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

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

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

Див. також

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

Посилання

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