分布式并行遙感圖像處理中的數據劃分

文/王玉坤

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

1 遙感數字圖像處理關鍵技術特點分析

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

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

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

2 并行遙感圖像處理和數據劃分分類

2.1 并行遙感圖像處理分類

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

圖2：數據按結果圖像平均劃分

2.2 數據劃分分類

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

3 分析域處理數據劃分的通訊量

3.1 通訊域和數據通訊量分析

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

3.2 點處理、線處理和域處理數據劃分凈通訊量分析

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

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

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

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

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

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

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

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

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

4 進一步數據劃分分析

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

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

5 結語

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