Na předchozích cvičeních jsme hledali korespondence mezi dvojicemi obrázků. Slabší stránkou metody, kterou jsme si zkusili je v její kvadratické složitosti v počtu obrázků. V aplikacích počítačového vidění často vyvstává podobný problém tzv. image nebo object retrieval – najít obrázek ve velké množině obrázků. Naivní přístup vyzkoušení všech možných párů je mnohdy nepraktický svou složitostí. Navíc množina podobných obrázků může tvořit je velmi malou část celé databáze obrazků. Bylo tedy potřebné vyvinout metody jež jsou rychlejší a efektivnější.

Jedna z metod rychlého vyhledávání ve velké množině obrázků je metoda vizuálních slov (bag of words, visual vocabulary). Její základní myšlenkou je reprezentovat každý obrázek v databázi množinou tzv. vizuálních slov. Vizuální slovo si můžeme představit jako reprezentanta nějakého často se vyskytujícího výřezu obrázku. S dostatečně obecnou množinou vizuálních slov můžeme podobně jako dokumenty v jazyce reprezentovat jakýkoliv obrázek.

Na minulých cvičeních jsme obrázek po nalezení záchytných bodů, geometrické a fotometrické normalizaci výřezů reprezentovali množinou popisů ve vysokodimenzionálním prostoru popisů. Vizuální slova budeme vybírat právě v tomto prostoru. Každý popis si v něm můžeme představit jako jeden bod. Výběr slov provedeme metodou kvantizace vektorů, budeme se snažit nalézt pro každý shluk popisů – bodů prostoru jedného reprezentanta, vektor jenž nazveme vizuální slovo. Z mnoha metod vektorové kvantizace si zkusíme jednoduchou metodu, k-means.

Jedna z nejjednodušších metod vektorové kvantizace je k-means. Algoritmus znáte z predmětu Rozpoznávání:

1. Inicializace, vybereme předem daný počet <latex>k</latex> “středů” shluků (červené křížky v obrázku). Můžeme zvolit náhodný body z množiny popisů nebo použít sofistikovanější metodu, která po výběru prvního bodu v každém dalším kroku přidá nejvzdálenější. Smyslem inicializace je zvolit také body, které nezaniknou hned v první iteraci, abychom jejich výběr nemuseli hned opakovat.
2. Přiřazení všech bodů k nejbližšímu shluku, nám rozdělí body do <latex>k</latex> tříd.
3. Posunutí středů do těžišť tříd. Spočítáme těžište každé třídy bodů a dostaneme novou pozici středu. V případě, že některý střed nemá přiřazené žádné body, vygenerujte mu novou náhodnou pozici, třeba

Kroky 2 a 3 opakujeme dokud se mění přirazení bodů v kroku 2, nebo pokud změna celkové vzdálenosti bodů od jejich nejbližšího středu klesně pod nějakou hranici.

Naprogramujte jednoduchou metodu vektorové kvantizace.

• napište funkci [idxs, dists]=nearest(means, data), jež nalezne ke každému sloupcovému vektoru v matici data (typu DOUBLE rozměru DxN, kde D je dimenze prostoru popisů a N je počet bodů) nejbližší vektor z množiny means (typu DOUBLE rozměru DxK, kde K je počet středů). Výstupem funkce budou indexy idxs (matice 1xN) nejbližších středů a dists (matice 1xN) vzdálenosti k nejbližšímu středu.
• napište funkci [means, err]=kmeans(K, data), která nalezne K středů means v prostoru vektorů data a vrátí celkovou vzdálenost err, sumu vzdáleností bodů data od nejbližších středů.

Kdybychom chtěli použít funkce kmeans a nearest k reprezentaci obrazku pomocí vizuálních slov, postupovali by jsme následovně. Pomocí funkce detect_and_describe spočteme s jedním nastavením popisy obrázků, nastavte parametry tak, aby jsme měli průměrně asi 2000 až 3000 popisů na obrázek. Aplikujeme na všechny popisy funkci kmeans a najděme 5000 středů shluků. Středy shluků – vektory v prostoru popisů očíslujeme a ich indexy – vizuální slova použijeme k reprezentaci popisů v obrázku. Množinu vektorů se středy shluků nazýváme vizuální slovník. Pro indexaci obrázků teď pomocí funkce nearest přiradíme ke každému popisu v obrázku index vizuálního slova a vektor s indexy vizuálních slov reprezentující obrázek i uložime do matice cellů vw{i}. Stejně si uložíme do matice cellů geom{i} pole 6xN_i s parametry rámce záchytného bodu t.j. s řádky [x;y;a11;a12;a21;a22] (ostatní pole struktury pts nebudeme potřebovat), N_i je počet bodů v i-tém obrázku. Pro usnadnění ůloh jsme pro vás taková data pripravili a uložili do archivu k testovacímu skriptu.

Naše obrázky máme po předchozím kroku reprezentovány vektorem vizuálních slov. Spočítáním stejných slov dostaneme vektor – reprezentaci obrázku četnostmi vizuálních slov (viz řádky <latex>\alpha</latex>,<latex>\beta</latex>,<latex>\gamma</latex> na obrázku níž, vlevo). Abychom mohli efektivně vyhledávat v databázi obrázků, budeme potřebovat nějak ohodnotit jejich podobnost. Standardně bychom spočítali vzdálenosti jejich popisů. Při použití metody vizuálních slov ale vektorovou kvantizaci nahradíme vzdálenost mezi popisy dvou obrázků její aproximací, kde vzdálenost 0 bude znamenat, že dva popisy obrázku byly přiřazeny ke stejnému vizuálnímu slovu a nekonečno v opačném případě. Pro obrázky reprezentované vektorem vizuálních slov definujme podobnost následovně

<latex>\displaystyle\mathrm{score}(\mathbf{x},\mathbf{y}) = \cos{\varphi} = \frac{\mathbf{x}\cdot \mathbf{y}}{\|\mathbf{x}\|\|\mathbf{y}\|} = \frac{1}{\|\mathbf{x}\|\|\mathbf{y}\|}\sum_{i=1}^D x_i y_i</latex>,

kde x a y jsou vektory násobností(počtů výskytů) vizuálních slov. Můžeme využít i to, že se část podobnosti dá spočítat předem a znormalizovat velikosti vektorů. Podobnost dvou obrázků pak bude jednoduchý skalární součin vektorů.

Seznam (slovník) vizuálních slov může být velmi dlouhý, často se používá slovník s desettisíci, milionem i více slovy. Aby se zjednodušilo počítání vzdáleností mezi takto dlouhými vektory, používá se tzv. invertovaný soubor. Je to struktura, která pro každé vizuální slovo (A,B,C,D v kroužku) obsahuje seznam obrázků <latex>\alpha</latex>,<latex>\beta</latex>,<latex>\gamma</latex> v nichž se slovo nachází, spolu s jeho násobností.

V Matlabu se tato struktura dá implementovat jako sparse matice. Matlab ale reprezentuje sparse matice jako sloupcové seznamy prvků. Náš invertovaný soubor tedy bude tedy 2D sparse matice, jejíž sloupce bodou vizuální slova a řádky obrázky. Např. třetí sloupec matice bude obsahovat váhy třetího slova v jednotlivých obrázcích. Váhu slova vypočteme z jeho četnosti podělené délkou (velikostí) vektoru vizuálních slov, t.j. odmocninou sumy kvadrátů četností slov v obrázku.

• implementujte funkci DB=createdb(vw, num_words), která spočítá invertovaný soubor DB ve formě popsané výše (sparse matice NxM, kde N je počet obrázků a M=num_words je počet vizuálních slov v slovníku). Parameter vw bude matice cellů 1xN, kde i-ty cell bude obsahovat seznam slov v i-tem obrázku. (tip – použijte funkci sparse Matlabu).

V reálných obrázcích se vizuální slova vyskytují s různou četností, podobně jako v textu, některá jsou častější a některá méně častá. Podobně počet vizuálních slov v obrázku se mění v závislosti na detektoru a komplexnosti scény. Aby se zohlednily tyto rozdíly, zavedeme váhy jednotlivých slov. Jedno z váhování TF-IDF (term frequency–inverse document frequency) je převzato z analýzy a vyhledávaní v textu. Váha každého výskytu slova <latex>\displaystyle i</latex> v obrázku <latex>\displaystyle j</latex> se skládá ze dvou hodnot

<latex>\displaystyle\mathrm{tf_{i,j}} = \frac{n_{i,j}}{\sum_k n_{k,j}},</latex>

kde <latex>n_{i,j}</latex> je počet výskytů slova <latex>i</latex> v obrázku <latex>j</latex>

<latex>\displaystyle\mathrm{idf_{i}} = \log \frac{|D|}{|\{d: t_{i} \in d\}|},</latex>

<latex>|D|</latex> je počet dokumentů a <latex>|\{d: t_{i} \in d\}|</latex> je počet dokumentů, v nichž se vyskytuje vizuální slovo <latex>\displaystyle i</latex>. Pro slova, jež se nebudou nacházet v žádném obrázku nastavíme <latex>\mathrm{idf_{i}}=0</latex>. Výsledná váha slova je

<latex>\mathrm{(tf\mbox{-}idf)_{i,j}} = \mathrm{tf_{i,j}} \times \mathrm{idf_{i}}</latex>

Budeme potřebovat dvě funkce

• funkci idf=getidf(vw, num_words), která spočítá se seznamu dokumentů IDF slov (použijte prirozený logaritmus). Výsledkem bude matice 1<latex>\times</latex>num_words.
• upravte funkci createdb na funkci DB=createdb_tfidf(vw, num_words, idf), která místo četnosti slov spočítá váhy pomocí TF-IDF. T.j. četnosti v každého slova přenásobí IDF slova. Výslednou délku obrázku (vektoru vah vizuálních slov) znormalizujte na 1 tak jako v předchozím případě (kvůli efektivnějšímu počítání podobnosti).

Pomocí invertovaného souboru můžeme přistoupit k vlastnímu seřazení obrázků podle podobnosti s dotazem. Dotaz zadáme výběrem části obrázku, s objektem zájmu. Pomocí obdélníku (viď. funkce Matlabu imrect) a pozic vizuálních slov první dva řádky (x,y) příslušného pole cellů geom vybereme vizuální slova, jenž se nacházejí uvnitř obdélníku. Spočítáme délku a váhy vizuálních slov dotazu a vynásobíme dotaz s příslušními sloupci invertovaného souboru, matice DB, dostaneme matici podobnosti dotazu s obrázkami v databázi.

• napište funkci [img_ids, score]=query(DB, q, idf), která spočítá podobnost dotazu q - seznamu vizuálních slov (1xK matice jejiž prvky jsou indexy vizuálních slov) a obrázků v invertovaném souboru DB. Parametr idf bodou IDF váhy všech vizuálních slov. Výsledkem funkce bude pole score s podobnostmi seřazenými v sestupném pořadí a img_ids, indexy obrázků v sestupném pořadí dle podobnosti.

Očekávame, že odevzdáte funkce nearest.m, kmeans.m, createdb.m, getidf.m, createdb_tfidf.m a query.m spolu se všemi potřebnými funkcemi.

Pro kontrolu správnosti odevzdaných funkcí jsme použili skript a funkci MATLABu publish. Nakopírujte si tfidf_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.

Po seřazení obrázků pomocí podobnosti vektorů vizuálních slov, najdeme množinu obrázků, jenž mají s dotazem některé společné vizuální slova. V ideálním případě dostaneme několik pohledů na tu samou scénu. Z postupu výpočtu vizuálních slov, víme, že popisy použité pro jejich nalezení reprezentují v obrázku časti scény. Proto, na rozdíl od slov v textových dokumentech, mají souřadnice vizuálních slov nalezené v obrázcích (pohledech) jedné scény geometrický vztah určený vzájemnou polohou scény a kamer při jejich získání. Tento vztah můžeme využít pro verifikaci zda nalezené obrázky skutečně odpovídají pohledům na tu samou scénu případně na ten samý objekt.

Při geometrické verifikaci přejdeme nejdřív od podobnosti vizuálních slov k tentativním korespondencím vizuálních slov. Pak použijeme tentativní korespondence pro nalezení geometrické transformací mezi souřadnicemi vizuálních slov v dotaze a každým z množiny podobných obrázků.

Z první fáze algoritmu, seřazení pomocí tf-idf, dostaneme množinu relevantních obrázků. Jsou to obrázky, jenž mají s dotazem několik podobných slov. Pro každý pár tvořen dotazem a relevatním obrázkem vytvoříme tentativní korespondence. Stejná vizuální slova reprezentují podobné popisy, stejných vizuálních slov, ale může být v jednom obrázku více a původní popisy nemáme v dispozici, proto musíme zkusit všechny dvojice. Nechť je tedy v dotaze slovo s četností M a v relevantním obrázku to samé vizuální slovo s četností N, vytvoříme kartézský součin MxN tentativně korespondujících párů (dvojic indexů slov v obrázcích). Takto postupujeme pro všechna společná vizuální slova v každé dvojici obrázků. Může se stát, že stejná slova mají vysoké četnosti (M a N) a jejich kartézský součin by vedl na mnoho párů, z nichž je ale správných maximálně min(M,N). Zavedeme proto dvě omezení na celkový počet tentativních korespondencí na jeden pár obrázků (max_tc) a nejvyšší počet párů (max_MxN). Navíc při zařazování(omezování počtu) tentativních korespondencí budeme preferovat vizuální slova s nižším produktem MxN.

• napište funkci corrs=corrm2m(qvw, vw, relevant, opt), která spočítá páry tentativních korespondencí a uloží je do pole cellů corrs (1xK typu CELL), každý cell bude obsahovat pole 2xT_k dvojic odpovídajících si indexů vizuálních slov (dotazů v prvním a databázového obrázku v druhém řádku). Vstupem bude vektor vizuálních slov qvw (matice 1xQ typu DOUBLE) dotazu; pole cellů vw se seznamy vizuálních slov v obrázcích databáze; matice relavant (1xK typu DOUBLE) se seznamem indexů relevatních obrázků. V struktuře opt budou dvě hodnoty max_tc a max_MxN viď popis výše.

Pro verifikaci tentativních korespondencí budeme potřebovat geometrický model, vztah souřadnic korespondujících bodů. Můžeme podobně jako v předchozí části použít homografii nebo epipolární geometrii. Verifikace tak velkého množství obrázků by ale trvala příliš dlouho, často je totiž v tentativních korespondencích jenom zlomek skutočně odpovídajících si bodů. Proto sáhneme po jednodušším modelu. Využijeme taky skutečnosti, že naše záchytné body nejsou jenom body, ale similaritní nebo afinní rámce. Vzpomeňte si, že rámec nám udává geometrický vztah mezi kanonickým rámcem a obrázkem. Když tedy spojíme transformace z dotazu do kanonického rámce a z kanonického rámce do relevatního obrázku v databázi, dostaneme afinní transformaci (resp. similaritní transformaci) okolí vizuálního slova z dotazu do obrázku v databázi. Samozřejmě skutečná geometrická transformace mezi dotazem a obrázkem databáze nemusí být afinní nebo similaritní transformace. Ovšem za předpokladu, že se jedná o planární objekt, můžeme jí chápat jako lokální aproximaci perspektivní transformace. S dostatečně velkým prahem tak můžeme všechny “přibližně” správně transformované body považovat za konzistentní. Výhodou tohto postupu je jeho rychlost, z jednoho páru korespondujících vizuálních slov dostaneme hypotézu transformace, není potřebné použít vzorkování. Můžeme tak pro každý pár dotaz+databázový obrázek ověrit všechny hypotézy a zapamatovat si nejlepší hypotézu. Její počet inlierů budeme považovat za nové skóre, kterým pak přeuspořádáme relevatní obrázky.

• napište funkci [scores, A]=ransacm2m(qgeom, geom, corrs, relevant, opt), která zjistí počty inlierů a nejlepší hypotézy A, transformace z dotazu do databázového obrázku. Vstupem bude pole qgeom (6xQ typu DOUBLE, kde Q je počet slov v dotazu) geometrií vizuálních slov dotazu, pole cellů geom s geometriemi obrázků v databázi, pole cellů corrs a seznam relevatních obrázků relevant z předchozí funkce. Funkce vrátí v poli scores (velikosti 1xK typu DOUBLE) počty inlierů a transformace A (matice 3x3xK) mezi dotazem a databázovým obrázkem. V struktuře opt bude nastavena hodnota threshold, maximální euklidovská vzdálenost bodu od reprojekce.
• spojte geometrickou verifikaci s tf-idf hlasováním do jediné funkce [scores, img_ids, A]=querysp(qvw, qgeom, bbx, vw, geom, DB, idf, opt), která seřadí obrázky dle počtu inlierů visuálních slov. Výsledkem bude výstup z funkce ransacm2m spojený s výstupem funkce query. Skóre relevatních obrázků bude připočteno ku skóre z funkce query. Transformace A budou pro ostatní obrázky nastaveny na nulovou maticí 3×3. img_ids bude seznam seřazených indexů obrázků podle nového skóre. Vstupem budou parametry popsány výše, s jediným rozdílem, parametry qvw a qgeom bodu obsahovat všechny slova dotazu a obdélník výběru, parametr bbx použijete k jejich selekci. Parametr bbx bude ve formátě [xmin;ymin;xmax;ymax]. Parametr opt bude obsahovat sjednocení parametrů pro funkce ransacm2m a corrm2m, maximální počet obrázků pro geometrickou verifikaci (maximální délka parametru relevant) bude nastaven v poli max_spatial.

(volitelný ůkol za 2 body navíc)

Základní myšlenkou query expansion je využít znalosti geometrické transformace mezi dotazem a obrázkem z databáze, k doplnění množiny vizuálních slov dotazu. Nejdříve musíme vybrat vhodné obrázky z výsledků prvního dotazu. Aby jsme zamezili expanzi nechtěných obrázků, je potřebné vybrat jenom obrázky skutečně odpovídající dotazu. To můžeme zabezpečit výběrem obrázků s dostatečným skóre (např. s nejmíň 10 inliery). Pro každý vybraný obrázek zobrazíme středy jeho vizuálních slov transformací A^-1 a vizualní slova jenž padnou do obdélniku dotazu přidáme k dotazu. Celkový počet vizuálních slov je dobré omezit. Vybereme vizuální slova, jenž nám přidávají nějakou informaci (je zbytečné přidat nejaké vizuální slova s nízkou informační hodnotou, váhou tf-idf, které jen málo ovlyvní skóre ve výsledku) proto je seřadíme sestupně podle tfidf a vybereme prvních max_qe.

• doplňte funkci [scores, img_ids, A]=querysp(qvw, qgeom, bbx, vw, geom, DB, idf, opt) o query expansion. Query expansion se použije když parametr opt.max_qe bude existovat a bude nenulový, ostatní parametry se nemění.

Funkce z části cvičení o hledání ve velkých databázích obrázků kmeans.m, nearest.m, createdb.m, createdb_tfidf.m, query.m, corrm2m.m, ransacm2m.m a querysp.m spolu se všemi potřebnými funkcemi (funkce z prvního cvičení přiložte, jen když jich potřebujete v této úloze) zabalte do archivu a odevzdejte do úlohy 07_spatial.

Pro kontrolu správnosti odevzdaných funkcí jsme použili skript a funkci MATLABu publish. Nakopírujte si spatial_test.zip, rozbalte ho do cesty MATLABu (nebo adresáře s vašimi funkcemi) do adresáře s vašimi funkcemi nakopírujte soubor s mpvdb_haff2.mat, rozbalte archiv s obrázky a spusťte v něm testovací skript. Výsledky, si ověrte porovnáním s referenčním řešením.

Na množine 1499 obrázků (225 vašich obrázků a obrazků vašich kolegů, 73 obrázků pokémonů, 506 obrázků z datasetu ukbench a 695 obrázků z datasetu Oxford buildings) jsme spočítali pomocí detektoru sshessian s baumbergovou iterací (haff2, vrací afinně kovariatní body) záchytné body, odhadli dominantní orientaci a spočítali SIFT popisy. Pomocí k-means (s approximate NN) se ze SIFT popisů spočítalo 50000 středů a přiřadili všechny popisy. Spracované dáta najdete v souboru mpvdb_haff2.mat, pole cellů se seznamy vizuálních slov v proměnné VW a pole cellů s geometriemi GEOM. V proměnné NAMES najdete názvy obrázků. Středy jsou uloženy v souboru mpvcx50k_haff2.mat v proměnné CX. Obrázky si můžete stáhnout zabalené v souboru mpvimgs.zip. Popisy k obrázkům najdete v souboru mpvdesc_haff2.mat, uloženy jako pole cellů DESC s prvky maticemi typu UINT8 rozměru 128xN_i, kde N_i je počet bodů v i-tém obrázku.

Vyberte si 20 obrázků:

• 5 z vaší dátové sady,
• 5 z dátových sad vašich kolegů,
• 5 pokémonů: X=(vaše pořadové číslo na předmětu MPV)-1, vaše jsou obrázky s indexem (2*X+1) až (2*X+5).
• 5 z obrázků datasetu ukbench.

Jejich indexy uložte do proměnné query_id. Přiřaďte popisy pomocí funkce nearest. Na každém obrázku vyberte obdélnik s objektem dotazu (např. pomocí funkce imrect, ale pozor na formát) a uložte jeho souřadnice (ne indexy, levý horní roh má souřadnice 0,0) do sloupce matice query_bbx rozměru 4×20 typu DOUBLE v pořadí [xmin;ymin;xmax;ymax]. Vyberte vizuální slova, jejichž středy se nachází uvnitř obdélniku (vrátaně hranic). Pomocí funkce querysp udělejte dotaz a jeho výsledek (skóre, seznam obrázků a transformace A) uložte do struktury query_results na příslušnou pozici (1..20) do polí score, img_ids, A. Všechny proměnné query_* a proměnnou opt s nastaveními algoritmů uložte do souboru results.mat a odevzdejte do odevzdávacího systému do úlohy 07_results.