基于多核計算環境的地貌暈渲并行算法

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

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

基于多核計算環境的地貌暈渲并行算法

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

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

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

多核環境；數字高程模型；地貌暈渲；并行計算；數據分塊；圖像拼接

0 引言

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

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

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

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

1.1 坡度與坡向計算

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

(1)

(2)

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

求解fx和fy方法是通過3×3的移動窗口掃描整個格網DEM，利用移動窗口中的格網點高程，按照給定的計算方法來計算中心格網點的fx和fy。常用的計算fx和fy的方法有數值分析法、快速傅里葉變換法、局部曲面擬合法和空間矢量法等。根據移動窗口中格網單元參與計算方式的不同，數值分析法又分為簡單差分法、二階差分法、三階不帶權差分法(Sharpnack算法)、三階反距離平方權差分法(Horn算法)、三階反距離權差分法和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個格網高程，g為DEM格網間隔。移動窗口上各個格網單元的編號如圖1所示。

圖1 3×3高程分析窗口

1.2 RSG邊緣處理

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

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

圖2 RSG邊緣處理

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

1.3 RSG網格光照強度計算

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

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

(5)

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

2 地貌暈渲并行算法

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

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

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

圖3 DEM暈渲并行算法流程

2.1 DEM數據分塊

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

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

圖4 DEM數據分塊

2.2 .NET環境下地貌暈渲的并行化

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

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

GetCPUNumber();

//獲取CPU數 GetMemory();

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

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

MergeImage();

//圖片拼接

Case 2:

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

Graphics12=Graphics.FromImage(bitmap12);

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

//圖片拼接

Case 4:

//四核 … }

程序運行時，主線程由系統自動生成，負責監管整個程序的運行，統一進行系統資源的調配；任務線程由主線程逐個啟動，線程數量取決于數據塊的數量，同時被系統分配到不同的CPU內核中，不同內核上運行的任務線程互相獨立。

2.3 暈渲結果拼接

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

3 實驗結果與分析

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

3.1 地貌暈渲效果分析

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

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

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

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

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

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

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

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

3.1.3 與ArcGIS地貌暈渲效果對比

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

圖7 本文算法與ArcGIS的暈渲結果對比

3.2 CPU核數對暈渲效率的影響

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

表1 不同DEM數據量的計算耗時和加速比對比

圖8 CPU核數與暈渲計算耗時關系

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

4 結語

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

References)

[1] 張玲,楊曉平,魏占玉,等.三維數據的二維可視化方法綜述[J].地震地質,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].計算機應用與軟件,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] 李少梅,闞映紅,陳艷麗,等.數字地貌暈渲光照模型研究[J].測繪科學技術學報,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] 丁宇萍,蔣球偉.地貌暈渲圖的生成原理與實現[J].計算機應用與軟件,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] 陳艷麗,陳欣,魏蘭.數字地貌暈渲光源的設置和應用研究[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環境下的等高線并行提取方法[J].計算機工程與應用,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] 徐昕.基于單機多核格網DEM填洼并行算法的研究與實現[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的大規模DEM并行三維暈渲[J].武漢大學學報(信息科學版),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] 黃先鋒,孫巖標,張帆,等.多核計算環境下的LiDAR數據DEM內插方法研究[J].山東科技大學學報(自然科學版),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] 王順緒.多核計算機上并行計算的實現與分析[J].淮海工學院學報(自然科學版),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。

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

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

1001- 9081(2017)07- 1911- 05

10.11772/j.issn.1001- 9081.2017.07.1911