史上最简SLAM零基础解读(3) - 白话来说SVD奇异值分解(1)→原理推导与奇异值求解举例

本人讲解关于slam一系列文章汇总链接:史上最全slam从零开始 有兴趣的朋友可以加微信 17575010159 相互讨论技术 - 文末公众号也可关注

 

一、前言

这篇博客，主要使用最通俗的语言来讲解SVD奇异值分解，通过该篇博客，将知道 SVD 的来龙去脉，底层原理。同时知道如何利用他去做图片压缩，PCA，求解矩阵(如 Fundamental 矩阵，Homography 矩阵)等。我会详细的讲解 SVD 的每一个细节。由浅到深，由窄到广。那么我们现在就开始吧。

 

二、简单原理介绍

在推导数学公式，以及几何意义之前，我们先来看看其物理层面的应用。这样有助于后面更深层次的理解。首先这里有个基本的概念简单说一下, 一个 m × n m \times n m×n 维的矩阵，我们可以分解成 m × k m \times k m×k 以及 k × n k \times n k×n 的矩阵相乘，如下图所示： 到了这一步还不够，我们还要继续分解，根据上面的原理，我们是不是可以对矩阵 X m × k X_{m\times k} Xm×k​ 做同样的分解，把他分解成两个矩阵。那么我们现在来做个假设(后面有推导该公式的细节以及计算过程)： A m × n = U m × m Σ m × n V n × n T (1) \tag{1} \color{blue} A_{m\times n}=U_{m\times m}\Sigma_{m\times n}V^T_{n \times n} Am×n​=Um×m​Σm×n​Vn×nT​(1)其下标 m × m , m × m , n × n {m\times m}, m\times m,n \times n m×m,m×m,n×n 分别表示对应形状。大家可能比较奇怪了，把一个矩阵分解成这个样子，有什么作用。如果矩阵 A m × m A_{m \times m} Am×m​ 使用其上三个矩阵来表示，似乎并没有节省空间。这个先不着急，继续往下分析，如果公式(1)中的具备如下特征： 对于 m m m 行 n n n 列的矩阵 A A A, 通过SVD分解之后，拆分成了3个子矩阵，其中 U U U 矩阵为 m m m 行 m m m 列的方阵， V V V 为 n n n 行 n n n 列的方阵， Σ \Sigma Σ为只有对角线有值的矩阵，其中的值称之为奇异值。看一个例子，原始矩阵如下: A 4 × 5 = [ 1 0 0 0 2 0 0 3 0 0 0 0 0 0 0 0 4 0 0 0 ] (2) \tag{2} \color{blue} A_{4\times 5}=\left[\begin{array}{lllll} 1 & 0 & 0 & 0 & 2 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 \end{array}\right] A4×5​= ​1000​0004​0300​0000​2000​ ​(2)奇异值分解的结果如下 U 4 × 4 = [ 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 ] , Σ 4 × 5 = [ 4 0 0 0 0 0 3 0 0 0 0 0 5 0 0 0 0 0 0 0 ] , V 5 × 5 T = [ 0 1 0 0 0 0 0 1 0 0 0.2 0 0 0 0.8 0 0 0 1 0 0.8 0 0 0 − 0.2 ] (3) \tag{3} \color{blue} U_{4\times 4}=\left[\begin{array}{llll} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{array}\right], \Sigma_{4\times 5}=\left[\begin{array}{ccccc} 4 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & \sqrt{5} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right], V^{T}_{5\times 5}=\left[\begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ \sqrt{0.2} & 0 & 0 & 0 & \sqrt{0.8} \\ 0 & 0 & 0 & 1 & 0 \\ \sqrt{0.8} & 0 & 0 & 0 & -\sqrt{0.2} \end{array}\right] U4×4​= ​0001​0100​1000​0010​ ​,Σ4×5​= ​4000​0300​005 ​0​0000​0000​ ​,V5×5T​= ​000.2 ​00.8 ​​10000​01000​00010​000.8 ​0−0.2 ​​ ​(3) 在奇异值分解中， Σ \Sigma Σ 矩阵的奇异值是按照从大到小的顺序排列的，而且减少的特别快，经常前 10% 的奇异值就占据了全部奇异值 99% 以上的比例。基于这个性质，我们可以只提取前几个奇异值及其对应的矩阵来近似的描述原来的矩阵。

那么我们现在就来做个实验，我们只获取矩阵得如下部分来复原矩阵 A A A:

也就是 U 4 × 3 = [ 0 0 1 0 1 0 0 0 0 1 0 0 ] , Σ 3 × 3 = [ 4 0 0 0 3 0 0 0 5 ] , V 3 × 5 T = [ 0 1 0 0 0 0 0 1 0 0 0.2 0 0 0 0.8 ] (4) \tag{4} \color{blue} U_{4\times 3}=\left[\begin{array}{llll} 0 & 0 & 1\\ 0 & 1 & 0\\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{array}\right], \Sigma_{3\times 3}=\left[\begin{array}{ccccc} 4 & 0 & 0\\ 0 & 3 & 0 \\ 0 & 0 & \sqrt{5}\\ \end{array}\right], V^{T}_{3\times 5}=\left[\begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ \sqrt{0.2} & 0 & 0 & 0 & \sqrt{0.8} \\ \end{array}\right] U4×3​= ​0001​0100​1000​ ​,Σ3×3​= ​400​030​005 ​​ ​,V3×5T​= ​000.2 ​​100​010​000​000.8 ​​ ​(4)这样就是然后我们求得 A 4 × 5 = U 4 × 3 Σ 3 × 3 V 3 × 5 T A_{4\times 5}=U_{4\times 3}\Sigma_{3\times 3} V^{T}_{3\times 5} A4×5​=U4×3​Σ3×3​V3×5T​,其结果如下： A 4 × 5 = [ 1 0 0 0 2 0 0 3 0 0 0 0 0 0 0 0 4 0 0 0 ] (5) \tag{5} \color{blue} A_{4\times 5}=\left[\begin{array}{lllll} 1 & 0 & 0 & 0 & 2 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 \end{array}\right] A4×5​= ​1000​0004​0300​0000​2000​ ​(5)可以看到其与(2)式中的 A 4 × 5 A_{4\times 5} A4×5​ 结果是完全一致的，完成了完美的复原。为什么这里能完成完美的复原呢? 因为 Σ \Sigma Σ 矩阵的奇异值表示其对应的 特征 ( 后面有详细讲解 ) \color{blue} {特征}(后面有详细讲解) 特征(后面有详细讲解) 重要性，其因为 Σ 3 × 3 \Sigma_{3\times 3} Σ3×3​ 已经包含了 Σ 4 × 5 \Sigma_{4\times 5} Σ4×5​ 的所有非零元素，所以其是可以完美复原出来的。现在我们来看看，其他的不同矩阵取值，如下图所示： 也就是 U 4 × 2 = [ 0 0 0 1 0 0 1 0 ] , Σ 3 × 3 = [ 4 0 0 3 ] , V 3 × 5 T = [ 0 1 0 0 0 0 0 1 0 0 ] (6) \tag{6} \color{blue} U_{4\times 2}=\left[\begin{array}{llll} 0 & 0 \\ 0 & 1 \\ 0 & 0 \\ 1 & 0 \end{array}\right], \Sigma_{3\times 3}=\left[\begin{array}{ccccc} 4 & 0\\\\ \\ 0 & 3 \\ \end{array}\right], V^{T}_{3\times 5}=\left[\begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ \\ 0 & 0 & 1 & 0 & 0 \\ \end{array}\right] U4×2​= ​0001​0100​ ​,Σ3×3​= ​40​03​ ​,V3×5T​= ​00​10​01​00​00​ ​(6)这样就是然后我们求得 A 4 × 5 = U 4 × 2 Σ 3 × 3 V 2 × 5 T A_{4\times 5}=U_{4\times 2}\Sigma_{3\times 3} V^{T}_{2\times 5} A4×5​=U4×2​Σ3×3​V2×5T​,其结果如下： A 4 × 5 = [ 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 4 0 0 0 ] (7) \tag{7} \color{blue} A_{4\times 5}=\left[\begin{array}{lllll} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 \end{array}\right] A4×5​= ​0000​0004​0300​0000​0000​ ​(7)这个时候我们与前面 (2) 式 A 4 × 5 A_{4 \times 5} A4×5​ 相比，可以发现其第1行的第4列与第4列的两个1，已经不见了。也就是说明其复原过程中出现了信息丢失。上面的两个实验可以总结如下图所示: 上图主要表示了如下公式( k k k与 n n n越接近说明图像还原度越高，当然压缩效果也没有那么明显): A m × n = U m × m Σ m × n V n × n T ≈ U m × k Σ k × k V k × n T (8) \tag{8} \color{blue} A_{m \times n}=U_{m \times m} \Sigma_{m \times n} V_{n \times n}^{T} \approx U_{m \times k} \Sigma_{k \times k} V_{k \times n}^{T} Am×n​=Um×m​Σm×n​Vn×nT​≈Um×k​Σk×k​Vk×nT​(8)

 

三、图像压缩

那么我们如何使用 SVD 来做图像压缩呢? 通过上面的介绍，我们就可以完成图像压缩了。这里我们把一张图像的像素看作前面的矩阵 A m × n A_{m \times n} Am×n​，然后编写代码如下：

import cv2
import numpy as np
# 调整该值重复运行代码保存图像
k = 200
img = cv2.imdecode(np.fromfile('./1.png', dtype=np.uint8), 0)
u, w, v = np.linalg.svd(img)
u = u[:, :k]
w = np.diag(w)
w = w[:k, :k]
v = v[:k, :]
img = u.dot(w).dot(v)
cv2.imencode('.jpg', img)[1].tofile('k={}.jpg'.format(k))

调整代码中的 k k k 值，重复保存图像。注意，根据前面的介绍我们可以得知 0 < k < h 0