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. |
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/f/f3/Phalaenopsis_fft_dct.png/200px-Phalaenopsis_fft_dct.png)
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:
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:
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:
x(k,l) a bemeneti minta, am, an 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.
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/1/15/Cikk-cakk_konverzi%C3%B3.png/200px-Cikk-cakk_konverzi%C3%B3.png)
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 | N2 | N2 | N4 | N4 |
2x(1-D) | 2N | 2N | 2N3 | 2N3 |
gyors DCT | 11 (N=8) | 29 (N=8) | 11 N2 | 29 N2 |
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. augusztus 14.) „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