2017/09/26

JPEG alapok 2 blokkosítás és a diszkrét koszinusz-transzformáció

Előzmények a RGB - YCbCr átalakítás. Ebben a lépésben még sem veszteség, sem tömörítés nem történik. Sőt.

2. Következő lépés a keletkezett három új csatorna (Y/Cb/Cr) 8X8-as blokkokra történő szegmentálása (MCU - minimum coded unit) - ezek határainak elhelyezkedésén sok fog múlni, ideális lenne ha a kép X és Y irányban is osztható lenne 8 pixellel. Mivel a fényképezőgépek mind tudnak JPEG-et menteni, adta magát a kérdés, hamar csekkoltuk is, minden gépünk maximális felbontása felosztható 8x8 egész számú többszöröseire. Gondolom erre a gyártók figyelnek, ha nektek van olyan gépetek, ami nem ilyen, írjátok meg. A wiki szerint a 8x8-as bontás oka történelmi, az IC technológia ezt tette lehetővé, és mivel bevált, azóta is ez maradt. Máshol azzal magyarázzák, hogy a 16x16 túl komplex lenne. Amennyiben a képet már megfaragtuk és már nem osztható maradéktalanul nyolccal, a csonka (<8pixel) blokkokat kiegészíti (padding), hogy a műveleteket el tudja végezni, majd trimmeli, hogy te ne vedd észre a trükköt

3. DCT - diszkrét koszinusz transzformáció, na ez a rész eddig a legdurvább, pedig ha sikerül megérteni, akkor egyszerű. Mindenesetre nem azért diszkrét, mert kevesen értik és azok sem beszélnek róla. Tele van vele az internet.

Lényege, hogy az adatokat különböző frekvenciájú koszinusz hullámokkal írja le. OK, mindjárt találunk rajta fogást. Lássuk mit értünk a képen kis és nagyfrekvencia alatt.

A képen alacsony frekvencia (luminanciában vagy kromában) jellemzi azokat a területeket, ahol a változás lassan (nagyobb felületen) következik be (pl. egy világoskék ég degradéja a sötétebb felé), vagyis itt nagy a hullámhossz. Nagy frekvencia jellemzi viszont a finom részleteket, ahol a változás akár pixelről pixelre történik (pl. apró pixelméretű fűszálak, pixelméretű sakktábla), ez rövid hullámhossz. A nagy frekvenciás komponensek a zaj-szerű képződmények, kis frekvenciásak a blokkon átívelő képződmények.
Más megközelítésben a képi elemek szélei mentén nagyfrekvenciás (pl egy lapi széle), a homogén felületeken alacsony frekvenciás komponensek vannak (a lapi felülete, amennyiben nem durván textúrás, mert az szintén magas frekvencia lenne).

Azt olvastuk, hogy az emberi látás sajátossága, hogy a szélek érzékelése lerontja a veszteségből adódó hibák észlelését, sokkal feltűnőbbek, idegesítőbbek a veszteségek a homogén felületeken. Ezt lehet ha majd később ellenőrizzük, egyelőre elfogadjuk. Ha sikerül szétválogatni a kép (még mindig 8*8 pixelről van szó!) komponenseit frekvenciák szerint, akkor külön lehet kigyomlálni a nagy- és kisfrekvenciás összetevőket, a nagyokat sokkal jobban lehet ritkítani, az alacsonyabbakat kevésbé, az emberi szem érzékenységével és a vállalt veszteséggel összhangban.
Nagyobb és kisebb frekvenciás blokkok a kép különböző részeiről.
Mellesleg a hibrid képek is az emberi látásnak ezen a jellegzetességén alapulnak, egyik képnek az alacsony, másiknak a magas frekvenciájú komponenseit keverik össze, de hibrid képekről majd máskor lesz szó.

Lássuk gyakorlatban a fenti elméletet. A képlettel inkább nem fárasztom magunkat. Inkább sok-sok képernyőképpel fárasztom. Nekünk így sikerült megérteni a dolgot. Egy dimenzió mentén így lehet leírni hullámmal egyetlen pixelsort.
Forrás 

Forrás. Példaként egyetlen dimenzió mentén a képpontok ezzel a hullámmal írhatóak le jó közelítéssel. 
(A mélyebbre hatoló anyagok a neten mind megmagyarázzák, miért is nem Fourier transzformációt használunk, de mivel bennünk fel nem merült volna, hogy magunktól azt használjuk, ezért arra nem térünk ki).
A fenti két példa végtelenül leegyszerűsített, egyetlen pixelsort mutat, olyan szerencsés értékekkel amelyek egyetlen függvénnyel leírhatóak. A valós képeken bonyibb a helyzet, egyetlen függvénnyel általában nem írhatóak le teljesen, de több függvényt kombinálva kialakítható a megfelelő alakzat:
Forrás. Itt két függvénnyel (piros görbék) írja le a komplexebb fehér görbét.
A koszinusz függvény a képekre (és hangokra) nagyon jól alkalmazható, a valós (organikus) képek viszonylag kevés koszinusz függvénnyel leírhatóak. Egy nyolc pixeles sor legfeljebb 8 darab függvény kombinálásával. De nekünk 8*8 pixeles tömbünk van, tehát a transzformáció két dimenzió mentén történik (x és y tengely), tehát 64 lehetséges függvényünk van, ami a blokkot leírhatja.
Tehát 64 darab adat helyett  (amit egyenként 8 biten kódoltunk 0-255 lépésben), most lett 64 másik adatunk, amiket már  jóval több biten tárolunk (-1024-től 1023 szintek). Egyelőre nagyobb lett csak az adathalmaz, de majd később ez is megoldódik.

Az ábra engem sokáig megtévesztett, a 64 különféle függvény patterneit egymáson kell elképzelni, egymás hatását erősíteni illetve lerontani fogják, így jön ki a végleges 8*8 pixeles kép. Természetesen nem minden esetben használjuk az összeset. Amennyiben csak a bal felső pontunkhoz (DC) rendelünk értéket, az összes többi 63 mező (AC értékek) a mátrixban nullás, akkor a 8*8 pixelünk gyakorlatilag olyan tónusú lesz, mint a bal felső érték. Sima homogén tömb. Ha csak a bal felső és jobb szomszédja kap értéket, akkor egy vízszintes átmenet fog megjelenni a blokkunkon és így tovább.

Összegezve, a bal felső pont kitüntetett (DC) ez a tömbünknek az átlaga. A többi érték (AC) azt adja meg, hogy az adott függvény milyen mértékben (egyáltalán, kicsit, nagyon) vesz részt a blokk kialakításában. A wiki példája egy 8*8 pixeles A betűt ír le. Az alábbi táblázat pedig azt mutatja, hogy az A betű formáját melyik függvény milyen arányban írja le.

Forrás. A wiki példája egy DCT mátrixra, ami egy A betűt formáz.
Van ott mozgó-gif is,
nem lopom ide azt is, de nézzétek meg, szemléletes.
Ez azért jó, mert egy 8x8-as blokkban általában nincs nagy szórás, valós esetben a blokkokban egymáshoz elég közeli pixelértékek szoktak lenni (az AC értékek nem lesznek túl nagy számok, ez a későbbiekben jól jön).
Ugyanaz a képrészlet 0 illetve 12-es tömörítéssel.
Ilyen brutális kvantálás mellett az alapfüggvények elég jól kivehetőek annak ellenére, hogy
ez már itt RGB-ben van.
Ha minden forrást végigolvastál és néztél, és még mindig gondot okoz a lényeg megsejtése, akkor van ez a jó kis jávás eszköz, amivel vizualizálni lehet a DCT-t. A DCT -1024..+1023 között vehet fel értéket, a kép meg 0..255 között.

Fehér blokk esetén a DC is maximális, az AC-k viszont zérósok, a képen nincs semmilyen eltérés.


Fekete blokk esetén a DC is mnimális, az AC-k viszont zérósok, a képen nincs semmilyen eltérés.

A blokk egyetlen fekete pixelt tartalmaz, 1x0+63*255/64 = 98%.
A baloldalon tehát megjelent a blokk átlaga (2048-nak a 98%-a) = 984 (-1024-től)
Az alacsony frekvenciás értékek -44-től haladnak  a nagyok felé -2-ig (jobb alsó sarok)
(alig 2-3%változás van a teljes blokkon, a képen szinte egybefüggő szürkének látszik, de nem az). 

A DC a blokk tónusának átlaga, látszik, hogy x tengelyen nincs AC,
y tengelyen is leginkább az alacsony frekvencia  (második sötét pötty) dominál a lassú átmenet miatt

Itt az x tengelyen a nagyfrekvenciák dominánsak (főleg a jobboldali érték miatt), y tengelyen meg semmi történik.


Az előbbi pattern inverze. Itt is a jobboldali magas frekvenciás függvény dominál de ellenkező előjellel (jobboldali fehér) 








































A DCT transzformáció oda-vissza, a leírások szerint nem okoz veszteséget, annyira nem látjuk át, hogy ezt cáfoljuk. Igazán kockáknak az internet tele van programkódokkal, mi ennél jobban nem akarunk belemenni. Különben is 17 éve programoztunk utoljára, miért pont most kezdenénk újra.

Nincsenek megjegyzések:

Megjegyzés küldése