Počítačová grafika: Komprese metodou RLE

Run-length encoding je jednoduchá metoda bezztrátové komprese. V článku vysvětlím, v čem spočívá, jak se s ní pracuje a ukážu příklad na obrázku BMP.

Motivace

Mějme řetězec 20-ti znaků

AAABBCCCCCCCAAAAAAAA

Dokážeme zmenšit počet znaků v řetězci, aniž bychom ztratili byť jen jedinou hodnotu, kterou obsahuje?

Mějme obrázek

Je nutné uložit jej pixelu po pixelu, aby pak mohl být ve stejné formě zobrazen?

Algoritmus RLE

Řetězec výše můžeme přečíst jako "á á á bé bé cé cé cé...", nebo možná přirozeněji "tři á, dvě bé, sedm cé a osm á". Stejně tak můžeme obrázek přečíst jako "tři černé, čtyři bílé, čtyři černé, pět bílých a čtyři černé". A to je ono - jednoduše nahradíme podřetězce stejných znaků jejich délkou a samotným znakem. Řetězec výše tedy bude po zakódování vypadat

3A2B7C8A

Vidíme, že z původních 20-ti znaků dostáváme 8, aniž bychom přišli o originál. Jsme totiž schopni z našich 8-mi znaků přesně rekonstruovat vstupní řetězec o délce 20-ti. Algoritmus existuje ve více variantách a úpravách, které z části řeší nevhodná vstupní data. Používají se speciální symboly, které například detekují opakování celých skupin, mění směr průchodu, nebo značí nezakódovanou sekvenci. Poslední případ můžeme demonstrovat na řetězci

AAABCDEFGHIII

který by po zakódování neoptimalizovaným způsobem vypadal

3A1B1C1D1E1F1G1H3I

Docílili jsme záporné komprese, kdy z původních 13-ti znaků dostáváme 18. Zkusme zavést speciální symbol "#", který použijeme spolu s číslem reprezentující počet nezakódovaných znaků. Dostaneme

3A7#BCDEFGH3I

tedy 13 znaků po zakódování.

Implementace

opakovani = 1;
vystup = "";

for(pro vsechny znaky - 1) {
   if (znak == nasledujici znak) {
      opakovani += 1;
   } else {
      vystup += opakovani + znak;
   }
}

if (predposledni znak != posledni znak) {
   vystup += "1" + posledni znak;
}

Cyklus projde vstupní řetězec znak po znaku a ve chvíli kdy se následující znak nerovná zpracovávanému přidá k výstupnímu řetězci informaci o počtu jeho opakování. Na konci máme v proměnné vystup řetězec s výsledným tvarem vstupu po kompresi.

Příklad s BMP

Obrázek použitý nahoře jako příklad jsem v Gimpu uložil jako BMP a poté otevřel v HEX módu v PSPadu. Jak vidíme, zapsal se nekomprimovaně. Byty 00 jsou pixely černé barvy a FF barvy bílé.