遙感影像三角網(wǎng)幾何校正并行算法及優(yōu)化研究★

張戰(zhàn)偉，劉培明，趙 熹

(1.山東明嘉勘察測(cè)繪有限公司,山東 淄博 255086; 2.中國(guó)礦業(yè)大學(xué)環(huán)境與測(cè)繪學(xué)院,江蘇 徐州 221116)

遙感技術(shù)在多個(gè)方面得到了應(yīng)用,特別是近年來(lái)衛(wèi)星遙感的快速發(fā)展,衛(wèi)星傳感器采樣精度、細(xì)度、頻率不斷提升[1]。衛(wèi)星遙感數(shù)據(jù)的應(yīng)用不斷拓展,多源衛(wèi)星遙感數(shù)據(jù)的融合應(yīng)用需求及場(chǎng)景也越來(lái)越多[2]。這些遙感數(shù)據(jù)的應(yīng)用需要統(tǒng)一的空間數(shù)據(jù)基準(zhǔn),遙感影像的幾何校正是其中一項(xiàng)重要的處理任務(wù),基于三角網(wǎng)進(jìn)行遙感影像幾何校正是常有方式[3-4]。伴隨長(zhǎng)時(shí)間序列、高分辨率影像及實(shí)時(shí)性強(qiáng)的處理需求,快速的遙感影像幾何校正處理算法的重要性更加突出。

遙感數(shù)據(jù)的處理效率提升的手段可以概括為兩個(gè)方面:一是增加硬件計(jì)算資源,目前云計(jì)算、超級(jí)計(jì)算機(jī)、計(jì)算機(jī)集群等技術(shù)均是該范疇;二是提高算法并行度及代碼質(zhì)量,主要包括多核CPU并行、GPU并行、代碼優(yōu)化、算法優(yōu)化等方法。本文從第二個(gè)角度開(kāi)展研究,采用的具體技術(shù)包括OpenMP,GPU通用計(jì)算、代碼優(yōu)化等。OpenMP是一種編程模型,其具有復(fù)雜度低、移植性好等優(yōu)點(diǎn),可方便的實(shí)現(xiàn)代碼并行及多線(xiàn)程化。隨著多核CPU的應(yīng)用,很多研究人員選擇OpenMP實(shí)現(xiàn)遙感數(shù)據(jù)多核CPU并行處理算法[5-6]。圖形處理單元(GPU)具有算力強(qiáng)、體積小、能耗低等優(yōu)點(diǎn),目前是遙感數(shù)據(jù)處理優(yōu)先選擇的計(jì)算機(jī)硬件,GPU在遙感數(shù)據(jù)校正、融合、識(shí)別、分類(lèi)等諸多方面得到廣泛應(yīng)用[7-9]。為了推動(dòng)GPU在通用計(jì)算中的應(yīng)用,Nvidia在2006年推出CUDA編程框架并進(jìn)行了持續(xù)完善,使其成為通用GPU編程的主要工具,此外OpenCL,C++AMP也可用于通用GPU編程。代碼優(yōu)化,通過(guò)高效的編碼語(yǔ)句、合理的數(shù)據(jù)結(jié)構(gòu)、科學(xué)的邏輯控制來(lái)提升代碼質(zhì)量,常有的代碼優(yōu)化方法包括代碼外提、變量歸納、循環(huán)展開(kāi)、常量合并、數(shù)據(jù)重用[10],其不依賴(lài)具體計(jì)算機(jī)硬件,優(yōu)化方法可以在算法運(yùn)行全流程中發(fā)揮作用[11]。

目前針對(duì)基于三角網(wǎng)遙感影像幾何校正并行算法設(shè)計(jì)及優(yōu)化相關(guān)的研究較少,因此為了提升遙感影像幾何校正的處理效率,本文從CPU并行、GPU并行、數(shù)據(jù)結(jié)構(gòu)優(yōu)化、處理算法編碼優(yōu)化等角度對(duì)基于三角網(wǎng)遙感影像幾何校正算法進(jìn)行了研究。

1 算法設(shè)計(jì)及優(yōu)化

1.1 并行算法設(shè)計(jì)

基于三角網(wǎng)的遙感影像幾何校正算法核心步驟包括三個(gè)部分:點(diǎn)坐標(biāo)初始化、三角網(wǎng)變換參數(shù)計(jì)算、坐標(biāo)關(guān)系映射,算法其他主要流程還包括影像基本信息獲取、坐標(biāo)經(jīng)度值及緯度值獲取、目標(biāo)(成果)影像參數(shù)計(jì)算、影像坐標(biāo)信息計(jì)算、目標(biāo)影像文件寫(xiě)入。

本文并行算法圍繞著基于三角網(wǎng)遙感影像幾何校正算法的三個(gè)核心步驟設(shè)計(jì),根據(jù)計(jì)算硬件特點(diǎn),面向多核CPU及GPU分別設(shè)計(jì),圖1為算法設(shè)計(jì)的整體框架。

1)多核CPU采用OpenMP編程接口實(shí)現(xiàn)算法并行,本文設(shè)計(jì)了點(diǎn)坐標(biāo)初始化、三角網(wǎng)變換參數(shù)計(jì)算、坐標(biāo)關(guān)系映射三個(gè)函數(shù),每個(gè)函數(shù)均根據(jù)影像特點(diǎn)采用兩層for循環(huán)結(jié)構(gòu),在外層循環(huán)嵌入for循環(huán)并行控制語(yǔ)句。2)GPU采用CUDA實(shí)現(xiàn)算法并行,算法包括數(shù)據(jù)拷貝(主機(jī)到設(shè)備、設(shè)備到主機(jī))及三個(gè)核函數(shù)。算法并行設(shè)計(jì)體現(xiàn)在三個(gè)核函數(shù)中,包括點(diǎn)坐標(biāo)初始化、三角網(wǎng)變換參數(shù)計(jì)算、坐標(biāo)關(guān)系映射三個(gè)函數(shù)。

1.2 算法實(shí)現(xiàn)

基于三角網(wǎng)遙感影像幾何校正算法的實(shí)現(xiàn),關(guān)鍵算法包括三角網(wǎng)生成、幾何變換關(guān)系計(jì)算、像素點(diǎn)歸屬判斷、像素值計(jì)算、影像生成等。

1)三角網(wǎng)生成:根據(jù)不同坐標(biāo)系統(tǒng)下的控制點(diǎn)坐標(biāo)信息,采用Delaunay三角剖分算法構(gòu)建三角網(wǎng)。2)幾何變換關(guān)系計(jì)算:基于生成的三角網(wǎng),使用仿射變換分別計(jì)算每個(gè)三角形的幾何變換關(guān)系。每個(gè)三角形具有唯一的變換關(guān)系,可以將衛(wèi)星影像上的像素點(diǎn)映射到地理坐標(biāo)系中的對(duì)應(yīng)位置。3)像素點(diǎn)歸屬判斷:遍歷衛(wèi)星影像上的每個(gè)像素點(diǎn),采用重心法確定其歸屬于哪個(gè)三角形。4)像素值計(jì)算:根據(jù)像素點(diǎn)所屬的三角形,將該三角形的變換關(guān)系應(yīng)用于該像素,計(jì)算其在目標(biāo)坐標(biāo)系中的對(duì)應(yīng)位置,采用雙線(xiàn)性插值計(jì)算像素值。5)校正影像生成:將變換后的像素點(diǎn)坐標(biāo)和像素值填充到新的柵格數(shù)據(jù)中,生成校正后的衛(wèi)星影像利用基于三角網(wǎng)進(jìn)行遙感影像幾何校正的方法,針對(duì)不同的區(qū)域具有不同的變換關(guān)系,由于每個(gè)三角形都有獨(dú)立的變換關(guān)系,因此該方法能夠應(yīng)用于不規(guī)則形變的影像。

1.3 GPU并行算法

本文基于CUDA實(shí)現(xiàn)基于三角網(wǎng)遙感影像幾何校正GPU并行算法,算法1為偽代碼,見(jiàn)圖2。

1)定義控制點(diǎn)和三角網(wǎng)結(jié)構(gòu):ControlPoint和Triangle結(jié)構(gòu)用于存儲(chǔ)控制點(diǎn)以及它們之間的三角網(wǎng)關(guān)系。2)實(shí)現(xiàn)并行變換核函數(shù):核函數(shù)(apply_transformation_kernel)并行處理影像中的每個(gè)像素?；诰€(xiàn)程索引計(jì)算像素坐標(biāo),然后遍歷三角剖分,尋找包含當(dāng)前像素坐標(biāo)的三角形。找到對(duì)應(yīng)三角形后,計(jì)算仿射變換關(guān)系并應(yīng)用于當(dāng)前像素坐標(biāo),得到新的坐標(biāo)。最后,使用插值方法計(jì)算像素值。3)設(shè)置參數(shù):設(shè)置核函數(shù)參數(shù),包括blockDim和gridDim,合理的設(shè)置參數(shù)能夠充分利用GPU資源,提高影像幾何校正的執(zhí)行速度。4)設(shè)計(jì)輔助函數(shù):包括像素點(diǎn)歸屬判斷函數(shù)(is_point_inside_triangl)、仿射變換計(jì)算函數(shù)(compute_affine_transformation)和像素插值計(jì)算函數(shù)(interpolate_pixel_value)。

1.4 代碼優(yōu)化

不同的代碼編寫(xiě)方法會(huì)導(dǎo)致算法執(zhí)行時(shí)間的明顯區(qū)別,代碼優(yōu)化策略需要根據(jù)不同算法進(jìn)行有針對(duì)性的設(shè)計(jì)。本文從訪問(wèn)及存儲(chǔ)優(yōu)化、代碼邏輯優(yōu)化兩個(gè)方面進(jìn)一步對(duì)并行算法的代碼進(jìn)行優(yōu)化。

1)訪問(wèn)及存儲(chǔ)優(yōu)化。采用結(jié)構(gòu)體及嵌套來(lái)描述及傳遞坐標(biāo)點(diǎn)及三角網(wǎng)信息值,通過(guò)精簡(jiǎn)算法過(guò)程數(shù)據(jù)的結(jié)構(gòu),降低內(nèi)存占用量和傳輸量,從而減少無(wú)效信息、降低冗余。此外,在內(nèi)存組織形式上進(jìn)行了優(yōu)化,采用同類(lèi)數(shù)據(jù)就近聚合策略,實(shí)現(xiàn)內(nèi)存合并訪問(wèn),從而進(jìn)一步降低訪存成本。2)代碼邏輯優(yōu)化。代碼邏輯優(yōu)化是針對(duì)具體處理方法編碼進(jìn)行的優(yōu)化,優(yōu)化策略更有針對(duì)性,雖然優(yōu)化方法可移植性?xún)r(jià)值不高,但是優(yōu)化邏輯可以作為其他處理方法的參考。在點(diǎn)坐標(biāo)與三角網(wǎng)空間位置關(guān)系判斷實(shí)現(xiàn)過(guò)程中,采用同類(lèi)項(xiàng)合并設(shè)計(jì)方案,具體包括函數(shù)合并及循環(huán)合并優(yōu)化,降低循環(huán)復(fù)雜度及計(jì)算復(fù)雜度,從而減少冗余操作。

2 實(shí)驗(yàn)及分析

2.1 實(shí)驗(yàn)數(shù)據(jù)及環(huán)境

實(shí)驗(yàn)使用MODIS(Moderate-resolution Imaging Spectroradiometer)數(shù)據(jù),MODIS是美國(guó)宇航局研制的大型空間遙感儀器,包括Terra,Aqua衛(wèi)星,該數(shù)據(jù)具有廣泛的用途,可用于地球表面溫度、陸地覆蓋、云層、氣溶膠、水蒸氣、溫度分布和森林火災(zāi)等方面。圖3為本文實(shí)驗(yàn)使用的MODIS遙感影像數(shù)據(jù),其中圖3(a)為原始影像,圖3(b)為幾何校正后的影像。

實(shí)驗(yàn)投入的計(jì)算機(jī)硬件具體配置:CPU為Intel Core i7-9700 (3.0 GHz, 8 CPUs);顯卡為NVIDIA GeForce GTX 1660,顯存容量6 GB;內(nèi)存容量為8 GB;磁盤(pán)分別為HDD及SSD,其中HDD轉(zhuǎn)速7 200 rpm,SATA3.0接口、緩存64MB,SSD讀取速度3 500 MB/S、寫(xiě)入速度3 000 MB/S。

2.2 實(shí)驗(yàn)結(jié)果分析

本文針對(duì)不同的影像大小進(jìn)行了實(shí)驗(yàn),影像大小介于33 MB～864 MB之間。對(duì)多核CPU及GPU并行計(jì)算運(yùn)行時(shí)間進(jìn)行了統(tǒng)計(jì),并與單線(xiàn)程算法進(jìn)行了對(duì)比。本文采用加速比評(píng)價(jià)并行算法的加速效果,加速比計(jì)算如式(1)所示。

(1)

其中,S為加速比;T1為單線(xiàn)程算法的執(zhí)行時(shí)間;T為并行算法的執(zhí)行時(shí)間。

表1為不同影像大小在不同硬件方案下的運(yùn)行時(shí)間及多核CPU,GPU相對(duì)單線(xiàn)程的加速比結(jié)果,圖4為不同影像大小情況下影像計(jì)算時(shí)間及總體處理時(shí)間的統(tǒng)計(jì)及對(duì)比結(jié)果。

表1 不同計(jì)算方案統(tǒng)計(jì)結(jié)果 s

從表1,圖4可以看出,當(dāng)采用8核CPU時(shí),多核CPU并行算法獲得了4.35x-6.43x的加速比;GPU并行算法獲得了1.32x-15.93x的加速比,且隨著影像大小的增加,加速效果越明顯,其中當(dāng)影像大小為863 MB時(shí),獲得了15.93x的加速比。此外,從圖4可以看出計(jì)算部分的加速效果要明顯優(yōu)于數(shù)據(jù)處理整體時(shí)間的加速效果,主要原因是讀、寫(xiě)部分執(zhí)行時(shí)間的影響,為了系統(tǒng)分析讀、寫(xiě)及計(jì)算的時(shí)間成本,本文進(jìn)行了多組實(shí)驗(yàn),如表2所示。

表2 不同方案數(shù)據(jù)處理時(shí)間對(duì)比結(jié)果

表2為影像大小486 MB時(shí)不同硬件方案數(shù)據(jù)處理時(shí)間的統(tǒng)計(jì)結(jié)果。從表2可以看出讀(I)、寫(xiě)(O)的執(zhí)行時(shí)間占比相對(duì)較大,因此造成整體加速效果不是非常明顯,主要原因是影像校正算法屬于訪存密集型任務(wù),主要瓶頸受制于內(nèi)存帶寬及I/O效率,大量耗時(shí)操作用于數(shù)據(jù)傳遞。從表2可以看出SSD相對(duì)HDD在I/O方面具有明顯優(yōu)勢(shì),因此在并行算法執(zhí)行時(shí)可以?xún)?yōu)先選擇SSD。雖然I/O影響了基于三角網(wǎng)的遙感影像幾何校正并行算法的加速效果,但是相對(duì)單線(xiàn)程算法,多核CPU及GPU并行算法仍獲得了明顯的加速效果,特別是GPU并行算法,影像數(shù)據(jù)量越大加速效果越明顯。

3 結(jié)論

本文以提升遙感影像幾何校正的處理效率為目標(biāo),從并行算法設(shè)計(jì)、代碼優(yōu)化角度對(duì)基于三角網(wǎng)的遙感影像幾何校正算法進(jìn)行了研究,經(jīng)過(guò)多組實(shí)驗(yàn)分析,得到了較為理想的加速效果。本文的主要貢獻(xiàn)如下:

1)基于CUDA實(shí)現(xiàn)了基于三角網(wǎng)遙感影像幾何校正GPU并行算法,當(dāng)影像大小為863 MB時(shí),獲得了15.93x的加速比。

2)基于OpenMP實(shí)現(xiàn)了基于三角網(wǎng)遙感影像幾何校正多核CPU并行算法,當(dāng)采用8核CPU時(shí),獲得了4.35x-6.43x的加速比。

3)在數(shù)據(jù)結(jié)構(gòu)體優(yōu)化、常量合并、循環(huán)體優(yōu)化等方面對(duì)算法代碼進(jìn)行了優(yōu)化,獲得了較為明顯的加速效果。

由于遙感影像幾何校正計(jì)算復(fù)雜度相對(duì)較低,數(shù)據(jù)的I/O成本相對(duì)計(jì)算成本比例較高,從而導(dǎo)致并行算法加速的綜合效率提升并不明顯,因此如何縮短遙感數(shù)據(jù)的I/O時(shí)間,降低I/O成本是需要研究的內(nèi)容。下一步,本文將基于GPU多流、疊加I/O及計(jì)算等技術(shù)或策略開(kāi)展相關(guān)研究,以進(jìn)一步提升遙感數(shù)據(jù)處理的整體效率。