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:

  1. 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.
  2. 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:

  1. První bod leží v oblasti Z.
  2. Blízké okolí korespondujících bodů musí být podobné.
  3. 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:

  1. 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.
  2. 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.
  3. 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:

    1. Korelační koeficient r(p1,p2) je největší mezi koeficienty r(p1,pj) pro všechny pj z P2.
    2. 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).

  4. 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:

    1. 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].
    2. Sestavte matici soustavy tak jako obvykle.
    3. Spočitejte SVD. Takový postup zajistí lepší numerickou stabilitu výsledku.

Poznámky

  1. Obrázky je možno před zpracováním převést na černobílé.

  2. Doporučujeme hledání Harrisových bodů implementovat jako samostatnou funkci, která dostane na vstupu obrázek (ev. parametery) a vrátí nadetekované body.
  3. 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.
  4. 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:

  1. Na konci 5. cvičení (22.10.) či krátce po něm byste měli mít implementovaný Harrisův detektor rohů.
  2. Na konci 6. cvičení (29.10.) byste měli mít implementovaný výpočet korelační tabulky.
  3. 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