CAD II – Ztrátová komprese Základní rozdělení Obecně každá ztrátová kompresní metoda je založena na odstraňování nadbytečných dat. Rozdělení kompresních metod obrazu: neztrátová - např. hledá delší sekvence stejných prvků nebo statisticky redukují informaci pro popis frekventovaných prvků, za cenu delšího popisu těch méně častých) ztrátová – odstraňuje zbytečné informace z obrazu. Různé druhy ztrátových kompresních metod se liší podle druhu odstraněných zbytečných informací. Komprese JPEG, JPG odstraňují zbytečné informace z funkcí vysokých frekvencí Fraktální komprese odstraňuje soběpodobnost. Nejlepších výsledků komprese dosahují metody, které odstraňují oba dva druhy redundance (frekvenční i soběpodobnost). (DCT-fraktál, wavelet-fraktál…)
1
2
3
4
5
6
7
8
9
CAD II – Ztrátová komprese Fraktálová komprese Fraktálová komprese se zakládá na fraktálech. Fraktály – jsou popsány fraktální geometrii, tedy množinou bodů. Asi nejznámější fraktál - Mandelbrotova množina Vlastnost fraktálů: Fraktál je nekonečně složitý, ale jeho popis je konečný. V přírodě se vyskytuje hodně útvarů, které se podobají fraktálům (stromy, kapradiny, mraky). Jejich popis pomocí Euklidovské geometrie je složitý. Dají se ale popsat „jednodušeji“ právě pomocí fraktální geometrie.
1
2
3
4
5
6
7
8
9
CAD II – Ztrátová komprese Fraktálová komprese Jestliže jde jednoduchým popisem dostat složitý obrazec, jde ze složitého obrazce získat jednoduchý popis? Tento problém zatím nebyl vyřešen a umíme ho řešit jen částečně. Nejprve musíme najít vhodnou třídu fraktálů, kterými se bude vstupní obrázek aproximovat. Fraktály lze na počítači generovat několika osvědčenými způsoby, z nichž nejvýznamnějším pro kompresi obrazu jsou IFS (Iterated Function Systems). IFS je soubor parametrů, které definují afinní (lineární) transformace a jejich množina pak určuje výsledný atraktor (kýžený fraktál, kterého jsme chtěli dosáhnout).
1
2
3
4
5
6
7
8
9
CAD II – Ztrátová komprese Fraktálová komprese
1
2
3
4
5
6
7
8
9
CAD II – Ztrátová komprese Fraktálová komprese Další příklad dokazuje, že aplikací stejných pravidel se dostáváme ke stejnému atraktoru, ačkoliv vstupní obrázek je libovolný.
1
2
3
4
5
6
7
8
9
CAD II – Ztrátová komprese Fraktálová komprese Srovnání výsledných atraktorů při různých vstupních obrázků
1
2
3
4
5
6
7
8
9
CAD II – Ztrátová komprese Fraktálová komprese
Fraktálová komprese je přesný opak. Pro daný obrázek máme najít množinu transformací tak, aby jsme těmito informacemi vygenerovali atraktor, co nejpodobnější originálu. Obrázek zakódovaný fraktálovou kompresí nese pouze informaci o transformacích, takže vůbec nezáleží na tom, jaký úvodní obrázek zvolíme. Aby bylo zajištěno, že po aplikaci transformací bude obrázek konvergovat do chtěného atraktoru, musí být transformace kontraktivní (zmenšující).
1
2
3
4
5
6
7
8
9
CAD II – Ztrátová komprese Matematický zápis funkce IFS Pro každý bod při aplikaci afinní transformace platí tato rovnice: (Tato rovnice platí pro IFS ve zjednodušené formě pro černobíle obrázky) Princip fraktálové komprese: Vycházíme z Kolážovacího teorému Pokud najdeme transformaci W pro obrázek B tak, že B a W(B) jsou velmi podobné, pak atraktor W bude také velmi podobný obrázku B. Fraktálová komprese spočívá ve vhodném rozložení obrázku na nepřekrývající se bloky, tzn. jejich sjednocení je celý obrázek. Pokud je každý z těchto bloků podobný celému obrázku, pak kombinace získaných transformací je IFS originálu. Jinými slovy, zakódování obrázku do IFS spočívá v nalezení kontraktivních afinních transformací w1, w2, ... wn, takže původní obrázek B je sjednocením n podobrázků.
CAD II – Ztrátová komprese Matematický zápis funkce IFS Přímá metoda vyhledání IFS je prakticky použitelná pouze jako příklad, protože její realizace vyžaduje právě ono nalezení optimální "koláže", tedy způsobu jak rozložit obrázek tak, aby jeho části byly co nejvíce podobné jemu samotnému. Pokud bychom dokázali inverzní problém vyřešit, zjistili bychom u Sierpinského trojúhelníka, že se skládá ze tří menších trojúhelníků. Jsou to nepřekrývající se bloky a jejich sjednocení dává dohromady celý obrázek. Zároveň je každý malý trojúhelník transformací obrázku celého. Pokud můžeme najít tyto transformace, IFS je souborem transformací pro Sierpinského trojúhelník.
CAD II – Ztrátová komprese Aplikace na obrázky
Když generujeme fraktál iterativním postupem, aplikujeme transformaci W na obrázek f. První iterace je tedy W(f), druhá W(W(f)), třetí W(W(W(f))) atd.. Fraktálová dekomprese: U fraktálové dekomprese obrázku se transformace provádí z větších bloků do menších (říkáme že větší bloky mapujeme do menších). Větší bloky se nazývají domény (ozn. D - domains) a menší oblasti (ozn. R ranges): Větší bloky se mohou překrývat, menší nikoliv. Pro každý menší blok se hledá co možná nejpodobnější větší blok (aby se zajistila kontraktivita).
CAD II – Ztrátová komprese Fraktální komprese – soběpodobnost Nálezy soběpodobnosti mohou vypadat následovně: Stejně jako při generování fraktálů můžeme použít opravdu jakýkoliv vstupní obrázek a na ten aplikovat iterace. Výstupní kvalita obrázku závisí především na míře podobnosti mezi malými a velkými bloky. Tím, že se kompresní metoda zakládá na fraktálech, dědí zakódované obrázky taky zajímavou vlastnost - nezávislost na rozlišení;tedy lze je dekódovat na libovolném rozlišení bez ztráty detailu.
CAD II – Ztrátová komprese Fraktálová komprese – PIFS Vlastnosti fraktálové komprimace: Komprese obrazu pomocí IFS je výpočetně náročný úkol, naopak dekódování je velmi rychlé. Jde tedy o silně asymetrický proces. -Fraktálová komprese poskytuje nezávislost na rozlišení. (můžeme obraz dekódovat v jiném rozlišení, než jsme ho kódovali). PIFS - Partitioned Iterated Function Systems PIFS vychází z IFS metody -je časově méně náročná -má menší účinnost Podtstatou je vyhledávat IFS transformace pouze pro části obrázku. Hledaná transformace obrázku je tedy sjednocením transformací částí obrázku:
Obrázek je rozdělen na malé nepřekrývající se bloky, tzv. ranges - R Předem definovaná množina doménových bloků - D D>R Fraktální kodér hledá pro každý R, co nejpodobnější D.
CAD II – Ztrátová komprese Fraktálová komprese – PIFS Úkolem fraktálního kóderu je potom najít množinu transformací, kterými namapujeme doménové bloky do oblastních. Pro porovnání R a D, musíme D zmenšit na Stejnou velikost jako R
Původní rovnice IFS se rozšířila O 2 hodnoty (jas, kontrast)
-podvrorkováním (rychlé, ale nekvalitní) -průměrem (delší, kvalitnější) Rozdílnost bloků určuje střední kvadratická uchylka (RMSE). (RMSE - Root Mean Square Error). Hodnoty pixelů v doméně jsou a, v oblastním bloku b. Pro známé hodnoty posunů jasu a kontrastu (získány metodou nejmenších čtverců) dostaneme minimální odchylku RMS.
-Pro rychlejší vyhledávání se může zavést dovolená odchylka RMSE, nebo se D můžou různě natáčet.
CAD II – Ztrátová komprese Dekodér Je mnohem rychlejší než kódování.Pro každý oblastní blok je nalezena vhodná transformace.Ta je popsána souřadnicemi domény a dvěma hodnotami pro barevné transformace. Dekodér prochází oblastní bloky stejně jako kodér při kódování, ale známe už příslušné transformace, takže stačí načíst doménový blok na známých souřadnicích, zmenšit ho a aplikovat barevné transformace. To se dělá tak, že hodnotu každého pixelu (intenzitu) vynásobíme škálovacím faktorem s a přičteme jasový posun o. Při každé iteraci se zvýší rozlišení dekódovaného obrázku
CAD II – Ztrátová komprese Fraktálová komprese – dekódování obrázku
Originální obrázek (Lenna)
Použití náhodné volby domény při 128 pokusech, první 4 iterace:
CAD II – Ztrátová komprese Fraktální artefakty Protože fraktálové obrázky jsou fraktály, můžeme ho donekonečna zvětšovat, bez ztráty ostrosti. Chybějící informace se dopočítavají.
Na vyhlazení obrázku se můžou použít různé filtry, který obrázek vyhladí. prosté zvětšení
bilineární filtr
CAD II – Ztrátová komprese Fraktálová komprese - QPIFS QPIFS - Quadtree Partitioned Iterated Function Systems Oproti předchozé metodě je rychlejší a účinnější, hlavně při definovaných větších RMS. Rekurzivní dělení obrázku na kvadrantový strom.
V kvadrantovém stromu mohou z každého uzlu vycházet čtyři hrany. Kořenem tohoto stromu je obrázek sám a větvení se interpretuje dělením částí obrázku na čtyři stejné části. Možnost volby minimální a maximílní velikosti oblastních bloků Každý ze čtyř vzniklých bloků podrobíme porovnávání s doménami. V těch blocích, kde jsme nenašli žádnou doménu s odchylkou splňující zadaný toleranční práh (RMS tolerance), se provede rozdělení a algoritmus může pokračovat rekurzivně.
CAD II – Ztrátová komprese Fraktálová komprese - QPIFS
Podle pravidel z klasifikace domén můžeme každý doménový blok zařadit do jedné ze tří základních tříd podle uspořádání světlosti kvadrantů a jedné z 24 podtříd podle variance. Oblastní bloky se pak porovnávají s oblasti domén se stejnou klasifikací, což vede ke snížení času vyhledávání. Další optimalizaci obrázku můžeme získat vytvořením pomocných bitmap.
CAD II – Ztrátová komprese Fraktálová komprese
originál (512x512 pixelů)
rozdělení obrázku Lenna při toleranci 4.0
CAD II – Ztrátová komprese Fraktálová komprese
1. a 2. iterace
CAD II – Ztrátová komprese Fraktálová komprese
3. a 4. iterace
CAD II – Ztrátová komprese Fraktálová komprese
5. iterace
originál
CAD II – Ztrátová komprese Fraktálová komprese Barevnost lze vyřešit jednoduše rozložením barevné vstupní bitmapy na tři pomocné bitmapy, které představují složky zvoleného modelu. Pro ztrátovou kompresi je nejlepší použít model YUV (YCbCr) nebo YIQ, kde jedna bitmapa Y nese informaci o jasu, na který je lidské oko velmi citlivé, proto tuto bitmapu zakódujeme s parametry pro vysokou kvalitu, a dvě barvonosné bitmapy U, V (I, Q) lze zakódovat s buď citelnější ztrátou, nebo použít konvenční metodu podvzorkování (zmenšení bitmap v poměru 1:2 nebo 1:4) - naše oko téměř nepozná rozdíl.
CAD II – Ztrátová komprese Fraktálová komprese - využití Fraktální komprese samotná není moc rozšířená. Více se používají metody, které jsou kombinované a mají lepší výsledky. Další možné využití metody:
porovnání obrázků zvětšování bez změny rozlišení pokročilé odstraňování šumu, odstraňování JPEG artefaktů
