Diszkrét koszinusz-transzformáció

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 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.

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.

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	N2	N2	N4	N4
2x(1-D)	2N	2N	2N3	2N3
gyors DCT	11 (N=8)	29 (N=8)	11 N2	29 N2

Irodalom

• (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. november 29.) „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