程付超,苗 放,2,陳 墾
(1.成都理工大學(xué) 地球探測與信息技術(shù)教育部重點實驗室,四川 成都610059;2.成都理工大學(xué) 地質(zhì)災(zāi)害防治與地質(zhì)環(huán)境保護國家重點實驗室,四川 成都610059)
目前,對于海量遙感影像的邊緣提取,通常采用的方法是 通 過MPI (message passing interface)進 行 并 行 編程[1],實現(xiàn)基于集群的邊緣提取并行處理。但是,由于MPI環(huán)境的構(gòu)建和編程難度較大,限制了其發(fā)展和應(yīng)用。Hadoop MapReduce計算模型具有較好的易用性,但其本身并不支持影像數(shù)據(jù)的計算與處理,需要對影像數(shù)據(jù)集的劃分方法及其相關(guān)接口進行設(shè)計和實現(xiàn)[2]?,F(xiàn)有基于Hadoop的遙感影像分布式計算方法中,數(shù)據(jù)集劃分缺乏對影像數(shù)據(jù)特征的充分考慮[3-5],往往采用單層平均分割[6],直接將影像數(shù)據(jù)按照固定粒度分為多個影像塊,某些影像特征被分割到多個影像塊中,造成影像特征丟失,影響計算結(jié)果的完整性。
為了解決這個問題,需要引入遙感影像組織技術(shù)作為分布式計算的數(shù)據(jù)集劃分算法。但現(xiàn)有技術(shù)中,剖分影像金字塔[7]主要針對影像的顯示和存儲進行設(shè)計,采用四叉樹分割,影像層級較多,不適用于分布式計算;廣義影像金字塔[8]主要面向云存儲進行設(shè)計,生成算法較為復(fù)雜,也不完全適用于分布式邊緣提取計算;文獻 [9]中提出一種并行處理機制,需要在數(shù)據(jù)預(yù)處理階段對提取的目標對象的最小矩形進行計算,其實質(zhì)上還是一種單層分割,仍存在特征丟失問題;其它一些遙感影像組織方式,如球面剖分模型[10]和文獻 [11]中提到的分布式遙感影像組織方法都具有類似的問題;而且,上述方法都需要在計算前將數(shù)據(jù)分塊單獨儲存并進行分發(fā),數(shù)據(jù)遷移量較大,不符合目前大數(shù)據(jù)計算中 “計算推向數(shù)據(jù)”[12]的思想。
針對現(xiàn)有計算方法在數(shù)據(jù)集劃分方法上存在的不足,本文提出了一種多層冗余的遙感影像數(shù)據(jù)集剖分模型——彈性影像金字塔 (resilient image pyramid,RIP),該模型按照預(yù)設(shè)的分辨率倍率將原始影像劃分為多個影像層級,并對每層影像數(shù)據(jù)按照一定的粒度進行正方形剖分,將其劃分為多個影像分區(qū) (Region),從而將原始影像數(shù)據(jù)劃分為多層冗余的組織結(jié)構(gòu),保證原始影像特征的完整性。同時,RIP通過原始像素坐標對影像分區(qū)進行索引,將影像金字塔以關(guān)鍵元數(shù)據(jù)的形式存儲,減少了計算中的數(shù)據(jù)遷移量。
在RIP基礎(chǔ)上,根據(jù)相關(guān)項目中海量遙感影像邊緣提取的實際需求,本文設(shè)計并實現(xiàn)了一種適用于海量遙感影像邊緣提取的MapReduce計算方法,將影像數(shù)據(jù)封裝為Key-Value格式,通過Hadoop把計算任務(wù)和RIP的關(guān)鍵元數(shù)據(jù)分發(fā)到具有相應(yīng)資源的計算節(jié)點上,各節(jié)點按照關(guān)鍵元數(shù)據(jù)生成影像分區(qū)并進行邊緣提取,最后采用一種面向空間面實體的簡單密度聚類算法實現(xiàn)冗余結(jié)果的歸并。在實驗分析中,采用本文計算方法對多幅嫦娥影像進行了月坑提取,提取率相比使用現(xiàn)有方法分別提升了12.25%、9.29%和20.14%,而增加的時耗始終維持在5%以下。
彈性影像金字塔 (RIP)是一種面向MapReduce計算的多分辨率層次影像模型,其影像層級結(jié)構(gòu)是彈性可調(diào)整的,可以靈活的控制影像分層策略,實現(xiàn)影像金字塔的按需構(gòu)建。
在彈性影像金字塔中,會按照預(yù)設(shè)的分辨率倍率將原始影像劃分為多個影像層級,并對每層影像數(shù)據(jù)按照一定的粒度進行正方形剖分,從而將原始影像數(shù)據(jù)劃分為多個影像分區(qū) (Region)。構(gòu)建RIP的關(guān)鍵在于其分層策略和分區(qū)方法,如圖1所示。1.1.1 RIP的分層策略
分層策略用于確定RIP 的層級數(shù)量和每一層數(shù)據(jù)的像素大小。構(gòu)建RIP首先需要對分辨率倍率進行設(shè)定,并按照倍率對原始影像進行多次重采樣,從而形成多個分辨率層次的影像金字塔結(jié)構(gòu)。從金字塔的底層開始,影像分辨率逐層降低,數(shù)據(jù)量也逐層減少,當(dāng)某層影像的數(shù)據(jù)量小于等于一個影像分區(qū)粒度時,則結(jié)束分層,具體算法如下。
圖1 彈性影像金字塔的結(jié)構(gòu)
算法1:(RIP分層算法)
(1)設(shè)定相鄰影像間的分辨率倍率T
其中,ResH為相鄰兩層影像中的較高分辨率,ResL為較低分辨率,因此T 應(yīng)該大于等于1。
(2)使用原始影像數(shù)據(jù)作為金字塔第0層數(shù)據(jù),令其像素大小為WO·HO。
(3)計算第L 層 (L>0)的影像的分辨率倍率TL
(4)計算第L 層影像的像素大小WL·HL
(5)計算第L 層影像的數(shù)據(jù)量QL
式中:DC——影像的色深。
(6)若第L 層影像數(shù)據(jù)量QL大于一個影像分區(qū)粒度,返回第 (2)步,計算第L+1層;否則,終止分層,金字塔層級數(shù)量為L。
1.1.2 影像的分區(qū)方法
影像的分區(qū)方法主要用于確定金字塔某一層的影像分區(qū)數(shù)量。在對一層影像數(shù)據(jù)進行分區(qū)時,需要考慮計算效率和I/O 效率兩方面因素:①在MapReduce計算中,為了提高計算效率,需要減少影像分區(qū)數(shù)量;②另一方面,由于計算的輸入數(shù)據(jù)和結(jié)果數(shù)據(jù)等都需要通過HDFS進行存儲,影像分區(qū)大小還應(yīng)該與HDFS的數(shù)據(jù)分片方式相兼容。因此,在RIP中采用了基于大粒度的影像分區(qū)方式,分區(qū)粒度默認為64MB,還可擴展到128MB 或更大粒度。令分區(qū)粒度為QR,影像色深為DC,設(shè)影像分區(qū)的像素寬度為SR,則影像分區(qū)的像素大小為S2R
在剖分過程中,如果存在不足S2R像素的 “尾塊”,應(yīng)對其進行補足。
1.2.1 基于原始像素坐標的影像分區(qū)索引方法
傳統(tǒng)的影像金字塔模型一般采用可遞歸的空間填充曲線對影像分塊進行編碼,其目的是為了提高空間檢索效率。在分布式特征提取計算中,每個影像分區(qū)是被獨立計算的,關(guān)注點集中在不同層級影像分區(qū)的重疊和冗余問題。因此,本文采用了一種基于原始影像像素坐標的影像分區(qū)索引方法。RIP中的影像層是原始影像通過一定的降采樣處理后形成的,各影像層中的像素能夠按照一定的算法映射到原始影像的對應(yīng)像素上。對原始影像的像素坐標描述形式進行約定后,即可以用來描述來自不同層次的影像分區(qū)的幅面范圍,從而判斷各影像分區(qū)的重疊和冗余情況,為MapReduce計算中的結(jié)果歸并提供依據(jù)。
RIP中約定原始像素的左上點為坐標原點,各影像分區(qū)坐標可通過數(shù)組RID進行描述
其中,(LTPX,LTPY)和 (RBPX,RBPY)分別表示分區(qū)左上點和右下點對應(yīng)于原始影像的像素坐標,如圖2所示。第L 層影像的分區(qū)坐標計算方法如下
其中,RNo是影像分區(qū)在該層影像中的序號,按照行掃描的方法進行計算。NHL是第L 層影像中橫向的影像分區(qū)個數(shù)。令該層影像像素大小為WL·HL,則
SRO是第L 層影像分區(qū)對應(yīng)的原始影像區(qū)域的像素寬度
由于RIP中不可能存在內(nèi)容完全相同的兩個影像分區(qū),因此可以采用RID作為影像分區(qū)的唯一標識符。同時,通過對比不同影像分區(qū)的LTPX、LTPY、RBPX和RBPY數(shù)值,可以較快的確定分區(qū)間的相交和重疊關(guān)系。
圖2 像素坐標的映射
1.2.2 基于關(guān)鍵元數(shù)據(jù)的影像分區(qū)存儲方法
RIP并不對每個影像分區(qū)的數(shù)據(jù)內(nèi)容進行單獨存儲,而只存儲構(gòu)建RIP所必須的關(guān)鍵元數(shù)據(jù)。在進行分布式計算的時候,計算任務(wù)和元數(shù)據(jù)被分發(fā)到存儲有相應(yīng)資源數(shù)據(jù)的節(jié)點上,計算節(jié)點可以通過元數(shù)據(jù)較快速的生成所需的影像分區(qū)數(shù)據(jù),從而減少了數(shù)據(jù)傳輸過程中的網(wǎng)絡(luò)帶寬、流量和時空開銷。構(gòu)建RIP的關(guān)鍵元數(shù)據(jù)包括基礎(chǔ)元數(shù)據(jù)、層級元數(shù)據(jù)和分區(qū)元數(shù)據(jù)3類,見表1。
表1 構(gòu)建RIP的關(guān)鍵元數(shù)據(jù)
遙感影像是一種非結(jié)構(gòu)化數(shù)據(jù),不能像結(jié)構(gòu)化數(shù)據(jù)那樣直接轉(zhuǎn)化成Key-Value格式。本文采用的方法是以RIP中的一個影像分區(qū)為一個Value,并以影像分區(qū)的RID值為Key,建立Key-Value映射關(guān)系。對于計算的中間結(jié)果,同樣按照這種思路進行處理,也使用RID作為Key,將其封裝為Key-Value格式。這種方法的優(yōu)點在于,每個Value都有且只有一個與之對應(yīng)的Key值,能夠確保輸入數(shù)據(jù)和中間結(jié)果數(shù)據(jù)在整個計算過程中都是可標識的。同時,一個Key-Value就是一個完整的輸入數(shù)據(jù)塊,簡化了計算中的Map過程。
基于RIP 的影像邊緣提取主要包括數(shù)據(jù)集劃分(Splite)、分布式處理 (Process)和結(jié)果歸并 (Cluster)這3個過程,具體步驟及其與Hadoop MapReduce框架的關(guān)系如圖3所示。
(1)數(shù)據(jù)集分割。按照RIP的構(gòu)建方式,對原始影像數(shù)據(jù)進行分割,計算其關(guān)鍵元數(shù)據(jù),并將計算任務(wù)和RIP的關(guān)鍵元數(shù)據(jù)以XML格式提交給Hadoop中的JobTracker。
圖3 基于RIP的影像邊緣提取方法
(2)分布式處理。JobTracker將計算任務(wù)和相關(guān)影像分區(qū)元數(shù)據(jù)分發(fā)給各個TaskTracker;Task-Tracker根據(jù)元數(shù)據(jù)去HDFS中實時獲取影像分區(qū),并按照用戶編寫的算法對其進行邊緣提取處理;處理后得到的中間結(jié)果被緩存到本地,作為輸入數(shù)據(jù)提供給后續(xù)歸并計算使用。
(3)結(jié)果歸并。通過RID可以判斷各層級不同影像分區(qū)之間的重疊關(guān)系,從而將中間結(jié)果分為多個可能存在冗余的結(jié)果集,對同一結(jié)果集內(nèi)的數(shù)據(jù)進行聚類分析,發(fā)現(xiàn)冗余結(jié)果并將之刪除。
對于重復(fù)的中間結(jié)果,本文采用了一種較為簡單的算法進行聚類分析,即以中間結(jié)果中空間面實體的幾何形心距離和面積差值為距離度量,采用DBSCAN 算法進行密度聚類。
(1)距離度量
1)幾何形心距離
其中,cA和cB分別為空間面實體A 和B 的形心坐標,該坐標是將提取出的空間面實體映射到原始影像相應(yīng)位置后計算出的像素坐標。幾何形心距離通過不同空間面實體形心坐標的像素偏移量進行衡量。
2)面積差值距離
其中,aA和aB為空間面實體A 和B 的像素面積,該面積值同樣是映射到原始影像上計算的,以保證不同層級結(jié)果的面積單位是一致的。面積差值距離通過不同實體間面積的像素差值來進行衡量。
(2)輸入輸出
輸入包含n個空間面實體的數(shù)據(jù)集,幾何形心距離鄰近域半徑ec,面積差值距離鄰近域半徑ead,核心實體鄰近域內(nèi) (同時滿足ec和ead)的最少實體數(shù)目MinPts;輸出k個滿足密度條件的空間面實體簇。
(3)算法流程
算法2:(面向空間面實體的簡單密度聚類算法,其流程如圖4所示。)
圖4 密度聚類算法流程
本文在CentOS 6.2環(huán)境下使用Java語言開發(fā)了一個驗證系統(tǒng),使用的Hadoop版本為0.20.205,部署在一個控制節(jié)點,3個計算節(jié)點的實驗集群上,節(jié)點之間通過千兆網(wǎng)卡連接。實驗所用的服務(wù)器主要參數(shù)指標為:Intel Xeon E3-1230 3.2GHz、內(nèi)存8GB DDR3、硬盤1TB SATA。實驗過程中采用基于Sobel算子的圓形構(gòu)造提取算法,在月球遙感影像上進行撞擊坑提取,該算法在月球中高緯度地區(qū)的提取準確率能夠達到78%~80%。本文實驗分為參數(shù)優(yōu)化實驗和性能分析實驗,前者通過小數(shù)據(jù)量實驗,與單機處理結(jié)果對比,優(yōu)化本文方法中的各參數(shù)取值;后者采用大數(shù)據(jù)量的實驗數(shù)據(jù),與現(xiàn)有的影像單層分割的分布式邊緣提取方法進行對比,分析本文方法的效果和性能。
在RIP的構(gòu)建和分布式邊緣提取中,對處理結(jié)果存在較大影響的參數(shù)有4個,見表2。本實驗首先以單臺服務(wù)器進行月坑提取,并以此結(jié)果為依據(jù),設(shè)計對照組實驗,對各參數(shù)進行優(yōu)化。實驗數(shù)據(jù)選用嫦娥一號月球影像數(shù)據(jù),影像范圍-14°44′26.16″~29°43′35.79″N,-27°14′24.25″~16°55′21.83″E,數(shù)據(jù)量約700M,如圖5 (a)所示。
表2 待優(yōu)化參數(shù)
經(jīng)實際測試,采用單臺服務(wù)器提取得到月坑數(shù)量為139217個。為了模擬實際應(yīng)用中高分辨率影像數(shù)據(jù)量大,影像分區(qū)較多的情況,對照實驗中將影像分區(qū)粒度設(shè)為1M,以保證參數(shù)優(yōu)化的準確性。
圖5 實驗數(shù)據(jù)
3.1.1 對照實驗一——RIP分層策略實驗
本實驗針對構(gòu)建RIP時參數(shù)T 的選擇問題,在其余參數(shù)取默認值的情況下,測試不同的T 值對提取結(jié)果的影響,實驗結(jié)果見表3??梢钥闯觯S著T 取值的增加,處理時耗呈降低的趨勢,這是由于需要處理的數(shù)據(jù)量逐漸減少。本實驗中提取效果受其余參數(shù)的影響,提取率與單機提取還有較大差距,但從總體趨勢上看,T 取值 [2,5]區(qū)間的提取效果較佳。綜合性能和效果兩方面因素,T 較佳的取值區(qū)間是 [4,5]。
3.1.2 對照實驗二——聚類算法實驗
本實驗針對結(jié)果聚類中相關(guān)參數(shù)的取值問題,保持T取值5,實驗不同參數(shù)組合對提取結(jié)果的影響,結(jié)果見表4,具體分析如下:
(1)從序號為1、2、3、4的列可以看出,當(dāng)ec取值過小時,會遺漏部分冗余結(jié)果,造成提取的月坑數(shù)量過多;當(dāng)ec值過大時,又會將部分位置較為接近的月坑誤判為冗余結(jié)果,造成輸出數(shù)據(jù)減少。從結(jié)果看,ec較為合適的取值大小為20左右。
(2)從1、5、6、7、8列可以看到,ead取值對結(jié)果的影像變化趨勢與ec類似,取值過小,輸出增加,取值過大,輸出減少,較為合適的ead值為50左右。
(3)從7、9、10這3列看,MinPts取值1較為合適,原因在于實驗中T 值為5,各層影像間的分辨率差別較大,某些中小型月坑只能在兩到三層影像中提取到,無法滿足MinPts條件,導(dǎo)致冗余結(jié)果未被處理。
從兩次對照實驗的結(jié)果可以看出,本文所述的分布式邊緣提取處理方法在采用T=5,ec=20,ead=50,MinPts=1的參數(shù)設(shè)置時,提取效果與單機實驗結(jié)果較為接近。
表3 RIP分層策略實驗結(jié)果
表4 聚類算法實驗結(jié)果
本實驗分別采用基于RIP 的影像邊緣提取方法與現(xiàn)有基于單層分割的方法進行對比測試,分析本文方法在保障結(jié)果完整性方面的效果。實驗數(shù)據(jù)采用嫦娥二號月球影像數(shù)據(jù),為了測試在不同復(fù)雜度影像狀態(tài)下本文方法的表現(xiàn),選取了3塊數(shù)據(jù)進行實驗,如圖5 (b)-(d),經(jīng)緯度范圍見表5。
實驗中,各參數(shù)按照優(yōu)化結(jié)果進行設(shè)置,影像分區(qū)粒度設(shè)為64M。為了減少提取算法本身的誤差,本實驗只對原始影像中直徑大于143像素 (約等于1000米)的撞擊坑進行統(tǒng)計。實驗結(jié)果見表6,雖然提取算法的不穩(wěn)定性導(dǎo)致提取結(jié)果出現(xiàn)了一定的波動,但從均值可以看出由于影像復(fù)雜程度不同,結(jié)果也有所不同。在3次實驗中,與現(xiàn)有方法相比,采用本文方法進行月坑提取使結(jié)果數(shù)量得到了不同程度的提升,分別為12.25%、9.29%和20.14%,而增加的時耗始終維持在5%以下。這一結(jié)果表明,本文方法由于采用了RIP進行數(shù)據(jù)集劃分,對于在分布式邊緣提取計算中提高結(jié)果集完整性具有較好的效果。
表5 性能分析實驗數(shù)據(jù)
表6 性能分析實驗結(jié)果
本文針對現(xiàn)有計算框架在數(shù)據(jù)集劃分方法上存在的不足,重點論述了RIP 的構(gòu)建、索引和存儲,提出并實現(xiàn)了一種面向海量遙感影像的邊緣提取MapReduce計算方法。實驗分析結(jié)果表明,采用本文計算方法進行遙感影像分布式邊緣提取,相比使用傳統(tǒng)平均分割數(shù)據(jù)集的方法,在不同影像復(fù)雜度的提取率分別提升了12.25%、9.29%和20.14%,而增加的時耗始終維持在5%以下。下一步的研究將集中在如何對RIP及其分布式計算方法中的相關(guān)參數(shù)進行更進一步地優(yōu)化,并將其推廣到遙感影像處理的其它領(lǐng)域。
[1]SHEN Zhanfeng,LUO Jiancheng,CHEN Qiuxiao,et al.High-efficiency remotely sensed image parallel processing method study based on MPI[J].Journal of Image and Graphics,2007,12 (12):2132-2136 (in Chinese).[沈占鋒,駱劍承,陳秋曉,等.基于MPI的遙感影像高效能并行處理方法研究[J].中國圖象圖形學(xué)報,2007,12 (12):2132-2136.]
[2]HUO Shumin.Research of the key technologies of management of massive image data based on Hadoop[D].Changsha:National University of Defense Technology,2010 (in Chinese).[霍樹民.基于Hadoop 的海量影像數(shù)據(jù)管理關(guān)鍵技術(shù)研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2010.]
[3]CHEN Weiwei,WU Haijia,XU Guanghui.Optimization model of file partition in distributed storage environment[J].Journal of PLA University of Science and Technology (Natural Science Edition),2010,11 (4):413-416 (in Chinese).[陳衛(wèi)衛(wèi),吳海佳,胥光輝.分布式存儲中文件分割的最優(yōu)化模型 [J].解放軍理工大學(xué)學(xué)報 (自然科學(xué)版),2010,11(4):413-416.]
[4]XUE Shengjun,LIU Yin.Establishment and test of meteorological data warehouse based on Hadoop [J].Computer Measurement & Control,2012,20 (4):926-928 (in Chinese).[薛勝軍,劉寅.基于Hadoop的氣象信息數(shù)據(jù)倉庫建立與 測 試 [J].計 算 機 測 量 與 控 制,2012,20 (4):926-928.]
[5]WANG Xudong.Distributed file system management technology research based on the massive remote sensing image data[D].Lanzhou:Lanzhou Jiaotong University,2012 (in Chinese).[王旭東.面向海量遙感影像數(shù)據(jù)的分布式文件系統(tǒng)管理技術(shù)研究 [D].蘭州:蘭州交通大學(xué),2012.]
[6]KANG Junfeng.Technologies of storage and efficient management on cloud computing for high resolution remote sensing image[D].Hangzhou:Zhejiang University,2011 (in Chinese).[康俊鋒.云計算環(huán)境下高分辨率遙感影像存儲與高效管理技術(shù)研究 [D].杭州:浙江大學(xué),2011.]
[7]CHENG Chengqi,ZHANG Endong,WAN Yuanwei,et al.Research on remote sensing image subdivision pyramid [J].Geography and Geo-Information Science,2010,26 (1):19-23 (in Chinese).[程承旗,張恩東,萬元嵬,等.遙感影像剖分金字塔研究 [J].地理與地理信息科學(xué),2010,26 (1):19-23.]
[8]XIA Yubin,LIU Fengtao.Generalized image pyramid and coding method-oriented cloud computing[J].Journal of Huazhong University of Science and Technology (Natural Science Edition),2012 (S1):22-25 (in Chinese). [夏榆濱,劉豐滔.面向云計算的廣義影像金字塔與編碼方法 [J].華中科技大學(xué)學(xué)報(自然科學(xué)版),2012 (S1):22-25.]
[9]ZENG Zhi,LIU Renyi,LI Xiantao,et al.A mechanism of remote sensing image for parallel processing base on splitting blocks[J].Journal of Zhejiang University (Science Edition),2012,39 (2):225-230 (in Chinese).[曾志,劉仁義,李先濤,等.一種基于分塊的遙感影像并行處理機制 [J].浙江大學(xué)學(xué)報 (理學(xué)版),2012,39 (2):225-230.]
[10]LV Xuefeng,CHENG Chengqi,GUAN Li.Framework and encoding analysis of global subdivision grid [J].Science of Surveying and Mapping,2011,36 (3):11-14 (in Chinese).[呂雪鋒,程承旗,關(guān)麗.球面剖分模型的架構(gòu)與編碼分析[J].測繪科學(xué),2011,36 (3):11-14.]
[11]CHEN Tianqing,XIE Jiancang,LI Jianxun,et al.Organization and schedule of remote sensing images under distributed environment[J].Computer Engineering,2010,36 (23):9-12 (in Chinese).[陳田慶,解建倉,李建勛,等.分布式環(huán)境下的遙感影像組織與調(diào)度[J].計算機工程,2010,36 (23):9-12.]
[12]QIN Xiongpai,WANG Huiju,DU Xiaoyong,et al.Big data analysis-competition and symbiosis of RDBMS and MapReduce[J].Journal of Software,2012,23 (1):32-45 (in Chinese). [覃雄派,王會舉,杜小勇,等.大數(shù)據(jù)分析—RDBMS與MapReduce的競爭與共生 [J].軟件學(xué)報,2012,23(1):32-45.]