臨近特征點(diǎn)類型匹配的多邊形漸變表達(dá)模型

劉鵬程 ，揭 毅 ，楊文博

1.華中師范大學(xué) 城市與環(huán)境科學(xué)學(xué)院，武漢 430079

2.地理過程分析與模擬湖北省重點(diǎn)實(shí)驗室，武漢 430079

網(wǎng)絡(luò)地圖是GIS發(fā)展到網(wǎng)絡(luò)時代的產(chǎn)物，也是GIS適應(yīng)IT技術(shù)潮流發(fā)展和全球化的必然要求，同時也是進(jìn)行地理空間資源共享的主要手段。隨著網(wǎng)絡(luò)可視化技術(shù)在相關(guān)領(lǐng)域的快速發(fā)展，靜態(tài)的、單一尺度的地圖可視化方式已經(jīng)無法滿足人們的實(shí)際應(yīng)用與分析需要，人們更希望能夠?qū)崿F(xiàn)空間信息可視化表達(dá)的多視角、多視點(diǎn)和多層次[1-3]。然而在網(wǎng)絡(luò)環(huán)境下，地圖可視化環(huán)境的任意性、地圖綜合的復(fù)雜性造成了地圖綜合算法的耗時與地圖多尺度度實(shí)時響應(yīng)需求的矛盾，因而網(wǎng)絡(luò)地圖適應(yīng)性表達(dá)也一直是GIS發(fā)展的一個瓶頸[4]。

Morphing連續(xù)變形技術(shù)最初產(chǎn)生于對圖像的連續(xù)平滑過渡漸變處理，隨著地圖綜合技術(shù)的發(fā)展，也被逐漸應(yīng)用于地圖自動綜合領(lǐng)域。其主要原理是依據(jù)同一目標(biāo)要素的兩個不同尺度下的實(shí)體要素數(shù)據(jù)，實(shí)現(xiàn)從一個尺度數(shù)據(jù)到另一個尺度數(shù)據(jù)的漸變，實(shí)現(xiàn)中間任意尺度數(shù)據(jù)的獲取，目前主要應(yīng)用于道路、河網(wǎng)、等高線等線性要素的綜合研究領(lǐng)域[5]。

本文將Morphing連續(xù)變形技術(shù)擴(kuò)展應(yīng)用于多邊形要素的連續(xù)尺度表達(dá)，依據(jù)輸入的同一多邊形的兩個不同尺度數(shù)據(jù)內(nèi)插獲取中間任意尺度的多邊形數(shù)據(jù)。Morphing連續(xù)變形技術(shù)在多邊形要素連續(xù)尺度表達(dá)的實(shí)現(xiàn)主要需解決以下幾方面關(guān)鍵技術(shù)：（1）多邊形輪廓形狀特征點(diǎn)的探測。特征點(diǎn)是指那些能夠代表當(dāng)前要素形狀特征的點(diǎn)，是對兩個尺度數(shù)據(jù)進(jìn)行匹配的控制點(diǎn)。對于線型要素特征點(diǎn)的探測，Chetverikov提出通過探測曲線彎曲的方式，以高曲率點(diǎn)作為曲線特征點(diǎn)[6]；N?llenburg利用貝塞爾曲線來篩選原曲線上弧度較大處的頂點(diǎn)作為特征點(diǎn)[7]；Cecconi通過打斷最長邊的方法實(shí)現(xiàn)兩個尺度曲線節(jié)點(diǎn)數(shù)量相等且一一對應(yīng)，以打斷后的節(jié)點(diǎn)作為特征點(diǎn)[8]；鄧敏通過構(gòu)建曲線彎曲樹和彎曲森林，以各個彎曲的起始點(diǎn)作為曲線特征點(diǎn)[9]；彭東亮對線要素構(gòu)建BLG樹，以BLG樹節(jié)點(diǎn)作為特征點(diǎn)[10-11]。本文認(rèn)為兩個尺度多邊形雖然存在位置、形狀細(xì)節(jié)的差異，但在總體輪廓上仍然具有相當(dāng)?shù)南嗨菩?，因此采用?gòu)建凸殼剖分樹的方法，以凸殼上的點(diǎn)作為多邊形的特征點(diǎn)。（2）建立曲線特征點(diǎn)的匹配關(guān)系。在這一問題上，彭東亮利用緩沖區(qū)探測匹配河流[10-11]；Cecconi以位移路徑距離最小進(jìn)行特征點(diǎn)弧段匹配[7]；鄧敏從彎曲度量指標(biāo)中提取出彎曲面積比作為特征點(diǎn)的匹配指標(biāo)[9]?？傮w來說，這些方法沒有在多個層次結(jié)構(gòu)上實(shí)施特征點(diǎn)的匹配。本文利用凸殼特征樹建立特征點(diǎn)的層次結(jié)構(gòu)，利用特征點(diǎn)的鄰近關(guān)系和類型匹配特征點(diǎn)使其匹配更有效，從而當(dāng)尺度變化時多邊形變化更為連續(xù)流暢。

1 多邊形多層次特征點(diǎn)的建立及層次曲線的分段

特征點(diǎn)的探測是Morphing技術(shù)實(shí)現(xiàn)中一個重要的前提條件，多邊形上兩個連續(xù)的特征點(diǎn)之間的弧段是Morphing技術(shù)實(shí)施的基本圖形單元，Morphing技術(shù)是以各個單元的漸變組合而成的。多邊形的特征點(diǎn)是包含圖形信息較多的點(diǎn)，多邊形凸殼上的點(diǎn)是多邊形凸起和凹陷的過渡點(diǎn)，能夠反應(yīng)多邊形圖形在這些點(diǎn)變化。本文對多邊形邊界特征點(diǎn)的探測采用多邊形的凸殼多層次模型[12-14]。具體方法如下：

首先，對多邊形構(gòu)建凸殼層次結(jié)構(gòu)，本文采用文獻(xiàn)[13]提出的方法，構(gòu)建多邊形的凸殼多叉樹，如圖1（a）和1（b）所示。其次，在多邊形凸殼多叉樹上，將多邊形及其子樹上的多邊形的弧段分為兩類：I類弧段：它們是多邊形的連續(xù)兩點(diǎn)或者多點(diǎn)。圖2（a）以根節(jié)點(diǎn)多邊形C0為例，0-1、52-53、70-71為相鄰連續(xù)兩點(diǎn)構(gòu)建的弧段，25-26-27、32-33-34、40-41-42、60-61-62-63為連續(xù)多點(diǎn)構(gòu)成的弧段，分別構(gòu)成該多邊形邊界上的凸起類型弧段。II類弧段：凸殼上連續(xù)兩點(diǎn)，它們在多邊形上為不連續(xù)的點(diǎn)，多邊形上這兩點(diǎn)之間的弧段為II類弧段。如圖2（a）上的 1-20、20-25、27-32、34-40、42-52、53-60、63-70、70-0節(jié)點(diǎn)構(gòu)成的弧段，表現(xiàn)為多邊形邊界上的凹陷部分。這樣便可以將多邊形的邊界分為凸凹兩種弧段形狀的組合。

圖1 多邊形凸殼剖分樹及其結(jié)構(gòu)圖

圖2 多邊形分段和層次特征點(diǎn)圖

最終多邊形邊界被分解為多個層次的多個凹凸弧段構(gòu)成的樹狀結(jié)構(gòu)，同一層次相鄰弧段的連接點(diǎn)即為當(dāng)前弧段所屬層次的特征點(diǎn)。為了方便后續(xù)特征點(diǎn)的匹配需要，以順時針方向為前進(jìn)方向，根據(jù)特征點(diǎn)連接前后弧段的的類型，將特征點(diǎn)分為以下三個類型：u-u類：前后均為凹陷，圖2（a）中的1-20和20-25相鄰弧段的連接點(diǎn)20即為u-u類；u-n類：前為凹陷后為凸起，圖2（a）中的20-25和25-27相鄰弧段的連接點(diǎn)25即為u-n類；n-u類：前為凸起后為凹陷，圖2（a）中的25-27和27-32相鄰弧段的連接點(diǎn)27即為n-u類。為了便于分析，將特征點(diǎn)分為三個層次分，即根節(jié)點(diǎn)多邊形的所有弧段連接節(jié)點(diǎn)構(gòu)成的第一層次特征點(diǎn)、第二級凸殼樹的凸殼點(diǎn)構(gòu)成第二層次特征點(diǎn)和其他層次的所有凸殼點(diǎn)組成第三層次特征點(diǎn)，最終結(jié)果如圖2（b）所示，黑色方塊、灰色圓和黑色圓分別對應(yīng)第一、二、三層次特征點(diǎn)。

整個多邊形邊界的各個弧段為一種層次關(guān)系，采用多叉樹的數(shù)據(jù)結(jié)構(gòu)來記錄各個層次的分段狀況：

2 基于位置臨近的特征點(diǎn)類型匹配

2.1 首級特征點(diǎn)的匹配

設(shè)f和g分別為同一要素的大比例尺和小比例尺兩個尺度下的面實(shí)體要素的邊界線，f的首級特征點(diǎn)集合為{P(Xi,Yi)|2＜i≤m}，m為f的首級特征點(diǎn)數(shù)量；g的首級特征點(diǎn)結(jié)合為{P(Xj,Yj)|2＜j≤n}，n為g的首級特征點(diǎn)數(shù)量。由于f和g均為面實(shí)體要素的邊界，邊界線為閉合的曲線，因此有f和g的特征點(diǎn)數(shù)量m＞2且n＞2；同時由于大比例尺要素具有更加詳細(xì)而復(fù)雜的輪廓信息，因此f的首級特征點(diǎn)數(shù)會多于g的首級特征點(diǎn)數(shù)，即m＞n＞2，因此特征點(diǎn)的匹配方向為由大比例尺圖形特征點(diǎn)集合向小比例尺特征點(diǎn)集合方向進(jìn)行映射匹配探測。

對于f上任意一點(diǎn)Pf(Xi,Yi)，以該點(diǎn)為起點(diǎn)，在g的特征點(diǎn)集合{P(Xj,Yj)|2＜j≤n}中查詢與Pf(Xi,Yi)線性距離最為臨近的點(diǎn)Pg(Xj,Yj)，建立最初的首級特征點(diǎn)匹配關(guān)系集合，如圖3（a）所示；由于大比例尺多邊形上的特征點(diǎn)多于小比例尺多邊形的特征點(diǎn)，因此可能會出現(xiàn)多個Pf(Xi,Yi)對應(yīng)一個Pg(Xj,Yj)的情況，如圖3（a）中的25-14和27-14；因此需要對初次匹配后的特征點(diǎn)關(guān)系進(jìn)行精細(xì)化的匹配處理，本文采用特征點(diǎn)類型匹配方法，即對應(yīng)匹配的特征點(diǎn)的前后曲線凹凸類型必須保持一致。如圖4（a）所示大比例尺曲線上的特征點(diǎn)25類型為u-n，27為n-u；小比例尺曲線上的特征點(diǎn)14的特征點(diǎn)類型為n-u，因此刪除不匹配的特征點(diǎn)配對25-14，如圖4（b）所示，最終f與g的首級特征點(diǎn)的匹配結(jié)果如圖3（b）所示，灰色邊框為大比例尺要素，特征點(diǎn)為灰色，點(diǎn)號以圓圈加數(shù)字表示；黑色邊框為小比例尺要素，特征點(diǎn)為灰色，點(diǎn)號以方框加數(shù)字表示。

圖3 首級特征點(diǎn)匹配

2.2 次級特征點(diǎn)的匹配

在完成首級特征點(diǎn)的匹配后，基本完成了對兩個尺度多邊形形狀的各個基本分弧段的匹配，兩個多邊形的邊界弧段被分劃為數(shù)量相等、一一對應(yīng)的弧段組合。在此基礎(chǔ)上，進(jìn)行下一等級的特征點(diǎn)匹配，同樣以大比例尺特征點(diǎn)為起點(diǎn)，向小比例尺方向?qū)?yīng)特征點(diǎn)弧段搜索最臨近特征點(diǎn)；首先處理多個特征點(diǎn)對應(yīng)一個特征點(diǎn)的情況，假如大比例尺要素f上有多個點(diǎn)同時對應(yīng)小比例尺要素g上的一個點(diǎn)，D(Pf,Pg)表示f上的點(diǎn)到g上的點(diǎn)的距離，AvgD表示所有距離的平均值，如果f上當(dāng)前點(diǎn)的D(Pf,Pg)>AvgD，則刪除該匹配，如圖5（b）所示；然后刪除特征點(diǎn)類型（特征點(diǎn)前后弧段凹凸類型）不匹配的組合，最后得到該層次的特征點(diǎn)匹配組合結(jié)果；如果最后結(jié)果中還有多個特征點(diǎn)對應(yīng)一個特征點(diǎn)的情況，我們將匹配線長度最小的匹配組合予以保留，使得特征點(diǎn)的匹配始終保持一一對應(yīng)的組合，如圖5（c）所示，以此類推，直到三個層次特征點(diǎn)全部匹配完成。如圖5（d）所示，紅色連接線表示第一層次特征點(diǎn)匹配連接，藍(lán)色色連接線表示第二級特征點(diǎn)的匹配連接，綠色連接線表示三級特征點(diǎn)的匹配，多邊形邊界上相鄰匹配特征點(diǎn)所構(gòu)成的弧段即為多邊形的匹配弧段，最后的兩個尺度下的匹配弧段數(shù)量相等且一一對應(yīng)。

圖4 基于特征點(diǎn)類型的精細(xì)匹配

圖5 次級特征點(diǎn)的匹配過程

特征點(diǎn)匹配是Morphing技術(shù)成功實(shí)施的關(guān)鍵，在在線式（on-line）地圖多尺度的表達(dá)中，計算效率是應(yīng)用得以實(shí)施的基礎(chǔ)。文獻(xiàn)[6]采用線性規(guī)劃的原理進(jìn)行形狀相似性匹配，計算復(fù)雜度很高，比較適合離線式（off-line）的地圖多尺度表達(dá)。本文采用基于位置臨近的特征點(diǎn)類型匹配方法，一方面顧及了兩個尺度下的多邊形局部形狀的相似性，另一方面充分考慮了不同尺度下同一要素的點(diǎn)位坐標(biāo)的相對一致性，而且凸殼計算復(fù)雜度不高，每個層次的計算復(fù)雜度為O(n2)（n為多邊形上點(diǎn)的個數(shù)），因而該算法是較為實(shí)用的算法。

為了驗證本文算法的合理性，本文在文獻(xiàn)[15]形狀相似性模型的基礎(chǔ)上提出了特征點(diǎn)匹配精度的驗證模型，如式（1）。

表1 兩種模型匹配精度比較

表1中，第2列為待匹配的兩多邊形的點(diǎn)數(shù)，第三列、第四列分別為按文獻(xiàn)[6]的方法得到的分段數(shù)及匹配精度，第三列、第四列分別為按本文的方法得到的分段數(shù)及匹配精度，從匹配精度而言，本文的方法略高于文獻(xiàn)[6]方法，這說明兩模型都是可行的。

3 中間尺度多邊形的獲取

3.1 內(nèi)插原理

式（2）中t為一個與比例尺相關(guān)的參數(shù)，h(t,μ)為由f(μ)和g(μ)內(nèi)插得到的中間尺度下的點(diǎn)。如果已知小比例尺為1∶S1和已知大比例尺為1∶S2，中間比例尺為1∶S3的t值可用式（3）計算得到：

t=0、t=1分別對應(yīng)小比例尺和大比例尺。

3.2 中間尺度多邊形的獲取操作

對于兩個匹配好的不同尺度同名多邊形，同樣以大比例尺多邊形的弧段向其匹配的小比例尺弧段為方向，將大比例尺多邊形邊界上位于該弧段的所有節(jié)點(diǎn)（包括弧段的起點(diǎn)和終點(diǎn)），映射到匹配好的小比例尺弧段上。映射方法為：計算大比例尺弧段各個節(jié)點(diǎn)沿多邊形邊界到其所處匹配弧段起點(diǎn)的距離與總弧段長度的比值，在小比例尺弧段上搜索到弧段起點(diǎn)的距離與弧段長度比值等于大比例尺弧段距離的點(diǎn)，這些新得到的點(diǎn)即為映射點(diǎn)；將大比例尺多邊形的邊界節(jié)點(diǎn)為起點(diǎn)與其映射點(diǎn)為終點(diǎn)連線構(gòu)成用于進(jìn)行數(shù)據(jù)內(nèi)插的內(nèi)插線，圖6中，黑色閉合曲線為小比例尺多邊形，灰色閉合曲線為大比例尺多邊形，連接兩個尺度多邊形的紅色線即為映射線，箭頭指示映射方向；根據(jù)式（3）和數(shù)據(jù)兩端比例尺以及所需的比例尺計算獲得當(dāng)前t值，將內(nèi)插線的起點(diǎn)、終點(diǎn)和t值帶入式（2）計算內(nèi)插點(diǎn)，將內(nèi)插得到的內(nèi)插點(diǎn)集合按順序連接并閉合構(gòu)成所需比例尺的多邊形數(shù)據(jù)，如圖6中的淺黃色區(qū)域構(gòu)成的多邊形即為內(nèi)插后得到的多邊形。

圖6 中間尺度數(shù)據(jù)的獲取過程

4 實(shí)驗和討論

為了討論本文模型的有效性，將本文的模型（以下簡稱A模型）和文獻(xiàn)[10]提供的基于BLG二叉樹的匹配模型（以下簡稱B模型）進(jìn)行了比較：A模型中，特征點(diǎn)的匹配均為“一對一”，不存在“一對多”的情況，在圖7（a）中，大尺度的特征點(diǎn)11與小尺度下的特征點(diǎn)19匹配，顯然不合理，在地圖要素的多尺度表達(dá)中，小尺度下的特征點(diǎn)19、21綜合為大尺度下的特征點(diǎn)11，在這種情況下“一對一”的匹配是錯誤的。圖7（b）是由A模型獲得的匹配，小尺度下的特征點(diǎn)19、21與大尺度下的特征點(diǎn)11匹配，匹配情況正好與地圖綜合的點(diǎn)要素的刪除相符。圖7（a）中這樣的情形還有多處，如大尺度的特征點(diǎn)2、4、6、13處都存在匹配錯誤。另外從得到的中間尺度的多邊形的效果看，模型A的漸變效果更合理。

圖7 兩種特征點(diǎn)匹配方法的比較

圖8 基于Morphing變形技術(shù)的多邊形內(nèi)插實(shí)驗結(jié)果

本文通過ArcGIS Server API for Flex對基于凸殼剖分樹的層次特征點(diǎn)提取、匹配，以及映射線的構(gòu)建和中間尺度數(shù)據(jù)的獲取全過程進(jìn)行了編程實(shí)現(xiàn)。并選取了四個不同關(guān)鍵尺度下的同名多邊形數(shù)據(jù)進(jìn)行試驗分析；當(dāng)對地圖進(jìn)行縮放操作時，根據(jù)當(dāng)前比例尺與最鄰近的前后兩個關(guān)鍵比例尺計算獲取t值，在兩個相鄰關(guān)鍵尺度間內(nèi)插獲得當(dāng)前地圖數(shù)據(jù)。如圖8（a1）-（f1）和（a2）-（f2）為數(shù)據(jù)庫中存儲的四個相鄰關(guān)鍵尺度數(shù)據(jù)，根據(jù)式（1）內(nèi)插分別獲取相鄰關(guān)鍵尺度的中間尺度多邊形數(shù)據(jù)，在兩個相鄰尺度中，分別取值t=0.2、t=0.4、t=0.6和t=0.8，可以看到隨著t值的遞增變化，多邊形的形狀實(shí)現(xiàn)了由一個關(guān)鍵尺度到其相鄰關(guān)鍵尺度的平滑過渡。傳統(tǒng)的地圖綜合過程完全由大比例尺一端控制，采取一定的綜合算法以增量的方式派生出其他相鄰比例尺，完成對小比例尺數(shù)據(jù)的輸出和顯示，隨著尺度距離的增大，綜合結(jié)果的形態(tài)難以控制；本文提出一種基于Morphing技術(shù)的多邊形連續(xù)尺度表達(dá)方法，利用兩個相鄰關(guān)鍵尺度的地理要素數(shù)據(jù)集合，內(nèi)插得到中間尺度數(shù)據(jù)的方法，實(shí)驗表明從兩端實(shí)現(xiàn)對綜合結(jié)果的控制，能夠很好的保持?jǐn)?shù)據(jù)的幾何以及拓?fù)涮匦?。本文的下一步研究工作將主要集中于進(jìn)一步提高M(jìn)orphing在多邊形中的內(nèi)插精度和算法效率。

[1]李精忠.尺度空間地圖多重表達(dá)的面向?qū)ο髷?shù)據(jù)模型研究[D].武漢：武漢大學(xué)，2009.

[2]張強(qiáng)，武芳，錢海忠，等.基于關(guān)鍵比例尺的空間數(shù)據(jù)多尺度表達(dá)[J].測繪科學(xué)技術(shù)學(xué)報，2011，28（5）：383-386.

[3]江南，白小雙，曹亞妮.基礎(chǔ)電子地圖多尺度顯示模型的建立與應(yīng)用[J].武漢大學(xué)學(xué)報：信息科學(xué)版，2010，35（7）：768-772.

[4]王艷慧，李娟，宮輝力.地理要素多尺度表達(dá)的基本問題[J].中國科學(xué)：E輯，技術(shù)科學(xué)，2006，36（增刊）：38-44.

[5]劉鵬程，龔沖亞，陶建斌，等.基于圖形漸變技術(shù)的等高線連續(xù)尺度表達(dá)模型[J].地理科學(xué)，2014，34（3）：332-337.

[6]Chetverikov D.A simple and efficient algorithm for detection of high curvature points in planar curves[C]//Computer Analysis of Images and Patterns.Berlin Heidelberg：Springer，2003：746-753.

[7]N?llenburg M，Merrick D，Wolff A，et al.Morphing polylines：A step towards continuous generalization[J].Computers，Environment and Urban Systems，2008，32（4）：248-260.

[8]Cecconi A.Integration of cartographic generalization and multi-scale databases for enhanced web mapping[D].University of Zurich，2003.

[9]鄧敏，彭東亮，徐震，等.一種基于彎曲結(jié)構(gòu)的線狀要素Morphing方法[J].中南大學(xué)學(xué)報：自然科學(xué)版，2012，43（7）：2674-2682.

[10]彭東亮，鄧敏，徐楓.顧及BLG樹結(jié)構(gòu)特征的線狀要素Morphing變換方法[J].武漢大學(xué)學(xué)報：信息科學(xué)版，2012，37（9）：1120-1124.

[11]彭東亮，鄧敏，趙彬彬，等.河網(wǎng)多尺度Morphing的變換方法研究[J].遙感學(xué)報，2012，16（5）：953-968.

[12]Ai T，bZ，LiuY.Progressive transmission of vector data based on changesaccumulation model[C]//Proceedings of the 11th International Symposium on Spatial Data Handling.Leicester，UK.Berlin：Springer-Verlag，2004：85-96.

[13]艾廷華，李志林，劉耀林，等.面向流媒體傳輸?shù)目臻g數(shù)據(jù)變化累積模型[J].測繪學(xué)報，2009，38（6）：514-519.

[14]艾廷華，成建國.對空間數(shù)據(jù)多尺度表達(dá)有關(guān)問題的思考[J].武漢大學(xué)學(xué)報：信息科學(xué)版，2005，30（5）：377-382.

[15]Arkin E M，Chew L P，Huttenlocher D P，et al.An efficiently computable metric for comparing polygonal shapes[J].IEEE Transactionson Pattern Analysisand Machine Intelligence，1991，13（3）：209-216.