基于稀疏表示理论的图像去噪
学习笔记
1 稀疏表示
1.1 稀疏表示理论
1993年 Mallat提出超完备字典，基于超完备字典的稀疏表示是图像稀疏去噪的重要研究方向。
1.2 稀疏表示模型
1.2.1 信号的稀疏模型
信号的稀疏表示是通过选取最少量的基函数通过线性组合对信号进行表示的过程。
设信号
x
⊂
R
N
x \subset R^N
x⊂RN,可由字典
D
=
[
d
1
,
d
2
,
⋅
⋅
⋅
，
d
M
]
⊂
R
N
×
M
（
M
>
N
)
D=[d_1,d_2,···，d_M] \subset R^{N \times M}（M>N)
D=[d1,d2,⋅⋅⋅，dM]⊂RN×M（M>N)中的少数基元线性组合来进行表示，即：
x
=
D
α
(1)
x=D\alpha \tag{1}
x=Dα(1)
其中，
α
=
[
α
1
,
α
2
,
⋅
⋅
⋅
，
α
M
]
T
⊂
R
M
\alpha=[\alpha_1,\alpha_2,···，\alpha_M]^T\subset R^M
α=[α1,α2,⋅⋅⋅，αM]T⊂RM是稀疏表示系数。
由于
M
>
N
M>N
M>N,因此求解
α
\alpha
α是一个欠定问题，解不唯一。稀疏表示算法寻找其中的最稀疏解，即
m
i
n
∥
α
∥
0
,
s
.
t
.
x
=
D
α
(2)
min \parallel\alpha\parallel_0,s.t. x=D\alpha\tag{2}
min∥α∥0,s.t.x=Dα(2)
其中，
∥
α
∥
0
\parallel\alpha\parallel_0
∥α∥0表示
α
\alpha
α的
l
0
l_0
l0范数，即
α
\alpha
α中的非0元素个数，
α
\alpha
α为稀疏表示系数，
D
D
D为稀疏变换矩阵，通常也被称作过完备字典（Overcomplete Dictionary)，
d
k
d_k
dk为字典中的原子。
1.2.2 小块图像的稀疏模型
图像的稀疏分解对于维数较小的字典更有利于分解。
考虑图像
X
X
X(总像素点数个数为
N
N
N)中的分块
μ
\mu
μ,大小为
n
×
n
\sqrt n\times \sqrt n
n
×n
,
n
≪
N
n\ll N
n≪N,将其排列成列向量
x
⊂
R
n
x\subset R^n
x⊂Rn,假设冗余字典
D
⊂
n
×
K
D\subset {n\times K}
D⊂n×K已知，
K
>
n
K > n
K>n。图像块
x
x
x基于字典
D
D
D的稀疏表示模型为：
α
^
=
a
r
g
m
i
n
α
∥
α
∥
0
s
.
t
.
D
α
=
x
(3)
\hat{\alpha}=arg min_\alpha \parallel\alpha\parallel_0 s.t. D\alpha=x\tag{3}
α^=argminα∥α∥0s.t.Dα=x(3)
其中，
∥
α
∥
0
\parallel\alpha\parallel_0
∥α∥0为向量
α
\alpha
α的非0元素个数。
上述模型计算较为复杂，为了简化该模型，使之能更方便的计算，采用误差约束
∥
D
α
−
x
∥
2
2
≤
ϵ
\parallel D\alpha-x\parallel _2^2 \leq \epsilon
∥Dα−x∥22≤ϵ替换
D
α
=
x
D\alpha=x
Dα=x，同时定义稀疏度为
L
L
L，使得
∥
α
^
∥
≤
L
≤
n
\parallel \hat{\alpha}\parallel \leq L \leq n
∥α^∥≤L≤n。于是(3)可以转换为：
α
^
=
a
r
g
m
i
n
α
∥
α
∥
0
s
.
t
.
∥
D
α
−
x
∥
≤
T
(4)
\hat{\alpha}=arg min_\alpha \parallel\alpha\parallel_0 s.t. \parallel D\alpha-x\parallel \leq T\tag{4}
α^=argminα∥α∥0s.t.∥Dα−x∥≤T(4)
其中
T
T
T的取值取决于
ϵ
\epsilon
ϵ与高斯白噪声标准差
σ
\sigma
σ，去噪后的块图像表达式为：
x
^
=
D
α
^
(5)
\hat{x}=D\hat{\alpha}\tag{5}
x^=Dα^(5)
将(4)的约束项转换为惩罚项，可以得到模型：
α
^
=
a
r
g
m
i
n
α
∥
D
α
−
x
∥
2
2
+
μ
∥
α
∥
0
(6)
\hat{\alpha}=argmin_\alpha\parallel D\alpha-x\parallel _2^2+\mu\parallel \alpha\parallel _0\tag{6}
α^=argminα∥Dα−x∥22+μ∥α∥0(6)
其中，
μ
\mu
μ称为惩罚因子。
1.2.3 整体图像的稀疏模型
对一幅大小为
N
×
N
\sqrt N\times \sqrt N
N
×N
的整体图像
X
X
X，假设上述稀疏模型适用于图像中所有图像块。假定
R
i
j
R_{ij}
Rij是提取图像分块的矩阵，那么
R
i
j
X
R_{ij}X
RijX则表示与图像分块矩阵相对应的图像块。于是整体图像的稀疏表示模型为：
α
i
j
^
,
X
^
=
a
r
g
m
i
n
α
i
j
,
X
λ
∥
X
−
Y
∥
2
2
+
∑
i
,
j
μ
i
j
∥
α
i
j
∥
0
+
∑
i
,
j
∥
D
α
i
j
−
R
i
j
X
∥
2
2
(7)
{\hat{\alpha_{ij}},\hat{X}}=argmin_{\alpha_{ij},X}\lambda\parallel X-Y\parallel_2^2+\sum_{i,j}\mu_{ij}\parallel \alpha_{ij}\parallel _0+\sum_{i,j}\parallel D\alpha_{ij}-R_{ij}X \parallel _2^2 \tag{7}
αij^,X^=argminαij,Xλ∥X−Y∥22+i,j∑μij∥αij∥0+i,j∑∥Dαij−RijX∥22(7)
上式中，
λ
∥
X
−
Y
∥
2
2
\lambda\parallel X-Y\parallel_2^2
λ∥X−Y∥22表明含噪图像Y和去噪图像X之间的相似程度；第二项表示稀疏性约束；第三项表示重建误差约束，
R
i
j
X
R_{ij}X
RijX表示图像块，
D
α
i
j
D\alpha_{ij}
Dαij表示重构后的图像块。
1.2.4 基于字典学习的图像稀疏去噪模型
若式（7）图像稀疏去噪模型中字典
D
D
D是不确定字典而非固定型字典，因此加入字典学习后的图像稀疏去噪模型可以表述为：
α
i
j
^
,
D
^
,
X
^
=
a
r
g
m
i
n
D
,
α
i
j
,
X
(
λ
∥
X
−
Y
∥
2
2
+
∑
i
,
j
μ
i
j
∥
α
i
j
∥
0
+
∑
i
,
j
∥
D
α
i
j
−
R
i
j
X
∥
2
2
)
(8)
{\hat{\alpha_{ij}},\hat{D},\hat{X}}=argmin_{D,\alpha_{ij},X}(\lambda\parallel X-Y\parallel_2^2+\sum_{i,j}\mu_{ij}\parallel \alpha_{ij}\parallel _0+\sum_{i,j}\parallel D\alpha_{ij}-R_{ij}X \parallel _2^2) \tag{8}
αij^,D^,X^=argminD,αij,X(λ∥X−Y∥22+i,j∑μij∥αij∥0+i,j∑∥Dαij−RijX∥22)(8)
2 稀疏分解算法
2.1 松弛优化算法
1.目的是得到原组合优化问题的解，通常利用凸的
l
1
l_1
l1范数来代替非凸的
l
0
l_0
l0范数，然后通过求解凸规划或非线性规划问题得到非凸组合优化问题的解。
2.松弛优化算法计算精度高，但运算速度慢。
3.松弛优化算法包括：基追踪算法（Basic Pursuit,BP)、最小全变差法（Toatal Variation，TV)
BP算法
1.对于过完备稀疏表示模型，由于
l
0
l_0
l0范数是非凸的，所以求解唯一解是一个NP-hard问题。
2.BP算法用
l
1
l_1
l1范数替换
l
0
l_0
l0范数，通过求解凸优化问题得到原组合优化问题的解。
3.算法计算复杂度高，运算速度慢。
2.2 贪婪追踪算法
1.贪婪追踪算法在每次迭代中从过完备字典中选择合适的原子，通过选择出来的原子对原始信号进行逼近。
2.具有代表性的有匹配追踪算法（Matching Pursuit, MP),正交匹配追踪（Orthogonal Matching Pursuit,OMP),最优正交匹配追踪(Optimized Orthogonal Matching Pursuit,OOMP),稀疏自适应匹配追踪(Sparsity Adaptive Matching Pursuit, SAMP)。
3.贪婪追踪算法相比于松弛优化算法，具有算法复杂度低，运算速度快的特点，但运算精度没有松弛优化算法高。
2.2.1 匹配追踪/MP算法
1.1993年Mallat和Zhang最早提出了匹配追踪算法。
2.该算法首先稀疏逼近一个过完备原子库
D
D
D中与信号
v
v
v最匹配的原子，并计算信号的残差，然后反复迭代求解与残差最匹配的原子。信号
v
v
v就可以通过这些原子的线性组合来表示。
3.MP算法具有收敛性，在每次迭代后，残差会越来越小。
4.缺点是迭代结果不是最优解，算法收敛需要较多的迭代次数(因为残差与之前的原子不正交，有可能投影到之前选择的原子上）。
2.2.2 正交匹配追踪/OMP算法
基于MP算法进行改进：OMP算法在进行信号稀疏分解时会对之前投影过的原子进行正交化处理，从而克服了MP算法的缺点。
3 过完备字典设计
3.1 固定字典
1.实现容易，收敛速度快。
2.固定字典包括：离散余弦变换（DCT)字典，Gabor字典，小波变换字典等。
3.2 学习型字典
1.训练出具有针对性的稀疏字典。
2.处理时间长；每次训练完字典重构出图像后，字典需要重新训练。
3.2.1 最优方向法（Method of Optimal Directions,MOD)
1.1999年Engan提出。
2.为了找到字典
D
D
D和稀疏系数
a
a
a,使两者之间的表达误差最小。
3.2.2 K-奇异值分解（K-SVD)
1.该算法逐个更新字典原子，避免运算量大的矩阵求逆运算。
2.与MOD步骤类似，同样可分为稀疏分解和字典更新两大步骤，在字典原子更新中，采用了SVD。
[1]:程一峰. 基于稀疏表示理论的图像去噪算法研究[D]. 昆明理工大学, 2017.