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

(Перенаправлено з Алгоритм Лукаса — Канаде)

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

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

Принцип ред.

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

 
 
 
 

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

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

 

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

  або
 

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

 

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

Матрицю   часто називають структурним тензором зображення в точці  .

Зважене вікно ред.

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

 

або

 

де   це діагональна матриця  , що містить ваги   для призначення рівнянню пікселя  . Тобто, воно обчислює

 

Вагу   зазвичай встановлюють як гауссову функцію відстані між   та  .

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

Для того, щоби рівняння   було розв'язним,   повинна бути невиродженою, або власні значення   повинні задовольняти  . Щоби уникнути проблеми шуму, зазвичай вимагають, щоби   було не надто малим. Також, якщо   є занадто великим, це означає, що точка   перебуває на ребрі, й цей метод страждає від проблеми вікна[en]. Отже, умова належної праці цього методу полягає в тому, щоби   та   були достатньо великими, й мали подібний порядок величини. Це також є умовою й для виявляння кутів. Це спостереження також показує, що можливо легко сказати, який піксель підходить для методу Лукаса — Канаде, перевіривши одне зображення.

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

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

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

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

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

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

Див. також ред.

Примітки ред.

  1. а б B. D. Lucas and T. Kanade (1981), An iterative image registration technique with an application to stereo vision. [Архівовано 17 січня 2009 у Wayback Machine.] Proceedings of Imaging Understanding Workshop, pages 121--130 (англ.)
  2. Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences [Архівовано 19 вересня 2017 у Wayback Machine.] (doctoral dissertation) (англ.)
  3. J. Y. Bouguet, (2001) . Pyramidal implementation of the affine lucas kanade feature tracker description of the algorithm. Intel Corporation, 5. [Архівовано 5 листопада 2021 у Wayback Machine.] (англ.)

Посилання ред.