Search
Hledání korespondencí je jedným ze základních problémů počítačového vidění. Cílem je najít odpovídajíci si části scény ve dvou nebo více obrazcích. Hledání korespondence pro každý pixel je výpočetně náročné. Metoda založená na korespondencích lokálních příznaků proto v každém obrazu nejdřív nalezne tzv. detektorem množina 'záchytných' bodů resp. regionů, ze kterých budou vybrány korespondující (lícovací) páry. Je třeba najít v různých obrazech takové odpovídající si body, které lze opakovaně identifikovat nehledě na geometrické a fotometrické transformace obrazu. K pozici každého záchytného bodu se přiřadí zakódovaný popis jeho okolních pixelů. Může to být např. vektor jasů okolních pixelů, histogram jasů, histogram gradientů nebo jiný invariantní popis. Způsob zakódování ovlivňuje dvě věci: invarianci vůči transformacím a diskriminativitu popisu. Výslední popis je takzvaný lokální příznak, vektor zachycujíci charakteristiky obrazové funkce malého, dobře lokalizovaného okolí záchytného bodu. Pri vlastním hledání korespondencí metodou lokálních příznaků se každý záchytný bod z prvního obrazu nalezneme bod z druhého obrazu s nejbližším popisem. Vlivem šumu, zákrytů a nepřesností modelů geometrické a fotometrické transformace jsou některé nalezené korespondence špatné, t.j. nespojují tytéž body scény. Potřebujeme tedy robustní algoritmus, jenž na základe známeho modelu transformace scény vybere největší podmnožinu korespondencí, v níž se všechny korespondence transformují konzistentne s modelem. Jedním z takových algoritmů je RANSAC (RANdom SAmpling Concensus), který si představíme v závěrečné časti úlohy.
První krok hledání korespondencí je nalezení tzv. záchytných bodů resp. oblastí (interest regions). Vyzkoušíme si napsat dva často používané detektory záchytních bodů, detektor maxim Hessiánu a Harrisův detektor.
Úkolem detektoru je opakovaně najít v obraze body nebo oblasti, jež jsou dobře lokalizovány a v jejichž okolí je dostatek informace aby bylo možné najít pokud možno jednoznačný popis jeho okolí. Detektor lokálních extrémů Hessiánu – determinantu Hessovy matice (matice druhých derivací)
<latex>\mathbf{H} = \left[\begin{array}{cc} D_{xx}(x,y;\sigma) & D_{xy}(x,y;\sigma) D_{xy}(x,y;\sigma) & D_{yy}(x,y;\sigma) \end{array}\right],</latex>
hledá centra tzv. blobů, lokálních extrémů intenzitní funkce, které jsou dobře lokalizovány v okolí daném variancí <latex>\sigma^2 </latex>. Body zájmu jsou pak ty lokální maxima, jejichž hodnota je nad určitou hranicí <latex>t</latex> danou úrovní šumu v obrázku
response=hessian_response(img,sigma)
Pro nalezení extrémů Hessiánu budeme potřebovat funkci, která zjistí zda je bod lokální extrém, toto zjistíme srovnáním hodnoty bodu s jeho osmi okolím.
maximg=nonmaxsup2d(response,thresh)
[x,y]=hessian(img,sigma,thresh)
[y,x]=find(maximg)
Harrisův detektor hledá body v nichž se gradient mění v dvou ortogonálních směrech, proto se někdy označuje jak detektor rohových bodů (corner points). Využíva vlastností tzv. autokorelační matice gradientu.
<latex> \mathbf{C}(x,y;\sigma_d,\sigma_i)=G(x,y;\sigma_i)*\left[\begin{array}{cc} D^2_{x}(x,y;\sigma_d) & D_x D_y(x,y;\sigma_d) D_x D_y(x,y;\sigma_d) & D^2_y(x,y;\sigma_d) \end{array}\right]</latex>
kde * je operátor konvoluce. Prostřednictvím okenní funkce <latex>G(x,y;\sigma_i)</latex> se akumulují matice vnějších součinů gradientu v <latex>\sigma_i</latex> okolí bodu. Matice vnějšího součin vektoru má vlastní vektor ve směru vektoru a vlastní číslo odpovídajíci druhé mocnině jeho velikosti. Akumulací vnějších součinů pomocí konvoluce a nalezením vlastních čísel autokorelační matice tedy můžeme určit dva dominantní směry gradientu v okolí bodu a jejich velikosti. Tohto pozorování si všimli Harris a Stephens a navrhli elegatní funkci
<latex> R(x,y) = \mathrm{det}(\mathbf{C})-\alpha\mathrm{trace}^2(\mathbf{C}). </latex>
Ta obchází výpočet vlastních čísel <latex>\lambda_1,\lambda_2</latex> matice <latex>\mathbf{C}</latex> využitím ekvivalencí
<latex> \begin{array}{rcl} \mathrm{det}(\mathbf{C})\!&=&\!\lambda_1\lambda_2 \mathrm{trace}(\mathbf{C})\!&=&\!\lambda_1 + \lambda_2 \end{array} </latex>
na zjištění vlastností jejich poměru.
Obrázek ukazuje průběh funkce <latex>R(x,y)</latex> pro <latex>\alpha=0.04</latex>, bílé usečky označují izokontury s hodnotami 0, 0.02, 0.04, 0.06, …, 0.18. Když tedy uvažujeme hodnoty vyšší než práh, požadujeme aby nižší z obou vlastních čísel (velikost menšího z dvou nejčetnejších gradientů) bylo dostatečně vysoké, a zároveň čím je nižší menší vlastní číslo tím je vyžadována vyšší hodnota vyššího vlastního čísla. V případe, že jsou jejich hodnoty podobné mohou mít obě vlastní čísla nižší hodnotu.
response=harris_response(img,
,
)
[x,y]=harris(img,
,thresh)
Základní verze Harris a Hessián detektoru potřebují parametr, měrítko (rozptyl) na němž se pozorují gradienty v obraze a hledají se “bloby”. Ukázalo se, že blobům v obraze je možné toto měŕítko určit automaticky. Na jeho nalezení je potřebné vybudovat tzv. prostor měrítek, tří dimenzionální prostor, v němž dvě dimenze tvoří obrázek (x,y souřadnice) a třetí rozměr měrítko. Varianty obrazu se zvyšujícim se měrítkem získame za pomocí filtrování obrazu, potlačením detailů se simuluje situace když by sme se na scénu dívali z větší vzdálenosti. Se zvyšujícím se potlačením detailů se ale snižuje rozptyl intenzit, pro výběr charakteristického měrítka je potřebné aby gradienty mezi dvěma měřítky byli porovnatelné. Zavedl se proto pojem normalizované derivace vzhledem ke “vzdálenosti” mezi pixely (získáme “bezrozměrný” gradient):
<latex> \frac{\partial f}{\partial \xi} = \frac{\partial f}{\partial (x/\sigma)} = \sigma \frac{\partial f}{\partial x}\mbox{,}\quad N_x(x,y;\sigma) = \sigma D_x(x,y;\sigma)\mbox{,}</latex>
Lindeberg ve své práci ukázal, že na takto normalizovaných derivacích je možné spočítat odezvu differenciálních operátorů Laplaciánu <latex>\mathrm{trace}(\mathbf{H}_{norm}(x,y,\sigma_i))=N_{xx}(x,y;\sigma_i)+N_{yy}(x,y;\sigma_i)</latex> a Hessiánu <latex>\mathrm{det}(\mathbf{H}_{norm}(x,y,\sigma_i)) = N_{xx}(x,y;\sigma_i) N_{yy}(x,y;\sigma_i) - N_{xy}^2(x,y;\sigma_i)</latex> a použít je na automatické určení charakteristického měrítka ideálního blobu. Vyhledáním lokálních maxim hodnot těchto operátorů v x,y a <latex>\sigma</latex> dostaneme pozici “blobů” spolu s jejich měřítkem.
Obrázek Gaussiánů se směrodatnými odchylkami=8,16,24 a 32. Odezva det(Hnorm) a trace(Hnorm) v středech Gaussiánů, všimněte si posun extrému proporcionální k velikosti blobu.
[ss,sigma]=scalespace(img,levels,step)
ss(:,:,1)
ss(:,:,i)
maximg=nonmaxsup3d(response, threshold)
[hes,sigma]=sshessian_response(img)
scalespace
nonmaxsup3d
sshessian_response
[x,y,s]=sshessian(img, thresh)
% ziskej matici maxim maximg=nonmaxsup3d(response, thresh); % najdi pozice [y x u]=ind2sub(size(nms), find(nms)); % preved z MATLAB indexu do souradnic x=x-1; y=y-1; % preved u na meritko s ...
Funkce vyzkoušejte napr. na obrázku
pro vizualizaci nalezených bodů můžete použít funkci showpts.m:
% nacti obrazek img=imread('sunflowers.png'); % najdi maxima Hessianu v scale space, pouzij threshold 0.02 [x,y,s]=sshessian(im2double(rgb2gray(img)), 0.02); % zobraz vysledek imshow(img); p.linewidth=2; p.color='red'; showpts([x;y;s], p);
Měli by jste dostat podobný výstup:
(velitelný studíjní materiál, pro aktívní studenty)
Rozšíření similaritně kovariatních bodů – detekovaných maxim Hessiánu v prostoru měřítek můžeme rozšířit na affině kovariantní body až na neznámou rotaci. Základom je tzv. Baumbergova iterace, jejíž ideou je sledovat distribuci gradientů v okolí detekovaného bodu. Předpokládáme-li, že existuje transformace, která “narovná” ve výřezu okolí bodu intenzity tak, aby rozložení gradientů bylo tzv. izotropní (s gradienty rovnoměrně distribuované do všech směrů), je možné ji najít pomocí matice druhých momentů gradientu, nebo-li nám už známé autokorelační matice gradientů.
Jak sme si již řekli dřív, tato matice reflektuje lokální distribuci gradientů, dá se ukázat, že když najdeme transformaci <latex>\mathbf{\mu} = \mathbf{C}^{-1/2}</latex>, která promítne souřadný systém daný vlastními vektory a vlastními čísly matice <latex>\mathbf{C}</latex> na kanonický, distribuce gradientů ve výřezu transformovaném matici <latex>\mathbf{\mu}</latex> bude více izotropní. Protože jsme ovšem použili kruhovou okenní funkci, stane se, že některé gradienty v okolí započítáme se špatnou vahou, případně vůbec. Proto je nutné tento postup opakovat kým vlastní čísla matice <latex>\mathbf{C}_i</latex> z i-té iterace okolí bodu nebude blízká identitě (násobku identity). To zjistíme porovnáním poměru vlastních čísel matice <latex>\mathbf{C}_i</latex>. Výslednou matici lokální afinní deformace získame jako celkovou deformaci okolí potřebnou na jeho “narovnání” na izotropní:
<latex>N = \prod_i \mu_i</latex>
Tato transformace je (po přidání translace a měrítka) ze souřadnic obrázku do kanonického souřadného systému. V praxi nás většinou zajímá inverzní transformace <latex>\mathbf{A}=\mathbf{N}^{-1}</latex>.
Na trochu jiném principu je založen detektor Maximalně Stabilních Extremálních Oblastí (MSER). Pri detekci se sleduje nárůstu oblastí v prahovaném obraze při zvyšování prahu intenzity. Se stupajíci intenzitou 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 intenzity, 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; mser = extrema(img, p, [1 2]);
regs=[mser{1}{2,:} mser{2}{2,:}]; x=[regs.cx]; y=[regs.cy]; a11=sqrt([regs.sxx]); a12=zeros(size(a11)); a21=[regs.sxy]./a11; a22=sqrt([regs.syy] - a21.*a21); imshow(img); showpts([x;y;a11;a12;a21;a22]);
Aby jste měli vaše detektory na čem zkoušet, každý nafoťte tři objekty z pěti různých pohledů se stupňující se složitostí. Dva obrázky věnujte jednoduché rotaci bez a se změnou měřítka. Ostatní odfoťte z jiných úhlů pohledu. Obrázky v rozlišení s delší hranou obrázku 1024px pomenujte obj(0-2)_view(0-4), zabalte do .zip archivu a odevzdejte do odevzdávacího systému do úlohy (02_data). Skuste na některých párech pustit napsané detektory, v případě potřeby si obrázky zmenšete na poloviční.
Očekávame, že odevzdáte funkce hessian_response.m, hessian.m, harris_response.m, harris.m, nonmaxsup2d.m, scalespace.m, nonmaxsup3d.m, sshessian_response.m a sshessian.m spolu se všemi potřebnými funkcemi. Nezapomeňte na dátovou sadu.
Pro kontrolu výsledků vašich funkcií jsme použili skript a funkci MATLABu publish. Nakopírujte detect_test.zip, rozbalte ho do cesty MATLABu (nebo adresáře s vašimi funkcemi) a spusťte. Výsledky si ověrte porovnáním s referenčním řešením.
Pro získaní lokálního popisu invariantního k geometrickým a fotometrickým transformacím scény, potřebujeme okolí získaných záchytných bodů znormalizovat tak aby jsme odstranili efekt geometrické resp. fotometrické transformace intenzity. Po odstranění těchto deformací pak můžeme na normalizovaném okolí počítat popis, jenž je nezávislý na těchto deformacích.
Jak sme již viděli, úkolem detektoru je opakovatelně zjistit tvar okolí záchytných bodů, tak aby nalezené záchytné body byly kovariatní (měnící se stejně) s jistou tŕídou transformací scény a osvětlení. Např. základní verze Harris a Hessian detektoru hledá body které jsou translačně kovariatní (když posuneme obrázek, posunou se stejně). Hessian v prostoru měřítek nebo DoG detektor přidáva informaci o “velikosti” oblasti a tudíž body jsou similaritně kovariatní až na neznámou orientaci (detekované body jí nemají definovanou). Afinně kovariatní detektory ako MSER, Hessian-Affine alebo Harris-Affine pri využití informace o orientaci najdou oblasti jenž se mění spolu s afinní transformaci obrazu. V následující části si ukážeme jak “uchopit” geometrickou informaci o okolí bodu, a využít ji k jeho normalizaci. V závislosti na množství informace (kovarianci záchytních bodů), která je o okolí záchytného bodu k dispozici z detektoru, může být výslední popis pozičně, similaritně, afinně nebo perspektivně invariantní.
Geometrickou normalizací nazýváme process geometrické transformace okolí bodu v obrázku do kanonického souřadného systému. Informace o geometrické transformaci okolí budeme uchovávat ve formě tzv. rámce – projekce kanonického souřadného systému do okolí záchytného bodu nebo oblasti v obrázku. Rámec reprezentujeme 3 x 3 transformací A, podobně jako na prvním cvičení. Transformaci A využijeme k získání výřezu, malého okolí záchytného bodu v kanonickém souřadném systému. Všechny další měrení na tomhle typicky čtvercovém výrězu původního obrázku jsou teď již invariantní k odpovídající geometrické transformaci scény.
Pro konstrukci transformace A můžeme použít geometrické informace o pozici a tvaru okolí bodu následovně:
s & 0 & x 0 & s & y 0 & 0 & 1 \end{array}\right]}_{A_{norm}} \left[\begin{array}{ccc} cos(\alpha) & sin(\alpha) & 0 -sin(\alpha)& cos(\alpha) & 0 0 & 0 & 1 \end{array}\right] </latex>
\left[\begin{array}{ccc} \sigma & 0 & x 0 & \sigma & y 0 & 0 & 1 \end{array}\right]}_{A_{norm}} \left[\begin{array}{ccc} cos(\alpha) & sin(\alpha) & 0 -sin(\alpha)& cos(\alpha) & 0 0 & 0 & 1 \end{array}\right] </latex>
\left[\begin{array}{ccc} a_{11} & a_{12} & x a_{21} & a_{22} & y 0 & 0 & 1 \end{array}\right]}_{A_{norm}} \left[\begin{array}{ccc} cos(\alpha) & sin(\alpha) & 0 -sin(\alpha)& cos(\alpha) & 0 0 & 0 & 1 \end{array}\right] </latex>
Mnohé detektory (všechy z předchozího cvičení) vrácí body (rámce), jenž jsou určeny similaritně nebo afinně kovariatné až na neznámou rotaci (úhel <latex>\alpha</latex>). Napr. pozice a měrítko bodu nám dají similaritně kovariatní bod, až na neznámou rotaci. Podobně matice druhých momentů a těžiště nám dají pět omezení na afinní transformaci a zbýva nám určit rotaci okolí bodu. Pro získaní plně similaritně nebo afinně kovariatního bodu potřebujeme z částečně geometricky normalizovaného okolí (pri normalizaci jsme použili nějakou hodnotu úhlu <latex>\alpha</latex>) určit orientaci bodu.
Normalizace s určením orientace musí probíhat většinou ve dvou krocích. Nejdříve se zhotoví výřez obrázku, jenž je nezávislý na translaci, velikosti případně častečné afinní transformaci (rotační matice z příkladu výše se předpokládá jednotková). Označme tuto matici <latex>A_{norm}</latex>. Na výřezu znormalizovaném maticí <latex>A_{norm}</latex> se pak se určí orientace dominantního gradientu (reprezentována rotační maticí) a složí se s <latex>A_{norm}</latex> do celkové transformace A. Tato se pak použije ke konečné transformaci bodu.
Pro určení dominatní orientace se na výřeze, částečne znormalizovaném transformací <latex>A_{norm}</latex>, se v každém bodě odhadne velikost a orientace gradientu a spočítá se histogram gradientů. Protože předpokládáme náhodné natočení výřezu je potřeba gradienty akumulovat jenom za kruhové okolí napr. pomocí váhování okenní funkcí, nebo podmínkou (x-stredx)^2+(y-stredy)^2 < (ps/2)^2, kde ps je velikost hrany výřezu. Jinak by orientaci ovlyvnil obsah “rohů” výřezu, jenž ale může být při jiném natočení jiný. Gradienty jsou váhovány jejich velikosti, větší gradient znamená vyšší příspevěk do odpovídajícího binu histogramu. Pro zvýšení robustnosti se hlas může rozdělit lineární interpolací do sousedních binů. Na závěr se histogram vyfiltruje 1D Gaussiánem a najde lokální maximum. Pro přesnou lokalizaci je možné do okolí maxima fitnout parabolu a najít orientaci s presností větší než 360/počet binů stupňů.
angle=dom_orientation(img)
atan2(y,x)
Teď již můžeme napsat funkce pro geometrickou normalizaci okolí bodů s využitím dominantní orientace. Napište funkce pro výpočet reprezentace bodů pomocí transformačních matic <latex>A</latex> a normalizovaných výřezů:
pts=transnorm(img,x,y,s,opt)
pts=simnorm(img,x,y,s,opt)
pts=affnorm(img,x,y,a11,a12,a21,a22,opt)
Vstupním parametrem opt bude struktura s parametry normalizace:
opt.ps - velikost výřezu opt.ext - velikost okolí bodu v kanonickém souřadném systému
Výstupem funkcí bude jednorozměrné pole struktur pts, které bude pro každý bod obsahovat: souřadnice x,y, 2×2 část transformační matice <latex>A</latex> v prvcích a11,a12,a21,a22, a normalizovaný výřez obrázku (ps x ps matice typu double) v prvku patch. Pro implementaci funkcí použijte jejich hierarchii, jednodušší funkce může vhodným voláním použít složitější funkci. Výslední výřez i výřez pro určení dominantní orientace vám spočítá funkce affinetr. Pseudokód normalizace s zjištěním orientace:
x
y
a11
a12
a21
a22
patch
affinetr
% ... pro všechny body (id) ... A_norm = zostav_matici_A_bez_rotace(x(id),y(id),...); % urceni orientace tmp = affinetr(img, A_norm, opt.ps, opt.ext); angle = dom_orientation(tmp); % finalni A, dame dominantni orientaci na 0 stupnu R = rotace_2x2(-angle); A(1:2,1:2) = A_norm(1:2,1:2)*R; % zostav vystup pts(id).x=x(id); pts(id).y=y(id); pts(id).a11=A(1,1); ... pts(id).patch=affinetr(img, A, opt.ps, opt.ext);
V této úloze se kvůli názornosti používa při normalizaci jenom orientace odpovídající nejsilnějšímu gradientu.
Fotometrická normalizace ma za cíl potlačit změny scény způsobeny změnou osvetlení. Nejjednodušší normalizace je roztáhnutí jasového kanálu tak aby se využil celý rozsah intenzit. Další možnost je roztáhnutí jasového kanálu tak aby po transformaci střední hodnota odpovídala půlce intenzitního rozsahu a směrodatní odchylka intenzit <latex>\sigma</latex> jeho rozsahu (případně <latex>2\times\sigma</latex>). V případě, že chceme využít všechny tři barevné kanály, normalizujeme každou složku zvlášť.
ptsn=photonorm(pts)
mean
std
Na geometricky a fotometricky invariantním výrězu obrázku z předchozího kroku můžeme spočítat libovolný nízkodimenzionální popis. Je zřejmé, že proces normalizace není úplně bezchybný a proto je žádoucí aby výpočet popisu nebyl príliš citlivý k zbývajícím neprěsnostem. Nejjednodušší popis je samotný výřez obrazku, medzi jeho nevýhody patří hlavně vysoká dimenze popisu, citlivost k malým posunom a lokálním změnám intenzity. Vyzkoušíme si proto kromě tohto popisu lepší varianty.
dct=dctdesc(img,num_coeffs)
dxdy=ghistodesc(img,num_bins)
sift=siftdesc(img)
Očekávame, že odevzdáte funkce transnorm.m, simnorm.m, affnorm.m, photonorm.m, dom_orientation.m a dctdesc.m spolu se všemi potřebnými funkcemi. Nezapomeňte na dátovou sadu. Volitelně můžete za dva body navíc odevzdat funkci siftdesc.m.
Pro kontrolu výsledků vašich funkcií jsme použili skript a funkci MATLABu publish. Nakopírujte desc_test.zip, rozbalte ho do cesty MATLABu (nebo adresáře s vašimi funkcemi) a spusťte. Výsledky si ověrte porovnáním s referenčním řešením. Test i řešení ještě doplním (o chybějící funkce).
Dřív, než začneme, budeme potřebovat funkci pts=detect_and_describe(img,detpar,descpar), jenž zapojí do výpočtu všechny funkce z předchozích cvičení a v obrázku img zdetekuje, geometricky a fotometricky znormalizuje a popíše záchytné body. Parametry detektoru se jí předají ve struktuře detpar:
pts=detect_and_describe(img,detpar,descpar)
detpar.type='hessian'; detpar.sigma % sigma pro vypocet derivaci detpar.threshold % prah
detpar.type='harris'; detpar.sigmad % derivacni sigma detpar.sigmai % integracni sigma detpar.threshold % prah
detpar.type='sshessian'; detpar.threshold % prah
detpar.type='mser'; detpar.min_margin % pozadovana stabilita detpar.min_size % velikost nejmensi oblasti v pixlech detpar.max_area % procento/100 plochy nejvetsi detekovane oblasti (v rozsahu 0 az 1).
Parametry normalizace a typu popisu dostane ve struktuře descpar
descpar.type % typ popisu ('dct' nebo 'ghisto' nebo 'sift') descpar.ps % velikost výřezu descpar.ext % velikost okolí bodu v kanonickém souřadném systému.
descpar.num_coeffs % pocet koeficientu v zig-zag poradi
descpar.num_bins % pocet binu na jedné osi histogramu.
Na výstupu vrátí body ve struktuře pts ve formátu funkce affnorm (pole x,y,a11,a12,a21,a22,patch) a photonorm (mean, std) z minulého cvičení, každému bodu <latex>i</latex> doplní pole pts(i).desc se spočteným popisem jako sloupcovým vektorem. Funkci si můžete stáhnout zde.
affnorm
photonorm
pts(i).desc
Po detekci a generování popisu, jenž probíhali na každém obrázku scény nezávisle, prikročíme k vlastnímu hledání korespondencí. První fází je nalezení tzv. tentativních korespondencí (někdy nazývaných i “matchů”). Tentativní korespondence je pár – dvojice popisů, jenž jsou si v nějaké vzdálenosti podobné. Nejjednodušší metodou pro nalezení korespondencí je najít vzdálenosti mezi všemi páry popisů. Tuto tabulku nazveme maticí vzdáleností. Jako kritérium podobnosti popisů použijte euklidovskou vzdálenost. Označme si obrázky v nichž hledáme korespondence pravý a levý. Zkusíme si několik metod výběru tentativních korespondencí:
Výstupem hledání tentativních korespondencí jsou dvojice indexů, párů z levého a pravého obrázku s nejpodobnějšími popisy.
corrs=match(pts1, pts2, par)
pts1
pts2
par
pts1(i).desc
pts2(i).desc
par.threshold
par.method = 'mutual'; % pro metodu vzajemne nejblizsich popisu 'stable'; % pro metodu slabeho parovani a 'sclosest'; % pro metodu prvni/druhy nejblizsi par.threshold % prah, dvojice popisu s euklidovskou vzdalenosti vyssi nez prah se ignoruji
Dvojice bodů získané v předchozím kroku na základě podobnosti zpravidla obsahují mnoho nekorespondujících bodů (nazývají se outliers), tedy tentativních korespondencí, jenž mají podobné popisy ale neodpovídají jednomu fyzickému prvku scény. Cílem poslední fáze hledání korespondencí je zbavit se těchto bodů za předpokladu o možné transformaci scény mezi dvěma pohledy. Výsledkem je nalezení modelu – transformace scény a množiny tzv. inlierů, tentativních korepsondencí, jenž jsou konzistentní s nalezeným modelem.
S transformací rovinné scény jste se již mohli setkat na předmětu Digitální obraz. Pro připomenutí si můžete znovu prostudovat dokument o hledání projektivní transformace. Ve zkratce:
Transformace roviny mezi dvěma pohledy perspektivní kamery je lineární transformace (nazývaná taky homografie) 3-dimenzionálních homogenních vektorů (korespondujících bodů v homogenních souřadnicích) reprezentovaná regulární <latex>3\times 3</latex> maticí <latex>\mathbf{H}</latex>:
<latex>
\lambda\left[\!\begin{array}{c}x'\\y'\\1\end{array}\!\right]= \left[\begin{array}{ccc}h_{11}&h_{12}&h_{13}\\h_{21}&h_{22}&h_{23}\\h_{31}&h_{32}&h_{33}\end{array}\right] \left[\!\begin{array}{c}x\\y\\1\end{array}\!\right]%
</latex>
Pro každý korespondující pár <latex>(x_i,y_i)^{\top} \leftrightarrow (x'_i,y'_i)^{\top}</latex> platí
<latex> \begin{array}{lcr}
x' (h_{31}\,x + h_{32}\,y + h_{33}) - (h_{11}\,x + h_{12}\,y + h_{13}) & = & 0 \\ y' (h_{31}\,x + h_{32}\,y + h_{33}) - (h_{21}\,x + h_{22}\,y + h_{23}) & = & 0
\end{array}</latex>
Pro korespondující páry můžeme zostavit systém rovníc:
<latex>\underbrace{\left[\begin{array}{r@{\ }r@{\ }rr@{\ }r@{\ }rr@{\ \ }r@{\ \ }r} -x_1&-y_1&-1&0&0&0&x_1'x_1&x'_1y_1&x_1'\\0&0&0&-x_1&-y_1&-1&y_1'x_1&y'_1y_1&y_1' -x_2&-y_2&-1&0&0&0&x_2'x_2&x'_2y_2&x_2'\\0&0&0&-x_2&-y_2&-1&y_2'x_2&y'_2y_2&y_2' &\vdots&&&\vdots&&&\vdots& -x_n&-y_n&-1&0&0&0&x_n'x_n&x'_ny_n&x_n'\\0&0&0&-x_n&-y_n&-1&y_n'x_n&y'_ny_n&y_n' \end{array}\right]}_\mathbf{C} \left[\begin{array}{c}h_{11}\\h_{12}\\h_{13}\\h_{21}\\h_{22}\\h_{23}\\h_{31}\\h_{32}\\h_{33}\end{array}\right]=0</latex>
Tento homogénní systém rovníc má 9 neznámých. Jedno netriviální řešení dostaneme jako pravý nulový prostor matice <latex>\mathbf{C}</latex>. Pro jednoznačné řešení potřebujeme, aby matice <latex>\mathbf{C}</latex> měla alespoň 8 lineárne nezávislých řádků, t.j. 8 omezení ze 4 korespondujících bodů v obecné poloze (žadné tři nesmí ležet na přímce).
H=u2h(u)
[ x1 x2 … x4; y1 y2 … y4; 1 1 1 1 ; x'1 x'2 … x'4; y'1 y'2 … y'4; 1 1 1 1]
dist=hdist(H,u)
Pro nalezení modelu scény – 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ů z tentativních korespondencí, použijeme algoritmus M.Fischlera a R.C.Bollese, RANSAC.
V našem případě má algoritmus RANSAC (budete se ním podrobněji zabývat na prednášce) tuto formu:
sample.m
hdist
Počet iterací zvolte nejdříve 1000 a odlaďte RANSAC na lehkém páru obrázků. V praxi se použivá pro zastavení výpočtu sofistikovanější kritérium, než je pevně zadaný počet iterací. Je založeno na odhadu pravděpodobnosti nalezení správneho vzorku (sestávajícího v našem případě ze čtyř správných korespondencí) za předpokladu průběžně odhadovaného procenta inlierů. Kritérium je implementováno funkcí nsamples.m a pro zvolenou pravděpodobnost conf spočítá potřebný celkový počet iterací:
nsamples.m
num_samples = nsamples(pocet_inlieru, pocet_paru, velikost_vzorku, conf);
nsamples
[Hbest,inl]=ransac_h(u,threshold,confidence)
Aby jste mohli ověrit korespondence i pro jiné než rovinné scény, budeme potřebovat obecnejší vztah svazující dva body ve dvou kamerách. Tento vztah se pro dvojici perspektivních kamer jmenuje epipolární geometrie. Podrobněji se jí budete zabývat na předmětu A4M33TZ, pro zběžnou představu poslouží wikipedie nebo písnička :). Pro nás je důležité, že epipolární geometrie je geometrický vztah korespondujících bodů <latex>x_L</latex> a <latex>x_R</latex>, obrazů bodu <latex>X</latex> ve scéně viděného dvojicí perspektivních kamer:
Tenhle vztah se dá matematicky vyjádřit:
<latex>x^\top_L \mathbf{F}\, x_R = 0</latex>
Epipolární geometrie je reprezentována maticí <latex>\mathbf{F}</latex>, zvanou fundamentální matice. Pro její nalezení je potřebných alespoň 7 korespondujících bodů. Aby náš RANSAC fungoval pro hledání epipolární geometrie, budeme potřebovat dvě věci, funkci u2f7.m pro výpočet modelu – fundamentální matice <latex>\mathbf{F}</latex> a funkci fds.m pro nalezení vzdálenosti bodů od modelu, t.j. vzdálenosti od epipolární přímky (obrazu paprsku v druhé kamere). Funkce mají stejné parametre jako u2h a hdist jen matice <latex>\mathbf{H}</latex> se zamění za matici <latex>\mathbf{F}</latex>. Funkce u2f7 může vrátit jedno (výsledek je 3×3 matice) nebo až tři řešení (3x3xpocet_reseni), je potřeba upravit verifikaci nalezeného modelu, tak aby zkusil najít nejlepší ze všech vrácených modelů.
u2f7.m
u2h
[Fbest,inl]=ransac_f(u,threshold,confidence)
fds
Naprogramujte funkce detect_and_describe.m, match.m, u2h.m, hdist.m, ransac_h.m, ransac_f.m a odevzdajte je do úlohy 04_corr spolu se všemi potřebnými funkcemi.
04_corr
Na vaší dátové sadě vyberte pro každý objekt nějakou kombinaci detektoru/popisu. Spusťte detektory a vygenerujte popisy pro všechny obrázky funkcí detect_and_describe. Uložte výsledky (strukturu pts) do souborů obj%d_view%d.mat spolu s konfigurací detektoru (detpar), normalizace a popisu (descpar). Obrázky i pohledy číslujeme od 0 (např. pro objekt 1 obrázek 3 bude výsledek: struktury pts, detpar a descpar uložen v souboru obj1_view3.mat, pro objekt 0 obrázek 0 v souboru obj0_view0.mat, atd.).
detect_and_describe
obj%d_view%d.mat
Vygenerujte tentativní korespondence pro každý objekt a všechny páry pohledů na objekt . Výsledkem bude matice TC cellů 5×5, jejíž prvky budou pole corrs z funkce match. Budeme předpokládat, že proces je symetrický (2→1 je to samé jako 1→2) a vygenerujeme jenom horní trojúhelník (index prvního obrázku bude řádek a index druhého sloupec) matice bez uhlopříčky. Výsledek, matici TC uložte spolu s konfigurací par metody match do souboru obj%d_tc.mat.
match
obj%d_tc.mat
Na závěr pro každý objekt pusťte oba RANSACy na vygenerovaných tentativních korespondencích a výsledky uložte do matic H, F, inlH a inlF cellů 5×5. Ostatní celly, dolní troúhelník matice a prvky na uhlopříčce nechte prázdné. Výsledek: matice cellů H, F, inlH a inlF znovu uložte do souboru obj%d_results.mat spolu s parametry thresh_h, thresh_f, conf_h, conf_f funkcí ransac_h a ransac_f.
obj%d_results.mat
Všechny výsledky zabalte do archivu a odevzdejte do úkolu 04_results, pro snížení pamětové náročnosti zmažte ze struktur pts pole patch, funkcí rmfield.
04_results
pts
rmfield
Pro kontrolu správnosti odevzdaných funkcí jsme použili skript a funkci MATLABu publish. Nakopírujte si corr_test.zip, rozbalte ho do cesty MATLABu (nebo adresáře s vašimi funkcemi) a spusťte. Výsledky si ověrte porovnáním s referenčním řešením.