DCT 离散余弦变换

本文最后更新于:2022年7月4日 上午

DCT 变换的全称是离散余弦变换(Discrete Cosine Transform),主要运用于数据或图像的压缩。本文记录相关内容。

概述

DCT变换的全称是离散余弦变换(Discrete Cosine Transform),主要运用于数据或图像的压缩。
由于DCT能够将空域的信号转换到频域上,因此具有良好的去相关性的性能。DCT变换本身是无损的且具有对称性。对原始图像进行离散余弦变换,变换后DCT系数能量主要集中在左上角,其余大部分系数接近于零。将变换后的DCT系数进行门限操作,将小于一定值得系数归零,这就是图像压缩中的量化过程,然后进行逆DCT运算,可以得到压缩后的图像。

定义

  • 一维 DCT 变换
$$ \begin{array}{c} F(u)=c(u) \sum_{i=0}^{N-1} f(i) \cos \left[\frac{(i+0.5) \pi}{N} u\right] \\ c(u)=\left\{\begin{array}{l}\sqrt{\frac{1}{N}}, u=0 \\ \sqrt{\frac{2}{N}}, u \neq 0\end{array}\right. \end{array} $$

其中,$f(i)$为原始的信号,$F(u)$是DCT变换后的系数,$N$为原始信号的点数,$c(u)$可以认为是一个补偿系数,可以使DCT变换矩阵为正交矩阵。

  • 二维 DCT 变换
$$ \begin{array}{c} F(u, v)=c(u) c(v) \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} f(i, j) \cos \left[\frac{(i+0.5) \pi}{N} u\right] \cos \left[\frac{(j+0.5) \pi}{N} v\right] \\ c(u)=\left\{\begin{array}{l}\sqrt{\frac{1}{N}}, u=0 \\ \sqrt{\frac{2}{N}}, u \neq 0\end{array}\right. \end{array} $$

其中,$f(i,j)$为原始的信号,$F(u,v)$是DCT变换后的系数,$N$为原始信号的点数,$c(u),c(v)$可以认为补偿系数,可以使DCT变换矩阵为正交矩阵。

推导

这么神奇的定义其实是 DFT 变换推导而来

由来

  • 在开始讲DCT变换之前,我们来看看DFT的变换公式

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

  • 将上式拆开

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

  • 实数部分为:

$$
\sum_{n=0}^{N-1} x[n]\left(\cos \frac{2 \pi \mathrm{kn}}{N}\right)
$$

  • 虚数部分为:

$$
j \sum_{n=0}^{N-1} x[n] \sin \left(\frac{2 \pi k n}{N}\right)
$$

  • 取 $ \cos \left(\frac{2 \pi k n}{N}\right)=\cos (k t) $,实数部分:

$$
R e[k]=\sum_{n=0}^{N-1} x[n] \cos (k t)
$$

  • 虚数部分

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

  • 当 $x[n]$ 为实偶函数时,$x[n] \sin (k t)$ 为奇函数

    那么如果我们可以构造一个实偶函数在$[-p, p]$ 的累加区间,岂不是这部分虚数就为 0 了?

    为了这个念想开始了 DCT 变换的构造

构造 DCT 变换

如果输入信号是实偶信号就可以不考虑虚部的 DFT 计算了,但是事实上没有那么多偶函数信号来用,那么只要信号是实数我们可以自己构造一组偶函数信号

  • 对于一组给定的真实实信号$ {x[0], x[1] \ldots x[N-1]} $,将这部分信号向负数方向镜像延拓一倍,用$x’$ 表示:

$$
{x’[-N],x’[-N+1],…,x’[-1],x’[0], x’[1] \ldots x’[N-1]}
$$

  • 并且有:

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

  • 其中,蓝色为原始信号,红色为延拓后的信号这样,我们就将一个实信号变成了一个实偶信号,那么,对这个延拓的信号的DFT变换怎么写呢,显然,信号的区间已经从之前的$[0, N-1]$,变成了$[-N,N-1]$,因此,DFT 变换变为:

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

  • 但是,这样的插值之后也随之带来了一个问题,这个信号并不关于m=0偶对称,它关于$ m=-\frac{1}{2} $ 对称,因此,为了让信号仍然关于原点对称,把整个延拓的信号向右平移$\frac{1}{2}$个单位

  • 上式 DFT 变换调整为

$$
X[k]=\sum_{m=-N+\frac{1}{2}}^{N-\frac{1}{2}} x^{\prime}\left[m-\frac{1}{2}\right] e^{\frac{-j 2 \pi m k}{2 N}}
$$

  • 此时信号已经为定义域关于 0 对称的实偶函数了,因此虚部系数为 0:

$$
X[k]=\sum_{m=-N+\frac{1}{2}}^{N-\frac{1}{2}} x^{\prime}\left[m-\frac{1}{2}\right] e^{\frac{-j 2 \pi m k}{2 N}}=\sum_{m=-N+\frac{1}{2}}^{N-\frac{1}{2}} x^{\prime}\left[m-\frac{1}{2}\right] \cos \left(\frac{2 \pi m k}{2 N}\right)
$$

  • 此时 m 定义域有小数也有负数的部分,仍然不是十分合理,根据偶函数性质进一步变换,得到:

$$
\sum_{m=-N+\frac{1}{2}}^{N-\frac{1}{2}} x^{\prime}\left[m-\frac{1}{2}\right] \cos \left(\frac{2 \pi m k}{2 N}\right)=2 * \sum_{m=\frac{1}{2}}^{N-\frac{1}{2}} x^{\prime}\left[m-\frac{1}{2}\right] \cos \left(\frac{2 \pi m k}{2 N}\right)
$$

  • 将变量进行替换,$m=n+\frac{1}{2}$,得到:

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

  • 至此 DCT 变换的核心部分已经出现了,系数$c(u)$是为了工程上矩阵运算正交化方便取了:
$$ c(u)=\left\{\begin{array}{l}\sqrt{\frac{1}{N}}, u=0 \\ \sqrt{\frac{2}{N}}, u \neq 0\end{array}\right. $$

用途

  • DCT变换是傅里叶变换的一种特殊情况,而真实数据绝大多数都是实数数据,进行DCT变换可以不再和虚数打交道,因此应用范围很广。
  • 在数字图像领域 JPEG 图像压缩使用了 DCT变换。
  • DCT同时也在音频信号处理,数字水印方面也发挥着各种作用。

参考资料


DCT 离散余弦变换
https://www.zywvvd.com/notes/study/math/fourier-transform/dis-cosine-trans/dis-cosine-trans/
作者
Yiwei Zhang
发布于
2022年3月28日
许可协议