Název předmětu

• Stránky předmětu: http://oi-wiki.cz/doku.php/courses/a4m33mpv
• Přednášející: Jiří Matas
• Cvičící: Perďoch

7.6.2010

4.6.2015

1. Bag of words (popis metody, inverted file, tf-idf, …)
2. SIFT descriptor (popis cele metody vcetne normalizaci, navrh na urychleni pomoci integralniho obrazku, …)
3. Navrhnete detektor/tracker pro detekci lidi ve staticke kamere tak, aby nehlasil falesne poplachy na psy a kocky.
4. Popiste postup pri odhadu fundamentalni matice nebo homografie pro par obrazku + reknete vyhody Harrise, Hessiana, MSERu a FASTu.

Bylo by dobré otázky ke zkoušce vypracovat. Není jich mnoho a pokud každý z nás vypracuje 2-3, tak máme hotovo. Připište se prosím každý, kdo má chuť pomoct, k nějaké otázce, vypracujte ji a výsledek poté vložte níže. Díky tomuto seznamu bychom se měli vyhnout tomu, aby dva lidé vypracovávali stejnou otázku. Pokud máte chuť nějakou z vypracovaných otázek opravit / doplnit, hurá do toho.

1. Martin Bresler
2. Jiří Fric
3. Jiří Fric
4. Vitalij Chalupník
5. Michal Uřičář
6. Vogal Martin 2010/06/02 17:12
7. Vitalij Chalupník
8. Vogal Martin 2010/06/03 13:41
9. Vitalij Chalupník
10. Vitalij Chalupník
11. Radek Petráň
12. Radek Petráň
13. Radek Petráň
14. Radek Petráň
15. Martin Bresler
16. Michal Uřičář
17. Michal Uřičář
18. Martin Bresler
19. Martin Bresler
20. Martin Bresler
21. Ondra Fisar
22. Ondra Fisar
23. Ondra Fisar
24. Ondra Fisar
25. Ondra Fisar
26. Martin Zachar
27. Ondra Fisar
28. Michal Uřičář & Martin Zachar
29. Martin Zachar
30. Vitalij Chalupník & Martin Vogal
31. Martin Zachar
32. Martin Zachar
33. Martin Bresler

1. Popište algoritmus detekce Harrisových bodu zájmu. Jaké má tento detektor parametry? Jaký je jejich vliv na pocet odezev (prímo nebo neprímo úmerný)? K jaké tríde geometrických a fotometrických transformací je Harrisuv detektor (teoreticky, odhlédneme-li od diskretizacních efektu) invariantní?

Algoritmus hledá rohové body, které mají velkou změnu intenzity jasu (gradient) ve všech směrech (x,y). K jejich nalezení se používá tzv. autokorelační matice C.

Z této matice se poté vypočítá Harrisova odezva R.

Postup:

• v kazdem bode [x, y] se spočítá derivace podle osy x a podle osy y,
• z toho se sestavi matice C pro konkretni bod [x, y],
• vypočte se R na tom konkretnim bode [x, y],
• a jestli je R dostatecne velke, tak tam bude roh

Vstup:

• x, y - souřadnice bodu

Parametry:

• σi - parametr pro rozmazaní gaussem (nepřímá úměra)
• σd - parametr pro derivaci (neprímá úměra)
• threshold - jaká musí být odezva, aby byl bod prohlášen za Harrisův (nepřímá úměra)
• non-maxima suppression (potlačení nemaximalních odezev) (nepřímá úměra)

Invariantní

• Invariantní k rotaci(geom.)
• Není Invariantní ke změně měřítka(Image scale)(geom.)
• Invariantní k posunu intenzity (fotom.)
• Není Invariantní ke škálování (násobek) intenzity (fotom.)

Z přednášky:

Harris Workflow: (a) - Original picture, (b) - Compute corner response R, © - Find points with large corner response: R > threshold, (d) - Take only the points of local maxima of R, (e) - Finded points

2. Popište výber merítka pomocí Laplaciánu.

Laplace je invariantní vůči záměně souřadnic - to znamená, že (je-li aplikován na vektorové či tenzorové pole), výsledek je opět vektorové či tenzorové pole.

Pointa je taková, že potřebujeme „bezrozměrný“ gradient, abychom docílili invariantní změně měřítka (image scale). Abychom mohli určit měřítko, je potřebné vybudovat tzv. prostor měřítek, tří dimenzionální prostor, v němž dvě dimenze tvoří obrázek (x, y souřadnice) a třetí rozměr měřítko.

Měřítka v jednotlivých dimenzích měníme tak, že vypouštíme určité detaily (Jako bychom zvětšovali pozorovací vzdálenost).

Algoritmus:

Rozdíl v algoritmu vůči předchozí otázce je takový, že výpočet derivace gaussianu provádíme pro „bezrozměrný“ gradient.

3. Popište kroky, jak zobecnit Harrisuv detektor tak, aby byl algoritmus afinne-invariatní.

Aby byl Harrisův detektor affině-invariantní znamená, že by měl být invariatní vůči rotaci a neuniformnímu (nerovnoměrnému) zvětšení. Vůči rotaci, jak známo, Harr. D. invariatní je.

1. Rozpoznat oblasti pomocí harrisova detektoru a vybrat měřítko.
2. Odhadnout tvar pomocí matice druhých momentů gradientu.
3. Normalizovat oblast do kruhové.
4. Pokud vlastní čísla matice druhých momentů gradientu nejsou stejné, pak jdi na krok 2.

4. Definujte, co to je MSER „Maximally Stable Extremal Region“. Popište algoritmus jejich detekce.

Je detektor Maximalně Stabilních Extremálních Oblastí.

Při detekci se sleduje nárůst oblastí v prahovém obraze při zvyšování prahu intenzity. Se stoupající intenzitou se vkládají do obrazu pixely. Spojují se do oblastí, až při maximální intenzitě zůstane jediná oblast. Po čase 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ě.

V obrázku postupně zvýšujeme threshold a tím propouštíme pouze pixely určitého jasu. Při thresholdu 0 je celý obrázek bílý, se zvýšováním thresholdu se objevují tmavé body (lokální minima). Při určité hodnotě thresholdu se lokální minima spojí a uzavřou oblast. S dalším zvyšováním thresholdu obrázek tmavne až je černý.

Množina všech spojených oblastí se nazývá množina maximálních regionů. Množinu minimálních regionů ziskáme inverzí jasu v obrázku.

Implementace:
Pomocí binsort se setřidí pixely podle jasu a v obrázku se označí svým pořadovým číslem - složitost N.
Spustí se union-find algoritmus pro nalezení oblastí.
Celková složitost: N*log(log n)

Vlastnosti:

• invariantní vůči afinní transformaci
  
• covariant with continuous deformations of images
  
• stability - since only extremal regions whose support is virtually unchanged over a range of thresholds is selected.
  
• multi-scale detection - Since no smoothing is involved, both very fine and very large structure is detected.
  

http://cmp.felk.cvut.cz/~matas/papers/matas-bmvc02.pdf

5. Deskriptor SIFT. Popis algoritmu, vlastnosti.

Algoritmus pro detekci a popis (detect and describe) „bodů“ zájmu. Diky svým dobrým vlastnostem je nejčastěji používaným algoritmem pro nalezení lokálních rysů v obraze.

• robustní (i k částečné okluzi)
• invariantní ke změně měřítka, orientace a affinímu zkreslení
• částečně invariantní ke změnám v intenzitě osvětlení
• rychlý (real-time)
• kompaktní

1. Scale-space extrema detection V této fázi se prohledává celý prostor měřítek. Efektivně se využívá funkce DoG (Difference of Gaussian) pro nalezení potenciálně zajímavých bodů zájmu, které jsou invariantní ke změně měřítka a orientace.
2. Keypoint Localization Na pozici kandidátů je proložen detailní model pro zjištění pozice a měřítka. Klíčové body jsou vybírány na základě míry jejich stability.
3. Orientation assignment Ke každému klíčovému bodu je přiřazena jedna nebo více orientací podle lokálních směrů gradientu. Všechny další operace jsou prováděny na obraze transformovaném relativně k přiřazené orientaci, měřítku a pozici každého rysu. Tento krok zaručuje invarianci k těmto transformacím.
4. Keypoint descriptor Výřez se rozdělí do pravidelné mřížky (nejčastěji 4×4) a v každém čtverci se spočítá histogram gradientů vážený jejich velikostí pro 8 orientací. Pro zvýšení robustnosti k nepřesnosti geometrické normalizace se velikosti gradientů váhují okenní funkcí. Dále je každý čtverec mřížky zvětšen tak, aby zasahoval do půlky hrany svých sousedů. Hlasování do binů orientací se provádí lineární interpolací do dvou sousedních binů.

SIFT deskriptor je tedy mřížka 4×4 histogramů orientací (kvantizovaných na 8 binů). Jde tedy o 128 prvkový vektor.

Prezentace o SIFT z MATFYZu

6. Popište deskriptor „Shape kontext“.

Shape kontext je určen k popisu tvarů (shape) které dovolují měření podobnosti a obnovu/znovuzískání korespondenčních bodů. Základní myšlenka je vzít n bodů na obrysech tvaru. Pro každý takový bod pi na tomto tvaru zvažuj n – 1 vektorů získaných spojením bodů pi se všemi ostatními body. Množina těchto všech vektorů je bohatý popis tvaru lokalizovaného bodu, ale až příliš detailní.

Klíčová myšlenka je, že rozdělení přes relativní pozice je robustní, kompaktní a vysoce rozlišující popis. Takže, pro bod pi, hrubý/surový histogram relativních souřadnic zbývajících n - 1 bodů,

je definovaný jako shape kontext bodu pi. Biny jsou normálně brány jako rovnoměrné v log-polar prostoru. Fakt, že shape kontext je bohatý a rozlišující popis (deskriptor) ukazuje obrázek níž, na kterém jsou ukázány shape kontexty dvou rozdílných verzí písmene „A“.

(a) a (b) jsou navzorkované hranové body dvou tvarů. © je diagram log-polar binů použitých k výpočtu shape kontextu. (d) je shape kontext kružnice (modré barvy v obrázku a), (e) je shape kontext diamantu (snad se jedná o ten červený čtvereček v obr. b) a (f) je shape kontext trojúhelníčku (v obrázku b). Je patrné, že zatímco pro (d) a (e) jsou shape kontexty pro dva blízce související body docela podobné, tak shape kontext v obr. (f) je velmi rozdílný.

Nyní aby významný rys byl užitečný, potřebuje splňovat jisté neměnnosti (invariance). Především je nutné, aby byl invariantní k translaci (posunu), scalu (změny měřítku), malým odchylkám a aby závisel na aplikační rotaci. Invariance vůči translaci přirozeně jde k shape kontextu. Scale invariance je zajištěna normalizací všech radiálních vzdáleností průměrnou vzdáleností mezi všemi páry bodů na patřičném tvaru třebaže medián vzdáleností může být také použit.

Kompletní systém, který používá shape kontext na shape matching (machování tvarů) se skládá z následujících kroků:

1. náhodně vyber množinu bodů, které leží na hranách známého tvaru (shape) a další množinu bodů ležících na neznámém tvaru (shape),
2. spočti shape kontext každého bodu nalezených v kroku 1,
3. spoj (match) každý bod ze známého tvaru k bodu na neznámém tvaru, pro minimalizace ceny spojení (cost of matching), vyber prvně transformaci (affine, thin plate spline, etc) která zdeformuje (warp) hrany známého tvaru do neznámého (podstatně vyrovná oba tvary), potom vyber bod na neznámém tvaru, který nejblíže koresponduje se všemi deformovanými body známého tvaru,
4. spočti „vzdálenost tvaru“ (shape distance) mezi všemi páry bodů na dvou tvarech, použij vážený součet vzdáleností shape kontextu, vzdálenost vzhledu obrázku a energie ohýbání (míra jak moc transformace je potřeba na zarovnání obou tvarů),
5. k identifikování neznámého tvaru použij klasifikátor nejbližšího-souseda pro srovnání jeho shape distance k shape distance známých objektů.

Z přednášky:

Literatura: http://en.wikipedia.org/wiki/Shape_context

7. Popište deskriptory typu „Local Binary Patterns“.

V okoli pixelu (ve vzdálenosti R) najdeme P pixelů. A výpočet provedeme podle obrázku níže.

Aby byl tento popis invariantní vůci otočení, zavedeme:

Tedy hledáme nejmenší číslo, které můžeme dostat nějakou cyklickou rotací - což simuluje otáčení obrázku.

LBP rozlišujeme uniformní a neuniformní. Uniformní jsou takové, že musí být max. 2 translace mezi 0 a 1 (mezi dvěmi nulami nesmí být žádná jednička).

Použití:

8. Použití lokálních afinních rámcu pro invariantní popis. (nejsem si jist, zda odpověď koresponduje s otázkou, prosím o úpravu/doplnění)

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.

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. 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.

Orientace dominantního gradientu

Na částečne normalizovaném výřeze 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ňů.

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 variance intenzit jeho rozsahu (případně 2x variance). V případě, že chceme využít všechny tři barevné kanály, normalizujeme každou složku zvlášť.

Citováno z: http://cw.felk.cvut.cz/doku.php/courses/a4m33mpv/cviceni/2_hledani_korespondenci/start

9. Popište, jak lze získat korespondence mezi dvojicí snímku, které se významne liší úhlem pohledu (tzv. „wide baseline matching“)

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.

Epipolární geometrie je reprezentována maticí F, zvanou fundamentální matice. Pro její nalezení je potřebných alespoň 7 korespondujících bodů.

Epipolární geometrie je geometrický vztah korespondujících bodů xl a xr, obrazů bodu ve scéně viděného dvojicí perspektivních kamer:

Viz: http://cw.felk.cvut.cz/doku.php/courses/a4m33mpv/cviceni/2_hledani_korespondenci/start#vzajemna_poloha_dvou_kamer_epipolarni_geometrie

10. Jak lze rychle (sub-lineárne) najít deskriptory, které se sobe podobají?

Pomocí indexace - např. struktura kD-tree.

11. Jak vyhledává podobné snímky metoda „bag of words“?

Skóre rozdílu dvou obrázků je reprezentováno jako velikost kosínu úhlu dvou vektorů, které tvoří četnosti vizuálních slov. Tj. vektor je histogram četností jednotlivých vizuálních slov – např. vektor pro obrázek x je (1,0,2,3,2,1,…), pokud obrázek obsahuje 1*slovo A, 0*slovo B, 2*slovo C, atp.

Vztah pro kosinus (je stejný jako z TZ):

Výpočet lze zrychlit zavedením koeficientů α,

Hlavní rys této metody: Nezohledňuje pozici jednotlivých bodů zájmu (slov) v obraze – dává je všechny na jednu hromadu a pouze počítá s jejich četnostmi.

Nezahrnuje tedy mechanismy „spatial verification“ (prostorového ověření) zda nalezená slova jsou v nalezených obrazech ve stejných „vztazích“.

12. Využití tzv. „inverted files“ pro rychlé vyhledávání obrázku.

Máme matici obrázků spolu s četnostmi vizuálních slov, ve které potřebujeme rychle vyhledávat. Pro efektivní vyhledávání je třeba dostat vizuální slova (A,B,C, …) a k nim seznam obrázků, ve kterých se vyskytují spolu s četností, tj. pouze seznam obrázků, kde je jejich četnost alespoň 1. Tuto strukturu můžeme dostat jako tzv. sparse matici - „sparse matrix“ (více na wikipedii). V MATLABu je na to vytvořená funkce »sparse(A).

13. Definujte tf-idf váhu vizuálního slova.

TF-IDF(term frequency–inverse document frequency)

Tato váha slouží k potlačení nedůležitých vizuálních slov. Alternativa k vyhledávání v textu, kde jsou nedůležité spojky a předložky.

Spočítá se jako logaritmus podílů počtu dokumentů a počtu dokumentů, ve kterých se slovo nachází. Tj. v čím více dokumentech se slovo nachází, tím menší bude jeho váha, naopak pokud je slovo jen v jednom dokumentu pak je jeho váha největší. Vážený histogram vizuálních slov tak má pak lepší výsledky protože potlačuje nevýznamná vizuální slova. (více na wikipedii)

14. Popište mechanismus „query expansion“ pro zvýšení úspešnosti vyhledávání.

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. Abychom 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élníku 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í slovo z každého obrázku s četností 100, budeme s ním mít problém při hledání korespondencí) proto je seřadíme sestupně podle tf a vybereme prvních max_qe.(citováno ze stránek cvičení)

Krok po kroku:

1. Provedu běžné vyhledávání.
2. Spatial verification – najdu transformaci z výsledku do původního obrazu a zobrazím všechny inliery z nalezeného obrázku do původního (query image). Ty, které padnou do vyhledávacího dotazu (obdélníku), přidám do query a vytvořím tak rozšířený (extended) dotaz.
3. Provedu vyhledávání s rozšířeným dotazem

15. Definujte, jak popisuje obrázky metoda min-Hash. Jaké má vlastnosti?

Metoda min-Hash definuje obrázky pouze pomocí několika relativně málo „náhodně“ vybraných vizuálních slov. Metoda se používá k nalezení podobných obrázků (zobrazujících stejný objekt) ve velkých databázích. Řekněme, že funkce m(Ii) je funkce, která vybírá z množiny vizuálních slov I obrázku i jedno vizuální slovo. Tento výběr může být proveden různě, ale musí více či méně platit:

Tato pravděpodobnost se označuje jako podobnost obrázků a značí se také jako sim(I1,I2).

My podobnost obrázků ale neznáme a naopak je naším cílem ji zjistit, abychom podle ní mohli seřadit obrázky během vyhledávání v databázi. Podobnost dvou obrázků získáme tak, že vybereme opakovaně pomocí funkce m vizuální slovo z množiny I1 a I2. Pokud to provedeme s-krát, získáme s-tici min-Hashů, která se nazývá sketch. Celý proces budeme opakovat a získáme k sketchů. Na obrázku níže je rovnice, která vyjadřuje pravděpodobnost, že alespoň v jednom sketchi budou vsechny min-Hashe totožné. My tuto pravděpodobnost ale známe (získáme opakovaným porovnáváním získaných sketchů) a naopak dokážeme vyjádřit snadno hledanou podobnost obrázků.

Ukazuje se, že i pro poměrně malé s se odhadnutá podobnost příliš neliší od skutečné. Ke zlepšení výsledku je možné využít ovážení vizuálních slov (často vyskytované budou mít menší váhu, nebo je funkce m nebude vůbec vybírat).

Vlastnosti:

• kompaktní - lze využít pro velmi velké databáze
• rychlé - lineární závislost na výstupu
• podporuje rozeznání i malých objektů
• přesné

16. Popište algoritmus RANSAC. Jaké má vlastnosti (výhody, nevýhody)? Jaké má parametry?

RANSAC (Random Sample Consensus)

Iterativní metoda pro odhad parametrů matematického modelu z pozorovaných dat zatížených šumem (obsahujicích outliery).

Je to randomizovaný algoritmus, funguje s ohledem na míru spolehlivosti.

1. inicializuj hodnotu maximalního počtu iterací nutných k nalezení modelu s určenou spolehlivostí (niter)
2. i = 0
3. Dokud i < niter:
4. Náhodný výběr vzorku m bodů (m je počet bodů charakteristický pro daný model - např. 2 pro přímku, 3 pro kružnici, atd.)
5. Výpočet parametrů modelu, který „sedí“ na vybraný vzorek.
6. Výpočet odchylky všech bodů od modelu
7. Výpočet podpory (inlierů, tzn. bodů, které podporují tento model), pokud je nový model lepší než doposud nalezený, ulož jeho parametry a přepočítej (sniž) maximální počet iterací (niter)
8. Zvyš číslo iterace i a opakuj výběr vzorku

Výhodou RANSACu je schopnost robustního odhadu parametrů modelu (i přes relativně vysoký počet outlierů dosahuje vysoké spolehlivosti)

Nevýhodou je absence horní meze časové složitosti. Dále korektnost výsledků (degenerace) a přesnost (model je odhadován z minimálního vzorku)

• N - Počet bodů
• I - počet inlierů
• m - velikost vzorku pro odhad modelu
  • p - požadovaná spolehlivost (např. 0.95)

17. Popište nejaké moderní vylepšení metody RANSAC (WaldSac, PROSAC).

Vzhledem k vysoke časové složitosti RANSACu bylo vyvinuto několik vylepšení:

SPRT (Sequential Probability Ratio Test)

Optimální test, který zajišťuje s pravděpodobností \alpha, že hypotéza „správného“ modelu nebude mylně zamítnuta.

Spočítá se věrohodnost .

Je-li \lambda_i > A, model je zamítnut. Je-li i = N, model je přijat za „dobrý“.

Důležité vlastnosti SPRT:

1. pravděpodobnost zamítnutí „dobrého“ modelu je \alpha < 1/A
2. Průměrný počet verifikací V = C log(A), kde C je

WaldSAC

Opakuj k/(1 - 1/A) krát:

1. Sestavení hypotézy
2. Verifikace modelu (použití SPRT)

WaldSAC dosahuje oproti klasickému RANSACu významného zrychlení. Zhruba 3x u wide-baseline matching a 9x u narrow-baseline.

PROSAC (Progressive Sample Consensus)

Využívá faktu, že ne všechny korespondence jsou vytvářeny rovnocenně.

Vzorky jsou vybírání semi-náhodně z progresivně se zvětšující množiny tentativních korespondencí. Zvýšení efektivity spočívá na slabém předpokladu, že tantativní korespondence s velkou similaritou mají velkou pravděpodobnost, že jsou inliery.

PROSAC může dosahovat zrychlení oproti klasickému RANSACu v řádu až 10^2. V nejhorším případě bude PROSAC dosahovat stejné efektivity jako RANSAC.

18. Popište strukturu detekce objektu typu „scanning windows“ („sliding windows“). Jak je dosaženo jejich přijatelné rychlosti?

Při detekci objektů metodou „scanning windows“ se vyhodnocují všechny možné výřezy obrázku a testuje se, obsahují-li hledaný objekt. K testu, jestli výřez obsahuje hledaný objekt, se používají učící se klasifikátory. Tento proces je z principu velmi časově náročný z následujících důvodů:

• možných výřezů je enormě hodně
• vyhodnocovací funkce klasifikátoru je velmi složitá

Algoritmus Viola-Jones řeší tento problém v reálném čase. K tomu využívá následujících fintiček:

1. Sekvenční rozhodování

Většina výřezů objekt neobsahuje, proto je výhodné se na místo hledání výřezu s objektem zaměřit na vyškrtávání výřezů, kde objekt jistě není. Na tomto principu lze vystavět kaskádu velmi jednoduchých klasifikátorů (postupně se zesložiťujících), které postupně odfiltrovávají výřezy, které nemají šanci. Takže každý následující klasifikátor pracuje s méně daty. Viz obrázek:

2. Bootstrap

Každý klasifikátor se učí pouze na datech, která se k němu dostanou skrz kaskádu předcházejících filtrů.
→ Na začátku mohu do kasakády natlačit mnohem více dat a učení bude pořád dostatečně rychlé → více trenovácích dat znamená lepší klasifikátor

3. Rychle vyčíslitelné příznaky

Jako příznaky se používají rozdíly jasů. Dříve se používaly hladké funkce - např. rozdíly Gaussianů nebo Gaborovy filtry.
Jejich vyčíslení je ale pomalé, proto V-J používá např. Haarovy wavelety - po částech konstantní funkce.
- jsou jen o málo méně přesné, ale jejich použití je mnohem rychlejší

4. AdaBoost

• Teoreticky podložený (dobrá generalizace)
• Velmi malá chyba v mnoha aplikacích
• Velice jednoduchý(“just 10 lines of code” [R. Schapire])
• Sám vybirá jednotlivé slabé klasifikátory

19. Ukažte, jak lze s výhodou využít integrálního obrázku pro výpočty součtu jasové funkce v obdélníkové oblasti.

V-J algoritmus potřebuje vypočítat součet hodnot jasů jednotlivých pixelů obrázku v určitém výřezu. K tomu lze využít integrální obrázek, který se vypočítá jendou na začátku a poté ho lze s výhodou použít. Nejprve si ukážeme, jak integrální obrázek vypadá:

Význam písmenek v rovnicích (kdyby to nebylo jasné): i - hodnota jasu v obrázku, ii - hodnota v integrálním obrázku, s - hodnota řádkového součtu
→ nejprve se spočítají řádkové součty a potom integrální obrázek (řádkové součty a z toho sloupcové součty)

Pokud tedy chceme vypočítat součet hodnot jasů v obdelníku na obrázku

stačí nám 3 sčítání: sum = A –B –C + D

POZOR: je to trošičku jinak, než je zde uvedeno (proto uvádím, jak to má být):

Chceme spočítat sumy jasu vyznačené modrou oblastí v původním obrázku. Proměnné A, B, C, D jsou označeny modrými čtverečky v integrálním obrázku. Problém byl v tom, že ta oblast je nutno zvětšit o 1 nahoru a doleva. Pak tedy platí v jedničce 21 - 11 - 11 +4 = 3 a ve dvojce:11 -2 -2 +0 = 7 .

Proměnné A, B, C a D představují hodnoty v integrálním obrázku.

20. Proc je v metodách „sliding windows“ používán typicky klasifikátor naučený metodou Adaboost? Uveďte více jak jeden důvod!

• Je velmi jednoduchý a přínáší velmi malou chybovost.
• AdaBoost je sám o sobě založen na složení silného klasifikátoru z mnoha slabých. To je přesně princip, který je v algoritmu V-J (Viola-Jones) zapotřebí → AdaBoost sám vybírá slabé klasifikátory (jaký Haarův wavelet se použije) do kaskády klasifikátorů.
• AdaBoost je teoreticky podložený, což představuje dobrou generalizaci.
• Jako příznak se nemusí používat jenom Haarovy wavelety, ale existuje např. LBP (Local Binary Patterns) - dobré pro detekci obličejů, apod.. V AdaBoostu je možné kombinovat různé typy příznaků, což je nespornou výhodou.

21. Popište algoritmus detekce parametrizované struktury (přímka, kružnice s daným poloměrem) pomocí Houghovy transformace (HT). Diskutujte vlastnosti algoritmu (časová a pametová nárocnost, volba parametru).

Houghova transformace je metoda pro nalezení parametrického popisu objektů v obraze. Při implementaci je třeba znát analytický popis tvaru hledaného objektu. Proto je tato metoda používána pro detekci jednoduchých objektů v obraze jakou jsou přímky, kružnice, elipsy. Hlavní výhodou této metody je robustnost vůči nepravidelnostem a porušení hledané křivky.

Workflow:

1. definuj parametry hledaného objektu ( přímka: fi, r kružnice: x, y, r )
2. rozděl Houghův prostor: pro každý parametr urči meze a prostor rozděl do určeného počtu buněk
3. vytvoř akumulátor A(fi, r) a nastav vše na 0
4. pro všechny vstupní body: pro každý možný model objektu (určený parametry) zahlasuj do akumulátoru.
5. vyber z akumulátoru takovou sadu parametrů, která má největší počet hlasů (pro redukci rušení se příspěvek připisuje i do okolních buněk)

Paměťová náročnost = jedinou paměťově náročnou proměnnou je Akumulátor, ten rapidně stoupá s počtem parametrů

Časová náročnost = podle wikipedie by mělo být , kde A je plocha obrazu a m je počet parametrů objektu

Houghova transformace na wikipedii

22. Porovnejte HT a prohledávání prostoru všech hledaných struktur hrubou silou.

Nevim jestli to je dobre … jenom intuice co znamena to prohl….. hrubou silou Tak jestli dobre chapu to „prohledávání prostoru všech hledaných struktur hrubou silou“, tak se jedna o to ze zkusim kazdy mozny model (nezavisle zdali je jeho soucasti alespon jeden bod) a hledam pocet bodu,ktere do tohoto modelu padne. Zase musi prijit v uvahu kvantizace (jinak by bylo nekonecne modelu). Je urcite narocnejsi nez HT, jelikoz prohledava cely Houhguv prostor, kde hleda inliery. Naproti tomu HT vychazi z bodu,tzn. uz minimalne jeden bod do tohoto modelu patri.

Podle me jde spis o to, ze zatimco u hrube sily je potreba vyzkouset vsechny moznosti (ale samozrejme jen ty smysluplne, nebudu prece zkouset primku kilometr daleko od jakehokoliv bodu), tak HT je v podstate reseni analyticke = znam analyticky popis hledaneho objektu a pro kazdy bod jen vykreslim FUNKCI, ktera ho zobrazi do Houghova prostoru. Tam uz jen hledam kolize, tj. nejvyssi naakumulovanou hodnotu. — Petr Kubizňák 2012/06/02 23:48

23. Porovnejte HT a RANSAC.

výhody

• velice efektivní pro rozpoznávání libovolných obrazců a objektů
• vypořádá se s velkým procentem out-lierů (95%)
• vytáhne seskupení ze změti v lineárnim čase

nevýhody

• problém kvantizace
• použitelné pouze pro modely s parametry do dimenze 4

výhody

• obecný algoritmus použitelný pro širokou množinu problémů
• jednoduchý na implementaci
• nazávislý na dimenzi parametrů modelu.

nevýhody

• schopný pracovat pouze s průměrným počtem out-lierů (50%)

24. Uvažujte problém nalezení malé cásti obrazu v obraze (patch matching). Navrhnete nekolik možných kriteriálních funkcí a diskutujte je z hlediska nárocnosti, direncovatelnost a pod.

• NCC - normalised cross correlation - neni konvexni, dobra rozeznatelnost, efektivni vypocet, nezavislost na rozsireni a posunu jasu, nejnarocnejsi casove

,where I is the image, T is the template and top left corner of Template lies on pixel (x,y).

• SSD - sum of squared differences - vetsi citlivost nez SAD, zavislost na rozsireni jasu (I = a*I'), nezavislost na posunu, zlaty sred

• SAD - sum of absolute differences - rychlejsi nez SSD, zavislost na rozsireni jasu (I = a*I'), nezavislost na posunu, nejmene narocny (pouzivany na mobilech)

25. Uvažujte statickou scénu pohyb kamery pouze v horizontálním smeru. Nacrtnete cást obrazu (image patch) který bude použitelný pro gradientní metody sledování (napr. KL tracker). Jaké vlastnosti by taková cást obrazu mela mít, aby byla dobre sledovatelná.

Jestli ze je pro nas fakt pohybu pouze v horizontalnim smeru znamý, pak by stacilo aby patch obsahoval svislou hranu, diky cemuz jsme schopny zjistit posunuti v sirce ( hloubka a vyska by meli zustat stejny).

26. Uvažujme gradientní metodu sledování, (napr. KL tracker). Jaké obrazové cásti (patches) jsou vhodné pro sledování? Proc? Jaké jsou naopak nevhodné, nebo nelze je sledovat vubec?

Jedná se o podobný problém jako u Harrisova detektoru.

U KLT hledáme posun:

Kde matice H je dána jako

Ze vzorečku je vidět, že záleží na inverzi hessiánu. Chceme, aby jeho vlastní čísla byla větší než zadané minimum (aby byla přibližně stejně velká, ale dostatečně velká).

Mějme tedy daný posun a dosaďme jej do matice. Z výsledku je vidět, že chceme mít různé derivace v obou směrech, což je obdoba Harrisova detektoru. Nechceme mít degenerovanou matici. Potřebujeme mít takovou, která má plnou hodnost. Chceme tedy oblasti s rohy. Nehodí se nám oblasti s hranami, které způsobí nestabilitu. A už vůbec se nám nehodí (nelze je sledovat vůbec) homogenní oblasti (flat areas).

27. Mean-shift algoritmus. Popište princip a vypočtěte praktický příklad . . . (1-D príklad s konkrétními císly).

tak,kdyz se k tomu nikdo nema … ale nedavam zadnou zaruku

Tzn. cilem algoritmu je nalezt „nejhutnejsi“ misto, tj misto kde je nejvice bodu v okoli.

1. Algoritmus zacne na nejakym miste
2. Spocita prumernou hodnotu ve svem okoli (dano okeni funkci .. gauss, flat … )
3. Do vypoctene hodnoty se posune.
4. Pokud posun presahnul urcity prah, pokracuje bodem 2. jinak konci

vypocet noveho stredu:

jinak, dle slidů: Pro obecný kernel K je odhad hustoty v bode x, kde h je šírka (bandwidth) kernelu a x1…n jsou vzorky.

where, given n data points xi in d-dimensional space R^d.

iterace algoritmu:

28. Mean-shift algoritmus. Barevné pixely [R, G, B]^T mužeme reprezentovat v 3-D prostoru. Jak byste provedli redukci do prostoru 256 barev? Mean shift muže najít shluky bodu. Jaké základní parametry je nutné nastavit algoritmu a jak ovlivní výstup algoritmu?

Warning - Informace v teto otazce muzou byt zatizeny chybou BO, proto ji berte s rezervou

Redukce do prostoru 256 barev

Vypočtené středy (mean-shift) kvantizujeme tak, aby patřily do zadaného prostoru (každá barva 8 bitů).

Jinak (ze zkoušky se ukázalo, že tudy cesta bohužel nevede):

Sestavme si z obrázku RBG graf, jako je na obrázku níže:

Potom v něm našli 256 různých shluků (zjistíme nejčastějších 256 barev), což by tvořilo tu segmentaci do prostoru 256 barev.

Vycházeli jsme z: http://cmp.felk.cvut.cz/cmp/courses/ZS1/Cviceni/cv4/meanshift.pdf

Základní parametry algoritmu

• Okenní funkce (jádro, velikost)

29. Vysvetlete princip duležitostního vzorkování (importance sampling). Predpokládejte, že máte k dispozici generátor rovnomerného rozdelení. Znáte datový vektor (vzorky-samples) x = [x1, x2, . . . , xn]^T a asociovaný vektor vah (pravdepodobností) w = [w1,w2, . . . ,wn]^T. Požadovaným výstupem je datový vektor xis délky n obsahující prvky z x tak, že cetnost výskytu bude úmerná váze (duležitosti) vzorku.

Sestavíme si graf distribuční funkce pravděpodobnosti, kde na horizontální ose máme vzorky (x1, x2, …, xn), na vertikální ose je vždy součet pravděpodobností předešlých vzorků plus aktuální. Vznikne tak neklesající funkce.

Poté „střílíme“ čísla on nuly do jedné s rovnoměrným rozdělením od vertikální osy. Narazí nám na graf funkce (čáru). Vezmeme vzorek, který je nejbližší vyšší od nárazu (viz.: http://cmp.felk.cvut.cz/cmp/courses/a4m33mpv/Videos/impsampl.avi). Ten uložíme do xis. Takto střílíme n-krát.

Obr. z VIDEA:

30. Objekt je reprezentován barevným histogramem (3-D histogram barevných kanálu). Navrhnete alespon jednu metodu, jak porovnávat oblast v obraze s objektem. Za další metodu mužete získat extra bod.

Idea:

Využijeme znalosti segmentace barevných (RGB) obrazů. Tento obrázek (bílá ovce na zelené louce) si rozdělíme do dvou tříd, tj. například budeme hledat oblast v obraze odpovídající nějakému objektu (ovce) a jeho pozadí.

Jednu třídu již máme zadanou barevným histogramem a to objekt (ovci). No a druhou třídu, tedy oblast (kterou můžeme buď dostat na vstupu a nebo postupně prohledávat celý obrázek například okenní fcí), máme také, tedy si z této oblasti zjistím jeho barevný histogram a oba dva pak porovnám a pokud míra shodnosti obou histogramů překračuje nějaký threshold, našli jsme objekt, pokud je míra menší než threshold, hledáme na jiné oblasti.

31. Obraz o rozmeru 256×256 pixelu (míst-sites), každý z nich muže nabývat 4 hodnot jasu (znacek-labels). Kolik existuje ruzných oznackování (labelings)?

4^(256×256)

32. Problém segmentace obrazu. Jasová hodnota pixelu i (znacka) fi závisí i na dalších pixelech, tedy P(fi|fS−{i}) != P(fi). Zformulujte podmínku pro to, aby P(fi|fS−{i}) bylo Markovské pole.

Teoreticky by mělo stačit jen

Kde {f_i'} je sada dalších labelů.

Popřípadě:

Kde f_N_i jsou labely v okolí pixelu i.

Nejsem si tím ale moc jistý. Je to jen můj nástřel.

33. Predpokládejme, že znackování je reprezentované sdruženou pravdepodobností P(f) = Z−1 e−U(f) , kde Z = X f2F e−U(f) je normalizacní koeficient. Hledáme znackování s nejvetší pravdepodobností P(f). Energii U(f) uvažujeme ve tvaru U(f) = Udata(f) + Usmooth(f) Navrhnete vhodnou energetickou funkci Udata(f) reprezentující shodu pixelu s modelem a energetickou funkci Usmooth(f) reprezentující skutecnost, že hodnoty pixelu závisí na nejbližším okolí a že objekt má obvykle urcitou velikost a kompaktnost.

Udata(f) se označuje jako „data term“ a vyjadřuje, jak dobre sedi label fp pixelu p. Přitom nehledí na labely v okolí. Data term je vyjádřen funkcí Dp, která může být např. následující:

Usmooth(f) se označuje jako „smoothness term“ a vyjadřuje naopak závislost labelu fp na okolních labelech. Smoothness term je vyhádřen pomocí funkce V, která představuje penalizaci, pokud se sousední labely fp a fq nerovnají. Výjádření smoothnes termu vzorečkem:

Penalizační funkce může být různá a velikost penalty nám ovlivní kompaktnost objektů - čím větší, tím bude objekt kompaktnější. Dovolil bych si sem vložit celý slajd o výběru penalizační funkce, což bude asi nejlepší.