基于Spark的海量圖像檢索系統設計

王迅，馮瑞

0 引言

基于內容的圖像檢索是指根據查詢圖像的視覺特征，在圖像庫中找出與之相似的圖像。隨著計算機科學技術和數字圖像采集技術的迅速發展以及互聯網的普及應用，每天從各行各業都產生出大量的多媒體數據，這些數據大部分是以圖片和視頻等形式表現的，傳統基于單節點架構的圖像檢索系統存在檢索速度慢、并發性差,實時性和穩定性無法保障等問題，已經不能滿足人們對于檢索性能的要求。因此分布式地圖像處理、快速及時地圖像檢索方法成為了研究熱門。

本文提出了一種基于 Spark[1]的圖像檢索方法，能夠處理海量圖像上的圖像檢索問題。該系統主要由離線特征提取，視覺詞袋模型[2]訓練，在線圖像檢索3部分構成。原始圖像集和提取的SIFT[3]特征都存儲在Hadoop文件系統HDFS[4]上。集群能夠隨圖像數據的增大，動態地增加集群節點數。

1 基于BoVW的圖像檢索

視覺詞袋模型（Bag-of-Visual-word，BoVW）是將文本檢索中的Bag-of-words模型應用于圖像檢索。和文本檢索相似，為了表示一幅圖像，我們可以將圖像看作是若干個“視覺單詞”組成的文檔，視覺單詞相互之間沒有順序。基于視覺詞袋模型的圖像檢索方法由Sivic和Zisserman等人于03年首次提出。BoVW是一種無監督學習，可以高效的對未經過標注的的圖像數據集建立索引。基于視覺詞袋模型的圖像檢索方法主要有如下步驟構成：

（1）特征提取

將圖像集中的圖像進行特征提取，基于 BoVW 的圖像檢索一般使用圖像的SIFT特征。

（2）視覺詞袋模型訓練

利用聚類算法對提取的特征進行訓練獲得視覺詞袋模型。

（3）構建視覺詞頻向量

對于圖像的每一個特征，通過最近鄰的方法在視覺詞典中找到對應的視覺單詞。記錄每個視覺單詞出現的次數,這樣一張圖像就可以用視覺單詞的視覺詞頻向量（Term Vector）表示。

（4）相似圖像檢索

根據視覺詞袋模型，計算出圖像庫中每張圖像的視覺詞頻向量。輸入查詢圖像，提取圖像特征，根據訓練出的視覺詞袋模型計算出查詢圖像的視覺詞頻向量，然后和圖像庫中每張圖像對應的視覺詞頻向量計算相似度，相似度靠前的圖像即為相似圖像。

1.1 特征提取

本文采用SIFT特征作為圖像的基本特征。SIFT特征提取方法是一種提取圖像局部特征的算法，在尺度空間尋找極值點，提取位置，尺度，旋轉不變量。由于SIFT特征具有尺度和旋轉不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩定性。因此，SIFT是基于視覺詞袋模型的圖像檢索方法中中最常用的特征。SIFT征提取算法主要步驟如下：

（1）檢測關鍵點

首先，構建圖像的尺度空間，然后，通過關鍵點檢測算法檢測圖像的關鍵點，并分配關鍵點的方向。得到關鍵點信息：位置、尺度、方向，如圖1所示：

圖1

圖1提取的關鍵點信息如圖2所示：

圖2

圖中圓心表示關鍵點的坐標位置，半徑表示尺度，角度表示方向。

（2）提取描述子

根據關鍵點及關鍵點周圍的像素點梯度信息提取圖像的SIFT描述子，通常描述子大小為128維，關鍵點的個數由圖像大小和圖像梯度分布所決定。

從圖1中提取的SIFT特征如下所示，關鍵點個數：2367，SIFT描述子維度：128

傳統的特征提取是在單機下運行的，無法快速處理海量圖像數據的情況。在單臺機器無法存儲海量圖像時，需要將圖像分批地存放在多臺機器上，在進行特征提取時需要在每一臺機器上運行特征提取算法，效率低下。這時需要將圖像數據集存儲在分布式文件系統中，如 Andrew系統，KASS系統，HDFS等。由于HDFS的易用開源，且Spark能很好地兼容HDFS的讀取，本文采用Spark來進行圖像特征提取，將提取好的特征以二進制形式保存在HDSF中。

1.2 視覺詞袋模型

和文本檢索中的分詞一樣，在多張圖像之間雖然存在差異，但是在這些差異中存在相同的地方。如在人臉檢測中，雖然不同的人臉在視覺上有差別，但眼睛，嘴，鼻子等一些比較細小的部位卻是相似的，從而可以將眼睛，嘴，鼻子等這些部位作為人臉的基本特征，從而用來檢測人臉。同樣，如果我們把同一類圖像之間共同的特征提取出來，就可以作為識別這一類目標的視覺單詞，從而可以區分相似圖像。這是視覺詞袋模型用于圖像檢索的基本思想。

對于提取的SIFT特征，可以利用K-Means聚類算法構建視覺詞典。將圖像集提取的所有特征進行聚成 K類，每一個類中心代表一個視覺單詞，這樣就建立了一個視覺詞典。K-Means聚類算法是一種無監督的學習算法，可以用于訓練未標注的圖像數據集。K-Means是一種基于樣本間相似性度量的間接聚類方法，算法以K為參數， 把N個對象分為K個簇，目的是使簇內具有較高的相似度，而簇間具有較低的相似度。利用 K-Means算法合并詞義相近的視覺單詞，過程如圖3所示：

圖3 K-Means 過程

K-Means將SIFT特征聚成K類后，每一個類的中心點向量為一個視覺單詞，這些視覺單詞被看作是組成任意一幅圖像的基本單位，K個視覺單詞構成一個視覺詞典。可視化后的視覺詞典如圖4所示：

圖4 視覺詞典可視化

有了視覺詞典后，可以用視覺詞典中的單詞表示一張圖像。對于圖像中提取的每一個SIFT特征，都可以通過最近鄰的方法在視覺詞典中找到與之最相似的單詞，即該特征與該視覺單詞所表示的特征最相近，我們可以認為該視覺單詞在圖像中出現了一次，對于一張圖像的所有SIFT特征，通過統計視覺詞典中每個單詞在圖像中出現的次數，就可以將圖像量化為成為一個 K維的視覺單詞直方圖，即視覺詞頻向量，如圖5所示：

圖5 詞頻直方圖

右上角為一張需要量化的圖像，詞頻直方圖的高度代表視覺單詞出現在該圖像中的次數。

對于一個圖像數據集，視覺詞袋模型的建立的主要流程如圖6所示：

圖6 視覺詞袋模型建立

1.3 索引與檢索

根據視覺詞袋模型，計算出圖像庫中每張圖像的視覺詞頻向量。輸入查詢圖像，提取圖像特征，根據訓練出的視覺詞袋模型計算出查詢圖像的視覺詞頻向量，然后和圖像庫中每張圖像對應的詞頻向量計算相似度，相似度靠前的圖像即為相似圖像，如圖7所示：

圖7 相似圖像檢索

圖像之間的相似度可以用圖像詞頻向量之間的歐式距離度量。對于海量數據集，并且詞頻向量非常稀疏的情況，可以建立視覺單詞-圖像倒排索引機制以加快檢索的速度。

2 Spark大數據計算平臺

傳統圖像檢索系統是在單機上運行的，在海量圖像情況下，無法有效地訓練視覺詞袋模型。本文將Spark計算框架與圖像檢索技術相結合，該方法在處理大數據圖像檢索時,具有速度快，可擴展性強等優點，能有效對海量圖像進行視覺詞袋模型訓練。

Spark誕生于伯克利大學AMPLab，是現今大數據領域里最為活躍，最為熱門，最為高效的大數據通用計算平臺。隨著大數據時代的到來，用戶對于大數據處理系統的要求也越來越高。而Spark大數據處理框架因為其出色的性能，越來越受到人們的關注。Spark是基于MapReduce思想實現的一個分布式計算框架，Spark繼承了Hadoop的MapReduce的優點，但是比Hadoop更為高效。Spark開創性地提出了抽象彈性數據集RDD的概念，使得Spark在處理迭代式，交互式，流式數據時非常高效。

大數據計算中計算過程通常分為多個階段，在MapReduce中，不同計算階段之間重用數據，需要將上一個階段的輸出數據保存到外部存儲系統中，例如分布式文件系統，這就導致了大量的數據復制、磁盤I/O、序列化，反序列化等開銷，這些甚至會占據整個應用執行的大部分時間。而Spark基于內存的計算框架在內存大小足夠的情況下，不同計算階段之間只需要讀寫內存即可，無需讀寫磁盤，在磁盤空間不足情況下，也可以像Hadoop一樣使用磁盤作為中間結果存儲的媒介。對于迭代式的算法，Spark相比Hadoop能提高100倍的速度。

Spark 計算框架使包括 SparkSq、SparkStreaming、MLLib、GraphX子框架，子框架和Spark庫之間可以無縫地共享數據和操作，解決了大數據中的 Batch Processing、Streaming Processing、Ad-hoc Query三大核心問題。Spark使用Scala語言編寫，運行在JVM上，能夠很好地兼容其他基于Java語言的大數據系統，如本文中使用的Hadoop文件系統HDFS。Spark提供的API相比Hadoop更加豐富，Spark程序的編寫也更加簡單易用，Spark集群的配置相比Hadoop更加簡單，這使得Spark成為了大數據處理首選的計算平臺，也是本文將Spark應用在海量圖像檢索系統中的原因。

Spark計算框架如圖8所示：

圖8 Spark計算框架

3 實驗結果及分析

本文提出的計算平臺在實驗集群上實現。實驗集群由1臺主節點，4臺從節點組成，均為物理機，操作系統皆使用CentOS6.5。集群使用的Hadoop 版本Hadoop-2.4，Spark 版本為Spark1.3.1。

主節點在Hadoop中充當NameNode，在Spark中充當Master。

從節點在 Hadoop中充當 DataNode，在 Spark中充當Worker，如表1所示：

表1 集群配置

本文使用 K-Means聚類算法訓練視覺詞袋模型。由于K-Means是一種迭代式的計算，用Hadoop的MapReduce框架計算，每次需要將中間的Map結果寫到HDFS，然后再從HDFS讀取數據，進行下一次 Map。但不同于 MapReduce的是Job中間輸出和結果可以保存在內存中，從而不再需要讀寫HDFS，從而大大減少了模型的訓練時間。

本文在holiday[5]數據集上實驗，提取后的SIFT特征集大小為5M，在視覺詞典大小分別為100、200、300的情況下，通過改變集群 worker節點數，視覺詞袋模型訓練的時間測試結果如圖9所示：

圖9 視覺詞袋模型訓練的時間測試結果

通過實驗表明，單機情況無法有效訓練視覺詞袋模型在holiday數據集上訓練大小為300的視覺詞袋模型需要21小時。而在 4個 worker節點上訓練視覺詞典模型只需要 5.2小時，大大減少了模型訓練時間，單位為小時，如表2所示：

表2

表 2給出了不同詞典大小和不同節點個數下視覺詞袋模型的具體時間，與圖9對應。

加速比是指同一個任務在單機系統和分布式系統中運行消耗的時間的比率，用來衡量分布式系統或的性能和效果，加速比的計算公式為Sp=T1/Tp，Sp是加速比，T1是單節點下算法的運行時間，Tp是在p個節點下的運行時間。當Sp=p時，是理想加速比。

表2中的測試數據對應的加速比，如圖10所示：

圖10 加速比

從圖10中可以看出，Spark集群在做視覺詞袋模型訓練時，因為算法的運行時間遠大于網絡傳輸和磁盤IO時間，加速比是隨著節點個數的增加而近似線性增長的，這證明算法的性能能夠隨著節點數的增加而成線性提升，具有良好的可擴展性。通過Spark集群可以高效地訓練海量的圖像數據，并且可以動態的增加集群節點，以適應圖像數據集的增加，具可擴展性，高效性的特點。理論上可以處理任意大小的數據集。

訓練好視覺詞袋模型后，在holiday數據集上0.1秒內即可查詢到相似圖像。查詢結果如圖11所示：

圖11 查詢結果

4 總結

本論文提出了一種基于Spark的海量圖像檢索系統，使用 HDFS作為圖像和特征的存儲系統，用Spark計算框架進行分布式計算。實驗表明本系統與傳統單節點圖像檢索系統相比，具有快速，高效，可擴展性強等優點，適合在大規模圖像數據集上使用。

[1] Zaharia. M, Chowdhury.M, Franklin.M. J, Shenker.S,and I. Stoica, Spark: cluster computing with working sets.the 2nd USENIX conference on Hot topics in cloud computing, 2010:10[C].

[2] Sivic J,Zisserman A.Video Google: A Text Retrieval Approach to Object Matching in Videos[C]. Nice, France:ICCV, 2003

[3] DAVIDG.LOWE.Distinctive Image Features from Scale-Invariant Keypoints[J]. International Journal of Computer Vision 2004, 60(2): 91-110.

[4] Borthakur.D, “The hadoop distributed file system:Architecture and design,”[C] Hadoop Project Website,2007,11:21.

[5] Herve Jegou, Matthijs Douze and Cordelia Schmid.Hamming Embedding and Weak geometry consistency for large scale image search[C]. Marseille, France:ECCV,2008.