一種線狀要素深度簡化方法

喬俊軍，胡馮偉

（武漢大學(xué)測繪學(xué)院，湖北武漢430079）

一種線狀要素深度簡化方法

喬俊軍，胡馮偉

（武漢大學(xué)測繪學(xué)院，湖北武漢430079）

提出了一種線狀要素深度簡化的方法，該方法將線狀要素簡化分解成若干子過程，每個(gè)子過程通過彎曲識(shí)別與分類，并利用具有一致性和自適應(yīng)的閾值組合實(shí)現(xiàn)了線狀要素的規(guī)模化處理。試驗(yàn)表明，該方法能適應(yīng)于不同制圖因子——線寬、類型、比例尺要素的簡化，相比于Douglas等簡化方法更接近于人工處理的結(jié)果。

線狀要素；深度簡化；彎曲分類；閾值組合；線寬

隨著由庫到圖的制圖技術(shù)越來越成熟，新版《國家普通地圖集》采用國家1∶100萬基礎(chǔ)地理信息數(shù)據(jù)庫作為制圖數(shù)據(jù)進(jìn)行縮編成圖。然而，從百萬比例尺縮編成幾百萬，甚至是千萬比例尺的地圖，不可避免地面臨著線要素綜合問題。其中，線要素簡化是線要素綜合的核心問題。

目前，國內(nèi)外已有很多關(guān)于線要素簡化方面的研究。其中較著名的有Douglas算法［1］，該方法通過判斷曲線節(jié)點(diǎn)與直線的距離是否小于給定的閾值，從而達(dá)到數(shù)據(jù)簡化的目的，如果小于，則剔除節(jié)點(diǎn)。為了彌補(bǔ)Douglas算法在簡化過程中損失的信息，Tong等利用最小二乘理論，提出了一種不確定性過程模型，避免了簡化后曲線長度、面積等信息的失真［2］。Li等受啟發(fā)于自然界中所觀察到的自然綜合過程原理，提出了一種自適應(yīng)線狀要素綜合算法，該方法利用最小可見目標(biāo)尺寸作為曲線細(xì)節(jié)信息刪除與否的閾值，以達(dá)到簡化的目的［3］。針對Li-Openshaw算法的不足，朱鯤鵬等利用局部極大值點(diǎn)［4］、黃志堅(jiān)等利用角點(diǎn)檢測器篩選出的關(guān)鍵點(diǎn)［5］，將曲線在特征點(diǎn)處分段，每段再用Li-Openshaw進(jìn)行簡化，從而更好地保持了曲線整體形狀。

近年來，學(xué)者們探尋出了一條利用彎曲識(shí)別來達(dá)到線要素簡化的新思路。艾廷華利用約束的Delaunay三角網(wǎng)模型提出了一種曲線彎曲特征的深度層次結(jié)構(gòu)，實(shí)現(xiàn)了大彎曲套小彎曲層次結(jié)構(gòu)的表達(dá)［6］。毋河海通過多次應(yīng)用矢量叉積乘積，結(jié)合曲線光滑原理，以尋找曲線的最或然拐點(diǎn)［7］。羅廣祥利用坐標(biāo)非單調(diào)性變化產(chǎn)生線狀地圖要素彎曲的認(rèn)知模型，并通過順序比較坐標(biāo)大小來識(shí)別地圖彎曲［8］。郭慶勝從視知覺的角度，綜合利用曲線的極值點(diǎn)、拐點(diǎn)、迂回曲線分界點(diǎn)、方向擾動(dòng)奇異點(diǎn)來識(shí)別彎曲［9］。操震洲以曲線軸線作為彎曲劃分基準(zhǔn)，通過遞歸方式層次化提取不同方向、不同區(qū)間上的彎曲［10］。

不置可否，目前所見文獻(xiàn)對線要素簡化有一定的研究意義，但現(xiàn)有處理方法所獲得的簡化結(jié)果較難令人滿意，以至于在制圖過程中，人們往往更愿意采用手工為主的方式對線要素進(jìn)行簡化，原因有以下幾點(diǎn):

1）就制圖而言，線要素簡化不僅要減少節(jié)點(diǎn)，保持彎曲特征，還要考慮地圖出版印刷等問題。

2）針對不同類型、比例尺的線要素，閾值較難保證統(tǒng)一，從而導(dǎo)致方法的適用性不高。

3）僅利用彎曲識(shí)別較難獲得滿意的結(jié)果，還需要對彎曲進(jìn)行分類，因?yàn)椴煌愋偷膹澢幚矸绞讲煌?/p>

綜上所述，如何提出一種能夠處理多類型線要素，且能與手工處理結(jié)果相接近的簡化方法，已成為《國家普通地圖集》迫切需要解決的問題［3］。為此，本文提出一種深度簡化方法，該方法將線要素簡化分解成若干子過程，各個(gè)子過程通過彎曲識(shí)別與分類，并根據(jù)自適應(yīng)或符合視覺認(rèn)知的閾值進(jìn)行組合，處理不同類型的彎曲。

一、彎曲分類與簡化閾值

1.彎曲分類

假設(shè)兩線段組成的彎曲為一級彎曲，三線段組成的彎曲為二級彎曲。

由于一級彎曲是最底層彎曲，具有普遍性，因此一級彎曲的可分類性不高，本文重點(diǎn)在于二級彎曲的分類。根據(jù)二級彎曲中是否存在拐點(diǎn)，可將其分為兩大類。其中拐點(diǎn)存在與否可利用式（1）來判斷［7］，即

結(jié)合下文中的彎曲夾角θ，又可將每個(gè)大類分成4小類，具體見表1。

表1　二級彎曲分類

令Q（ P1，P2，P3，P4）為彎曲識(shí)別函數(shù)，P為輸入的節(jié)點(diǎn)，其值域?yàn)镼1～Q8。由表1可知，任何節(jié)點(diǎn)數(shù)大于4的線要素都是由二級彎曲組合而成的。

2.簡化閾值

為了判斷二級彎曲在何種情況下需要處理，閾值是個(gè)不可避免的問題，其定義如下:

1）彎曲口長L［11］:一級彎曲中，首尾節(jié)點(diǎn)之間的距離，如圖1所示。

2）彎曲深度H［11］:一級彎曲中，中間節(jié)點(diǎn)到首尾節(jié)點(diǎn)所在直線的距離，如圖1所示。

3）彎曲夾角θ:一級彎曲中，兩線段的夾角，其中0〈θ〈180°，如圖1所示。

圖1　一級彎曲上的簡化閾值

4）拐線長度L′:二級彎曲中間線段的長度。

5）平均線段長度ˉL:曲線上所有線段的平均值。

6）平均彎曲夾角θ:曲線上彎曲夾角的平均值。

7）彎曲重疊度D:因線寬導(dǎo)致的曲線在轉(zhuǎn)角處產(chǎn)生重疊與相鄰線段的差值，如圖2所示，其中

式中，W為線寬。需要說明的是二級彎曲的拐線有兩個(gè)彎曲重疊度。

圖2　彎曲重疊度

二、線要素深度簡化

簡化目標(biāo):在保證彎曲特征的情況下，使原始線要素禁錮在結(jié)果線要素的線寬范圍內(nèi)，且盡可能使原始線要素處于結(jié)果線要素的中間，如圖3所示，黑色為原始線要素。灰色為簡化結(jié)果線要素。

圖3　簡化目標(biāo)

簡化思想:如果僅將線要素分成一級彎曲來處理，很難得到滿意的結(jié)果，因?yàn)橐患墢澢g的關(guān)聯(lián)性很強(qiáng)，處理一級彎曲時(shí)，會(huì)對其相鄰的一級彎曲造成破壞。雖然二級彎曲之間的關(guān)聯(lián)性較弱，但如果將彎曲對象僅局限于單個(gè)的二級彎曲，也較難獲得滿意的結(jié)果，因?yàn)樵诰€要素節(jié)點(diǎn)環(huán)境非常復(fù)雜的情況下，往往存在單個(gè)二級彎曲的處理是模糊的情況，即使人工都難以決策。而且在線要素簡化的過程中，線要素上各個(gè)一、二級彎曲的尺寸是逐漸變大的。

基于此，深度簡化方法應(yīng)運(yùn)而生。該方法將線要素的簡化過程剝離成多個(gè)子過程，每個(gè)子過程處理不同類型的彎曲，且每個(gè)子過程的閾值組合隨著彎曲類型的不同而不同。具體如下:

1.重點(diǎn)剔除

輸入節(jié)點(diǎn)P1、P2，計(jì)算點(diǎn)間距l(xiāng)12，若l12〈Δl，則刪除節(jié)點(diǎn)P1或P2，并進(jìn)行迭代，直到?jīng)]有新點(diǎn)刪除為止。

2.第1層簡化

考慮到當(dāng)比例尺相差較大時(shí)，如從百萬數(shù)據(jù)庫到千萬比例尺圖的縮編過程，線要素上的節(jié)點(diǎn)數(shù)量是非常巨大的，因此需要首先對一級彎曲進(jìn)行處理，為下層簡化減輕負(fù)擔(dān)。假設(shè)輸入節(jié)點(diǎn) （P1，P2，P3），計(jì)算彎曲深度、彎曲口長和彎曲夾角，利用如下閾值組合，判斷是否處理當(dāng)前彎曲

式中］表示“并”，下同。式（3）表明，當(dāng)彎曲深度小于Δh、彎曲口長小于dl，且彎曲夾角小于平均彎曲夾角時(shí)，一級彎曲近似于線段，故刪除節(jié)點(diǎn)P2。

迭代上述過程，直到?jīng)]有新點(diǎn)刪除為止。如圖4（a）所示。

3.第2層簡化

該層簡化主要對獨(dú)立的二級彎曲進(jìn)行處理。假設(shè)輸入節(jié)點(diǎn) （P1，P2，P3，P4），首先利用式（2）計(jì)算該二級彎曲首尾兩線段的彎曲重疊度D1、D3，以及拐線的彎曲重疊度D21、D22，然后根據(jù)二級彎曲的類型，進(jìn)行如下處理

式中｛表示“或”，下同。由式（4）可知，當(dāng)彎曲類型為Q2～Q8時(shí)，判斷D21、D22是否小于0.1 mm。若兩者都小0.1 mm，說明拐線很短，在視覺上會(huì)被相鄰線段淹沒掉。此時(shí)，若l12、l34均小于平均點(diǎn)間距ˉL，那么移動(dòng)節(jié)點(diǎn)P2，并刪除節(jié)點(diǎn)P3。

若彎曲類型為Q5～Q8時(shí)，判斷D1、D21是否小于0.1 mm。若相鄰兩線段的彎曲重疊度均小于0.1 mm，那么在視覺上兩線段近似重合。此時(shí)，需要?jiǎng)h除節(jié)點(diǎn)P2。同理，當(dāng)D22、D3均小于0.1 mm時(shí)，刪除節(jié)點(diǎn)P3。

由于線要素的節(jié)點(diǎn)環(huán)境對于計(jì)算機(jī)而言是未知的，在某些情況下，式（4）的判斷會(huì)無效，但是拐線在視覺上仍然會(huì)被淹沒掉，主要原因是L′〈W，因此在這種情況下，需根據(jù)式（5）來處理彎曲

式中，n為顯著系數(shù)。由式（5）可知，當(dāng)存在L′〈W的情況時(shí)，首先判斷l(xiāng)12與l34的關(guān)系，如果l12明顯比l34長，那么刪除節(jié)點(diǎn)P3，反之刪除節(jié)點(diǎn)P2。如果兩者長度對比不明顯，就移動(dòng)節(jié)點(diǎn)P2，并刪除節(jié)點(diǎn)P3。迭代上述過程，直到?jīng)]有新點(diǎn)刪除為止，如圖4（b）所示。

4.第3層簡化

實(shí)際上，第2層簡化能夠?qū)Υ蟛糠知?dú)立二級彎曲進(jìn)行處理，但在某些情況下，獨(dú)立二級彎曲的處理是模糊的，即使人工都難以判斷，因此需要對獨(dú)立二級彎曲進(jìn)行延伸，以作為輔助判斷來決定當(dāng)前二級彎曲處理方式。

假設(shè)輸入節(jié)點(diǎn) （P0，P1，P2，P3，P4，P5），（P1，P2，P3，P4）為當(dāng)前二級彎曲，P0、P5為延伸點(diǎn)，從而將獨(dú)立的二級彎曲延伸為3個(gè)相鄰的二級彎曲。

1）若當(dāng)前彎曲類型為Q1，彎曲的處理方式見式（6）

式（6）表明，為了控制彎曲的處理長度，保證曲線特征，首先比較l12、L′及第1個(gè)彎曲口長L1與平均點(diǎn)間距ˉL的大小，若都小于ˉL，繼續(xù)判斷Q（P0，P1，P2，P3）的彎曲類型，若為Q1，則直接移動(dòng)節(jié)點(diǎn)P2，同時(shí)根據(jù)l12與l34的關(guān)系，移動(dòng)節(jié)點(diǎn)P3；若當(dāng)前二級彎曲的前后相鄰的二級彎曲為Q2和Q5～Q8，則刪除節(jié)點(diǎn)P2。同理，比較L′、l34及第2個(gè)彎曲口長L2與ˉL的關(guān)系，進(jìn)行同樣過程的處理。最后，若拐線較短，且二級彎曲首尾線段較長，即比較l12、L′、l34與ˉL的大小，若符合式（6），則移動(dòng)節(jié)點(diǎn)P2，并刪除節(jié)點(diǎn)P3。

2）若當(dāng)前彎曲類型為Q2時(shí)，彎曲的處理方式見式（7），需要說明的，彎曲類型Q3與Q2處理方式一致。

根據(jù)式（7），首先判斷l(xiāng)12、L′、L1與ˉL的關(guān)系，若均小于ˉL，則判斷Q（ P0，P1，P2，P3）是否為Q1，若是，則移動(dòng)節(jié)點(diǎn)P1和P2。為處理節(jié)點(diǎn)P3，還需判斷l(xiāng)34與Lˉ的大小，若l34小于ˉL，可認(rèn)為l34很短，則根據(jù)兩節(jié)點(diǎn)坐標(biāo)平均值移動(dòng)節(jié)點(diǎn)；否則，認(rèn)為l34較長，直接根據(jù)坐標(biāo)平均值會(huì)影響簡化的效果，故利用l34與Lˉ的比值關(guān)系來移動(dòng)節(jié)點(diǎn)P3。若Q（ P0，P1，P2，P3）為Q3，則先判斷D1和D21是否小于0.1 mm，若是，則刪除節(jié)點(diǎn)P2；否則，為剔除無意義的突起彎曲，再判斷l(xiāng)01是否小于ˉL，若是，則刪除節(jié)點(diǎn)P2。

3）若當(dāng)前彎曲類型為Q4時(shí)，彎曲的處理方式見式（8）。

根據(jù)式（8），首先判斷L2是否小于Lˉ，若是，再判斷Q（ P0，P1，P2，P3）是否為Q4，若是，則刪除節(jié)點(diǎn)P2。若Q（ P0，P1，P2，P3）沒有拐點(diǎn)，且l34小于平均點(diǎn)間距，那么移動(dòng)節(jié)點(diǎn)P2，并刪除節(jié)點(diǎn)P3，當(dāng)L2〈Lˉ時(shí)，彎曲的處理方式與L1〈ˉL一致。

迭代上述過程，直到?jīng)]有新點(diǎn)刪除為止。如圖4（c）所示。

需要說明的是:

1）在線要素深度簡化的過程中，平均點(diǎn)間距Lˉ的作用是控制彎曲的長度，保證彎曲特征。

2）式（5）—式（8）中，部分節(jié)點(diǎn)有的根據(jù)坐標(biāo)均值來移動(dòng)，有的根據(jù)線段比值關(guān)系來移動(dòng)。主要是考慮到當(dāng)線段明顯較短時(shí)，可以直接用坐標(biāo)均值的方式移動(dòng)節(jié)點(diǎn)，而當(dāng)線段明顯較長時(shí)，如果用坐標(biāo)均值的方式移動(dòng)節(jié)點(diǎn)，會(huì)導(dǎo)致簡化后的線段偏離原始線段，這就背離了上文闡述的“簡化目標(biāo)”，因此需要根據(jù)線段的比值關(guān)系來移動(dòng)節(jié)點(diǎn)。有精度的。

2）對于式（3）中的Δh、dl的取值，根據(jù)圖上最小可視距離［11］為0.3～0.6 mm。試驗(yàn)中將dl取值為0.3 mm。同時(shí)，考慮到線寬是線要素一個(gè)非常重要的制圖因子，試驗(yàn)中將Δh取值為線寬的1/4。因此，當(dāng)一級彎曲滿足式（3）的閾值組合時(shí)，可用直線代替一級彎曲，達(dá)到簡化的目的。

3）對于式（5）中的顯著系數(shù)n，可取值為1.5，因?yàn)楫?dāng)線段A的長度大于線段B的1.5倍時(shí)，可視為線段A明顯長于線段B。

4）彎曲重疊度的賦值，主要考慮到線段在視覺上是否會(huì)被淹沒等情況。一般情況下取值為0.1，即當(dāng)兩線段間距小于0.1 mm時(shí)，可視為兩線段重合。

5）其他閾值在簡化過程中是自適應(yīng)的，與平均點(diǎn)間距、平均彎曲夾角有關(guān)。

2.簡化試驗(yàn)

試驗(yàn)數(shù)據(jù)來源于國家百萬數(shù)據(jù)庫。

1）同線寬不同比例尺下的深度簡化試驗(yàn)，見圖5、表2，線寬為0.2 mm，黑色細(xì)線為原始線要素。

圖4中，黑色為原始線要素，灰色為各子過程簡化后的線要素。

圖4　深度簡化過程

圖5　不同比例尺線要素的深度簡化

表2　簡化后的節(jié)點(diǎn)對比

三、試驗(yàn)結(jié)果與分析

1.閾值賦值

1）對于重點(diǎn)剔除過程中的Δl取值，試驗(yàn)中將其賦值為0.000 1 mm。需要說明的是，Δl取值不固定，只要認(rèn)為兩點(diǎn)的點(diǎn)間距小于Δl，就視為重點(diǎn)即可，但該值一定不能為0，因?yàn)橛?jì)算機(jī)的浮點(diǎn)計(jì)算是

2）同比例尺不同線寬的深度簡化試驗(yàn)，見圖6、表3，線要素的比例尺為1∶800萬。

圖6　不同寬度線要素的深度簡化

表3　簡化后的節(jié)點(diǎn)對比

3）不同類型要素的深度簡化試驗(yàn)，如圖7所示，包括島嶼、境界線、道路、海岸線。

圖7　不同型線要素的深度簡化

4）與其他簡化方法的對比試驗(yàn)，見圖8、表4，線寬為0.2 mm，比例尺為1∶1600萬。

圖8　不同簡化方法對比

表4　簡化后的節(jié)點(diǎn)對比

3.結(jié)果分析

1）根據(jù)圖5和表2，在線寬相同的條件下，隨著比例尺的增大，深度簡化能夠保留線要素更多的細(xì)節(jié)，相應(yīng)的，線要素的節(jié)點(diǎn)也會(huì)增加；反之，會(huì)剔除多余彎曲，使節(jié)點(diǎn)更少。這與客觀認(rèn)識(shí)是相符合的，因?yàn)閷ν灰囟裕壤咴酱螅秶驮酱螅幸饬x的信息就會(huì)越多，就越能看清要素的細(xì)節(jié)部分；反之，能看到的細(xì)節(jié)就越少。

2）根據(jù)圖6和表3，在比例尺相同的情況下，隨著線寬的減小，深度簡化能夠保留線要素更多的細(xì)節(jié)，相應(yīng)的，線要素節(jié)點(diǎn)就會(huì)增加；反之，會(huì)剔除無意義細(xì)節(jié)，使節(jié)點(diǎn)更少。這與客觀認(rèn)識(shí)是相符合的，因?yàn)椋€寬越小，彎曲之間的影響就越小，能夠顯示的細(xì)節(jié)就越多，反之，細(xì)節(jié)會(huì)被淹沒。

3）根據(jù)圖7，深度簡化能夠適應(yīng)于多種不同類型的線要素簡化。但各類型線要素的簡化結(jié)果并非是相同的。其中，道路簡化的效果最好，簡化后，幾乎不用人工再參與；相比較而言，海岸線與島嶼的簡化結(jié)果就沒有道路那么好，還需要人工檢查與再編輯；境界線次之。主要原因是自然要素的邊界無規(guī)律可循，節(jié)點(diǎn)環(huán)境非常復(fù)雜，而人文要素邊界規(guī)律性較強(qiáng)，節(jié)點(diǎn)環(huán)境相對較簡單。

4）根據(jù)圖8和表4，深度簡化的結(jié)果與人工的簡化結(jié)果最接近，優(yōu)于道格拉斯與ArcGIS彎曲簡化所獲得的結(jié)果。

四、結(jié)束語

本文提出了一種深度簡化方法，該方法將簡化過程剝離成數(shù)個(gè)子過程，每個(gè)子過程通過彎曲識(shí)別與分類，并利用不同的閾值組合來處理彎曲。試驗(yàn)證明，該方法充分考慮了線要素的制圖因子——線寬，并針對不同比例尺、不同類型的對象都有很好的簡化效果。同時(shí)，相比于其他簡化方法，該方法的簡化結(jié)果更接近于人工處理結(jié)果，基本實(shí)現(xiàn)了以計(jì)算機(jī)為主、人工為輔的目標(biāo)，提高了制圖效率。

為了進(jìn)一步減少人工參與，提高要素尤其是自然要素簡化的滿意度，本文后續(xù)將會(huì)嘗試對三級甚至更高級的彎曲進(jìn)行分類與處理。

［1］ DOUGLAS D H，PEUCKER T K.Algorithms for the

Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature［J］.Canadian Cartographer，1973，10（2）:112-122.

［2］ TONG X，XU G.A New Least Squares Method Based Line Generalization in GIS［J］.International Geoscience and Remote Sensing Symposium，2004（5）:2912-2915.

［3］ LI Z L.OPENSHAW S.Linear Feature’s Self-adapted Generalization Algorithm Based on Impersonality Generalized Natural Law［J］.Translation of Wuhan Technical University of Surveying and Mapping，1994（1）: 49-58.

［4］ 朱鯤鵬，武芳，王輝連，等.Li-Openshaw算法的改進(jìn)與評價(jià)［J］.測繪學(xué)報(bào)，2007，36（4）:450-455.

［5］ 黃志堅(jiān)，張金芳，徐帆江.關(guān)鍵點(diǎn)檢測的線要素綜合算法［J］.中國圖象圖形學(xué)報(bào)，2012，17（2）:241-248.

［6］ 艾廷華，郭仁忠，劉耀林.曲線彎曲深度層次結(jié)構(gòu)的二叉樹表達(dá)［J］.測繪學(xué)報(bào)，2001，30（4）:343-348.

［7］ 毋河海.數(shù)字曲線拐點(diǎn)的自動(dòng)確定［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2003，28（3）:330-335.

［8］ 羅廣祥，祝國瑞，毋河海，等，坐標(biāo)單調(diào)分析下地圖曲線彎曲識(shí)別模型的研究［J］，測繪通報(bào)，2005（10）: 21-24.

［9］ 郭慶勝，黃遠(yuǎn)林，章莉萍.曲線的彎曲識(shí)別方法研究［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2008，33（6）: 596-599.

［10］ 操震洲，李滿春，陳亮.曲線彎曲的多叉樹表達(dá)［J］.測繪學(xué)報(bào)，2013，42（4）:602-607.

［11］ 黃博華，武芳，崔仁健，等.保持彎曲特征的線要素化簡算法［J］.測繪科學(xué)技術(shù)學(xué)報(bào)，2014，31（5）:533-537.

A Method of Deep Simplification for Line Features

QIAO Junjun，HU Fengwei

10.13474/j.cnki.11-2246.2016.0222.

P28

B

0494-0911（2016）07-0048-07

2015-09-17；

2015-11-02

喬俊軍（1961—），男，高級工程師，主要從事地圖學(xué)與地理信息工程教學(xué)及研究工作。E-mail:623083313@qq.com

引文格式：喬俊軍，胡馮偉.一種線狀要素深度簡化方法［J］.測繪通報(bào)，2016（7）:48-54.