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 algoritmu pro automatické nalezení homografie (projektivní transformace) mezi dvěma obrazy je následující:
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.m a getMaxima.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 im1 a im2 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í 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:
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
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.
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.
a zavoláte:pt.drid - identifikator (poradove cislo) pt.x - x suradnice pt.y - y suradnice pt.s - scale
Funkce vypočítá SIFT popisy a vrátí je v podobné struktuře s naplněným sift_descs.desc.% generate SIFT descriptions from Harris points p.description_type = 1; sift_descs = lowesift(obrazek, harris_body, p);