DCT

离散余弦变换（Discrete Cosine Transform, DCT）是离散傅里叶变换（Discrete Fourier transform, DFT）的变体，其数学公式推导位于 详解离散余弦变换（DCT），思路非常清晰，本文不再赘述。

DCT 用于 JPEG 压缩

JPEG 压缩是一种有损压缩，其思路是这样的：

1. 每一张方形像素图先转为 YCbCr 空间的三个整数方阵 $X_i$ 存储。
2. 我们可以用下面这个方式用另一种方式存储任何像素方阵 $X$ ：只需确定一个可逆矩阵 $C$ ，存储 $Y=CX{C}^{-1}$，并且使用 $X=C^{-1}YC$ 在合适的时机还原。
3. 注意到，这样存储的 $Y$ 与 $X$ 有相同的规格，也没有特别性质保证 $Y$ 的可压缩性比 $X$ 更好，因此需要的存储空间是相同的。因此，我们希望通过使用特殊的 $C$ 来让保证 $Y$ 的可压缩性比 $X$ 更好，这样就能实现无损压缩，但这从理论上不可能。
4. 可是，这难以做到，于是退而求其次，我们需要对 Y 本身进行改变来提升可压缩性。JPEG使用的压缩方法是行程编码（Run-Length-Encoding, RLE），所以我们需要减小 Y 中数字的值域，最好出现很多 $0$，这都能使 RLE 变得有效。当然，改变 $Y$ 会导致有损压缩。
5. 这一点通过量化矩阵（Quantization Matrix）做到。量化矩阵是一个预先确定的矩阵 $Q$，规格与 $X$ 和 $Y$ 相同，元素值大于 $1$，于是定义 $Y_q$ 矩阵为 $Y_q(u,v)=round\left(\frac{Y(u,v)}{Q(u,v)}\right)$，这样就能做到减小值域和增加 $0$ 的数量。可以在 Quantization 找到如下示例：

6. 问题的关键在于这样压缩后，还原出来的 $X_q=C^{-1}{Y}_{q}C$ 还像不像原来的图像？可想而知，如果 $C$ 是随意选取的，那么效果一定很差，因此需要谨慎地选取 $C$ 来让 $Y$ 有特别的性质。而 JPEG 算法中的 $C$ ，实际上就是 DCT 变换矩阵，这让 $Y$ 成为时域 $X$ 对应的频域矩阵。
7. 我们知道低频信息决定了图像的整体，而高频信息对应边缘和细节。因此在有损压缩中，优先保留低频信息，而高频信息去除也无妨，因此量化矩阵 $Q$ 的元素从左上角的低频到右下角的高频呈增大趋势。
8. 最后，对于 $Y_q$，进行 Zigzag 扫描，使 $0$ 集中在末尾，再对扫描结果串进行 RLE 编码，最后进行哈夫曼熵编码。
9. 部分实现细节是：压缩并不直接对整个像素矩阵进行，而是分为 $8\times 8$ 的小矩阵，也就是 $X,Y,C,Q$ 的规格始终为 $8\times 8$ ；每个像素先减 128 使信号中心在 0 附近

DCT 中的延拓和平移如何改变频谱能量分布？

一个值得思考的问题是：DCT 不同于 DFT，它对原信号做了偶延拓，这会不会导致原来的频率能量分布改变？答案是会。

我们先让原信号向右平移 $b$ ，根据平移定理，这使得傅里叶变换的结果乘上 $e^{-2\pi ibs}$ 因子，不改变频率的模，只改变了频率的相位，从而也就不改变频谱能量分布。

然后，增加对称的信号 $g(t)=f(-t)$，则 $(\mathcal{F}g)(s)=(\mathcal{F}f)(-s)$ ，因此 $(\mathcal{F}(f+g))(s)=(\mathcal{F}f)(s)+(\mathcal{F}f)(-s)$，由于共轭性，这抵消了频率虚部，并且将实部放大为 $2$ 倍，这显然能够改变不同频率能量的序关系，因为排序依据从模变成了原信号的实部。这是公平的，我们不能认为这让能量向低频聚集，也不能认为这让能量向高频聚集。

最后，相对于 DFT，DCT 确实能让能量向低频聚集，从而提高能量集中度。这是因为，DFT 做周期延拓并截断后，由于周期左端和右端的值不同，在周期边界处实际上产生了断裂，这改变了原来的频谱，产生了高频信号。而 DCT 先做了偶对称再进行周期延拓，此时周期的左端和右端是相等的，没有产生断裂，所以相对于 DFT，能量留在了低频部分。

由于压缩时对低频信号的保留更完整，我们当然希望能量向低频聚集，让压缩后图像与原图像的相似度更高，视觉效果更好。同时，由于高频能量更低，在压缩后会产生更多的 $0$ 或其他连续相同数字，提高压缩率。