遙感影像區域面積快速計算并行算法研究

楊靜靜　馬駿

摘? 要： 為了有效地解決遙感應用中感興趣區域內有效遙感影像面積統計效率的問題，提出一種基于MPI（Message Passing Interface）的并行計算環境，采用經典數學定理鞋帶公式（Shoelace Formula）及計算機圖形學中向量積法計算多邊形面積。使用三角分割法對多邊形進行切割并行，判斷多邊形之間拓撲關系，獲取交集頂點表，使用鞋帶公式并行計算交多邊形面積。以1.96407的加速比有效提高遙感影像有效面積統計效率，加快網頁加載速度，提高用戶體驗度。

關鍵詞： 遙感影像; 交多邊形面積; MPI; 并行計算; 鞋帶公式; 向量積

中圖分類號：TP312? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2020）06-08-05

Abstract： In order to effectively solve the problem of statistical efficiency of effective remote sensing image area in the region of interest in remote sensing applications， this paper proposes a parallel computing environment based on MPI （Message Passing Interface）， which uses the classic mathematical theorem Shoelace Formula and Cross Product Algorithm in computer graphics to calculate the polygon area. Triangular segmentation is used to cut the polygons in parallel， determine the topological relationship between the polygons， obtain the intersection vertex data， and Shoelace Formula is used to calculate the area of the intersection polygons in parallel. With an acceleration ratio of 1.96407， it effectively improves the statistical efficiency of the effective area of remote sensing images， speeds up the loading of web pages， and improves user experience.

Key words： remote sensing image; intersection polygon area; MPI; parallel computing; Shoelace Formula; Cross Product

0 引言

隨著衛星遙感技術的迅速發展，采集的衛星遙感影像爆炸式冪指數增加。面對巨量的遙感影像，滿足大范圍檢索條件要求的數據趨于上萬條，對判斷遙感影像間拓撲關系及計算遙感影像交并面積的計算效率提出挑戰。

每一個遙感影像都有專屬的坐標位置屬性信息，故將計算多個遙感影像交并面積問題轉換為計算多個簡單多邊形交并面積問題。計算多邊形交并面積，首先需要獲取多邊形交并集頂點。判斷任意多邊形間拓撲關系不僅是計算幾何與計算機圖形學中的基本問題，也是GIS疊加分析的理論基礎。因此，對這一問題的研究無論是在理論上，還是在實踐上都有重要意義[4]。國內外針對多邊形交并判斷及交并面積計算問題，分別提出各類針對不同應用環境的多個多邊形拓撲關系判斷算法。如Shamos算法[5]、O' Rourke算法[6]用于處理凸多邊形，Weiler-Atherton算法[7]、Vatti算法[8]、Greiner-Hormann算法[9]、Sutherland-Hodgman算法[10]和M.Rivero提出的算法[11]能處理任意簡單多邊形的情況。針對這些經典算法在不同生活領域的應用，分別存在不同角度及不同層面的不足。對此，許多相關領域專家分別提出的不同的改進方法。

齊東洲等提出優化數據結構提高算法執行效率的計算交點、將交點插入多邊形頂點序列、遍歷三個步驟的高效多邊形布爾計算方法[12]。陳濤提出了適用于凹多邊形裁剪的Cyrus-Beck改進算法[13]。劉勇奎等[14]、侯寶明等[15]和魏許青[16]等分別在Weiler算法的基礎上改進算法;劉勇奎等提出的算法采用單鏈表數據結構，減少了計算交點的時間;魏許青利用算法中的多邊形鏈表求出交/并集頂點表，求出交/并多邊形面積;侯寶明等采用接縫技術的算法大大簡化了運算過程。王結臣等提出基于掃描線和梯形分割思想的復雜多邊形裁剪算法[17];彭杰等提出基于交點排序思想的多邊形裁剪算法[18]等。結合以上多邊形裁切算法計算多邊形交/并面積的研究已經逐漸擴展。陳占龍等實現多核環境下基于Hilbert曲線空間劃分的多邊形并行合并[19];范俊甫等基于OGC簡單要素模型和Vatti算法，在集群MPI環境下對圖層級多邊形疊加合并[20];趙斯思等實現基于GPU加速的多邊形裁剪[21];高藝等提出基于GPU的柵格化多邊形相交面積算法GPURAS，并結合蒙特卡洛方法和遮擋查詢技術算法優勢互補，提高計算效率[22]。上述研究學者主要在改進經典算法、經典算法結合優勢互補方向深入研究，而在基于計算幾何中數學定理的MPI并行環境下計算多邊形交/并面積的研究較少。

本文提出了一種基于MPI并行計算環境，鞋帶公式及向量積法計算多邊形面積。用三角分割法對多邊形進行切割并行，判斷多邊形之間拓撲關系，獲取交集頂點表，使用鞋帶公式并行計算交多邊形面積的并行算法研究。本文算法在實際應用中有效提高數據執行效率，縮短程序執行時間，提高用戶體驗度。在遙感影像有效區域面積統計研究方面具有一定的參考價值。

1 多邊形交集面積計算算法

1.1 多邊形相交判斷及交點坐標獲取

為了計算方便借坐標原點為輔助點，視多邊形A為實體多邊形，則多邊形B為切割多邊形（首先要判斷多邊形A、B點排列方向順時針輸入，保證多邊形面積為正）。坐標原點與多邊形任意相鄰的兩個頂點構成一個三角形（如圖1多邊形三角分割），而三角形的面積可由三個頂點構成的兩個平面向量的外積求得。多邊形面積的計算和原點的選取沒有關系，通常選取原點坐標點o（0，0）或者多邊形的第一個點，這里選取原點坐標點。以切割多邊形B任意兩點與原點o（0，0）組成的三角形ocd，每條邊為直線向量切割實體多邊形A任意兩點與原點組成的三角形oab，用向量積法判斷多邊形A、B每條邊之間拓撲關系，獲取交點坐標集。向量積求三角形面積如圖2所示。

1.2 多邊形面積計算

1.2.1 鞋帶公式

鞋帶公式[1-3]，又稱“鞋帶算法”（Shoelace Formula，也稱為高斯面積公式），是一種數學算法，其用于計算簡單多邊形的面積，這些多邊形的頂點由平面中的笛卡爾坐標表示。對這些坐標進行叉乘計算，找到包圍多邊形的區域，并從周圍的多邊形中找到其中的多邊形區域。根據其交叉乘的過程像系鞋帶一樣，故稱為鞋帶公式。

1.2.2 多邊形面積計算

本文用鞋帶公式計算多邊形面積。 依據1.1節中獲取的交點坐標Pi，循環遍歷鞋帶算法計算兩三角形有向交面積之和Sum。

傳統經典算法通過循環遍歷切割多邊形，向量積法多次循環判斷切割三角形兩兩之間拓撲關系判斷及獲取多邊形交點坐標，調用鞋帶算法計算交多邊形面積，即計算三角形之間有向交面積并統計所有切割三角形交面積之和作為多邊形有效交面積。傳統多邊形交面積計算程序數據計算串行執行耗時較長，在遇到多邊形頂多較多的情況時會降低算法的執行效率，影響算法應用效果。

2 基于MPI并行計算交多邊形面積

本文針對上述算法存在的缺陷，提出基于MPI信息傳遞接口并行環境計算多邊形面積，對數據分塊進行多線程并行計算，減少數據計算執行等待時間，提高算法的執行效率。

2.1 MPI消息傳遞接口

消息傳遞接口（Message Passing Interface，簡稱MPI），是一種跨語言的通訊協議，用于編寫并行計算機，支持點對點和廣播通信[24]。目前用于編寫并行計算機較為流行。MPI是一個并行計算消息傳遞接口標準，由MPI論壇（MPI Forum）推出，制定該標準的目的是提高并行程序的可移植性和開發效率[25]。MPI現在已經成為產業界廣泛支持的并行計算標準[26]。MPI主要消息傳遞接口如下。

⑴ Mpi_Init（）; 初始化MPI環境，建立多個MPI進程之間的聯系，為后續通信做準備。

⑵ Mpi_Finalize（）; 退出MPI環境。

⑶ Mpi_Comm_rank（MPI_COMM_WORLD，&rank）;獲取當前進程在指定通信域中的編號，返回整型的錯誤值，將自身與其他程序區分。MPI_COMM_WORLD類型的通信域，標識參與計算的MPI進程組;&rank返回調用進程中的標識號。

⑷ Mpi_Comm_size（MPI_COMM_WORLD，&size）;獲取指定通信域的進程個數，確定自身完成任務比例。

⑸ MPI_Bcast（&n1，1，MPI_INT，0， MPI_COMM_

WORLD）;廣播數據集。

⑹ MPI_Reduce（&myResult，&result，1，MPI_DOUBLE， MPI_SUM，0，MPI_COMM_WORLD）; 數據歸約，由進程0進行歸約，把每個進程計算出來的myResult進行相加（MPI_SUM），賦給result。

⑺ Mpi_send（buf，counter，datatype，dest，tag，comm）：buf發送緩沖區的起始地址，可以是數組或結構指針;count：非負整數，發送的數據個數;datatype：發送數據的數據類型;dest：整型，目的的進程號;tag：整型，消息標志;comm：MPI進程組所在的通信域。

⑻ Mpi_recv（buf，count，datatype，source，tag，comm，status）：source：整型，接收數據的來源，即發送數據進程的進程號; status：MPI_Status結構指針，返回狀態信息。

2.2 基于MPI并行計算多邊形面積

據算法使用背景本文使用組通信并行編程模型，利用消息傳遞方法實現任務間的并行。通過指定通信因子和組來對進程進行一種邏輯上劃分，通訊因子定義了進程組內或組間通訊的上下文。Foster方法下并行化設計步驟。

⑴ 劃分：數據分發，0號進程讀入整個坐標數據向量，將獲取的數據分為comm_size塊（comm_size個核），并將數據發送給需要分量的其他進程。不同進程對收到的數據塊進行計算順序相鄰的兩個頂點與原點組成的三角形面積。

⑵ 通信：各線程內坐標數據塊的臨界坐標需要相互間通信，并發地執行對數據的相交判斷及面積計算，期間多機有相互間的網絡通信開銷。

⑶ 聚集：多任務運行時，0號進程收集向量的所有分量，然后由0號進程聚集降低原始任務之間本需要的相互通信開銷。

⑷ 映射：聚合過的任務主要通過for循環部分通過調度對任務進行并行化計算，循環中的迭代需要按照迭代次數及核數進行輪播分配。

如圖3組通信任務分配所示。源數據指定特定通信組，通信組內由多個處理機組成，通信組內通過MPI_Bcast廣播數據組，根據組內處理機數量對源數據進行任務分塊，組內處理機之間通過網絡傳送消息實現相互通信，實現任務間并行。MPI_Reduce規約各個進程任務塊計算結果。

本文主要用到上一節中前6個消息傳遞接口。

3 實驗與分析

在Windows7 64位系統環境，8G運行內存，同樣機型4臺，一臺作為主進程（0號進程，負責數據讀入、分發、聚合），其他3臺機作為并行節點。

實驗主要采用梯度驗證法設置一些測試梯度，以提高測試準確性。通常采用加速比S和效率E來測量并行計算效率，如等式⑸和等式⑹。

其中，Ts為串行算法執行耗費時間，Tp為并行算法執行耗費時間，P為算法并行節點數。

為了更加準確的驗證實驗結論，本文分兩種情況進行實驗驗證，一是節點數一定改變多邊形頂點數;二是多邊形頂點數一定改變節點數。首先我們驗證節點數一定為2，多邊形頂點數分別為3，10，20，40，實驗結果如表1節點數一定改變多邊形頂點個數和圖4節點數一定改變多邊形頂點個數所示。

當并行節點數一定時，改變串行、并行頂點數量，發現隨著頂點數的增加計算時間增大，當數據過小時CPU消費的時間會影響并行計算效率，并行效果不明顯，在頂點數一定時串行和并行計算時加速比和效率是呈線性增加趨勢。

再次驗證頂點數一定為20，節點數分別為1，2，3，4，實驗結果如表2多邊形頂點個數一定改變節點數和圖5多邊形頂點個數一定改變節點數所示。

當頂點數一定時，改變并行節點數量，發現隨著節點數的增加，計算時間增大，當數據過小時，CPU消費的時間會影響并行計算效率。節點數繼續增加，加速比增長緩慢且有下降趨勢，因為線程啟動需要開銷一定的時間。故隨著節點數的增加，并行程序的效率越來越低。

綜上所述，本研究中當節點數為2時，并行計算效率最高，達到相對最佳并行計算節點。

4 結論

本研究主要為了解決多邊形頂點足夠多時，多邊形分割及三角形向量面積計算需要通過多層循環遍歷，程序串行執行效率低下問題。本文提出基于MPI并行計算多邊形交面積，提高多邊形面積計算效率。在多邊形頂點增多時，本文并行計算多邊形面積效率明顯比串行計算速度快，相比串行方法本文并行計算方法在提高計算效率方面具有一定的研究價值。但是本文實驗利用消息傳遞方法實現多處理機處理任務并行，該方法需要網絡環境才能實現多處理機的并行，本次實驗僅在一種網絡環境下進行實驗，接下來可以嘗試換一種網絡帶寬進行并行測試，來驗證并行實驗的有效性。

參考文獻（References）：

[1] Dahlke， Karl. "Shoelace Formula" （http：//www.mathreference.com/la-det，shoe.html）. Retrieved 9 June 2008.

[2] Shoelace Theorem （http：//www.artofproblemsolving.com/wiki/index.php？title=Shoelace_Theorem）， Art of Problem Solving Wiki.

[3] Younhee Lee，? Woong Lim. Shoelace Formula： Connecting the Area of a Polygon with Vector Cross Product[J]. The Mathematics Teacher，2017.110（8）：631-636

[4] 朱雅音，王化文，萬豐等. 確定兩個任意簡單多邊形交_并_差的算法[J]. 計算機研究與發展， 2003.4：69-76

[5] Preparata. Computational Geometry： An Introduction[J].?texts & monographs in computer science，1986.47（176）.

[6] O' Rourke. Computational Geometry in C[J]. Cambridge：Cam-bridge University Press，1985.37：128-129

[7] Kevin Weiler ， Peter Atherton. Hidden surface removal?using polygon area sorting[C]. Proceedings of the 4th Annual Conference on Computer Graphic and Interactive Techniques，1977.11：214-222

[8] Bala R. Vatti.? A generic solution to polygon clipping[J].?Communication of the ACM，1992.35：56-63

[9] Hoffmann CM ， The problems of accuracy and robustness?in geometric computations[J]. IEEE Computer，1989.22：31-42

[10] 蘇誠，韓俊剛.Sutherland-Hodgman裁剪算法的改進[J].西安郵電學院學報，2013.18（3）：80-82

[11] Rivero， F R Feito. Boolean operations on general planarpolygons[M].Computers& Graphics，2000.24（6）：881-898

[12] 齊東洲，吳敏.高效的多邊形布爾計算方法[J].計算機應用，2014.S2：85-89

[13] 陳濤.適用于凹多邊形的Cyrus-Beck改進算法[J].計算機科學，2006.33（12）：217-220

[14] 劉永奎，高云，黃有群.一個有效的多邊形裁剪算法[J].軟件學報，2003.14（4）：845-856

[15] 侯寶明，劉雪娜.任意多邊形區域交的有效算法[J]，計算機輔助工程，2009.18（2）：73-76

[16] 魏許青.計算多邊形交集_并集面積的算法[J].計算機工程與科學，2007.12：89-90

[17] 王結臣，沈定濤，陳焱明，等.一種有效的復雜多邊形裁剪算法[J].武漢大學學報（信息科學版），2010.35（3）：369-372

[18] 彭杰，劉南，唐遠彬等.一種基于交點排序的高效多邊形裁剪算法[J].浙江大學學報（理學版），2012.39（1）：107-111

[19] 陳占龍，吳亮，劉煥煥.多核環境下Hilbert曲線劃分簡單要素多邊形合并算法[J].計算機應用研究，2012.29（7）：2747-2750

[20] 范俊甫，馬廷，周成虎等.基于集群MPI的圖層級多邊形并行合并算法[J].地球信息科學學報，2014.16（4）： 15-21

[21] 趙斯思，周成虎.GPU加速的多邊形疊加分析[J]. 地理科學進展，2013.32（1）：114-120

[22] 高藝，羅健欣，裘杭萍等.基于GPU的任意多邊形相交面積計算方法_高藝[J].測繪工程，2017.26（12）：58-62

[23] Meister， A. L. F.， Generalia de genesi figurarum planarumet inde pendentibus earum affectionibus， https：//books.google.com/books？id=fOE_AAAAcAAJ，1769，Nov.Com. G?tt. （in Latin）， 1：144

[24] https：//baike.baidu.com/item/MPI/15277241？fr=aladdin

[25] 李久楷，朱俊，寧交賢.MPI并行計算性能的研究[J].四川大學學報（自然科學版），2009.33（5）：496-499

[26] 申煥，石曉春，邱宏華.基于MPI的海量遙感影像并行處理技術探析[J].全球定位系統，2012.37（6）：73-76