Tömörítés, kép ábrázolás

Informatika alapjai-4 Tömörítés

1/12

Tömörítés, kép ábrázolás [Forrás els sorban WIKIPEDIA] A tömörítés alapcélja, hogy információt – a számítástechnikában egy vagy több file-t - kisebb helyen lehessen tárolni, átvinni. A tömörítés lehet veszteségmentes (ZIP, TIF), vagy veszteséges (JPEG, MPEG). A tömörítéssel együtt történhet - adatvédelem: a tömörítéshez jó hatásfokú hibajavító kódolást használnak, amely u.n. folthibák esetén is lehet vé teszi a javítást. - titkosítás: a tömörített file csak kulcs megadása után fejthet ki. A tömörítés azon alapszik, hogy az információ tárolása redundáns, és olyan eljárásokat alkalmazunk, melyekkel a redundancia csökkenthet . A redundancia azt jelenti, hogy az elem sorozat (információ) elemei nem függetlenek egymástól. Ebb l kiindulva számszer;síthet az elem sorozat redundanciája, amely alapvet információelméleti fogalom (Shannon). A redundancia azt fejezi ki, hogy egy elem sorozatot mennyivel lehetne lerövidíteni úgy, hogy az eredeti információt vissza lehessen állítani. Elég nyilvánvalóan redundáns az írott beszédszöveg: nem lehet benne akármilyen karakter sorozat. El ször is kevés kivételt l eltekintve csak értelmes szavak vannak benne, az értelmes szavak értelmes mondatokat alkotnak. Egy szón belül is eltér az egyes bet;k el fordulási valószín;sége (leggyakoribb: E), magánhangzó után nagyobb valószín;séggel mássalhangzó következik, és fordítva. Hasonlóan redundáns a képek bit-mapként történ tárolása: - vonalas ábránál nagy összefügg fehér és kisebb, de összefügg fekete területek váltakoznak, tehát sokkal kisebb a váltás valószín;sége, mint az, hogy egy fehér pontot fehér pontok, fekete pontot fekete pontok vesznek körül. - fényképnél az egymás melletti képpontok többnyire kismértékben különböznek - filmben az egymás utáni kockák általában kismértékben különböznek.

Run Length Encoding (RLE) Futás hossz kódolás: egyforma adatokból álló sorozat helyett a sorozat darabszámát és az elemet továbbítjuk. Például WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

helyett:

12WB12W3B24WB14W

(W: fehér képpont, B: fekete képpont) Els sorban a fax technikában alkalmazzák. Legegyszer;bb esetben a tömörítés csak egy soron belül történik, a bonyolultabb algoritmus azt is kihasználja, hogy az egymás utáni sorok hasonlóak.

ZIP A legismertebb veszteségmentes tömörítési technika. 1989-ben Phil Katz dolgozta ki cégében, a PKWARE-ben. F jellemz k: - egy vagy több file egyetlen file-ba becsomagolva. Nyereség kisebb file-ok esetén a minimális blokk méret miatt (u.n. Cluster: tipikusan 4 kbyte). [20 db. 200 byte-os file egyenként tárolva 80 kbyte, tömörítés nélkül egyberakva ~ 4 kbyte, a szükséges adminisztrációval 8 kbyte] - a file-ok a ZIP file-ban szétválasztva vannak benne, egyenként törölhet k, módosíthatók, vagy új file-ok tehet k be.


2/12

-

a program az egyes file-okat különböz módszerekkel tömöríti: (nincs tömörítés,) Shrinking, Reducing, Imploding, Tokenizing, Deflating, Imploding, Method 11, BZip2. - a tömörítéssel együtt titkosítás is történhet (könnyen feltörhet ) - a hiba hatása korlátozódik arra az eredeti file-ra, melynek becsomagolt formájában a hiba el fordul. A felsorolt tömörítési eljárások közül a leggyakrabban alkalmazott a Deflating (= [gáz, leveg ] leeresztése). Ez az LZ77 eljárást és Huffman kódolást kombinálja. Az LZ77 eljárás – mint az összes eljárás, melynek neve LZ-vel kezd dik (pl. LZW) – Abraham Lempel és Jacob Ziv nevéhez köt dik (1977). A tömörítend file-ban ismétl d részeket keresünk, ezeket egy szótárban kigy;jtjük, és egy sorszámot rendelünk hozzájuk. A tömörített file két részb l áll: a szótárból és egy sorszám listából. Például legyen a file a következ szöveg: „Ha buta vagyok, nem tudom, hogy buta vagyok, mert buta vagyok.” Ebb l nyilván létrehozható a következ szótár és szöveg: $1=” buta vagyok” “Ha$1, nem tudom, hogy$1, mert$1.” A sorszám listában a sorszámok kódolására Huffman kódot alkalmazunk, azaz annál rövidebb a sorszám kódja, minél gyakrabban fordul el a szótár elem a file-ban. Nyilvánvalóan csak akkor van tömörítés, ha a szótár elemek sokszor fordulnak el . Tételezzük fel, hogy a tömörít csak egy szöveg karaktereit ismeri fel, így a karakterek kerülnek a szótárba. Ekkor a módszer a szöveg karakterenkénti Huffman kódolását eredményezi. Néhány ZIP tömörítési eredmény: Magyar nyelv; szöveg tömörítése: 114502 byte-ból 35990 byte (100%-68%=32%) Program forrás tömörítése: 1019565 byte-ból 203091 byte (100%-80%=20%) 26 db. vonalas BMP file: 88 Mbyte-ból 1,665 Mbyte (100%-98%=2%).

Képábrázolás A számítástechnikában a képeket kétféleképpen írhatjuk le: • vektorgrafikusan: ekkor a kép elemeit adjuk meg, például egy egyenes kezd és végpontjának koordinátáit, vastagságát, stílusát, színét. Alapvet en így m;ködik például a CorelDraw rajzolóprogram. • Raszter grafikaként: a képet raszterpontokra osztjuk, és az egyes pontok jellemz it (világosság, szín) adjuk meg. Nem foglalkozunk a kétféle eljárás el nyeivel-hátrányaival, és a továbbiakban csak a raszter grafikus ábrázolásról beszélünk. A legismertebb tömörítetlen raszter grafikus ábrázolási forma a Windows Bitmap. Az ilyen file-ok kiterjesztése általában .BMP. A bitmap file felépítése: Fejléc: a file mérete (x * y) a file típusa, ezen belül az egy pontot leíró bitek száma (B). Ez lehet 1 (fekete-fehér), 4 (16 szín;), 8 (256 szín;, vagy 256 szürkeárnyalatú), 16 (RGB555 vagy RGB565: alapszínenként ~5 bit, 65536 szín) vagy 24 (RGB888: alapszínenként 8 bit, 16 777 216 szín).


3/12

Színtábla: 4 és 8 bit/pont bitmap-nél megadja, hogy a 16, illetve 256 féle képpont milyen szín; (24 bites felbontásban). 16 és 24 bites bites felbontásban nincs színtábla. Bitmap: ennek mérete >= B * x * y / 8 byte. Például egy 8 x 10 pixeles kétszín; kép és bitmapja: 00000000 00h 00011000 18h 00111100 3Ch 01100110 66h 01000010 42h 01111110 7Eh 01111110 7Eh 01000010 42h 01000010 42h 00000000 00h A bitmap képek nagyon nagyok lehetnek. Egy 800 x 600 pontos 24 bites bitmap mérete: 800 x 600 x 3 byte = 1 440 000 byte. A képméret tömörítéssel csökkenthet (van RLE tömörítést alkalmazó BMP formátum, a legismertebb a JPEG képtömörítés).

Színlátás fizikája A látható fény hullámhossza ~ 400...700nm:

A tiszta színek spektruma egyetlen vonal, a kevert színek spektruma valamilyen hullámhossz eloszlású görbe.


4/12

Például egy villanólámpa fényének spektruma (4600K):

A CIE patkó diagram A diagram az összes látható színt mutatja. A színes terület peremén a tiszta színek, közép felé haladva a kevert színek látszanak. A fekete vonal a fekete test sugárzását mutatja a h mérséklet függvényében.

A szem A szem szerkezete:


5/12

A retinában kétféle fényérzékel sejt van. Pálcikák: egyenletesen elosztva helyezkednek el. Els sorban az éjszakai és a periferiális látásban van szerepük. Csak egyféle pálcika van, a pálcikák a színlátásban nem vesznek részt. Csapok: háromféle csap van, melyek a kék, zöld és vörös színre érzékenyek. Ezért ezeket Beta (blue = kék), Gamma (green = zöld) és Rho (red = piros) csapnak nevezik. A csapok színérzékenysége:

(A színvakság a csapok m;ködési zavaraival függ össze. Leggyakoribb a zöld-vörös színtévesztés, amikor a Gamma vagy Rho csapok hiányoznak, vagy a Gamma és Rho spektrum összecsúszik.) Az hogy valamilyen eloszlási spektrumot milyen szín;nek látunk, attól függ, hogy a háromféle csap milyen ingert kap. Ezért egy színes képhez nem kell végtelen sok színt generálni, hanem elég háromfélét – lehet leg úgy, hogy a három komponens a háromféle csapot ingerelje. A színes képerny n a kép RGB komponensekb l tev dik össze:

Látszik, hogy a szétválasztás nem tökéletes, például a kék foszfor fénye a Beta szenzoron kívül a Gamma és Rho szenzort is ingerli.


6/12

A szín a komponensek arányától függ. A következ ábra az úgynevezett szín kocka. Az ábra most az els dleges és másodlagos színeket mutatja a telített színt l a fehérig változóan:

Látszik, hogy például a sárga szín a piros és zöld összegeként állítható el , és minél több kéket keverünk hozzá, annál fehéresebb (precizebben: csökken a szín telítettsége). A 24 bites bitmap képnél egy pont színét és fényességét 3x8 biten adjuk meg, ahol a 3 byte az RGB komponensek intenzitása. A PC-ben a maximális intenzitású alapszínek 24 bites kódja: Kék FF 00 00 Zöld 00 FF 00 Piros 00 00 FF Ebb l tehet össze a többi szín, például: Sárga FF FF 00 Magenta FF 00 FF Fehér FF FF FF Szürke 80 80 80

Képtömörítés Vonalas ábra bitmapja jól tömöríthet ZIP-pel (ld. korábban). Nem ilyen jó a helyzet fénykép tömörítésnél. Az alábbi példában szerepl 519 kbyte-os kép ZIP-ple tömörítve 444 kbyte (!). Ezért fényképek tömörítésére más elven m;köd eljárást dolgoztak ki. Ez a JPEG. A JPEG veszteséges tömörítés, azaz nem állítható vissza pontosan az eredeti file, de a képmin ség romlása nagyon kicsi lehet. A JPEG eljárásnak a felhasználó szempontjából legfontosabb tulajdonsága, hogy különböz min ség; tömörítést tesz lehet vé, és ha a min ségb l engedünk, a tömörítés egyre nagyobb lehet. A következ képsorozat egy BMP képet, és annak kétféleképpen tömörített változatát mutatja. Látszik, hogy 10-es tömörítésnél nincs észrevehet min ségromlás, 90-esnél a romlás jól észrevehet , de a kép azért még használható. Az utóbbi esetben a tömörített képfile a BMP 1,64%-a! Minden digitális fényképez gép tud JPEG képet készíteni, a jobbak u.n. RAW képet is, amelyik pontosan a gép által felvett bitmap kép teljes színfelbontásban, kiegészítve a felvételre vonatkozó információkkal (felvétel ideje, beállítások). Ha a képen képfeldolgozást akarunk végezni, akkor RAW formátumban érdemes menteni. A RAW formátum nem szabványos, gyáranként, s t géptípusonként is változhat.


JPEG tömörítés

423 x 408 x 24bit BMP: 519030 byte

JPG 10-es tömörítés: 58908 byte

JPG 90-es tömörítés: 8492 byte

7/12


8/12

Csak felsoroljuk a tömörítés lépéseit, általában nem magyarázzuk azokat. 1. Szétválasztjuk a fényesség és szín információt (RGB YCbCr transzformáció) A fényesség információt megkapjuk, ha az RGB komponenseket súlyozottan összeadjuk: (1)

Y = 0.299 * R + 0.587 * G + 0.114 * B (0.299 + 0.587 + 0.114 = 1)

A különböz konstansok azt fejezik ki, hogy a szem pirosra, zöldre és kékre eltér en érzékeny, legérzékenyebb zöldre, legkevésbé érzékeny kékre. A színtartalmat két változóval adjuk meg: a kék szín és a fényesség, valamint a piros szín és a fényesség kölönbsége (2) (3)

Cb = 0.5 * (B - Y) Cr = 0.5 * (R - Y) Ha Akkor Y

R, G, B 0...1

0...1 Cb, Cy -0.5...+0.5

(Az átalakítás lényegében ugyanaz, mint a PAL színes TV adásban használt fényesség/szín szétbontás, ahol ennek els dleges célja a fekete-fehér TV vev kkel való kompatibilitás megtartása volt.) Y, Cb, Cr-b l könnyen visszaállítható RGB, az (1)..(3) egyenletek felhasználásával. Színes és a szürkeárnyalatos kép:

2. A színtartalmat redukálhatjuk, azaz lecsökkentjük a felbontást. Ezt azért tehetjük meg, mert a szem fényesség felbontása sokkal jobb, mint szín felbontása.


9/12

[A lehet ségek 4:4:4 (nincs redukálás), 4:2:2 (redukálás 2-vel vizszintesen), leggyakrabban 4:2:0 (redukálás mindkét irányban 2-vel). A továbbiakban az eredeti Y és a redukált Cb és Cr táblát hasonlóan kezeljük, azaz 3 bitmap-en dolgozunk. 3. A bitmapeket 8 x 8 –as mez kre osztjuk. Az baloldali ábra a felosztást, a jobboldali egy 8x8-as mez t mutat.

4. A 8x8-as mez kön diszkrét cosinus transzformációt hajtunk végre (ez amplitúdófrekvencia átalakítás, hasonlít a diszkrét Fourier transzformációhoz). A transzformáció eredménye is 8x8-as mátrix. DCT-II

Egy alkép:

minden elemb l kivonunk 128-at, hogy a számtartomány -128..127 legyen:


10/12

A DCT eredménye egészre kerekítve:

A frekvencia balról jobbra és fentr l lefelé n , a bal fels sarokban lév nagy szám a DC összetev (a 0 frekvenciás komponens, vagy átlag). A mátrix a vízszintes és függ leges térbeli frekvencia komponenseket mutatja. 5. Kvantálás A felbontás csökkentésére minden komponenst elosztunk egy számmal. Ezt azért tehetjük meg, mert a szem ugyan nagyon érzékeny a nagyobb területek fényesség változására, de nem észleli pontosan a gyorsan változó kisebb területek fényességét. Egy szokásos kvantálási mátrix:


11/12

Elvégezve a kvantálást, az el z DCT mátrixon az eredmény:

(A bal fels elemre: -415 / 16 = 25.94) Látszik, hogy nagyobb frekvenciákon csupa 0 együttható van. A képmin séget és a tömörített képméretet a kvantálás mértéke szabja meg. 5. Az eredményt úgynevezett Entrópia kódolással kódoljuk, amiben benne van az együtthatók átrendezése, RLE és Huffman kódolása (az utóbbi kett t a ZIP tömörítésb l ismerjük). Az u.n cik-cak átrendezést a következ ábra szemlélteti:

Kb. 10-szeres tömörítésnél a JPEG-b l visszaállított kép szemmel nem különböztethet meg az eredetit l, 100-szoros tömörítésnél már jelent s eltérések vannak, de a kép jól felismerhet .

MPEG tömörítés Lényege: a mozgókép „els ” kockáját tömörítjük. A további kockáknál kihasználjuk, hogy azok az el z kockához hasonlítanak, és csak a különbséget visszük át, persze ezt is tömörítve. Bizonyos számú kocka után, vagy ha vágás van a filmben, újra a teljes képtartalmat visszük át. MPEG-1 CD-ROM-on és VIDEO-CD-n használt eljárás (elavult) MPEG-2 TV min ség; képátvitelt biztosít (normál vagy HDTV). A digitális TV m;sorszórásban és újabb video felvev knél használt MPEG-4 Nagyon kisfelbontású és sávszélesség igény; eljárás. Újabban a nagyon nagy felbontású HDTV alkalmazásokban is használják.


12/12

Egy TV csatornán a bitsebesség a felbontástól és a tömörítést l függ. Az ismert eljárások bitsebessége:

Látszik, hogy a PAL átvitel sebessége 216 Megabit/s, amit az MPEG-2 eljárás 4-6 Megabit/sra csökkent. Így egy kétórás film tárolási igénye kb. 4..6 * 106 Megabit/s * 7200s / 8 = 3,6..4,8 Gigabyte. Ez a DVD igényelt kapacitása.

Tömörítés, kép ábrázolás

Recommend Documents