更充分利用獨立彎曲結(jié)構(gòu)的線狀要素Morphing變換方法

彭東亮，鄧 敏，劉慧敏

中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南 長沙 410083

更充分利用獨立彎曲結(jié)構(gòu)的線狀要素Morphing變換方法

彭東亮，鄧 敏，劉慧敏

中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南 長沙 410083

提出更充分利用獨立彎曲結(jié)構(gòu)的線狀要素Morphing變換方法。該方法首先對不同比例尺表達(dá)的對應(yīng)線狀要素分別構(gòu)建約束Delaunay三角網(wǎng)并建立彎曲森林，然后進行彎曲匹配以獲得對應(yīng)彎曲。鑒于對應(yīng)彎曲“背面”的獨立彎曲結(jié)構(gòu)隱藏于更高層次的大彎曲中，將對應(yīng)彎曲重新構(gòu)建約束Delaunay三角網(wǎng)進而建立其“背面”的彎曲森林并進行彎曲匹配得到新的對應(yīng)彎曲。依此遞歸，更充分地挖掘?qū)?yīng)彎曲結(jié)構(gòu)。在此基礎(chǔ)上，將所有對應(yīng)彎曲的對應(yīng)起點和對應(yīng)終點都作為斷點切割原線狀要素，獲得對應(yīng)線段。最后，采用線性插值算法建立各對應(yīng)線段之間的對應(yīng)點，并以對應(yīng)點之間的直線段作為移位路徑進行Morphing變換。通過實例分析，驗證了本文充分利用獨立彎曲結(jié)構(gòu)的方法能夠提高對應(yīng)彎曲特征點的識別能力，從而能夠更好地保持彎曲特征點并改善Morphing變換效果。

Morphing；形狀內(nèi)插；彎曲；線狀要素；制圖綜合

1 引 言

在信息化地圖制圖學(xué)時代，空間數(shù)據(jù)的自動綜合仍是國際上制圖領(lǐng)域最具挑戰(zhàn)性和創(chuàng)造性的研究難題，這亦是GIS空間數(shù)據(jù)多尺度表達(dá)的需要［1］。近年來，用戶對電子地圖提出了連續(xù)尺度表達(dá)的新要求，這一方面有助于用戶在進行放大、縮小等操作時保持視點，另一方面使得用戶能夠從任意尺度查詢地圖信息。為了適應(yīng)這一要求，文獻(xiàn)［2］提出了地圖連續(xù)綜合技術(shù)，該技術(shù)通過對地圖進行連續(xù)微小的變形以實現(xiàn)地圖的連續(xù)尺度變換。Morphing變換技術(shù)是一種同時顧及形狀和顏色的圖像內(nèi)插技術(shù)，用于實現(xiàn)從源圖像到目標(biāo)圖像的平滑漸變，在動畫制作、圖像壓縮以及醫(yī)學(xué)圖像重構(gòu)等計算機可視化領(lǐng)域有廣泛應(yīng)用［3－5］。由于Morphing變換平滑漸變的思想與地圖連續(xù)綜合技術(shù)相契合，其在地圖連續(xù)綜合中亦逐漸受到重視。按照數(shù)據(jù)模型的不同，Morphing變換可以分為基于矢量數(shù)據(jù)的Morphing變換［6－11］和基于柵格數(shù)據(jù)的Morphing變換［12－14］。目前，基于矢量數(shù)據(jù)的Morphing變換主要用于道路、河流等線狀要素的形狀內(nèi)插，以生成所需尺度線狀要素形態(tài)［9－10］。

基于矢量數(shù)據(jù)的Morphing變換可分為兩個步驟：首先，對不同尺度上兩對應(yīng)要素建立對應(yīng)點；然后，以一定的移位路徑進行形狀內(nèi)插。文獻(xiàn)［15］指出，一般情況下由于Morphing變換幅度較小，不易產(chǎn)生拓?fù)鋯栴}，因此可以用對應(yīng)點之間的直線段作為移位路徑。可以看出，在移位路徑確定的前提下，對應(yīng)點的精度決定了Morphing變換結(jié)果的精度。在建立對應(yīng)點方面，文獻(xiàn)［9］鑒于較小比例尺線狀要素頂點數(shù)相對較少，提出對其重復(fù)搜索最長邊，并在最長邊中點增加頂點的策略，使得兩不同比例尺線狀要素具有相等的頂點數(shù)，進而按點號順序建立頂點之間的一一對應(yīng)關(guān)系。文獻(xiàn)［10］考慮到數(shù)據(jù)量對時間復(fù)雜度的影響，利用貝塞爾曲線篩選兩線狀要素弧度較大處的頂點作為特征點，然后以特征點、相鄰特征點間的線段為基本單位，借助動態(tài)規(guī)劃的方法進行匹配，這一方法既提高了運行效率，又在一定程度上保證了對應(yīng)點精度。文獻(xiàn)［16］對于線狀要素的每一個頂點，分別連接前后一定范圍內(nèi)的頂點，并選取有較大夾角的頂點作為候選點，然后從候選點中選取一定范圍內(nèi)夾角值最大的頂點作為特征點［17］，進而基于位移最小的原則建立特征點間對應(yīng)關(guān)系。綜上分析，目前已有的矢量數(shù)據(jù)Morphing變換方法在建立對應(yīng)點時是基于線狀要素的局部結(jié)構(gòu)，而忽視了整體結(jié)構(gòu)。在這種情況下，容易得到錯誤的對應(yīng)點，且這些錯誤將無法得到有效糾正，進而導(dǎo)致不合理的Morphing變換結(jié)果。為此，本文立足于線狀要素的整體結(jié)構(gòu)建立對應(yīng)線狀要素間的對應(yīng)點。

對于一線狀要素，將較大比例尺線狀要素記為A，較小比例尺線狀要素記為B，并令f：［0，1］→A為一連續(xù)函數(shù)，且f（0）和f（1）分別為A的起點和終點；令g：［0，1］→B為一連續(xù)函數(shù)，且g（0）和g（1）分別為B的起點和終點。對A和B建立對應(yīng)關(guān)系，使得A上一點f（u），在B上的對應(yīng)點為g（u），其中0≤u≤1。此時，即可通過一定的移位路徑內(nèi)插生成線狀要素Ct。本文以對應(yīng)點之間的直線段作為移位路徑，不妨令h（t，u）：［0，1］2→R2，且h（t，0）和h（t，1）分別為Ct的起點和終點，建立Ct與A、B的關(guān)系為［9］

式中，h（t，u）是與f（u）、g（u）對應(yīng)的內(nèi)插點；t為形狀內(nèi)插的程度，并與目標(biāo)比例尺有關(guān)。據(jù)式（1），當(dāng)t＝0時，內(nèi)插結(jié)果Ct為A；當(dāng)t＝1時，內(nèi)插結(jié)果Ct為B；當(dāng)0＜t＜1時，內(nèi)插結(jié)果即為中間比例尺線狀要素。如何更充分地利用獨立彎曲結(jié)構(gòu)提高對應(yīng)點精度是本文研究重點。對線狀要素而言，其空間結(jié)構(gòu)特征信息主要通過彎曲特征來表現(xiàn)［18－19］。分析可以發(fā)現(xiàn)，對應(yīng)線狀要素在形態(tài)結(jié)構(gòu)上的區(qū)別在于較大比例尺線狀要素更為細(xì)致，但這種區(qū)別并不影響人們對彎曲層次結(jié)構(gòu)的整體感官認(rèn)知。從整體上看，不同比例尺線狀要素的彎曲結(jié)構(gòu)具有相似性，這些相似彎曲結(jié)構(gòu)可以為建立對應(yīng)點映射關(guān)系提供重要約束。而在識別彎曲的過程中，部分獨立彎曲結(jié)構(gòu)由于隱藏于其他彎曲中而難以被發(fā)現(xiàn)，影響了對相似彎曲結(jié)構(gòu)的利用。因此，本文以獨立彎曲結(jié)構(gòu)為切入點充分挖掘線狀要素的彎曲結(jié)構(gòu)，提出一種更充分利用獨立彎曲結(jié)構(gòu)的線狀要素Morphing變換方法，采取從整體到局部的策略建立線狀要素之間的對應(yīng)點，以提高對應(yīng)點的精度。具體策略如圖1所示。

2 更充分利用獨立彎曲結(jié)構(gòu)的Morphing變換方法

2．1 彎曲的相關(guān)概念

文獻(xiàn)［18］基于約束Delaunay三角網(wǎng)（簡稱CDT）模型提出了一種方法描述線狀要素彎曲特征在深度上的層次結(jié)構(gòu)，通過對三角網(wǎng)覆蓋區(qū)域由外向內(nèi)的三角形“剝皮”操作，以“剝皮”行進過程中不同特征的三角形為依據(jù)構(gòu)建二叉樹，實現(xiàn)了對線狀要素大彎曲套小彎曲層次結(jié)構(gòu)的表達(dá)。這是一個基于Gestalt對稱性和連續(xù)性原則的方法，符合人們的視覺感官認(rèn)知，因此本文亦采用該方法識別彎曲結(jié)構(gòu)。為了能夠更好地描述本文方法，下面首先討論彎曲的相關(guān)概念。

圖1 本文方法流程圖Fig．1 The framework of Morphing transformation of linear features proposed

對于一個復(fù)合彎曲I，分別以ILeft代表I的左孩子彎曲，IRight代表I的右孩子彎曲；以IStart代表I的第一個頂點，IEnd代表I的最后一個頂點。相應(yīng)的，以ILeftStart和ILeftEnd分別代表彎曲ILeft的第一個和最后一個頂點；以IRightStart和IRightEnd分別代表彎曲IRight的第一個和最后一個頂點。于是，這些頂點的序號大小具有如下關(guān)系

據(jù)文獻(xiàn)［20］，不包含孩子彎曲的彎曲為基本彎曲，以圖2（a）為例（左下角箭頭指示線狀要素A1的方向），如彎曲ILeft1、IRight1、J1、KLeft1、KRight1；由若干個彎曲套合組成的復(fù)雜彎曲稱為復(fù)合彎曲，如彎曲I1、K1；若一彎曲不是任何其他彎曲的孩子彎曲，則該彎曲為獨立彎曲，如彎曲I1、J1、K1。不難發(fā)現(xiàn)，獨立彎曲可能是基本彎曲，也可能是復(fù)合彎曲。對于一個線狀要素，其往往存在多個獨立彎曲，這些獨立彎曲無法表達(dá)于同一個二叉樹中，為此，下面提出彎曲樹和彎曲森林的概念。

圖2 線狀要素的彎曲結(jié)構(gòu)表達(dá)Fig．2 Bend structural representation of linear features

定義1：彎曲樹。表達(dá)一個獨立彎曲層次結(jié)構(gòu)的二叉樹。彎曲樹的葉子結(jié)點對應(yīng)基本彎曲，根結(jié)點對應(yīng)獨立彎曲，其他結(jié)點對應(yīng)復(fù)合彎曲，結(jié)點的層次關(guān)系表達(dá)了彎曲的層次結(jié)構(gòu)。如圖2（b）所示，彎曲樹I1、J1、K1分別為圖2（a）中獨立彎曲I1、J1、K1的彎曲層次結(jié)構(gòu)表達(dá)。

定義2：彎曲森林。一個線狀要素?fù)碛袃蓚?cè)，即左側(cè)和右側(cè)，每一側(cè)都通常含有多個獨立彎曲，每個獨立彎曲對應(yīng)一顆彎曲樹，同一側(cè)的彎曲樹按線狀要素方向依次排列，構(gòu)成彎曲森林。據(jù)此，一個線狀要素有左、右兩個彎曲森林。如圖2所示，彎曲樹I1、J1、K1共同構(gòu)成線狀要素A1右側(cè)的彎曲森林ARight1。

2．2 匹配指標(biāo)

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

文獻(xiàn)［21］在裁剪彎曲以對線狀要素進行簡化時基于CDT模型提出了面積、周長、深度、平均寬度、寬度標(biāo)準(zhǔn)差和裁剪前后基線與線狀要素間夾角變化量等6種有關(guān)彎曲的度量指標(biāo)。由于兩對應(yīng)線狀要素間的差異度與比例尺的跨度有關(guān)，并且同一對應(yīng)線狀要素各局部的差異度也不盡一致，所以這些指標(biāo)值會有較大波動，不利于對應(yīng)彎曲的識別。分析發(fā)現(xiàn)，彎曲的基線不依賴于彎曲的內(nèi)部結(jié)構(gòu)，因此受上述差異度的影響較小。這里，彎曲基線是由彎曲的起點和終點連接而成的直線段。例如在圖2（a）中，彎曲I1的基線為直線段，記為B（I1）；彎曲的基線為直線段，記為B。下面將采用彎曲基線夾角和彎曲基線長度比這兩個指標(biāo)作為兩彎曲是否為對應(yīng)彎曲的判定標(biāo)準(zhǔn)。

定義3：彎曲基線夾角。對于兩個彎曲，將一個彎曲基線移向另一個彎曲基線，使它們的起點重合，則這兩個彎曲基線之間大小為［0，π］的夾角即為彎曲基線夾角。以彎曲I1、I2為例，它們的彎曲基線夾角記為ABL（I1，I2）。

理想狀況下，彎曲基線夾角應(yīng)該等于0。但由于數(shù)據(jù)生產(chǎn)過程中誤差不可避免，從而使得彎曲基線夾角并不一定嚴(yán)格等于0。因此，必須給出適當(dāng)?shù)拈撝礣A以容忍誤差。具體地，若彎曲I1、I2為對應(yīng)彎曲，則其彎曲基線夾角須滿足

定義4：彎曲基線長度比。以彎曲I1、I2為例，B（I1）與B（I2）的長度比值稱為彎曲I1、I2的彎曲基線長度比，記為RBL（I1，I2），表達(dá)為

理想狀況下，彎曲基線長度比應(yīng)該等于1。同樣考慮到誤差不可避免，這里給定閾值范圍U，使得若彎曲I1、I2為對應(yīng)彎曲，則須滿足

式中，U定義為

式中，TL∈［0，1］是一個控制閾值范圍U的參數(shù)，其大小可根據(jù)數(shù)據(jù)的實際情況而定。值得注意的是，當(dāng)TL取值較小時，閾值范圍U較大，此時差異較大的兩個彎曲可能被視作對應(yīng)彎曲；當(dāng)TL取值較大時，閾值范圍U較小，一些實際對應(yīng)彎曲可能無法正確識別。因此，一個適當(dāng)?shù)腡L非常重要。

綜上分析，只有當(dāng)兩個彎曲同時滿足式（3）和式（5）時，這兩個彎曲才可被當(dāng)做對應(yīng)彎曲。

2．3 彎曲匹配

彎曲匹配分為兩個主要步驟：獨立彎曲匹配和子彎曲匹配。獨立彎曲匹配是對彎曲森林中的獨立彎曲進行匹配以發(fā)現(xiàn)對應(yīng)獨立彎曲的過程。子彎曲匹配是匹配當(dāng)前對應(yīng)彎曲的子彎曲的過程，該步驟使彎曲匹配可以遞歸深入到較低層次的彎曲結(jié)構(gòu)中。下面將對整個彎曲匹配過程進行詳細(xì)描述。

2．3．1 獨立彎曲匹配

由于每個線狀要素有兩個彎曲森林，因此本步驟亦需對兩線狀要素的左、右側(cè)彎曲森林中的獨立彎曲分別進行匹配。盡管在2．2節(jié)中已提出ABL、RBL作為兩彎曲是否為對應(yīng)彎曲的判定指標(biāo)，但僅根據(jù)這兩個指標(biāo)判斷兩個獨立彎曲是否為對應(yīng)彎曲仍有可能導(dǎo)致錯誤。這是因為兩同側(cè)彎曲森林中都含有多個獨立彎曲，可能出現(xiàn)兩獨立彎曲位置相差很大但彎曲參數(shù)接近（即滿足式（3）和式（5））的情況，而這樣的兩個獨立彎曲不應(yīng)被當(dāng)做對應(yīng)獨立彎曲。因此，進一步提出限制條件，以避免這種錯誤發(fā)生。

定義5：沿線狀要素長度。假設(shè)p0是線狀要素D上的一個點，其沿線狀要素長度為D的起點沿著D到p0的線段長度。

定義6：相對位置（relative location）。假設(shè)p0是線狀要素D上的一個點，其相對位置為p0的沿線狀要素長度與D 的長度之比，記為RLo（p0）。顯然，RLo（p0）∈［0，1］。

一般的，若兩個彎曲I、J為對應(yīng)彎曲，則它們起點和終點的相對位置應(yīng)該接近，即相對位置之差的絕對值｜RLo（IStrart）－RLo（JStart）｜和｜RLo（IEnd）－RLo（JEnd）｜都應(yīng)該很小。這樣，可以為相對位置之差的絕對值設(shè)定一個閾值以限定匹配目標(biāo)搜索范圍。這個閾值的設(shè)定需要考慮兩個方面：其一，從縮小搜索范圍、避免錯誤匹配的角度，該閾值應(yīng)盡可能小；其二，從避免漏掉真對應(yīng)獨立彎曲的角度，該閾值應(yīng)盡可能大。下面將借助相對長度以確定這個合適的閾值。

定義7：相對長度（relative length）。假設(shè)I是線狀要素D上的一個彎曲，I的相對長度為I的長度與D的長度之比，記為RLe（I），RLe（I）∈［0，1］。在實際應(yīng)用中，RLe（I）＝RLo（IEnd）－RLo（IStart）。

分析可知，兩彎曲相對長度的差距越大，則它們是對應(yīng)彎曲的可能性越小。這里，以LIB（larger independent bend）表示當(dāng)前遍歷的兩個獨立彎曲中相對長度大的獨立彎曲，以SIB（smaller independent bend）表示相對長度較小的獨立彎曲，提出如下假設(shè)：

假設(shè)1：對于兩個獨立彎曲，當(dāng)RLe（SIB）＞0．5RLe（LIB）時，這兩個獨立彎曲才有可能被判定為對應(yīng)獨立彎曲。這里，將參數(shù)設(shè)置為0．5亦是基于兩個方面的原因：其一，當(dāng)RLe（SIB）≤0．5 RLe（LIB）時，這兩個獨立彎曲幾乎不可能是對應(yīng)獨立彎曲，因此參數(shù)0．5能夠識別并直接擯棄差異較大的非對應(yīng)獨立彎曲；其二，參數(shù)0．5給獨立彎曲匹配留有足夠大的差異空間，不會漏掉真對應(yīng)獨立彎曲。根據(jù)此假設(shè)，可以得到如下關(guān)系：（RLo（LIBEnd）－RLo（SIBEnd））－（RLo（LIBStart）－

如上所述，相對位置之差的絕對值｜RLo（LIBStrart）－RLo（SIBStart）｜和｜RLo（LIBEnd）－RLo（SIBEnd）｜都應(yīng)該很小，因此把差異空間平分為兩半，分別容忍兩個獨立彎曲起點的差異和終點的差異，進一步提出如下假設(shè)：

假設(shè)2：對于兩個獨立彎曲，僅當(dāng)滿足以下公式時，它們才有可能被判定為獨立彎曲。即

值得注意的是，式（8）、式（9）是式（7）的充分不必要條件。這里，根據(jù)假設(shè)1和假設(shè)2推導(dǎo)出來的參數(shù)0．25能夠保證搜索范圍內(nèi)不會出現(xiàn)兩個獨立彎曲位置相差很大但彎曲參數(shù)接近的情況，又留有足夠大的差異空間保證了不會漏掉真正對應(yīng)的獨立彎曲。因此，參數(shù)0．25是合理的，且具有普適意義。到此為止，兩彎曲被判定為對應(yīng)獨立彎曲的條件已全部給出，即若兩個獨立彎曲同時滿足式（3）、式（5）、式（8）和式（9）時，這兩個獨立彎曲將被判定為對應(yīng)獨立彎曲。

2．3．2 孩子彎曲匹配

定義數(shù)組Corresponding Bends記錄匹配成功的對應(yīng)彎曲。首先，將一對對應(yīng)獨立彎曲添加到Corresponding Bends中；然后，將該對對應(yīng)獨立彎曲作為當(dāng)前對應(yīng)彎曲進行孩子彎曲匹配。對于當(dāng)前對應(yīng)彎曲：

（1）如果它們都有孩子彎曲且左、右子彎曲分別對應(yīng)，即滿足式（3）和式（5），則將左、右兩對對應(yīng)子彎曲都添加到Corresponding Bends中，并將它們分別作為當(dāng)前對應(yīng)彎曲進行更深層次子彎曲匹配。

（2）如果它們都有子彎曲，但左、右子彎曲并不分別對應(yīng)，則有可能是圖3所示的情況。I3和I4為對應(yīng)彎曲，在它們的孩子彎曲中，還有L3和L4及M3和M4也分別是對應(yīng)彎曲。這里，將J3和K3稱為干擾彎曲。為了排除干擾彎曲并準(zhǔn)確識別對應(yīng)彎曲（L3，L4）和（M3，M4），分別計算RBL（LSBLaC，SSBLeC）和RBL（LSBLaC，SSBRiC）。其中，LSBLaC為較大比例尺線狀要素上彎曲的較大孩子彎曲，SSBLeC為較小比例尺線狀要素上彎曲的左孩子彎曲，SSBRiC為較小比例尺線狀要素上彎曲的右子彎曲。這里，彎曲大小的依據(jù)為彎曲基線長度。如圖3所示，需要計算RBL（K3，L4）和RBL（K3，M4）。如果這兩個值都大于式（6）中所定義的TL，則將LSBLaC和較小比例尺線狀要素上的當(dāng)前彎曲LSB作為當(dāng)前對應(yīng)彎曲（但作為對應(yīng)彎曲記錄添加到Corresponding Bends）進行更深層次的子彎曲匹配。即將圖3中的K3和I4作為對應(yīng)彎曲進行孩子彎曲匹配，使得對應(yīng)彎曲（L3，L4）和（M3，M4）能夠被識別出來。（LSB：larger scale bend；LaC：larger child bend；SSB：smaller scale bend；LeC：left child bend；RiC：right child bend）。

圖3 干擾彎曲示例Fig．3 An illustration of the abnormal bends

（3）否則，該分支的子彎曲匹配結(jié)束。

當(dāng)采用子彎曲匹配對所有對應(yīng)獨立彎曲處理完畢后，最終將得到一個記錄對應(yīng)彎曲的數(shù)組Corresponding Bends。

2．3．3 更充分利用獨立彎曲結(jié)構(gòu)

獨立彎曲的起點和終點通常為較明顯的極值點，在制圖過程中亦能夠得到較好保留，且獨立彎曲是最高級的彎曲，不受干擾彎曲的影響。因此，對應(yīng)獨立彎曲能夠提供高精確度的對應(yīng)彎曲特征點。但是，在構(gòu)建CDT并建立彎曲森林的過程中，有部分獨立彎曲結(jié)構(gòu)隱藏于更高層次的大彎曲中無法被識別。這里，將描述如何更充分利用獨立彎曲結(jié)構(gòu)。

更充分利用獨立彎曲結(jié)構(gòu)這一思想體現(xiàn)在圖1中的步驟③。對于一對對應(yīng)彎曲（包括對應(yīng)獨立彎曲），對它們所含的彎曲線段分別重新構(gòu)建CDT，并構(gòu)建該對應(yīng)彎曲異側(cè)的彎曲森林（本側(cè)實際上就是對應(yīng)彎曲本身，已被識別），亦通俗地表述為建立對應(yīng)彎曲“背面”的彎曲森林。然后，對于新得到的兩個彎曲森林，又可重復(fù)利用彎曲匹配以識別對應(yīng)彎曲。為便于統(tǒng)一，這里規(guī)定在重復(fù)利用彎曲匹配的過程中，RLo、RLe等參數(shù)值仍然參照原線狀要素長度進行計算。

2．4 獲取對應(yīng)線段

對于Corresponding Bends中記錄的每對對應(yīng)彎曲，它們的對應(yīng)起點和對應(yīng)終點都將作為對應(yīng)彎曲特征點以對原始線狀要素進行切割。值得注意的是，由于同一對對應(yīng)彎曲特征點可能屬于不同的對應(yīng)彎曲（如一對對應(yīng)彎曲的對應(yīng)終點同時又是另外一對對應(yīng)彎曲的對應(yīng)起點）導(dǎo)致這些對應(yīng)彎曲特征點可能被重復(fù)識別。因此，對于重復(fù)的對應(yīng)彎曲特征點應(yīng)予以刪除，僅保留一對即可。在此基礎(chǔ)上，以對應(yīng)彎曲特征點為斷點將原始線狀要素進行對應(yīng)切割，即可得到若干對對應(yīng)線段。

3 實例分析

下面通過本文方法在實際數(shù)據(jù)中的應(yīng)用來論證其有效性，同時亦將給出直接使用線性插值算法的結(jié)果和本文方法在圖1中步驟③時（這里稱之為基于彎曲結(jié)構(gòu)的方法）的結(jié)果以作比較。這里采用加權(quán)Translation指標(biāo)［10］對各方法的結(jié)果進行定量評價。加權(quán)Translation指標(biāo)定義為一個線狀要素e：［0，1］→E，使得e（u）＝g（u）－f（u），其中，u∈［0，1］，則∑ei（｜ai｜＋｜bi｜）／（｜A｜＋｜B｜）即為加權(quán)Translation指標(biāo)值，其中，ei、ai、bi分別為線狀要素E、A、B上的直線段。加權(quán)Translation指標(biāo)反映了對應(yīng)點之間“移位矢量”的加權(quán)變化情況，在移位路徑為對應(yīng)點之間直線段的情況下，其越小說明Morphing變換的效果越好。

試驗數(shù)據(jù)采用中國鐵路長林線，該數(shù)據(jù)來源于國家基礎(chǔ)地理信息系統(tǒng)，如圖4所示。其中，圖4（a）為該段鐵路在1∶500萬比例尺地圖上的表達(dá)，圖4（b）為1∶1000萬比例尺地圖上的表達(dá)，該鐵路兩個不同比例尺線狀要素間差異較大，比較容易體現(xiàn)出不同算法試驗結(jié)果的差別。

本文試驗程序在C＃2005與ArcGIS Engine 9．2的環(huán)境下編譯運行，系統(tǒng)環(huán)境為Windows XP，CPU性能是Intel Core 2 Duo T6600 2．20 GHz，內(nèi)存為2 GB（DDR3 1067 MHz）。試驗中，本文2．2節(jié)介紹的參數(shù)TA取值15°，該值在文獻(xiàn)［22］中用于多尺度線狀要素目標(biāo)匹配，并取得了良好的效果，而該應(yīng)用與本文的彎曲基線匹配在原理上是相通的。TL根據(jù)本文試驗數(shù)據(jù)實際情況及作者大量實踐經(jīng)驗取值0．95（對于一般的數(shù)據(jù)而言，該值應(yīng)該都是合適的）。

圖4 長林線鐵路數(shù)據(jù)Fig．4 Spatial data of the Changlin railway

圖5顯示了基于彎曲方法和更充分利用獨立彎曲結(jié)構(gòu)方法的對應(yīng)彎曲特征點結(jié)果，其中每一根連接兩線狀要素的直線段的兩個端點代表一對對應(yīng)彎曲特征點。另外，圖5中三角網(wǎng)背景為對整個線狀要素構(gòu)建CDT的結(jié)果。從圖5可知，基于彎曲結(jié)構(gòu)的方法識別出18對對應(yīng)彎曲特征點，更充分利用獨立彎曲結(jié)構(gòu)的方法識別出25對對應(yīng)彎曲特征點。因此，更充分利用獨立彎曲結(jié)構(gòu)的方法對對應(yīng)彎曲特征點的識別能力有較大程度的提升（近40%）。

進一步地，將各方法的運行時間和加權(quán)Translation指標(biāo)值列于表1。從表中可以看出，基于彎曲結(jié)構(gòu)的方法由于涉及構(gòu)建CDT、建立彎曲森林及進行彎曲匹配等步驟，與直接使用線性插值算法相比，增加了運行時間，但同時也改善了Morphing變換效果。而更充分利用獨立彎曲結(jié)構(gòu)的方法由于需多次構(gòu)建CDT、建立彎曲森林及進行彎曲匹配，運行時間進一步增加，同時Morphing變換效果也得到了進一步改善。

圖5 對應(yīng)彎曲特征點識別結(jié)果Fig．5 Corresponding characteristic points detectedfrom the corresponding bends

表1 3種方法運行時間及加權(quán)Translation指標(biāo)值Tab．1 The running time and weighted Translation values of the three approaches

最后，列出各方法的對應(yīng)點結(jié)果及t＝0．25、0．5和0．75時的Morphing變換結(jié)果，如圖6所示。圖中每一根穿過線狀要素的直線段的兩個端點代表一對對應(yīng)點，中間與原線狀要素大致平行的3個線狀要素從上到下即依次為t＝0．25、0．5和0．75時的Morphing變換結(jié)果。從圖6中可以觀察到，相對于線性插值算法，基于彎曲結(jié)構(gòu)的方法和更充分利用獨立彎曲結(jié)構(gòu)的方法對彎曲結(jié)構(gòu)的保持都有大幅度提升。當(dāng)然，后兩者的差別則難以從肉眼上進行區(qū)分。

圖6 3個方法得到的對應(yīng)點及Morphing變換結(jié)果Fig．6 The results of both corresponding points and morphing transformation by the three different approaches

4 結(jié)論與展望

本文針對部分獨立彎曲結(jié)構(gòu)隱藏于更高層次的大彎曲中而難以被發(fā)現(xiàn)這一實際情況，提出了更充分利用獨立彎曲結(jié)構(gòu)的線狀要素Morphing變換方法。該方法的主要思想在于：①對原線狀要素構(gòu)建CDT并建立彎曲森林，通過彎曲匹配得到對應(yīng)彎曲；②對于對應(yīng)彎曲重新構(gòu)建CDT，建立其“背面”的彎曲森林再次運用彎曲匹配得到新的對應(yīng)彎曲，并可不斷遞歸挖掘?qū)?yīng)彎曲結(jié)構(gòu)；③將所有對應(yīng)彎曲的對應(yīng)起點和對應(yīng)終點作為斷點切割原線狀要素，獲得對應(yīng)線段。通過實例分析，論證了本文更充分利用獨立彎曲結(jié)構(gòu)的方法能夠提高對對應(yīng)彎曲特征點的識別能力，從而能夠更好地保持彎曲特征點，并改善Morphing變換效果。

對于較為極端的情況，如兩線狀要素結(jié)構(gòu)差異非常大或兩線狀要素本身并非對應(yīng)線狀要素，本文方法可能無法識別到對應(yīng)彎曲。此時，本文方法可以對兩線狀要素直接采用線性插值算法識別對應(yīng)點。也就是說，本文方法將蛻化為普通的線性插值算法，因此能夠適應(yīng)極端情況。

下一步研究工作將主要集中在兩個方面：①充分挖掘線狀要素的形態(tài)結(jié)構(gòu)特征信息，進一步改善Morphing變換效果；②研究不同程度形狀內(nèi)插結(jié)果與比例尺的對應(yīng)關(guān)系。

［1］ WANG Jiayao．Development Trends of Cartography and Geographic Information Engineering［J］．Acta Geodaetica et Cartographica Sinica，2010，39（2）：115－119．（王家耀．地圖制圖學(xué)與地理信息工程學(xué)科發(fā)展趨勢［J］．測繪學(xué)報，2010，39（2）：115－119．）

［2］ SESTER M，BRENNER C．Continuous Generalization for Visualization on Small Mobile Devices［C］∥Proceedings of the 11th International Symposium on Spatial Data Handling．Berlin：Springer－Verlag，2004：355－368．

［3］ 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．Beijing：ISPRS，2008：637－642．

［4］ LI Jingzhong．An Object－oriented Model for Map Data Multiple Representation over Scale Space［D］．Wuhan：Wuhan University，2009．（李精忠．尺度空間地圖多重表達(dá)的面向?qū)ο髷?shù)據(jù)模型研究［D］．武漢：武漢大學(xué)，2009．）

［5］ WOLBERG G．Image Morphing：A Survey［J］．The Visual Computer，1998，14（8－9）：360－372．

［6］ GUIBAS L，HERSHBERGER J，SURI S．Morphing Simple Polygons［J］．Discrete and Computational Geometry，2000，21（1）：1－34．

［7］ BEREG S．An Approximate Morphing between Polylines［J］．International Journal of Computational Geometry and Applications，2005，15（2）：193－208．

［8］ EFRAT A，HAR－PELED S，GUIBAS L J，et al．Morphing between Polylines［C］∥Proceedings of the 12th Annual ACM－SIAM Symposium on Discrete Algorithms．Philadelphia：Society for Industrial and Applied Mathematics，2001：680－689．

［9］ CECCONI A．Integration of Cartographic Generalization and Multi－scale Databases for Enhanced Web Mapping［D］．Zurich：University of Zurich，2003．

［10］ 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．

［11］ DANCIGER J，DEVADOSS S L，MUGNO J，et al．Shape Deformation in Continuous Map Generalization［J］．Geoinformatica，2009，13（2）：203－221．

［12］ REILLY D F，INKPEN K M．Map Morphing：Making Sense of Incongruent Maps［C］∥Proceedings of Graphics Interface．Waterloo：Canadian Human－computer Communications Society，2004，231－238．

［13］ PANTAZIS D，KARATHANASIS B，KASSOLI M，et al．Are the Morphing Techniques Useful for Cartographic Generalization？［C］∥Proceedings of Urban and Regional Data Management．London：CRC Press，2009：195－204．

［14］ PANTAZIS D，KARATHANASIS B，KASSOLI M，et al．Morphing Techniques：Towards New Methods for Raster Based Cartographic Generalization［C］∥Proceedings of the 24th ICC International Cartography Conference．Santiago：ICC，2009：15－21．

［15］ VAN KREVELD M．Smooth Generalization for Continuous Zooming［C］∥Proceedings of the 20th International Cartographic Conference．Beijing：ICC，2001：2180－2185．

［16］ ALBRECHT S．A Solution to the Vertex Correspondence Problem in 2D Polygon Morphing［D］．Osnabruck：Universitat Osnabruck，2006．

［17］ 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：［s．n．］，1999：175－184．

［18］ AI Tinghua，GUO Renzhong，LIU Yaolin．A Binary Tree Representation of Curve Hierarchical Structure in Depth［J］．Acta Geodaetica et Cartographica Sinica，2001，30（4）：343－348．（艾廷華，郭仁忠，劉耀林．曲線彎曲深度層次結(jié)構(gòu)的二叉樹表達(dá) ［J］．測繪學(xué)報，2001，30（4）：343－348．）

［19］ PLAZANET C，AFFHOLDER J G，F(xiàn)RITSCH E．The Importance of Geometric Modeling in Linear Feature Generalization［J］．Cartography and Geographic Information Systems，1995，22（4）：291－305．

［20］ ZHAI Renjian，WU Fang，Zhu Li，et al．Structured Representation of Curve Shape［J］．Acta Geodaetica et Cartographica Sinica，2009，38（2）：175－182．（翟仁健，武芳，朱麗，等．曲線形態(tài)的結(jié)構(gòu)化表達(dá)［J］．測繪學(xué)報，2009，38（2）：175－182．）

［21］ POORTEN P，JONES C B．Customisable Line Generalization Using Delaunay Triangulation［C］∥Proceedings of the 19th International Cartographic Association Conference．Ottawa：Canadian Institute of Geomatics．1999：35－42．

［22］ ZHANG M，SHI W，MENG L．A Generic Matching Algorithm for Line Networks of Different Resolutions［C］∥Proceedings of the 8th ICA Workshop on Generalization and Multiple Representation．La Coru?a：ICA，2005：7－8．

（責(zé)任編輯：叢樹平）

Morphing Transformation of Linear Features by Using Independent Bend Structures More Sufficiently

PENG Dongliang，DENG Min，LIU Huimin
School of Geosciences and Info－physics，Central South University，Changsha 410083，China

This paper proposes a morphing approach for linear features by using their independent bend structures more sufficiently．Firstly，the constrained Delaunay triangulations（CDT）of the pair of linear features are respectively constructed．Bend structures are identified and represented by bend forests．Secondly，corresponding bends are obtained by bend matching．To use independent bend structures more sufficiently，the CDT of every pair of the obtained corresponding bends are constructed．Then the new pairs of bend forests on the back－side of these corresponding bends are built．Again，bend matching is implemented on the new pairs of bend forests and new corresponding bends are obtained．This process is iteratively carried out until no more corresponding bends can be found．Thirdly，the starts and ends of all the pairs of corresponding bends are used to split the two original linear features so that corresponding segments are obtained．The linear interpolation algorithm is utilized to detect corresponding points for every pair of the corresponding segments．Lastly，straight－line trajectories are used for morphing．The experimental results show that the proposed approaches can improve the ability of identifying corresponding characteristic points and preserving characteristic points in the process of morphing．

Morphing；shape interpolation；bends；linear features；cartographic generalization

PENG Dongliang（1987—），male，PhD candidate，majors in cartographic generalization and multi－scale representation．

DENG Ming

P208

A

1001－1595（2014）06－0637－08

國家自然科學(xué)基金（41171351；41301515）；教育部新世紀(jì)優(yōu)秀人才支持計劃（NECT－10－0831）；湖南省國土資源廳科技項目（2010－20）；湖南省研究生科研創(chuàng)新項目（CX2012B039）

2013－01－15

彭東亮（1987—），男，博士生，研究方向為地圖綜合和多尺度表達(dá)的理論與方法。

鄧敏

PENG Dongliang，DENG Min，LIU Huimin．Morphing Transformation of Linear Features by Using Independent Bend Structures More Sufficiently［J］．Acta Geodaetica et Cartographica Sinica，2014，43（6）：637－644，652．（彭東亮，鄧敏，劉慧敏．更充分利用獨立彎曲結(jié)構(gòu)的線狀要素Morphing變換方法［J］．測繪學(xué)報，2014，43（6）：：637－644，652．）

10．13485／j．cnki．11－2089．2014．0100

修回日期：2013－08－13

E－mail：pengdlzn＠163．com

E－mail：dengmin028＠yahoo．com