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

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

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

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

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

國家自然科學(xué)基金資助項(xiàng)目（No.61202022）、上海市科委科技創(chuàng)新項(xiàng)目（No.12595810200）

0　引言

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

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

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

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

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

1　基本概念

1.1相似性度量

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

1.2圖像檢索性能評價指標(biāo)

評價圖像檢索性能指標(biāo)的是查準(zhǔn)率和査全率，這兩個指標(biāo)是圖像檢索領(lǐng)域最基本的評價指標(biāo)，分別反映檢索系統(tǒng)的兩個最重要側(cè)面。查準(zhǔn)率是對圖像檢索系統(tǒng)信噪比的衡量指標(biāo)，即檢索結(jié)果中與查詢樣例內(nèi)容相關(guān)的圖像數(shù)目與檢索出的圖像總數(shù)目的比例；査全率是對檢索系統(tǒng)成功率的衡量指標(biāo)，即檢索結(jié)果中與查詢樣例內(nèi)容相關(guān)的圖像數(shù)目與圖像庫中全部相關(guān)圖像數(shù)目之比，如式（2）所示。

式（2）中，A為檢索結(jié)果中與目標(biāo)圖像準(zhǔn)確相關(guān)的圖像數(shù)量，B為檢索結(jié)果中與目標(biāo)圖像不相關(guān)的圖像數(shù)量，C為圖像庫中與目標(biāo)圖像相關(guān)，但未檢索到的圖像數(shù)量。

1.3Spark平臺介紹

Spark是 UC Berkeley AMP lab所開源的類Hadoop MapReduce的通用并行框架，由加州大學(xué)伯克利分校AMP實(shí)驗(yàn)室開發(fā)，可用來構(gòu)建大型的、低延遲的數(shù)據(jù)分析應(yīng)用程序。Spark作為一種并行處理框架，具有Hadoop的一些優(yōu)點(diǎn)，而且，它有更好的內(nèi)存管理機(jī)制，在迭代計算上具有比Hadoop更高的效率。盡管創(chuàng)建Spark是為了支持分布式數(shù)據(jù)集上的迭代作業(yè)，但是實(shí)際上它是對Hadoop的補(bǔ)充，可以在Hadoop文件系統(tǒng)中并行運(yùn)行。

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

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

2.1SIFT算法及其分析

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

第1步，生成尺度空間。

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

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

第2步，檢測尺度空間極值點(diǎn)。

每一個樣本點(diǎn)和它周圍同尺度的8領(lǐng)域點(diǎn)進(jìn)行比較是否為極值點(diǎn)。

第3步，精確定位極值點(diǎn)。

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

第4步，為每個關(guān)鍵點(diǎn)指定方向參數(shù)。

每個關(guān)鍵點(diǎn)方向?yàn)閰?shù)是由關(guān)鍵點(diǎn)領(lǐng)域像素的梯度方向分布特性決定的，一個關(guān)鍵點(diǎn)可能會被分配多個方向，其中一個是主方向，其他的是輔助方向，這樣可以增強(qiáng)圖像特征匹配的魯棒性。

第5步，生成關(guān)鍵點(diǎn)描述子。

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

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

圖1　SIFT算法的圖解過程

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

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

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

那么它們的相似度系數(shù)為：

參照文獻(xiàn)［9］以及本文的實(shí)際情況，

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

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

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

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

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

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

改進(jìn)的SIFT算法具體的過程如下：

第1步，特征集的提取。

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

第2步，特征庫構(gòu)建。

特征庫指的是SIFT特征向量的集合，也就將第一步中輸出的結(jié)果進(jìn)行保存。構(gòu)建特征庫是為了節(jié)約磁盤容量和提高圖像檢索的效率，因?yàn)殡S著圖像庫容量的增長，檢索的效率會大大下降，同時數(shù)據(jù)存儲成本也越來越大。特征庫的建立可以將這些特征向量集一一對應(yīng)著圖像庫中的每幅圖像，也即達(dá)到了節(jié)約存儲容量的效果。

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

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

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

第4步，特征匹配。

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

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

圖2　SIFT特征集的提取

參照文獻(xiàn)［10］以及本文的實(shí)際情況，

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

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

第5步，輸出匹配的結(jié)果。

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

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

3　實(shí)驗(yàn)過程與分析

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

3.1實(shí)驗(yàn)過程

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

3.2結(jié)果與分析

實(shí)驗(yàn)一是SIFT算法與改進(jìn)的SIFT算法對圖像庫中三類（花、大象、駿馬）的查準(zhǔn)率，見表1。

表1　傳統(tǒng)SIFT與改進(jìn)的SIFT對某幾類圖像庫的查準(zhǔn)率對比

從表1可知，改進(jìn)的SIFT算法對各類平均查準(zhǔn)率較傳統(tǒng)SIFT算法高約20%，說明改進(jìn)的SIFT算法優(yōu)勢明顯。

實(shí)驗(yàn)二是改進(jìn)的SIFT算法與傳統(tǒng)SIFT算法在不同規(guī)模數(shù)據(jù)量時的時間復(fù)雜度進(jìn)行對比，結(jié)果詳見圖3。

圖3　SIFT算法與改進(jìn)的SIFT算法運(yùn)行時間對比

從圖3可以看出，隨著圖像庫的規(guī)模增大，傳統(tǒng)SIFT算法時間代價增長較快，而改進(jìn)的SIFT算法時間代價增長相對較緩，改進(jìn)的SIFT算法的運(yùn)行效率明顯優(yōu)于傳統(tǒng)SIFT算法。

實(shí)驗(yàn)三為傳統(tǒng)SIFT算法與改進(jìn)的SIFT算法對候選檢索結(jié)果排序的對比，結(jié)果詳見圖4。

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

4　結(jié)語

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

圖4　兩種算法候選結(jié)果排序

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

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

［4］Zaharia M，Chowdhury M，F(xiàn)ranklin M J，et al.Spark∶Cluster Computing with Working Sets［J］.Book of Extremes，2010，15（1）∶1765-1773.

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

［6］楊德三，李明，劉玲.一種新的基于重排序的相關(guān)反饋圖像檢索方法［J］.計算機(jī)工程與應(yīng)用，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-），男，江蘇鹽城人，碩士，研究方向?yàn)閳D像處理、數(shù)據(jù)挖掘

高茂庭（1963-），男，江西九江人，博士，教授，研究方向?yàn)橹悄苄畔⑻幚?、?shù)據(jù)庫與信息系統(tǒng)

2016-04-25

2016-07-05