Waveletová transformace: definice, aplikace, příklad

Vznik cenově dostupných digitálních fotoaparátů vedl k tomu, že významná část obyvatel naší planety, bez ohledu na věk a pohlaví, získala zvyk zachytit každý krok a dát obrazy na veřejný displej v sociálních sítích. Navíc, pokud byl před rodinným archivem fotografií umístěn do jednoho alba, dnes se skládá ze stovek obrázků. Aby se usnadnilo jejich ukládání a přenos přes sítě, je třeba snížit váhu digitálního obrazu. Za tímto účelem se používají metody založené na různých algoritmech, včetně transformace waveletů. Co je to, říká náš článek.

Co je to digitální obrázek?

Vizuální informace v počítači jsou reprezentovány jako čísla. Jednoduše řečeno, fotografie pořízená digitálním fotoaparátem je tabulka, ve které jsou zapsány barevné hodnoty jednotlivých pixelů. Pokud mluvíme o monochromním obrazu, pak jsou nahrazeny hodnotami jasu z intervalu [0, 1], kde 0 znamená černé barvy a 1 je bílá. Zbývající odstíny jsou uvedeny v částečných číslech, ale s nimi je nepohodlné pracovat, takže rozsah je rozšířen a hodnoty jsou vybrány z intervalu mezi 0 a 255. Proč z toho? Je to jednoduché! Při této volbě je v binárním zobrazení třeba přesně 1 bajt pro kódování jasu každého pixelu. Je zřejmé, že ukládání i malého obrazu vyžaduje spoustu paměti. Například velikost fotografie 256 x 256 pixelů bude trvat 8 kB.

Několik slov o metodách komprese obrazu

Určitě všichni viděli fotografie špatné kvality, kde jsou deformace ve formě obdélníků stejné barvy, které se obvykle nazývají artefakty. Vznikají v důsledku tzv. Ztrátové komprese. Může výrazně snížit váhu obrazu, ale nevyhnutelně ovlivňuje jeho kvalitu.

Mezi ztrátové kompresní algoritmy patří:

• JPEG. V tuto chvíli je to jeden z nejpopulárnějších algoritmů. Je založen na aplikaci diskrétní kosinové transformace. Ve skutečnosti je třeba poznamenat, že existují varianty formátu JPEG, které provádějí bezztrátovou kompresi. Mezi ně patří Lossless JPEG a JPEG-LS.
• JPEG 2000. Tento algoritmus se používá na mobilních platformách a je založen na aplikaci diskrétní vlnové transformace.
• Fraktální kompresní algoritmus. V některých případech vám umožňuje získat vynikající kvalitu obrazu i při silné kompresi. Nicméně kvůli problémům s patentováním je tato metoda nadále exotická.

Bez ztráty se komprese provádí pomocí algoritmů:

• RLE (používá se jako hlavní metoda ve formátech TIFF, BMP, TGA).
• LZW (používá se ve formátu GIF).
• LZ-Huffman (používá se pro formát PNG).

Fourierova transformace

Předtím než přistoupíme k úvahám o waveletách, má smysl studovat funkci s nimi spojenou, která popisuje koeficienty při rozkladu počáteční informace na elementární složky, tj. Harmonické kmity s různými frekvencemi. Jinými slovy, Fourierova transformace je unikátní nástroj, který spojuje diskrétní a souvislé světy.

Vypadá to takto:

Invertní vzorec je napsán následovně:

Co je wavelet?

Za tímto jménem leží matematická funkce, která umožňuje analyzovat různé frekvenční složky studovaných dat. Jeho graf představuje kmity podobné vlnám, jejichž amplituda se snižuje na 0 od původu. Ve všeobecném případě jsou zajímavé vlnkové koeficienty, určené integrální transformací signálu.

Waveletovy spektrogramy se liší od obyčejných Fourierových spekter, protože propojují spektrum různých signálních prvků s jejich časovou složkou.

Wavelet transformace

Tento způsob převodu signálu (funkce) umožňuje převést jej z doby na časovou reprezentaci.

Aby vlnová transformace byla možná, musí být splněny následující podmínky pro odpovídající waveletovou funkci:

• Pokud pro nějakou funkci psi (t) Fourierova transformace má formu

pak musí být splněna následující podmínka:

Navíc:

• wavelet musí mít konečnou energii;
• musí být integrální, spojitá a mít kompaktní nosič;
• Vlna musí být lokalizována jak ve frekvenci, tak v čase (ve vesmíru).

Typy

Pro odpovídající signály se používá kontinuální vlnová transformace. Mnohem větší zájem představuje jeho diskrétní analog. Koneckonců, může být použita pro zpracování informací v počítačích. To však vyvolává problém, že vzorce pro diskrétní DVP nelze získat prostým vzorkováním odpovídajících vzorců DNP.

Řešení tohoto problému našel I. Dobesi, který byl schopen zvolit metodu, která umožňuje konstrukci řady takových ortogonálních vln, které jsou určeny konečným počtem koeficientů. Později byly vytvořeny rychlé algoritmy, například algoritmus Mall. Při použití pro rozklad nebo obnovu je nutné provést pořadí operací cN, kde N je délka vzorku a c je počet koeficientů.

Vaivlet Haar

Za účelem komprimujte obraz, je nutné najít určitý vzorec mezi svými daty, nebo dokonce lépe, pokud jde o dlouhý řetězec nul. To je místo, kde algoritmus waveletových transformací může být užitečný. Pokračujeme však ve zvažování metody v pořadí.

Nejprve je třeba si uvědomit, že fotografie jasu sousedních pixelů se zpravidla liší o malé množství. Dokonce i když existují oblasti s ostrými kontrastními rozdíly jasu na reálných snímcích, zabírají jen malou část obrazu. Jako příklad si vezměme známý zkušební obraz Lenny ve stupních šedi. Pokud vezmeme matrici jasu jejích pixelů, pak část prvního řádku bude vypadat jako posloupnost čísel 154, 155, 156, 157, 157, 157, 158, 156.

Abychom získali nuly, lze na ni aplikovat takzvanou delta metodu. Za tímto účelem je zachováno pouze první číslo a pro ostatní jsou odebírány pouze rozdíly mezi jednotlivými čísly od předchozího čísla se znaménkem "+" nebo ";".

Výsledkem je sled: 154,1,1,0,0,1,2.

Nevýhodou delta kódování je jeho ne-lokality. Jinými slovy, je nemožné vzít jen kus sekvence a zjistit, které jasy jsou zakódovány v ní, pokud všechny hodnoty před ním nejsou dekódovány.

Pro překonání této nevýhody, číslo je rozdělena do dvojic a každá je polovina součtu (v. A) a polovině rozdílu (v. D), m. F o (154.155) (156.157) (157.157) (158.156) mají (154,5, 0,5) (156.5,0.5) (157,0.0), (157, -1,0). V tomto případě je vždy možné najít hodnotu těchto dvou čísel v páru.

Ve všeobecném případě pro diskrétní transformaci waveletů signálu S máme:

Tato diskrétní metoda vyplývá z kontinuálního případu transformace Haar wavelet a je široce používána v různých oblastech zpracování a komprese informací.

Komprese

Jak již bylo uvedeno, jednou z aplikací waveletové transformace algoritmus je metoda komprese JPEG 2000 s použitím Haar na základě převodní vektoru dvou bodů v X a Y vektoru (X + Y) / 2 a (X - Y) / 2. Postačí násobit počáteční vektor v níže uvedené matrice.

Pokud je více bodů, pak vezměte větší matrici s úhlopříčnými maticemi H. Proto je původní vektor, bez ohledu na jeho délku, zpracován ve dvojicích.

Filtry

Výsledné "poloviny" jsou průměrné hodnoty jasu v párech pixelů. To znamená, že hodnoty při převedení na obraz by měly poskytnout jeho kopii sníženou o faktor 2. V tomto případě poloviny částek průměrně jas, to znamená, "odfiltrovat" náhodné výbuchy jejich hodnot a hrát roli frekvenčních filtrů.

Nyní se podívejme na rozdíly. "Přidělují" interpikelové "bursty", čímž eliminují konstantní součást, tj. "Filtrovají" hodnoty s nízkými frekvencemi.

Dokonce i z výše uvedené transformace vlnky Haar pro "figuríny" je zřejmé, že se jedná o dvojici filtrů, které rozdělují signál na dvě složky: vysokofrekvenční a nízkofrekvenční. Pro získání původního signálu stačí jednoduše tyto komponenty znovu spojit.

Příklad:

Chci kompresi fotografického portrétu (zkušební obraz Lenny). Zvažte příklad vlnové transformace její matrice jasu pixelů. Vysokofrekvenční součást obrazu je zodpovědná za zobrazení malých detailů a popisu šumu. Pokud jde o nízkou frekvenci, nese informace o tvaru obličeje a hladkých změnách jasu.

Zvláštnosti lidského vnímání fotografií jsou taková, že druhá složka je důležitější. To znamená, že během komprese může být část vysokofrekvenčních dat vyřazena. Navíc má menší hodnoty a je kódově kompaktnější.

Chcete-li zvýšit kompresní poměr, můžete několikrát použít transformaci Haar na data s nízkým kmitočtem.

Aplikace na dvourozměrné pole

Jak již bylo uvedeno, digitální obraz v počítači je reprezentován jako matice hodnot intenzity jeho pixelů. Měli bychom tedy zajímat Haarovou dvojrozměrnou transformaci waveletů. Chcete-li jej implementovat, stačí jednoduše provést jednorozměrnou konverzi pro každý řádek a každý sloupec matice intenzity pixelů obrazu.

Hodnoty blízké nule mohou být vyřazeny bez významného poškození dekódovaného obrazu. Takový proces je známý jako kvantizace. A právě v této fázi jsou některé informace ztraceny. Mimochodem lze měnit počet nulovatelných koeficientů, čímž se upraví kompresní poměr.

Všechna popsaná opatření vedou k vytvoření matice, která obsahuje velké množství 0. Měla by být napsána řádkově po řádku do textového souboru a komprimována libovolným archivorem.

Dekódování

Reverzní transformace na obrázek se provádí podle následujícího algoritmu:

• archiv je rozbalen;
• používá se inverzní Haarova transformace;
• Dekódovaná matice se přemění na obrázek.

Výhody před JPEG

Při zvažování algoritmu Společná fotografická skupina expertů bylo řečeno, že je založeno na DCT. Tato transformace se provádí blokově (8 x 8 pixelů). Výsledkem je, že pokud je komprese silná, objeví se struktura bloku na obnoveném obrazu. Při kompresi pomocí waveletů tento problém chybí. Mohou se však objevit i jiné typy zkreslení, které vypadají jako zvlnění blízko ostrých hran. Předpokládá se, že takové artefakty jsou v průměru méně nápadné než "čtverce", které jsou vytvořeny při aplikaci algoritmu JPEG.

Nyní víte, jaké vlnky jsou, jaké to jsou a jaká praktická aplikace pro ně byla nalezena při zpracování a kompresi digitálních obrazů.