Run-Length kódovanie (RLC)

Veľa dokumentov, listov, obrázkov sa dá prenášať použitím faxu. Pri tomto prenose sú dokumenty kvantizované do binárnej úrovne (biela a čierna farba). Rozlíšenie týchto dokumentov býva často pomerne veľké a na každom riadku dokumentu sa za sebou vyskytuje veľké množstvo bodov s rovnakou intenzitou (v tomto prípade buď biele alebo čierne). RLC kódy sa používajú práve na komprimovanie takýchto dokumentov.

1-D Run-Length kódovanie

V tejto verzii RLC kódu sa berie každý riadok ako nezávislý, teda v úvahu sa berie iba horizontálna koherencia. Ide teda o kódovanie postupnosti bielych a čiernych znakov (núl a jednotiek), kde sa kódujú vzdialenosti prechodov postupností. Predpokladá sa, že začiatok postupnosti sú biele znaky, ale táto dohoda nie je nutná (v najhoršom prípade bude dekódovaný dokument inverzný k pôvodnému). Ak je prvý bod čierny, dĺžka bielej sekvencie je 0. Proces komprimácie asi najlepšie vystihuje stavový diagram na obrázku 3.7. Na koniec každého riadku sa pridáva ešte jeden špeciálny symbol, EOL (end-of-line).

Na ukážku si zoberme postupnosť

Výsledok kódovania je potom

Vo veľkej miere záleží na počte bitov, ktoré sme ochotní poskytnúť na kódovanie vzdialeností. Ak poskytneme 3 bity, potom výstupná sekvencia bude

čo je 24 bitov oproti pôvodným 30 bitom. Ak ale budeme na vzdialenosti počítať 4 bity, vznikne nasledujúca postupnosť

čo už je 32 bitov oproti tridsiatim z pôvodného zdroja.

Teda významne záleží na tom, akým spôsobom si zvolíme maximálnu dĺžku sekvencie znakov, aby kódovanie bolo optimálne. Existuje niekoľko spôsobov:

štatisticky prehľadať kódované dáta a zistiť počty, ktoré sú najčastejšie
metóda pokusov a omylov. Kódujeme pre rôzne počty.
výsledok kódovania nerobíme binárne, ale využijeme niektorý z VLC (Huffman alebo jeho modifikácia).

Obrázok 3.7: Vývojový diagram pre RLE na bitovej úrovni

Modifikácie

Existujú rôzne varianty tohto kódu, ktoré už nepracujú na bitovej úrovni, ale na bajtovej, prípadne inej. Keď máme viac ako dve úrovne, už nám nestačí kódovať iba počet znakov, ktoré sa opakujú, ale aj samotné znaky. Napríklad to môže vyzerať následovne: , . Náš stavový diagram na obrázku 3.7 sa potom mierne zmení. Budeme si pamätať aj kódovaný znak(RunValue) a pred zapísaním hodnoty RunCount zapíšeme hodnotu RunValue.

Rozšírenie 1-D RLC

Zaujímavým rozšírením je kódovanie nazývané 2-D RLC. Toto kódovanie berie v úvahu, že kódovaný dokument je dvojrozmerný objekt, takže okrem horizontálnej koherencie je braná v úvahu aj vertikálna.

Pri kódovaní vzdialenosti prechodov máme na výber

vzdialenosť od posledného prechodu v tom istom riadku
vzdialenosť od rovnakého prechodu v predchádzajúcom riadku smerom vľavo,
vzdialenosť od rovnakého prechodu v predchádzajúcom riadku smerov vpravo.

Vyberá sa najkratšia z týchto vzdialeností. Pridáva sa ku nej ešte prefix, ktorý ju jednoznačne identifikuje. O tomto algoritme sa viac dočítate v [1], [3] a [4].