基于Hadoop分布式計(jì)算的圖像檢索方法

梁欣然等

摘要：針對(duì)傳統(tǒng)單節(jié)點(diǎn)的基于內(nèi)容的圖像檢索方法計(jì)算速度較慢，檢索效率不高的問(wèn)題，提出了一種基于Hadoop分布式計(jì)算的圖像檢索方法。首先提取出圖像的顏色、紋理和形狀特征用于表示圖像，在檢索階段將檢索任務(wù)分配到各個(gè)Map子節(jié)點(diǎn)，所有的Map結(jié)果根據(jù)相似度非減進(jìn)行排序，并將前N個(gè)結(jié)果進(jìn)行輸出。實(shí)驗(yàn)結(jié)果表明，該方法有效地利用了云計(jì)算平臺(tái)的并行處理能力，相比較單節(jié)點(diǎn)的圖像檢索方法，提高了CBIR方法的運(yùn)行效率。

關(guān)鍵詞：圖像檢索；分布式計(jì)算；Hadoop

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）17-0153-02

Image Retrieval Based on Hadoop Distributed Computing

LIANG Xin-ran1， LIANG Peng2， ZHOU Hai-tao1， ZHOU Jian-xiong1， ZHOU Yi-shu1， LAO Xue-li3

（1.China Mobile， South Base， Guangzhou 510640， China；2.School of Computer Science， GuangDong Polytechnic Normal University， Guangzhou 510665， China；3.Bingosoft Development Corporation Limited， Guangzhou 510663， China）

Abstract： Aiming at the problem of inefficiently of traditional content based image retrieval method， this paper proposes an image retrieval method based on hadoop distributed computing. We first extract color features， texture features and sharp features from image dataset. Then， the retrieval job will be distributed to all map services and all retrieval results will be sorted according to matching results. Finally， the first N images will be sent back to user. The experimental result shows that our proposed method can improve the computing efficiency of traditional CBIR method.

Key words： image retrieval； distributed computing； hadoop

基于內(nèi)容的圖像檢索（CBIR）是指根據(jù)圖像內(nèi)容而并非文字關(guān)鍵詞對(duì)圖像進(jìn)行檢索的方法，并在許多領(lǐng)域得到了廣泛的使用[1-3]。CBIR檢索方法首先提取出圖像數(shù)據(jù)集的特征，用圖像的特征代表圖像，匹配時(shí)用測(cè)試圖像特征與特征數(shù)據(jù)集進(jìn)行比較，最后返回匹配程度較高的部分圖像。然而當(dāng)圖像數(shù)據(jù)集數(shù)量增大時(shí)，檢索性能和速度會(huì)急劇下降，如何提高CBIR檢索方法的計(jì)算速度成為了一個(gè)迫切的研究問(wèn)題。

云計(jì)算是指將數(shù)據(jù)存儲(chǔ)和檢索任務(wù)分布在大量的分布式計(jì)算機(jī)上，而非本地計(jì)算機(jī)。Hadoop[6，7]是一個(gè)可擴(kuò)展的分布式系統(tǒng)基礎(chǔ)架構(gòu)，并且對(duì)用戶(hù)提供了開(kāi)發(fā)接口，使得用戶(hù)無(wú)需關(guān)注分布式底層的實(shí)現(xiàn)細(xì)節(jié)，很方便地搭建分布式計(jì)算平臺(tái)；此外Hadoop技術(shù)支持在普通計(jì)算機(jī)上實(shí)現(xiàn)分布式計(jì)算架構(gòu)，而無(wú)需服務(wù)器進(jìn)行支撐，因此得到了廣泛的應(yīng)用[4，5，6]。

為此，本文提出基于Hadoop分布式計(jì)算的圖像檢索方法，利用云計(jì)算平臺(tái)的并行處理能力提高CBIR方法的運(yùn)行效率，實(shí)驗(yàn)結(jié)果表明基于Hadoop分布式計(jì)算的圖像檢索方法減少了檢索的時(shí)間，提高了檢索的效率。

1 Hadoop平臺(tái)

Hadoop平臺(tái)是當(dāng)今使用最廣泛的分布式云計(jì)算平臺(tái)，主要分為HDFS、MapReduce和Hbase三部分。HDFS提供了一個(gè)可以運(yùn)行在普通硬件集群上的分布式文件系統(tǒng)，可以存儲(chǔ)超大文件并使用流對(duì)文件進(jìn)行高速讀寫(xiě)。HDFS是由一個(gè)NameNode主服務(wù)器和多個(gè)DataNode塊服務(wù)器組成的主從結(jié)構(gòu)，NameNode用于管理文件系統(tǒng)的命名空間以及用戶(hù)對(duì)文件的讀寫(xiě)訪(fǎng)問(wèn)，其中包括各個(gè)DataNode的新增、刪除和修改；DataNode則實(shí)現(xiàn)了對(duì)大數(shù)據(jù)的分割和存儲(chǔ)，此外DataNode之間的數(shù)據(jù)還會(huì)相互復(fù)制以保證數(shù)據(jù)的安全和高速讀取。

MapReduce是一個(gè)可用于大數(shù)據(jù)處理的分布式計(jì)算框架，實(shí)現(xiàn)了并行計(jì)算功能。研究發(fā)現(xiàn)，大部分的并行計(jì)算都可以分解為Map-Reduce的框架，其主要思想是將一個(gè)大數(shù)據(jù)的檢索任務(wù)分割為多個(gè)子任務(wù)，系統(tǒng)根據(jù)不同的分配策略將子任務(wù)分配到各個(gè)節(jié)點(diǎn)中運(yùn)行，子節(jié)點(diǎn)將結(jié)果返回后再進(jìn)行合并處理。具體的來(lái)說(shuō)，即將輸入的檢索請(qǐng)求分解為多個(gè)中間的Key/Value組合（Map），再將返回的Key/Value合成最終的用戶(hù)輸出（Reduce），如圖1所示。

圖像存儲(chǔ)在HDFS系統(tǒng)中，提取的圖像特征則存儲(chǔ)在Hbase數(shù)據(jù)庫(kù)中，Hbase數(shù)據(jù)庫(kù)是一種非結(jié)構(gòu)化數(shù)據(jù)庫(kù)，數(shù)據(jù)存儲(chǔ)以列為模式，每一個(gè)數(shù)據(jù)行可以增加任意數(shù)量的列數(shù)據(jù)，這種變長(zhǎng)的數(shù)據(jù)存儲(chǔ)模式很適用于長(zhǎng)度可變的圖像特征。

2 基于分布式計(jì)算的圖像檢索

2.1 圖像特征提取

圖像屬于高維數(shù)據(jù)，除了目標(biāo)物體外還有大量的背景圖像和噪聲物體。直接采用圖像進(jìn)行匹配，不僅檢索準(zhǔn)確率不高，所需的檢索時(shí)間也很長(zhǎng)。因此需要先抽取出圖像的特征作為圖像的表示，用特征匹配代替圖像匹配。

常用的圖像特征有顏色、紋理和形狀特征，將圖像數(shù)據(jù)庫(kù)中的每幅圖像分別提取其顏色、紋理和形狀特征作為特征向量，將圖像和特征向量分別存儲(chǔ)到HDFS和HBase中；查詢(xún)時(shí)，將查詢(xún)圖像的特征與HBase中的特征進(jìn)行匹配，最后將匹配對(duì)應(yīng)的圖像返回給用戶(hù)。

1） 顏色特征

顏色特征是指圖像顏色的全局概率分布直方圖，是對(duì)整幅圖像進(jìn)行統(tǒng)計(jì)的全局特征，但是丟失了圖像的空間信息，文中采用的顏色特征有顏色直方圖。

2） 形狀特征

形狀特征分為輪廓特征和區(qū)域特征兩種，前者是指圖像中目標(biāo)物體的外輪廓表示，后者則是表示整個(gè)形狀區(qū)域的表示，文中采用的形狀特征是candy邊緣特征。

3） 紋理特征

紋理特征表示圖像灰度變化的方向和規(guī)律，紋理特征主要對(duì)粗糙度、對(duì)比度、方向度、線(xiàn)像度、規(guī)整度和粗略度等6個(gè)方面進(jìn)行提取，文中采用的紋理特征是LBP紋理特征。

2.2特征匹配

圖像特征是向量表示，因此特征匹配采用向量之間的歐式距離來(lái)表示，給定兩個(gè)特征向量[X={x1，x2，...，xn}]和[Y={y1，y2，...，yn}]，其向量之間的歐式距離為：

[d（X，Y）=i=1n|xi-yi|2]

由于每種特征的取值范圍不同，因此需要對(duì)計(jì)算后歐式距離進(jìn)行歸一化處理，用[dc（X，Y）]、[ds（X，Y）]和[dg（X，Y）]分別表示顏色、形狀和紋理特征的歐式距離，歸一化的處理如下：

[dc（X，Y）=dc（X，Y）-μcσc]

[ds（X，Y）=ds（X，Y）-μsσs]

[dg（X，Y）=dg（X，Y）-μgσg]

則兩幅圖像[I1]和[I2]的距離表示為：

[d（I1，I2）=13（dc（I1，I2）+ds（I1，I2）+dg（I1，I2））]3.2 MapReduce的圖像檢索

當(dāng)測(cè)試圖像進(jìn)行檢索時(shí)，利用MapReduce并行計(jì)算框架對(duì)實(shí)現(xiàn)并行計(jì)算，減少檢索所需的時(shí)間：

1） 首先提取出測(cè)試圖像的顏色、形狀、紋理特征，并將三種特征進(jìn)行組合；

2） Map階段，將測(cè)試圖像的特征與各個(gè)子節(jié)點(diǎn)中的圖像特征進(jìn)行匹配，Map的輸出格式為（相似度，圖像ID）鍵值，并將結(jié)果復(fù)制作為Reduce階段的輸入；

3） Reduce階段，所有的Map結(jié)果根據(jù)相似度非減進(jìn)行排序，并將前N個(gè)結(jié)果進(jìn)行輸出。

3 實(shí)驗(yàn)及討論

為了驗(yàn)證本文方法的有效性，我們采用著名的Caltech256數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，Caltech256數(shù)據(jù)集有256個(gè)類(lèi)別的目標(biāo)圖像，平均每個(gè)類(lèi)別約有80張-200張圖像，示例圖像如圖3所示。

本文采用IBM高性能計(jì)算集群進(jìn)行分布式環(huán)境的搭建，其硬件性能主要有：系統(tǒng)存儲(chǔ)能力20TB，內(nèi)存468GB，16個(gè)節(jié)點(diǎn)，其中1個(gè)NameNote，1個(gè)IO節(jié)點(diǎn)，14個(gè)DataNote，NameNote服務(wù)器的配置為Intel Core i7 4.5GHz，內(nèi)存為16GB，DataNote服務(wù)器的配置為AMD Athlon II X4 2.8GHz，內(nèi)存為8GB，所有服務(wù)器節(jié)點(diǎn)均配置千兆傳輸網(wǎng)絡(luò)。軟件操作系統(tǒng)采用Red Hat Enterprise Linux Server release 5.6 X86_64，Hadoop-0.20.2以及jdk1.6。

首先我們進(jìn)行系統(tǒng)檢索性能的比較，我們將文中的分布式圖像檢索與傳統(tǒng)的單節(jié)點(diǎn)圖像檢索系統(tǒng)進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖2所示。

從圖2中可以看出，隨著圖像數(shù)量的增加，兩種方法的檢索時(shí)間都有所增加，但是對(duì)于圖像數(shù)量較多時(shí)，分布式圖像檢索方法的檢索時(shí)間遠(yuǎn)低于單節(jié)點(diǎn)圖像檢索方法。

然后我們對(duì)文中方法的查全率和準(zhǔn)確率進(jìn)行實(shí)驗(yàn)，查全率和準(zhǔn)確率分別表示如下：

[ 查全率=正確分類(lèi)的圖像數(shù)量該類(lèi)別的圖像數(shù)量×100%]

[ 準(zhǔn)確率=正確分類(lèi)的圖像數(shù)量分類(lèi)為該類(lèi)別的圖像數(shù)量×100%]

查全率-準(zhǔn)確率曲線(xiàn)形成一個(gè)區(qū)域，該區(qū)域面積越大，表示檢索方法的性能越好，選擇檢索圖像為7000張圖像時(shí)，本文方法與單節(jié)點(diǎn)檢索方法的查全率-準(zhǔn)確率曲線(xiàn)如圖3所示。

從圖3中可以看出，分布式圖像檢索雖然將檢索數(shù)據(jù)分為多個(gè)子任務(wù)進(jìn)行檢索，但是并沒(méi)有降低其檢索性能。

4 結(jié)論及未來(lái)工作

本文針對(duì)傳統(tǒng)單節(jié)點(diǎn)的CBIR檢索方法計(jì)算速度較慢，檢索效率不高的問(wèn)題，提出了一種基于Hadoop分布式計(jì)算的圖像檢索方法，利用云計(jì)算平臺(tái)的并行處理能力提高CBIR方法的運(yùn)行效率，實(shí)驗(yàn)結(jié)果表明基于Hadoop分布式計(jì)算的圖像檢索方法減少了檢索的時(shí)間，提高了檢索的效率。未來(lái)的主要工作集中在提高CBIR檢索的準(zhǔn)確率和查全率。

參考文獻(xiàn)：

[1] 宋真，顏永豐.基于興趣點(diǎn)綜合特征的圖像檢索[J].計(jì)算機(jī)應(yīng)用，2012，32（10）：2840-2842.

[2] 張泉，邰曉英 基于Bayesian 的相關(guān)反饋在醫(yī)學(xué)圖像檢索中的應(yīng)用[J].計(jì)算機(jī)工程， 2008，44（ 17） ： 158-161.

[3] 余勝，謝莉，成運(yùn).基于顏色和基元特征的圖像檢索[J].計(jì)算機(jī)應(yīng)用， 2013， 33（6）：1674-1708.

[4] 陳康， 鄭緯民. 云計(jì)算： 系統(tǒng)實(shí)例與研究現(xiàn)狀. 軟件學(xué)報(bào)， 2009，20（5）： 1337-1348.

[5] 陳全， 鄧倩妮. 云計(jì)算及其關(guān)鍵技術(shù)[J].計(jì)算機(jī)應(yīng)用， 2009，29（9）： 2562-2567.

[6] Armbrust M. A view of cloud computing. Communications of the ACM， 2010， 53（4）： 50-58.

[7] Borthakur D. The hadoop distributed file system： Architecture and design. Hadoop Project Website， 2007： 11-21.