蔡麗娟

（福建廣播電視大學(xué)漳州分校，福建漳州，363000）

基于內(nèi)容的Hadoop/MapReduce架構(gòu)圖像檢索方法

蔡麗娟

（福建廣播電視大學(xué)漳州分校，福建漳州，363000）

運用Hadoop/MapReduce并行海量圖像處理框架進行基于內(nèi)容的海量圖像檢索，將海量圖像數(shù)據(jù)分布式存儲在眾多節(jié)點上，運用優(yōu)化的ACCC算法在各節(jié)點上進行基于內(nèi)容的圖像搜索分析算法一體化處理，通過與傳統(tǒng)并行計算方法和單節(jié)點方法試驗對比，演示本方法在存儲能力和計算檢索效能的優(yōu)勢。

Hadoop/MapReduce；并行處理；圖像處理

基于內(nèi)容的圖像檢索（CBIR）方法幾十年來一直是海量圖像檢索與分析的研究熱點，但由于海量圖片數(shù)據(jù)量巨大，對計算能力要求極高，因此尚不能達到實時處理的能力，無法實現(xiàn)實際應(yīng)用。[1]目前大多數(shù)的CBIR研究論文往往集中在研究算法的改進和局部應(yīng)用實驗方面上，如一種基于內(nèi)容的聯(lián)合查詢圖像檢索系統(tǒng)已被提出，[2][3]用于實現(xiàn)圖像查詢和相關(guān)特征反饋，該系統(tǒng)雖然在準(zhǔn)確性方面性能表現(xiàn)突出，但在處理海量圖片數(shù)據(jù)時，單機基于多線程的架構(gòu)無法滿足實時要求，在效率方面不能令人滿意。許多研究人員也試圖通過使用分布式計算解決這個問題[4][5]（例如利用集群計算），如陸永泉等人[6]提出了一種并行計算方法進行圖像特征提取，并設(shè)計了基于集群架構(gòu)的圖像特征相似性比較方案。實驗表明，該集群很好地提高了檢索性能，但始終沒有很好的解決系統(tǒng)高效存儲和負(fù)載均衡的問題。

隨著大數(shù)據(jù)Hadoop系統(tǒng)和MapReduce計算架構(gòu)的出現(xiàn)，為海量圖像高效存儲和實時處理提供了可能。本文在Hadoop/MapReduce并行圖像處理框架基礎(chǔ)上，提出了一種有效的顏色特征提取方法——自動顏色相關(guān)圖算法Auto Color Correlogram and Correlation(ACCC)，[7]用于提取圖像低級特征，該方法與MapReduce計算架構(gòu)有效結(jié)合到一起，顯著提高了下檢索不同來源圖像相似性的能力。[8][9]

一、Hadoop/MapReduce架構(gòu)

Hadoop采用開放式源代碼框架，[1]具備大型數(shù)據(jù)處理能力，其中的MapReduce分布式模型實現(xiàn)了資源虛擬化管理、調(diào)度和共享，是當(dāng)今應(yīng)用最為廣泛的開源大數(shù)據(jù)編程平臺。

為了簡化系統(tǒng)，HDFS集群中只部署一個NameNode（選擇相對性能較好的計算機），其余節(jié)點各運行一個DataNode。當(dāng)然，NameNode節(jié)點性能足夠好，也可在該機上部署一個或多個DataNode。同理，同一物理機上的DataNode數(shù)量是沒有規(guī)定的，只要計算機的存儲能力能夠滿足要求。

如圖1所示，HDFS采取的是主從架構(gòu)，每個HDFS集群均有一個NameNode和多個DataN原ode。其中，NameNode為主服務(wù)器，負(fù)責(zé)管理HDFS系統(tǒng)，接受客戶端請求；DataNode是從服務(wù)器，作用為存儲數(shù)據(jù)；HDFS將一個文件分割成多個塊，這些塊可存儲在一個或多個DataN原ode上。同時，采用HBase存儲半結(jié)構(gòu)化和非結(jié)構(gòu)化的松散數(shù)據(jù)，提供高列存儲、高性能、可伸縮、可靠的實時讀寫服務(wù)。

圖1 HDFS體系架構(gòu)

MapReduce是Hadoop架構(gòu)的基礎(chǔ)計算模型，其將輸入海量圖像數(shù)據(jù)劃分為大小確定數(shù)據(jù)塊（默認(rèn)64MB）進行處理的過程，過程稱為MapReduce的“映射與歸約”。這種分布式并行映射任務(wù)的實現(xiàn)方法，意味著每一數(shù)據(jù)塊處理時間相對于整個海量數(shù)據(jù)任務(wù)處理時間會大幅度縮短。且分區(qū)處理數(shù)據(jù)少并且性能高的設(shè)備，可以處理更多數(shù)據(jù)塊，因此參加并行計算的每個分區(qū)負(fù)載會更加平衡。對于大量性能相近的計算硬件設(shè)備，只要任務(wù)分區(qū)合理，負(fù)載平衡能力可取得令人滿意的效果。但數(shù)據(jù)塊過小，分區(qū)管理和創(chuàng)建映射任務(wù)開銷占總?cè)蝿?wù)開銷的比例會增大。對于大多數(shù)的進程，合適的分區(qū)大小取決于分布式文件系統(tǒng)數(shù)據(jù)塊的大小，這可以通過集群技術(shù)（對所有剛被創(chuàng)建的文件）或文件創(chuàng)建時指定方法加以解決。

圖2 MapReduce的映射與歸約

MapReduce程序主要在“映射Map”和“歸約Reduce”這兩個階段執(zhí)行，每個階段由數(shù)據(jù)處理函數(shù)定義，這些函數(shù)分別稱為“映射函數(shù)”和“歸約函數(shù)”。在映射階段，MapReduce接受輸入數(shù)據(jù)并且將每個數(shù)據(jù)元素發(fā)射到“映射器”；在歸約階段，歸約函數(shù)處理所有來自映射器的數(shù)據(jù)，映射歸約任務(wù)流程如圖2所示，方格表示節(jié)點，虛線箭頭表示數(shù)據(jù)的邏輯映射與歸約，實線箭頭表示節(jié)點間的實際數(shù)據(jù)傳輸?？梢钥闯?，海量圖像數(shù)據(jù)塊被映射為多個單元，計算完成后規(guī)約為統(tǒng)一結(jié)果輸出，且在多重映射過程中，每一次映射信息記錄均獨立保存。

二、基于內(nèi)容的圖像檢索系統(tǒng)的MapReduce框架

本文采取MapReduce方法對海量圖片進行并行檢索處理，映射函數(shù)的輸出值在輸入到歸約函數(shù)之前，需經(jīng)過MapReduce進行處理，這一過程是通過一系列關(guān)鍵詞對鍵值的分類和組合完成的。所有的歸約函數(shù)必須循環(huán)通過每個HDFS文件進行圖像整理和分類。圖3展示了MapReduce是在CBIR整個系統(tǒng)實現(xiàn)原理。首先，將海量圖像文件通過映射分割成若干HDFS分區(qū)文件，實現(xiàn)了再HDFS的分布式存儲；其次，通過映射與規(guī)約計算機制提取其圖像特征；最后，實現(xiàn)圖片特征向量相似性匹配并輸出結(jié)果?？梢钥闯觯琀adoop/MapReduce系統(tǒng)通過“節(jié)點”來訪問圖像數(shù)據(jù)。MapReduce把輸入的數(shù)據(jù)拆分成獨立的數(shù)據(jù)塊，并且這些并且并行實現(xiàn)數(shù)據(jù)塊的數(shù)據(jù)處理及算，最后把輸出結(jié)果歸類后給Reduce規(guī)約輸出。輸入和輸出過程都存儲在一個文件系統(tǒng)里（HDFS文件），Hadoop/ MapReduce框架保管調(diào)度任務(wù)，監(jiān)測并再次執(zhí)行失敗了的任務(wù)。

圖3 基于內(nèi)容的圖像檢索系統(tǒng)的MapReduce框架

三、圖像的特征計算

本文上節(jié)提出了MapReduce架構(gòu)用以高效處理海量圖像數(shù)據(jù)，但要得到更好的系統(tǒng)效能，我們依然需關(guān)注CBIR系統(tǒng)自身圖片特征提取方法，也就是如何提高提取圖像顏色特征可靠性和實時性的問題。基于此，我們將顏色索引技術(shù)的自相關(guān)函數(shù)（ACC）[10]擴展，提出了一種新的圖像特征提取自動顏色相關(guān)圖算法（ACCC）。其中的自相關(guān)函數(shù)描述了如何求取像素cj和其相距為k-th的任意像素的計算平均顏色值。通常，圖像I(x，y)，x=1，2，…，M；y=1，2，……，N的ACC可定義為：

在這里，原始圖像I(x，y)可被量化為顏色特征C1，C2，…Cj等，任意兩個像素間的距離且屬固定值（例如圖片的長度和寬度），那么MCj可表示在圖像I(x，y)中從像素Cj到像素Ci距離為k的圖像顏色特征，計算方法如下：

我們提出方法，實在基于自相關(guān)函數(shù)的上擴展的自關(guān)聯(lián)技術(shù)（ACCC），它是將自相關(guān)函數(shù)和自動顏色關(guān)聯(lián)技術(shù)進行的整合。由此，AC原CC可定義為：

根據(jù)以上原理，ACCC的偽代碼科表示為：

圖像檢索根據(jù)特征相似度矩陣來進行度量，在個顏色特征范圍內(nèi)，使得ACCC成對的出現(xiàn)在和里。圖像相似性可用AC和ACC之間的距離度量，[11]如下式所示：

式中姿1和姿2在函數(shù)自相關(guān)和顏色關(guān)聯(lián)的加權(quán)常量。根據(jù)實驗經(jīng)驗，可得姿1=0.5和姿2=0.5。ai和βi定義如下：

四、性能對比實驗

（一）存儲性能對比

在硬件設(shè)備性能基本一致的前提下，采用本文提出的Hadoop/MapReduce并行ACCC圖像處理框架，與傳統(tǒng)并行集群系統(tǒng)及B/S單點檢索系統(tǒng)進行實驗對比，在處理圖像數(shù)量不同、節(jié)點不同情況下，圖像存儲時間如圖4所示?？梢钥闯觯?dāng)數(shù)據(jù)達到一定數(shù)量時，本文方法圖像存儲時間更短，使得整體性能得以提高。

圖4 三種系統(tǒng)的圖像存儲時間對比

（二）檢索效率對比

對不同規(guī)模的圖像庫進行試驗，圖像檢索耗時如圖5所示?？梢钥闯?，由于Map砸educe的并行計算優(yōu)勢，節(jié)點越多，檢索速度越快，增加節(jié)點數(shù)，可以提高圖像檢索系統(tǒng)性能。

圖5 三種系統(tǒng)的圖像檢索效率對比

結(jié)論

文章表述了一種使用Hadoop/MapReduce方法進行基于內(nèi)容的圖像檢索的框架，并基于CBIR提出了ACCC算法，用于減少特征計算的運行時間。仿真測試結(jié)果表明，Hadoop/MapRe原duce圖像檢索系統(tǒng)提高了圖像存儲和檢索效率，獲得較優(yōu)的檢索結(jié)果。未來的工作重點是提高Map任務(wù)與砸educe任務(wù)之間數(shù)據(jù)傳輸速度，減少更多由于傳輸信息所產(chǎn)生的時間消耗，進一步提高現(xiàn)有圖像檢索系統(tǒng)的執(zhí)行效率。

[1]Anucha，T.&P.Wichian.On-line Content-Based Image Retrieval System using Joint Querying and Relevance Feedback Scheme[J].WSEAS Transaction on Computers，2010，（5）:26-38.

[2]Change，E.Y.Content-based soft annotation for multimodal image retrieval using Bayes point machines[J].IEEE Transactions on Circuits and Systems for Video Technology，2003，（1）:26-38.

[3]Cohn，D.The missing link-a probabilistic model of document content and hypertext connectivity[J].Advances in Neu鄄ral Information Processing Systems，2001，（5）:25-31.

[4]Kao，O.Scheduling aspects for image retrieval in cluster-based image databases[C].IEEE/ACM Cluster Computing and the Grid.Urbana:University of Illinois Press，2001:329-336.

[5]Ling，Y.Image Semantic Information Retrieval Based on Parallel Computing[C].International Conference on Com鄄puter Vision.New York:Cambridge University Press，2008:255-259.

[6]Gonzalez，R.C.Digital Image Processing[M].London:Prentice-Hall，2009:135-127.

[7]Anucha，T.Spatial Color Indexing using ACC Algorithms[C].International Conference on Computer Vision.Urbana: University of Illinois Press，2009:113-117.

[8]Newman，D.Distributed Inference for Latent Dirichlet Allocation[C].Neural Information Processing Systems（NIPS）. Urbana:University of Illinois Press，2008:1081-1088.

[9]Tong，S.Support Vector Machine active learning for image retrieval[C].ACM international conference on Multimedi鄄a.New York:Cambridge University Press，2001:107-118.

[10]Anucha，T.Spatial Color Indexing using ACC Algorithms[C].IEEE Transactions on Circuits and Systems for Video Technology.New York:Cambridge University Press，2009:113-117.

[11]Lee，Y.H&K.H.Lee.Spatial Color Descriptor for Image Retrieval and Video Segmentation[J].IEEE Transaction on Multimedia，2003，（3）:358-367.

[責(zé)任編輯：陳曉蔚]

TP3911.41

A

1008-7346（2014）05-0041-09

2014-08-30

蔡麗娟，女，福建石獅人，福建廣播電視大學(xué)漳州分校講師。