應用MapReduce與視覺描述符的圖像檢索算法

盛昀瑤，張福泉，任 艷

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

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

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

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

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

1 基于內容的圖像檢索技術

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

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

2 算法設計

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

圖1 一個標準的CBIR系統

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

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

圖2 本算法的線下層算法

2.1 線上層

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

2.1.1 圖像庫預處理模塊

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

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

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

(1)

式中：L(x,y,σ)為定義尺度空間的函數；“*”為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為一個常量系數。

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

m(x,y)=

(4)

(5)

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

2.1.2 圖像表示模塊

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

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

(6)

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

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

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

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

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

2.1.3 Hadoop輸入文件預處理模塊

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

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

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

2.2 線下層

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

圖4 本算法的線上層算法

2.2.1 查詢圖像的預處理模塊

與圖像庫的預處理方式相同。

2.2.2 Mapper-reducer模塊

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

首先，生成足夠數量的mapper函數，每個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個任務是重組key-value記錄，將value聚集到一起。因此，Reducer將查詢圖像與圖像庫中所有圖像的相似性聚集到一起，生成每個查詢圖像與整個圖像庫的相似性平均值。最終，將計算的相似性排序處理，并且將圖像庫中最相似的若干圖像作為查詢結果，返回給用戶。

3 仿真實驗與分析

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

3.1 實驗環境與參數設置

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

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

圖5 圖像檢索實驗的benchmark數據集實例

3.2 性能度量指標

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

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

Precision(i,j)=nij/nj

(7)

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

平均精度：

*Ij

(8)

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

3.3 實驗結果與數據分析

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

3.3.1 大規模數據集的檢索準確率性能

圖6所示是5個算法對于benchmark數據集的檢索精度結果，從圖中可看出：當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所示是本算法對于不同數量圖像集合的檢索時間效率，可以看出：本算法的計算時間隨著圖像數量呈對數增長的趨勢。雖然圖像庫中Holiday數據集的圖像分辨率較高，但本算法對于圖像庫的規模仍然表現出較好的可擴展性。

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

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

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

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

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

4 結束語

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

由于本算法是基于內容的圖像檢索算法，所以本算法的穩定性、魯棒性均有待提高，未來將研究利用深度學習技術提高系統的穩定性與魯棒性。