Úvod do geografických informačních systémů (GIS)
Datové modely používané v GIS pro ukládání prostorových dat
Vytisknout  studijní materiál

Studijní článek: Kompresní techniky pro ukládání pravidelných rastrů

Kompresní techniky používané pro ukládání pravidelných rastrů

Uložení rastrových dat je velice náročné na prostor a má vysoké režijní náklady. Velikost dat záleží na rozloze představované oblasti a na rozlišení bodu, ale vůbec nezávisí na obsahu. Pro zmenšení náročnosti je nutné zavést více účinné způsoby uložení, hlavně pro reprezentaci řídce rozptýlených bodů. Se zavedením kompresních technik se však pro operace využívající okolí zpracovávaného bodu musí data nejdříve dekódovat a až pak je možné data zpracovat. Nejenom z tohoto důvodu se kompresní techniky většinou užívají jen pro ukládání dat na disk a pro vlastní zpracování v paměti je k reprezentaci užívána dvourozměrná matice.

Metoda délkových kódů (Run Lenght Encoding - RLE)

RLE je jedna z technik odstraňující neefektivnost uložení rastrových dat pomocí matic. Využívá vlastnosti, že mnoho dat obsahuje rozsáhlé homogenní objekty, reprezentované velkým množstvím pixelů. Místo uchovávání hodnot každého bodu, run lenght encoding organizuje řádku pixelů o stejné hodnotě do skupiny a tu potom ukládá ve formě (počet hodnota). Uvažujme následující rastrová data.

1 1 1 1 5 5 9 9 9 9 9 9 9 2 9 9 9

Při použití techniky RLE dostaneme datovou strukturu, kde jsou původní data nahrazena páry skládající se z počtu opakujících se pixelů stejné hodnoty za sebou a vlastní hodnoty pixelu. Podle našeho příkladu se tedy první čtyři pixely o hodnotě 1 ze tvaru (1 1 1 1) zakódují do (4 1). Celý zakódovaný řádek vypadá následovně.

(4 1) (2 5) (7 9) (1 2) (3 9)

Jak si je možné všimnout, pixel o hodnotě 2 je zakódován jako (1 2), tudíž místo komprese nastala expanze jednoho elementu do dvou. Díky této vlastnosti není RLE technika vhodná pro data s častými změnami v průběhu. V nejhorším případě, když neexistují žádné úseky se stejnými hodnotami, se po zakódování dat zvětší velikost dvakrát. Z tohoto důvodu se používají současně s RLE i jiné techniky komprese.

Kódování úseků řádků (Run Length Codes - RLC)

RLC je metoda komprese, která definuje příslušnost buněk rastru k objektu po řádcích nebo sloupcích, přičemž se udává jen začátek a konec úseku buněk v systému řádků a sloupců, které mají uloženou stejnou hodnotu. Viz obr. .

Čtyřstrom (QuadTree)

QuadTree je zástupcem hierarchických rastrových struktur. Využívá model "rozděl a panuj" tak, že dělí prostor do kvadrantů, které jsou opět rozděleny do dalších čtyř kvadrantů, až do doby, kdy kvadrantu odpovídá homogenní oblast. Tato struktura vytváří strom s uzly reprezentujícími heterogenní oblasti a listy oblasti se stejnou hodnotou. Na obrázku je uveden rastrový obraz a jemu odpovídající strom. Viz obr. .

Nevýhodou QuadTree struktury je, že není invariantní s operacemi translace, rotace a změna měřítka. Tento problém se ale týká všech hierarchických modelů reprezentace rastrových dat využívajících dělení prostoru.

Adaptivní komprese

Adaptivní komprese rastrových dat využívá vlastnosti, že data jdou rozdělit do bloků a ty lze zakódovat pomocí metody s nejvyšší účinností. Takový způsob má výhodu v tom, že nedochází ke zbytečnému nárůstu režijních nákladů pro jakákoli data, jak tomu je v případě RLE a částečně i QuadTree.