樹狀結(jié)構(gòu)引導(dǎo)下的脊線層次劃分方法研究

高 翔，徐 柱＊

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

0 引言

不同尺度下的DEM表達(dá)不同尺度的地形信息，為獲得粗尺度的地形信息，需對(duì)精細(xì)尺度的DEM進(jìn)行綜合［1－4］，基于結(jié)構(gòu)線的方法能夠保證粗尺度下的DEM充分保留原始地形的骨架結(jié)構(gòu)，因此常采用該方法實(shí)現(xiàn)尺度轉(zhuǎn)換［5，6］。首先需獲得具有層次的山谷線與山脊線［7］，即需對(duì)谷線與脊線實(shí)施分級(jí)。對(duì)于山谷線，其層次劃分方法已較為成熟［8－10］。對(duì)于山脊線，主要有基于分形的方法與基于圖論的方法?；诜中蔚姆椒ǎ?，11－17］優(yōu)點(diǎn)在于與地理學(xué)中的分形理論相契合，缺點(diǎn)在于難以采用簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)表達(dá)地形特征線?；趫D論的方法能較好地克服這一缺陷，將特征線表達(dá)為圖中的節(jié)點(diǎn)，將線段間的拓?fù)渎?lián)通關(guān)系表達(dá)為節(jié)點(diǎn)的連接邊，以此將復(fù)雜的地形特征結(jié)構(gòu)轉(zhuǎn)換為計(jì)算機(jī)易于實(shí)現(xiàn)的圖結(jié)構(gòu)?，F(xiàn)階段，眾多學(xué)者已采用這一方法實(shí)現(xiàn)了水網(wǎng)結(jié)構(gòu)的層次劃分［18，19］，鑒于脊線與水網(wǎng)在地形中呈現(xiàn)出某種程度的結(jié)構(gòu)相似性，因而，同樣可以借用圖論方案研究脊線中的層次結(jié)構(gòu)。

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

基于這一地理學(xué)意義，本文提出一種新的山脊線層次劃分方案。首先從脊線自身的拓?fù)浣Y(jié)構(gòu)出發(fā)，將脊線表達(dá)為具有多個(gè)根節(jié)點(diǎn)的二叉樹，用樹的深度對(duì)脊線的區(qū)域跨度進(jìn)行丈量，從而將脊線的層次劃分問題轉(zhuǎn)換為樹的主支干判別問題，并從脊線拓?fù)浣Y(jié)構(gòu)的表達(dá)與樹的主干搜索兩個(gè)角度對(duì)層次劃分過程進(jìn)行論述。實(shí)驗(yàn)部分分別從脊線層次劃分結(jié)果、分級(jí)算法效率及不確定性擾動(dòng)效應(yīng)三方面對(duì)新方法的有效性進(jìn)行驗(yàn)證。

1 層次劃分研究

1.1 脊線樹的構(gòu)建

脊線中的一級(jí)主干與一個(gè)或多個(gè)二級(jí)主干相連，二級(jí)主干與一個(gè)或多個(gè)三級(jí)主干相連，多叉樹能夠很好地表達(dá)這一分形特征。樹中的節(jié)點(diǎn)表示地理實(shí)體中的脊線段，節(jié)點(diǎn)間的聯(lián)通關(guān)系用以表達(dá)脊線段的拓?fù)浣Y(jié)構(gòu)。

由于脊線中不存在地理意義上的出入口，且脊線本身不具有流向信息，基于這一無向的拓?fù)浣Y(jié)構(gòu)構(gòu)建多叉樹，首先需確定脊線的根節(jié)點(diǎn)位置?？紤]到脊線兩端的線段通常距離流域出口最近，為簡(jiǎn)單起見，選用脊線段集合中距離流域出口最近的線段作為根節(jié)點(diǎn)。然后，逐一計(jì)算與其相連的脊線段，并將其作為當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)，重復(fù)執(zhí)行該過程直到將所有脊線段納入至多叉樹中。研究發(fā)現(xiàn)，隊(duì)列能夠很好地模擬上述過程，具體的實(shí)現(xiàn)方法為：1）將當(dāng)前節(jié)點(diǎn)插入至隊(duì)列中，計(jì)算與其聯(lián)通的節(jié)點(diǎn)，并將這些節(jié)點(diǎn)標(biāo)記為當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)；2）將當(dāng)前節(jié)點(diǎn)從隊(duì)列中移除，同時(shí)將其子節(jié)點(diǎn)插入至隊(duì)列中；3）重復(fù)執(zhí)行第二步，直到完成子樹中所有節(jié)點(diǎn)的處理；4）搜索新的根節(jié)點(diǎn)，跳轉(zhuǎn)至第一步，進(jìn)行新一輪的廣度優(yōu)先遍歷，直到所有脊線段均處理完成。圖1進(jìn)一步描述了脊線樹的構(gòu)建過程，當(dāng)前子樹共有9條脊線段，首先從集合中選取距離流域出口最近的脊線段（1號(hào)線段）作為樹的根節(jié)點(diǎn)并加入至隊(duì)列中，接著，搜索與1號(hào)線段相連的2號(hào)與3號(hào)子線段，將其加入至隊(duì)列中，同時(shí)將1號(hào)線段從隊(duì)列中移除，這一過程將反復(fù)執(zhí)行，直到完成所有線段的遍歷。

1.2 脊線的分層與遍歷

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

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

2 實(shí)驗(yàn)分析

2.1 實(shí)驗(yàn)樣區(qū)的選擇

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

圖3為兩幅實(shí)驗(yàn)區(qū)DEM及相應(yīng)山脊線的提取結(jié)果，可見尺度與地表復(fù)雜度的不同導(dǎo)致了兩幅DEM提取的脊線在整體形態(tài)與豐富程度上存在較大的差異。

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

2.2 脊線的層次劃分結(jié)果

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

2.3 層次劃分效率分析

為進(jìn)一步研究新方法的層次劃分效率，對(duì)實(shí)驗(yàn)樣區(qū)的脊線進(jìn)行抽稀處理（實(shí)驗(yàn)區(qū)1的脊線結(jié)構(gòu)更為豐富，因而選用該樣區(qū)脊線進(jìn)行效率分析）。抽稀完成后，得到復(fù)雜程度各不相同的6組脊線，利用主干抽離法與傳統(tǒng)的節(jié)點(diǎn)標(biāo)注法進(jìn)行脊線等級(jí)劃分，最終，6組脊線的線段總數(shù)以及不同方法下所需的分級(jí)時(shí)間數(shù)據(jù)如表2所示。

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

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

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

3 結(jié)論

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

在后續(xù)研究中，筆者將繼續(xù)關(guān)注谷線、脊線及水文線這類重要的地形特征線的層次結(jié)構(gòu)研究，并嘗試實(shí)現(xiàn)一種統(tǒng)一的層次劃分機(jī)制，從而為地形層次結(jié)構(gòu)研究領(lǐng)域提供一致性更強(qiáng)的科學(xué)研究工具。

［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］ 董有福，湯國安.利用地形信息強(qiáng)度進(jìn)行DEM地形簡(jiǎn)化研究［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），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］ 劉先龍，楊勤科.流域拓?fù)潢P(guān)系建立方法研究［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的水系提取及水系網(wǎng)多級(jí)分解［D］.成都：西南交通大學(xué)，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與實(shí)測(cè)河網(wǎng)的流域編碼方法［J］.水科學(xué)進(jìn)展，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］ 任立良，劉新仁.數(shù)字高程模型在流域水系拓?fù)浣Y(jié)構(gòu)計(jì)算中的應(yīng)用［J］.水科學(xué)進(jìn)展，1999，10（2）：129－134.

［18］ 陳玉芬，李書琴，何東健.流域拓?fù)浣Y(jié)構(gòu)分析與計(jì)算機(jī)實(shí)現(xiàn)［J］.干旱地區(qū)農(nóng)業(yè)研究，2005，23（5）：183－186.

［19］ 劉先龍.基于DEM的流域水文網(wǎng)絡(luò)建立方法研究［D］.咸陽：西北農(nóng)林科技大學(xué)，2011.

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

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

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

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