摘  要：针对图像检索中的语义鸿沟问题，提出一种新颖的自动图像标注方法。该方法首先采用了一种基于软约束的半监督图像聚类算法（SHMRF-Kmeans）对已标注图像的区域进行语义聚类，这种半监督的聚类方法可以同时考虑图像的视觉信息和语义信息，并结合概率模型和基于图的学习算法--Manifold排序学习算法充分发掘语义概念与区域聚类中心的关系，并得到其概率关系表。然后可以利用已学习好的语义概念-区域聚类中心的概率关系表标注未知标注的图像，并依此构建了图像检索系统。该方法与以前的方法相比可以更加充分地结合图像的视觉特征和高层语义。通过在通用图像集上的实验表明，本文提出的自动图像标注方法是有效的，构建的图像检索系统具有较好的检索性能。
关键词：半监督聚类；软约束；图像标注；Manifold排序学习

1  引  言
   自动图像标注是基于内容图像检索中重要而具有挑战性的工作。它可以利用已标注的图像集自动学习语义概念空间与视觉特征空间的关系模型，并用此模型标注未知语义的图像，即它试图给高层语义特征和底层视觉特征之间建立一座桥梁。因此，它可以一定程度解决大多基于内容图像检索方法存在的语义鸿沟问题。如果能实现自动图像标注,那么现有的图像检索问题实际上就可以转化成技术已经相当成熟的文本检索问题。它的潜在应用领域包括生物医学、商业、军事、教育、数字图书馆和互联网检索等。
   本文提出一种新颖的自动图像标注框架，并在此基础上构建了图像检索系统。其主要思想是：首先将已标注图像集分割为图像区域，再利用提出的基于软约束的半监督图像聚类算法（SHMRF-Kmeans）对图像区域进行语义聚类，实现图像区域的简化表示，即图像集在图像空间中的量化表示，每个子类称为blob[1]。然后结合概率模型和Manifold排序学习算法[2]建立语义概念和blobs之间的概率关系。当有未标注的图像时，通过判断其区域所属的blob即可利用此概率关系进行自动标注。

2  相关工作
   基于内容的图像检索近十几年来得到了研究者的关注，一系列的基于内容的图像检索方法和检索系统被提出来[13]。然而由于图像底层的视觉特征和高层语义存在不一致性，即所谓的“语义鸿沟”。由于自动图像标注可以缓解这一问题，所以得到了研究者的极大关注。
   自动图像标注的一个方向是采用分类方法，每一个语义概念被当作一个类别进行分类。代表方法有：SVM方法[11]，贝叶斯点机方法[12]等等。这种方法当语义概念相当多时会遇到困难。
   自动图像标注的另一个方向是建立图像和语义概念的统计概率模型。Duygulu等提出的翻译模型（TM）[9]，模型利用传统的语言统计翻译模型将语义概念翻译为由图像区域聚类产生的blobs。Jeon等介绍了一种交叉媒体相关模型（CMRM）[5]，将图像标注问题看作跨语言检索问题，模型通过计算blobs和语义概念的联合概率进行图像标注，获得了比较好的效果。但是这类概率的方法对语义和图像特征的利用比较粗糙，两者的结合不是很紧密。而且，这类方法对图像区域聚类结果的好坏比较敏感。

3  自动图像标注框架
3.1  框架结构
   本文提出的自动图像标注的框架见图1 ，其主要基于两种技术：基于软约束的半监督图像聚类算法--SHMRF-Kmeans算法和Manifold排序学习算法。

图1 自动图像标注框架

   基于约束的半监督聚类是在加有数据间的约束数据集上实现聚类的方法。约束的种类主要有：正关联约束（must-link constraint），它表示两数据点必须归于同一类别；负关联约束（cannot-link constraint），它表示两数据点不能归于同一类别。软约束是相对于硬约束来说，它是在硬约束基础上加上了强度因子，表示约束的强度。比起硬约束，软约束可以更好的表达数据间的约束关系。
   本文提出的基于软约束的半监督图像聚类算法SHMRF-Kmeans，其基本思想是利用隐马尔科夫随机场模型结合了基于约束的方法实现在数据软约束条件下的聚类。算法首先利用隐马尔科夫随机场模型的先验能量建立聚类的目标函数，然后利用EM算法计算目标函数的最小值，实现聚类。由于软约束是根据已知的图像标注确定的，所以SHMRF-Kmeans算法对图像区域聚类的结果同时利用了图像的视觉信息和语义信息，改善了图像区域聚类效果，可以给基于区域聚类的图像标注方法的下一步工作奠定良好的基础。本文算法是对Basu等[3]工作的延伸。算法细节将在3.2节介绍。
   Manifold排序学习算法是一种基于图的算法，起初是用于发掘数据的特性和内在维数的方法。本文中，由于一般的概率模型无法充分利用blob之间和blob与概念间的深层关系，所以提出利用概率模型先计算出blob与概念间的初始概率关系表T(0)，然后利用Manifold排序学习算法通过叠代充分发掘数据间的关系得到最终的概率关系表。算法细节将在3.3节介绍。
3.2  SHMRF-Kmeans的描述
3.2.1  软约束的描述
   软约束可以表示为(A,B,S) 。当S>0时，表示A与B存在正关联约束，强度因子为S，表明A，B属于同一类别的概率为S；同理，当S<0时，表示a与b存在负关联约束，强度因子为-s，表明a，b不属于同一类别的概率为-s。
   软约束的强度因子可以采用下式计算：

   其中D为图像区域A，B的标注的语义距离。这里我们定义了上下两个阈值，如果D在阈值范围之外，则会形成一个软约束。LIN方法[4]可以计算词与词之间的语义距离，它采用了信息熵理论和WordNet词典可以计算出两个单词间的语义距离。本文利用LIN方法首先计算出单词间的语义距离，进而计算出图像区域对应标注之间的语义距离。
3.2.2  目标函数
   聚类的目标函数[3]可以表示为：

   其中M表示正关联约束集合，C表示负关联约束集合。是在Xi和Xj之间违反正关联/负关联约束的代价权重，li是Xi所属于的类标记。是类li的代表元素。I是指示函数（〔I〔true〕=1, I〔false〕=0〕）。可以看出该目标函数中第一个项是标准的K均值目标函数；第二项是违背正关联约束的惩罚函数；而第三个是违背负关联约束的惩罚函数。
   但是，此目标函数不能处理软约束。这里采用了指示函数法来修改目标函数以使它可以处理软约束。
   在原始的目标函数中，指示函数I(a)是一个二值函数。为了处理软约束，指示函数被修改成一个范围从0到1的连续函数I'(a)。当a的值是真时，连续指示函数I'(a)的值与强度因子S的绝对值相等，即（〔I〔true〕=S, I〔false〕=0〕）。因此在修改过的目标函数中，惩罚值与强度因子S的绝对值是成比例的。
3.2.3  算法步骤
   SHMRF-Kmeans算法目标是使总的惩罚值最小。这一目标是通过类似EM算法的方法使目标函数值到达局部最小达到的。在E步，给定当前类的重心，每个数据点重新分配给使其对目标函数值最小的类；在M步，利用目标函数值重新估计每一类的中心。E步和M步叠代进行直到算法收敛。
3.3  Manifold排序学习算法描述
3.3.1  初始概率表生成
   本文采用类似于CMRM[5]的概率模型。定义为区域聚类中心blob的集合，为所有标注的集合。r为训练图像集合，。于是可以确定任意blob与标注概念的联合概率：

其中

其中代表图像J的标注中单词w出现的次数。代表单词w在训练基中总共出现的次数。反映了blob b在图像J中出现的次数。反映了blob b在训练基中总共出现的次数。等于图像J中blob数和标注数的总和。为训练集的大小。平滑系数。
3.3.2   Manifold排序学习算法
   上文的概率模型只考虑了标注与图像的关系和blob与图像的关系，而忽略了blob之间和标注之间的关系，没能紧密结合图像的视觉特征和高层语义，显然只利用概率模型不能得到比较好的结果。因此，Manifold排序学习算法由于可以挖掘数据间的深层关系而被用来计算概率表T，并且选取概率模型的结果为初始值。
   定义(x是blob的特征，m是x的维数)，为所有标注的集合。Manifold排序的算法过程见图2。其直观的描述是：首先把每个数据点作为顶点建立一张加权图。然后每个数据点传递自己的概率值给在加权图中的邻顶点，也就是概率值在相似度比较高的顶点间传递。这种概率值的传递可以反映了所有数据之间的关系：在特征空间中，距离较远的顶点会具有不同的概率值，而距离近的顶点会分享相近的概率值。这恰好满足了自动图像标注问题的需求。

图2 Manifold 排序算法

   确定相似度矩阵 是本算法的关键之一。距离度量 一般采用L2距离。但是前人的工作[6-7]表明，在通过图像特征比较图像时L1距离可以更好的表达图像间的视觉差异。因此，本文采用L1距离测度替代L2距离，并采用拉普拉斯核表示的相似度矩阵：

4  实验结果与分析
4.1  数据集
   实验图像数据集采用Duygulu等[8-9]提供的两组Corel图像集：
   ECCV 2002：近年来此数据集已成为图像标注领域的通用图像库。图像数据集由Corel图像集中的5000幅图像组成。图像分割算法采用Normalized Cut[10]算法，确保对每幅图像有1到10个blobs，最终有47065个图像区域。每幅图像标注1到5个关键词。图像集一共有374个词，把数据集分成2个部分——4500幅图像作为训练集和500幅图像作为测试集。测试集中包含260个单词。
   JMLR 2003：共有10组Corel图像集，每组包括5000多幅图像,共约16000幅图像。每组图像集大约有50000个区域，聚类后有500个blob。每组图像集大约有165个单词。每组数据集分成2个部分——约75%的图像作为训练集和约25%的图像作为测试集。图像特征提取于ECCV 2002图像库相同。
4.2  自动图像标注
   测试集图像也需要分割为区域，并通过相似度比较确定其属于的blob类别，然后利用语义概念-blob概率表T求出其与所有单词的联合概率，最后从中选出概率值最大的五个单词作为测试图像的标注。采用查准率、查全率和F1值衡量实验结果。查准率定义为查询结果中正确结果的比例；查全率定义为查询结果中正确结果占数据库中正确结果的比例；F1值定义：2*查准率*查全率/（查准率+查全率）。表1给出49个最好标注结果的平均性能[5]，本文的方法在与TM、CMRM算法相比时标注的查准率、查全率和F1值上都有提高。

表1 自动图像标注性能比较

   表2是一些标注结果，并与TM、CMRM方法的结果做了比较。

表2 自动注果（最好的5个）与人工注释结果比较

4.3  基于自动图像标注的图像检索
   图3给出了三种图像检索系统在标注了的测试图像集上的检索结果。实验比较了本文方法和CMRM方法对应的图像检索系统在查询为三个单词时的性能。从实验结果可见，本文的方法还是很有效的。

图3  图像检索系统的查准率-查全率图

5  总  结
   针对图像检索中的语义鸿沟问题，本文提出一种新颖的图像标注方法。该方法试图改变前人方法中图像视觉特征和高层语义结合不紧密的问题。提出了一种基于软约束的半监督图像聚类算法（SHMRF-Kmeans）对已标注图像的区域进行语义聚类，这种半监督的聚类方法可以同时考虑图像的视觉信息和语义特征；并提出将概率模型和基于图的算法--Manifold排序学习算法结合起来充分发掘语义概念与区域聚类中心的关系，并得到其概率关系表。在一个55000多幅图像的数据集上进行实验，并与TM[9]、CMRM[5]方法进行了比较，实验结果表明该方法能够获得更好的查全率和查准率。

参 考 文 献
[1] Carson C, Thomas M, et al. Blobworld: A system for region-based image indexing and retrieval[C], Third International Conference on Visual Information Systems, 1999, 509~516
[2] Zhou D, Bousquet O, et al. Learning with local and global consistency[c], Advances in Neural Information Processing Systems, 2004, 321~328
[3] Basu S, Bilenko M, Mooney R J. A probabilistic framework for semi-supervised clustering[C]. Proceedings of the 2004 ACM SIGKDD international conference on Knowledge discovery and data mining, 2004,59～68
[4] Lin D. Using syntactic dependency as local context to resolve word sense ambiguity[C]. Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics, 1997, 64～71
[5] J.jeon, v.Lavernko, R.Manmatha, Automatic image annotation and retrieval using cross-media relevance models[C], Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, 2003, 119—126
[6] Kokare M, Chatterji B.N., and Biswas P.K, Comparison of similarity metrics for texture image retrieval[C], IEEE Conf. on Convergent Technologies for Asia-Pacific Region, vol. 2, pp.571-575, 2003.
[7] Stricker M., Orengo M., Similarity of color images[C], Storage and Retrieval for Image and Video Databases, Proc. SPIE 2420, pp 381-392, 1995.
[8] Barnard K, Duygulu P, Matching words and pictures[J], Journal of Machine Learning Research, MIT Press, 2003, 1107~1135
[9] Duygulu P, Barnard K, De F N, et al. Object recognition as machine translation: Learning a lexicon for a fixed image vocabulary[C]. Seventh European Conference on Computer Vision , 2002, 4: 97～112
[10]Shi J, Malik J. Normalized Cuts and Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888～905
[11]Claudio, C., Gianluigi, C., Raimondo, S. Image annotation using SVM[C], In Proceeding Of Internet imaging IV, Vol. SPIE, 2004.
[12]Edward Chang, Kingshy Goh, Gerard Sychay, Gang Wu, CBSA: content-base soft annotation for multimodal image retrieval using bayes point machines. CirSysVideo, pp. 26-38, 13(1), 2003.
[13]章毓晋，基于内容的视觉信息检索，北京：科学出版社，2003