通過(guò)空間相似度設(shè)置閾值的Douglas-Peucker算法

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

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

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

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

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

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

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)與給定的化簡(jiǎn)閾值Dmax之間的關(guān)系,若最大距離小于閾值(dmax

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

2 空間相似度

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

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

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

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

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

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

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

2.2 計(jì)算公式

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

(1)

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

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

圖1 化簡(jiǎn)前后的線狀地物Fig.1 Linear objects before and after simplification

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

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

(2)

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

(3)

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

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

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

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

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

3.1 閾值的轉(zhuǎn)換

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

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

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

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

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

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

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

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

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

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

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

3.4 曲線擬合

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

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

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

表2 化簡(jiǎn)閾值和空間相似度

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

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

(4)

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

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

4 結(jié)語(yǔ)

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

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