A számítógépes képfeldolgozás lényegében nagy adathalmazon végzett adatfeldolgozás. Mivel az adatok tárolása és átvitele a képek esetében is egyike az alapfeladatoknak, az adattömörítés fontos. Ebben a részben a képtömörítés alapelveit, legfontosabb típusait és gyakorlati alkalmazásait ismertetjük.

Alapfogalmak

A hagyományos képtárolás adathordozói a fotóanyagokon alkalmazott ezüstvegyületek, a képmagnetofon szalagja és a számítógépes képfeldolgozás számos példája pl.: mikrofilm-alpú, tv-képarchiváló rendszer, sajnos a tapasztalat szerint sem megbízhatóságban, sem adathűségben és sebességben nem váltották be a hozzájuk fűzött reményeket. A kiutat a digitális adathordozók megjelenése jelentett.

Hasonló a helyezet a képek átvitele terén is. Az adatok digitális kezelése minden tekintetben előnyösebb az analóg megoldásoknál. Mivel azonban mind az adattárolók, mind pedig a hírközlési csatornák használata költséges, természetes, hogy a digitális képtárolás és képátvitel megjelenésével egyidejűleg  jelentkezett az az igény is, hogy a képi információt minél hűbben, de ugyanakkor minél kisebb adatmennyiséggel lehessen ábrázolni, erre irányul a képtömörítés.

A képtömörítés iránti érdeklődés több, mint 30 éves múltra tekint vissza. A kezdeti időszak erőfeszítései elsősorban az analóg módszerekre korlátozódtak, tipikus példájuk a képi jelekre vonatkozó sávszélesség-csökkentés. 
A digitális feldolgozás elterjedésével az érdeklődés eltolódott a digitális képtömörítés felé. A napjainkban elterjedő multimédia eszközök működése szintén elképzelhetetlen lenne a kép és a hang rögzítése terén egyaránt alkalmazott adattömörítés nélkül. 

Redundanciák

Ugyanazt az információt különböző fajtájú és mennyiségű adat hordozhatja. Az adathalmaz redundáns, ha mennyisége nem a lehető legkevesebb. Adattömörítésen azt a folyamatot értjük, amelynek során csökkentjük a bizonyos információt reprezentáló adatok mennyiségét. A számítógépes képfeldolgozás területén háromféle redundanciát szokás megkülönböztetni.

1. Kódolási redundancia

Tekintsünk egy bináris képet, amelyben mindössze kétféle világosságkód fordul elő, azonban ezeket 1 byte-on tároljuk. 0 a fekete 255 a fehér. Világos, hogy ez az információ egy biten is ábrázolható. Ez esetben a kódolás redundanciája ad módot a tömörítésre.

2. Képi redundancia

A képben lehetnek olyan belső összefüggések, amelyek kihasználása esetén  az ábrázoláshoz kevesebb adat is elegendő. Pl.:

- ha a képen csak azonos színű objektumok vannak, homogén háttér előtt, hatékonyan kódolható az objektumok határoló vonalainak megadásával.
- ha az egymás után következő képek csak kis mértékben különböznek, gazdaságosan kódolhatók a képek közötti változások megadásával.
- ha a képen szabályos alakzatok vannak, hatásosan kódolható az alakzatokat generáló függvénykapcsolatok leírásával.

3. Pszichovizuális redundancia

A képek sok olyan információt tartalmaznak, amelyet az emberi látórendszer nem érzékel. Ha csak a kép megjelenítése a feladat, de egzakt feldolgozására nincs szükség, a felesleges információ kiszűrésével adattömörítés érhető el. Ez az eljárás információvesztéssel jár. Pl.:

- ha a képpontokat 24 biten ábrázoljuk, ami közel 17 millió féle színt   tudnánk megjeleníteni, de a látórendszer felbontását ez messze meghaladja, nyilvánvaló , hogy elég csak a legjellemzőbb színek megtartása.
- ha a képen látható objektumok erősen zajosak, zajszűréssel csökkenthetjük a látás szempontjából felesleges információ mennyiségét.
-ha a kép kevés látnivalót tartalmaz túl nagy méretben, akkor a kép mérete arányos csökkenthető, amíg a csökkentés nem megy a látvány rovására.

Egy adattömörítési eljárástól általában az alábbiakat várjuk el:

- a tömörítési arány a lehető legkisebb legyen, az algoritmus használja ki a tömörítendő adathalmaz sajátos szerkezetét.
- az algoritmus legyen hatékonyan implementálható
- illeszkedjék a meglévő rendszerek kötött lehetőségeihez.

Képek tömörítésekor bizonyos feltételek teljesülése esetén általában megengedhető az információveszteség.

Képtömörítési eljárások

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

A veszteségmentes képtömörítés lehetővé teszi, hogy a helyreállítás során az eredeti képpel tökéletesen azonos képet kapjunk vissza. Ez azt jelenti, hogy a bemenő- és a kimenőkép megfelelő képpontjainak világosságkódja azonos. Ilyen eljárások akkor indokolta, ha a későbbi felhasználás során nincs semmilyen lehetőség a képtartalom módosítására. Sajnos, a szokásos összetételű tónusos képek esetén csak nagyon kis tömörítés érhető el, az 1/2 arány már jónak mondható.

A veszteségmentes tömörítés egyszerű esete, ha a sorfolytonos tárolt kép leírására a világosságkódok helyett pontonkénti változásukat használjuk. A szomszédos képpontok nagy valószínűséggel közel azonos fényességűek, illetve színűek.

Változó hosszúságú kódolás

Változó adathosszúságú kódolás (VLC=variable length coding) során a tömörítési eljárás kizárólag a kódolási redundancia csökkentésén alapul. A szokásos esetekben 1/2, nagyon jó esetben  az 1/30 tömörítési arány is elérhető. Az alábbiakban két eljárást ismertetünk:

Huffman-kódolás

Az egyik legismertebb és leggyakrabban alkalmazott eljárás A. Huffmantól származik, 1952-ből. Lényege, hogy egyes adatokhoz rendelt kód hossza (bitszám) fordítottan arányos előfordulásuk gyakoriságával. A kódok megállapítására a következő egyszerű eljárás szolgálhat:

- írjuk fel a bemenő adatokat egymás alá az előfordulási gyakoriságuk szerint növekvő sorrendben,
- induljunk el a tábla két legkisebb gyakoriságú eleménél és vonjuk össze őket, úgy, hogy egyben adjuk össze a hozzájuk tartozó gyakoriság értékeket is,
- ezt a páronkénti összevonást mindaddig folytassuk, amíg az összeggel el nem érkezünk a teljes képpontszámig.
- ezután minden egyes adathoz olyan kódot rendeljünk, melynek bitszáma megegyezik az adatot tartalmazó összevonások számával. A kód azon bitjei legyenek 1 értékűek, amelyek a hozzájuk tartozó összevonásokban a párjuknál feljebb voltak.

Aritmetikai kódolás

Bár az aritmetikai kódolást a változó hosszúságú eljárások közé soroljuk, valójában egy nagy bitfolyam áll elő, amelyben a bemenő és a kimenő adatok részletei között nincs egyértelmű megfeleltetés. Az eljárás a bemenő adatok sorozatának egy részletéhez rendel kódot. Előnyei: a lokális adaptív változata is könnyen programozható, s így  igen kis tömörítési arányok érhetők el, ellentétben a Huffman kódolással, az adatokhoz nemcsak egész hosszúságú kód tartozhat, ezáltal a tömörítés tovább növekszik.

Bitsík-kódolás

A bitsík-kódolás szintén a kódolási redundanciára épül, de kihasználja a világosságkódok közötti korrelációt is. A lényege, hogy a bemenő képet kódolás előtt felbontjuk annyi független képre, ahány bitesek a világosságkódok, így minden részkép egy-egy bitsík adatait tartalmazza. A kapott egybites képeket ezután tömörítjük valamilyen jó hatásfokú veszteségmentes eljárással. Helyreállításnál a kép fokozatosan alakul ki.

Homogén foltok kódolása

Az alábbi négyesfa generálás néven ismert eljárással túlnyomó részt nagy homogén foltokat tartalmazó, bináris képeket lehet hathatósan tömöríteni, mert lényegében egy speciális fára fűzi fel a képi adathalmazt.

Határvonal-kódolás

A homogén foltok kódolásának másik gazdaságos módja, hogy a foltokat határoló vonalakat kódoljuk és kijelöljük azokat a zárt tartományokat, amelyek nem a háttérhez hanem az objektumhoz tartoznak.

Kódolás előrebecsléssel

A képi redundancia kihasználásának egyik egyszerű módszere az előrebecslés (prediction). Ez azon alapul, hogy a kép közeli részletei között nagymértékű a korreláció, így a kép adott részlete alapján a közeli környezete többé-kevésbé megbecsülhető.

Ha sorfolytonosan haladunk balról jobbra és ismerjük az aktuális, valamint az előző világosságkódot, akkor a sorban következőről feltételezhető, hogy az elődeinek megfelelő tendencia rá is érvényes. Ebből kiindulva a képet alapvetően előrebecsléssel állítjuk helyre. A kódolás során pedig a kép helyett csak azokat a korrekciós adatokat tároljuk el, melyek az előrebecslés tévedéseit kijavítják.

Veszteséges tömörítés

A veszteséges képtömörítés értelemszerűen nem teszi lehetővé az eredeti képtartalom maradéktalan helyreállítását. A leggyakoribb követelmény a látvány változatlansága, ami megengedi, hogy a bemenő- és a kimenőkép megfelelő világosságkódjai eltérőek legyenek.

A veszteséges eljárásokkal viszonylag nagy tömörítés érhető el, a megengedett minőségromlás mértékétől függően. Tipikus az 1/20, de ha csak a kép felismerhetősége a cél, az 1/100 arány sem lehetetlen. Különböző összetett eljárásoknál az 1/70 arány még jó minőségű helyreállítást tesz lehetővé. Két fő csoportra bonthatók az eljárások:

- Az előrebecslésen alapuló módszerek általában kevés információ ismeretében nagy számú világosságkódot becsülnek meg előre. A tömörítés pontossági igényétől függően korrigálni kell a tényleges értékektől való eltérést. Jó esetben a korrekció mértéke viszonylag kicsi, ekkor a korrekciós paraméterek gazdaságosan  adhatók meg változó hosszúságú kódokkal.

- A matematikai transzformáción alapuló módszereknél a képet a világosságkódok helyett bázisfüggvények együtthatóival írjuk le, illetve ugyanezen bázisfüggvény adott pontbeli súlyozott összegzésével állítjuk helyre.

JPEG szabvány

A JPEG (Joint Photographic Experts Group) ajánlások napjainkra az állóképek veszteséges tömörítésének szabványaivá váltak. Az eljárás (adaptív) diszkrét koszinusz transzformáción (DCT) alapul és eleve úgy alakították ki, hogy mind hardverben, mind szoftverben egyaránt könnyen lehessen megvalósítani. Segítségével 1/30 tömörítési arány is elérhető a megengedett minőségromlás mértékét a felhasználó paraméterezheti.

A JPEG tömörítési eljárás egymástól függetlenül kezeli a színösszetevőket, vagyis a színes képek esetében mind a háromra végre kell hajtani. Ha a tömörítés veszteségmentes volna, nem lenne túl nagy jelentősége annak, hogy a világosságkódokat milyen színtérben ábrázoljuk. Mivel azonban a JPEG megengedi a veszteséget, célszerű olyan világosságkód-ábrázolást választani, amelyik a legkevésbé érzékeny az elkövetett hibákra, illetve amelyben az adatok belső összefüggései a legnagyobb tömörítést teszik lehetővé. Pszichovizuális okok miatt az RGB színrendszer helyett előnyösebb az YUV használata. Ezért a színes képeket tömörítése előtt a színrendszert transzformálni kell YUV rendszerbe. Az eljárás első lépésében az adott színösszetevőt egymástól független, 8*8-as blokkokra bontjuk, amelyeket ezután függetlenül kezelünk. A transzformáció végrehajtásával blokkonként (8*8=) 64 együtthatót kapunk a kétdimenziós diszkrét bázisfüggvényekhez. Az eljárás képlettel a következőképpen fejezhető ki:

ahol

- N a blokk mérete
- q(m,n) a világosságkód az (m,n) blokk-relatív koordinátájú képpontban
- k,l blokk-relatív koordináták.

A fenti képlet közvetlen számításokra alkalmatlan, mivel valós adatokkal kellene nagyszámú műveletet elvégezni. A transzformáció igen jó közelítése pl. az RVFFT (Real Valued Fasf Fourier Transform) eljáráson alapul. A DCT transzformáció a kiindulási adatoknál inkább többet eredményez, mint kevesebbet, hiszen a kapott együtthatókat nagyobb pontossággal kell ábrázolni, mint az eredeti világosságkódokat. Előnye mégis abban van, hogy a 64 transzformációs együttható gyakorlatilag nem mutat belső összefüggést, szemben a blokk többnyire erősen korreláló 64 képpontjával. (A diszkrét koszinusz transzformáció a Karhunen-Loéve transzformációt megközelítő mértékben tudja az adatokat független paraméterekké alakítani.) Pszichovizuális kísérletek bebizonyították, hogy ez a 64 együttható nem azonos mértékben fontos az eredetit közelítő látvány létrehozásához. Kiderült, hogy a nagyobb frekvenciájú képtartalomváltozást reprezentáló bázisfüggvények ebből a szempontból még akkor sem játszanak túl nagy szerepet, ha a hozzájuk tartozó együttható értéke nagy. (Megjegyzendő, hogy a kísérleteket megadott képernyőméret-látótávolság összefüggések mellett végezték, s a DCT tömörítési eljárás alkalmazása esetén is feltételezik a képhelyreállítás bizonyos standard körülményeit.)

Az előbbiekből  tehát az következik, hogy a nagyobb frekvenciájú bázisfüggvények együtthatói sokkal durvábban (pontatlanabbul) kódolhatók, mint a kis frekvenciájúaké. A kódolás pontosságát úgy is előírhatjuk, hogy megszabjuk, melyik együttható hányféle értéket vehet fel, azaz milyen pontosságú a kvantálása. (A legegyszerűbb kvantálás, ha az együtthatót elosztjuk egy adott számmal és a hányados egészrészét vesszük. Minél nagyobb az osztó, annál kevesebb különböző eredményt kaphatunk, így visszaszorzás után annál durvább lesz a "lépcsőzés". Ha pl. egy együttható értéke 11 és a kvantálási osztó 16, akkor az eredmény 0 lesz. Ugyancsak nulla lesz az eredmény, ha az együttható értéke a {-15, .., 15} tartományban bármilyen más értéket vesz fel.

Tipikus kvantáló- (azaz 64, együtthatóról-együtthatóra változó osztót tartalmazó) mátrixokat mutatunk az alábbi ábrán a luminanciához (a), illetve a krominanciához (b).

(a)                                                                    (b)

A szokásos JPEG-alapú rendszerekben a képminőséget (s ezzel a tömörítési arányt is) pl. a kvantálási szintek változásával lehet befolyásolni. Minél feljebb toljuk a kvantálási szinteket, annál durvább lesz a kép, viszont annál kisebb lesz a tömörítés aránya.

A kvantálás után kapott 64 együttható túlnyomó része 0 vagy igen kis abszolútértékű szám lesz. A kvantálási adatok megválasztásából következik, hogy a legtöbb nem-zérus értékű együttható a blokk bal felső sarkának közelében található, s attól távolodva egyre több lesz a nulla. Ez a tény igen jól kihasználható a kódolás során.

Evégett rendezzük át az együtthatókat abban a sorrendben, ahogyan a blokk bal felső sarkától a jobb alsó sarok felé haladó törtvonalon elhelyezkednek.

1 2 6 7 15 16 28 29 3 5 8 14 17 27 30 43 4 9 13 18 26 31 42 44 10 12 19 25 32 41 45 54 11 20 24 33 40 46 53 55 21 23 34 39 47 52 56 61 22 35 38 48 51 57 60 62 36 37 49 50 58 59 63 64

Az első együttható a konstans-függvényt reprezentálja, amely a blokkon belüli világosságkódok átlagértéke. Ezt az együtthatót (az elektronika egyenáram /direct current/ elnevezésének analógiájára) DC együtthatónak nevezik. A többi együttható a nem-konstans bázisfüggvényekhez tartozik; ezek az AC - (váltakozó összetevő alternating current) együtthatók. A JPEG szabvány szerint a blokkok DC együtthatóit az AC együtthatóktól függetlenül kódolják, és helyettük a blokkonkénti változásukat tárolják. Az AC együtthatók kódolására változó hosszúságú kódokat (adaptív VLC eljárással) használnak.

A tömörítés eredménye az előbbiekben leírtak szerint olyan bitfolyam, amelyik közvetlenül felhasználható az eredeti képtartalom rekonstrukciójára; ekkor sorfolytonos kép-felépítésről beszélünk. Ez a JPEG eljárás leggyakoribb felhasználási módja; pl. képi másolat készítéséhez erre van szükség.

Egyes felhasználási területeken kiemelt fontosságú, hogy a kép helyreállítása során minél hamarabb kerüljön felismerhető állapotba, még ha ennek az is az ára, hogy a teljes rekonstrukció az előbbinél kissé tovább tart (progresszív képfelépítés). Előbb a DC együtthatók alapján áll össze egy igen durva kép, melynél minden 8*8 pontos blokk egy-egy átlagérték jellemez. A következő ciklusban az első AC együtthatók szerinti módosítás történik meg minden blokkban; ez 4*4 pontos mintákat eredményez, s így haladunk az egyre finomabb felbontás felé. (Tipikus alkalmazási terület: képi adatbázisban kereséskor a durva képből egyre finomabb képet hozunk létre, a folyamat bármikor megszakítható - ha kiderül, hogy másik képre van szükség.)

Eredeti kép: méret: 12.3 kbyte
10%-os tömörítés méret: 11.6 kbyte	20%-os tömörítés méret: 8.5 kbyte
30%-os tömörítés méret: 6.5 kbyte	40%-os tömörítés méret: 5.6 kbyte
50%-os tömörítés méret: 4.8 kbyte	60%-os tömörítés méret: 4.3 kbyte
70%-os tömörítés méret: 3.7 kbyte	80%-os tömörítés méret: 3.0 kbyte
90%-os tömörítés méret: 2.1 kbyte	99%-os tömörítés méret: 1.2 kbyte

A JPEG tömörítés hatékonysága
(látható, hogy 70%-os tömörítésnél még alig észrevehető minőségromlás jelentkezik)

Fraktál-tömörítés

Meg kell említenünk még egy másik, az eddigiektől gyökeresen eltérő elvű, igen jó hatásfokú képtömörítési eljárást is, amely a fraktálokon alapul és 1/40-1/80 tömörítési arányt eredményez, kismértékű látványromlás árán. (A fraktálokat Michael Barnsley, a számítógépes grafika egyik úttörő kutatója fedezte fel.)

Az eljárás lényege, hogy megkeresi a tónusos kép fraktálokkal történő eőállításának szabályait és ezeket tárolja. Hátránya, hogy igen jelentős a tömörítés-irányú számítás-igénye; ezen speciális processzorok alkalmazásával segítenek. 

Ellentétben a tömörítés viszonylagos lassúságával, a helyreállítás rendkívül gyors lehet; pl.: egy 320*200 képpontból álló 24 bit/képpont színfelbontású kép 386/25 MHz PC-n kevesebb mint egy másodperc alatt készül el. További előny, hogy a helyreállítás során a kép tetszőlegesen nagyítható, s ekkor látszatra új részletek tűnnek elő, a globális mintázatok lokális ismétlésével.