孫孟柯 張紅梅

摘要：該系統(tǒng)將Bag of words模型用于大批量圖像檢索，基于OpenCV C語言庫提取圖像的SIFT特征，然后使用Kmeans算法進(jìn)行聚類，再將其表示成Bag of words矢量并進(jìn)行歸一化，實現(xiàn)大批量圖像檢索，并用caltech256數(shù)據(jù)集進(jìn)行實驗。實驗表明，該系統(tǒng)該系統(tǒng)采用的方法是有效的。

關(guān)鍵詞：SIFT; Kmeans; Bag of words;大批量;圖像檢索

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)05-1139-03

Based on the Bag of Words of the Model of Image Retrieval System Design and Implementation

SUN Meng-ke, ZHANG Hong-mei

(Henan University of Technology College of Information Science and Engineering, Zhengzhou 450000, China)

Abstract: The system will be Bag of words model used in large quantities of image retrieval, based on OpenCV C library image SIFT fea? ture extraction, and then use Kmeans clustering algorithm, and then it says a Bag of words and vector normalization, realizing mass image retrieval, and caltech256 data set for experiments. Experiments show that the system adopts the method is effective.

Key words: SIFT; kmeans; bag of words; mass data; image retrieval

近年來，隨著計算機科學(xué)的飛速發(fā)展，模式識別技術(shù)在社會生活中的應(yīng)用已經(jīng)非常普遍，特別是計算機圖像識別技術(shù)，因為其直觀，方便，快速，準(zhǔn)確的特點，更是受到了人們的青睞。

目前常用的利用計算機自動檢索圖像的方法是使用顏色、紋理、形狀等全局視覺特征來獲得圖像內(nèi)容信息，衡量圖像之間的相似程度以實現(xiàn)圖像檢索。然而，這種方法反映的只是圖像的客觀統(tǒng)計特性，不能被人的視覺所理解。

本文考慮到圖像檢索系統(tǒng)的用戶是根據(jù)圖像中的目標(biāo)來判別圖像之間的相似性，因而將目標(biāo)識別中的典型模型-Bag of words模型引入圖像的檢索識別領(lǐng)域，提取圖像的局部特征來實現(xiàn)圖像的匹配檢索，一定程度上對圖像有了語義方面的理解，也屏蔽了復(fù)雜背景對檢索結(jié)果的影響。

Gabriella Csurka等人[1]首先于2004年在圖像處理領(lǐng)域引入了Bag of words模型，提取圖像的SIFT特征并用支持向量機對5類圖像進(jìn)行分類，結(jié)果表明該模型對復(fù)雜背景具有一定的健壯性，并且在不利用幾何信息的情況下，也能得到很好的分類效果。

Herbert Bay等人[2]在2006年提出了一種特征提取的快速算法SURF(Speeded Up Robust Features)，通過簡化主流的興趣點檢測算子（a Hessian matrix-based measure）和描述算子（a distribution-based descriptor）來實現(xiàn)，并以recall、1-precision為標(biāo)準(zhǔn)同SIFT做了比較，結(jié)果顯示，SURF在各個方面的性能均接近或超越了SIFT，但是計算速度卻是SIFT的3倍左右。

何友松等人[3]在2009年將Bag of Words模型引入汽車圖像識別領(lǐng)域，并提出將SIFT特征提取算法和PLSA分類算法結(jié)合在一起實現(xiàn)車輛和背景圖像分類的思想，實驗對比了該算法與Tamura紋理特征算法和Gabor紋理特征算法在車輛圖像識別中的效果，結(jié)果表明該算法分類正確率優(yōu)于另外兩種方法。

綜上所述，目下對于Bag of words模型在圖像處理領(lǐng)域中的應(yīng)用，大都集中在對小批量圖像的處理，相應(yīng)的對于在大批量圖像處理中的應(yīng)用卻鮮見于報端。本文將Bag of words模型中的聚類算法改進(jìn)之后，用于對大批量數(shù)據(jù)進(jìn)行聚類，取得了非常好的效果。

1 Bag of words模型概述

Bag of words模型最初被用在文本分類中將文檔表示成特征矢量。它的基本思想是假定對于一個文本，忽略其詞序和語法、句法，僅僅將其看做是一些詞匯的集合，而文本中的每個詞匯都是獨立的。

簡單說就是將每篇文檔都看成一個袋子（因為里邊裝的都是詞匯，所以稱為詞袋，Bag of words即由此來)，然后看這個袋子里裝的都是些什么詞匯，將其分類。如果文檔中豬、馬、牛、羊、山谷、土地、拖拉機這樣的詞匯多些，而銀行、大廈、汽車、公園這樣的詞匯少些，我們就傾向于判斷它是一篇描述鄉(xiāng)村的文檔，而不是描述城鎮(zhèn)的。

與之類似，我們也可以將圖像當(dāng)成一些圖像片段（image patch—本文中用SIFT特征來描述）的集合。譬如構(gòu)成一幅人臉圖像的圖像片段必定傾向于描述人的眼睛、鼻子、耳朵、嘴巴這些事物（我們稱這些事物為視覺詞匯）。

現(xiàn)在假設(shè)要使用Bag of words模型從一批訓(xùn)練圖像中檢索出與測試圖像最相似的圖像，我們要做的工作主要都有哪些呢？

首先要對訓(xùn)練圖像集進(jìn)行預(yù)處理。包括圖像增強、分割、圖像同一格式、同一規(guī)格的處理等等。

其次提取圖像的SIFT特征。即將每一幅圖像劃分成很多個圖像片段，每一個圖像片段都用一個128維的SIFT描述子矢量來表示。

再次聚類生成視覺詞，構(gòu)建碼本。一幅圖像的碼本是由兩部分組成的，視覺詞以及與其對應(yīng)的SIFT描述子矢量的數(shù)目，即詞頻。假設(shè)碼本包含k個視覺詞序列，將上步中所有的SIFT描述子矢量用Kmeans聚類生成k個簇，最終這k個簇中心即為碼本的k個視覺詞。然后計算每幅圖像中每個SIFT描述子到這些視覺詞的距離，若其距離某個視覺詞最近，就將其映射到該視覺詞，并將該視覺詞對應(yīng)的詞頻數(shù)增1。直至將所有的SIFT描述子都映射到碼本中，將每幅圖像都用一個與視覺詞序列相對應(yīng)的詞頻矢量來描述，這個詞頻矢量即為相似度檢索時所要使用的圖像的Bag of words特征矢量,另外，由于每幅圖像所包含的SIFT矢量的數(shù)目是不確定的，還需要對Bag of words特征矢量進(jìn)行歸一化。

最后計算圖像距離相似度進(jìn)行檢索。測試圖像也要經(jīng)過預(yù)處理，提取SIFT特征，生成碼本矢量并進(jìn)行歸一化的過程，然后計算其與訓(xùn)練碼本的距離，并將此距離相似度按升序排列。

2圖像特征提取

2.1 SIFT特征提取

SIFT算法由D.G.Lowe在1999年[4]提出，并于2004年[5]完善總結(jié)。SIFT算法是一種提取局部特征的算法，在尺度空間尋找極值點，提取位置，尺度，旋轉(zhuǎn)不變量,從而使其對旋轉(zhuǎn)、尺度縮放保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。

高斯卷積核是實現(xiàn)尺度變換的唯一線性核，于是一副二維圖像I()

x,y的尺度空間定義：L(x,y,σ)=G(x,y,σ)?I(x,y),其中G(x,y,σ)=

x,y是空間坐標(biāo)，反映像素的位置；σ是尺度坐標(biāo)，決定圖像的平滑程度。

為了在尺度空間檢測到穩(wěn)定的關(guān)鍵點，需要計算高斯差分尺度空間（DOG scale-space）：

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))?I(x,y)=L(x,y,kσ)-L(x,y,σ)

DOG算子計算簡單，是尺度歸一化的LOG算子的近似。

在檢測極值時，需要跟其周圍鄰域同一尺度的8個像素和相鄰尺度對應(yīng)位置的9×2個像素進(jìn)行比較，以確保在尺度空間和二維圖像空間都檢測到局部極值。

關(guān)鍵點的方向參數(shù)是利用關(guān)鍵點鄰域像素的梯度方向分布特性為其指定的。以關(guān)鍵點為中心在其鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計鄰域像素的梯度方向，直方圖的峰值就作為該關(guān)鍵點的主方向。如圖1，圖2所示。

圖1關(guān)鍵點主方向示意圖

圖2一幅測試圖像

特征描述子生成時，選取以特征點為中心的16*16鄰域作為采樣窗口，將采樣點與特征點的相對方向通過高斯加權(quán)后歸入包含8個bin的方向直方圖，最后獲得4*4*8（128維）的特征描述子。

2.2 Bag of words特征表示

SIFT特征雖然也能描述一幅圖像，但是每個SIFT矢量都是128維的，而且一幅圖像通常都包含成百上千個SIFT矢量，在進(jìn)行相似度計算時，這個計算量是非常大的，通行的做法是用聚類算法對這些矢量數(shù)據(jù)進(jìn)行聚類，然后用聚類中的一個簇代表Bag of words中的一個視覺詞，將同一幅圖像的SIFT矢量映射到視覺詞序列生成碼本，這樣每一幅圖像就只用一個碼本矢量來描述，這樣計算相似度時效率就大大提高了。

Kmeans算法是數(shù)據(jù)挖掘技術(shù)中基于分裂法的一個經(jīng)典的聚類算法，因其理論可靠、算法簡單、收斂速度快而被廣泛應(yīng)用[6]。

該算法采用迭代更新的思想，常規(guī)的思路是先將要參與聚類的特征數(shù)據(jù)載入內(nèi)存，然后隨機選擇K個對象對聚類中心初始化

123, , ,...,K c c cc --初始化過程，再對剩下的每個對象ix（i =1，2，3，…，n)根據(jù)其與各個簇中心的距離（本文取歐氏距離）將它賦給最近的簇（m是特征數(shù)據(jù)的維數(shù)）--映射過程：

然后重新計算每個簇的均值作為下一次迭代的聚類中心—更新類中心：

cj=

xi∈sjxi，其中Nj為第j個簇sj中的對象數(shù)目即Kmeans算法需要進(jìn)行初始化，映射和更新類中心3個過程，其中后兩個過程要不斷重復(fù)，直到所有類中心都不再變化為止，最后得到的類中心就是Bag of words模型所需要的視覺詞（visual words）。然后將每幅圖像中的每個SIFT描述子都映射到某個視覺詞，得到的詞頻序列就是該幅圖像的碼本矢量。

但是當(dāng)數(shù)據(jù)量比較大時，該思路實現(xiàn)的聚類算法在運行過程中很可能會因內(nèi)存分配不足而崩潰。為了保證程序平穩(wěn)運行，筆者采用分批載入，整體聚類的思想實現(xiàn)該算法。每次載入SIFT特征數(shù)據(jù)時限定數(shù)量，將所有SIFT特征數(shù)據(jù)分成有數(shù)的幾批分別載入內(nèi)存，然后處理一批，釋放一批。

即在映射過程中，計算每個批次中每一個SIFT矢量到各個簇中心的距離，記錄下與其距離最近的那個簇的標(biāo)號，就將那一批SIFT數(shù)據(jù)從內(nèi)存中釋放掉。在更新類中心的過程中同樣如此，載入一個批次的SIFT后，讀取該批次對應(yīng)的SIFT類標(biāo)號，將相同類標(biāo)號的SIFT相加求和，然后釋放，求和完畢之后，再求平均，得到新的類中心，這樣分批載入的思想就解決了程序運行過程中可能出現(xiàn)的內(nèi)存分配不足的問題。

3系統(tǒng)實現(xiàn)

本軟件主要采用C++語言在vc++6.0平臺下開發(fā)，基于OpenCV C語言庫提取圖像的SIFT特征，使用Bag of words模型將它表示成特征矢量，最后計算測試圖像的碼本矢量與訓(xùn)練圖像的碼本矢量之間的距離實現(xiàn)圖像檢索。

SIFT特征提取模塊主要基于OpenCV開源庫提供的API，使用C語言編寫。涉及到的主要數(shù)據(jù)結(jié)構(gòu)為feature，其屬性主要包括：位置（x,y）、方向（orientation）、尺度（scale）、描述子矢量（double數(shù)組），所在文件為：sift.c和sift.h。

Bag of words表示模塊主要利用Kmeans聚類算法生成視覺詞，然后統(tǒng)計每幅圖像上某個視覺詞匯出現(xiàn)次數(shù)，最后通過歸一化將它們轉(zhuǎn)換為特征矢量；該模塊對應(yīng)的類文件為：BagWords.h和BagWords.cpp。

Kmeans算法實現(xiàn)的功能主要是：

數(shù)據(jù)存儲模塊在本軟件的設(shè)計中占有重要地位，它直接為特征提取模塊和Bag of words表示模塊提供支持，下面將要介紹它的主要成員變量：

1）特征矢量Mat類_X：它是stl的vector容器，裝有double型的指針，因此它的特征是：支持動態(tài)地增加double型的數(shù)組。由于每幅圖像產(chǎn)生的SITF特征的數(shù)目不固定，因此我們在處理每幅圖像時，需要逐步地將每個SIFT特征加入vector。

2）標(biāo)號矢量Mat類_y：同上，每副圖像關(guān)聯(lián)到一個double數(shù)組而不是一個標(biāo)量，可以存儲多個標(biāo)號，如對于每個SIFT特征而言，我們需要同時存儲它所在的圖像索引號和類別索引號。

3）圖像路徑映射表map類_image_map：string到string的映射表，主要將圖像索引號與其路徑建立一一對應(yīng)關(guān)系，便于程序進(jìn)行處理。

4）其他：mat文件數(shù)據(jù)是模塊自定義的一種簡單的數(shù)據(jù)格式，第一行為數(shù)據(jù)矩陣的行數(shù)和列數(shù)，其他行為數(shù)據(jù)，每一行為一個樣本，數(shù)據(jù)均以float型數(shù)據(jù)讀入；程序通過map來存儲命令行的參數(shù)和參數(shù)值，并且作為全局變量供所有的程序訪問，因此，我們可以在所有的類中使用我們所需的任意參數(shù)值（對于整數(shù)和浮點數(shù)需要通過系統(tǒng)函數(shù)進(jìn)行轉(zhuǎn)換_atoi等）。

4實驗及分析

目前常用的的圖像數(shù)據(jù)集主要有：Caltech-101，加州理工學(xué)院101類圖像數(shù)據(jù)庫，每類有40-800幅圖像，每幅圖像大小約為300*200像素；Caltech-256，加州理工學(xué)院256類圖像數(shù)據(jù)庫,包含256類共30607幅圖像；Pascal數(shù)據(jù)集是為每年一次的voc競賽精心準(zhǔn)備的數(shù)據(jù)集，voc2011數(shù)據(jù)集，包含20類共1萬多幅圖像；此外還有TU Darmstadt數(shù)據(jù)集，MIT-CSAIL數(shù)據(jù)集等。

本文使用caltech-256數(shù)據(jù)集，在CPU型號為酷睿i5 750，內(nèi)存容量為2G，操作系統(tǒng)為windows XP的機器上進(jìn)行訓(xùn)練。將30607幅圖像分批載入內(nèi)存，提取超過1680萬個SIFT特征，記錄下每幅圖像的索引序號和索引路徑以及每個特征矢量對應(yīng)的圖像標(biāo)號，并按批分文件保存到硬盤中，共用時13982.74秒。

然后分別讀取每一批的數(shù)據(jù)進(jìn)行kmeans聚類。測試時隨機選取5幅圖像做實驗，提取SIFT,并映射到視覺詞序列生成碼本，分別計算這些碼本到訓(xùn)練圖像碼本的距離，按升序進(jìn)行排列，并查詢圖像標(biāo)號與路徑索引表，最終得到5幅圖像的查全率與查準(zhǔn)率如表1所示。

表1實驗結(jié)果

該實驗結(jié)果表明：

1)特征提取速度和檢索速度非?？欤桓眻D片的檢索的總時間大概為1秒，調(diào)整系統(tǒng)的參數(shù)和采用其他聚類及檢索算法，可以進(jìn)一步改善系統(tǒng)的性能。

2)系統(tǒng)的可靠性較好，可以處理caltech256數(shù)據(jù)集的3萬多幅圖像文件，得到1600多萬的特征，但是仍然不會出錯。

3)圖像旋轉(zhuǎn)、尺度縮放、亮度變化、視角變化、仿射變換和噪聲等可變因素影響下，系統(tǒng)的檢索性能并沒有太大的化。

5結(jié)論

經(jīng)過以上分析，我們可以看到，將Bag of words模型應(yīng)用于大批量圖像檢索的思路是正確的，不僅計算量大大減小，而且得到了比較滿意的檢索效果。但是如果要進(jìn)一步優(yōu)化系統(tǒng)性能，還需要做更深入的研究，比如聚類要聚成幾類才是最合適的，這個決定最終碼本矢量維數(shù)的數(shù)據(jù)對系統(tǒng)性能的影響是可以想見的；另外聚類過程中的時間開銷非常大，雖然是在線下運行的，但是有沒有可能讓時間花費更少一點，讓其聚類效果更精確一點呢。

參考文獻(xiàn)：

[1] Csurka G,Dance C,Fan L,et al.Visual categorization with bags of keypoints[C].ECCV04 workshop on Statistical Learning in Computer Vi? sion,2004:59-74.

[2] Bay H,Ess A,Tuytelaars T,et al.SURF: Speeded Up Robust Features[J].Computer Vision and Image Understanding(CVIU),2008,110(3): 346-359.

[3]何友松,吳煒,陳默,等.基于Bag of Features算法的車輛圖像識別研究[J].電視技術(shù),2009,33(12):104-107.

[4] Lowe D G.Object recognition from local scale invariant features[C].Corfu,Greece:International Conference on Computer Vision,1999: 1150-1157.

[5] Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Conference on Computer Vision,2004,60(2):99-110.

[6]邊肇祺,張學(xué)工.模式識別[M].北京:清華大學(xué)出版社,2000.