Resize solver
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ů + 1tedy 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).