樹狀結構引導下的脊線層次劃分方法研究

高 翔，徐 柱＊

（西南交通大學遙感信息工程系，四川 成都 611756）

0 引言

不同尺度下的DEM表達不同尺度的地形信息，為獲得粗尺度的地形信息，需對精細尺度的DEM進行綜合［1－4］，基于結構線的方法能夠保證粗尺度下的DEM充分保留原始地形的骨架結構，因此常采用該方法實現尺度轉換［5，6］。首先需獲得具有層次的山谷線與山脊線［7］，即需對谷線與脊線實施分級。對于山谷線，其層次劃分方法已較為成熟［8－10］。對于山脊線，主要有基于分形的方法與基于圖論的方法。基于分形的方法［8，11－17］優點在于與地理學中的分形理論相契合，缺點在于難以采用簡單的數據結構表達地形特征線。基于圖論的方法能較好地克服這一缺陷，將特征線表達為圖中的節點，將線段間的拓撲聯通關系表達為節點的連接邊，以此將復雜的地形特征結構轉換為計算機易于實現的圖結構。現階段，眾多學者已采用這一方法實現了水網結構的層次劃分［18，19］，鑒于脊線與水網在地形中呈現出某種程度的結構相似性，因而，同樣可以借用圖論方案研究脊線中的層次結構。

為利用圖論方案構建脊線層次，需要確定脊線段間的層次關系。傳統的樹結構層次劃分方案有3種：基于長度的層次劃分法［20］、基于角度逼近的層次劃分法［21］和谷線耦合分層法［22］。前兩種層次劃分方案嘗試利用脊線的幾何形態對線段的層次等級進行評估，從地理學的角度考慮，現實地表中的脊線主干線段長度并不一定大于支干，主干線段間的連接形態也并非總是逼近于直線，因而這類方案并不適合。與前兩種方案相比，第三種層次劃分策略地理學意義更強，然而該方法最大的缺陷在于脊線的層次確定過程極大地依賴于谷線的分級結果，谷線的分級方法較多，不同方案下其分級結果不盡相同，得到的脊線層次也將隨之改變，這使得脊線的分級過程存在較大的不確定性，無法為實際應用提供準確、唯一的數據支撐。脊線的分形結構雖與谷線共軛，但其分級應是一個面向其自身結構的、獨立式的過程。考慮到脊線等級越高，其在地表中的覆蓋范圍越廣，這在結構上表現為整體跨度越大。

基于這一地理學意義，本文提出一種新的山脊線層次劃分方案。首先從脊線自身的拓撲結構出發，將脊線表達為具有多個根節點的二叉樹，用樹的深度對脊線的區域跨度進行丈量，從而將脊線的層次劃分問題轉換為樹的主支干判別問題，并從脊線拓撲結構的表達與樹的主干搜索兩個角度對層次劃分過程進行論述。實驗部分分別從脊線層次劃分結果、分級算法效率及不確定性擾動效應三方面對新方法的有效性進行驗證。

1 層次劃分研究

1.1 脊線樹的構建

脊線中的一級主干與一個或多個二級主干相連，二級主干與一個或多個三級主干相連，多叉樹能夠很好地表達這一分形特征。樹中的節點表示地理實體中的脊線段，節點間的聯通關系用以表達脊線段的拓撲結構。

由于脊線中不存在地理意義上的出入口，且脊線本身不具有流向信息，基于這一無向的拓撲結構構建多叉樹，首先需確定脊線的根節點位置。考慮到脊線兩端的線段通常距離流域出口最近，為簡單起見，選用脊線段集合中距離流域出口最近的線段作為根節點。然后，逐一計算與其相連的脊線段，并將其作為當前節點的子節點，重復執行該過程直到將所有脊線段納入至多叉樹中。研究發現，隊列能夠很好地模擬上述過程，具體的實現方法為：1）將當前節點插入至隊列中，計算與其聯通的節點，并將這些節點標記為當前節點的子節點；2）將當前節點從隊列中移除，同時將其子節點插入至隊列中；3）重復執行第二步，直到完成子樹中所有節點的處理；4）搜索新的根節點，跳轉至第一步，進行新一輪的廣度優先遍歷，直到所有脊線段均處理完成。圖1進一步描述了脊線樹的構建過程，當前子樹共有9條脊線段，首先從集合中選取距離流域出口最近的脊線段（1號線段）作為樹的根節點并加入至隊列中，接著，搜索與1號線段相連的2號與3號子線段，將其加入至隊列中，同時將1號線段從隊列中移除，這一過程將反復執行，直到完成所有線段的遍歷。

1.2 脊線的分層與遍歷

完成脊線樹的構建后，需基于樹結構搜索山脊線的主干與支干從而完成脊線的層次劃分。樹結構傳統的遍歷方式是從其根節點處開始逐層向下搜索，然而這一過程需基于線段的重要性程度選取同級子節點，線段重要性程度的確定存在較大的隨意性，不同的策略必將導致不一致的重要性確定結果。針對這一點，本文提出一種深度優先的節點選擇方案。首先在子樹中搜索具有最大深度的葉子節點，之后從葉子節點開始，自下而上逆向遍歷，直到搜索至根節點為止。這一遍歷路徑上所有節點將作為脊線的同級主干，這一過程將反復執行，直到所有節點均被賦予等級。該方法充分利用多叉樹特有的結構特征，將父節點與子節點的一對多的聯通關系轉換為子節點對父節點的一對一的聯通關系，所以能夠解決傳統分級方法存在的缺陷。值得注意的是，當地形較為復雜時，脊線中可能存在少部分具有相同深度的葉子節點，考慮到脊線兩端的線段距離流域出口最近，因此，選擇至最近流域出口距離最短的葉子節點作為最終的搜索起點。

在上述多級主干的確定過程中，需重點關注采用何種搜索遍歷模式。傳統的主干搜索模式是對已遍歷的節點進行標注，在確定新一級主干時，依次判斷當前遍歷線段是否已處理，若已處理，則停止搜索，否則，繼續后續遍歷（后文稱之為“節點標注法”）［19］；然而，當地形較為復雜時，樹中存儲的脊線段較多，這種遍歷方式需進行大量重復性的節點判別，從而極大降低脊線的分級效率。為高效確定脊線的層次結構，應最大限度地避免節點遍歷的重復性。考慮到當某節點的父節點作為主干成員被刪除后，當前節點的父節點為空，該節點將作為新子樹的根節點參與至后續的分級過程中，這表明多叉樹的分解具有極強的靈活性。為充分利用多叉樹的這一特征，采用多級主干抽離方法完成脊線的層次劃分，其過程可描述為：1）基于深度優先法確定搜索的起始節點；2）逆向遍歷，確定脊線的當前主干，并將其從多叉樹中移除；3）分解多叉樹，完成新樹的重構，繼續進行次級主干的搜索。圖2進一步描述了脊線樹的分解過程：當確定脊線的一級主干＜1－3－6－12＞后，將其從樹中移除，多叉樹自行分解為3棵子樹，并獲得二級主干＜2－5－10－21＞、＜24＞、＜13－26＞以及＜7－14－29＞，將二級主干從樹中移除，多叉樹自行分解為6棵子樹，這一過程將持續進行，直到所有脊線段均獲得等級。

2 實驗分析

2.1 實驗樣區的選擇

實驗分別選取SRTM 90 m分辨率與GDEM 30 m分辨率DEM進行山脊線的層次劃分研究，第一幅DEM的區域跨度為171 km×114 km，第二幅DEM的區域跨度為：20 km×13 km；同時，地形高差、平均坡度及表面粗糙度數據表明兩研究區域在地形起伏與形態復雜度上也存在一定程度的差異（表1）。因而，實驗將在不同尺度、不同地形復雜度的區域上進行脊線層次劃分方法的探究。

圖3為兩幅實驗區DEM及相應山脊線的提取結果，可見尺度與地表復雜度的不同導致了兩幅DEM提取的脊線在整體形態與豐富程度上存在較大的差異。

圖3 選取DEM及其山脊線（黑色實線）Fig.3 DEM and extracted ridgelines

2.2 脊線的層次劃分結果

實驗主要從兩方面對新的脊線分級方法的有效性進行驗證：1）不同分級策略下脊線的層次結構對比；2）不同遍歷方式下分級效率對比。本文選取的分級策略分別為長度優先策略、180°角度逼近策略及深度優先策略，選取的遍歷方法分別為主干抽離法與節點標注法。兩幅實驗樣區在三種策略下得到的分級結果如圖4（見封2）所示，其中圖4a－圖4c為實驗區1不同方法下得到的脊線層次劃分結果，圖4d－圖4f為實驗區2不同方法下得到的脊線分層結果。可以發現：1）利用長度優先法與角度逼近法劃分脊線等級，得到的層次關系過多，分級結果十分破碎，難以基于結果識別脊線的主干與支干：實驗區1在兩種方法下得到的脊線等級總數分別為54與44，實驗區2在兩種方法下得到的脊線等級總數分別為22與15。這兩種層次劃分方法雖能夠在一定程度上完成脊線的分級工作，但破碎的層次關系難以為脊線的主、支干的判讀提供實質性的指導；2）無論對于大尺度還是小尺度地形，新方法均能夠獲得較為理想的層次劃分結果：大尺度地形上，深度優先法將脊線劃分為5個等級，而在小尺度地形中，該方法則為脊線確定了4個等級，較少的等級數目能夠更加清晰直觀地表達脊線的層次關系。從圖4c、圖4d可以發現，新方法搜索出的脊線主干具有最廣的覆蓋范圍，層次越低，其跨越的區域范圍也越小。這一實驗結果表明，新方法所劃分的層次結構不僅具有鮮明的地理學意義，且在表達效果上也優于傳統方法。

2.3 層次劃分效率分析

為進一步研究新方法的層次劃分效率，對實驗樣區的脊線進行抽稀處理（實驗區1的脊線結構更為豐富，因而選用該樣區脊線進行效率分析）。抽稀完成后，得到復雜程度各不相同的6組脊線，利用主干抽離法與傳統的節點標注法進行脊線等級劃分，最終，6組脊線的線段總數以及不同方法下所需的分級時間數據如表2所示。

為進一步研究脊線分級效率隨脊線豐富程度的變化情況，繪制兩種方法下分級時間隨脊線豐富程度的變化曲線，并進行回歸擬合（圖5）。分析發現：1）兩種方法下，脊線分級時間隨脊線豐富程度的變化規律相似，當脊線的線段總數較少時，分級時間較小，隨著豐富程度的增強，脊線的分級時間迅速增加，這一變化趨勢可用冪函數進行擬合。2）當脊線的豐富程度較弱時，兩種方法的效率差異較小，隨著脊線豐富程度的增強，兩種方法的差異性逐漸增大，最終，當線段總數達到2 500左右時，兩種方法分級消耗時間相差265 ms。當地形變化程度較為劇烈時，脊線的豐富程度通常較高，此時，主干抽離方法能夠更好地保證脊線的分級效率。

2.4 尺度推演中的不確定性對脊線層次劃分的干擾性研究

不同尺度下的脊線層次存在某種程度的相似性與統一性，層次劃分方法應當對地形簡化過程中的不確定性具有較好的抗干擾能力。下面以實驗樣區1為基礎數據，利用地形簡化方法獲得不同尺度下的地形，并在此基礎上研究多尺度下脊線間的層次差異（圖6，見封2）。1）建立研究區域的多尺度表面：選用最為常用的Z-tolerance算法提取地形特征點［23］，并構建不同尺度下的地形表面，如圖6a－圖6c所示；2）提取多尺度表面的山脊線；3）利用層次劃分法確定不同尺度下脊線的層次結構，如圖6d－圖6f所示。實驗結果表明：1）隨著升尺度過程的進行，地形的細部信息逐漸丟失，與之相對的是，地形脊線的豐富程度逐漸下降；2）隨著尺度的上推，脊線豐富程度隨之降低，但不同尺度下的脊線主干并未發生明顯變化。如圖6d中，1級主干擁有2－5級支干，圖6e中1級主干擁有2－4級支干，圖6f中1級主干擁有2－3級支干。可以發現，隨著尺度的推演，脊線層數逐漸減少，但劃分得到的主干在整體形態與區域布局上呈現出較強的相似性與統一性。這表明：尺度效應引發的不確定性并未對新方法產生過多的擾動。

3 結論

為準確、高效地獲得脊線的層次結構，本文提出一種新的脊線分級方法。首先基于分水嶺邊界準確提取地形山脊線；利用隊列建立其多叉樹模型來表達脊線的拓撲結構；利用深度優先算法確定脊線的主干搜索起點，并基于主干抽離模式獲得多層次下的脊線主干，從而完成脊線的層次劃分。最后，分別從層次劃分結果、分級效率以及層次劃分對不確定性的抗干擾能力三方面，對新方法的有效性進行驗證。結果表明：1）與傳統的長度優先法和角度逼近法相比，深度優先方法得到的脊線等級更加簡要，表達的脊線層次結構更加清晰；2）當脊線的線性結構較為簡單時，其分級效率也較高，隨著脊線豐富程度的增加，脊線的分級時間迅速增加，冪函數能夠很好地擬合這一變化趨勢，同時，與傳統的遍歷策略相比，本研究采用的主干抽離方法能更好地提升脊線的分級效率；3）尺度上推將影響脊線的豐富程度，但不同尺度上的脊線主干存在相似性與統一性，表明新方法具有較強的不確定性抗干擾能力。

在后續研究中，筆者將繼續關注谷線、脊線及水文線這類重要的地形特征線的層次結構研究，并嘗試實現一種統一的層次劃分機制，從而為地形層次結構研究領域提供一致性更強的科學研究工具。

［1］ ZHANG X，DRAKE N A，WAINWRIGHT J，et al.Comparison of slope estimates from low resolution DEMs：Scaling issues and a fractal method for their solution［J］.Earth Surface Processes and Landforms，1999，24（9）：763－779.

［2］ LI Z L.Multi-scale digital terrain modelling and analysis［A］.ZHOU Q，LEES B，TANG G.Advances in Digital Terrain A-nalysis［C］.Berlin：Springer-Verlag，2008.59－83.

［3］ LI Z L，ZHU Q.Digital Elevation Model［M］.Wuhan：Wuhan University of Surveying and Mapping Press，2003.

［4］ 董有福，湯國安.利用地形信息強度進行DEM地形簡化研究［J］.武漢大學學報（信息科學版），2013，38（3）：353－357.

［5］ ZHOU Q，CHEN Y.Generalization of DEM for terrain analysis using a compound method［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2011，66（1）：38－45.

［6］ FEI L，HE J.A three-dimensional Douglas-Peucker algorithm and its application to automated generalization of DEMs［J］.International Journal of Geographical Information Science，2009，23（6）：703－718.

［7］ LI J Z，AI T H，WANG H.The DEM generalization based on the filling valley coverage［J］.Acta Geodaetica et Cartographica Sinica，2009，38（3）：272－275.

［8］ PFAFSTETTER O.Classification of hydrographic basins：Coding methodology［R］.Brazil：Departamento Nacional de Obras de Saneamento，1989.

［9］ GARBRECHT J.Determination of the execution sequence of channel flow for cascade routing in a drainage network［J］.Hydrosoft，1988，1（3）：129－138.

［10］ 劉先龍，楊勤科.流域拓撲關系建立方法研究［J］.水土保持研究，2010，17（3）：82－86.

［11］ STRAHLER A N.Hypsometric（area-altitude）analysis of erosional topography［J］.Bulletin of the Geological Society of America，1952，2（63）：1117－1142.

［12］ 陳于林.基于DEM的水系提取及水系網多級分解［D］.成都：西南交通大學，2006.

［13］ SHREVE R L.Infinite topologically random channel networks［J］.Journal of Geology，1967，75（2）：178－186.

［14］ VERDIN K L，VERDIN J P.A topological system for delineation and codification of the Earth′s river basins［J］.Journal of Hydrology，1999，218（1－2）：1－12.

［15］ 羅翔宇，賈仰文，王建華，等.基于DEM與實測河網的流域編碼方法［J］.水科學進展，2006，17（2）：259－264.

［16］ GARBRECHT J.Determination of the execution sequence of channel flow for cascade routing in a drainage network［J］.Hydrosoft，1988，1（3）：129－138.

［17］ 任立良，劉新仁.數字高程模型在流域水系拓撲結構計算中的應用［J］.水科學進展，1999，10（2）：129－134.

［18］ 陳玉芬，李書琴，何東健.流域拓撲結構分析與計算機實現［J］.干旱地區農業研究，2005，23（5）：183－186.

［19］ 劉先龍.基于DEM的流域水文網絡建立方法研究［D］.咸陽：西北農林科技大學，2011.

［20］ BRIGGS I.Water Flow Using Desity of Area［R］.1989.1－11.

［21］ 張園玉，李霖，金玉平，等.基于圖論的樹狀河系結構化繪制模型研究［J］.武漢大學學報（信息科學版），2004，29（6）：537－543.

［22］ 賀文慧，湯國安，楊昕，等.面向DEM地貌綜合的山脊線等級劃分研究——以黃土丘陵溝壑區為例［J］.地理與地理信息科學，2011，27（2）：30－33.

［23］ CHANG K T.Introduction to Geographic Information Systems［M］.Singapore：McGraw-Hill，2008.