分布式并行遙感圖像處理中的數(shù)據(jù)劃分

文/王玉坤

信息時代背景下，各種復(fù)雜性的應(yīng)用技術(shù)被廣泛應(yīng)用。其中數(shù)據(jù)處理的海量性是大規(guī)模復(fù)雜應(yīng)用系統(tǒng)的特點之一。其中該系統(tǒng)應(yīng)用最為常見的領(lǐng)域是在地球科學(xué)分析上。主要目的是遙感監(jiān)測重大自然災(zāi)害，以便可以在決策系統(tǒng)的參考下，制定對策加以解決。數(shù)學(xué)分析模型在遙感和地理信息系統(tǒng)中的應(yīng)用將遇到不斷膨脹的大型空間數(shù)據(jù)庫。在此背景下，原來傳統(tǒng)順序處理模式已經(jīng)不能滿足當(dāng)前形勢發(fā)展的需求，難以滿足數(shù)據(jù)運算要求。針對目前的情況需要加強對分布式并行遙感圖像處理中數(shù)據(jù)劃分的研究。以便在實現(xiàn)處理技術(shù)高效運行的基礎(chǔ)上，降低原有成本。

1 遙感數(shù)字圖像處理關(guān)鍵技術(shù)特點分析

遙感數(shù)字圖像處理技術(shù)在地球科學(xué)分析領(lǐng)域被廣泛應(yīng)用。作為地球科學(xué)分析領(lǐng)域中關(guān)鍵性技術(shù)之一，具有內(nèi)在并行性的特點。提高實時處理海量數(shù)組圖像系統(tǒng)的實用化需要建立集群分布式并行的微機(jī)、工作站圖像處理系統(tǒng)。其中以下是對該技術(shù)特征分析。首先，較大的計算量。遙感數(shù)字圖像處理技術(shù)具有計算量大的特點。再者，相同的計算形式。除了邊界之外，任何數(shù)據(jù)點上的計算形式是相同的。都是將原有一個區(qū)域分成許多個區(qū)域。這樣的區(qū)域劃分可以將問題轉(zhuǎn)變成許多個小規(guī)模的區(qū)域，形成小區(qū)域子問題。最后，局部的變量間相互作用。我們可以對其按照以下的方式進(jìn)行理解，在計算所有數(shù)據(jù)點時，可以利用小距離內(nèi)鄰近點值。大計算量可以滿足該技術(shù)的客觀需求。相同計算形式的特點和局部變量間相互作用的特點可以滿足并行處理的要求。以上特點共同滿足分布式并行處理的要求。其中共享存儲系統(tǒng)和消息傳遞系統(tǒng)是分布式系統(tǒng)的兩種形式。消息傳遞系統(tǒng)可以在對消息傳遞仔細(xì)設(shè)計下，提高傳遞效率，但是此種形式的傳遞系統(tǒng)編程不簡單，難度較高。共享存儲系統(tǒng)經(jīng)過精心設(shè)計，它的消息傳遞效率與消息傳遞系統(tǒng)存在一定相似性，但是該種系統(tǒng)在編程上較為簡單。因此共享存儲系統(tǒng)在遙感圖像處理領(lǐng)域市場更廣。分布式共享系統(tǒng)存儲系統(tǒng)中。系統(tǒng)完成數(shù)據(jù)之間的傳遞。將處理節(jié)點間的通訊盡可能減小是提高并行分布計算執(zhí)行效率的前提。而要想實現(xiàn)對通訊量的控制，需要利用遙感圖像數(shù)據(jù)進(jìn)行恰當(dāng)?shù)膭澐?。以下是筆者對共享存儲系統(tǒng)中并行遙感圖像處理技術(shù)的分析。

表1：按條帶劃分和按矩形塊劃分的凈通訊量之比

圖1：三種劃分方式下的凈通訊量(以k=4為例)

2 并行遙感圖像處理和數(shù)據(jù)劃分分類

2.1 并行遙感圖像處理分類

域處理和點處理是圖像處理常見的分類方式。但是在筆者看來，此種分類方式存在一定的不合理性?？煞譃辄c處理、線處理和域處理。其中輸入元素中單純涉及一個像素的一類圖像處理稱為點處理。集中在一行或者一列的一類圖像處理中的輸入元素為線處理。集中在一列上的線處理稱為豎直線處理。輸入元素集中在一行上的線處理稱為水平線處理。輸入元素分布在一個矩形區(qū)域內(nèi)的一類圖像處理稱為域處理。針對以上內(nèi)容，我們可以得出域處理包括線處理的內(nèi)容，線處理是域處理中的個例。但是我們在域處理中分出線處理的原因是，一線處理自身帶有的特殊性，方便數(shù)據(jù)劃分分析。二圖像處理中線處理應(yīng)用較為常見，我們可以將域處理劃分為線處理，采用行、列兩個方向的線處理模式。此中轉(zhuǎn)換可并行化這類算法。

圖2：數(shù)據(jù)按結(jié)果圖像平均劃分

2.2 數(shù)據(jù)劃分分類

水平條帶、豎直條帶、矩形塊、不規(guī)則劃分是圖像數(shù)據(jù)劃分四種主要形式。實際中使用最少的為不規(guī)則劃分。而使用較為常見的為水平條帶、豎直條帶、矩形塊劃分。豎直線處理和水平線處理是線處理的兩種情況，因此在數(shù)據(jù)劃分時也需要分類劃分。域處理中不管采用以上四種劃分方式中的任何一種，都會涉及到遠(yuǎn)程數(shù)據(jù)調(diào)用問題，因此劃分方法的選擇需要根據(jù)并行計算支撐環(huán)境來定。

3 分析域處理數(shù)據(jù)劃分的通訊量

3.1 通訊域和數(shù)據(jù)通訊量分析

數(shù)據(jù)通訊量是選擇數(shù)據(jù)劃分的方式依據(jù)。筆者看來凈通訊量和實際通訊量是數(shù)據(jù)通訊量進(jìn)一步細(xì)化的兩種分類方式。并行運算實際需要的數(shù)據(jù)通訊量為凈通訊量。并行運算過程中并行計算支撐環(huán)境實際傳送的數(shù)據(jù)量稱為實際通訊量。而連帶通訊量是指凈通訊量與實際通訊量之差。而人們通常說的通訊量可以包含以上的任何一種。數(shù)據(jù)傳送的分布范圍稱為通訊域，實際通訊域和凈通訊域是通訊域進(jìn)一步劃分的形式表現(xiàn)。

3.2 點處理、線處理和域處理數(shù)據(jù)劃分凈通訊量分析

矩形面積一定時，周長最短的為正方形。當(dāng)k設(shè)為處理機(jī)數(shù)時，k (k≥ 4,且 k的平方根為整數(shù))，m為待處理圖像的長和寬。其中(2×n+1)×(2×n+1)為域處理范圍。假設(shè)n、k比m小(n×k×2

圖1中凈通訊域為陰影部分，水平條帶和豎直條帶是劃分的主要方式。凈通訊量一樣，但是按照矩形塊劃分形成的凈通訊量是非常小的。采用條帶劃分n×m×(k-1)×2像素為凈通訊量。n×m×(sqrt(k)-1)×2×2像素則是按矩形塊劃分成的凈通訊量。經(jīng)過以上凈通訊量的劃分比較，可以確定兩者之間的凈通訊量之比為(k-1)/((sqrt(k)-1)×2)。此外我們要想對按條帶劃分和按矩形塊劃分的凈通訊量進(jìn)行更加清楚的比較，可以采用圖表的方式。見表1。

通過上述圖表可以看出，在處理機(jī)數(shù)不斷增加的基礎(chǔ)上，凈通訊量之比越來越高，這說明按矩形塊劃分優(yōu)于按條帶劃分。消息傳遞系統(tǒng)中，程序員可以對消息傳遞函數(shù)進(jìn)行嚴(yán)格控制的基礎(chǔ)下，將消息傳遞函數(shù)剛好傳送到所需的遠(yuǎn)程數(shù)據(jù)。因此矩形快劃分方式可以優(yōu)先采用。而針對復(fù)雜性的分布式共享存儲系統(tǒng)，由于此種系統(tǒng)情況的復(fù)雜性，需要將實際通訊量考慮進(jìn)去。

3.3 點處理、線處理和域處理實際通訊量分析

為了將應(yīng)用程序員編程的難度降低，在分布式共享存儲系統(tǒng)中，應(yīng)用程序不控制遠(yuǎn)程數(shù)據(jù)傳送，二是字DSM系統(tǒng)下完成。數(shù)據(jù)預(yù)送技術(shù)是DSM系統(tǒng)常采用的方式，數(shù)據(jù)傳送按照頁面為單位。此種情況下，實際通訊量就會遠(yuǎn)遠(yuǎn)大于凈通訊量。

當(dāng)P為頁面大小時，為了更好的方便計算，可以化簡P到以前的像素單位，其他條件一樣。之后我們在對點處理、線處理和域處理三種劃分方式實際通訊量進(jìn)行分析。圖1中連帶通訊域為短線條和實心矩形塊，他們劃分方式為豎直條帶劃分，此時實際通訊量是最大的。

3.3.1 實際通訊量最大的按豎直條帶劃分圖1b所示，將第一條帶和第二條帶之間遠(yuǎn)程數(shù)據(jù)調(diào)用情況進(jìn)行比較分析，其他各條之間大致相同。其中最佳情況為條帶的寬度大于p,實心矩形塊的寬度為(p-n)。此時0為短線條長度，實際通訊量要大于或等于(n+p）×(m-1))×(k-1)×2像素。

3.3.2 實際通訊量最小的按水平條帶劃分

圖1a所示，(p-1)像素是連帶通訊域在最壞的情況，此時實際通訊量應(yīng)小于或等于(n×m+(p-1))×(k-1)×2像 素。(n+ p× (m - 1) ) /(n× m+ ( p - 1) )為上述兩者比值。當(dāng)將一景m=10000的三波段點交叉影像為案例，設(shè)4K 字節(jié)為系統(tǒng)傳遞的頁面大小n = 2,p = 4096 /3≈ 1365。此時按豎直條帶劃分和按水平條帶劃分的實際通訊量的比值比638大。同理將k=4，按矩形塊劃分和按水平條帶劃分的實際通訊量的比值比567大。由此可見水平條帶劃分方式是分布式共享存儲系統(tǒng),域處理的數(shù)據(jù)劃分最先佳采用的方式。

4 進(jìn)一步數(shù)據(jù)劃分分析

以上平均分配的數(shù)據(jù)劃分在圖像增強等卷積運算中是合理的。但是將其放在圖像的幾何糾正等帶有圖像旋轉(zhuǎn)的運算不太適應(yīng)。如圖2所示，將原始圖像旋轉(zhuǎn)一個角度。數(shù)據(jù)在結(jié)果圖像下平均分配，此時結(jié)果圖像空白地方較大，但是空白處的計算量較小。因此第二臺、第三臺處理機(jī)要比第一臺和最后一臺處理機(jī)小大的多，伴隨不斷增加的旋轉(zhuǎn)角度，差異性也不斷增大。差別達(dá)到最大的時刻為旋轉(zhuǎn)角度達(dá)到45度。此時第一臺和最后一臺處理機(jī)運算的非空白區(qū)域只有第二臺和第三臺處理機(jī)的三分之一。

此時差異對系統(tǒng)效率會有影響，因此需要針重新調(diào)整分配任務(wù)，實現(xiàn)動態(tài)負(fù)載平衡。實現(xiàn)方法如下：原圖像四個角點在結(jié)果圖像上的位置按照直接法求出。此時會得到原圖像在結(jié)果圖像上的大致分布范圍的四邊形。各個處理機(jī)上平均分配這些像元。此種方法的特點是可以實現(xiàn)任務(wù)分配的平衡性。當(dāng)原圖像周邊地形起伏較大的情況下，此時原圖像與圖2中的四邊形存在較大差異，需要進(jìn)一步細(xì)致劃分。此時可以在求得原圖像邊界上每個點所在的結(jié)果圖像上位置時采用直接法，以此作為再次劃分依據(jù)。

5 結(jié)語

綜上所述，對數(shù)據(jù)通信量進(jìn)行有效控制是提高遙感圖像數(shù)據(jù)并行分布處理執(zhí)行效率的關(guān)鍵。其中將三種劃分方式分成點處理、線處理和域處理三類可以將并行圖像處理的數(shù)據(jù)劃分分析變得更加清晰。將數(shù)據(jù)通訊量進(jìn)一步劃分為實際通訊量和凈通信量，此時數(shù)據(jù)劃分最佳方式得出。分布式共享存儲系統(tǒng)中，可以不使用到遠(yuǎn)程數(shù)據(jù)，因此可以在點處理、線處理和域處理三種處理方式中任選其中的一種。水平處理需要采用水平條帶劃分，豎直線處理需要采用豎直線條帶劃分；其中按水平條帶劃分方式是域處理的數(shù)據(jù)劃分優(yōu)先選擇的劃分方式，此種數(shù)據(jù)劃分方式可以將實際通訊量減少。再者，有些圖像幾何糾正等帶有圖像旋轉(zhuǎn)運算問題的，不適合采用數(shù)據(jù)平均分配方式。此時需要采取非平均分配時的數(shù)據(jù)劃分方法。以上就是筆者針對分布式并行遙感圖像處理中數(shù)據(jù)劃分問題進(jìn)行的詳細(xì)介紹。