Discrete cosinustransformatie

De discrete cosinustransformatie (DCT) is een transformatietechniek uit de numerieke wiskunde. De methode wordt onder meer toegepast bij datacompressie van audio- en videodata, zoals bij het beeldformaat jpeg. Een gemodificeerde vorm van de methode wordt onder andere gebruikt in het kader van het audioformaat mp3. De discrete cosinustransformatie werd voor het eerst beschreven in 1974 door N. Ahmed et al.

De discrete cosinustransformatie behoort tot de reëelwaardige discrete, lineaire orthogonale transformaties die, net als de discrete fouriertransformatie, een discreet signaal van het tijds- of ruimtedomein omzet naar het frequentiedomein. De discrete cosinustransformatie drukt daartoe een eindige rij data uit als een eindige som van cosinussen met verschillende frequenties. Door een of meer termen met de hoogste frequenties weg te laten kunnen de data gereduceerd (gecomprimeerd) worden, waarbij alleen iets van de scherpte in het beeld verloren gaat.

Principe

Een cosinustransformatie drukt de rij van $N$ data

$x=(x_{0},\ldots ,x_{N-1})$

uit als lineaire combinatie van cosinussen. Daartoe wordt het interval $[0,\pi ]$ opgedeeld in $N-1$ deelintervallen van gelijke lengte $h=\pi /(N-1)$ door de equidistante deelpunten $t_{n}=nh,\ n=0,1,\ldots ,N-1$ en worden de cosinussen $C_{k}(t)=\cos(kt)$ geëvalueerd in de deelpunten, wat resulteert in de coëfficiënten $C_{k,n}=C_{k}(t_{n})$.

De lineaire combinatie is dan van de vorm

$x_{n}=\sum _{k=0}^{N-1}X_{k}a_{k}C_{k,n}$ voor $n=0,\ldots ,N-1$

waarin de $a_{k}$ nog vrij te kiezen evenredigheidsfactoren zijn. In vectorvorm:

$x=\sum _{k=0}^{N-1}X_{k}a_{k}C_{k}$

De rijen coëfficiënten $C_{k}=(C_{k,0},\ldots ,C_{k,N-1})$ vormen een orthogonaal stelsel met betrekking tot het inproduct voor rijen $p=(p_{0},\ldots ,p_{N-1})$:

$\langle p,q\rangle =\sum _{k=0}^{N-1}w_{k}p_{k}q_{k}={\tfrac {1}{2}}p_{0}q_{0}+\sum _{k=1}^{N-2}p_{k}q_{k}+{\tfrac {1}{2}}p_{N-1}q_{N-1}$

dus met weegcoëfficiënten $w=({\tfrac {1}{2}},1,\ldots ,1,{\tfrac {1}{2}})$. Dat houdt in:

$\langle C_{i},C_{j}\rangle =0$ voor $i\neq j$

Verder is:

$\langle C_{0},C_{0}\rangle =\langle C_{N-1},C_{N-1}\rangle =N-1$

$\langle C_{k},C_{k}\rangle ={\tfrac {1}{2}}(N-1)$ voor $0<k<N-1$

Bewijs 

Er geldt namelijk

${\begin{aligned}\langle C_{i},C_{j}\rangle &={\tfrac {1}{2}}(C_{i,0}C_{j,0}+C_{i,N}C_{j,N})+\sum _{n=1}^{N-1}C_{i,n}C_{j,n}\\&={\tfrac {1}{2}}(1+(-1)^{i+j})+{\tfrac {1}{2}}\sum _{n=1}^{N-1}[\cos((i+j)t_{n})+\cos((i-j)t_{n})]\end{aligned}}$

Noem

$S_{k}=\sum _{n=1}^{N-1}\cos(kt_{n})=\sum _{n=1}^{N-1}\cos(knh),\quad k=0,...,2N$

Vermenigvuldig beide leden met $2\sin({\tfrac {1}{2}}kh)$

$2\sin({\tfrac {1}{2}}kh)S_{k}=\sum _{n=1}^{N-1}2\cos(knh)\sin({\tfrac {1}{2}}kh)=\sum _{n=1}^{N-1}[\sin((n+{\tfrac {1}{2}})kh)-\sin((n-{\tfrac {1}{2}})kh)]$

De summanden in de som zijn van hoog naar laag

$\sin((N-1+{\tfrac {1}{2}})kh)-\sin((N-1-{\tfrac {1}{2}})kh)$

$\sin((N-2+{\tfrac {1}{2}})kh)-\sin((N-2-{\tfrac {1}{2}})kh)$

$\ldots$

$\sin((2+{\tfrac {1}{2}})kh)-\sin((2-{\tfrac {1}{2}})kh)$

$\sin((1+{\tfrac {1}{2}})kh)-\sin((1-{\tfrac {1}{2}})kh)$

De som is dus gelijk aan

$\sum _{n=1}^{N-1}[\sin((n+{\tfrac {1}{2}})kh)-\sin((n-{\tfrac {1}{2}})kh)]=\sin((N-{\tfrac {1}{2}})kh)-\sin({\tfrac {1}{2}}kh)$

zodat voor $k\neq 0,k\neq 2N$ (merk op dat $\sin(Nkh)=\sin(k\pi )=0$)

${\begin{aligned}S_{k}&={\frac {\sin((N-{\tfrac {1}{2}})kh)-\sin({\tfrac {1}{2}}kh)}{2\sin({\tfrac {1}{2}}kh)}}={\frac {\sin((N-{\tfrac {1}{2}})kh)}{2\sin({\tfrac {1}{2}}kh)}}-{\tfrac {1}{2}}\\&={\frac {\sin(Nkh)\cos({\tfrac {1}{2}}kh)-\cos(Nkh)\sin({\tfrac {1}{2}}kh)}{2\sin({\tfrac {1}{2}}kh)}}-{\tfrac {1}{2}}\\&={\frac {-\cos(k\pi )\sin({\tfrac {1}{2}}kh)}{2\sin({\tfrac {1}{2}}kh)}}-{\tfrac {1}{2}}=-{\tfrac {1}{2}}\cos(k\pi )-{\tfrac {1}{2}}={\begin{cases}-1&{\text{voor even }}k\\0&{\text{voor oneven }}k\end{cases}}\end{aligned}}$

Verder is

$S_{0}=S_{2N}=\sum _{n=1}^{N-1}\cos(0)=\sum _{n=1}^{N-1}\cos(2\pi )=N-1$

Dus volgt voor $i\neq j$ (omdat $\cos(-x)=\cos(x)$ mogen we $S_{i-j}$ schrijven als $S_{\mid i-j\mid }$)

$\langle C_{i},C_{j}\rangle =1+{\tfrac {1}{2}}(S_{i+j}+S_{\mid i-j\mid })=1+{\tfrac {1}{2}}(-1+-1)=0$ als $i+j\ {\text{even is}}$

$\langle C_{i},C_{j}\rangle ={\tfrac {1}{2}}(S_{i+j}+S_{\mid i-j\mid })={\tfrac {1}{2}}(0+0)=0$ als $i+j\ {\text{oneven is}}$

Ook is

$\langle C_{0},C_{0}\rangle =1+{\tfrac {1}{2}}(S_{0}+S_{0})=1+{\tfrac {1}{2}}(N-1+N-1)=N$

$\langle C_{k},C_{k}\rangle =1+{\tfrac {1}{2}}(S_{2k}+S_{0})=1+{\tfrac {1}{2}}(-1+N-1)={\tfrac {1}{2}}N$ voor $0<k<N$

$\langle C_{N},C_{N}\rangle =1+{\tfrac {1}{2}}(S_{2N}+S_{0})=1+{\tfrac {1}{2}}(N-1+N-1)=N$

Uitwerken van het inproduct $\langle x,C_{k}\rangle$ levert

$\langle x,C_{k}\rangle ={\big \langle }\sum _{m=0}^{N}X_{m}a_{m}C_{m},C_{k}{\big \rangle }=\sum _{m=0}^{N}X_{m}a_{m}\langle C_{m},C_{k}\rangle =X_{k}a_{k}\langle C_{k},C_{k}\rangle$

Voor de coëfficiënten $X_{k}$ volgt daardoor

$X_{k}={\frac {1}{a_{k}}}{\frac {\langle x,C_{k}\rangle }{\langle C_{k},C_{k}\rangle }}={\frac {1}{a_{k}}}{\frac {2}{N}}({\tfrac {1}{2}}x_{0}+\sum _{n=1}^{N-1}x_{n}C_{k,n}+{\tfrac {1}{2}}x_{N}(-1)^{k})$ voor $0<k<N$

$X_{0}={\frac {1}{a_{0}}}{\frac {\langle x,C_{0}\rangle }{\langle C_{0},C_{0}\rangle }}={\frac {1}{a_{0}}}{\frac {1}{N}}({\tfrac {1}{2}}x_{0}+\sum _{n=1}^{N-1}x_{n}+{\tfrac {1}{2}}x_{N})$

en

$X_{N}={\frac {1}{a_{N}}}{\frac {\langle x,C_{N}\rangle }{\langle C_{N},C_{N}\rangle }}={\frac {1}{a_{N}}}{\frac {1}{N}}({\tfrac {1}{2}}x_{0}+\sum _{n=1}^{N-1}x_{n}C_{N,n}+{\tfrac {1}{2}}x_{N}(-1)^{N})$

of in matrixvorm:

$X=Cx$.

Daarbij is $C=(c_{k,n})$ een orthogonale matrix met als elementen de coëfficiënten $c_{k,n}$ die de waarden van een cosinus zijn, afhankelijk van $k,n$ en $N$ eventueel nog met een normeringsfactor. Omdat de matrix $C$ orthogonaal is, kan de transformatie ook omgekeerd worden, en kunnen de oorspronkelijke data $(x)$ uit de getransformeerde data $(X)$ teruggevonden worden.

Er zijn verschillende vormen van de discrete cosinustransformatie, die onderling verschillen door de keuze van de coëfficiënten $c_{k,n}$. Opgemerkt moet worden dat de verschillende normeringsfactoren in de literatuur niet eenduidig vast liggen. Zo voeren bijvoorbeeld sommige auteurs een extra factor${\sqrt {2/N}}$ in om te vermijden dat bij de omgekeerde transformatie nog een extra factor benodigd is. Ook is bij de verschillende keuzes nog een extra factor nodig om de matrix $C$ tot een orthogonale matrix te maken.

DCT-I

Bij deze vorm kiest men $a_{0}=a_{N}=1/N$ en $a_{n}=2/N,\ n=1,\ldots ,N-1$ De coëfficiënten worden dan:

$c_{k,0}={\tfrac {1}{2}}={\tfrac {1}{2}}\cos(0)$

$c_{k,n}=C_{k}(t_{n})=\cos(kn{\tfrac {\pi }{N}})$ voor $n=1,\ldots ,N-1$

$c_{k,N}={\tfrac {1}{2}}(-1)^{k}={\tfrac {1}{2}}\cos(kN{\tfrac {\pi }{N}})={\tfrac {1}{2}}\cos(k\pi )$

De DCT-I is dus gedefinieerd door:

$X_{k}={\tfrac {1}{2}}(x_{0}+(-1)^{k}x_{N})+\sum _{n=1}^{N-1}x_{n}\cos \left(kn{\frac {\pi }{N}}\right)$ voor $k=0,\ldots ,N$.

De DCT-I is op een factor $2/N$ na z'n eigen omgekeerde.

DCT-II

De gebruikelijke vorm van de cosinustransformatie is de DCT-II. De $N$ data $x_{0},\ldots ,x_{N-1}$ worden weer geschreven als lineaire combinatie van cosinussen. Voor het bepalen van de coëfficiënten

$X_{k}=\sum _{n=0}^{N-1}c_{k,n}x_{n}$

wordt het interval $[0,\pi ]$ opgedeeld in $N$ gelijke delen, dus met lengte $h=\pi /N$. De cosinussen worden nu geëvalueerd in de middens $m_{k}$ van de deelintervallen

$m_{n}=\left(k+{\tfrac {1}{2}}\right)h=\left(n+{\tfrac {1}{2}}\right){\frac {\pi }{N}}$

De coëfficiënten worden:

$c_{k,n}=C_{k}(m_{n})=\cos \left(k\left(n+{\tfrac {1}{2}}\right){\frac {\pi }{N}}\right)$

De DCT-II is dus gedefinieerd door:

$X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left(k\left(n+{\tfrac {1}{2}}\right){\frac {\pi }{N}}\right)$ voor $k=0,\ldots ,N-1$

DCT-III

De DCT-III is op een factor $2/N$ na de omgekeerde van de DCT-II. De coëfficiënten zijn:

$c_{k,0}={\tfrac {1}{2}}={\tfrac {1}{2}}\cos \left(0\right)$

$c_{k,n}=\cos \left(\left(k+{\tfrac {1}{2}}\right)n{\frac {\pi }{N}}\right)$ voor $n=1,\ldots ,N-1$

De DCT-III is dus gedefinieerd door:

$X_{k}={\tfrac {1}{2}}x_{0}+\sum _{n=1}^{N-1}x_{n}\cos \left(\left(k+{\tfrac {1}{2}}\right)n{\frac {\pi }{N}}\right)$ voor $k=0,\ldots ,N-1$

DCT-IV

Bij deze vorm van de discrete cosinustransformatie zijn de coëfficiënten:

$c_{k,n}=\cos \left(\left(k+{\tfrac {1}{2}}\right)\left(n+{\tfrac {1}{2}}\right){\frac {\pi }{N}}\right)$

De DCT-IV is dus gedefinieerd door:

$X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left(\left(k+{\tfrac {1}{2}}\right)\left(n+{\tfrac {1}{2}}\right){\frac {\pi }{N}}\right)$ voor $k=0,\ldots ,N-1$

De DCT-IV is op een factor $2/N$ na z'n eigen omgekeerde.

Voorbeeld

Van de $N=16$ data

$x=(8,8,8,8,0,0,0,0,8,8,8,8,0,0,0,0)$

wordt met de DCT-II de getransformeerde berekend.

$X=(64;16{,}9;0;33{,}3;0;-20{,}5;0;-2{,}6;0;2{,}1;0;10{,}9;0;-10{,}1;0;-1{,}7)$

Merk op, dat zoals te verwachten was, de coëfficiënten met even index gelijk zijn aan 0:

$X_{2k}=0$ voor $k=1,2,\ldots ,7$

Terugtransformeren levert de oorspronkelijke data op uitgedrukt in cosinussen:

$x_{n}={\tfrac {1}{8}}\left({\tfrac {1}{2}}X_{0}+\sum _{k=1}^{15}X_{k}\cos \left((n+{\tfrac {1}{2}})k{\frac {\pi }{16}}\right)\right)$

Laat men de hoogste frequentie weg, door $X_{15}=0$ te stellen, dan levert terugtransformeren niet meer de oorspronkelijke data $x$ op, maar (afgerond):

$x^{*}=(8{,}0;7{,}9;8{,}1;7{,}9;0{,}2;-0{,}2;0{,}2;-0{,}2;8{,}2;7{,}8;8{,}2;7{,}8;0{,}1;-0{,}1;0{,}1;0)$

Transformatie met de DCT-I levert:

$X=(60;12{,}9;0;33{,}9;0;-16;0;-4{,}90;-1{,}90;12{,}9;0;-4{,}9;0;-4)$

Meer dimensies

Speciaal in de digitale beeldbewerking wordt gebruikgemaakt van een discrete cosinustransformatie in twee dimensies gebaseerd op DCT-II. Uitbreiding naar meer dimensies gebeurt eenvoudigweg door toepassing van de transformatie in elk van de dimensies. In het geval van tweedimensionale data

$(x_{n,m}),\ n=0,\ldots ,N-1,\ m=0,\ldots ,M-1$

door toepassing van DCT-II op de rijen en op de kolommen.

De coëfficiënten $X_{i,j}$ worden bepaald door

$X_{i,j}=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}x_{n,m}\cos \left(i(n+{\tfrac {1}{2}}){\frac {\pi }{N}}\right)\cos \left(j(m+{\tfrac {1}{2}}){\frac {\pi }{M}}\right)$

Werking DCT

Figuur 1

Figuur 2

3D tabel

Om te begrijpen hoe een DCT werkt, is het belangrijk te weten wat voor data gemanipuleerd worden. Een afbeelding wordt voorgesteld als een array van natuurlijke getallen. Ieder getal stelt de grijswaarde van een pixel van de afbeelding voor. Figuur 1 geeft een grijs vierkant van 8×8 pixels weer. In figuur 2 worden de pixelwaarden in een matrix voorgesteld. Deze grijswaardes gaan van 0 (zwart) tot 255 (wit). De weergegeven grijstint heeft 140 als waarde.

Een DCT transformeert de grijswaardes, gegeven in de array, naar het frequentiedomein. Dit betekent dat de data in de matrix worden voorgesteld als de som van een reeks golven met verschillende amplitudes en frequenties.

Om de afbeelding als een golfvorm te kunnen voorstellen, kan de 3D-tabel beschouwd worden. In deze figuur is iedere waarde van elke pixel voorgesteld als de hoogte op de verticale as. De verandering in deze waardes (of hoogtes) kan worden gezien als een 2D-golfvorm.

Deze 2D-golfvorm wordt door de DCT opgedeeld in frequentiecomponenten, net zoals een 1D-golfvorm die wordt omgezet naar het frequentiedomein. De som van de frequentiecomponenten gemaakt door DCT is gelijk aan de originele golf. Het resultaat van de DCT, uitgevoerd op figuur 1a, is te zien in onderstaande matrix. De waarde van de laagste frequentie staat in de linkse bovenhoek. De frequentie stijgt als we meer naar rechts of naar onder gaan.

$A={\begin{bmatrix}800&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\end{bmatrix}}$

Het enige element heeft een waarde van 800. Dit komt doordat de afbeelding bestaat uit slechts 1 grijswaarde.

Toepassing

In het volgende voorbeeld wordt de DCT $A'$ berekend van de 2×2-matrix.

$A={\begin{bmatrix}120&115\\112&100\end{bmatrix}}$

Voor de elementen van $A'$ geldt de formule.

$A'_{u,v}=\sum _{r=0}^{M-1}\sum _{s=0}^{N-1}{\frac {2\cdot C(u)\cdot C(v)}{\sqrt {M\cdot N}}}\cos \left({\frac {(2r+1)u\pi }{2M}}\right)\cos \left({\frac {(2s+1)v\pi }{2N}}\right)A_{r,s}$,

waarin $M=2$ het aantal rijen en $N=2$ het aantal kolommen voorstellen en

$C(\delta )={\tfrac {1}{2}}{\sqrt {2}}$ enkel als $\delta =0$

$C(\delta )=1$ in de andere gevallen

Voor $u=v=0$ volgt, met $C(0)={\tfrac {1}{2}}{\sqrt {2}}$:

$A'_{0,0}=\sum _{r=0}^{2-1}\sum _{s=0}^{2-1}{\frac {2\cdot {\frac {\sqrt {2}}{2}}\cdot {\frac {\sqrt {2}}{2}}}{\sqrt {2\cdot 2}}}\cos \left({\frac {(2r+1)0\pi }{2\cdot 2}}\right)\cos \left({\frac {(2s+1)0\pi }{2\cdot 2}}\right)A_{r,s}$

$=\sum _{r=0}^{1}\sum _{s=0}^{1}{\frac {1}{\sqrt {4}}}\cos(0)\cos(0)A_{r,s}=\sum _{r=0}^{1}\sum _{s=0}^{1}{\tfrac {1}{2}}A_{r,s}$

Dus

$A'_{0,0}={\tfrac {1}{2}}\cdot 120+{\tfrac {1}{2}}\cdot 115+{\tfrac {1}{2}}\cdot 112+{\tfrac {1}{2}}\cdot 100=223{,}5$

Voor $u=0$ en $v=1$ volgt op soortgelijke wijze:

$A'_{0,1}=\sum _{r=0}^{2-1}\sum _{s=0}^{2-1}{\frac {2\cdot 1\cdot {\frac {\sqrt {2}}{2}}}{\sqrt {2\cdot 2}}}\cos \left({\frac {(2r+1)0\pi }{2\cdot 2}}\right)\cos \left({\frac {(2s+1)1\pi }{2\cdot 2}}\right)A_{r,s}$

$=\sum _{r=0}^{1}\sum _{s=0}^{1}{\frac {\sqrt {2}}{2}}\cos \left({\frac {(2s+1)1\pi }{2\cdot 2}}\right)A_{r,s}$

Dus

$A'_{0,1}={\frac {\sqrt {2}}{2}}\left[\cos \left({\frac {\pi }{4}}\right)\cdot 120+\cos \left({\frac {3\pi }{4}}\right)\cdot 115+\cos \left({\frac {\pi }{4}}\right)\cdot 112+\cos \left({\frac {3\pi }{4}}\right)\cdot 100\right]=8{,}5$

De twee andere elementen worden op analoge manier berekend; het uiteindelijke resultaat is:

$A'={\begin{bmatrix}223{,}5&8{,}5\\11{,}5&-3{,}5\end{bmatrix}}$

Ook hier staat de grootste waarde in de linkerbovenhoek.

Zie ook

• JPEG

Externe link

• Gilbert Strang, The Discrete Cosine Transform