基于分布式并行計算的SIFT算法

蘇勇剛，高茂庭（上海海事大學信息工程學院，上?！?01306）

基于分布式并行計算的SIFT算法

蘇勇剛，高茂庭
（上海海事大學信息工程學院，上海201306）

針對SIFT算法處理較大圖像庫的效率低和檢索結果中圖像排序不合理的問題，提出一種基于分布式并行計算的SIFT算法，在Spark平臺下利用K-means算法對圖像特征庫進行聚類，將初始圖像特征庫劃分成若干特征簇，每一個特征可由每一類庫中的單位特征向量來表示，這樣就可以高效地使用多特征的相似性度量進行比較圖像間的相似度，即多特征代替單一特征度量來達到優化圖像檢索結果排序的效果，以改善用戶體驗。實驗結果表明，與SIFT算法相比，改進的SIFT算法在性能上得到顯著提高。

SIFT；分布式；相似性度量；圖像檢索

國家自然科學基金資助項目（No.61202022）、上海市科委科技創新項目（No.12595810200）

0　引言

隨著Internet技術的飛速發展，互聯網資源從文本逐漸演變成為視頻、圖像等多媒體形式并存，數據量隨之急劇上升，同時呈現飛速增長的態勢。如何從這個海量的圖像資源中快速準確地檢索到用戶所需的圖像信息，提高圖像檢索的性能，就成為一個迫切需要解決的問題。

圖像檢索就是根據對圖像內容的描述，在某個目標圖像集合中找到具有指定特征或包含指定內容的圖像。近年來，基于內容的圖像檢索技術得到廣泛的關注和應用，作為一種主要的基于內容的圖像檢索算法，SIFT（Scale-Invariant Feature Transform）算法［1］通過求原始圖像中的特征點以及尺寸和方向的描述子來得到特征，并進行圖像特征點匹配，最終得出圖像之間的相似度。這種方法的優勢在于SIFT特征主要能夠準確地進行匹配且一定程度上不受光照變化、尺寸大小和位置變化等因素的影響。然而，面對海量圖像庫，SIFT算法檢索圖像的時間開銷也非常巨大，而且，它的單一特征相似性度量也較為粗糙，使得檢索出的多個圖像有相同的相似度，難以給出合理的排序。

針對海量圖像庫的檢索效率，研究者借助大數據平臺已經做了大量研究，例如，為了解決在處理海量數據信息所面臨的存取容量和處理速度的問題，文獻［2］和［3］基于Hadoop平臺分別提出了基于MapReduce實現對數字圖像并行化處理和一種基于傳統視覺詞袋（BoVW）模型結合MapReduce計算模型的大規模圖像檢索（MR-BoVW）方案，實驗證明在處理海量圖像庫時，借助Hadoop能極大地提高圖像檢索性能，但它采用離線方式進行批處理，不能實時處理。與Hadoop類似，Spark［4］也是一個大數據平臺，采用基于內存計算的并行處理框架且在迭代計算上具有較高的效率，為用戶的實時體驗提供了有利保障。

在對檢索結果圖像的排序方面，研究者也提出了很多實用方法，例如，利用視覺特征［5］對圖像進行重排序以及引入重排序機制的相關反饋方法［6］，重排序方法的改進可提高檢索的準確率和滿足實時性的要求。

特韋爾斯基（Twersky）認為相似性不能依賴于普通的長度單位來度量，而是定義一個對比模型作為一種參考［7］。本文借鑒對比模型的思想改進相似度度量，借助Spark大數據平臺，提出一種基于分布式并行計算的SIFT算法，Spark平臺下利用K-means算法對圖像特征庫進行聚類，將初始圖像特征庫劃分成單位圖像特征庫，每一個特征可由每一類庫中的單位特征向量來表示，這樣就可以高效地使用多特征的相似性度量進行比較圖像間的相似度，從而提高圖像檢索效率，最后，在圖像相似度上，采用多特征代替單一特征度量來達到優化圖像檢索結果排序的效果，以改善用戶體驗。

1　基本概念

1.1相似性度量

圖像特征相似性度量技術是基于內容的圖像檢索的核心。度量圖像相似性的方法很多，有的用于專門領域，有的適用于特定類型數據，用于圖像檢索的相似性度量方法主要分為距離度量和圖像特征度量。本文所用的是一種距離度量的直方圖距離。

1.2圖像檢索性能評價指標

評價圖像檢索性能指標的是查準率和査全率，這兩個指標是圖像檢索領域最基本的評價指標，分別反映檢索系統的兩個最重要側面。查準率是對圖像檢索系統信噪比的衡量指標，即檢索結果中與查詢樣例內容相關的圖像數目與檢索出的圖像總數目的比例；査全率是對檢索系統成功率的衡量指標，即檢索結果中與查詢樣例內容相關的圖像數目與圖像庫中全部相關圖像數目之比，如式（2）所示。

式（2）中，A為檢索結果中與目標圖像準確相關的圖像數量，B為檢索結果中與目標圖像不相關的圖像數量，C為圖像庫中與目標圖像相關，但未檢索到的圖像數量。

1.3Spark平臺介紹

Spark是 UC Berkeley AMP lab所開源的類Hadoop MapReduce的通用并行框架，由加州大學伯克利分校AMP實驗室開發，可用來構建大型的、低延遲的數據分析應用程序。Spark作為一種并行處理框架，具有Hadoop的一些優點，而且，它有更好的內存管理機制，在迭代計算上具有比Hadoop更高的效率。盡管創建Spark是為了支持分布式數據集上的迭代作業，但是實際上它是對Hadoop的補充，可以在Hadoop文件系統中并行運行。

2　基于分布式并行計算的SIFT算法

1999年，Lowe［8］首次提出了SIFT特征的概念，隨后在2004年得到完善。SIFT算法是一種機器視覺的算法，它可用來提取和描述圖像的局部特征。SIFT特征主要能夠準確地進行匹配且一定程度上不受光照變化、尺寸大小和位置變化等因素的影響。SIFT算法的主要思想是將圖像之間的相似性度量轉化成特征點向量之間的相似性度量。SIFT算法具有廣泛的應用，其中主要包括圖像檢索、視覺跟蹤和三維重建等。

2.1SIFT算法及其分析

根據SIFT算法的概念，SIFT算法的基本步驟如下：

第1步，生成尺度空間。

目前，相關研究者們大多運用Lowe［5］的高斯差分尺度空間來作為二維圖像的尺度空間，其公式為：

式（3）中，G（x，y，σ）是尺度可變的高斯函數；采用高斯差分尺度空間來尋找極值點，是為了有效檢測到關鍵點。

第2步，檢測尺度空間極值點。

每一個樣本點和它周圍同尺度的8領域點進行比較是否為極值點。

第3步，精確定位極值點。

為了精確定位極值點，可通過擬合泰勒公式展開的三維二次函數達到此效果；這樣同時也可以去除不穩定的邊緣噪點和低對比度的關鍵點，也即提高抗噪能力。

第4步，為每個關鍵點指定方向參數。

每個關鍵點方向為參數是由關鍵點領域像素的梯度方向分布特性決定的，一個關鍵點可能會被分配多個方向，其中一個是主方向，其他的是輔助方向，這樣可以增強圖像特征匹配的魯棒性。

第5步，生成關鍵點描述子。

指定完每個關鍵點的方向，然后接下來為關鍵點生成描述子；其中描述子一般是由4×4×8維向量特征，也即是4×4組8個方向的梯度方向直方圖；對于一個關鍵點產生32個數據，即最終形成128維的SIFT特征向量。一般需要對特征向量的長度進行歸一化處理，則可以去除光照變化的影響。

第6步，根據SIFT特征向量來計算兩幅圖像的相似度。

圖1　SIFT算法的圖解過程

下面以一個實例圖解SIFT算法來計算兩幅圖像的相似度，設有兩幅大小一致的紅花朵圖像，如圖1所示。

若相似度系數越接近0，則表示兩幅圖像越相似。

分別利用SIFT算法對兩幅圖像進行特征提取，然后利用兩幅圖像的描述子 （分別是k1×128維和k2× 128維），將其每個描述子按照梯度大?。╯cale）來映射到直方圖的各個方向的的局部子直方圖中，如圖1所示，紅花a圖對應的描述子直方圖集合另一幅圖紅花b圖對應的描述子直方圖集合Hb=則計算Ha和Hb的距離公式為：

那么它們的相似度系數為：

參照文獻［9］以及本文的實際情況，

若，0≤α≤0.4則兩幅圖像相似。

若α≥0.4，則兩幅圖像不相似。

最后通過計算得到它們的相似度系數為0.14，則說明兩幅圖像相似。

根據上述SIFT算法的基本步驟，分析了SIFT算法的不足：一是，提取出每幅圖像的SIFT特征比較單一和粗糙（局部的圖像特征代替整個圖像特征）；二是，隨著圖像庫容量的迅猛增長，SIFT算法的計算效率也隨之大大下降。

2.2基于分布式并行計算的SIFT算法

由于SIFT算法利用局部的圖像特征來進行圖像的檢索，也就說用局部的圖像特征代替整個圖像特征，從而導致查準率降低了；為了提高查準率，這就需要對圖像進行分塊以及再對分塊的圖像提取SIFT特征，但在這個過程中圖像分塊和提取各分塊圖像的SIFT特征會大大降低圖像檢索效率。為了提高檢索效率，本文通過Spark平臺處理大規模的數據集圖像來并行提取SIFT特征，從而降低算法的復雜度，這就是所謂的并行計算策略。

改進的SIFT算法具體的過程如下：

第1步，特征集的提取。

此步驟中包含了SIFT算法的第一到第五步，這里就不在詳細地描述。為了實現分布式的提取SIFT特征，即需要對原始圖像進行分塊，圖像分塊原則是將圖像分成每塊大小為N×N像素的塊圖像，這樣有利于比較塊圖像之間的相似性，再對每一塊圖像進行生成高斯差分尺度空間，再檢測極值點和計算描述子，最終實現了特征提取。如圖2所示。

第2步，特征庫構建。

特征庫指的是SIFT特征向量的集合，也就將第一步中輸出的結果進行保存。構建特征庫是為了節約磁盤容量和提高圖像檢索的效率，因為隨著圖像庫容量的增長，檢索的效率會大大下降，同時數據存儲成本也越來越大。特征庫的建立可以將這些特征向量集一一對應著圖像庫中的每幅圖像，也即達到了節約存儲容量的效果。

第3步，特征庫歸類。為了進一步節約存儲成本和較快匹配特征，就需要將這些特征向量進行分類。由于SIFT的特征向量一般是128維向量，也是基于歐氏空間的。K-means主要用于基于距離進行聚類的算法，即可以對這些特征向量集進行分類。特征庫中的所有特征向量經過K-means算法聚類后生成基本映射特征庫S，該特征庫集合可表示為：

其中ek表示任意一個單位映射特征，n表示單位映射特征總數。由此可看出每個單位映射特征是基于歐氏空間的128維特征向量，特征庫被分成了n個簇，也即第特征向量可有表示為：

其中，αiei表示單位映射特征ei在第特征向量中出現的αi次。

第4步，特征匹配。

依據上述的特征表示公式得知，第β個特征向量可有ek表示為：

則兩個特征的匹配公式如下所示：

圖2　SIFT特征集的提取

參照文獻［10］以及本文的實際情況，

若0≤p（α，β）≤0.4，則兩個特征相匹配。

若p（α，β）＞0.4，則兩個特征不相匹配。

第5步，輸出匹配的結果。

一般一幅圖像包含多個特征，即圖像間的匹配就意味著圖像的多特征匹配。

本文采用的是匹配原則是以一個主特征為主，其余的特征為輔。

3　實驗過程與分析

Corel圖像庫是一個人為整理且根據先驗知識對圖像進行劃分的圖像庫，它被研究者們當作圖像檢索領域的測試圖像標準庫。Corel圖像庫的種類繁多，目前包含了數十萬幅圖像。從實驗的硬件環境出發，在Corel圖像庫［10］中選取10000幅圖像，進行測試與分析，這些圖像分為十個類別，每類1000幅，分別為花、巴士、食物、大象、建筑、駿馬、恐龍、人臉、天空和雪山。對于本文提出的基于內容的檢索算法所要處理的圖像庫而言，首先將已分類好的圖像庫進行打亂，為了使其滿足本文算法的圖像庫要求。實驗硬件平臺為2.67GHz主頻的CPU，可用內存3.87G，軟件開發工具Eclipse，開發語言Java，并基于Spark平臺對原圖像庫中的每幅圖像進行分塊并行計算提取SIFT特征。

3.1實驗過程

實驗分成三個對照實驗，將SIFT算法與改進的SIFT算法進行比較，從而驗證改進的SIFT算法比SIFT算法有更好的性能并且用戶的體驗效果更佳。實驗一：將這兩種算法分別運用基于內容的圖像檢索基本系統，然后分別在其中查詢相同的目標圖像，最后比較它們的查準率，目的是為了通過評價它們檢索的性能來驗證改進的SIFT算法性能更優；實驗二：改進的SIFT算法與傳統SIFT算法在不同規模的圖像庫下，通過對比其平均檢索時間來比較它們的時間復雜度，目的是為了驗證改進的SIFT算法在檢索大規模圖像集的圖像庫時的時間復雜度較低，即在用戶可接受范圍之內；實驗三：傳統SIFT算法與改進的SIFT算法分別應用于基本的內容的檢索系統中，查詢相同的目標圖像，通過對比返回的候選檢索結果排序，目的是為了驗證改進的SIFT算法檢索出的圖像頁面排序更合理和便于用戶友好的交互。

3.2結果與分析

實驗一是SIFT算法與改進的SIFT算法對圖像庫中三類（花、大象、駿馬）的查準率，見表1。

表1　傳統SIFT與改進的SIFT對某幾類圖像庫的查準率對比

從表1可知，改進的SIFT算法對各類平均查準率較傳統SIFT算法高約20%，說明改進的SIFT算法優勢明顯。

實驗二是改進的SIFT算法與傳統SIFT算法在不同規模數據量時的時間復雜度進行對比，結果詳見圖3。

圖3　SIFT算法與改進的SIFT算法運行時間對比

從圖3可以看出，隨著圖像庫的規模增大，傳統SIFT算法時間代價增長較快，而改進的SIFT算法時間代價增長相對較緩，改進的SIFT算法的運行效率明顯優于傳統SIFT算法。

實驗三為傳統SIFT算法與改進的SIFT算法對候選檢索結果排序的對比，結果詳見圖4。

圖4為待查詢圖像為紅色花朵圖像b（如圖1）時的候選檢索結果，圖4（a）的SIFT算法頁面查詢結果中的候選圖像根據比較單個SIFT特征值來排序，從而導致圖像的排序比較粗糙和單一，即會影響到用戶的友好體驗；而圖4（b）的改進的SIFT算法頁面查詢結果中候選圖像則依據圖像的多個SIFT特征值的相似度大小來排序，從而會使圖像的排序更加合理和多樣化，最終會改善用戶的體驗。

4　結語

本文提出了基于分布式并行計算的SIFT算法，該算法不需要用戶對檢索結果評價的樣本，也不需要控制圖像庫數據集大小，運用了分布式的并行計算框架，對分塊的圖像并行地提取各自的SIFT特征值，然后對提取出來的SIFT特征值利用K-means進行聚類，找出每個類庫中的單位特征向量，使得每個SIFT特征向量可由單位特征向量組成，然后在計算圖像間的相似度時，利用多特征代替單一特征度量，不僅適應海量圖像的檢索，而且檢索結果的圖像排序也更加合理。實驗結果表明，這種基于分布式并行計算的SIFT算法有效地解決了圖像檢索的數據集擴張局限和候選圖像集的不合理排序等問題，從而便于有效地提高了用戶交互體驗。

圖4　兩種算法候選結果排序

［1］ZK Wen，WZ Zhu，Quyang-Jie，et al.A Robust and Discriminative Image Perceptual Hash Algorithm［C］.2010 Fourth International Conference on.IEEE，2011∶709-712.

［2］田進華，張韌志.基于MapReduce數字圖像處理研究［J］.電子設計工程，2014.

［3］朱為盛，王鵬.基于Hadoop云計算平臺的大規模圖像檢索方案［J］.計算機應用，2014.

［4］Zaharia M，Chowdhury M，Franklin M J，et al.Spark∶Cluster Computing with Working Sets［J］.Book of Extremes，2010，15（1）∶1765-1773.

［5］陳暢懷，韓立新，曾曉勤，等.基于視覺特征的圖像檢索重排序［J］.信息技術，2012

［6］楊德三，李明，劉玲.一種新的基于重排序的相關反饋圖像檢索方法［J］.計算機工程與應用，2008

［7］A.Twersky.Features of Similarity.Psychological Review，84，No 4∶327-352，July 1977.

［8］David G.Lowe.Object Recognition from Local Scale-Invariant Features［C］.International Conference on Computer Vision，Corfu，Greece，1999.9.

［9］David G.Lowe.Distinctive Image Features from Scale-Invariant Keypoints［J］.International Journal of Computer Vision，2004.

［10］Wang J Z's Research Group，The Pennsylvania State University.Test Image Database［EB/OL］.［2005-10-08］.

Sift；Distribution；Similarity Measure；Image Retrieval

SIFT Algorithm Based on Distributed Parallel Computing

SU Yong-gang，GAO Mao-ting
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

To overcome the problem that the SIFT algorithm handles large amount of images in lower efficiency and the sequence of the result images is unreasonable，proposes SIFT algorithm based on distributed parallel compute，the new algorithm utilizes K-means algorithm to cluster initial image feature library，divides these features into several feature clusters，every feature can be expressed by each unit feature vector in every cluster so that it can effectively use multi feature similarity measures compare the similarity between images，namely multi feature instead of a single feature to optimize the sort of the retrieved image set and improve the user's experience.Experimental results show that compared with the SIFT algorithm，the improved algorithm has been significantly improved in performance.

1007-1423（2016）20-0018-06

10.3969/j.issn.1007-1423.2016.20.004

蘇勇剛（1992-），男，江蘇鹽城人，碩士，研究方向為圖像處理、數據挖掘

高茂庭（1963-），男，江西九江人，博士，教授，研究方向為智能信息處理、數據庫與信息系統

2016-04-25

2016-07-05