典型時間規整算法支持下的建筑物形狀相似性度量

李精忠,毛凱楠

1. 蘭州交通大學測繪與地理信息學院,甘肅 蘭州 730070; 2. 武漢大學資源與環境科學學院,湖北 武漢 430079; 3. 自然資源部城市國土資源監測與仿真重點實驗室,廣東 深圳 518000

建筑物要素是基礎地理信息的重要組成部分,其形狀相似性度量對建筑物空間模式識別、分類、查詢和制圖綜合具有重要意義[1-6]。矢量幾何圖形相似性度量涉及兩個關鍵問題:即幾何形狀的定量描述方法及形狀之間差異性(或相似性)的度量模型[7]。

幾何圖形的定量描述方法可以分成基于圖形區域、基于圖形結構特征和基于圖形輪廓特征3種類別[8]?；趫D形區域的方法以圖形的整體指標來反映圖形結構,通常使用定量的形狀參數符(如面積、延展度等)來表征形狀的整體結構。典型的方法有網格描述符[9]和基于矩的形狀描述方法[10],前者將網格用于描述形狀特征的區域統計信息,適用于基于內容的圖像表達;后者使用低階矩構造出由7個不變量所構成的不變矩組,適用于矢量多邊形的區域統計信息表達。此類方法主要基于圖形區域的整體特征,側重于反映形狀的全局結構,會導致形狀輪廓細節信息的丟失?；趫D形結構特征的方法通常以圖形的骨架特征作為形狀的結構化表達,該方法主要應用于非剛性變化的形狀相似性度量[11]。文獻[12]通過比較骨架端點之間的測地線距離來匹配骨架圖。文獻[13]使用不連續骨架的形狀相似性度量方法解決傳統骨架連接中的不穩定問題。然而,由于尺度變化,地圖要素的形狀骨架特征并不唯一,該方法主要適用于度量圖像數據集(如動物形狀)和非剛性變換形狀之間的相似性?；趫D形輪廓特征的方法,其基本思想是將形狀節點轉換為幾何表達式,以字符串或者函數的形式來近似擬合形狀邊界。常用方法有傅里葉描述子、鏈碼法、轉角函數法、形狀上下文、輪廓點分布直方圖等。其中,傅里葉描述子通過將空間域的坐標轉換為頻域的頻率來實現形狀的定量描述[14];鏈碼法是一種基于邊界的編碼描述法,該方法通過形狀起始點的坐標和邊界點方向代碼來描述圖形[15];轉角函數法將多邊形形狀轉換為函數,在函數空間中分析結構并計算相似性[16];形狀上下文以兩個圖形輪廓采樣點之間的相互關系(如距離、梯度)作為形狀匹配策略[17];輪廓點分布直方圖在極坐標下對目標形狀的輪廓特征點進行描述[18]。此類方法強調鄰近節點之間的相互關系,幾何輪廓的局部噪聲會影響形狀的定量表達。綜上,傳統的幾何形狀定量描述方法存在以下不足:基于圖形區域的方法以統計特征描述整體信息,容易忽略局部細節;基于圖形結構特征的方法,其結構信息提取算法往往復雜度高且提取結果不唯一;基于圖形輪廓的方法需要構建復雜的圖形編碼序列或者形狀輪廓描述符,且多數方法并不具備圖形的旋轉、平移和縮放不變性,不能直接用于形狀相似性度量。

在多邊形形態特征的定量描述基礎上,形狀之間的差異通常用形狀相似性或相異性(距離)表示,形狀相似性越大,則形狀之間的距離越短,兩個形狀越相似[19]。建筑物的形狀相似性度量方法往往基于圖形的幾何特征,主要包括簡單幾何特征法、編碼法、形狀描述符法等。簡單幾何特征法主要選擇單個或多個指標,例如距離相似度(歐氏距離、Hausdorff距離[20]等)、方向相似度[21](余弦法、方向關系矩陣[22]等)、幾何相似度[23](面積比、周長比、面輪廓線相似性[24]等),或者使用加權平均法進行綜合相似性度量。編碼法主要是對比計算編碼相似度或構建相似度描述函數[15],其計算量相對較小,但對復雜圖形的識別準確率不高。形狀描述法則通過形狀描述子之間的差異來度量形狀相似性。例如,傅里葉描述函數將圖形的輪廓特征以傅里葉函數表示,通過計算不同階次系數之間的差異(歐氏距離)來測量形狀相似性距離[25]。轉角函數表示了形狀邊界上切角對弧長之間的關系,形狀間的相似性以切角的差異來衡量[26]。在以上方法中,幾何特征法對于相似性指標的選取和權重的確定具有較大的主觀性,編碼法難以識別復雜的幾何圖形,而基于形狀描述符的方法需進行復雜的傅里葉或轉角函數變換,其計算性能較低,且存在傅里葉展開級數和轉角起始點難以確定的問題。

針對目前幾何圖形定量描述方法和形狀之間差異性度量模型存在的問題,本文提出了一種基于典型時間規整(canonical time warping,CTW)算法的建筑物形狀相似性度量方法,該方法具有以下特點:①以建筑物矢量坐標序列作為形狀的定量描述方法,可以直接根據矢量坐標序列進行形狀相似性的計算,無須將問題拆分為幾何形狀的定量描述和相似性度量兩個過程。因為直接利用矢量坐標序列,故可同時兼顧幾何圖形的整體特征與局部特征。②在相似性度量中,該方法可以對齊具有不同節點個數的建筑物形狀,對于多尺度地圖數據中建筑物圖形的旋轉、平移和縮放等操作不敏感,具有旋轉、平移和縮放不變性,穩健性較強[27]。③該方法基于降維思想,將二維矢量坐標序列降維至一維序列,以降維后一維序列間的距離作為建筑物形狀之間的相似性距離,整個算法不需要人為控制相似性指標權重或閾值,可操作性強。

1 典型時間規整原理

CTW算法計算得到的距離被稱為典型規整距離[28],該算法結合了典型相關分析(canonical correlation analysis,CCA)和動態時間規整(dynamic time warping,DTW)算法[27],主要應用于步態序列識別和多個序列的時間對齊[29-30]。其中,DTW算法用于時間序列對齊,CCA算法實現多維序列進行特征提取和降維[31]。

(1)

式中,彎曲路徑P需要同時滿足以下3個條件:①端點對齊。路徑P從第一個點對開始,在最后一個點對結束,即p1=(1,1),pK=(m,n);②連續性。路徑上的任意兩個相鄰點pk=(a,b)與pk-1=(a′,b′)滿足0≤|a-a′|≤1,0≤|b-b′|≤1;③單調性。若pk=(a,b)與pk-1=(a′,b′)為路徑上前后兩個點,則需滿足a-a′≥0,b-b′≥0。K為滿足上述條件后對齊兩個時間序列所需的索引數。符合上述條件的彎曲路徑可能有多條,其中最短的彎曲路徑可以通過動態規劃算法求得,公式如下

γ(i,j)=d(qi,cj)+min{γ(i-1,j-1),
γ(i-1,j),γ(i,j-1)}

(2)

式中,γ(i,j)表示序列Q[1:i]與序列C[1:j]之間的DTW距離,也就是當前單元格和相鄰元素的最小累計距離。

為了方便在DTW算法中添加特征選擇機制從而實現DTW算法與CCA算法的結合,式(1)中的代價函數可以修改為如下形式

(3)

式中,Wq∈{0,1}K×m和Wc∈{0,1}K×n分別為對齊時間序列Q和C的規整矩陣,對齊后序列Q和C的長度一致。K為式(1)中對齊兩個序列所需的索引數。

圖1 DTW算法實現序列對齊Fig.1 Sequence alignment based on DTW algorithm

(4)

(5)

(6)

2 基于CTW算法的建筑物形狀相似性度量

地圖中建筑物矢量多邊形輪廓由一系列首尾相連的有序坐標點組成,這種有序坐標點串的表達方式與時間序列的表達方式相似。對于兩個建筑物多邊形形狀相似性的比較,可以提取二者的輪廓坐標,將其歸一化到相同的參考體系,然后計算二者坐標點位之間的累積距離差值。顯然,差值越小則形狀越相似,差值越大則形狀差異性越大。在概念上,這一思想與時間序列相似性度量方法CTW的原理契合。地圖中不同的建筑物多邊形具有不同的位置、方向和大小,且多邊形之間的節點數目也各不相同。CTW算法具有平移、旋轉和縮放不變性,且能對點數各異的矢量建筑物坐標序列進行特征提取,并計算這些序列在特征空間的相似性距離,從而能夠度量兩個多邊形形狀之間的相似性。

(7)

假設DTW算法對齊后的序列長度為K(式(1)中的索引數),經過CTW算法收斂后,建筑物A可以表示為a=[a1,a2,…,aK],建筑物B可以表示為b=[b1,b2,…,bK],序列a和b之間的歐氏距離即為建筑物A和B之間的CTW距離

(8)

然而,矢量坐標序列的不同構建順序及不同起始點的選擇會導致不同的節點匹配結果,從而產生不同的CTW距離。本文參考了文獻[26]的策略,統一以順時針方向生成矢量坐標序列,采用移動邊界起始點的方法求得所有序列之間CTW距離的最小值,作為最終的相似性計算結果。另外,建筑物形狀中常常會出現具有孔洞結構的多邊形。根據Gestalt原則,對于有孔洞的復雜多邊形來說,人們對于其形狀特征的認知以最外圍輪廓為主,其內環對于多邊形整體形狀認知的影響不大。因此,本文不考慮圖形內部的孔洞結構對形狀認知的影響,統一以圖形外圍輪廓構成的矢量坐標序列進行相似性度量。

圖3是L型建筑物(圖3(a))和經過旋轉(圖3(b))、平移(圖3(c))和放大(圖3(d))后的形狀示例圖。為了證實CTW算法的平移、旋轉和縮放不變性,本文對比了形狀a與形狀b、c、d之間的CTW距離與DTW距離。由表1可以看出,形狀a與形狀b、c、d之間DTW距離遠大于CTW距離,且CTW距離幾乎為0,說明平移、旋轉和放大后的形狀與原始形狀非常接近。這一結果符合人類的視覺空間認知,證實了使用CTW算法計算形狀相似性的可行性。

表1 圖3建筑物中原始形狀a與形狀b、c、d之間的CTW和DTW距離

圖3 L型建筑物形狀變換后Fig.3 L-shaped buildings after shape transformation

3 試驗分析

3.1 試數據

深圳是1979年成立的中國第一個經濟特區,現在是珠江三角洲的先驅城市[33]。2019年,深圳城市化率達到99.52%(http:∥tjj.sz.gov.cn/)。因此,深圳的建筑形態和分布可以被視為中國大城市的典型代表。本次試驗以深圳市1∶10 000的矢量建筑物分布圖為參考數據。深圳的建筑物主要分布在道路沿線,建筑形態特征相對規則。

本文選出了7種典型的形狀:矩形、L形、E形、十字形、C形、T形和Z形,并選取了420個類似的形狀作為試驗數據,其中每種類型分別包含60個建筑形狀。在數據采集和存儲的過程中,參考數據中可能會有一些異常節點,如冗余點和共線點[34],這些點需要在試驗前刪除。之后將這些建筑物圖形縮放、平移至同一圖幅,如圖4所示。另外,本文構建了7個基本形狀模板來方便比較形狀相似性(圖4中的紅色形狀)。

圖4 試驗數據Fig.4 The experimental data

3.2 試驗方法

試驗使用Mathematica 12.1中的Canonical Warping Distance函數來計算420個建筑物形狀與7個模板形狀之間的相似性距離(CTW距離)[28],根據與模板最短距離確定建筑物形狀識別結果。本文與快速傅里葉變換(fast Fourier transform,FFT)計算得到的建筑物形狀相似性結果進行了對比,對比結果見表2。其中,TP表示算法識別結果與人類視覺感知一致的建筑物數目,FP表示算法識別結果與人類視覺感知不一致的建筑物數目,FN表示算法識別錯誤的結果中與人類視覺感知一致的建筑物數目。CTW算法的時間復雜度為O(N3),試驗耗時約617 s(11.2 min),FFT算法的展開級數為500,時間復雜度為O(Nlog2N),試驗耗時約40 s。

表2 基于CTW和FFT算法的形狀相似性度量結果統計

由表2可知,基于CTW算法的試驗耗時較大,但是其查全率和查準率均高于98%,遠高于FFT的識別準確率(52.857%)。同時,針對不同類型的建筑物形狀,基于CTW算法的查全率和查準率均達到95%以上,且對于矩形、十字形和T型建筑物形狀而言,查全率和查準率均為100%。這是因為CTW算法的本質是基于圖形輪廓進行的形狀相似性度量,其特點是同時考慮了圖形的整體和局部特征,如果圖形輪廓存在噪聲節點,將會影響算法匹配結果,進而會降低算法的準確率。本次試驗數據中的矩形、十字形和T型建筑物形狀比較規整和對稱,影響形狀輪廓的噪聲節點數目較少,因此基于CTW算法的準確度較高。對于FFT的算法而言,該算法在識別L型和T型建筑物時的查全率和查準率均低于50%,準確率較低。這是因為FFT算法無法有效顧及建筑物形狀中多直角表達的形態特征,該算法相對更適合非多直角表達的復雜形狀之間的相似性度量,如面狀湖泊[8]。試驗結果表明,與FFT算法相比,CTW算法在建筑物形狀相似性度量上具有更好的性能。

3.3 試驗分析

針對試驗數據中出現的有孔多邊形,本文統一以圖形外圍輪廓構成的矢量坐標序列進行了相似性度量,這些形狀在本次試驗中都能得到正確的度量結果。表3展示了本次試驗數據中與人類認知結果不一致的圖形(建筑物1—6),及部分幾何復雜度較高但是被本文算法正確識別的圖形(建筑物7—10)相似度量結果。表3中的視覺認知結果表示使用CTW算法獲得的最相似形狀與人類認知結果一致。對比建筑物1、2、3、6和建筑物9,其中建筑物1、2、3和9在人類視覺認知中都屬于E型建筑物但不屬于標準的E型。由于建筑物9的整體結構較規整,相對模板形狀而言影響其形狀輪廓的噪聲節點較少,因此仍能得到正確的相似性度量結果。建筑物1、2、3和建筑物6,形狀輪廓的噪聲節點極大影響了形狀整體結構,如形成了齒輪狀(建筑物1)或圓弧狀(建筑物6)的多余結構,這會影響圖形與模板坐標序列節點的對齊,從而導致錯誤的相似性度量結果。建筑物4,該形狀具有二義性,可識別成L型或C型,這說明CTW算法可以反映一些具有二義性的建筑物形狀。對于建筑物5和建筑物7、8、10,雖然建筑物7、8、10的幾何復雜度較高,噪聲節點較多,但是這些噪聲節點分布較集中,比如建筑物10的噪聲節點只分布在L型兩個直角拐彎處,該圖形仍具有與傳統形狀類似的整體結構,因此仍能得到正確的相似性度量結果。相對而言,建筑物5噪聲節點數量多且分布分散,且該形狀與人類視覺認知中傳統的Z型建筑物相差過大,因此造成了錯誤的度量結果。

表3 CTW方法被錯誤識別的建筑物形狀和部分復雜建筑物形狀的相似性度量結果

表4為本次試驗結果與人類認知結果不一致的復雜多邊形(表3中的建筑物1—6)經Douglas-Peucker算法化簡后的相似性度量結果。結果表明,復雜多邊形經輪廓化簡后的形狀在CTW算法下均能得到正確的相似性度量結果。因此,針對數量較多且分布分散的噪聲節點,可以考慮在相似性度量前使用傳統的化簡算法進行多余節點的抽稀,從而減少圖形的噪聲節點,提升算法的準確率。建筑物形狀中的少量局部噪聲節點一般不會影響建筑物的整體結構,對CTW算法的相似性度量結果影響較小。對于表3中的所有復雜建筑物及表4中化簡后的建筑物1—5,使用FFT算法均不能得到正確的相似性度量結果,而CTW算法可以正確識別表3中的建筑物7—10及表4中的所有形狀。

表4 復雜建筑物形狀經Douglas-Peucker算法化簡后的相似性度量結果

3.4 應 用

形狀檢索是以人類認知的角度從GIS數據庫中找到與模板形狀匹配的目標圖形,建筑物形狀檢索的關鍵問題在于形狀相似性的度量。本文方法可有效應用建筑物形狀檢索。表5記錄了與每個模板形狀最相似的前6個建筑物以及它們之間的CTW距離,可以看出,這些形狀與模板形狀在視覺上都較為相似,表明CTW算法可以有效地應用于形狀檢索場景。其中,對于矩形和十字型建筑物而言,模板形狀與前6個形狀在視覺上非常相似,其形狀之間的CTW距離最小,且矩形形狀的長寬比對形狀相似性度量結果沒有太大影響;對于C型和T型建筑物而言,其模板形狀具有對稱性,而第4個C型建筑物和第5個T型建筑物并不具備,表明多邊形的矢量坐標序列對形狀的整體特征具有較好的表示能力。此外,在Z型建筑物的檢索結果中,前5個建筑物形狀均為Z型模板形狀旋轉、縮放或平移后的圖形,而第6個形狀為Z型模板的鏡像圖形,說明CTW算法不僅具有旋轉、縮放、平移不變性,還具有鏡像不變性。

表5 基于CTW算法的前6個與模板最相似建筑物形狀及相似性距離

4 結 論

在傳統的度量建筑物形狀相似性的算法中,往往需要構建復雜的圖形編碼序列或形狀輪廓描述符。本文提出了一種基于CTW算法的建筑物形狀相似性度量方法,該方法可以對齊具有不同節點個數的建筑物坐標序列,能直接根據矢量坐標序列進行形狀相似性的計算,降低了算法的復雜性,提升了方法的可操作性。其中建筑物多邊形的矢量坐標序列可以顧及圖形原始的輪廓特征。試驗證明CTW算法具有平移、旋轉、縮放和鏡像不變性,該算法計算得到的建筑物形狀相似性符合人的視覺空間認知。值得注意的是,本文算法并不能處理結構復雜和噪聲節點過多的建筑物形狀,需要結合地圖綜合算法進行處理。未來將進一步探究復雜多邊形的形狀相似性度量,提升CTW算法的適用性。