====== Hledání korespondencí ====== 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. ====== 1. Detekce bodů zájmu ====== 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. ===== Hessian 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 [[http://cs.wikipedia.org/wiki/Hessova_matice|Hessovy]] matice (matice druhých derivací) \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], hledá centra tzv. blobů, lokálních extrémů intenzitní funkce, které jsou dobře lokalizovány v okolí daném variancí \sigma^2 . Body zájmu jsou pak ty lokální maxima, jejichž hodnota je nad určitou hranicí t danou úrovní šumu v obrázku * Napište funkci ''response=hessian_response(img,sigma)'', která vypočíta Hessián pre každý pixel vstupného obrazu //img// dle vzorce: \mathrm{det}(\mathbf{H}) = D_{xx} D_{yy} - D_{xy}^2. Pro výpočet druhých derivací D_{xx},D_{yy},D_{xy} použijte derivaci Gaussiánu s variancí \sigma^2. 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. * Napište funkci ''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í. * Nakonec spojte obě funkce do detektoru ''[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 ===== 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. \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] kde * je operátor konvoluce. Prostřednictvím okenní funkce G(x,y;\sigma_i) se akumulují matice vnějších součinů gradientu v \sigma_i 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 [[http://en.wikipedia.org/wiki/Corner_detection#The_Harris_.26_Stephens_.2F_Plessey_corner_detection_algorithm|Harris a Stephens]] a navrhli elegatní funkci R(x,y) = \mathrm{det}(\mathbf{C})-\alpha\mathrm{trace}^2(\mathbf{C}). Ta obchází výpočet vlastních čísel \lambda_1,\lambda_2 matice \mathbf{C} využitím ekvivalencí\\ \\ \begin{array}{rcl} \mathrm{det}(\mathbf{C})\!&=&\!\lambda_1\lambda_2\\ \mathrm{trace}(\mathbf{C})\!&=&\!\lambda_1 + \lambda_2 \end{array} na zjištění vlastností jejich poměru. {{ harris_response.png |Obrázek ukazuje průběh funkce R(x,y) pro alpha=0.04, bílé usečky označují izokontury s hodnotami 0, 0.02, 0.04, 0.06, ..., 0.18.}} Obrázek ukazuje průběh funkce R(x,y) pro \alpha=0.04, 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. * Napište funkci ''response=harris_response(img,''\sigma_d'',''\sigma_i'')'', která vypočíta odezvu Harrisovy funkce pro každý pixel vstupného obrazu //img//.Pro výpočet použijte derivací Gaussiánu D_{x},D_{y} se směrodatnou odchylkou \sigma_d a Gaussián jako okenní funkci se směrodatnou odchylkou \sigma_i . * Analogicky s detektorem maxim Hessianů napište funkci ''[x,y]=harris(img,''\sigma_d'',''\sigma_i'',thresh)'', detekujíci maxima Harrisovy funkce se směrodatnou odchylkou pro počítaní derivací \sigma_d a okenní funkcí se směrodatnou odchylkou \sigma_i jenž jsou vyšší než //thresh//. ===== Scale-space - prostor měřítek a automatické určení měřítka ===== 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): \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{,} 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 \\ \\ \mathrm{trace}(\mathbf{H}_{norm}(x,y,\sigma_i))=N_{xx}(x,y;\sigma_i)+N_{yy}(x,y;\sigma_i) \\ \\ a Hessiánu \\ \\ \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) \\ \\ 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 \sigma 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. {{blobs.png?350x350|Obrázek Gaussiánů se směrodatnými odchylkami=8,16,24 a 32.}} {{scalespace_signature.png?350x350|Odezva differenciálních operátorů v prostoru měřítek ve středech Gaussiánů.}} * napište funkci ''[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 \sigma_1 = 1 a ''ss(:,:,i)'' bude jeho filtrovaná verze S(x,y,\sigma_{i+1}), kde \sigma_{i+1}=\mathrm{step}\cdot\sigma_i pro i \in \{2,\ldots,\mathrm{levels}\}. Ve vektoru //sigma// bodou hodnoty \sigma_i . * napište funkci ''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//. {{maximum26.png|Okolí bodu v 3D.}} * napište funkci ''[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. * spojte funkce ''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 {{ sunflowers.png }} pro vizualizaci nalezených bodů můžete použít funkci {{showpts.m|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: {{ sunflowers_sshesian.png |Obrázek s detekovanými multiscale Hessián body.}} ===== Afinní kovariance, Baumbergova iterace ===== **(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ů. \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] Jak sme si již řekli dřív, tato matice reflektuje lokální distribuci gradientů, dá se ukázat, že když najdeme transformaci \mathbf{\mu} = \mathbf{C}^{-1/2}, která promítne souřadný systém daný vlastními vektory a vlastními čísly matice \mathbf{C} na kanonický, distribuce gradientů ve výřezu transformovaném matici \mathbf{\mu} 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 \mathbf{C}_i 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 \mathbf{C}_i. Výslednou matici lokální afinní deformace získame jako celkovou deformaci okolí potřebnou na jeho "narovnání" na izotropní: N = \prod_i \mu_i 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 \mathbf{A}=\mathbf{N}^{-1}. * napište funkci [x,y,a11,a12,a21,a22]=affinehessian(img, threshold), která rozšíří detektor maxim Hessiánů z předchozího kroku a pro každé maximum v prostoru měřítek spočte jeden krok Baumbergovy iterace. Funkce vrátí pozici bodu a 2x2 submatici matice A: A=s*inv(C^{-1/2}/sqrt(det(C^{-1/2})))) ===== Maximalně Stabilní Extremální Oblasti ===== 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 {{extrema.zip|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}}. ===== Dátová sada ===== 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í. ===== Co odevzdat? ===== 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. ===== Kontrola výsledků ===== Pro kontrolu výsledků vašich funkcií jsme použili skript a funkci MATLABu publish. Nakopírujte {{detect_test.zip|detect_test.zip}}, rozbalte ho do cesty MATLABu (nebo adresáře s vašimi funkcemi) a spusťte. {{results.zip|Výsledky}} si ověrte porovnáním s [[http://cmp.felk.cvut.cz/~perdom1/mpv/02_detect/test.html|referenčním řešením]]. ===== Reference ===== - [[http://en.wikipedia.org/wiki/Feature_detection_(computer_vision)|Přehled nejpoužívanějších metod pro hledání bodů a oblastí zájmu.]] - [[http://www.bmia.bmt.tue.nl/education/courses/FEV/book/pdf/02%20Foundations%20of%20scale-space.pdf|Teoretické základy a odvození Gaussiánu jako vhodného jádra pro vybudování scale-space.]] - [[http://en.wikipedia.org/wiki/Scale-space|Scale space, základní nástroj pro hledání bodů zájmu nezávislých na měřítku.]] - [[http://en.wikipedia.org/wiki/Affine_shape_adaptation|Process afinní adaptace.]] - [[http://www.robots.ox.ac.uk/~vgg/research/affine/|Přehled afinně kovariatních detektorů]] ====== 2. Generování lokálního invariantního popisu ====== 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í. ===== Geometrická normalizace ===== 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 [[courses:a4m33mpv:cviceni:1_uvod:start#geometricke_transformace_a_interpolace_jasove_funkce|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 | | {{cutoff1.jpg?150x150}} | {{translation1.jpg?100}} | {{euclidean1.jpg?100}} | {{similarity1.jpg?100}} | {{affine1.jpg?100}} | | {{cutoff2.jpg?150x150}} | {{translation2.jpg?100}} | {{euclidean2.jpg?100}} | {{similarity2.jpg?100}} | {{affine2.jpg?100}} | | 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ě: - Pro rotačně a translačně kovariatní bod máme souřadnice x,y a úhel \alpha a s velikost rámce stejná pro všechny body (a zvolená manuálně). Pak\\ A=\underbrace{\left[\begin{array}{ccc} 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] - Pro similaritní bod souřadnice x,y velikost okolí \sigma a úhel \alpha. Matici A dostaneme\\ A=\underbrace{ \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] - Pri afinně kovariatním bode nebo oblasti máme náme tři body na které se promítnou body z kanonického souřadného systému, viď predposlední úkol prvního cvičení. Nebo je pro bod známa pozice, částečná afinní transformace a zbytková rotace o úhel \alpha. Matici A pak složíme z translace a 2x2 podmatice následovně \\ A=\underbrace{ \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] 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 \alpha). 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 \alpha) 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 A_{norm}. Na výřezu znormalizovaném maticí A_{norm} se pak se určí orientace dominantního gradientu (reprezentována rotační maticí) a složí se s A_{norm} 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í A_{norm}, 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ňů. * napište funkci ''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 A a normalizovaných výřezů: * při známe pozici bodu, funkci ''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é). * při známe pozici a měrítku bodu, funkci ''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). * při známe pozici a částečné afinní transformaci bodu, funkci ''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'', 2x2 část transformační matice A 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 ===== 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 \sigma jeho rozsahu (případně 2\times\sigma). V případě, že chceme využít všechny tři barevné kanály, normalizujeme každou složku zvlášť. * Napište funkci ''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''. ===== Výpočet popisu ===== 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. - popis využívající dvourozměrnou diskrétní kosínusovou transformaci (DCT). Koeficienty této integrální transformace vzniknou skalárním součinem výrězu obrázku s tzv. DCT bázovými funkcemi viď. obrázek: \\ {{dct_basefn.png|Obrázek prvních 8 bázových funkcí v každé z dimenzíí dvourozměrné DCT.}} {{zigzag.png?346x346|Zig-zag pořadí koeficientů}}\\ Výřez obrázku je takto rozložen na jednotlivé "frekvence" podobně jako u JPEG komprese. Podobně jako u komprese obrázků vybereme podmnožinu těchto koeficientů obsahující informaci o nízkých frekvencích. Tím dosáhneme odolnost popisu k vysokofrekvenčnímu šumu a do jisté míry i k nepřesnostem v geometrické normalizaci. Z obrázku bázových funkcí vidíme, že výběr DCT koeficientů budeme provádet v tzv. [[http://en.wikipedia.org/wiki/JPEG#Entropy_coding|zig-zag]] pořadí, kdy budeme přidávat postupne vyšší a vyšší frekvence. * napište funkci ''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>. - (volitelný úkol) RGB histogram, RG histogram, histogram gradientů jsou metody využívající globálních vlastnosti výřezu obrázku. Barevné kanály obrázku (napr. R,G,B) se nejdříve spracují a vypočtou se charakteristiky jenž se následne kvantizují do binů a spočítají. Výsledný popis je tvořen lineárním vektorem, počtami v jednotlivých binech. RG projekce nebo tzv. [[http://en.wikipedia.org/wiki/Rg_chromaticity|chromacity]] barevný prostor má dvě složky \\ R=\frac{R}{R+G+B}\quad G=\frac{G}{R+G+B}, \\ vyjádřuje podíl červené a zelené složky v obraze. Výhodou histogramů výřezu je necitlivost k nepřesnostem geometrické normalizace, nevýhodou je nižší rozlišovací schopnost tzv. distinktivita. * napište funkci ''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_bins//2 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 popis - Lokální histogram orientací (volitelný úkol) ===== - lokální histogramy řeší problém s rozlišovací schopností tím, že se výřez rozdělí na menší částečně prěkrývající se části a histogramy se akumulují v těchto částech. Nejpoužívanější popis založený na lokálních histogramech je [[http://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf|SIFT]]. SIFT je lokální histogram orientací gradientů ve čtvercové mřížce. Výřez se rozdělí do pravidelné mřížky nejčastěji 4x4 a v každém čtverci se spočíta histogram gradientů vážený jejich velikostí rozdělen na 8 orientací. Pro zrobustnení vůči nepřesnosti geometrické normalizace se velikosti gradientů váhují okenní funkcí (o velikosti sigma=ps/6). Dále se každý čtvěrec 4x4 mřížky zvetší tak, aby zasahoval do půlky hrany svých sousedů. Stejně hlasování do binů orientací se provádí lineární interpolací do dvou sousedních binů. Takto spočítaný popis je velice robustní a hodně používán. \\ {{ gradient-descriptor.png |SIFT deskriptor}} \\ * napište funkci ''sift=siftdesc(img)'', která na výřeze obrázku spočítá SIFT popis se 4x4 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. ===== Co odevzdat ===== 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. ===== Kontrola výsledků ===== Pro kontrolu výsledků vašich funkcií jsme použili skript a funkci MATLABu publish. Nakopírujte {{desc_test.zip|desc_test.zip}}, rozbalte ho do cesty MATLABu (nebo adresáře s vašimi funkcemi) a spusťte. {{desc_results.zip|Výsledky}} si ověrte porovnáním s [[http://cmp.felk.cvut.cz/~perdom1/mpv/03_desc/test.html|referenčním řešením]]. Test i řešení ještě doplním (o chybějící funkce). ===== Reference ===== - [[http://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf|David G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, 60, 2 (2004), pp. 91-110.]] - [[http://lear.inrialpes.fr/pubs/2005/MS05/mikolajczyk_pami05.pdf|Porovnání různých metod generování lokálních popisů]]. ====== 3. Hledání tentativních korespondencí a RANSAC ====== ===== Příprava ===== 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//: * pro Hessian detektor: \\ detpar.type='hessian'; detpar.sigma % sigma pro vypocet derivaci detpar.threshold % prah * pro Harris detektor: \\ detpar.type='harris'; detpar.sigmad % derivacni sigma detpar.sigmai % integracni sigma detpar.threshold % prah * pro Hessian detektor v prostoru měřítek \\ detpar.type='sshessian'; detpar.threshold % prah * pro MSER detektor \\ 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 poradi a 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 i doplní pole ''pts(i).desc'' se spočteným popisem jako sloupcovým vektorem. Funkci si můžete stáhnout {{detect_and_describe.m|zde}}. ===== Tentativní korespondence ===== 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í: - Tentativní korespondence **vzájemně nejbližších** popisů vznikne, pokud zvolený popis A z pravého obrázku má ze všech popisů z levého obrázku nejbližší popis B a zároveň, popis B má nejbližší ze všech popisů v pravém obrázku popis A. - Při (slabém) **stabilním párovaní** popisů, postupujeme jinak. V každém kroku algoritmu najdeme globálně nejbližší popisy A a B. Vytvoříme tentativní korespondenci a popisy A a B vyloučíme z dalšího hledání (např. nastavením vzdáleností příslušného řádku sloupce na nekonečno). Postup opakujem pokud zůstali v matici vzdáleností nějaké aktivní prvky (hodnoty menší než nekonečno). - Jiný postup je najít ke každému popisu z levého obrazu nejbližší dva v pravém obrazu. Když je poměr vzdáleností **prvního/druhého nejbližšího** popisu menší než např. 0.8, popisy korespondují, a zároveň je zaručeno, že v jistém "okolí" v prostoru popisů není žádný bod s kterým by sme si ho mohli splést. Tuto metodu je možné použít pro diskriminativní popisy, např. SIFT. 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. * napište funkci ''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 i 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 ignoruji Výstupem bude matice 2xN, indexů tentativních korespondencí, kde první řádek budou indexy do pole pts1 a druhý řádek indexy do pole pts2. ===== RANSAC a geometrický model scény ===== 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. ==== Nalezení transformace rovinné scény ==== S transformací rovinné scény jste se již mohli setkat na předmětu [[http://cmp.felk.cvut.cz/cmp/courses/DZO/Lab03/lab03.html#u2|Digitální obraz]]. Pro připomenutí si můžete znovu prostudovat [[http://cmp.felk.cvut.cz/cmp/courses/383ZS/X383ZS2005-6_Leto/cvic3/geomtransf.pdf|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í 3\times 3 maticí \mathbf{H}: \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]% Pro každý korespondující pár (x_i,y_i)^{\top} \leftrightarrow (x'_i,y'_i)^{\top} platí \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} Pro korespondující páry můžeme zostavit systém rovníc: \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 Tento homogénní systém rovníc má 9 neznámých. Jedno netriviální řešení dostaneme jako pravý nulový prostor matice \mathbf{C}. Pro jednoznačné řešení potřebujeme, aby matice \mathbf{C} 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). * napište funkci ''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 \mathbf{H}. Matice //u// je rozměru 6x4: ''[ 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 []. * napište funkcie ''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ů \mathbf{H} (x_i, y_i,1)^\top a (x'_i, y'_i,1)^\top. ==== RANSAC ==== 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: - Náhodně vybereme 4 korespondující páry, tzv. vzorek (sample). K vygenerování nahodné permutace můžete použít funkci ''{{sample.m}}''. - Z těchto bodů vypočteme homografii \mathbf{H}. - Zjistíme tzv. podporu nebo-li support nalezeného modelu. Je-li \mathbf{H} spočtená ze správných korespondencí, měly by transformované body (x_i,y_i) ležet na místech korespondujících bodů (x'_i,y'_i) v druhém obraze. Podporu modelu kvantifikujeme počtem bodů konzistentních s modelem. T.j. bodů se vzdáleností (viď funkce ''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). - Pokud je hodnota podpory nalezené homografie doteď největší, uložíme si její hodnotu, doteď-nejlepší-model \mathbf{H}^* a množinu inlierů nebo-li bodů které podporili tento model. - Body 1-4 opakujeme iterativně, a hledáme takovou \mathbf{H}^* která správně transformuje největší počet korespondencí, tj. maximalizuje kritérium definované v bodě 3. 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''. * s využitím výše uvedených funkci pro určení modelu a vzdálenosti od homografie, napište funkci ''[Hbest,inl]=ransac_h(u,threshold,confidence)'', která najde homografii \mathbf{H}^* 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 \mathbf{H}^*. 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). \\ Výstupem bude nejlepší nalezený model \mathbf{H}^* a pole inl 1xN, kde 0 bude znamenat outlier a 1 inlier, kde N je počet bodů, sloupců matice //u//. ===== Vzájemná poloha dvou kamer, epipolární geometrie ===== 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ží [[http://en.wikipedia.org/wiki/Epipolar_geometry|wikipedie]] nebo [[http://danielwedge.com/fmatrix/|písnička :)]]. Pro nás je důležité, že epipolární geometrie je geometrický vztah korespondujících bodů x_L a x_R, obrazů bodu X ve scéně viděného dvojicí perspektivních kamer: | {{ 500px-epipolar_geometry.svg.png }} | | Epipolární geometrie, zdroj [[http://en.wikipedia.org/wiki/Epipolar_geometry|wikipedie]] | Tenhle vztah se dá matematicky vyjádřit: x^\top_L \mathbf{F}\, x_R = 0 Epipolární geometrie je reprezentována maticí \mathbf{F}, 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 \mathbf{F} 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 \mathbf{H} se zamění za matici \mathbf{F}. Funkce u2f7 může vrátit jedno (výsledek je 3x3 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ů. * s využitím výše uvedených funkci pro určení modelu a vzdálenosti od modelu epipolární geometrie, napište funkci ''[Fbest,inl]=ransac_f(u,threshold,confidence)'', která najde fundamentální matici \mathbf{F}^* 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 \mathbf{F}^*. 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).\\ Výstupem bude nejlepší nalezený model \mathbf{F}^* a pole inl 1xN, kde 0 bude znamenat outlier a 1 inlier, kde N je počet bodů, sloupců matice //u//. ===== Zadání úlohy na hledání korespondencí ===== 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ů 5x5, 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ů 5x5. 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''**. ===== Kontrola výsledků ===== Pro kontrolu správnosti odevzdaných funkcí jsme použili skript a funkci MATLABu publish. Nakopírujte si {{corr_test.zip|corr_test.zip}}, rozbalte ho do cesty MATLABu (nebo adresáře s vašimi funkcemi) a spusťte. {{corr_results.zip|Výsledky}} si ověrte porovnáním s [[http://cmp.felk.cvut.cz/~perdom1/mpv/04_corr/test.html|referenčním řešením]].