====== Sledování objektů ====== Sledování (video tracking) je proces určení polohy pohybujícího se objektu v čase použitím kamery. Algoritmus vytvořený pro sledování analyzuje video snímky a určuje polohu objektu v jednotlivých snímcích. Jednoduchými modely pohybu pro sledování můžou být např. * Planární objekt s modelem pohybu představující 2D transformaci obrazu (affiní transformaci nebo homografii) objektu. * Rigidní 3D objekt s modelem pohybu závisející na jeho 3D poloze a orientaci. * Objekt se zajímavými body (např. Harrisovy body) nebo oblastmi (např. MSER) v obraze, které jsou jednotlivě sledovány, to vytváří robustnost vůči zákrytům. * Nerigidní (deformovatelné) objekty aproximovány na povrchu síťovým grafem. Pohyb objektu je určený pozicí hran síťového grafu. Mezi nejznámější sledovací algoritmy patří korelace, mean-shift, Kanade-Lucas-Tomasi (KLT) tracking, Kalman tracking, particle filtering, (sekvenční) linearní prediktory atd. V našem cvičení se seznáníme se sledováním pomocí korelace a KLT trackingem. ====== 1. Sledovani pomocí korespondencí nebo korelace ====== Ve druhé úloze jsme se naučili hledat korespondence mezi obrázky. Úloha sledování je velmi podobná a hledá korespondenci objektu (výřezu, oblasti, významného bodu s okolím) známého v jednom obraze videosekvence v neznámém(ých) obraze(ch) ve vidoesekvenci následujícím(ch). Rozdílem proti hledání korespondencí je možnost předpokládat jen malé změny objektu (polohové, deformační, fotometrické...) mezi jednotlivými snímky, avšak změny v průběhu celé vidosekvence však mohou být značné. Výběr sledovaného objektu se provádí zpravidla ručně nebo automatickou detekcí, která je mimo rozsah tohoto cvičení. V úloze si vyzkoušíme volitelně jednu z metod: * sledování hledáním korespondencí mezi obrázky s využitím metod z [[../2_hledani_korespondenci/start | úlohy 2]] * sledování pomocí korelace okolí harrisových bodů Protože v obou podúlohách budeme pracovat v MATLABu s videem, stáhněte a prostudujte si funkci ''processMpvVideo(filename,method,options)'', kde ''filename'' je název souboru s videem (např. ''pokus.avi''), ''method'' je použitá metoda sledování a ''options'' je struktura s parametry pro sledovací funkci. Funkce produkuje video s vykreslenými sledovanými body do složky ''./export/'' a průběžně zobrazuje jeho náhled. Uvedený script pracuje pod většinou verzí Windows, je však možné, že butete mít problém s kodeky. Vstupní video jsme proto uvolnili v několika verzích (níže). Na Linuxu, nebo v případě nemožnosti číst ani jeden z kodeků, použijte upravenou verzi ''processmpvvideo_jpeg.m'' pro čtení videa rozsekaného na sekvenci jpeg obrázků. Obrázky si můžete buď přímo stáhnout (níže) nebo alternativně sami vytvořit: * Linux: ''mplayer -vo png video.avi'' * Windows: např. [[http://virtualdub.sourceforge.net/|VirtualDub]] Upravená verze pro zpracování obrázky rovněž produkuje jako výstup sekvenci jpeg obrázků do složky ''./export/''. Pro její složení zpět do videa, které odevzdáváte použijte: * Linux: ''mencoder mf://*.png -mf w=640:h=480:fps=15:type=png -ovc lavc -lavcopts vcodec=mpeg4:vbitrate=2400 -oac copy -o video.avi '' * Windows: např. utilitku [[http://makeavi.sourceforge.net/|MakeAvi]] Jednotlivé metody sledování pak budeme postupně dopisovat do funkcí ''xNew = track_//method//(imgPrev,imgNew,xPrev,options)'', kde ''imgPrev'' je předchozí snímek v sekvenci, ''xPrev'' jsou sledované body v předchozím snímku v sekvenci, ''imgNew'' je nový snímek v sekvenci a ''xNew'' jsou sledované body nalezené v novém snímku. Sledované body jsou reprezentovány strukturou, x.x % SLOUPCOVY vektor x-ovych souradnic x.y % SLOUPCOVY vektor y-ovych souradnic x.ID % SLOUPCOVY vektor jednoznacne indentifikace bodu (samotny index v poli nestaci, nebot body budou v prubehu sledovani ubyvat) x.data %informace specificke pro danou metodu sledovani (např. SIFT popis okoli apod.) Jak jsme již zmínili, sledovací algoritmy sledují zvolený objekt skrz celou sekvenci. Výběr objektu pro sledování provedeme v naší úloze dvoufázově - ''processMpvVideo'' volá postupně funkce ''data = processMpvInit(img,options)'', která v prvním obrázku ''img'' sekvence vybere objekt sledování, v našem případě reprezentovaný souřadnicemi výřezu data.xRect %x-ove souradnice rohu vyrezu (proti smeru hodinovych rucicek) data.yRect %y-ove souradnice rohu vyrezu (proti smeru hodinovych rucicek) Druhá funkce ''x = track_init(img,options)'' vyhledá samotné body ''x'' vhodné pro sledování. ''options'' je struktura s parametry. Na závěr zpracování každého snímku je zavolána funkce ''processMpvFrame(data,imgPrev,imgNew,xPrev,xNew,options)'', která umožňuje sledované body využít dále, např. pro hledání homografie mezi snímky apod. Nastavení struktury ''options'' a volání funkce ''processMpvVideo.m'' napište do "main" souboru ''cv08_//method//.m'' a rovněž odevzdejte. Pro usnadnění práce a lepší pochopení významu předávaných parametrů jsme připravili kostry popsaných funkcí, které navíc simulují konstantní posun náhodně zvolených sledovaných bodů. {{courses:a4m33mpv:cviceni:4_sledovani_objektu:cv08.zip|Vše v jednom}} {{courses:a4m33mpv:cviceni:4_sledovani_objektu:struktura_programu.png|}} ===== Zadání úlohy ===== Cílem úlohy bude skrýt identitu vybraného objektu ve videu. Uděláme to tak, že na prvním snímku označíme ručně obdélníkem vybraný objekt (např. zeleninu, kterou vám nechutná) a dále v celé video sekvenci ji budeme rozostřovat nezávisle na její poloze tak, jak to znáte třeba u reklamních log nebo obětí třestných činů v televizních zprávách. Lze to udělat dvěma způsoby: * sledovat přímo označený objekt * předpokládat nepohyblivost objektu ve scéně, sledovat celou scénu a rozmazávat výřez Pokud víme nebo můžeme předpokládat, že scéna v dané sekvenci je jedna a je rovinná (planární, v praxi např. letecké snímkování), můžeme požít druhou metodu, sledovat celou scénu a hledat mezi snímky homografii, podobně jako ve [[../2_hledani_korespondenci/start?#nalezeni_transformace_rovinne_sceny|druhé úloze]] nebo předmětu [[http://cmp.felk.cvut.cz/cmp/courses/TZ/2010/HomeWorks/HW-06/|A4M33TZ]]. To nám umožní trackování udělat robustnější a eliminovat vliv chybě sledovaných bodů (outlierů) na výsledek. V povinné části úlohy si vyzkoušíme sledování celé scény a hledání homografií, volitelně však můžete metodu porovnat se sledováním samotného objektu. Cílem dnešní úlohy je seznámit se a dotvořit obecné prostředí pro sledování a implemetovat jednoduchý sledovací algoritmus založený na předchozích znalostech (buď korelace nebo korespondence). Úspěšné sledování mnoha bodů ve scéně poté použít pro hledání homografií mezi obrázky a přenášení zadaného obdélníku napříč sekvencí. - Seznamte se s kostrou sledovacího frameworku a testovací sekvencí, dostupné jako: * ve formátu xvid {{courses:a4m33mpv:cviceni:4_sledovani_objektu:billa_xvid.avi|}} * sada obrázků jpeg {{courses:a4m33mpv:cviceni:4_sledovani_objektu:billa_jpg.zip|}} * ve formátu MPEG4 {{courses:a4m33mpv:cviceni:4_sledovani_objektu:billa_mpeg4.avi|}} * ve formátu WMV2 {{courses:a4m33mpv:cviceni:4_sledovani_objektu:billa_wmv2.avi|}} - Vyberte si, zda implementujete hledání pomocí korespondencí **nebo** korelace - Implementujte hledání sledovaných bodů v celém obrázku funkcí ''track_init_//method//.m'' - Implementujte sledování nalezených bodů zájmu funkcí ''track_//method//.m'' - Vyzkoušejte algoritmus na testovacím videu a vykreslete tracky - Ze sledovaných bodů spočítejte mezisnímkovou homografii obrázků - Transformujte výřez označující nežádoucí objekt - Obrázek v oblasti transformovaného výřezu rozmažte - Body 6-8 shrňte do funkce ''processmpvframe.m'' - Vygenerujte video s rozmazaným výřezem Příklad transformace výřezu - bez rozmazání {{courses:a4m33mpv:cviceni:4_sledovani_objektu:export_billa_xvid.avi|}} ===== Sledování pomocí korespondencí ===== Na základě svých znalostí a s využitím kódů ze druhé úlohy byste měli být schopni napsat funkce pro hledání korespondujících bodů mezi po sobě jdoucími obrázky sekvence a stejně tak i homografii dvou snímků ve známými korespondujícími body. Nového kódu bude skutečně málo. Vhodnou kombinací pro první pokusy se zdají být harrisovy body a dct popis. Pokud vám algoritmy ze druhé úlohy nebudou dávat dobré výsledky, mužete při hledání korespondencí zkusit přidat omezení, že vzdálenost dvou korespondujících bodů nemůže být moc velká (snímky jdou v sekvenci po sobě, scéna se nemohla fyzicky příliš změnit). Použité metody necháme na vašem uvážení a můžete pochopitelně i různě experimentovat. Minimem pro splnění této úlohy je odevzdání chodících funkcí ''track_init_correspond.m'' a ''track_correspond.m'', které dokáží udržet a transformovat výřez zkrz celkou sekvenci. ===== Sledování pomocí korelace ===== Sledování pomocí korelace hledá korespondence okolí významných bodů objektu ne na zákadě jejich zjednodušeného popisu (SIFT atd.), ale přímo pomocí porovnání těchto okolí. Měřítkem, jak moc si okolí odpovídají může být lineární korelační koeficient. * Korelační koeficient (také nazývaný normalized cross-correlation, zkratka NCC) je definován jako \frac{\sum_{\mathbf{k}}\sum_{\mathbf{l}}(T(k,l) - \overline{T})(I(x+k,y+l)-\overline{I(x,y)})} {\sqrt{\sum_{\mathbf{k}}\sum_{\mathbf{l}}(T(k,l) - \overline{T})^2} \sqrt{\sum_{\mathbf{k}}\sum_{\mathbf{l}}(I(x+k,y+l) - \overline{I(x,y)})^2}} kde T(x,y) je obrazový vzor a I(x,y) vstupní obraz. Jeho hodnota leží v intervalu ?-1,+1? (viz. [[http://cmp.felk.cvut.cz/cmp/courses/X33PVR/2008zLabs/DU/ncc.pdf|teoretický návod]]) a často se používá jako míra podobnosti okének. Pokud jste absolvovali předmět DZO, můžete výpočet korelačního koeficientu převzít z [[http://cmp.felk.cvut.cz/cmp/courses/DZO/Lab02/lab02/node8.html|úlohy 8]], zcela dostačující je však využití matlabovské funkce ''corr2''. Ncc lze počítat i efektivněji např. [[http://www.idiom.com/%7Ezilla/Papers/nvisionInterface/nip.html|takto]]. Tato pokročilá implementace bude oceněna jedním bonusovým bodem. * Výhody: NCC je invariantní vůči lineárním transformacím jasu. * Nevýhody: NCC není invariantní ke změnám měřítka obrázku, jeho rotaci a perspektivní distorzi.V některých aplikacích může být uváděna nevýhoda výpočetní náročnost. Ukazuje se, že body vhodné pro sledování jsou rohové body nalezené harrisovým detektorem. S využitím funkce ''harris(img,''\sigma_d'',''\sigma_i'',thresh)'' proto napište funkci ''x = track_init(img,options)'', která vrací harrisovy body ''x'' ve zvolené oblasti zájmu ''options.ROI''. Struktura ''options'' za tímto účelem dále obsahuje položky ''sigma_d'', ''sigma_i'' a ''thresh''. Jak jsme již uvedli, metoda je vlastně obdobou hledání korespondencí - v každém snímku nalezněte harrisovy body (''track_init'' bude tedy volána i z ''track_corr''!) a na základě porovnání jejich okolí za pomoci korelačního koeficientu se je pokuste spárovat, najít korespondence. Velikost uvažovaného okolí nastavte parametrem ''options.ps'' a zkuste přesnost sledování porovnat pro různá nastavení. S předpokladem jen malých posunů mezi následujícími snímky je zbytečné, dokonce nevhodné počítat korelace mezi všemi dvojicemi okolí. Pro každý bod v prvním obrázku stačí spočítat korelace jen s body v druhém obrázku do určité vzdálenosti, protože vzdálené body nemohou korespondovat. Tuto vzdálenost nastavíme parametrem ''options.corr_max_dist'' a její velikost je závislá na charakteru pohybu v konkrétní sekvenci. Pro naši úlohu doporučujeme hodnotu asi 30px. Pro spárování dvojic bodů s vysokým korelačním koeficientem použijte např. známého principu vzájemně nejbližších korespondencí - tedy, že výřez imgPrev z předchozího obrázku je nejbližší výřezu imgNew ze všech popisů v aktuálním obrázku jen tehdy, pokud nejbližší výřez imgNew z aktuálního obrázku je nejbližší výžezu imgPrev z předchozího ze všech předchozích. Pokud k bodu z předchozího obrázku není nalezen korespondující bod v aktuálním obrázku, je tento bod zahozen a dále se již pro sledování neuvažuje. Výsledné chování shrňte do funkce ''xNew = track_corr(imgPrev,imgNew,xPrev,options)''. ===== Hledání homografií ===== Pokud známe vzájemně si odpovídající body mezi jednotlivými obrázky (tentativní korespondence), můžeme za předpokladu jedné, víceméně planární scény najít homogafii mezi snímky. K tomu použijeme již dobře známou funkci ''[Hbest,inl]=ransac_h(u,threshold,confidence)'' ze druhé úlohy. Vektor bodů u vytvoříte za znalosti jejich ''ID'' a pomůže vám předpoklad, že ''xPrev'' jistě obsahuje všechny body ''xNew''. Nastavení předejte v ''options.rnsc_threshold'' a ''options.rnsc_confidence''. Body, které nevyšly jako inlayers z dalšího sledování vyřadíme. Lepší sledovací algoritmy mají pochopitelně průběžné doplňování nových bodů, toto však v naší úloze kvlůli omezenému času implementovat nebudeme. Při znalosti matice H můžeme transformovat (x_{n} = H_{best} x_{p}) body čtyřúhelníku vymezujícího nežádoucí objekt z jednoho snímku do druhého. Oblast danou čtyřúhelníkem potom snadno rozmažete funkcí ''gaussfilter.m'' s dostatečně velkým sigma. Využijte svých znalostí z TZ (nepřipomíná vám úloha [[http://cmp.felk.cvut.cz/cmp/courses/TZ/2010/HomeWorks/HW-06/|dokreslování pokémonů]]?) a ve skutečném obrázku rozmazávejte skutečně pouze příslušně deformovaný obdélník, tedy obecný čtyúhelník. Celé toto chování shrňte do funkce '' [dataOut xNewOut] = processMpvFrame(data,imgPrev,imgNew,xPrev,xNew,options)''. Funkce vrací strukturu ''dataOut'' obsahující dataOut.xRect %transformovane x-ove souradnice rohu vyrezu (proti smeru hodinovych rucicek) dataOut.yRect %transformovane y-ove souradnice rohu vyrezu (proti smeru hodinovych rucicek) dataOut.H %nalezená homografie a ''xNewOut'' obsahují vytříděné body v aktuálním snímku s vyřaznými outliery. Dále funkcí vykreslujte do aktuální figury obrázek s rozmazaným výřezem vč. hranice transformovaného obdélníku. ===== Co odevzdat ===== Do odevzdávacího systému nahrajte soubor ''cv08.m'' nastavením struktury ''options'' pro vaši imlementaci, dále dokončenou funkci ''processmpvframe.m'' a ( (''track_init_correspond.m'' a ''track_correspond.m'') **nebo** (''track_init.m'' a ''track_corr.m'') ). spolu se všemi kódy ze druhé úlohy, které ke své činnosti vyžadují. Odevzdejte také vygenerovaný soubor ''export_billa_xvid.avi'' s rozmazaným a rámečkem vyznačeným výřezem a rovněž vygenerovaný ''homography.mat'' s transformačními maticemi. Pro splnění úlohy je nezbytné implementovat jednu z jednoduchých metod sledování tak, aby vygenerovala dostatek bodů pro trackovaní a bez jejich doplňování jich udržela zkrz celou testovací sekvenci dostatek pro generování homografií (tedy min 4, přijatelné minimum je alespoň 20 bodů v celé scéně). Prosím **NE**odevzdávejte ''procesMpvVideo.m''. Komplikuje to automatické hodnocení úlohy. ===== Kontrola výsledků ===== Pro kontrolu správnosti odevzdaných funkcí jsme použili skript a funkci MATLABu publish. Nakopírujte si {{courses:a4m33mpv:cviceni:4_sledovani_objektu:track_test.zip|track_test.zip (20.4.)}}, rozbalte a přidejte k němu soubory, které vyžadujeme pro odevzdání. Nerozbalujte jej přímo rozbalit do adresáře, kde vyvíjíte, neboť obsahuje vlastní upravenou testovací processMpvVideo.m. Výsledky si ověrte porovnáním s [[http://cmp.felk.cvut.cz/~zichluk1/mpv/08_track/test.html|referenčním řešením]]. Jako míru kvality svého algoritmu můžete použit poslední část testu, kde sledujete body na obrázku uměle transformovaném známou homografií a ideálně byste tedy měli dostat tuto matici zpět. Ostatní porvnání jsou s hodnotami získanými KLT trackerem z volně dostupné knihovny utilit počítačového vidění [[http://sourceforge.net/projects/opencvlibrary/|Open CV]] a odchylka vašeho řešení tedy může dokonce znamenat, že váš algoritmus je lepší =) ===== Co dál ===== Sledování pomocí korespondencí má několik nevýhod * nutnost hledat objekty (harrisy...) i v následujícím snímku * přesnost je daná přesností jejich nalezení V příští úloze se ukážeme, jak hledat přímo k výřezu ve známém obraze jeho polohu (případně komplexnější transformaci) v následujícím obraze a objekty hledat jen v prvním snímku. ====== 2. Kanade-Lucas-Tomasi Tracking (KLT tracker) ====== KLT se snaží měřit similaritu pomocí kvadrátu L_2 normy, která určuje kvadratickou chybu mezi obrazovým vzorem a vstupním obrazem. Minimalizace chyby je dosahováno iterativně pomocí gradientní metody. Představme si obrazový vzor T(\mathbf{x}) , který získáme vybraním okénka v čase t , kde okénko překrývá námi sledovaný objekt. \ \mathbf{x} je sloupcový vektor souřadnic v obrazu [x,y]^T V čase t+1 se námi sledovaný objekt posune do jiné části obrazu. V čase t+1 vybereme okénko \ I(\mathbf{x}) , které je ve stejné pozici jako v čase t . Uvažujme množinu dovolených translací \ \mathbf{W}(\mathbf{x;p})=[x+p_x;y+p_y]^T. Gradientní metodou (Newton-Raphson) se okénko \ I(\mathbf{W}(\mathbf{x;p})) v každé iteraci posunuje tak, aby byla minimalizována kvadratická chyba mezi vzorem a vstupním obrazem. Optimální posunutí \mathbf{p*} okénka minimalizuje nepodobnost obrazového vzoru a vstupního obrazu (1)\;\;\sum_{\mathbf{x}}(I(\mathbf{W}(\mathbf{x;p})) - T(\mathbf{x}))^2. Předpokládejme nejlepší změnu posunutí o \ \Delta \mathbf{p} , tímto (1) přejde ve tvar (2)\;\;\sum_{\mathbf{x}}(I(\mathbf{W}(\mathbf{x;p}+\Delta \mathbf{p})) - T(\mathbf{x}))^2. Tento výraz se snažíme minimalizovat vzhledem k \ \Delta \mathbf{p} . Nelineární výraz (2) je linearizován Taylorovým rozvojem prvního řádu na tvar (3)\;\;\sum_{\mathbf{x}}(I(\mathbf{W}(\mathbf{x;p})) + \nabla I\frac{\partial \mathbf{W}}{\partial \mathbf{p}}\Delta \mathbf{p}- T(\mathbf{x}))^2, kde \nabla I = [\frac{\partial I}{\partial x},\frac{\partial I}{\partial y}] je gradient v obrazu vypočtený z \ \mathbf{W}(\mathbf{x;p}). Člen \frac{\partial \mathbf{W}}{\partial \mathbf{p}} je Jacobiho matice (symetrická matice prvních parciálních derivací) translací ve směru x a y . Výsledná Jacobiho matice se získá (4)\;\; \frac{\partial \mathbf{W}}{\partial \mathbf{p}}= \frac{ \partial[x+p_x;y+p_y]^T}{\partial [p_x,p_y]^T}= \left[\begin{array}{cc} 1 & 0\\ 0 & 1 \end{array}\right]. K nalezení minima výrazu (3) parciálně derivujeme podle \ \Delta \mathbf{p} . Poté explicitně vyjádříme posunutí (5)\;\;\Delta \mathbf{p}=H^{-1}\sum_{\mathbf{x}}[\nabla I\frac{\partial \mathbf{W}}{\partial \mathbf{p}}]^T [T(\mathbf{x})-I(\mathbf{W}(\mathbf{x;p}))] kde H je aproximace Hessovy matice používaná v Gauss-Newtonově gradientní metodě. Je třeba také poznamenat, že Gauss-Newtonova metoda řeší nelineární regresi (nelineární metodu nejmenších čtverců) a minimalizuje tak tvar (3). Povšimněme si, že aproximace Hessovy matice v této nelineární regresi je rovna autokorelační matici (Harrisově matici),tj. skalárním součinem prvních parciálních derivací. Z toho vyplývá, že nejlepší je trackovat body v malém okolí okolo Harrisových bodů. (6)\;\; H = \sum_{\mathbf{x}}[\nabla I\frac{\partial \mathbf{W}}{\partial \mathbf{p}}]^T[\nabla I\frac{\partial \mathbf{W}}{\partial \mathbf{p}}] Použitím výrazu (4) se v (5) a (6) zjednodušší \nabla I\frac{\partial \mathbf{W}}{\partial \mathbf{p}}=\nabla I . Krok (5) je vypočítáván v každé iteraci a pro další iteraci je updatováno celkové posunutí (7)\;\; \mathbf{p} \leftarrow \mathbf{p} + \Delta \mathbf{p} Konvergenci můžeme ukončit nastavením maximálního počtu iterace, nebo ukončovací podmínku ve tvaru (8)\;\; ||\Delta \mathbf{p}||\leq \epsilon. ===== Zadání úlohy ===== Cílem cvičení je implementovat algoritmus KLT sledování a hledání translace harrisových bodů a vyzkoušet jej na známé sekvenci s reklamním letákem. - Pokud nemáte hotovo z první části úlohy, implemetujte funkci ''track_init.m'' pro hledání Harrisových bodů v obrázku - Implementujte funkci ''getPatchSubpixel.m'' pro subpixelový výběr výřezu z obrázku - Implementujte KLT algoritmus do funkce ''track_klt.m'' - Vyzkoušejte algoritmus na sekveci z první části úlohy, transformujte výřez a nalezněte mezisnímkové homografie stejně jako v první části úlohy. Celý proces shrňte (s využítím poskytnutých i napsaných kódů z minula) do ''cv09.m'' ===== KLT algoritmus ===== Aby KLT algoritmus pracoval správně, je téměř nezbytné veškeré operace provádět subpixelově. Zkuste se zamyslet na tím proč a navrhnout jednoduchou situaci, kdy by nesubpixelový algoritmus selhal. Budete potřebovat funkci pro výběr výřezu z obrázku ''patch = getPatchSubpix(img,x,y,win_x,win_y)'', kde ''patch'' je výřez obrázku ''img'' kolem středu ''x,y'' velikosti ''win_x*2+1 x win_y*2+1''. Předpokládejte, že ''win_x,win_y'' jsou celá čísla, avšak ''x,y'' mohou být reálná. Při implementaci se vám bude hodit se vám bude ''interp2.m''. **Tip:** Mnohem rychlejšího výpočtu dosáhnete, pokud před použitím ''interp2.m'' obrázek oříznete celopixelově. Samotný KLT algoritmus lze sumarizovat v několika krocích: Zvol vzorek T(\mathbf{x}) v okolí Harrisova bodu \mathbf{x} v minulém obrázku ''xPrev'', nastav \mathbf{p} = [0 ; 0] a iteruj: - Vyber vzorek I ( \mathbf{W}(\mathbf{x;p})) z obrázku ''imgNew'' v okolí harrisova bodu \mathbf{x} s uvažováním aktuálního posuntí \mathbf{p} - Vypočti obrazovou chybu E = I(\mathbf{W}(\mathbf{x;p})) - T(\mathbf{x}) . - Vypočti gradienty \nabla I s translací \mathbf{W}(\mathbf{x;p}) . - Aproximuj Hessovu matici H skalárním součinem H = \sum_{\mathbf{x}}[\nabla I]^T[\nabla I]. - Odhadni translaci \Delta \mathbf{p}= H^{-1}\sum_{\mathbf{x}}[\nabla I]^T [T(\mathbf{x})-I(\mathbf{W}(\mathbf{x;p}))] - Updatuj parametry použitím \mathbf{p} \leftarrow \mathbf{p} + \Delta \mathbf{p} - Testuj konvergenci ||\Delta \mathbf{p}||\leq \epsilon. Nastav novou pozici Harrisova bodu \mathbf{x} \leftarrow \mathbf{x} + \mathbf{p} Pokud algoritmus nezkonverguje v daném počtu kroků, je nejlepší tento bod z dalšího sledování vyřadit, protže s velkou pravděpodobností jsme nalezli jiný než skutečný posun. %% Implementace - ukázka [Gx,Gy]= ... ; % výpočet gradientů g = [ Gx(:) Gy(:) ]; H = g'*g; % aproximace hessovy matice skalarním součinem Zjednodušené ilustrační schéma algoritmu na příkladu trackování auta je níže na obrázku \\ {{example.png}} \\ Implementujte funkci ''xNew = track_klt(imgPrev,imgNew,xPrev,options)'', kde parametry jsou známé z předchozí úlohy a struktura options obsahuje options.klt_window % velikost vyrezu W(x,p) ve smyslu getPatchSubpix.m options.klt_stop_count % maximalni pocet iteracnich kroku algoritmu options.klt_stop_treshold % minimalni změna epsilon^2 pro zasteveni iteraci (mocnina pro snazsi vypocet vzdalenosti) options.klt_show_steps % 0/1 zapina nebo vypina vykreslovani prubehu iteraci **Tip:** Neignorujte varování matlabu a raději než funkci ''inv()'' použijte na inverzi matice H operátor ''\'' Abyste si vy i my mohli správnou činnost iteračního algoritmu zkotrolovat, přidejte na konec každé iterace volání vykreslovací funkce if (options.klt_show_steps) showKltStep(step,T,I,E,Gx,Gy,aP); end % step - poradove cislo iterace pocitano od 0 % T - vzor, tedy vyrez z imgPrev % I - aktualne posunuty vyrez imgNew % E - aktualni obrazova chyba (I - T) % Gx,Gy - potrebne gradienty v prislusnych smerech % aP - velikost aktualniho posunu delta P ===== Co odevzdat ===== Do odevzdávacího systému nahrajte soubor ''cv09.m'' nastavením struktury ''options'' pro vaši imlementaci, dále dokončenou funkci ''track_init.m'', ''track_klt.m'' a ''getPatchSubpix.m'' spolu se všemi kódy ze druhé a minulé úlohy, které ke své činnosti vyžadují. Odevzdejte také vygenerovaný soubor ''export_billa_xvid.avi'' s rozmazaným a rámečkem vyznačeným výřezem a rovněž vygenerovaný ''homography.mat'' s transformačními maticemi. Prosím **NE**odevzdávejte ''procesMpvVideo.m'' ani ''showKltSteps.m''. Komplikuje to automatické hodnocení úlohy. ===== Kontrola výsledků ===== Pro testování i vývoj si můžete stáhnout {{courses:a4m33mpv:cviceni:4_sledovani_objektu:showkltstep.m|}} pro vizualizaci iteraci KLT. Pro kontrolu správnosti odevzdaných funkcí jsme použili skript a funkci MATLABu publish. Nakopírujte si {{courses:a4m33mpv:cviceni:4_sledovani_objektu:klt_test.zip|klt_test.zip}}, rozbalte a přidejte k němu soubory, které vyžadujeme pro odevzdání. Nerozbalujte jej přímo rozbalit do adresáře, kde vyvíjíte, neboť obsahuje vlastní upravenou testovací processMpvVideo.m a showKltSteps.m. Výsledky si ověrte porovnáním s [[http://cmp.felk.cvut.cz/~zichluk1/mpv/09_klt/test.html|referenčním řešením]]. /* ===== Pyramidová implementace KLT (bonusová úloha) ===== KLT tracker vychází z několika předpokladů (i) konstantní osvětlení mezi následujícími snímky, (ii) malý pohyb bodů zájmu, (iii) koherentní okolí bodu (sousední body leží na stejném povrchu -> mají podobný pohyb). Řešení pro trackovaní bodů s velkým pohybem tedy není zvětšování okolí bodu (tím porušujeme (ii) předpoklad) ale iterativní zjemňování odhadu pohybu na tzv. pyramidových obrázcích. Pyramidové obrázky tvoří scale space původního obrázku (level 0 pyramidy) tím, že zmenšujeme jeho rozlišení (downsampling) podle předpisu : $I^L(x, y) = 1/4 * I^{L-1}(2x, 2y) + 1/8 * (I^{L-1}(2x-1, 2y) + I^{L-1}(2x+1, 2y) + I^{L-1}(2x, 2y-1) + I^{L-1}(2x, 2y+1)) + 1/16 * (I^{L-1}(2x-1, 2y-1) + I^{L-1}(2x+1, 2y+1) + I^{L-1}(2x-1, 2y+1) + I^{L-1}(2x+1, 2y-1)) $ potom souřadnice bodu zájmu na úrovni pyramidy L je u^L$ = u/2^L$ a zjemňování odhadu mezi pyramidami se tudíž řídí předpisem $p^{L-1} = 2*(p^L + \bigtriangleup p^L)$ */ ===== Reference ===== [[http://grvc.us.es/staff/ferruz/master_vision/correspondencia/baker_2003_lucas_kanade.pdf|Lucas-Kanade 20 Years On: A Unifying Framework]] [[http://robots.stanford.edu/cs223b04/algo_tracking.pdf|Pyramidal Implementation of the Lucas Kanade Feature Tracker Description of the algorithm]]