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

У комп'ютернім зорі, ме́тод Лу́каса — Кана́де (Шаблон:Lang-en, також алгори́тм Лу́каса — Кана́де) — це широко вживаний диференціальний метод оцінювання оптичного потоку, розроблений Шаблон:Нпні та Шаблон:Нп. Він спирається на припущення, що в локальному околі розгляданого пікселя цей потік є суттєво сталим, і розв'язує базові рівняння оптичного потоку для всіх пікселів у цьому околі методом найменших квадратів.^[1]^[2]

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

Принцип

Метод Лукаса — Канаде спирається на припущення, що зміщення вмісту зображення між двома сусідніми моментами (кадрами) є малим і приблизно сталим в межах околу точки $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})

⋮

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}$ у поточний момент часу.

Ці рівняння може бути записано в матричному вигляді $A v = b$ , де

A = [\begin{matrix} I_{x} (q_{1}) & I_{y} (q_{1}) \\ I_{x} (q_{2}) & I_{y} (q_{2}) \\ ⋮ & ⋮ \\ I_{x} (q_{n}) & I_{y} (q_{n}) \end{matrix}] v = [\begin{matrix} V_{x} \\ V_{y} \end{matrix}] b = [\begin{matrix} - I_{t} (q_{1}) \\ - I_{t} (q_{2}) \\ ⋮ \\ - I_{t} (q_{n}) \end{matrix}]

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

A^{T} A v = A^{T} b

або

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

де $A^{T}$ це транспонування матриці $A$ . Тобто, він обчислює

[\begin{matrix} V_{x} \\ V_{y} \end{matrix}] = {[\begin{matrix} \sum_{i} I_{x} (q_{i})^{2} & \sum_{i} I_{x} (q_{i}) I_{y} (q_{i}) \\ \sum_{i} I_{y} (q_{i}) I_{x} (q_{i}) & \sum_{i} I_{y} (q_{i})^{2} \end{matrix}]}^{- 1} [\begin{matrix} - \sum_{i} I_{x} (q_{i}) I_{t} (q_{i}) \\ - \sum_{i} I_{y} (q_{i}) I_{t} (q_{i}) \end{matrix}]

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

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

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

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

A^{T} W A v = A^{T} W b

або

v = (A^{T} W A)^{- 1} A^{T} W b

де $W$ це діагональна матриця $n \times n$ , що містить ваги $W_{i i} = w_{i}$ для призначення рівнянню пікселя $q_{i}$ . Тобто, воно обчислює

[\begin{matrix} V_{x} \\ V_{y} \end{matrix}] = {[\begin{matrix} \sum_{i} w_{i} I_{x} (q_{i})^{2} & \sum_{i} w_{i} I_{x} (q_{i}) I_{y} (q_{i}) \\ \sum_{i} w_{i} I_{x} (q_{i}) I_{y} (q_{i}) & \sum_{i} w_{i} I_{y} (q_{i})^{2} \end{matrix}]}^{- 1} [\begin{matrix} - \sum_{i} w_{i} I_{x} (q_{i}) I_{t} (q_{i}) \\ - \sum_{i} w_{i} I_{y} (q_{i}) I_{t} (q_{i}) \end{matrix}]

Вагу $w_{i}$ зазвичай встановлюють як гауссову функцію відстані між $q_{i}$ та $p$ .

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

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

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

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

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

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

Метод Лукаса — Канаде сам по собі можливо використовувати лише коли вектор потоку зображення $V_{x}, V_{y}$ між двома кадрами є достатньо малим, щоби виконувалося диференціальне рівняння оптичного потоку, що часто менше за відстань між пікселями. Коли вектор потоку може перевищувати це обмеження, як в узгоджуванні стереопар (Шаблон:Lang-en) або реєстрації деформованих документівШаблон:Уточнити термін (Шаблон:Lang-en), метод Лукаса — Канаде все ж можливо застосовувати для уточнювання деякої грубої оцінки того ж, отриманої іншими засобами; наприклад, шляхом екстраполювання векторів потоку, обчислених з попередніх кадрів, або виконанням методу Лукаса — Канаде на зменшених версіях зображень. Насправді, крайній метод є основою популярного алгоритму зіставляння ознак Канаде — Лукаса — Томазі (КЛТ).

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

Див. також

Примітки

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

Посилання

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

[LKproc-1] 1,0 ^1,1 B. D. Lucas and T. Kanade (1981), An iterative image registration technique with an application to stereo vision. Шаблон:Webarchive Proceedings of Imaging Understanding Workshop, pages 121--130 Шаблон:Ref-en

[Lthesis-2] Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences Шаблон:Webarchive (doctoral dissertation) Шаблон:Ref-en

[iteraLK-3] J. Y. Bouguet, (2001) . Pyramidal implementation of the affine lucas kanade feature tracker description of the algorithm. Intel Corporation, 5. Шаблон:Webarchive Шаблон:Ref-en

[1]

[2]

[3]

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

Зміст

Принцип

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

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

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

Див. також

Примітки

Посилання

Навігаційне меню

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

Принцип

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

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

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

Див. також

Примітки

Посилання

Навігаційне меню

Пошук