應(yīng)用MapReduce與視覺描述符的圖像檢索算法

盛昀瑤，張福泉，任 艷

(1.常州機電職業(yè)技術(shù)學院 信息工程學院， 江蘇 常州 213164；2.北京理工大學 計算機學院， 北京 100081；3.新疆財經(jīng)大學 計算機科學與工程學院, 烏魯木齊 830012)

隨著移動互聯(lián)網(wǎng)的普及，諸如微信、團購網(wǎng)站、淘寶網(wǎng)等應(yīng)用中包含了海量的圖像數(shù)據(jù)庫，目前許多購物網(wǎng)站與搜索引擎均支持對圖像的直接搜索[1]，如何準確、快速地檢索出目標圖像成為了當前的研究熱點[2-4]。

當前的大型網(wǎng)站與APP大多采用云計算與云存儲技術(shù)構(gòu)建后端服務(wù)器，這一方面能提高資源的利用率，另一方面也可以降低服務(wù)提供商的運營成本。Apache的Hadoop項目[5]已經(jīng)廣泛地應(yīng)用于商業(yè)與科研領(lǐng)域中，成為一個完整的生態(tài)系統(tǒng)，可以通過JAVA語言編程實現(xiàn)基于Apache Hadoop的云計算分布式處理程序。一方面許多網(wǎng)絡(luò)服務(wù)提供商采用了云計算與云存儲來提供優(yōu)質(zhì)的服務(wù)，另一方面，可通過云計算的分布式處理提高網(wǎng)絡(luò)服務(wù)(例如圖像檢索)的計算效率[6]。因此，基于云計算的圖像檢索算法成為了當前的研究熱點[7-8]。

目前，針對云計算中圖像檢索算法的研究較多。文獻[9]提出了一種基于傳統(tǒng)視覺詞袋(BoVW)模型和MapReduce計算模型的大規(guī)模圖像檢索(MR-BoVW)方案，該方案引入一種改進的Hadoop圖像數(shù)據(jù)處理方法，在此基礎(chǔ)上采用分特征向量生成、特征聚類、圖片的向量表示與倒排索引構(gòu)建3個階段MapReduce化，獲得了較好的效果。但該方案為了避免Hadoop處理小文件效率低的問題，將原始圖片的所有信息存入一個大文件中，嚴重影響了算法的時間效率。文獻[10]提出了一種基于Hadoop的圖像檢索算法，該算法采用SURF提取圖像的特征，采用LSH實現(xiàn)圖像的特征匹配，利用Hadoop的并行計算能力提高了基于內(nèi)容圖像檢索的效率，但是并未考慮Hadoop平臺處理小文件性能差的問題，因此，該算法仍然具有提升的空間。

基于Hadoop的CBIR(基于內(nèi)容的圖像檢索)系統(tǒng)主要有3個難題[9]：① 在保證提取圖像特征效果的同時，如何提高圖像特征的提取速度；② 在不影響檢索準確率的前提下，如何提高大數(shù)據(jù)CBIR系統(tǒng)的時間效率；③ Hadoop云計算平臺對小文件的管理效率差，而圖像數(shù)據(jù)庫由大量的小文件組成。針對上述3個難題，本文提出了一個基于Hadoop框架的快速CBIR算法，使用BOVW(視覺詞袋模型)[10]提取圖像的特征，對二叉搜索樹進行了修改，提高圖像檢索過程中相似性匹配的搜索效率，并且設(shè)計了新的圖像索引技術(shù)，將小文件高效地組織成大文件，提高Hadoop對圖像庫的管理效率。

1 基于內(nèi)容的圖像檢索技術(shù)

基于內(nèi)容的圖像檢索技術(shù)(CBIR)主要包含以下步驟：首先，提取查詢圖像的特征矢量；然后，通過將該圖像特征矢量與特征庫中的特征矢量進行相似性匹配，根據(jù)匹配結(jié)果到圖像庫中搜索，提取出與所查詢圖像最相似的圖像；最終，將提取的圖像返回給用戶。

一個標準的CBIR系統(tǒng)主要可分為4層，如圖1所示。第1層為用戶查詢與人機交互。該層讀取用戶查詢請求，對用戶的查詢請求與圖像庫進行預(yù)處理。第2層為圖像的信息表示與特征提取。該層主要包含2個任務(wù)：首先檢測與表示圖像的興趣點，然后建立圖像的索引。一般而言，圖像的視覺特征矢量屬于高維空間，因此可使用聚類算法對特征矢量進行處理。第3層為相似性匹配與圖像索引，首先計算查詢圖像特征向量與特征庫中特征向量的相似性，然后通過索引獲得圖像庫中對應(yīng)的圖像。第4層為相關(guān)反饋，即通過人機交互建立圖像視覺特征與圖像語義之間的聯(lián)系，提高檢索精度。

2 算法設(shè)計

本文設(shè)計了結(jié)合Hadoop與CBIR系統(tǒng)的新框架，設(shè)計了圖像的視覺特征提取算法，并且設(shè)計了圖像興趣點的提取算法，最終采用Hadoop的Map Reduce分布式處理來完成最耗時間的相似性匹配程序。該框架分為線下層和線上層。

圖1 一個標準的CBIR系統(tǒng)

1) 線下層。該層各個模塊的任務(wù)無需人機交互。如圖2所示，分別是圖像數(shù)據(jù)庫的預(yù)處理模塊、圖像表示模塊與Hadoop輸入文件預(yù)處理模塊。本系統(tǒng)的線下層有3個優(yōu)點：① 提高了視覺特征的視覺表示準確率；② 降低了圖像表示的維度；③ 解決了Hadoop管理小文件性能較差的問題。

2) 線上層。該層的模塊負責人機交互，分別是查詢預(yù)處理模塊、Maper Reducer模塊。本算法線上層的優(yōu)點為：通過MapReduce的分布式處理降低了相似性匹配的計算時間。

圖2 本算法的線下層算法

2.1 線上層

線上層由3個模塊組成：圖像庫預(yù)處理模塊、圖像表示模塊與Hadoop輸入文件預(yù)處理模塊。

2.1.1 圖像庫預(yù)處理模塊

該模塊對圖像庫的圖像進行預(yù)處理，共包含2個部分:① 對輸入圖像進行尺度變換，檢測圖像興趣點；② 將彩色圖像變換為灰度圖像，建立圖像描述符(尺度不變特征描述符SIFT)。

檢測圖像興趣點：將輸入圖像I(x,y)與變尺度高斯函數(shù)G(x,y,σ)進行卷積運算，然后，通過高斯分布的差分方法(DOG)搜索尺度空間的興趣點。式(1)～(3)是搜索圖像興趣點的算法。

L(x,y,σ)=G(x,y,σ)*I(x,y)

(1)

式中：L(x,y,σ)為定義尺度空間的函數(shù)；“*”為x維度與y維度的卷積運算；σ為尺度空間的因子。

G(x,y,σ)=1/(2πσ2)e-(x2+y2)/2σ2

(2)

檢測DOG興趣點的方法如式(3)所示。

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

L(x,y,kσ)-L(x,y,σ)

(3)

式中k為一個常量系數(shù)。

尺度不變特征描述符(SIFT)：SIFT描述符具有旋轉(zhuǎn)不變性與尺度不變性，根據(jù)興趣點的位置決定興趣點的方向[13]。假設(shè)一個樣本圖像為L(x,y)，可通過以下兩式計算其梯度高度m(x,y)與梯度方向θ(x,y)[13]：

m(x,y)=

(4)

(5)

在檢測的興趣點周圍劃分16個子區(qū)域，根據(jù)興趣點的幅度與方向為每個子區(qū)域建立一個直方圖(包含8個bin)。最終，將16個直方圖與8個bin做卷積運算，即每個興趣點共有128個值，組成SIFT的描述符向量。

2.1.2 圖像表示模塊

為了提高視覺詞袋的計算效率，對傳統(tǒng)的視覺詞袋技術(shù)進行了改進。該模塊主要包含3個部分：興趣點分類器、改進二叉搜索樹的計算模塊、視覺描述符生成器。

1) 興趣點分類器。圖像的興趣點包含大量的SIFT詞匯(BOW)向量，因此需要對龐大的SIFT詞匯向量進行分類處理。使用歐式距離度量2個SIFT詞匯向量之間的距離，從而計算圖像中2個興趣點的相似性，該步驟為每個圖像構(gòu)建了一個(興趣點-興趣點)的相似性矩陣。2個興趣點(x1,y1)與(x2,y2)之間的歐式距離dx,y計算式如下：

(6)

2) 基于修改二叉搜索樹的視覺特征檢測。給定一個圖像的興趣點，目標是找到圖像中與該興趣點距離最近的點，將這些點稱為近鄰點。可通過遍歷圖像的所有點，計算各點到中心點(興趣點)的距離，即可簡單地解決該問題，顯然該線性搜索算法的計算復雜度較高。本文為此設(shè)計了高效率的計算算法。二叉搜索樹(BST)的排序速度與搜索速度較快[14-15]，因此本文使用二叉搜索樹來提高該步驟的速度。設(shè)計了一個修改的二叉搜索樹，該搜索樹支持同時分配興趣點與樹的值，將圖像中每一對興趣點的圖像ID作為鍵值(key)，2個興趣點的相似性作為二叉樹的值(value)。

二叉樹的新節(jié)點插入算法：首先，計算該對興趣點(新興趣點)的相似性，然后，計算該對興趣點的下一個最小相似性，并且向樹內(nèi)插入一對新的興趣點。確定二叉樹第一層的節(jié)點之后，計算二叉樹第一層節(jié)點的相似性平均值，將該值稱為樹的閾值。重復上述步驟可完成所有興趣點的插入，對于新的視覺特征，則重復上述步驟。

圖3是本算法創(chuàng)建前2個視覺特征的實例。首先，建立特征庫中興趣點之間相似性的(興趣點-興趣點)矩陣，將相似性最小的興趣點-興趣點組合作為二叉搜索樹的根節(jié)點；然后，計算二叉樹第1層的相似性平均值，作為二叉樹的閾值，根據(jù)該閾值決定新插入的節(jié)點；最終，將滿足閾值的新節(jié)點插入二叉樹中，建立完全的二叉搜索樹。

3) 創(chuàng)建視覺特征。通過視覺特征來表示圖像的視覺信息，使用SIFT描述符描述圖像的信息，每個SIFT向量共有128個值，一個SIFT向量描述一個興趣點的信息，因此，一個SIFT向量集合描述了一個圖像的視覺信息。

因為SIFT向量的維度較高，計算復雜度較高，所以需要降低興趣點的數(shù)量。通過比較分析技術(shù)創(chuàng)建圖像的視覺特征。首先，在圖像的所有興趣點中選出候選興趣點，計算圖像中所有興趣點的均值，提取出均方誤差(MSE)最小的興趣點來表示圖像的視覺信息。

2.1.3 Hadoop輸入文件預(yù)處理模塊

Hadoop處理大文件的效率明顯高于碎片化的小文件。Hadoop的邏輯是將大文件分配到一個機器上處理，但許多小文件則會均衡地分配到各個機器上處理，而這些小文件的復制為分布式服務(wù)器增加了帶寬負擔，從而減緩而了整個Hadoop中MapReduce任務(wù)的處理時間。

Hadoop主要讀取3個文件類型：① Text Input format：將文件中每一行作為一個記錄，每一行在文件中的起始偏移量作為key值，每一行的內(nèi)容作為value值；② key-value Text Input format：根據(jù)文件中的tab符號來區(qū)分每行記錄的key值與value值；③ Sequence File Input format：Sequence文件中的key值和value值以二進制形式存放。

在該模塊中，設(shè)計了一個key-value的索引方案將若干的小文件組織成一個大文件，從而提高MapReduce的處理效率。將每個圖像的ID作為key，圖像的特征作為value，key-value信息是Mapper模塊的輸入信息。具體流程為：首先，讀取每個圖像的視覺特征；然后，將圖像ID作為key，將圖像特征作為value，圖像庫的每個圖像生成一個key-value數(shù)據(jù)，保存于一個索引文件中。

2.2 線下層

線下層包含2個模塊：查詢預(yù)處理模塊與Mapper-Reducer模塊，如圖4所示。

圖4 本算法的線上層算法

2.2.1 查詢圖像的預(yù)處理模塊

與圖像庫的預(yù)處理方式相同。

2.2.2 Mapper-reducer模塊

MapReduce是Hadoop的編程模型，該模塊利用Hadoop的MapReduce模塊計算查詢圖像與圖像庫之間的相似性。該模塊的任務(wù)是計算查詢圖像與圖像庫的特征相似性，相似性匹配計算是本算法中最耗時的程序。

首先，生成足夠數(shù)量的mapper函數(shù)，每個Mapper模塊迭代地讀取每個key-value記錄；然后，Mapper模塊將key值相同的所有key-value記錄輸出到同一個reduce模塊，因此，該處理包含了“復制→合并→排列”3個操作，最終將key值相同的key-value記錄傳遞至同一個reducer模塊。

① Mapper：將各個查詢圖像與圖像庫均表示為視覺特征的集合。本文將圖像ID作為key，并且建立了每個查詢圖像的特征與圖像庫的特征組合，每個組合表示為，其中key表示圖像ID，value表示該圖像特征與所有查詢圖像特征的總體相似性，例如：的意義是：I_ID表示了圖像序號，Sim_value表示了圖像庫所有特征與查詢圖像特征相似性的平均值。

② Reducer：MapReduce的第2個任務(wù)是重組key-value記錄，將value聚集到一起。因此，Reducer將查詢圖像與圖像庫中所有圖像的相似性聚集到一起，生成每個查詢圖像與整個圖像庫的相似性平均值。最終，將計算的相似性排序處理，并且將圖像庫中最相似的若干圖像作為查詢結(jié)果，返回給用戶。

3 仿真實驗與分析

本算法的目標是利用MapReduce云計算分布式處理能力來降低基于內(nèi)容的大數(shù)據(jù)圖像檢索算法的計算時間，在此，通過一組仿真實驗評估本算法的性能與效果。

3.1 實驗環(huán)境與參數(shù)設(shè)置

在開源平臺Apache Hadoop YARN(2.7.2)上采用Java JDK 1.6編程實現(xiàn)了本算法的線上部分，Hadoop平臺設(shè)置了8個節(jié)點，并且使用Matlab實現(xiàn)了本算法的線下部分。實驗環(huán)境為Intel Core i7處理器，8GB內(nèi)存，Ubuntu 12.10操作系統(tǒng)。

為了評估本算法對不同圖像數(shù)據(jù)集的有效性，采用了2個圖像檢索領(lǐng)域的公開數(shù)據(jù)集：① INRIA Holidays dataset(http://lear.inrialpes.fr/～jegou/data.php)。該數(shù)據(jù)集的圖像分辨率較高，圖像容量較大，共有812個圖像，每個圖像分辨率為2448×3264，圖像的平均大小為2 M；② NUS-WIDE dataset(http://lms.comp.nus.edu.sg/research/NUS-WIDE.htm)，該數(shù)據(jù)集屬于大規(guī)模數(shù)據(jù)集，共有269 648個圖像，每個圖像分辨率為240×180，圖像的平均容量為26 K。本實驗將INRIA Holidays dataset與NUS-WIDE dataset匯合成實驗的benchmark數(shù)據(jù)集，評估本算法對于不同分辨率、不同類型的圖像數(shù)據(jù)集的性能。圖5所示是2個圖像檢索公開數(shù)據(jù)集的部分圖像實例。

圖5 圖像檢索實驗的benchmark數(shù)據(jù)集實例

3.2 性能度量指標

目前針對圖像檢索系統(tǒng)尚無統(tǒng)一的性能指標，本文采用精度指標評估檢索系統(tǒng)的準確率性能。精度定義為檢索出的相關(guān)圖像數(shù)與檢索出的圖像總數(shù)的比率，衡量的是檢索系統(tǒng)的查準率。

假設(shè)檢索系統(tǒng)將圖像數(shù)據(jù)集分為j個類，那么圖像檢索系統(tǒng)的精度與平均精度則可分別定義為：

Precision(i,j)=nij/nj

(7)

式中：n表示圖像數(shù)量；ni是類in的圖像數(shù)量；nj是簇j的圖像數(shù)量；nij是同屬于類i與類j的圖像數(shù)量。

平均精度：

*Ij

(8)

式中：N是相關(guān)圖像的數(shù)量；Nj是最高j個搜索結(jié)果中的相關(guān)圖像數(shù)量；k為用戶設(shè)定的候選相關(guān)圖像數(shù)量。如果第j個樣本是相關(guān)圖像，那么Ij設(shè)為1，否則設(shè)為0。

3.3 實驗結(jié)果與數(shù)據(jù)分析

HadoopCBIR是一種基于Hadoop的CBIR系統(tǒng)，該算法采用SURF提取圖像的特征，采用LSH實現(xiàn)圖像的特征匹配，該算法利用Hadoop的并行計算能力提高了基于內(nèi)容圖像檢索的效率，但是并未考慮Hadoop平臺處理小文件性能差的問題，將本算法與之比較，評估本算法的改進效果。SSHashCBIR[16]與hashCBIR[17]算法均為檢索準確率較高的CBIR算法，將本算法與兩者比較，評估本算法的檢索準確率。

3.3.1 大規(guī)模數(shù)據(jù)集的檢索準確率性能

圖6所示是5個算法對于benchmark數(shù)據(jù)集的檢索精度結(jié)果，從圖中可看出：當k=1時，本算法的精度比HadoopCBIR、SSHashCBIR、hashCBIR算法分別提高了0.2、0.13、0.112；當k=100時，本算法的精度比HadoopCBIR、SSHashCBIR、hashCBIR算法分別提高了0.04、0.03、0.02。可見本算法獲得了較高的檢索準確率。

圖6 4個算法的平均檢索精度值

3.3.2 檢索算法的時間效率

圖7所示是本算法對于不同數(shù)量圖像集合的檢索時間效率，可以看出：本算法的計算時間隨著圖像數(shù)量呈對數(shù)增長的趨勢。雖然圖像庫中Holiday數(shù)據(jù)集的圖像分辨率較高，但本算法對于圖像庫的規(guī)模仍然表現(xiàn)出較好的可擴展性。

圖7 本算法對于不同數(shù)量圖像集合的檢索時間

將本算法的時間效率與HadoopCBIR算法進行比較，結(jié)果如圖8所示。從圖8中可看出：本算法的檢索時間明顯地快于HadoopCBIR算法。一方面，本算法利用了Hadoop的分布式處理技術(shù)計算了圖像檢索系統(tǒng)中最耗時的相似性匹配部分，另一方面，本文設(shè)計的修改二叉搜索樹技術(shù)高效地提取了圖像特征，進一步加速了圖像的相似性匹配過程。然而，HadoopCBIR算法并未考慮Hadoop平臺處理小文件性能差的問題，Hadoop平臺管理海量小文件的效率較低。

圖8 本算法與HadoopCBIR算法的時間效率比較

最終評估本算法對于不同規(guī)模數(shù)據(jù)集的加速效果。隨機地將benchmark數(shù)據(jù)集分為3個規(guī)模：小規(guī)模數(shù)據(jù)集共有1 000個圖像，總存儲量為1.01 GB；中等規(guī)模數(shù)據(jù)集共有50 000個圖像，總存儲量為2.5 GB；大規(guī)模數(shù)據(jù)集則包含所有的benchmark數(shù)據(jù)集圖像，總存儲量為7.1 GB。圖9所示是本算法對于3個數(shù)據(jù)集的加速效果(與Yin算法比較)，可見數(shù)據(jù)集規(guī)模越大，本算法的加速效果越明顯。對于7.1GB的數(shù)據(jù)集，本算法將檢索時間效率提高了約20%，獲得了明顯的效果。

圖9 本算法對于3個數(shù)據(jù)集的加速效果(與HadoopCBIR算法比較)

4 結(jié)束語

本文提出了一個基于Hadoop框架的快速CBIR算法，使用BOVW(視覺詞袋模型)提取圖像的特征，對二叉搜索樹進行了修改，提高圖像檢索過程中相似性匹配的搜索效率，并且設(shè)計了新的圖像索引技術(shù)，將小文件高效地組織成大文件，提高Hadoop對圖像庫的管理效率。結(jié)合Hadoop與CBIR系統(tǒng)的新框架，設(shè)計了圖像的視覺特征提取算法，并且設(shè)計了圖像興趣點的提取算法，最終采用Hadoop的Map Reduce分布式處理來完成最耗時間的相似性匹配程序。最終基于大數(shù)據(jù)圖像庫的實驗結(jié)果表明，本算法不僅獲得了較高的檢索準確率，并且大幅度地提高了圖像檢索的速度，對于大數(shù)據(jù)集的加速效果更為明顯。

由于本算法是基于內(nèi)容的圖像檢索算法，所以本算法的穩(wěn)定性、魯棒性均有待提高，未來將研究利用深度學習技術(shù)提高系統(tǒng)的穩(wěn)定性與魯棒性。