基于GIS的復雜環境空間通達性預測方法研究

孫 騫，許 睿，萬 航

（1.桂林市環境監測中心站, 廣西 桂林 541002；2.桂林電子科技大學, 廣西 桂林 541004）

路徑通達性預測方法是人工智能領域中的一個研究熱點問題，并且已經在交通旅游、城市規劃、電子導航等領域得到了廣泛的應用。求解路徑可達性的預測算法很多，如Floyd算法、Dijkstra算法等[1]。這些算法在進行最佳路徑的規劃時，往往依賴于現存的交通路網，大多依賴于固定的路網節點，以路網固定節點間的路徑距離為因素建立權矩陣，然后通過分析計算，求解路網中任意兩點的最佳路徑；而對于沒有固定路網、地質起伏、障礙繁多的野外復雜空間環境，整個空間區域節點數目不確定，通達性計算方法復雜、工作量大，傳統的導航尋路方法已經很難滿足復雜空間環境中目的點最佳路徑的規劃要求，這就需要對現有的尋路方法進行改進研究，以滿足無路網空間環境中最佳路徑的選取和規劃。

A*算法是一種啟發式算法，它能夠在有限步內終止，并找到最優解，通過改進A*算法能夠實現野外復雜環境中目的點最佳路徑的搜索[2-4]。

1 野外復雜環境空間數據的處理

1.1 研究方法

根據通達性預測方法，選取特定地形影響因子數據，通過對各影響因子權重關系的分析，確定算法的估價函數。最終，結合高精DEM數據、NDVI植被數據以及Landsat影像數據，實現對野外復雜環境空間通達性的預測分析，為以后的路徑選取工作提供決策支持。具體研究步驟如圖1所示。

1.2 影響因子分析

通過DEM數據，預測空間的通達性狀況，實際上就是通過DEM高程數據，結合路徑搜索算法，實現空間起點和目的點最佳路徑的搜索。在對起點和目的點最佳路徑的分析計算之前，必須對影響路徑搜索的數值因子進行分析計算，它們包括：數字高程值Dk，用來描述當前點位置的數字高程信息；格網相鄰個數N，描述格網間的空間距離；坡度值P，描述空間點位置地形的起伏狀況；坡度容忍度T，坡度值在（-T，T）里格網才可達；格網地貌值GE（k），用來表示不同的地貌狀況，如山地、平原、河流等[5]； NDVI植被指數Z，用于檢測空間點位置植被覆蓋情況，取值在[-1,1]之間，負值表示地面覆蓋為冰、雨、雪等，對可見光反射，0表示地面為裸土巖石，數值越大，表示地面植被覆蓋度越高，通達性越差。

1.3 區域可達模型建立

利用GIS技術結合高精度DEM，通過分析和計算，確定區域鄰接格網的穿行代價。最終，根據空間穿行代價函數，建立野外復雜環境區域可達模型。

圖1 研究步驟

首先，結合DEM，通過移動窗口數據優化方法，判別點位置8方向DEM網格的可達性，確定區域可達網格集，實現DEM高程數據的優化[6-8]。然后，結合GIS的空間分析和圖像渲染技術，根據DEM高程圖和NDVI植被覆蓋圖，提取區域內空間環境的坡度和植被覆蓋情況。最終，通過改進A*算法，實現起始點和目的點最佳路徑的搜索。

坡度分析實現步驟：

1）加載DEM數字數據。

2）利用空間分析工具，實現對研究區DEM高程圖的裁剪。

3）根據DEM數字高程圖，計算區域坡度信息，選擇坡度表示方法，生成區域坡度渲染圖，如圖2所示。

圖2 坡度變化圖

NDVI植被指數分析步驟：

1）加載ENVI植被數據。

2）實現研究區NDVI植被圖的裁剪獲取。

3）通過計算，分析區域植被覆蓋情況，計算公式如下：

式中，NIR為近紅外波段；R為紅光波段。

4）進行輻射定標與大氣校正。

5）輸出NDVI植被覆蓋圖，植被覆蓋情況如圖3所示。

2 算法分析

2.1 A*算法估價函數選取

A*算法像Dijkstra算法一樣，能夠實現起始點到目的點最佳路徑的搜索[9-11]。區別在于A*算法具有啟發性，它能夠在啟發函數的引導下進行有目的的路徑搜索。A*算法的核心是估價函數f（n），算法如下：

圖3 植被覆蓋圖

式中，g（n）為出發網格到第n個網格的實際代價，因為DEM格網是規則等分網格，所以相鄰距離都是一定的。同時根據野外地形的實際情況，結合實地區域的距離、植被、坡度和地貌信息，定義A*的實際估價函數：

h（n）體現了算法的啟發性，它能夠估算當前節點到目標節點的代價值，引導算法快速、高效地獲取到達目的點的最短路徑。地理信息系統中的最短路徑搜索問題，大多數都是給定起始點，經過一定的中間節點，搜索最佳路徑。對于啟發式搜索方法來說，如果中間節點到目的點的方向與起始點到目的點的方向一致，那么最短路徑經過這個點的可能性就更大[12]。在用二維數組表示的DEM網格中，與起始點到目的點方向一致的中間節點往往就是中間點到目的點距離最短的點，所以定義啟發函數為：

式中，X（n）、Y（n）分別為節點在二維數組中的x，y下標。

2.2 算法優化

采用上述方法已經能夠實現野外環境空間通達性的預測，但算法的實現效率和準確度仍不是很高，需要對算法進一步優化。

A*算法的優化主要分為2個方面：①對Open表的優化，加快Open表的存儲訪問速度；②對估價函數f（n）的優化，改變估價函數的權值，實現搜索速度和準確率的提高。

從A*搜索原理來看，隨著搜索范圍的擴大，Open表中的節點數量會呈幾何倍數增長。對于越來越多的節點數量，算法根據啟發性原理，往往希望向最有可能達到目的點的方向進行搜索，這就需要在Open表中取出具有最小估價總值的節點。因此，有必要對Open表中的節點進行估價值計算，并按照估價值大小進行遞增排序，這樣每次進行算法運算時，只需取出第一個節點即可，可以降低算法的時間復雜度，提高路徑搜索的效率[13]。

對于估價函數，g（n）是源點到節點n的路徑代價，而啟發函數h（n）是節點n到目的點最短路徑的估價值，它決定了算法的搜索效率。理論上h（n）不能大于當前節點n到目的點的實際最短距離，最理想的情況是啟發函數的估計值與實際值相等，但在實際應用中估計值的大小只能盡可能地接近實際值。同時為保證算法的完備性和高效性，需要引入加權模型來平衡估價函數中各影響因子的權重。本文針對高精度DEM數據，引入加權因子，定義如下：

隨著n的增大，減小k2的取值，使啟發函數的值接近實際值，以此提高搜索的精度和效率。

2.3 實現步驟

根據分析結果，確定算法流程（圖4）：

1）DEM格網的初始化。

2）創建Open表，加載源點信息。

3）判斷Open表是否為空，若為空則尋路失敗。

圖4 算法流程

4）取出Open表中估價值最小的節點V，并放入Close表中。

5）如果節點V為終點，則尋路成功，轉向7）。

6）如果V不是終點，則對相鄰的8個方向節點進行判斷：①如果節點在Close表中，則返回6）繼續；②如果該節點不在Open表中，則將節點添加到Open表中，計算估價值，并按照大小順序進行遞增排序；③如果節點在Open表中，則計算節點的估價值，并與舊值進行比較，選擇較小值，更新Open表；④如果8個方向檢查完畢，則轉向3），否則，轉向6）。

7）輸出路徑。

3 實驗結果與驗證

根據實驗需求，選取比例尺為1∶10 000，格網間距為5 m的高分辨率DEM數字高程圖，結合算法，在圖層范圍內任意選取2點作為算法的起始點和目的點，通過仿真，建立空間通達性預測模型，實現源點和目的點最佳路徑的規劃。路徑輸出渲染結果如圖5所示。

圖5 路徑輸出圖

根據數值高程圖，選取左上角A點作為方法的起點，B點作為方法的目的點。結合改進A*算法，方法能夠根據DEM和NDVI數據信息，實現空間最短路徑的準確、快速搜索。路徑表現為一條細長曲折的運動軌跡線。實驗結果表明，野外環境中建立空間可達性模型，能夠在野外行軍、森林救火、雪崩救援、抗洪救災等方面得到應用。

4 結 語

構建了一種基于GIS的野外復雜環境空間通達性預測方法。通過改進A*算法，該方法能夠實現野外環境中最佳路徑的搜索，可在野外無拓撲道路的地形環境中得以應用，具有一定的合理性和實用性。但在現實應用中，模型仍存在著一些不足之處，主要包括DEM格網的采集精度、Landsat影像數據和NDVI植被覆蓋數據的分辨率、NDVI大氣影響校正指數、坡度提取的準確度等，這都需要進一步研究和探討。目前，本系統僅能對單一精度的遙感影像數據進行最佳路徑的規劃分析，而對不同精度、不同需求的影像數據的分析計算，系統仍需優化完善。后續可采用分層和并行計算的思想來完善系統，提高方法的運行速度與計算效率。

[1]Felner A, Stern R, Ben-Yair A, et al.PHA*:Finding the Shortest Path with A* in an Unknown PhysicaL Environment[J].Journal of Artif icial Intelligence Research, 2004(21): 631-670

[2]張和平, 張前哨.A*算法在游戲地圖尋徑中的應用與實現[J].計算機應用與軟件, 2005 (12): 198-200

[3]劉浩.A*算法在矢量地圖最優路徑搜索中的應用[J].計算機仿真, 2008, 25(4): 253-257

[4]Goldberg A, Kaplan H, Werneck R.Reach for A*: Efficient Point–to-Point Shortest Path Algorithms[C].Philadelphia,United States: Workshop on Algorithm Engineering and Experiments, Miami Society for Industrial and Applied Mathematics Publications, 2006

[5]胡偉, 盧小平, 盧遙, 等.基于移動窗口法的DEM數據優化方法研究[J].測繪通報, 2011(5): 45-47

[6]原江波, 母攀良, 史樂,等.大場景中虛擬車輛自動尋路的高效算法[J].計算機工程與設計, 2008, 29(10): 2 622-2 625

[7]陳易, 王晶.帶通行限制的加權A*算法及其數據庫實現[J].北京化工大學學報, 2009, 36(5): 107-111

[8]李建元, 師軍, 曹菡, 等.一種分層尋路算法中的域值放棄策略[J].計算機應用, 2007, 27(2): 473-478

[9]于曉艷, 馬勁松, 劉艷, 等.城市通達性面狀分布模型研究[J].水電能源科學, 2010, 28(6): 56-58

[10]林篤斌, 李欣.基于DEM格網的改進型A*路徑搜索算法[J].計算機工程與設計, 2011, 32(10): 3 414-3 418

[11]劉學軍, 卞璐, 盧華興.顧及DEM誤差自相關的坡度計算模型精度分析[J].測繪學報, 2008, 37(2): 200-206

[12]曹強, 張明智, 李志強, 等.CTI中車輛實時最佳路徑搜索算法設計與實現[J].系統仿真學報, 2009, 21(21):6 777-6 780

[13]嚴寒冰, 劉迎春.基于GIS的城市道路網最短路徑算法探討[J].計算機學報, 2000, 23(2): 210-215