DCT离散余弦变换

DCT

$$F(u)=c(u)\sum_{x=0}^{N-1}f(x)cos[\frac{(x+0.5)\pi}Nu]$$

1. 函数的偶对称性，使DCT只有实数域变换结果, 不再涉及复数运算，运算简单，费时少
2. 与离散傅里叶变换的关系：DCT等价于对一个信号的2N点离散傅立叶变换，通过矩阵延拓将输入图像偶对称
3. DCT系数是实数，而DFT系数是复数，因此，DCT的硬件实现比DFT更容易
4. FFT结构还可以使DCT运算速度更快，因此已成为许多应用的首选

先对DFT展开

$$X[k]=\sum_{n=0}^{N-1}x[n](\cos\frac{2\pi\text{kn}} N ) - j \sum _ { n = 0 }^{N-1}x[n]sin(\frac{2\pi kn}N)$$

单独分析实部和虚部的系数，有

$$Re[k]=\sum_{n=0}^{N-1}x[n]cos(kt)$$

$$Im[k]=\sum_{n=0}^{N-1}x[n]sin(kt)$$

我们可以知道，实部的系数为偶函数，虚部的系数为奇函数。

接下来考虑原式信号$x[n]$的奇偶关系，如果$x[n]$为一个实偶函数，那么我们在求DFT时，就可以只求实部的运算，称为DCT。

首先对这个信号进行对称扩充(-1/2对称)

$$\begin{aligned}&x^{^{\prime}}[m]=x[m](0\leq m\leq N-1)\\{}\\&x^{^{\prime}}[m]=x[-m-1](-N\leq m\leq-1)\end{aligned}$$

此时关于这段信号的DFT变为

$$X[k]=\sum_{m=-N}^{N-1}x^{'}[m]e^{\frac{-j2\pi mk}{2N}}$$

我们为了让信号关于$x=0$对称，把它向右平移$\frac{1}{2}$

$$X[k]=\sum_{m=-N+\frac12}^{N-\frac12}x^{^{\prime}}[m-\frac12]e^\frac{-j2\pi mk}{2N}$$

对其进行展开后，我们只需要保留实数部分，因为此时虚数部分为0

$$X[k]=\sum_{m=-N+\frac12}^{N-\frac12}x^{^{\prime}}[m-\frac12]e^{\frac{-j2\pi mk}{2N}}=\sum_{m=-N+\frac12}^{N-\frac12}x^{^{\prime}}[m-\frac12]cos(\frac{2\pi mk}{2N})$$

由于该序列是个偶函数，那么根据偶函数的性质，可以改写为

$$\sum_{m=-N+\frac12}^{N-\frac12}x^{^{\prime}}[m-\frac12]cos(\frac{2\pi mk}{2N})=2*\sum_{m=\frac12}^{N-\frac12}x^{^{\prime}}[m-\frac12]cos(\frac{2\pi mk}{2N})$$

设$n = m - \frac{1}{2}$，带入可得

$$2*\sum_{n=0}^{N-1}x^{^{\prime}}[n]cos(\frac{2\pi(n+\frac12)k}{2N})=2*\sum_{n=0}^{N-1}x^{^{\prime}}[n]cos(\frac{(n+\frac12)\pi k}N)$$

此时，我们可以加入一个实数系数，乘到原式中

$$c(u)\sqrt{\frac2N}*\sum_{n=0}^{N-1}x^{^{\prime}}[n]{cos(\frac{(n+\frac12)\pi k}N)}$$

他的基函数即为

$$q_{u+1}=\left\{\sqrt{\frac{2}{N}}c(u)\cos\left[\frac{\pi}{2N}\left(2x+1\right)u\right]\right\}$$

$$c(u)=\left\{\begin{array}{cc}\frac{1}{\sqrt{2}}&\quad u=0\\1&\quad u=1,2,...,N-1\end{array}\right.$$

将基函数写成矩阵的形式，此矩阵每一行代表着频率的变化，每一列代表不同x（n）的取值

$$\sqrt{\frac{2}{N}}.\begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}...&\frac{1}{\sqrt{2}}\\\cos\left(\frac{1\pi}{2N}\right)&\cos\left(\frac{3\pi}{2N}\right)...&\cos\left(\frac{(2N-1)\pi}{2N}\right)\\\vdots&\vdots&\vdots\\\cos\left(\frac{(N-1)\pi}{2N}\right)&\cos\left(\frac{3(N-1)\pi}{2N}\right)...&\cos\left(\frac{(2N-1)(N-1)\pi}{2N}\right)\end{bmatrix}$$

那么当我们要求一个一维离散余弦变换的时候，只需要计算出这个变换矩阵，然后运算矩阵乘法即可

二维情况

想象在平面直角坐标下，我们对一个正方形进行操作，沿x，y轴对阵，然后在进行平移，直到中心在原点。
二维DCT：

$$F_{s}(u,\nu)=\frac1{2N}\sum_{x=-N}^{N-1}\sum_{y=-N}^{N-1}f_{s}(x,y)\exp\left(-\frac{j2\pi[u(x+\frac12)+\nu(y+\frac12)]}{2N}\right)$$

由于也是偶实对称的，所以

$$F_{s}(u,v)=\frac{1}{2N}\sum_{x=-N}^{N-1}\sum_{y=-N}^{N-1}f_{s}(x,y)\cdot\cos\biggl[\frac{\pi(2x+1)u}{2N}\biggr]\cdotp\cos\biggl[\frac{\pi(2y+1)\nu}{2N}\biggr]$$

四个象限相同，所以有

$$F_{s}(u,v)=\frac{2}{N}\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}f(x,y)\cdot\cos\biggl[\frac{\pi(2x+1)u}{2N}\biggr]\cdot\cos\biggl[\frac{\pi(2y+1)\nu}{2N}\biggr]$$

然后进行与一维类似的定义

$$F(u,v)=\frac2NK(u)K(v)\overset{N-1N-1}{\operatorname*{\sum}}\sum_{y=0}^{N-1}f(x,y)\cdot\cos\left[\frac{\pi(2x+1)u}{2N}\right]\cdot\cos\left[\frac{\pi(2y+1)\nu}{2N}\right]$$

$$\begin{aligned}K\left(u\right)&=\begin{cases}\frac{1}{\sqrt{2}}&\quad u=0\\1&\quad u=1,2,\cdots,N-1&\end{cases}\\\\K\left(\nu\right)&=\begin{cases}\frac{1}{\sqrt{2}}&\quad\nu=0\\1&\quad\nu=1,2,\cdots,N-1&\end{cases}\end{aligned}$$

逆变换为

$$\begin{aligned}f(x,y)=\frac{2}{N}\sum_{\begin{array}{c}u=0\\\end{array}}^{N-1}\sum_{\begin{array}{c}v=0\\\end{array}}^{N-1}K(u)K(v)F(u,v)\cos\left[\frac{\pi(2x+1)u}{2N}\right]\cos\left[\frac{\pi(2x+1)u}{2N}\right]\\x,\:y=1,2,...,N-1\end{aligned}$$

$$\begin{aligned}K\left(u\right)&=\begin{cases}\frac{1}{\sqrt{2}}&\quad u=0\\1&\quad u=1,2,\cdots,N-1&\end{cases}\\\\K\left(\nu\right)&=\begin{cases}\frac{1}{\sqrt{2}}&\quad\nu=0\\1&\quad\nu=1,2,\cdots,N-1\end{cases}\end{aligned}$$

与一维的形式类似，我们也可以找出基函数，然后完成类似的定义

$$\begin{aligned}F&\:=\:q\cdot f\:\cdot q^T\\\\f&\:=\:q^T \cdot F\:\cdot q\end{aligned}$$