第9卷第1期 智能系统学报 Vol.9 No.1 2014年2月 CAAI Transactions on Intelligent Systems Feb.2014 D0:10.3969/j.issn.1673-4785.201303021 网络出版地址：http://www.cnki.net/kcms/doi/10.3969/j.issn.1673-4785.201303021.html 有监督全局流形排序的图像检索算法 练浩，曾宪华，李淑芳 (重庆邮电大学计算智能重庆市重点实验室，重庆400065) 摘要：针对流形排序图像检索中无正反馈标记的查询查准率为零时，查询无法得到改善的情况，提出了有监督全 局流形排序图像检索算法(SG-MRBR)。该算法充分利用图像库中图像的局部与非局部的几何分布信息、标记信息 以及用户的查询反馈信息来提高检索性能，并且通过不相关排序对检索到的相关排序向量进行校正，改善了第一次 查询查准率为零的情况。在MSRA-MM图像库上的实验表明，SG-MRBR算法明显改善了图像检索性能，特别是第 一次用户反馈后就使得平均查准率与广义流形排序图像检索算法(G-MRBIR)相比有所提高，说明了该算法的有效 性和优越性。 关键词：流形学习：图像检索算法：流形排序：有监督流形排序：不相关排序 中图分类号：TP391文献标志码：A文章编号：1673-4785(2014)01-0092-06 中文引用格式：练浩，曾宪华，李淑芳.有监督全局流形排序的图像检索算法[J].智能系统学报，2014,9(1)：92-97. 英文引用格式：LIAN Hao,ZENG Xianhua,LI Shufang.Supervised global manifold ranking based image retrieval algorithm[J】. CAAI Transactions on Intelligent Systems,2014,9(1):92-97. Supervised global manifold ranking based image retrieval algorithm LIAN Hao,ZENG Xianhua,LI Shufang (Chongqing Key Laboratory of Computational Intelligence,Chongqing University of Posts and Telecommunications,Chongqing 400065, China) Abstract:In manifold ranking based image retrieval,if there is no positive feedback,the situation where the preci- sion ratio is zero can not be changed.So a new supervised global manifold ranking based image retrieval(SG-MR- BIR)algorithm is proposed.For improving the image retrieval performance,this algorithm fully applies the local and non-local geometrical distribution of image datasets,image label information and user's related feedback infor- mation.And the related ranking vectors of the retrieved image are corrected by using uncorrelated ranking.Finally, the situation where the first query precision is zero is improved.The experimental results for the MSRA-MM image database show that our SG-MRBIR algorithm distinctly improves the image retrieval performance.Especially,after the first feedback by users in the experiments,the average precision ratio of retrieving was increased as compared with the generalized manifold ranking based image retrieval(G-MRBIR)algorithm.This verifies the effectiveness and superiority of this algorithm. Keywords:manifold learning;image retrieval algorithm;manifold ranking;supervised manifold ranking;uncorre- lated ranking 基于内容的图像检索(content based image re- 化特征和用户语义概念之间的“语义鸿沟”问题] trieval,CBIR)技术是为了解决如何有效地从图 以及“维度灾难”问题，严重限制了检索性能的提 像数据库中检索出相关图像的技术。通常CBR中 高。流形学习能够发现图像数据集内在的几何分布 图像的表示是基于底层可视化特征，而这种表示方 规律)，不但能找出图像间内在的语义关系还能进 法不能直接表达用户的语义，因此出现了底层可视 行维数约减，已被广泛应用到图像检索问题中46。 将用户反馈的语义融入到流形学习过程中能提高图 收稿日期：2013-03-14.网络出版日期：2014-02-20. 像检索性能[)，流形排序(manifold ranking,MR)[s劉 基金项目：国家自然科学基金资助项目(61075019,61203308)：重庆 市自然科学基金资助项目(CSTC-2010BB2406). 就是一类融入用户反馈信息的基于拓扑图的图像检 通信作者：曾宪华.E-mail:xianhuazeng(@gmail.com 索排序算法。传统的基于流形排序的图像检索
第 ９ 卷第 １ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．１ ２０１４ 年 ２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｆｅｂ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３０３０２１ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｏｉ ／ １０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３０３０２１．ｈｔｍｌ 有监督全局流形排序的图像检索算法 练浩，曾宪华，李淑芳 （重庆邮电大学 计算智能重庆市重点实验室，重庆 ４０００６５） 摘 要：针对流形排序图像检索中无正反馈标记的查询查准率为零时，查询无法得到改善的情况，提出了有监督全 局流形排序图像检索算法（ＳＧ⁃ＭＲＢＩＲ）。 该算法充分利用图像库中图像的局部与非局部的几何分布信息、标记信息 以及用户的查询反馈信息来提高检索性能，并且通过不相关排序对检索到的相关排序向量进行校正，改善了第一次 查询查准率为零的情况。 在 ＭＳＲＡ⁃ＭＭ 图像库上的实验表明，ＳＧ⁃ＭＲＢＩＲ 算法明显改善了图像检索性能，特别是第 一次用户反馈后就使得平均查准率与广义流形排序图像检索算法（Ｇ⁃ＭＲＢＩＲ）相比有所提高，说明了该算法的有效 性和优越性。 关键词：流形学习；图像检索算法；流形排序；有监督流形排序；不相关排序 中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０１⁃００９２⁃０６ 中文引用格式：练浩，曾宪华，李淑芳．有监督全局流形排序的图像检索算法［Ｊ］． 智能系统学报， ２０１４， ９（１）： ９２⁃９７． 英文引用格式：ＬＩＡＮ Ｈａｏ， ＺＥＮＧ Ｘｉａｎｈｕａ， ＬＩ Ｓｈｕｆａｎｇ． Ｓｕｐｅｒｖｉｓｅｄ ｇｌｏｂａｌ ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（１）： ９２⁃９７． Ｓｕｐｅｒｖｉｓｅｄ ｇｌｏｂａｌ ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ａｌｇｏｒｉｔｈｍ ＬＩＡＮ Ｈａｏ， ＺＥＮＧ Ｘｉａｎｈｕａ， ＬＩ Ｓｈｕｆａｎｇ （Ｃｈｏｎｇｑｉｎｇ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｃｈｏｎｇｑｉｎｇ ４０００６５， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ， ｉｆ ｔｈｅｒｅ ｉｓ ｎｏ ｐｏｓｉｔｉｖｅ ｆｅｅｄｂａｃｋ， ｔｈｅ ｓｉｔｕａｔｉｏｎ ｗｈｅｒｅ ｔｈｅ ｐｒｅｃｉ⁃ ｓｉｏｎ ｒａｔｉｏ ｉｓ ｚｅｒｏ ｃａｎ ｎｏｔ ｂｅ ｃｈａｎｇｅｄ． Ｓｏ ａ ｎｅｗ ｓｕｐｅｒｖｉｓｅｄ ｇｌｏｂａｌ ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ （ＳＧ⁃ＭＲ⁃ ＢＩＲ） ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ． Ｆｏｒ ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ｐｅｒｆｏｒｍａｎｃｅ， ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｆｕｌｌｙ ａｐｐｌｉｅｓ ｔｈｅ ｌｏｃａｌ ａｎｄ ｎｏｎ⁃ｌｏｃａｌ ｇｅｏｍｅｔｒｉｃａｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｉｍａｇｅ ｄａｔａｓｅｔｓ， ｉｍａｇｅ ｌａｂｅｌ ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ ｕｓｅｒｓ ｒｅｌａｔｅｄ ｆｅｅｄｂａｃｋ ｉｎｆｏｒ⁃ ｍａｔｉｏｎ． Ａｎｄ ｔｈｅ ｒｅｌａｔｅｄ ｒａｎｋｉｎｇ ｖｅｃｔｏｒｓ ｏｆ ｔｈｅ ｒｅｔｒｉｅｖｅｄ ｉｍａｇｅ ａｒｅ ｃｏｒｒｅｃｔｅｄ ｂｙ ｕｓｉｎｇ ｕｎｃｏｒｒｅｌａｔｅｄ ｒａｎｋｉｎｇ． Ｆｉｎａｌｌｙ， ｔｈｅ ｓｉｔｕａｔｉｏｎ ｗｈｅｒｅ ｔｈｅ ｆｉｒｓｔ ｑｕｅｒｙ ｐｒｅｃｉｓｉｏｎ ｉｓ ｚｅｒｏ ｉｓ ｉｍｐｒｏｖｅｄ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｆｏｒ ｔｈｅ ＭＳＲＡ⁃ＭＭ ｉｍａｇｅ ｄａｔａｂａｓｅ ｓｈｏｗ ｔｈａｔ ｏｕｒ ＳＧ⁃ＭＲＢＩＲ ａｌｇｏｒｉｔｈｍ ｄｉｓｔｉｎｃｔｌｙ ｉｍｐｒｏｖｅｓ ｔｈｅ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ｐｅｒｆｏｒｍａｎｃｅ． Ｅｓｐｅｃｉａｌｌｙ， ａｆｔｅｒ ｔｈｅ ｆｉｒｓｔ ｆｅｅｄｂａｃｋ ｂｙ ｕｓｅｒｓ ｉｎ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ， ｔｈｅ ａｖｅｒａｇｅ ｐｒｅｃｉｓｉｏｎ ｒａｔｉｏ ｏｆ ｒｅｔｒｉｅｖｉｎｇ ｗａｓ ｉｎｃｒｅａｓｅｄ ａｓ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｇｅｎｅｒａｌｉｚｅｄ ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ （Ｇ⁃ＭＲＢＩＲ） ａｌｇｏｒｉｔｈｍ． Ｔｈｉｓ ｖｅｒｉｆｉｅｓ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ａｎｄ ｓｕｐｅｒｉｏｒｉｔｙ ｏｆ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｍａｎｉｆｏｌｄ ｌｅａｒｎｉｎｇ； ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ａｌｇｏｒｉｔｈｍ； ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ； ｓｕｐｅｒｖｉｓｅｄ ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ； ｕｎｃｏｒｒｅ⁃ ｌａｔｅｄ ｒａｎｋｉｎｇ 收稿日期：２０１３⁃０３⁃１４． 网络出版日期：２０１４⁃０２⁃２０． 基金项目：国家自然科学基金资助项目（ ６１０７５０１９，６１２０３３０８）；重庆 市自然科学基金资助项目（ＣＳＴＣ⁃２０１０ＢＢ２４０６）． 通信作者：曾宪华． Ｅ⁃ｍａｉｌ：ｘｉａｎｈｕａｚｅｎｇ＠ ｇｍａｉｌ．ｃｏｍ． 基于内容的图像检索（ ｃｏｎｔｅｎｔ ｂａｓｅｄ ｉｍａｇｅ ｒｅ⁃ ｔｒｉｅｖａｌ， ＣＢＩＲ）技术［１］ 是为了解决如何有效地从图 像数据库中检索出相关图像的技术。 通常 ＣＢＩＲ 中 图像的表示是基于底层可视化特征，而这种表示方 法不能直接表达用户的语义，因此出现了底层可视 化特征和用户语义概念之间的“语义鸿沟”问题［２］ 以及“维度灾难” 问题，严重限制了检索性能的提 高。 流形学习能够发现图像数据集内在的几何分布 规律［３］ ，不但能找出图像间内在的语义关系还能进 行维数约减，已被广泛应用到图像检索问题中［４⁃６］ 。 将用户反馈的语义融入到流形学习过程中能提高图 像检索性能［７］ ，流形排序（ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ， ＭＲ） ［８］ 就是一类融入用户反馈信息的基于拓扑图的图像检 索排序算法。 传统的基于流形排序的图像检索
第1期 练浩，等：有监督全局流形排序的图像检索算法 ·93. (manifold ranking based image retrieval,MRBIR)[9] 式中：a为比例系数（常数）。获得一个与图像库X 对于查询图像位于数据库之外时，需要重新计算拓 对应的排序向量∫=[∫∫2…f]',根据∫值大 扑图，因此在线查询时效率低。在此基础上提出的 小的排序结果，判断查询样例图像跟待检索图像间 广义流形排序图像检索算法(generalized manifold 的相似度，将与查询样例最相关的图像作为检索结 ranking based image retrieval,G-MRBIR)[oj及其变 果反馈给用户。 种EMR(efficient manifold ranking))通过重复利用 5)用户如果对查询结果不满意，则根据相关和 离线计算的近邻相似矩阵，大大减少了计算量，能有 不相关对图像进行标记，得到新的y,再返回步骤 效地应用于在线图像检索。考虑到图像数据库中的 4),否则查询结束。 图像很多时候是已经有分类标记的或者部分图像是 对于f的计算可以用式子f=(1-a)(I-aS)1y 有标记的，如人、动物、建筑、风景等，这些标记信息 近似代替[8)，其中a为常数，I为单位阵，同时用如 可以融入流形排序算法中，因此提出有监督和半监 下∫近似代替也不影响最后排序结果。 督的流形排序算法，可以提高图像检索的查准率：但 f=(I-aS)y (3) 是当用户查询结果的反馈是在无正反馈的情况下， 1.2广义流形排序图像检索算法 用户语义却不能进一步改进流形排序算法的查询结 流形排序图像检索算法(MRBR)的不足是每 果，针对这种情况，从全局出发引入不相关排序来校 次处理数据库外的图像时，需要重新计算n×n的相 正检索图像对应的相关排序向量，从而获得进一步 似矩阵S,尤其是同样大小的矩阵I-aS的逆矩阵 优化的排序结果。这就提出了一种新的有监督全局 A=(I-aS)的计算，会使在线检索时间较长。但是 流形排序的图像检索算法(supervised global mani- 广义流形排序算法(G-MRBIR)[O]能够避免这种问 fold ranking based image retrieval,SG-MRBIR), 题。G-MRBIR相当于首先通过欧式距离找到图像 利用了图像库的局部与非局部的几何分布信息、标 数据集外的查询图像x。在图像数据集X={x1,x2, 记信息以及用户的查询反馈信息，以进一步提高图 …,xn}内相关的前m幅图像{x,i=1,2,…,m},相 像检索的查准率，并在著名的MSRA-MM图像库上 应的权值e(i)=exp[-d(xo,x)/2c2],剩余的e(i) 进行对比实验来验证本文算法的性能。 取0，对e归一化处理后得到排序向量： f=a(I-aS)e (4) 1基于流形排序的图像检索 与流形排序不同的是，在面对图像数据集外新 1.1流形排序图像检索算法 的待查询图像，利用相关反馈方法不用再重新计算 基于流形排序算法应用于图像检索中的基本思 S与A=(I-aS)-1了，具体步骤如下。 想是：首先对图像库中的图像构建近邻连通图，然后 1)通过式(4)求得初始流形排序f。,即 通过此图将查询样例的值传播给其他每个节点，最 fo=a(I-aS)e (5) 后每个节点都会得到一个排序值，被排序数据便可 2)对反馈的第i幅图像用y:°=1或-1进行标 以基于此值排序)。设图像数据库表示为X={x, 记，如果反馈的图像用户判断与查询图像是相关的 x2,…,xg,xg+1,…,xn},其中x1,x2,…,x,表示数据 就标记为1，否则标记为-1。这样就对反馈的前k 库中的q幅样例图像，x,+1,x,2,…,x表示n-q幅待 幅（实际检索中一般取10~30幅是可以接受的）最 检索的图像，在所有图像上实施如下步骤： 相近图像进行了标记，其他未标记的设为0。首先， 1I)构建k最近邻(k-nearest neighbor,k-NN)图。 计算正相关向量y和负相关向量y分别为 2)计算k-NN图中节点间边的权值，求得相似 片=/八，为=1 矩阵W,计算公式为 0,y=0,-1 W(i,j)=exp[-d(xo,x)/202] (1) (-1,y=-1 式中：σ是热核常数。 y:= (0,y=0,1 3)正则化得到相似矩阵S,即S=D-2wD-2」 然后计算正相关排序向量广=Ay*和负相关排序向 其中D是对角矩阵，D(i,i)为矩阵W的第i行或 量∫=Ay,求得最终的流形排序∫为 列和。 f=f。+(1-m)f+f,0<m<1 (6) 4)根据用户相关性反馈y更新排序向量∫，其 式中：n=exp(-7,),n为y*中元素为1的个数。 中将检索到与查询图像相关图像的对应元素y:设置 3)如果用户对结果不满意，则返回步骤2)，可 为1，否则为0。排序向量∫的更新迭代式为 以对反馈的图像中未标记的图像重新用同样的方法 f(t+1)=aSf(t)+(1-a)y (2) 进行标记，得到新的y与y,在不需重新计算S与
（ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ， ＭＲＢＩＲ） ［９］ 对于查询图像位于数据库之外时，需要重新计算拓 扑图，因此在线查询时效率低。 在此基础上提出的 广义流形排序图像检索算法（ ｇｅｎｅｒａｌｉｚｅｄ ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ， Ｇ⁃ＭＲＢＩＲ） ［１０］ 及其变 种 ＥＭＲ（ｅｆｆｉｃｉｅｎｔ ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ） ［１１］通过重复利用 离线计算的近邻相似矩阵，大大减少了计算量，能有 效地应用于在线图像检索。 考虑到图像数据库中的 图像很多时候是已经有分类标记的或者部分图像是 有标记的，如人、动物、建筑、风景等，这些标记信息 可以融入流形排序算法中，因此提出有监督和半监 督的流形排序算法，可以提高图像检索的查准率；但 是当用户查询结果的反馈是在无正反馈的情况下， 用户语义却不能进一步改进流形排序算法的查询结 果，针对这种情况，从全局出发引入不相关排序来校 正检索图像对应的相关排序向量，从而获得进一步 优化的排序结果。 这就提出了一种新的有监督全局 流形排序的图像检索算法（ ｓｕｐｅｒｖｉｓｅｄ ｇｌｏｂａｌ ｍａｎｉ⁃ ｆｏｌｄ ｒａｎｋｉｎｇ ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ， ＳＧ⁃ＭＲＢＩＲ），充分 利用了图像库的局部与非局部的几何分布信息、标 记信息以及用户的查询反馈信息，以进一步提高图 像检索的查准率，并在著名的 ＭＳＲＡ⁃ＭＭ 图像库上 进行对比实验来验证本文算法的性能。 １ 基于流形排序的图像检索 １．１ 流形排序图像检索算法 基于流形排序算法应用于图像检索中的基本思 想是：首先对图像库中的图像构建近邻连通图，然后 通过此图将查询样例的值传播给其他每个节点，最 后每个节点都会得到一个排序值，被排序数据便可 以基于此值排序［７］ 。 设图像数据库表示为 Ｘ ＝ ｛ ｘ１ ， ｘ２ ，…，ｘｑ， ｘｑ ＋１ ，…，ｘｎ ｝，其中 ｘ１ ，ｘ２ ，…，ｘｑ表示数据 库中的 ｑ 幅样例图像，ｘｑ ＋１ ，ｘｑ＋２ ，…，ｘｎ表示 ｎ－ｑ 幅待 检索的图像，在所有图像上实施如下步骤： １）构建 ｋ 最近邻（ｋ⁃ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ， ｋ⁃ＮＮ）图。 ２）计算 ｋ⁃ＮＮ 图中节点间边的权值，求得相似 矩阵 Ｗ，计算公式为 Ｗ（ｉ，ｊ）＝ ｅｘｐ［－ｄ ２ （ｘ０ ，ｘｉ） ／ ２σ ２ ］ （１） 式中：σ 是热核常数。 ３）正则化得到相似矩阵 Ｓ，即 Ｓ ＝ Ｄ －１／ ２ＷＤ －１／ ２ ， 其中 Ｄ 是对角矩阵，Ｄ（ ｉ，ｉ） 为矩阵 Ｗ 的第 ｉ 行或 列和。 ４）根据用户相关性反馈 ｙ 更新排序向量 ｆ，其 中将检索到与查询图像相关图像的对应元素 ｙｉ设置 为 １，否则为 ０。 排序向量 ｆ 的更新迭代式为 ｆ（ｔ＋１） ＝ ａＳｆ（ｔ） ＋ （１－ａ）ｙ （２） 式中：ａ 为比例系数（常数）。 获得一个与图像库 Ｘ 一一对应的排序向量 ｆ ＝ ［ｆ１ ｆ２ … ｆｎ ］ Ｔ ，根据 ｆ 值大 小的排序结果，判断查询样例图像跟待检索图像间 的相似度，将与查询样例最相关的图像作为检索结 果反馈给用户。 ５）用户如果对查询结果不满意，则根据相关和 不相关对图像进行标记，得到新的 ｙ，再返回步骤 ４），否则查询结束。 对于 ｆ 的计算可以用式子 ｆ ＝ （１－ａ） （ Ｉ－ａＳ） －１ ｙ 近似代替［８］ ，其中 ａ 为常数，Ｉ 为单位阵，同时用如 下 ｆ 近似代替也不影响最后排序结果。 ｆ ＝ （Ｉ－ａＳ） －１ ｙ （３） １．２ 广义流形排序图像检索算法 流形排序图像检索算法（ＭＲＢＩＲ） 的不足是每 次处理数据库外的图像时，需要重新计算 ｎ×ｎ 的相 似矩阵 Ｓ，尤其是同样大小的矩阵 Ｉ－ａＳ 的逆矩阵 Ａ＝（Ｉ－ａＳ） －１的计算，会使在线检索时间较长。 但是 广义流形排序算法（Ｇ⁃ＭＲＢＩＲ） ［１０］ 能够避免这种问 题。 Ｇ⁃ＭＲＢＩＲ 相当于首先通过欧式距离找到图像 数据集外的查询图像 ｘ０在图像数据集 Ｘ ＝ ｛ ｘ１ ，ｘ２ ， …，ｘｎ ｝内相关的前 ｍ 幅图像｛ｘｉ， ｉ ＝ １，２，…，ｍ｝，相 应的权值 ｅ（ｉ）＝ ｅｘｐ［－ｄ ２ （ｘ０ ，ｘｉ） ／ ２σ ２ ］，剩余的ｅ（ｉ） 取 ０，对 ｅ 归一化处理后得到排序向量： ｆ ＝ ａ（Ｉ－ａＳ） －１ ｅ （４） 与流形排序不同的是，在面对图像数据集外新 的待查询图像，利用相关反馈方法不用再重新计算 Ｓ 与 Ａ＝ （Ｉ－ａＳ） －１了，具体步骤如下。 １）通过式（４）求得初始流形排序 ｆ０ ，即 ｆ０ ＝ ａ（Ｉ － ａＳ） －１ ｅ （５） ２）对反馈的第 ｉ 幅图像用 ｙ ∗ ｉ ＝ １ 或－１ 进行标 记，如果反馈的图像用户判断与查询图像是相关的 就标记为 １，否则标记为－１。 这样就对反馈的前 ｋ 幅（实际检索中一般取１０～ ３０ 幅是可以接受的） 最 相近图像进行了标记，其他未标记的设为 ０。 首先， 计算正相关向量 ｙ ＋和负相关向量 ｙ–分别为 ｙ ＋ ｉ ＝ １， ｙ ∗ ｉ ＝ １ ０， ｙ ∗ ｉ ＝ ０， － １ { ｙ － ｉ ＝ － １，ｙ ∗ ｉ ＝ － １ ０， ｙ ∗ ｉ ＝ ０，１ { 然后计算正相关排序向量 ｆ ＋ ＝ Ａｙ ＋和负相关排序向 量 ｆ － ＝Ａｙ － ，求得最终的流形排序 ｆ 为 ｆ ＝ηｆ０ ＋ （１－η） ｆ ＋ ＋ ｆ － ，０＜η＜１ （６） 式中：η ＝ ｅｘｐ（－ηｒ），ηｒ为 ｙ ＋中元素为 １ 的个数。 ３）如果用户对结果不满意，则返回步骤 ２），可 以对反馈的图像中未标记的图像重新用同样的方法 进行标记，得到新的 ｙ ＋与 ｙ － ，在不需重新计算 Ｓ 与 第 １ 期 练浩，等：有监督全局流形排序的图像检索算法 ·９３·
·94 智能系统学报 第9卷 A的情况下更新∫+与∫，这样就达到了更新排序∫ 距离。 的目的，直到用户满意为止。 引入监督信息，假设图像x:与图像x:属于同一 2有监督全局流形排序的图像检索算法 类，即有相同的标记时，存放在集合B中，满足集合 中的元素对(i,)所对应的图像x:、x间的相似度增 考虑到图像数据库中的图像可能是已经有类别 加为原值的入（入≥1）倍，否则相似度为0。则有监 标记的或者部分图像是有标记的，在广义流形排序 督近邻图像相似矩阵为W。与有监督非近邻图像相 图像检索算法(G-MRBR)中融入检索图像库中图 似矩阵W。应该满足： 像的标记信息，能够改善查询结果的相关性，有利于 exp[-d(x,x)/2o2]×入， 提高检索性能。因此本文在求相似矩阵时引入了监 Wo(i,j)= (i,)∈{(i,)lj∈形n(i,j)∈B} 督权值入，目的是为了提高属于同一类2幅图像间 其他 的相似度及降低属于不同类2幅图像间的相似度。 (9) 方法如下：假设图像x,与图像x,属于同一类，即有相 [exp[-d(x,x)/2o2]×入， 同的标记时，存在集合B,满足集合中的元素对(i,j) 所对应的图像x:、x,之间的相似度增加为原值的入 W。(i,j)= (i)e{(i,)8n(i,)年B到 (入≥1)倍，否则相似度设为0。于是有监督相似矩 0, 其他 阵为W(i,)=W(i,)·入，其中W(i,)为式(1)中 (10) 所求相似矩阵，(i,)∈B,其他为0。 2.2不相关排序 将广义流形排序图像检索算法中的相似矩阵 检索过程中，图像数据集中除了少部分用户反 W(i,)用有监督相似矩阵W(i,j)代替后，就得到 馈标记的图像外，还有很大一部分未获得反馈标记， 有监督流形排序图像检索算法(S-MRBIR)。对比 这些未获得反馈标记的非近邻图像势必会对排序有 实验表明，有监督流形排序图像检索算法使查准率 所影响，为此引入非近邻图像的不相关排序p来改 得到一定提高，但存在一个问题就是当遇到没有用 善流形排序。不相关排序是指查询图像与非近邻图 户的正反馈时，无法获得有价值的反馈信息，导致反 像相关度的一个排序。与非近邻图像相关度越小， 馈后继续迭代无法改善查询结果，查准率可能依然 不相关排序值就越小；反之，与非近邻图像相关度越 得不到改进[]。针对无正反馈的查询且反馈后的 大，不相关排序值也越大。 查询查准率依然为零的情况，从全局出发考虑到近 在MRBIR中，利用式子f(t+1)=aSf(t)+ 邻图像与非近邻图像对检索都有不同程度的影响， (1-a)y可迭代近似计算出排序向量f=(I-aS)y, 引入不相关排序来校正相关排序向量，提出了有监 其中y是标记后的相关向量，S是正则化近邻图像 督全局流形排序图像检索算法(SG-MRBIR)。SG 相似矩阵，a是平衡常数。若用不相关向量y·代替 MRBIR算法充分利用了图像库的局部与非局部的 相关向量y,同时求得正则化非近邻图像相似矩阵 几何分布信息、用户的查询反馈信息，以进一步提高 S°，于是结合式子p(t+1)=aS“p(t)+(1-a)y°可 检索性能。 迭代近似计算出不相关排序p=(I-aS·)-y·,其 2.1相似矩阵 中S·=(D·)2W°(D·)2,D·是对角矩阵， 近邻图像相似矩阵W表示的是近邻图像间的 D·(i,)为非近邻图像相似矩阵W·的第i行或列 相似拓扑关系，非近邻图像相似矩阵W·描述的是 之和。不相关排序p反映的是与查询图像的无关 非近邻图像间的拓扑关系。对于任意一幅图像， 度，相对来说对前一次迭代查准率为零的查询影响 根据欧氏距离可以判断出离，最近的k幅图像，这 较大。 样得到近邻集合8={x,x3,…,x},则W与W·可 由于S·是正则化的非近邻图像相似矩阵，通过 由热核函数计算如下： 迭代计算出来的排序表示的是查询图像与y·中对 xp[-d(x:,s)/2o2],(i)e{(i)je} W(ij)= 应标记图像的关联值。而y·中标记的是与查询图 0. 其他 像不相关的图像，那么排序对应的就是不相关排序， (7) 不相关排序值越大，与非近邻图像相关度就越大，反 (exp[-d(x,x)/2σ2]，(ij)e{(ij)jE8} w°(i,j)= 之说明与查询图像间的相关度越小。如果结合有监 0. 其他 督近邻图像相似矩阵W。与有监督非近邻图像相似 (8) 矩阵W。,对应得到的S。与S。就是带有监督信 式中：0是热核常数，d(:,x)是x:与x的欧式 息的
Ａ 的情况下更新 ｆ ＋与 ｆ － ，这样就达到了更新排序 ｆ 的目的，直到用户满意为止。 ２ 有监督全局流形排序的图像检索算法 考虑到图像数据库中的图像可能是已经有类别 标记的或者部分图像是有标记的，在广义流形排序 图像检索算法（Ｇ⁃ＭＲＢＩＲ） 中融入检索图像库中图 像的标记信息，能够改善查询结果的相关性，有利于 提高检索性能。 因此本文在求相似矩阵时引入了监 督权值 λ，目的是为了提高属于同一类 ２ 幅图像间 的相似度及降低属于不同类 ２ 幅图像间的相似度。 方法如下：假设图像 ｘｉ与图像 ｘｊ属于同一类，即有相 同的标记时，存在集合 β，满足集合中的元素对（ｉ，ｊ） 所对应的图像 ｘｉ、ｘｊ之间的相似度增加为原值的 λ （λ≥１）倍，否则相似度设为 ０。 于是有监督相似矩 阵为 Ｗ０（ｉ，ｊ）＝ Ｗ（ｉ，ｊ）·λ，其中 Ｗ（ｉ，ｊ）为式（１）中 所求相似矩阵，（ｉ，ｊ）∈β，其他为 ０。 将广义流形排序图像检索算法中的相似矩阵 Ｗ（ｉ，ｊ）用有监督相似矩阵 Ｗ０（ｉ，ｊ）代替后，就得到 有监督流形排序图像检索算法（ Ｓ⁃ＭＲＢＩＲ）。 对比 实验表明，有监督流形排序图像检索算法使查准率 得到一定提高，但存在一个问题就是当遇到没有用 户的正反馈时，无法获得有价值的反馈信息，导致反 馈后继续迭代无法改善查询结果，查准率可能依然 得不到改进［１０］ 。 针对无正反馈的查询且反馈后的 查询查准率依然为零的情况，从全局出发考虑到近 邻图像与非近邻图像对检索都有不同程度的影响， 引入不相关排序来校正相关排序向量，提出了有监 督全局流形排序图像检索算法（ ＳＧ⁃ＭＲＢＩＲ）。 ＳＧ⁃ ＭＲＢＩＲ 算法充分利用了图像库的局部与非局部的 几何分布信息、用户的查询反馈信息，以进一步提高 检索性能。 ２．１ 相似矩阵 近邻图像相似矩阵 Ｗ 表示的是近邻图像间的 相似拓扑关系，非近邻图像相似矩阵 Ｗ ∗ 描述的是 非近邻图像间的拓扑关系。 对于任意一幅图像 ｒ， 根据欧氏距离可以判断出离 ｒ 最近的 ｋ 幅图像，这 样得到近邻集合 θ ｒ ＝ ｛ｘ ｒ １ ，ｘ ｒ ２ ，…， ｘ ｒ ｋ｝，则 Ｗ 与 Ｗ ∗可 由热核函数计算如下： Ｗ（ｉ，ｊ）＝ ｅｘｐ［－ｄ ２ （ｘｉ，ｘｊ） ／ ２σ ２ ］， （ｉ，ｊ）∈｛（ｉ，ｊ） ｜ｊ∈θ ｉ ｝ {０， 其他 （７） Ｗ ∗ （ｉ，ｊ）＝ ｅｘｐ［－ｄ ２ （ｘｉ，ｘｊ） ／ ２σ ２ ］， （ｉ，ｊ）∈｛（ｉ，ｊ） ｜ｊ∉θ ｉ ｝ {０， 其他 （８） 式中：σ 是热核常数， ｄ ２ （ ｘｉ， ｘｊ ） 是 ｘｉ 与 ｘｊ 的欧式 距离。 引入监督信息，假设图像 ｘｉ 与图像 ｘｊ 属于同一 类，即有相同的标记时，存放在集合 β 中，满足集合 中的元素对（ｉ，ｊ）所对应的图像 ｘｉ、ｘｊ 间的相似度增 加为原值的 λ（λ≥１）倍，否则相似度为 ０。 则有监 督近邻图像相似矩阵为 Ｗ０与有监督非近邻图像相 似矩阵 Ｗ ∗ ０ 应该满足： Ｗ０（ｉ，ｊ）＝ ｅｘｐ［－ｄ ２ （ｘｉ，ｘｊ） ／ ２σ ２ ］×λ， （ｉ，ｊ）∈｛（ｉ，ｊ） ｜ ｊ∈θ ｉ∩（ｉ，ｊ）∈β｝ ０， 其他 ì î í ï ï ïï （９） Ｗ ∗ ０ （ｉ，ｊ）＝ ｅｘｐ［－ｄ ２ （ｘｉ，ｘｊ） ／ ２σ ２ ］×λ， （ｉ，ｊ）∈｛（ｉ，ｊ） ｜ ｊ ∉ θ ｉ∩（ｉ，ｊ） ∉ β｝ ０， 其他 ì î í ï ï ï ï （１０） ２．２ 不相关排序 检索过程中，图像数据集中除了少部分用户反 馈标记的图像外，还有很大一部分未获得反馈标记， 这些未获得反馈标记的非近邻图像势必会对排序有 所影响，为此引入非近邻图像的不相关排序 ｐ 来改 善流形排序。 不相关排序是指查询图像与非近邻图 像相关度的一个排序。 与非近邻图像相关度越小， 不相关排序值就越小；反之，与非近邻图像相关度越 大，不相关排序值也越大。 在 ＭＲＢＩＲ 中，利用式子 ｆ （ ｔ ＋ １） ＝ ａＳｆ （ ｔ） ＋ （１－ａ）ｙ 可迭代近似计算出排序向量 ｆ ＝ （Ｉ－ａＳ） －１ ｙ， 其中 ｙ 是标记后的相关向量，Ｓ 是正则化近邻图像 相似矩阵，ａ 是平衡常数。 若用不相关向量 ｙ ∗ 代替 相关向量 ｙ，同时求得正则化非近邻图像相似矩阵 Ｓ ∗ ，于是结合式子 ｐ（ｔ＋１）＝ ａＳ ∗ ｐ（ｔ） ＋（１－ａ） ｙ ∗ 可 迭代近似计算出不相关排序 ｐ ＝ （ Ｉ－ａＳ ∗ ） －１ ｙ ∗ ，其 中 Ｓ ∗ ＝ （ Ｄ ∗ ） －１／ ２ Ｗ ∗ （ Ｄ ∗ ） －１／ ２ ， Ｄ ∗ 是对角矩阵， Ｄ ∗ （ｉ，ｉ）为非近邻图像相似矩阵 Ｗ ∗ 的第 ｉ 行或列 之和。 不相关排序 ｐ 反映的是与查询图像的无关 度，相对来说对前一次迭代查准率为零的查询影响 较大。 由于 Ｓ ∗是正则化的非近邻图像相似矩阵，通过 迭代计算出来的排序表示的是查询图像与 ｙ ∗ 中对 应标记图像的关联值。 而 ｙ ∗ 中标记的是与查询图 像不相关的图像，那么排序对应的就是不相关排序， 不相关排序值越大，与非近邻图像相关度就越大，反 之说明与查询图像间的相关度越小。 如果结合有监 督近邻图像相似矩阵 Ｗ０与有监督非近邻图像相似 矩阵 Ｗ ∗ ０ ，对应得到的 Ｓ０ 与 Ｓ ∗ ０ 就是带有监督信 息的。 ·９４· 智 能 系 统 学 报 第 ９ 卷
第1期 练浩，等：有监督全局流形排序的图像检索算法 ·95. 在G-MRBIR算法中，初始排序f。=a(I-aS)-· 具体步骤描述如下： e=aAe,其中e为相关权值向量，也就是说初始排 1)构建流形拓扑图。 序主要由近邻图像决定，对于图像数据集中大量的 通过构建k-NN图来尽可能逼近图像数据的流 非近邻图像没有考虑。通过欧式距离查找最相关的 形子空间拓扑结构。计算k-NN图中节点间边的权 前m幅图像求e的过程中，可以在其他非近邻图像 值，求得有监督相似图像相似矩阵W。与有监督非近 中找到最不相关的幅图像。于是可以得到不相关 邻图像相似矩阵W。,并进一步正则化得到近邻图 权值向量t,其中与n幅图像对应的不相关权值 像相似矩阵S。与非近邻图像相似矩阵S。。 t(i)=exp[-d(xo,x)/2σ2]，剩余t(i)取0。那 2)求对应的流形排序值。 么，可以得到初始不相关排序po=a(I-aS·)-t= 根据欧式距离初步判断相关向量y与不相关向 aBt,其中B=(I-aS·)-1。如果非近邻图像相似矩 量y·,求得初始相关排序∫。与初始不相关排序P。, 阵采用的是有监督的非近邻图像相似矩阵W。,那 对于图像集中的每个样本点x:一一对应每个排序值 么得到的不相关排序P,就是带有监督信息的不相 ∫，利用∫的大小排序可以把与查询样例最相关的图 关排序了。 像作为检索结果反馈给用户。 上述方法保证了查询图像与非近邻图像间不相 3)根据查询结果进行标记后反馈给系统。 关度越小的同时与近邻图像越相似，这样就可以求 用户如果对以上查询结果不满意，再依据相关 得有监督全局流形排序结果为 和不相关对图像进行标记，根据相关反馈确定新的 f°=f%+(1-m)f-po+f,0<<1 相关向量y与不相关向量y“。如果相关向量y全 式中：f=Ay,f=Ay,为初始相关排序，P。为初 为0，即上次迭代查准率为0时，则采用新的排序 始不相关排序。经过多次实验得到验证，在前一次 ∫=+(1-7)-p。+∫，否则还是沿用排序∫= 查准率为零的情况下，与有监督流形排序图像检索 。+(1-刀)∫+。再返回步骤2)，将结果反馈给 算法的排序结果相比，利用∫°进行下一步迭代，查 系统，直到用户满意。 准率更高。 3实验结果与分析 2.3有监督全局流形排序的图像检索算法 有监督全局流形排序图像检索算法SG-MRBIR 为了验证提出的有监督全局流形排序算法在图 的算法流程如图1。 像检索中的性能，在微软亚洲研究院多媒体图像集 图像 Microsoft Research Asia Internet Multimedia Dataset 数据库 1.0&2.0,MSRA-MM)上与广义流形排序作对比实 验。MSRA-MM图像集为在线收集，包括68类，每 构造k近邻图 类大约有1000幅图像，一共是65443幅图像，每幅 图像附加了关联值（非常关联、关联、不关联3种相 初始排序 查询 关性，对应3个关联值分别是2、1、0)，其中每幅图 图像 像的有效特征包括：1)225 D lack-wise color moment; N 2)64DSV颜色直方图：3)256DGB颜色直方图：4) 有无正反 带不相关排序 标记 的流形排序 144D颜色相关图：5)75D边缘分布直方图：6)128D 纹理图：7)7D人脸特征，因此每个样本是899维。 为了实验方便，从这些数据集中只选用10类作 不带无相关排序 为实验数据，分别是Panda、Ronaldinho、Birds、Baby、 的流形排序 Trees、Cow、Flags、Football、Nokia、Hotels.。然后从关 联值为2和1的7694幅图像中，选择每类的前300 是否满意 幅共3000幅图用于实验。对3000幅样本图像集 用户反债 进行10倍交叉验证，每次选取3000幅中的每类30 幅共300幅作为测试集，其他2700幅作为训练集。 实验中热核常数σ取的是2，k取的是20，平衡 输出结果 常数a取的是0.8，监督权值入取的是2。对每次反 图1SG-MRBR算法流程 馈前20幅图像进行标记，依次迭代求出3000幅图 Fig.1 SG-MRBIR algorithm diagram 的平均查准率，对比结果如表1、表2所示
在 Ｇ⁃ＭＲＢＩＲ 算法中，初始排序 ｆ０ ＝ ａ（Ｉ－ａＳ） －１· ｅ ＝ ａＡｅ，其中 ｅ 为相关权值向量，也就是说初始排 序主要由近邻图像决定，对于图像数据集中大量的 非近邻图像没有考虑。 通过欧式距离查找最相关的 前 ｍ 幅图像求 ｅ 的过程中，可以在其他非近邻图像 中找到最不相关的 ｎ 幅图像。 于是可以得到不相关 权值向量 ｔ，其中与 ｎ 幅图像对应的不相关权值 ｔ（ｉ） ＝ ｅｘｐ［ －ｄ ２ （ ｘ０ ，ｘｉ ） ／ ２σ ２ ］，剩余 ｔ （ ｉ） 取 ０。 那 么，可以得到初始不相关排序 ｐ０ ＝ ａ（ Ｉ－ａＳ ∗ ） －１ ｔ ＝ ａＢｔ，其中 Ｂ＝ （Ｉ－ａＳ ∗ ） －１ 。 如果非近邻图像相似矩 阵采用的是有监督的非近邻图像相似矩阵 Ｗ ∗ ０ ，那 么得到的不相关排序 ｐ０就是带有监督信息的不相 关排序了。 上述方法保证了查询图像与非近邻图像间不相 关度越小的同时与近邻图像越相似，这样就可以求 得有监督全局流形排序结果为 ｆ ∗ ＝ηｆ０ ＋ （１－η） ｆ ＋ － ｐ０ ＋ｆ － ，０＜η＜１ 式中：ｆ ＋ ＝ Ａｙ ＋ ，ｆ － ＝ Ａｙ － ，ｆ －为初始相关排序，ｐ０为初 始不相关排序。 经过多次实验得到验证，在前一次 查准率为零的情况下，与有监督流形排序图像检索 算法的排序结果相比，利用 ｆ ∗ 进行下一步迭代，查 准率更高。 ２．３ 有监督全局流形排序的图像检索算法 有监督全局流形排序图像检索算法 ＳＧ⁃ＭＲＢＩＲ 的算法流程如图 １。 图 １ ＳＧ⁃ＭＲＢＩＲ 算法流程 Ｆｉｇ．１ ＳＧ⁃ＭＲＢＩＲ ａｌｇｏｒｉｔｈｍ ｄｉａｇｒａｍ 具体步骤描述如下： １）构建流形拓扑图。 通过构建 ｋ⁃ＮＮ 图来尽可能逼近图像数据的流 形子空间拓扑结构。 计算 ｋ⁃ＮＮ 图中节点间边的权 值，求得有监督相似图像相似矩阵 Ｗ０与有监督非近 邻图像相似矩阵 Ｗ ∗ ０ ，并进一步正则化得到近邻图 像相似矩阵 Ｓ０与非近邻图像相似矩阵 Ｓ ∗ ０ 。 ２）求对应的流形排序值。 根据欧式距离初步判断相关向量 ｙ 与不相关向 量 ｙ ∗ ，求得初始相关排序 ｆ０与初始不相关排序 ｐ０ ， 对于图像集中的每个样本点 ｘｉ一一对应每个排序值 ｆｉ，利用 ｆｉ的大小排序可以把与查询样例最相关的图 像作为检索结果反馈给用户。 ３）根据查询结果进行标记后反馈给系统。 用户如果对以上查询结果不满意，再依据相关 和不相关对图像进行标记，根据相关反馈确定新的 相关向量 ｙ 与不相关向量 ｙ ∗ 。 如果相关向量 ｙ 全 为 ０，即上次迭代查准率为 ０ 时，则采用新的排序 ｆ ∗ ＝ηｆ０ ＋ （１－η） ｆ ＋ － ｐ０ ＋ ｆ － ，否则还是沿用排序 ｆ ＝ ηｆ０ ＋ （１－η） ｆ ＋ ＋ ｆ － 。 再返回步骤 ２），将结果反馈给 系统，直到用户满意。 ３ 实验结果与分析 为了验证提出的有监督全局流形排序算法在图 像检索中的性能，在微软亚洲研究院多媒体图像集 （Ｍｉｃｒｏｓｏｆｔ Ｒｅｓｅａｒｃｈ Ａｓｉａ Ｉｎｔｅｒｎｅｔ Ｍｕｌｔｉｍｅｄｉａ Ｄａｔａｓｅｔ １．０ ＆ ２．０， ＭＳＲＡ⁃ＭＭ）上与广义流形排序作对比实 验。 ＭＳＲＡ⁃ＭＭ 图像集为在线收集，包括 ６８ 类，每 类大约有 １ ０００ 幅图像，一共是 ６５ ４４３ 幅图像，每幅 图像附加了关联值（非常关联、关联、不关联 ３ 种相 关性，对应 ３ 个关联值分别是 ２、１、０），其中每幅图 像的有效特征包括：１）２２５Ｄ ｌａｃｋ⁃ｗｉｓｅ ｃｏｌｏｒ ｍｏｍｅｎｔ； ２）６４Ｄ ＳＶ 颜色直方图；３）２５６Ｄ ＧＢ 颜色直方图；４） １４４Ｄ 颜色相关图；５）７５Ｄ 边缘分布直方图；６）１２８Ｄ 纹理图；７）７Ｄ 人脸特征，因此每个样本是 ８９９ 维。 为了实验方便，从这些数据集中只选用 １０ 类作 为实验数据，分别是 Ｐａｎｄａ、Ｒｏｎａｌｄｉｎｈｏ、Ｂｉｒｄｓ、Ｂａｂｙ、 Ｔｒｅｅｓ、Ｃｏｗ、Ｆｌａｇｓ、Ｆｏｏｔｂａｌｌ、Ｎｏｋｉａ、Ｈｏｔｅｌｓ。 然后从关 联值为 ２ 和 １ 的 ７ ６９４ 幅图像中，选择每类的前 ３００ 幅共 ３ ０００ 幅图用于实验。 对 ３ ０００ 幅样本图像集 进行 １０ 倍交叉验证，每次选取 ３ ０００ 幅中的每类 ３０ 幅共 ３００ 幅作为测试集，其他 ２ ７００ 幅作为训练集。 实验中热核常数 σ 取的是 ２，ｋ 取的是 ２０，平衡 常数 ａ 取的是 ０．８，监督权值 λ 取的是 ２。 对每次反 馈前 ２０ 幅图像进行标记，依次迭代求出 ３ ０００ 幅图 的平均查准率，对比结果如表 １、表 ２ 所示。 第 １ 期 练浩，等：有监督全局流形排序的图像检索算法 ·９５·
.96· 智能系统学报 第9卷 表1有无监督情况的比较 验证了基于有监督全局流形排序的图像检索算法的 Table 1 Comparison of supervised and unsupervised situations 有效性。 反馈次数 G-MRBIR S-MRBIR 图2是S-MRBIR的检索情况，图3是SG-MR 无反馈 BR的检索情况，其中第1行是查询图像，其余的是 0.34100 0.34100 检索结果，可以看出在无反馈时查准率为零的情况 第1次 0.59037 0.93923 下经过一次反馈后的比较结果。图2查询到的20 第2次 0.72290 0.93966 幅图像中没有一幅与查询图像相关，即查准率依然 为零：而图3查询到的20幅图像中有8幅与查询相 表2有无不相关排序的比较 关。说明在本次查询中，经过一次反馈后采用SG Table 2 Comparison of related and unrelated situations MRBIR检索效果更佳。 反馈次数 S-MRBIR SG-MRBIR 无反馈 0.34100 0.3410 (a)查询图像 第1次 0.93923 0.9489 第2次 0.93966 0.9823 表1比较了无监督与有监督情况下流形排序算 法的查准率，可以看出引入监督信息后，S-MRBIR 查准率比之前无监督的情况G-MRBIR有明显的提 高，第1次反馈后相比提高了34.8%，第2次反馈后 相比提高了21.7%。 实验中首次迭代是无反馈标记的，其中整个 3000次查询中有182次查询的查准率为零。经过 一次反馈，传统方法查准率为零的次数仍然是182， (b)检索结果 但是引入不相关排序后得到查准率为零的次数减少 图2S-MRBIR第1次反馈后检索结果 到53，比之前少了129次，也正是这129次提高了 Fig.2 Retrieval results by S-MRBIR after first feedback 图像查询的查准率。从表2可以看出，SG-MRBIR 与S-MRBIR相比，查准率有所提高，第1次反馈相 比提高了1%，第2次反馈相比也提高了4.2%。 (a)查询图像 同时，对于2种算法在不同的反馈标记图像数 目(10、20、30)情况下，在第2次反馈后的查准率统 计结果如表3所示。 表3不同反馈标记数目的比较 Table 3 Comparison of different feedback tag numbers 反馈标记数目 S-MRBIR SG-MRBIR 10 0.86157 0.92053 20 0.93966 0.98230 30 0.96780 0.99319 (b)检索结果 从表3可以看出，无论反馈标记数目是多少 图3SG-MRBIR第1次反馈后检索结果 SG-MRBIR都比S-MRBR算法查准率要高，进一步 Fig.3 Retrieval results by SG-MRBIR after first feedback
表 １ 有无监督情况的比较 Ｔａｂｌｅ １ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｓｕｐｅｒｖｉｓｅｄ ａｎｄ ｕｎｓｕｐｅｒｖｉｓｅｄ ｓｉｔｕａｔｉｏｎｓ 反馈次数 Ｇ⁃ＭＲＢＩＲ Ｓ⁃ＭＲＢＩＲ 无反馈 ０．３４１ ００ ０．３４１ ００ 第 １ 次 ０．５９０ ３７ ０．９３９ ２３ 第 ２ 次 ０．７２２ ９０ ０．９３９ ６６ 表 ２ 有无不相关排序的比较 Ｔａｂｌｅ ２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｅｌａｔｅｄ ａｎｄ ｕｎｒｅｌａｔｅｄ ｓｉｔｕａｔｉｏｎｓ 反馈次数 Ｓ⁃ＭＲＢＩＲ ＳＧ⁃ＭＲＢＩＲ 无反馈 ０．３４１ ００ ０．３４１ ０ 第 １ 次 ０．９３９ ２３ ０．９４８ ９ 第 ２ 次 ０．９３９ ６６ ０．９８２ ３ 表 １ 比较了无监督与有监督情况下流形排序算 法的查准率，可以看出引入监督信息后，Ｓ⁃ＭＲＢＩＲ 查准率比之前无监督的情况 Ｇ⁃ＭＲＢＩＲ 有明显的提 高，第 １ 次反馈后相比提高了 ３４．８％，第 ２ 次反馈后 相比提高了 ２１．７％。 实验中首次迭代是无反馈标记的，其中整个 ３ ０００次查询中有 １８２ 次查询的查准率为零。 经过 一次反馈，传统方法查准率为零的次数仍然是 １８２， 但是引入不相关排序后得到查准率为零的次数减少 到 ５３，比之前少了 １２９ 次，也正是这 １２９ 次提高了 图像查询的查准率。 从表 ２ 可以看出，ＳＧ⁃ＭＲＢＩＲ 与 Ｓ⁃ＭＲＢＩＲ 相比，查准率有所提高，第 １ 次反馈相 比提高了 １％，第 ２ 次反馈相比也提高了 ４．２％。 同时，对于 ２ 种算法在不同的反馈标记图像数 目（１０、２０、３０）情况下，在第 ２ 次反馈后的查准率统 计结果如表 ３ 所示。 表 ３ 不同反馈标记数目的比较 Ｔａｂｌｅ ３ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｄｉｆｆｅｒｅｎｔ ｆｅｅｄｂａｃｋ ｔａｇ ｎｕｍｂｅｒｓ 反馈标记数目 Ｓ⁃ＭＲＢＩＲ ＳＧ⁃ＭＲＢＩＲ １０ ０．８６１ ５７ ０．９２０ ５３ ２０ ０．９３９ ６６ ０．９８２ ３０ ３０ ０．９６７ ８０ ０．９９３ １９ 从表 ３ 可以看出，无论反馈标记数目是多少， ＳＧ⁃ＭＲＢＩＲ 都比 Ｓ⁃ＭＲＢＩＲ 算法查准率要高，进一步 验证了基于有监督全局流形排序的图像检索算法的 有效性。 图 ２ 是 Ｓ⁃ＭＲＢＩＲ 的检索情况，图 ３ 是 ＳＧ⁃ＭＲ⁃ ＢＩＲ 的检索情况，其中第 １ 行是查询图像，其余的是 检索结果，可以看出在无反馈时查准率为零的情况 下经过一次反馈后的比较结果。 图 ２ 查询到的 ２０ 幅图像中没有一幅与查询图像相关，即查准率依然 为零；而图 ３ 查询到的 ２０ 幅图像中有 ８ 幅与查询相 关。 说明在本次查询中，经过一次反馈后采用 ＳＧ⁃ ＭＲＢＩＲ 检索效果更佳。 图 ２ Ｓ⁃ＭＲＢＩＲ 第 １ 次反馈后检索结果 Ｆｉｇ．２ Ｒｅｔｒｉｅｖａｌ ｒｅｓｕｌｔｓ ｂｙ Ｓ⁃ＭＲＢＩＲ ａｆｔｅｒ ｆｉｒｓｔ ｆｅｅｄｂａｃｋ 图 ３ ＳＧ⁃ＭＲＢＩＲ 第 １ 次反馈后检索结果 Ｆｉｇ．３ Ｒｅｔｒｉｅｖａｌ ｒｅｓｕｌｔｓ ｂｙ ＳＧ⁃ＭＲＢＩＲ ａｆｔｅｒ ｆｉｒｓｔ ｆｅｅｄｂａｃｋ ·９６· 智 能 系 统 学 报 第 ９ 卷
第1期 练浩，等：有监督全局流形排序的图像检索算法 .97. [7]刘利，韦佳，马千里基于流形学习的图像检索研究进展 4 结束语 [J].北京交通大学学报，2010,34(5)：164-171 本文将图像集中图像已有的分类标记信息融入 LIU Li,WEI Jia,MA Qianli.State-of-the-art on image re- trieval based on manifold learning[J].Journal of Beijing 流形排序算法，提出了有监督流形排序图像检索算 Jiaotong University,2010,34(5):164-171. 法，在MSRA-MM图像库上的实验表明，通过引入不 [8]ZHOU Dengyong,JASON W,ARTHUR G.et al.Ranking 相关排序，避免了不能通过用户的多次反馈改善初 on data manifolds C]//Advances in Neural Information 次反馈查准率为零的情况，进一步提高了图像检索 Processing Systems.Vancouver,Canada,2003:169-176. 性能。此外，现实生活中的图像可能同时具有多个 [9]HE Jingrui,LI Mingjing,ZHANG Hongjiang,et al.Mani- 标记信息，也就是同一幅图像同时属于不同的类，如 fold-ranking based image retrieval[C]//Proceedings of the 12%h Annual ACM International Conference on Multimedia. 果引入更加丰富的监督信息势必会更好地改善检索 New York,USA,2004:9-16. 效果，这值得进一步探索。 [10]HE Jingrui,LI Mingjing,ZHANG Hongjiang,et al.Gen- eralized manifold ranking based image retrieval[J].IEEE 参考文献： Transactions on Image Process,2006,15(10):3170- 3177. [1]KATO T.Database architecture for content-based image re- trieval[C]//Proceedings of the SPIE Vol.1662-Image [11]XU Bin,BU Jiajun,CHEN Chen,et al.Efficient manifold ranking for image retrieval [C]//The 34th Annual ACM Storage and Retrieval Systems.San Jose,USA,1992:112- SIGIR Conference.Beijing,China,2011:24-28. 123. 作者简介： [2]RITENDRA D,DHIRAJ J,LI Jia,et al.Image retrieval: 练浩，男，1985年生，硕士研究生， ideas influence,and trends of the new age[]]ACM Com- 主要研究方向为智能信息处理。 puter Surveys,2008,40(2):Article No.5. [3]HE Xiaofei,NIYOGI P.Locality preserving projections [C]//Advances in Neural Information Processing Systems. Vancouver,Canada,2003:3-15. [4]HE Xiaofei.Incremental semi-supervised subspace learning 曾宪华，男，1973年生，副教授，博 for image retrieval [C]//Proceedings of the 12h Annual 士，计算机学会会员，主要研究方向为 ACM International Conference on Multimedia.New York, 流形学习、计算机视觉等。 USA,2004:2-8. [5]LIN Yenyu,LIU Tyngluh,CHEN Hwanntzong.Semantic manifold learning for image retrieval [C]//Proceedings of the 13%h Annual ACM International Conference on Multime- 李淑芳，女，1987年生，硕士研究 dia.Singapore,2005:249-258. 生，主要研究方向为流形学习。 [6]HE Xiaofei,CAI Deng,HAN Jiawei.Learning a maximum margin subspace for image retrieval[J].IEEE Transactions on Knowledge and Data Engineering,2008,20(2):189- 201
４ 结束语 本文将图像集中图像已有的分类标记信息融入 流形排序算法，提出了有监督流形排序图像检索算 法，在 ＭＳＲＡ⁃ＭＭ 图像库上的实验表明，通过引入不 相关排序，避免了不能通过用户的多次反馈改善初 次反馈查准率为零的情况，进一步提高了图像检索 性能。 此外，现实生活中的图像可能同时具有多个 标记信息，也就是同一幅图像同时属于不同的类，如 果引入更加丰富的监督信息势必会更好地改善检索 效果，这值得进一步探索。 参考文献： ［１］ＫＡＴＯ Ｔ． Ｄａｔａｂａｓｅ ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ ｃｏｎｔｅｎｔ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅ⁃ ｔｒｉｅｖａｌ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＳＰＩＥ Ｖｏｌ． １６６２—Ｉｍａｇｅ Ｓｔｏｒａｇｅ ａｎｄ Ｒｅｔｒｉｅｖａｌ Ｓｙｓｔｅｍｓ． Ｓａｎ Ｊｏｓｅ， ＵＳＡ， １９９２： １１２⁃ １２３． ［２］ＲＩＴＥＮＤＲＡ Ｄ， ＤＨＩＲＡＪ Ｊ， ＬＩ Ｊｉａ， ｅｔ ａ１． Ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ： ｉｄｅａｓ ｉｎｆｌｕｅｎｃｅ， ａｎｄ ｔｒｅｎｄｓ ｏｆ ｔｈｅ ｎｅｗ ａｇｅ［ Ｊ］． ＡＣＭ Ｃｏｍ⁃ ｐｕｔｅｒ Ｓｕｒｖｅｙｓ， ２００８， ４０（２）： Ａｒｔｉｃｌｅ Ｎｏ． ５． ［ ３ ］ ＨＥ Ｘｉａｏｆｅｉ， ＮＩＹＯＧＩ Ｐ． Ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｊｅｃｔｉｏｎｓ ［Ｃ］ ／ ／ Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ． Ｖａｎｃｏｕｖｅｒ， Ｃａｎａｄａ， ２００３： ３⁃１５． ［４］ ＨＥ Ｘｉａｏｆｅｉ． Ｉｎｃｒｅｍｅｎｔａｌ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｓｕｂｓｐａｃｅ ｌｅａｒｎｉｎｇ ｆｏｒ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １２ ｔｈ Ａｎｎｕａｌ ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｕｌｔｉｍｅｄｉａ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２００４： ２⁃８． ［５］ ＬＩＮ Ｙｅｎｙｕ， ＬＩＵ Ｔｙｎｇｌｕｈ， ＣＨＥＮ Ｈｗａｎｎｔｚｏｎｇ． Ｓｅｍａｎｔｉｃ ｍａｎｉｆｏｌｄ ｌｅａｒｎｉｎｇ ｆｏｒ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １３ ｔｈ Ａｎｎｕａｌ ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｕｌｔｉｍｅ⁃ ｄｉａ． Ｓｉｎｇａｐｏｒｅ， ２００５： ２４９⁃２５８． ［６］ＨＥ Ｘｉａｏｆｅｉ， ＣＡＩ Ｄｅｎｇ， ＨＡＮ Ｊｉａｗｅｉ． Ｌｅａｒｎｉｎｇ ａ ｍａｘｉｍｕｍ ｍａｒｇｉｎ ｓｕｂｓｐａｃｅ ｆｏｒ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００８， ２０（ ２）： １８９⁃ ２０１． ［７］刘利，韦佳，马千里．基于流形学习的图像检索研究进展 ［Ｊ］．北京交通大学学报， ２０１０， ３４（５）： １６４⁃１７１． ＬＩＵ Ｌｉ， ＷＥＩ Ｊｉａ， ＭＡ Ｑｉａｎｌｉ． Ｓｔａｔｅ⁃ｏｆ⁃ｔｈｅ⁃ａｒｔ ｏｎ ｉｍａｇｅ ｒｅ⁃ ｔｒｉｅｖａｌ ｂａｓｅｄ ｏｎ ｍａｎｉｆｏｌｄ ｌｅａｒｎｉｎｇ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｂｅｉｊｉｎｇ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ， ２０１０， ３４（５）： １６４⁃１７１． ［８］ＺＨＯＵ Ｄｅｎｇｙｏｎｇ， ＪＡＳＯＮ Ｗ， ＡＲＴＨＵＲ Ｇ． ｅｔ ａｌ． Ｒａｎｋｉｎｇ ｏｎ ｄａｔａ ｍａｎｉｆｏｌｄｓ ［ Ｃ］ ／ ／ Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ． Ｖａｎｃｏｕｖｅｒ， Ｃａｎａｄａ， ２００３： １６９⁃１７６． ［９］ＨＥ Ｊｉｎｇｒｕｉ， ＬＩ Ｍｉｎｇｊｉｎｇ， ＺＨＡＮＧ Ｈｏｎｇｊｉａｎｇ， ｅｔ ａ１． Ｍａｎｉ⁃ ｆｏｌｄ⁃ｒａｎｋｉｎｇ ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １２ ｔｈ Ａｎｎｕａｌ ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｕｌｔｉｍｅｄｉａ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２００４： ９⁃１６． ［１０］ＨＥ Ｊｉｎｇｒｕｉ， ＬＩ Ｍｉｎｇｊｉｎｇ， ＺＨＡＮＧ Ｈｏｎｇｊｉａｎｇ， ｅｔ ａ１． Ｇｅｎ⁃ ｅｒａｌｉｚｅｄ ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓ， ２００６， １５ （ １０）： ３１７０⁃ ３１７７． ［１１］ＸＵ Ｂｉｎ， ＢＵ Ｊｉａｊｕｎ， ＣＨＥＮ Ｃｈｅｎ， ｅｔ ａｌ． Ｅｆｆｉｃｉｅｎｔ ｍａｎｉｆｏｌｄ ｒａｎｋｉｎｇ ｆｏｒ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ［ Ｃ］ ／ ／ Ｔｈｅ ３４ｔｈ Ａｎｎｕａｌ ＡＣＭ ＳＩＧＩＲ Ｃｏｎｆｅｒｅｎｃｅ． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２０１１： ２４⁃２８． 作者简介： 练浩，男，１９８５ 年生，硕士研究生， 主要研究方向为智能信息处理。 曾宪华，男，１９７３ 年生，副教授，博 士，计算机学会会员，主要研究方向为 流形学习、计算机视觉等。 李淑芳，女，１９８７ 年生，硕士研究 生，主要研究方向为流形学习。 第 １ 期 练浩，等：有监督全局流形排序的图像检索算法 ·９７·