基于MapReduce數(shù)字圖像處理研究

田進(jìn)華，張韌志

（黃淮學(xué)院 河南 駐馬店 463000）

以互聯(lián)網(wǎng)為計(jì)算平臺(tái)的云計(jì)算，將會(huì)涉及非常多的海量數(shù)據(jù)處理任務(wù)[1]，海量數(shù)據(jù)處理是指對(duì)大規(guī)模數(shù)據(jù)的計(jì)算和分析，通常數(shù)據(jù)規(guī)?？梢赃_(dá)到TB甚至PB級(jí)別。當(dāng)今世界最流行的海量數(shù)據(jù)處理可以說是MapReduce編程模式。MapReduce分布式編程模型允許用戶在不了解分布式系統(tǒng)底層實(shí)現(xiàn)細(xì)節(jié)的情況下開發(fā)并行應(yīng)用程序。用戶可以利用Hadoop輕松地組織計(jì)算機(jī)資源，進(jìn)而搭建自己的分布式計(jì)算云平臺(tái)，并且可以充分利用集群的計(jì)算和存儲(chǔ)能力，完成海量數(shù)據(jù)的處理。

1 Map Reduce計(jì)算模型

Hadoop是一個(gè)開源分布式計(jì)算平臺(tái)。以分布式文件系統(tǒng)HDFS和MapReduce為核心的分布式計(jì)算和分布式存儲(chǔ)的編程環(huán)境[2]。MapReduce是用于大規(guī)模數(shù)據(jù)集分布式的計(jì)算模型，實(shí)現(xiàn)一個(gè)MapReduce應(yīng)用，首先，通過Map程序?qū)?shù)據(jù)切割成小塊，然后，分配給大量服務(wù)器處理，最后，通過Reduce程序?qū)⑻幚砗蟮慕Y(jié)果匯整輸出給客戶端。MapReduce的整個(gè)架構(gòu)是由Map和Reduce函數(shù)組成，當(dāng)程序輸入一大組Key/Value鍵值對(duì)時(shí)，Map負(fù)責(zé)根據(jù)輸入的Key/Value（鍵值）對(duì)，生成中間結(jié)果，這生成中間結(jié)果同樣采用Key/Value（鍵值）對(duì)的形式。開發(fā)者只需要實(shí)現(xiàn)Map和Reduce函數(shù)的邏輯，然后提交給MapReduce運(yùn)行環(huán)境，計(jì)算任務(wù)便會(huì)在大量計(jì)算機(jī)組成的集群上被自動(dòng)、并行地調(diào)度執(zhí)行。MapReduce的運(yùn)行環(huán)境是有兩個(gè)不同類型的節(jié)點(diǎn)組成:Master和Worker。Worker負(fù)責(zé)數(shù)據(jù)處理，Master主要負(fù)責(zé)任務(wù)分配和節(jié)點(diǎn)之間數(shù)據(jù)共享。需要實(shí)現(xiàn)或指定以下編程接口：

Map 函數(shù)：接收輸入的鍵值對(duì)＜kl，vl＞，計(jì)算生成一組中間的鍵值對(duì)＜k2，v2＞

Reduce函數(shù):接收鍵值對(duì)集合＜k2，v2的列表＞，聚集計(jì)算得到新鍵值對(duì)＜k3，v3＞。

Combiner函數(shù)：它是對(duì)Map函數(shù)輸出的中間數(shù)據(jù)在本地執(zhí)行歸并，將處理結(jié)果再傳輸給Reduce節(jié)點(diǎn)。Combiner可以降低Map任務(wù)節(jié)點(diǎn)和Reduce任務(wù)節(jié)點(diǎn)之間的通信代價(jià)。

InputFormat，OutputFormat：InputFormat 支 持 Hadoop 作業(yè)輸入數(shù)據(jù)鍵值對(duì)的轉(zhuǎn)換；OutputFormat表示Hadoop作業(yè)計(jì)算結(jié)果存儲(chǔ)在HDFS中的格式。

Partitioner函數(shù)：用于對(duì)Map函數(shù)輸出的中間結(jié)果進(jìn)行劃分，Map任務(wù)點(diǎn)根據(jù)所提供的Partition函數(shù)，將數(shù)據(jù)結(jié)果劃分給相應(yīng)Reduce任務(wù)節(jié)點(diǎn)。

Hadoop運(yùn)行MapReduce作業(yè)的流程圖如圖1所示。MapReduce作業(yè)包含四個(gè)相對(duì)獨(dú)立的模塊。客戶端主要負(fù)責(zé)MapReduce作業(yè)代碼的編寫，配置作業(yè)相關(guān)參數(shù)，向JobClient實(shí)體提交作業(yè)；JobTracker節(jié)點(diǎn)主要負(fù)責(zé)用戶提交作業(yè)的初始化，調(diào)度作業(yè)，與所有的TaskTracker節(jié)點(diǎn)進(jìn)行通信，協(xié)調(diào)用戶提交作業(yè)的執(zhí)行；TaskTracker節(jié)點(diǎn)負(fù)責(zé)自主與JobTracker節(jié)點(diǎn)進(jìn)行通信，根據(jù)所分配的數(shù)據(jù)塊執(zhí)行Map或Reduce任務(wù)，調(diào)用用戶定義的Map或Reduce函數(shù)；HDFS負(fù)責(zé)保存作業(yè)的數(shù)據(jù)、配置信息和作業(yè)結(jié)果等。

圖1 Hadoop運(yùn)行MapReduce作業(yè)流程圖Fig.1 MapReduce job’s flow chart on Hadoop

2 構(gòu)建圖像處理云平臺(tái)

在MapReduce計(jì)算框架中，Hadoop將輸入數(shù)據(jù)劃分成等長(zhǎng)的作業(yè)分片，每個(gè)Map任務(wù)處理一個(gè)作業(yè)分片，這些Map任務(wù)是并行執(zhí)行的[3]。Hadoop又將每個(gè)作業(yè)分片劃分為多個(gè)相同的鍵值對(duì)，每個(gè)Map任務(wù)對(duì)該分片中每個(gè)鍵值對(duì)再調(diào)用map函數(shù)來進(jìn)行處理。本系統(tǒng)把一個(gè)圖像文件作為一個(gè)作業(yè)分片，再把整個(gè)作業(yè)分片作為一個(gè)鍵值對(duì)來處理[4]。這樣每個(gè)Map任務(wù)只需調(diào)用一次map函數(shù)來處理一個(gè)圖像文件，進(jìn)而實(shí)現(xiàn)多個(gè)圖像文件的并行化處理。本系統(tǒng)只定義了一個(gè)Reduce任務(wù)，其調(diào)用reduce函數(shù)對(duì)每個(gè)鍵值對(duì)進(jìn)行簡(jiǎn)單的輸出操作。

1）鍵值對(duì)類型的設(shè)計(jì)

Hadoop中map和reduce函數(shù)的輸入和輸出是鍵/值對(duì)（Key/Valuepair），MapReduce框架并不允許任意的類作為鍵和值的類型，只有支持序列化的類才能夠在這個(gè)框架中充當(dāng)鍵或者值[5]。Hadoop有自己的序列化格式 Writable，實(shí)現(xiàn)Writable接口的類可以作為值類型。Writable接口定義了兩個(gè)方法：一個(gè)將其狀態(tài)寫到DataOutput二進(jìn)制流，另一個(gè)從DataInput二進(jìn)制流讀取其狀態(tài)[6]。實(shí)現(xiàn)WritableComparable＜T＞接口的類既可以作為鍵類型也可以作為值類型，該接口繼承自Writable和java.lang.Comparable接口。

WritableComparator是對(duì)繼承自WritableComparable類的RawComparator類的一個(gè)通用實(shí)現(xiàn)，提供了兩個(gè)主要功能：第一，對(duì)原始compare（）方法的默認(rèn)實(shí)現(xiàn)，能反序列化將在流中進(jìn)行比較的對(duì)象，并調(diào)用對(duì)象的compare（）方法；第二，充當(dāng)?shù)氖荝awComparator實(shí)例的工廠。Hadoop自帶的org.apache.hadoop.io包中有廣泛的Writable類，它們形成了如圖2所示的層次結(jié)構(gòu)。

圖2 Writable類層次結(jié)構(gòu)圖Fig.2 Writable class's hierarchical structure

本系統(tǒng)使用的鍵類型為Text，用來存儲(chǔ)圖像文件的名；值類型為Image，實(shí)現(xiàn)了Writable接口，用來存儲(chǔ)圖像文件的內(nèi)容。本系統(tǒng)的鍵值對(duì)在Map任務(wù)和Reduce任務(wù)數(shù)據(jù)變化流程如圖3所示。任務(wù)調(diào)用map函數(shù)對(duì)每個(gè)鍵值對(duì)進(jìn)行處理，處理前后鍵Filename的內(nèi)容不會(huì)發(fā)生改變，而存儲(chǔ)圖像信息的值Image的內(nèi)容會(huì)發(fā)生變化。Reduce任務(wù)調(diào)用reduce函數(shù)實(shí)現(xiàn)對(duì)其輸入的鍵值對(duì)進(jìn)行簡(jiǎn)單的鍵值對(duì)輸出操作。

圖3 本系統(tǒng)Map任務(wù)和Reduce任務(wù)數(shù)據(jù)流Fig.3 Map task and reduce task’s data flow in this system Map

2）作業(yè)的輸入格式設(shè)計(jì)

一個(gè)輸入分片（split）就是由單個(gè)Map任務(wù)處理的輸入塊，每個(gè)分片被劃分為若干個(gè)記錄，每條記錄就是一個(gè)鍵值對(duì)，map函數(shù)一個(gè)接一個(gè)處理每條記錄。map函數(shù)用該實(shí)現(xiàn)從InputSplit中讀取輸入的鍵值對(duì)。本系統(tǒng)設(shè)計(jì)了ImageFileInputFormat類繼承自 FileInputFormat＜Text，Image＞類的實(shí)現(xiàn)，把一個(gè)圖像文件作為一個(gè)輸入分片，不進(jìn)行文件分 割 ；ImageRecordReader 類 繼 承 自 RecordReader＜Text，Image＞類的實(shí)現(xiàn)，把輸入分片轉(zhuǎn)化為一個(gè)鍵值對(duì)，即圖像文件名作為鍵Text類型的一個(gè)實(shí)例，圖像文件內(nèi)容作為值Image類型的一個(gè)實(shí)例。ImageRecordReader類實(shí)現(xiàn)解碼讀取存儲(chǔ)在HDFS上作為輸入分片的圖像文件，獲得其字節(jié)流，然后將字節(jié)流轉(zhuǎn)化為上一節(jié)實(shí)現(xiàn)的值類型Image的一個(gè)實(shí)例，圖像文件的名字作為鍵類型Text的一個(gè)實(shí)例，其核心代碼如下:

FileSplit split=（FileSplit）genericSplit；

Configuration conf=context.getConfiguration（）；

Path file=split.getPath（）；

FileSystem fs=file.getFileSystem（conf）；

FSDataInputStream fileIn=fs.open（split.getPath（））；

byte[]b=new byte[fileIn.available（）]；

fileIn.readFully（b）；

image=new Image （cvDecodeImage （cvMat （1， b.length，CV_8UC1，

new BytePointer（b）），iscolor））；

fileName=split.getPath（）.getName（）.toString（）；

3）作業(yè)的輸出格式設(shè)計(jì)

MapReduce作業(yè)的輸出樣式用OutputFormat描述。根據(jù)OutputFormat，MapReduce框架檢驗(yàn)作業(yè)的輸出；看作業(yè)初始化的配置與驗(yàn)證輸出結(jié)果類型是否一致；通過RecordWriter用來輸出作業(yè)的結(jié)果，輸出文件保存在Hadoop的文件系統(tǒng)上。要定義OutputFormat抽象類。FileOutputFormat是所有使用文件作為其數(shù)據(jù)源的OutputFormat實(shí)現(xiàn)的基類。系統(tǒng)設(shè)計(jì)了 ImageOutputFormat 類 繼 承 自 FileOutputFormat＜Text，Image＞類的實(shí)現(xiàn)，把一個(gè)鍵值對(duì)作為內(nèi)容進(jìn)行輸出；ImageRecordWriter類繼承自 RecordWriter＜Text，Image＞類的實(shí)現(xiàn)，把鍵Text類型的實(shí)例作為圖像文件名，值Image類型的實(shí)例作為圖像文件內(nèi)容，生成一個(gè)圖像文件存入Hadoop文件系統(tǒng)中。ImageRecordWriter類實(shí)現(xiàn)編碼值類型Image的一個(gè)實(shí)例，作為圖像文件內(nèi)容的字節(jié)流，根據(jù)作業(yè)初始化的輸出目錄，再結(jié)合值類型FileName的一個(gè)實(shí)例，作為圖像文件的文件名，生成圖像文件，存儲(chǔ)在分布式文件系統(tǒng)HDFS中。

4）圖像處理功能

網(wǎng)上的數(shù)字圖像一般是一個(gè)大的二維數(shù)組，該數(shù)組的元素稱為像素，其值為一整數(shù)，稱為灰度值。圖像處理就是利用計(jì)算機(jī)對(duì)數(shù)字圖像的灰度值信息進(jìn)行處理，從中提取有用的信息或得到某種預(yù)期的效果。數(shù)字圖像處理的過程：首先是獲取圖像，對(duì)數(shù)字圖像縮放處理和圖像增強(qiáng)處理，圖像縮放常用的插值方法有最近鄰插值、雙線性插值、使用象素關(guān)系重采樣和立方插值。本文使用雙線性插值算法來實(shí)現(xiàn)在map函數(shù)中對(duì)圖像進(jìn)行0.5倍的縮放。然后進(jìn)行圖像復(fù)原和彩色圖像處理，利用小波與多分辨率對(duì)圖像處理，將一幅圖像分割成小的圖像，最后進(jìn)行特征提取和目標(biāo)識(shí)別。

對(duì)數(shù)字圖像的邊緣檢測(cè)是進(jìn)行圖像分割、目標(biāo)區(qū)域識(shí)別、區(qū)域形狀提取等圖像分析的技術(shù)基礎(chǔ)。對(duì)于連續(xù)圖像f（x，y），邊緣檢測(cè)就是求梯度的局部最大值和方向。利用Canny邊緣檢測(cè)算子，在map函數(shù)中實(shí)現(xiàn)對(duì)圖像的邊緣檢測(cè)，從而實(shí)現(xiàn)對(duì)圖像文件的并行化邊緣檢測(cè)。邊緣檢測(cè)步驟如下：

首先用2D高斯濾波模板與原始圖像進(jìn)行卷積，以消除噪聲。其次利用導(dǎo)數(shù)算子，找到圖像灰度沿著兩個(gè)方向的導(dǎo)數(shù)GxGy，并求出梯度大小。 然后利用2）的結(jié)果求出了邊緣的方向，就可以把邊緣的梯度方向大致分為 4 種（0°、45°、90°、135°），并可以找到這個(gè)像素梯度方向的鄰接像素。接著遍歷圖像。若某個(gè)像素的灰度值與其梯度方向上前后兩個(gè)像素的灰度值相比不是最大的，那么將這個(gè)像素值置為0，即不是邊緣。最后使用累計(jì)直方圖計(jì)算兩個(gè)閾值。凡是大于高閾值的一定是邊緣；凡是小于低閾值的一定不是邊緣。如果檢測(cè)結(jié)果在兩個(gè)閾值之間，則根據(jù)這個(gè)像素的鄰接像素中有沒有超過高閾值的邊緣像素，如果有，則它就是邊緣，否則不是。

5）MapReduce程序的編寫

為了使用 Hadoop中MapReduce來進(jìn)行海量圖像數(shù)據(jù)挖掘，需要編寫 MapReduce程序。目前大多數(shù) MapReduce程序的編寫都可依賴于一個(gè)模板及其變種。當(dāng)撰寫一個(gè)新的MapReduce程序時(shí)，通常會(huì)采用一個(gè)現(xiàn)有的MapReduce程序，并將其修改為所希望的樣子。編寫 MapReduce程序的第一步就是要了解數(shù)據(jù)流，設(shè)計(jì)所需的鍵值對(duì)類型。Hadoop自身只提供處理簡(jiǎn)單數(shù)字或字符的鍵值對(duì)類型，根據(jù)實(shí)際的需要設(shè)計(jì)相應(yīng)的類型。例如本文第四章，設(shè)計(jì)了名為Image的值類型，而鍵類型采用 Hadoop自帶的Text類型。MapReduce程序由三部分組成，分別是用戶定義的 map函數(shù)、用戶定義的 reduce函數(shù)和作業(yè)驅(qū)動(dòng)程序；map函數(shù)在Map任務(wù)執(zhí)行時(shí)被調(diào)用，reduce函數(shù)在 Reduce任務(wù)執(zhí)行時(shí)被調(diào)用，作業(yè)驅(qū)動(dòng)程序用于初始化作業(yè)的配置。

3 結(jié)束語(yǔ)

Hadoop[7]云平臺(tái)的圖像處理系統(tǒng)設(shè)計(jì)，把一個(gè)圖像文件作為一個(gè)作業(yè)分片，再把整個(gè)作業(yè)分片作為一個(gè)鍵值對(duì)來處理。這樣每個(gè)Map任務(wù)只需調(diào)用一次map函數(shù)來處理一個(gè)圖像文件，進(jìn)而實(shí)現(xiàn)多個(gè)圖像文件的并行化處理。節(jié)點(diǎn)可以自由地?cái)U(kuò)充，通過鍵值對(duì)的設(shè)計(jì)、作業(yè)的輸入與輸出格式的設(shè)計(jì)，可以實(shí)現(xiàn)海量圖像文件信息的并行化處理。整個(gè)云平臺(tái)提供的計(jì)算和存儲(chǔ)能力近乎是無限的。隨著圖像文件量的增加，MapReduce處理數(shù)據(jù)的最佳速度最好與數(shù)據(jù)在云平臺(tái)中的傳輸速度相同，系統(tǒng)的利用率會(huì)有隨之提高。

[1]劉鵬.云計(jì)算[M].2版.北京:電子工業(yè)出版社，2011.

[2]朱義明.基于Hadoop平臺(tái)的圖像分類[J].西南科技大學(xué)學(xué)報(bào)，2011（2）:70-73.ZHUYi-ming.Imageclassification based on hadoop platform[J].Journal of Southwest University of Science and Technology，2011（2）:70-73.

[3]CHUCK LAM.Hadoop in action[M].Manning，2010

[4]TOM WHITE.Hadoop the definitive guide[M].O'Reilly|Yahoo!PRESS，2009.

[5]崔朝國(guó)，劉志明，李婧，等.一種基于Hadoop的Scool云存儲(chǔ)平臺(tái)[J].電腦知識(shí)與技術(shù)，2013（2）:405-408，411.CUI Chao-guo，LIU Zhi-ming，LI Jing，et al.A scool cloud storage platform based on the hadoop[J].Computer Knowledge and Technology，2013（2）:405-408，411.

[6]多雪松，張晶，高強(qiáng).基于Hadoop的海量數(shù)據(jù)管理系統(tǒng)[J].微計(jì)算機(jī)信息，2010（13）:202-204.DUO Xue-song，ZHANG Jing，GAO Qiang.A mass data management system based on the hadoop[J].Microcomputer Information，2010（13）:202-204.

[7]趙慶.基于Hadoop平臺(tái)下的Canopy-Kmeans高效算法[J].電子科技，2014（2）:29-31.ZHAO Qing.Canopy-Kmeans efficient algorithm based on Hadoop platform [J].Electronic Science and Technology，2014（2）:29-31.