图像分类在图像检索[1]、智能交通[2]等领域中有着普遍的应用。目前, 最为常见的是基于视觉词袋(Bag of Visual Words, BoVW)模型[3]的图像分类, 该模型中特征编码方案的有效性、准确性和鲁棒性在很大程度上决定了图像分类的效果和性能, 因此特征编码方案的构建成为本文的一个重要研究内容。
BoVW模型主要是将图像中的视觉词汇聚类得到视觉字典, 然后采用矢量量化策略, 统计每一幅图像中视觉词汇对应的视觉字典基上出现的频次, 从而构建视觉特征直方图, 用来表示对应图像的内容。然而, 在特征编码的过程中, 存在的图像空间语义信息丢失的问题。为此Lazebnik等[4]提出了将特征空间信息加入到特征编码中的空间金字塔匹配(Spatial Pyramid Matching, SPM)算法(BowSPM), 该算法使得每一个待重构特征的编码有且仅有一个非零元素, 因此存在编码重构误差较大的问题。为了进一步减少重构误差, 获得更为准确的特征表达, Yang等[5]提出了一种基于稀疏编码(ScSPM)的分类算法, 该算法分别对每个特征进行单独的稀疏重构, 使用
本文在快速低秩编码的理论框架下加入特征之间的相关性和局部性信息, 提出一种强化局部约束的快速低秩编码算法, 从而达到约束特征编码、降低编码量化误差、增强编码准确性的目标。与文献[5-6]算法相比, 本文算法在快速处理大规模图像分类的情况下, 仍保持较高的分类准确率。
1 基于BoVW的图像分类图像中局部特征的近似编码不仅能准确地表达图像内容, 而且能有效改善分类的准确性。目前, 大多数的编码方案都是在BoVW模型的基础上改进扩展, 如:BowSPM[4]、ScSPM[5]、LrrSPM[6]、局部约束线性编码(LLC)[7]和拉普拉斯稀疏编码(LScSPM)[8]等。本章主要对BowSPM、ScSPM和LrrSPM三种编码方案进行介绍。其中矩阵X=x1, x2, …, xn]∈Rd×n表示从图像I中提取到的n个d维局部特征矩阵(如尺度不变特征转换(Scale Invariant Feature Transform, SIFT)特征[9]、方向梯度直方图(Histogram of Oriented Gradient, HOG)特征[10]), X中的每一列xi代表图像中的一个局部特征向量。由随机选取的样本特征聚类得到的k个聚类中心组成一个视觉字典矩阵D=d1, d2, …, dk]∈Rd×k, 向量di表示字典中的视觉词汇。特征编码矩阵C=c1, c2, …, cn]∈Rk×n, ci是xi对应的特征编码系数。在特征聚合阶段, 使用SPM算法将每一个图像分解成不同的尺度l=0, 1, 2, 每一尺度的图像块个数是2l×2l, 然后计算每一个块内的局部特征直方图, 最终将所有直方图组合成一个向量来表示图像I。
1.1 空间金字塔编码(BowSPM)对于图像中的一个局部特征xi使用矢量量化(Vector Quantization, VQ)方式编码[4], 其目标函数如式(1) 所示:
$ \begin{array}{l} \;\;\;\;\;\mathop {{\rm{min}}}\limits_{\mathit{\boldsymbol{C}}, \mathit{\boldsymbol{D}}} \sum\limits_{i = 1}^n {\left\| {{\mathit{\boldsymbol{x}}_i} - \mathit{\boldsymbol{D}}{\mathit{\boldsymbol{c}}_i}} \right\|_2^2} \\ {\rm{s}}{\rm{.t }}\;\;Card\left( {{\mathit{\boldsymbol{c}}_i}} \right) = 1 \end{array} $ | (1) |
其中:‖·‖2代表
Yang等[5]提出ScSPM对xi进行稀疏编码, 模型表达式如式(2) 所示:
$ \mathop {{\rm{min}}}\limits_{{\mathit{\boldsymbol{c}}_i}} \left\| {{\mathit{\boldsymbol{x}}_i} - \mathit{\boldsymbol{D}}{\mathit{\boldsymbol{c}}_i}} \right\|_2^2 + \lambda {\left\| {{\mathit{\boldsymbol{c}}_i}} \right\|_1} $ | (2) |
其中:‖·‖1是
Peng等[6]提出了LrrSPM算法, 其目标函数如式(3) 所示:
$ \begin{array}{l} \mathop {\;\;\;\;\;{\rm{min}}}\limits_{\;\;\;\;\;\;\;\;\mathit{\boldsymbol{C}}} {\rm{ rank}}\left( \mathit{\boldsymbol{C}} \right)\\ {\rm{s}}{\rm{.t }}\;\;\;\mathit{\boldsymbol{X}} = \mathit{\boldsymbol{DC}} \end{array} $ | (3) |
其中:rank(C)表示矩阵C的秩。该模型通过解决秩最小化问题将特征之间的群组信息加入到编码中, 不仅增强了编码的判别性、鲁棒性以及模型的泛化能力, 而且提高了编码的效率, 文献[6]中的实验结果表明, LrrSPM的编码效率比ScSPM高25~29倍。但是LrrSPM在编码过程中忽略了特征之间的相关性和局部性信息, 使得特征编码不能准确表达图像内容。
2 本文算法采用不同的编码方案, 对编码施加不同的约束, 目的是从有限的特征集中筛选出具有判别性的信息, 使编码向量能够更加准确地表达图像内容。因此, 本文在快速低秩编码[8]的基础上, 以图像中局部信息的重要性大于稀疏性信息[7]的结论为依据, 提出了一种基于局部约束的快速低秩编码的图像分类算法。算法在原有表达图像特征之间群组结构性信息的基础上, 加入特征之间的相似性和局部性信息, 使图像中的局部相似特征具有相似的编码。另外考虑到局部特征之间的结构相关性, 采用特征聚类的方法强化特征空间的一致性, 进一步减小特征重建误差, 并且在快速分类的基础上提高了分类的准确率。
2.1 算法原理为了使相似特征具有相似的编码, 获取特征之间的相似性信息, 本文算法对特征点矩阵X进行聚类, 得到k′个聚类中心, 则将矩阵X划分k′类, Xi表示聚类得到的第i类特征点矩阵, Xi∈Rd×l, i∈{1, 2, …, k′}, li是第i类特征矩阵的特征个数。此外, 为了加入特征之间的局部性信息, 并且进一步约束相似特征具有相似编码, 本文算法根据得到的k′个聚类中心, 以K最近邻(K Nearest Neighbor, KNN)策略为依据, 依次找到每一个特征聚类中心对应的字典D中的k"个近邻的视觉词汇组成小字典Dk", 改进算法如图 1所示, 其中特征矩阵X中的每一列代表一个特征向量, 字典矩阵D中的每一列代表一个视觉词汇, 特征编码Ci中的每一列代表对应特征的编码系数。
根据得到的Xi以及对应的小字典Dk", 采用快速低秩编码算法求解编码系数Ci, 其中, 则本文改进算法模型可表示为式(4):
$ \begin{array}{l} \;\;\;\;\;\mathop {{\rm{min}}}\limits_{{\mathit{\boldsymbol{C}}_{^i}}} {\rm{ rank}}\left( {{\mathit{\boldsymbol{C}}_{^i}}} \right)\\ {\rm{s}}{\rm{.t}}{\rm{. }}\;\;{\mathit{\boldsymbol{X}}_{^i}}{\rm{ }} = {\rm{ }}{\mathit{\boldsymbol{D}}_{^{k''}}}{\mathit{\boldsymbol{C}}_{^i}} \end{array} $ | (4) |
本文采用文献[6]方法求解式(4), 其最优解可表示为式(5)。但是在实际求解过程中, 使用的是D的伪逆, 可表示为式(6):
$ \mathit{\boldsymbol{C}}_i^* = \mathit{\boldsymbol{D}}_{k''}^{ - 1}{\mathit{\boldsymbol{X}}_i} $ | (5) |
其中D-1表示D的逆。
$ \mathit{\boldsymbol{C}}_i^* = \mathit{\boldsymbol{D}}{}_{k''}^*{\mathit{\boldsymbol{X}}_i} $ | (6) |
基于上述结果, 可以得出式(7):
$ \begin{array}{l} {\rm{rank}}\left( {\mathit{\boldsymbol{C}}_i^*} \right) \le {\rm{min}}\left\{ {{\rm{rank}}\left( {\mathit{\boldsymbol{D}}_{k''}^{\rm{† }}} \right), {\rm{rank}}\left( {{\mathit{\boldsymbol{X}}_i}} \right)} \right\} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{min}}\left\{ {{\rm{rank}}\left( {{\mathit{\boldsymbol{D}}_{k''}}} \right), {\rm{rank}}\left( {{\mathit{\boldsymbol{X}}_i}} \right)} \right\} \end{array} $ | (7) |
式(7) 表明Dk"和Xi的秩与Ci*的秩之间的关系, 即当字典Dk"是低秩时, Ci*也是低秩的。由于Dk"是过完备字典, 则能够推出Ci*是低秩。为了避免过拟合问题, 在求解过程中结合Frobenius范数正则化方法[11]约束得到的Ci*, 如式(8) 所示:
$ \mathit{\boldsymbol{C}}_i^* = {\left( {\mathit{\boldsymbol{D}}_{k''}^{\rm{T}}{\mathit{\boldsymbol{D}}_{k''}} + \lambda \mathit{\boldsymbol{I}}} \right)^{ -1}}\mathit{\boldsymbol{D}}_{k''}^{\rm{T}}{\mathit{\boldsymbol{X}}_i} $ | (8) |
其中:λ > 0是正则化参数; I表示单位矩阵。最终得到的k′个Ci, 并根据每一个特征聚类中心对应的单个视觉词汇在字典D中的位置, 还原每一个Ci, 形成矩阵C表示一幅图像中对应局部特征的编码, 则C是X在字典D上的具有稀疏性、局部性和相似性的低秩编码。
2.2 改进算法的流程本文算法具体流程如下:
1) 输入图像I, 字典D∈Rd×k, 正则化参数λ。
2) 提取图像I中的SIFT特征点, 构成特征矩阵X。
3) 使用k均值(k-means)聚类算法对特征点矩阵X聚类, 得到k′个聚类中心, 以及每一个类包含的特征点Xi。
4) 将得到的k′个特征中心分别查找字典D中对应的k"个近邻视觉词汇, 并且将k"个视觉词汇组成小字典Dk"。
5) 计算Xi对应的编码Ci=(Dk"TDk"+λI)-1Dk"TXi, 并且使用
6) 考虑到字典中存在的噪声问题, 使用式(9) 并设定阈值ε剔除C中的一些无效数据, cji=c1i, c2i, …, cki]T通常ε=0.98。
$ {\mathit{\boldsymbol{c}}_{ji}} = \left\{ \begin{array}{l} {\mathit{\boldsymbol{c}}_{ji}}, \;\;\;\;K\frac{{{\mathit{\boldsymbol{c}}_{ji}}}}{{\sum\limits_j {{\mathit{\boldsymbol{c}}_{ji}}} }} < \varepsilon \\ 0, \;\;\;\;\;\;{\rm{其他}} \end{array} \right. $ | (9) |
7) 根据SPM算法, 将矩阵C划分为b=2l×2l块, l=0, 1, 2代表金字塔的层数。对于每一层中的每一块采用最大聚合(max-pooling)算法得到一幅图像的最终表示向量zi=max{|ci1|, |ci2|, …, |cib|}, 其中cij是第i个图像块中的第j个特征向量;
8) 输出表示图像I的最终向量zi。
3 实验结果及分析 3.1 实验环境及参数设置为验证本文所提改进算法的有效性, 选择两个常用图像库进行图像分类实验, 分别是Scene-15图像库[4]和Caltech-101图像库[12]。本文所有实验, 特征提取阶段均采用Dense SIFT提取每一幅图像中所有大小为16×16图像块的局部特征, 步长为6。采用无监督聚类算法随机选取图像库中200 000个SIFT特征作为构建过完备字典的训练样本。编码过程中的正则化参数λ主要是为了避免出现过拟合的问题, 阈值ε主要是用于消除部分编码误差, 根据文献[6]中所述, 本文的所有实验设置λ=0.7,ε=0.98。特征聚合阶段, 采用l=3层的空间金字塔匹配模型(SPM)并结合max-pooling算法形成一幅图像的最终表示向量。在分类阶段, 采用一对多的线性SVM作为分类器。为了获取稳定的分类结果, 本文对所有图像库均进行5次重复训练及测试, 使用平均分类准确率和平均编码时间作为本文算法的评价指标。
由于本文采用无监督聚类方法分别对每一幅图像中的所有特征聚类得到k′, 以及使用KNN策略选取字典D中的k"个最近邻视觉词汇, 为了观察两者之间的关系, 在图像库Scene-15上, 随机选取每类的100幅图像训练, 其余作为测试图像, 设置k′=[20, 30, 40, 50, 60], k"=[20, 30, 40, 50, 60], 得到k′和k"的关系如图 2所示, 根据多组实验对比得出在k′=40, k"=40时本文算法能达到较好效果。
Scene-15图像库中有15个场景, 共计4 485幅图像, 包含办公室、卧室、厨房和客厅等室内场景, 以及工厂、街道、森林、海岸、高速公路、原野和山脉等室外场景, 每类场景包含图像约200~400幅。实验过程中, 训练字典D∈R128×1 024, 随机选取每类场景的100幅图像作为训练图像, 剩余图像作为测试图像, 实验结果如表 1所示。
实验结果表明, 本文算法的分类准确率比LrrSPM算法提升了4.53%左右, 比ScSPM算法提升了1%左右。而编码时间比LrrSPM算法仅仅增加了36 s左右, 但比ScSPM算法编码效率提高了6倍左右。由于在场景分类中, 每一类场景包含的信息都十分复杂而且非常丰富, 本文算法通过加入特征之间的局部约束性信息, 能较准确地对场景中的有效特征进行筛选编码, 并且使得特征编码能够较准确地表达图像内容。因此本文算法与LrrSPM算法相比, 能够在编码算法时间大致相当的情况下, 显著提高分类准确率。与ScSPM算法相比, 由于本文算法采用快速低秩编码算法, 编码过程中主要是利用了F范数近似核范数的求解, F范数可直接求导得近似解, 所以本文算法能够在显著降低编码时间的情况下, 仍然保持较高的分类准确率。
3.3 Caltech-101图像库Caltech-101图像库包含101类, 共9 144幅图像, 如植物、动物、交通工具和家具等类别, 每类图像包含31~800幅图像。该图像库具有较大的类间变化及类内变化, 并且图像自身更具多样性和复杂性, 因此该图像库是图像分类中难度较高的数据库之一。实验过程中训练字典D∈R128×2 048, 随机选取每类图像的30幅作为训练图像, 其余作为测试图像, 实验结果如表 2所示。
实验结果表明, 本文算法比LrrSPM算法快50 s左右, 并且本文算法的分类准确率比LrrSPM提高了8%左右。与ScSPM算法相比, 虽然分类准确率降低了2%左右, 但是编码效率是ScSPM算法的5~6倍。在物体分类中, 由于图像的背景较为简单, 噪声较少, 又因ScSPM算法是对单个特征单独编码, 对于此种情况, ScSPM能够较好地表达图像中的物体信息, 所以本文改进的算法与ScSPM相比分类准确率减少了1%左右。但是, 本文算法实现了对图像中局部相似特征的约束, 剔除局部区域内不相关的特征, 使得特征编码也能够较准确地表达图像内容, 因此本文算法与LrrSPM算法相比不仅分类准确率方面有显著提高, 并且编码时间也有所减少。
由表 1~2可知, 本文算法在物体分类上的准确率较高, 由于加入特征的局部约束的条件, 使得在场景分类上的准确率更高。此外, 在样本数量增大一倍的情况下, 本文改进的编码算法仍然具有较高的编码效率。同时, 在数据量较大的情况下, 本文算法编码时间比LrrSPM有所降低, 反映本文算法能够较好地适应较大规模的图像分类问题。
4 结语本文在LrrSPM算法的基础上, 对LrrSPM算法中的编码方式进行改进, 加入特征之间的相关性和局部性信息, 实现了图像的快速编码, 并且提升了编码的一致性和准确性, 从而提高了分类准确率。实验结果表明, 本文算法在物体图像库和场景图像库上都有较好的分类效果, 然而相对于场景分类准确率, 物体分类效果欠佳。因此, 在下一步的工作中将进一步约束编码方式以及增强字典的判别性, 使特征编码能够更加准确地表达图像内容, 增强对物体分类的鲁棒性, 在保持较高编码效率的情况下, 进一步提高分类的准确率。同时, 也可以尝试将本文算法应用到模式识别的其他领域中, 如人脸识别、人体行为识别等。
[1] | HONG R, TANG J, TAN H K, et al. Beyond search: event-driven summarization for Web videos[J]. ACM Transactions on Multimedia Computing Communications and Applications, 2011, 7(4): 702-715. |
[2] | HUANG Y, WU Z, WANG L, et al. Feature coding in image classification: a comprehensive study[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(3): 493-506. DOI:10.1109/TPAMI.2013.113 |
[3] | CSURKA G, DANCE C R, FAN L, et al. Visual categorization with bags of keypoints [EB/OL]. [2017-01-10]. http://www.europe.naverlabs.com/content/download/23625/171397/version/1/file/2004_010.pdf. |
[4] | LAZEBNIK S, SCHMID C, PONCE J. Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[C]//Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2006: 2169-2178. |
[5] | YANG J, YU K, GONG Y, et al. Linear spatial pyramid matching using sparse coding for image classification[C]//CVPR 2009: Proceedings of the 2009 Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2009: 1794-1801. |
[6] | PENG X, YAN R, ZHAO B, et al. Fast low rank representation based spatial pyramid matching for image classification[J]. Knowledge-Based Systems, 2015, 90(12): 14-22. |
[7] | WANG J, YANG J, YU K, et al. Locality-constrained linear coding for image classification[C]//CVPR 2010: Proceedings of the 2010 Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2010: 3360-3367. |
[8] | GAO S, TSANG W H, CHIA L T, et al. Local features are not lonely-Laplacian sparse coding for image classification[C]//CVPR 2010: Proceedings of the 2010 Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2010: 3555-3561. |
[9] | LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110. DOI:10.1023/B:VISI.0000029664.99615.94 |
[10] | DALAL N, TRIGGS B. Histograms of oriented gradients for human detection [C]//CVPR 2005: Proceedings of the 2005 Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2005: 886-893. |
[11] | ZHANG H, YI Z, PENG X. FlRR: fast low-rank representation using Frobenius-norm[J]. Electronics Letters, 2014, 50(13): 936-938. DOI:10.1049/el.2014.1396 |
[12] | FEIFEI L, FERGUS R, PERONA P. One-shot learning of object categories[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(4): 594-611. DOI:10.1109/TPAMI.2006.79 |