Discrete cosinustransformatie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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.

Principe[bewerken]

Een cosinustransformatie zet de rij van N data

x_0, \ldots, x_{N-1}

om in de rij

X_0, \ldots, X_{N-1}

via een lineaire transformatie:

X_k = \sum_{n=0}^{N-1}c_{k,n}x_n voor k=0,\ldots, N-1

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[bewerken]

Voor deze vorm van de discrete cosinustransformatie worden de coëfficiënten als volgt gekozen:

c_{k,0}=\tfrac 12=\tfrac 12\cos \left(0 \right)
c_{k,n}=\cos \left(kn\frac{\pi}{N-1} \right) voor n=1,\ldots, N-2
c_{k,N-1}=\tfrac 12(-1)^k=\tfrac 12\cos \left(k(N-1)\frac{\pi}{N-1} \right)=\tfrac 12\cos \left(k\pi \right)

De DCT-I is dus gedefinieerd door:

X_k = \tfrac 12 (x_0 + (-1)^k x_{N-1}) + \sum_{n=1}^{N-2} x_n \cos \left(kn\frac{\pi}{N-1} \right) voor k=0,\ldots, N-1.

De DCT-I is op een factor \tfrac 2{N-1} na z'n eigen omgekeerde.

DCT-II[bewerken]

De gebruikelijke vorm van de cosinustransformatie is de DCT-II. Hiervoor zijn de coëfficiënten:

c_{k,n}=\cos \left(k\left(n+\tfrac 12\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 12\right)\frac{\pi}{N} \right) voor k=0,\ldots, N-1.

DCT-III[bewerken]

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 12=\tfrac 12\cos \left(0 \right)
c_{k,n}=\cos \left(\left(k+\tfrac 12\right) n\frac{\pi}{N} \right) voor n=1,\ldots, N-1.

De DCT-III is dus gedefinieerd door:

X_k = \tfrac 12 x_0 + \sum_{n=1}^{N-1} x_n \cos \left(\left(k+\tfrac 12\right) n\frac{\pi}{N} \right) voor k=0,\ldots, N-1.

DCT-IV[bewerken]

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

c_{k,n}=\cos \left(\left(k+\tfrac 12 \right)\left(n+\tfrac 12\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 12 \right) \left(n+\tfrac 12\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.

Werking DCT[bewerken]

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 8x8 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 de 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[bewerken]

Nu we een algemeen idee hebben hoe de waardes van een DCT worden berekend passen we dit toe op een voorbeeld. We berekenen de DCT van volgende 2x2 matrix.

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

We maken gebruik van onderstaande formule. F(u,v) = \sum_{r=0} ^{M-1} \sum_{s=0} ^{N-1} \frac{2 \cdot C(u)\cdot C(v)}{\sqrt[2]{M \cdot N}} cos \left( \frac{(2r + 1)u\pi}{2M}\right) cos \left( \frac{(2s + 1)v\pi}{2N}\right)f(r,s)

C(δ) = \frac{ \sqrt[2]{2}} {2}  enkel als δ = 0

C(δ) = 1 andere gevallen In de formule stellen u en v de posities voor van het element dat we aan het berekenen zijn in de matrix. M en N stellen dan weer het aantal rijen en kolommen voor, r en s zijn de waardes van de posities die we doorlopen bij iedere berekening. We krijgen dus een som van alle waardes in de array.

In dit voorbeeld is M = 2 en N = 2, we gaan element per element te werk, dus we krijgen 4 berekeningen. Als eerste is u = 0 en v = 0. De waarde van C(u) en C(v) is dan ook  \frac{ \sqrt[2]{2}} {2}  . F(0,0) = \sum_{r=0} ^{2-1} \sum_{s=0} ^{2-1} \frac{2 \cdot \frac{ \sqrt[2]{2}} {2}\cdot \frac{ \sqrt[2]{2}} {2}}{\sqrt[2]{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)f(r,s)

F(0,0) = \sum_{r=0} ^{1} \sum_{s=0} ^{1} \frac{1 }{\sqrt[2]{4}} cos(0) cos(0) f(r,s)

F(0,0) = \sum_{r=0} ^{1} \sum_{s=0} ^{1} \frac{1 }{2} f(r,s)

Nu werken we verder de sommatie tekens uit:

F(0,0) = \frac{1 }{2} \cdot 120 +\frac{1 }{2} \cdot 115 +\frac{1 }{2} \cdot 112 + \frac{1 }{2} \cdot 100 = 223,5

We hebben nu de eerste waarde van de DCT matrix. Voor de overige 3 waardes veranderen we v en u. Het volgende element wordt berekend door u = 0 en v = 1.

F(0,1) = \sum_{r=0} ^{2-1} \sum_{s=0} ^{2-1} \frac{2 \cdot \cdot \frac{ \sqrt[2]{2}} {2}}{\sqrt[2]{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)f(r,s)

F(0,1) = \sum_{r=0} ^{1} \sum_{s=0} ^{1} \frac{\sqrt[2]{2}}{2} cos \left( \frac{(2s + 1)1\pi}{2\cdot 2}\right)f(r,s)

F(0,1) = \frac{\sqrt[2]{2}}{2} \left[ cos \left( \frac{(2 \cdot 0 + 1)\pi}{4}\right)\cdot 120 + cos \left( \frac{(2 \cdot 1 + 1)\pi}{4}\right)\cdot 115 + cos \left( \frac{(2 \cdot 0 + 1)\pi}{4}\right)\cdot 112 + cos \left( \frac{(2 \cdot 1 + 1)\pi}{4}\right)\cdot 100 \right]

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

De 2 andere elementen worden op een analoge manier berekent de volledige uitkomst ziet er als volgt uit:

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

Ook hier zien we dat de hoogste waarde terug te vinden is in de linkerbovenhoek.

Zie ook[bewerken]