基于近鄰可視的圖像瀏覽方式研究

摘要:針對圖像搜索引擎的結果，對圖像集依據視覺相似度將視覺相近的圖像組織在一起，提供給用戶一個有效的瀏覽接口#65377;為降低計算時間，提出一種基于關鍵維的近鄰搜索算法#65377;實驗證明了以上算法的有效性#65377;

關鍵詞:圖像檢索; 結果瀏覽; 最近鄰; 關鍵維

中圖分類號:TP391.41文獻標志碼:A

文章編號:1001-3695(2007)10-0200-03

隨著互聯網及數字圖像技術的發展，互聯網上可獲得的圖像信息也在飛速增長，基于Web的圖像檢索技術得到了人們的廣泛關注#65377;現有的一些圖像搜索引擎[1，2]均是基于傳統的關鍵字搜索技術，也沿用著文本檢索中的算法，對檢索返回的結果，依據網頁的相關等級算法返回給用戶，并不對圖像視覺特征本身進行分析，因此，不適合用戶對搜索返回的圖像集進行瀏覽和比較#65377;Kerry Rodden等人[3]的研究結果表明，在圖像檢索系統中，對圖像的合理組織可以有效提高檢索效率#65377;本文針對圖像搜索結果，提出基于近鄰可視化的圖像瀏覽方式，將搜索返回的圖像集按其視覺特征進行組織，使得視覺上相似的圖像瀏覽時也相近，這樣提供給用戶一個有效的瀏覽方式，方便用戶對搜索返回的圖像集進行瀏覽和比較，提高了圖像檢索的效率#65377;本文通過逐步擴展圖像在檢索集中的k近鄰，實現基于近鄰可視的圖像瀏覽方式#65377;在信息檢索領域中，檢索的實時性是不容忽視的，為提高高維空間中最近鄰搜索效率，筆者提出了基于關鍵維的近鄰搜索算法#65377;通過實驗證明，本文提出的算法有效地提高了計算性能#65377;

本文的主要工作在于:對于圖像檢索結果的組織，基于圖像的視覺特征提出一種基于近鄰可視化的圖像瀏覽方式;針對高維空間中，計算k近鄰搜索的高時間復雜度，提出一種基于關鍵維的k近鄰搜索算法#65377;

1相關工作介紹

搜索引擎在追求搜索速度的同時也犧牲了搜索的精確度#65377;也正是由于追求搜索速度，增加了用戶判斷信息相關性的難度#65377;用戶在享受基于自由文本檢索方便的同時不得不花費大量的時間來對檢索結果進行甄選#65380;評估#65377;隨著Web上的信息不斷增多，信息過載與信息迷航成為網絡信息搜索中越來越嚴重的問題#65377;Internet中大多搜索引擎采用文檔向量空間模型進行關鍵詞的匹配來決定檢索結果，而在HTM網頁中的顯示并沒有涉及到語義內容，因此搜索引擎并不能真正理解用戶的檢索意圖[4]#65377;借助于可視化方式，既可以提供整體瀏覽，用戶也可選任意其中的某點，了解對應相關的詳細信息#65377;Ben Shneidenman提出人機界面設計的原則#65377;其中在信息檢索可視化過程中最重要的是:提供信息反饋;允許檢索過程的可逆;支持檢索策略控制;減少檢索記憶負擔;提供一般用戶和專家用戶的界面選擇等[5]#65377;

已有研究者[6~11]對圖像搜索結果的組織進行了一些討論，聚類分析在信息檢索中的應用也已有較長的歷史#65377;Cai Deng等人[6]對返回的圖像集基于文本信息聚類，在此結果上再進行基于視覺的聚類分析#65377;Li Zuiwei等人[7]認為每一幅圖像均由兩類區域組成，即關鍵區和背景區#65377;假設搜索引擎返回的圖像集語義是一致的，圖像之間的差別在其背景區，因此，對每一幅圖像提取關鍵區，然后對背景區進行分類處理#65377;W.Sunayama等人[8]提出的算法對圖像相關網頁中提取文本信息進行分析，統計出現頻率高的詞作為圖像的標簽，去掉出現頻率高但與所搜索的關鍵字無關的標簽，然后對標簽集進行短語關聯以及共現關聯處理，選擇出合適的label集，將搜索返回的圖像集按照標簽集進行分類#65377;Liu Hao等人[11]將圖像集按照其視覺的相似性映射到二維網格上，提供給用戶瀏覽#65377;

在高維空間中，兩點間的距離計算具有較高的時間復雜度，因此，高維空間中的最近鄰搜索算法的瓶頸，采用基于關鍵維的搜索策略證明關鍵維的應用將有效地提高高維空間中的相似搜索效率[12，13]#65377; 

2基于近鄰可視的圖像瀏覽方式

本文用圖像所對應的k近鄰來實現近鄰可視的圖像瀏覽方式，用近鄰子集來表示圖像集，可使得圖像集中視覺特征相似的圖像在瀏覽器中也是相鄰的#65377;

2.1特征提取算法[14]

圖像特征的提取是實現檢索的基礎，顏色是圖像非常重要的視覺特征#65377;相對于其他特征(如紋理#65380;形狀特征等)，顏色特征非常穩定，具有對旋轉#65380;平移變化不敏感等特點，表現出很強的魯棒性#65377;本文采用顏色特征來表示圖像的視覺內容#65377;

在顏色表示方面，HSI模型比RGB模型更符合人的視覺感應;在顏色特征方面，顏色直方圖描述了圖像顏色的統計分析特征，且具有平移#65380;尺度和旋轉不變性#65377;以HSI空間中顏色分布的直方圖來描述圖像整體的顏色特征，將HSI顏色空間的三個分量根據人眼對色彩的視覺感知進行適當的量化，在此基礎上計算圖像的72維顏色直方圖#65377;

關鍵維k的選擇很關鍵，筆者對數據集V進行隨機采樣，選擇采樣數據中方差最大的維為關鍵維k#65377;

2.4圖像集的瀏覽

搜索返回的圖像集通常較大，因此隨機選取一個圖像子集生成初步瀏覽目錄集#65377;用戶點擊相應的圖片后，系統將返回以該圖片為中心的近鄰圖像子集，用戶可點擊近鄰集中的圖像來進行下一輪的近鄰搜索及瀏覽，從而找到所需要的圖片#65377;

3實驗分析

本文提出的基于關鍵維的最近鄰搜索算法的性能測試結果，以及在此基礎上實現的近鄰可視化圖像結果瀏覽方式的有效性分析#65377;以Google圖像檢索引擎的返回結果集為初始的實驗數據集，選取檢索結果前1 000幅圖像，用文中的算法進行分析和組織#65377;在賽揚2.66 GB/256 MB的PC機上，使用Windows XP操作系統，用VC++ 6.0對本文算法進行了實驗#65377;

3.1瀏覽方式對比

使用相同的數據集對不同的瀏覽方式進行測試比較#65377;在Google圖像搜索引擎上用六個不同的關鍵字進行圖像檢索，將每一次返回的前200幅圖片作為數據測試集#65377;測試中所使用的檢索關鍵字有天子山#65380;足球#65380;蘋果#65380;長城#65380;日出#65380;草原#65377;分別計算每幅圖的72維特征矢量#65377;

圖1為Google檢索返回的結果，每一頁顯示與檢索關鍵字相關的20幅圖片，用戶可以點擊下一頁查看更多的圖片#65377;Google的圖像排列依據是一些網頁的等級算法，檢索返回的結果集雖在語義上是相關的，但相鄰圖像之間的視覺特征并不相關，瀏覽起來略顯雜亂，不便于比較和選擇#65377;

圖2為基于聚類的表達方式，用Kmeans算法將200幅圖片聚成五類，并為每一類隨機選擇一個代表圖#65377;左邊顯示每一類的代表圖片，右邊顯示的是相關類中的圖片#65377;用戶可以選擇相應的代表圖來查看對應類中的圖片#65377;聚類結果具有類間低相似#65380;類內高相似的特點，但類內數據沒有得到較好的組織，因此，用戶對數據集的分布只有大概的了解，但仍不便于將類內的數據集進行比較#65377;值得指出的是，該聚類算法的時間復雜度較高#65377;

本文提出的基于近鄰可視的瀏覽方式，實驗中的瀏覽器使用一個5×5的網格#65377;首先隨機給出目錄集，用戶點擊相應的目錄圖片后，返回以該圖為中心展開的k(=8)近鄰;然后分別計算其k近鄰的k(=2)近鄰#65377;用戶可繼續點擊近鄰集中的圖像來進行下一輪的近鄰搜索及瀏覽，從而找到所需要的圖片#65377;圖3是目錄集，圖4是以某目錄節點展開后的近鄰圖像子集#65377;

可以看出，該算法通過提取圖像的視覺特征，將視覺上相近的圖片組織在一起，構造一個目錄與子集的兩層瀏覽模式，更方便用戶比較與選擇，即目錄給用戶提供了一個對整體圖像集的大致瀏覽，相關的子集則提供給用戶進行細節的比較#65377;用戶可以根據自己的喜好逐步瀏覽圖像集，由于近鄰集本身的特性，用戶只是逐漸瀏覽到感興趣的圖片集#65377;該算法對噪聲圖片有一定程度的過濾#65377;

3.2算法性能分析

考慮到算法的實際應用環境，實驗均是針對小型的數據集#65377;首先提取圖片集中每一幅圖片的72維顏色直方圖;然后選取一關鍵維，隨機選取目錄集返回給用戶瀏覽，用戶選擇感興趣的目錄圖片，用文中提出的基于關鍵維的最近鄰搜索法計算對應節點的近鄰點，返回給用戶瀏覽以該目錄節點展開的最近鄰圖像子集#65377;計算每幅圖片的72維特征矢量，在矢量集上，按照本文提出的算法#65380;逐一比較算法搜索最近鄰及Mtree[15]算法分別計算其k(=10)近鄰#65377;主要用搜索過程中節點距離的計算次數來衡量算法的性能(圖5)#65377;

從圖5中可以看出，相比于傳統的逐一比較算法，使用本文的最近鄰搜索算法，由于使用了一個關鍵維，在計算時不斷縮小搜索范圍，避免了逐個計算兩點間的距離，從而減少了搜索的時間，性能有所提高#65377;而Mtree算法在小型數據集中優勢全無，節點間的計算次數大于節點集的個數，性能劣于逐一比較法，且該計算次數僅是查詢時需要比較的次數，不包括建樹時的計算#65377; 

4結束語

本文對圖像搜索引擎的結果再次進行了分析，將圖像集按照相似度進行組織，提供給用戶一個有效的瀏覽接口#65377;為了降低計算時間，提出了一種有效的基于關鍵維的k近鄰搜索算法，在Google搜索結果上的實驗分析顯示，基于近鄰可視的瀏覽方式是有效的#65377;實驗證明，該近鄰搜索算法提高了計算效率#65377;下一步工作將圍繞圖像的語義分析#65380;結合圖像的語義以及視覺特征，拉近底層視覺特征與高層語義特征之間的鴻溝，從而提供更有效的檢索人機接口#65377;

參考文獻:

[1]Google image search[EB/OL].[2006].http://images.google.cn/.

[2]Alta vista image search[EB/OL].[2006].http://www.altavista.com/image.

[3]RODDEN K， BASALAJ W， SINCLAIR D， et al. Does organisation by similarity assist image browsing[C]//Proc of the SIGCHI Conference on Human Factors in Computing System. New York: ACM Press， 2001.

[4]文燕平.WWW信息檢索可視化研究[D].武漢:武漢大學，2004.

[5]李愛國，汪社教.信息檢索可視化[J].信息檢索技術，2004(2):50-52.

[6]CAI Deng，HE Xiaofei，LI Zhiwei， et al. Hierarchical clustering of WWW search results using visual， textual and link information[C]//Proc of the 12th Annual ACM International Conference on Multimedia. New York: ACM Press， 2004:952-959.

[7]LI Zhiwei， XU Gu， LI Mingjing. Grouping WWW image search results by novel inhomogeneous clustering method[C]//Proc of the 7th Int Multimedia Modeling Conference.[S.l.]: IEEE， 2005.

[8]SUNAYAMA W， AKIKO， YACHIDA M. Image clustering system on WWW using Web texts[C]//Proc of the 4th Int Conf on Hybrid Intelligent Systems. Washington， DC: IEEE Computer Society， 2004.

[9]MUKHERJEA S， HIRATA K， HARA Y.Using clustering and visualization for refining the results of a WWW image search engine[C]//Proc of Workshop on New Paradigms in Information Visualization and Manipulation. New York: ACM Press， 2000.

[10]DESELAERS T， KEYSERS D， NEY H. Clustering visually similar images to improve image search engines[C]//Informatiktage der Gesellschaft für Informatik. Bad Schussenried， Germany:[s.n.]， 2003.[11]LIU Hao， XIE Xing， TANG Xiaoou， et al. Effective browsing of Web image search results[C]//Proc of the 6th Int Conf on Multimedia Information Retrieval. New York: ACM Press， 2004.

[12]周項敏，王國仁.基于關鍵維的高維空間劃分策略[J].軟件學報，2004，15(9):13611374.

[13]胡建軍，唐常杰，李川，等.基于最近鄰優先的高效聚類算法[J].四川大學學報:工程科學版，2004，36(6):93-99.[14]李弼程，彭天強，彭波.智能圖像處理技術[M].北京:電子工業出版社，2004.

[15]CIACCIA P， PATELLA M， ZEZULLA P. Mtree: an effective access method for similarity search in metric spaces[C]//Proc of the 23rd Int Conf on VLDB. Athens: Morgan Kaufmann， 1997:426-435.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”