У комп'ютернім зорі, ме́тод Лу́каса — Кана́де (англ. Lucas–Kanade method, також алгори́тм Лу́каса — Кана́де) — це широко вживаний диференціальний метод оцінювання оптичного потоку, розроблений та [en]. Він спирається на припущення, що в локальному околі розгляданого пікселя цей потік є суттєво сталим, і розв'язує базові рівняння оптичного потоку для всіх пікселів у цьому околі методом найменших квадратів.
Поєднуючи інформацію з кількох сусідніх пікселів, метод Лукаса — Канаде часто здатен розв'язувати притаманну невизначеність рівняння оптичного потоку. Він також менш чутливий до шуму в зображенні, ніж поточкові методи. З іншого боку, оскільки це суто локальний метод, він не здатен надавати інформацію про потік всередині однорідних областей зображення.
Принцип
Метод Лукаса — Канаде спирається на припущення, що зміщення вмісту зображення між двома сусідніми моментами (кадрами) є малим і приблизно сталим в межах околу точки , яку розглядають. Таким чином, можна вважати, що рівняння оптичного потоку виконується для всіх пікселів у межах вікна з центром в . А саме, вектор локального потоку (швидкості) зображення мусить задовольняти
де це пікселі всередині вікна, а це частинні похідні зображення за положенням за та часом , оцінювані в точці у поточний момент часу.
Ці рівняння може бути записано в матричному вигляді , де
Ця система має більше рівнянь ніж невідомих, і відтак є надвизначеною. Метод Лукаса — Канаде отримує компромісний розв'язок за допомогою принципу [en]. А саме, він розв'язує систему
- або
де це транспонування матриці . Тобто, він обчислює
де середня матриця в цьому рівнянні це (обернена матриця). Суми пробігають від до .
Матрицю часто називають структурним тензором зображення в точці .
Зважене вікно
Наведене вище просте розв'язання методом найменших квадратів надає однакової важливості всім пікселям у вікні. На практиці зазвичай краще надавати більшої ваги пікселям, ближчим до центрального пікселя . Для цього використовують зважену версію рівняння найменших квадратів,
або
де це діагональна матриця , що містить ваги для призначення рівнянню пікселя . Тобто, воно обчислює
Вагу зазвичай встановлюють як гауссову функцію відстані між та .
Умови та методики використання
Для того, щоби рівняння було розв'язним, повинна бути невиродженою, або власні значення повинні задовольняти . Щоби уникнути проблеми шуму, зазвичай вимагають, щоби було не надто малим. Також, якщо є занадто великим, це означає, що точка перебуває на ребрі, й цей метод страждає від [en]. Отже, умова належної праці цього методу полягає в тому, щоби та були достатньо великими, й мали подібний порядок величини. Це також є умовою й для виявляння кутів. Це спостереження також показує, що можливо легко сказати, який піксель підходить для методу Лукаса — Канаде, перевіривши одне зображення.
Одним з основних припущень цього методу є те, що рух є невеликим (наприклад, менше 1 пікселя між зображеннями). Якщо рух є великим і порушує це припущення, однією з методик є спершу знижувати роздільність зображення, а потім застосовувати метод Лукаса — Канаде.
Щоби добиватися за допомогою цього методу відстежування руху, вектор потоку можливо застосовувати й перераховувати ітеративно, поки не буде досягнуто певного порогу близько нуля, після чого можливо припустити, що вікна об'єкту дуже близькі за схожістю. Роблячи це для кожного наступного вікна відстежування, цю точку можливо послідовно відстежувати протягом кількох зображень, поки її або не буде затулено, або вона вийде з кадру.
Втілення та розширення
Підхід найменших квадратів неявно припускає, що похибки в даних зображення мають гауссів розподіл з нульовим середнім. Якщо очікують, що вікно міститиме певний відсоток «викидів» (вкрай неправильних значень даних, що не слідують «звичайному» гауссовому розподілу похибок), можуть використовувати статистичний аналіз, щоби виявляти їх, і знижувати відповідно їхню вагу.
Метод Лукаса — Канаде сам по собі можливо використовувати лише коли вектор потоку зображення між двома кадрами є достатньо малим, щоби виконувалося диференціальне рівняння оптичного потоку, що часто менше за відстань між пікселями. Коли вектор потоку може перевищувати це обмеження, як в узгоджуванні стереопар (англ. stereo matching) або реєстрації деформованих документів[] (англ. warped document registration), метод Лукаса — Канаде все ж можливо застосовувати для уточнювання деякої грубої оцінки того ж, отриманої іншими засобами; наприклад, шляхом екстраполювання векторів потоку, обчислених з попередніх кадрів, або виконанням методу Лукаса — Канаде на зменшених версіях зображень. Насправді, крайній метод є основою популярного алгоритму зіставляння ознак Канаде — Лукаса — Томазі (КЛТ).
Подібну методику можливо застосовувати для обчислювання диференціальних афінних деформацій вмісту зображення.
Див. також
Примітки
- 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 (англ.)
- Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences [ 19 вересня 2017 у Wayback Machine.] (doctoral dissertation) (англ.)
- J. Y. Bouguet, (2001) . Pyramidal implementation of the affine lucas kanade feature tracker description of the algorithm. Intel Corporation, 5. [ 5 листопада 2021 у Wayback Machine.] (англ.)
Посилання
- Плагін стабілізування зображення для ImageJ на основі методу Лукаса — Канаде
- Mathworks Lucas-Kanade, втілення для Matlab оберненого та нормального афінного Лукаса — Канаде
- втілення на ГП оптичного потоку на основі ітеративного Лукаса — Канаде
- KLT: втілення відстежувача ознак Канаде — Лукаса — Томазі
- Takeo Kanade (англ.)
- Приклад мовою C++ з використанням алгоритму оптичного потоку Лукаса — Канаде
- Приклад мовою Python з використанням алгоритму оптичного потоку Лукаса — Канаде
- Приклад мовою Python з використанням відстежувача Лукаса — Канаде для зіставляння гомографії
- Швидкий приклад в MATLAB методу Лукаса — Канаде для показування оптичного потоку
- Швидкий приклад в MATLAB методу Лукаса — Канаде для показування векторів швидкостей об'єктів
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U komp yuternim zori me tod Lu kasa Kana de angl Lucas Kanade method takozh algori tm Lu kasa Kana de ce shiroko vzhivanij diferencialnij metod ocinyuvannya optichnogo potoku rozroblenij ta en Vin spirayetsya na pripushennya sho v lokalnomu okoli rozglyadanogo pikselya cej potik ye suttyevo stalim i rozv yazuye bazovi rivnyannya optichnogo potoku dlya vsih pikseliv u comu okoli metodom najmenshih kvadrativ Poyednuyuchi informaciyu z kilkoh susidnih pikseliv metod Lukasa Kanade chasto zdaten rozv yazuvati pritamannu neviznachenist rivnyannya optichnogo potoku Vin takozh mensh chutlivij do shumu v zobrazhenni nizh potochkovi metodi Z inshogo boku oskilki ce suto lokalnij metod vin ne zdaten nadavati informaciyu pro potik vseredini odnoridnih oblastej zobrazhennya PrincipMetod Lukasa Kanade spirayetsya na pripushennya sho zmishennya vmistu zobrazhennya mizh dvoma susidnimi momentami kadrami ye malim i priblizno stalim v mezhah okolu tochki p displaystyle p yaku rozglyadayut Takim chinom mozhna vvazhati sho rivnyannya optichnogo potoku vikonuyetsya dlya vsih pikseliv u mezhah vikna z centrom v p displaystyle p A same vektor lokalnogo potoku shvidkosti zobrazhennya Vx Vy displaystyle V x V y musit zadovolnyati Ix q1 Vx Iy q1 Vy It q1 displaystyle I x q 1 V x I y q 1 V y I t q 1 Ix q2 Vx Iy q2 Vy It q2 displaystyle I x q 2 V x I y q 2 V y I t q 2 displaystyle vdots Ix qn Vx Iy qn Vy It qn displaystyle I x q n V x I y q n V y I t q n de q1 q2 qn displaystyle q 1 q 2 dots q n ce pikseli vseredini vikna a Ix qi Iy qi It qi displaystyle I x q i I y q i I t q i ce chastinni pohidni zobrazhennya I displaystyle I za polozhennyam za x y displaystyle x y ta chasom t displaystyle t ocinyuvani v tochci qi displaystyle q i u potochnij moment chasu Ci rivnyannya mozhe buti zapisano v matrichnomu viglyadi Av b displaystyle Av b de A Ix q1 Iy q1 Ix q2 Iy q2 Ix qn Iy qn v VxVy b It q1 It q2 It qn displaystyle A begin bmatrix I x q 1 amp I y q 1 10pt I x q 2 amp I y q 2 10pt vdots amp vdots 10pt I x q n amp 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 Cya sistema maye bilshe rivnyan nizh nevidomih i vidtak ye nadviznachenoyu Metod Lukasa Kanade otrimuye kompromisnij rozv yazok za dopomogoyu principu en A same vin rozv yazuye sistemu 2 2 displaystyle 2 times 2 ATAv ATb displaystyle A T Av A T b abo v ATA 1ATb displaystyle mathrm v A T A 1 A T b de AT displaystyle A T ce transponuvannya matrici A displaystyle A Tobto vin obchislyuye VxVy iIx qi 2 iIx qi Iy qi iIy qi Ix qi iIy qi 2 1 iIx qi It qi iIy qi It qi displaystyle begin bmatrix V x 10pt V y end bmatrix begin bmatrix sum i I x q i 2 amp sum i I x q i I y q i 10pt sum i I y q i I x q i amp 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 de serednya matricya v comu rivnyanni ce obernena matricya Sumi probigayut i displaystyle i vid 0 displaystyle 0 do n displaystyle n Matricyu ATA displaystyle A T A chasto nazivayut strukturnim tenzorom zobrazhennya v tochci p displaystyle p Zvazhene viknoNavedene vishe proste rozv yazannya metodom najmenshih kvadrativ nadaye odnakovoyi vazhlivosti vsim n displaystyle n pikselyam qi displaystyle q i u vikni Na praktici zazvichaj krashe nadavati bilshoyi vagi pikselyam blizhchim do centralnogo pikselya p displaystyle p Dlya cogo vikoristovuyut zvazhenu versiyu rivnyannya najmenshih kvadrativ ATWAv ATWb displaystyle A T WAv A T Wb abo v ATWA 1ATWb displaystyle mathrm v A T WA 1 A T Wb de W displaystyle W ce diagonalna matricya n n displaystyle n times n sho mistit vagi Wii wi displaystyle W ii w i dlya priznachennya rivnyannyu pikselya qi displaystyle q i Tobto vono obchislyuye VxVy iwiIx qi 2 iwiIx qi Iy qi iwiIx qi Iy qi iwiIy qi 2 1 iwiIx qi It qi iwiIy qi It qi displaystyle begin bmatrix V x 10pt V y end bmatrix begin bmatrix sum i w i I x q i 2 amp 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 amp 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 Vagu wi displaystyle w i zazvichaj vstanovlyuyut yak gaussovu funkciyu vidstani mizh qi displaystyle q i ta p displaystyle p Umovi ta metodiki vikoristannyaDlya togo shobi rivnyannya ATAv ATb displaystyle A T Av A T b bulo rozv yaznim ATA displaystyle A T A povinna buti nevirodzhenoyu abo vlasni znachennya ATA displaystyle A T A povinni zadovolnyati l1 l2 gt 0 displaystyle lambda 1 geq lambda 2 gt 0 Shobi uniknuti problemi shumu zazvichaj vimagayut shobi l2 displaystyle lambda 2 bulo ne nadto malim Takozh yaksho l1 l2 displaystyle lambda 1 lambda 2 ye zanadto velikim ce oznachaye sho tochka p displaystyle p perebuvaye na rebri j cej metod strazhdaye vid en Otzhe umova nalezhnoyi praci cogo metodu polyagaye v tomu shobi l1 displaystyle lambda 1 ta l2 displaystyle lambda 2 buli dostatno velikimi j mali podibnij poryadok velichini Ce takozh ye umovoyu j dlya viyavlyannya kutiv Ce sposterezhennya takozh pokazuye sho mozhlivo legko skazati yakij piksel pidhodit dlya metodu Lukasa Kanade perevirivshi odne zobrazhennya Odnim z osnovnih pripushen cogo metodu ye te sho ruh ye nevelikim napriklad menshe 1 pikselya mizh zobrazhennyami Yaksho ruh ye velikim i porushuye ce pripushennya odniyeyu z metodik ye spershu znizhuvati rozdilnist zobrazhennya a potim zastosovuvati metod Lukasa Kanade Shobi dobivatisya za dopomogoyu cogo metodu vidstezhuvannya ruhu vektor potoku mozhlivo zastosovuvati j pererahovuvati iterativno poki ne bude dosyagnuto pevnogo porogu blizko nulya pislya chogo mozhlivo pripustiti sho vikna ob yektu duzhe blizki za shozhistyu Roblyachi ce dlya kozhnogo nastupnogo vikna vidstezhuvannya cyu tochku mozhlivo poslidovno vidstezhuvati protyagom kilkoh zobrazhen poki yiyi abo ne bude zatuleno abo vona vijde z kadru Vtilennya ta rozshirennyaPidhid najmenshih kvadrativ neyavno pripuskaye sho pohibki v danih zobrazhennya mayut gaussiv rozpodil z nulovim serednim Yaksho ochikuyut sho vikno mistitime pevnij vidsotok vikidiv vkraj nepravilnih znachen danih sho ne sliduyut zvichajnomu gaussovomu rozpodilu pohibok mozhut vikoristovuvati statistichnij analiz shobi viyavlyati yih i znizhuvati vidpovidno yihnyu vagu Metod Lukasa Kanade sam po sobi mozhlivo vikoristovuvati lishe koli vektor potoku zobrazhennya Vx Vy displaystyle V x V y mizh dvoma kadrami ye dostatno malim shobi vikonuvalosya diferencialne rivnyannya optichnogo potoku sho chasto menshe za vidstan mizh pikselyami Koli vektor potoku mozhe perevishuvati ce obmezhennya yak v uzgodzhuvanni stereopar angl stereo matching abo reyestraciyi deformovanih dokumentiv utochniti termin angl warped document registration metod Lukasa Kanade vse zh mozhlivo zastosovuvati dlya utochnyuvannya deyakoyi gruboyi ocinki togo zh otrimanoyi inshimi zasobami napriklad shlyahom ekstrapolyuvannya vektoriv potoku obchislenih z poperednih kadriv abo vikonannyam metodu Lukasa Kanade na zmenshenih versiyah zobrazhen Naspravdi krajnij metod ye osnovoyu populyarnogo algoritmu zistavlyannya oznak Kanade Lukasa Tomazi KLT Podibnu metodiku mozhlivo zastosovuvati dlya obchislyuvannya diferencialnih afinnih deformacij vmistu zobrazhennya Div takozhOptichnij potik Metod Gorna Shunka Algoritm viyavlyannya kutiv Si Tomazi Vidstezhuvach oznak Kanade Lukasa TomaziPrimitkiB D Lucas and T Kanade 1981 An iterative image registration technique with an application to stereo vision 17 sichnya 2009 u Wayback Machine Proceedings of Imaging Understanding Workshop pages 121 130 angl Bruce D Lucas 1984 Generalized Image Matching by the Method of Differences 19 veresnya 2017 u Wayback Machine doctoral dissertation angl J Y Bouguet 2001 Pyramidal implementation of the affine lucas kanade feature tracker description of the algorithm Intel Corporation 5 5 listopada 2021 u Wayback Machine angl PosilannyaPlagin stabilizuvannya zobrazhennya dlya ImageJ na osnovi metodu Lukasa Kanade Mathworks Lucas Kanade vtilennya dlya Matlab obernenogo ta normalnogo afinnogo Lukasa Kanade vtilennya na GP optichnogo potoku na osnovi iterativnogo Lukasa Kanade KLT vtilennya vidstezhuvacha oznak Kanade Lukasa Tomazi Takeo Kanade angl Priklad movoyu C z vikoristannyam algoritmu optichnogo potoku Lukasa Kanade Priklad movoyu Python z vikoristannyam algoritmu optichnogo potoku Lukasa Kanade Priklad movoyu Python z vikoristannyam vidstezhuvacha Lukasa Kanade dlya zistavlyannya gomografiyi Shvidkij priklad v MATLAB metodu Lukasa Kanade dlya pokazuvannya optichnogo potoku Shvidkij priklad v MATLAB metodu Lukasa Kanade dlya pokazuvannya vektoriv shvidkostej ob yektiv