一種基于圖的多模態(tài)隨機游走重排序算法

趙鵬，陳浩 ，劉慧婷，姚晟

?

一種基于圖的多模態(tài)隨機游走重排序算法

趙鵬1,2，陳浩2，劉慧婷1,2，姚晟1,2

(1.安徽大學 計算智能與信號處理教育部重點實驗室，安徽 合肥 230039；2.安徽大學 計算機科學與技術學院，安徽 合肥 230601)

為了提高圖像檢索中的重排序效果，提出了一種基于圖的多模態(tài)隨機游走重排序算法。不同于現(xiàn)有的重排序算法根據(jù)檢索返回的圖像順序設置圖像列表得分序列初值，該算法將多模態(tài)融合應用于隨機游走算法，避免單一模態(tài)獲取圖像內容的片面性，并利用多模態(tài)隨機游走方法對返回圖像列表得分序列進行初始化，然后利用多模態(tài)重排序算法最優(yōu)化目標函數(shù)，對相關參數(shù)和得分列表進行迭代更新，從而獲得最終重排序后的圖像序列。實驗顯示了所提出的算法具有良好的重排序效果。

圖像檢索；多模態(tài)；隨機游走；重排序；基于圖的學習

隨著互聯(lián)網(wǎng)搜索引擎日趨多元化，用戶已經(jīng)習慣于在互聯(lián)網(wǎng)上借助各類搜索引擎搜索各種信息，包括文本、圖像和視頻等。現(xiàn)有主流的互聯(lián)網(wǎng)搜索引擎，如Google、Bing、百度等，進行圖像相關搜索時，主要利用圖像周遭的文本信息實現(xiàn)圖像的搜索和排序，缺乏考慮圖像間內在的聯(lián)系和圖像自身的內容，導致基于文本的圖像搜索結果不盡如人意[1]。 如何將符合用戶所需的圖像排在搜索結果中靠前的位置，提高圖像相關搜索結果的質量，已經(jīng)得到了眾多研究者的關注。

圖像重排序是在基于初始搜索結果的前提下，挖掘圖像間內在的聯(lián)系和圖像自身的內容，對初始排序結果重新進行排序，將符合用戶所需的圖像排在靠前的位置[2-5]。目前，圖像重排序方法大體可以分為四類：基于線性組合的重排序[6-7]、基于聚類的重排序[8-9]、基于分類的重排序[10-11]和基于圖的重排序[12-14]?；诰€性組合的重排序方法首先通過若干種重排序方法得到多組排序結果，進而利用權值向量將多組排序結果進行線性組合?；诰垲惖闹嘏判蚍椒▽⒁曈X上相似的圖像聚集到一起，從而進行重排序?；诜诸惖闹嘏判蚍椒▽⒅嘏判騿栴}轉變?yōu)槎诸悊栴}，對返回圖像只做相關或不相關的辨別?；趫D的重排序方法構建一個圖，頂點表示圖像，邊表示圖像對之間的相似度，將圖的相關理論應用于重排序的優(yōu)化過程。文獻[12]提出了一種基于圖的多模態(tài)重排序算法，該算法自適應地將多模態(tài)集成到一個基于圖的重排序框架中。

現(xiàn)有基于圖的重排序方法采用偽相關方法設置初始排序得分，即默認檢索結果越靠前的圖像得分越高。但事實并非如此。由于初始結果是基于文本檢索所得，沒有考慮到圖像自身視覺信息以及圖像間內在聯(lián)系，往往存在靠前的圖像不符合用戶檢索需求，而靠后的圖像更符合用戶檢索需求。因此，本文提出了一種基于圖的多模態(tài)隨機游走重排序算法(multimodal graph-based reranking through random walk, MGRRW)，MGRRW算法將多模態(tài)融合應用到隨機游走算法中，以期避免單一模態(tài)抽取圖像內容信息的片面性，從而獲得更為豐富的圖像內容信息，并利用多模態(tài)隨機游走算法初始化圖像序列得分列表初值，然后采用多模態(tài)重排序方法最優(yōu)化目標函數(shù)，對相關參數(shù)和得分列表進行迭代更新。

1 基于圖的多模態(tài)重排序和隨機游走模型

1.1 基于圖的重排序

(1)

(2)

由此可得，貝葉斯重排序的過程可以表示為

(3)

大多數(shù)重排序基于以下兩點假設[12]：1)重排序后的排序列表和初始列表差距不應過大，即基于文本信息本身的排序能夠提供基本合理的排序列表。

2)視覺一致性假設，即視覺相似的圖像排序得分應該靠近。

(4)

(5)

式中：Z2=∑rexp(-R(r,χ))，R(r,χ)為正則項，用來描述相似圖像排序得分的一致性。

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

(6)

式中：Z=Z1Z2為歸一化參數(shù)。

令

(7)

1.2 隨機游走模型

隨機游走是指隨機選取節(jié)點并移動的過程，即確定一個圖模型和一個節(jié)點i，并以一定概率pij移至鄰接節(jié)點j，而后以節(jié)點j為新起點并重復上述的操作。隨機游走過程節(jié)點間連結示例如圖1所示。 v(i)和v(j)為節(jié)點i和j的初始得分。

圖1 隨機游走過程節(jié)點間示意圖Fig.1 Example of a graph for random walk

文獻[15]將重排序問題轉化為隨機游走過程，將每幅圖像看作一個節(jié)點，用圖像間的相似度W來表示節(jié)點間的權重，根據(jù)圖像節(jié)點的關系構造一個加權無向圖。每次游走后得出一個概率分布，如第m-1次游走后的概率分布X(m-1)，該概率分布刻畫了第m-1次游走后每一節(jié)點被訪問到的概率。某一節(jié)點被訪問到的概率越大，說明該圖像的排序應該越靠前。使用X(m-1)作為下次隨機游走模型的輸入，反復迭代這一過程，最終所得概率分布會趨于收斂。第m次隨機游走后概率分布計算

(8)

式中：X為返回圖對應的穩(wěn)態(tài)概率向量，β∈[0,1]為權衡因子，P為狀態(tài)轉移矩陣，可通過相似度矩陣W按列歸一化獲得。V為返回圖像的初始排序得分列表，經(jīng)過式(8)的不斷迭代，X將達到穩(wěn)定狀態(tài)，最終根據(jù)穩(wěn)態(tài)概率向量X的降序對返回圖像進行重排序。

1.3 多模態(tài)及相關參數(shù)優(yōu)化

多模態(tài)是指多種模態(tài)特征。單一模態(tài)特征往往不能較好的表達圖像的語義信息，基于多模態(tài)的圖像重排序可以獲得更為豐富的圖像語義信息。圖像的多模態(tài)包括顏色、紋理以及邊緣分布等不同模態(tài)。

多模態(tài)的融合分為早融合和遲融合。為了避免早融合導致“維度災難”，本文采用后融合，先對各模態(tài)特征加以處理，然后對處理結果加權融合。

根據(jù)圖像模態(tài)特征分布情況，本文采用了文獻[12]中的圖像相似度計算方法及參數(shù)優(yōu)化方法。在圖像相似性度量中采用了馬氏距離

式中：Wk,ij為第k個模態(tài)下第i幅與第j幅圖像間的相似度。 xk,i與xk,j為第k個模態(tài)下第i幅與第j幅圖像的特征。Mk矩陣為第k個模態(tài)對應的對稱半正定矩陣。將Mk矩陣分解：Mk=AkTAk

(10)

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

(11)

(12)

(13)

式中：α=[α1,α2,…,αK]為每個模態(tài)所對應的權值。ζ為模態(tài)權值對應的調節(jié)參數(shù)。因此目標函數(shù)定義為minimizeQ(r,χ,α,A1,A2,…,Ak)=

(14)

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

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

(15)

然后固定r和1/Zn。使用梯度下降法對式(14)中的模態(tài)Ak進行更新

(16)

最后，固定r，Ak，利用坐標下降法更新αk。式(14)可轉換為

(17)

(18)

(19)

2 基于圖的多模態(tài)隨機游走重排序算法

本文提出一種基于圖的多模態(tài)隨機游走重排序算法(multimodalgraph-basedre-rankingthroughrandomwalk，MGRRW)，該算法的一般過程如圖2所示。

MGRRW算法首先對檢索返回的圖像集提取K種模態(tài)特征，生成K個特征矩陣。然后將多模態(tài)融合應用于隨機游走模型中，即分別對每個模態(tài)特征，利用隨機游走算法進行處理，并將處理后的結果進行加權融合，作為多模態(tài)重排序中圖像序列得分列表初值，最后采用基于圖的多模態(tài)重排序算法，對初始的K種模態(tài)進行更新，迭代指定步長后結束。圖3為MGRRW算法的總體流程框架。

具體算法描述如算法1。

算法1: 基于圖的多模態(tài)隨機游走重排序算法

輸入：檢索返回的初始圖像序列

輸出：重排序后返回的圖像序列

1)初始化

①將步數(shù)t設置為0；

2)多模態(tài)隨機游走初始化圖像序列得分列表

②對每一個模態(tài)依次執(zhí)行以下循環(huán),分別計算出K個得分列表r1,r2,…,rK：

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

式中：μ為權衡因子，μ∈[0,1]；m表示迭代的層級，Pk表示第k個模態(tài)下的狀態(tài)轉移矩陣。rk表示第k個模態(tài)下圖像對應的概率分布；阻尼向量V表示圖像的初始得分；為了突出視覺一致性假設，V的成員取值逐次遞減，將上式不斷迭代，最終達到穩(wěn)定狀態(tài)。

其中β1,β2,…,βk∈[0,1]，為各模態(tài)得分列表的權值，根據(jù)各模態(tài)特征維數(shù)占模態(tài)特征維數(shù)總和的百分比設置，且β1+β2+…+βk=1；

圖2 基于圖的多模態(tài)隨機游走重排序的一般過程Fig.2 The general process of multimodal graph-based reranking through random walk

圖3 算法總體流程框架Fig.3 The frame of general algorithm procedure

3)迭代更新得分列表及相關參數(shù)

①根據(jù)式(15)，計算r(t)；

⑤ift

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

else

輸出圖像序列得分，按照得分從高到低，給出重排序后的圖像序列。

3 實驗結果與分析

3.1 數(shù)據(jù)集與評價指標

本文使用了MSRA-MM1.0版本數(shù)據(jù)集[19]。該數(shù)據(jù)集包括68類，每類約有1 000幅圖像，共有65 443幅。所有圖像都是微軟在線收集，每幅圖像有一個關聯(lián)標準，分別是非常關聯(lián)，關聯(lián)和不關聯(lián)。對應三個關聯(lián)值分別是2、1、0。圖4為該數(shù)據(jù)集中的部分示例。

圖4 數(shù)據(jù)庫示例Fig.4 Examples in image base

該數(shù)據(jù)集中圖像包括7種模態(tài)特征，具體包括：1)225維分塊顏色矩；2)256維RGB顏色直方圖；3)144維顏色相關圖；4)75維邊緣分布直方圖；5)64維HSV顏色直方圖；6)128維小波紋理圖；7)7維人臉特征圖。本文使用了前六種模態(tài)特征。

實驗使用歸一化有損積累增益[20](normalizeddiscountedcumulativegain,NDCG)作為衡量排序效果的評價指標。計算公式為

(20)

(21)

式中：n表示檢索返回的圖像個數(shù)，1/Zn是歸一化參數(shù)，使得最優(yōu)的NDCG@n=1。NDCG@n∈[0,1]，其值越接近1表明排序效果越好。m(j)是重排序算法迭代后的第j幅圖像對應的關聯(lián)程度。l(j)是第j幅圖像在最優(yōu)排序中對應的關聯(lián)程度。

3.2 三種重排序算法在不同類別中的性能比較

為了檢驗本文所提出的基于圖的多模態(tài)隨機游走重排序算法(MGRRW)的排序效果，實驗將MGRRW與多模態(tài)隨機游走算法(multimodallearningthroughrandomwalk,MLRW)和基于圖的多模態(tài)重排序算法(multimodalgraph-basedlearning,MGL)[12]進行了對比實驗。返回圖像的數(shù)量設置為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 不同檢索深度情況下三種重排序算法性能比較

本實驗檢驗檢索返回圖像的個數(shù)對三種重排序算法效果的影響。實驗設置了4個檢索返回圖像的數(shù)量，即n分別取值為10、20、50和100。實驗對所有查詢類別求其平均NDCG@n值。實驗結果如表2所示。實驗結果顯示：

1)本文所提出的算法MGRRW在不同的返回圖像數(shù)量的情況下，排序結果均優(yōu)于其他兩種算法MLRW和MGL。

2)隨著返回圖像的個數(shù)逐漸增多，返回圖像集的平均NDCG@n值隨之略有減小。由此說明，當返回結果逐漸增多的情況下，檢索結果的準確度也會隨之降低。

表2 在不同深度情況下3種重排序算法性能的比較

3.4 單一模態(tài)重排序算法與MGRRW算法對比

本實驗檢驗單一模態(tài)對圖像重排序的影響，對六種模態(tài)分別進行重排序實驗。表3 中“75D-EDH”、“225D-CM”、“64D-HSV”、“114D-CORR”、“128D-Wave”、“226D-RGB”等代表使用相應單一模態(tài)的基于圖的隨機游走重排序算法。返回圖像的數(shù)量設置為100，表格左邊第二列為檢索返回的圖像序列的初始平均NDCG@100?？梢钥闯觯合鄬τ诔跏疾樵兎祷氐膱D像序列，單一模態(tài)在大部分情況下，能提高重排序算法的排序效果。最右一列加黑部分為本文所提出的MGRRW算法的平均NDCG@100，對比可見MGRRW算法的排序效果更好,由此可看出多模態(tài)融合的重排序算法較單一模態(tài)的重排序算法的排序效果更加顯著，對所有類別的排序結果均有提高，這表明多模態(tài)融合的算法可以更好的抽取圖像豐富的內容信息，避免單模態(tài)算法可能抽取片面的內容信息而造成排序效果下降的可能，因而適應面也更廣。

表3 檢索深度為100情況下使用單一模態(tài)重排序算法與MGRRW算法對比

4 結論

本文提出了一種基于圖的多模態(tài)隨機游走重排序算法。實驗結果表明將多模態(tài)融合應用到隨機游走算法中，并利用多模態(tài)隨機游走算法初始化圖像序列得分列表初值，能夠有效的提高圖像重排序的效果。

重排序仍然是信息檢索領域中一項富有挑戰(zhàn)性的研究課題。由于每位用戶所關注的內容和個人的喜好不同，所期望的檢索效果也不同。未來的研究將考慮如何將個性化信息融合到圖像結果重排序中，以期更加符合用戶個性化的檢索需求。

[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)；安徽大學信息保障技術協(xié)同創(chuàng)新中心公開招標課題(ADXXBZ2014-5 ADXXBZ2014-6).

趙鵬(1976-)，女，副教授.

趙鵬，E-mail: zhaopeng_ad@163.com.

10.11990/jheu.201508029

網(wǎng)絡出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20160829.1422.060.html

TP391

A

1006-7043(2016)10-1387-07

趙鵬，陳浩，劉慧婷，等. 一種基于圖的多模態(tài)隨機游走重排序算法[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.