用奇异值压缩图像

特征值&奇异值

如果说一个向量 $v$ 是方阵 $A$ 的特征向量，将一定可以表示成下面的形式：

$$
A v=\lambda v
$$

这时候 $λ$ 就被称为特征向量 $v$ 对应的特征值，一个矩阵的一组特征向量是一组正交向量。特征值分解是将一个矩阵分解成下面的形式：

$$
A=Q \Sigma Q^{-1}
$$

总结一下，特征值分解可以得到特征值与特征向量，特征值表示的是这个特征到底有多重要，而特征向量表示这个特征是什么。但是特征值分解也有很多的局限，比如说变换的矩阵必须是方阵。

对于普通非方阵普通方阵，描述其特征，我们使用奇异值分解。对于任意一个 $m \times n$ 的矩阵 $A$ ， $A^{T} A$ 总是一个 $n$ 阶的对称矩阵, 而且其特征值都为非负实数。将 $A^{T} A$ 的特征值表示为非负实数的平方，并按照递减的顺序排列：

$$
\sigma_{1}^{2} \geq \sigma_{2}^{2} \geq \cdots \geq \sigma_{r}^{2}>0, \quad \sigma_{r+1}^{2}=\cdots=\sigma_{n}^{2}=0, \quad r=\operatorname{rank}(A)
$$

存在 $m$ 阶的正交矩阵 $U$ 与 $n$ 阶的正交矩阵 $V$ 使得:

$$
A=U^{} S^{} V^{T}, \quad S=\operatorname{diag}\left(\sigma_{1}, \cdots, \sigma_{r}\right)
$$

这个分解就称为 A 的奇异值分解。

压缩图片

图片可以看作一个矩阵，图片像素大小即为矩阵的大小，每个像素值对应的即为矩阵的每个元素。我们记这个由图片组成的矩阵为 $A$ ，假设其为 $n*m$ 的矩阵。对 $A$ 进行奇异值分解，那么得到的 $U$ 是一个 $n*n$ 的方阵，$S$ 是一个 $n*m$ 的矩阵，$V^T$ 是一个 $n*n$ 的矩阵

$$
A_{m \times n}=U_{m \times m}S_{m \times n}V^{T}_{n \times n}
$$

奇异值 $σ$ 跟特征值类似，在矩阵 $S$ 中也是从大到小排列，而且 $σ$ 的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。于是我们就可以使用前几项大的奇异值来近似整个矩阵（图片），达到压缩图片的目的。

$$
A_{m \times n} \approx U_{m \times r} S_{r \times r} V_{r \times n}^{T}
$$

右边的三个矩阵相乘的结果将会是一个接近于 $A$ 的矩阵，在这儿，$r$ 越接近于 $n$ ，则相乘的结果越接近于 $A$ 。而这三个矩阵的面积之和（在存储观点来说，矩阵面积越小，存储量就越小）要远远小于原始的矩阵 $A$ ，于是仅需要记录 $U、S、V^{T}$ 即可代替原本的像素矩阵。

理论存在，实践开始

我们将一个黑白颜色的图像表示为一个 $15 \times 25$ 矩阵，其中每个条目要么是 $0$ ，代表黑色像素，要么是 $1$ ，代表白色。因此，矩阵中有 $375$ 个条目

对 $M$ 进行奇异值分解，发现只有三个非零奇异值

$$
\begin{array}{l}
\sigma_{1}=14.72 \
\sigma_{2}=5.22 \
\sigma_{3}=3.31
\end{array}
$$

则矩阵可表示为

$$
M=\mathbf{U}{1} \sigma{1} \mathbf{V}{1}^{T}+\mathbf{U}{2} \sigma_{2} \mathbf{V}{2}^{T}+\mathbf{U}{3} \sigma_{3} \mathbf{V}_{3}^{T}
$$

有三个向量 $V_{i}$ ，每个向量有 $15$ 个条目，三个向量 $U_{i}$ ，每个向量都有 $25$ 个条目，以及三个奇异值 $σ_{i}$ 。可以仅使用 $123$ $(3 \times 15(U_{i}) + 3 \times 45(V_{i}) + 3(\sigma_{i}))$ 个数字而不是矩阵中出现的 $375$ 个数字来表示矩阵，从而达到压缩图像的目的。

实现代码

使用工具：python(函数库真香)，你需要准备以下内容：

pillow 库：用于图像处理
numpy 库：储存处理数组
一张jpg图片，不要太大，放置于与源代码相同的文件夹内，重命名为 1.jpg

# 引入 pillow
# 引入 numpy
import numpy as np
from PIL import Image

# 奇异值分解函数
def imgCompress(channel,percent):
    U, sigma, V_T = np.linalg.svd(channel)
    m = U.shape[0]
    n = V_T.shape[0]
    reChannel = np.zeros((m,n))
 
    for k in range(len(sigma)):
        reChannel = reChannel + sigma[k]* np.dot(U[:,k].reshape(m,1),V_T[k,:].reshape(1,n))
        if float(k)/len(sigma) > percent:
            reChannel[reChannel < 0] = 0
            reChannel[reChannel > 255] = 255
            break
 
    return np.rint(reChannel).astype("uint8")
 
# 请在源文件文件夹中放置一张图片：1.jpg
oriImage = Image.open(r'1.jpg', 'r')
imgArray = np.array(oriImage)

# 3个颜色通道，R、G、B，将其分离
R = imgArray[:, :, 0]
G = imgArray[:, :, 1]
B = imgArray[:, :, 2]


a=float(input("请输入压缩数值（值越大越清晰）:")) # 对单通道颜色矩阵进行奇异值分解，并取前a%的奇异值
reR = imgCompress(R, a)
reG = imgCompress(G, a)
reB = imgCompress(B, a)
reI = np.stack((reR, reG, reB), 2)
 
Image.fromarray(reI).save("{}".format(a)+"compress.jpg")