李精忠,毛凱楠

1. 蘭州交通大學(xué)測繪與地理信息學(xué)院,甘肅 蘭州 730070; 2. 武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院,湖北 武漢 430079; 3. 自然資源部城市國土資源監(jiān)測與仿真重點(diǎn)實(shí)驗(yàn)室,廣東 深圳 518000

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

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

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

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

1 典型時(shí)間規(guī)整原理

CTW算法計(jì)算得到的距離被稱為典型規(guī)整距離[28],該算法結(jié)合了典型相關(guān)分析(canonical correlation analysis,CCA)和動(dòng)態(tài)時(shí)間規(guī)整(dynamic time warping,DTW)算法[27],主要應(yīng)用于步態(tài)序列識別和多個(gè)序列的時(shí)間對齊[29-30]。其中,DTW算法用于時(shí)間序列對齊,CCA算法實(shí)現(xiàn)多維序列進(jìn)行特征提取和降維[31]。

(1)

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

γ(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距離,也就是當(dāng)前單元格和相鄰元素的最小累計(jì)距離。

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

(3)

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

圖1 DTW算法實(shí)現(xiàn)序列對齊Fig.1 Sequence alignment based on DTW algorithm

(4)

(5)

(6)

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

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

(7)

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

(8)

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

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

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

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

3 試驗(yàn)分析

3.1 試數(shù)據(jù)

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

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

圖4 試驗(yàn)數(shù)據(jù)Fig.4 The experimental data

3.2 試驗(yàn)方法

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

表2 基于CTW和FFT算法的形狀相似性度量結(jié)果統(tǒng)計(jì)

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

3.3 試驗(yàn)分析

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

表3 CTW方法被錯(cuò)誤識別的建筑物形狀和部分復(fù)雜建筑物形狀的相似性度量結(jié)果

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

表4 復(fù)雜建筑物形狀經(jīng)Douglas-Peucker算法化簡后的相似性度量結(jié)果

3.4 應(yīng) 用

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

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

4 結(jié) 論

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