3.6.2 DCT. Discrete Cosine Transformation

The Discrete Cosine Transformation is a variant of the Fourier-Transform (Fourier-Series). The basic idea behind these transformations is that any (periodic) function can be decomposed in sine and cosine functions with frequencies being multiples of the given periodicity. Consider the symmetric $N\times N$-matrix

$$A_2:= \begin{pmatrix} 1 & -1 & 0 & \hdots & \hdots& 0 \\ -1 & 2 ... ... & & \ddots & -1 & 2 & -1 \\ 0 & \hdots &\hdots & 0 & -1 & 1 \\ \end{pmatrix}$$

Its Eigenvectors are $v_k:j\mapsto \cos((j+\frac12)\frac{k\pi}N)$ for $0\leq k<N$ with Eigenvalues $\lambda _k:=2\Bigl(1-\cos\bigl(\frac{k\pi}N\bigr)\Bigr)$ for $1<k<N-1$, since for $\th :=\frac{k\pi}N$ we have

$$\cos\Bigl(\frac12\th\Bigr)-\cos\Bigl(\frac32\th\Bigr) = 2\Bigl(1-\cos(\th )\Bigr)\cos\Bigl(\frac12\th\Bigr)$$

$$-\cos\Bigl((j-\frac12)\th\Bigr)+2\cos\Bigl((j+\frac12)\th\Bigr)-\cos\Bigl((j+\frac{3}2)\th\Bigr) =2(1-\cos\th )\cos\Bigl((j+\frac12)\th\Bigr),$$

$$\cos((N-\frac12)\th )-\cos\Bigl((N-\frac32)\th\Bigr) = 2\Bigl(1-\cos(\th )\Bigr)\cos\Bigl((N-\frac12)\th\Bigr)$$

using

$$\cos(a)+\cos(b)=2\cos\Bigl(\frac{a+b}2\Bigr)\cos\Bigl(\frac{a-b}2\Bigr).$$

Since $A_2$ is symmetric, and the sequence of Eigenvalues is strictly monotone increasing, we conclude that the Eigenvectors $v_k$ are orthogonal, thus any vector $a\in\protect\mathbb{R}^N$ can be reconstructed from the projections $\langle a,v_k\rangle$ via

$$a=\sum_{k=0}^{N-1}\frac{\langle a,v_k\rangle}{\Vert v_k\Vert^2} v_k$$

The norms are $\Vert v_0\Vert^2=N$ and $\Vert v_k\Vert^2=\frac{N}2$ for $k\ne 0$, since

$$\Vert v_k\Vert^2 = \sum_{j<N} \cos\Bigl((j+\frac12)\th\Bigr)^2 = \frac12 \sum_{j<N} \biggl(1+\cos\Bigl((2j+1)\th\Bigr)\biggr)$$

$$= \frac{N}{2} + \frac12\Re\biggl(\sum_{j=0}^{N-1} e^{i\th (2j+1)}... ...c12\Re\biggl(\sum_{j=0}^{2N-1} e^{i\th j} - \sum_{j=0}^{N-1} e^{i\th 2j}\biggr)$$

$$= \frac{N}{2} + \frac12\Re\biggl(\frac{e^{i\th 2N}-1}{e^{i\th }-1} - \frac{e^{i\th 2N}-1}{e^{i\th 2}-1}\biggr) = \frac{N}{2} + 0,$$

using $2\cos(a)^2=1+\cos(2a)$ and $e^{ia}=\cos(a)+i\sin(a)$. So

$$\mathcal F(a)_k :=\frac{\langle a,v_k\rangle}{\Vert v_k\Vert} =\left\{\begin{arra... ...\cos\Bigl((j+\frac12)\frac{k\pi}N\Bigr) &\text{f\uml ur }k>0 \end{array}\right.$$

defines an ISOMETRY $\protect\mathbb{R}^N\to\protect\mathbb{R}^N$, i.e. is length-preserving with respect to the euclidean norm, since

$$\Vert a\Vert^2 =\left(\sum_{k<N} \frac{\langle a,v_k\rangle}{\Vert v_k\Vert^2}v_k\right)^2$$

$$=\sum_{k<N} \left(\frac{\langle a,v_k\rangle}{\Vert v_k\Vert^2}v_k\right)^2$$

$$=\sum_k \left(\frac{\langle a,v_k\rangle}{\Vert v_k\Vert}\right)^2$$

$$=\sum_k (\mathcal F(a)_k)^2.$$

The 2-dimensional DCT is now defined by applying the 1-dimensional DCT to rows and columns, i.e.

$$\mathcal F(a)_{r,s} :=C_r\,C_s\,\sum_i\sum_j a_{i,j}\, \cos\left(\frac{r(2i+1)}{2N}\pi\right)\, \cos\left(\frac{s(2j+1)}{2N}\pi\right)$$

Thus with respect to the ${\infty}$-norm we get for the 2-dimensional DCT:

$$\vert\mathcal F(a)_{r,s}\vert \leq \Vert a\Vert _2 \leq \sqrt{\sum_{i,j<N} \Vert a\Vert _{\infty}^2}=\sqrt{N^2}\Vert a\Vert _{\infty}< N*128=1024.$$

Note that here we used a shift for the original data $0\leq a_{i,j}<256$ to $-128\leq a_{i,j}-128<128$.

See also www.ztt.fh-worms.de/.../node34.html