Paper——Image Super-Resolution as Sparse Representation of Raw Image Patches

这次阅读一篇关于超分辨的论文。这篇文章的作者里有马毅老师，他是伯克利的老师，也是TBSI的老师，是非常有威望的一名学者。这篇文章在超分辨领域是比较经典的文章了。

超分辨（super resolution，简称SR）的问题，是从比较低的分辨率的图片中，得到高分辨率的图片。这个问题在本篇文章之前也有比较多的解决方法，它们大多数有着自己的缺陷，比如需要多张低分辨图，对于基于学习的方法，一般需要非常大的数据库来进行学习，也有一些学者提出了利用高分辨与低分辨在流形空间上的相似度来解决，但是容易因为overfitting或者underfitting会带来模糊。本篇文章主要解决的是从一张单一的低分辨图得到高分辨图，仅需要少量的训练数据来达到这样的效果，而且训练数据中也不需要在高分辨率的图片上进行学习，而是直接在低分辨率训练patch上工作。这篇文章主要是收到了稀疏信号代表的启发，关于稀疏信号代表的研究保证了高分辨与低分辨之间的线性关系，使得高分辨率的信号可以准确的从它们的低纬度投影恢复出来。

这里简单介绍一下稀疏代表（sparse representation）以及字典的含义。实际上，字典是一个矩阵D∈Rn×K$\mathit{D}\in {\mathbb{R}}^{n\times K}$，它由K$K$个原型信号原子(prototype signal-atoms)组成，每个原子实际上是一个n$n$维向量，一个完备（complete）的字典意思是任何一个信号x∈Rn$x\in {\mathbb{R}}^n$可以由这些原子线性组合得到，过完备也就意味着，这样的组合可能不止一个。其实放到线性代数中，我觉得可以这样理解，一个字典就是n维向量空间的一组基。因此，每个信号向量x$x$都可以写为：

x=Dα0$$\mathit{x}=\mathit{D}{\mathit{\alpha }}_0$$

其中，α0∈RK${\mathit{\alpha }}_0\in {\mathbb{R}}^K$是一个稀疏的系数向量，只有少量的元素（≪K$\ll K$）非0，因为这个字典是过完备的。在实际中，我们可能只观察到x$x$的一个小集合测量值y$y$:

y≐Lx=LDα0$$\mathit{y}\doteq L\mathit{x}=L\mathit{D}{\mathit{\alpha }}_0$$

上式中L∈Rk×n$L\in {\mathbb{R}}^{k\times n}$，k<n$k<n$。在超分辨问题中，高分辨率的图像就是x$x$，而低分辨率图像则是y$y$。如果这个字典D$\mathbf{D}$是过完备的，那么等式x=Dα$\mathit{x}=\mathit{D}\mathit{\alpha }$是一个欠定方程，有无数多组α$\mathit{\alpha }$的解，对于等式y=LDα$\mathit{y}=L\mathit{D}\mathit{\alpha }$也是一样。尽管如此，在弱假设（mild condition）下，对于这个等式最稀疏的解α0${\mathit{\alpha }}_{\mathbf{0}}$也是唯一的。此外，如果D$\mathit{D}$满足一个合适的near-isometry条件，那么对一个高分辨率图像x$\mathit{x}$的任何足够稀疏的线性代表都可以完美的从低分辨率图像中恢复出来。下面的图是一个超分辨的例子：

实际上稀疏代表已经应用到图像处理的各个方向，比如图像压缩，图像去噪以及图像恢复。在这篇论文中，作者没有直接计算高分辨率patch的字典，而是建立了两个字典，Dℏ$D_{\hslash }$对应于高分辨率patch，而Dℓ=LDℏ${\mathit{D}}_{\ell }=L{\mathit{D}}_{\hslash }$则对应于低分辨率patch。Dℓ${\mathit{D}}_{\ell }$被用来直接从对应的Dℏ$D_{\hslash }$恢复高分辨率patch，因为各个patch之间的overlap，可以得到一个局部一致的解，接着利用全局优化，来得到全局一致的解。注意，这里高分辨率patch的字典只用来进行高分辨率path的恢复，而且算法会自动选择最相关的patch，因此相对于其他的算法，这个算法有更好的表现。

下面介绍下算法的推导。

Super-resolution from Sparsity

这部分简单介绍一下从系数得到超分辨的模型。现在有一个低分辨图Y$\mathbf{Y}$，超分辨问题就是用这张图恢复相同场景下的高分辨图X$\mathbf{X}$。X$\mathbf{X}$与Y$\mathbf{Y}$之间最基本的约束是需要保持consistent。观察的Y$\mathbf{Y}$是原先的高分辨率图的一个模糊加下采样的结果：

Y=DHX$$\mathit{Y}=DH\mathit{X}$$

在这里,H$H$是一个模糊滤波器，D$D$表示下采样操作。对于低分辨率Y$Y$，实际上可以有无数的高分辨率图像在模糊与下采样之后得到Y$Y$，因此作者通过对X$X$上的小区域（patch）x$\mathit{x}$的先验来重新整理这个问题：稀疏代表先验。解释如下：
对于高分辨率图片X$X$的patchx$\mathit{x}$可以表示成字典Dℏ$D_{\hslash }$中向量的稀疏线性组合，字典Dℏ$D_{\hslash }$是通过对训练集中的高分辨patch采样得到的：

x≈Dℏα for some α∈RK with ∥α∥0≪K$$\mathit{x}\approx {\mathit{D}}_{\hslash }\mathit{\alpha }\text{ for some }\mathit{\alpha }\in {\mathbb{R}}^K\text{ with }\Vert \mathit{\alpha }{\Vert }_0\ll K$$

为了使用稀疏代表的先验来解决超分辨问题，作者将问题分成了两个步骤来解决：

1. 使用稀疏先验，找到每个局部patch的稀疏代表，并且要考虑到相邻patch的关系。
2. 根据上面的到的稀疏代表，来利用重建约束来对整个图片进行改进。

Local Model from Sparse Representation

这一部分讲得到局部稀疏代表的过程。首先，我们要建立字典，前面提到的字典有两种：高分辨率的字典以及对应的低分辨率的字典。假设我们已经得到了低分辨率字典。Dℓ${\mathit{D}}_{\ell }$，那么关于低分辨率patch的最稀疏的代表定义如下：

min∥α∥0 s.t. ∥FDℓα−Fy∥22≤ϵ$$min\Vert \mathit{\alpha }{\Vert }_0\text{ s.t. }{\Vert F{\mathit{D}}_{\ell }\mathit{\alpha }-F\mathit{y}\Vert }_2^2\le ϵ$$

这里的F$F$表示特征提取，它的作用会在之后说明。尽管上述问题的解决是NP-hard，是对0范数的求解。但是最近的结果显示了只要α$\alpha$是足够稀疏的，那么它们可以通过解决1范数来近似，因此优化问题变成了下面的形式：

min∥α∥1 s.t. ∥FDℓα−Fy∥22≤ϵ$$min\Vert \mathit{\alpha }{\Vert }_1\text{ s.t. }{\Vert F{\mathit{D}}_{\ell }\mathit{\alpha }-F\mathit{y}\Vert }_2^2\le ϵ$$

使用拉格朗日乘数方法可以构造一个等价的式子：

minλ∥α∥1+12∥FDℓα−Fy∥22$$min\lambda \Vert \mathit{\alpha }{\Vert }_1+\frac{1}{2}{\Vert F{\mathit{D}}_{\ell \mathit{\alpha }}-F\mathit{y}\Vert }_2^2$$

但是对每个patch单独解决上述的式子得到的结果不能保证相邻patch之间的兼容性，因此我们还需要别的约束，加上之后这个优化问题变成了：

min∥α∥1 s.t. ∥PDℏα−w∥22≤ϵ2∥FDℓα−Fy∥22≤ϵ1$$\begin{array}{rl}min\Vert \mathit{\alpha }{\Vert }_1\text{ s.t. }& {\Vert F{\mathit{D}}_{\ell }\mathit{\alpha }-F\mathit{y}\Vert }_2^2\le {ϵ}_1\\ {\Vert P{\mathit{D}}_{\hslash }\mathit{\alpha }-\mathit{w}\Vert }_2^2\le {ϵ}_2\end{array}$$

这里的P$P$提取了当前目标patch与之前重建的高分辨率图像之间的重接区域，而w$\mathit{w}$包含了之前重建的高分辨率图片中重叠区域的值。这个优化问题可以被简化写成成下面的形式：

minλ∥α∥1+12∥D~α−y~∥22$$min\lambda \Vert \mathit{\alpha }{\Vert }_1+\frac{1}{2}\Vert \tilde{\mathit{D}}\mathit{\alpha }-\tilde{\mathit{y}}{\Vert }_2^2$$

上式中：

D~=[FDℓβPDh] and y~=[Fyβw]$$\tilde{D}=\left[\begin{array}{c}F{\mathit{D}}_{\ell }\\ \beta P{\mathit{D}}_h\end{array}\right]\text{ and }\tilde{\mathit{y}}=\left[\begin{array}{c}F\mathit{y}\\ \beta \mathit{w}\end{array}\right]$$

这里β$\beta$是一个参数，用来调整兼容性与对应之间的tradeoff，可以简单设为1。利用上式求得α∗${\mathit{\alpha }}^{\ast }$，那么高分辨率patch可以通过下式得到：

x=Dℏα∗.$$\mathit{x}={\mathit{D}}_{\hslash }{\mathit{\alpha }}^{\ast }.$$

Enforcing Global Reconstruction Constraint

需要注意的是，在上面的推导中，我们不要求|FDℓα−Fy|2=0${\left|F{\mathit{D}}_{\ell }\mathit{\alpha }-F\mathit{y}\right|}_2=0$，再加上noise的存在，使得最后得到的结果不一定会满足全局的约束，也就是从得到的高分辨率图片X0$X_0$经过模糊下采样之后，不一定能得到Y$Y$。为了使得结果满足全局一致，我们投影X0$X_0$到DHX=Y$DH\mathit{X}=\mathit{Y}$的解空间，计算：

X∗=argminX∥X−X0∥ s.t. DHX=Y$${\mathit{X}}^{\ast }=\arg \underset{\mathit{X}}{min}\Vert \mathit{X}-{\mathit{X}}_0\Vert \text{ s.t. }DH\mathit{X}=\mathit{Y}$$

可以通过back-projection方法迭代来解决上面的问题，更新等式如下：

Xt+1=Xt+((Y−DHXt)↑s)∗p$${\mathit{X}}_{t+1}={\mathit{X}}_t+\left(\left(\mathit{Y}-DH{\mathit{X}}_t\right)\uparrow s\right)\ast p$$

这里的p$p$是一个back-projection滤波器，而↑s$\uparrow s$表示因子s$s$下的上采样。

到目前为止，整个算法流程如下：

我们将X∗${\mathit{X}}^{\ast }$作为最后对高分辨率图像的估计。这个估计在满足全局约束的条件下尽可能接近最开始估计的X0${\mathit{X}}_0$。

Global Optimization Interpretation

上述中，对于patch各个计算是分开进行的，实际上给定足够多的计算资源，对于所有patch的相关联系是可以同时计算的。此外，整个高分辨率图像本身可以作为一个变量，因此与其要求X$X$通过稀疏代表系数α$\alpha$被完美地恢复，我们可以将高分辨率图像与这些系数的差异作为一个惩罚项。通过这些细数得到的高分辨率图像，允许这个解不是完全稀疏的，但是会更好的满足重建约束。这样的策略下，对于高分辨率问题的求解成了一个很大的优化问题：

X∗=argminX,{αij}{∥DHX−Y∥22+η∑i,j∥αij∥0+γ∑i,j∥Dℏαij−PijX∥22+τρ(X)}$$\begin{array}{rl}{\mathit{X}}^{\ast }=& \underset{\mathbf{X},\left\{{\mathit{\alpha }}_{ij}\right\}}{\arg min}\left\{\Vert DH\mathit{X}-\mathit{Y}{\Vert }_2^2+\eta \sum _{i,j}{\Vert {\mathit{\alpha }}_{ij}\Vert }_0+\gamma \sum _{i,j}\Vert {\mathit{D}}_{\hslash }{\mathit{\alpha }}_{ij}-P_{ij}\mathit{X}{\Vert }_2^2+\tau \rho (\mathit{X})\right\}\end{array}$$

上式中αij${\mathit{\alpha }}_{ij}$表示X$X$在位置(i,j)$(i,j)$的patch的代表系数，Pi,j$P_{i,j}$是一个投影矩阵用来选择X$X$的第(i,j)$(i,j)$个patch，而ρ(X)$\rho (\mathit{X})$是一个惩罚函数，编码了关于高分辨率的一些先验信息，对于不同种类的图片应该对应不同的ρ$\rho$。实际上，我们之前提出的稀疏代表算法，正是对这个算法的一个计算效率比较高的估计。仔细观察，原来版本的优化问题是在最小化上式的第二项和第三项，将第二项的0范数放宽成了1范数，同时用低分辨率的字典下的稀疏代表来估计高分辨率的版本。同时，当代表系数固定时，实际上：

∑i,j∥Dℏαij−PijX∥22≈∥X0−X∥22$$\sum _{i,j}{\Vert {\mathit{D}}_{\hslash }{\mathit{\alpha }}_{ij}-P_{ij}\mathit{X}\Vert }_2^2\approx {\Vert {\mathit{X}}_0-\mathit{X}\Vert }_2^2$$

因此，对于比较小的γ$\gamma$，之前算法的back-projection步骤正是在最小化全局优化问题中的第一项和第三项。但是我们之前的算法并没有解决第4项，但实际上稀疏代表假设已经是一个足够强的先验信息，让算法能取得比较好的结果。

Dictionary Preparation

分析到现在，可以看到字典在算法中的关键作用。这一部分将说明如何构造出字典。

Random Raw Patches from Training Images

想要学习一个最佳的过完备字典是非常困难的。在这篇文章中，作者没有试着去学习这样一个字典或者使用一个通用的基向量，而是通过对原始训练集（相似的统计数据）中的patch简单进行随机采样。实验中我们发现这样简单的策略，就足够生成高质量的重建结果了。

下图是展示了几张训练用的图片以及从它们中采样得到的patch，在作者给出的实验中，准备了两个字典：一个是对各类型花朵的采样，生成的字典用来恢复相似场景的超分辨率图像，另一个是对动物图片的采样，用来恢复带有毛的纹理表现更好。对于每张高分辨率图像X$\mathbf{X}$，我们通过模糊以及下采样来得到对应的低分辨率图像Y$\mathbf{Y}$。对于某种类型的图片，我们仅仅对30多张训练图片进行随机采样得到100000左右的patch来生成字典。

Derivative Features

在之前Local Model from Sparse Representation中，我们在公式中有一个特征提取的操作F$F$，来确保计算得到的系数能够匹配上低分辨率信号中最相关的部分。典型地来说，F$F$是一些高通滤波器，在感知角度来说这个是合理的，因为人们对图片中的高频内容更敏感。同样的，低分辨率中的高频信息在恢复高分辨率中被丢掉的高频内容的过程中也是最重要的。在本篇文章中，选取的高频滤波是一阶二阶导数，来作为低分辨率patch的特征。尽管这个滤波器很简单，但是却非常有效。更准确的说，4个用来提取导数的1-D滤波器为：

f1=[−1,0,1],f3=[1,0,−2,0,1],f2=fT1f4=fT3$$\begin{array}{ll}{f}_1=[-1,0,1],& f_2=f_1^T\\ f_3=[1,0,-2,0,1],& f_4=f_3^T\end{array}$$

通过应用这些滤波器，对于每个patch我们得到4个描述特征，它们被组织成一个向量，来作为最终低分辨率patch的代表。

到目前为止，整个算法过程就说完了。这个算法的流程如下：

1. 生成patch，通过3×3或者5×5大小的patch，运用一阶二阶导数滤波器，得到一个向量来作为该patch的代表。
2. 对训练集中的高分辨率图，通过模糊以及下采样得到低分辨率图，根据低分辨率图来生成低分辨率的字典，根据高分辨率图来生成高分辨率的字典。生成字典的方式是随机采样得到patch代表，对于每个种类的图片，生成字典大概仅仅需要30张图片以及100000个patch。
3. 根据低分辨率的字典以及低分辨率的输入图像，求解得到每个patch的稀疏代表（一个优化问题，最稀疏），同时根据高分辨率字典来恢复高分辨率的patch，接着，根据全局约束，来不断迭代得到的高分辨率图，直到满足全局约束，最后得到的就是恢复的超分辨图像。

下面是一些实验结果：

可以看到的是，实际上这个算法对于字典的依赖很大，因此如果训练集的图片与输入图片不相关，那么最后得到的超分辨图像也是崩掉的。