# 前言

给自己叠甲，说是浅析，实际自己也是个一知半解，有错误希望指出

# 图形超分辨率

开始前提个问题，你觉得一张$512×512$ 的图片放大成$1024×1024$ 是长啥样的？

512×512

1024×1024

就像上面看到的，应该放大后依旧能清晰的看到图像的细节，实际上这就是超分辨率技术的应用，如果没应用这项技术，实际应该是下面这张图。

1024×1024

图像放大后，放大的部分存在没有像素值的位置，需要你去猜相似的像素值填充进去，保持你对原有图像的观感。 所以在我理解下的图形超分辨率的定义就是当图像被扩展成不同于原图像分辨率的情况下，仍能通过某种手段还原图像缺失的像素值的一种手段。

# 稀疏表示

稀疏表示的定义是一个一维信号可以表示为一个过完备字典和一个一维稀疏系数的线性表达。公式如下。

$$x = D\alpha$$

$x$ 是一个一维信号，$D$ 是一个过完备矩阵，$\alpha$ 是一个大多数目为零的稀疏系数。更多详情可以看大佬的文章图像的稀疏表示（Sparse Representation）。

# 稀疏矩阵求解

这里稀疏矩阵的求解我用的是正交匹配追踪算法 (OMP)，算法介绍如下。

输入： $M * N$ 的二维信号 $Y$， $M*K$ 的字典矩阵 $D$，稀疏度 $k$.

输出： $K*N$ 的稀疏矩阵$X$.

1. 初始化稀疏矩阵 $X=0$，额外保存归一化的字典矩阵 $D_{norm}$.
2. 对二维信号的每一列信号 $y_i$ 循环 3~8 步骤.
3. 初始化残差 $r=y_i$, 索引 $I=\oslash$，迭代次数 $t=1$.
4. 找到残差与归一化的字典矩阵的列 $dn_j$ 内积最大值 $j = argmax_{1,2...k}(r^T\cdot dn_j)$.
5. 更新索引 $I=I\cup j$，重建原子集合 $A_{new}=[D_{I\ne 0}]$.
6. 最小二乘法求解稀疏信号 $x_i=argmin||y_i-A_{new}x_i||=(A_{new}^TA_{new})^{-1}A_{new}^Ty_i$.
7. $t=t+1$.
8. 如果 $t < k$，循环 4~7 步骤，否则跳出循环.

# 字典求解

这里字典求解我用的是 KSVD 算法，算法介绍如下。

输入： $M * N $ 的二维信号 $Y$， $M * K $ 的字典矩阵 $D$，$K*N$ 的稀疏矩阵 $X$，稀疏度 $k$.

输出： $M * K$ 的字典矩阵 $D$， $K * N $ 的稀疏矩阵 $X$.

1. 初始化字典矩阵 $D$ 并使用 $L_2$ 范数每列归一化.
2. 对二维信号 $Y$ 通过 OMP 算法求解稀疏系数 $X=argmin(Y-DX)$.
3. 对字典矩阵的每一列原子 $d_j$，循环执行步骤 4~6.
4. 找到原子 $d_j$ 对应行稀疏系数非零项索引$w_j = \left \{ i|1\le i \le N, x_j\ne 0\right \}$.
5. 按照稀疏系数非零项索引 $w_j$ 构建新的稀疏系数 $x_j'$ 和信号矩阵 $y_j'$，并计算残差 $E_k=y_j'-d_jx_j'$.
6. 对残差进行奇异值 SVD 分解 $E_k=U\Delta V^T$，其中更新的原子 $\tilde{d_j}=U(1,0)$，更新后的稀疏系数 $\tilde{x_j'}=V(1,0)\Delta(1,1)$.

# 图像的稀疏表示

对于图像而言，图像是二维信号，而稀疏表示的要求是一维信号，所以需要近似表达，我使用的图像分块方法，把图像的每块表达成一维列向量，逐列进行过完备字典和稀疏矩阵的求解，可惜最终实验效果不是很理想。

原图

还原图

# 总结

一次失败的基于稀疏表示的图形超分辨率研究，或许是我压根就没整明白过吧，于此纪录一次失败的经历。我最终效果展示的代码仓库 KSVD-and-OMP，虽然渣的一批。

# 参考

图像的稀疏表示（Sparse Representation）
K-SVD 代码及效果
正交匹配追踪
字典学习（Dictionary Learning, KSVD）详解
kSVD-Image-Denoising
KSVD