一种基于图的多模态随机游走重排序算法

赵鹏，陈浩 ，刘慧婷，姚晟



一种基于图的多模态随机游走重排序算法

赵鹏1,2，陈浩2，刘慧婷1,2，姚晟1,2

(1.安徽大学 计算智能与信号处理教育部重点实验室，安徽 合肥 230039；2.安徽大学 计算机科学与技术学院，安徽 合肥 230601)

为了提高图像检索中的重排序效果，提出了一种基于图的多模态随机游走重排序算法。不同于现有的重排序算法根据检索返回的图像顺序设置图像列表得分序列初值，该算法将多模态融合应用于随机游走算法，避免单一模态获取图像内容的片面性，并利用多模态随机游走方法对返回图像列表得分序列进行初始化，然后利用多模态重排序算法最优化目标函数，对相关参数和得分列表进行迭代更新，从而获得最终重排序后的图像序列。实验显示了所提出的算法具有良好的重排序效果。

图像检索；多模态；随机游走；重排序；基于图的学习

随着互联网搜索引擎日趋多元化，用户已经习惯于在互联网上借助各类搜索引擎搜索各种信息，包括文本、图像和视频等。现有主流的互联网搜索引擎，如Google、Bing、百度等，进行图像相关搜索时，主要利用图像周遭的文本信息实现图像的搜索和排序，缺乏考虑图像间内在的联系和图像自身的内容，导致基于文本的图像搜索结果不尽如人意[1]。 如何将符合用户所需的图像排在搜索结果中靠前的位置，提高图像相关搜索结果的质量，已经得到了众多研究者的关注。

图像重排序是在基于初始搜索结果的前提下，挖掘图像间内在的联系和图像自身的内容，对初始排序结果重新进行排序，将符合用户所需的图像排在靠前的位置[2-5]。目前，图像重排序方法大体可以分为四类：基于线性组合的重排序[6-7]、基于聚类的重排序[8-9]、基于分类的重排序[10-11]和基于图的重排序[12-14]。基于线性组合的重排序方法首先通过若干种重排序方法得到多组排序结果，进而利用权值向量将多组排序结果进行线性组合。基于聚类的重排序方法将视觉上相似的图像聚集到一起，从而进行重排序。基于分类的重排序方法将重排序问题转变为二分类问题，对返回图像只做相关或不相关的辨别。基于图的重排序方法构建一个图，顶点表示图像，边表示图像对之间的相似度，将图的相关理论应用于重排序的优化过程。文献[12]提出了一种基于图的多模态重排序算法，该算法自适应地将多模态集成到一个基于图的重排序框架中。

现有基于图的重排序方法采用伪相关方法设置初始排序得分，即默认检索结果越靠前的图像得分越高。但事实并非如此。由于初始结果是基于文本检索所得，没有考虑到图像自身视觉信息以及图像间内在联系，往往存在靠前的图像不符合用户检索需求，而靠后的图像更符合用户检索需求。因此，本文提出了一种基于图的多模态随机游走重排序算法(multimodal graph-based reranking through random walk, MGRRW)，MGRRW算法将多模态融合应用到随机游走算法中，以期避免单一模态抽取图像内容信息的片面性，从而获得更为丰富的图像内容信息，并利用多模态随机游走算法初始化图像序列得分列表初值，然后采用多模态重排序方法最优化目标函数，对相关参数和得分列表进行迭代更新。

1 基于图的多模态重排序和随机游走模型

1.1 基于图的重排序

(1)

(2)

由此可得，贝叶斯重排序的过程可以表示为

(3)

大多数重排序基于以下两点假设[12]：1)重排序后的排序列表和初始列表差距不应过大，即基于文本信息本身的排序能够提供基本合理的排序列表。

2)视觉一致性假设，即视觉相似的图像排序得分应该靠近。

(4)

(5)

式中：Z2=∑rexp(-R(r,χ))，R(r,χ)为正则项，用来描述相似图像排序得分的一致性。

将式(4)、(5)代入式(3)可得到

(6)

式中：Z=Z1Z2为归一化参数。

令

(7)

1.2 随机游走模型

随机游走是指随机选取节点并移动的过程，即确定一个图模型和一个节点i，并以一定概率pij移至邻接节点j，而后以节点j为新起点并重复上述的操作。随机游走过程节点间连结示例如图1所示。 v(i)和v(j)为节点i和j的初始得分。

图1 随机游走过程节点间示意图Fig.1 Example of a graph for random walk

文献[15]将重排序问题转化为随机游走过程，将每幅图像看作一个节点，用图像间的相似度W来表示节点间的权重，根据图像节点的关系构造一个加权无向图。每次游走后得出一个概率分布，如第m-1次游走后的概率分布X(m-1)，该概率分布刻画了第m-1次游走后每一节点被访问到的概率。某一节点被访问到的概率越大，说明该图像的排序应该越靠前。使用X(m-1)作为下次随机游走模型的输入，反复迭代这一过程，最终所得概率分布会趋于收敛。第m次随机游走后概率分布计算

(8)

式中：X为返回图对应的稳态概率向量，β∈[0,1]为权衡因子，P为状态转移矩阵，可通过相似度矩阵W按列归一化获得。V为返回图像的初始排序得分列表，经过式(8)的不断迭代，X将达到稳定状态，最终根据稳态概率向量X的降序对返回图像进行重排序。

1.3 多模态及相关参数优化

多模态是指多种模态特征。单一模态特征往往不能较好的表达图像的语义信息，基于多模态的图像重排序可以获得更为丰富的图像语义信息。图像的多模态包括颜色、纹理以及边缘分布等不同模态。

多模态的融合分为早融合和迟融合。为了避免早融合导致“维度灾难”，本文采用后融合，先对各模态特征加以处理，然后对处理结果加权融合。

根据图像模态特征分布情况，本文采用了文献[12]中的图像相似度计算方法及参数优化方法。在图像相似性度量中采用了马氏距离

式中：Wk,ij为第k个模态下第i幅与第j幅图像间的相似度。 xk,i与xk,j为第k个模态下第i幅与第j幅图像的特征。Mk矩阵为第k个模态对应的对称半正定矩阵。将Mk矩阵分解：Mk=AkTAk

(10)

将式(10)代入式(9)，得到

(11)

(12)

(13)

式中：α=[α1,α2,…,αK]为每个模态所对应的权值。ζ为模态权值对应的调节参数。因此目标函数定义为minimizeQ(r,χ,α,A1,A2,…,Ak)=

(14)

采用交替优化的思想，迭代更新r，Ak(k=1,2,…,K)，和1/Zn。

首先固定Ak(k=1,2,…,K)，和1/Zn，可导出公式

(15)

然后固定r和1/Zn。使用梯度下降法对式(14)中的模态Ak进行更新

(16)

最后，固定r，Ak，利用坐标下降法更新αk。式(14)可转换为

(17)

(18)

(19)

2 基于图的多模态随机游走重排序算法

本文提出一种基于图的多模态随机游走重排序算法(multimodalgraph-basedre-rankingthroughrandomwalk，MGRRW)，该算法的一般过程如图2所示。

MGRRW算法首先对检索返回的图像集提取K种模态特征，生成K个特征矩阵。然后将多模态融合应用于随机游走模型中，即分别对每个模态特征，利用随机游走算法进行处理，并将处理后的结果进行加权融合，作为多模态重排序中图像序列得分列表初值，最后采用基于图的多模态重排序算法，对初始的K种模态进行更新，迭代指定步长后结束。图3为MGRRW算法的总体流程框架。

具体算法描述如算法1。

算法1: 基于图的多模态随机游走重排序算法

输入：检索返回的初始图像序列

输出：重排序后返回的图像序列

1)初始化

①将步数t设置为0；

2)多模态随机游走初始化图像序列得分列表

②对每一个模态依次执行以下循环,分别计算出K个得分列表r1,r2,…,rK：

rk(m)=μPk(t)rk(m-1)+(1-μ)V，

式中：μ为权衡因子，μ∈[0,1]；m表示迭代的层级，Pk表示第k个模态下的状态转移矩阵。rk表示第k个模态下图像对应的概率分布；阻尼向量V表示图像的初始得分；为了突出视觉一致性假设，V的成员取值逐次递减，将上式不断迭代，最终达到稳定状态。

其中β1,β2,…,βk∈[0,1]，为各模态得分列表的权值，根据各模态特征维数占模态特征维数总和的百分比设置，且β1+β2+…+βk=1；

图2 基于图的多模态随机游走重排序的一般过程Fig.2 The general process of multimodal graph-based reranking through random walk

图3 算法总体流程框架Fig.3 The frame of general algorithm procedure

3)迭代更新得分列表及相关参数

①根据式(15)，计算r(t)；

⑤ift

{t=t+1，跳到②；}

else

输出图像序列得分，按照得分从高到低，给出重排序后的图像序列。

3 实验结果与分析

3.1 数据集与评价指标

本文使用了MSRA-MM1.0版本数据集[19]。该数据集包括68类，每类约有1 000幅图像，共有65 443幅。所有图像都是微软在线收集，每幅图像有一个关联标准，分别是非常关联，关联和不关联。对应三个关联值分别是2、1、0。图4为该数据集中的部分示例。

图4 数据库示例Fig.4 Examples in image base

该数据集中图像包括7种模态特征，具体包括：1)225维分块颜色矩；2)256维RGB颜色直方图；3)144维颜色相关图；4)75维边缘分布直方图；5)64维HSV颜色直方图；6)128维小波纹理图；7)7维人脸特征图。本文使用了前六种模态特征。

实验使用归一化有损积累增益[20](normalizeddiscountedcumulativegain,NDCG)作为衡量排序效果的评价指标。计算公式为

(20)

(21)

式中：n表示检索返回的图像个数，1/Zn是归一化参数，使得最优的NDCG@n=1。NDCG@n∈[0,1]，其值越接近1表明排序效果越好。m(j)是重排序算法迭代后的第j幅图像对应的关联程度。l(j)是第j幅图像在最优排序中对应的关联程度。

3.2 三种重排序算法在不同类别中的性能比较

为了检验本文所提出的基于图的多模态随机游走重排序算法(MGRRW)的排序效果，实验将MGRRW与多模态随机游走算法(multimodallearningthroughrandomwalk,MLRW)和基于图的多模态重排序算法(multimodalgraph-basedlearning,MGL)[12]进行了对比实验。返回图像的数量设置为100。从表1可以看出，本文所提出的MGRRW比MLRW和MGL的平均NDCG@100值有了明显提高，表明本文所提出的算法比其他两个算法排序效果更好。图5为在查询条件为“Earth”下，初始的查询返回结果和3种重排序算法重排序后返回的结果示例。方框内的图像是与查询不相关的图像，可以看出本文所提算法可以较好剔除不相关的图像。

图5 查询初值和三种重排序返回图像序列示例Fig.5 The three reranking methods for an example Earth

表1 在检索深度为100情况下3种重排序算法性能的比较

3.3 不同检索深度情况下三种重排序算法性能比较

本实验检验检索返回图像的个数对三种重排序算法效果的影响。实验设置了4个检索返回图像的数量，即n分别取值为10、20、50和100。实验对所有查询类别求其平均NDCG@n值。实验结果如表2所示。实验结果显示：

1)本文所提出的算法MGRRW在不同的返回图像数量的情况下，排序结果均优于其他两种算法MLRW和MGL。

2)随着返回图像的个数逐渐增多，返回图像集的平均NDCG@n值随之略有减小。由此说明，当返回结果逐渐增多的情况下，检索结果的准确度也会随之降低。

表2 在不同深度情况下3种重排序算法性能的比较

3.4 单一模态重排序算法与MGRRW算法对比

本实验检验单一模态对图像重排序的影响，对六种模态分别进行重排序实验。表3 中“75D-EDH”、“225D-CM”、“64D-HSV”、“114D-CORR”、“128D-Wave”、“226D-RGB”等代表使用相应单一模态的基于图的随机游走重排序算法。返回图像的数量设置为100，表格左边第二列为检索返回的图像序列的初始平均NDCG@100。可以看出：相对于初始查询返回的图像序列，单一模态在大部分情况下，能提高重排序算法的排序效果。最右一列加黑部分为本文所提出的MGRRW算法的平均NDCG@100，对比可见MGRRW算法的排序效果更好,由此可看出多模态融合的重排序算法较单一模态的重排序算法的排序效果更加显著，对所有类别的排序结果均有提高，这表明多模态融合的算法可以更好的抽取图像丰富的内容信息，避免单模态算法可能抽取片面的内容信息而造成排序效果下降的可能，因而适应面也更广。

表3 检索深度为100情况下使用单一模态重排序算法与MGRRW算法对比

4 结论

本文提出了一种基于图的多模态随机游走重排序算法。实验结果表明将多模态融合应用到随机游走算法中，并利用多模态随机游走算法初始化图像序列得分列表初值，能够有效的提高图像重排序的效果。

重排序仍然是信息检索领域中一项富有挑战性的研究课题。由于每位用户所关注的内容和个人的喜好不同，所期望的检索效果也不同。未来的研究将考虑如何将个性化信息融合到图像结果重排序中，以期更加符合用户个性化的检索需求。

[1]CAI Junjie, ZHA Zhengjun, WANG Meng, et al. An attribute-assisted reranking model for web image search[J]. IEEE transactions on image processing, 2015, 24(1): 261-272.

[2]HOU Hongmei, XU Xinshun, WANG Gang, et al. Joint-Rerank: a novel method for image search reranking[J]. Multimedia tools and applications, 2015, 74(4): 1423-1442.

[3]YANG Linjun, HANJALIC A. Prototype-based image search reranking[J]. IEEE transactions on multimedia, 2012, 14(3): 871-882.

[4]LIU Yuan, MEI Tao, WANG Meng, et al. Typicality-based visual search reranking[J]. IEEE transactions on circuits and systems for video technology, 2010, 20(5): 749-755.

[5]JI Zhong, PANG Yanwei, HE Yuqing, et al. Semi-supervised LPP algorithms for learning-to-rank-based visual search reranking[J]. Information sciences, 2015, 302: 83-93.

[6]LI Xirong, WANG Dong, LI Jianmin, et al. Video search in concept subspace: a text-like paradigm[C]//Proceedings of the 6th ACM International Conference on Image and Video Retrieval. Amsterdam, Netherlands: ACM, 2007: 603-610.

[7]NATSEV A, HAUBOLD A, TEIJ, et al. Semantic concept-based query expansion and re-ranking for multimedia retrieval[C]//Proceedings of the 15th ACM International Conference on Multimedia. Augsburg, Bavaria, Germany: ACM, 2007: 991-1000.

[8]BERG T L, FORSYTH D A. Animals on the web[C]//Proceedings of 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York: IEEE, 2006, 2: 1463-1470.

[9]HSU W H, KENNEDY L S, CHANG S F. Video search reranking via information bottleneck principle[C]//Proceedings of the 14th ACM International Conference on Multimedia. Santa Barbara, USA: ACM, 2006: 35-44.

[10]YAN Rong, HAUPTMANN A G. Co-retrieval: a boosted reranking approach for video retrieval[M]//ENSER P, KOMPATSIARIS Y, O′CONNOR N E, et al. Image and Video Retrieval. Berlin Heidelberg: Springer, 2004: 60-69.

[11]FERGUS R, PERONA P, ZISSERMAN A. A visual category filter for google images[M]//PAJDLA T, MATAS J. Computer Vision-ECCV 2004. Berlin Heidelberg: Springer, 2004: 242-256.

[12]WANG Meng, LI Hao, TAO Dacheng, et al. Multimodal graph-based reranking for web image search[J]. IEEE transactions on image processing, 2012, 21(11): 4649-4661.

[13]DENG Cheng, JI Rongrong, TAO Dacheng, et al. Weakly supervised multi-graph learning for robust image reranking[J]. IEEE transactions on multimedia, 2014, 16(3): 785-795.

[14]YANG Xiaopeng, ZHANG Yongdong, YAO Ting, et al. Click-boosting multi-modality graph-based reranking for image search[J]. Multimedia systems, 2015, 21(2): 217-227. [15]HSU W H, KENNEDY L S, CHANG S F. Video search reranking through random walk over document-level context graph[C]//Proceedings of the 15th ACM International Conference on Multimedia. Augsburg, Bavaria, Germany: ACM, 2007: 971-980.

[16]TIAN Xinmei, YANG Linjun, WANG Jingdong, et al. Bayesian video search reranking[C]//Proceedings of the 16th ACM International Conference on Multimedia. Vancouver, Canada: ACM, 2008: 131-140.

[17]ZHOU Dengyong, BOUSQUET O, LAL T N, et al. Learning with local and global consistency[C]//Advances in Neural Information Processing Systems 16. Cambridge, MA: MIT Press, 2004: 321-328.

[18]ZHU XIAOJIN, GHAHRAMANI Z, LAFFERTY J. Semi-supervised learning using gaussian fields and harmonic functions[C]//Proceedings of the Twentieth International Conference on Machine Learning. Washington, DC, USA: ICML, 2003: 912-919.

[19]WANG M, YANG L, HUA X S. MSRA-MM: bridging research and industrial societies for multimedia information retrieval[R]. Microsoft Research Asia. Technology Report, 2009.

A multimodal graph-based re-ranking through random walk algorithm

ZHAO Peng1,2,CHEN Hao2, LIU Huiting1,2, YAO Sheng1,2

(1.Key Laboratory of Intelligent Computing and Signal Processing of the Ministry of Education ,Anhui University, Hefei 230039,China; 2. School of Computer Science and Technology, Anhui University, Hefei 230601,China)

To improve the effect of re-ranking algorithms in image retrieval, this paper presented a multimodal graph-based re-ranking through random walk. Different from existing re-ranking algorithms which set the initial score sequence value of an image list according to the image sequence returned by retrieval, the proposed method integrated multimodal to acquire more information and employed a multimodal random walk algorithm to initialize the relevance score list of the retrieved images. Then, the proposed method optimized the objective function by using a multimodal graph-based reranking algorithm in which an iteration procedure was used to update the parameters and relevance score list. Finally, the retrieved images were reordered according to the relevance score list. Experimental results demonstrate that the proposed reranking algorithm performs better than some other state-of-the-art algorithms.

image retrieval; multimodal; random walk; re-ranking; graph-based learning

2015-08-14.

日期：2016-08-29.

国家自然科学基金项目(61602004, 61472001)；安徽省自然科学基金项目(1408085MF122，1508085MF127)；安徽省高校自然科学研究重点项目(KJ2016A041)；安徽大学信息保障技术协同创新中心公开招标课题(ADXXBZ2014-5 ADXXBZ2014-6).

赵鹏(1976-)，女，副教授.

赵鹏，E-mail: zhaopeng_ad@163.com.

10.11990/jheu.201508029

网络出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20160829.1422.060.html

TP391

A

1006-7043(2016)10-1387-07

赵鹏，陈浩，刘慧婷，等. 一种基于图的多模态随机游走重排序算法[J]. 哈尔滨工程大学学报， 2016, 37(10): 1387-1393.

ZHAO Peng, CHEN Hao, LIU Huiting， et al. A multimodal graph-based re-ranking through random walk algorithm[J]. Journal of Harbin Engineering University, 2016, 37(10): 1387-1393.