Grafikus képek kódolásának folyamata
A grafikus képek kódolásának folyamatát három részre bontjuk:
Szűrés (mapping): szükségtelen redundanciák kiszűrése, az így kapott kép kisebb méretű lesz mint az eredeti kép.
Leszűkítés (quantization): az input kép méreteinek leszűkítése a lehetséges output méretre. Előfordulhat, hogy nincs szükségünk a teljes méretű képre mind az 5100x6600 pontjával együtt, csak bizonyos részleteit kívánjuk használni, amely elfér a képernyő 640x480-as felbontásán. Természetesen, ha az eredeti képre is szükség van, akkor kihagyjuk ezt a lépést, mert a folyamat visszafordíthatatlan.
Kódolás: a kódolt, tömörített adat- és a megfelelő kódtábla előállítása.
Huffmann kód algoritmusa
A Huffmann kód algoritmusa során egy bináris fát építünk fel:
1. Legyen az OP halmaz az előfordulási gyakoriságok halmaza.
2. Legyen Pi és Pj az OP halmaz két legkisebb eleme.
2.1. Hozzunk létre egy új csomópontot az Nij -t, amely a Pi és Pj apja a fában
2.2. Az Nij -->Pi él címkéje legyen 0, az Nij -->Pj él címkéje pedig 1.
2.3. Legyen P(Nij)=Pi+ P, , a Pi –t és a Pj-t töröljük az OP halmazból és P(Nij) -t felvesszük az OP halmazba.
3. Ha az OP halmaz egy elemű, akkor vége, egyébként folytassuk a 2. ponttól.
Az algoritmus vége után egy bináris fát kapunk, melynek levelei az input ábécé elemei. A gyökérből az egyes levél elemhez vezető úton lévő címkéket egymásután írva kapjuk az inputelem kódját.
Az algoritmusból adódik, hogy a gyökérhez nem rendelünk címkét. Az OP halmaz előállítása például történhet úgy, hogy megszámláljuk egy elem (pl. egy szín) előfordulását, majd a kapott értéket elosztjuk az input szöveg hosszával. 256 színű kép esetén minden képpont egy B-on tárolódik, ezért ilyenkor a kép B-okban mért hosszával osztunk.
A kódolás során figyelembe vesszük, hogy a kiszámított valószínűségek összege 1.
Példaként nézzük meg egy 100 B méretű, 7 különböző színt tartalmazó kép átkódolását. Az egyes színek előfordulási valószínűségét a táblázat tartalmazza.
Figyelembe véve, hogy az eredeti input kép pontjai azonos hosszúságú elemekből épülnek fel a használt színek számától függően (pl. 1 képpont 1 B -on tárolódik), igen hatékony tömörítést érhetünk el, ha a leggyakrabban előforduló elemeket (kép esetén ez általában a háttérszín) rövidebb kóddal helyettesítjük. Ezen az elven alapszik a Huffman kód is. Ennek a kódnak a lényege, hogy meghatározzuk az input kép elemeinek előfordulási valószínűségét, vagy az előfordulási gyakoriságát.
A módszer lényege, hogy az input kép különböző elemeit tekintsük az input ábécének, pl. ha a kép maximum 256 színt használ (1 B-os tárolás) akkor értelemszerűen az input ábécé elemszáma is maximum 256. Az input ábécé elemeit növekvő sorrendbe állítjuk előfordulási valószínűségük szerint, és a sorrendnek megfelelően egyre rövidebb kódot rendelünk az elemekhez. Természetesen adatvesztés nélküli egyértelmű kódot kell előállítanunk.
RLE algoritmus
Ismétlődésen alapuló tömörítés, amit legegyszerűbben a következő példával szemléltethetjük. Kódoljuk a következő input jelsorozatot:
Input: 0000033000344 13 byte
Output: 5023301324 10 byte
azaz 5db. 0, 2db 3, 3db 0 1db 3, 2db 4.
Tehát a kód szövegben az első byte tartalmazza, hogy hány db, a második byte pedig, hogy milyen jel következik. A példánkban 3 B-ot takaríthatunk meg. TrueColor képeknél az RLE tömörítés gyakran hosszabb kódot eredményez, mint a forrás kép mérete.
Természetesen csak akkor hatásos ez a tömörítés, ha az input kép igen sok azonos képpontot tartalmaz egy sorban. Az alacsonyabb hatékonyság mellett az algoritmus igen gyors, egyszerű és könnyen programozható. RLE rendkívül népszerű és elterjedt az olyan alkalmazásoknál, ahol a tömörítés mellet fontos a kép gyors visszakódolása (előállítása a kódolt fájlból).
Az RLE algoritmus (Run-length encoding), azaz futáshossz szerinti tömörítés a grafikus képek gyors, de nem túl hatékony tömörítési ismétlődésen alapuló algoritmusa.
Background Block Skipping (BBS) algoritmus
Az algoritmus javított változata a Background Block Skipping (BBS). Az algoritmus abban különbözik az RLE-től, hogy a háttér színt nem kódolja, tulajdonképpen a háttér blokkok kihagyásáról van szó. Tekintsünk egy példát:
<math display="block" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow>
<mtable columnalign="left">
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mtext>Input</mtext>
</mrow>
</mtd>
<mtd columnalign="left">
<mrow>
<mn>0</mn><mn>0</mn><mn>0</mn><mn>0</mn><mn>0</mn><mn>3</mn><mn>3</mn><mn>0</mn><mn>0</mn><mn>0</mn><mn>3</mn><mn>4</mn><mn>4</mn><mn>2</mn><mn>2</mn><mn>0</mn><mn>0</mn><mn>0</mn><mn>0</mn><mn>0</mn><mn>0</mn><mn>1</mn><mn>1</mn><mn>1</mn><mn>1</mn><mn>1</mn><mn>2</mn><mn>1</mn><mn>1</mn>
</mrow>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mtext>Output</mtext>
</mrow>
</mtd>
<mtd columnalign="left">
<mrow>
<mn>5</mn><mn>2</mn><mn>3</mn><mn>1</mn><mn>0</mn><mn>1</mn><mn>3</mn><mn>2</mn><mn>4</mn><mn>2</mn><mn>2</mn><mn>2</mn><mn>1</mn><mn>5</mn><mn>1</mn><mn>1</mn><mn>2</mn><mn>2</mn><mn>1</mn>
</mrow>
</mtd>
</mtr>
</mtable>
</mrow>
<annotation encoding="MathType-MTEF">
</annotation>
</semantics></math>
A kövéren szedett számok pozíciókat jelölnek megadva, hogy hol következik a háttértől különböző érték.
21. századi közoktatás - fejlesztés, koordináció (TÁMOP-3.1.1-08/1-2008-0002)
