一種基于彎曲結(jié)構(gòu)的線狀要素Morphing方法

鄧敏 ，彭東亮，徐震，劉慧敏

(1. 中南大學(xué) 地球科學(xué)與信息物理學(xué)院，湖南 長(zhǎng)沙，410083 2. 中南大學(xué) 有色金屬成礦預(yù)測(cè)教育部重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙，410083)

Morphing技術(shù)又稱為連續(xù)變形技術(shù)，起源于 20世紀(jì)90年代，最初用于圖像漸變，現(xiàn)已成為處理圖像視覺效果的一種強(qiáng)有力工具。該技術(shù)可實(shí)現(xiàn)從源圖像到目標(biāo)圖像的平滑漸變，是一種兼顧形狀和顏色的圖像內(nèi)插方法，在動(dòng)畫制作、圖像壓縮以及圖像重構(gòu)等領(lǐng)域具有廣泛應(yīng)用[1-4]。在地圖制圖領(lǐng)域，空間數(shù)據(jù)多尺度表達(dá)可以使用戶了解到目標(biāo)區(qū)域不同詳細(xì)程度的空間信息[5]，但是用戶瀏覽地圖時(shí)的隨意放大縮小給空間數(shù)據(jù)任意比例尺表達(dá)帶來巨大挑戰(zhàn)，尤其是任意比例尺地圖數(shù)據(jù)的存儲(chǔ)、傳輸更為困難。顯然，通過現(xiàn)有基本比例尺地圖數(shù)據(jù)按需生成任意比例尺地圖數(shù)據(jù)是學(xué)者們解決這個(gè)問題的主要途徑。然而，以地圖綜合為代表的傳統(tǒng)尺度變換模式只采用一個(gè)初始數(shù)據(jù)集，僅能做一端控制，其變換結(jié)果容易產(chǎn)生幾何、拓?fù)涞炔灰恢虑樾蝃2]。借鑒Morphing技術(shù)思想，采用2個(gè)不同尺度的初始數(shù)據(jù)集，對(duì)尺度變換進(jìn)行兩端控制，在一個(gè)數(shù)據(jù)集平滑漸變?yōu)榱硪粋€(gè)數(shù)據(jù)集的過程中，不同漸變程度實(shí)際對(duì)應(yīng)了不同的中間尺度地圖數(shù)據(jù)表達(dá)，這一尺度變換模式有效提高了所需比例尺地圖的精度。考慮到所需尺度數(shù)據(jù)由兩端尺度數(shù)據(jù)內(nèi)插生成，文獻(xiàn)[2]中稱之為形狀內(nèi)插尺度變換。目前，Morphing技術(shù)在地圖制圖領(lǐng)域主要用于道路、河流等線狀要素的形狀內(nèi)插，以生成所需尺度線狀要素形態(tài)[6-7]。相關(guān)研究主要集中在2個(gè)方面：一是對(duì)兩要素分別選取特征點(diǎn)并對(duì)其進(jìn)行匹配，建立對(duì)應(yīng)關(guān)系[6-8]；二是確定對(duì)應(yīng)點(diǎn)間的移位路徑[8-12]。對(duì)于第1個(gè)方面，Cecconi[6]考慮到小比例尺線狀要素頂點(diǎn)數(shù)相對(duì)較少，提出每次尋找并從中點(diǎn)打斷其最長(zhǎng)邊，從而使得2個(gè)比例尺線狀要素頂點(diǎn)數(shù)相等，進(jìn)而將每個(gè)頂點(diǎn)作為特征點(diǎn)按點(diǎn)號(hào)順序一一匹配。N?llenburg等[7]考慮到特征點(diǎn)數(shù)量對(duì)時(shí)間復(fù)雜度的影響，提出利用貝塞爾曲線篩選兩線狀要素弧度較大處的頂點(diǎn)作為特征點(diǎn)以減小數(shù)據(jù)量，然后以特征點(diǎn)、相鄰特征點(diǎn)間的線段為基本單位，以匹配后移位路徑最小進(jìn)行匹配。Albrecht等[8,13]將弧度較大處的頂點(diǎn)視作特征點(diǎn)，進(jìn)而基于位移最小的原則建立特征點(diǎn)間對(duì)應(yīng)關(guān)系。綜上分析，在選取特征點(diǎn)并建立對(duì)應(yīng)關(guān)系方面，現(xiàn)有方法大多是基于線狀要素的細(xì)部信息，忽視了線狀要素的整體結(jié)構(gòu)信息，從而導(dǎo)致建立特征點(diǎn)對(duì)應(yīng)關(guān)系時(shí)容易出現(xiàn)誤匹配，進(jìn)而影響Morphing的精度。為此，本文作者立足于線狀要素整體結(jié)構(gòu)信息，以線狀要素固有的彎曲結(jié)構(gòu)為切入點(diǎn)，分別對(duì)兩線狀要素的彎曲結(jié)構(gòu)進(jìn)行識(shí)別，并依此將兩線狀要素分割成多對(duì)對(duì)應(yīng)線段，從而達(dá)到增加匹配控制點(diǎn)的目的。在此基礎(chǔ)上進(jìn)行 Morphing，以期提高M(jìn)orphing的精度。

1 研究策略

對(duì)于同一線狀要素，不妨將其大比例尺表達(dá)記為α，小比例尺表達(dá)記為β，則本文所研究的Morphing問題轉(zhuǎn)換為對(duì)線狀要素α和β進(jìn)行形狀內(nèi)插。令f:[0 ,1]→α為一連續(xù)函數(shù)，且f(0)和f(1)分別為α的起點(diǎn)和終點(diǎn)，令 g :[0 ,1]→β為一連續(xù)函數(shù)，且g(0)和g(1)分別為β的起點(diǎn)和終點(diǎn)，對(duì)α和β建立對(duì)應(yīng)關(guān)系，使得α上的一點(diǎn)f(u)，在β上的對(duì)應(yīng)點(diǎn)為g(u)，其中 0≤u≤1。此時(shí)，即可通過一定的移位路徑內(nèi)插生成線狀要素 γ，本文以對(duì)應(yīng)點(diǎn)間的直線作為移位路徑進(jìn)行形狀內(nèi)插，不妨令h:[0,1]→γ，建立γ與α、β的關(guān)系如下[7]：

式中：0≤u≤1，0≤t≤1；h(t, u)為與 f(u)，g(u)對(duì)應(yīng)的內(nèi)插點(diǎn)；t為一個(gè)與比例尺有關(guān)的參數(shù)，表明內(nèi)插結(jié)果隨比例尺的不同而變化。

如何利用線狀要素固有的彎曲信息提高內(nèi)插精度是本文研究重點(diǎn)。對(duì)線狀要素而言，其空間結(jié)構(gòu)特征信息主要通過彎曲特征來表現(xiàn)[14-15]。分析可以發(fā)現(xiàn)，同一線狀要素的不同比例尺表達(dá)在形態(tài)結(jié)構(gòu)上的區(qū)別在于大比例尺表達(dá)更為細(xì)致，但這種區(qū)別并不影響對(duì)彎曲層次結(jié)構(gòu)的整體感官認(rèn)知。從整體上看，不同比例尺表達(dá)上彎曲結(jié)構(gòu)具有相似性，具體表現(xiàn)為獨(dú)立彎曲的數(shù)量及結(jié)構(gòu)相似，對(duì)應(yīng)獨(dú)立彎曲的高層次彎曲結(jié)構(gòu)近乎一致，低層次彎曲結(jié)構(gòu)則較相近。因此，兩線狀要素彎曲層次結(jié)構(gòu)的相似性可以為選取特征點(diǎn)并建立對(duì)應(yīng)關(guān)系提供重要的約束信息，這亦是進(jìn)一步提高M(jìn)orphing精度并保持中間內(nèi)插結(jié)果彎曲特征一致性的重要依據(jù)。

2 基于彎曲的Morphing方法

2.1 彎曲的相關(guān)基本概念

文獻(xiàn)[14]基于約束 Delaunay三角網(wǎng)(Constrained Delaunay Triangulation，簡(jiǎn)稱CDT)模型提出了一種方法描述線狀要素彎曲特征在深度上的層次結(jié)構(gòu)，通過對(duì)三角網(wǎng)覆蓋區(qū)域由外向內(nèi)的三角形“剝皮”操作，以“剝皮”行進(jìn)過程中不同特征的三角形為依據(jù)構(gòu)建二叉樹，實(shí)現(xiàn)了對(duì)線狀要素大彎曲套小彎曲層次結(jié)構(gòu)的表達(dá)。基于此，本文利用線狀要素一側(cè)的CDT識(shí)別其彎曲結(jié)構(gòu)，通過兩線狀要素同側(cè)的彎曲結(jié)構(gòu)識(shí)別對(duì)應(yīng)彎曲。因而，不妨規(guī)定后續(xù)所涉及的彎曲結(jié)構(gòu)及彎曲區(qū)域都僅針對(duì)線狀要素右側(cè)。下面首先將討論彎曲的相關(guān)概念，進(jìn)而發(fā)展彎曲樹和彎曲森林2個(gè)更深層次的概念。圖1所示為線狀要素的結(jié)構(gòu)表達(dá)。

如圖 1(a)所示，對(duì)于一個(gè)復(fù)合彎曲 A，將兩孩子及各頂點(diǎn)編碼如下：以A_Left代表A的左孩子彎曲，A_Right代表A的右孩子彎曲；將彎曲A各頂點(diǎn)依次編號(hào)為{A_StartID，A_StartID +1，…，A_EndID-1，A_EndID }，同時(shí)令左孩子彎曲的首尾頂點(diǎn)序號(hào)為A_LeftStartID和A_LeftEndID，右孩子彎曲的首尾頂點(diǎn)序號(hào)為 A_RightStartID和 A_RightEndID，于是有：A_StartID≤A_LeftStartID＜A_LeftEndID=A_RightStartID＜A_RightEndID≤A_EndID，其中左下角較粗箭頭代表線狀要素方向。翟仁健等[16]認(rèn)為不包含孩子彎曲的彎曲稱為基本彎曲，如彎曲A_Left、彎曲 A_Right和彎曲 B。進(jìn)而，由若干個(gè)彎曲套合組成的復(fù)雜彎曲稱為復(fù)合彎曲，如彎曲 A。不是任何其他彎曲的孩子彎曲的彎曲稱為獨(dú)立彎曲，如彎曲A和彎曲 B。不難發(fā)現(xiàn)，獨(dú)立彎曲可能是基本彎曲，也可能是復(fù)合彎曲。對(duì)于一個(gè)線狀要素，其往往存在多個(gè)獨(dú)立彎曲，這些獨(dú)立彎曲無法在同一個(gè)二叉樹中表達(dá)，為此，下面提出彎曲樹和彎曲森林的概念。

定義1 彎曲樹：表達(dá)一個(gè)獨(dú)立彎曲的彎曲層次結(jié)構(gòu)的二叉樹稱為該獨(dú)立彎曲的彎曲樹。彎曲樹的葉子節(jié)點(diǎn)對(duì)應(yīng)基本彎曲，根節(jié)點(diǎn)對(duì)應(yīng)獨(dú)立彎曲，其他節(jié)點(diǎn)對(duì)應(yīng)復(fù)合彎曲，結(jié)點(diǎn)的層次關(guān)系表達(dá)了彎曲的層次結(jié)構(gòu)，如圖1(b)的彎曲樹A、彎曲樹B分別為圖1(a)中獨(dú)立彎曲A、獨(dú)立彎曲B的彎曲層次結(jié)構(gòu)表達(dá)。

定義2 彎曲森林：一個(gè)線狀要素通常含有多個(gè)獨(dú)立彎曲，每個(gè)獨(dú)立彎曲對(duì)應(yīng)一顆彎曲樹，所有這些彎曲樹按線狀要素方向依次排列，構(gòu)成彎曲森林。如圖1所示，彎曲樹A和彎曲樹B共同構(gòu)成線狀要素α的彎曲森林。

2.2 匹配指標(biāo)

對(duì)兩線狀要素α和β分別建立 CDT并識(shí)別彎曲森林后，即可對(duì)彎曲樹及其孩子彎曲進(jìn)行匹配，以獲得匹配線段。由于兩線狀要素的結(jié)構(gòu)形態(tài)并不完全一致，兩彎曲森林也可能不一致，體現(xiàn)在2個(gè)方面：(1)兩彎曲森林中彎曲樹的數(shù)量不一定相等；(2) 對(duì)應(yīng)彎曲樹的深度及形態(tài)結(jié)構(gòu)不一致。因此，僅從彎曲森林及彎曲樹的角度，難以準(zhǔn)確地進(jìn)行彎曲匹配，必須引入度量彎曲相似性的指標(biāo)，以指導(dǎo)彎曲匹配。

Poorten等[17]提出了彎曲面積、彎曲周長(zhǎng)等6種有關(guān)彎曲的度量指標(biāo)，考慮到對(duì)應(yīng)彎曲在尺寸上必定相近，同時(shí)相較彎曲周長(zhǎng)，彎曲面積更符合人們將彎曲及其延伸區(qū)域視為一個(gè)整體的直觀認(rèn)知，本文采用彎曲面積作為彎曲大小的度量指標(biāo)。具體地，將彎曲 A的基線及 A各邊圍成的多邊形區(qū)域稱為 A的彎曲區(qū)域，而彎曲區(qū)域覆蓋的面積即為彎曲面積，記為SA。類似地，線狀要素α各獨(dú)立彎曲的彎曲面積之和稱為α的線彎曲總面積，記為αS。

小比例尺地圖上的彎曲是大比例尺地圖上對(duì)應(yīng)彎曲的簡(jiǎn)化表達(dá)形式，理想狀況下，由于左右簡(jiǎn)化程度相當(dāng)，彎曲面積增減相互抵消，兩對(duì)應(yīng)彎曲面積之比收斂于 1，但在地圖生產(chǎn)過程中受各種因素影響，彎曲面積呈現(xiàn)規(guī)律性地增大或減小，此時(shí)對(duì)應(yīng)彎曲的面積之比收斂于另一個(gè)值。為了估算這個(gè)值，并有效指導(dǎo)彎曲匹配，下面引入彎曲面積比和線彎曲總面積比概念。

圖1 線狀要素的結(jié)構(gòu)表達(dá)Fig.1 Structural representation of linear feature

定義3 彎曲面積比：彎曲A的面積與彎曲B的面積的比值稱為彎曲面積比，記為Ratio(A, B)，表達(dá)為：

定義4 線彎曲總面積比：線狀要素α的線彎曲總面積與線狀要素β的線彎曲總面積的比值稱為線彎曲總面積比，記為),(βαRatio，表達(dá)為：

線彎曲總面積比),(βαRatio即為對(duì)應(yīng)彎曲面積比收斂值的估算值，理想狀況下，若兩彎曲A和B為于誤差不可避免，彎曲面積比不可能嚴(yán)格等于線彎曲總面積比，因此必須給出適當(dāng)?shù)拈撝捣秶匀萑陶`差。本文利用參數(shù) Threshold結(jié)合線彎曲總面積比設(shè)定閾值范圍U，使得UBARatio∈),(時(shí)，認(rèn)為兩彎曲為對(duì)應(yīng)彎曲，其中U表達(dá)如下：

顯然，當(dāng)參數(shù)Threshold取值較小時(shí)，閾值范圍U較大，此時(shí)差異較大的2個(gè)彎曲將被視作對(duì)應(yīng)彎曲，當(dāng)參數(shù)Threshold取值較大時(shí)，閾值范圍U較小，一些對(duì)應(yīng)彎曲可能無法正確識(shí)別。因此，設(shè)置一個(gè)合理的 Threshold值極為重要。通過大量實(shí)驗(yàn)發(fā)現(xiàn)，

2.3 彎曲匹配

彎曲匹配分兩步進(jìn)行。首先是彎曲樹匹配，即對(duì)彎曲森林中的彎曲樹進(jìn)行匹配，提取對(duì)應(yīng)獨(dú)立彎曲；然后是孩子彎曲匹配，即匹配兩對(duì)應(yīng)獨(dú)立彎曲的孩子彎曲，提取對(duì)應(yīng)線段。定義數(shù)組CorrespondingTree記錄匹配成功的對(duì)應(yīng)彎曲樹，定義數(shù)組CorrespondingSegment記錄匹配成功的對(duì)應(yīng)線段。

彎曲樹匹配時(shí)，對(duì)兩彎曲森林同時(shí)從第1棵彎曲樹開始匹配，若彎曲樹i與彎曲樹j為對(duì)應(yīng)彎曲樹，則添加記錄(i, j)到CorrespondingTree，并匹配它們的下1棵彎曲樹；若彎曲樹i，j不為對(duì)應(yīng)彎曲樹，則忽略較小的彎曲樹，并將較小彎曲樹后面的彎曲樹與當(dāng)前較大彎曲樹進(jìn)行匹配。這樣依次匹配，直到其中一個(gè)彎曲森林的彎曲樹被全部遍歷。彎曲樹匹配后，還需注意殘留線段的存在。假設(shè)在彎曲樹匹配過程中產(chǎn)生的匹配彎曲樹為(i+2，j+3)，則線段a：{i_EndID，…，(i+2)_StartID}和線段 b：{j_EndID，…，(j+3)_StartID}并未顧及到，稱為殘留線段，此時(shí)可以簡(jiǎn)單地將線段對(duì)(a，b)作為對(duì)應(yīng)線段記錄添加到CorrespondingSegment。如圖2所示，匹配完彎曲樹后，應(yīng)將(B0，L1)添加到 CorrespondingSegment。

在彎曲樹匹配的基礎(chǔ)上，可對(duì)對(duì)應(yīng)彎曲樹進(jìn)行深層次的孩子彎曲匹配。針對(duì)建立的對(duì)應(yīng)彎曲，如果它們都有孩子彎曲且左右孩子彎曲分別對(duì)應(yīng)，則孩子彎曲匹配成功，并將對(duì)應(yīng)的孩子彎曲作為當(dāng)前對(duì)應(yīng)彎曲進(jìn)行更深層次的孩子彎曲匹配；否則將兩對(duì)應(yīng)彎曲線段作為對(duì)應(yīng)線段記錄添加到 CorrespondingSegment。與彎曲樹匹配過程相似，孩子彎曲匹配中也有殘留線段存在，假設(shè)對(duì)應(yīng)彎曲A和B的左右孩子彎曲也分別對(duì)應(yīng)，且在彎曲 A中有 A_StartID＜A_LeftStartID，A_RightEndID＜A_EndID，如圖 1(a)所示，對(duì)應(yīng)的在彎曲B中有B_StartID＜B_LeftStartID, B_RightEndID＜B_EndID，則彎曲A的殘留線段為a1：{A_StartID, …,A_LeftStartID}和 a2：{A_RightEndID, …, A_EndID}，彎曲B的殘留線段為b1：{B_StartID, …, B_LeftStartID}和 b2：{B_RightEndID, …, B_EndID}，此時(shí)，將(a1, b1)和(a2, b2)作為對(duì)應(yīng)線段記錄添加到CorrespondingSegment。

圖2 兩對(duì)應(yīng)線狀要素的彎曲森林Fig.2 Bend forests of two corresponding linear features

整個(gè)彎曲匹配過程完成后，得到一個(gè)對(duì)應(yīng)線段數(shù)組 CorrespondingSegment，該數(shù)組的每一個(gè)元素記錄一對(duì)對(duì)應(yīng)線段，每對(duì)對(duì)應(yīng)線段的兩始點(diǎn)和兩終點(diǎn)分別為一對(duì)對(duì)應(yīng)特征點(diǎn)。因此，在彎曲匹配過程中，對(duì)對(duì)應(yīng)彎曲特征點(diǎn)完成了提取及匹配，并確定為對(duì)應(yīng)特征點(diǎn)，進(jìn)而對(duì)每對(duì)對(duì)應(yīng)線段利用現(xiàn)有算法(本文采用線性插值算法)按統(tǒng)一參數(shù)t進(jìn)行Morphing，得到的結(jié)果即為本文方法最終Morphing結(jié)果。

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

下面采用模擬實(shí)驗(yàn)和實(shí)例來說明本文方法的可行性和有效性。本文引入線性插值算法[7]選取并建立對(duì)應(yīng)特征點(diǎn)，以對(duì)應(yīng)特征點(diǎn)間的直線作為移位路徑；將直接使用線性插值算法所得結(jié)果與識(shí)別彎曲后再分段進(jìn)行線性插值的結(jié)果進(jìn)行對(duì)比。這里，采用Translation指標(biāo)[7]對(duì) 2種方法的結(jié)果進(jìn)行評(píng)價(jià)。Translation指標(biāo)Translation指標(biāo)值。Translation指標(biāo)反應(yīng)了對(duì)應(yīng)特征點(diǎn)間“移位矢量”的變化情況，在移位路徑為對(duì)應(yīng)特征點(diǎn)間直線的情況下，其越小說明 Morphing的效果越好。

3.1 模擬算例分析與比較

模擬算例實(shí)驗(yàn)數(shù)據(jù)如圖3所示。其中，圖3(a)中線狀數(shù)據(jù)頂點(diǎn)較多，表達(dá)較細(xì)致，代表地理實(shí)體L表達(dá)于大比例尺地圖上的線狀要素α，圖3(b)中線狀數(shù)據(jù)代表L表達(dá)于小比例尺地圖上的線狀要素β，左下角箭頭指示線狀數(shù)據(jù)方向。另外，α和β的 CDT結(jié)構(gòu)和彎曲樹結(jié)構(gòu)亦展示于圖3中。α和β雖形態(tài)有所差別，但彎曲結(jié)構(gòu)相似，且各對(duì)應(yīng)彎曲的彎曲特征點(diǎn)為重合點(diǎn)。

圖4所示為線性插值算法對(duì)應(yīng)特征點(diǎn)結(jié)果。圖5所示為基于彎曲的線性插值算法對(duì)應(yīng)特征點(diǎn)結(jié)果。圖4(a)所示為直接使用線性插值算法得到的對(duì)應(yīng)特征點(diǎn)結(jié)果，而圖 5(a)為在識(shí)別彎曲的基礎(chǔ)上使用線性插值算法得到的對(duì)應(yīng)特征點(diǎn)結(jié)果，其中兩線狀要素之間的直線為對(duì)應(yīng)線，對(duì)應(yīng)線的兩端點(diǎn)為對(duì)應(yīng)特征點(diǎn)。由于對(duì)應(yīng)線多，較難分辨，僅顯示部分對(duì)應(yīng)線。對(duì)于α的彎曲特征點(diǎn) f(0)，f(3)，f(11)，f(18)，f(20)和 f(29)，在圖4(b)中，僅有始末點(diǎn)g(0)和g(29)為對(duì)應(yīng)的彎曲特征點(diǎn)，而 g(3)，g(11)，g(18)和 g(20)偏離于對(duì)應(yīng)的彎曲特征點(diǎn)，顯然不夠準(zhǔn)確，其Translation指標(biāo)值為288.5；圖5(b)中，彎曲特征的識(shí)別保證了兩線狀要素彎曲特征點(diǎn)準(zhǔn)確匹配，g′(0)，g′(3)，g′(11)，g′(18)，g′(20)和g′(29)均為對(duì)應(yīng)彎曲特征點(diǎn)，其 Translation指標(biāo)值為216.0，Morphing精度有較大提高。圖6和7分別為2種方法的形狀內(nèi)插結(jié)果。其中t=0和t=1分別為L(zhǎng)的大、小比例尺表達(dá)，t=0.25，0.5，0.75為不同程度的形狀內(nèi)插結(jié)果。可以看出：圖7的結(jié)果更加符合人的直觀認(rèn)知。比較圖6和7中標(biāo)記的“Ⅰ”區(qū)和“Ⅱ”區(qū)不同程度內(nèi)插結(jié)果形態(tài)變化特點(diǎn)可以發(fā)現(xiàn)，未識(shí)別彎曲的方法試圖對(duì)形態(tài)特征進(jìn)行重構(gòu)，即原來的特征點(diǎn)消失，另外產(chǎn)生新特征點(diǎn)并移至該處，而基于彎曲的方法則在各內(nèi)插結(jié)果中有效保持了彎曲特征點(diǎn)的一致性，因此，進(jìn)行彎曲識(shí)別后的內(nèi)插結(jié)果更加準(zhǔn)確。

3.2 實(shí)際算例分析與比較

實(shí)際算例實(shí)驗(yàn)數(shù)據(jù)采用中國鐵路長(zhǎng)林線的一段，數(shù)據(jù)來源于國家基礎(chǔ)地理信息系統(tǒng)(National Fundamental Geographic Information System，簡(jiǎn)稱NFGIS)，如圖8所示。其中，圖8(a)所示為該段鐵路在1:500萬比例尺地圖上的表達(dá)，圖8(b)所示為1:1 000萬比例尺地圖上的表達(dá)，這一段鐵路數(shù)據(jù)彎曲明顯，2種不同比例尺鐵路數(shù)據(jù)差異較大，較易體現(xiàn)出不同算法實(shí)驗(yàn)結(jié)果的差別。

圖3 L的不同比例尺表達(dá)及彎曲二叉樹結(jié)構(gòu)Fig.3 Representations of L at different scales and their binary bend structure trees

圖4 線性插值算法對(duì)應(yīng)特征點(diǎn)結(jié)果Fig.4 Corresponding characteristic points obtained by linear interpolation algorithm

圖5 基于彎曲的線性插值算法對(duì)應(yīng)特征點(diǎn)結(jié)果Fig.5 Corresponding characteristic points obtained by linear interpolation algorithm based on bend structures

圖6 線性插值算法形狀內(nèi)插結(jié)果Fig.6 Results obtained by linear interpolation algorithm

圖9所示為線性插值算法對(duì)應(yīng)特征點(diǎn)結(jié)果。圖10所示為基于彎曲的線性插值算法對(duì)應(yīng)特征點(diǎn)結(jié)果。圖9(a)所示為直接使用線性插值算法得到的對(duì)應(yīng)特征點(diǎn)結(jié)果；圖10(a)所示為在識(shí)別彎曲的基礎(chǔ)上使用線性插值算法得到的對(duì)應(yīng)特征點(diǎn)結(jié)果。比較可以發(fā)現(xiàn)，圖10(a)的對(duì)應(yīng)線分布更加勻稱、合理；將圖 9(a)中標(biāo)記的“Ⅲ”區(qū)和圖10(a)中標(biāo)記的“Ⅳ”區(qū)放大，刪除部分對(duì)應(yīng)線并以α的獨(dú)立彎曲為依據(jù)修改部分對(duì)應(yīng)線染色狀態(tài)后分別顯示于圖9(b)和圖10(b)。可以看到，圖9(b)中部分非對(duì)應(yīng)獨(dú)立彎曲上的特征點(diǎn)被識(shí)別為對(duì)應(yīng)特征點(diǎn)，如圖9(b)虛線連接的對(duì)應(yīng)特征點(diǎn)，偏差較大，而圖10(b)的結(jié)果由于利用了彎曲信息，α中獨(dú)立彎曲的特征點(diǎn)嚴(yán)格與β中對(duì)應(yīng)獨(dú)立彎曲的特征點(diǎn)匹配為對(duì)應(yīng)特征點(diǎn)；2個(gè)結(jié)果的Translation指標(biāo)值分別為75.2 km和50.3 km，基于彎曲的方法具有明顯優(yōu)勢(shì)；圖11和12中t=0.25，0.5，0.75顯示了2種方法不同程度的形狀內(nèi)插結(jié)果。

圖7 基于彎曲的線性插值算法形狀內(nèi)插結(jié)果Fig.7 Results obtained by linear interpolation algorithm based on bend structures

圖8 實(shí)際空間數(shù)據(jù)庫Fig.8 Real spatial data

圖9 線性插值算法對(duì)應(yīng)特征點(diǎn)結(jié)果Fig.9 Corresponding characteristic points obtained by linear interpolation algorithm

圖10 基于彎曲的線性插值算法對(duì)應(yīng)特征點(diǎn)結(jié)果Fig.10 Corresponding characteristic points obtained by linear interpolation algorithm based on bend structures

圖11 線性插值算法形狀內(nèi)插結(jié)果Fig.11 Results obtained by linear interpolation algorithm

圖12 基于彎曲的線性插值算法形狀內(nèi)插結(jié)果Fig.12 Results obtained by linear interpolation algorithm based on bend structures

4 結(jié)論

提出了一種基于彎曲結(jié)構(gòu)的線狀要素 Morphing方法。該方法充分利用線狀要素的層次彎曲結(jié)構(gòu)信息，將原始線狀要素分割成多對(duì)對(duì)應(yīng)線段，進(jìn)而對(duì)各對(duì)應(yīng)線段進(jìn)行Morphing。通過實(shí)驗(yàn)對(duì)比分析發(fā)現(xiàn)基于彎曲結(jié)構(gòu)的方法提高了Morphing精度，并有效保持了線狀要素的彎曲結(jié)構(gòu)特征。

[1] Li Z L, Wong M. Animating basic operations for digital map generalization with morphing techniques[C]//Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Science (Part B2). Beijing, 2008:637-642.

[2] 李精忠. 尺度空間地圖多重表達(dá)的面向?qū)ο髷?shù)據(jù)模型研究[D].武漢: 武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院, 2009: 67-72.LI Jing-zhong. An object-oriented model for map data multiple representation over scale space[D]. Wuhan: Wuhan University.School of Resource and Environmental Science, 2009: 67-72.

[3] Wolberg G. Image morphing: A survey[J]. The Visual Computer,1998, 14: 360-372.

[4] Guibas L, Hershberger J, Suri S. Morphing simple polygons[J].Discrete and Computational Geometry, 2000, 21(1): 1-34.

[5] Sester M, Brenner C. Continuous generalization for fast and smooth visualization on small displays[C]//Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. 2004: 1293-1298.

[6] Cecconi A. Integration of cartographic generalization and multi-scale databases for enhanced web mapping[D]. Zurich:University of Zurich. Faculty of Mathematics & Science, 2003:109-112.

[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: 248-260.

[8] Albrecht S. A solution to the vertex correspondence problem in 2D polygon morphing[D]. Osnabruck: Universitat Osnabruck.Department of Mathematics/Computer Science, 2006: 11-22.

[9] Efrat A, Har-Peled S, Guibas L J, et al. Morphing between polylines[C]//Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: ACM Press,2001: 680-689.

[10] Hahmann S, Bonneau G P, Caramiaux B, et al. Multi-resolution morphing for planar curves[J]. Computing, 2007, 79: 197-209.

[11] 戴塔根, 毛先成. 攀枝花鐵礦地測(cè)自動(dòng)成圖系統(tǒng)(GDPS)的研究和開發(fā)[J]. 中南工業(yè)大學(xué)學(xué)報(bào): 自然科學(xué)版, 1995, 26(5):565-569.DAI Ta-gen, MAO Xian-cheng. GPDS—An automatic generating and plotting system of geology-survey maps for panzhihua iron deposits[J]. Journal of Central South University of Technology: Natural Science, 1995, 26(5): 565-569.

[12] 趙建三. 基于格網(wǎng)DEM的自適應(yīng)等高線內(nèi)插方法[J]. 中南工業(yè)大學(xué)學(xué)報(bào): 自然科學(xué)版, 2003, 34(3): 315-319.ZHAO Jian-san. An adaptive algorithm of contour interpolation based on grid DEM[J]. Journal of Central South University of Technology: Natural Science, 2003, 34(3): 315-319.

[13] Chetverikov D, Szabo Z. A simple and efficient algorithm for detection of high curvature points in planar curves[C]//Proceedings of the 23rd Workshop of Australian Pattern Recognition Group. Steyr, 1999: 175-184.

[14] 艾廷華, 郭仁忠, 劉耀林. 曲線彎曲深度層次結(jié)構(gòu)的二叉樹表達(dá)[J]. 測(cè)繪學(xué)報(bào), 2001, 30(4): 343-348.AI Ting-hua, GUO Ren-zhong, LIU Yao-lin. A binary tree representation of curve hierarchical structure in depth[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(4): 343-348.

[15] Plazanet C, Affholder J G, Fritsch E. The importance of geometric modeling in linear feature generalization[J].Cartography and Geographic Information Systems, 1995, 22(4):291-305.

[16] 翟仁健, 武芳, 朱麗, 等. 曲線形態(tài)的結(jié)構(gòu)化表達(dá)[J]. 測(cè)繪學(xué)報(bào), 2009, 38(2): 175-182.ZHAI Ren-jian, WU Fang, ZHU Li, et al. Structured representation of curve shape[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(2): 175-182.

[17] Poorten P, Jones C B. Customisable line generalisation using delaunay triangulation[C]//Proceedings of the 19th International Cartographic Association Conference. Ottawa, 1999: 45-51.