基于改進視覺字典模型的圖像檢索算法

李 強， 左 欣， 沈繼鋒， 徐云凱， 宋 穎

（1.江蘇科技大學 計算機科學與技術，江蘇 鎮江 212000；2.江蘇大學 電氣信息工程學院，江蘇 鎮江 212003）

基于改進視覺字典模型的圖像檢索算法

李 強1， 左 欣1， 沈繼鋒2， 徐云凱1， 宋 穎1

（1.江蘇科技大學 計算機科學與技術，江蘇 鎮江 212000；2.江蘇大學 電氣信息工程學院，江蘇 鎮江 212003）

目前在圖像檢索領域，由于視覺字典其性能突出，已成為圖像檢索領域構建視覺詞典的主流方法。但傳統的視覺字典方法存在運行時間效率低、內存消耗大等缺點。因此本文采用ROOTSift算法提取圖像的特征點并利用高效的K-means聚類算法建立支持動態擴充的隨機視覺字典。該方法基于視覺字典構建視覺詞匯直方圖和倒排序索引文件，并對視覺詞重新分配權重以提高檢索命中率。最后利用歐氏距離法查詢完成相似性匹配。試驗結果表明該方法能提高圖像檢索的準確率，對大規模的圖像檢索能夠達到很好的檢索質量。

圖像檢索；ROOTSift算法；K-means聚類；視覺字典

隨著多媒體技術和Internet的飛速發展，網上的數字圖片急劇增長。面對這些海量的圖像數據，如何快速有效的檢索到用戶所需要的圖片信息成為圖像處理領域的研究熱點。傳統的圖像檢索一般都是基于關鍵字的檢索方法，但是有時候人們想要通過圖片內容來檢索出類似的相關圖片。基于這種需要，基于圖像的圖像檢索研究成了近年來的研究熱點。

經過長時間和大量的分析，雖然圖像圖像檢索技術還不成熟，但是仍有部分研究機構、大型公司推出了一些檢索系統。如IBM、MIT、Standford等。而這些系統都存在著一些共性問題。比如在圖像匹配算法中遇到的高維圖像向量的“維度災難”。

針對上述問題，我們采用視覺字典的方法進行圖像檢索。視覺字典通過統計局部不變特征的全局出現情況來實現的，其特征既保留了局部特征的不變性又增加了全局特征的魯棒性，同時與數量龐大的局部不變特征相比還能起到簡化特征的作用。

為了提高檢索的準確率，提出了基于ROOTSift的改進視覺字典模型的圖像檢索算法。本算法采用ROOTSift算法高效的提取圖像的特征點，然后利用高效的K-means聚類算法建立支持動態擴充的隨機視覺字典，并且利用倒排排序建立索引，最后利用歐式距離來匹配相似度來達到匹配圖像的目的。

1 特征提取

1.1 SIFT

David G Lowe在1999年提出了尺度不變的特征（SIFT，Scale-Invariant Feature Transform），用來進行物體的識別和圖像匹配[1]，并于2004年進行了更深入的發展和加以完善[2]。SIFT算法是一種提取局部特征的算法，在尺度空間尋找極值點，提取位置，尺度，旋轉不變量。SIFT特征是圖像的局部特征，其對旋轉、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪音也保持一定程度的穩定性，并且其在獨特性方面也有不錯的效果，信息量豐富，適合用在海量特征數據庫中進行快速、準確的匹配。提取步驟如下圖。

圖1 SIFT算法步驟Fig.1 SIFT algorithm step

從圖1可以看出，SIFT算法包含4個主要步驟，其中使用高斯公式來檢測出現在任何一個尺度空間中的極值點，然后把這些極值點用相應的方法進行篩選，去除對比度低和邊緣點的極值點，進一步用特殊的公式來去除不穩定點最后得到了穩定的特征點，為每一個穩定的關鍵點統計它們的梯度和方向作為它們的方向參數。

SIFT算法最后生成關鍵點描述子如圖2所示。在每4×4的小塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，即可形成一個種子點，如上圖右部分所示。此圖中一個關鍵點由2×2共4個種子點組成，每個種子點有8個方向向量信息。為了增強匹配的穩健性，對每個關鍵點使用4×4共16個種子點來描述，這樣對于一個關鍵點就可以產生128個數據，即最終形成128維的SIFT特征向量。

圖2 SIFT特征向量Fig.2 SIFT feature vectors

以上是SIFT算法的詳細原理和步驟。但是經過大量的實驗，我們發現，采集出的特征點有很大的幾率受噪音等的影響。因此，選用了一種基于SIFT算法的改進版ROOTSift。

1.2 ROOTSift

ROOTSift是 sift的變形，不是真正的 sift，是 Harris+Surf。變形公式如下：

圖3 人物頭像縮放以后，相同特征點用連線連接Fig.3 Avatars after scaling，the same feature points with a wired connection

此方法得到的128維向量均為正值且兩兩差距較之前減少，這樣可以有效的降低噪音導致的影響。通過38張圖片12 000多個點比對，原來匹配1 125（2張誤匹配），使用ROOTSift后匹配1 207（3張誤匹配），提高9%。而其它原來匹配的圖片中匹配點更穩定。圖4為兩種區別。

由表1可知，ROOTSift算法有效的提高了特征點匹配的準確率，有利于最后的圖像匹配。

表1 圖4中SIFT和ROOTSift的匹配結果Tab.1 Matching result between SIFT and ROOTSift in picture 4

2 K-means均值聚類

聚類是一種無監督的學習方法，按照物以類聚的思想，將數據集中按數據之間的相似程度劃分為幾類，并且使得同一類或者簇中的樣本相似度盡可能大，反之則數據樣本的相似度盡可能小[3]。它的優點是算法復雜度低，簡單快捷。具體算法流程圖描述如圖5所示。

圖4 SIFT算法和ROOTSift算法的比較Fig.4 The comparison of the SIFT algorthm and ROOTSift algoritdm

圖5 K-means算法流程圖Fig.5 K-means algorithm flow chart

3 視覺字典的形成

字典是一種按照一定內部元素組成順序排列而成的一種方便查找修改的工具。而如果把圖像庫中的大量圖像按照圖像之間的某種關系將他們排列起來就形成了一部字典，這種字典可形象稱之為視覺字典。而之所以引入視覺字典這一概念，是為了克服低層特征和高層語義之間的“鴻溝”[4]。

視覺字典是基于上述兩步ROOTSift特征提取和K-means均值聚類而形成的一種數據。其主要思路如下：假定上述K-means聚類算法中成功聚類得出了K類，那么我們再重頭對圖像庫中的每幅圖像進行審定，判斷這幅圖像中的每個關鍵點的所屬聚類，為了更加直白的表示這種表示這種關系，我們選用直方圖作為承載物，每個直方圖有K個柱，每個柱的大小表示在這個聚類中這幅圖像的關鍵點數目，依次計算，就可以得到圖像庫中所有圖像的直方圖。把這些直方圖按照某種順序排列，就形成了需要的視覺字典。下面是視覺字典形成的主要步驟：

第1步 將用SIFT提取出的大量的關鍵點運用K-means聚類算法得出K個聚類中心。

第2步 為每幅圖片創建一個具有K個維度的向量V{v1，v2，……，vk}，初始均為0。我們這里可以形象成直方圖以方便理解。

第3步 提取圖像庫中的一幅圖像，對這幅圖像的每個關鍵點進行分析，判斷這個關鍵點是屬于i號聚類，則把vi加一。最后形成了這幅圖像的一個視覺直方圖，每幅直方圖又可稱之為視覺單詞。

第4步 重復第3步，直到將圖像庫中的圖像遍歷一遍。

第5步 將這些直方圖按照一定的格式保存成本地文件。視覺字典正式形成。

數據字典生成以后隨之而來的是新的問題：龐大的數據量如何行之有效的將它們組織在一起并且高效的進行搜索排序等操作呢？在這里，引入了一種數據結構來解決如上問題，這種數據結構就叫做倒排文件，所用算法稱為倒排序。

圖6 視覺字典（圖像分解及對應的直方圖）Fig.6 Visual dictionary（image decpmposition and the corresponding histogram）

倒排文件描述了一個詞項集合元素和一個文檔集合元素對應關系的數據結構。在倒排文件中，可以直接給出一個集合出現在哪些文檔中，和在某個文檔中出現的位置和頻率。倒排文件分為兩部分：第一部分是由不同詞項組成的索引，稱為詞表，第二部分由每個詞項出現過的文檔集合構成，稱為記錄文件，每個詞項的對應部分稱為倒排表，可以通過詞表訪問[6]。

4 相似性匹配

這個環節，需要對用戶輸入的圖像和圖像庫中的圖像進行一一比較。判斷兩幅圖是否相似意味著兩幅圖的特征向量之間的距離很小。一般的相似性匹配有Minkowsky距離、直方圖相交法和二次式距離。這里選用歐式距離法。

5 實驗結果分析

圖7 實驗流程圖Fig.7 Flow diagram of experiment

在實驗中，選用的測試環境是VS2010下的VC++。主要是將基于SIFT的檢索應用于2種類型的圖片集，主要是通過對不同類型的圖片比較SIFT以及ROOTSift特征進行匹配的效果。圖片集包含9 000幅圖片，其中包含有商標圖和風景圖。這些圖片中選取的圖像從背景明亮度以及黑白對比度都進行了大量的取樣，盡可能的覆蓋各種可能。同時，為每一幅圖片都設置了與之接近的尺度不同的圖像。而商標圖是為了討論ROOTSift對于相似的抽象圖案的匹配度，風景圖則是為了檢驗當圖像背景不同且雜亂時對于主要關鍵物體的匹配效果。而之所以為了對每幅圖像設計與之相似的尺度不同的圖像，是為了檢驗ROOTSift算法對圖像特征點的尺度不變性。實驗具體流程圖如圖7所示及實驗結果如圖8、9所示。

圖8 圖像庫中文件Fig.8 The file of image library

圖9 對圖像進行的匹配結果Fig.9 The searching result of the image

表2 在商標類圖中兩種方法的比較Tab.2 Comparison of the two methods in trademark class diagram

表3 在風景類圖中兩種方法的比較Tab.3 Comparison of the two methods in sight class diagram

本文基于ROOTSift特征的視覺字典算法具有以下特點：首先，ROOTSift是一種具有尺度、旋轉不變性的局部特征，它對于視覺變化的圖片也能較好的匹配；其次，ROOTSift特征提取的特征數目與圖片的具體內容以及圖片的分辨率成正比；最后ROOTSift特征很適合用于相似圖像的檢索和圖像拼接，它對于同一場景或同一物體不同大小或者小視角變化的檢索結果也較好。從上述實驗結果圖以及實驗結果中可以看出，ROOTSift算法相對于SIFT算法來講，在查全率和查準率等方面均有了顯著的提高，切實的提高了圖像匹配的成功率。

6 結束語

為了提高檢索的準確率，提出了基于ROOTSift的改進視覺字典模型的圖像檢索算法。本算法采用ROOTSift算法高效的提取圖像的特征點，然后利用高效的K-means聚類算法[7]建立支持動態擴充的隨機視覺字典，并且利用倒排排序建立索引，最后利用歐式距離來匹配相似度來達到匹配圖像的目的。實驗結果證明，文中算法具有高度的匹配成功率以及擁有良好的匹配速度，較前人的檢索算法有了較大的提高。

[1]Lowe D G.Object recognition from local scale-invariant features，international conference on computer vision[J].Corfu，Greece，1999：1150-1157.

[2]David G.Lowe，Distinctive Image Features from Scaleinvariant Keypoints[J].International Journal of Computer Vision，2004，60（2）:91-110.

[3]邊肇棋，張學工.模式識別 [M].北京:清華大學出版社，2000.

[4]刁蒙蒙，張菁，卓力，等.一種基于視覺單詞的圖像檢索方法[D].北京：北京工業大學，2011.

[5]AHMET CAGRI SIMSEK Content-Based Image Retrieval using the Bag-of-Words Concept[J].IEEE.2010：3-4.

[6]Terry Liang.Lucene 2.1研究：倒排序基本常識[EB/OL].（2007）.http://www.blogjava.net/Liangtianyu/archive/2007/06/11/123281.htmls.

[7]聶曉偉.基于K-Means算法的雷達信號預分選方法 [J].電子科技，2013（11）:55-58.

NIE Xiao-wei.Method of radar signal pre-sorting based on K-Means algorithm[J].Electronic Science and Technology，2013（11）:55-58.

Image retrieval algorithm based on improved visual dictionary model

LI Qiang1， ZUO Xin1， SHEN Ji-feng2， XU Yun-kai1， SONG Ying1

（1.School of Computer Science and Engineering，Jiangsu University of Science and Technology，Zhenjiang212000，China；2.School of Electrical and Information Engineering，Jiangsu University，Zhenjiang212003，China）

In the current research field of image searching， due to the good performance， visual vocabulary has currently become the mainstream method for creating visual dictionaries.The traditional method based on visual vocabulary has the disadvantages of low efficiency， high memory consumption and so on.Thus， the system in this paper utilizes the ROOTSift algorithm to extract feature points in images and adopts the efficient k-means cluster algorithm to create random visual vocabulary which can be expanded dynamically.While there are some open problems in current image searching system，such as the problems of ambiguity and synonymity in visual vocabulary， object positioning and detection performance with big data，this system creates the visual vocabulary histogram and index files with reverse order based on visual vocabulary and reallocates the weights to visual vocabulary to improve the hit ratio of detection.Finally，the similarity matching is achieved through Euclidean distance searching.The experiments show that this method can increase the success rate of image searching and improve the efficiency of the searching，and it can achieve a nice retrieval quality of the image searching.

image searching；ROOTSift algorithm；K-means clustering；visual dictionary

TN391.3

A

1674-6236（2014）15-0082-04

2013-10-12 稿件編號：201310064

江蘇大學高級人才科研啟動基金（No.13JDG093）

李 強（1995—），男，山西靜樂人。研究方向：圖像處理和檢索。