賈鈺涵,馮建華,蔡昕楠,劉 斌

(1.長安大學(xué)地質(zhì)工程與測繪學(xué)院,陜西 西安 710054; 2.西安航天天繪數(shù)據(jù)技術(shù)有限公司,陜西 西安 710065)

地圖綜合一直以來都是地圖學(xué)領(lǐng)域的重點(diǎn)和難點(diǎn)之一。根據(jù)地圖要素的分類,綜合主要針對點(diǎn)狀要素的取舍、線狀要素的化簡以及面狀要素輪廓的化簡與合并3個方面[1]。線狀要素作為地圖的重要組成部分,對于線狀要素的化簡方法是研究的熱點(diǎn)[2-3]。

線狀要素化簡的基本思想是在維持其形狀的同時減少節(jié)點(diǎn)的數(shù)量[4]。針對線狀要素的化簡,前人提出了很多方法,如Douglas-Peucker(DP)算法[5]、Li-Openshaw算法[6]、彎曲組算法[7]等,各種算法的化簡效果各有差異,其中DP算法作為最經(jīng)典的算法,在地圖綜合中得到了廣泛應(yīng)用,不斷有學(xué)者對其進(jìn)行研究[8-10],并且其在除了地圖綜合外的其他領(lǐng)域也有應(yīng)用[11]。該算法實(shí)現(xiàn)簡單,化簡效率高,在對整個線狀地物進(jìn)行化簡的同時,可以很好地保留其形狀特征,并且不會產(chǎn)生多余的點(diǎn)[12]。

盡管如此,DP算法在進(jìn)行化簡時需要人為選取閾值。閾值的設(shè)置直接關(guān)系到化簡結(jié)果,若閾值設(shè)置過大,那么化簡結(jié)果會變得粗略,無法保持線狀地物的特征;若閾值設(shè)置過小,那么化簡結(jié)果會過于詳細(xì),化簡結(jié)果也不太理想。通常,在使用該算法時,制圖人員需要不斷調(diào)整閾值,并對化簡的中間結(jié)果進(jìn)行比較才能夠得到最為合適的化簡結(jié)果[13]。

線狀要素的化簡過程本質(zhì)上是一種相似變換,通過研究化簡前后線狀要素間的空間相似度和DP算法閾值的關(guān)系,便可以根據(jù)空間相似度來選取合適的閾值,避免不斷重復(fù)以選取最優(yōu)閾值的繁瑣過程,提高了化簡的效率,降低了化簡的主觀性。

1 Douglas-Peucker算法

Douglas-Peucker算法在1973年由D.Douglas和T.Peucker提出[5],算法的步驟如下:

(1) 首先將線的首尾端點(diǎn)AB連成一條直線,遍歷線上其他所有的點(diǎn),并算出這些點(diǎn)距離這條直線的距離,找到最大距離的點(diǎn)C,最大距離記為dmax。

(2) 比較該最大距離(dmax)與給定的化簡閾值Dmax之間的關(guān)系,若最大距離小于閾值(dmax

(3) 若最大距離大于等于閾值(dmax≥Dmax),那么保留最大距離(dmax)對應(yīng)的點(diǎn)C,并且以該點(diǎn)為界,把線分為AC和CB兩部分,并且對每部分繼續(xù)重復(fù)使用上述方法,直到線上的所有點(diǎn)到對應(yīng)直線的距離都小于給定的閾值。

2 空間相似度

空間相似性是人類認(rèn)知地圖中的重要概念,在手工制圖階段,地圖綜合質(zhì)量是質(zhì)檢人員通過經(jīng)驗(yàn)來比對原圖和綜合結(jié)果圖之間的相似程度來確定的[14]。

空間相似度是[0,1]區(qū)間內(nèi)的一個值,其基于空間相似關(guān)系計(jì)算得到,用于度量空間目標(biāo)之間的相似程度,如果用百分比表示,則是0～100%之間的一個值。該值越大,空間目標(biāo)間的空間相似度越高,當(dāng)值為1時代表完全相似[15]。

空間相似度不僅可以評判化簡前后空間目標(biāo)之間的一致性,也可以作為評價制圖質(zhì)量好壞的依據(jù)。

2.1 計(jì)算依據(jù)

吳立新等[16]認(rèn)為空間相似關(guān)系包括了兩方面的含義:空間目標(biāo)幾何形態(tài)上的相似以及空間目標(biāo)(群組)結(jié)構(gòu)上的相似。

形狀是空間感知以及傳遞信息的重要因素,也被認(rèn)為是描述線的最關(guān)鍵因素。通過對象的形狀來計(jì)算空間相似度,可以有效解決自動綜合的問題。對于單個線狀地物的研究,并不需要考慮線狀地物群之間結(jié)構(gòu)的相似。因此,用線的形狀來描述線的相似程度。

兩幅地圖之間的相似程度可以使用“相同程度”來描述評估?！跋嗤潭取笔褂脙煞貓D之間一致或不一致的面積來表示地圖間的相似程度[17]。線狀地物在圖上一般作為半依比例尺符號,由此,在不考慮線狀地物的寬度時,長度就成為了最重要的因素,因此在研究中使用線狀地物之間的公共長度來計(jì)算其化簡前后的空間相似度。將化簡前后的線狀地物相應(yīng)的端點(diǎn)疊加,就可以得出兩者之間的公共長度,基于公共長度也就可以計(jì)算出兩者之間的空間相似度。

2.2 計(jì)算公式

基于公共長度計(jì)算相似度最簡單的方法是:求得化簡前后的線狀地物之間的公共長度(兩條直線重合的長度),線狀地物間的相似度公共長度和化簡前的線狀地物的比值計(jì)算公式為

(1)

其中:a代表化簡前的線段;b代表化簡后的線段;l代表兩條線段的公共長度;L代表化簡前線段a的長度。相似度Sim由以上幾個參數(shù)計(jì)算得出。

利用式(1)計(jì)算相似度有著很明顯的缺陷:計(jì)算時并沒有考慮到化簡前后線狀地物之間的鄰近關(guān)系,只有完全重合的部分被認(rèn)為是相似部分(如圖1所示)。這種情況(實(shí)線為化簡前,虛線為化簡后)計(jì)算出來的兩條線之間的相似度就會是0,很明顯這是不符合人類的認(rèn)知規(guī)律的。

圖1 化簡前后的線狀地物Fig.1 Linear objects before and after simplification

2.3 計(jì)算公式改進(jìn)

在考慮化簡前后線狀地物之間的鄰近關(guān)系后,基于公式(1)對計(jì)算相似的方法進(jìn)行改進(jìn)。在地圖上,線狀地物是由一系列的坐標(biāo)點(diǎn)組成的,利用Douglas-Peucker算法進(jìn)行化簡時保留的是原始線狀地物的首尾端點(diǎn)以及各分線段的端點(diǎn)。因此,在計(jì)算相似度時,給化簡后的線狀地物的各分線段賦予一個權(quán)重,該權(quán)重基于各分線段與化簡前的線狀地物對應(yīng)的線段之間的距離,計(jì)算公式為

(2)

其中:n代表化簡后的線狀地物的線段數(shù)目;L代表化簡前線狀地物的長度;li代表化簡后的第i段線段的長度;ωi代表該線段基于距離計(jì)算出的權(quán)重,計(jì)算方法為

(3)

其中:di代表化簡前后線狀地物對應(yīng)線段之間的距離;li代表化簡后該線段的長度。

di的計(jì)算方法如圖2所示,其中:ABCD(虛線)為化簡前的線段;AD(實(shí)線)為化簡后的線段。計(jì)算B、C(除了重合的首尾端點(diǎn))與化簡后的線段AD之間的距離并求出平均數(shù)即為di。

圖2 化簡前后對應(yīng)的線段Fig.2 Corresponding line segment before and after simplificatio

3 空間相似度與DP算法閾值間的關(guān)系

研究兩者間關(guān)系的總體思路是首先通過DP算法,選取不同的閾值對線狀地物進(jìn)行化簡,然后通過公式計(jì)算化簡前后的線狀地物間的空間相似度,最后通過曲線擬合的方式得到閾值和空間相似度間的關(guān)系。

3.1 閾值的轉(zhuǎn)換

DP算法的閾值是一個絕對的值(長度),對于不同的線狀地物,選取相同的閾值進(jìn)行化簡后,得到的結(jié)果與原本的線狀地物間的空間相似度一般不同。因此,將DP算法化簡時選取的閾值轉(zhuǎn)換為一種相對的閾值。

根據(jù)DP算法的特點(diǎn),首先,將DP算法的化簡閾值設(shè)為0,由此計(jì)算出化簡時線狀地物每一段的最大距離dmax,將最大距離去掉0值之后,形成一個從小到大的序列;然后,將最大距離點(diǎn)繪制在坐標(biāo)軸上,依次連接成一條折線,并且計(jì)算該折線與坐標(biāo)軸圍成的面積Stotal(見圖3);最后,計(jì)算折線上起點(diǎn)到所設(shè)置閾值點(diǎn)與坐標(biāo)軸圍成的面積Spart(見圖4),那么該絕對閾值對應(yīng)的相對閾值為兩者面積之比(總面積為分母),即Spart/Stotal。

圖3 Stotal的計(jì)算Fig.3 The calculation of Stotal

圖4 Spart的計(jì)算Fig.4 The calculation of Spart

3.2 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)對象為一條線狀地物,原始形狀如圖5所示。

圖5 實(shí)驗(yàn)選取的線狀地物Fig.5 Linear objects selected in the experiment

將所選取的線狀地物計(jì)算出來的dmax中的0值去掉之后,分布情況見表1。

表1 最大距離在各個區(qū)間的數(shù)量

由表1可以看出,最大距離大部分處于0～1這個區(qū)間內(nèi),這也符合圖上線狀地物彎曲度不大,較為平緩的特點(diǎn)。因此,選取較多0～1的閾值進(jìn)行實(shí)驗(yàn),以此來觀察閾值和相似度之間的關(guān)系。

3.3 計(jì)算空間相似度

首先使用DP算法設(shè)置不同的閾值對該線狀地物進(jìn)行化簡,得到化簡后的結(jié)果,部分結(jié)果如圖6所示。

圖6 部分化簡結(jié)果Fig.6 Part of the simplication results

從化簡結(jié)果中可以看出,隨著閾值的增大,線狀地物的形狀化簡的程度也在增大,當(dāng)閾值大于3之后,線的形狀已經(jīng)變得十分簡單,這也符合最大距離的分布范圍。

通過相似度計(jì)算方法和閾值轉(zhuǎn)換方法,計(jì)算出不同閾值下化簡后的線狀地物和原本線狀地物之間的相似度,部分結(jié)果見表2。

3.4 曲線擬合

通過線性擬合得出兩者之間的關(guān)系。擬合優(yōu)度是指擬合結(jié)果對觀測值的擬合程度。度量擬合優(yōu)度的統(tǒng)計(jì)量是可決系數(shù)(亦稱確定系數(shù))R2,R2最大值為1。R2的值越接近1,說明回歸直線對觀測值的擬合程度越好;R2的值越小,說明回歸直線對觀測值的擬合程度越差。

根據(jù)表2中數(shù)據(jù),將相對閾值作為自變量,相似度作為因變量,得到的擬合結(jié)果如圖7所示。

圖7 擬合曲線Fig.7 Fitting results curve

表2 化簡閾值和空間相似度

構(gòu)造出的3種曲線的擬合優(yōu)度R2分別為0.883、0.823 8、0.956 9,可以看出多項(xiàng)式擬合的擬合程度是最好的。

因此,選取多項(xiàng)式擬合的曲線作為計(jì)算相似度的結(jié)果,計(jì)算公式為

(4)

其中:t代表相對閾值,可由絕對閾值計(jì)算得來。

通過公式(4)即可建立閾值與空間相似度之間的關(guān)系,通過空間相似度可以更快獲取到想要的化簡結(jié)果,避免了頻繁地選取閾值和比較。

4 結(jié)語

DP算法是進(jìn)行線化簡時的一種非常經(jīng)典的算法,但是在進(jìn)行化簡時需要進(jìn)行多次實(shí)驗(yàn)才能確定合適的閾值。通過對DP算法的閾值和化簡前后線之間的空間相似度之間的關(guān)系進(jìn)行了研究,將原本的絕對閾值轉(zhuǎn)換為相對閾值,選取線狀地物進(jìn)行實(shí)驗(yàn),建立起DP算法的化簡閾值和化簡前后線狀地物間空間相似度的關(guān)系?；诖?通過空間相似度即在利用DP算法進(jìn)行化簡時,避免了以往需要多次實(shí)驗(yàn)和比較才能選取到合適閾值的情況,提高了算法的效率。

但是,研究只針對一個線狀地物做了實(shí)驗(yàn)得出結(jié)果,可能只是對某一類線狀地物效果較好,若想得到適用于更多類型的線狀地物的結(jié)果,仍需選取更多的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。此外,在進(jìn)行空間相似度的計(jì)算時,只考慮了公共長度這個因素,并沒有考慮到空間相似度的其他影響因子,計(jì)算方法仍待改進(jìn)。若能在后續(xù)研究中解決以上問題,所得結(jié)果也可用于自動制圖綜合。