基于Hadoop集群的Sobel邊緣檢測

徐昌榮， 王聰穎

（江西理工大學(xué)建筑與測繪工程學(xué)院，江西贛州341000）

0 引 言

空間數(shù)據(jù)獲取方式在技術(shù)上的進步，特別是傳感器技術(shù)領(lǐng)域的革命，使得遙感影像數(shù)據(jù)量空前增長[1-2]；加之地理信息系統(tǒng)作為一種決策支持系統(tǒng)，已經(jīng)越來越廣泛的滲入生產(chǎn)中的各個環(huán)節(jié)， 所以，從遙感影像中提取信息以輔助決策，成為生產(chǎn)實踐中的重要環(huán)節(jié).

索貝爾邊緣檢測算子 （Sobel edges detection operator） 用于運算圖像亮度函數(shù)的梯度近似值[3]，從而提取特征地物的邊緣信息. 傳統(tǒng)的方法是通過數(shù)學(xué)形態(tài)的變化來得到遙感影像的二值化圖像，然后確定合適的闕值，就可以提取出邊緣二值化的影像. 但是對于海量高分辨率遙感影像的索貝爾邊緣提取，單機環(huán)境下完成該運算所耗時間太多[4].然而，Google MapReduce[5-8]并行編程框架的提出，卻能解決海量遙感影像信息提取方面較為費時的難題. 不僅可以在多個節(jié)點上并行完成各節(jié)點的運算，達到處理海量數(shù)據(jù)的效果，還可以極大地縮短各節(jié)點上影像邊緣提取的時間[7].

1 相關(guān)技術(shù)

1.1 MapReduce 并行計算模型

MapReduce 并行編程框架的核心是Map 和Reduce 函數(shù)， 輸入和輸出數(shù)據(jù)都被約束成為＜key,value＞對的形式[7]. 用戶程序通過調(diào)用MapReduce 庫函數(shù)將輸入文件分割成（M+1）個數(shù)據(jù)分片，經(jīng)由（M+1）個節(jié)點上的（M+1）個Map 任務(wù)并行運算之后，把輸出以中間＜key, value＞對的形式寫入HDFS(Hadoop Distributed File System)[9-10]中. Map 的所有輸出被輸入給每個Reduce 之前， 用戶可以選擇性的編寫Shuffle 和Sort 程序， 使得Map 輸出更加有秩序以便于Reduce 函數(shù)的執(zhí)行. 經(jīng)過Shuffle 程序處理后的輸出文件被分配給（R+1）個Reduce 任務(wù)來執(zhí)行，Reduce 合并計算結(jié)果并輸出所求，整個過程如圖1 所示.

1.2 Sobel 邊緣檢測算子

Sobel 算子是一階微分算子， 通過計算影像中每一個像素的梯度值， 依據(jù)閾值大小來取舍像素點，進而完成邊緣檢測與圖像增強[3,11-13]. 算法如下：

圖1 MapReduce 執(zhí)行過程示意圖

（1） 使用3×3 高斯濾波器對圖像濾波；

（2） 按照式（1）所示，計算圖像中每個像素點的梯度值M，

其中A 表示原始圖像；

（3） 根據(jù)設(shè)定好的閾值，保留梯度大于閾值的像素點，而把梯度小于閾值的像素點設(shè)置為零.

為提高效率，可將不開方的近似值來代替式(1)中的梯度值，也就是以式（6）的計算結(jié)果作為每一像元的灰度值.

2 并行索貝爾邊緣檢測

為了使海量影像能夠在Hadoop[9-10,14]環(huán)境中的多個節(jié)點上并行處理，本文通過把同一時刻的整幅影像作為一個輸入文件分配給一個Map 任務(wù)來實現(xiàn). 為此，需要修改Hadoop 源碼.

2.1 修改Hadoop 源碼

在MapReduce 框架中， 每個Map 任務(wù)處理的數(shù)據(jù)量和讀取的輸入文件類型等信息由InputFormat 接口來決定， 該接口包括了下面兩個接口函數(shù)：

InputSplit [] getSplits （JobConf job, int numSplits） throws IOException;

RecordReader ＜K , V ＞ getRecordReader(InputSplit split, JobConf job, Reporter reporter)throws IOExceptions;

其中g(shù)etSplits 函數(shù)根據(jù)輸入文件量和參數(shù)numSplits 的值決定Map 任務(wù)的數(shù)量， 并把文件劃分為InputSplit 數(shù)組. 為實現(xiàn)并行索貝爾濾波算法，需要重載isSplitable 方法， 使其返回值為false，確保輸入整幅影像到一個Map 任務(wù)進行處理.getRecordReader 函數(shù)讀取InputSplit 中的數(shù)據(jù)，以RecordReader 為輸出類型到每個Map 任務(wù)進行并行運算.

Map 任務(wù)中， 本文還構(gòu)建了BufferedImage 和JPEGImageEncoder 兩個類， 以滿足影像數(shù)據(jù)索貝爾濾波并行計算要求. BufferedImage 類用于存儲影像的每個像元坐標(biāo)和灰度值，這樣程序能夠返回影像的像素信息進而進行運算；JPEGImageEncoder類用于把運算結(jié)果以JPEG 格式編碼， 并寫入HDFS 中. 輸入流把原始影像數(shù)據(jù)讀入到Map 任務(wù)中，接著轉(zhuǎn)換成BufferedImage 類進行索貝爾運算，最后以JPEG 格式進行編碼輸出.

2.2 基于MapReduce 的索貝爾邊緣檢測

2.2.1 索貝爾邊緣檢測的算法

對于圖像函數(shù)而言，可用差分式子來近似代替導(dǎo)數(shù)式子，這樣可根據(jù)式（2）和式（3）中的兩個矩陣， 分別計算水平x 方向和豎直y 方向上的差分值，進而求得各像素點的梯度值. 然而卷積模板以三階格網(wǎng)的形式作用于影像陣列，從陣列第一行開始自左向右計算梯度值，到達最右端時再跳轉(zhuǎn)至第二行. 這種模式不能夠計算出影像陣列最后一行與最后一列的梯度值，當(dāng)三階格網(wǎng)的中心置于最后一行（列）時，該格網(wǎng)會超出影像范圍，無法求得最后一行（列）的梯度值，一般的解決辦法是將其近似認為是前一行或前一列的梯度值. 算法步驟如下：

（1）令兩個卷積模板沿著圖像從影像左上角第一個像素依次移動到另一個像素，移動到這一行最后一個像素之后，繼續(xù)轉(zhuǎn)入第二行仍然按同樣的順序移動，每移動一次都要使得模板中心與圖像的某一像素重合；

（3）由式（7）計算每個像素點的梯度值；

（4）確定一個閾值τ，對于G（i， j）＞τ 的像素點，把它確定為邊界并輸出.

2.2.2 基于MapReduce 的索貝爾邊緣檢測算法

MapReduce 并行編程框架中， 通過InputFormat 對象和RecordReader 對象負責(zé)數(shù)據(jù)的輸入任務(wù)， 其中InputFormat 對象用于分割數(shù)據(jù)和把每一數(shù)據(jù)分片轉(zhuǎn)換為輸入數(shù)據(jù)集， 而RecordReader 對象則用于負責(zé)把每一數(shù)據(jù)集指派給每個Mapper 進行運算. 若對遙感影像進行分割為數(shù)據(jù)塊供Map 程序來處理， 勢必影響影像的質(zhì)量，或者導(dǎo)致信息丟失. 為此，文中前述2.1 節(jié)修改了Hadoop 源碼， 目的是使整幅影像可以單獨被一個Mapper 運算，所有影像分配到各個Mapper 中并行運算.

Mapper 任務(wù)中包含了影像索貝爾濾波的算法， 輸入影像經(jīng)Map 階段運算后再把結(jié)果寫回到HDFS 中. 設(shè)定輸入給Mapper 的key 的類型為NullWritable 類型，value 類型為BytesWritable 類型，這能夠保證影像不被分割這個前提，并行索貝爾濾波的輸出影像的鍵值對為＜Text，Text＞.

壓力是一把雙刃劍，它既能摧毀意志，也能激發(fā)斗志。作為一名校長，在學(xué)校實際管理中總會遇到許多壓力，比如安全壓力、升學(xué)壓力等等。如何處理好這些壓力，讓它在學(xué)校發(fā)展中起到作用？我認為，在壓力面前要提前籌謀，尋找科學(xué)穩(wěn)妥的方式才能化壓力為動力。

運算結(jié)果在Map 階段直接寫回HDFS，并且不需要Reducer， 所以輸出鍵值對被設(shè)定為Text 類型，以滿足MapReduce 框架的需求，不代表任何實際意義. 以下給出并行索貝爾邊緣檢測算法的偽代碼.

（1）設(shè)定輸入數(shù)據(jù)和輸出數(shù)據(jù)的路徑；

（2） 設(shè)定輸入數(shù)據(jù)InputFormat 類型為WholeFileInputFormat 類型， 輸出數(shù)據(jù)類型為Text類型；

（3） 輸入影像到Mapper，Mapper 以Bytes Array 類型讀入影像字節(jié)；

（4） 用ImageIO.read 方法讀入源影像；

（5） 創(chuàng)建FileSystem OutputStream 輸出流類型實例，準(zhǔn)備把結(jié)果寫入文件系統(tǒng)；

（6） 按照原始影像的像素高度和寬度，創(chuàng)建輸出影像緩存區(qū)；

（8） 創(chuàng)建BufferedImageOp 實例， 計算影像陣列每一像素點的梯度值，根據(jù)設(shè)定的閾值確定待提取的邊緣；

（9） 應(yīng)用JPEGImageEncoder 類編碼輸出影像為JPEG 格式；

（10） 把輸出影像寫回HDFS 中.

3 實驗結(jié)果與分析

3.1 實驗環(huán)境及實驗數(shù)據(jù)

為驗證并行索貝爾算法執(zhí)行的效率，本文設(shè)計了實驗. 實驗環(huán)境采取搭建于普通PC 機上的Hadoop 集群，節(jié)點數(shù)為12 個，具體實驗平臺參數(shù)表2 所示.

表2 實驗平臺明細

HDFS 和MapReduce 框架都是主從模式，在這12 個節(jié)點中， 采用10 節(jié)點DataNode， 用于HDFS的分布式存儲， 并在每一DataNode 上運行MapReduce 的TaskTracker；剩余兩個節(jié)點，由一個節(jié)點運行HDFS 的NameNode 專門管理分布式存儲，另外一個節(jié)點運行JobTracker 管理MapReduce任務(wù)的分配與協(xié)調(diào).

實驗數(shù)據(jù)采用Landsat 衛(wèi)星全彩色遙感影像，文中搜集到該衛(wèi)星自2002 年開始到2009 年底拍攝的贛州市影像，平均每幅影像大小為548 MB，總數(shù)據(jù)量為240 GB 左右. 在集群運算之前， 需要調(diào)整實驗影像的大小， 以便于有限的Java 堆棧可以順利讀入這些數(shù)據(jù)到Mapper 進行并行處理.

3.2 實驗結(jié)果

文中為測試單機和集群環(huán)境下海量遙感影像的索貝爾邊緣檢測運算的執(zhí)行效率，設(shè)計了兩組實驗：其一，對比隨著影像數(shù)據(jù)量的增加，兩者所耗費運算時間上的差異， 結(jié)果表明相對于單機運算，集群運算時間顯著降低，見圖2；其二，驗證隨著集群節(jié)點數(shù)目的逐漸增加， 系統(tǒng)運算時間的變化規(guī)律，結(jié)果表明運算時間隨著節(jié)點數(shù)目的增加，以近似線性的方式減少，如圖3 所示.

圖2 單機與集群運算對比圖

圖3 運算時間隨節(jié)點數(shù)變化規(guī)律

4 結(jié) 論

海量遙感影像的處理是一種存儲和計算密集型應(yīng)用，現(xiàn)實生產(chǎn)中，對影像的索貝爾濾波計算，單機運算已不能很好的滿足海量柵格運算的需求，本文提出了把運算遷徙到Hadoop 集群上的方法，把單個整幅影像作為一個輸入分配給一個Map 任務(wù)， 來完成海量影像數(shù)據(jù)的并行輸入與并行運算.實驗結(jié)果證明集群環(huán)境顯著縮短了計算時間，并且對于給定的數(shù)據(jù)量，計算時間隨著集群節(jié)點數(shù)目的增加，近似線性減少的規(guī)律.

[1] 李德仁，王樹良，史文中，等. 論空間數(shù)據(jù)挖掘和知識發(fā)現(xiàn)[J]. 武漢大學(xué)學(xué)報，2001，26(6):491-499.

[2] 楊建欽， 周子勇. GeoTIFF 在處理海量遙感圖像中的實現(xiàn)及應(yīng)用[J]. 計算機應(yīng)用，2007(6):434-435.

[3] 王瀚聞，翟涌光，郝 蕾. 基于索貝爾算子的高分辨率遙感影像分割技術(shù)研究[J]. 科技創(chuàng)新導(dǎo)報，2012 (22):18.

[4] 霍樹民. 基于Hadoop 的海量影像數(shù)據(jù)管理關(guān)鍵技術(shù)研究[D]. 長沙:國防科學(xué)技術(shù)大學(xué)，2010.

[5] 李成華，張新訪，金 海，等. MapReduce：新型的分布式并行計算編程模型[J]. 計算機工程與科學(xué)，2011，33(3):129-135.

[6] 覃雄派，王會舉，杜小勇，等.大數(shù)據(jù)分析——RDBMS 與MapReduce的競爭與共生[J].軟件學(xué)報，2012，23(1):32-45.

[7] 李建江，崔 健，王 聃，等. MapReduce 并行編程模型研究綜述[J]. 電子學(xué)報，2011，39(11):2635-2642.

[8] Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.

[9] Shvachko K, Kuang H, Radia S, et al. The hadoop distributed file system[C]//Mass Storage Systems and Technologies (MSST), 2010 IEEE 26th Symposium on. IEEE, 2010: 1-10.

[10] White T. Hadoop: The definitive guide [M]. O'Reilly Media, Inc.,2012.

[11] 張宇偉，王耀明，蔣慧鈞. 一種結(jié)合Sobel 算子和小波變換的圖像邊緣檢測方法[J]. 計算機應(yīng)用與軟件，2007，24(4):133-161.

[12] 袁春蘭，熊宗龍，周春花，等. 基于Sobel 算子的圖像邊緣檢測研究[J]. 激光與紅外，2009，39(1):85-87.

[13] 王麗晶，吳學(xué)峰，關(guān) 雷，等. 淺析沿海區(qū)域衛(wèi)星遙感影像圖像增強技術(shù)研究[J]. 測繪與空間地理信息，2012，35(5):110-113.

[14] Apache. Welcome to Apache Hadoop [EB/OL]. http://hadoop.apache.org/.2012-02-05.