DTW算法支持下的線狀要素連續(xù)地圖綜合方法

康二梅, 毛凱楠

(1. 甘肅省基礎(chǔ)地理信息中心,甘肅 蘭州 730000; 2. 武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院,湖北 武漢 430072)

地圖綜合是通過對地圖中的點(diǎn)、線、面、注記等要素進(jìn)行選取和概括以實(shí)現(xiàn)地圖數(shù)據(jù)的抽象與尺度變換,是地圖制圖、空間數(shù)據(jù)庫建設(shè)及空間分析的理論和技術(shù)基礎(chǔ),長期以來,眾多學(xué)者對該問題進(jìn)行了研究[1]。當(dāng)今,隨著Web2.0技術(shù)的發(fā)展,人們不再滿足于有限比例尺的傳統(tǒng)地圖服務(wù)模式,任意比例尺地圖數(shù)據(jù)的動態(tài)生成技術(shù)成為研究的熱點(diǎn),因此出現(xiàn)連續(xù)地圖綜合技術(shù)[2],即通過拓展地圖綜合理論與方法實(shí)現(xiàn)對地圖數(shù)據(jù)的連續(xù)尺度變換,動態(tài)派生任意比例尺的地圖數(shù)據(jù)。

連續(xù)地圖綜合方法大致可分為兩類,一類是對傳統(tǒng)地圖綜合方法的改進(jìn),增加其尺度敏感性,使得算法輸出數(shù)據(jù)變化粒度更加精細(xì),從而實(shí)現(xiàn)連續(xù)地圖綜合[3-4];另一類是基于尺度融合技術(shù),通過對同一區(qū)域一大一小兩套比例尺數(shù)據(jù)的融合,動態(tài)派生任意中間尺度的數(shù)據(jù)[5]。當(dāng)前,我國已經(jīng)建立了基本比例尺系列地圖數(shù)據(jù)庫[6],可以作為基于尺度融合的連續(xù)地圖綜合方法的數(shù)據(jù)基礎(chǔ)。

與專題覆蓋圖斑類地圖不同[7-10],在普通地圖中,河流、道路、管網(wǎng)和等高線等線狀地圖要素占據(jù)了很大的比例,本文聚焦于線狀要素的連續(xù)地圖綜合,提出一種基于DTW算法的線狀要素連續(xù)地圖綜合新方法。

1 DTW算法支持下的線狀要素連續(xù)地圖綜合模型

基于尺度融合概念的連續(xù)地圖綜合模型可表達(dá)為[11-12]

Rs=F(S1,S2,T)

(1)

式中,S1和S2分別為同一地理實(shí)體在大小比例尺中的兩種幾何表達(dá);F為尺度融合函數(shù);T為與比例尺有關(guān)的歸一化參數(shù),用于控制融合結(jié)果隨比例尺的不同而逐漸變化。對任意0≤T≤1,Rs關(guān)于T是單調(diào)、連續(xù)的,當(dāng)T=0時,Rs=S1;當(dāng)T=1時,Rs=S2;當(dāng)0

上述連續(xù)地圖模型的實(shí)現(xiàn),涉及2個基本過程。一是幾何表達(dá)S1和S2之間頂點(diǎn)對應(yīng)關(guān)系的建立;二是插值路徑的選擇[13-14],因任何中間表達(dá)狀態(tài)Rs與S1和S2都屬于同一地理實(shí)體,故插值路徑選用簡單的線性插值[15]。對于同名實(shí)體不同比例尺的幾何表達(dá),S1和S2往往具有不同數(shù)目的坐標(biāo)點(diǎn)數(shù),其坐標(biāo)點(diǎn)的集合具有不同基數(shù)。在不同基數(shù)的兩個集合之間建立映射關(guān)系,必然存在非一對一映射關(guān)系,對于空間數(shù)據(jù)而言,表現(xiàn)為S1和S2的頂點(diǎn)之間存在一對多的對應(yīng)關(guān)系。顯然,這種映射關(guān)系可以有多種,如何建立兩者之間的最優(yōu)匹配,是連續(xù)地圖綜合模型實(shí)施的關(guān)鍵。

本文采用動態(tài)時間歸整(dynamic time warping, DTW)方法對S1和S2的頂點(diǎn)集合進(jìn)行最優(yōu)匹配。DTW是時間序列匹配的經(jīng)典方法[15],它通過對兩個序列進(jìn)行自適應(yīng)空間扭曲和動態(tài)時間規(guī)整找出兩序列間最優(yōu)匹配,實(shí)現(xiàn)兩個序列之間的精準(zhǔn)時空對齊。對于地圖目標(biāo)S1和S2,其矢量坐標(biāo)序列分別表示為集合Q和C。其中,集合Q的基數(shù)為n,Q={q1,q2,…,qi,…,qn};集合C的基數(shù)為m,C={c1,c2,…,cj,…,cm}。Q和C中每個分量qi和cj具有相同的維度,對于二維地圖數(shù)據(jù),該分量是一個由縱橫坐標(biāo)組成的二維向量。為了對齊Q和C中的頂點(diǎn)序列,如圖1(a)所示,DTW首先構(gòu)造一個n×m的矩陣網(wǎng)格,矩陣元素(i,j)表示點(diǎn)qi和cj對齊,其數(shù)值為qi與cj兩坐標(biāo)點(diǎn)之間的距離,記為d(qi,cj),可使用歐式距離,d(qi,cj)=(qi-cj)2。該距離反映了序列Q和C的每個點(diǎn)之間的相似度,距離越小則相似度越高。建立Q和C之間頂點(diǎn)對應(yīng)關(guān)系的過程,表現(xiàn)為構(gòu)造一條從方格點(diǎn)(1,1)到方格點(diǎn)(n,m)的幾何路徑W(W=w1,w2,…,wk)(wK(max(m,n)≤K≤(m+n-1)),其中K為對齊兩個坐標(biāo)序列所需的索引數(shù)。如圖1(b)所示,該路徑確定了待匹配序列Q與C上每個點(diǎn)之間的對應(yīng)關(guān)系,該路徑允許一對多對應(yīng),圖中w4和w5分別表示Q中第4點(diǎn)同時對應(yīng)于C中第4和第5兩個點(diǎn)。

圖1 DTW算法

幾何路徑W的生成需滿足3個約束條件:①邊界約束,W從第一個點(diǎn)對開始,在最后一個點(diǎn)對結(jié)束,即w1=(1,1),wK=(m,n);②連續(xù)性,路徑上的任意兩個相鄰點(diǎn)wk=(a,b)與wk-1=(a′,b′)滿足0≤|a-a′|≤1,0≤|b-b′|≤1;該約束要求路徑不能跳過某些頂點(diǎn)進(jìn)行匹配,當(dāng)前點(diǎn)只能與自己相鄰的點(diǎn)對齊,以保證Q和C中每個坐標(biāo)均在路徑中出現(xiàn);③單調(diào)性約束,若wk=(a,b)與wk-1=(a′,b′)為路徑上前后兩個點(diǎn),則需滿足a-a′≥0,b-b′≥0。因n不一定等于m,這種匹配關(guān)系有多種可能性,每種匹配關(guān)系均可用一條彎曲路徑表示,最短彎曲路徑的長度即為序列Q與C之間的DTW距離,其對應(yīng)的匹配即為Q和C的頂點(diǎn)之間的最優(yōu)匹配。滿足最短路徑匹配的DTW距離可表示為

(2)

該優(yōu)化問題可采用的動態(tài)規(guī)劃算法進(jìn)行求解,公式為

γ(i,j)=d(xi,yj)+min[γ(i-1,j-1),

γ(i-1,j),γ(i,j-1)]

(3)

式中,γ(i,j)表示當(dāng)前單元格中的距離和相鄰元素的最小累計距離。

線狀地圖要素在尺度變換過程中常采用的地圖綜合算子為彎曲的取舍、夸大,連續(xù)彎曲的典型化,以及節(jié)點(diǎn)的抽稀。其中,節(jié)點(diǎn)抽稀的結(jié)果也表現(xiàn)為細(xì)小彎曲的舍棄。

2 試驗(yàn)分析

本文將驗(yàn)證基于DTW的頂點(diǎn)匹配算法在曲線彎曲舍棄和連續(xù)彎曲典型化2種基本場景下的匹配效果。為了驗(yàn)證本文方法的可行性和有效性,分別采用模擬和實(shí)際數(shù)據(jù)進(jìn)行試驗(yàn)。圖2(a)為模擬數(shù)據(jù)在大比例尺S1和小比例尺S2下疊置顯示的效果,分別記為曲線a和曲線b,該數(shù)據(jù)反映了多尺度環(huán)境下線狀要素尺度變換的基本特征,圖2(a)中虛線橢圓A和D所在區(qū)域的曲線b,由a經(jīng)彎曲刪除產(chǎn)生,橢圓B所在區(qū)域的曲線b由a經(jīng)頂點(diǎn)抽稀產(chǎn)生,橢圓C所在區(qū)域由彎曲典型化產(chǎn)生。模擬數(shù)據(jù)在大比例尺S1中由72個頂點(diǎn)組成,記為a={a1,a2,…,a72},在小比例尺S2中由57個頂點(diǎn)組成,記為b={b1,b2,…,b57}。圖2(b)為基于DTW算法在不同尺度下線狀要素的頂點(diǎn)匹配關(guān)系。其中,b1對應(yīng)于a1、a2和a3,因此在b1的位置將會插入2個與b1相同的點(diǎn),記為b1-1、b1-2,分別對應(yīng)于a2和a3。然后針對頂點(diǎn)匹配結(jié)果進(jìn)行線性插值。

圖2 模擬數(shù)據(jù)在不同比例尺下的疊置效果及其匹配關(guān)系

圖3為模擬數(shù)據(jù)基于DTW算法的Morphing漸變效果。T=0和T=1分別為線狀要素在大比例尺S1的表達(dá)a和小比例尺S2的表達(dá)b,T=0.1～0.9為不同程度的形狀內(nèi)插結(jié)果,T與中間比例尺Rs的關(guān)系為Rs=(1-T)S1+T·S2?？梢钥闯?隨著T的不斷增大,中間比例尺Rs的曲線形態(tài)越來越逼近小比例尺S2,曲線彎曲特征的化簡、舍棄及典型化操作實(shí)現(xiàn)了從左到右的光滑過渡,該結(jié)果符合空間數(shù)據(jù)的漸變特征,說明本文方法適用于Morphing漸變。

圖3 基于DTW算法的模擬數(shù)據(jù)Morphing漸變效果

圖4和圖5分別為某區(qū)域1∶10 000和1∶50 000的真實(shí)河流及等高線數(shù)據(jù)在采用本文DTW算法后的形狀內(nèi)插結(jié)果,河流及等高線的數(shù)據(jù)來源于OpenStreetMap。其中,圖4(a)與圖5(a)為1∶10 000的原始形狀,相應(yīng)的T值為0;圖4(f)與圖5(f)為1∶50 000的目標(biāo)形狀,相應(yīng)的T值為1;圖4與圖5中的(b)到(e)分別對應(yīng)1∶18 000、1∶26 000、1∶34 000及1∶42 000的形狀表達(dá),對應(yīng)的T值分別為0、0.2、0.4、0.6、0.8和1。可以看出,對于河流而言,Morphing的漸變結(jié)果保留了線狀地物的連接性與網(wǎng)狀結(jié)構(gòu);對于等高線而言,其結(jié)果保留了圖形中山谷和山脊的形態(tài)特征且沒有出現(xiàn)拓?fù)溴e誤。因此本文方法可以較好地保持線狀地物的幾何形態(tài)及拓?fù)浣Y(jié)構(gòu),并實(shí)現(xiàn)線狀要素彎曲形態(tài)由復(fù)雜到簡單光滑的過渡。

圖4 基于DTW算法的河流數(shù)據(jù)Morphing漸變

圖5 基于DTW算法的等高線數(shù)據(jù)Morphing漸變

3 結(jié) 語

本文提出了一種基于DTW算法的地圖線狀要素連續(xù)綜合方法。該方法基于尺度融合的思想,以同一地理實(shí)體在大小比例尺下兩種不同的幾何表達(dá)作為輸入,首先基于DTW算法建立兩種幾何表達(dá)坐標(biāo)頂點(diǎn)之間的對應(yīng)關(guān)系,然后采用線性內(nèi)插方法動態(tài)派生任意中間尺度上幾何數(shù)據(jù),從而實(shí)現(xiàn)連續(xù)地圖綜合。插值的難點(diǎn)在于建立不同比例尺下同名地理實(shí)體坐標(biāo)頂點(diǎn)之間的非一一對應(yīng)關(guān)系,為建立最優(yōu)匹配關(guān)系,本文方法以頂點(diǎn)距離為匹配代價,以整體最小距離為目標(biāo)函數(shù),采用DTW算法求解最優(yōu)匹配。試驗(yàn)結(jié)果表明,基于DTW的頂點(diǎn)匹配方法可適應(yīng)不同的河網(wǎng)、等高線等典型地圖綜合場景,該方法支持下的地圖綜合效果可實(shí)現(xiàn)連續(xù)、光滑漸變,符合地圖表達(dá)規(guī)則和人類空間認(rèn)知。不足之處為對于比例尺跨度較大的情況,可能存在實(shí)體的消亡(即刪除),此類情形無法建立同名實(shí)體之間的對應(yīng)關(guān)系,因此無法進(jìn)行形狀內(nèi)插。后期將進(jìn)一步研究此類情形的解決方法。