基于Nyström谱聚类的词典学习

王鑫，李璐，王晓芳

1.安徽建筑大学数理系，合肥 230601

2.解放军陆军军官学院计算机教研室，合肥 230031

基于Nyström谱聚类的词典学习

王鑫1，李璐1，王晓芳2

1.安徽建筑大学数理系，合肥 230601

2.解放军陆军军官学院计算机教研室，合肥 230031

构建视觉词典是BOVW模型中关键的一个步骤，目前大多数视觉词典是基于K-means聚类方式构建。然而由于K-means聚类的局限性以及样本空间结构的复杂性与高维性，这种方式构建的视觉词典往往区分性能较差。在谱聚类的框架下，提出一种区分性能更强的视觉词典学习算法，为了减少特征在量化过程中区分性能的降低以及谱聚类固有的存储计算问题，算法根据训练样本的类别标签对训练数据进行划分，基于Nyström谱聚类得到各子样本数据集的中心并得到最终的视觉词典。在Scene-15数据集上的实验结果验证了算法的正确性和有效性。特别当训练样本有限时，采用该算法生成的视觉词典性能较优。

图像分类；视觉词袋模型；视觉词典；谱聚类

近年来，视觉词袋模型（BOVW）技术广泛地应用于计算机视觉特别是图像分类、图像检索、目标检测等领域，并取得很大的成功。BOVW的思想来源于词袋模型。词袋模型（BOW）源于自然语言处理领域，通过统计每个文档中词项出现的频率，将文档表示为稀疏的词项向量，其中每一个元素为字典中的单词，其值表示该词项在文档中出现的频率，进而文档可以被描述为词项的归一化直方图。

BOVW借鉴了上述思想，用一组无序的图像局部特征集合来表示图像，这种方法计算量小并且易于理解，在计算机视觉领域中受到越来越多的关注。BOVW通过视觉词典将图像底层局部特征表示为直方图空间中具有固定长度的特征向量，其中视觉词典的区分性能决定着模型的质量，视觉词典的大小决定着模型的复杂度。由此可见，在BOVW中视觉词典的构建具有重要的意义，影响着图像最终的分类与识别性能。在理想情况下，希望BOVW模型中的视觉单词与自然语言中的词项一样具有明确的语义信息，但实际情况并非如此，并且视觉词典的性能受到诸如特征提取方式、聚类方法、视觉词典大小以及距离测度等多方面的影响。

从本质上讲，视觉词典的构建其实是对特征空间的一种划分，将同一子空间中的特征用一个或多个视觉单词表示。目前，视觉词典的构建主要有如下两种方式：第一，基于标注的方法；第二，基于数据驱动的方法。第一种方法中，图像分割和图像区域标注等监督学习算法被引入其中，通过对划分的图像块赋予有意的标签如天空、水、植物等构建词典，这方法工作量大、主观性强，限制了其在实际中的应用。第二种方法目前被广泛应用，多种非监督聚类算法被应用于构建视觉词典，其中使用最频繁的是K-means算法[1-3]，mean-shift[4]，层次K-means[5]及Gaussian Mixture Models[6]（GMM）等。K-means聚类算法简单，但是其有自身的局限性：（1）对于初始聚类中心敏感。对于小规模视觉词典的构建，可以设置不同的聚类中心多次运行寻找最佳聚类中心，但是对于大规模视觉词典的构建，反复多次运行K-means算法极为浪费时间。（2）K-means算法本身存在样本需要服从高斯分布的隐形假设，很少考虑样本数据的真实分布情况。当图像具有同质结构特性时如纹理图像，特征空间趋于高斯分布，采用K-means聚类方式生成的视觉词典具有很好的区分性能。但对于自然场景图像以及结构更加复杂的真实图像，采用这种方式生成的视觉词典性能较差。（3）K-means聚类具有密度敏感性。特征的空间分布表现出一定的长尾特性，大量低区分性能的特征出现频率较高，而少量高区分性能的频率出现频率较低，特别是在图像分类与场景识别领域中，高频率的特征往往表现为图像的一般性结构信息如边缘、背景以及噪声信息等，而具有较强区分性能的特征由于出现频率较低而无法生成聚类中心，因此高区分性能的特征存在较大的量化误差，带来了信息的损失。从而导致视觉词典区分性能的下降。

Yang，L[7]通过分类器训练学习区分性能强的视觉词典并用于物体识别；Moosmann基于Random Forest提出一种ERC-Forest[8]。Wang L[9]首先根据层次聚类构建大规模视觉词典，然后采用特征选择的方式构建规模适度、区分性能更强的视觉词典。R.J.Lopez[10]根据最大化聚类精度和自适应优化准则构建视觉词典。Yadong Mu[11]基于Locality Sensitive Hashing和Random Forest思想提出一种Random Locality Sensitive Vocabulary（RLSV）的词典构建算法，算法不以聚类为基础，而是通过随机投影的方式生成多个视觉词典并加以融合，实验验证了算法的有效性。虽然上述各方法均取得了不错的效果，但在基于学习过程的分类方法中很少考虑到如何减少量化误差以及样本数据特性对图像分类与识别的影响。在大规模图像分类与识别中，图像数据主要表现出两个方面的特性：一是样本数目越来越多，空间结构越来越复杂；二是图像局部特征描述子的维数越来越高，在特征空间中的分布极不均匀并具有流形结构特性。在低维空间具有良好性能的聚类算法如K-means或GMM等都是建立在凸样本空间上，当样本空间不为凸时，算法会陷入局部最优解，无法反映数据的全局一致性，因此基于传统方法在高维特征空间聚类生成的视觉词典并不能反映特征的真实分布情况，性能较差。

为了解决视觉词典构建过程的上述问题，提出一种基于谱聚类构建视觉词典的算法。谱聚类仅与样本数据点的数目有关，而与维数无关，因此避免了高维特征向量造成的奇异性问题，并且能在任意形状的样本空间中收敛于全局最优解。在研究相关算法的基础上，本文提出一种基于Nyström谱聚类的词典学习算法，算法充分利用谱聚类在高维、任意形状特征空间中聚类的优点，避免了高维特征向量造成的奇异性以及传统聚类算法的不稳定性。为了充分利用各类别的先验信息并且减少长尾特性带来的影响以及解决谱聚类中的存储计算问题，算法根据样本的类别标签对图像特征空间进行划分，在各类子空间中分别生成聚类中心，一定程度上减小了量化过程带来的误差并且增加了词典的语义信息。并且在各类子空间谱聚类的过程中使用Nyström低秩矩阵近似进一步减小了算法中的存储以及计算问题，最后生成区别性能更强、规模更加紧凑的视觉词典。

1 BOVW模型

BOVW模型在图像分类、场景识别等领域取得了一定的成功，Sivic.J[12]首次提出BOVW模型的概念并成功用于视频检索。Fei-Fei等[13]在BOVW模型的基础上利用LDA模型和PLSA模型完成图像的场景分类。Lazebnik等[14]提出一种空间金字塔匹配方法用于自然图像的分类与识别，算法在BOVW模型的基础上包含了图像的几何空间信息。BOVW模型用于图像分类与识别主要包括以下步骤：特征提取，构建视觉词典，特征编码及分类器设计。（1）特征提取。Mikolajczyk和Schmid[15]对常见的几种图像局部特征进行了实验对比，验证了SIFT特征相比于其他局部特征具有较好的光照、旋转、尺度以及仿射不变性，取得最好的实验性能。（2）构建视觉词典。通过对训练集图像中的SIFT特征进行聚类生成视觉词典，其中每一个聚类中心称为一个视觉单词。（3）特征编码。对每幅图像中提取的每一个特征，将其赋值于视觉词典中最近的一个或者多个视觉单词。（4）分类器设计。将归一化后的表示目标图像的特征向量用于训练分类器，根据生成的训练器在测试图像中进行分类与识别。

2 谱聚类

为了能在任意形状的样本空间上聚类，且收敛于全局最优解，学者提出谱聚类算法。谱聚类算法的思想来源于谱图划分理论，将聚类问题看成一个无向图的多路划分问题，定义一个图划分判据，如Shi和Malik[16]提出的一个有效的图划分判据---规范切判据，最优化这一判据，使得同一类内的点具有较高的相似性，不同类的点具有较低的相似性。由于图划分问题的组合本质，求图划分判据最优解是一个NP难题，一个行之有效的方法是考虑问题的连续放松形式，这样便可将原问题转换成求图的Laplacian矩阵谱分解问题，这类方法统称为谱聚类。

对于给定的样本点x1，x2，…，xn，谱聚类算法计算样本点间相似性矩阵S=[sij]∈Rn×n，其中sij≥0表示样本点xi和xj之间的相似度，再根据相似信息将样本点划分为k个簇。代表算法有Ng等提出的基于规范化拉普拉斯矩阵的谱聚类（标准谱聚类算法），算法步骤如下：首先计算相似矩阵S及其标准拉普拉斯矩阵L。

D为度矩阵，对角线元素取值如式（3），非对角线上的元素取值为0。然后计算矩阵L的k个尾特征向量V= (v1，v2，…，vn)，将V的每一行看成一个样本数据点使用K-means得到聚类结果。

谱聚类直接分析样本数据点间的相似矩阵来达到聚类的目的，但是计算与存储数据点之间的相似度矩阵及前k个Laplacian矩阵特征值对应的特征向量，阻碍了其在大规模数据中的应用。缓解这种问题一个有效的方法是利用Nyström方法进行低秩矩阵近似[17]。

3 基于Nyström谱聚类构建视觉词典

Williams[18]将Nyström方法应用于核矩阵加速运算。Fowlkes[19]等在谱聚类中使用Nyström近似算法来避免计算整个相似矩阵并应用于图像分割中，Nyström方法每次从核矩阵中选择m列，然后利用被选列和剩余列之间的关系构造整个矩阵的低秩近似。本文首先根据训练样本的类别信息对训练样本集进行划分得到样本子集合C1…Cn，然后对各样本子集Ci基于Nyström方法进行谱聚类，分别得到每个样本集合的若干聚类中心V1…Vn，最后由聚类中心构造样本空间并采用谱聚类生成最终的视觉词典。

对A进行特征分解，A=VAΣAVTA，ΣA包含A的特征值，VA为矩阵A特征值对应的特征向量。基于Nyström方法，矩阵Sd有如下近似低秩分解：

4 实验结果与分析

本实验采用图像分类与识别领域中最常用的标准数据集Scene-15，采用文献[13]中的方式提取每幅图像的特征，以8像素为步长，在16×16大小的像素块内提取稠密SIFT特征。为了包含图像的空间信息，采用空间金字塔匹配核，空间金字塔总层数为3，大小分别为1×1，2×2，4×4。如果没有特别说明，采用文献[21]所提出的局部受限软赋值编码方式。采用图像分类通用的方法从图像集中随机选取10组训练图像集和测试图像集，每次实验的结果是数据集中所有类别图像分类正确率的平均值。采用一对多的方式构造多类分类器，采用直方图交作为SVM分类器的核函数。

在Nyström谱聚类构建视觉词典的过程中，随机采样数目l和尺度参数δ具有重要的意义，其中l决定了特征分解的时间复杂度，很大程度上影响着算法的时间复杂度。而δ在构建相似度矩阵时具有重要的意义，很大程度上决定了谱聚类的质量，影响着视觉词典的性能。为了验证l和δ对分类性能的影响，实验中分别取l为1 000，1 500，2 000，2 500，3 000，4 000，δ取20，30，40和50（最终视觉词典的大小为500、训练样本个数为30），实验结果如图1所示。

图1 不同采样数目和尺度参数对词典性能的影响

从图1中可以看出当δ取30的时候，对于不同大小的采样数目实验均取得了不错的识别正确率；当δ取50时，其对应的图像分类正确率几乎都是最低。从图中还可以看出当l足够大时，图像分类正确率趋于稳定，并且随着采样数目l的增加，图像分类正确率有所降低。为了取得最优的分类识别效果，后续实验中l取2 500，δ取30。

以上实验验证了基于Nyström谱聚类算法的有效性以及将该方法引入视觉词典构建的可行性。在BOVW模型中，大多数视觉词典是基于K-means聚类方式构建。本章分别基于K-means聚类算法和本文算法构建视觉词典并从不同方面比较词典对识别性能的影响。

首先分析不同训练样本数目构建视觉词典对分类性能的影响。从Scene-15每类场景图像中分别随机选择10，20，30，40，50，60张图像作为训练样本，剩余的全部作为测试样本，实验比较结果如图2所示。实验结果表明，图像识别正确率随着训练样本数目逐渐增加并且当训练样本数目一定的时候，基于本文算法构建的视觉词典从识别正确率上完胜基于K-means算法。特别是当训练样本不足时（小于40），基于谱聚类生成的视觉单词区分性能较强，识别正确率远高于K-means算法。当训练样本数目为30时，采用本文算法图像识别正确率达到（72.81%），高于训练样本数目为50、采用K-means算法构建词典的图像识别正确率。

图2 不同训练样本数目对词典性能的影响

图3反映了不同大小视觉词典对图像识别正确率的影响。当视觉词典的长度过小时（K=200），采用两种方法构建视觉词典所获得图像识别正确率均是最低，而视觉词典的长度比较大时（K=1 500），所获得图像分类正确率几乎都是最高，不难看出随着视觉词典长度的增加，图像的识别正确率都有所增加。但对基于K-means方式构建的视觉词典，当词典的大小从1 000增加到1 500时，图像分类正确率几乎没有变化，可以认为在此过程中没有生成更具区分性能的视觉单词，仅仅增加了算法的复杂性；而采用谱聚类算法时，由于最终的特征空间是由各图像类的特征空间均匀构成，当词典的大小同样从1 000增加到1 500时，图像分类正确率仍然有所增加。从图中可以看出，采用谱聚类构建视觉词典时，其尺度为500所获得的图像识别正确率已经稍胜于尺度大小为800、基于K-means算法所构建的视觉词典。

图3 不同视觉词典大小对识别性能的影响

图4 不同算法的分类混淆矩阵

在基于BOVW模型中，构建视觉词典的指导原则之一就是其长度大小。当视觉词典过小时视觉词典的区分性能过低，不同的语义特征可能标记为相同的视觉单词；当视觉词典过大时，一方面所生成的视觉词典对噪声比较敏感，降低了图像分类与识别的性能，另一方面所生成特征向量的高维性会引起“维度灾难”等相关问题，增加了算法的复杂性。从图可以看出，当基于谱聚类构建视觉词典时，当其大小取500时便可获得相对不错的分类性能，后续实验中取K=500。

图2和图3给出的是平均识别正确率，这种方式没有给出各子类具体的识别情况。为了给出不同类别的识别正确率，采用分类混淆矩阵进行衡量。其分类混淆矩阵如图4（a）、（b）所示，其中（a）表示采用本文方法构建视觉词典的分类结果，（b）表示采用传统K-means聚类构建视觉词典的分类结果。图中X轴表示图像类别信息，Y轴表示测试图像经过分类器预测之后的类别，第i行j列的值表示第i类图像被分类为第j类图像的数目，因此混淆矩阵对角线上的值表示每类场景的分类准确率，图中背景颜色越深，分类正确率越高。从图4（a）中可以看出，在15个类别中有7个类别的识别正确率超过了85%，识别正确率最高的类别为MITforest（94.4%），识别正确率最低的类别为bedroom（50.2%），而在图4（b）中，仅有5个类别的识别正确率超过85%，识别正确率最高的类别为MITforest（92.3%），分类正确率最低的类别为kitchen（48.6%）。图4（b）中分类正确率最低的4个类别分别是kitchen（48.6%）、bedroom（51.3%）、industrial（52.4%）以及MITopencountry（55.8%）。这些场景错分率比较高，主要原因是没有考虑到类别的信息以及K-means聚类算法的局限性，生成的视觉词典相对于某些类别具有较弱的区分性能。而在谱聚类构建视觉词典中，除了bedroom类别，其他3类的分类正确率均有所提高，分类正确率分别为kitchen（49.3%），industrial（54.1%），MITopencountry（56.7%）。

为了进一步验证基于本文算法构建视觉词典的有效性，本文在不同视觉词典构建方法与特征编码方法的情况下比较图像分类与识别的正确率，其中训练样本个数均为30，视觉词典大小均为500。为了表示方便，采用本文算法生成的视觉词典记为SCV，传统K-means方法生成的视觉词典记为KMV。编码方式分别为硬赋值（Hard-C），软赋值[22]（Soft-C），稀疏编码[23]（SC），局部受限软赋值（LSC）以及LLC[24]，实验结果如图5所示。

图5 不同算法在Scene-15图像集上的分类性能比较

由实验结果可知，在Scene-15场景图像识别中对于相同的编码方式结合本文方法构建的视觉词典均取得了较高的分类正确率并且具有较好的稳定性。与文献[22-23]相比，本文算法既考虑了图像的底层特征信息，又考虑了各类类别信息，特别是考虑到实际样本特征空间的非凸性与复杂性，因而可以更好地实现图像场景建模，构建区分性能更高、更具稳定性的视觉词典。

5 结论

在BOVW模型中，视觉词典的构建一般采用K-means等聚类方法，考虑到实际样本空间的结构复杂性与高维性，本文尝试采用谱聚类算法构建视觉词典。为了减小量化误差并缓解谱聚类在实际应用中的瓶颈问题——相似矩阵的存储以及矩阵特征分解，本文首先根据样本的类别信息对数据样本空间进行分割，然后对于得到的各子空间分别采用Nyström低秩矩阵近似的方法进行谱聚类。Scene-15场景分类实验验证了本文所提算法的有效性和鲁棒性，从大量实验中发现当训练样本有限时，采用本算法构建视觉词典用于图像分类与识别可以取得不错的正确率。然而本文算法仍存在不足之处，为了将谱聚类算法用于视觉词典的构建中，需要对样本空间进行两次谱聚类或者特征选择才能生成最终的视觉词典，当样本规模比较大时，算法具有比较高的时间复杂度和空间复杂度。因此，本文下一步的主要工作是解决谱聚类在构建视觉词典时的时间复杂度和空间复杂度问题，并将其应用于大规模的图像分类与识别任务中。

[1]Csurka G，Dance C，Fan L，et al.Visual categorization with bags of keypoints[C]//Workshop on Statistical Learning in Computer Vision，ECCV，2004：1-22.

[2]Li T，Mei T，Kweon I S.Learning optimal compact codebook for efficient object categorization[C]//IEEE Workshop on Applications of Computer Vision，WACV 2008，2008：1-6.

[3]Winn J，Criminisi A，Minka T.Object categorization by learned universal visual dictionary[C]//Tenth IEEE International Conference on Computer Vision，ICCV 2005，2005：1800-1807.

[4]Jurie F，Triggs B.Creating efficient codebooks for visual recognition[C]//Tenth IEEE International Conference on Computer Vision，ICCV 2005，2005：604-610.

[5]Nister D，Stewenius H.Scalable recognition with a vocabulary tree[C]//2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2006：2161-2168.

[6]Dorko G，Schmid C，Lear P.Object class recognition using discriminative local features，technical report RR-5497[R]. 2005.

[7]Yang L，Jin R，Sukthankar R，et al.Unifying discriminative visual codebook generation with classifier training for object category recognition[C]//IEEE Conference on Computer Vision and Pattern Recognition，CVPR 2008，2008：1-8.

[8]Moosmann F，Nowak E，Jurie F.Randomized clustering forests for image classification[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30（9）：1632-1646.

[9]Wang L.Toward a discriminative codebook：codeword selection across muti-resolution[C]//IEEE Conference on Computer Vision and Pattern Recognition，CVPR’07，2007：1-8.

[10]López-Sastre R J，Tuytelaars T，Acevedo-Rodríguez F J，et al.Towards a more discriminative and semantic visual vocabulary[J].Computer Vision and Image Understanding，2011，115（3）：415-425.

[11]Mu Y，Sun J，Han T X，et al.Randomized locality sensitive vocabularies for bag-of-features model[C]//Computer Vision-ECCV2010.BerlinHeidelberg：Springer，2010：748-761.

[12]Sivic J，Zisserman A.Video Google：a text retrieval approach to object matching in videos[C]//Ninth IEEE International Conference on Computer Vision，2003：1470-1477.

[13]Fei-Fei L，Perona P.A bayesian hierarchical model for learning natural scene categories[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition，CVPR 2005，2005：524-531.

[14]Lazebnik S，Schmid C，Ponce J.Beyond bags of features：spatial pyramid matching for recognizing natural scene categories[C]//IEEEComputer Society Conference on Computer Vision and Pattern Recognition，2006：2169-2178.

[15]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.

[16]Shi J，Malik J.Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）：888-905.

[17]Williams C K I，Rasmussen C E，Scwaighofer A，et al. Observations on the Nyström method for Gaussian process prediction[R].University of Edinburgh and University College London，London，UK，2002.

[18]Williams C，Seeger M.Using the Nyström method to speed up kernel machines[C]//Advances in Neural Information Processing Systems，2001.

[19]Fowlkes C，Belongie S，Chung F，et al.Spectral grouping using the Nyström method[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（2）：214-225.

[20]Li M，Lian X C，Kwok J T，et al.Time and space efficient spectral clustering via column sampling[C]//2011 IEEE Conference on Computer Vision and Pattern Recognition（CVPR），2011：2297-2304.

[21]Liu L，Wang L，Liu X.In defense of soft-assignment coding[C]//2011 IEEE International Conference on Computer Vision（ICCV），2011：2486-2493.

[22]van Gemert J C，Geusebroek J M，Veenman C J，et al. Kernel codebooks for scene categorization[C]//Computer Vision-ECCV 2008.Berlin Heidelberg：Springer，2008：696-709.

[23]Yang J，Yu K，Gong Y，et al.Linear spatial pyramid matching using sparse coding for image classification[C]// IEEE Conference on Computer Vision and Pattern Recognition，CVPR 2009，2009：1794-1801.

[24]Wang J，Yang J，Yu K，et al.Locality-constrained linear coding for image classification[C]//2010 IEEE Conference on Computer Vision and Pattern Recognition（CVPR），2010：3360-3367.

[25]Chen W Y，Song Y，Bai H，et al.Parallel spectral clustering in distributed systems[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（3）：568-586.

WANG Xin1,LI Lu1,WANG Xiaofang2

1.Department of Mathematics and Physics,Anhui Jianzhu University,Hefei 230601,China
2.Department of Computer,Army Officer Academy of PLA,Hefei 230031,China

Construction of visual vocabulary is a crucial step in popular Bag-of-Visual-Words（BOVW）model.Currently, K-means clustering is generally applied to constructing the visual vocabulary.However,the visual dictionary tends to be of low discrimination due to limitation of K-means clustering and complexity of high dimensional spatial structure of samples. Under the frame of spectral clustering,a dictionary learning algorithm with stronger discriminative capability is proposed. In order to reduce degradation of descriptors discriminative power during quantization and the inherent problems of storage and calculation in spectral clustering,the training samples are divided into sub-sample sets according to the label information of category.Centers of each data set are obtained based on spectral clustering with Nyström algorithm and then the final compact visual dictionary is generated.Experimental results in Scene-15 dataset verify the correctness and effectiveness of the proposed algorithm.Especially when the training samples are limited,the visual dictionary via the algorithm can obtain better performance.

image classification;bag of visual words;visual vocabulary;spectral clustering

A

TP391

10.3778/j.issn.1002-8331.1401-0173

WANG Xin,LI Lu,WANG Xiaofang.Dictionary learning based on spectral clustering with Nyström.Computer Engineering and Applications,2014,50（6）：112-117.

安徽省教育厅自然科学项目（No.KJ2013B067，No.KJ2012B034）。

王鑫（1980—），女，讲师，主要研究方向：数字图像处理；李璐（1980—），女，讲师，主要研究方向：数字图像处理；王晓芳（1976—），女，讲师，主要研究方向：数字图像处理。

2014-01-13

2014-02-28

1002-8331（2014）06-0112-06