算法首先对图像进行分块并进行相似块的聚类，再利用相似块之间的稀疏性或者低秩性 进行重构或降噪，通常会获得更好的效果。有很多评估块之间相似度的函数，通常使用的是 欧式距离，即计算块与块之间矩阵形式表示的像素值的差距，差距越小的块越相似，这看起 来是很合理的，但如果对于所有的分块两两都要为了减少计算量，算法的计算量会相当大， 因此不会计算所有分块之间的欧式距离，对于一个样本块，通常只计算以其为中心周围固定 的大小范围内的图像块之间的相似度，这个相似块的搜索范围叫做窗口。分块之后再对这些 分好的块进行分类，将近似的块放入同一类中，通常使用的分类算法有：自组织映射方法[15]、 K-means方法[16]、模糊聚类法[17]等等，但是使用这些分类的算法产生的相似块的集合是没有交 集的。本文介绍的算法使用了欧式距离来衡量相似块之间的相似度并使用k-邻近算法作为聚 类算法。

在基于非局部相似性算法设计中应该注意以下几个参数的选择： 1）相似块的总个数：相似块的总个数直接影响着图像块之间稀疏性的表达，设想如果

在分块时相似块的数目很少，则块与块之间的相似性必然没有得到充分的表达。但如果相似 块分割得太小，则会导致在计算块间相似度时计算量增大。

2）窗口的大小：为了减少计算量，对于同一个窗口里的相似块通常不会进行两两之间的 相似度评估，而是在选择一些样本块，在以这些样本块为中心的窗口内对样本块与其他分块 的相似度进行计算。由此可见，如果窗口选择过大，不仅会增加算法的计算复杂度而且增加 算法性能的几率很小，因为超出某个范围后出现相似块的几率也会变小，同理，如果窗口的 选择过小，则有可能没有对潜在的相似性进行充分的挖掘。文献综述

3）样本块的个数：在上面提到了会选择一些样本块为中心，样本块的个数和相似块组的 个数是一样的，如果样本块个数过多，则会增加算法的计算复杂度，虽然图像重构的质量会 增加，但如果样本块的个数较少，则会导致图像的自相似性得不到很好的表达，降低算法的 有效性。

3。2 图像重构中的非局部低秩正则化

前面提到了可以使用 l1 -范数作为原目标函数 l0 -范数的凸松弛替代函数，问题（2。3）的 目标函数是凸的，并且是一个等式约束最优化问题，因此可以使用拉格朗日定理选择一个合 适的参数 将问题（2。3）转化为无约束优化问题：

问题（3。1）可以通过很多方法解决，包括迭代收缩算法[17]、Bregman分割法[18]和迭代方

向乘子法[19]等等。最近的研究表明，使用非凸的 l  (0 p 1) 作为目标函数可以获得更好的重

构效果，虽然计算复杂度会增加。有些重构算法会加入非局部相似性作为先验知识，因为自 然图像中常常有结构相似的部分，很多非局部算法都利用这种图像的这种自相似性。本文介 绍了一种基于非局部相似模型的重构算法，并实验证明了该算法相比于其他主流算法在视觉 和PSNR指标上都有更好的重构效果。

该算法是基于自然图像中自相似性充足的前提下的，首先对初始图像进行分块和相似块 的聚类。算法主要包括对相似块的矩阵表达形式的低秩近似和利用交替方向乘子法对图像进

行恢复两个部分。算法首先是对图像进行分块，每个分块的大小 

，分块之间可以重

合，则可以用向量 xˆi   C

来表示每一个分块，其中的每个分量代表着样例块中一个像素点的