劉 坡,張 宇,龔建華

1．中國(guó)科學(xué)院遙感與數(shù)字地球研究所,北京 100101;2．浙江中科空間信息技術(shù)應(yīng)用研發(fā)中心,浙江杭州 314100;3．中南大學(xué)地球科學(xué)與信息物理學(xué)院,湖南長(zhǎng)沙 410083

中誤差和鄰近關(guān)系的多尺度面實(shí)體匹配算法研究

劉 坡1,2,張 宇1,3,龔建華1,2

1．中國(guó)科學(xué)院遙感與數(shù)字地球研究所,北京 100101;2．浙江中科空間信息技術(shù)應(yīng)用研發(fā)中心,浙江杭州 314100;3．中南大學(xué)地球科學(xué)與信息物理學(xué)院,湖南長(zhǎng)沙 410083

將中誤差引入面實(shí)體匹配的過程,結(jié)合相鄰面實(shí)體鄰近聚集算法,提出一種基于中誤差和鄰近關(guān)系的面實(shí)體匹配算法,可以解決多尺度空間數(shù)據(jù)匹配的閾值大小和多對(duì)多關(guān)系難確定的問題。試驗(yàn)結(jié)果表明該方法具有良好的穩(wěn)定性和可靠性。

多尺度;面;中誤差;鄰近關(guān)系;匹配

1 引 言

整合和更新來(lái)自不同來(lái)源、不同比例尺、不同時(shí)間段的表示同一地圖目標(biāo)的地理數(shù)據(jù)越來(lái)越引起人們的關(guān)注?？臻g面狀地物和自然要素在很多地圖表示中都占有很大的比例,可以用來(lái)表示房屋、土地利用、面狀水體和植被等,它是地圖表達(dá)和地圖使用者關(guān)心的主要內(nèi)容,本文主要討論多尺度空間面實(shí)體的匹配?？臻g面實(shí)體數(shù)據(jù)主要有空間特征和屬性特征,空間特征主要包括幾何特征和拓?fù)涮卣?幾何特征主要包括重心位置、中心位置、面積大小和邊界[1],拓?fù)涮卣髦饕娣e重疊度、屬性成分關(guān)聯(lián)度;屬性特征主要是使用實(shí)體的屬性信息。

空間面匹配,國(guó)外學(xué)者作過大量的研究。在幾何匹配方面,文獻(xiàn)[2]提出面質(zhì)心結(jié)合多種匹配檢驗(yàn)規(guī)則的幾何匹配方法,通過面實(shí)體柵格化后收縮來(lái)確定質(zhì)心,然后將其矢量化,用點(diǎn)在面內(nèi)的規(guī)則進(jìn)行粗匹配,再結(jié)合多邊形的面積A和面密度C進(jìn)行匹配檢驗(yàn),最終判斷匹配情況。文獻(xiàn)[3]通過匹配面的邊界來(lái)計(jì)算邊界的距離來(lái)檢測(cè)不同時(shí)間點(diǎn)的空間面的明顯不同,該方法適合于明確的邊界的面數(shù)據(jù),不適合于大量變化的地形數(shù)據(jù)。文獻(xiàn)[4]提出一種基于鄰近關(guān)系確定面與面大致的關(guān)系,輔助Hausdorff距離來(lái)區(qū)分面之間的匹配關(guān)系,來(lái)確定面之間的共軛點(diǎn),可以用來(lái)匹配面數(shù)據(jù)。語(yǔ)義信息主要取決于空間數(shù)據(jù)模型和屬性數(shù)據(jù)模型,語(yǔ)義信息可以用來(lái)輔助匹配關(guān)系。文獻(xiàn)[5]提出一種基于知識(shí)的非空間屬性數(shù)據(jù)匹配策略,通過計(jì)算屬性項(xiàng)的相似度值以確定匹配實(shí)體。文獻(xiàn)[8]提出一種基于語(yǔ)義和結(jié)構(gòu)的相似性的屬性數(shù)據(jù)匹配方法,來(lái)匹配正式和非正式的地理數(shù)據(jù)。

國(guó)內(nèi)學(xué)者也作了大量的工作,文獻(xiàn)[7]提出基于模糊拓?fù)潢P(guān)系分類的匹配方法,該方法計(jì)算形態(tài)距離比較麻煩,只適合于房屋等人工地物。文獻(xiàn)[8]在擴(kuò)展文獻(xiàn)[9]的概率論匹配算法的基礎(chǔ)上提出一種多準(zhǔn)則融合算法,對(duì)于面數(shù)據(jù),主要采用重心S和面的重疊度A指標(biāo),指標(biāo)的權(quán)重是由專家經(jīng)驗(yàn)來(lái)獲取的。文獻(xiàn)[10]提出基于相似性的面實(shí)體匹配方法,該方法適合于相似比例尺的地圖數(shù)據(jù)的匹配。文獻(xiàn)[11]提出了基于成分關(guān)聯(lián)區(qū)域相似度的面實(shí)體模糊匹配算法,但模糊分類比較困難,不適合多比例尺數(shù)據(jù)。文獻(xiàn)[12]也提出一種基于幾何特征的多尺度的面實(shí)體匹配方法,這也是一種基于相似性的匹配方法,需要確定各個(gè)指標(biāo)的權(quán)重。

目前的面匹配的算法還存在一些問題。首先,如何確定每個(gè)指標(biāo)的閾值或者權(quán)重。需要確定的閾值主要有:緩沖區(qū)半徑、Hausdorff距離[13]、形態(tài)距離[7]、屬性相似性[14]。指標(biāo)的閾值都與比例尺密切相關(guān)。概率匹配、相似性匹配雖然都不需要閾值,但是每個(gè)指標(biāo)的權(quán)重在不同的比例尺下是不相同的,如何確定權(quán)重也是一個(gè)難點(diǎn)。面數(shù)據(jù)由點(diǎn)組成,利用點(diǎn)的精度信息來(lái)匹配空間數(shù)據(jù),文獻(xiàn)[15]等首先使用點(diǎn)距離信息確定匹配,緩沖區(qū)大小根據(jù)地圖的點(diǎn)位精度而定。文獻(xiàn)[16—17]也利用地圖中點(diǎn)的誤差來(lái)實(shí)現(xiàn)點(diǎn)的匹配,但是點(diǎn)位誤差很難確定。其次,如何確定面的M∶N關(guān)系。目前的大多都匹配算法都是基于文獻(xiàn)[9]提出的雙向匹配策略,但是其方法只適合于點(diǎn)匹配。文獻(xiàn)[4]提出用面數(shù)據(jù)的鄰近關(guān)系,利用聚集算法可以確定面與面數(shù)據(jù)之間的多對(duì)多的關(guān)系的大致關(guān)系,再根據(jù)Hausdorff距離確定數(shù)據(jù)之間的精確關(guān)系,該距離沒有考慮多尺度情況下的匹配,需要統(tǒng)計(jì)數(shù)據(jù)才能確定范圍。最后,很難確定數(shù)據(jù)匹配不確定性的范圍,錯(cuò)誤信息的范圍對(duì)人工交互的過程有重要的影響。文獻(xiàn)[18]提出一種基于證據(jù)理論來(lái)匹配點(diǎn)目標(biāo),但是計(jì)算每個(gè)指標(biāo)的信任度仍然是一個(gè)經(jīng)驗(yàn)的過程。

根據(jù)制圖誤差理論,中誤差作為數(shù)據(jù)質(zhì)量和地圖綜合的指標(biāo),而且其大小范圍隨著比例尺的變化而變化,可以有效地應(yīng)用于多尺度空間數(shù)據(jù)的匹配,并可以確定數(shù)據(jù)不確定性的范圍。本文在文獻(xiàn)[4]提出的鄰近關(guān)系匹配的基礎(chǔ)上,提出一種基于中誤差和鄰近關(guān)系的多尺度空間面實(shí)體匹配算法,不僅可以確定準(zhǔn)確的數(shù)據(jù)范圍,同時(shí)可以確定不確定性的匹配范圍,同時(shí)考慮了不同比例尺下制圖綜合的影響,可以有效應(yīng)用于多尺度面實(shí)體匹配。

2 基于中誤差和鄰近關(guān)系的算法原理

2．1 中誤差

中誤差是衡量觀測(cè)精度的一種數(shù)字標(biāo)準(zhǔn),亦稱“標(biāo)準(zhǔn)差”或“均方根差”。它是觀測(cè)值與真值偏差的平方和與觀測(cè)次數(shù)n比值的平方根。點(diǎn)位誤差表示點(diǎn)位的觀測(cè)值與真值之差,制圖規(guī)范中的點(diǎn)位誤差用地物點(diǎn)和控制點(diǎn)的位置中誤差來(lái)衡量。點(diǎn)位誤差概率分布曲線呈正態(tài)分布或類正態(tài)分布[21]。點(diǎn)誤差的大小通過中誤差來(lái)衡量,其概率分布滿足正態(tài)分布的點(diǎn)位誤差表示99%以上的點(diǎn)都分布2倍中誤差以內(nèi),中誤差的大小隨著數(shù)據(jù)源的不同而變化,但是傳統(tǒng)的規(guī)范制圖中規(guī)定同比例尺中誤差的范圍是固定的,該范圍隨著比例尺的變大而變大,中誤差σ必須滿足－σmax≤σ≤σmax。文獻(xiàn)[19]提出相互誤差范圍(mutualerror)表示不同來(lái)源空間數(shù)據(jù)之間的誤差,假設(shè)空間數(shù)據(jù)點(diǎn)A和B,ρA、ρB分別表示A和B數(shù)據(jù)點(diǎn)位誤差的大小,則相互誤差范圍ρAB的大小為

ρAB確定了A和B中相應(yīng)的點(diǎn)的最大距離[17]。但是直接利用相互誤差范圍存在兩個(gè)問題:首先,面狀地物主要由點(diǎn)組成,組成面狀地物的點(diǎn)與點(diǎn)之間不一定存在對(duì)應(yīng)關(guān)系;其次,空間數(shù)據(jù)的點(diǎn)位誤差信息很難獲得。雖然空間數(shù)據(jù)的點(diǎn)位誤差分布是隨機(jī)的,但是,其大小必須滿足制圖規(guī)范中對(duì)誤差的要求。其范圍大小在一定的范圍內(nèi),假設(shè)A和B數(shù)據(jù)的中誤差大小的范圍為Ra、Rb,由于點(diǎn)位誤差概率分布曲線呈正態(tài)分布,則可得

大部分的多分辨率地理數(shù)據(jù)都在R1的范圍內(nèi), 99%的數(shù)據(jù)都在R2的范圍內(nèi)(由制圖規(guī)范可以知道城市地形圖中取λ＝2),不同比例尺數(shù)據(jù)的中誤差大小的范圍都可以在制圖規(guī)范中查到。如果空間數(shù)據(jù)有明確的點(diǎn)位誤差信息,也可以用ρAB作為R1的距離。

目前的基于概率、相似性的面匹配算法,雖然可以通過重疊面積的比例來(lái)確定要素的關(guān)系,但沒有考慮多比例尺下和制圖綜合的過程多數(shù)據(jù)的影響。在1∶500比例尺,要素主要判斷為1∶1關(guān)系,但是在1∶10 000情況下,考慮制圖綜合的因素,可能判斷為1∶0的對(duì)應(yīng)關(guān)系。如果僅以距離的大小或者重疊的面積判斷,會(huì)出現(xiàn)明顯的錯(cuò)誤,其閾值也很難確定。

2．2 匹配關(guān)系

面狀要素的關(guān)系主要有1∶0、1∶M(M＞1)、1∶1、M∶1(M＞1)、M∶N(M＞1,N＞1)、0∶1關(guān)系,圖3所示的面要素S對(duì)于匹配的候選要素集T,主要的匹配關(guān)系有以下4類:

(1)一對(duì)零關(guān)系。S或者T不包含任何對(duì)應(yīng)的匹配要素,對(duì)應(yīng)的匹配關(guān)系為1∶0、0∶1關(guān)系。

(2)一對(duì)一關(guān)系。S和T的對(duì)應(yīng)關(guān)系為1∶1關(guān)系。

(3)一對(duì)多關(guān)系。S和T的對(duì)應(yīng)關(guān)系為1∶M(M＞1)、M∶1(M＞1)關(guān)系。

(4)多對(duì)多關(guān)系。S和T的對(duì)應(yīng)關(guān)系M∶N(M＞1,N＞1)關(guān)系。

為了確定要素之間的關(guān)系,常用Hausdorff距離來(lái)度量這種關(guān)系。關(guān)于要素S和候選T對(duì)應(yīng)的Hausdorff距離,文獻(xiàn)[13]也提出一種擴(kuò)展的Hausdorff距離來(lái)計(jì)算面之間的關(guān)系。Hausdorff距離很難反映數(shù)據(jù)的多尺度變化。本文使用點(diǎn)位誤差密切相關(guān)的中誤差距離d來(lái)表示不同面要素之間的對(duì)應(yīng)關(guān)系,d距離表示地物相離的程度。

圖1所示的幾種典型的面狀地物的對(duì)應(yīng)關(guān)系,假設(shè)匹配的要素相互誤差的限差為δ(對(duì)應(yīng)于式(1)或式(2))。要素之間的對(duì)應(yīng)關(guān)系可以通過中誤差距離來(lái)確定,面狀要素之間的對(duì)應(yīng)關(guān)系都可以通過距離和限差的大小來(lái)確定,在圖中:

(1)如圖1(a)所示,要素S和T相離,對(duì)于S要素的對(duì)應(yīng)關(guān)系為1∶0關(guān)系,而對(duì)于T要素為0∶1關(guān)系。圖1(e)所示,要素T沒有候選要素,也為0∶1關(guān)系。

(2)如圖1(b)、1(c)所示,要素S和T相交,在圖1(b)中,如果中誤差距離d＜δ,則對(duì)于S要素,其對(duì)應(yīng)關(guān)系為1∶0關(guān)系,而對(duì)于T為0∶1關(guān)系;如果中誤差距離d＞δ,則要素的對(duì)應(yīng)關(guān)系為1∶1關(guān)系。在圖1(c)所示的關(guān)系中,明顯可以看出d＞δ,對(duì)應(yīng)的關(guān)系為1∶1關(guān)系。

(3)如圖1(d)所示,要素S包含于要素T,可以明顯可以看出要素的對(duì)應(yīng)關(guān)系為1∶1關(guān)系。

(4)如圖1(f)所示,要素S和T、T1、T2疊置,T要素包含于S,T1、T2和要素S相交,其關(guān)系主要取決于d1、d2和δ的大小關(guān)系。

如上文的分析可以知道,要素之間的對(duì)應(yīng)關(guān)系主要取決于要素之間的中誤差的距離的大小。通過比較中誤差距離和相互誤差限差δ的大小,可以確定面與面之間一對(duì)零關(guān)系、一對(duì)一關(guān)系、一對(duì)多關(guān)系。對(duì)于多對(duì)多關(guān)系,可以通過鄰近關(guān)系來(lái)確定。

圖1 面狀要素關(guān)系Fig．1 Multi-scale polygon relations

2．3 鄰近關(guān)系

對(duì)于多對(duì)多匹配關(guān)系也是一個(gè)匹配的難點(diǎn)問題,引入鄰近關(guān)系來(lái)完成面與面之間最終的匹配。M∶N匹配實(shí)際上是一個(gè)聚類問題,表示分別用M面和N面來(lái)表示同一個(gè)地物目標(biāo)。文獻(xiàn)[20]提出利用鄰近關(guān)系來(lái)合并分散的面片,文獻(xiàn)[6]在此工作的基礎(chǔ)上用面與面之間的疊置關(guān)系來(lái)確定面之間關(guān)系。前面可以通過計(jì)算中誤差距離可以初步確定要素的對(duì)應(yīng)關(guān)系,可以充分利用上一步匹配過濾之后的匹配成果來(lái)完成M∶N匹配。假設(shè)“源數(shù)據(jù)”中A有M要素(Ai,i＝1,2,…,M),目標(biāo)數(shù)據(jù)集B有對(duì)應(yīng)的N要素(Bj,j＝1, 2,…,N),構(gòu)建鏈接關(guān)系矩陣C,如果Ai和Bj有相交關(guān)系,C(i,j)的值為1,構(gòu)建如下的方程

式中,Im×m、In×n表示單位矩陣。通過對(duì)C″做D次相乘可以得到數(shù)據(jù)之間的對(duì)應(yīng)關(guān)系,D的次數(shù)由于反復(fù)自乘之后矩陣中0的個(gè)數(shù)不發(fā)生變化為止。在2．2節(jié)中,已經(jīng)將對(duì)應(yīng)的關(guān)系初步確定了,只有M∶N匹配關(guān)系了。對(duì)于原始要素S對(duì)應(yīng)的候選集合的每個(gè)要素,可以反向搜索每個(gè)候選要素的對(duì)應(yīng)的疊置的集合,判斷要素的方法如2．2節(jié)方法一致,并將該要素添加到“源要素”集中,構(gòu)建M要素集合和N要素集合,最終完成M∶N匹配。

2．4 算法流程

整個(gè)算法主要是由5個(gè)過程組成:①數(shù)據(jù)預(yù)處理,消除系統(tǒng)誤差,檢查拓?fù)潢P(guān)系和建立數(shù)據(jù)索引;②確定中誤差大小或者范圍;③初匹配,確定在范圍之內(nèi)的高信任度的幾何目標(biāo);④確定推理弱匹配的要素;⑤交互匹配或者檢索低信任度的確定的地圖要素。整個(gè)算法流程如圖2所示。

圖2 匹配流程圖Fig．2 The flow diagram of matching process

2．4．1 預(yù)處理

為了提高匹配的效率,需要對(duì)要素進(jìn)行預(yù)處理,主要包括空間校準(zhǔn)、拓?fù)錂z查、建立索引。消除系統(tǒng)的誤差,首先需要將“源數(shù)據(jù)”校準(zhǔn)到“參考數(shù)據(jù)集”中[21]。人工采集4個(gè)以上的控制點(diǎn),利用最小二乘原理將“源數(shù)據(jù)”校準(zhǔn)到參考數(shù)據(jù)集中。

2．4．2 中誤差范圍

依據(jù)GB14912-94,在1∶1000比例尺中,一般地區(qū)σmax＝0．3 m,對(duì)于1∶5000比例尺,一般地區(qū)σmax＝2．5 m;而在1∶10 000比例尺中,一般地區(qū)為σmax＝5．0 m。數(shù)據(jù)制圖中總的精度根據(jù)具體的制圖情況來(lái)確定,空間數(shù)據(jù)中誤差概率分布曲線呈正態(tài)分布,2倍中誤差為最大的誤差范圍。盡管每個(gè)地物的點(diǎn)位誤差信息都是變化的,但是其點(diǎn)位中誤差都是在一定的范圍之內(nèi)。

2．4．3 初始匹配

面狀要素的關(guān)系主要有:①一對(duì)零關(guān)系;②一對(duì)一關(guān)系;③一對(duì)多關(guān)系;④多對(duì)多關(guān)系。第一步初步確定一對(duì)一關(guān)系和一對(duì)多關(guān)系,之后再確定多對(duì)多關(guān)系。對(duì)于單個(gè)源要素S,確定其候選要素,首先對(duì)S要素做拓?fù)浣贿\(yùn)算得到候選要素集合T。主要的匹配過程為:

(1)如果候選集合的個(gè)數(shù)為0,則對(duì)應(yīng)為①或②類型,再對(duì)要素進(jìn)一步作拓?fù)浒\(yùn)算,如果拓?fù)浒囊貍€(gè)數(shù)為0,對(duì)應(yīng)為①類型,否則到步驟(2)。

(2)如果拓?fù)浒募系膫€(gè)數(shù)不為0,對(duì)S以R1為半徑做緩沖區(qū)得到要素c。對(duì)候選集的每個(gè)要素和緩沖區(qū)要素c作拓?fù)浒\(yùn)算,如果全部的要素都在c的范圍內(nèi),要素的數(shù)目為1,則對(duì)應(yīng)為②類型。否則對(duì)應(yīng)為③關(guān)系。

(3)步驟(2)中如果候選要素不全在c要素內(nèi),可能的類型為③型和④型,需要對(duì)候選要素作拓?fù)浣贿\(yùn)算。如果候選的要素有和S相交的要素,則需要反向計(jì)算該要素是否在d的范圍之內(nèi)或該要素超過一個(gè)對(duì)應(yīng)的要素,如果超過這個(gè)范圍則這種類型為④類型,否則為③類型。

(4)通過步驟(3)計(jì)算之后,最后只剩下④類型。則需要進(jìn)一步利用鄰近關(guān)系來(lái)確定數(shù)據(jù)的匹配關(guān)系。

(5)利用鄰近關(guān)系來(lái)確定多對(duì)多匹配的關(guān)系。

(6)對(duì)要匹配的要素,反向重新計(jì)算一次,找到0∶1的匹配關(guān)系和M∶1關(guān)系,計(jì)算過程和前面類似。

2．4．4 二次匹配

由式(1)—式(3)所知,R1的初始搜索范圍可以通過式(1)或者式(2)可以獲得,表示了大部分的數(shù)據(jù)的誤差范圍,如果有精確的點(diǎn)位誤差,可以用式(1)計(jì)算得到,否則通過式(2)獲得,R2表示理論上的最大誤差的范圍。由于數(shù)據(jù)要素的匹配的要素可能也在R2范圍之內(nèi),對(duì)于沒有檢索到的要素,擴(kuò)大檢索的范圍R1到R2,重復(fù)2．4．2節(jié)的過程,進(jìn)一步提高要素的檢索范圍,由于前面的匹配有著嚴(yán)格的數(shù)學(xué)依據(jù),再進(jìn)一步調(diào)整匹配的對(duì)應(yīng)關(guān)系。會(huì)改變對(duì)應(yīng)的匹配的關(guān)系,該部分?jǐn)?shù)據(jù)為低信任度的部分?jǐn)?shù)據(jù)。

2．4．5 后處理

最后,將所有檢索到的目標(biāo)數(shù)據(jù)集合,匹配方法不可能考慮到所有的情況,但是將有可能出現(xiàn)錯(cuò)誤的要素提交給用戶,由用戶來(lái)人工判斷和實(shí)地檢查,從而完成整個(gè)匹配的過程。由于第二次匹配的過程中的匹配關(guān)系與第一次匹配是有差異,并且多對(duì)多匹配的過程最容易發(fā)生錯(cuò)誤,將第二次更新的關(guān)系,提交給最終用戶來(lái)人工交互檢查。

3 試驗(yàn)分析

3．1 試驗(yàn)數(shù)據(jù)

為了驗(yàn)證本文提出方法,利用浙江海鹽地區(qū)的2012年航空影像人工采集的1∶1000、1∶5000、1∶10 000地形圖。該數(shù)據(jù)可用于城市規(guī)劃、房產(chǎn)屬性、市政建設(shè)等方面,各種要素齊全,但是屬性信息比較少,分別用A、B、C來(lái)表示。還有同一個(gè)地區(qū)2008年采集的1∶10 000比例尺的第二次土地利用調(diào)查數(shù)據(jù)(DLTB),主要包含是道路、河流和房屋、土地范圍等,房屋信息只含村鎮(zhèn)的范圍信息,但是土地利用的權(quán)屬信息十分完備。整個(gè)研究區(qū)范圍大小一共是6．6 km2的包含多要素的城市地區(qū)。研究區(qū)域如圖3所示,表示同一個(gè)區(qū)的要素,面要素類型主要有居民地和土地。

圖3 案例數(shù)據(jù)集Fig．3 Datasets for research area

試驗(yàn)主要的目的是驗(yàn)證算法對(duì)多尺度地理數(shù)據(jù)的匹配適用性,以及相同尺度的下的不同來(lái)源和數(shù)據(jù)模型的數(shù)據(jù)匹配適用情況。用1∶1000比例尺的地形圖數(shù)據(jù)匹配1∶5000、1∶10 000的地形圖數(shù)據(jù),來(lái)驗(yàn)證同一數(shù)據(jù)模型下的多尺度面實(shí)體匹配適用性;用1∶10 000地形圖數(shù)據(jù)匹配1∶10 000的土地利用調(diào)查數(shù)據(jù),來(lái)驗(yàn)證不同來(lái)源和數(shù)據(jù)模型的面實(shí)體匹配適用性。這里數(shù)據(jù)都不知道每個(gè)數(shù)據(jù)點(diǎn)位誤差準(zhǔn)確的大小,根據(jù)制圖誤差理論,1∶1000、1∶5000、1∶10 000的中誤差范圍大小為0．3 m、2．5 m、5．0 m。

表1 誤差分布范圍Tab．1 The static range of error

3．2 精度評(píng)價(jià)

3．2．1 檢索率和準(zhǔn)確率

評(píng)價(jià)算法的精度是整個(gè)匹配過程中非常重要的一步,主要用檢索率和準(zhǔn)確率評(píng)價(jià)結(jié)果,檢索率表示自動(dòng)檢索的目標(biāo)對(duì)和人工交互檢索的目標(biāo)對(duì)的數(shù)目的百分比,準(zhǔn)確率表示檢索的目標(biāo)對(duì)的正確率[9]。表2表示不同比例尺數(shù)據(jù)的匹配結(jié)果?？梢赃M(jìn)一步擴(kuò)大誤差R2的范圍,將變化的匹配關(guān)系提交給用戶,由人工進(jìn)行交互檢查,提高匹配的精度。

如表2所示,在1∶M匹配關(guān)系中,1∶1000 和1∶5000比例尺下空間數(shù)據(jù)匹配的結(jié)果為447/448,其表示算法自動(dòng)檢測(cè)出空間數(shù)據(jù)的匹配對(duì)為448對(duì),其中447對(duì)為正確,其余匹配結(jié)果表示含義類似。本文的算法主要是通過重疊度來(lái)檢索數(shù)據(jù),如果數(shù)據(jù)存在重疊都能全部檢索到,檢索率分別率都達(dá)到100%。對(duì)于多尺度空間面數(shù)據(jù)匹配也有很好的匹配準(zhǔn)確率,準(zhǔn)確率分別都達(dá)到99．5%、98．6%、98．5%。對(duì)應(yīng)的4種匹配關(guān)系中,多對(duì)多匹配的匹配精度相對(duì)低一些。

表2 試驗(yàn)結(jié)果質(zhì)量評(píng)價(jià)Tab．2 Result of the matching approach

3．2．2 算法比較

多比例尺數(shù)據(jù)匹配,文獻(xiàn)[2]提出柵格質(zhì)心和重疊面積,采用概率的方法來(lái)確定要素的對(duì)應(yīng)關(guān)系;文獻(xiàn)[8]提出的概率算法,和文獻(xiàn)[2]很相似,但是都存在指標(biāo)的權(quán)重難確定的問題。文獻(xiàn)[4]主要采用要素的擴(kuò)展Hausdorff距離來(lái)確定要素之間的對(duì)應(yīng)關(guān)系,該方法是一種統(tǒng)計(jì)的計(jì)算方法。此外文獻(xiàn)[10]提出的相似性匹配算法,該方法也存在指標(biāo)的權(quán)重問題,該方法的邊界指標(biāo)不適合于比例尺變化大的數(shù)據(jù)。本文主要是與文獻(xiàn)[4, 8,10]進(jìn)行比較。本文試驗(yàn)采用是在1∶10 000比例尺下地形圖和土地利用圖(DLTB)進(jìn)行比較。文獻(xiàn)[8]中的概率算法,取重心指標(biāo)和面積重疊度指標(biāo),假設(shè)每個(gè)指標(biāo)的權(quán)重都為1。文獻(xiàn)[10]中的相似性匹配算法,取中心指標(biāo)、邊界指標(biāo)、面積大小指標(biāo),假設(shè)每個(gè)指標(biāo)的權(quán)重都為1。文獻(xiàn)[4]的鄰近關(guān)系匹配主要采用擴(kuò)展Hausdorff距離來(lái)確定。統(tǒng)計(jì)結(jié)果見表3、表4。

表3 檢索率比較Tab．3 Recall of comparison with other matching methods

表4 準(zhǔn)確率比較Tab．4 Precision of comparison with other matching methods

從表3可以看出,概率匹配算法不需要每項(xiàng)指標(biāo)的閾值,對(duì)于空間數(shù)據(jù)有很小的疊置都識(shí)別為1∶M關(guān)系,其主要對(duì)面的匹配概率大小的比較來(lái)確定空間數(shù)據(jù)的匹配關(guān)系。對(duì)于多對(duì)多匹配關(guān)系,比較難確定,將很多的多對(duì)多匹配關(guān)系,識(shí)別為1∶M關(guān)系。相似性、Hausdorff距離和中誤差的方法的檢索率分別達(dá)到72．5%、87．6%、100%。從表4可以看出,對(duì)于不同的匹配方法,對(duì)于1∶0和0∶1匹配,各種不同的匹配方法精度都差不多,算法的效率主要取決于1∶M和M∶N匹配的精度,4個(gè)算法精度分別達(dá)到71．9%、49．7%、81．1%、 98．5%。和相似性匹配算法、Hausdorff距離和概率匹配算法比較,本文提出的基于中誤差和鄰近關(guān)系的面匹配方法有著明顯的提高。

將檢索距離擴(kuò)展到在R2范圍下,多檢索出7 對(duì)1∶0匹配的情形,同時(shí)少檢索出5對(duì)多對(duì)多匹配的情形,將之匹配為1∶M的情形,變化的關(guān)系為低信任度的關(guān)系。根據(jù)制圖誤差理論,如果對(duì)應(yīng)點(diǎn)的誤差超過R2范圍,則表示不是同一個(gè)目標(biāo)。

4 結(jié)論和討論

本文根據(jù)制圖誤差理論,利用空間數(shù)據(jù)的中誤差范圍信息和數(shù)據(jù)鄰近關(guān)系來(lái)匹配多尺度空間面實(shí)體數(shù)據(jù)。利用中誤差信息可以有效地提高初始搜索到準(zhǔn)確率,首先確定1∶0以及1∶M關(guān)系,通過建立鄰近關(guān)系矩陣來(lái)確定數(shù)據(jù)的多對(duì)多關(guān)系,并通過擴(kuò)大范圍確定相對(duì)低一些的信任度的匹配關(guān)系,接著將這些關(guān)系進(jìn)行人工交互處理,最終完成整個(gè)匹配的過程。和已有的方法比較,本算法具有良好的準(zhǔn)確度和效率,試驗(yàn)結(jié)果表明該方法具有有效性和實(shí)用性。

本算法有以下幾個(gè)方面的特點(diǎn):首先,不需要專家經(jīng)驗(yàn)或統(tǒng)計(jì)學(xué)習(xí)的方法確定每個(gè)指標(biāo)的閾值。中誤差范圍只是由匹配的目標(biāo)尺度決定,不受地圖綜合和制圖方法的影響。其次,依據(jù)制圖誤差理論,可以適用于各種來(lái)源不同比例尺的地理數(shù)據(jù)。再次,算法從高信任度的匹配數(shù)據(jù)來(lái)推理相對(duì)信任度的數(shù)據(jù),同時(shí)將低信任度交給用戶交互,進(jìn)一步提高了匹配的效率,更符合數(shù)據(jù)生產(chǎn)的過程。

最后,本文的方法適用于嚴(yán)格的制圖規(guī)范下的多尺度地理數(shù)據(jù)的匹配,不一定適用于沒有按照制圖規(guī)范制作的志愿者地理數(shù)據(jù)。志愿者地理信息作為空間數(shù)據(jù)的一個(gè)新的重要的來(lái)源,如何有效地整合志愿地理數(shù)據(jù)和傳統(tǒng)的數(shù)據(jù),是下一步研究的方向。

[1] WENTZ E A．Shape Analysis in GIS[C]∥Proceedings of Auto-Carto 13．Seattle:ACSM/ASPRS,1997:204-213．

[2] YUAN S X,TAO C．Development of Conflation Components [C]∥Proceedings of Geoinformatics 99 Conference．Ann Arbor:[s．n．],1999:1-12．

[3] MASUYAMA A．Methods for Detecting Apparent Differences between Spatial Tessellations at Different Time Points[J]．International Journal of Geographical Information Science, 2006,20(6):633-648．

[4] HUH Y,YU K,HEO J．Detecting Conjugate-point Pairs for Map Alignment between Two Polygon Datasets[J]．Computers,Environment and Urban Systems,2011,35 (3):250-262．

[5] COBB M A,CHUNG M J,FOLEY III H,et al．A Rulebased Approach for the Conflation of Attributed Vector Data[J]．GeoInformatica,1998,2(1):7-35．

[6] A L-BA KRI M,FAIRBAIRN D．Assessing Similarity Matching for Possible Integration of Feature Classifications of Geospatial Data from Official and Informal Sources[J]．International Journal of Geographical Information Science,2012,26(8):1437-1456．

[7] ZHANG Qiaoping,LI Deren,GONG Jianya．Areal Feature Matching among Urban Geographic Databases[J]．Journal of Remote Sensing,2004,8(2):107-112．(張橋平,李德仁,龔健雅．城市地圖數(shù)據(jù)庫(kù)面實(shí)體匹配技術(shù)[J]．遙感學(xué)報(bào),2004,8(2):107-112．)

[8] TONG Xiaohua,DENG Susu,SHI Wenzhong．A Probabilistic Theory-based Matching Method[J]．Acta Geodaetica et Cartographica Sinaca,2007,36(2):210-217．(童小華,鄧愫愫,史文中．基于概率的地圖實(shí)體匹配方法[J]．測(cè)繪學(xué)報(bào),2007,36(2):210-217．)

[9] BEERI C,KANZA Y,SAFRA E,et al．Object Fusion in Geographic Information Systems[C]∥Proceedings of the 30th International Conference on Very Large Data Bases: 30．Toronto:VLDB Endowment,2004:816-827．

[10] HAO Yanling,TANG Wenjing,ZHAO Yuxin,et al．Areal Feature Matching Algorithm Based on Spatial Similarity [J]．Acta Geodaetica et Cartographica Sinaca,2008,37 (4):501-506．(郝燕玲,唐文靜,趙玉新,等．基于空間相似性的面實(shí)體匹配算法研究[J]．測(cè)繪學(xué)報(bào),2008,37(4): 501-506．)

[11] YE Yaqin,WAN Bo,CHEN Bo．The Fuzzy Match Algorithm between Area Object Considering Associated Area Similarities[J]．Earth Science:Journal of China University of Geosciences),2010,35(4):385-390．(葉亞琴,萬(wàn)波,陳波．基于成分關(guān)聯(lián)區(qū)域相似度的面實(shí)體模糊匹配算法[J]．地球科學(xué):中國(guó)地質(zhì)大學(xué)學(xué)報(bào),2010,35(4):385-390．)

[12] SHAO Shiwei．Researehes and Applications on Polygon Entity Matching for Multi-scale Vector Data Based on Geometric Features[D]．Wuhan:Wuhan University,2011．(邵世維．基于幾何特征的多尺度矢量面狀實(shí)體匹配方法研究與應(yīng)用[D]．武漢:武漢大學(xué),2011．)

[13] DENG M,LI Z L,CHEN X Y．Extended Hausdorff Distance for Spatial Objects in GIS[J]．International Journal of Geographical Information Science,2007,21(4):459-475．

[14] XIONG D,SPERLING J．Semiautomated Matching for Network Database Integration[J]．ISPRS Journal of Photogrammetry and Remote Sensing,2004,59(1-2): 35-46．

[15] GABAY Y,DOYTSHER Y．Automatic Adjustment of Line Maps[C]∥Proceedings of the GIS/LIS．Phoenix:[s．n．], 1994:333–341．

[16] SAFRA E,KANZA Y,SAGIV Y,et al．Location-based Algorithms for Finding Sets of Corresponding Objects over Several Geo-spatial Data Sets[J]．International Journal of Geographical Information Science,2010,24(1):69-106．

[17] SAFRA E,KANZA Y,SAGIV Y,et al．Ad hoc Matching of Vectorial Road Networks[J]．International Journal of Geographical Information Science,2013,27(1):114-153．

[18] OLTEANU A-M．A Multi-criteria Fusion Approach for Geographical Data Matching[M]∥Quality Aspects in Spatial Data Mining．Boca Raton:CRC Press,2008: 47-55．

[19] ZANDBERGEN P A．Positional Accuracy of Spatial Data: Non-normal Distributions and a Critique of the National Standard for Spatial Data Accuracy[J]．Transactions in GIS,2008,12(1):103-30．

[20] GOMBOSˇI M,ZˇALIK B,KRIVOGRAD S．Comparing Two Sets of Polygons[J]．International Journal of Geographical Information Science,2003,17(5):431-443．

[21] CHEN C C,KNOBLOCK C A,SHAHABI C,et al．Automatically and Accurately Conflating Orthoimagery and Street Maps[C]∥Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems．Washington:ACM,2004:47-56．

(責(zé)任編輯:叢樹平)

Root Mean Square Error and Neighbouring Relation Matching Approach for Multi-scale Areal Feature

LIU Po1,2,ZHANG Yu1,3,GONG Jianhua1,2
1．Institute of Remote Sensing and Digital Earth,Chinese Academy of Sciences,Beijing 100101,China;2．Zhejiang-CAS Application Center for Geoinformatics,Hangzhou 314100,China;3．Institute of Geoscience and Info-Physics, Central South University,Changsha 410083,China

The RMSE is introduced in the process of matching,combined with the clustering algorithm of adjacent elements to match areal feature．It can effectively solve the problems for dertermining the threshold and many-to-many relationship in the multi-scale spatial areal feature matching．The experimental results show that the stability and reliability of this method is fine．

multi-scale;areal feature;root mean square error;neighbouring relation;match

LIU Po(1985－),male,PhD candidate, majors in spatial data updating and vitual geographic enviroment．

P208

A

1001-1595(2014)04-0419-07

2012-11-30

劉坡(1985—),男,博士生,研究方向?yàn)榭臻g數(shù)據(jù)更新、虛擬地理環(huán)境。

E-mail:liuposwust＠163．com

LIU Po,ZHANG Yu,GONG Jianhua．Root Mean Square Error and Neighbouring Relation Matching Approach for Multi-scale Areal Feature[J]．Acta Geodaetica et Cartographica Sinica,2014,43(4):419-425．(劉坡,張宇,龔建華．中誤差和鄰近關(guān)系的多尺度面實(shí)體匹配算法研究[J]．測(cè)繪學(xué)報(bào),2014,43(4):419-425．)

10．13485/j．cnki．11-2089．2014．0062

國(guó)家自然科學(xué)基金(41371387);中國(guó)科學(xué)院知識(shí)創(chuàng)新工程重要方向項(xiàng)目(KZCX2-EW-318);嘉善縣科技計(jì)劃(2011A44)

修回日期:2013-05-15