Non Parametric Sampling - první verze

Po dohodě s vedoucím své práce jsem začal s patrně nejjednodušší úlohou – non parametric samplingem. Nebudu rozebírat, jak funguje (článek je volně k dipozici), ale rovnou se zaměřím na výsledky.

Nejprve jsem se snažil celý problém uchopit z hlediska správného (tj. hezky pěkně strukturovaného a modulárního :)) návrhu a prakticky všechno, co šlo, zapouzdřit do vlastní třídy. Jenže u téhle aplikace by mělo jít v první řadě o rychlost, takže tenhle přístup se po prvním testování ukázal jako ne úplně použitelný.

Samozřejmě jsem na OOP zcela nerezignoval, ale výsledkem je de facto jediná třída Solver, která zapouzdřuje celý problém. Uchovává si informace o jednotlivých pixelech (RGB, 8 bitů na barvu) a zároveň si vnitřně spravuje bitové masky jednak pro díry a "dvak" pro zakázané oblasti (resp. jejich doplňek). Pro správu bitových masek jsem použil třídu dynamic_bitset z knihovny boost, která celou věc zjednodušuje, šetří místo a hlavně je rychlá.

V rychlosti ještě zmíním některé detaily implementace. Pro vytvoření instance solveru je třeba znát rozměry zkoumaného obrázku a rozměry kontextového okna (což musí být liché číslo) jsou inicializovány příslušné datové struktury pro obrázek a obě bitové masky. Všechna dvourozměrná pole jsou implementována jako ukazatele na ukazatele (k jednotlivým prvkům se tedy přistupuje přes indexy [řádek][sloupec]). Při zadávání děr (tj. míst k řešení) do obrázku jsou automaticky aktualizovány maska děr (jedničkový bit → díra; nulový bit → známý pixel) i maska zakázaných, resp. povolených pozic (jedničkový → validní pozice; nulový → zakázaná pozice).

Validní pozice jsou takové pozice, ve kterých má klouzavé okno pohybující se postupně obrázkem zajištěno, že vždy všechny pixely v něm budou známé. To eliminuje jednak pixely u kraje obrázků a dále ty v okolí děr. Proto pak není při porovnávání jednotlivých pixelů klouzavého okna a okna okolo aktuálně zkoumaného pixelu (dále referenční okno) testovat pozice v klouzavém okně ani to, zda náhodou neobsahují díru. Také pozice v referenčním oknu lze otestovat pouze jednou na začátku (před zkoumáním všech validních pozic) a pak porovnávat pouze ty, které leží v obrázku a ne v díře.

Ještě bych zmínil, že při počítání chyby mezi okolím klouzavého a referenčního okna používám přenásobení dvoudimenzionálním gaussovským jádrem (GJ), a to kvůli zvýraznění významu lokálního okolí zkoumaného pixelu (viz odkazovaný článek). To samozřejmě také přináší jisté zpomalení a zatím se mi nepodařilo na testovaných datech úplně odhadnout, jestli to tam má smysl nechávat.

K výsledkům... Pochopitelně se zvětšující se velikostí obrázku, díry nebo velikosti klouzavých a referenčních oken dost podstatně stoupá čas výpočtu. Ještě podotknu, že všechny uváděné časy byly měřeny pro release build ve Visual Studiu 2010 s plnou optimalizací (tedy, myslím to nastavení v MSVS 2010, ne že bych to ještě nějak zkoušel vylepšovat).

Výsledné obrázky uvádím vždy jako trojici, kde první obrázek je původní obrázek, druhý obsahuje definované díry (černá místa) a zakázané oblasti (šedá místa) a třetí je výsledný obrázek získaný algoritmem.


Odstranění ptáčka – rozlišení 400×276 px; oblast 24×26 px; velikost okna 13 px; GJ zapnuté; doba výpočtu 69 s.

Jak vidno, rychlost není závratná. I při takovémto rozlišení obrázku totiž na každý z 624 doplňovaných pixelů připadne 101 064 porovnání a každé takové porovnání obnáší porovnávání dalších pixelů mezi sebou (teoreticky až 13×13 − 1) a každé takovéto porovnání přináší další odčítání a umocňování pro každou ze tří barevných složek.


Cihlová zeď 1 – rozlišení 200×200 px; oblast 32×32 px; velikost okna 9 px; GJ zapnuté; doba výpočtu 18 s.

Okno o velikosti 9 px v tomto případě evidentně nestačí na dostatečné zachycení struktury textury.


Cihlová zeď 2 – rozlišení 200×200 px; oblast 32×32 px; velikost okna 17 px; GJ zapnuté; doba výpočtu 59 s.

Tak tady je něco špatně – okno o velikosti 17 pixelů a pořád takové artefakty? Zkusme "vypnout" gaussovské jádro:


Cihlová zeď 3 – rozlišení 200×200 px; oblast 32×32 px; velikost okna 17 px; GJ vypnuté; doba výpočtu 49 s.

To už je lepší. Kromě zrychlení došlo i ke zlepšení kvality výstupu. Pro další pokusy ho tedy jádro prozatím nechám vypnuté.


Dav – rozlišení 360×215 px; oblasti 13×15, 17×19 a 15×21 px; velikost okna 11 px; GJ vypnuté; doba výpočtu 39 s.

Na první pohled je všechno relativně v pořádku, ale při bližším pohledu na inkriminovaná místa už je vidět, že tento typ obrázků asi nebude úplně vhodný. Ostatně, když jsem zkoušel experimentovat s velikostí okna, kvalita výstupu zůstávala přibližně stejná (tj. nízká).


Krajina – rozlišení 400×320 px; oblast 44×44 px; velikost okna 9 px; GJ vypnuté; doba výpočtu 92 s.

Výsledek není špatný, ale něco tomu chybí. Zvětšení okna by sice nejspíš výsledek o něco zlepšilo, ale při této velikosti obrázku už by to trvalo neúměrně dlouho.

Všechny testy jsem spouštěl na počítači s procesorem Intel Core i5 460M s frekvencí 2.53 GHz.

Resumé

Na začátek jsem implementoval základní verzi NPS porovnávající každý hledaný pixel se všemi "validními pixely". Takové řešení sice poskytuje určité výsledky, ale pro praktické použití je příliš pomalé.

V další fázi se proto zaměřím na implementaci optimalizací navržených vedoucím:

  1. Pokusím se zjistit, v jak velkém okolí hledaného pixelu má smysl prohledávat. Lze předpokládat, že takové postačující okolí bude řádově menší než celý obrázek.
  2. Prohledávat nejprve ve zmenšeném obrázku a získaný výsledek použít k nalezení konečného výsledku v původním obrázku.
  3. Případně obě metody zkombinovat.

Kódy

  • NPS.rar – solution pro MSVS 2010

napsáno 23. 2. 2011 | naposledy změněno 27. 2. 2011 | 15009× okometováno | ↑ nahoru

Komentáře