李 強(qiáng)， 左 欣， 沈繼鋒， 徐云凱， 宋 穎

（1.江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)，江蘇 鎮(zhèn)江 212000；2.江蘇大學(xué) 電氣信息工程學(xué)院，江蘇 鎮(zhèn)江 212003）

基于改進(jìn)視覺字典模型的圖像檢索算法

李 強(qiáng)1， 左 欣1， 沈繼鋒2， 徐云凱1， 宋 穎1

（1.江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)，江蘇 鎮(zhèn)江 212000；2.江蘇大學(xué) 電氣信息工程學(xué)院，江蘇 鎮(zhèn)江 212003）

目前在圖像檢索領(lǐng)域，由于視覺字典其性能突出，已成為圖像檢索領(lǐng)域構(gòu)建視覺詞典的主流方法。但傳統(tǒng)的視覺字典方法存在運(yùn)行時(shí)間效率低、內(nèi)存消耗大等缺點(diǎn)。因此本文采用ROOTSift算法提取圖像的特征點(diǎn)并利用高效的K-means聚類算法建立支持動(dòng)態(tài)擴(kuò)充的隨機(jī)視覺字典。該方法基于視覺字典構(gòu)建視覺詞匯直方圖和倒排序索引文件，并對(duì)視覺詞重新分配權(quán)重以提高檢索命中率。最后利用歐氏距離法查詢完成相似性匹配。試驗(yàn)結(jié)果表明該方法能提高圖像檢索的準(zhǔn)確率，對(duì)大規(guī)模的圖像檢索能夠達(dá)到很好的檢索質(zhì)量。

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

隨著多媒體技術(shù)和Internet的飛速發(fā)展，網(wǎng)上的數(shù)字圖片急劇增長(zhǎng)。面對(duì)這些海量的圖像數(shù)據(jù)，如何快速有效的檢索到用戶所需要的圖片信息成為圖像處理領(lǐng)域的研究熱點(diǎn)。傳統(tǒng)的圖像檢索一般都是基于關(guān)鍵字的檢索方法，但是有時(shí)候人們想要通過圖片內(nèi)容來(lái)檢索出類似的相關(guān)圖片。基于這種需要，基于圖像的圖像檢索研究成了近年來(lái)的研究熱點(diǎn)。

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

針對(duì)上述問題，我們采用視覺字典的方法進(jìn)行圖像檢索。視覺字典通過統(tǒng)計(jì)局部不變特征的全局出現(xiàn)情況來(lái)實(shí)現(xiàn)的，其特征既保留了局部特征的不變性又增加了全局特征的魯棒性，同時(shí)與數(shù)量龐大的局部不變特征相比還能起到簡(jiǎn)化特征的作用。

為了提高檢索的準(zhǔn)確率，提出了基于ROOTSift的改進(jìn)視覺字典模型的圖像檢索算法。本算法采用ROOTSift算法高效的提取圖像的特征點(diǎn)，然后利用高效的K-means聚類算法建立支持動(dòng)態(tài)擴(kuò)充的隨機(jī)視覺字典，并且利用倒排排序建立索引，最后利用歐式距離來(lái)匹配相似度來(lái)達(dá)到匹配圖像的目的。

1 特征提取

1.1 SIFT

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

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

從圖1可以看出，SIFT算法包含4個(gè)主要步驟，其中使用高斯公式來(lái)檢測(cè)出現(xiàn)在任何一個(gè)尺度空間中的極值點(diǎn)，然后把這些極值點(diǎn)用相應(yīng)的方法進(jìn)行篩選，去除對(duì)比度低和邊緣點(diǎn)的極值點(diǎn)，進(jìn)一步用特殊的公式來(lái)去除不穩(wěn)定點(diǎn)最后得到了穩(wěn)定的特征點(diǎn)，為每一個(gè)穩(wěn)定的關(guān)鍵點(diǎn)統(tǒng)計(jì)它們的梯度和方向作為它們的方向參數(shù)。

SIFT算法最后生成關(guān)鍵點(diǎn)描述子如圖2所示。在每4×4的小塊上計(jì)算8個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的累加值，即可形成一個(gè)種子點(diǎn)，如上圖右部分所示。此圖中一個(gè)關(guān)鍵點(diǎn)由2×2共4個(gè)種子點(diǎn)組成，每個(gè)種子點(diǎn)有8個(gè)方向向量信息。為了增強(qiáng)匹配的穩(wěn)健性，對(duì)每個(gè)關(guān)鍵點(diǎn)使用4×4共16個(gè)種子點(diǎn)來(lái)描述，這樣對(duì)于一個(gè)關(guān)鍵點(diǎn)就可以產(chǎn)生128個(gè)數(shù)據(jù)，即最終形成128維的SIFT特征向量。

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

以上是SIFT算法的詳細(xì)原理和步驟。但是經(jīng)過大量的實(shí)驗(yàn)，我們發(fā)現(xiàn)，采集出的特征點(diǎn)有很大的幾率受噪音等的影響。因此，選用了一種基于SIFT算法的改進(jìn)版ROOTSift。

1.2 ROOTSift

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

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

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

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

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

2 K-means均值聚類

聚類是一種無(wú)監(jiān)督的學(xué)習(xí)方法，按照物以類聚的思想，將數(shù)據(jù)集中按數(shù)據(jù)之間的相似程度劃分為幾類，并且使得同一類或者簇中的樣本相似度盡可能大，反之則數(shù)據(jù)樣本的相似度盡可能小[3]。它的優(yōu)點(diǎn)是算法復(fù)雜度低，簡(jiǎn)單快捷。具體算法流程圖描述如圖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 視覺字典的形成

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

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

第1步 將用SIFT提取出的大量的關(guān)鍵點(diǎn)運(yùn)用K-means聚類算法得出K個(gè)聚類中心。

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

第3步 提取圖像庫(kù)中的一幅圖像，對(duì)這幅圖像的每個(gè)關(guān)鍵點(diǎn)進(jìn)行分析，判斷這個(gè)關(guān)鍵點(diǎn)是屬于i號(hào)聚類，則把vi加一。最后形成了這幅圖像的一個(gè)視覺直方圖，每幅直方圖又可稱之為視覺單詞。

第4步 重復(fù)第3步，直到將圖像庫(kù)中的圖像遍歷一遍。

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

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

圖6 視覺字典（圖像分解及對(duì)應(yīng)的直方圖）Fig.6 Visual dictionary（image decpmposition and the corresponding histogram）

倒排文件描述了一個(gè)詞項(xiàng)集合元素和一個(gè)文檔集合元素對(duì)應(yīng)關(guān)系的數(shù)據(jù)結(jié)構(gòu)。在倒排文件中，可以直接給出一個(gè)集合出現(xiàn)在哪些文檔中，和在某個(gè)文檔中出現(xiàn)的位置和頻率。倒排文件分為兩部分：第一部分是由不同詞項(xiàng)組成的索引，稱為詞表，第二部分由每個(gè)詞項(xiàng)出現(xiàn)過的文檔集合構(gòu)成，稱為記錄文件，每個(gè)詞項(xiàng)的對(duì)應(yīng)部分稱為倒排表，可以通過詞表訪問[6]。

4 相似性匹配

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

5 實(shí)驗(yàn)結(jié)果分析

圖7 實(shí)驗(yàn)流程圖Fig.7 Flow diagram of experiment

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

圖8 圖像庫(kù)中文件Fig.8 The file of image library

圖9 對(duì)圖像進(jìn)行的匹配結(jié)果Fig.9 The searching result of the image

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

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

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

6 結(jié)束語(yǔ)

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

[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]邊肇棋，張學(xué)工.模式識(shí)別 [M].北京:清華大學(xué)出版社，2000.

[4]刁蒙蒙，張菁，卓力，等.一種基于視覺單詞的圖像檢索方法[D].北京：北京工業(yè)大學(xué)，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研究：倒排序基本常識(shí)[EB/OL].（2007）.http://www.blogjava.net/Liangtianyu/archive/2007/06/11/123281.htmls.

[7]聶曉偉.基于K-Means算法的雷達(dá)信號(hào)預(yù)分選方法 [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 稿件編號(hào)：201310064

江蘇大學(xué)高級(jí)人才科研啟動(dòng)基金（No.13JDG093）

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