Diszkrét koszinusz-transzformáció

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 8×8 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\neq 0\ \ \ \ \ \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 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.

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.

A DCT műveletigénye szerkesztés

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²

Irodalom szerkesztés

(1978. június 1.) „On the Computation of the Discrete Cosine Transform”. IEEE Transactions on Communications 26 (6), 934–936. o. DOI:10.1109/TCOM.1978.1094144.
(1980. február 1.) „A fast cosine transform in one and two dimensions”. IEEE Transactions on Acoustics, Speech, and Signal Processing 28 (1), 27–34. o. DOI:10.1109/TASSP.1980.1163351.
(1987. június 1.) „Real-valued fast Fourier transform algorithms”. IEEE Transactions on Acoustics, Speech, and Signal Processing 35 (6), 849–863. o. DOI:10.1109/TASSP.1987.1165220.
(1988. november 1.) „A fast DCT-SQ scheme for images”. IEICE Transactions 71 (11), 1095–1097. o.
(2005. január 1.) „Fast and numerically stable algorithms for discrete cosine transforms”. Linear Algebra and Its Applications 394 (1), 309–345. o. DOI:10.1016/j.laa.2004.07.015.
(1990. április 1.) „Fast fourier transforms: A tutorial review and a state of the art”. Signal Processing 19 (4), 259–299. o. DOI:10.1016/0165-1684(90)90158-U.
(1991. január 1.) „How I came up with the discrete cosine transform”. Digital Signal Processing 1 (1), 4–9. o. DOI:10.1016/1051-2004(91)90086-Z.
(1992. szeptember 1.) „Fast algorithms for the discrete cosine transform”. IEEE Transactions on Signal Processing 40 (9), 2174–2193. o. DOI:10.1109/78.157218.
Malvar, Henrique (1992), Signal Processing with Lapped Transforms, Boston: Artech House, ISBN 978-0-89006-467-2
(1994. május 1.) „Symmetric convolution and the discrete sine and cosine transforms”. IEEE Transactions on Signal Processing 42 (5), 1038–1051. o. DOI:10.1109/78.295213.
Oppenheim, Alan; Schafer, Ronald & Buck, John (1999), Discrete-Time Signal Processing (2nd ed.), Upper Saddle River, N.J: Prentice Hall, ISBN 978-0-13-754920-7, <https://archive.org/details/discretetimesign00alan>
(2005. február 1.) „The Design and Implementation of FFTW3”. Proceedings of the IEEE 93 (2), 216–231. o. DOI:10.1109/JPROC.2004.840301.
(2004. április 1.) „Fast Algorithm for the 3-D DCT-II”. IEEE Transactions on Signal Processing 52 (4), 992–1000. o. DOI:10.1109/TSP.2004.823472.
(2003. április 22.) „New fast algorithm for multidimensional type-IV DCT”. IEEE Transactions on Signal Processing 51 (1), 213–220. o. DOI:10.1109/TSP.2002.806558.
(1977. szeptember 1.) „A Fast Computational Algorithm for the Discrete Cosine Transform”. IEEE Transactions on Communications 25 (9), 1004–1009. o. DOI:10.1109/TCOM.1977.1093941.
Press, WH; Teukolsky, SA & Vetterling, WT et al. (2007), "Section 12.4.2. Cosine Transform", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8

Matematikaportál
Informatikai portál