一种基于语义子空间谱聚类的自动图像标注的方法

一种基于语义空间谱聚类的自动图像标注方法郭玉堂1,2，韩昌刚21．合肥师范学院计算机科学与技术系,合肥2306012．安徽大学计算机科学与技术学院,合肥230039摘要:由于“语义鸿沟”的存在，低层特征相同或相似的图像，其语义有可能完全不同。如何挖掘图像的高层语义与低层特征之间的内在联系是当前图像标注领域研究的难点之一。在详细分析现有的图像标注方法优缺点的基础上，提出了一种基于语义一致性的谱聚类图像标注方法。该方法首先在语义空间内，对训练图像先按语义聚类，使得语义相同或相近的图像处于同一类中，再对每个语义类按区域特征聚类，把相似区域聚类到同一个块中，然后运用多伯努利模型求出语义类中每个块与语义间的联合概率分布，利用该联合概率分布模型为未标注图像进行标注。实验结果表明所提出的方法明显提高了标注准确度。能有效地建立图像的低层特征与语义特征间的一致性。关键词:图像标注K-调和均值图谱聚类语义鸿沟AutomaticImageAnnotationUsingSemanticSubspacegraphspectralclusteringAlgorithnGuoYu-tang1，HanChang-gang21．DepartmentofComputerScienceandTechnologyinHefeiNormalCollege,Hefei230061,China2．SchoolofComputerScienceandTechnologyinAnhuiUniversity,Hefei230039,[e-mail]:Duetoexistingthesemanticgap,imageswiththesameorsimilarlowlevelfeaturesarepossiblytotallydifferentonsemanticlevel.Howtofindtheunderlyingrelationshipbetweenthehigh-levelsemanticandlowlevelfeaturesisoneofthedifficultproblemsforimageannotation.Inthispaper,anewimageannotationmethodbasedongraphspectralclusteringwiththeconsistencyofsemanticsisproposedwithdetailedanalysisontheadvantagesanddisadvantagesoftheexistedimageannotationmethods.Thismethodfirstlyclusterimageintoseveralsemanticclassesbysemanticsimilaritymeasurementinthesemanticsubspace.Withineachsemanticclass,imagesarere-clusteredwithvisualfeaturesof.regionThen,thejointprobabilitydistributionofblobsandwordswasmodeledbyusingMultiple-BernoulliRelevanceModel.Wecanannotateaunannotatedimagebyusingthejointdistribution.Experimentalresultsshowthetheeffectivenessoftheproposedapproachintermsofqualityoftheimageannotation,theconsistencyofhigh-levelsemanticsandlowlevelfeaturesisefficientlyachieved.KeyWords:imageannotation,K-HarmonicMeans,graphspectralclustering,semanticgap1引言自动图像标注指的是指借助计算机视觉、机器学习与模式识别等多学科技术，从一组已标注好的图像集合中学习图像特征与文本标注两种模态间的相关性，为未标注的图像推理出最为可能的标注基金项目：安徽省自然科学基金项目（11040606M134）、安徽省高校自然科学基金重点项目（KJ2009A150）或关键字。一旦图像被成功标注，图像检索问题就可以转化就可以用这样一组关键词来进行，当前技术已相当成熟的文本检索方法就可以用于图像检索[1]中。因此，图像语义标注得到了国内外相关领域的研究人员的广泛重视。目前，国内外已经有许多学者提出了各种不同的方法，并取得了相当多的成果。如共现模型[2]、翻译模型[3-4]、交叉媒体相关模型[5]和多伯努利相关模型[6]等。聚类分析是机器学习领域中的一个主要分支，是人们认识和探索事物之间内在联系的有效手段。近几年来，基于聚类分析的自动图像标标注技术运应而生，并取得了可喜的效果。在参考文献[7-8]中，聚类用于一组训练图像的低层特征，利用统计学方法获得低层特征与标注词间的一组映射。用获得的映射规则标注图像。这些方法都基于一种假设：视觉特征相同或相似的图像，其语义也应相同相似。由于语义鸿沟的存在，实际情况并非如此，那些有着相似的视觉特征的图像它们的语义并不相同，甚至相差很远。如“天空”与“大海”是不同的语义，但它们的视觉特征却很相似。如何挖掘图像的高层语义与低层特征之间的内在联系是当前图像标注领域中研究难点之一。本文提出基于语义子空间谱聚类的图像自动标注方法。为了建立图像的低层视觉特征与标注文本特征间的相关性，在训练集上分别提取图像的低层视觉特征和语义特征。在语义子空间内，以图像标注词作为特征向量，利用调和均值谱聚类算法对图像进行聚类，形成若干个语义类。用每个类的中心词作为该类的标签，再在图像空间内对每个语义类中的图像分割成区域，提取每分割后的每区域的低层特征，根据区域的低层特征的相似关系，再次利用谱聚类算法把同一语义类中的相似区域聚类到同一个块中，形成若干个块。然后运用多伯努利模型求出语义类中每个块与主题词的联合概率分布，通过两次聚类有效地建立图像的低层特征与语义特征间的一致性。这样，我们就在图像语义与低层特征之间架建了一座桥梁。利用该联合概率分布我们可以为未标注图像进行自动标注。2．基于语义子空间谱聚类的图像自动标注2.1基于K-调和均值谱聚类如果把一幅图像看作一个文档，图像的标注词看作文档的关键词，那么我们对图像的标注词为特征进行聚类，就采用文本聚类方法对图像进行聚类了。目前流行的聚类方法主要有以K-Means为代表的基于划分的方法和谱聚类方法等。谱聚类方法是基于图理论，根据数据间的相似性进行聚类，由于与数据点的维数无关，只与数据点的个数有关，因此适用于非测度空间。它得到广泛关注[9]。但传统的谱聚类算法对初始中心选择的比较敏感,使得其运行结果不稳定,且易于陷入局部极小点。同时,文本聚类问题本身也有其特殊性，文本向量通常为稀疏向量,含有较多的0,这也为聚类中心的选择带来困难。为此，我们通过引入K-调和均值,改善谱聚类算法的性能。K-调和均值（K-HarmonicMeans，KHM）算法[10]是一种基于中心的聚类算法，该算法通过计算数据点到聚类中心距离的调和平均来构造其性能函数。算法表述如下：算法1:基于K-调和均值谱聚类算法输入：n个数据点),(21nxxxX，聚类数目k输出：数据点集的类别Step1:构造相似矩阵nnRA，其中)2||||exp(22jiijxxa,ij，0iia。其中是参数.Step2:构造Laplacian矩阵2/12/1ADDL。其中D是对角矩阵，njijiiaD1Step3:计算L的前k个最大的特征值所对应的特征向量keee21,，生成矩阵knkReeZ],,[1；Step4:将矩阵Z的行向量转变为单位向量，得到矩阵jijijZZY2/12)/(。Step5:采用KHM算法，把矩阵Y的每行聚成k类；由于KHM算法用数据点与所有聚类中心的距离的调和平均替代了数据点与聚类中心的最小距离，克服了对初始值敏感的问题。2.2基于语义子空间的图像聚类设},...,{21mtttL是用于标注图像的关键词词汇表，m是词汇表的大小，设)},(),...,,(),,{(2211nnwIwIwIT是训练图像集，Lwi是图像iI的一组标注词。如果把图像iI看作一个文档，则iw可视为文档的关键词。对每个图像TIi，我们构造其关键词的矢量},...,,{21imiiixxxX。如果词汇表中第k个关键词ikwt，则1ikx。否则0ikx。由此我们可得到训练图像集中图像的标注词特征向量：TnXXXX...21(1)两特征向量iX，jX之间的距离定义为),(jiXXd，利用余弦距离计算),(jiXXd的值。在文本空间内，以图像标注词向量X作为特征，利用K-调和均值谱聚类算法对进行聚类，形成n个语义类),,2,1(niCi。用每个类的中心词作为该类的语义（类标签）},,{21iliii2.3图像低层特征与语义映射关系在每个语义类中，我们把图像分割成区域，提取分割后的区域的低层特征（包括形状、空间位置、颜色和纹理等）用特征矢量f表示。f采用24维矢量表示。根据区域的低层特征的相似关系，再次利用K-调和均值谱聚类算法把同一语义类中的相似区域聚类到同一个块（blob）中，形成K个块),2,1(kibi。通过优化块的个数K，使得每块内尽可能集中，块与块间距尽可能远离。为了确定最优K值，通过设置不同的K进行多次聚类，对不同的K值，计算各块之间的距离),(intjierXXd和每个块内距)(intiraXd根据Davies-Bouldin指数[11]，式（2）：),()()(max1intintint1jierjrairakijiXXdXdXdk(2)取得最小值时的K应为最优的K值，也即：),()()(max1minargintintint1jierjrairakijikXXdXdXdkk(3)从而，在每个语义类内，我们获得了k个块。这些块继承了所在类的语义iL。通过两次聚类，训练图像集T被分割成若干个语义类),,2,1(niCi，每个语义类用可用块的中心特征和该类的关键词},,{21iliii表示：};,,{21iikiiiLbbbC},,;,,{2121iliiikii(4)在一个语义类中，块ib与关键词iijLw的联合概率分布通过下式求得：)()|,(),(iiiijiijCpCbwpbwp)()|(),|(iiiiiijCpCbpCbwp(5)式中)(iCp是类iC的先验概率，),|(iiijCbwp表示类iC中关键词ijw的条件概率，根据多伯努利模型可得：||)(),|(,iijCwiiijCwNCbwpjij(6)上式中是平衡系数；如果类jC有标注词ijw，iijCw,取值为1，否则为0。)(ijwN表示标注词ijw在类iC中出现的次数，||iC表示类iC中图像个数。)|(iiCbp可能通过下式计算得到：klliiibbCbp1||||)|((7)其中||ib表示块ib中区域的个数。算法描述如下：算法2:区域块与标注词语义映射算法输入：训练图像集)},(),...,,(),,{(2211nnwIwIwIT；标注词词汇表},...,{21mtttL；输出：区域块与语义词的联合概率表),(iijbwp。Step1:对每一训练集中图像TI，提取其颜色、纹理、形状等低层特征，并组成特征向量Tiqiiiyyyy),...,,(21。根据公式（1）提取标注词特征向量LStep2:以标注词特征向量L为特征，利用K-调和均值谱聚类算法对图像进行聚类