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)
, která vypočíta Hessián pre každý pixel vstupného obrazu img dle vzorce: <latex>\mathrm{det}(\mathbf{H}) = D_{xx} D_{yy} - D_{xy}^2</latex>. Pro výpočet druhých derivací <latex>D_{xx},D_{yy},D_{xy}</latex> použijte derivaci Gaussiánu s variancí <latex>\sigma^2</latex>.
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)
pro potlačení nemaximálních bodů, t.j. ze vstupního obrázku response (matice o rozměru HxW kde H je výška a W je šířka obrázku). Funkce vrátí matici maximg o stejné velikosti, ve které nastaví všechny lokální maxima matice větší než thresh na hodnotu jedna a ostatní body v matici maximg nastaví na nulu. Funkce testuje lokální maxima v 8mi okolí.[x,y]=hessian(img,sigma,thresh)
, jenž nalezne maxima Hessiánu v obrázku img při měrítku gradientu sigma. Vraťte pouze souřadnice (x,y) těch lokálnich maxim jejichž hodnota je vyšší než práh thresh. Pro nalezení souřadnic bodů můžete použít funkci [y,x]=find(maximg)
. Výslední vektory x a y vraťte jako řádkové vektory stejné velikosti kde x(1),y(1) bodou souřadnice prvního bodu, x(2),y(2) druhého bodu, atd… . Dejte pozor na indexy, jenž jsou v MATLABe číslovány od jedničky a náš levý horní pixel obrázku chceme se souřadnicemi (0,0).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,
<latex>\sigma_d</latex>,
<latex>\sigma_i</latex>)
, která vypočíta odezvu Harrisovy funkce pro každý pixel vstupného obrazu img.Pro výpočet použijte derivací Gaussiánu <latex>D_{x},D_{y}</latex> se směrodatnou odchylkou <latex>\sigma_d</latex> a Gaussián jako okenní funkci se směrodatnou odchylkou <latex>\sigma_i</latex> .
[x,y]=harris(img,
<latex>\sigma_d</latex>,
<latex>\sigma_i</latex>,thresh)
, detekujíci maxima Harrisovy funkce se směrodatnou odchylkou pro počítaní derivací <latex>\sigma_d</latex> a okenní funkcí se směrodatnou odchylkou <latex>\sigma_i</latex> jenž jsou vyšší než 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)
, která vrátí třírozměrný prostor meřítek (matici HxWxL, kde H je výška, W je šírka a L je počet úrovní levels), kde ss(:,:,1)
bude vstupní obrázek img o němž budeme předpokládat <latex>\sigma_1 = 1</latex> a ss(:,:,i)
bude jeho filtrovaná verze <latex>S(x,y,\sigma_{i+1})</latex>, kde <latex>\sigma_{i+1}=\mathrm{step}\cdot\sigma_i </latex> pro <latex>i \in \{2,\ldots,\mathrm{levels}\}</latex>. Ve vektoru sigma bodou hodnoty <latex>\sigma_i </latex>.
maximg=nonmaxsup3d(response, threshold)
pro potlačení nemaximálních bodů v třírozměrné matici response (t.j. uvažujte všechny 26 okolí bodu), funkce vrátí matici o velikosti jako vstupní matice response, ve které budou jedničky na místech lokálních maxim matice response větších než thresh.
[hes,sigma]=sshessian_response(img)
, která použije funkci scalespace
a spočítá odezvu Hessianu na normalizovaných derivacích Gaussiánu. Vhodně zvolte parametry step a levels funkce scalespace
(napr. step=1.1, levels=40). Pro výpočet odezvy použijte odhad druhých derivací differenciálnimi filtry aplikovanými na výsledek funkce scalespace. Derivace normalizujte směrodatnou odchylkou za každý řád derivace (viď. popis výše). Výstupem bude třírozměrná matice hes v níž elementy budou odpovídat normalizované odezvě Hessiánu v prostoru měrítek.
nonmaxsup3d
a sshessian_response
v detektor maxim Hessiánu s automatickým výběrem měrítka [x,y,s]=sshessian(img, thresh)
. Vraťte jenom body jenž mají hodnotu Hessiánu vyšší než thresh. Výsledkem volání budou řádkové vektory stejné délky, pozice x, y a měřítko s maxim Hessiánu v prostoru měrítek větších než thresh. Levý horní bod obrázku má souřadnice 0,0. Pro lokalizaci bodů můžete použít následující program:
% 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ů.
<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>
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]);MSER jsou afinně kovariatní oblasti, jejich kovarianční matice je možné vizualizovat jako elliptické oblasti, s delší poloosí odpovídající maximálnímu rozptylu elementů. Pro konverzi na eliptické oblasti můžete použít následující kód
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]);Pro vizualizaci si nezapomeňte stáhnout nejnovější verzi showpts.m.
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.
Původní obrázek | Translace | Translace a rotace | Similarita | Afinní transformace |
Ukázka geometrické normalizace výřezu, různými třídami transformací (autorem obrázků je Štepán Obdržálek). |
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)
pro odhad dominantní orientace gradientu v normalizovaném výřeze obrázku. Vstupem bude částečně normalizovaný výřez obrázku (ps x ps matice typu double), výstupem hodnota úhlu (v radiánech v intervalu < -pi, pi>) od osi x obrázku, měrená po směru hodinových ručiček (úhel vám pro vektor (x,y) spočítá funkce atan2(y,x)
). Volitelně může funkce vrátit více než jednu orientaci, orientace budou seřazeny dle “dominantnosti” gradientu od největšího po nejmenší.
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)
kde img bude vstupní obrázek x,y řádkové vektory se souřadnicemi bodů a s - skalární hodnota, měrítko bodů (pro všechny body stejné).
pts=simnorm(img,x,y,s,opt)
kde img bude vstupní obrázek x,y řádkové vektory se souřadnicemi bodů a s - řádkový vektor s měřítky bodů (viď, výstup z funkce sshessian).
pts=affnorm(img,x,y,a11,a12,a21,a22,opt)
kde img bude vstupní obrázek x,y řádkové vektory se souřadnicemi bodů a a11,a12,a21,a22 - řádkové vektory s afinní transformací bodů.
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:
% ... 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)
, která pro každý bod v poli struktur pts fotometricky znormalizuje výřez obrázku (v poli patch
) tak aby střední hodnota na výřezu byla 0,5 a směrodatná odchylka 0,2. Hodnoty jenž budou mimo rozsah <0,1> nastaví na mezní hodnoty. Funkce a vrátí pole struktur ptsn o stejné velikosti jako pts s modifikovaným výřezem v poli patch
a uloží hodnoty původní střední hodnoty a směrodatné odchýlky do pole mean
a 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)
, která spočíta pro vstupní výřez DCT transformaci a vrátí prvních num_coeffs koeficientů v zig-zag pořadí. Hodnoty koeficientů normalizujte do rozsahu <0,1>.
dxdy=ghistodesc(img,num_bins)
, která spočítá histogram gradientů, num_bins je počet binů na kanál, t.j. výslední dxdy popis bude sloupcový vektor s num_bins2 elementů histogramu (velikost gradientu v dx - řádek, dy - sloupec) po sloupcích (matlab operator (:) ). Elementy normalizujte do rozsahu <0,1> (0 - žádný výskyt, 1 - výskyt v každém bodě výřezu).
sift=siftdesc(img)
, která na výřeze obrázku spočítá SIFT popis se 4×4 histogramy o 8mi orientacích. Výsledný popis sloupcový vektor o 128položkách normalizujte na velikost 1.0, v případě že některá složka přesáhne hodnotu 0.2, nastavte ji na 0.2 a opakujte normalizaci.
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:
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.pro popis dct navíc:
descpar.num_coeffs % pocet koeficientu v zig-zag poradia pro popis ghisto:
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.
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)
, jenž pro body pts1
a pts2
zadané strukturami nalezne korespondence metodou specifikovanou ve struktuře par
. Popisy bodů jsou pro každý bod <latex>i</latex> uloženy v poli pts1(i).desc
resp. pts2(i).desc
. Metoda je specifikovaná ve struktuře par poli par.method jako řetezec. Pro každou z metod ignorujte dvojice popisů (tentativní korespondence) se vzdáleností větší než práh 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 ignorujiVýstupem bude matice 2xN, indexů tentativních korespondencí, kde první řádek budou indexy do pole pts1 a druhý řádek indexy do pole pts2.
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)
, která dostane matici 4 dvojic korespondujících bodů v homogénních souřadnicích a spočítá z nich homografii <latex>\mathbf{H}</latex>. Matice u je rozměru 6×4: [ 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]
, kde xi,yi jsou body v levém obrázku a x'i,y'i v pravém. V případě, že bude nejaká trojice bodů blízka přímce, vráti prázdnou matici [].
dist=hdist(H,u)
, která dostane u matici N dvojic korespondujících bodů v homogénních souřadnicích t.j. matici 6xN a vrátí dist (matice 1xN) druhou mocninu vzdálenosti bodů <latex>\mathbf{H} (x_i, y_i,1)^\top</latex> a <latex>(x'_i, y'_i,1)^\top</latex>.
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
) transformovaného bodu z levého obrázku a odpovídajícího bodu v pravém obrázku menší než zadaný práh (např. 1-3 pixely).
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í:
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
.
[Hbest,inl]=ransac_h(u,threshold,confidence)
, která najde homografii <latex>\mathbf{H}^*</latex> a množinu inlierů inl. Vstupem budou dvojice souřadnic u (matice 6xN, dvojic odpovídajících si bodů v homogénních souřadnicích), podobně jako ve funkci hdist
. Parametr threshold bude udávat maximální vzdálenost bodů pomocí funkce hdist
jenž budou označeny jako inliery, konzistetní s výslední homografii <latex>\mathbf{H}^*</latex>. Parametr confidence bude hodnota v intervalu (0,1), požadovaná pravděpodobnost správného výsledku (pro testování použijte napr. 0.95). 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:
Epipolární geometrie, zdroj wikipedie |
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ů.
[Fbest,inl]=ransac_f(u,threshold,confidence)
, která najde fundamentální matici <latex>\mathbf{F}^*</latex> a množinu inlierů inl. Vstupem budou dvojice souřadnic odpovídajících si bodů (dle tentativních korespondencí) v homogénních souřadnicích, podobně jako ve funkci hdist
. Parametr threshold bude udávat maximální vzdálenost bodů pomocí funkce fds
jenž budou označeny jako inliery, konzistetní s výslední epipolární geometrii <latex>\mathbf{F}^*</latex>. Parametr confidence bude hodnota v intervalu (0,1), požadovaná pravděpodobnost správného výsledku (pro testování použijte napr. 0.95).
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.
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.).
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
.
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.
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
.
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.