Diszkrét koszinusz-transzformáció

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

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:

${\displaystyle 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)}$

${\displaystyle \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:

${\displaystyle 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:

${\displaystyle 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

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:

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. április 23.) „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