《一种基于结构学习的图像标注方法.doc》由会员分享，可在线阅读，更多相关《一种基于结构学习的图像标注方法.doc（6页珍藏版）》请在三一办公上搜索。
1、精品论文一种基于结构学习的图像标注方法崔超然，马军（山东大学计算机科学与技术学院，济南 250101）5摘要：图像标注工作对于当前的基于关键词的图像检索系统至关重要。本文中，我们将图像 标注问题看作一个最优子集选择的问题，并通过结构学习的框架来学习一个得分函数，利用 该函数来评估不同候选标注集合的质量。一个标注集合的质量由它与待标注图像的视觉近邻 图像的多种关系来判定。在基准数据集上的实验结果证明了该方法在图像标注任务中的有效 性。10关键词：计算机应用技术；图像标注；结构学习中图分类号：TP391Image Annotation via Structural LearningCUI Chao
2、ran, Ma Jun15(School of Computer Science and Technology, Shandong University, JiNan 250101) Abstract: Image annotation plays an important role in modern keyword-based image retrieval systems. In this paper, we formulate the image annotation problem as that of selecting the optimal keyword subset for
3、 an image, and employ a structural learning framework to learn a scoring function for evaluating the quality of different candidate subsets. The quality of a keyword subset20is assessed based on its relations with visually similar neighbors of that image. Experiments on benchmark data set demonstrat
4、e the effectiveness of our approach for image annotation.Keywords: computer applied technology; image annotation; structural learning0引言25伴随着网络的发展和数字摄影技术的提高，互联网中数字图像的数目呈现出爆炸式的增 长。与此同时，这也增强了人们对高效的图像检索技术的需求。当前的商用搜索引擎仍是采 用基于文本的检索技术，通过对图像的标注信息建立索引，来为用户提供检索服务的，其检 索性能依赖于图像标注的质量。但由于人工手动地为图像添加标注是一项十分耗时耗力的工
5、作，因此，近年来研究人员开展了对自动图像标注技术的研究30自动图像标注是指机器自动地选择一组相关的标注词来反映图像的视觉内容。已有的工 作大体可以分三类，即：基于概率的方法，基于分类的方法和基于近邻的方法。基于概率的 方法旨在利用训练集来推断出图像的视觉特征和标注词之间的联合概率分布。在进行标注 时，分别计算不同的标注词相对图像的条件概率。基于分类的方法为每一个标注词训练一个 分类器从而预测该标注词是否在图像中出现。在基于近邻的方法中，算法首选在训练中找到35一组与测试图像视觉相近的“近邻”图像，然后将这些“近邻”的标注词传递给测试图像。 本质上，图像标注工作的输入是一幅图像，输出是一组标签集
6、合。因此，该问题可以被看作一个结构学习(structural learning)的问题。本文中，我们提出通过 Structural SVM1框架 来学习一个评价函数，并利用该函数评估不同的候选标签相对于给定图像的相关性。一个标 签的相关性由它和测试样本的“近邻”图像的多种关系来判定。我们采用了 Cutting Plane40算法2来求解问题中推导出的优化问题，然后利用学习到的评价函数来为测试图像选择最优基金项目：教育部博士点基金(20110131110028)作者简介：崔超然，(1987-)，男，博士研究生，主要研究领域为信息检索、多媒体信息的分析与理解。通信联系人：马军，（1956-），教授
7、，博士生导师，主要研究领域为 Web 文本和多媒体检索、社会网络。E-mail: majun- 6 -的标注词。实验中，我们在 Corel 5K 数据集上对本文提出的方法进行了评测。实验结果显示，相 比于以往方法在该数据上公布的实验结果，本文在准确率和召回率等测度上均取得了最优的 结果。451问题描述指定 X=x1,x2,.,xN代表一个图像集合，所有可能在该集合中出现的不同的标注词的集 合为 W=w1,w2,.,wM。图像标注的目标是学习一个映射 h: XY，其中 Y 代表包含所有可能的标注词集合的空间。给定一幅图像 xX，我们利用 h 为 x 预测一个合适的标注词集合 yW。在监督学习中，
8、我们会被给予一组训练样本，S=(x(i),y(i)XY: i = 1,.,T，其中 y(i)是图像50x(i)的真实标注词集合。我们希望学习到的映射函数 h 可以使得训练样本的经验损失最小化， 即1Tmin R (h) = min ( y( i ) , h( x(i ) )hShT i =1上式中，(y(i),h(x(i)代表预测标注 h(x(i)和真实标注 y(i)之间的差距。在本文中，我们将它定 义为如下形式：55( y, y ) = 1 -2 prp = | y y |p = | y y |p + r| y | y |其中，y 和 y分别代表两个标注词集合，|y|代表 y 中标签的个数，
9、|yy|表示两个集合中相 同标签的个数。本文中，我们采用 structural SVM 学习框架来解决上述问题。Structural SVM 框架的基 本思想是学习一个得分函数 F(x,y): XYR，该函数度量了候选标注集合 y 相对于给定图像60x 的相关程度。我们通过特征向量(x,y)来表示图像/标注对(x,y)。类比于线性 SVM，我们假 设得分函数 F(x,y)可以被表示为(x,y)的线性组合，即F ( x, y) = wT ( x, y)其中，w 是一个权重向量。直观上说，特征表示函数必须能较好地区别高质量和低质量的候选标注。我们将在下一节介绍的具体表示形式。65当得分函数 F(x
10、,y)确定后，映射函数 h 可以利用下式为图像 x 预测它的标注词集合y* = h( x) = arg max F (x, y)yY 遵循以往的工作3-5，实验中我们每幅图像预测 L(L = 5)个标签，因此，在上式中|y*| = L。2特征表示在本节中，我们讨论图像/标注对的联合特征表示函数。给定训练样本集，我们希望70能代表一组联合特征，使得图像和真实标注的特征与它和其它候选标注的特征的差异较 大。直观上感觉，视觉上相似的图像的内容往往反映了同一主题，因而它们更有可能会关联 到相同的标注词。从这点出发，给定一个图像/标注对(x,y)，我们首选寻找 x 在训练集中的视 觉“近邻”图像，然后再
11、根据 y 与这些“近邻”的关系来定义(x,y)。具体地，(x,y)被定 义为如下形式：1 S NN (w, NN1 ) 75 ( x, y) = | y |w y M S NNK (w, NN ) | y |wy K 其中 NN1, ., NNK 是与 x 最为相似的 K 个“近邻”图像，SNN1, ., SNNK 分别代表它们相对于 x的相似性。(w, NNi)是一个特征向量，它编码了标注词 w 和第 i 个“近邻”NNi 之间的关系。 进一步地，我们可以看到，实际上(x,y)是 K 个这样的关系分量的组合特征向量。在本文中，我们分别计算图像在不同视觉特征上的距离，并取它们的平均值作为两幅图
12、80像间最终的距离3，进而根据距离的大小选择出视觉“近邻”。我们认为“近邻”NNi 对 x的影响程度与它和 x 的相关性大小呈正相关关系。定义 NNi 相对于 x 的相关性为： 1S= expNNi1 + d (x, NN ) i 其中，d(x, NNi)是 x 和 NNi 之间归一化后的视觉距离。如上所述，(w, NNi)编码了标注词 w 和第 i 个“近邻”NNi 之间的关系。具体地，(w,85NNi)反映了 w 相对于 NNi 的以下三种关系，即出现频率，共现性以及语义相关性。根据 w 在训练集样本中的出现频率，我们可以通过多重伯努利模型(Multiple Bernoulli)6来估计用
13、 w 来标注 NNi 的概率大小，即： w, NN + TwP(w | NN ) =ii + T这里，是一个平滑参数，实验中我们通过交叉验证来确定它的取值大小。w, NNi = 1，如90果 w 出现在 NNi 的真实标注词集合中，反之，w, NNi = 0。Tw 代表训练集中含有标签 w 的图 像的数目，而 T 表示训练集中全部图像的数目。为了进一步探究标注词 w 和“近邻”图像 NNi 的相关性，我们考虑关键词之间的两种语义关系，即共现性和 WordNet 语义相关性。两个关键词之间的共现性 Sco 被定义为：S (w , w ) = tf (w1 , w2 ) ，co12tf (w2 )
14、95其中 w1 和 w2 是两个关键词，tf(w2)表示 w2 在训练集中的出现频率，tf(w1,w2)表示训练集中同 时包含 w1 和 w2 的图像的数目。此外，我们利用林氏相关度(Lins similarity measure)7来估计 两个关键词之间的 WordNet 语义相关性 Swn。根据 Sco 和 Swn 的定义，w 与 NNi 的标注之间的 共现性和 WordNet 语义相关性进而被分别定义为：Rco (w, NNi ) = max Sco (w, t )tNNi 。Rwn (w, NNi ) = max Swn (w, t )tNNi100基于上面的定义，(w, NNi)的具
15、体的形式是一个三维向量，即： P(w | NNi ) (w, NNi ) = Rco (w, NNi ) 。 Rwn (w, NNi )因此，当我们考虑 x 的 K 个“近邻图像”时，联合特征向量(x,y)的总维度是 3K。3基于 Structural SVM 的学习过程算法 1 Cutting plane 算法 输入：(x(1), y(1), ., (x(T), y(T), C, 输出：w1. 初始化 Wi for all i=1,.,T2. 重复3. for i = 1, ., T doi4. H ( y; w) ( y ( i ) , y) + wT ( x( i ) , y)5. 计算
16、y* = arg max yY H ( y; w)6. 计算i = max0, max yWH ( y; w)7. if8.H ( y*; w) i + Wi Wi y*T9.重新求解优化目标min 1 | w |2 + Ci10. end if11. end for12. 直到 没有 Wi 在本轮迭代中改变13. 返回 ww, 0 2n i =1算法 2 贪心标签子集选择算法输入：(x(i), y(i), w, L输出：y*1. 初始化y* 2. V ( x, y, y) ( y, y) + wT ( x, y)3. for k =1,., L4. ( i ) (i )t* arg maxt
17、y V (x5. y y t*, y , y t)1056. end for7. 返回 y*在本节中，我们利用 Structural SVM 来训练一个图像标注模型。给定一组训练样本， S=(x(i),y(i)XY: i = 1,.,T，Structural SVM 通过求解下面的优化问题来得到最优的权重 向量 w1：优化问题 1. (Structural SVM)110min 1 | w |2 + CTisubjected to:w, 0 2i, y Y y(i ) :n i =1iwT ( x(i ) , y(i ) ) wT (x( i ) , y) + ( y(i ) , y) 115
18、上式中，每一幅图像的每一个不正确的标注候选项均对应一个约束条件。因此，该优化问题 总共涉及到关键词个数的指数次方个约束条件。在本文中，我们采用 cutting plane 算法2来 解决该问题，过程如算法 1 所示。该算法旨在找到一个全部约束的子集，使得满足该子集中120125约束的解同时也能在一定误差率下满足全部约束。算法为每一个训练样本(x(i),y(i)寻找能产生 最违反的约束条件的候选标注集 y*(算法 5 行)。如果此时的解违反约束子集的程度超过， 则算法将 y*加入到结合 Wi 中，然后求解这一修改后的优化问题(算法 7-10 行)。算法 1 中，我们需要在每一轮中迭代中寻找最违反
19、的约束条件，即求解下面的优化问题：arg max ( y( i ) , y) + wT ( x(i ) , y)yY本文中，我们提出了一个简单而有效的贪心算法来解决该问题，如算法 2 所示。算法不断的选择能给当前的标注集合 y*带来最大收益标注词 t*，并将 t*加入到 y*直到 y*中标注词的个 数达到 L。同时，该贪心算法也被用来在测试时为新图像预测它的标注词集合。4实验Tab. 1 不同方法的标注结果的比较P% R% N+MSC4 25JEC3 27LASSO3 24GS5 30Our Method 3132 13632 13929 12733 14636 151130135140145
20、4.1实验设置实验中，我们采用了 Corel 5K 数据集。该数据被广泛应用在以往的图像标注工作中， 因而我们可以与以往工作的结果进行直接比较。对于每幅图像，我们提取了与文献3所述 相同的特征描述。为了评价方法给出的预测标注的性能，我们以每一个关键词为查询进行图 像检索操作，取各查询结果的平均准确率(P)和平均召回率(R)作为两个评价指标。同时，我 们也考虑了结果中非零召回率的查询的个数(N+)。实验中，我们为每幅图像选取 K=100 个 “近邻”图像。4.2实验结果我们将本文提出的方法与以往的多个算法进行了比较，比较结果如表 1 所示。相比于 JEC3方法，尽管我们的方法与它采用了相同的视觉
21、特征来计算“近邻”图像，但却在 P，R 和 N+三个测度上分别提高了 4%，4%和 12。同时，相比于以往方法中其他复杂模型的结果， 如 MSC4，LASSO3和 GS5，我们的方法也取得了最好的效果，这证明了本文提出的基于 结构学习的图像标注方法的有效性。5结论本文给出了一种基于结构学习的自动图像标注方法。在本文中，图像标注问题被看作一 个结构学习的问题。我们提出通过 Structural SVM 框架来学习一个评价函数，并利用该函数 来评估不同的候选标签相对于给定图像的相关性。在基准数据集上的实验结果显示，相比于 以往方法公布的实验结果，本文在准确率和召回率等测度上均取得了最优的结果。参考
22、文献 (References)1501 I. TSOCHANTARIDIS, T. JOACHIMS, T. HOFMANN, Y. ALTUN. Large margin methods for structured and interdependent output variablesJ. Journal of Machine Learning Research, 2006, 6: 1453.2 T. JOACHIMS, T. FINLEY. Cutting-plane training of structural svmsJ. Machine Learning, 2009, 77: 27
23、-59. 3 A. MAKADIA, V. PAVLOVIC, S. KUMAR. A new baseline for image annotationA. Proceedings of the 10th155160european conference on computer visionC. Marseille, France4 WANG C, YAN S, ZHANG L, ZHANG H J. Multi-label sparse coding for automatic image annotationA. Proceedings of the 22nd IEEE Computer
24、 Society Conference on Computer Vision and Pattern RecognitionC. Miami, Florida, USA5 ZHANG S, HUANG J, HUANG Y, YU Y, LI H. Automatic image annotation using group sparsityA. Proceedings of the 23rd IEEE Computer Society Conference on Computer Vision and Pattern RecognitionC. SanFrancisco, USA6 FENG
25、 S L, R. MANMATHA, V. LAVRENKO. Multiple bernoulli relevance models for image and video annotationA. Proceedings of the 17th IEEE Computer Society Conference on Computer Vision and Pattern RecognitionC. Washington, DC, USA7 LIN D. An information-theoretic definition of similarityA. Proceedings of the 15th International Conference on Machine LearningC. Alberta, Canada
