王迅，馮瑞

0 引言

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

本文提出了一種基于 Spark[1]的圖像檢索方法，能夠處理海量圖像上的圖像檢索問題。該系統(tǒng)主要由離線特征提取，視覺詞袋模型[2]訓(xùn)練，在線圖像檢索3部分構(gòu)成。原始圖像集和提取的SIFT[3]特征都存儲(chǔ)在Hadoop文件系統(tǒng)HDFS[4]上。集群能夠隨圖像數(shù)據(jù)的增大，動(dòng)態(tài)地增加集群節(jié)點(diǎn)數(shù)。

1 基于BoVW的圖像檢索

視覺詞袋模型（Bag-of-Visual-word，BoVW）是將文本檢索中的Bag-of-words模型應(yīng)用于圖像檢索。和文本檢索相似，為了表示一幅圖像，我們可以將圖像看作是若干個(gè)“視覺單詞”組成的文檔，視覺單詞相互之間沒有順序?；谝曈X詞袋模型的圖像檢索方法由Sivic和Zisserman等人于03年首次提出。BoVW是一種無監(jiān)督學(xué)習(xí)，可以高效的對(duì)未經(jīng)過標(biāo)注的的圖像數(shù)據(jù)集建立索引?；谝曈X詞袋模型的圖像檢索方法主要有如下步驟構(gòu)成：

（1）特征提取

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

（2）視覺詞袋模型訓(xùn)練

利用聚類算法對(duì)提取的特征進(jìn)行訓(xùn)練獲得視覺詞袋模型。

（3）構(gòu)建視覺詞頻向量

對(duì)于圖像的每一個(gè)特征，通過最近鄰的方法在視覺詞典中找到對(duì)應(yīng)的視覺單詞。記錄每個(gè)視覺單詞出現(xiàn)的次數(shù),這樣一張圖像就可以用視覺單詞的視覺詞頻向量（Term Vector）表示。

（4）相似圖像檢索

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

1.1 特征提取

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

（1）檢測(cè)關(guān)鍵點(diǎn)

首先，構(gòu)建圖像的尺度空間，然后，通過關(guān)鍵點(diǎn)檢測(cè)算法檢測(cè)圖像的關(guān)鍵點(diǎn)，并分配關(guān)鍵點(diǎn)的方向。得到關(guān)鍵點(diǎn)信息：位置、尺度、方向，如圖1所示：

圖1

圖1提取的關(guān)鍵點(diǎn)信息如圖2所示：

圖2

圖中圓心表示關(guān)鍵點(diǎn)的坐標(biāo)位置，半徑表示尺度，角度表示方向。

（2）提取描述子

根據(jù)關(guān)鍵點(diǎn)及關(guān)鍵點(diǎn)周圍的像素點(diǎn)梯度信息提取圖像的SIFT描述子，通常描述子大小為128維，關(guān)鍵點(diǎn)的個(gè)數(shù)由圖像大小和圖像梯度分布所決定。

從圖1中提取的SIFT特征如下所示，關(guān)鍵點(diǎn)個(gè)數(shù)：2367，SIFT描述子維度：128

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

1.2 視覺詞袋模型

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

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

圖3 K-Means 過程

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

圖4 視覺詞典可視化

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

圖5 詞頻直方圖

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

對(duì)于一個(gè)圖像數(shù)據(jù)集，視覺詞袋模型的建立的主要流程如圖6所示：

圖6 視覺詞袋模型建立

1.3 索引與檢索

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

圖7 相似圖像檢索

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

2 Spark大數(shù)據(jù)計(jì)算平臺(tái)

傳統(tǒng)圖像檢索系統(tǒng)是在單機(jī)上運(yùn)行的，在海量圖像情況下，無法有效地訓(xùn)練視覺詞袋模型。本文將Spark計(jì)算框架與圖像檢索技術(shù)相結(jié)合，該方法在處理大數(shù)據(jù)圖像檢索時(shí),具有速度快，可擴(kuò)展性強(qiáng)等優(yōu)點(diǎn)，能有效對(duì)海量圖像進(jìn)行視覺詞袋模型訓(xùn)練。

Spark誕生于伯克利大學(xué)AMPLab，是現(xiàn)今大數(shù)據(jù)領(lǐng)域里最為活躍，最為熱門，最為高效的大數(shù)據(jù)通用計(jì)算平臺(tái)。隨著大數(shù)據(jù)時(shí)代的到來，用戶對(duì)于大數(shù)據(jù)處理系統(tǒng)的要求也越來越高。而Spark大數(shù)據(jù)處理框架因?yàn)槠涑錾男阅?，越來越受到人們的關(guān)注。Spark是基于MapReduce思想實(shí)現(xiàn)的一個(gè)分布式計(jì)算框架，Spark繼承了Hadoop的MapReduce的優(yōu)點(diǎn)，但是比Hadoop更為高效。Spark開創(chuàng)性地提出了抽象彈性數(shù)據(jù)集RDD的概念，使得Spark在處理迭代式，交互式，流式數(shù)據(jù)時(shí)非常高效。

大數(shù)據(jù)計(jì)算中計(jì)算過程通常分為多個(gè)階段，在MapReduce中，不同計(jì)算階段之間重用數(shù)據(jù)，需要將上一個(gè)階段的輸出數(shù)據(jù)保存到外部存儲(chǔ)系統(tǒng)中，例如分布式文件系統(tǒng)，這就導(dǎo)致了大量的數(shù)據(jù)復(fù)制、磁盤I/O、序列化，反序列化等開銷，這些甚至?xí)紦?jù)整個(gè)應(yīng)用執(zhí)行的大部分時(shí)間。而Spark基于內(nèi)存的計(jì)算框架在內(nèi)存大小足夠的情況下，不同計(jì)算階段之間只需要讀寫內(nèi)存即可，無需讀寫磁盤，在磁盤空間不足情況下，也可以像Hadoop一樣使用磁盤作為中間結(jié)果存儲(chǔ)的媒介。對(duì)于迭代式的算法，Spark相比Hadoop能提高100倍的速度。

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

Spark計(jì)算框架如圖8所示：

圖8 Spark計(jì)算框架

3 實(shí)驗(yàn)結(jié)果及分析

本文提出的計(jì)算平臺(tái)在實(shí)驗(yàn)集群上實(shí)現(xiàn)。實(shí)驗(yàn)集群由1臺(tái)主節(jié)點(diǎn)，4臺(tái)從節(jié)點(diǎn)組成，均為物理機(jī)，操作系統(tǒng)皆使用CentOS6.5。集群使用的Hadoop 版本Hadoop-2.4，Spark 版本為Spark1.3.1。

主節(jié)點(diǎn)在Hadoop中充當(dāng)NameNode，在Spark中充當(dāng)Master。

從節(jié)點(diǎn)在 Hadoop中充當(dāng) DataNode，在 Spark中充當(dāng)Worker，如表1所示：

表1 集群配置

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

本文在holiday[5]數(shù)據(jù)集上實(shí)驗(yàn)，提取后的SIFT特征集大小為5M，在視覺詞典大小分別為100、200、300的情況下，通過改變集群 worker節(jié)點(diǎn)數(shù)，視覺詞袋模型訓(xùn)練的時(shí)間測(cè)試結(jié)果如圖9所示：

圖9 視覺詞袋模型訓(xùn)練的時(shí)間測(cè)試結(jié)果

通過實(shí)驗(yàn)表明，單機(jī)情況無法有效訓(xùn)練視覺詞袋模型在holiday數(shù)據(jù)集上訓(xùn)練大小為300的視覺詞袋模型需要21小時(shí)。而在 4個(gè) worker節(jié)點(diǎn)上訓(xùn)練視覺詞典模型只需要 5.2小時(shí)，大大減少了模型訓(xùn)練時(shí)間，單位為小時(shí)，如表2所示：

表2

表 2給出了不同詞典大小和不同節(jié)點(diǎn)個(gè)數(shù)下視覺詞袋模型的具體時(shí)間，與圖9對(duì)應(yīng)。

加速比是指同一個(gè)任務(wù)在單機(jī)系統(tǒng)和分布式系統(tǒng)中運(yùn)行消耗的時(shí)間的比率，用來衡量分布式系統(tǒng)或的性能和效果，加速比的計(jì)算公式為Sp=T1/Tp，Sp是加速比，T1是單節(jié)點(diǎn)下算法的運(yùn)行時(shí)間，Tp是在p個(gè)節(jié)點(diǎn)下的運(yùn)行時(shí)間。當(dāng)Sp=p時(shí)，是理想加速比。

表2中的測(cè)試數(shù)據(jù)對(duì)應(yīng)的加速比，如圖10所示：

圖10 加速比

從圖10中可以看出，Spark集群在做視覺詞袋模型訓(xùn)練時(shí)，因?yàn)樗惴ǖ倪\(yùn)行時(shí)間遠(yuǎn)大于網(wǎng)絡(luò)傳輸和磁盤IO時(shí)間，加速比是隨著節(jié)點(diǎn)個(gè)數(shù)的增加而近似線性增長的，這證明算法的性能能夠隨著節(jié)點(diǎn)數(shù)的增加而成線性提升，具有良好的可擴(kuò)展性。通過Spark集群可以高效地訓(xùn)練海量的圖像數(shù)據(jù)，并且可以動(dòng)態(tài)的增加集群節(jié)點(diǎn)，以適應(yīng)圖像數(shù)據(jù)集的增加，具可擴(kuò)展性，高效性的特點(diǎn)。理論上可以處理任意大小的數(shù)據(jù)集。

訓(xùn)練好視覺詞袋模型后，在holiday數(shù)據(jù)集上0.1秒內(nèi)即可查詢到相似圖像。查詢結(jié)果如圖11所示：

圖11 查詢結(jié)果

4 總結(jié)

本論文提出了一種基于Spark的海量圖像檢索系統(tǒng)，使用 HDFS作為圖像和特征的存儲(chǔ)系統(tǒng)，用Spark計(jì)算框架進(jìn)行分布式計(jì)算。實(shí)驗(yàn)表明本系統(tǒng)與傳統(tǒng)單節(jié)點(diǎn)圖像檢索系統(tǒng)相比，具有快速，高效，可擴(kuò)展性強(qiáng)等優(yōu)點(diǎn)，適合在大規(guī)模圖像數(shù)據(jù)集上使用。

[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.