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

?

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

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

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

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

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

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

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

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

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

1.1 基于圖的重排序

(1)

(2)

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

(3)

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

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

(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為新起點并重復(fù)上述的操作。隨機游走過程節(jié)點間連結(jié)示例如圖1所示。 v(i)和v(j)為節(jié)點i和j的初始得分。

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

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

(8)

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

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

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

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

根據(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)對應(yīng)的對稱半正定矩陣。將Mk矩陣分解：Mk=AkTAk

(10)

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

(11)

(12)

(13)

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

(14)

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

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

(15)

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

(16)

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

(17)

(18)

(19)

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

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

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

具體算法描述如算法1。

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

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

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

1)初始化

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

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

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

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

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

其中β1,β2,…,βk∈[0,1]，為各模態(tài)得分列表的權(quán)值，根據(jù)各模態(tài)特征維數(shù)占模態(tài)特征維數(shù)總和的百分比設(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)迭代更新得分列表及相關(guān)參數(shù)

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

⑤ift

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

else

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

3 實驗結(jié)果與分析

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

本文使用了MSRA-MM1.0版本數(shù)據(jù)集[19]。該數(shù)據(jù)集包括68類，每類約有1 000幅圖像，共有65 443幅。所有圖像都是微軟在線收集，每幅圖像有一個關(guān)聯(lián)標(biāo)準(zhǔn)，分別是非常關(guān)聯(lián)，關(guān)聯(lián)和不關(guān)聯(lián)。對應(yīng)三個關(guā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維顏色相關(guān)圖；4)75維邊緣分布直方圖；5)64維HSV顏色直方圖；6)128維小波紋理圖；7)7維人臉特征圖。本文使用了前六種模態(tài)特征。

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

(20)

(21)

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

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

為了檢驗本文所提出的基于圖的多模態(tài)隨機游走重排序算法(MGRRW)的排序效果，實驗將MGRRW與多模態(tài)隨機游走算法(multimodallearningthroughrandomwalk,MLRW)和基于圖的多模態(tài)重排序算法(multimodalgraph-basedlearning,MGL)[12]進行了對比實驗。返回圖像的數(shù)量設(shè)置為100。從表1可以看出，本文所提出的MGRRW比MLRW和MGL的平均NDCG@100值有了明顯提高，表明本文所提出的算法比其他兩個算法排序效果更好。圖5為在查詢條件為“Earth”下，初始的查詢返回結(jié)果和3種重排序算法重排序后返回的結(jié)果示例。方框內(nèi)的圖像是與查詢不相關(guān)的圖像，可以看出本文所提算法可以較好剔除不相關(guān)的圖像。

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

表1 在檢索深度為100情況下3種重排序算法性能的比較

3.3 不同檢索深度情況下三種重排序算法性能比較

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

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

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

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

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

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

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

4 結(jié)論

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

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

[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.

國家自然科學(xué)基金項目(61602004, 61472001)；安徽省自然科學(xué)基金項目(1408085MF122，1508085MF127)；安徽省高校自然科學(xué)研究重點項目(KJ2016A041)；安徽大學(xué)信息保障技術(shù)協(xié)同創(chuàng)新中心公開招標(biāo)課題(ADXXBZ2014-5 ADXXBZ2014-6).

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

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

10.11990/jheu.201508029

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

TP391

A

1006-7043(2016)10-1387-07

趙鵬，陳浩，劉慧婷，等. 一種基于圖的多模態(tài)隨機游走重排序算法[J]. 哈爾濱工程大學(xué)學(xué)報， 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.