L32-基变换和图像压缩

参考

Unit III: Positive Definite Matrices and Applications - Change of Basis; Image Compression | pdf
课本章节：Read Section 7.2 in the 4^th edition or Section 8.2 in the 5^th edition.
练习题：L32-基变换和图像压缩-习题集

可以选择不同的基向量组合来表示同一个向量空间，这会影响在该空间中的数据的表示形式（向量的坐标形式），选择的一组合适的基向量可以有效地简化运算，其中一个应用实例是图像压缩（降低数据量的大小）

最常见的一些基向量：

傅里叶基向量 Fourier basis vectors
例如以下是在 $\mathbb{R}^{8}$ 空间的一组傅里叶基向量（选择构成傅里叶矩阵的向量来作为一组基向量） $\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ \end{bmatrix}, \begin{bmatrix} 1 \\ \omega \\ \omega^{2} \\ \omega^{3} \\ \omega^{4} \\ \omega^{5} \\ \omega^{6} \\ \omega^{7} \\ \end{bmatrix}, \begin{bmatrix} 1 \\ \omega^{2} \\ \omega^{4} \\ \omega^{6} \\ \omega^{8} \\ \omega^{10} \\ \omega^{12} \\ \omega^{14} \\ \end{bmatrix}, \dots, \begin{bmatrix} 1 \\ \omega^{7} \\ \omega^{14} \\ \omega^{21} \\ \omega^{28} \\ \omega^{35} \\ \omega^{42} \\ \omega^{49} \\ \end{bmatrix}$
小波基向量 Haar wavelet basis
例如以下是在 $\mathbb{R}^{8}$ 空间的一组小波基向量（这些基向量是相互正交的） $\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ -1 \\ -1 \\ -1 \\ -1 \\ \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ -1 \\ -1 \\ \end{bmatrix}, \begin{bmatrix} 1 \\ -1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{bmatrix}, \dots, \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ -1 \\ \end{bmatrix}$

例如采用傅里叶基向量对图像压缩流程如下

signal~x \xrightarrow{lossless} 64~coefficients~c \xrightarrow{lossy compression} \hat{c} (many~zeros) \xrightarrow{} \hat{x}=\sum \hat{c_{i}}v_{i}

说明

一般将分辨率为 $512 \times 512$ 的图像分割为一个个 $8 \times 8$ 较小的图片分别进行处理，所以在流程前半部分需要选择一组元素数量为 $64$ 的基向量来表示 $\mathbb{R}^{64}$ 的向量空间

basis change 基变换：选择一组合适的基向量来表示原始的输入图像信号 $x$ ，这一步属于无损压缩，该信号用一组基向量的线性组合表示，所以可以得到一组相应的系数（ $64$ 个系数 $c$ ）
threshold 阈值量化压缩：「抛弃」系数较小的项（即将相应的基向量的系数改为 $0$ ），则可以得到一组新的系数（如果所选择的基向量合适，可能包含大量的 $0$ 作为系数 $\hat{c}$ ，即只需要用几个基向量就可以表示大部分的信号数据）
重构信号： $\hat{x}=\sum \hat{c_{i}}v_{i}$ 用仅剩的几个基向量（系数不为 $0$ ）的线性组合来表示原信号，达到压缩的目的

以上步骤与本课程相关的是基变换，即从标准正交基变换为其他基向量 $x=c_{1}w_{1}+\dots+c_{8}w_{8}$ （其中 $x$ 是使用标准正交基时向量的坐标表示形式，该公式将其改为用另一组基向量的线性变换来表示），关键是寻找系数 $c_{i}$ ，即 $c=W^{-1}x$

一组 good basis 「好」的基向量是可以让基变换更简单、更快速地完成计算的。而对于特定的场景，例如图像压缩，则衡量一组基向量是否足够「好」的标准还可能有附加的条件

可以快速计算（基变换）
压缩效率高（变换后只需要少量的基向量的线性组合既可以表示图片的大部分信息，即大部分系数 $c_{1}$ 是接近于零的，相应的基向量可以舍去）

视频压缩

视频压缩不仅需要考虑对每一帧压缩（和图片压缩一样），还需要考虑对系列帧进行压缩（只保留帧与帧之间的差别）

基变换

可以通过公式 $x=Wc$ 对向量 $x$ 进行基变换，其中矩阵 $W$ 是由一组新的基向量构成（作为矩阵的列向量），列向量 $c$ 为这一组新的基向量的线性组合的系数构成

基变换与线性变换

基变换后，向量的坐标表示形式变了，如果用矩阵来描述一个线性变换，那么同样的线性变换在不同的一组基向量的描述下，所对应的矩阵也会相应的变化

当基向量为 $v_{1}, v_{2}, \dots, v_{8}$ 时，线性变换 $T$ 对应的矩阵为 $A$ ；而选择基向量为 $w_{1}, w_{2}, \dots, w_{8}$ 时，则同样的线性变换 $T$ 所对应的矩阵为 $B$ ，那么这两个矩阵的关系时相似矩阵，即存在一个可逆矩阵 $M$ 使得等式成立 $B=MAM^{-1}$ ，其实 $M$ 为实现基变换矩阵（即新的一组基向量作为列向量构成的矩阵）

如果使用线性变换所对应的矩阵的特征向量作为该空间的一组基向量，则该线性变换所对应的矩阵就是一个对角矩阵，该矩阵（对角线上的）元素是特征值 $A=\Lambda$

证明

假如线性变换 $T$ 是将任意向量从向量空间 $\mathbb{R}^{8}$ 变换到同一个向量空间 $\mathbb{R}^{8}$ （两个向量空间都选择同一组基向量 $v_{1}, v_{2}, \dots, v_{8}$ 表示）

由于线性变换 $T(v)$ 用矩阵的形式表示为 $Av$ ，则基向量也是矩阵 $A$ 的特征向量，即基向量 $v_{i}$ 都满足 $T(v_{i})=Av_{i}=\lambda_{i}v_{i}$

而经过线性变换后 $Av_{i}$ 结果向量依然在 $\mathbb{R}^{8}$ 空间中，所以结果向量可以使用基向量来表示 $Av_{i}=c_{1}v_{1}+c_{2}v_{2}+\dots+c_{i}v_{i}+\dots+c_{8}v_{8}$

再结合前面分析 $T(v_{i})=Av_{i}=\lambda_{i}v_{i}$ 可知系数的具体值为 $Av_{i}=0 \cdot v_{1}+0\cdot v_{2}+\dots+\lambda_{i}v_{i}+\dots+0\cdot v_{8}$

所以对于基向量 $v_{1}, v_{2}, \dots, v_{8}$ 可得

\begin{aligned} \left\{\begin{matrix} T(v_{1})=\lambda_{1}v_{1}+0\cdot v_{2}+\dots+0\cdot v_{8} \\ T(v_{2})=0\cdot v_{1}+\lambda_{2}v_{2}+\dots+0\cdot v_{8} \\ \vdots \\ T(v_{i})=0\cdot v_{1}+\dots+\lambda_{i}v_{i}+\dots+0\cdot v_{8} \\ \vdots \\ T(v_{8})=0\cdot v_{1}+\dots+\lambda_{8}v_{8} \\ \end{matrix}\right. \end{aligned}

将以上等式的系数作为矩阵 $A$ 的相应列的向量，可得

A= \begin{bmatrix} \lambda_{1} & 0 & \dots & 0 & 0 & 0 \\ 0 & \lambda_{2} & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & \lambda_{i} & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 0 & 0 & \lambda_{8} \end{bmatrix}

矩阵 $A$ 为对角矩阵，该矩阵（对角线上的）元素是特征值 $A=\Lambda$

那么这一组基向量可以称得上是一组 good base 「好」的基向量，因为进行基变换时（ $x=Ac$ 所乘的矩阵是一个对角矩阵）易于计算。