[ hlavní stránka cvičení | detekce | generování popisu | hledání korespondencí | RANSAC | úkoly | tipy ]

33DZO – 4. Cvičení: Hledání korespondencí

Na cvičení ke geometrickým transformacím obrazu jsme zadávali korespondující body (lícovací páry) ručně, nyní se ukážeme, jak je nalézt automaticky. Úkolem bude vyzkoušet si a porovnat dvě metody pro výběr kandidátů na korespondence – Harrisův detektor a MSER detektor – a z podmnožiny kandidátů vybraných algoritmem RANSAC spočítat projektivní transformaci mezi obrazy. Předpokládáme vyřešení cvičení na geometrickou transformaci, jeho kód využijeme.

tasks in English (česká verze na této stránce dole)

Princip

Princip algoritmu pro automatické nalezení homografie (projektivní transformace) mezi dvěma obrazy je následující:

Detekce

První krok hledání korespondencí je nalezení tzv. záchytných bodů resp. oblastí (interest regions). Vyzkoušíme si dvě metody: první metoda tzv. Harrisův detektor (implementován v souborech harris.mgetMaxima.m) hledá místa v obrazu, kde se mění gradient ve dvou směrech. Použití je následující:

pts1 = getMaxima (harris (im1, scale));
pts2 = getMaxima (harris (im2, scale));

Tím získáte seznam bodů ve formě [x y velikost_odezvy]. Parametr scale určuje velikost použitých gaussovských filtrů a ovlivňuje tak velikost detailu na které detektor reaguje. Použijte hodnotu 2 nebo 3, experimentovat však mužete i s jinými. Harrisův detektor je tzv. rotačne invariantní t.j. natočení obrazu nemá vliv na detekovaná místa. V experimentu pozorujte a popište chování detektoru pri jiné transformaci obrazu.

Druhá metoda využívá sofistikovanější detektor Maximalně Stabilních Extremálních Oblastí (MSER) vyvinutý a používaný v CMP. Princip detektoru je založen na sledováni nárůstu oblastí v prahovaném obraze při zvyšování prahu intensity. Se stupajíci intensitou se vkládají do obrazu pixely, spojují se do oblastí až pri maximální intenzitě zůstane jediná oblast. Počas růstu se sledují statistiky jednotlivých oblastí (plocha a délka hranice) a hledají se rozsahy intensity, kde se poměr velikosti oblasti ku délce hranice mění nejméně. MSER detektor je implementován jako MEX modul. Použití je následující:

p.min_margin = 10;
p.min_size   = 30;
oblasti1 = extrema(im1, p, [1 2]);
oblasti2 = extrema(im2, p, [1 2]);

Vstupní obrazy im1im2 musí být černobílé nebo barevné (H×W×1, H×W×3) matice typu uint8. Tento detektor je na rozdíl od jednoduchého Harrisova detektoru tzv. afinně kovariantní – detekované regiony se mění spolu s afinní transformací obrazu. Perspektivní transformace obrazu se dá lokálně (v blízkém okolí oblasti) aproximovat pomocí afinní transformace.

Generování popisu

Jeden ze způsobů rychlého hledání korespondencí mezi záchytnými body/oblastmi je vygenerovat ke každému bodu popis a porovnat popisy bodů z obou obrazů. Pro Harrisův detektor přiřaďte nalezeným bodům popis tvořený vektorem hodnot jasu pixelů ze čtvecového okolí o velikosti hrany např. 11 pixelů (t.j. pro každý nalezený bod vytvořte vektor 1×121 prvků s hodnotami jasu v okolí). Zkuste se zamyslet a použít jinou reprezentaci než čtvercový výřez obrazu (např. kruh) a jiný popis (např. histogram). Pro jednodušší manipulaci s body a jejich popisy vytvořte pro každý bod strukturu pt funkcí podobnou této:

function body_s_popisem = describePts(obraz, detekovane_body)

body_s_popisem = [];

for i=1:pocet_detekovanych_bodu
  pt.drid = i;
  pt.x = x souradnice bodu
  pt.y = y souradnice bodu
  pt.s = pouzity scale pri detekci
  pt.desc = generujPopis(obraz, pt.x, pt.y);
  body_s_popisem = [body_s_popisem pt];
end;

V případě oblastí nalezených MSER detektorem použijeme tzv. SIFT popis, který vyvinul David Lowe. SIFT popis je robustně vypočtený histogram orientací v okolí bodu resp. na oblasti. Okolí je rozděleno na 4×4 čtverce a v každém čtverci se orientace rozdělí do osmi přihrádek (bins). Výsledkem je 128-dimenzionální vektor pro každou oblast. Generátor SIFT popisů je rovněž implementován v MEX modulu. Před generováním popisů je potřebné detekované oblasti předzpracovat, t.j. transformovat každou oblast na elipsu se středem v těžišti a osami danými druhými momenty oblasti. Funkce describeRegions.m zabezpečí tuto transformaci a výpočet popisu, její použití je následující:

  oblasti_sift1 = describeRegions(obrazek, oblasti1);

a vrátí pole struktur pt pro jednotlivé oblasti v nasledujícim tvaru:

  pt.drid = cislo_popisu
  pt.x = x souradnice teziste oblasti
  pt.y = y souradnice teziste oblasti
  pt.a11, pt.a12, pt.a21, pt.a22 = parametre elipsy
  pt.desc = sift popis oblasti

Jak vidíme, každá oblast je funkcí describeRegions "zredukována" na težište a eliptické okolí a popis. V dalším kroku využijeme polohu težiště oblasti a vygenerovaný SIFT popis.

Hledání korespondencí

Pro každý záchytný bod z prvního obrazu najděte ve druhém obrazu záchytný bod s nejbližsím popisem. Jako kritérium podobnosti popisu použijte euklidovskou vzdálenost d=norm(u-v). Při určení korespondující dvojice je možné postupovat různými způsoby (označme jeden obraz jako levý a druhý jako pravý):

Výstupem tohoto kroku je vektor [x;y;u;v] odpovídajících si bodů, tj. každý sloupec obsahuje x(i),y(i) souřadnice z levého obrazu a u(i),v(i) souřadnice z pravého obrazu.

RANSAC

Dvojice bodů získané v předchozím kroku na základě podobnosti zpravidla obsahují mnoho nekorespondujících bodů (outliers). Pro nalezení správné projektivní transformace dvou rovin potřebujeme alespoň čtyři bezchybné korespondence, které neleží na přímce. Abychom nalezli nejlepší projektivní transformaci mezi získanými dvojicemi bodů, použijeme algoritmus RANSAC. V naší aplikaci má robustní estimátor RANSAC tuto formu:

  1. Náhodně vybereme 4 korespondující páry, tzv. vzorek (sample). K vygenerování nahodné permutace můžete použít funkci sample.m.
  2. Z těchto bodů vypočteme homografii T.
  3. Všechny korespondujici body (x1, y1), (x2 y2), ..., (xn yn) prvního obrazu transformujeme pomocí T.
  4. Je-li T spočtená ze správných korespondencí, měly by transformované body (xi,yi) ležet na místech korespondujících bodů (ui,vi) v druhém obraze. Kvalitu transformace kvanfikujeme počtem bodů se vzdáleností bodu T(xi,yi) a odpovídajícího bodu (ui,vi) menší než zadaný práh (např. 1-3 pixely).
  5. Body 1-4 opakujeme iterativně, a hledáme takovou T která správně transformuje největší počet korespondencí, tj. minimalizuje kritérium definované v bodě 4. Počet iterací zvolte nejdříve 1000.

V praxi se použivá sofistikovanější kritérium pro zastavení výpočtu než je pevně zadaný počet iterací. Je založeno na odhadu pravdepodobnosti nalezení správneho vzorku (sestávající se v našem případě ze čtyř správných korespondencí). Kritérium je implementováno funkcí nsamples.m a pro zvolenou pravděpodobnost conf spočítá potřebný celkový počet iterací:

  num_samples = nsamples(pocet_inlieru, pocet_paru, velikost_vzorku, conf);

kde pocet_inlieru je průbežně odhadovaný, tj. při každém nalezení lepší transformace (dle kritéria v bodě 4) přepočítáme potřebný počet kroků funkcí nsamples.

Úkoly

  1. Za pomoci uvedených funkcí a MEX modulů implementujte dvě metody automatického hledání korespondencí v obraze:
    Metoda 1: Detekce bodů Harrisovým detektorem, popis okolím 11×11 pixelů a nalezení odpovídajících si párů metodou vzájemne nejbližsích popisů.
    Metoda 2: Detekce oblastí MSER detektorem, SIFT popis oblastí a nalezení korespondencí metodou vzájemně nejbližsích popisů nebo porovnáním poměru vzdáleností prvního a druhého nejbližšího popisu.
  2. S využítím korespondencí nalezněte algoritmem RANSAC projektivní transformaci mezi obrazy.
  3. Metody otestujte na obrazech: img1 a jeden z obrazků t1, t2, t3t4.
  4. Porovnejte použitelnost metod na dalších obrazech postupnou záměnou druhého obrazu za img2, img3, img4img5. Jaké jsou výhody a nevýhody metody založené na Harrisově detektoru? Zkuste se zamyslet a použít jinou reprezentaci okolí než čtvercový výřez obrazu (např. kruh) a jiný popis (např. histogram). Porovnejte toto zlepšení s původní metodou.

Poznámky: Do zprávy uveďte kompletní m-file. Pro každý experiment uveďte tvar matice transformace, transformovaný první obraz a rozdílový obraz – transformovaný první obraz přeložený přes druhý a odečtený.

Tipy

Následující tipy vám zjednoduší implementaci a poradí, co zkusit nad rámec cvičení a zadaného úkolu.

  1. Pro zjednodušení zahoďte všechny body do xx pixelů od okraje.
  2. Oblasti z funkce extrema si zobrazíte pomoci showRegions.m.
  3. 2D pole neighbourhood zlinearizujete do řádkového vektoru: desc = neighbourhood(:)'.
  4. Funkce horzcat převede vektory z pole struktur na matici: descs = horzcat(body_s_popisem.desc)
  5. Výpočet SIFT popisů trvá dlohou dobu (>20sec), uložte si popisy z jednotlivých obrazů do souborů a načtěte je pri experimentování s RANSACem.
  6. Napište funkci pro hledání korespondencí nezávislou na délce popisu, použijte ji pro obě metody.
  7. Body detekované Harrisovým detektorem je možné považovat za kruhové oblasti o velikosti scale a použít na ně SIFT popis. Je možné využít funkci lowesift, pokud dodržíte uvedený formát harris_bodu:
    pt.drid - identifikator (poradove cislo)
    pt.x - x suradnice
    pt.y - y suradnice
    pt.s - scale
    
    a zavoláte:
    % generate SIFT descriptions from Harris points
    p.description_type = 1;
    sift_descs = lowesift(obrazek, harris_body, p);
    
    Funkce vypočítá SIFT popisy a vrátí je v podobné struktuře s naplněným sift_descs.desc.
  8. Můžete si zkusit webovou aplikaci pracující na podobném principu a porovnat výsledky.

[ hlavní stránka cvičení | detekce | generování popisu | hledání korespondencí | RANSAC | úkoly | tipy ]