遙感影像并行處理的數據劃分及其路徑優化算法

方 雷，姚申君，包航成，康俊峰，劉 婷

1. 復旦大學環境科學與工程系，上海 200438； 2. 華東師范大學地理科學學院，上海 200241； 3. 金華市規劃與地理信息中心，浙江 金華 321000； 4. 江西理工大學建筑與測繪工程學院，江西 贛州 341000； 5. 杭州師范大學理學院，浙江 杭州 311121

海量空間信息處理和應用具有信息密集和運算密集的特征，目前廣泛依賴于并行技術和高性能計算機的應用。遙感影像處理(如影像的校正、配準、識別)是并行技術在空間信息處理領域的一大主要應用。早在10年前，國內外就已廣泛開展圖像的并行化處理研究[1-10]，在該領域取得多方面的成果。例如，結合并行技術和遺傳算法有學者提出利用低分辨率相機獲取高分辨率圖像的方法[6]；部分研究人員提出能高效實現遙感圖像預處理的分布式共享存儲并行處理系統[7]、遙感衛星圖像幾何粗校正的數據并行方法[8]、基于小波的遙感圖像全局配準算法[9]、遙感多圖像配準中自動提取特征點的并行算法[10]、基于GPU的并行算法[11-12]等，此外還有針對遙感影像識別、分割、分類、融合等高性能算法[13-18]。針對數據量呈指數增長的全球遙感圖像，必須研究基于并行化的快速、有效、高精度的自動圖像配準算法，為此，有學者提出了相應的遙感圖像自動配準的并行策略[19-20]。而隨著遙感影像并行化方法的研究深入，近5年來，越來越多的學者不滿足于某一類操作或者數據的并行化處理算法，而傾向于提出并行算法的通用模型[21-24]。

可以看出，目前研究主要還是利用遙感圖像的矩陣可分解性質，設計了大量關于影像并行算法和并行處理的環境。但是，在云計算環境下，一份遙感數據存在多個冗余備份，具備同步并行處理多個計算任務，解決了對一份數據處理時輸入輸出(I/O)資源爭用的問題。例如，可以同時對同一份遙感數據的不同備份進行數據劃分和壓縮操作，快速生成金字塔索引。過往并沒有針對該環境的最佳并行處理路徑選擇的深入研究。本文在總結前人研究的基礎上，給出一個一般情況下的基于數據劃分的最佳并行處理路徑的數學模型，實現了在相同的遙感影像處理算法和同等的計算資源條件下，計算機自主選擇最優處理路徑，達到最優的遙感影像處理效率。

1 基于數據劃分的最佳并行處理路徑的數學模型

并行分為功能分解和數據分解。基于數據分解的并行處理，在遙感圖像的并行處理中使用較為普遍。例如，創建金字塔索引時，對原始影像劃分的過程中同時伴隨著數據壓縮。本文根據柵格數據的可分解性給出柵格影像數據并行處理的相關定義，最后提出最佳并行處理路徑選擇算法的數學模型，即旋轉門模型。

1.1 并行處理算法數學模型及其相關定義

一般的柵格影像劃分存儲及并行處理過程均可以抽象成如圖1所示的模型。它包含以下4個要素：數據態Ri、元素個數ni、相對信息量rj、映射f及其對應的單位信息量下的計算代價φp。

圖1 柵格影像的一般并行處理過程Fig.1 General parallel processing model of a raster image

如果要想從源數據態Ri, j生成3個數據態(Ri, j+1、Ri+1, j和Ri+1, j+1)必須經過一次f和f′操作以及一次Ri, j到Ri+1, j的操作；或一次f′和f操作以及一次Ri, j到Ri, j+1的操作。這兩次操作可以是串行的操作也可以是并行的操作。任何一條獨立的處理鏈無法同時(并行的)獲得3個結果數據態，所以并行操作必須將圖中x方向和y方向的操作相結合，形成多路并行處理過程：既生成3個結果數據態，又可以充分利用云計算平臺中的多個計算節點的計算資源，提高數據處理效率。此外，雖然有兩條處理路徑均能生成數據態Ri+1, j+1，但是這種情況在實際的并行過程中顯然是不被允許的，因為該方式造成了計算資源的浪費。于是對并行模型進行化簡，得到縱向并行和橫向并行。

圖2給出了更為一般的縱向并行和橫向并行處理，顯示了從源數據態經過處理鏈得到的不同的數據態(劃分數據態和其他數據態)的過程。圖2(a)和(b)均是一個不完全二叉樹。易知，不完全二叉樹上的每一個分叉都表示一種實行并行的可能性。若將每一個映射過程視為一個并行任務，則并行維數為d的映射過程，可以形成d條并行的子任務。若生成所有的數據態，均有橫向并行和縱向并行兩種并行路徑的選擇。易知，若映射f不發生變化，并行路徑不發生改變。在具體的并行處理實施過程中，如何讓計算機根據映射f動態選擇最佳的并行路徑將是“遙感影像并行處理并對處理后的數據進行分布式存儲，再對存儲后的遙感影像進行下一次的并行處理”這種循環往復操作的關鍵問題。

圖2 一般性縱向并行與橫向并行處理Fig.2 General longitudinal and horizontal parallel processing

經過推導[25]，采用式(1)對并行處理路徑進行選擇

(1)

1.2 示例及討論

(2)

即①劃分的計算代價大于壓縮時，采用橫向并行(先劃分再壓縮)；②劃分的計算代價小于壓縮時，采用縱向并行(先壓縮再劃分)；③劃分與壓縮的計算代價近似時，為臨界狀態，采用橫向并行和縱向并行均可。

(3)

圖3 生成四叉樹索引(4層)Fig.3 Generating quadtree spatial index to image pyramid

圖4 柵格影像目標識別Fig.4 Detection and recognition parallel processing of target

(3) 橫向并行和縱向并行的多種并行操作組合(圖5)。上述兩個示例均為一個并行操作和劃分操作組合的并行策略分析，本文提出的最佳并行策略可以推廣到多個并行。例如，圖5(a)給出了3個并行操作和劃分操作，包含了兩個縱向并行和一個橫向并行組合，稱為旋轉門模型。旋轉門模型是解決多個并行處理操作組合策略的問題，本質上是最優路徑規劃，而不是先后組合的問題。與“傳統的、沒有路徑規劃的”并行算法相比，旋轉門模型的優勢在于：可以實現在相同的遙感影像處理算法和同等的計算資源條件下，計算機自主選擇最優處理路徑，達到最優的遙感影像處理效率。旋轉門模型以遙感影像數據劃分為基礎，是這個旋轉門的主軸，每一扇門都是一個縱向或橫向的選擇(必定包含數據劃分操作部分)，并且由于數據有多個冗余備份，每一扇門與其他扇門的操作都是可以同時進行的、獨立并行的關系。如果不以劃分為軸，這種組合起來的策略還可變成一個彼此為邊的立方體模型(圖5(b))。

此外，進一步討論式(2)和式(3)可知，旋轉門模型的路徑判斷準則可簡單概括為“何種操作的單位計算代價大則先進行何種操作”。即，要獲得全級別的柵格影像這一前提下，要實現多種并行處理操作組合的時間最優，則要優先進行計算代價大的操作。這一結論與傳統的認知和經驗不同，是旋轉門模型的另一理論貢獻。

2 算法實現流程描述及討論

圖6 算法流程Fig.6 Algorithm flow diagram

總之，通過實現算法的描述可知，旋轉門模型原理簡單實用，可以使計算機集群平臺自動根據用戶輸入的遙感影像和指定的遙感影像處理程序準確地得到并行處理時間最短的最優路徑，解決了將并行技術應用于海量遙感影像分布式存儲和處理領域時其處理模型所具有的多路可達性所引起的路徑動態、最優選擇問題，滿足了并行處理時耗時最短、最高效的要求。

特別的，在云計算或集群平臺上，圖2的縱向并行和橫向并行的旋轉門模型在計算節點上的實際運行過程示意圖如圖7所示。由圖7可知，在實際運行過程中，除第1個計算節點之外，旋轉門模型分配每個計算節點“非常有秩序地”都在做相同的操作，而且任何一個節點又都是一個不完全二叉樹的子節點的根節點，它們遵守相同的規則，環環嵌套。這樣的“秩序”是根據“計算時間最少”這一標準，由公式自動計算出來，沒有人工干預。每個節點都做同樣的操作對龐大的云計算平臺有著諸多優勢。例如，在同一個計算節點內，若指令快速緩沖存儲區(cache)和數據cache都有限時，做同樣的事情可以有機會讓代碼和數據一直在cache里，從而提高效率；再如，減少數據傳輸次數，規避數據傳輸瓶頸；還有，容錯率高，不會影響其他計算節點的計算結果，容易找到出錯節點或問題所在，容易恢復中斷的處理和操作等等。綜上，旋轉門模型雖然是遙感影像處理領域的一個算法，但是從一個側面反映了“秩序即效率”的自然或社會規律。

圖7 縱向并行與橫向并行的旋轉門模型在計算節點上的實際運行過程Fig.7 Longitudinal and horizontal parallel processing on compute nodes

3 結果驗證與分析

前文已經通過嚴密的理論論證提出了旋轉門模型。旋轉門模型的本質是多種并行處理的組合基礎上的最優路徑選擇策略。前文在分析傳統的遙感影像并行處理的缺點時，已經指出現有的并行處理策略只注重單一操作的并行處理，若完成數據劃分、目標識別、數據壓縮、投影變換、特征提取等處理過程，只能依次先完成數據劃分再進行目標識別，然后數據壓縮等。所以，第2節的理論模型就是在“多種遙感影像處理并行策略一定優于這些并行處理過程各自完成再串行”這一前提假設的基礎上提出的。即旋轉門模型與現有并行處理策略相比具有天然的優勢。換句話說，旋轉門模型可以實現在相同的遙感影像處理算法和同等的計算資源條件下，計算機自主選擇最優處理路徑，達到最優的遙感影像處理效率。所以本文試驗的目的是為論證實際遙感影像并行處理過程中基于數據劃分的最佳并行路徑選擇模型的正確性及其性能，并未重點測試比較旋轉門模型與現有并行處理策略的高低(討論部分間接說明了旋轉門模型與現有并行處理策略的優勢)。試驗內容以四叉樹金字塔并行生成過程和目標識別為例，測試了“先壓縮再劃分和先劃分再壓縮”、“先識別再劃分和先劃分再識別”的運行時間，最后結合壓縮算法、目標識別算法和劃分算法的計算代價，對上述兩個測試結果進行深入分析。需要說明的是，數據量和軟硬件環境不同會影響測試時間，但是最優路徑的選擇結果和結論不會發生變化。

3.1 測試環境

測試采用名字節點3個，配置為表1中第1及第2類共3臺PC機；計算節點32個，配置為表1中8類共32臺PC機。本文試驗的軟件環境簡單，Windows操作系統運行穩定、操作方便、安全性較高，為保證系統的正常運行，服務器端操作系統采用Windows 2008 Server(64 bits)或Windows 2003 Server(32 bits)。其中，選擇Windows 2008 Server是為運行Dryad平臺，選擇Windows 2003 Server(32 bits)是用其作為UDDI的服務目錄服務器。對客戶端理論上沒有要求，任何安裝了網絡瀏覽器的普通PC機均可作為客戶端。

數據選擇表2所示數據，其數據量從200 MB到5.58 GB不等。

表1 PC機及網絡設備配置

表2 試驗用柵格數據

3.2 測試內容

3.2.1 生成四叉樹金字塔(壓縮和劃分組合策略測試)

測試1：使用10個計算節點，對測試數據A采用先壓縮再劃分的并行策略，構建8、10、12層四叉樹金字塔，記錄總時間；使用10個計算節點，對測試數據A采用先劃分再壓縮的并行策略，同樣構建8、10、12層四叉樹金字塔，記錄總時間。

測試2：測定壓縮和劃分操作的單位信息量下的計算代價φp。分別請求壓縮和劃分操作，則云端的計算節點分別使用ENVI/IDL算法執行壓縮(將一份影像數據按四叉樹金字塔的壓縮方法進行壓縮)和劃分(將同一份影像數據劃分64份)處理，分別記錄柵格數據A—F壓縮和劃分時間，并計算出相同環境下單位信息量下的計算代價。

3.2.2 目標識別(目標識別和劃分組合策略測試)

測試1：本文采用Tensorflow與CNN卷積神經網絡結合的目標識別方法*，使用10個計算節點，對測試數據F采用先目標識別再劃分的并行策略，構建2、3、4層數據，最終將4、16、64份數據均勻存儲在計算節點上為止，記錄1—2級、2—3級、3—4級的時間；使用10個計算節點，對測試數據F采用先劃分再目標識別的并行策略，同樣構建2、3、4層數據，最終將4、16、64份數據均勻存儲在計算節點上為止，記錄1—2級、2—3級、3—4級的時間。

測試2：測定目標識別和劃分操作的單位信息量下的計算代價φp。分別請求目標識別和劃分操作，則云端的計算節點分別使用ENVI/IDL算法執行目標識別(將一份影像數據按Tensorflow與CNN卷積神經網絡結合的目標識別方法進行目標識別)和劃分(將同一份影像數據劃分64份)處理，分別記錄柵格數據A—F目標識別和劃分時間，并計算出相同環境下單位信息量下的計算代價。

為了客觀起見，本測試試驗運行50～100次，取其均值作為試驗結果。表3和表5結果為實際并行處理過程模擬，故包含傳輸時間。

3.3 測試結果

3.3.1 生成四叉樹金字塔(壓縮和劃分組合策略測試)

柵格數據A采用不同的并行策略獲得的測試結果如表3所示。

表3 柵格數據A構建四叉樹金字塔并行策略測試結果

Tab.3 Results of building quadtree pyramid parallel processing of dataAmin

測定壓縮和劃分操作的單位信息量下的計算代價如表4所示。

表4 單位信息量下的計算代價測定結果

3.3.2 目標識別(目標識別與劃分組合策略測試)

柵格數據F采用不同的并行策略獲得的測試結果如表5所示。

測定目標識別和劃分操作的單位信息量下的計算代價如表6所示。

表5 柵格數據F目標識別并行策略測試結果

Tab.5 Results of target detection and recognition parallel processing of dataFh

表6 單位信息量下的計算代價測定結果

3.4 結果討論

3.4.1 生成四叉樹金字塔(壓縮和劃分組合策略測試)

由圖3可知，若創建n級金字塔索引，則該索引中的文件總數Sn為

(4)

那么，柵格數據A在構建8級、10級、12級金字塔索引過程中新生成29 123份、466 029份、7 456 535份圖像文件。同理，若原始圖像的數據量為a，則數據總量m為

(5)

3.4.2 目標識別(目標識別和劃分組合策略測試)

目標識別是一個數據量增加的過程，易從表5結果獲知“先識別再劃分”的并行策略遠遠優于“先劃分再識別”的并行策略。從表6可知，目標識別的單位信息量下的計算代價遠遠大于劃分，所以進行先識別再劃分的策略是正確的。“先劃分再識別”的策略(橫向并行)，相對“先識別再劃分”策略會讓計算節點過多地處理復雜的識別處理操作，從而會降低整體的計算效率。此外，從表6可知，由于目標識別算法的單位計算代價過大，且與數據量和像元數量正相關，所以傳統方法中，將原數據分割成幾份再進行并行目標識別會減少數據處理的總時間。但是，旋轉門模型卻告訴我們，在生成全級別的柵格影像并同時實現目標識別操作時，要“先識別再劃分”，然后再將各級別的結果分布存儲于云計算平臺上，既能保證數據完整性和目標識別的準確性，又能保證效率最高。

3.4.3 目標識別、數據壓縮和數據劃分綜合并行操作組合

綜上，若同時進行目標識別、數據壓縮和數據劃分綜合并行組合操作，生成全級別的柵格影像時，最優路徑應是“目標識別—數據壓縮—數據劃分”或“目標識別—數據劃分”與“數據壓縮—數據劃分”兩種選擇，此路徑即能保證時間效率最高，又能保證數據操作的正確性。若先進行數據壓縮或數據劃分操作，則目標識別則需要重新訓練樣本，除時間效率低下之外，還會增加多余的操作時間。

4 結 論

得益于云計算理論和技術的提出，遙感影像的處理可以實現對同一份數據進行多任務的并行處理。本文在此前提下，深入研究了基于數據劃分的遙感影像并行處理問題，提出了8個定義(數據態、信息量、元素、映射過程、表達式、并行維數、計算代價與縱向/橫向并行)，6個性質(有向性、傳遞性、繁殖性、多維性、同一性與多路可達性)。以這些定義和性質為基礎，從相鄰數據態之間的一次映射逐步推導致“基于數據劃分的遙感影像并行處理”的一般情況，提出最佳并行路徑選擇模型——旋轉門模型，用于解決將并行技術應用于遙感影像分布式存儲和處理領域時，其處理模型所具有的多路可達性所引起的路徑動態、最優選擇問題。本文的貢獻在于：在批量處理海量遙感數據的情形下，同時實現遙感數據生成、目標識別等并行任務時，最優并行路徑的選擇只與平均計算和數據態的相對信息量、元素個數的比值這一標志有關，而且從原始數據(源數據態1)到最終數據(最終數據態n)的諸多并行路徑中，看似復雜，其實只有獨立上行和獨立下行組成的單向最優路徑。

本文還進一步給出四叉樹索引并行生成、基于四叉樹的目標識別并行處理的研究結果。指出在四叉樹索引并行生成過程中，如果劃分的計算代價大于壓縮時，采用先劃分再壓縮的橫向并行；如果劃分的計算代價小于壓縮時，采用先壓縮再劃分的縱向并行。基于四叉樹的目標識別并行處理操作中，當檢測結果很多時，無論劃分映射過程和目標識別映射過程的效率如何，采用縱向并行(先目標識別再劃分)的策略才能實現最優化并行。

本文提出了基于數據劃分的遙感影像并行處理問題的基本概念和性質，最終立足于最佳并行路徑選擇問題上。在模型的提出上，使用了簡單直觀的遙感影像二維矩陣來抽象表示遙感數據(可以理解為TIFF格式)，并在此基礎上提出概念、性質和公式推導，最后得出結論。實際上，遙感數據在云計算平臺中存儲方式多樣，如果把一個二維矩陣按行重新組織成一維直線(1個像元高度)。原本二維矩陣里讀取一行或一列都很方便，現在，在一維直線中讀取一行可以直接根據偏移量連續讀取，但是如果讀一列需要先算好起始點和長度，然后每隔固定像元讀取一個像元，這種情況下就無法批量讀取；同樣如果將二維矩陣按列重新組織成一維直線，則按行批量讀取時也會有問題。得益于云計算環境中同一份數據的多個冗余備份特性，在實際應用中，將遙感影像既按行存儲也按列存儲，并設計調度器對不同的遙感影像處理程序進行調度，依據需要來處理按行存儲或按列存儲的一維數據。所以，實際存儲方式并不影響本文提出的算法模型及相關理論。只是基于不同的遙感數據存儲結構或存儲方式，需要對模型進行具體化。同時針對不同的遙感影像處理方法，也需要對模型進行具體化，還要考慮很多算法在實際應用時的細節，特別是容錯性和健壯性問題，這些都將是未來的研究工作的重點。此外，基于本文提出的概念和性質，遙感影像并行處理問題還有很多其他的內容可以研究，例如，負載均衡、質量檢驗等，而這些將在未來的研究工作中深入展開。