Veszteségmentes képtömörítés

Képek mindenhol vannak körülöttünk, az alkalmazások ikonjaitól kezdve az animált GIF-eken keresztül a fényképekig. A képfájlok sok helyet foglalhatnak el, ezért a számítógépek különböző algoritmusokat alkalmaznak tömörítésükre.

A legegyszerűbb képek esetében a számítógépek használhatják az úgynevezett futamhossz kódolás (run-length encoding, RLE) tömörítési algoritmust.

Mielőtt elmélyednénk a képtömörítésben, nézzük, hogyan tudunk képeket binárisan ábrázolni bármiféle tömörítés nélkül.

Íme egy egyszerű kép, egy 16×16-os szív ikon:

Közelítsünk rá és helyezzünk rá egy rácsot, hogy jobban láthassuk, pontosan melyik pixel piros és melyik fehér:

A szív ikon csak két színből, pirosból és fehérből áll, így a számítógép binárisan úgy tudja ábrázolni, hogy a piros pixelekhez $1$‍-et, a fehér pixelekhez pedig $0$‍-t rendel hozzá. Ezt bittérképnek nevezzük, mivel a pixelek bitekre való leképezéséről van szó.

Ezzel a módszerrel a szív ikon a következőképpen jelenik meg:

Képzeld el, hogy az eddigi szöveget lediktálod valakinek. Egy idő után lehet, hogy olyanokat mondanál, mint „öt nulla” a „nulla nulla nulla nulla nulla" helyett. Nos, erre a számítógép is képes...

A futamhossz-kódolásnál a számítógép minden egyes sort számokkal helyettesít. Ezek megadják, hogy hány egymást követő pixel azonos színű. A számsor mindig a fehér pixelek számával kezdődik.

Az első sor például 3 fehér pixelt, 2 piros pixelt, 5 fehér pixelt, 2 piros pixelt, majd 4 fehér pixelt tartalmaz:

Ez az alábbi módon ábrázolható:

A negyedik sor azért érdekes, mert piros pixellel kezdődik. A futamhossz-kódolások a fehér pixelek számával kezdődnek, ezért ezt a program így ábrázolná:

Ha egy számítógép futamhossz kódolást használ, képesnek kell lennie arra, hogy a tömörített ábrázolásból tökéletesen visszaállítsa a képet – és nekünk is képesnek kell lennünk rá, ha követjük a számítógép módszerét.

Próbáljuk ki! Íme egy fekete-fehér ikon RLE-vel tömörített változata:

Az első sorban 4 fehér képpont van, majd 9 fekete képpont, aztán 3 fehér képpont. Ez így néz ki:

A következő sorban 4 fehér pixel van, majd 7 fekete, 2 fehér, 1 fekete és 2 fehér. Ez így néz ki:

Ha továbbmegyünk, a végső ikon egy csésze és egy csészealj lesz:

Azt állítottuk, hogy a futamhossz kódolás helyet takarít meg az egyszerű képek tárolásakor – de mennyi helyet?

Hogy ezt kiderítsem, írtam egy programot, amely fekete-fehér bittérképeket kódol RLE-vel. Az alábbi táblázatban az eredmény összefoglalására három, egyre nagyobb méretű szív ikont választottam ki:

Vess egy pillantást az utolsó oszlopra, a helymegtakarításra. Felismerted a sémát? Ahogy egyre nagyobb a méret, egyre több helyet takarítunk meg, mivel a futamok sokkal hosszabbak.

Mi a helyzet az azonos méretű képekkel? Az alábbi táblázat három nagy ikon RLE-vel való tömörítésének eredményeit foglalja össze:

Most már biztosan érted, miért a szív ikont választottam példának: a sok fekete vagy fehér futamnak köszönhetően nagyon jól tömöríthető. Az RLE-tömörítés noha szintén a felére csökkenti a többi ikon méretét, de közel sem takarít meg ennyi helyet.

Sőt, néha az RLE egyáltalán nem tud helyet megtakarítani...

Nézzük most ezt a 16×16-os ikont:

Nagyítsunk rá, hogy minden egyes pixel láthatóvá váljon:

Az ikon minden képpontja különböző színű, és nincsenek futamok.

A futamhossz kódolás egyáltalán nem képes egy ilyen képet tömöríteni. Ezt a példát csak ehhez a leckéhez találtam ki (ez a program generálta), ez nem olyasmi, ami gyakran előfordul.

A fényképek azonban hasonlóak ehhez az ikonhoz – a való világ tele van olyan részletekkel, amelyek megszakítják a futamokat.

A Khan Academy csapatának oldalán található ez a kedves fotó egy kutyáról, amint a számítógép képernyőjét nézi:

Normál felbontásnál úgy tűnik, mintha hasonló színű blokkok lennének, akár a kutya bundájában, akár a számítógép szürke képernyőjében.

Nagyítsunk rá a pixelekre:

Láthatod, hogy még a látszólag egyszerű számítógép képernyője is rengeteg hasonló, de nem teljesen azonos színt tartalmaz. A pixelek futamhossz kódolása ebben az esetben nemigen csökkentené a fájlméretet.

Az RLE tömörítés igen népszerű technika volt abban az időben, amikor a legtöbb számítógépen lévő kép korlátozott színpalettájú ikonokból állt.

Manapság a képeink összetettebbek, és nem tartalmaznak annyi azonos színű futamot.

Hol használják ma az RLE-t? A faxkészülékek még mindig használják az RLE-t a faxolt dokumentumok tömörítésére, mivel csak fekete-fehér betűket kell ábrázolniuk. A JPEG képek a tömörítés utolsó szakaszában használják az RLE-t, de először egy összetettebb algoritmussal tömörítik a fényképrészleteket. Ezt hamarosan részletesebben is megvizsgáljuk.

🙋🏽🙋🏻‍♀️🙋🏿‍♂️Kérdésed van a témával kapcsolatban? Szívesen válaszolunk, csak kérdezz alább, a „Kérdések” részben!