基于SIFT特征圖像檢索的分布式應(yīng)用

徐文博，吳 戀，于國龍

(1．貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院，貴州貴陽 550025; 2．貴州師范學(xué)院貴州省高校工業(yè)物聯(lián)網(wǎng)工程技術(shù)研究中心，貴州貴陽 550018)

基于SIFT特征圖像檢索的分布式應(yīng)用

徐文博1，2，吳 戀2，于國龍2

(1．貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院，貴州貴陽 550025; 2．貴州師范學(xué)院貴州省高校工業(yè)物聯(lián)網(wǎng)工程技術(shù)研究中心，貴州貴陽 550018)

SIFT特征被廣泛運用于圖像檢索，由于其高維度的特性，對于大量圖像檢索而言，很難在保證準確度的前提下達到理想的速度。本文提出一種基于分布式并行計算的SIFT算法，在hadoop集群下利用K -Means將特征聚類，將聚類中心作為Bag-of-Words模型的視覺詞袋，得到所有圖像直方圖，最終計算這些圖像與檢索圖像特征向量之間的相似度，返回相似度最大的一些圖像。

SIFT;圖像檢索;分布式

引言

圖像檢索是希望利用計算機視覺領(lǐng)域的相關(guān)技術(shù)解析理解一張圖像，通過解析圖像達到直接利用圖片作為介質(zhì)去檢索與之相關(guān)的內(nèi)容即實現(xiàn)“以圖搜圖”的目的。近年來，基于圖像內(nèi)容的圖像檢索技術(shù)在計算機視覺領(lǐng)域炙手可熱，涌現(xiàn)出許多描述圖像內(nèi)容的優(yōu)秀算法，其中，SIFT(Scale-Invariant Feature Transform)［1］算法是一種經(jīng)典的基于內(nèi)容的圖像特征提取算法，它利用高斯模糊獲得空間尺度并從中檢測極值點，提取出在位置發(fā)生變化、大小改變、圖像發(fā)生旋轉(zhuǎn)的復(fù)雜情況下都能保持不變性的特征。因此，將SIFT特征用于描述一幅圖像并將其用作圖像檢索的依據(jù)是一個實現(xiàn)“以圖搜圖”的解決方法。但是，由于高維度的特征向量，在圖像庫規(guī)模很大的時候，用SIFT算法檢索圖像所花費的時間開銷非常巨大，改進的SIFT算法［2］雖然在速度上有所提升，但是在降維的情況下犧牲了精度。

得益于近年來云計算的飛速發(fā)展，分布式云計算在處理大規(guī)模數(shù)據(jù)的時候能很好地提高處理效率，所以針對提高基于傳統(tǒng)SIFT圖像特征的圖像索引效率，運用云計算下的大數(shù)據(jù)處理平臺是一個簡單直接的手段。大數(shù)據(jù)處理領(lǐng)域的Hadoop［5］平臺是一個開源且比較成熟的產(chǎn)品化技術(shù)平臺，我們可以在不了解如何具體實現(xiàn)分布式數(shù)據(jù)處理的情況下更充分地利用計算資源對需要高計算量的數(shù)據(jù)進行可靠的加速處理，這一點對依賴計算機處理性能的圖像處理具有很大的意義。針對海量圖像庫的檢索效率問題，本文在Hadoop平臺下提出了運用MapReduce［4］［9］實現(xiàn)對圖像特征提取、K-Means［3］聚類進行并行化處理，在匹配圖像階段，運用Bag-Of-Words［6］詞袋模型將圖像特征歸一化表示成向量直方圖，通過計算圖像的向量夾角來得到兩幅圖之間的相似度，按照相似度的大小從大到小輸出檢索結(jié)果。

分布式處理技術(shù)能夠有效解決原來因計算能力而受到限制的優(yōu)秀算法，運用分布式大數(shù)據(jù)處理技術(shù)能改進提升SIFT特征算子在作為匹配依據(jù)時大維度帶來的計算效率低問題，再加上本文提出的一系列優(yōu)化能讓圖像檢索在保證精度的前提下提升速度。

1 相關(guān)工作

在有關(guān)圖像處理的各項研究中，基于內(nèi)容的圖像檢索首先從圖像的語義處理著手，關(guān)注圖像的表示方法，選擇的目標是找到一種合適和穩(wěn)定的方式來描述圖像的內(nèi)容，提取出與圖像中的物體的方向、位置、形變和光線變換等無關(guān)且具有高度辨識度的信息即我們常說的圖像特征。在圖像特征中HOG特征、LBP特征、SURF特征、SIFT特征是幾種典型優(yōu)秀的特征提取算法。其中，HOG (Histogram of Oriented Gradient)方向梯度直方圖，在一幅圖中局部目標的外觀表象(appearance)和形狀(shape)能夠用梯度或者邊緣的方向密度分布很好地描述出來，HOG算法就是統(tǒng)計這些梯度信息去描述一幅圖像，這個特征算法常常和支持向量機(SVM)相結(jié)合在行人檢測和人臉識別有很好的效果。LBP(Local Binary Pattern，局部二值模式)是一種優(yōu)秀的圖像局部紋理描述算子，能夠保持旋轉(zhuǎn)和灰度的不變性，常常用于人臉表情特征識別。針對圖像檢索的實際應(yīng)用情況，研究對比了現(xiàn)有圖像特征提取算子之后發(fā)現(xiàn)，經(jīng)過SIFT圖像特征描述算子表示的特征能夠在大小、方位、角度等特性發(fā)生變化的情況下還能夠保持匹配的正確性，鑒于這樣的一個鮮明特性，將SIFT特征用于在數(shù)據(jù)庫中檢索匹配相似圖像是一個很不錯的選擇。

圖1 Bag-Of-Visual-Words模型應(yīng)用于圖像表示

雖然SIFT算子提取出的圖像特征有著很好的識別度，但是只是建立在了一個高達128維的矢量上，這對于有一定規(guī)模的目標數(shù)據(jù)庫來說，在不經(jīng)任何處理的情況下運用SIFT特征是不明智的。在信息檢索領(lǐng)域，有一個Bag-Of-Words (BOW)模型，這個模型它忽略掉文本的語法和語序，將無序的單詞作為基本元素來表示一段文字或者一篇文章。在計算機視覺領(lǐng)域，我們通過將圖像信息與文本信息類比，將圖像的特征作為基本元素來表示或者描述某一張圖像，將圖像進行“文字化”以后會更加便于規(guī)格較大的圖像處理，有人會把這個稱為視覺詞袋(Bag-Of-Visual-Word，BOVW)。

這里運用BOVW處理圖像數(shù)據(jù)的基本思想是:(1)提取特征:根據(jù)數(shù)據(jù)集選取SIFT特征，然后進行描述，形成特征數(shù)據(jù)，檢測圖像中的 sift keypoints，然后計算 keypoints descriptors，生成128-D的特征向量;(2)生成詞袋:將處理好的特征數(shù)據(jù)全部合并，再用聚類的方法把合并的數(shù)據(jù)聚成設(shè)定的類別數(shù)(這里是具體設(shè)計的視覺詞典的單詞數(shù))，每個類就代表一個視覺單詞，最后得出詞典。(3)詞袋表示圖像特征:類比文章的書寫，將圖像特征視為文章中的詞語，把圖像整體用若干視覺詞袋中的視覺單詞表示出來以判斷圖像所屬的類別。這樣一來再去計算圖像之間的相似度就能很大程度的提高效率了。

Hadoop處理圖像問題:雖然Hadoop能夠方便的存儲和快速的讀寫大數(shù)據(jù)，盡管這里要處理的也是大量的圖片，但是卻不能直接處理這些數(shù)據(jù)，因為通常情況下基于內(nèi)容的圖像處理系統(tǒng)處理的都是些小文件，數(shù)據(jù)量雖然大，但Hadoop計算框架不適合處理大量的小文件，所以本文使用HIPI來將初始大量的小圖片預(yù)處理為一個大文件并作為MapReduce程序的輸入。

圖2 HIPI Image Bundle存儲結(jié)構(gòu)

2 分布式SIFT特征檢索方案設(shè)計

本文將基于內(nèi)容的圖片檢索(CBIR)應(yīng)用到Hadoop分布式大數(shù)據(jù)處理平臺上，使用SIFT特征對圖像進行局部特征描述，采用K-Means聚類算法構(gòu)造Bag-Of-Words的視覺詞匯表，再使用TF-IDF(term frequency-inverse document frequency)詞頻方法來衡量每個特征對于圖像辨識度的貢獻程度，得到優(yōu)化處理后的特征作為相似匹配依據(jù)，計算出每一對匹配向量的余弦夾角，將夾角最小的一批結(jié)果返回作為檢索結(jié)果。

圖3 整體設(shè)計方案

2．1 HIPI圖像數(shù)據(jù)處理

Hadoop能對處理大規(guī)模數(shù)據(jù)文件進行方便的存儲和快速的讀寫處理，但是本文中所處理的數(shù)據(jù)圖像是大批量的小文件，Hadoop并不擅長處理這樣的小文件，所以先要使用HIPI來將大量的圖像預(yù)處理成為一個大文件來作為MapReduce的輸入。做法如下:

輸入:包含分類圖像文件目錄的根目錄

輸出:HIPI Image Bundle(HIB)文件:index文件和dat文件

Map:(Key:子目錄序號;Value:子目錄路徑，即一個類別的圖像集合)，遍歷該子目錄路徑下的所有文件讀取圖像內(nèi)容，存入局部HIB文件中，中間結(jié)果＜Key:布爾值true;Value:局部HIB文件名＞

Reduce:(Key:布爾值true;Value:局部HIB文件名)，將局部HIB文件追加到HDFS中最終的HIB文件

最終結(jié)果〈Key:布爾值true;Value:局部HIB文件名＞

在得到HIB文件后，為了實現(xiàn)對圖片的隨機讀取，要建一個索引文件，里面保存了圖像在文件中的偏移量，通過偏移量能夠找到圖像的位置。

2．2 SIFT特征提取

SIFT特征提取首先尋找極值點，通過(1)式高斯卷積建立尺度空間，(3)式高斯差分尺度空間(DOG scale-space)穩(wěn)定有效檢測出關(guān)鍵點。

(1)式中是尺度可變高斯函數(shù)，

為得到的關(guān)鍵點分配基準方向，并在關(guān)鍵點尺度空間內(nèi)4*4的窗口中計算的8個方向的梯度信息，這樣就可以為每個 feature形成一個4*4*8=128維的描述子，將這個向量歸一化后就能進一步去除光照的影響，最后生成每個keypoint的SIFT特征。

Map:輸入為(Key:圖像 id，value:圖像數(shù)據(jù))，Map函數(shù)的作用是將輸入的待處理圖像提取特征極值點，為每個特征點加上SIFT描述子得到圖像特征，將特征輸出給Reduce函數(shù)。

Reduce:這里的接收Map的結(jié)果不做任何處理，輸出到結(jié)果文件。

2．3 K-Means特征聚類

通過K-Means來聚類圖像特征，得到聚類中心來構(gòu)成圖像BOVW的視覺詞匯表，算法原理為最小化所有向量到其簇中心的距離平方和，即殘差平方和(Residual Sum ofSquares，RSS):

步驟為:

(1)從N個特征中隨機選取K個作為中心。

(2)對于每一個新加入的特征測量它到每個中心的距離，然后把它歸類到距離最小的類。

(3)重新計算已經(jīng)得到的各個特征類的中心。

(4)對每一個圖像的所有keypoint都做(2)、(3)兩步操作直到(3)中得到的中心與原來的中心相等或距離小于某個指定的值。

2．4 BOVW圖像向量表示

得到聚類中心(視覺詞匯表)后每張圖像都能夠表示成一個向量表(2，0，5，1，0，0……)的形式，每個分量數(shù)字表示該圖像所具有的此類特征數(shù)量，0表示不具有這類特征。對于傳統(tǒng)BOVW中每個分量都具有相同的重要性，這里利用TFIDF為分量加上權(quán)值進行改進。

在上述式子中ni，j是該特征在其圖像所有特征中的出現(xiàn)次數(shù)，∑knk，j表示這個圖像總共有多少個特征。|D|是圖像特征庫中的特征總數(shù)，|{j∶ti∈dj}|包含ti這個特征的圖像數(shù)目(即ni，j≠0的圖像數(shù)目)。這個算法在這里用以評估某一特征對于識別一張圖像和這個特征在整個特征庫中的重要程度，如果某個特征比較少見，但是它在這個圖像中多次出現(xiàn)，那么它很可能就反映了這張圖像的特性，正是我們所需要的關(guān)鍵特征。

得到加權(quán)優(yōu)化的圖像高維特征以后，本文采用兩個向量間的余弦夾角來判斷兩張圖像特征點是否是一對相似匹配，并根據(jù)實際場景設(shè)定值N，當(dāng)用于比較的兩幅圖的特征點匹配數(shù)量大于N時，視作找到相似圖返回結(jié)果。相似度S:

Map:(Key:圖像id，Value:圖像特征的詞匯描述)，Map函數(shù)中提取出所屬類(聚類id)、圖像id和特征數(shù)量作為鍵值對輸出。

Reduce:(Key:聚類id，Value:(圖像id，特征數(shù)))，一個Reduce任務(wù)下處理相同聚類id的數(shù)據(jù)，分別對兩個變量tn，dn累加，每出現(xiàn)一個新的圖像id時tn、dn加1，對于每次遇到出現(xiàn)過的圖像id對tn加1，最后用log(N/dn)得到IDF，對于每張圖像用其tn除以特征數(shù)得到TF。

經(jīng)過這個步驟，會得到每一幅圖像的BOVW向量表示，并存儲了這些特征向量，在檢索圖像時，也是通過相同的處理流程對待檢索圖像進行SIFT特征提取得到特征向量，將每個特征分配到與之距離最小的視覺單詞，用得到的TF、IDF值為向量中的每個分量加上權(quán)重后進行匹配計算。

3 實驗與分析

數(shù)據(jù)集:corel10k，我們使用同一數(shù)據(jù)集來對系統(tǒng)在不同節(jié)點數(shù)量上處理所花費的時間對比來評價表現(xiàn)。

實驗環(huán)境:環(huán)境為3個節(jié)點的hadoop集群，hadoop版本2．3．0，jdk1．7，cpu Intel雙核3．3 GHz 4g內(nèi)存，操作系統(tǒng)Ubuntu14．04。

實驗中視覺詞匯K=500，分別在控制圖片數(shù)量、節(jié)點的數(shù)量、單節(jié)點的mapper數(shù)下進行實驗，由于hadoop會受到任務(wù)調(diào)度、網(wǎng)絡(luò)負載均衡的影響，每次實驗的結(jié)果都會出現(xiàn)差別，所以每一組實驗都會重復(fù)5次去平均值作為實驗結(jié)果。

在這次實驗中，筆者將同一個任務(wù)分別在單個節(jié)點和多個節(jié)點上運行所花費的時間作為實驗結(jié)果依據(jù)，規(guī)定單節(jié)點任務(wù)時間/多節(jié)點任務(wù)時間作為加速比，用圖像數(shù)為5000、8000和10000的實驗數(shù)據(jù)繪制了圖4節(jié)點加速比結(jié)果圖。

圖4 節(jié)點加速比

透過實驗結(jié)果我們可以看到:經(jīng)過分布式增加節(jié)點加速的處理方法，用BOVW去表示一張圖像以及關(guān)鍵的搜索匹配上速度相比單節(jié)點都有很明顯地提升，三條分別表示數(shù)據(jù)量為5000、8000、10000的折線也表現(xiàn)出處理的數(shù)據(jù)越多，加速效果越明顯的現(xiàn)象，這個也證明了分布式在處理大數(shù)據(jù)量的優(yōu)勢。當(dāng)然，由于分布式中間調(diào)度過程的開銷和網(wǎng)絡(luò)負載均衡等因素的影響，實際實驗結(jié)果也不可能呈現(xiàn)加速效果和節(jié)點數(shù)成線性增長。

圖5 并行任務(wù)數(shù)對速度影響

另外實驗還通過設(shè)置每個節(jié)點的mapper數(shù)增加并行任務(wù)提取圖像SIFT特征來測試并行任務(wù)數(shù)對時間提升的效果，實驗結(jié)果如圖5。

從實驗結(jié)果能看出，當(dāng)3個節(jié)點的總mapper并行任務(wù)在12個左右時速度的提升達到最優(yōu)，原因很簡單，在并行分布計算中，對于同樣的工作任務(wù)，過多的分片和任務(wù)會在任務(wù)控制等待阻塞上耗費過多的時間，不能充分發(fā)揮集群單個節(jié)點的計算能力。

結(jié)語

本文為優(yōu)化提高基于SITF特征的圖像檢索速度，將檢索算法運用到分布式大數(shù)據(jù)處理平臺hadoop上，把基于SIFT特征的CBIR系統(tǒng)中對特征提取、特征聚類、BOVW模型表示圖像、圖像匹配這些需要消耗大量計算資源的部分用MapReduce進行并行化計算，經(jīng)過多方案實驗表明，該方案能夠有效利用hadoop強大的并行計算能力，提升檢索速度。

隨著云計算和人工智能的飛速發(fā)展，基于深度學(xué)習(xí)人工智能正成為最熱的研究方向之一，基于深度學(xué)習(xí)的卷積神經(jīng)網(wǎng)絡(luò)能夠在圖像識別領(lǐng)域發(fā)揮很大的作用。下一步的研究方向希望引入深度學(xué)習(xí)，在圖像特征中通過學(xué)習(xí)對提取出的特征加上更加有效的權(quán)值，使得識別率更高，識別速度更快。

［1］D．G．Lowe．Distinctive image features from scale-invariant keypoints．International Journal of Computer Vision，60(2):91-110，2004．

［2］Ke Y，Sukthankar R．PCA-SIFT:a more distinctive representation for local image descriptors［J］．2004，2(2): 506-513．

［3］Hartigan J A，Wong M A．A K-means clustering algorithm．［J］．Applied Statistics，2013，28(1):100-108．

［4］Dean J，Ghemawat S．MapReduce:Simplified Data Processing on Large Clusters．［J］．In Proceedings of Operating Systems Design and Implementation(OSDI，2004，51 (1):107-113．

［5］Shvachko K，Kuang H，Radia S，et al．The Hadoop Distributed File System［C］．IEEE，Symposium on MASS Storage Systems and Technologies．IEEE Computer Society，2010:1-10．

［6］Zhang Y，Jin R，Zhou Z H．Understanding bag-ofwords model:A statistical framework［J］．International Journal of Machine Learning＆Cybernetics，2010，1(1): 43-52．

［6］蘇勇剛，高茂庭．基于分布式并行計算的SIFT算法［J］．現(xiàn)代計算機，2016(20)．

［7］朱為盛，王鵬．基于Hadoop云計算平臺的大規(guī)模圖像檢索方案［J］．計算機應(yīng)用，2014．

［8］田進華，張韌志．基于MapReduce數(shù)字圖像處理研究［J］．電子設(shè)計工程，2014．

［9］Dittrich J，Quian＆#，Ruiz J A．Efficient big data processing in Hadoop MapReduce［J］．Proceedings of the Vldb Endowment，2012，5(12):2014-2015．

［10］Chum O，Philbin J，Zisserman A．Near Duplicate Image Detection:min-Hash and tf-idf Weighting［C］．British Machine Vision Conference 2008，Leeds，September，2008．

［責(zé)任編輯:莊 鵬］

Distributed image retrieval application based on SIFT feature

XU Wen-Bo1，2，WU Lian2，YU Guo-Long2

(1．College of Computer Science＆Information，Guizhou University，Guiyang，Guizhou，550025; 2．Industrial Internet of Things Engineering Research Center of the Higher Education Institutions of Guizhou Province，Guizhou Education University，Guiyang，Guizhou，550018)

SIFT feature is widely used in image retrieval to ensure the accuracy of image retrieval in a largescale image dataset，which，however，can hardly achieve a desired speed because of its high dimension．This paper presents a kind of SIFT algorithm based on distributed parallel computation．Cluster centroids acquired by KMeans clustering algorithm are used to generate a visual dictionary of Bag-of-Words model，then we can get the histogram for each image．Finally we calculate the similarity between the images，and return a certain number of images with the largest similarity．

SIFT;Image retrieval;Distributed computation

TP391．41

A< class="emphasis_bold">文章編號:1

1674-7798(2016)09-0013-05

10.13391/j.cnki.issn.1674-7798.2016.09.003

2016-07-09

2016年貴州省省級重點支持學(xué)科“計算機應(yīng)用技術(shù)”(黔學(xué)位合字ZDXK［2016］20號);2016年度貴州省科技平臺及人才團隊專項資金項目(項目編號:黔科合平臺人才［2016］5609);2016年度省教育廳高校自然科學(xué)研究項目(黔教合字［2016］015、黔教合KY字［2016］040);2015年省級高技術(shù)產(chǎn)業(yè)示范工程專項(黔發(fā)改投資［2015］1588號);2014年省級本科教學(xué)工程項目“計算機科學(xué)與技術(shù)”專業(yè)綜合改革(黔教高發(fā)［2014］378號);2015年省級本科教學(xué)工程建設(shè)項目“貴州師范學(xué)院大學(xué)生互聯(lián)網(wǎng)+創(chuàng)新創(chuàng)業(yè)訓(xùn)練中心”(黔教高發(fā)［2015］337號)。

徐文博(1992-)，男，貴州畢節(jié)人，貴州大學(xué)在讀碩士研究生，研究方向:計算機數(shù)字圖像處理、深度學(xué)習(xí)。