一種形狀多級描述方法及在多尺度空間數(shù)據(jù)幾何相似性度量中的應(yīng)用

安曉亞，孫 群，肖 強(qiáng)，嚴(yán)薇，2

1.信息工程大學(xué)測繪學(xué)院，河南鄭州450052；2.61512部隊(duì)，北京100088

1 引 言

空間數(shù)據(jù)幾何相似性度量模型被廣泛應(yīng)用于地理信息科學(xué)的眾多領(lǐng)域，根據(jù)應(yīng)用，將其分為兩類：第一類用于度量不同目標(biāo)之間的幾何相似性，主要應(yīng)用于空間數(shù)據(jù)匹配［1－6］，其實(shí)質(zhì)是從指定數(shù)據(jù)集中找到一個與待匹配對象在空間位置、方向、大小、長度和形狀上最相似的目標(biāo)，最終識別不同數(shù)據(jù)集上的同名實(shí)體［4］；第二類主要應(yīng)用于同一目標(biāo)在數(shù)據(jù)處理前后變形程度的度量［7－8］。上述應(yīng)用中，多尺度幾何形狀相似性度量難度最大，其關(guān)鍵是形狀描述子對形狀的整體和局部特征都要能刻畫，即滿足緊致性，如第一類模型要求描述子盡量對形狀的整體特征進(jìn)行描述，而第二類模型要求描述子必須顧及尺度的變化，對局部細(xì)節(jié)特征更要考慮。目前有代表性的形狀描述方法及其特點(diǎn)是：簡單描述子對復(fù)雜形狀的描述明顯不足，中心距離對角度函數(shù)僅能刻畫全局特征，單一的傅里葉描述對噪聲敏感，小波描述嚴(yán)重依賴于形狀起始點(diǎn)，形狀上下文描述僅能刻畫局部特征［7－11］。文獻(xiàn)［1—6］基于第一類模型進(jìn)行數(shù)據(jù)匹配，但很難達(dá)到相似度量結(jié)果不受尺度變化影響，文獻(xiàn)［4］提出以中心距離對弧長的函數(shù)來描述幾何形狀，在同比例尺數(shù)據(jù)匹配中效果較好。

對此，提出一種具備對形狀多級描述能力的新方法，既能以較詳細(xì)的程度刻畫形狀，同時通過調(diào)節(jié)相關(guān)參數(shù)也能以較概略的程度刻畫形狀，可以達(dá)到通用于兩類模型的目標(biāo)。基于該方法，建立通用多尺度相似性度量模型，并將它們分別應(yīng)用于多尺度數(shù)據(jù)匹配和圖形化簡前后的相似性度量中。

2 形狀的多級描述方法

將形狀輪廓表示為一組有序點(diǎn)集：A＝｛Pi＝（xi，yi）｜i＝1，2，…，N｝（圖1（a）），O為幾何中心，從Pi出發(fā)，沿逆時針將A按弧長等分為K個弧段，K為偶數(shù)，Gt（t＝1，2，…，K－1）是對應(yīng)等分點(diǎn)。連接Pi與Gt，得到K－1條弦｛PiG1，PiG2，…，PiGK－1｝，lt（Pi）表示Pi對應(yīng)第t條弦PiGt的弦長。s（Pi）表示O到Pi的中心距離。當(dāng)Pi在輪廓線上改變時，每一個Pi對應(yīng)一個lt（Pi）和s（Pi），故lt（Pi）和s（Pi）是Pi的函數(shù)。設(shè)P0為起始點(diǎn)，則Pi可表示為弧的長度ci。以ci為自變量，lt（Pi）和s（Pi）可表示為ci的函數(shù)Lt（ci）和S（ci）。至此，A可由自變量弧長ci、因變量弦長Lt（ci）和S（ci）來描述。對于線目標(biāo)（圖1（b）），如果lAB／cAB≥0.5，尋找一點(diǎn)O，使△OAB為等邊三角形，然后以O(shè)為幾何中心，計(jì)算s（Pi），在計(jì)算lt（Pi）時，將△OAB看作面目標(biāo)，然后依據(jù)圖1（a）的方法計(jì)算；如果lAB／cAB＜0.5，直接連接首末點(diǎn)A、B，將其轉(zhuǎn)化為面目標(biāo)按圖1（a）的方法計(jì)算lt（Pi）和s（Pi）。

圖1 多級弦長Fig.1 Multilevel chord length

一個ci對應(yīng)弦長函數(shù)L1（ci），L2（ci），…，LK－1（ci）有K－1個，其中，ci∈［0，C］，C為輪廓線周長。將有序集合F（ci）＝｛L1（ci），L2（ci），…，LK－1（ci）｝稱之為ci對應(yīng)的多級弦長函數(shù)，Lt（ci）表示ci對應(yīng)的第t級弦長函數(shù)。當(dāng)t＝K／2時，LK／2（ci）是輪廓線1／2弧長對應(yīng)的弦長，當(dāng)t大于K／2時，無法將輪廓線整數(shù)等分，因此，將F（ci）壓縮一半為F（ci）＝｛L1（ci），L2（ci），…，LK／2（ci）｝，只包含K／2級弦長函數(shù)。

上述描述方法滿足旋轉(zhuǎn)和平移不變性，用C對ci進(jìn)行歸一，然后以S（ci）和Lt（ci）的均值對它們進(jìn)行歸一化后可滿足縮放不變性。

3 相似性度量模型建立及應(yīng)用

3.1 利用多級描述方法度量形狀相似性

多級弦長函數(shù)描述形狀滿足緊致性。以圖2為例，計(jì)算兩圖當(dāng)K＝8時的4級弦長函數(shù)，并繪制曲線進(jìn)行對比，圖3為1～4級弦長曲線。計(jì)算當(dāng)橫坐標(biāo)取同一數(shù)值（從0開始到1，間隔為0.05）時每幅圖對應(yīng)兩曲線縱坐標(biāo)的差值，求這些差值序列對應(yīng)的標(biāo)準(zhǔn)差s，分別為0.16、0.11、0.08和0.05，標(biāo)準(zhǔn)差越大，說明兩形狀越不相似，反之則否。經(jīng)第一級弦長函數(shù)描述的兩形狀最不相似，說明對細(xì)節(jié)信息能很好地刻畫，第2、3級弦長函數(shù)的相似性逐漸增大，到第4級弦長函數(shù)，兩曲線已非常接近，說明對整體形狀相似性能有效地描述。因此，可以利用多級描述方法來度量不同尺度空間數(shù)據(jù)的形狀整體或者局部相似性。

圖2 整體相似而細(xì)節(jié)有較大差異的兩個形狀Fig.2 Two shapes have whole similarity and local difference

圖3 圖2中兩形狀的4級弦長曲線Fig.3 4levels chord length curve for Fig.2

之所以可以采用上述方法利用標(biāo)準(zhǔn)差直接度量兩形狀的相似性，是因?yàn)閮尚螤畹钠鹗键c(diǎn)位置基本一致，且采樣相同的輪廓線點(diǎn)數(shù)20。但在實(shí)際應(yīng)用中，兩形狀起始點(diǎn)位置不一定一致，且輪廓線點(diǎn)數(shù)也不相等，導(dǎo)致每一級弦長函數(shù)的個數(shù)不一致，無法進(jìn)行比較。為此，通過以下方法來改進(jìn)：

（1）對輪廓線以等弧長間隔進(jìn)行重采樣N′個點(diǎn)c0，c1，…，cN′－1近似表達(dá)原始輪廓線，其中，N′＝2n，n是滿足2n＞N的最小整數(shù)，然后計(jì)算Lt（ci）。

（2）對每一個Lt（ci）進(jìn)行快速傅里葉變換，其形式為

以｜zt（m）｜描述第t級弦長函數(shù)，｜zt（0）｜＝1，取N′個系數(shù)中的前M 個，構(gòu)造向量μt＝［｜zt（1）｜｜zt（2）｜…｜zt（M）｜］代替第t級弦長函數(shù)描述形狀，得到有序集μ＝［μ1μ2…μK／2］Τ。以相同方法對S（ci）進(jìn)行傅里葉變換，得到系數(shù)向量s＝［｜S（1）｜｜S（2）｜…｜S（M）｜］，于是通過μ和s描述整個形狀。因此，即使兩輪廓線上的點(diǎn)數(shù)不一致，但因?yàn)閷λ邢议L和中心距離進(jìn)行傅里葉變換，在度量相似性時，兩個形狀都取變換系數(shù)中的前M個進(jìn)行比較，故可以解決點(diǎn)數(shù)不一致的問題，同時，μ和s獨(dú)立于輪廓線的起始點(diǎn)（證明略）。

至此，得到滿足旋轉(zhuǎn)、平移、縮放不變性，且滿足緊致性和獨(dú)立于輪廓線起始點(diǎn)的形狀描述子μ和s。故可以用μ和s度量兩個形狀之間的形狀相似度：設(shè)形狀A(yù)和形狀B的μ、s分別為μA＝和A和B之間的形狀差異度定義為

｜sA－sB｜、｜μAi－μBi｜均指向量之間的歐氏距離，權(quán)系數(shù)w1、w2之和為1，μ、s均做了歸一化處理，故d（A，B）shape∈［0，1］，則形狀相似度sim（A，B）shape＝1－d（A，B）shape，且sim（A，B）shape∈［0，1］。因?yàn)橹行木嚯x函數(shù)可以刻畫整體形狀特征［8］，故當(dāng)K值較小時，ds和dμ均可度量兩形狀的整體差異性，當(dāng)K值較大時，dμ可度量細(xì)節(jié)差異性。

3.2 面向兩類應(yīng)用的幾何相似度量模型建立

無論是第一類還是第二類模型，都要度量兩目標(biāo)對應(yīng)形狀的幾何相似性。因此，可以將這兩類模型統(tǒng)一于一個模型，僅在應(yīng)用的過程中調(diào)節(jié)相關(guān)參數(shù)即可。設(shè)待度量的兩目標(biāo)為A和B，度量其幾何相似性的總體思路與文獻(xiàn)［4］基本一致，都是從兩目標(biāo)空間位置的鄰近程度、形狀、方向和大?。ɑ蜷L度）相似性程度綜合考慮并加權(quán)求和，但文獻(xiàn)［4］未考慮方向相似程度，且本文提出計(jì)算空間位置鄰近程度及形狀相似性程度均與文獻(xiàn)［4］不同。設(shè)［a1a2a3a4］Τ、［b1b2b3b4］Τ分別為描述A和B的向量，各分量代表位置、方向、大?。ɑ蜷L度）和形狀分量。d（A，B）表示A和B的差異度，sim（A，B）表示A和B的相似度，則A、B的幾何相似性可通過下式來計(jì)算

采用加權(quán)的Minkowski距離來度量d（A，B），則式（3）轉(zhuǎn)化為

式中，p值取2；ωj為權(quán)系數(shù)，且bj｜（j＝1，2，3，4）是經(jīng)過歸一化后的值，其含義是A和B中第j個分量的差異度，故｜aj－bj｜∈［0，1］，d（A，B）∈［0，1］，sim（A，B）∈［0，1］。

對空間位置的鄰近程度度量，文獻(xiàn)［4］提出的方法僅能度量面目標(biāo)，不能度量線目標(biāo)。對此，利用Hausdorff距離來度量線目標(biāo)或面目標(biāo)之間的鄰近距離。但傳統(tǒng)Hausdorff距離易受目標(biāo)局部變形程度影響，為此，基于高斯概率統(tǒng)計(jì)模型改進(jìn)Hausdorff距離。基本思路是：先計(jì)算A上的每個點(diǎn)與B上所有點(diǎn)的最小距離集合Df（A，B）；然后計(jì)算B上的每個點(diǎn)與A上所有點(diǎn)的最小距離集合Db（B，A），最后根據(jù)拉依達(dá)3σ準(zhǔn)則，剔除局部變形較大點(diǎn)，具體步驟為：

（1）計(jì)算Df（A，B）和Db（B，A）及其均值和均方差

（2）對Df（A，B）中的任意元素dft，t＝1，2，…，m，m為A上的點(diǎn)數(shù)，如果它滿足不等式

則認(rèn)為此元素為A的內(nèi)點(diǎn)，放入D′f（A，B）中，否則舍棄；對Db（B，A）存在類似操作，形成D′b（B，A）。

（3）令dfmax＝max｛D′f（A，B）｝，dbmax＝max｛D′b（B，A）｝，則A和B的Hausdorff距離為

設(shè)Hkmax（A，B）為A和B點(diǎn)集中兩點(diǎn)最大距離，則第一個分量｜a1－b1｜＝Hk（A，B）／Hkmax（A，B）是經(jīng)過歸一化處理后的Hausdorff距離值。

空間目標(biāo)的方向以MABR（minimum area bounding rectangle）的長軸方向角代替，故第二個分量方向差異度為｜a2－b2｜＝｜θA－θB｜／π，θA、θB分別為A、B的方向角；第三個分量面積或周長差異度為｜a3－b3｜＝｜SA－SB｜／max（SA，SB），SA、SB分別為A、B的面積或周長；第四個分量形狀差異分量采用3.1節(jié)式（2）的計(jì)算方法計(jì)算，即｜a4－b4｜＝dshape（A，B）。將上述四個分量帶入式（4）即可得到目標(biāo)A、B的總的幾何相似度。

利用上述幾何相似度量模型進(jìn)行空間目標(biāo)匹配的基本步驟是：設(shè)A為待匹配的目標(biāo)，利用式（4）逐一度量A與指定數(shù)據(jù)集D中的所有目標(biāo)的幾何相似度，然后從D中找到一個與A最相似的目標(biāo)C，且當(dāng)sim（A，C）的值大于給定的閾值sim0時，認(rèn)為A與C匹配，否則不匹配。為提高匹配效率，可以縮小D的范圍，方法是在A的最小外接矩形的橫向和縱向加一個兩數(shù)據(jù)集幾何位置偏移最大Hausdorff距離maxDist，然后形成擴(kuò)展的最小外接矩形EMBR（enlarge minimum bounding rectangle），處于EMBR內(nèi)的目標(biāo)集合構(gòu)成集合D。

利用幾何相似度量模型度量同一目標(biāo)在化簡前后變形程度的基本思路是：設(shè)A為原始目標(biāo)，以不同的化簡閾值對A進(jìn)行化簡后得到的新目標(biāo)序列為B1，B2，…，Bn，然后利用式（4）分別計(jì)算sim（A，Bi）（i＝1，2，..，n）的值，進(jìn)而探尋不同化簡算法對形狀保持程度的規(guī)律。

3.3 相關(guān)參數(shù)及閾值的確定

匹配過程中的相關(guān)參數(shù)及閾值的確定：

（1）M和K的確定。因傅里葉變換的高頻易受噪聲影響，故M不能太高，根據(jù)文獻(xiàn)［9］，M暫取為10，根據(jù)經(jīng)驗(yàn)，K值暫取為8。后文還會對M，K的取值進(jìn)行討論。

（2）其余參數(shù)的確定。引入相關(guān)反饋技術(shù)來確定匹配過程中的各種閾值［12］，匹配前，先選取一定數(shù)量的正例樣本（已經(jīng)確定匹配的目標(biāo)），分別計(jì)算ds、dμ、｜aj－bj｜（j＝1，2，3，4）的值，并求上述每個分量的標(biāo)準(zhǔn)差，取倒數(shù)并歸一化，分別得到式（2）和式（4）中的權(quán)值w1、w2和ωj（j＝1，2，3，4），最后根據(jù)式（4）計(jì)算每對正例樣本的相似值，并計(jì)算其均值標(biāo)準(zhǔn)差σ，則

圖形化簡前后相似度計(jì)算過程中相關(guān)參數(shù)及閾值的確定：M的值與匹配過程一致，由于對形狀的細(xì)節(jié)特征更要顧及，因此K值要更大。ωj、w1和w2的取值可根據(jù)對目標(biāo)變形的關(guān)注程度調(diào)整。

4 實(shí)例及分析

4.1 多尺度幾何匹配試驗(yàn)

匹配對應(yīng)兩種數(shù)據(jù)源分別為：現(xiàn)勢性截止于2005年的4幅1∶25萬數(shù)據(jù)，現(xiàn)勢性截止于2009年的1幅1∶50萬數(shù)據(jù)。經(jīng)坐標(biāo)系統(tǒng)一后將兩種數(shù)據(jù)源疊加在一起，以1∶50萬水域要素匹配1∶25萬水域要素。

4.1.1 面狀水庫及島嶼的匹配

經(jīng)統(tǒng)計(jì)，1∶25萬數(shù)據(jù)中共有面狀水庫102個，島嶼78個，1∶50萬數(shù)據(jù)中共有面狀水庫67個，島嶼49個。匹配的基本過程是：

（1）選取10對正例樣本，就可計(jì)算出ds、dμ、｜aj－bj｜，如表1所示。

表1 樣本相似特征分量及總相似值Tab.1 The swatch similarity characteristic components and general similarity value

得到ds和dμ對應(yīng)標(biāo)準(zhǔn)差分別為0.017 5和0.069 1，則w1和w2的值分別為0.797 7和0.202 3。得到｜aj－bj｜（j＝1，2，3，4）的標(biāo)準(zhǔn)差分別為0.024 8、0.013 1、0.071 5、0.022 9，則ωj的值分別為0.231 4、0.437 3、0.080 2、0.251 0。得到sim的標(biāo)準(zhǔn)差為0.022 7，均值為0.950 4，則sim0的值為0.882 3。

（2）將上述閾值代入式（4），然后根據(jù)3.2節(jié)匹配面狀水庫和島嶼。記n1為匹配結(jié)果集中所有實(shí)體對的數(shù)目；r為n1中正確的匹配數(shù)目；n2為兩種數(shù)據(jù)源中同名實(shí)體的對數(shù)。定義查準(zhǔn)率P＝r／n1，查全率R＝r／n2。本例中，水庫漏匹配8個，故n1＝67－8＋49＝108，在n1中沒有誤匹配，故r＝108，查看相似值小于sim0的實(shí)體集，發(fā)現(xiàn)漏匹配的8個水庫中，有3個在1∶25萬數(shù)據(jù)中為常年湖，另外3個是因?yàn)樾螤畈町愄螅▓D4（c）），2個是因?yàn)樵?∶25萬數(shù)據(jù)沒有相應(yīng)的實(shí)體。故n2＝67－3＋49＝111，則P＝100%，R＝97.4%。圖4是從結(jié)果集中選取的島嶼匹配的正例1個（圖4（a）），水庫匹配的正例1個（圖4（b）），水庫漏匹配的負(fù)例1個（圖4（c）），實(shí)線包圍區(qū)域?yàn)?∶50萬數(shù)據(jù)，陰影部分為1∶25萬數(shù)據(jù)。

圖4 面目標(biāo)的匹配Fig.4 Area matching

A1對應(yīng)搜索對象集合包括B1和B2；A2對應(yīng)搜索對象集合也包括B1和B2；A3僅包括B3；A4僅包括B4。表2是圖4的匹配結(jié)果。

表2 圖4的匹配結(jié)果Tab.2 The results of Fig.4

4.1.2 線狀河流的匹配

選取10對已匹配樣本，得到w1和w2的值分別為0.660 2和0.339 8。ωj的值分別為0.302 5、0.219 4、0.191 0、0.287 1，sim0的值為0.882 4。圖5是兩種數(shù)據(jù)疊加在一起的顯示效果，實(shí)線為1∶50萬數(shù)據(jù)，虛線為1∶25萬數(shù)據(jù)，圖的左邊部分是局部放大圖。先根據(jù)河流代碼將1∶25萬數(shù)據(jù)進(jìn)行合并，合并的方法是先進(jìn)行節(jié)點(diǎn)匹配，然后逐段合并1∶25萬數(shù)據(jù)中河流代碼相同的目標(biāo)，例如，B3是由P1P2和P2P3段合并而成。經(jīng)統(tǒng)計(jì)，該區(qū)域共有1∶50萬河流58條，其匹配結(jié)果為：55條正確匹配，2條漏匹配，1條是因?yàn)?∶25萬數(shù)據(jù)無此目標(biāo)，故P＝100%，R＝96.5%。從圖5中選取一個正例（左上圖）和負(fù)例（左下圖），A1對應(yīng)搜索對象集合包括：B1、B2、B3和B4，A2僅包括B5，表3是具體的匹配結(jié)果。

圖5 線目標(biāo)的匹配Fig.5 Line matching

表3 圖5的匹配結(jié)果Tab.3 The results of Fig.5

4.1.3 算法比較

比較本文與文獻(xiàn)［2］所提出的利用緩沖區(qū)增長方法而不用幾何相似性度量方法在匹配的查準(zhǔn)率、查全率和效率上的不同，同時與文獻(xiàn)［4］所提出的形狀相似度量方法進(jìn)行比較。所利用的數(shù)據(jù)與前文所述一致，分別比較線目標(biāo)和面目標(biāo)匹配結(jié)果，具體結(jié)果如表4所示。通過分析，文獻(xiàn)［2］與本文相比，查準(zhǔn)率一樣，即沒有錯誤匹配出現(xiàn)，但查全率降低，即出現(xiàn)漏匹配。漏匹配的原因是當(dāng)兩線目標(biāo)空間位置相鄰較遠(yuǎn)時，文獻(xiàn)［2］提出的方法不能匹配這兩目標(biāo)，而利用本文方法，即使兩線目標(biāo)距離較遠(yuǎn)，只要總體形狀具有很大的相似性，仍然可以匹配。從匹配速度上看，文獻(xiàn)［2］的方法較低，因?yàn)橐獦?gòu)建線目標(biāo)緩沖區(qū)，所以耗時較長；文獻(xiàn)［4］與本文相比，查準(zhǔn)率仍然一樣，查全率也降低，原因是文獻(xiàn)［4］提出的形狀相似度量方法適用于同比例尺目標(biāo)的匹配，當(dāng)度量不同比例尺上的同一目標(biāo)時，相似值差別會很大，因此可能導(dǎo)致漏匹配，如圖4（b）所示情況，匹配速度與本文基本相同。

表4 匹配算法的比較Tab.4 The comparison of matching algorithms

4.1.4 K和M值對匹配結(jié)果的影響分析

仍以上述數(shù)據(jù)為試驗(yàn)數(shù)據(jù)，比較當(dāng)K分別取2、4、8、16和32和M取1～20時查準(zhǔn)率P和查全率R的變化情況，如圖6所示。

圖6 K和M值對匹配性能的影響Fig.6 The matching results for different Kand M

由圖6可知，當(dāng)K＝8時，無論對面目標(biāo)或線目標(biāo)的查全率和查準(zhǔn)率，都能達(dá)到最大。當(dāng)M取 9、10、11、12時線目標(biāo)匹配查準(zhǔn)率和查全率能達(dá)到最大。

4.2 圖形化簡前后的相似性度量

以1∶25萬水域要素為原始數(shù)據(jù)，利用Douglas－Peucker（簡稱D－P）和Li－Openshaw（簡稱L－O）對目標(biāo)以不同的閾值化簡，然后利用式（4）度量化簡前后的相似值，探尋相似值隨化簡閾值的變化情況。取參數(shù)M＝10，K＝16，w1＝w2＝0.5，ωj的值為0.25，表示對化簡前后目標(biāo)在空間位置、方向、大小和形狀上變化的關(guān)注程度一致。D－P和L－O方法對應(yīng)化簡閾值d的初始值為0.05mm，步長也為0.05mm，最大值為1mm，對圖7所示實(shí)心水庫進(jìn)行化簡，分別得到20個化簡結(jié)果和相似值。圖7是化簡閾值分別為0.55mm和1mm時兩種化簡方法對應(yīng)的結(jié)果。

圖7 兩種化簡方法的對比Fig.7 The comparison of two methods of simplification

圖8（a）是總相似值sim（A，Bi）隨d而變化的曲線，圖8（b）是形狀總相似值1－｜a4－b4｜隨d而變化的曲線，根據(jù)3.1節(jié)，1－ds即為整體形狀相似值，圖8（c）是1－ds隨d而變化的曲線。當(dāng)K＝16時，本文提出的形狀多級描述方法可以度量局部相似值，1－dμ是局部形狀相似值，圖8（d）是1－dμ隨d而變化的曲線。分析圖8，可得出以下結(jié)論：

（1）當(dāng)0＜d≤0.55時，D－P和L－O對應(yīng)總相似值具有基本相同的變化規(guī)律，用最小二乘線性擬合該區(qū)間的相似值得到sim（A，Bi）D－P＝－0.088 1d＋0.997 4，sim（A，Bi）L－O＝－0.070 3d＋0.991 3；當(dāng)0.55＜d≤1時，D－P對應(yīng)總相似值sim（A，Bi）隨d而變化的變化率要明顯比L－O大，用最小二乘線性擬合該區(qū)間的相似值得到sim（A，Bi）D－P＝－0.060 8d＋0.982 0，sim（A，Bi）L－O＝－0.003d＋0.959 8。

（2）與總相似值sim（A，Bi）的變化規(guī)律類似，形狀總相似值、整體形狀相似值和局部形狀相似值在0＜d≤0.55時，D－P和L－O具有基本相同的變化規(guī)律，但當(dāng)0.55＜d≤1時，L－O對應(yīng)形狀變化比D－P更具有穩(wěn)定性。由此說明當(dāng)化簡閾值在較小范圍變化時，D－P和L－O對形狀的保持基本一致，但當(dāng)化簡閾值超出這一范圍時，D－P算法對化簡前后形狀的保持要比L－O算法差。

圖8 相似值隨化簡閾值變化的曲線Fig.8 The relationships between similarity value and simplification threshold

5 總 結(jié)

本文主要工作及創(chuàng)新點(diǎn)包括：

（1）組合多級弦長函數(shù)和中心距離函數(shù)描述空間數(shù)據(jù)幾何形狀，達(dá)到形狀描述的緊致性和唯一性，該方法的最大優(yōu)點(diǎn)是通過調(diào)節(jié)K值可以從整體到詳細(xì)逐級描述形狀，滿足多尺度相似性度量要求和兩類相似性度量模型的應(yīng)用需求；通過多級弦長和中心距離的離散傅里葉變換，解決兩形狀輪廓線點(diǎn)數(shù)不一致和起始點(diǎn)不一致的問題。

（2）基于形狀的多級描述方法建立顧及形狀、方向、長度和空間位置的第一類相似性度量模型，并將其應(yīng)用于不同比例尺空間數(shù)據(jù)的幾何匹配，在此過程中，利用高斯概率統(tǒng)計(jì)模型改進(jìn)傳統(tǒng)的Hausdorff距離，提高抗噪水平；引入信息檢索中相關(guān)反饋技術(shù)解決模型中閾值的確定問題。線目標(biāo)和面目標(biāo)的匹配試驗(yàn)表明，該模型可有效實(shí)現(xiàn)不同比例尺之間水域要素的匹配。

（3）基于第一類相似性度量模型建立了第二類相似度量模型，然后比較兩類經(jīng)典的化簡算法Douglas－Peucker算法和Li－Openshaw算法在化簡前后形狀相似值隨化簡閾值變化的規(guī)律。

［1］ DUEKHAM M，WORBOY F.An Algebraic Approach to Automated Information Fusion［J］.International Journal of Geographical Information Science，2005，19（5）：537－557.

［2］ ZHANG M，SHI W，MENG L Q.A Generic Matching Algorithm for Line Networks of Different Resolutions［C］∥Proceedings of the 8th ICA Workgroup on Generalization and Multiple Representations.LA Coruna：ICA，2005：1－8.

［3］ GOMBOSI M，ZALIK B，KRIVOGRAD S.Comparing Two Sets of Polygons［J］.International Journal of Geographical Information Science，2003，17（5）：431－443.

［4］ HAO Yanling，TANG Wenjing，ZHAO Yuxin，et al.Areal Feature Matching Algorithm Based on Spatial Similarity［J］.Acta Geodaetica et Cartographica Sinica，2008，37（4）：204－209.（郝燕玲，唐文靜，趙玉新，等.基于空間相似性的面實(shí)體匹配算法研究［J］.測繪學(xué)報(bào)，2008，37（4）：204－209.）

［5］ TONG Xiaohua，DENG Susu，SHI Wenzhong.A Probabilistic Theory－based Matching Method［J］.Acta Geodaetica et Cartographica Sinica，2007，36（2）：210－217.（童小華，鄧愫愫，史文中.基于概率的地圖實(shí)體匹配方法［J］.測繪學(xué)報(bào)，2007，36（2）：210－217.）

［6］ FU Z L，WU J H.Entity Matching in Vector Spatial Data［C］∥The International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences.Beijing：ISPRS，2008：146－147.

［7］ BIAN Lihua，YAN Haowen，LIU Jiping，et al.An Approach to the Calculation of Similarity Degree of a Polygon before and after Simplification［J］.Science of Surveying and Mapping，2008，33（6）：207－208.（邊麗華，閆浩文，劉紀(jì)平，等.多邊形化簡前后相似度計(jì)算的一種方法［J］.測繪科學(xué)，2008，33（6）：207－208.）

［8］ TANG Luliang，LI Qingquan，YANG Bisheng.Shape Similarity Measuring for Multi－resolution Transmission of Spatial Datasets over the Internet［J］.Acta Geodaetica et Cartographica Sinica，2009，38（4）：336－340.（唐爐亮，李清泉，楊必勝.空間數(shù)據(jù)網(wǎng)絡(luò)多分辨率傳輸?shù)膸缀螆D形相似性度量［J］.測繪學(xué)報(bào)，2009，38（4）：336－340.）

［9］ ZHANG D S，LU G J.Study and Evaluation of Different Fourier Methods for Image Retrieval［J］.Image and Vision Computing，2005，23（1）：33－49.

［10］ SEO C K，TAE J K.Texture Classification and Segmentation Using Wavelet Packet Frame and Gaussian Mixture Model［J］.Pattern Recognition，2007，40（4）：1207－1221.

［11］ CHEN Shi，MA Tianjun，HUANG Wanhong，et al.Gait Recognition Based on Shape Context Descriptor［J］.Pattern Recognition and Artificial Intelligence，2007，20（6）：794－799.（陳實(shí)，馬天駿，黃萬紅，等.基于形狀上下文描述子的步態(tài)識別［J］.模式識別與人工智能，2007，20（6）：794－799.）

［12］ WU Hong，LU Hanqing，MA Songde.A Survey of Relevance Feedback Techniques in Content－Based Image Retrieval［J］.Chinese Journal of Computers，2005，28（12）：1969－1979.（吳洪，盧漢清，馬頌德.基于內(nèi)容圖像檢索中相關(guān)反饋技術(shù)的回顧［J］.計(jì)算機(jī)學(xué)報(bào)，2005，28（12）：1969－1979.）