Adaptivní metody zpracování signálů

adaptivní kompresory své slovníky takříkajíc za pochodu a od úplného začátku. Slovníky takovýchto metod neobsahují žádné předdefinovaná slova či výrazy. Adaptivní algoritmy jsou tak schopné přizpůsobit se jakýmkoliv vstupním datům a dosáhnout tak pro daný vstupní obraz ten nejefektivnější kompresní poměr. Kromě striktně adaptivních a neadaptivních metod existují i kombinace obou postupů. Tyto algoritmy nazýváme jako semiadaptivní. Semiadaptivní kompresní systémy provádí dvojí průchod dat. V prvním průchodu se vytvoří optimální kódovací slovník pro daná vstupní data a v druhém průchodu se provede vlastní kódování. Při použití těchto metod je tedy vhodný kódovací slovník vytvořen ještě před vlastním kompresním kódováním. 2. Adaptivní metody pro kompresi obrazových dat Jako adaptivní metody pro kompresi obrazových dat označujeme takové algoritmy, které umožňují optimalizovat kompresní poměr v závislosti na vstupních obrazových datech. Velice oblíbenou adaptivní metodou v teorii komprese obrazových dat je tzv. Lempel - Ziv - Welchova metoda. 2.1 Lempel - Ziv - Welchova metoda komprese dat Základy slovníkových kompresních metod položili v roce 1977 pánové Abraham Lempel a Jakob Ziv. Jejich algoritmus se ujal pod názvem LZ77 a tvoří základ dnes tolik oblíbených kompresních metod jako jsou např. pkzip, arj a jiné. O sedm let později byla původní kompresní metoda zdokonalena Terry Welchem a výsledkem byl universální komprimační algoritmus, dnes všeobecně označovaný jak LZW. Jak již bylo řečeno, LZW je všeobecný kompresní algoritmus, který je schopen zpracovávat téměř jakýkoli typ dat. Jedná se o tzv. Substituční adaptivní algoritmus, což je dáno tím, že nepracuje s pevně stanoveným datovým slovníkem, ale při každé kompresní úloze začíná tvořit nový datový slovník, specifický pro daný vstupní nekomprimovaný obraz. Datové vzorky (podřetězce) jsou definovány jako toky dat a shodují se se vstupy do slovníku. Pokud se podřetězec ve slovníku nevyskytuje, je podle obsahu informace vytvořena kódová fráze a je uložena do slovníku. Fráze je poté zapsána do komprimovaného výstupního toku. Pokud se daný podřetězec v datech znovu objeví je fráze tohoto podřetěze už uloženého ve slovníku přímo zapsána na výstup. Protože hodnota fráze má fyzickou velikost , která je menší než původní podřetězec, je dosaženo datové komprese. Lempel – Ziv – Welchův algoritmus je v současné době hojně používán v rozšířených grafických formátech TIFF a GIF. V současné době se také vyskytují různé varianty LZW komprese. Populární je například varianta algoritmu, která sleduje kompresní proces ta, aby nedošlo k poklesu účinnosti komprese. Pokud k nějakému poklesu dojde, je nejméně používaná fráze ze slovníku odstraněna, čímž se vytvoří místo pro umístění nové, více se vyskytující fráze. Lze také zrušit a přebudovat kompletně celý slovník. I když algoritmus LZW představuje poměrně zajímavý prostředek pro bezeztrátovou kompresi nejen obrazováých dat, jeho širšímu využití brání právní nároky, které si na LZW algoritmus začala nárokovat společnost Unisys. Obr. 1: Zjednodušené blokové schéma LZW algoritmu