崔紅艷　曹建芳

(忻州師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系　山西 忻州 034000)

?

基于改進(jìn)的分布式K-Means特征聚類的海量場(chǎng)景圖像檢索

崔紅艷曹建芳*

(忻州師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系山西 忻州 034000)

摘要針對(duì)傳統(tǒng)的圖像檢索方法在處理海量數(shù)據(jù)時(shí)面臨的問(wèn)題，提出一種基于改進(jìn)的分布式K-Means特征聚類的海量場(chǎng)景圖像檢索方法。對(duì)分布式K-Means算法進(jìn)行改進(jìn)，優(yōu)化了初始聚類中心的選擇和迭代過(guò)程，并將其應(yīng)用與場(chǎng)景圖像的特征聚類中；充分利用Hadoop分布式平臺(tái)的海量存儲(chǔ)能力和強(qiáng)大并行計(jì)算能力， 提出了海量場(chǎng)景圖像的存儲(chǔ)和檢索方案，設(shè)計(jì)了場(chǎng)景圖像特征提取、特征聚類以及圖像檢索三個(gè)階段分布式并行處理的Map和Reduce任務(wù)。多組實(shí)驗(yàn)表明，提出的方法數(shù)據(jù)伸縮率曲線平緩，取得了優(yōu)良的加速比，效率大于0.6，檢索的平均準(zhǔn)確率達(dá)到了88%左右，適合海量場(chǎng)景圖像數(shù)據(jù)的檢索。

關(guān)鍵詞Hadoop分布式平臺(tái)MapReduce分布式K-Means算法特征聚類場(chǎng)景圖像檢索

0引言

多媒體技術(shù)及網(wǎng)絡(luò)技術(shù)的快速發(fā)展，已導(dǎo)致圖像數(shù)據(jù)的迅速增長(zhǎng)，面對(duì)海量的圖像數(shù)據(jù)，如何快速、準(zhǔn)確地檢索到用戶需要的圖像，已成為人們關(guān)注的熱點(diǎn)問(wèn)題。傳統(tǒng)的基于單節(jié)點(diǎn)架構(gòu)的圖像檢索方法，在同時(shí)訪問(wèn)用戶數(shù)量較少時(shí)，基本可以滿足用戶對(duì)訪問(wèn)時(shí)間的要求，但隨著圖像數(shù)量的迅速增長(zhǎng)，圖像特征庫(kù)會(huì)變得很大，在線同時(shí)訪問(wèn)用戶數(shù)量也會(huì)隨之增多，導(dǎo)致圖像的檢索速度會(huì)因此而急速下降；另外，圖像的特征相似度計(jì)算屬于復(fù)雜運(yùn)算，使用傳統(tǒng)的檢索方法會(huì)耗費(fèi)大量的計(jì)算資源，運(yùn)算速度也很慢。這些都會(huì)導(dǎo)致大量用戶同時(shí)檢索時(shí)，系統(tǒng)運(yùn)行效率迅速下降，甚至無(wú)法承受，難以及時(shí)對(duì)用戶作出響應(yīng)[1]。因此，傳統(tǒng)的圖像檢索方法已無(wú)法完成對(duì)海量圖像數(shù)據(jù)的處理，難以滿足人們對(duì)圖像檢索性能的要求。對(duì)海量圖像的檢索面臨巨大的挑戰(zhàn)，探索新的圖像檢索方法已成為數(shù)字圖像理解領(lǐng)域的研究熱點(diǎn)。

云計(jì)算技術(shù)的發(fā)展為海量圖像數(shù)據(jù)的處理提供了新的思路，云計(jì)算技術(shù)的發(fā)展過(guò)程一直與大規(guī)模數(shù)據(jù)的處理關(guān)系密切，因此利用云計(jì)算平臺(tái)進(jìn)行分布式并行處理是實(shí)現(xiàn)海量圖像高效檢索的一種有效解決方案。Hadoop是一個(gè)能夠?qū)Υ笠?guī)模數(shù)據(jù)進(jìn)行分布式并行處理的軟件框架，自問(wèn)世以來(lái)因其優(yōu)秀的大規(guī)模數(shù)據(jù)處理能力、良好的可擴(kuò)展性、高可靠性以及低成本等優(yōu)點(diǎn)得到了廣泛的應(yīng)用[2]。本文以最常見(jiàn)的場(chǎng)景圖像為例，在分析傳統(tǒng)的圖像檢索方法的基礎(chǔ)上，研究了Hadoop平臺(tái)中的MapReduce并行編程框架，提出了基于MapReduce的海量場(chǎng)景圖像檢索方案和改進(jìn)的分布式K-Means特征聚類算法，設(shè)計(jì)了場(chǎng)景圖像并行特征聚類的Map任務(wù)和Reduce任務(wù)，實(shí)現(xiàn)了海量場(chǎng)景圖像的高效檢索。為驗(yàn)證本文提出的檢索方法的性能，實(shí)驗(yàn)從檢索準(zhǔn)確率、數(shù)據(jù)伸縮率、加速比與效率等多個(gè)方面驗(yàn)證了檢索方案的強(qiáng)大并行計(jì)算能力。

1相關(guān)工作

近年來(lái)，研究者們對(duì)分布式K-Means聚類算法進(jìn)行了一些研究，目前研究應(yīng)用較多的平臺(tái)是Hadoop分布式平臺(tái)，它利用MapReduce并行編程計(jì)算模型實(shí)現(xiàn)大規(guī)模數(shù)據(jù)的存儲(chǔ)和計(jì)算。對(duì)分布式K-Means聚類算法的改進(jìn)大多是借鑒于傳統(tǒng)的非分布式K-Means算法，而對(duì)于傳統(tǒng)的K-Means算法的改進(jìn)主要集中在初始聚類中心的確定和距離函數(shù)的確定兩個(gè)方面。NehaA等人[3]利用所有的數(shù)據(jù)對(duì)象到特定中心的計(jì)算，選取中間的數(shù)據(jù)對(duì)象作為數(shù)據(jù)中心，避免了隨機(jī)選取初始聚類中心的不確定性，減少了循環(huán)迭代的次數(shù)。張軍偉等人[4]和韓最蛟[5]根據(jù)聚類數(shù)據(jù)間的距離和密度，選擇距離較大或密度較小的數(shù)據(jù)作為聚類中心。出了對(duì)K-Means算法的聚類過(guò)程做一些改進(jìn)之外，針對(duì)Hadoop分布式平臺(tái)，趙衛(wèi)中[6]等人提出了一種基于云平臺(tái)的并行K-Means聚類算法，利用MapReduce并行編程模型的Combine函數(shù)進(jìn)行本地的合并，加快了算法的迭代速度。金偉健[7]等人通過(guò)在計(jì)算模型中增加通信模塊，減少重復(fù)的通信流量，從而提高了數(shù)據(jù)的傳輸速率。盡管這些算法都可以對(duì)大規(guī)模數(shù)據(jù)進(jìn)行處理，但其聚類的質(zhì)量并不是很高，也沒(méi)有很好地考慮算法執(zhí)行過(guò)程中的計(jì)算量的問(wèn)題。

在海量圖像處理方面，WileyK[8]等人通過(guò)將圖像轉(zhuǎn)換成序列化的二進(jìn)制文件，利用Hadoop實(shí)現(xiàn)了對(duì)天文圖像的分析處理，但因其無(wú)法對(duì)圖像進(jìn)行隨機(jī)讀寫(xiě)，所以應(yīng)用受到了一定的限制。AlmeerMH[1]等人利用Hadoop的HDFS實(shí)現(xiàn)了對(duì)大規(guī)模遙感圖像的分析和存儲(chǔ)。朱義明[9]通過(guò)自定義圖像接口讀寫(xiě)整張圖像，提出了基于Hadoop平臺(tái)的圖像分類方法， 但該方法未考慮小文件低效率的問(wèn)題，從而導(dǎo)致一定的資源浪費(fèi)，因此僅適合對(duì)遙感圖像的處理。SweeneyC[10]提出了一種新的方法，通過(guò)將圖像數(shù)據(jù)信息轉(zhuǎn)化為Float數(shù)組的方式將其存儲(chǔ)在一個(gè)文件中，并附有索引文件，從而有效解決了小文件低效率問(wèn)題并支持通過(guò)索引文件隨機(jī)讀取，但這種方法不能存儲(chǔ)圖像的原始完整信息，而且圖像與數(shù)組互相轉(zhuǎn)換的編碼與解碼方法較為復(fù)雜，目前僅支持RGB顏色空間和jpg、png、ppm格式的圖像，應(yīng)用范圍受到一定的限制。

綜上所述，目前幾乎沒(méi)有一種適合大規(guī)模場(chǎng)景圖像的高效的特征聚類和檢索方法。因此，本文在上述研究的基礎(chǔ)上，以傳統(tǒng)的K-Means算法和海量場(chǎng)景圖像為研究對(duì)象，在MapReduce冰箱編程模型框架下，研究場(chǎng)景圖像的特征聚類優(yōu)化方法，分析如何能準(zhǔn)確、快速、高效的從海量場(chǎng)景圖像庫(kù)中檢索到用戶需要的圖像數(shù)據(jù)，實(shí)現(xiàn)“以人為本”的高效場(chǎng)景圖像檢索。

2系統(tǒng)整體架構(gòu)

針對(duì)傳統(tǒng)的單節(jié)點(diǎn)架構(gòu)和場(chǎng)景圖像迅速增長(zhǎng)引發(fā)的瓶頸問(wèn)題，本文提出了Hadoop分布式平臺(tái)下的場(chǎng)景圖像檢索方案，系統(tǒng)整體架構(gòu)如圖1所示。

系統(tǒng)整體架構(gòu)分為三層：

(1) 表現(xiàn)層：用戶通過(guò)Internet獲取服務(wù)，提交示例圖像或接收檢索結(jié)果。

(2) 業(yè)務(wù)邏輯層：Web服務(wù)器根據(jù)用戶的檢索請(qǐng)求執(zhí)行相應(yīng)的業(yè)務(wù)處理。

(3) 數(shù)據(jù)處理層：是整個(gè)系統(tǒng)的核心部分，主要進(jìn)行海量場(chǎng)景圖像的存儲(chǔ)和管理，負(fù)責(zé)場(chǎng)景圖像的特征提取、匹配、輸出結(jié)果等。用戶將檢索示例圖像或檢索關(guān)鍵字通過(guò)Internet提交給Hadoop分布式系統(tǒng)，經(jīng)過(guò)MapReduce計(jì)算模型進(jìn)行特征提取(如果是示例圖像)，然后進(jìn)行特征匹配：如果是示例圖像檢索，就將示例圖像特征與HDFS中存儲(chǔ)的場(chǎng)景圖像特征庫(kù)匹配；如果是關(guān)鍵字檢索，就將檢索關(guān)鍵字與場(chǎng)景圖像庫(kù)的標(biāo)注信息匹配；最后輸出檢索結(jié)果。

圖1　海量場(chǎng)景圖像檢索系統(tǒng)架構(gòu)

2.1MapReduce并行編程模型

MapReduce是Hadoop分布式處理的核心技術(shù)之一，它為大數(shù)據(jù)的處理提供了一種面向底層的分布式并行處理計(jì)算模式，為開(kāi)發(fā)者提供了一套完整的編程接口和執(zhí)行環(huán)境。MapReduce采用標(biāo)準(zhǔn)的函數(shù)式編程計(jì)算模式，核心是可以將被稱為高次函數(shù)的函數(shù)作為參數(shù)進(jìn)行傳遞，通過(guò)多個(gè)高次函數(shù)的串接，將數(shù)據(jù)的計(jì)算過(guò)程轉(zhuǎn)換成為函數(shù)的執(zhí)行過(guò)程。

MapReduce將數(shù)據(jù)的計(jì)算過(guò)程分為Map和Reduce兩個(gè)階段，分別對(duì)應(yīng)兩個(gè)函數(shù)：mapper和reducer。在Map階段，原始數(shù)據(jù)經(jīng)分段處理后作為輸入給mapper，經(jīng)過(guò)過(guò)濾和轉(zhuǎn)換，將產(chǎn)生的中間結(jié)果作為Reduce階段reducer的輸入，最后經(jīng)過(guò)聚合處理得到最終結(jié)果。

Map階段，MapReduce將用戶的輸入數(shù)據(jù)分割為固定大小的片段(Split)，然后將每個(gè)Split分解成一批鍵值對(duì)；Hadoop為每個(gè)Split建立一個(gè)Map任務(wù)，將每個(gè)Split對(duì)應(yīng)的鍵值作為輸入，對(duì)執(zhí)行用戶自定義的mapper函數(shù)，產(chǎn)生中間結(jié)果；接著將中間結(jié)果按照k2的值排序，將key值相同的value放在一起形成一個(gè)新的列表；最后再根據(jù)key值的范圍對(duì)這些元組進(jìn)行分組，對(duì)應(yīng)形成不同的Reduce任務(wù)。

Reduce階段，Reduce把從不同的mapper函數(shù)接收過(guò)來(lái)的數(shù)據(jù)整合排序，然后調(diào)用對(duì)應(yīng)的reducer函數(shù)，將作為輸入，并做相應(yīng)的處理，獲得鍵值對(duì)輸出到HDFS上。

其過(guò)程表示為：

Map：(k1,v1)→list(k2,v2)

Reduce：(k2,list(v2))→list(k3,v3)

2.2HDFS體系結(jié)構(gòu)設(shè)計(jì)

HDFS也是Hadoop的核心子項(xiàng)目之一，采用主從(Master/Slave)模式體系結(jié)構(gòu)，將大規(guī)模的數(shù)據(jù)存儲(chǔ)在多臺(tái)相關(guān)聯(lián)的計(jì)算機(jī)上，既可增加存儲(chǔ)容量，又能實(shí)現(xiàn)自動(dòng)容錯(cuò)，能夠自動(dòng)檢測(cè)和快速恢復(fù)硬件故障，在超大規(guī)模數(shù)據(jù)集上方便的進(jìn)行流式數(shù)據(jù)訪問(wèn)。

當(dāng)圖像數(shù)據(jù)規(guī)模很大時(shí)，如果將其全部存儲(chǔ)在HDFS中，那么讀取圖像會(huì)產(chǎn)生很大的時(shí)間開(kāi)銷，HBase是一個(gè)在HDFS之上的面向列的分布式數(shù)據(jù)庫(kù)，可以進(jìn)行實(shí)時(shí)讀寫(xiě)，因此本文將場(chǎng)景圖像的存儲(chǔ)路徑和特征存儲(chǔ)于HBase分布式數(shù)據(jù)庫(kù)中。結(jié)構(gòu)如表1所示。

表1　海量場(chǎng)景圖像的存儲(chǔ)表設(shè)計(jì)

將場(chǎng)景圖像的ID作為HBase表的主鍵，取圖像和提取的圖像特征、標(biāo)注信息作為HBase表的兩個(gè)列族。由于HBase對(duì)表執(zhí)行的是按行原子操作，因此將一張場(chǎng)景圖像的所有信息全部放在一行存放，以便于讀寫(xiě)。

3改進(jìn)的分布式K-Means特征聚類算法

3.1場(chǎng)景圖像特征提取

由于SURF算法能在保持尺度、旋轉(zhuǎn)、照明變化等無(wú)關(guān)特性的同時(shí)，使得計(jì)算過(guò)程效率更高，因此，本文采用SURF算法提取場(chǎng)景圖像的特征。過(guò)程如下：

(1) 計(jì)算場(chǎng)景圖像每個(gè)像素點(diǎn)X=(x,y)在尺度σ下的Hessian矩陣：

(1)

該矩陣是由二階導(dǎo)數(shù)構(gòu)成的矩陣，用不同尺度σ下的近似高斯核計(jì)算求得，因此，Hessian值實(shí)際上是一個(gè)包含三個(gè)變量的函數(shù)：H(x,y,σ)。

(2) 計(jì)算在空間域和尺度域上同時(shí)達(dá)到局部極大值時(shí)的相應(yīng)位置和尺度。

對(duì)于每個(gè)特征點(diǎn)，求其在半徑為6σ的圓內(nèi)的Haar小波在x和y方向的響應(yīng)dx和dy，對(duì)覆蓋在60°范圍內(nèi)的響應(yīng)求和，旋轉(zhuǎn)窗口得到最長(zhǎng)向量的方向即為主要方向。

(3) 對(duì)得到的64維特征向量做歸一化處理。

該過(guò)程在Hadoop分布式處理平臺(tái)下的MapReduce計(jì)算過(guò)程如下：

Map任務(wù)：

輸入：

輸出：

mapper函數(shù)對(duì)每張場(chǎng)景圖像利用SURF算法特征向量，并統(tǒng)計(jì)特證數(shù)，便于歸一化處理。

Reduce任務(wù)：

reducer函數(shù)將mapper函數(shù)輸出的每個(gè)鍵值對(duì)作為自己的輸入，并再將其傳遞到輸出部分。

3.2特征聚類

K-Means聚類算法是一個(gè)重復(fù)迭代算法，在分布式環(huán)境下，每次迭代都會(huì)耗費(fèi)大量的時(shí)間和通信量，而且用于圖像的特征聚類時(shí)，圖像的屬性維數(shù)較高，數(shù)量較多，因此傳統(tǒng)的分布式K-Means算法的時(shí)間復(fù)雜度很大。本文改進(jìn)了傳統(tǒng)的分布式K-Means算法，首先使用Canopy算法選擇初始聚類中心，然后在聚類中心點(diǎn)生成的過(guò)程中使用Combine函數(shù)進(jìn)行了本地的合并，這樣既優(yōu)化了初始聚類中心，又優(yōu)化了算法的迭代過(guò)程，大大降低了分布式K-Means算法的時(shí)間復(fù)雜度。

(1) Canopy算法和K-Means算法

Canopy算法[11]的主要思想是將聚類分成兩個(gè)階段：首先，使用一個(gè)簡(jiǎn)單、快捷的距離計(jì)算方法將數(shù)據(jù)分成被稱為“canopy”的可重疊的子集；然后，使用一個(gè)精準(zhǔn)而嚴(yán)密的距離計(jì)算方法計(jì)算出現(xiàn)在第一階段中的屬于同一個(gè)“canopy”的所有數(shù)據(jù)向量的距離。該算法由于只計(jì)算重疊部分的數(shù)據(jù)向量而有效地減少了計(jì)算量。

K-Means算法[11]是一種經(jīng)典的基于距離的聚類算法，它采用距離作為相似性的評(píng)價(jià)指標(biāo)，即兩個(gè)對(duì)象的距離越近，相似性就越大。其基本思想為：首先隨機(jī)選取k個(gè)點(diǎn)作為初始聚類中心，然后計(jì)算各樣本到中心點(diǎn)的距離，將樣本歸類到離其最近的簇中，接著對(duì)調(diào)整后的新類計(jì)算新的簇中心，若相鄰兩次的簇中心沒(méi)有變化，則樣本調(diào)整結(jié)束，聚類準(zhǔn)則函數(shù)E收斂。

(2)

其中，Mi為類Ci中數(shù)據(jù)對(duì)象的均值，p是類Ci中的空間點(diǎn)。

分布式K-Means算法[11]的基本思想是：首先隨機(jī)選擇一個(gè)站點(diǎn)作為主站點(diǎn)，然后主站點(diǎn)利用K-Means算法將其劃分為k個(gè)簇，接著主站點(diǎn)將各個(gè)簇的中心點(diǎn)廣播給其余的k-1個(gè)子站點(diǎn)，最后各子站點(diǎn)計(jì)算本站點(diǎn)的數(shù)據(jù)對(duì)象與中心站點(diǎn)各個(gè)簇中心點(diǎn)的距離，并將每個(gè)樣本點(diǎn)歸入離其最近的中心點(diǎn)，將不屬于自己的樣本對(duì)象傳送給與該樣本對(duì)象所屬的簇類對(duì)應(yīng)的站點(diǎn)。反復(fù)迭代，直到判別函數(shù)E收斂為止。

(2) 改進(jìn)的分布式K-Means特征聚類算法描述

本文將Canopy算法與K-Means算法結(jié)合，利用Canopy算法優(yōu)化K-Means算法的初始聚類中心，其算法描述如下。

算法分為兩大部分：初始聚類中心的優(yōu)化和聚類迭代過(guò)程的優(yōu)化。

利用Canopy算法對(duì)初始聚類中心的優(yōu)化過(guò)程為：

輸入：場(chǎng)景圖像數(shù)據(jù)集List(形如)

輸出：k個(gè)初始聚類中心(形如)

① 數(shù)據(jù)預(yù)處理。將場(chǎng)景圖像數(shù)據(jù)集合List按照?qǐng)D像的image_id排序，并設(shè)置初始距離閾值T1和T2(使用交叉驗(yàn)證獲得)，且T1>T2。

②mapper函數(shù)隨機(jī)選取一個(gè)場(chǎng)景圖像樣本向量作為一個(gè)canopy中心向量，然后遍歷場(chǎng)景圖像數(shù)據(jù)集合List，若場(chǎng)景圖像數(shù)據(jù)與canopy中心向量之間的距離小于T1，則將該圖像數(shù)據(jù)歸入此canopy；若距離小于T2，則將該圖像數(shù)據(jù)從原始數(shù)據(jù)集中去除，直到List為空；最后輸出所有的canopy中心向量。

③reducer函數(shù)處理mapper函數(shù)的輸出，整合Map階段產(chǎn)生的canopy中心向量，生成新的canopy中心向量，即初始聚類中心。

這樣就得到了k個(gè)初始聚類中心。

利用K-Means算法進(jìn)行特征聚類的迭代優(yōu)化過(guò)程為：

輸入：場(chǎng)景圖像數(shù)據(jù)集List(形如)

輸出：k個(gè)聚類中心(形如)

①mapper函數(shù)接收Canopy算法reducer函數(shù)的輸出，計(jì)算各場(chǎng)景圖像數(shù)據(jù)對(duì)象到其所屬的各canopy中最近的簇中心的距離，輸出場(chǎng)景圖像數(shù)據(jù)及所屬的簇，形如。

②combine函數(shù)接收mapper函數(shù)的輸出，在本地進(jìn)行同一簇對(duì)象的合并，即對(duì)各簇中場(chǎng)景圖像數(shù)據(jù)對(duì)象的對(duì)應(yīng)維求和，統(tǒng)計(jì)數(shù)據(jù)對(duì)象的個(gè)數(shù)，得到形如的輸出。

③reducer函數(shù)接收combine函數(shù)的輸出，統(tǒng)計(jì)各簇的所有場(chǎng)景圖像數(shù)據(jù)對(duì)象的對(duì)應(yīng)維之和、場(chǎng)景圖像數(shù)據(jù)對(duì)象的總個(gè)數(shù)，得到新的簇中心值作為穩(wěn)定的K-Means簇中心，形如，并且判斷K-Means算法是否收斂。

④ 根據(jù)產(chǎn)生的穩(wěn)定的簇中心，進(jìn)行聚類劃分：mapper函數(shù)接收待聚類場(chǎng)景圖像數(shù)據(jù)作為輸入，并加載穩(wěn)定的K-Means簇中心，計(jì)算各場(chǎng)景圖像數(shù)據(jù)對(duì)象與k個(gè)簇中心之間的距離，得到該數(shù)據(jù)對(duì)象最終所屬的簇；reducer函數(shù)接收mapper函數(shù)的輸出，進(jìn)行數(shù)據(jù)收集，得到最終的聚類結(jié)果。

對(duì)于場(chǎng)景圖像特征相似度的計(jì)算，本文采用歐幾里得距離公式進(jìn)行計(jì)算。

(3)

4海量場(chǎng)景圖像檢索的實(shí)現(xiàn)

檢索流程如圖2所示。

圖2　海量場(chǎng)景圖像檢索流程

基于改進(jìn)的分布式K-Means特征聚類的海量場(chǎng)景圖像檢索，根據(jù)場(chǎng)景圖像的SURF特征描述圖像，結(jié)合場(chǎng)景圖像的標(biāo)注信息特征，實(shí)現(xiàn)圖像檢索。主要是以下幾個(gè)步驟：

(1) 場(chǎng)景圖像庫(kù)以及標(biāo)注信息存儲(chǔ)于HDFS的HBase分布式數(shù)據(jù)庫(kù)中，用于特征提取、聚類以及獲取檢索結(jié)果。

(2) 對(duì)庫(kù)中的場(chǎng)景圖像使用SURF算法進(jìn)行分布式并行特征提取，并使用本文提出的改進(jìn)的分布式K-Means算法進(jìn)行特征聚類，將聚類后的圖像數(shù)據(jù)及特征信息存儲(chǔ)于HDFS中。

(3) 在圖像檢索階段，Map任務(wù)接收用戶輸入的檢索要求，并讀取圖像特征信息庫(kù)，判斷檢索要求，提取示例圖像特征，計(jì)算待檢索圖像特征與圖像庫(kù)中各聚類中心的相似度，并將計(jì)算的結(jié)果作為中間結(jié)果輸出。

(4)Reduce任務(wù)接收Map任務(wù)的輸出，將相似度按從大到小的順序排序，將相似度最大的聚類中心的場(chǎng)景圖像作為最終檢索結(jié)果輸出。

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

5.1實(shí)驗(yàn)環(huán)境和測(cè)試數(shù)據(jù)

本文實(shí)驗(yàn)環(huán)境搭建的Hadoop集群由局域網(wǎng)內(nèi)5臺(tái)計(jì)算機(jī)構(gòu)成，其中1臺(tái)計(jì)算機(jī)為Master節(jié)點(diǎn)，其余4臺(tái)計(jì)算機(jī)為Slave節(jié)點(diǎn)，各節(jié)點(diǎn)計(jì)算機(jī)采用4G雙核處理器，500GB硬盤(pán)空間的基本配置，操作系統(tǒng)采用Ubuntu。

本文的實(shí)驗(yàn)測(cè)試數(shù)據(jù)來(lái)自Internet上的SUNDatabase場(chǎng)景圖像數(shù)據(jù)庫(kù)，該數(shù)據(jù)庫(kù)目前包含131 067張場(chǎng)景圖像，908個(gè)場(chǎng)景類別。由于實(shí)驗(yàn)條件的限制，我們從中選取20 000張場(chǎng)景圖像作為實(shí)驗(yàn)測(cè)試數(shù)據(jù)集。

5.2系統(tǒng)性能測(cè)試與分析

(1) 存儲(chǔ)性能測(cè)試與分析

在做存儲(chǔ)性能實(shí)驗(yàn)測(cè)試時(shí)，根據(jù)Hadoop集群不同節(jié)點(diǎn)個(gè)數(shù)的情況，我們對(duì)存儲(chǔ)不同的場(chǎng)景圖像集規(guī)模所需消耗的時(shí)間進(jìn)行了實(shí)驗(yàn)對(duì)比，場(chǎng)景圖像集的規(guī)模分別設(shè)置為：500、1000、3000、6000、10 000、15 000、20 000張；在1個(gè)、2個(gè)、3個(gè)和4個(gè)節(jié)點(diǎn)時(shí)分別做了存儲(chǔ)耗時(shí)性能的測(cè)試。實(shí)驗(yàn)結(jié)果如圖3所示。

圖3　海量場(chǎng)景圖像存儲(chǔ)耗時(shí)對(duì)比

可以看出，在場(chǎng)景圖像的規(guī)模小于1000張時(shí)，節(jié)點(diǎn)數(shù)量的增長(zhǎng)對(duì)場(chǎng)景圖像存儲(chǔ)耗時(shí)性能的影響并不明顯，當(dāng)場(chǎng)景圖像的規(guī)模大于1000時(shí)，分布式并行存儲(chǔ)的優(yōu)勢(shì)逐漸明顯。在相同的圖像規(guī)模下，存儲(chǔ)耗時(shí)隨著節(jié)點(diǎn)的數(shù)量增加而下降；隨著圖像規(guī)模的增大，存儲(chǔ)耗時(shí)也在不斷增加，然而，單節(jié)點(diǎn)集群增加最快，而4個(gè)節(jié)點(diǎn)集群的增長(zhǎng)速度最為緩慢，即在圖像規(guī)模不太大時(shí)，不適合采用多節(jié)點(diǎn)集群分布式存儲(chǔ)，而當(dāng)圖像規(guī)模變大時(shí)，采用分布式存儲(chǔ)的效率是很高的。

(2) 檢索性能測(cè)試與分析

為驗(yàn)證檢索的效果，本文從檢索準(zhǔn)確率、加速比與效率、數(shù)據(jù)伸縮率等三個(gè)方面進(jìn)行了實(shí)驗(yàn)對(duì)比。

① 檢索準(zhǔn)確率

本文首先使用傳統(tǒng)的查準(zhǔn)率、召回率以及F1值來(lái)衡量系統(tǒng)的檢索效果。表2是在不同的場(chǎng)景圖像規(guī)模下，結(jié)合人工輔助的統(tǒng)計(jì)，得到的檢索效率。

表2　檢索平均準(zhǔn)確率比較

從表2可以看出，系統(tǒng)檢索的查準(zhǔn)率、召回率和F1值都較高，檢索效果較好；另外，還可以看到，隨著場(chǎng)景圖像規(guī)模的不斷增大，雖然系統(tǒng)的查準(zhǔn)率和召回率在降低，但下降的幅度很小，這充分說(shuō)明，采用分布式并行處理方式非常適合大規(guī)模數(shù)據(jù)的處理。

② 數(shù)據(jù)伸縮率

數(shù)據(jù)伸縮率[2]是衡量設(shè)計(jì)的方案處理不同數(shù)據(jù)規(guī)模的能力的一個(gè)指標(biāo)，是指處理擴(kuò)大后的數(shù)據(jù)集所需的時(shí)間與處理原始數(shù)據(jù)集所需時(shí)間的比值。實(shí)驗(yàn)以節(jié)點(diǎn)數(shù)為4進(jìn)行，從1 000張場(chǎng)景圖像的數(shù)據(jù)規(guī)模起，逐漸將圖像規(guī)模增加到10 000，測(cè)試結(jié)果如圖4所示。

圖4　系統(tǒng)數(shù)據(jù)伸縮率測(cè)試

可以看到，在場(chǎng)景圖像的規(guī)模小于5000時(shí)，數(shù)據(jù)伸縮率曲線較為平緩，這說(shuō)明在圖像數(shù)量較少時(shí)，系統(tǒng)并不能充分發(fā)揮各數(shù)據(jù)節(jié)點(diǎn)的計(jì)算能力，而當(dāng)圖像規(guī)模大于5000時(shí)，數(shù)據(jù)伸縮率的增長(zhǎng)趨勢(shì)較快，曲線上升較為陡峭，這進(jìn)一步的說(shuō)明數(shù)據(jù)規(guī)模愈大，愈能發(fā)揮各數(shù)據(jù)節(jié)點(diǎn)的計(jì)算能力。同時(shí)，可以看出，圖像規(guī)模從5000張擴(kuò)大到10 000張時(shí)大約需要3.8倍的時(shí)間，而從1000張擴(kuò)大到10 000張時(shí)只用了大約5.8倍的時(shí)間，系統(tǒng)取得了較好的數(shù)據(jù)伸縮率。

③ 加速比與效率

加速比[2,13]是指同一任務(wù)在單個(gè)計(jì)算節(jié)點(diǎn)的運(yùn)行時(shí)間與多個(gè)計(jì)算節(jié)點(diǎn)的運(yùn)行時(shí)間之比，效率是加速比與計(jì)算節(jié)點(diǎn)數(shù)量之比，二者是用來(lái)衡量檢索方案整體性能的指標(biāo)。圖5是場(chǎng)景圖像規(guī)模分別為5000、10 000、15 000時(shí)系統(tǒng)加速比與效率的實(shí)驗(yàn)對(duì)比結(jié)果。

圖5　系統(tǒng)性能對(duì)比

在理想狀態(tài)下，系統(tǒng)加速比應(yīng)隨著節(jié)點(diǎn)個(gè)數(shù)增加而線性增長(zhǎng)，效率始終保持不變。但實(shí)際上由于任務(wù)的控制受到通信開(kāi)銷、負(fù)載平衡等因素的影響，加速比不會(huì)線性增長(zhǎng)，系統(tǒng)效率并不會(huì)達(dá)到1。GollerA[12,14]等人認(rèn)為只要效率達(dá)到0.5，即可認(rèn)為系統(tǒng)獲得了很好的性能。從圖5可以看出，通過(guò)對(duì)三組規(guī)模不同的場(chǎng)景圖像的測(cè)試，加速比隨著節(jié)點(diǎn)個(gè)數(shù)的增加而增加，效率都在0.5以上，這充分說(shuō)明系統(tǒng)獲得了很好的性能。另外，隨著場(chǎng)景圖像規(guī)模的增大，節(jié)點(diǎn)個(gè)數(shù)愈多，加速比與效率的性能就愈好，這同時(shí)也說(shuō)明在分布式并行處理情況下，數(shù)據(jù)規(guī)模愈大，愈能充分發(fā)揮各數(shù)據(jù)節(jié)點(diǎn)的計(jì)算能力。

從整體上看，無(wú)論是存儲(chǔ)性能還是檢索性能，本文提出的基于改進(jìn)的分布式K-Means特征聚類的海量場(chǎng)景圖像檢索方法都達(dá)到了很好的效果。

6結(jié)語(yǔ)

本文對(duì)基于改進(jìn)的分布式K-Means特征聚類的海量場(chǎng)景圖像檢索方法進(jìn)行了深入探討和研究，研究了如何對(duì)分布式K-Means算法改進(jìn)，并將其應(yīng)用于場(chǎng)景圖像檢索的特征聚類中，在Hadoop分布式處理平臺(tái)上實(shí)現(xiàn)了海量場(chǎng)景圖像的檢索。實(shí)驗(yàn)結(jié)果表明，設(shè)計(jì)的檢索方案能均衡系統(tǒng)負(fù)載，充分利用分布式系統(tǒng)的資源，提高檢索速度；面對(duì)海量的場(chǎng)景圖像數(shù)據(jù)，Hadoop分布式系統(tǒng)的檢索效率相對(duì)于單節(jié)點(diǎn)架構(gòu)的系統(tǒng)有很大提高，充分體現(xiàn)了分布式并行處理架構(gòu)的強(qiáng)大計(jì)算能力。

隨著大數(shù)據(jù)時(shí)代的到來(lái)以及云計(jì)算、多媒體技術(shù)的快速發(fā)展，對(duì)于大規(guī)模多媒體數(shù)據(jù)的分析和處理逐漸成為新的研究熱點(diǎn)。本文下一步的研究?jī)?nèi)容主要包括：(1) 擴(kuò)展Hadoop分布式平臺(tái)的節(jié)點(diǎn)數(shù)，調(diào)節(jié)系統(tǒng)的相關(guān)參數(shù)，進(jìn)一步提高分布式系統(tǒng)的工作效率；(2) 優(yōu)化特征提取和聚類算法，提高檢索的準(zhǔn)確率；(3) 優(yōu)化分布式處理Map任務(wù)和Reduce任務(wù)的設(shè)計(jì)，從而實(shí)現(xiàn)更快、更精確的檢索。

參考文獻(xiàn)

[1]AlmeerMH.CloudHadoopmapreduceforremotesensingimageanalysis[J].JournalofEmergingTrendsinComputingandInformationSciences,2012,3(4):637-644.

[2] 朱為盛,王鵬.基于Hadoop云計(jì)算平臺(tái)的大規(guī)模圖像檢索方案[J].計(jì)算機(jī)應(yīng)用,2014,34(3):695-699.

[3]NehaA,KiriiA.Amid-pointbasedk-meanclusteringalgorithmforDatamining[J].InternationalJournalonComputerScienceandEngineering,2012,4(6):1174-1180.

[4] 張軍偉,王念濱,黃少濱,等.二分K均值聚類算法優(yōu)化及并行化研究[J].計(jì)算機(jī)工程,2011,37(11):23-25.

[5] 韓最蛟.基于數(shù)據(jù)密集性的自適應(yīng)K均值初始化方法[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(2):182-187.

[6] 趙衛(wèi)中,馬慧芳,傅燕翔,等.基于云計(jì)算平臺(tái)Hadoop的并行K-Means聚類算法設(shè)計(jì)研究[J].計(jì)算機(jī)科學(xué),2011,38(10):166-168.

[7] 金偉健,王春枝.適于進(jìn)化算法的迭代式MapReduce框架[J].計(jì)算機(jī)應(yīng)用,2013,33(12):3591-3595.

[8]WileyK,ConnollyA,KrughoffS,etal.AstronomicalimageprocessingwithHadoop[C]//Proceedingsofthe20thConferenceonAstronomicalDataAnalysisSoftwareandSystems.SanFrancisco:AstronomicalSocietyofthePacific,2011:93-96.

[9] 朱義明.基于Hadoop平臺(tái)的圖像分類[J].西南科技大學(xué)學(xué)報(bào),2011,26(2):70-73.

[10]SweeneyC,LiuL,AriettaS,etal.HIPI:aHadoopimageprocessinginterfaceforimage-basedmapreducetasks[D].Charlattesville:UniversityofVirginia,2011.

[11] 樊哲.Mahout算法解析與案例實(shí)戰(zhàn)[M].北京:機(jī)械工業(yè)出版社,2014.

[12]GollerA,GlendinningI,BachmannD,etal.Parallelanddistributedprocessing[M].DigitalImageAnalysis.Berlin:Springer-Verlag,2001:135-153.

[13] 王賢偉,戴青云,姜文超,等.基于MapReduce的外觀設(shè)計(jì)專利圖像檢索方法[J].小型微型計(jì)算機(jī)系統(tǒng),2012,33(3):626-632.

[14] 顏宏文,陳鵬.基于云模型的電網(wǎng)統(tǒng)計(jì)數(shù)據(jù)質(zhì)量評(píng)估方法研究[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(12):100-103.

MASSIVE SCENE IMAGE RETRIEVAL BASED ON IMPROVED DISTRIBUTEDK-MEANSFEATURECLUSTERING

Cui HongyanCao Jianfang*

(Department of Computer Science and Technology,Xinzhou Teachers University,Xinzhou 034000,Shanxi,China)

AbstractConcerning that traditional image retrieval methods are confronted with the problems when processing massive data, we put forward a retrieval method for massive scene images, which is based on improved k-means feature clustering. We improved the distributed K-means algorithm, optimised the selection of initial cluster centres and the iteration procedure, and applied it to feature clustering of scene images. We made full use of the massive storage capacity and the powerful parallel computing ability of Hadoop distributed platform, proposed the storage and retrieval scheme on massive scene image, and designed the Map and Reduce tasks of three-phase distributed parallel processing on scene image with feature extraction, feature clustering and image retrieval. Sets of experiments demonstrated that the proposed method has gentle curve of data expansion rate, achieves good speedup ratio, the efficiency is greater than 0.6, and the average accuracy rate of retrieval reaches about 88%. The proposed scheme is suitable for large-scale scene image data retrieval.

KeywordsHadoop distributed platformMapReduceDistributed k-means algorithmFeature clusteringScene image retrieval

收稿日期：2015-01-19。國(guó)家自然科學(xué)基金項(xiàng)目(61202163)；山西省高校大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項(xiàng)目(2014383)；山西省自然科學(xué)基金項(xiàng)目(2013011017-2)；忻州師范學(xué)院重點(diǎn)學(xué)科專項(xiàng)課題(XK201308)。崔紅艷，本科生，主研領(lǐng)域：數(shù)字圖像理解。曹建芳，副教授。

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.06.047