朱 翔 林學飛

（南京理工大學計算機科學與工程學院 南京 210094）

基于反饋框架的交互式圖像檢索系統(tǒng)?

朱 翔 林學飛

（南京理工大學計算機科學與工程學院 南京 210094）

隨著圖像數(shù)量的迅猛增長，圖像檢索已經(jīng)在計算機視覺領(lǐng)域引起了越來越多的關(guān)注。遺憾的是，其中也存在著人們的檢索需求和搜索結(jié)果不一致的問題。為此，論文基于改進的聚類算法和重排名算法，提出一種基于反饋框架的交互式圖像檢索系統(tǒng)來自適應地展示檢索結(jié)果，從而獲得更佳的用戶體驗。檢索結(jié)果的多樣性由一個縮放因子來控制，用戶可以根據(jù)自己的意圖自由地放大或縮小縮放因子，相當于調(diào)整了聚類中心數(shù)目k。該系統(tǒng)演示上傳于https：//youtu.be/hYnx3UkVQEA。

圖像檢索；用戶界面；縮放因子；多樣性

1 引言

近幾年來，圖像數(shù)量的快速增長已經(jīng)在多媒體領(lǐng)域引起了巨大關(guān)注。在這期間，前人提出了許多的圖像檢索算法，例如基于內(nèi)容的圖像檢索和基于標簽的圖像檢索［1～2，17］。這些方法的主要出發(fā)點在于考慮如何有效地提高檢索的精度。不過遺憾的是，通常這些方法存在檢索結(jié)果和用戶期望不一致的鴻溝。需要強調(diào)的一點是，在設(shè)計圖像檢索系統(tǒng)時將用戶意圖納入考慮是一件非常具有挑戰(zhàn)性的任務。

在文獻［3］的主要思想中，相關(guān)反饋包含正反饋和負反饋，作者通過設(shè)計反饋框架來表述用戶對檢索結(jié)果相關(guān)性程度的評估。在該文章中，用戶需要給出檢索結(jié)果與其期望是否相符的反饋。不過，這樣的做法會帶來額外的認為參與，從而導致更差的用戶體驗。另一方面，由于存在大量的圖片，當前搜索引擎返回的優(yōu)先檢索結(jié)果基本上是重復的?？v觀前人的工作，很少關(guān)注如何能夠在任何情況下，從用戶執(zhí)行的操作推斷出隱式的相關(guān)性反饋，例如眼睛的眨動［4］。不同于先前的工作，我們注重設(shè)計一個更加自然的隱式相關(guān)性反饋框架從而完成交互式的圖像檢索任務。

為了解決上述存在的問題，本文提出一個可以自由控制檢索結(jié)果的相關(guān)性和多樣性的全新的反饋框架?；谏鲜瞿繕?，我們引入一個縮放因子來捕捉用戶在圖像檢索中的意圖。通過調(diào)節(jié)縮放因子，實際上是對聚類算法中的初始聚類中心數(shù)目k進行調(diào)整修改，用戶可以直接瀏覽具有不同相關(guān)性和多樣性得分的返回結(jié)果。為了確?？s放因子能夠有效控制檢索結(jié)果，我們利用改進的聚類算法來對相似性相關(guān)的圖片進行有效分組。通過縮放因子的調(diào)節(jié)和提出的重排算法，可以使得檢索結(jié)果與用戶期望達成一致，從而緩解用戶期望與檢索結(jié)果之間的鴻溝。因此，該系統(tǒng)取得了更好的用戶體驗。

2 相關(guān)工作

前人對圖像檢索技術(shù)［6］的研究已經(jīng)有了很多年的積累，關(guān)于相關(guān)性的研究遠遠超過了多樣性。趙等［7］從貝葉斯角度和圖像特征方向來計算圖像的語義相關(guān)性從而獲得最符合查詢的結(jié)果標簽。錢等［9］通過利用社交圖片的多樣性語義給圖片重新打上標簽進而改善圖像的標簽質(zhì)量。上述的這些方法可以改善基于標簽的圖像檢索方法，但是存在著丟失多樣性的問題。

近幾年關(guān)于相關(guān)結(jié)果多樣化的研究大致可以分為三個方面：重排名，聚類和去重。Thomas等［10］定義了一套標準來評價檢索結(jié)果的相關(guān)性和多樣性，王等［8］通過計算候選集圖像的視覺和語義相似性得分，提出了一種重排名策略，他們設(shè)計了一種貪婪算法來優(yōu)化平均多樣精度（ADP）。Marina等［11］提出一種名為DisC的多樣性定義，在一個查詢結(jié)果的多樣性子集中，每個返回值都應當代表一個子主題，并且彼此之間不相似。

通過對檢索結(jié)果進行有效聚類［12］，我們可以找到每個類別具有代表性的圖片。蔡等［13］利用視覺和文本信息進行層次聚類，Alex等［5］提出一種新的聚類方法，主要思想源于聚類中心比鄰居點具有更高的密度。區(qū)別于聚類算法，去重法直接對檢索結(jié)果中的重復圖片進行刪除。Fishchlla等［14］基于局部敏感哈希的思想對檢索結(jié)果中的重復項進行檢測，他們利用存在的相似點對，動態(tài)地進行查詢。

不難發(fā)現(xiàn)的是，上述方法都存在相同的缺點，例如聚類中心數(shù)目的不確定性以及在聚類過程中忽略圖片的相關(guān)性。去重算法需要設(shè)定一個閾值，該值對檢索結(jié)果的多樣性結(jié)果具有直接的重要影響。此外，在單個矩陣中同時考量相關(guān)性和多樣性是一件很困難的事。為了解決上述存在的問題，我們提出了一種新的重排名算法來進行聯(lián)合優(yōu)化。

3 工作流程與方法

本文提出了一個基于反饋框架的交互式圖像檢索方案，圖1說明了該系統(tǒng)的工作流程。該反饋框架可用于圖像檢索領(lǐng)域，有助于幫助用戶獲取更加符合期望的結(jié)果。從圖1中我們可以看到，整個系統(tǒng)主要包含以下幾個部分：

圖1 基于反饋框架的交互式圖像檢索流程圖

1）圖像收集以及特征提?。何覀儚膱D像分享網(wǎng)站Fliker上大規(guī)模地收集具有元數(shù)據(jù)的圖像，其中元數(shù)據(jù)包括用戶提供的標簽信息等。然后我們執(zhí)行一些必要的預處理步驟，包括提取視覺特征和處理紋理信息。最后為我們數(shù)據(jù)庫中的圖片設(shè)置索引。

2）基于文獻［5］的思想，我們同時計算每張圖像的密度峰值，前k個圖像用來執(zhí)行初始化劃分。然后基于K-means算法將結(jié)果進行聚類。

3）基于用戶反饋調(diào)整自適應改變聚類結(jié)果，構(gòu)建排序候選集，最終利用改進排序算法進行最終排序。

我們令符號I={i m1，im2，…，imN}表示圖像集，令表示圖像i的標簽集，重排算法將利用圖像的綜合信息重新構(gòu)建子集S={i ms1， ims2， …， imsk}，S∈I并且 | S|=K，K≤N 。

3.1 圖像收集以及特征提取

從圖像分享網(wǎng)站上大規(guī)模地收集具有元數(shù)據(jù)的圖像，其中元數(shù)據(jù)包括用戶提供的標簽信息等。然后我們執(zhí)行一些必要的預處理步驟，包括提取視覺特征和處理紋理信息。最后為我們數(shù)據(jù)庫中的圖片設(shè)置索引。

3.1.1 特征提取

這里綜合考慮時間、效率等因素提取了顏色直方圖［15］、全局 gist［16］特征、邊緣直方圖形成一個融合特征作為輸入。

3.1.2 TF-IDF向量

圖像對應的標簽，類別眾多，形式各異，因此就需要將所有的標簽信息拼接成一個句子，作為圖像

語義的描述信息。對于整個數(shù)據(jù)集的語義信息，需要計算圖像標簽中的TF-IDF權(quán)值向量。

3.1.3 歸一化降維模塊設(shè)計

特征歸一化：特征之間存在著一定的差異性，每個特征的值域都各不相同，所以需要用歸一化操作來消除這一影響。為了數(shù)據(jù)處理方便，系統(tǒng)利用線性函數(shù)歸一化把數(shù)據(jù)映射到0～1范圍之內(nèi)處理，更加便捷快速。線性歸一化方法為

特征降維：主成分分析（PCA）是多元統(tǒng)計分析中用來分析數(shù)據(jù)的一種方法，它是用一種較少數(shù)量的特征對樣本進行描述以達到降低特征空間維數(shù)的方法，它的本質(zhì)實際上是K-L變換。

3.2 優(yōu)化聚類

本文基于文獻［5］的思想，我們同時計算每張圖像的密度峰值，前k個圖像用來執(zhí)行初始化劃分。然后基于K-means算法將結(jié)果進行聚類。

K-means算法的基本思想是：以空間中k個隨機點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。但是K-means的問題就是：1）初始聚類圖像難以確定，隨機選取就會導致每次聚類的結(jié)果會變化。2）聚類中心的個數(shù)難以確定。針對這兩個問題，本系統(tǒng)通過兩種方式很好的加以解決，詳見圖2。

圖2 改進的K-means聚類算法

針對第一個問題，本文利用計算密度峰值，即圖像的代表性來獲取初始圖像，這里需要兩個重要的參數(shù)：

其中，dij表示imi與imj之間的距離并且dc表示截斷距離。一般性來說，ρi表示與點i的距離小于dc所有點的連續(xù)值。dc取值本文取平均距離。

根據(jù)密度峰值的大小對圖像進行排序，選取值最大的k幅圖像進行K-means聚類的初始值，最終迭代生成聚類結(jié)果。

針對聚類中心個數(shù)的問題，我們將其交由用戶調(diào)控，通過用戶的反饋，來調(diào)整聚類結(jié)果，最終改變重排結(jié)果。

3.3 構(gòu)建候選集

用戶調(diào)整縮放因子，實際直接改變聚類數(shù)k，進而調(diào)整聚類結(jié)果，聚類結(jié)果的改變直接調(diào)整重排候選集，利用重排算法實現(xiàn)結(jié)果多樣性和相關(guān)性的平衡以滿足不同用戶的意圖。

這里，將縮放因子引入K-means以實現(xiàn)聚類的重新生成，針對每一個類，將所有的圖像根據(jù)peak（密度峰值）的大小進行重排列以求出k個中心。

其中，我們有如下成立：

針對重排的聚類結(jié)果可以發(fā)現(xiàn)類與類之間差異性大，類間圖像之間相似性大，分別對應結(jié)果中的多樣性和相關(guān)性，但是，類中圖像通過密度峰值即代表性排序之后，排序靠后的圖像并不具有代表性，所以本文將利用每個類的前60%圖像構(gòu)建最后所需排序的候選集，這個候選集有來自同一個類的最具代表性的同類圖像，又有不同類的差異性圖像，所以這個候選集去除了過于相似且不具有代表性的圖像，最終簡化了候選集的大小。

同時，根據(jù)用戶的調(diào)整因子的不同，候選集對多樣性以及相關(guān)性的側(cè)重點會有所不同。當用戶的調(diào)整因子小時，那么聚類數(shù)就小，最終聚類結(jié)果就小，所以在構(gòu)造候選集時類中相似圖像會相對較多。那么最終的排序結(jié)果多樣性相對較小。當用戶增大縮放因子，那么候選集差異性圖像增多，最終排序結(jié)果多樣性增大。

3.4 改進排序算法

根據(jù)［8］提出的DRR排序算法，本文提出了一個基于多樣性、代表性和相關(guān)性的重排算法。對提供的重排候選集進行重新排列最終形成重排的結(jié)果。排序的方法就是利用最優(yōu)化的操作方式。首先提出一個計算標準，然后不停地迭代計算圖片的在這個標準下的值。每次選取最大的那個圖像插入到最終的圖像列表中去。迭代的標準函數(shù)為

函數(shù)F(i)表示第i幅圖像的綜合多樣性、相關(guān)性、和代表性的值。這里函數(shù) R(?)，Div(?)，Peak(?)分別表示相關(guān)性、多樣性以及代表性的值。Si表示最終排序列表中已經(jīng)重排序好i幅圖像。下面分別對表示相關(guān)性、多樣性以及代表性的計算方法進行闡述：

相關(guān)性表示的是兩個方面：圖像與檢索詞的相關(guān)性，圖像與圖像之間的相關(guān)性，由于系統(tǒng)的圖像是以相關(guān)性的方式進行檢索下載的，所以圖像的下載就是一個相關(guān)性遞減的過程，因此我們將圖片原始下載的排序位置作為圖像相關(guān)性的表述（i表示圖像的位置）：

多樣性表述的是待選圖像與已經(jīng)重排好的所有圖像的差異性，這里我們利用到上述的相似度矩陣，公式如下（R表示候選集，S(i，j)表示圖像的混合相似度）：

代表性表述的是圖像代表性計算值，之前已經(jīng)提到過。公式如下（normalize表示歸一化操作）

4 實驗結(jié)果

圖3簡單說明了一個用戶可以與之互動的應界面。界面的左邊將聚類結(jié)果進行顯示，每一類將選取最具代表性的三張圖片，并且可以根據(jù)用戶的選擇顯示出每類的所有圖片，顯示的所有的圖像將按照代表性排序的方式展示。此外，相比較于傳統(tǒng)的圖像檢索界面，我們特別在界面的下方加了滑動條。不同位置的滑動條正好對應于不同取值的縮放因子，最左邊的位置對應于縮放因子取值為0，最右邊對應于最大值的縮放因子。當用戶調(diào)節(jié)滑動條時，改變了系統(tǒng)當前的縮放因子，也即是改變了當前聚類中心數(shù)k，系統(tǒng)將根據(jù)用戶意圖實時地顯示當前返回結(jié)果。從左向右滑動滑動條時，圖片在相關(guān)性的基礎(chǔ)的逐步的增加圖片的多樣性，所呈現(xiàn)的靠前的圖片所包含的話題量將會增大，用戶將獲得更多的信息，即所獲取到的圖片多樣性得到增強。在圖4中，我們將本文提出的DRCR算法與傳統(tǒng)的基于相關(guān)性的檢索算法和DRR［8］算法進行了實驗對比，統(tǒng)計了在不同查詢結(jié)果下的ADP值。實驗結(jié)果表明了本文提出的方法的有效性。

圖3 系統(tǒng)用戶界面的一個樣例

圖4 實驗結(jié)果對比

為了有效地執(zhí)行圖像檢索的任務，我們首先需要從Fliker上爬取大量的圖片。同時為了證明該反饋框架的有效性，我們也進行了用戶調(diào)查，我們一共邀請了30位經(jīng)常在線檢索圖像的用戶來進行這份用戶研究。每個用戶根據(jù)他們對檢索結(jié)果的滿意度按照｛1，2，3，4，5｝進行打分，打分結(jié)果與用戶滿意度成正相關(guān)，打分越高，則代表其對結(jié)果的滿意度越高。在圖5中，我們將提出的系統(tǒng)與傳統(tǒng)的不具有縮放因子的系統(tǒng)進行有效對比，對比結(jié)果有力地說明了我們的系統(tǒng)具有更好的用戶的滿意度，證明了該方法的有效性。此外，為了更加鮮明地展示縮放因子對聚類算法的作用，我們在圖6中以“蘋果”作為一條查詢進行具體說明。從圖6中不難看出，系統(tǒng)針對不同的縮放因子顯示不同的檢索結(jié)果，本質(zhì)是當前（b）的聚類數(shù)目要多于（a）中。后者（b）顯然返回了更加相關(guān)且多樣性豐富的檢索結(jié)果，也更加滿足用戶的檢索需求。

圖5 用戶滿意度的比較

圖6 縮放因子的影響

5 結(jié)語

本文提出的基于反饋框架的交互式圖像檢索系統(tǒng)，不僅考慮到了檢索結(jié)果的相關(guān)性要求，同時將多樣性指標考慮其中，利用縮放因子的手動調(diào)整改變初始聚類中心數(shù)，利用密度峰值概念完成聚類樣本中心的選取。實驗證實本文提出的基于多樣性，代表性和相關(guān)性的重排算法取得了更好的ADP值，使得最終的檢索結(jié)果同時滿足相關(guān)性與多樣性的要求，更加契合用戶需求，具有一定的優(yōu)越性。

［1］Smeulders A W M，Worring M，Santini S，et al.Content-Based Image Retrieval at the End of the Early Years［J］.IEEE Transactions on Pattern Analysis&Machine Intelligence，2000，22（12）：1349-1380.

［2］Datta R，Joshi D，Li J，et al.Image retrieval：Ideas，influences，and trends of the new age［J］.Acm Computing Surveys，2008，40（2，article 5）：2007.

［3］Xiang S Z，Huang T S.Relevance feedback in image retrieval：A comprehensive review［J］.Multimedia Systems，2003，8（6）：536-544.

［4］Jech T.Can relevance of images be inferred from eye movements［M］.Following the tracks of Ennin's 9th c.journey：.China Intercontinental Press，2007：134-140.

［5］Rodriguez A，Laio A.：Machine learning.Clustering by fast search and find of density peaks.Science，2014，344（6191）：1492-6.

［6］Sun A，Bhowmick S S.Image tag clarity：in search of visual-representative tags for social images［C］//Sigmm Workshop on Social Media.ACM，2009：19-26.

［7］Zhao Y，Zha Z J，Li S，et al.Which Tags Are Related to Visual Content［C］//Advances in Multimedia Modeling，InternationalMultimediaModelingConference，MMM 2010，Chongqing，China，January 6-8，2010.Proceedings.2010：669-675.

［8］Wang M，Yang K，Hua X S，et al.Towards a Relevant and Diverse Search of Social Images［J］.IEEE Transactions on Multimedia，2010，12（8）：829-842.

［9］Qian X，Hua X S，Tang Y Y，et al.Social Image Tagging With Diverse Semantics［J］.Cybernetics IEEE Transactions on，2014，44（12）：2493-2508.

［10］Deselaers T，Gass T，Dreuw P，et al.Jointly optimising relevance and diversity in image retrieval［C］//ACM International Conference on Image and Video Retrieval，Civr 2009，Santorini Island，Greece，July.2009：1-8.

［11］Drosou M，Pitoura E.DisC diversity：result diversification based on dissimilarity and coverage［J］.Proceedings of the Vldb Endowment，2012，6（1）：13-24.

［12］Zechao Li，Jing Liu，Yi Yang，et al.Clustering-Guided Sparse Structural Learning for Unsupervised Feature Selection［J］.IEEE Transactions on Knowledges&sdata Engineering，2014，26（9）：1-1.

［13］Cai D，He X，Li Z，et al.Hierarchical Clustering of WWW Image Search Results Using Visual［C］//ACM International Conference on Multimedia，2004：952-959.

［14］Fisichella M，Deng F，Nejdl W.Efficient Incremental Near Duplicate Detection Based on Locality Sensitive Hashing.［C］//Database and Expert Systems Applications，International Conference，DEXA 2010，Bilbao，Spain，August 30-September 3，2010，Proceedings.2010：152-166.

［15］解洪勝，王連國，孫玉芳.模糊顏色直方圖在基于內(nèi)容的圖像檢索中的應用研究［J］.計算機系統(tǒng)應用，2009，18（5）：139-143.XIE Hongsheng，WANG Lianguo，SUN Yufang.Application of Content-Based Image Retrieval with Fuzzy Color Histogram［J］.Computer Systems Application，2009，18（5）：139-143.

［16］Oliva A，Torralba A.Modeling the Shape of the Scene：A Holistic Representation of the Spatial Envelope［J］.International Journal of Computer Vision，2001，42（3）：145-175.

［17］童振興.基于內(nèi)容的圖像檢索技術(shù)綜述與展望［J］.計算機光盤軟件與應用，2010，5（6）：88-88.TONG Zhenxing.Review and prospect of content-based image retrieval technology［J］.Computer CD-ROM Software and Application，2010，5（6）：88-88.

Interactive Image Search System Based on Feedback Framework

ZHU Xiang LIN Xuefei
（School of Computer Science and Engineering，Nanjing University of Science&Technology，Nanjing 210094）

With the explosive growth of the number of images，image search has been drawing much interest from the research community.However，there exists the inconsistency between people's search needs and the search results.Towards this end，this paper presents a new feedback framework for interactive image retrieval by adaptively displaying the search results，which can obtain better user experience.The diversity of search results is controlled by introducing a zoom factor，which makes users freely zoom in or out on the results according to their intents.The demo is available at https：//youtu.be/hYnx3UkVQEA.

image search，interface，zooming-factor，diversity

TP391

10.3969/j.issn.1672-9722.2017.11.041

Class Number TP391

2017年5月7日，

2017年6月28日

朱翔，男，碩士研究生，研究方向：圖像檢索模式識別。林學飛，男，碩士研究生，研究方向：圖像檢索。