稀疏编码(Sparsecoding)在图像检索中的应用

摘要：稀疏编码（Sparse Coding）作为深度学习的一个分支，在机器学习领域取得了多个方面的突破。本文将探索如何将Sparse Coding结合到图像检索的多个模块中，利用Sparse Coding的优点来提高检索的效果。

关键词：图像检索 稀疏编码 深度学习

中图分类号：TP391.41 文献标识码：A 文章编号：1007-9416（2013）11-0076-03

随着互联网图片数量的几何速度增长，大量无标签图片的产生和标签的不准确性，使得基于标签检索图片无法满足要求，基于内容的图像检索成为趋势。近年来，Sparse Coding作为深度学习的一个分支，在多个领域获得较好的效果，尤其是在图像识别和图像处理方面效果显著。本文将探讨如何把Sparse Coding融入到基于内容的图像检索的某些模块中，以获得较好的检索效果，并着重介绍Sparse Coding的背景和将其在图像预处理，特征提取，特征融合模块中融入的方法和意义。

1 图像检索系统流程

目前常见的基于内容的图像检索引擎流程图如图1所示。

该节主要讲述其中的图像预处理，特征提取，特征融合三个部分，这也是本文将稀疏编码的特性融入的模块。

1.1 图像预处理

图像预处理主要作用是去除图片噪声，去除相关性，加强边缘等，以提高后续特征抽取的有效性。常见的图片预处理有白化，高通滤波，低通滤波，高斯去噪等。

1.2 特征提取

特征提取在图像检索中处于核心地位，有效的特征能够表达出一幅图像所描述的某些特定内容。常见的特征有SIFT，SURF，Gabor纹理特征，Gist，颜色直方图，DAISY，ORB，HOG等。

1.3 特征融合

这里的特征融合是针对一种局部特征（描述子）来进行的，当某个描述子在不同图片上抽取出的数目不定时，有必要使得所有的图片具有统一维度的特征向量表达。常见的有效的方式是使用文本挖掘中的词袋（BOW，也称BOF）的思想。

BOW的主要思想：首先对所有图片的所有描述子进行聚类，聚类一般使用KMEAN算法，生成N个类中心，即码本。然后对于某张图片的所有描述子依次按照最近邻思想，将描述子分配到最近的类中心，并对类中心的计数加一。最后，则得到关于描述子投影到类中心的统计直方图，以该直方图作为N维的特征向量表示图片。

2 稀疏编码（Sparse Coding）

稀疏编码在人脸识别，信号去噪，图像重建，超像素，图像分割，图像分类，背景建模方面都有很好的效果。稀疏性被解释为人眼视觉层中的V1层[9]，具备了人眼识别物体的基础特性。这种视觉特性使得其特别适合图像相关的处理和识别。本节将简要介绍稀疏编码的理论和算法。

2.1 系数编码的理论

2.2 求解系数

组合系数的求解算法根据0范和1范会有所不同。0范的算法典型的可以采用贪心的思想，并结合一些迭代。而1范问题构成了一个凸优化问题，凸优化问题求解有许多现成的工具，如cvx。实际中常用的算法有Basis Pursuit算法，MP算法，OMP算法，LASSO算法，LARS算法等。

2.3 学习字典

超完备字典的学习可以根据具体的任务使用不同的算法，目前常用的是KSVD算法，DKSVD算法，DDL算法，AutoEncoder算法等。KSVD重点在保证重建误差最低来构造完备字典。DKSVD算法引入了判别模型，使得训练的字典具有可区分性。而DDL算法引入了训练集之间的关联性和判别模型，使得字典更具有可区分性。图2中展示了使用AutoEncoder和稀疏性条件在MNIST数据集上学习到的字典。

MNIST数据集中包含60000张手写且不规则的0到9的图片数据，本文作者使用AutoEncoder和稀疏条件构建了稀疏表达模型，并利用Back Propagation算法不断的迭代更新学习字典。图2中的每一块是字典中的一个基元的可视化的结果。每一块只有部分是白色的区域，这正是由于稀疏性的限制，使得学习到的字典是综合了全局数据的一种局部特征，该局部特征可以被多种数据使用。从图中可以看到数字7，8，9共同的部分被学习出来了。

3 稀疏编码与图像检索

稀疏编码的明显的优点是能够重建信号，能去除噪声，抗部分丢失性，更具有表达粒度，学习字典可以是完全无监督学习，或者有监督学习。本节将充分利用这些特点，将稀疏编码引入到图像检索中的一些模块。

3.1 图像预处理阶段

传统图像预处理方法没有对图像进行分析，忽略了某些总体信息（例如是否符合图像中物体的轮廓）另外传统方法几乎无法对有小部分损坏或者遮挡的图片进行恢复。稀疏编码的去噪能力，抗部分丢失性和重建能力（Sparse model for Image Reconstruction），使其提供了一个完美的统一的解决方案来对图像进行处理。这些处理使得后续的特征提取更加可靠。

3.2 图像特征提取

特征提取一直都是图像处理的核心，好的特征能够表达一幅图像的某些内容。类似SIFT这种特征，其缺点有两个，一是这种特征基于局部点，无法完整的表达一幅图像，丢失了很多信息，二是这种特征没有考虑图片与图片之间的关系，例如关联性，差异性等。

稀疏编码的优点在于字典的学习是来至于海量的图片，考虑到了不同图片之间的关系，考虑到了现实世界图片中物体外观与轮廓是否合理。利用稀疏编码来抽取某些特征，更能加强特征表达图片内容的能力。可以给字典引入一些知识，如可区分性，图片关联性。

如何利用字典来学习特征，这里给出一个简单的思路。假如不引入任何先验知识，可以使用海量的图片块，学习出一个紧致的完备的字典。得到该字典后，将图片按照统一的规则，进行分块，将每一块在该字典上进行系数求解。然后将该系数向量01化，使得其能利用汉明距离来加速特征匹配，使用该01向量作为一个特征点。

3.3 特征融合

传统的BOW使用的是先利用K-MEAN得到多个类中心，然后对每个描述子对应的类中心计数。该过程其实与系数编码完全对应，更准确来说是BOW是稀疏编码的一种特例。我们可以把类中心看作是字典中的基元，把一个描述子对应的最近邻数目加1看成是求解由该字典的组合系数，只是该稀疏约束为系数向量中只能有一个元素非零，且该元素值为1。

传统BOW中有两个问题，首先是该字典是由类中心组成的，未必能覆盖图片局部特征点的空间，即该字典未必是完备的。其次是字典构建的过程中只考虑了局部特征点之间的相似程度，且局部特征点仅与一个字典基元关联，并未考虑局部特征点与其他字典基元的关联。这两个缺陷可能会导致一张图片的多个局部特征点融合为一个特征的时候，表达粒度和区分粒度不足。如果使用Sparse Coding可以克服BOW的缺点。

本文提供一个简单的融合办法（假设不考虑引入判别性等）：第一步：将训练集图片中的所有局部特征点（如SIFT或者SURF）作为。第二步：使用KSVD或其他算法在数据集上学习字典。第三步：对每一张图片，提取图片的所有局部特征点，构成集合，其中为一个局部特征点。并初始化一个零向量，其维度为字典中的基元个数，该向量作为图片最终的特征向量。第四步：对每一个计算其在字典上的系数向量，最终会获得一个系数矩阵。第五步：对矩阵进行max-pooling或者average-pooling操作，将pool的值放到对应位置处，最终以作为图片的特征向量。算法完毕。

3.4 细节优化

（1）图片预处理阶段可以先使用稀疏编码处理，然后再使用传统预处理的算法处理。（2）在抽取特征的地方，可以去除掉一些重建误差较大的特征点，以减少噪声点的影响。（3）可以使用稀疏编码抽取的特征，结合传统的局部特征共同表达一幅图像。（4）在特征融合阶段的字典，可引入一些判别信息，采用DDL或者DKSVD等算法学习字典。

4 缺陷

由于Sparse Coding在学习字典和求解系数上比较困难，目前还没有特别快速的算法能够兼顾性能和效率。将其融入检索系统，会造成前期字典数据的离线训练会比较长。其次是在利用Sparse Coding进行特征抽取和特征融合的地方，时间也有一定的增加。总之，如何加快Sparse Coding的速度成了一个核心问题。

5 展望

Sparse Coding作为机器学习，模式识别，计算机视觉的一个新兴研究方向，并且获得了诸多领域前所未有的成绩，值得对其进行更加深入的研究和探索。作者期待Sparse Coding能有更进一步的研究成果，并将致力于如何提高Sparse Coding的时效性，表达性和发掘其应用价值。

参考文献

[1]John Wright，Yi Ma.Sparse Representationfor Computer Visionand Pattern Recognition.Proceedings of the IEEE，2010：1031-1044.

[2]Michal Aharon，Michael Elad，Alfred Bruckstein.K-SVD：An Algorithm for Designing OvercompleteDictionaries for Sparse Representation. IEEE TRANSACTIONS ON SIGNAL PROCESSING，2006：4311-4322

[3]John Wright，Arvind Ganesh.Robust Face Recognition via Sparse Representation. Pattern Analysis and Machine Intelligence， IEEE Transactions on （Volume：31 ，Issue： 2 ），2009：210–227

[4]杨谦，齐翔林，汪云九.视皮层V1区简单细胞的稀疏编码策略.计算物理，2001.