1. Abstract

Image Super-Resolution Via Sparse Representation
J Yang et al. IEEE TIP 2010

西瓜书11.6
https://blog.csdn.net/weixin_40117184/article/details/80415224

  ScSR的理论基础来源于compressed sensing, 就是从降采样的信号(低于Nyquist采样频率)还原出原始信号

compressed sensing

  A是感知矩阵(或者叫退化模型), D为高维数据的over-complete dictionary D_h , α为高维数据在字典D情况下的系数向量, 可以把A*D看作是退化数据的over-complete dictionary D_l, 这样, 只要求出了退化数据(LR)在字典D_l下的稀疏表示向量α , 我们就可以通过x=D_h∗α还原出原始的信号

  这个理论就是ScSR最关键的先验(Prior), 尽管LR图像存在退化降质, 但是HR与其对应的LR图像的几何结构, 或者说稀疏表示是近似的, 我们可以这么理解, 用积木拼一个房子, LR是用纯色块积木拼成的, HR是用带图案的积木拼成的, 当然HR细节更丰富, 但是拼成一个房子我们都用了一样的结构, 这里的积木块就相当于字典的atom, Dl和Dh是不同的, 但是用积木块搭起的结构(稀疏表示向量α)是一样的

2. Sparse Representation

西瓜书11章
http://www.cnblogs.com/daniel-D/p/3222576.html

  稀疏表达(sparse representation)与特征选择相关, 我们把数据集D考虑成一个矩阵, 其每列对应着一个样本, 每一行对应一个特征(这里跟西瓜书稍有不同, 是为了跟下面那张图对上), 特征选择考虑的问题是特征具有稀疏性, 即矩阵中的许多行和当前学习任务无关, 可以直接去除这些行。

  而sparse representation考虑的是另一种稀疏性, D所对应的矩阵中存在很多零元素, 但这些零元素并不是以整列、整行的形式存在的, 一个形象的例子就是汉语的表达, 《康熙字典》有47035个汉字, 意味着矩阵有4w多行, 即便是考虑《现代汉语常用字典》中的汉字, 该矩阵也有3500行, 然而给一个特定的文档, 大部分的字是不会出现在这个文档中的, 也就是说矩阵的每一行都有大量零元素, 但是不同的文档(不同的列), 零元素出现的位置往往很不相同, 这就是表达的稀疏性

  在一般的学习任务中, 并不存在现成的《现代汉语常用字典》, 需要学习出这样一个"字典", 为普通稠密表达的样本找到合适的字典, 将样本转化为合适的稀疏表达形式, 从而简化学习任务, 模型复杂度降低, 通常称为"字典学习"(dictionary learning), 也叫"稀疏编码"(sparse coding)

  给定数据集{x₁, x₂,…,x_m}, 字典学习最简单的形式是

稀疏字典学习优化函数

  B∈R^(d×k) 为字典矩阵
  k称为字典的词汇量, 通常由用户指定
  α_i∈R^k 是样本x_i∈∈R^d 的稀疏表示
  上面这个式子的第一项是希望由α_i能很好的重构x_i, 第二项是希望α_i∈ 尽量稀疏, 在字典学习过程中, 用户可以通过设置词汇量k的大小来控制字典规模, 影响稀疏程度

  用于图像的SC(Sparse Coding), 可以用下图来表示

sparse coding示意

  一张8x8的image, 可以表示成64维(N)的向量x
  左边矩阵D是字典矩阵, 由K个N维向量组成, 根据K与N的关系, 又可以划分为

• K>N: over-complete, 这种情况在稀疏表示中最常见
• K=N: complete, 例如傅立叶变换和DCT变换都是这种情况
• K<N: under-complete
    中间列向量α是一个稀疏向量, 特点是非零项很少, 代表D矩阵对应行向量的线性组合
    最后x向量表示恢复后的向量
    atoms表示D的列向量
    实际DCT也可以看作是一种稀疏表示, 它的D向量是由固定的且刚好完备的正交基向量组成, 并且α向量也具有一定稀疏性

Sparse Coding

现有字典D和带噪声的信号y, 进行稀疏编码的问题可以表示为L0优化问题

sparse coding l0 normal

  这是一个组合优化问题, 假设α的非零项数为L(sparse level), 先令L=1, 每一个列向量尝试一遍, 看看是否有满足条件的, 共有K中组合。如果没有, 再令L=2, 再尝试, 共有K(K-1)/2种组合。还没有满足条件的, 令L=3……, 组合的数目呈指数增长, 这是一个NP-hard问题(多项式时间可以验证解的正确性, 但是多项式的时间不一定能求解问题本身)。实际应用中K=1000, L=10, 要穷尽所有的排列组合需要百万年, 要采用近似算法, 主要有relaxation methods和greedy methods

• Relaxation Methods - the Basis Pursuit(BP)
    L0 norm 可以数出向量中非零entries数目, 但是L0 norm不可导, 不适合作为一个优化模型中的目标函数, 所以我们采用松弛方法将L0 norm转换为L1 norm:
  
  sparse coding l1 normal

  虽然我们把count number变成了count the magnitude, 但是在某些条件下, 上式的解与松弛前的解等价, 这个方法叫BP, 新定义的问题是一个凸优化问题, 解决方法很多, 有Interior Point methods, Sequential shrinkage for union of ortho-bases, Iterative shrinkage等

• Greedy Methods - Matching Pursut(MP)
    第一步, 找到最接近(平行)y的atom, 等效与在alpha向量上仅取一个非零项, 求出最接近的atom, 保留下来
    第二步, 计算误差是否满足要求, 如果满足, 算法停止, 否则, 计算出残差信号, 和第一步类似, 找到最接近残差向量的atom, 保留下来
    第三步, 调整已选向量的系数, 使得Da最接近y, 重复第二步(OMP, Orthogonal Matching Pursuit)

  总结一下解决这个问题的算法有

解决sparse coding优化问题的方法

Dictionary Learning

  下面简单介绍一下怎么来解字典学习的问题
  现在有P个信号(张图片)要进行稀疏表示, 如何学习一个字典D

Dictionary Learning优化公式

  上式字典矩阵D和α组成的稀疏表示A矩阵都是可变量, 解决这个问题的常用方法是K-SVD(K-Means的一种变种)

K-SVD

  假设现在有原始信号x^T, 该矩阵的每一行表示一张图, D是字典矩阵, 右下方是sparse coding矩阵, 红色点表示非零项

  算法步骤:

• Step 1: Initialize, 在x^T 矩阵中随机挑选一些行向量, 填满矩阵D(K-Means随机选点初始化)
• Step 2: Sparse Coding, 用上一节的方法进行稀疏编码, Row-by-Row 计算出稀疏矩阵
• Step 3: Dictionary Update, 字典以列向量为基, 自然要column-column地更新字典, 比如现在更新某一列, 下方对应的红点, 根据红点找到对应图像, 然后除掉其他不相关的图像, 得到示意图如下
  
  k-svd 算法

  上图中字典的atom对四张图都有贡献, 我们调整atom的目的是使这个贡献更大, 从而使稀疏性表示效果更好。一个atom只能表示一条直线,三张图的信号极有可能不在这条直线上, 我们要做的是将中间的误差降到最小, 这就是一个MSE问题, 具体做法是将最右下角的矩阵进行SVD分解, 找出主成分, 然后回到step2, iteration

3. Algorithm

  理解了ScSR的理论基础和物理意义, 我们来看一下算法实现过程

  整体的算法结构
https://zhuanlan.zhihu.com/p/38181216
https://blog.csdn.net/jiangjieqazwsx/article/details/50414259

ScSR整体架构

  ScSR的操作过程分成了四个部分
https://blog.csdn.net/weixin_40117184/article/details/80415224

• ①字典对训练(Joint Dictionary Training)
    对于给定的高分辨率图像X_h, 首先对其进行退化操作得到低分辨率图像X_l, 而对X_h/X_l分别切块并化矩阵为向量, F为高通滤波算子, 可以视作线性映射(ScSR论文中提到了F is a linear feature extraction operator)

Joint Dictionary Training

• ②求解稀疏表达α(Sparse representation)
    上一步通过联合训练, HR/LR图像已经求得, 根据compressed sensing理论可知: 当LR图像在字典D_l下的系数向量α已知, 便可以顺利求出相应的HR图像

sparse representation

  怎么去求Sparse representation这个是个通用方法, 可以去看一下西瓜书11.6
  这里面有两个trick
  首先, F(feature extraction operator)的引入, 这个F对LR图像的作用我不是特别理解, 在paper中给出的解释是
  we use a feature transformation F to ensure that the computed coefficients fit the most relevant part of the low resolution signal, and hence have a more accurate prediction for the high resolution image patch reconstruction
  F是一个高通滤波器, 是希望去除掉LR图像中与重建关系不大的低频成分
  还有一个trick就是考虑相邻图块的兼容性, 而不是让各图块完全独立的去求解稀疏表达
  在图块scan的过程中, 假设左边图块已经求出稀疏表达稀疏α, 并且通过α和Dh已经重建出了HR图块ω， 为了考虑相邻图块的兼容性, 在原来的目标函数上加了一项就是叠加部分(红色)对应Dl字典的稀疏表达再通过已经求出的Dh还原回去的时候要和已经重建出的ω尽量像

ScSR相邻图块兼容性

• ③重建HR图块(HR image patch reconstruction)
    根据求得的HR图像的字典Dh已经LR图像的系数向量α, 可以很方便求出这个LR patch对应的HR patch

HR image patch reconstruction

• ④重建约束(Enforcing global reconstruction constraint)
    重建出来的图像是把一块块重建HR patch拼起来的, 这或许是HR图像, 但是也有可能会出现重建过度或是重建不足等异常现象, 因此对重建出来的X0加上全局约束

Enforing global reconstuction constraint

  X是最终的重建HR结果, 这个的意义就是说你不只要在局部上满足我之前提出来的compressed sensing先验, 同时还要满足退化模型的先验, 就是

退化模型, H-blur, S->downsample

  The observed low-resolution image Y is a blurred and downsampled version of the high resolution image X

4. Discussion

4.1 paper的意义

  ScSR应该是SR领域在前DL时代最有影响力的一篇paper, 在DL时代, 仍然有很多新算法拿它作为state-of-art比较对象, ScSR也是最接近DL思想的, 提取LR和HR的共同特征, 但是Sparse Coding只能是线性过程, 所以它提取的特征的level是比较低的

4.2 paper的优点

  其实研究SR, 大家的出发点都是一样的, SR本身是一个ill-posed问题, 大家都是通过不同的prior去regularize这个问题, 之前有soft edge, 还有neighbor embedding, primal sketch, 但是ScSR显然是找到了更好的prior去限定这个ill-posed问题, 就是相似的图像具有相似的结构, 这个相似的结构可以通过稀疏表达来体现, 它的优点应该前向去比同时代其他的SR算法

4.3 paper的缺点

  Compute cost方面的问题在paper中并没有提及, 但是关键有两个优化过程(求解sparse representation和global constraint), 而且L1 Norm没有解析解(L2 Norm有, 这就是为什么ANR可以直接在训练阶段就求出LR->HR的映射矩阵), 所以ScSR每次都要迭代去算LR representation, 这个cost就低不了
  还有就是过程比较复杂, 先验的知识比较多, 比如F应该选什么样的滤波器, scan的时候overlap应该设多大等等, 过程不够简练, 所以不太像一个优秀的算法, 很多的trick应该都是在基础理论上通过实验得到的, 相当于有很多补丁, 这证明这个算法并没有到理想的状态

https://blog.csdn.net/walilk/article/details/78175912

  Sparse Coding在实际使用过程中速度很慢, 这是因为即使我们在训练阶段把输入数据集的超完备基学到了, 在测试阶段还是要通过凸优化的方法去求其特征值, 所以这要比一般的前馈网络速度慢