Patch Match je randomizovaný algoritmus pro hledání hustých korespondencí mezi dvěma obrazy (ne nutně různými). Jako takový je vhodný nejen pro problém vyplňování děr v obrazu, ale i pro další strukturální změny v obraze (přesun objektů apod.).
Implementované jádro podle článku PatchMatch: A Randomized Correspondence Algorithm.. je napsané jako základní verze tohoto algoritmu. Samotná implementace sestává z několika tříd, které mají za cíl oddělit jednotlivé fáze celého procesu z hlediska jejich funkce. Tyto třídy jsou: Core, IO, Application, Statistics, TimeStamp a ještě pár dalších, které však nejsou příliš důležité. Názvy zmíněných tříd pravděpodobně dostatečně popisují jejich účel (minimálně pro potřeby tohoto příspěvku).
Výsledky a měření a jejich interpretace
Při měření jsem měřil zvlášť jak čas inicializace (vytvoření a nastavení objektu jádra – instance třídy Core, náhodný offset), tak samotné iterace. Počet je vždy uveden u konkrétního obrázku. Výstupem pak je kromě časových údajů čtveřice obrázků. První je původní obrázek, druhý obrázek, ze kterého se samplovaly patche, třetí je obrázek zrekonstruovaný z nejlepších matchů a čtvrtý (černobílý) pak graficky představuje rozdíl mezi hodnotou pixelu na dané pozici v původním originálním obrázku s pixelem se zrekonstruovaného obrázku.
Čím světlejší, tím menší odchylku pixel na daném místě má. Odchylka byla počítána jako Sum of Squared Differences přes všechny barevné kanály (tj. RGB). Protože ale maximální možná odchylka mezi bílým a černým pixelem (uvažovaná v barevných obrázcích) představuje hodnotu 3 * 2552, byly by tyto výsledné srovnávací obrázky povětšinou světlé s několika málo tmavými skvrnami. Proto jsou odstíny namapovány do rozsahu maximální barevné odchylky, která se ve zkoumaném obrázku objevila. Hodnota této chyby, stejně jako průměrná hodnota chyby a její medián, jsou také uvedeny u každého z popsaných obrázků. Pokud není pod obrázkem uvedeno jinak, je rozměr obou obrázků stejný.
"Umělý" případ
Tento poněkud umělý případ představuje pro algoritmus obtížnější problém neboť většina pixelů je shodné (bílé) barvy a jen relativně málo jich obsahuje nějakou informaci. Pozn.: Šedivý rámeček není součástí obrázků, je zde pouze pro jejich ohraničení od pozadí.
Umělý případ, 1. iterace – rozlišení 160×120 px.
Doba výpočtu: INIT = 0.019 s, ITER = 0.145 s, TOTAL = = 0.165 s.
Chyby pixelů: MAX = 97613, AVG = 270.827, MED = 0.
Jak je vidět z obrázků i ze statistik, naprostá většina pixelů je nalezena správně, u okrajů obou geometrických objektů na bílém pozadí však dochází k nepřesnostem.
Umělý případ, 5. iterace – rozlišení 160×120 px.
Doba výpočtu: INIT = 0.020 s, ITER = 0.770 s, TOTAL = = 0.790 s.
Chyby pixelů: MAX = 78803, AVG = 37.557, MED = 0.
Při vyšším počtu iterací (4 až 5 iterací je v článku doporučeno jako počet, při němž konverguje většina obrázků) je nepřesností znatelně méně a výsledek vypadá o mnoho lépe.
Dětský obličej
Dětský obličej, 1. iterace – rozlišení 200×150 px.
Doba výpočtu: INIT = 0.029 s, ITER = 0.174 s, TOTAL = = 0.203 s.
Chyby pixelů: MAX = 50992, AVG = 495.639, MED = 61.
Podle očekávání se největší chyby pixelů nalézají v očích, kde je na místě prakticky bílého pixelu bělma nějaký jinak barevný.
Dětský obličej, 5. iterace – rozlišení 200×150 px.
Doba výpočtu: INIT = 0.029 s, ITER = 0.762 s, TOTAL = = 0.791 s.
Chyby pixelů: MAX = 28269, AVG = 243.140, MED = 13.
Podle obrázku chyb by se mohlo zdát, že při 5. iteraci došlo k nalezení většího množství nesprávných matchů, ale opakuji, že jde pouze důsledek mapování hodnot jasu do rozsahu <0,MAX>.
Akropole
Akropole, 1. iterace – rozlišení 600×393 px (první obrázek), resp. 415×332 px (druhý obrázek).
Doba výpočtu: INIT = 0.305 s, ITER = 1.708 s, TOTAL = = 2.013 s.
Chyby pixelů: MAX = 77241, AVG = 1650.740, MED = 1109.
Tyto dva obrázky jsou již poměrně rozdílné, proto jsou chybové statistiky poměrně vyšší než u předchozích dvou obrázků, a to zejména co se týká střední hodnoty.
Akropole, 5. iterace – rozlišení 600×393 px (první obrázek), resp. 415×332 px (druhý obrázek).
Doba výpočtu: INIT = 0.298 s, ITER = 9.031 s, TOTAL = = 9.329 s.
Chyby pixelů: MAX = 41834, AVG = 1409.270, MED = 984.
Došlo sice k částečnému zjemnění hrany a zlepšení chybových statistik, ale další zlepšení by snad mohl přinést zobecněný Patch Match, který hledá korespondence kromě translací i přes další tranformace jako rotace či změna měřítka.
Další postup
Prioritou v dalším postupu implementace je jednoznačně zobecněný Patch Match, který by mohl přinést zlepšení v kvalitě korespondencí. Dalším krokem by pak mělo být využití PM speciálně pro úlohu vyplňování děr v obraze.
Jakub Fišer
22. 5. 2011
Patch Match
Fázová korelace je metoda registrace obrazu. K vyplňování děr není primárně určena, ale je možno ji k tomuto účelu využít. Nejprve je třeba pixely díry zahladit. K tomu slouží jednoduchá třída CircleIterator, která postupně v soustředných "kruzích" projde všechny pixely označené jako díry a ze známých pixelů v okolí vyplní pixel v obrázku. V masce ovšem pixel zůstane označen jako maskovaný. V další fázi je pro každý maskovaný pixel vytvořen obrázek sestávajícího z malého okolí tohoto pixelu (rozměry okolí odpovídají rozměrům kontextového okénka) a pomocí knihovny FFTW je spočteno jeho spektrum. To je spočteno i pro původní obrázek – se zahlazenými dírami.
Ze získaných spekter obou obrázku je spočteno tzv. cross power spectrum a je provedena korelace. Následně je získán určitý malý počet nejvyšších hodnot, které jsou vybrány za kandidáty na nejlepší shodu. Okolí těchto pixelů je pak porovnáváno s okolím hledaného pixelu a pixel s nejvyšší mírou shody je vybrán. Mezi kandidáty je zpravidla s nejvyšší hodnotou zastoupen i původní pixel v obrázku, který je ovšem z dalšího zpracování vyloučen (jinak by byl hledaný pixel nahrazen sám sebou).
Složitost takového postupu není prakticky závislá na velikosti kontextového okénka – počet provedených fourierových transformací je úměrný počtu pixelů díry a samotná FFT pak rozměrům obrázku. U nižších rozměrů kontextových okének proto hrubá sílá – základní Non Parametric Sampling – dosahuje lepších časů. Se zvětšující se velikostí okénka ovšem doba výpočtu podstatně vzrůstá (zejm. u vyšších rozlišení obrázků), zatímco u fázové korelace (v tabulce a v grafech označované jako FFT) zůstává prakticky stejná.
Provedl jsem měření na dvou obrázcích, první o rozlišení 200×200 px, druhý 400×276. Velikost kontextového okénka se měnila od 13 do 23 px. Výsledky uvádím v tabulkách a graficky. Obrázky byly před počítáním korelace převedeny na černobílé.
Obrázek o rozlišení 200×200 px
| Velikost okna |
Doba výpočtu |
| NPS |
FFT |
| 13 px |
1 s |
2 s |
| 15 px |
2 s |
2 s |
| 17 px |
3 s |
2 s |
| 19 px |
5 s |
2 s |
| 21 px |
7 s |
2 s |
| 23 px |
10 s |
2 s |
Obrázek 200×200 px, díra 10×10 px.
| Velikost okna |
Doba výpočtu |
| NPS |
FFT |
| 13 px |
5 s |
9 s |
| 15 px |
8 s |
9 s |
| 17 px |
10 s |
9 s |
| 19 px |
14 s |
9 s |
| 21 px |
20 s |
9 s |
| 23 px |
25 s |
9 s |
Obrázek 200×200 px, díra 20×20 px.
| Velikost okna |
Doba výpočtu |
| NPS |
FFT |
| 13 px |
14 s |
20 s |
| 15 px |
17 s |
20 s |
| 17 px |
29 s |
20 s |
| 19 px |
38 s |
20 s |
| 21 px |
49 s |
20 s |
| 23 px |
54 s |
20 s |
Obrázek 200×200 px, díra 30×30 px.
Obrázek o rozlišení 400×276 px
| Velikost okna |
Doba výpočtu |
| NPS |
FFT |
| 13 px |
7 s |
15 s |
| 15 px |
12 s |
15 s |
| 17 px |
18 s |
15 s |
| 19 px |
22 s |
15 s |
| 21 px |
28 s |
15 s |
| 23 px |
33 s |
15 s |
Obrázek 400×276 px, díra 10×10 px.
| Velikost okna |
Doba výpočtu |
| NPS |
FFT |
| 13 px |
17 s |
46 s |
| 15 px |
25 s |
46 s |
| 17 px |
32 s |
46 s |
| 19 px |
41 s |
46 s |
| 21 px |
52 s |
46 s |
| 23 px |
65 s |
46 s |
Obrázek 400×276 px, díra 20×20 px.
| Velikost okna |
Doba výpočtu |
| NPS |
FFT |
| 13 px |
27 s |
95 s |
| 15 px |
38 s |
95 s |
| 17 px |
59 s |
95 s |
| 19 px |
87 s |
95 s |
| 21 px |
112 s |
95 s |
| 23 px |
146 s |
95 s |
Obrázek 400×276 px, díra 30×30 px.
Zdá se tedy, že se vzrůstající velikostí obrázku a tedy i dobou výpočtu FFT, se hranice velikosti kontextového okénka, od které je rychlejší použít místo hrubé síly fázovou korelaci, posouvá směrem k vyšším hodnotám.
Jakub Fišer
2. 5. 2011
Non Parametric Sampling, Phase correlation
Třída ResizeSolver funguje na jednoduchém principu. Původní obrázek se zmenší, v něm se nalezne návrh řešení a souřadnice nalezeného pixelu (pochopitelně přenásobené převrácenou hodnotou koeficientu zmenšení) se poté využijí k hledání výsledného řešení v původním obrázku. Kromě navrženého pixelu je vhodné prohledat i jeho určité malé okolí.
Implementace
"Zmenšovací solver" je stejně jako jednoduchý solver – třída SimpleSolver – potomkem třídy Solver, která zajišťuje operace, u kterých očekávám, že budu všem solverům společné (načítání obrázků, gettery/settery privátních třídních proměnných atd.). Samotná třída před hledáním vlastního řešení vytvoří instanci "vnitřního" solveru, který použije k hledání ve zmenšeném obrázku. Tento vnitřní solver je opět potomkem společné base třídy, takže je možné využít zmenšovací pyramidy, kdy jsou řešení hledána od nejmenšího obrázku po největší – původní. Velikost kontextových okének je přitom zachovávána stejná.
Pro manipulaci s obrázky jsem vytvořil třídu Image zapouzdřující nejen samotná data, ale také některé operace nad obrázky. K nim je využita knihovna CImg, která vyniká zejména svou kompaktností (jde o jeden hlavičkový soubor). Knihovna obsahuje několik algoritmů umožňujících změnu velikosti obrázků, z nichž nejpoužitelněji se jeví bikubická interpolace, která zajistí dostatečnou ostrost zmenšovaného obrázku.
Algoritmus již rovněž provádí early termination, tedy včasné zastavení porovnávání dvou kontextových oken, je-li aktuální chyba již větší než dosud dosažené minimum.
Výsledky
Níže uvádím některé časy a výsledné obrázky. Všechny testy běžely na stejném stroji (viz Non Parametric Sampling - první verze). Pouze pár vysvětlivek:
- Velikost okna tradičně značí velikost kontextového okna. Velikost zůstala stejná ve všech fázích (tj. všechny případné vnitřní solvery pracovaly se stejnou hodnotou).
- Zmenšení představuje hodnotu od 0 do 1 udávající velikost zmenšovaného obrázku v poměru ku původnímu.
- Počet zmenšovacích cyklů udává kolikrát byl obrázek zmenšován příslušným zmenšovacím poměrem.
počet cyklů + 1 tedy udává, kolikrát celkem byl obrázek řešen v různých fázích hledání řešení.
Na obrázcích je vždy v levé části červeně označena oblast, která byla solveru předána k vyřešení. Na obrázku jsem ji nicméně nezačernil, aby bylo vidět, jak by zhruba mělo vypadat ideální řešení. V pravé části je pak zeleným rámečkem označena tato část po vyřešení. Uprostřed jsou ještě přidány náhledy (vyřešených) zmenšenin, tentokrát již bez označení hledané oblasti.
Cihlová zeď – rozlišení 200×200 px; oblast 32×32 px; velikost okna 21 px; zmenšení 0.5; počet cyklů 1; doba výpočtu 2 s.
Plástve – rozlišení 600×400 px; oblast 64×64 px; velikost okna 19 px; zmenšení 0.3; počet cyklů 1; doba výpočtu 5 s.
Pro textury tedy zmenšování funguje velice dobře a přináší velké zrychlení. Není třeba provádět více zmenšovacích cyklů a je možné i relativně velké zmenšení (viz 30% původní velikosti obrázku v případě obrázku Plástve), pouze je třeba zajistit, aby byl zmenšený obrázek dostatečně ostrý.
Krajina 1 – rozlišení 400×320 px; oblast 44×44 px; velikost okna 11 px; zmenšení 0.5; počet cyklů 1; doba výpočtu 4 s.
Krajina 2 – rozlišení 400×320 px; oblast 120×30 px; velikost okna 11 px; zmenšení 0.5; počet cyklů 1; doba výpočtu 13 s.
Pro části obrazu, kde je pro člověka příliš složité rozlišovat jednotlivé části v obrazu – viz Krajina 2 – jsou výsledky také poměrně dobře vypadající. Tam, kde už začínají určité konkrétnější (ale z hlediska barevnosti méně rozdílné) konkrétní obrysy – jako v případě Krajina 1 (namodralé mraky na modrém pozadí) – jsou výsledky o něco méně věrohodné.
Poušť 1 – rozlišení 700×500 px; oblast 64×64 px; velikost okna 13 px; zmenšení 0.5; počet cyklů 1; doba výpočtu 35 s.
Poušť 2 – rozlišení 700×500 px; oblast 64×64 px; velikost okna 19 px; zmenšení 0.4; počet cyklů 2; doba výpočtu 2 s.
V tomto případě hodně záleží na zmenšeném obrázku. Jakmile začne docházet k aliasingu, výsledek se začíná odchylovat od ideálního.
Další plány
V průběhu psaní zmenšovacího solveru jsem také implementoval paralelní verzi třídy SimpleSolver využívající POSIX Threads, která pro každý řešený neznámý pixel vytvoří N vláken, která prohledávají obraz v N vodorovných pruzích a jednotlivé nejlepší výsledky (pixely) v každém řezu jsou pak v hlavním vláknu porovnány a daný pixel je zapsán do obrazu. Bohužel ale nelze nechat každé vlákno samostatně řešit např. 1/N pixelů díry, protože vyřešené pixely jsou dále uvažovány při řešení dalších (sousedních) neznámých pixelů, a tak se zatím zdá, že režie na vytváření/správu vláken je příliš velká, takže časová úspora proti řešení jednoduchým solverem není příliš významná (u malých obrázků je doba výpočtu dokonce větší). Proto bych se rád ještě podíval na to, pro jaké obrázky je použití více vláken vhodné.
Také bych rád během začátku tohoto týdne ještě začal s implementací solveru, který se dívá pouze do určitého vzdálenosti od hledaného pixelu. Za tímto učelem chci nejprve zjistit a vizualizovat jakési "distanční mapy", které by napověděly, do jaké vzdálenosti je třeba se v průměru dívat. Rád bych také zjistil, zda by šlo využít této mapy ve spojení s prohledáváním ve zmenšeném obrázku (tj. najdu řešení ve zmenšeném obrázku, zjistím jeho distanční mapu, z ní zjistím průměrnou vzdálenost, tu upravím podle použitého zmenšní a v jejím dosahu pak hledám řešení pro neznámý pixel).
Jakub Fišer
18. 3. 2011
Non Parametric Sampling
Pro zrychlení výpočtu se nabízí využití instrukcí ze sady SSE, resp. SSE2. Konkrétně instrukce PSADBW. Kód lze zapisovat buď přímo pomocí assembleru nebo s pomocí tzv. intrinsics funkcí, které kompilátor přímo zamění za instrukce v assembleru:
__m128i _mm_sad_epu8 (__m128i a, __m128i b);
Tato funkce umožňuje vezme dvě 128-bitové proměnné (tj. 16 bytů) a provede součet absolutních hodnot rozdílů jednotlivých bytů (viz dokumentace).
Použití této instrukce ovšem znamená, že rozdíl mezi jednotlivými barevnými složkami již nelze brát jako kvadrát součtů jejich rozdílů, ale pouze jako součet absolutních hodnot těchto rozdílů. Při testech jsem ovšem nepozoroval nějaké významné zhoršení (pouze při některých konfiguracích).
Velkým problémem znemožňujícím efektivnější použití SSE instrukcí se bohužel ukázala nutnost pro každé porovnání (resp. pro každých X porovnání) přesunovat data do vyhrazené paměti. Nalézt efektivní způsob tohoto přesunu, resp. nějaký obecný vzorec, který by umožnil některá data pro pixely v pozicích posunujícího se klouzavého okna zachovat a nenačítat opakovaně (byť na jiných pozicích), se mi zatím bohužel nepodařilo.
Algoritmus s implementovanými SSE instrukcemi probíhá takto:
- Do (zarovnané) paměti jsou načteny validní pixely v kontextovém okně okolo právě řešeného pixelu.
- Do paměti je načteno okolí X (specifikováno uživatelem) pixelů pro X validních pozic klouzavého okna.
- Těchto X pozic je porovnáno a vybrán pixel (střed) s nejmenší chybou.
- Kroky 2 a 3 se opakují, dokud ještě existují nepoužité validní pozice (
počet pozic / X).
- Pokud ještě existují maskované pixely, znovu ke kroku 1; jinak konec.
Výsledky běhu algoritmu s a bez implementovaných SSE instrukcí (testovacím obrázkem byl obrázek Krajina – viz článek Non Parametric Sampling - první verze). Levý sloupec označuje velikost kontextových oken:
| |
solveScalar() |
solveWithSse() |
solveWithSseSingleChunk() |
| powDiff |
absDiff |
32 chunks |
256 chunks |
2048 chunks |
| 7 px |
49 s |
49 s |
40 s |
41 s |
42 s |
41 s |
| 13 px |
172 s |
174 s |
137 s |
139 s |
143 s |
138 s |
| 19 px |
327 s |
374 s |
297 s |
299 s |
311 s |
294 s |
Pozn.: solveWithSseSingleChunk() řeší speciální případ, kdy je do paměti načten vždy jen jedno klouzavé okno.
Z tabulky je patrné, že při "skalárním" zpracování není velký rozdíl v době výpočtu rozdílu barev mezi použitím absolutní hodnoty a mocněním. V případě SSE instrukcí pak nehraje příliš roli počet najednou nahrávaných klouzavých oken ("chunků"). Přibližné zrychlení oproti "skalárnímu" zpracování je cca. 20%.
Bohužel se tedy zdá, že tento druh paralelismu při stávající implementaci velké zlepšení nepřináší.
Eventuálním řešením by možná mohlo být rozdělit prohledávány prostor na cca. čtyři menší a jednotlivé prostory prohledávat samostatnými vlákny. Výsledné 4 nejlepší pixely pro konkrétní hledaný maskovaný pixel by pak už jen stačilo porovnat mezi sebou. Výhodou by také byl fakt, že by již nebylo třeba nijak přesouvat data v paměti.
EDIT: Projekt je nyní dostupný na githubu (pouze zdrojové kódy).
Jakub Fišer
4. 3. 2011
Non Parametric Sampling
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:
- 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.
- 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.
- Případně obě metody zkombinovat.
Kódy
Jakub Fišer
23. 2. 2011
Non Parametric Sampling, Kódy
