韓李濤，劉海龍，孔巧麗,3，陽凡林

(1.山東科技大學(xué) 測繪科學(xué)與工程學(xué)院，山東 青島 266590； 2.海島(礁)測繪技術(shù)國家測繪地理信息局重點實驗室(山東科技大學(xué))，山東 青島 266590；3.公路地質(zhì)災(zāi)變預(yù)警空間信息技術(shù)湖南省工程實驗室(長沙理工大學(xué))，長沙 410004) (*通信作者電子郵箱hlt1978@163.com)

基于多核計算環(huán)境的地貌暈渲并行算法

韓李濤1,2*，劉海龍1，孔巧麗1,3，陽凡林1,2

(1.山東科技大學(xué) 測繪科學(xué)與工程學(xué)院，山東 青島 266590； 2.海島(礁)測繪技術(shù)國家測繪地理信息局重點實驗室(山東科技大學(xué))，山東 青島 266590；3.公路地質(zhì)災(zāi)變預(yù)警空間信息技術(shù)湖南省工程實驗室(長沙理工大學(xué))，長沙 410004) (*通信作者電子郵箱hlt1978@163.com)

針對現(xiàn)有地貌暈渲算法多是基于單核單線程編程模式從而導(dǎo)致計算效率較低的問題，提出利用多核并行計算模式對現(xiàn)有地貌暈渲算法進行并行化改進。首先，通過格網(wǎng)分割方式對原始數(shù)字高程模型(DEM)數(shù)據(jù)進行分割從而實現(xiàn)數(shù)據(jù)分塊；其次，利用.NET環(huán)境下的Parallel類對分塊數(shù)據(jù)進行并行暈渲處理，得到各個分塊數(shù)據(jù)的暈渲結(jié)果；最后，對各個分塊數(shù)據(jù)的暈渲圖像進行拼接，從而得到完整的地貌暈渲圖像。實驗結(jié)果表明：并行化改進算法的計算效率明顯高于現(xiàn)有單核單線程地貌暈渲算法，且參與計算核數(shù)與暈渲效率基本上呈線性增長關(guān)系；同時，分析發(fā)現(xiàn)地貌暈渲的立體真實感與光源參數(shù)的設(shè)置極其相關(guān)。

多核環(huán)境；數(shù)字高程模型；地貌暈渲；并行計算；數(shù)據(jù)分塊；圖像拼接

0 引言

地貌暈渲圖通過模擬太陽光對地面照射所產(chǎn)生明暗程度的不同，采用隨光度近似連續(xù)變化的灰度或彩色色調(diào)表示地面點顏色[1]，從而實現(xiàn)以圖像形式表達逼真的三維地形起伏，是地形二維表達形式中最具立體真實感的一種可視化表達方式[2]?，F(xiàn)有文獻從地貌暈渲實現(xiàn)機制出發(fā)，對影響地貌暈渲效果的地形因子計算、光照模型及光照模型參數(shù)設(shè)置等因素進行了深入研究，取得了許多成果[2-5]，但現(xiàn)有算法多是基于單核單線程計算模式，計算效率相對較低。目前，高分辨遙感影像、高密度LiDAR(Light Detection And Ranging)點云數(shù)據(jù)等精細化數(shù)字高程模型(Digital Elevation Model， DEM)數(shù)據(jù)源的獲取技術(shù)已經(jīng)相當(dāng)成熟，這使得DEM表達的精細程度越來越高。隨著地貌暈渲區(qū)域的范圍擴大和表達精度增加，地貌暈渲需要處理的地形網(wǎng)格數(shù)顯著增加，計算時間消耗更多，對現(xiàn)有單核單線程地貌暈渲算法提出了挑戰(zhàn)。

從硬件角度考慮，目前高性能并行計算實現(xiàn)的方式[6-7]主要有計算機集群、多核處理器(Multi-core processors)以及圖形處理器(Graphics Processing Unit， GPU)。從軟件架構(gòu)來說，最常用的支持并行計算的并行計算庫包括MPI(Message Passing Interface)、OpenMP(Open Multi Processing)、Intel IPP(Integrated Performance Primitives)等。計算機集群模式需要多計算機支持，成本高且開發(fā)復(fù)雜，僅限于在一些專門領(lǐng)域使用。隨著多核處理器以及圖形加速卡的普及，基于多核或GPU的并行計算模式正成為未來程序開發(fā)的發(fā)展趨勢。這不僅充分發(fā)揮了新的硬件架構(gòu)的計算性能，也極大提升了應(yīng)用程序的運行效率。在地學(xué)領(lǐng)域，許多學(xué)者將單機多核并行計算引入地學(xué)計算，作了許多創(chuàng)造性的工作，顯著提升了計算效率，如潰壩水流模擬[8]、DEM洼地識別與填充[9]、海量DEM處理[10]、基于坡度的Lidar點云簡化與內(nèi)插[11]、遙感圖像處理算法并行化[12]等。

為了適應(yīng)當(dāng)前計算機多核處理的發(fā)展趨勢，微軟從.NET Framework 4.0開始集成TPL(Task Parallel Library)和PLINQ(Parallel LINQ)來支持并行，在統(tǒng)一的工作調(diào)度程序下進行硬件并行協(xié)調(diào)，在提高應(yīng)用程序性能的同時降低了現(xiàn)存并發(fā)模型的復(fù)雜性。本文將在.NET環(huán)境下利用多核并行計算模式對現(xiàn)有地貌暈渲算法進行改進，提高地貌暈渲效率。

1 基于坡度坡向的地貌暈渲算法

1.1 坡度與坡向計算

DEM表達主要有不規(guī)則三角網(wǎng)(Triangulated Irregular Network， TIN)和規(guī)則格網(wǎng)(Regular Square Grid， RSG)兩種模型。由于RSG模型具有存儲結(jié)構(gòu)簡單、適于多分辨率表達、計算處理方便以及易于影像等其他柵格數(shù)據(jù)融合等優(yōu)勢，而被廣泛采用。地形的坡度和坡向的計算方法與地形的表達形式密切相關(guān)。當(dāng)采用規(guī)則格網(wǎng)形式表達時，一般采用差分公式來計算。坡度、坡向的計算公式分別為：

(1)

(2)

其中：fx為X方向上的高程變化率，fy為Y方向上的高程變化率。坡向值按照正北方向為0°，按順時針方向依次遞增，取值范圍為0°～360°。

求解fx和fy方法是通過3×3的移動窗口掃描整個格網(wǎng)DEM，利用移動窗口中的格網(wǎng)點高程，按照給定的計算方法來計算中心格網(wǎng)點的fx和fy。常用的計算fx和fy的方法有數(shù)值分析法、快速傅里葉變換法、局部曲面擬合法和空間矢量法等。根據(jù)移動窗口中格網(wǎng)單元參與計算方式的不同，數(shù)值分析法又分為簡單差分法、二階差分法、三階不帶權(quán)差分法(Sharpnack算法)、三階反距離平方權(quán)差分法(Horn算法)、三階反距離權(quán)差分法和Frame差分法等方法。這里采用Horn算法，計算公式如下：

fx=[z3-z1+2×(z6-z4)+z9-z7]/(8g)

(3)

fy=[z7-z1+2×(z8-z2)+z9-z3]/(8g)

(4)

其中：z1～z9為移動窗口中的9個格網(wǎng)高程，g為DEM格網(wǎng)間隔。移動窗口上各個格網(wǎng)單元的編號如圖1所示。

圖1 3×3高程分析窗口

1.2 RSG邊緣處理

當(dāng)移動窗口移動到RSG邊緣時，計算邊緣網(wǎng)格的坡度坡向會缺少必需的格網(wǎng)單元值。如圖2(a)，以z1和z12分別代表移動窗口在RSG四周和角點邊緣時的兩種典型情況，z1和z12為待計算單元，空白單元為移動窗口計算時的缺失單元。為了使移動窗口在邊緣計算時能夠獲得足夠的網(wǎng)格數(shù)，可在DEM格網(wǎng)周圍增加一圈虛擬網(wǎng)格。具體步驟為：1)對邊緣格網(wǎng)上下左右各增加一虛擬行或一虛擬列；2)對虛擬行、列上的在原始RSG上進行高程推算。

為了保證邊緣地形的自然延展趨勢，增強邊緣格網(wǎng)暈渲處理效果，高程推算采用虛擬網(wǎng)格所在行、所在列或所在對角線上鄰近的2個網(wǎng)格的高程值進行線性外推，得到虛擬網(wǎng)格的高程值。如圖2(b)所示，陰影部分為實際網(wǎng)格，空白格網(wǎng)部分為虛擬網(wǎng)格，則虛擬網(wǎng)格za、zb、zc的推算值分別為2×z1-z6、2×z1-z2、2×z1-z5，其他虛擬網(wǎng)格的高程可以類似推算。

圖2 RSG邊緣處理

依據(jù)推算格網(wǎng)單元的位置，可以將虛擬網(wǎng)格分為角點網(wǎng)格(左上、左下、右上、右下)、行網(wǎng)格(上、下)、列網(wǎng)格(左、右)等3大類8小類，然后分別處理。假設(shè)擴展后的RSG為一個n×n的矩陣，則通過虛擬網(wǎng)格的行列號很容易確定網(wǎng)格類別、具體所在行列以及參與該網(wǎng)格推算的兩個實際網(wǎng)格，從而計算出虛擬網(wǎng)格的高程。

1.3 RSG網(wǎng)格光照強度計算

除了地形起伏形態(tài)(主要是坡度、坡向)，光源的類型、數(shù)量以及方位等對地貌暈渲效果也起著決定性作用[13]。通常，地貌暈渲時將光源設(shè)置為方向光源來模擬太陽照射效果，有時也會引入多個光源構(gòu)成綜合光照效果以凸顯復(fù)雜地形地貌形態(tài)[4-5]。本文算法引入一個光源模擬太陽照射，并采用暈渲效果較好的相對輻射模型來計算每個網(wǎng)格的光照強度IR。計算公式為：

IR=Gmax×(cos(Af-As) sinHfcosHs+cosHfsinHs)

(5)

其中：Gmax為最大灰度級，一般取255；Af為網(wǎng)格的坡向，取值范圍為[0，360]；As為太陽方位角，取值范圍為[0，360]，以正北方向為0°基準，順時針增加；Hf為網(wǎng)格的坡度，取值范圍為[0，90)；Hs為太陽高度角，取值范圍為[0，90]；IR的取值范圍在[0，255]，0為最黑，255為最亮。

2 地貌暈渲并行算法

當(dāng)前，許多個人計算機和工作站都有兩個或兩個以上的內(nèi)核。為了充分利用硬件資源，提高計算效率，需要對代碼進行并行化，以將工作分攤在多個處理器上。微軟從.NET Framework 4開始提供了新的運行時、類庫以及診斷工具，增強對并行編程的支持。這些功能簡化了并行開發(fā)，使程序員能夠通過固有方法編寫高效、細化且可伸縮的并行代碼，而不必直接處理線程或線程池等低級操作。

規(guī)則格網(wǎng)DEM的數(shù)據(jù)結(jié)構(gòu)類似于柵格數(shù)據(jù)，許多有關(guān)計算都是以移動窗口方式進行的局部運算，當(dāng)將規(guī)則格網(wǎng)DEM分割后，各個子塊仍然可以獨立地完成相應(yīng)的計算，因此，規(guī)則格網(wǎng)DEM具有適用并行計算的特性，并行計算模式成為提升格網(wǎng)DEM地形分析算法效率的有效途徑，如并行計算模式下的等高線提取[14]、洼地填充[15]、三維暈渲[16]等。并行化算法在算法設(shè)計過程中需要將整個任務(wù)劃分成若干個互相獨立子任務(wù)，這些子任務(wù)不考慮互相的依賴和順序。盡管規(guī)則格網(wǎng)DEM的暈渲過程依次包括了坡度計算、坡向計算、網(wǎng)格光照強度計算等3個子過程，但每個網(wǎng)格的坡度、坡向及光強度計算僅與其相鄰網(wǎng)格有關(guān)，因此，地貌暈渲算法的并行化采用數(shù)據(jù)并行的策略。

規(guī)則格網(wǎng)DEM地貌暈渲算法并行化實現(xiàn)的主要步驟是：1)獲取運行計算機的CPU核數(shù)與內(nèi)存，作為數(shù)據(jù)分塊的依據(jù)；2)將規(guī)則格網(wǎng)DEM數(shù)據(jù)根據(jù)內(nèi)核數(shù)按2n進行分塊，n從0～4；3)對每個數(shù)據(jù)分塊創(chuàng)建一個線程，并將該線程分配到不同的CPU內(nèi)核上，經(jīng)過坡度、坡向以及光照強度計算，獲得分塊數(shù)據(jù)的暈渲圖像；4)主線程接收來自各個子線程的暈渲子圖像，依據(jù)數(shù)據(jù)分塊時子塊在整個DEM數(shù)據(jù)矩陣的行列號確定位置，對暈渲子圖像進行合并，從而得到完整的地貌暈渲圖。算法流程如圖3所示。該算法通過自動檢測運行計算機的內(nèi)核數(shù)和內(nèi)存容量，從而自動適應(yīng)計算機的硬件配置，靈活而充分地利用硬件資源。

圖3 DEM暈渲并行算法流程

2.1 DEM數(shù)據(jù)分塊

常用的DEM數(shù)據(jù)分塊方法有按行分割、按列分割、按格網(wǎng)分割3種[17]：按行分割是將DEM數(shù)據(jù)按照行數(shù)分成2n個數(shù)據(jù)塊；按列分割是將DEM數(shù)據(jù)按照列數(shù)分成2n個數(shù)據(jù)塊；按格網(wǎng)分割是將DEM數(shù)據(jù)按照行數(shù)、列數(shù)分成2n個數(shù)據(jù)塊。n取整數(shù)且2n小于等于核數(shù)。為了使各個線程上的任務(wù)能夠同時結(jié)束，從而保證主線程在圖像合并時能得到完整的內(nèi)容，需要均勻分塊，保證各個子塊處理時間大致相等。

地貌暈渲算法采用格網(wǎng)均勻分割，分割后每個子塊都需要處理邊緣網(wǎng)格(見1.2節(jié))，因此，對DEM數(shù)據(jù)進行分割時，在計算好分割線的情況下，可在分割線的基礎(chǔ)上多增加一行或一列，即DEM相鄰分塊之間有2行或2列的重疊區(qū)。以16×16的原始格網(wǎng)DEM均勻分割為4個子塊為例(圖4)，每個子塊應(yīng)該為4×4的格網(wǎng)。為處理邊緣，可通過增加內(nèi)部重疊網(wǎng)格和邊緣虛擬網(wǎng)格將每個4×4子塊擴展為5×5的格網(wǎng)，從而既消除了因DEM數(shù)據(jù)分割而產(chǎn)生的邊緣網(wǎng)格暈渲誤差，又滿足了數(shù)據(jù)子塊內(nèi)各個網(wǎng)格單元的移動窗口計算要求。

圖4 DEM數(shù)據(jù)分塊

2.2 .NET環(huán)境下地貌暈渲的并行化

.NET Framework4.0通過引入并行庫TPL實現(xiàn)了基于任務(wù)設(shè)計而不用處理重復(fù)復(fù)雜線程的并行開發(fā)框架，支持數(shù)據(jù)并行、任務(wù)并行與流水線。為了簡化DEM暈渲算法的并行化過程，采用Parallel類的Invoke方法，它可以實現(xiàn)對給定任務(wù)實現(xiàn)并行開發(fā)。

算法首先判斷計算機的內(nèi)核數(shù)以及內(nèi)存大小，依據(jù)配置確定采用的線程數(shù)及任務(wù)分解方式。在DEM數(shù)據(jù)分塊后，將不同的數(shù)據(jù)子塊以及按照范圍分別載入相應(yīng)的暈渲方法中，并傳入太陽高度角、太陽方位角、畫布等參數(shù)。利用Invoke方法并行化的過程就是將每個分塊對應(yīng)的暈渲方法作為參數(shù)傳遞給Invoke方法即可。當(dāng)所有暈渲線程完成暈渲后，將結(jié)果圖片進行拼接。需要注意的是，拼接過程要等所有子線程都處理完成后再進行，否則導(dǎo)致部分子塊暈渲圖像丟失。由于對DEM進行了均勻分割，因此每個線程執(zhí)行的時間幾乎相等，這樣避免了單個線程運行時間過長而影響整體計算時間。以偽代碼方式，并行化暈渲算法如下：

GetCPUNumber();

//獲取CPU數(shù) GetMemory();

//獲取內(nèi)存大小 Switch(CPUNumber){ Case 1:

//單核 bitmap11=new Bitmap(DEM行數(shù),DEM列數(shù)); Graphics11=Graphics.FromImage(bitmap11); parallelCalBlock11=new parallelCal(DEM,Graphics11,太陽方向角,太陽高度角,子塊起始行號,子塊起始列號,bitmap11高度,bitmap11寬度); Parallel.Invoke(parallelCalBlock11.DEMHillshade);

MergeImage();

//圖片拼接

Case 2:

//雙核，DEM被橫向分割為兩塊 bitmap11=new Bitmap(DEM行數(shù)/2,DEM列數(shù)); Graphics11=Graphics.FromImage(bitmap11); parallelCalBlock11=new parallelCal(DEM,Graphics11,太陽方向角,太陽高度角,子塊起始行號,子塊起始列號,bitmap11高度,bitmap11寬度); bitmap12=new Bitmap(DEM行數(shù)/2,DEM列數(shù));

Graphics12=Graphics.FromImage(bitmap12);

parallelCalBlock12=new parallelCal(DEM,Graphics12,太陽方向角,太陽高度角,子塊起始行號,子塊起始列號,bitmap12高度,bitmap12寬度); Parallel.Invoke(parallelCalBlock11.DEMHillshade, parallelCalBlock12.DEMHillshade); MergeImage();

//圖片拼接

Case 4:

//四核 … }

程序運行時，主線程由系統(tǒng)自動生成，負責(zé)監(jiān)管整個程序的運行，統(tǒng)一進行系統(tǒng)資源的調(diào)配；任務(wù)線程由主線程逐個啟動，線程數(shù)量取決于數(shù)據(jù)塊的數(shù)量，同時被系統(tǒng)分配到不同的CPU內(nèi)核中，不同內(nèi)核上運行的任務(wù)線程互相獨立。

2.3 暈渲結(jié)果拼接

單機多核計算機作并行計算時各個線程共享內(nèi)存。內(nèi)核中任務(wù)線程運行的結(jié)果保存在內(nèi)存中，待所有任務(wù)線程結(jié)束后，需要將不同內(nèi)核生成的圖像按照數(shù)據(jù)塊的對應(yīng)位置由主線程進行拼接，形成一張圖像作為最后暈渲結(jié)果。圖形設(shè)備接口GDI+(Graphics Device Interface Plus)提供了3種實現(xiàn)圖像拼接的途徑：像素復(fù)制、BitBlt函數(shù)以及DrawImage函數(shù)。像素復(fù)制利用BitMap類的GetPixel和SetPixel函數(shù)在像素操作層次上實現(xiàn)圖像拼接，效率較低，而調(diào)用Windows應(yīng)用編程接口(Application Programming Interface， API)提供的BitBlt函數(shù)實現(xiàn)拼接又較為復(fù)雜，因此本文采用DrawImage函數(shù)。具體步驟是：首先，利用Bitmap類創(chuàng)建一個與DEM原始行列數(shù)相等的空白圖像；其次，將空白圖像作為畫布；最后，按照DEM各個子塊對應(yīng)的位置將各個暈渲子圖像繪制到該畫布上就可以完成暈渲圖像的拼接。

3 實驗結(jié)果與分析

為了驗證上述地貌暈渲算法的效果和效率，在.NET多核編程環(huán)境下，使用C#語言編寫了地貌暈渲并行處理算法。計算環(huán)境配置為：CPU Intel 2.6 GHz，4個物理硬件核心，內(nèi)存為4 GB，Windows 7操作系統(tǒng)。

3.1 地貌暈渲效果分析

選取地形起伏明顯的某山地區(qū)域，格網(wǎng)DEM大小為1 001×1 001，設(shè)定正東方向為0°方位角。首先，分別測試了本文算法在不同方位角和高度角下的地貌暈渲效果；然后在相同光照條件下本文算法與ArcGIS軟件的地貌暈渲效果。

3.1.1 太陽方位角對地貌暈渲效果的影響

選取太陽高度角為45°，方位角分別取45°、135°、225°和315°時的地貌暈渲效果如圖5所示。

圖5 不同方位角地貌暈渲效果對比

從圖5中可以看出，太陽方位角對地貌暈渲的立體感影響不大，但對地形的陰影分布和立體形態(tài)有著較為明顯的影響，方位角為45°、135°時地貌暈渲的立體形態(tài)和方位角為225°、315°時的結(jié)果甚至呈現(xiàn)反地形現(xiàn)象。

3.1.2 太陽高度角對地貌暈渲效果的影響

選取太陽方位角為45°，高度角分別取30°、45°、60°和90°時的地貌暈渲效果，如圖6所示。從圖6中可以看出，太陽高度角對地貌暈渲效果的影響十分明顯，當(dāng)高度角為45°時，地貌暈渲立體效果最好；當(dāng)高度角為90°時地形立體效果幾乎就消失了。

圖6 不同高度角地貌暈渲效果對比

3.1.3 與ArcGIS地貌暈渲效果對比

設(shè)置太陽方位角和高度角均為45°，本文算法與ArcGIS的暈渲結(jié)果對比如圖7所示。兩者都對不同網(wǎng)格灰度值之間的過渡較平滑，立體感強。相對于ArcGIS，本文算法的暈渲效果中亮度對比適中，而ArcGIS暈渲的結(jié)果則相對偏暗，山谷河谷區(qū)域顏色太深，掩蓋了部分地形細節(jié)。

圖7 本文算法與ArcGIS的暈渲結(jié)果對比

3.2 CPU核數(shù)對暈渲效率的影響

為了研究CPU物理內(nèi)核數(shù)目與DEM暈渲耗時的關(guān)系，使用行列數(shù)分別為500×500、1 000×1 000、5 000×5 000、10 000×10 000等四組不同大小的DEM數(shù)據(jù)，在相同實驗計算環(huán)境下，對不同核數(shù)參與計算進行效率統(tǒng)計。算法使用多核并行化后的效果可用加速比Sp=T1/Tp以及并行效率ηp=Sp/p衡量[18]。p代表核數(shù)，T1代表最佳串行計算時間，Tp代表使用p個核并行計算的時間。實際操作時T1也往往表示使用一個核計算的時間。表1列出了各組DEM數(shù)據(jù)在不同CPU核數(shù)參與計算情況下的耗時以及加速比，圖8為不同數(shù)據(jù)規(guī)模下不同核數(shù)參與計算時的算法耗時對比。取表1中S2的平均值計算η2為90.31%；同理，計算η4為81.84%。

表1 不同DEM數(shù)據(jù)量的計算耗時和加速比對比

圖8 CPU核數(shù)與暈渲計算耗時關(guān)系

由測試統(tǒng)計結(jié)果可知，DEM暈渲并行化大大提高了算法效率，充分發(fā)揮了硬件性能。依據(jù)Amdahl定律，算法并行化效率的提升與算法的串行化比例有關(guān)，因此，盡管算法效率與參與CPU核數(shù)呈正相關(guān)關(guān)系，但并不會出現(xiàn)核數(shù)增加一倍，耗時減少一半的理想情況。另外，核數(shù)的增加需要更多的數(shù)據(jù)分塊和數(shù)據(jù)拼接處理時間，CPU向內(nèi)存頻繁存取數(shù)據(jù)以及協(xié)調(diào)各個線程的開銷增加，算法的并行效率會有所降低。

4 結(jié)語

目前大多數(shù)計算機都支持多核計算，利用多核計算模式來提升傳統(tǒng)算法的計算效率是一種可行方法。本文利用多核編程技術(shù)對現(xiàn)有地貌暈渲算法進行了改進和實驗驗證。地貌暈渲效果實驗表明：1)本文算法具有良好暈渲效果；2)光源設(shè)置與地貌暈渲效果之間關(guān)系密切。效率實驗結(jié)果表明：參與計算核數(shù)與地貌暈渲效率大致呈線性正相關(guān)關(guān)系，多核并行計算可以大大提高地貌暈渲算法的效率。另外，本文的地貌暈渲并行化算法還不能處理大規(guī)模格網(wǎng)DEM數(shù)據(jù)，若DEM數(shù)據(jù)規(guī)模大于計算機內(nèi)存容量，則需要開辟專門的線程進行內(nèi)存與硬盤數(shù)據(jù)之間的數(shù)據(jù)調(diào)度，這也是下一步要研究的內(nèi)容。

References)

[1] 張玲,楊曉平,魏占玉,等.三維數(shù)據(jù)的二維可視化方法綜述[J].地震地質(zhì),2014,36(1):275-284.(ZHANG L, YANG X P, WEI Z Y, et al. Overview of visualization methods of three dimensional topographic data [J]. Seismology and Geology, 2014, 36(1): 275-284.)

[2] 王少榮,陳星宇,徐秋紅.基于曲率的小比例尺地貌暈渲圖生成方法[J].計算機應(yīng)用與軟件,2015,32(7):204-206.(WANG S R, CHEN X Y, XU Q H. Generation method of small-scale relief shading based on curvature [J]. Computer Applications and Software, 2015, 32(7): 204-206.)

[3] 李少梅,闞映紅,陳艷麗,等.數(shù)字地貌暈渲光照模型研究[J].測繪科學(xué)技術(shù)學(xué)報,2010,27(1):57-60.(LI S M, KAN Y H, CHEN Y L, et al. Research on illumination model of digital relief shading [J]. Journal of Geomatics Science and Technology, 2010, 27(1): 57-60.)

[4] 丁宇萍,蔣球偉.地貌暈渲圖的生成原理與實現(xiàn)[J].計算機應(yīng)用與軟件,2011,28(9):214-216.(DING Y P, JIANG Q W. Hill shading map generation principles and realization [J]. Computer Applications and Software, 2011, 28(9): 214-216.)

[5] VERONESI F, HURNI L. A GIS tool to increase the visual quality of relief shading by automatically changing the light direction [J]. Computers & Geosciences, 2015, 74: 121-127.

[6] JIN H, JESPERSEN D, MEHROTRA P, et al. High performance computing using MPI and OpenMP on multi-core parallel systems [J]. Parallel Computing, 2011, 37(9): 562-575.

[7] GEPNER P, KOWALIK M F. Multi-core processors: new way to achieve high system performance [C]// PARELEC 2006: Proceedings of the 2006 International Symposium on Parallel Computing in Electrical Engineering. Washington, DC: IEEE Computer Society, 2006: 9-13.

[8] ZHANG S H, XIA Z X, YUAN R, et al. Parallel computation of a dam-break flow model using OpenMP on a multi-core computer [J]. Journal of Hydrology, 2014, 512: 126-133.

[9] ZHOU G Y, LIU X L, FU S H, et al. Parallel identification and filling of depressions in raster digital elevation models [J/OL]. International Journal of Geographical Information Science, 2016: 1-18 [2017- 01- 10]. http://dx.doi.org/10.1080/13658816.2016.1262954.

[10] YILDIRIM A A, WATSON D, TARBOTON D, et al. A virtual tile approach to raster-based calculations of large digital elevation models in a shared-memory system [J]. Computers & Geosciences, 2015, 82: 78-88.

[11] SHARMA R, XU Z W, SUGUMARAN R, et al. Parallel landscape driven data reduction & spatial interpolation algorithm for big LiDAR data [J/OL]. ISPRS International Journal of Geo-Information, 2016, 5(6): 97:1-14 [2016- 10- 15]. http://dx.doi.org/10.3390/ijgi5060097.

[12] YANG J H, ZHANG J X. Parallel performance of typical algorithms in remote sensing-based mapping on a multi-core computer [J]. Photogrammetric Engineering & Remote Sensing, 2015, 81(5): 373-385.

[13] 陳艷麗,陳欣,魏蘭.數(shù)字地貌暈渲光源的設(shè)置和應(yīng)用研究[J].測繪與空間地理信息,2016,39(1):91-93.(CHEN Y L, CHEN X, WEI L. The research on setting and application of light sources of digital relief shading [J]. Geomatics & Spatial information Technology, 2016, 39(1): 91-93.)

[14] 王宗躍,馬洪超,徐宏根,等.在集群多核CPU環(huán)境下的等高線并行提取方法[J].計算機工程與應(yīng)用,2010,46(17):5-7.(WANG Z Y, MA H C, XU H G, et al. Method of parallel contours extraction based on multi-core CPU [J]. Computer Engineering and Application, 2010, 46(17): 5-7.)

[15] 徐昕.基于單機多核格網(wǎng)DEM填洼并行算法的研究與實現(xiàn)[J].城市地理,2015(24):96-97.(XU X. Research and implementation of parallel algorithm filling grid DEM based on multi-core computer [J]. Cultural Geography, 2015(24): 96-97.)

[16] 陳景廣,佘江峰,宋曉群,等.基于多核CPU的大規(guī)模DEM并行三維暈渲[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2013,38(5):618-621.(CHEN J G, SHE J F, SONG X Q, et al. Parallel rendering of large-scale DEM based on multi-core CPU [J]. Geomatics and Information Science of Wuhan University, 2013, 38(5): 618-621.)[17] 黃先鋒,孫巖標,張帆,等.多核計算環(huán)境下的LiDAR數(shù)據(jù)DEM內(nèi)插方法研究[J].山東科技大學(xué)學(xué)報(自然科學(xué)版),2011,30(1):1-6.(HUANG X F, SUN Y B, ZHANG F, et al. Research on DEM interpolation method with Lidar data under multi-core computing environment [J]. Journal of Shandong University of Science and Technology (Natural Science), 2011, 30(1): 1-6.)

[18] 王順緒.多核計算機上并行計算的實現(xiàn)與分析[J].淮海工學(xué)院學(xué)報(自然科學(xué)版),2009,18(3):30-33.(WANG S X. Implementation and analyses of parallel computation on multi-core computers [J]. Journal of Huaihai Institute of Technology (Natural Science Edition), 2009, 18(3): 30-33.)

This work is partially supported by the National Natural Science Foundation of China (41201381, 41376108), the Open Fund of Engineering Laboratory of Spatial Information Technology of Highway Geological Disaster Early Warning in Hunan Province (kfj150605).

HANLitao, born in 1978, Ph. D., associate professor. His research interests include virtual geographical environment, spatial information visualization.

LIUHailong, born in 1995, M. S. candidate. His research interests include geographical information system.

KONGQiaoli, born in 1979, Ph. D., lecturer. Her research interests include global positioning and navigation system.

YANGFanlin, born in 1974, Ph. D., professor. His research interests include marine surveying and mapping, ocean GIS.

Parallelalgorithmforhillshadingundermulti-corecomputingenvironment

HAN Litao1,2*, LIU Hailong1, KONG Qiaoli1,3, YANG Fanlin1,2

(1.CollegeofGeomatics,ShandongUniversityofScienceandTechnology,QingdaoShandong266590,China;2.KeyLaboratoryofSurveyingandMappingTechnologyonIslandandReed,NationalAdministrationofSurveying,MappingandGeoinformation(ShandongUniversityofScienceandTechnology),QingdaoShandong266590,China;3.EngineeringLaboratoryofSpatialInformationTechnologyofHighwayGeologicalDisasterEarlyWarninginHunanProvince(ChangshaUniversityofScience&Technology),ChangshaHunan410004,China)

Most of the exiting hillshading algorithms are implemented based on single-core single-thread programming model, which makes them have lower computational efficiency. To solve this problem, an improved algorithm for parallelizing the existing hillshading algorithms based on multi-core programming model was proposed. Firstly, the original Digital Elevation Model (DEM) data were divided into several data blocks by grid segmentation. Secondly, these data blocks were shaded in parallel using the class Parallel under the .Net environment to generate shaded image of each block. Finally, the shaded images were spliced into a complete hillshading image. The experimental results show that the calculation efficiency of the improved parallelized algorithm is obviously higher than that of the existing shading algorithms based on single-core single-thread programming, and there is an approximate linear growth relation between the number of the involved cores and the shading efficiency. Additionally, it is also found that the three dimensional and realistic effect of the hillshading image is extremely relevant to the parameter setting of the light source.

multi-core environment; Digital Elevation Model (DEM); hillshading; parallel computing; data segmentation; image mosaic

P283.3; TP391

:A

2017- 02- 08;

:2017- 03- 06。

國家自然科學(xué)基金資助項目(41201381, 41376108)；公路地質(zhì)災(zāi)變預(yù)警空間信息技術(shù)湖南省工程實驗室開放基金資助項目(kfj150605)。

韓李濤(1978—)，男，山東菏澤人，副教授，博士，主要研究方向：虛擬地理環(huán)境、空間信息可視化； 劉海龍(1995—)，男，山東菏澤人，碩士研究生，主要研究方向：地理信息系統(tǒng)； 孔巧麗(1979—)，女，山東菏澤人，講師，博士，主要研究方向：全球定位與導(dǎo)航； 陽凡林(1974—)，男，湖北荊州人，教授，博士，主要研究方向：海洋測繪、海洋GIS。

1001- 9081(2017)07- 1911- 05

10.11772/j.issn.1001- 9081.2017.07.1911