裴洪星

(信息工程大學，河南 鄭州 450001)

層次特征點控制的線狀要素Morphing方法

裴洪星

(信息工程大學，河南 鄭州 450001)

針對多尺度表達中同名線要素的變換問題，提出一種層次特征點控制下的線狀要素Morphing變換方法，在已有的線性插值Morphing變換基礎(chǔ)上，利用層次特征點對線要素進行分段控制，按對應弧段的結(jié)點的相對位置在本弧段的相同的相對位置處插入點，提高插值過程中點的位置對應精度，使中間比例尺的插值表達得到優(yōu)化，提高Morphing變換的精度。

線狀要素；Morphing；插值；層次特征點

Morphing又稱圖形漸變技術(shù)，最早應用于計算機圖形處理領(lǐng)域，其基本思想是采用某種內(nèi)插方法使得初始圖形連續(xù)、平滑地漸變到目標圖形，具體實施涉及兩個基本過程，即圖形特征匹配和形狀插值[1]。近年來，由于電子地圖多尺度表達的發(fā)展，要求變換過程中地圖要素能夠連續(xù)、平滑地顯示，這與Morphing的目標相一致，由此促進了Morphing技術(shù)在地圖制圖領(lǐng)域的應用與發(fā)展，目前Morphing技術(shù)在地圖制圖領(lǐng)域主要應用于道路、河流以及居民地邊界等線狀要素的形狀內(nèi)插，以生成所需尺度的線狀要素形態(tài)[2-4]。

傳統(tǒng)的基于綜合方法的尺度變換模式是在某一比例尺數(shù)據(jù)下對線要素進行化簡，實現(xiàn)尺度變化過程中的要素形態(tài)變化。要素在進行化簡時，往往采用的是傳統(tǒng)的經(jīng)典算法，如Douglas-Peucker算法[5]、Li-Openshaw算法[6]，其缺點在于缺少要素變換方向的控制，容易產(chǎn)生幾何、拓撲不一致，無法做到控制數(shù)據(jù)向另一端的數(shù)據(jù)漸進變換[7]。借鑒Morphing思想，通過某一尺度變換區(qū)間兩端的同名要素控制變換的方向，實現(xiàn)不同比例尺同名道路的連續(xù)、平滑變換，在多尺度表達中更加合理。基于矢量數(shù)據(jù)的Morphing變換可分為兩個步驟：首先，對不同尺度上兩對應要素建立對應點；然后，以一定的移位路徑進行形狀內(nèi)插。一般情況下由于Morphing變換幅度較小，不易產(chǎn)生拓撲問題，因此可以用對應點之間的直線段作為移位路徑[8]?？梢钥闯?，在移位路徑確定的前提下，對應點的精度決定了Morphing變換結(jié)果的精度。對于線狀要素的Morphing變換，李精忠利用模擬退火的思想建立線要素之間點的最優(yōu)匹配，實現(xiàn)了真實數(shù)據(jù)的Morphing漸變效果[9]；鄧敏、彭東亮對線狀要素的彎曲結(jié)構(gòu)進行提取，通過對線要素整體結(jié)構(gòu)分析建立彎曲對應關(guān)系實現(xiàn)Morphing變換[10-11]，提高了匹配精度。雖然都實現(xiàn)了線狀要素Morphing變換，且在一定程度上提高了精度，但是算法本身存在設(shè)計較復雜、耗時長、對要素的結(jié)構(gòu)相似性要求較高，不利于快速生成所需尺度的表達。為此，本文提出層次特征點控制下的線狀要素Morphing變換方法。

1 基本原理

對于不同比例尺的同名線狀要素，設(shè)其大比例尺表達為A，小比例尺表達為B，它們分別是不同函數(shù)的連續(xù)表達，設(shè)A的函數(shù)表達為f(x)(0≤x≤1),f(0)和f(1)分別對應A的起點和終點，B的函數(shù)表達為h(x)(0≤x≤1),h(0)和h(1)分別對應A的起點和終點。本文研究的目標就是利用Morphing思想在不同比例尺的同名曲線A和B之間進行一系列中間比例尺處的形狀插值，實現(xiàn)兩者之間連續(xù)、平滑的變換。設(shè)中間插值生成的連續(xù)表達為M，其函數(shù)表達為g(x),它的定義域為[0,1]，g(0)和g(1)分別對應M的起點和終點。A和B可以通過對應點之間的連線作為移位路徑，插值生成中間比例尺的表達M。設(shè)t為要素A對中間插值表達的影響因子(0≤t≤1)，

(1)

式中：S0和S1分別為大、小比例尺數(shù)據(jù)的分母，S是中間插值表達的比例尺分母。則中間某一具體比例尺處插值的函數(shù)表達為[3]

(2)

式中:f(u)與h(u)分別為A和B上相對應的點，g(t,u)為二者之間對應點生成的中間比例尺表達。其中代表中間插值受兩端比例尺影響的程度。t=0時，M的內(nèi)插表達為A；t=0時，M的內(nèi)插表達為B。

特征點控制線狀要素的基本形態(tài)，同一線狀要素，在不同比例尺下其細節(jié)層次存在一定的差異，但其整體的形態(tài)往往是高度一致的，因此，通過提取控制要素整體結(jié)構(gòu)的特征點對不同比例尺的同名要素進行分段約束，使線要素整體對應變?yōu)榫€要素之間的弧段之間的對應，從而提高了對應精度，使形狀插值更加精確，提高Morphing精度。

2 層次特征點控制的Morphing變換

本文提出一種方法，利用Douglas-Peucker算法思想對線要素逐層提取特征點，建立層次特征點的二叉樹結(jié)構(gòu)，使線要素被不同層次特征點的逐級分割，將同名線要素整體的對應關(guān)系轉(zhuǎn)換為線要素之間弧段的一一對應關(guān)系，從而提高整體的對應精度，在對應的弧段對之間進行插值，實現(xiàn)任意中間比例尺要素的生成。

2.1 提取層次特征點

Douglas-Peucker算法是一種經(jīng)典的線狀要素化簡方法[3]，其實質(zhì)是根據(jù)線狀要素上具有較大意義的一系列特征點提取其主要形態(tài)。借鑒其思想，本文利用Douglas-Peucker算法的循環(huán)迭代提取曲線上控制其整體基本形態(tài)的特征點。提取特征點的過程如下：

1)設(shè)定閾值d，利用道格拉斯-普克法提取距離曲線首末點連線的距離最大點，記錄其ID號，將其作為二叉樹根結(jié)點，以該點為界將曲線劃分為左右子曲線。

2)對左右子曲線計算各自范圍內(nèi)的距離首末結(jié)點連線最大的結(jié)點，并分別存儲在二叉樹的下一層左右子結(jié)點中，并記錄他們各自的ID號，若某一子曲線中不存在大于閾值的點，則記錄為空，存儲在相應的二叉樹子結(jié)點處。

3)循環(huán)進行，直到二叉樹的最后一層葉子結(jié)點全部為空，循環(huán)停止。加入首末結(jié)點至此提取出所有特征點。

提取的特征點組織上構(gòu)成了一棵完全二叉樹，同名線要素對應特征點處在二叉樹中的相同位置。提取出的結(jié)點具有層次性，對線要素形成逐級劃分，使同名線要素被分為不同弧段并逐級對應。理論上，提取的特征點越多，對曲線進行的分段控制效果就越好，Morphing的精度就越高，但是當閾值過小時，線要素的小彎曲會對特征點的提取造成干擾，從而提取到小彎曲上的點作為錯誤的特征點，破壞同名線要素特征點二叉樹結(jié)點的對應性。因此，需要設(shè)定合理的閾值，盡可能提取到多的特征點，同時使同名線要素之間的特征點準確對應，如圖1所示。

2.2 結(jié)點相對位置插值

提取特征點的目的是通過特征點對曲線進行分段，使不同比例尺的同一曲線能夠分段對應，再進行插值，從而提高插值的精度。上一節(jié)中，利用道格拉斯-普克法的思想提取了不同比例尺同一線狀要素的特征點并將特征點分層存儲在二叉樹的結(jié)點中，小比例尺下線狀要素的表達是從大比例尺下的表達經(jīng)過頂點抽稀、彎曲刪除、彎曲夸大等操作得到的，小比例尺下提取的特征點能在大比例尺中找到對應點，反之則未必[5]。因此，本文根據(jù)小比例尺二叉樹中的特征點，在大比例尺特征點二叉樹中的相同位置尋找對應點，從而建立不同比例尺同名曲線之間特征點的對應關(guān)系。曲線的特征點將曲線劃分不同層級為若干弧段，根據(jù)特征點的層次建立曲線間弧段的對應關(guān)系。由特征點劃分得到的弧段稱為控制弧段。

建立控制弧段之間的對應關(guān)系后，在對應控制弧段對上分別進行點的插值，以完成控制弧段內(nèi)結(jié)點的對應關(guān)系。為了便于說明確定插值的位置，定義如下：

定義1結(jié)點的位置p。結(jié)點到曲線起點的所有線段的長度之和L與曲線的長度L0的比值，p=L/L0。

插值過程如下：

1)根據(jù)提取的特征點對曲線進行劃分。對同名曲線上特征點二叉樹進行遍歷，只有兩個二叉樹同一位置特征點都存在且不為空時，才同時選擇該處的特征點作為劃分兩條同名曲線特征點。選取所有滿足條件的特征點，根據(jù)特征點在二叉樹中的層次性將曲線逐級劃分，使弧段一一對應。

2)對各控制弧段進行點插值。在特征點選取時，特征點之間嚴格的對應關(guān)系已經(jīng)確定了控制弧段的匹配關(guān)系，對分段后的曲線A和B分別求取每個弧段的長度，并計算控制弧段內(nèi)的結(jié)點的相對位置，記錄在列表中。

3)對曲線進行分段插值求同名曲線的中間比例尺表達。對曲線A上的控制弧段A1，曲線B上與其對應的控制弧段B1，訪問存儲B1上的結(jié)點相對位置的列表，讀取該弧段上各點的相對位置，然后在控制弧段A1內(nèi)的同樣的相對位置處插入點，同樣在B1上相同的位置處插入A1上的對應點。循環(huán)繼續(xù)進行，直到曲線A、B各控制弧段上都插入了對應的點，連接對應的結(jié)點，稱之為插值路徑，計算對應結(jié)點在插值路徑上的插值點。插值點的坐標(x,y)計算公式為

(3)

式中：(x,y)為新插值點的坐標，(xs,ys)為插值路徑的起點坐標，(xe,ye)為插值路徑的末結(jié)點坐標，t為式(1)中大比例尺要素對插值表達的影響因子。

對同名線要素上所有的對應點插值得到插值點集。依次連接相鄰插值路徑上的插值點，得到曲線A和B的Morphing變換曲線，最后對插值得到的曲線進行平滑處理。

3 實驗與分析

為了驗證方法的可行性，基于C#語言使用Visual Studio 2010平臺構(gòu)建實驗平臺，選取寧波市1∶25萬和1∶100萬的某兩條同名道路線狀要素進行實驗，對它們進行Morphing變換，生成它們的中間比例尺的表達。數(shù)據(jù)的初始狀態(tài)和最終狀態(tài)(即t=0和t=1時的圖形)，如圖2所示。

對實驗數(shù)據(jù)中的同名線狀道路分別提取特征點，經(jīng)過多次試驗，設(shè)定閾值d=300 m時，能夠在同名道路線要素提取比較一致的特征點。如圖3所示，根據(jù)提取到的特征點的層次性對道路整體進行逐級劃分，實驗中兩條道路分別各自提取到9個特征點，這些特征點將它們各自劃分為8條控制弧段，根據(jù)特征點的層次對應性建立控制弧段之間的一一對應關(guān)系。

圖2 實驗數(shù)據(jù)

圖3 提取特征點

以控制弧段為單位，在進行Morphing變換前對控制弧段進行點加密處理。計算并記錄控制弧段上的結(jié)點的相對位置，在控制弧段上讀取與之匹配的弧段的結(jié)點的相對位置，并在同樣的位置處插入結(jié)點。經(jīng)過點插入操作，匹配弧段上的結(jié)點數(shù)量保持一致，即從道路線要素的起點開始，在兩條同名道路之間建立了所有結(jié)點的一一對應關(guān)系。矢量道路數(shù)據(jù)是根據(jù)“結(jié)點—弧段”結(jié)構(gòu)進行組織的，實際上線要素是一系列有序的點的集合，因此，兩條同名道路線要素的Morphing中間變換時，本質(zhì)上是求中間狀態(tài)的點集。在點插入操作后，道路線要素間從起點開始所有結(jié)點依次一一對應，如圖4所示。

圖4 特征點控制下線要素結(jié)點對應

對應結(jié)點之間的連線就是結(jié)點的插值路徑。由式(3)確定對應點的中間插值表達點，最終生成所有對應點的同一尺度的表達，將插值得到的點集轉(zhuǎn)換為線要素，得到同名道路線要素的中間尺度表達，據(jù)此得到的Morphing變換曲線局部起伏較大，需要對其進行平滑處理，從而得到更好的視覺效果，經(jīng)過逐步插值得到了不同比例尺下的中間表達，從而實現(xiàn)了同名道路從1∶25萬到1∶100萬的平滑過渡表達。圖5、圖6分別為線性插值算法和本文算法實現(xiàn)的Morphing變換。

對兩種方法進行的Morphing變換進行對比，線性變換在插值過程中，只是在對應結(jié)點之間進行插值，得到中間尺度的點集，再由點集轉(zhuǎn)化為線要素，從而生成線要素中間尺度表達。其缺點在于原始線要素結(jié)點只是在順序上互相對應，位置上并沒有受到約束，因此，對應點之間在位置上存在偏差。Morphing變換過程中，插值在錯誤對應的位置之間進行，導致中間表達出現(xiàn)偏差，由圖5(b)可以觀察到線性插值后同名線要素同一拐點并沒有成為對應點，而是出現(xiàn)了一定的位置偏差；本文方法則是在提取控制點的前提下，由控制點的對應關(guān)系約束相鄰控制點之間的弧段對應關(guān)系，能控制Morphing變換過程的關(guān)鍵位置的偏差，圖6與圖5對比可以看出本文方法結(jié)點位置的對應精度更高，相比于線性插值方法， 其Morphing準確度更高。

圖5 線性插值Morphing變換

圖6 層次特征點控制下Morphing變換

4 結(jié) 論

本文方法利用計算機圖形處理領(lǐng)域的Morphing漸變思想，對不同比例尺的線狀要素進行插值變換，實現(xiàn)同名線要素間的平滑變換，對已有的線性插值方法進行了改進，在其原有的基礎(chǔ)上提高了插值的精度，提高了Morphing變換的準確性，使其表達更合理。本方法還存在一定缺陷，需要提高匹配的控制弧段內(nèi)的結(jié)點的位置對應的精度，可以考慮在控制弧段內(nèi)的再次提取次特征點，提高弧段的對應精度，從而提高插值精度，進一步優(yōu)化Morphing變換的表達。

[1] 李華,朱光喜,朱耀庭,等.物體漸變技術(shù)現(xiàn)狀與發(fā)展[J].中國圖象圖形學報,2002,7(8): 745-751.

[2] 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.

[3] 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.

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

[5] DOUGLAS D H,PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. The Canadian Cartographer, 1973, 10(2): 112-122.

[6] LI Zhilin, Openshaw S.基于客觀綜合自然規(guī)律的線狀要素自動綜合的算法[J].武測譯文,1994(1):49-58.

[7] 李精忠.尺度空間地圖多重表達的面向?qū)ο髷?shù)據(jù)模型研究[D]. 武漢:武漢大學,2009:67-72.

[8] 馬江林,趙忠明,孟瑜,等.海量遙感分類圖連通域標記力法[J].計算機工程,2008,34(1): 262-264.

[9] 李精忠,吳晨琛,楊澤龍.一種利用模擬退火思想的線狀要素Morphing方法[J].武漢大學學報(自然科學版),2014,39(12):1446-1451.

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

[11] 彭東亮,鄧敏,劉慧敏. 更充分利用獨立彎曲結(jié)構(gòu)的線狀要素Morphine變換方法[J].測繪學報,2014,43(6),638-646.

[責任編輯：劉文霞]

A Morphing method based on hierarchical feature points for linear features

PEI Hongxing

(Information Engineering University, Zhengzhou 450001, China)

A new Morphing method for two linear features is proposed based on the feature points of the linear features to solve the problem of transformation between linear features of the same in multi-scale representation. To improve the position precision of points each other, hierarchical feature points are extracted so that linear features will be split into several parts. And every part can be matched with one of another linear features. Then new points will be added in one of the pairs the same relative position as others of the other one. Compared with the linear interpolation, the precision of Morphing of this method is improved, thus realizing a more reasonable representation between two linear features of two different scales.

linear features; Morphing; interpolation; hierarchical feature points

引用著錄：裴洪星.層次特征點控制的線狀要素Morphing方法[J].測繪工程，2017，26(4)：53-57.

10.19349/j.cnki.issn1006-7949.2017.04.010

2016-04-15；

2016-05-15

裴洪星(1991-)，男，碩士.

P208

A

1006-7949(2017)04-0053-05