層次特征點(diǎn)控制的線狀要素Morphing方法

裴洪星

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

層次特征點(diǎn)控制的線狀要素Morphing方法

裴洪星

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

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

線狀要素；Morphing；插值；層次特征點(diǎn)

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

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

1 基本原理

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

(1)

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

(2)

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

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

2 層次特征點(diǎn)控制的Morphing變換

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

2.1 提取層次特征點(diǎn)

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

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

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

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

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

2.2 結(jié)點(diǎn)相對(duì)位置插值

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

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

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

插值過(guò)程如下：

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

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

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

(3)

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

對(duì)同名線要素上所有的對(duì)應(yīng)點(diǎn)插值得到插值點(diǎn)集。依次連接相鄰插值路徑上的插值點(diǎn)，得到曲線A和B的Morphing變換曲線，最后對(duì)插值得到的曲線進(jìn)行平滑處理。

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

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

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

圖2 實(shí)驗(yàn)數(shù)據(jù)

圖3 提取特征點(diǎn)

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

圖4 特征點(diǎn)控制下線要素結(jié)點(diǎn)對(duì)應(yīng)

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

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

圖5 線性插值Morphing變換

圖6 層次特征點(diǎn)控制下Morphing變換

4 結(jié) 論

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

[1] 李華,朱光喜,朱耀庭,等.物體漸變技術(shù)現(xiàn)狀與發(fā)展[J].中國(guó)圖象圖形學(xué)報(bào),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ī)律的線狀要素自動(dòng)綜合的算法[J].武測(cè)譯文,1994(1):49-58.

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

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

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

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

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

[責(zé)任編輯：劉文霞]

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

引用著錄：裴洪星.層次特征點(diǎn)控制的線狀要素Morphing方法[J].測(cè)繪工程，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