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

• Narasimha, M.; Peterson, A. (1978. június). "On the Computation of the Discrete Cosine Transform". IEEE Transactions on Communications. 26 (6): 934–936. doi:10.1109/TCOM.1978.1094144.
• Makhoul, J. (1980. február). "A fast cosine transform in one and two dimensions". IEEE Transactions on Acoustics, Speech, and Signal Processing. 28 (1): 27–34. doi:10.1109/TASSP.1980.1163351.
• Sorensen, H.; Jones, D.; Heideman, M.; Burrus, C. (1987. június). "Real-valued fast Fourier transform algorithms". IEEE Transactions on Acoustics, Speech, and Signal Processing. 35 (6): 849–863. CiteSeerX 10.1.1.205.4523. doi:10.1109/TASSP.1987.1165220.
• Arai, Y.; Agui, T.; Nakajima, M. (1988. november). "A fast DCT-SQ scheme for images". IEICE Transactions. 71 (11): 1095–1097.
• Plonka, G.; Tasche, M. (2005. január). "Fast and numerically stable algorithms for discrete cosine transforms". Linear Algebra and Its Applications. 394 (1): 309–345. doi:10.1016/j.laa.2004.07.015.
• Duhamel, P.; Vetterli, M. (1990. április). "Fast fourier transforms: A tutorial review and a state of the art". Signal Processing (Submitted manuscript). 19 (4): 259–299. doi:10.1016/0165-1684(90)90158-U.
• Ahmed, N. (1991. január). "How I came up with the discrete cosine transform". Digital Signal Processing. 1 (1): 4–9. doi:10.1016/1051-2004(91)90086-Z.
• Feig, E.; Winograd, S. (1992. szeptember). "Fast algorithms for the discrete cosine transform". IEEE Transactions on Signal Processing. 40 (9): 2174–2193. Bibcode:1992ITSP...40.2174F. doi:10.1109/78.157218.
• Malvar, Henrique (1992), Signal Processing with Lapped Transforms, Boston: Artech House, ISBN 978-0-89006-467-2
• Martucci, S. A. (1994. május). "Symmetric convolution and the discrete sine and cosine transforms". IEEE Transactions on Signal Processing. 42 (5): 1038–1051. Bibcode:1994ITSP...42.1038M. 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
• Frigo, M.; Johnson, S. G. (2005. február). "The Design and Implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301. S2CID 6644892.
• Boussakta, Said.; Alshibami, Hamoud O. (2004. április). "Fast Algorithm for the 3-D DCT-II" (PDF). IEEE Transactions on Signal Processing. 52 (4): 992–1000. Bibcode:2004ITSP...52..992B. doi:10.1109/TSP.2004.823472. S2CID 3385296.
• Cheng, L. Z.; Zeng, Y. H. (2003). "New fast algorithm for multidimensional type-IV DCT". IEEE Transactions on Signal Processing. 51 (1): 213–220. doi:10.1109/TSP.2002.806558.
• Wen-Hsiung Chen; Smith, C.; Fralick, S. (1977. szeptember). "A Fast Computational Algorithm for the Discrete Cosine Transform". IEEE Transactions on Communications. 25 (9): 1004–1009. doi:10.1109/TCOM.1977.1093941.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (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