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

康二梅, 毛凱楠

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

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

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

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

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

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

Rs=F(S1,S2,T)

(1)

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

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

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

圖1 DTW算法

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

(2)

該優化問題可采用的動態規劃算法進行求解,公式為

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

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

(3)

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

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

2 試驗分析

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

圖2 模擬數據在不同比例尺下的疊置效果及其匹配關系

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

圖3 基于DTW算法的模擬數據Morphing漸變效果

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

圖4 基于DTW算法的河流數據Morphing漸變

圖5 基于DTW算法的等高線數據Morphing漸變

3 結 語

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