Patch Match – základní implementace

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.

napsáno 22. 5. 2011 | naposledy změněno 23. 5. 2011 | 47287× okometováno | ↑ nahoru

Komentáře