基于SIFT特征圖像檢索的分布式應用

徐文博，吳 戀，于國龍

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

基于SIFT特征圖像檢索的分布式應用

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

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

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

SIFT;圖像檢索;分布式

引言

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

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

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

1 相關工作

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

圖1 Bag-Of-Visual-Words模型應用于圖像表示

雖然SIFT算子提取出的圖像特征有著很好的識別度，但是只是建立在了一個高達128維的矢量上，這對于有一定規(guī)模的目標數(shù)據(jù)庫來說，在不經任何處理的情況下運用SIFT特征是不明智的。在信息檢索領域，有一個Bag-Of-Words (BOW)模型，這個模型它忽略掉文本的語法和語序，將無序的單詞作為基本元素來表示一段文字或者一篇文章。在計算機視覺領域，我們通過將圖像信息與文本信息類比，將圖像的特征作為基本元素來表示或者描述某一張圖像，將圖像進行“文字化”以后會更加便于規(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ù))，每個類就代表一個視覺單詞，最后得出詞典。(3)詞袋表示圖像特征:類比文章的書寫，將圖像特征視為文章中的詞語，把圖像整體用若干視覺詞袋中的視覺單詞表示出來以判斷圖像所屬的類別。這樣一來再去計算圖像之間的相似度就能很大程度的提高效率了。

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

圖2 HIPI Image Bundle存儲結構

2 分布式SIFT特征檢索方案設計

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

圖3 整體設計方案

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

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

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

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

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

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

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

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

2．2 SIFT特征提取

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

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

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

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

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

2．3 K-Means特征聚類

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

步驟為:

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

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

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

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

2．4 BOVW圖像向量表示

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

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

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

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

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

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

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內存，操作系統(tǒng)Ubuntu14．04。

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

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

圖4 節(jié)點加速比

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

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

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

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

結語

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

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

［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］．計算機應用，2014．

［8］田進華，張韌志．基于MapReduce數(shù)字圖像處理研究［J］．電子設計工程，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．

［責任編輯:莊 鵬］

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

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