一種啟發式有環河系自動分級算法

郝志偉，李成名，殷 勇，武鵬達，吳 偉

(中國測繪科學研究院，北京 100830)

一種啟發式有環河系自動分級算法

郝志偉，李成名，殷 勇，武鵬達，吳 偉

(中國測繪科學研究院，北京 100830)

在地圖綜合中，河流分級是對水系要素表達的重點也是技術難點，對精確性和計算速度都有較高的要求。目前對河系分級的研究中，已有分級算法的效率較低，且鮮有針對有環河系的分級。基于此，本文建立了河系分級的屬性規則、幾何規則、環規則，對河系中存在的不同環類型進行了分類處理，且在求取河流最長路徑時，運用啟發式算法迭代計算，實現了河系的自動分級。實際河系數據試驗表明，該算法能在對有環河系的處理中取得良好的效果，提高了河系分級的計算效率和準確度。

地圖制圖；河流分級；有環河系；啟發式算法

在計算機制圖的時代，GIS軟件的功能日益強大，應用更加廣泛。在對河流進行分級時，不必像過去一樣對每一條河段進行選取、查看，而是依賴自動成圖的手段，通過河段的屬性、幾何特征等信息對河流進行自動分級。相較于人工指定河流等級，自動分級不僅減輕了人工煩瑣的勞動，也提高了河流分級的精確度。

目前對河流進行自動分級的研究有：毋河海[1]建立了河流樹對進行分級，并認為河流中主流具有最大的長度，可以通過尋找最大長度的河流來確定主流，但僅用河流的長度來確定主流時，分級的結果不顧及河流的流向和特征，只追求最長，導致分級不準確；Paiva[2]等針對河流中各條河段流向的地質知識，即在河流的匯合處,上下游河段的流向幾乎在一條直線上，提出了一種用角度判別等級的方法,但僅用角度進行分級時，若在河段的節點處出現角度偏差，分級結果也會出現較大偏差；郭慶勝[3]等認為，主流往往是最長的河流，在節點處也符合180°假設，將兩種方法結合起來對河流進行主支流的判斷，通過長度角度來綜合考慮河流等級，但未考慮河流的屬性信息和河流的實際意義；吳偉[4]等在對河流進行漸變時，運用了流向、圖層、名稱等的屬性信息進行約束，加強了河流分級的合理性，但僅用角度進行分級會出現一些分級錯誤。以上的研究工作中，均未對河系中的環進行處理，且在求取河流的最長路徑時效率較低。

綜上，本文運用屬性和幾何規則對河系進行了分級，依據河系中不同的環類型分為單入單出環和多入多出環；并對不同類型的環運用最短路徑和角度優先的方法進行了處理；同時，對于幾何規則判斷中最長路徑搜索效率較低的問題，采用了啟發式的算法，減少了搜索的次數，從而提高了效率。

1 河流分級規則

在已有的研究成果中，河流分級的基本方法可總結如下[5-9]：

首先，對河系信息進行重新組織，構建河流樹，以河流的一個匯出點作為起始節點來進行河流的搜索，尋找主流，并將主流作為河流的第一級；將該主流從河系中去除，從主流中存在支流的節點繼續搜索，尋找主流，作為河流的第二級；遞歸調用對河流進行搜索，依次向下分級，直到河流的所有河段都被搜索過為止。

在搜索的過程中，如何準確地確定主流至關重要，決定了最終的河流分級結果[10-11]。對河流主流的判斷采用屬性信息和幾何特征相結合的方式。其中，河流的屬性包括：河流的名稱、河流的類型、河流的流向等；幾何特征包括：河流的角度、河流的長度、河流是否有環等。本文據此提出河流分級的規則如下：

1.1 屬性信息規則

運用河流的屬性特征建立一些規則來確定主流，這些信息可以從河流的屬性信息中讀取和判斷，規則如下(優先級自上而下)：

(1) 河流流向約束原則，即流向與當前河流不一致的河流不能構成同一河流。

(2) 河流類型約束原則，即相同的河流類型優先構成同一河流。

(3) 河流名稱約束原則，即相同的河流名稱優先構成同一河流。

如圖1所示，當前河流均是A河流，分別依據上述原則，選擇B為下一條主流。

圖1 主流選擇示意圖

1.2 幾何特征規則

若河流無屬性信息或屬性信息不足以確定哪一個候選河段為主流時，就需要以河流的形狀特征來判斷。河流的幾何特征主要是河流的角度、長度。河流的角度是判斷當前河段與下一河段的角度，優先選擇平直的河段；而河流的長度則是判斷下一河段是否在從當前河段出發的最長路徑上，優先選擇在最長路徑上的河段。規則如下(優先級自上而下)：

(1) 長度優先原則，若該河段出發的最長路徑遠遠大于其他路徑，則選擇最長路徑上的河段優先構成同一河流。如圖2所示，應用該原則選擇路徑長的作為河流的主流。

圖2 長度優先原則

(2) 角度優先原則，若從該河段出發的最長路徑與候選河段的長度相近，且候選河段的角度比最長路徑上的角度好很多，則應選擇角度好的候選河段作為主流。如圖3所示，應用該原則選擇角度較好的作為河流主流。

圖3 角度優先原則

1.3 環規則

上述基本原則可以對無環的河流進行分級，但當河流中出現環時，上述規則對河流的分級效果欠佳。因此，本文對環進行了詳細的分類，以選擇不同的方法對河流環進行處理。

1.3.1 單入單出環

河流中的單入單出環是指只有一個入口和一個出口的環。單入單出環在河流分級中最為常見，由于環的凸起部分路徑往往較平直的路徑長，運用上述原則對環進行判斷時，一般選擇長度較長的那條路徑，會造成分級的錯誤。因此，需要對河流中的單入單出環作判斷。在找出單入單出環后，選擇從環的入口到出口之間的路徑最短的或與入口處的弧段所成的角度較好的那條路徑作為主流，可以大大減少單入單出環的分級錯誤。如圖4所示的單入單出環，選擇了長度較短路徑的作為河流的主流。

圖4 河流中單入單出環

1.3.2 多入多出環

多入多出環則是河流環有多個入口或多個出口，環中的河流流向多條河流，如圖5所示。這時，可以遵照角度優先的原則，即選擇入口河段與環的兩條路徑中所成角度最好的作為主流，這樣就可避免大多數多入多出環的分級錯誤。如圖5所示的多入多出環，選擇角度較好的作為河流的主流。

圖5 河流中多入多出環

2 河流的自動分級

河流的自動分級首先需要對河系構建河系樹，尋找河流的一個匯出點作為起始節點來搜索；再通過主流識別，確定該條主流的等級；最后進行迭代處理，從而對每一條河流進行分級。主流識別需要利用河流的屬性信息和幾何特征，根據上文所述的規則進行判斷。在分級的過程中，屬性信息優先級大于幾何特征優先級，即先通過屬性信息判斷等級，在無屬性信息或屬性信息不足以分級的情況下，再用幾何信息進行分級。

圖6是一個河系，N1為匯出點，河系的屬性信息見表1。

圖6 河系圖

表1 河系的屬性信息

2.1 屬性信息確定主流

根據上文所述的屬性信息規則，可以運用屬性信息對河流的主流進行判斷。如圖6所示，在M2處，由于(M2，S1)為時令河，與上一個河段的河流類型不同，因此選擇(M2，M3)為主流。又如在N2處，選擇下一條主流河段，由于兩條候選河段與(N1，N2)的類型都相同，因此用名稱信息來判斷主流。由于(N2，M1)的河段名稱與(N1，N2)河段不同，而與(N2，N3)的名稱相同，因此選擇(N2，N3)作為主流河段。在N3節點處，(N3，N7)與(N3，N4)為兩條候選河段，兩個河段的類型和名稱均相同，因此需要用幾何特征來選擇主流河段。

2.2 幾何特征確定主流

在幾何規則中，采用長度結合角度判斷主流的方式對主流進行判別。利用長度判別時，需要尋找河流的最長路徑，這可認為是對有向圖進行單源最長路徑的搜索問題。對河系樹的最長路徑問題[12]描述如下：

設G=(V,A)是一個完全連通圖，V={0,1,…,n}節點集合，(Xn,Yn)是節點n的地理坐標，A={(i,j),i,j∈V}是弧集合。其中,0節點是起始節點,最長路徑的求解目標是找到一條從起始節點出發的最長的路徑。

在河流最長路徑的問題中，河流信息通常以空間數據庫的方式存儲，不僅有地理要素的屬性數據，還有空間數據[13]。利用這些地理要素的位置數據，就可以對搜索的路徑進行啟發。搜索過程中引入啟發信息，可以省略大量無效的搜索路徑，提高效率。

啟發式算法計算最長路徑算法描述如下：

(3) 將節點n作為當前節點，按照步驟(2)的方法繼續向下搜索，直到搜索到葉子結點，查看該葉子結點是否在待搜索的目標節點集合T中，若在，刪除T中的該節點。

(4) 若目標節點集合為空，結束搜索；若不為空，選擇當前節點為未完全搜索節點隊列S的末尾節點，到步驟(2)繼續搜索。

如在N3處，(N3，N7)與(N3，N4)為兩條候選河段，且屬性信息相同，因此需要用幾何特征來選擇主流河段。分別用啟發式算法計算從N3出發經過N7和N4的最長路徑，并進行比較選擇主流。

如圖7所示，計算從N3出發經過N7的最長路徑。經過篩選后目標節點集合為{N15，N16}，未完全搜索節點集合為空，當前狀態空間的起始節點為N7，節點N7有兩個可擴展節點N17和N8，選擇目標節點為N16，f(N7，N17)=g(N7，N17)+h(N17)=lengthN7N17+distN17N16，f(N7，N8)=g(N7，N8)+h(N8，N17)=lengthN7N8+distN8N17，計算min{f(N7，N17)，f(N7，N8)}，因此f(N7，N8)較小，因此選擇下一個節點為N8節點。同時，將節點N7放入未完全搜索節點集合中，繼續搜索，直到搜索到目標節點N16，目標節點集合刪除N16，未完全搜索集合放入節點N14。下一個目標節點為N15，從未完全搜索集合中取出最新放入的節點N14，繼續搜索，搜索到N15，目標節點集合刪除N15，集合為空，程序結束。

圖7 啟發式算法選擇主流

在N8、N10節點處，河段有環，且環的類型為多入多出環，因此選擇角度最好的河段作為主流河段，因此(N8，N9)、(N9，N10)、(N10，N12)、(N12，N13)為主流河段。

2.3 河流自動分級

從N1節點搜索到N16節點為止，為一級河流。將一級河流從河系中去除，再進行迭代。圖8為迭代一次后的結果。

圖8 迭代一次后的結果

對主流上的節點繼續搜索，直到所有河段都被搜索和分級過為止。最終的分級結果如圖9所示。

圖9 分級結果

3 試驗與分析

試驗平臺基于WJ-Ⅲ無級地圖工作站，開發環境基于Microsoft Visual Studio 2010，采用C++編程語言，試驗測試的環境為單臺PC機，系統版本為Windows 7，系統類型為64位操作系統，CPU為Intel Core i7-6700，主頻為3.40 GHz，內存(RAM)為4 GB。試驗數據采用地理國情監測的水系數據，對水系進行分級試驗。水系數據中已有的信息包括：河流的流向、河流的類型、河流的名稱。

試驗利用兩個地區的水系數據，對用啟發式算法優化前和優化后的情況進行測試，見表2。

由試驗結果可以看出，對不同地區的河流數據進行分級的過程中，優化算法后，遍歷的弧段數和時間都有不同程度的減少，但分級的結果相同，效率有所提高，且弧段總數越多，提升的時間越明顯。對啟發式算法的精確度和時間分析如下：

(1) 算法精確度：啟發式算法與原算法的不同僅出現在對河流終結點的篩選中，可能將正確結果篩選掉。但在實際情況中，通過屬性信息的分級后，運用該算法搜索的河流往往是一些較小的支流，通常短而直，因此正確的終結點被篩選掉的情況極少。

表2 長度算法優化前后的對比

(2) 算法時間：在未優化的情況下，該算法是完全遍歷，需要搜索每一個弧段，找出最長路徑。優化后的算法首先會尋找符合條件的候選終結點，再通過啟發信息對這些終結點進行尋找，通過減少搜索的次數來縮短算法的時間。優化后的最好情況下，在尋找最長路徑時，目標節點只有一個，與起始節點構成一個最長路徑，且每一次啟發式選擇的節點都是該條路徑上的節點。此時，算法的總執行次數為最長路徑上的節點的個數。在最差情況下，則需要對所有弧段進行遍歷，與未優化時的情況相同。一般情況下，優化算法的時間介于最好和最差之間。

圖10(a)即為上述兩試驗地區之一的原始河系圖。分級后的等級用顏色和粗細區分出來，其中顏色越深、線條越粗的代表的河系等級越高。從圖10(b)、(c)的河系分級結果可以看出，基于以上規則，分級取得了良好的效果，對河流等級識別準確，層次分明。尤其河系中出現復雜情況時，如河系中有環、節點處有多條弧段時，分級的效果優于已有的河流分級的算法，滿足制圖要求。

圖10 試驗的分級結果

4 結 語

本文對河流分級的算法進行了改進，在準確性上，結合屬性信息和幾何特征的同時，通過對不同類型的環的處理，減少了復雜河流中尤其是有環河流的分級錯誤；在效率上，運用啟發式算法改進了河系最長路徑的算法，減少了搜索次數；并通過試驗證明了該方法的有效性和合理性。在對河流分級的過程中，還可以考慮河流的更多幾何特征，如河流的密度、河流的左右分支的數目等信息，以更進一步提升河流分級的準確性。

[1] 毋河海.自動綜合的結構化實現[J].武漢大學學報(信息科學版),1996,21(3):277-285.

[2] PAIVA J, EGENHOFER M J, FRANK A.Spatial Reasoning about Flow Directions: Towards an Ontology for River Networks[J].International Archives of Photogrammetry and Remote Sensing, 1992, 24(B3):318-324.

[3] 郭慶勝, 黃遠林.樹狀河流主流的自動推理[J].武漢大學學報(信息科學版),2008,33(9):978-981.

[4] 吳偉, 李成名, 殷勇,等.有向拓撲的河系漸變自動繪制算法[J].測繪科學,2016,41(12): 89-93.

[5] 張園玉,李霖,金玉平，等.基于圖論的樹狀河系結構化繪制模型研究[J].武漢大學學報(信息科學版), 2004,29(6):537-539，543.

[6] 張青年, 全洪.河系樹的建立及其應用[J].中山大學學報(自然科學版),2005，44(6):101-104.

[7] 艾自興.地理信息系統中的河網平面結構模型及其自動建立[J].測繪,1995(2):75-79.

[8] 郭慶勝. 河系的特征分析和樹狀河系的自動結構化[J].地礦測繪, 1999(4):7-9.

[9] 張青年. 線狀要素的動態分段與制圖綜合[J].中山大學學報(自然科學版),2004，43(2):104-107.

[10] 艾自興, 牛瑞芳, 毋河海，等.基于動態樹結構的河網分析方法[J].測繪科學, 2006,31(3):80-81.

[11] 譚笑, 武芳, 黃琦，等.主流識別的多準則決策模型及其在河系結構化中的應用[J].測繪學報, 2005,34(2):154-160.

[12] 王建新, 楊志彪, 陳建二.最長路徑問題研究進展[J].計算機科學，2009,36(12):1-4，31.

[13] 鄔倫, 劉瑜.地理信息系統原理、方法和應用[M].北京：科學出版社，2001:133-134.

[14] 蔡自興, 徐光祐.人工智能及其應用[M].2版.北京：清華大學出版社，1996:71-73.

[15] 陸汝鈴.人工智能[M].北京：科學出版社，1996:259-261.

AHeuristicAlgorithmforAutomaticClassificationofRiverSystemwithRing

HAO Zhiwei,LI Chengming,YIN Yong,WU Pengda,WU Wei
(Chinese Academy of Surveying and Mapping，Beijing 100830，China)

The river classification is the key point and the technical difficulty for river expression in the map generalization, and the accuracy and calculation speed are higher requirements. In the previous research on river system classification, the algorithm’s efficiency is low, and ring is without consideration in river system. Based on this, we set up the attribute rules, geometric rules and ring rules of river system classification to process different types of ring and use heuristic algorithm to realize the automatic classification of rivers system. The test results show that the river system containing rings can achieve good effect by this algorithm, and reduce the computation time.

map cartographic; river classification; river with a ring; heuristic algorithm

郝志偉，李成名，殷勇,等.一種啟發式有環河系自動分級算法[J].測繪通報，2017(10)：68-73.

10.13474/j.cnki.11-2246.2017.0318.

2017-02-17

測繪地理信息公益性行業科研專項(201512020；201512027)

郝志偉(1993—)，男，碩士，主要研究方向為自動化制圖綜合和人工智能的實踐和應用。E-mail: hao_zhi_wei@sina.com

P283

A

0494-0911(2017)10-0068-06