33PVR – Počítačové vidění a virtuální realita – DU-02
Domácí úloha č.2: Automatizovaný výpočet homografie
Zimní semestr 2009/2010.
Zadání
Vstup: Videosekvence scény obsahující významnou rovinnou oblast.
Úkol:
- Vyberte si náhodně dva po sobě jdoucí snímky. Zvolte si rovinný objekt ve
scéně a ohraničte jej v prvním snímku ručně zadaným čtyřúhelníkem. Spočítejte
homografii, která svazuje souřadnice bodů uvnitř takto vybrané oblasti
se souřadnicemi jim korespondujících bodů ve druhém snímku.
- Transformujte pomocí nalezené homografie první obrázek do souřadného
systému druhého a druhý do souřadného systému prvního. Odečtěte obrázky od
sebe a zhodnoťte, do jaké míry se kryjí. Srovnejte kvalitu překryvu s vašimi
výsledky v předchozí úloze, kde jste vybírali korespondence ručně.
Uzávěrka pro odevzdání
Zprávu spolu se zdrojovým kódem nahrajte v odpovídajícím formátu, viz. zde,
do odevzdávacího systému do 11.11. 23:59.
Podrobnosti
Pracujeme vždy s dvojicí snímků (obrazů), které označíme I1 a I2. V obraze
I1 navíc vyznačíme rovinnou oblast Z. Máme najít množinu korespondujících dvojic
bodů takovou, že první bod ve dvojici vždy pochází z oblasti Z, druhý je z
druhého obrazu a zároveň oba odpovídají stejnému bodu v zobrazené scéně. Tyto
korespondující body najdeme na základě toho, že musí splňovat tři podmínky:
- První bod leží v oblasti Z.
- Blízké okolí korespondujících bodů musí být podobné.
- Celá množina korespondujících dvojic bodů musí splňovat jistou
geometrickou podmínku. V našem případě, kdy oblast Z zachycuje planární
oblast ve scéně, je touto podmínkou existence homografie, která váže body z
oblasti Z v prvním obraze s body ve druhém obraze.
Pro nalezení korespondence a homografie mezi obrazy I1 a I2 použijte
následující postup:
- Implementujte Harrisův detektor rohů podle přednášek. Vyzkoušejte si, jak detekce
závisí na parametrech detektoru (měřítko sigma, velikost okénka). Body vykreslete.
- Implementovaným detektorem detekujte v obrazech I1 a I2 rohy. Označme P1
množinu detekovaných bodů ležících uvnitř oblasti Z v obraze I1. Označme P2
množinu bodů detekovaných v obraze I2. Dále označme N1 resp. N2 velikost
množiny P1 resp. P2.
- Kolem každého bodu uvažujte okénko WxW pixelů (ve středu
okénka je Harrisův bod, s velikostí okénka experimentujte). Spočítejte
lineární korelační koeficient r(p1,p2) mezi okénky kolem všech bodů p1 z P1
a p2 z P2. Argumenty lineárního korelačního koeficientu budou dva vektory o
délce WxW obsahující jasy z obou okének, srovnané např. po sloupcích.
Lineární korelační koeficient (také nazývaný normalized
cross-correlation, zkratka NCC) je invariantní vůči lineárním transformacím
jasu, proto se často používá jako míra podobnosti okének. Jeho
hodnota leží v intervalu <-1, +1 > a vypočítat ho lze např. podle
návodu zde.
Hodnotu koeficientu r(p1,p2) pro všechny možné kobminace bodů p1 a p2 je
vhodné reprezentovat maticí R o rozměru N1xN2, které se někdy říká korelační
tabulka. Čím větší je hodnota R(i,j), tím pravděpodobnější je, že body pi z
P1 a pj z P2 korespondují.
Protože kamera se pohybuje omezenou rychlostí, nebudou od sebe
korespondující body v po sobě jdoucích obrázcích příliš vzdálené. Není
proto nutné počítat všech N1xN2 korelačních koeficientů a u bodů, jejichž
vzdálenost d(pi,pj) přesahuje stanovenou mez Dmax, můžeme položit hodnotu
R(i,j) rovnou hodnotě -1.
Najděte s pomocí matice R dvojice bodů (p1,p2), které splňují podmínku
symetrie:
- Korelační koeficient r(p1,p2) je největší mezi koeficienty r(p1,pj)
pro všechny pj z P2.
- Korelační koeficient r(p1,p2) je největší mezi koeficienty r(pi,p2)
pro všechny pi z P1.
Tyto dvojice mají velkou pravděpodobnost, že opravdu korespondují. Budeme
je nazývat kandidáty na korespondenci. Body opět vykreslete (jinou barvou).
- Pomocí metody RANSAC (Random Sampling Concensus, viz. přednáška) vyberte z množiny kandidátů
na korespondenci maximální podmnožinu dvojice bodů, jenž jsou s dostatečnou
přesností svázány homografií. Tj. hledáme množinu A dvojic bodů a zároveň
homografii H tak, že pro každé (p1,p2) z A platí s nějakou přesností, že
lambda*x2(p2)=H*x1(p1). Zde jsme x1(p1) rexp. x2(p2) označili homogenní
souřadnice bodu p1 v prvním resp. p2 v druhém obraze.
Uvědomte si, že výstupem RANSACu nejsou jen homografie. Neméně důležité
je, že RANSAC rozdělí množinu kandidátů na "správné" (inliers) a "špatné"
(outliers). Inliers vykreslete (zase jinou barvou).
Homografii můžete po skončení algoritmu RANSAC ješte zpřesnit, tak že ji
přepočítáte ze všech bodů, které byly inliers nejlepší homografie H nalezené
RANSACem.
Poznámka: Přesnost homografie bude také ovlivňovat konkrétni
implementace, kterou zvolíte pro její vypocet. Z minulého domáciho úkolu
víme, jak počítat homografii; udělali jsme to sestavenim matice soustavy a
její vyřešení pomocí null/SVD. Nyni si vyzkoušejte vhodnějsi postup:
- Přeškálujte souřadnice bodů v obrazcích tak, aby extremální hodnoty v
každé souřadnici nebyly v absolutní hodnotě větší než 1. Tj. souřadnice
bodu v obrázku se z rozmezí [Xmin..Xmax, Ymin..Ymax] namapuji do rozmezí [-1..1,
-1..1].
- Sestavte matici soustavy tak jako obvykle.
- Spočitejte SVD. Takový postup zajistí lepší
numerickou stabilitu výsledku.
Poznámky
- Obrázky je možno před zpracováním převést na černobílé.
- Doporučujeme hledání Harrisových bodů implementovat jako samostatnou
funkci, která dostane na vstupu obrázek (ev. parametery) a vrátí nadetekované body.
- Doporučujeme hledání kandidátů na korespondence implementovat jako samostatnou
funkci, která na vstupu dostane obrázky a nadetekované Harrisovy body a na výstupu
vrátí kandidáty na korespondence.
- Doporučujeme hledání homografie implementovat jako samostatnou funkci,
která jako vstup bere I1, I2, P1, P2 a Dmax a výstupem je nalezená homografie +
seznam inlieru. Funkce se bude hodit v následující úloze.
Časový harmonogram
Tato úloha je složitější než DU-01. Kdo si nechá úlohu na poslední chvíli,
nemá šanci to stihnout (čímž nesplní podmínky pro absolvování předmětu). Proto
doporučujeme osobní průběžnou kontrolu implementovaných výsledků v
následujících třech cvičeních takto:
- Na konci 5. cvičení (22.10.) či krátce po něm byste měli mít
implementovaný Harrisův detektor rohů.
- Na konci 6. cvičení (29.10.) byste měli mít implementovaný výpočet
korelační tabulky.
- Na konci 7. cvičení (5.11.) byste měli mít vyřešené zbývající úkoly (RANSAC).
Tím budete mít dostatek času na sepsání zprávy. Kdo bude rychlejší, tím
lépe pro něj.
Poslední změna 5. 10. 2009