基于反饋框架的交互式圖像檢索系統?

朱 翔 林學飛

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

基于反饋框架的交互式圖像檢索系統?

朱 翔 林學飛

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

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

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

1 引言

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

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

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

2 相關工作

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

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

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

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

3 工作流程與方法

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

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

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

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

3）基于用戶反饋調整自適應改變聚類結果，構建排序候選集，最終利用改進排序算法進行最終排序。

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

3.1 圖像收集以及特征提取

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

3.1.1 特征提取

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

3.1.2 TF-IDF向量

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

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

3.1.3 歸一化降維模塊設計

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

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

3.2 優化聚類

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

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

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

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

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

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

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

3.3 構建候選集

用戶調整縮放因子，實際直接改變聚類數k，進而調整聚類結果，聚類結果的改變直接調整重排候選集，利用重排算法實現結果多樣性和相關性的平衡以滿足不同用戶的意圖。

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

其中，我們有如下成立：

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

同時，根據用戶的調整因子的不同，候選集對多樣性以及相關性的側重點會有所不同。當用戶的調整因子小時，那么聚類數就小，最終聚類結果就小，所以在構造候選集時類中相似圖像會相對較多。那么最終的排序結果多樣性相對較小。當用戶增大縮放因子，那么候選集差異性圖像增多，最終排序結果多樣性增大。

3.4 改進排序算法

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

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

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

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

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

4 實驗結果

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

圖3 系統用戶界面的一個樣例

圖4 實驗結果對比

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

圖5 用戶滿意度的比較

圖6 縮放因子的影響

5 結語

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

［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］解洪勝，王連國，孫玉芳.模糊顏色直方圖在基于內容的圖像檢索中的應用研究［J］.計算機系統應用，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］童振興.基于內容的圖像檢索技術綜述與展望［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日

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