Diszkrét koszinusz transzformáció

A Wikipédiából, a szabad lexikonból.

2D DCT összehasonlítva a DFT-vel (a világosabb árnyalatok jelzik a nem zérus együtthatókat)

A diszkrét koszinusz transzformáció (angol nyelvű rövidítése: DCT) egy Fourier-transzformáció, hasonló a diszkrét Fourier-transzformációhoz, de nem komplex, hanem valós számokon dolgozik.

A tömörítés során a lényegtelen információk elhagyására törekszünk. A CS&Q eljárást alkalmazva a mintavételi frekvencia és/vagy a kvantálási lépcsők számának csökkentésével jóval kisebb adathalmazt kapunk, miközben a képminőség csak az elfogadható mértékben romlott. Nem használtuk ki azonban az emberi látás néhány fontos tulajdonságát. Ha az adathalmazunkra alkalmazzuk a DCT-t, a kapott új adathalmaz nem lesz nagyobb, mint az eredeti, de ez most a kép spektrális tulajdonságaira lesz jellemző. Az emberi szem azonban a nagyfrekvenciás összetevőkre jóval kevésbé érzékeny, mint a DC-hez közeliekre. Elhagyva a nagyfrekvenciás összetevők kb. 50%-át, az inverz transzformáció után az eredeti kódolt információnak legfeljebb 5%-a veszik el.

A JPEG kódolás során a képet 8x8 pixelből álló blokkokra osztjuk, és ezt a 64 képpontot együtt transzformáljuk. Ezt eredetileg az indokolta, hogy az eljárás kifejlesztésének idején az integrált áramkörös technológia ennyit tett lehetővé. A 8x8-as technika jól bevált, ezért azóta sem módosították. Az MPEG technika a kódolás és a mozgásbecslés során szintén 8x8-as blokkokat használ, de ott a blokkméret növelése igen jelentős számítástechnikai többletigénnyel járna.

Ha egy N mintából álló sorozatot szimmetrikussá teszünk úgy, hogy a mintákat csökkenő index szerint megismételjük, akkor egy páros függvényt kapunk. A függvény Fourier transzformáltjának (spektrumának) N db harmonikus összetevője lesz (0 - N-1). Valamennyi összetevő koszinuszos és valós. Egyszerűsítve ez a DCT. Az N mintából álló sorozat diszkrét koszinusz-transzformáltja:

$y(k)=\sqrt{\frac{2}{N}}\cdot\alpha_k\cdot\sum_{n=0}^{N-1}x(n)\cdot cos \left( \frac{2n+1}{2N} \cdot k\cdot\pi \right)$

$\alpha_k = 1\ \ \ \ ha\ \ \ \ \ k\neq0\ \ \ \ \ \alpha_k=\frac{1}{\sqrt{2}}\ \ \ \ ha\ \ \ \ k=0\ \ \ \ \ \ n,k=0..N-1$

Az N db mintát együtt transzformáltuk. Ha az N = 8, akkor 8 féle alapfüggvényt (harmonikus összetevőt) kapunk, amiből a k = 0-hoz tartozó összetevő a DC, és értéke:

$y(0) = \frac{1}{\sqrt{N}}$

Ne feledkezzünk meg azonban arról, hogy a képet három (Y,U,V) kétváltozós (x,y) függvény írja le, ezért kétdimenziós DCT-re van szükségünk. Ezt elvégezhetjük úgy is, hogy két egydimenziós DCT-t egymás után kapcsolunk. A kétdimenziós DCT formula:

$y(m,n) = \frac{2}{N} \cdot \alpha_m \cdot \alpha_n \cdot \sum_{k=0}^{N-1} \sum_{l=0}^{N-1} x(k,l) \cdot cos \left( \frac{2k+1}{2N} \cdot m \cdot \pi \right) \cdot cos \left( \frac{2l+1}{2N} \cdot n \cdot \pi \right)$

x(k,l) a bemeneti minta, a_m, a_n ugyanúgy alakul, mint az egydimenziós DCT-nél. 8x8 képpontból álló blokkok együttes transzformálásakor 64 féle alapfüggvényt kapunk, vagyis megkaptuk a DC és a 63 féle koszinuszos összetevő együtthatóit. (A transzformáció szempontjából teljesen mindegy, hogy egy [[Pixel|képpontot] eredetileg hány biten kódoltunk.) A 64 minta helyett most van 64 másik számunk. Látszólag feleslegesen dolgoztunk. Rendezzük 8x8-as mátrixba az együtthatókat úgy, hogy a mátrix (0,0)-ás eleméhez tartozzon a DC, a (7,7) pozíciójú eleméhez pedig a legnagyobb frekvenciájú összetevő. Az együtthatókat kvantáljuk. A még elfogadható minőségromlás mértéke határozza meg, hogy hány kvantálási lépcsőt alkalmazunk. A kvantálás optimalizálható, ha a kvantálási mátrixot az adott képhez illesztjük (adaptáljuk), de akkor azt is át kell vinni.

A szem érzékenysége a frekvencia növelésével rohamosan csökken, a (7,7)-es elem esetén már csak kb. 256-od része a DC összetevőnek. Találhatunk tehát egy olyan súlyozó mátrixot, amellyel megszorozva az együtthatómátrixot, a nagyfrekvenciás együtthatók nagy része nulla, vagy nullához közeli értékű lesz. Tekintsünk nullának minden olyan értéket, amely egy adott minimum alá esik. Ha végigjárjuk a mátrixot a DC-től kiindulva cikk-cakk alakban úgy, hogy fokozatosan távolodjunk a DC összetevőtől, igen nagy a valószínűsége, hogy nullák sorozatával fogunk találkozni. Ez szinte megköveteli a futamhossz-kódolás alkalmazását.

cikk-cakk konverzió

Az együtthatókat soros számfolyammá kell alakítani, de a nagyfrekvenciásak nem lényegesek. Ha egyszerűen elhagyjuk őket, az adaptációs képesség nulla. Súlyozás után a minimum alattiakat eldobhatjuk, de akkor meg kell adni a következő értékes együttható címét. A legjobb megoldás a cikk-cakk konverzió és az azt követő futamhossz-kódolás.

Az alkalmazott futamhossz-kódolás némiképp eltér a korábban megismerttől. Az értékes együttható kódja után mindig a követő nullák száma (futási hossza) áll:

eredeti számsorozat: 2,1,4,3,0,0,0,1,0,0,0,0,0,6,8,1,0,0,0, ...

RLE után: (2,0),(1,0),(4,0),(3,3),(1,5),(6,0),(8,0,),(1,3), ...

A számpárokra még alkalmazhatunk változó szóhosszúságú (Huffman) kódolást is, akár bemenő blokkonként változó kódtáblával.

A JPEG kódolás során kétféle eljárást használhatunk. A nem keresztbeszövött kódolás során az egyes komponenseket (Y,U,V) külön-külön kódoljuk, a keresztbeszövött esetén pedig mindegyikből egyszerre annyit, amennyi a felbontásukból adódik.

[szerkesztés] A DCT műveletigénye

Az alábbi táblázatban összefoglaltuk, hogy NxN képpontból álló blokkok esetén a DCT végrehajtásához hány művelet szükséges:

	1 blokk 1 együtthatója		Teljes blokk
	szorzás	összeadás	szorzás	összeadás
definíció szerint	N²	N²	N⁴	N⁴
2x(1-D)	2N	2N	2N³	2N³
gyors DCT	11 (N=8)	29 (N=8)	11 N²	29 N²

A lap eredeti címe "http://hu.wikipedia.org../../../d/i/s/Diszkr%C3%A9t_koszinusz_transzform%C3%A1ci%C3%B3.html"

Kategóriák: Algoritmusok | Fourier-analízis

Diszkrét koszinusz transzformáció

A Wikipédiából, a szabad lexikonból.

[szerkesztés] A DCT műveletigénye

Views

Navigáció

Keresés

Más nyelveken