-
线性代数学习笔记9-2：基变换（求变换后的坐标、同一个线性变换不同相似矩阵）、图像压缩（基变换的应用）
本文介绍基变换的基本知识，更多内容参考3.7 基变换，图像压缩
基变换
之前说过，矩阵基于坐标来描述线性变换（给定依赖的坐标系，则线性变换对应于一个特定的矩阵）；
基变换就是「转换所依赖的坐标系」，从不同角度观察同一个问题，意义在于选择合适的基向量可以简化计算；基变换的重要应用就是图像、音视频的压缩储存
基变换和线性变换有某种内在联系
基变换前后：
输入/输出的空间维度相同，对应拉伸和旋转的线性变换；
输入/输出的空间维度不同，对应投影/降维的线性变换；
而我们学习线性变换时，可以从“基向量发生变换”的角度理解其对应的矩阵，详见线性代数学习笔记3-1：矩阵与线性变换进行基变换时，发生了两件事：
- 每个向量（在新的基向量下）有了新的坐标，求新旧坐标之间的关系，此即基变换的坐标转换问题
基变换只不过是在同一个空间中，用不同方式（基于不同坐标系）来描述同一个向量 - （由于矩阵基于坐标来描述线性变换），每个线性变换（在新坐标系下）有了新的矩阵表示，求新旧矩阵之间的关系，此即相似矩阵问题（同一线性变换在不同坐标系下的矩阵表示）
相似矩阵只不过是在不同坐标系下，同不同方式来描述同一个线性变换
1. 基变换的坐标转换问题
原坐标系的基向量为 v 1 , v 2 , . . . , v n \mathbf{v}_1,\mathbf{v}_2,...,\mathbf{v}_n v1,v2,...,vn
若向量 x = x 1 v 1 + x 2 v 2 + … + x n v n \mathbf{x}=x_{1} \mathbf{v}_{1}+x_{2} \mathbf{v}_{2}+\ldots+x_{n} \mathbf{v}_{n} x=x1v1+x2v2+…+xnvn，其坐标记为 x = [ x 1 , x 2 , . . . , x n ] \mathbf{x}=[\mathrm x_1, \mathrm x_2, ...,\mathrm x_n] x=[x1,x2,...,xn]目标：我们希望变换到另一组基（ w 1 , w 2 , . . . , w n \mathbf{w}_1,\mathbf{w}_2,...,\mathbf{w}_n w1,w2,...,wn），在另一组基下表示同一个向量 x \mathbf{x} x
- 这就是要求解一组 c = [ c 1 , c 2 , . . . , c n ] \mathbf{c}=[\mathrm c_1, \mathrm c_2, ...,\mathrm c_n] c=[c1,c2,...,cn]，满足 x = c 1 w 1 + c 2 w 2 + … … + c n w n \mathbf{x}=c_1 \mathbf{w}_1+c_2 \mathbf{w}_2+\ldots \ldots+c_n \mathbf{w}_n x=c1w1+c2w2+……+cnwn
- 最终，问题就是求解方程
x
=
W
c
\mathbf x=\boldsymbol{W} \mathbf{c}
x=Wc
其中 W \boldsymbol{W} W的列向量为另一组基 w 1 , w 2 , . . . , w n \mathbf{w}_1,\mathbf{w}_2,...,\mathbf{w}_n w1,w2,...,wn
方程的解 c = [ c 1 , c 2 , . . . , c n ] = W − 1 x \mathbf{c}=[\mathrm c_1, \mathrm c_2, ...,\mathrm c_n]=\boldsymbol{W}^{-1} \mathbf{x} c=[c1,c2,...,cn]=W−1x就是 x \mathbf{x} x在另一组基下的坐标
ps.这里的前提是，我们可以写出新的基向量「在旧基向量体系下的坐标」（即： W \boldsymbol{W} W的列向量/新的基向量的坐标，是针对原坐标系而言的），从而方程两端才有可比性、才能相等 - 可见，新坐标系的基向量选取恰当，才能保证 W \boldsymbol{W} W可逆、新坐标 c = W − 1 x \mathbf{c}=\boldsymbol{W}^{-1} \mathbf{x} c=W−1x易于计算
2. 相似矩阵
矩阵基于特定坐标系来描述线性变换，或者说同一个线性变换，在不同坐标系下的矩阵不同，实际上这就是两个相似矩阵
对于同一个线性变换：
- 在基向量
v
1
,
v
2
,
.
.
.
,
v
n
\mathbf{v}_1,\mathbf{v}_2,...,\mathbf{v}_n
v1,v2,...,vn下，线性变换对应矩阵
A
\boldsymbol A
A
在基向量 w 1 , w 2 , . . . , w n \mathbf{w}_1,\mathbf w_2,...,\mathbf{w}_n w1,w2,...,wn下，线性变换对应矩阵 B \boldsymbol B B - 那么，两个矩阵的关系为：
B
=
M
−
1
A
M
\boldsymbol B=\boldsymbol M^{-1}\boldsymbol A\boldsymbol M
B=M−1AM
其中， M \boldsymbol M M就是基变换矩阵
基变换的应用：信号有损压缩问题
注意，压缩分为有损和无损，这里讨论有损压缩
对于一个原始未处理的信号 x \mathbf x x（二维图像也可以化为一个列向量），有损压缩的思路是：
-
首先进行基变换，用另一组基 w 1 , w 2 , . . . , w n \mathbf{w}_1,\mathbf w_2,...,\mathbf{w}_n w1,w2,...,wn表示同样的信号 x \mathbf x x，其在新基向量下的坐标为 c = [ c 1 , c 2 , . . . , c n ] \mathbf{c}=[\mathrm c_1, \mathrm c_2, ...,\mathrm c_n] c=[c1,c2,...,cn]，满足 x = c 1 w 1 + c 2 w 2 + … … + c n w n \mathbf{x}=c_1 \mathbf{w}_1+c_2 \mathbf{w}_2+\ldots \ldots+c_n \mathbf{w}_n x=c1w1+c2w2+……+cnwn
注意，这一步是无损的，但这样做的意义是：
若不变换就不能进行压缩（丢掉任意一个基向量的坐标信息，都会损失掉大量信息）；
而如果选择了一组良好的基，一部分基向量包含主要信息，而另一部分基向量的系数很小，无关紧要，从而可以设定阈值，直接将较小的系数（坐标值）置为0丢弃，从而以较小的信息损失实现压缩 -
对新坐标 c = [ c 1 , c 2 , . . . , c n ] \mathbf{c}=[\mathrm c_1, \mathrm c_2, ...,\mathrm c_n] c=[c1,c2,...,cn]进行压缩，也就是丢弃一些较小的坐标值（对整个图片呈现效果影响不大），得到新的“近似”坐标 c ^ \mathbf{\hat{c}} c^（含大量0元素），这一步是有损压缩（在1中已经讲过原理）
-
最终，有损压缩后的信号为 x ^ = ∑ c ^ i v i \hat{\mathbf{x}}=\sum \hat{c}_{i} \mathbf{v}_{i} x^=∑c^ivi，此时求和项已经不是n项（ c ^ \mathbf{\hat{c}} c^含大量0元素），可能只剩下两三项，从而实现压缩
整个压缩流程如图：
可见，图像压缩的本质就是基变换寻找合适的基
上面说过，想要获得好的压缩效果，就需要找到一组好的基，它需要满足：
- 计算速度快（做基变换/求逆/做乘法迅速）
做基变换是上述压缩过程的必须步骤
而再结合前文的知识，求解基变换后的新坐标，就是求 c = W − 1 x \mathbf{c}=\boldsymbol{W}^{-1} \mathbf{x} c=W−1x，因此要求求逆 W − 1 \boldsymbol{W}^{-1} W−1迅速、做乘法 W − 1 x \boldsymbol{W}^{-1} \mathbf{x} W−1x迅速 - 基向量有较好的压缩性，即：用少量基向量就能近似重现信号/图像
如果单纯要求速度快，那么“不变换”就是运算速度最快的方案，然而后续压缩就会丢失大量信息；而合适的基下，信号 x \mathbf x x的 c = [ c 1 , c 2 , . . . , c n ] \mathbf{c}=[\mathrm c_1, \mathrm c_2, ...,\mathrm c_n] c=[c1,c2,...,cn]有很多较小值，可以实现损失很小的压缩
图像压缩JPEG
JPEG（联合图像专家组 Joint Photographic Experts Group）是一种图像有损压缩
图像由若干像素点组成，每个像素点的参数为0-255的灰度值（彩色图像与之类似，区别是有三个通道）
对于较大的512x512图像，JPEG先将其划分为8x8的较小网格（64个像素点），并且将二维的数据排放到一列，那么最终图像可以视为一个列向量 x \mathbf{x} x，假如图像共有 64 64 64个像素点，那么 x \mathbf{x} x的长度就是 64 64 64（向量有 64 64 64个分量，每个分量就是一个像素点的灰度值），即 x \mathbf{x} x位于 R 64 \mathbf{R}^{64} R64空间内，需要64个基向量
正常情况下，我们使用标准基 [ 1 0 0 ⋮ 0 ] , [ 0 1 0 ⋮ 0 ] , ⋯ [ 0 0 0 ⋮ 1 ] \left[100⋮0\right], \left[010⋮0\right], \cdots\left[000⋮1\right] ⎣ ⎡100⋮0⎦ ⎤,⎣ ⎡010⋮0⎦ ⎤,⋯⎣ ⎡000⋮1⎦ ⎤，基向量长度/个数与图像的列向量 x \mathbf{x} x相同（像素点总数64）
基向量选择方案1：直观想法
直观上，图像中的一片区域，颜色是非常接近，基于这个特性，我们可以压缩图像
此时 [ 1 1 1 ⋮ 1 ] \left[111⋮1\right] ⎣ ⎡111⋮1⎦ ⎤（低频信号，频率为0）是一个很好的基向量，因为这代表“平滑”，或者说对应图像中颜色接近的一个色块，在图像经常存在，因而其系数通常很大，大片色块几乎只需要这一个基向量来表现（而其余的基向量的系数/坐标值很小，可以压缩丢弃）
例如，一幅天空的照片，有大片白色，此时我们将「亮度值全为255」作为一个基向量，那么白色色块基本可由这一个基向量表征，而其他系数（坐标值）较小的基向量，可以压缩（系数置为0）
基于类似思路，还可得到与上述基向量配套的一系列基向量：
- 基向量 [ + 1 − 1 + 1 − 1 ⋮ ] \left[+1−1+1−1⋮\right] ⎣ ⎡+1−1+1−1⋮⎦ ⎤对应类似棋盘的“黑白相间”状态，即噪音扰动等（最高频信号），基变换后在图像中很少存在
- 基向量 [ ⋮ + 1 − 1 ⋮ − 1 ] \left[⋮+1−1⋮−1\right] ⎣ ⎡⋮+1−1⋮−1⎦ ⎤对应图像一半图像暗一半图像亮的情况
基向量选择方案2：傅里叶基Fourier basis
从频域上看，语音和图像信号，大部分集中在一个频段（而其余频段对应的傅里叶基系数很小，可以压缩丢弃），则可以以频率的高低划分出一系列基向量，这就是傅里叶基
傅里叶基就是之前讲过的傅里叶矩阵的列向量，每个元素为复数的幂（用其做基变换，就是傅里叶变换，即从时域到频域的分析）
对于 R 8 \mathbf{R}^{8} R8空间内的列向量 x \mathbf{x} x，其傅里叶基为 [ 1 1 1 1 1 1 1 1 ] , [ 1 ω ω 2 ω 3 ω 4 ω 5 ω 6 ω 7 ] , [ 1 ω 2 ω 4 ω 6 ω 8 ω 10 ω 12 ω 14 ] , ⋯ [ 1 ω 7 ω 14 ω 21 ω 28 ω 35 ω 42 ω 49 ] \left[11111111\right], \left[1ωω2ω3ω4ω5ω6ω7\right], \left[1ω2ω4ω6ω8ω10ω12ω14\right], \cdots\left[1ω7ω14ω21ω28ω35ω42ω49\right] ⎣ ⎡11111111⎦ ⎤,⎣ ⎡1ωω2ω3ω4ω5ω6ω7⎦ ⎤,⎣ ⎡1ω2ω4ω6ω8ω10ω12ω14⎦ ⎤,⋯⎣ ⎡1ω7ω14ω21ω28ω35ω42ω49⎦ ⎤
基向量选择方案3：小波 Wavelets
小波基是傅里叶基的有力竞争对手
对于 R 8 \mathbf{R}^{8} R8空间内的列向量 x \mathbf{x} x，其小波基为 [ 1 1 1 1 1 1 1 1 ] , [ 1 1 1 1 − 1 − 1 − 1 − 1 ] , [ 1 1 − 1 − 1 0 0 0 0 ] , [ 0 0 0 0 1 1 − 1 − 1 ] , [ 1 − 1 0 0 0 0 0 0 ] , [ 0 0 1 − 1 0 0 0 0 ] , [ 0 0 0 0 1 − 1 0 0 ] , [ 0 0 0 0 0 0 1 − 1 ] \left[11111111\right], \left[1111−1−1−1−1\right], \left[11−1−10000\right], \left[000011−1−1\right], \left[1−1000000\right], \left[001−10000\right], \left[00001−100\right], \left[0000001−1\right] ⎣ ⎡11111111⎦ ⎤,⎣ ⎡1111−1−1−1−1⎦ ⎤,⎣ ⎡11−1−10000⎦ ⎤,⎣ ⎡000011−1−1⎦ ⎤,⎣ ⎡1−1000000⎦ ⎤,⎣ ⎡001−10000⎦ ⎤,⎣ ⎡00001−100⎦ ⎤,⎣ ⎡0000001−1⎦ ⎤
这个只是一个小波选择，然而这一组基中有太多从+1跳转到-1的变化，还有很多种更多精细的选择
小波基的优势：- 是一组正交基，即任意两个基向量做内积为0（但不是标准正交的，可以将其长度标准化）
从而求逆运算速度快（列向量标准正交，求逆等价于转置）； - 并且矩阵向量乘法也很快，因为有快速小波变换FWT
之前学过，对于线性变换，其特征向量给出最佳的基向量，因为在此坐标系下线性变换对应简单的对角阵，每个特征向量给出了主导方向，这是压缩最理想的结果
然而实际中找出图像的特征向量代价太大，我们转而寻求代价小但是接近理想状态的基向量（例如小波基）进行基变换，完成压缩过程 - 每个向量（在新的基向量下）有了新的坐标，求新旧坐标之间的关系，此即基变换的坐标转换问题
-
相关阅读:
selenium 自动化测试
数据结构题目收录（四）
ubuntu部署k8s
VS2022开发Arduino（90%转载10%原创）
河北工业大学数据挖掘实验二 数据立方体与联机分析处理构建
Java 集合类的高级特性介绍
项目需求及架构设计
mysql-binlog
【EI会议征稿】第四届计算机网络安全与软件工程国际学术会议（CNSSE 2024）
Spring Boot TestEntityManager
- 原文地址：https://blog.csdn.net/Insomnia_X/article/details/126681829