基于MapReduce數字圖像處理研究

田進華，張韌志

（黃淮學院 河南 駐馬店 463000）

以互聯網為計算平臺的云計算，將會涉及非常多的海量數據處理任務[1]，海量數據處理是指對大規模數據的計算和分析，通常數據規模可以達到TB甚至PB級別。當今世界最流行的海量數據處理可以說是MapReduce編程模式。MapReduce分布式編程模型允許用戶在不了解分布式系統底層實現細節的情況下開發并行應用程序。用戶可以利用Hadoop輕松地組織計算機資源，進而搭建自己的分布式計算云平臺，并且可以充分利用集群的計算和存儲能力，完成海量數據的處理。

1 Map Reduce計算模型

Hadoop是一個開源分布式計算平臺。以分布式文件系統HDFS和MapReduce為核心的分布式計算和分布式存儲的編程環境[2]。MapReduce是用于大規模數據集分布式的計算模型，實現一個MapReduce應用，首先，通過Map程序將數據切割成小塊，然后，分配給大量服務器處理，最后，通過Reduce程序將處理后的結果匯整輸出給客戶端。MapReduce的整個架構是由Map和Reduce函數組成，當程序輸入一大組Key/Value鍵值對時，Map負責根據輸入的Key/Value（鍵值）對，生成中間結果，這生成中間結果同樣采用Key/Value（鍵值）對的形式。開發者只需要實現Map和Reduce函數的邏輯，然后提交給MapReduce運行環境，計算任務便會在大量計算機組成的集群上被自動、并行地調度執行。MapReduce的運行環境是有兩個不同類型的節點組成:Master和Worker。Worker負責數據處理，Master主要負責任務分配和節點之間數據共享。需要實現或指定以下編程接口：

Map 函數：接收輸入的鍵值對＜kl，vl＞，計算生成一組中間的鍵值對＜k2，v2＞

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

Combiner函數：它是對Map函數輸出的中間數據在本地執行歸并，將處理結果再傳輸給Reduce節點。Combiner可以降低Map任務節點和Reduce任務節點之間的通信代價。

InputFormat，OutputFormat：InputFormat 支 持 Hadoop 作業輸入數據鍵值對的轉換；OutputFormat表示Hadoop作業計算結果存儲在HDFS中的格式。

Partitioner函數：用于對Map函數輸出的中間結果進行劃分，Map任務點根據所提供的Partition函數，將數據結果劃分給相應Reduce任務節點。

Hadoop運行MapReduce作業的流程圖如圖1所示。MapReduce作業包含四個相對獨立的模塊。客戶端主要負責MapReduce作業代碼的編寫，配置作業相關參數，向JobClient實體提交作業；JobTracker節點主要負責用戶提交作業的初始化，調度作業，與所有的TaskTracker節點進行通信，協調用戶提交作業的執行；TaskTracker節點負責自主與JobTracker節點進行通信，根據所分配的數據塊執行Map或Reduce任務，調用用戶定義的Map或Reduce函數；HDFS負責保存作業的數據、配置信息和作業結果等。

圖1 Hadoop運行MapReduce作業流程圖Fig.1 MapReduce job’s flow chart on Hadoop

2 構建圖像處理云平臺

在MapReduce計算框架中，Hadoop將輸入數據劃分成等長的作業分片，每個Map任務處理一個作業分片，這些Map任務是并行執行的[3]。Hadoop又將每個作業分片劃分為多個相同的鍵值對，每個Map任務對該分片中每個鍵值對再調用map函數來進行處理。本系統把一個圖像文件作為一個作業分片，再把整個作業分片作為一個鍵值對來處理[4]。這樣每個Map任務只需調用一次map函數來處理一個圖像文件，進而實現多個圖像文件的并行化處理。本系統只定義了一個Reduce任務，其調用reduce函數對每個鍵值對進行簡單的輸出操作。

1）鍵值對類型的設計

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

WritableComparator是對繼承自WritableComparable類的RawComparator類的一個通用實現，提供了兩個主要功能：第一，對原始compare（）方法的默認實現，能反序列化將在流中進行比較的對象，并調用對象的compare（）方法；第二，充當的是RawComparator實例的工廠。Hadoop自帶的org.apache.hadoop.io包中有廣泛的Writable類，它們形成了如圖2所示的層次結構。

圖2 Writable類層次結構圖Fig.2 Writable class's hierarchical structure

本系統使用的鍵類型為Text，用來存儲圖像文件的名；值類型為Image，實現了Writable接口，用來存儲圖像文件的內容。本系統的鍵值對在Map任務和Reduce任務數據變化流程如圖3所示。任務調用map函數對每個鍵值對進行處理，處理前后鍵Filename的內容不會發生改變，而存儲圖像信息的值Image的內容會發生變化。Reduce任務調用reduce函數實現對其輸入的鍵值對進行簡單的鍵值對輸出操作。

圖3 本系統Map任務和Reduce任務數據流Fig.3 Map task and reduce task’s data flow in this system Map

2）作業的輸入格式設計

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

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）作業的輸出格式設計

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

4）圖像處理功能

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

對數字圖像的邊緣檢測是進行圖像分割、目標區域識別、區域形狀提取等圖像分析的技術基礎。對于連續圖像f（x，y），邊緣檢測就是求梯度的局部最大值和方向。利用Canny邊緣檢測算子，在map函數中實現對圖像的邊緣檢測，從而實現對圖像文件的并行化邊緣檢測。邊緣檢測步驟如下：

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

5）MapReduce程序的編寫

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

3 結束語

Hadoop[7]云平臺的圖像處理系統設計，把一個圖像文件作為一個作業分片，再把整個作業分片作為一個鍵值對來處理。這樣每個Map任務只需調用一次map函數來處理一個圖像文件，進而實現多個圖像文件的并行化處理。節點可以自由地擴充，通過鍵值對的設計、作業的輸入與輸出格式的設計，可以實現海量圖像文件信息的并行化處理。整個云平臺提供的計算和存儲能力近乎是無限的。隨著圖像文件量的增加，MapReduce處理數據的最佳速度最好與數據在云平臺中的傳輸速度相同，系統的利用率會有隨之提高。

[1]劉鵬.云計算[M].2版.北京:電子工業出版社，2011.

[2]朱義明.基于Hadoop平臺的圖像分類[J].西南科技大學學報，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]崔朝國，劉志明，李婧，等.一種基于Hadoop的Scool云存儲平臺[J].電腦知識與技術，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]多雪松，張晶，高強.基于Hadoop的海量數據管理系統[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平臺下的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.