裴洪星，翟仁健，武 芳，李靖涵，鞏現(xiàn)勇，吳 錚

信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450000

?

小比例尺道路網(wǎng)眼約束下的多尺度道路網(wǎng)自動匹配

裴洪星，翟仁健，武 芳，李靖涵，鞏現(xiàn)勇，吳 錚

信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450000

針對道路網(wǎng)多尺度匹配的問題，提出了一種在小比例尺數(shù)據(jù)道路網(wǎng)眼約束下的多尺度道路匹配方法。首先，構(gòu)建兩幅不同比例尺數(shù)據(jù)的道路網(wǎng)眼；其次，在小比例尺道路網(wǎng)眼的約束下，提取出大比例尺道路中由若干道路網(wǎng)眼構(gòu)成的復(fù)合網(wǎng)眼，并完成與小比例尺道路網(wǎng)眼具有多對一和一對一關(guān)系的網(wǎng)眼匹配；然后，實現(xiàn)不同比例尺道路網(wǎng)眼的多對多匹配；最后，由復(fù)合網(wǎng)眼與小比例尺道路網(wǎng)眼的匹配關(guān)系轉(zhuǎn)化為多比例尺道路網(wǎng)眼邊界道路之間的匹配和內(nèi)部道路之間的匹配，完成整個道路網(wǎng)的匹配。試驗結(jié)果證明，本方法能較好地實現(xiàn)多尺度道路網(wǎng)的匹配。

多尺度匹配；道路網(wǎng)匹配；道路網(wǎng)眼

尺度是地理數(shù)據(jù)的重要特征[1]。不同尺度的數(shù)據(jù)在形態(tài)特征、細(xì)節(jié)信息和抽象程度上存在差異，使得空間數(shù)據(jù)的多尺度表達(dá)成為制約GIS應(yīng)用的難點之一[2-4]。空間數(shù)據(jù)多尺度表達(dá)的目的在于，解決離散數(shù)據(jù)與連續(xù)顯示之間的矛盾。目前多尺度表達(dá)數(shù)據(jù)庫的建立機(jī)制主要有兩種：一是靜態(tài)多版本方法，二是動態(tài)在線的方式[2,5]。理想的多尺度表達(dá)方法是由單一大比例尺矢量數(shù)據(jù)直接自動綜合生成任意小比例尺矢量數(shù)據(jù)，但是由于自動綜合這一國際難題仍未取得突破性進(jìn)展，因此現(xiàn)有條件下多尺度表達(dá)數(shù)據(jù)庫的建立主要是基于靜態(tài)多版本機(jī)制[6-7]。傳統(tǒng)基于關(guān)鍵比例尺的多尺度表達(dá)，數(shù)據(jù)間跳躍程度大，不能給用戶以連續(xù)的視覺感受，隨著研究日益深入，為了解決這一問題，基礎(chǔ)比例尺數(shù)據(jù)參與中間比例尺的新數(shù)據(jù)的生成被認(rèn)為是更合理的方式，實現(xiàn)的手段是在相鄰比例尺數(shù)據(jù)之間進(jìn)行插值，生成中間比例尺的表達(dá)。生成的插值數(shù)據(jù)要同時反映兩端比例尺數(shù)據(jù)的特征，因此需要建立兩端比例尺數(shù)據(jù)之間的聯(lián)系，從而出現(xiàn)了多尺度匹配的問題。建立兩端比例尺數(shù)據(jù)之間的聯(lián)系，必須借助空間數(shù)據(jù)匹配技術(shù)?？臻g數(shù)據(jù)匹配是空間數(shù)據(jù)集成與更新的核心技術(shù)，是指通過對目標(biāo)的幾何、拓?fù)浜驼Z義進(jìn)行相似性度量，識別出同一地區(qū)不同來源空間數(shù)據(jù)集中的同一地物[8-9]。

道路網(wǎng)作為最重要的地理要素之一，是多尺度表達(dá)研究的重點。長期以來，許多研究人員都對道路匹配算法進(jìn)行了研究，文獻(xiàn)[10]基于概率統(tǒng)計的基本思想，對道路數(shù)據(jù)進(jìn)行了幾何匹配，其核心是計算一定范圍內(nèi)候選目標(biāo)的匹配概率，取概率最大者為匹配結(jié)果，屬于典型的緩沖區(qū)增長法(buffer growing)[11-13]；文獻(xiàn)[14—15]用迭代幾何匹配算法對GDF導(dǎo)航數(shù)據(jù)和德國ATKIS道路數(shù)據(jù)進(jìn)行了匹配，屬于迭代最近點法(iterative closest point)。前者是一種基于道路弧段的道路網(wǎng)匹配方法，后者是一種基于道路節(jié)點的道路網(wǎng)匹配方法，現(xiàn)有道路網(wǎng)匹配基本上都屬于這兩類方法，或者是基于這兩類方法的合并與改進(jìn)。文獻(xiàn)[16]采用層次分析法進(jìn)行道路網(wǎng)整體分析，自動對道路的相似評價指標(biāo)分配權(quán)值，評價道路的整體相似度完成道路的自動匹配。文獻(xiàn)[17]提出基于多尺度道路網(wǎng)距離的匹配算法，將復(fù)雜的折線與折線之間的幾何相似度計算轉(zhuǎn)化為求節(jié)點到折線的距離，并通過建立格網(wǎng)索引提高了計算效率。文獻(xiàn)[18]提出全局尋優(yōu)的矢量道路網(wǎng)自動匹配方法，綜合利用道路弧段和節(jié)點的特征信息，建立最優(yōu)化模型，利用概率松弛法求解最優(yōu)解，獲得道路弧段之間的匹配關(guān)系。文獻(xiàn)[19]針通過對道路交叉口的結(jié)構(gòu)化描述，提取道路節(jié)點的局部網(wǎng)絡(luò)模式特征，計算節(jié)點之間的形態(tài)相似性進(jìn)行道路匹配。

傳統(tǒng)方法多是基于對同尺度的道路之間的整體相似度進(jìn)行評價，而在多尺度條件下，同名道路之間的形態(tài)具有明顯差異，在屬性信息缺失條件下，利用幾何特征提取道路整體往往會出現(xiàn)錯誤，不能保證不同比例尺的道路數(shù)據(jù)提取出完全相同的道路整體，因此利用多指標(biāo)建立的相似性評價體系可能無法得到滿意的匹配效果。針對這一難題，本文提出一種基于小比例尺道路網(wǎng)眼約束下的多尺度道路自動匹配算法，先建立大比例尺道路網(wǎng)眼與小比例尺道路網(wǎng)眼之間的匹配關(guān)系，然后利用道路網(wǎng)眼的匹配關(guān)系作為約束條件完成不同比例尺同名道路之間的匹配。

1 道路網(wǎng)眼多尺度匹配模型

本文的匹配研究主要是針對簡單形態(tài)的多尺度道路網(wǎng)數(shù)據(jù)，不考慮具有復(fù)雜結(jié)構(gòu)體以及雙線道路的道路網(wǎng)數(shù)據(jù)之間的匹配。

1.1 道路網(wǎng)眼的定義

地圖中道路縱橫交錯，將地圖分割成若干個相互獨立的面狀區(qū)域，這些面狀區(qū)域構(gòu)成了道路網(wǎng)眼。道路網(wǎng)眼并不是一種具體的地理要素，而是人們在研究道路網(wǎng)智能選取、多尺度矢量空間數(shù)據(jù)匹配、道路自動綜合算法等過程中為了方便表達(dá)與描述道路網(wǎng)空間結(jié)構(gòu)特征而抽象出的一種對象[20]。

道路的層次性決定了道路圍成的道路網(wǎng)眼的層次性。高等級道路對空間區(qū)域形成主要分割，形成較高等級的網(wǎng)眼，低等級道路對空間區(qū)域形成次要分割，形成低等級網(wǎng)眼。最典型的實例就是“城市街區(qū)系統(tǒng)”。為了區(qū)分道路網(wǎng)眼的層次性，根據(jù)其復(fù)雜性的不同將道路網(wǎng)眼劃分為基本道路網(wǎng)眼和復(fù)合道路網(wǎng)眼?；镜缆肪W(wǎng)眼是道路網(wǎng)形態(tài)結(jié)構(gòu)分解的最小單元，如圖1中的a、b、c、d，它的基本特征是網(wǎng)眼內(nèi)部不存在其他道路對其產(chǎn)生有效分割。復(fù)合道路網(wǎng)眼的內(nèi)部則存在多條道路對道路網(wǎng)眼所在區(qū)域進(jìn)行分割，形成其他的道路網(wǎng)眼。實際上也就是復(fù)合道路網(wǎng)眼是由兩個或者兩個以上的道路網(wǎng)眼組合而成。如道路網(wǎng)眼A、B和C，它們都是由圖1中較小的網(wǎng)眼進(jìn)一步合并而成。復(fù)合網(wǎng)眼并不是隨意由相鄰任意基本網(wǎng)眼簡單組合而成，形成復(fù)合網(wǎng)眼的邊界道路，對空間區(qū)域形成主要分割，與復(fù)合網(wǎng)眼內(nèi)部道路相比，具有更高的等級。

圖1 道路網(wǎng)眼及其分類示例Fig.1 The classification sample of road meshes

為了保證道路網(wǎng)眼的構(gòu)成符合人的認(rèn)知習(xí)慣，在構(gòu)成上必須遵循下列原則[21]：

(1) 道路網(wǎng)眼的邊界由頂點和邊構(gòu)成，邊實際對應(yīng)一條道路(stroke)的一部分(路段)，頂點則是不同道路的交點。

(2) 復(fù)合道路網(wǎng)眼邊界道路的等級不能低于其內(nèi)部網(wǎng)眼邊界道路的等級。

道路網(wǎng)眼邊界道路的等級由道路本身的屬性等級、結(jié)構(gòu)重要性以及長度來決定，具體判斷方法參考文獻(xiàn)[22]。

1.2 多尺度道路網(wǎng)眼的對應(yīng)關(guān)系

反映同一地區(qū)的小比例尺道路網(wǎng)數(shù)據(jù)和大比例道路網(wǎng)數(shù)據(jù)中存在著同名道路，這些道路在大比例尺路網(wǎng)數(shù)據(jù)中具有較高的等級，它們構(gòu)成了大比例尺道路網(wǎng)的“骨架”網(wǎng)絡(luò)。小比例尺道路網(wǎng)將空間區(qū)域劃分為若干較大的網(wǎng)眼區(qū)域，大比例尺道路往往對這些大道路網(wǎng)眼所對應(yīng)的區(qū)域做進(jìn)一步細(xì)分，從而產(chǎn)生較小網(wǎng)眼，顯然這些較小的網(wǎng)眼包含于小比例尺道路網(wǎng)的大網(wǎng)眼之中，即大比例尺的小網(wǎng)眼處于小比例尺大網(wǎng)眼的約束之下，這是本文匹配方法的思想基礎(chǔ)。圖2是某一區(qū)域1∶5萬和1∶25萬道路數(shù)據(jù)，反映了大小比例尺數(shù)據(jù)的道路網(wǎng)眼之間可能的對應(yīng)情況。

圖2 同一地區(qū)不同比例尺道路網(wǎng)眼的對應(yīng)關(guān)系Fig.2 Matching relationships of road networks meshes of different scales in the same area

對同一地區(qū)的道路網(wǎng)數(shù)據(jù)，大比例尺道路將小比例尺道路網(wǎng)眼內(nèi)部空間進(jìn)一步劃分為若干較小網(wǎng)眼，使大比例尺和小比例尺同名道路網(wǎng)眼之間以構(gòu)成N∶1(N>1)的匹配關(guān)系，顯而易見，在多尺度網(wǎng)眼匹配關(guān)系中以N∶1匹配為主。除此之外，也存在著少量的M∶N(M>1,N>1)和1∶1匹配關(guān)系。

1.3 基本思想

由于大比例尺數(shù)據(jù)道路密度較大，同時存在位置誤差，導(dǎo)致小比例尺中的道路容易與同名實體道路附近道路發(fā)生錯誤匹配。利用道路網(wǎng)眼進(jìn)行匹配可以突出道路結(jié)構(gòu)的重要性，削弱位置誤差對匹配造成的影響，并且道路網(wǎng)眼越大，對位置誤差的容錯能力越強(qiáng)。其基本思想是：通過建立道路之間的拓?fù)潢P(guān)系，構(gòu)建道路網(wǎng)眼，道路網(wǎng)眼將整個道路網(wǎng)劃分為不同的道路子集，首先利用道路網(wǎng)眼匹配實現(xiàn)網(wǎng)眼邊界道路的匹配，再對網(wǎng)眼內(nèi)部道路實施匹配，這樣不但縮小了匹配搜索的范圍，而且增加了匹配道路的相關(guān)性，便于匹配道路對象的快速準(zhǔn)確查找。

大比例尺道路網(wǎng)眼與小比例尺道路網(wǎng)眼的N∶1和M∶N的匹配關(guān)系反映的是網(wǎng)眼邊界路段之間的N∶1和M∶N匹配關(guān)系。在道路要素的匹配關(guān)系中，N∶1和M∶N匹配關(guān)系要比1∶1關(guān)系復(fù)雜的多。理想的方法是將道路之間的N∶1和M∶N匹配關(guān)系轉(zhuǎn)化為1∶1匹配關(guān)系，從而提高匹配效率和準(zhǔn)確率。實際上，小比例尺數(shù)據(jù)中的道路在大比例尺數(shù)據(jù)中的同名實體道路往往是大比例尺道路網(wǎng)中的骨架道路，從大比例尺道路網(wǎng)眼中提取與小比例尺網(wǎng)眼或其組合構(gòu)成為“1∶1”匹配關(guān)系道路網(wǎng)眼或復(fù)合網(wǎng)眼，根據(jù)網(wǎng)眼間的“1∶1”匹配關(guān)系實現(xiàn)匹配網(wǎng)眼間對應(yīng)邊界道路的“1∶1”匹配，然后根據(jù)一致性原則對網(wǎng)眼內(nèi)部道路進(jìn)行合并處理，再進(jìn)行網(wǎng)眼內(nèi)部道路匹配。

圖3 多尺度路網(wǎng)匹配Fig.3 Matching of multi-scale road networks

2 多尺度道路匹配的實現(xiàn)方法

2.1 根據(jù)匹配關(guān)系提取復(fù)合網(wǎng)眼

2.1.1 提取N∶1和1∶1匹配關(guān)系的復(fù)合網(wǎng)眼

利用道路網(wǎng)眼實現(xiàn)多尺度道路匹配的關(guān)鍵在于分別從大小比例尺道路網(wǎng)數(shù)據(jù)中提取出構(gòu)成匹配關(guān)系的道路網(wǎng)眼(或復(fù)合道路網(wǎng)眼)。大比例尺路網(wǎng)與小比例尺路網(wǎng)構(gòu)成N∶1(N>1)和1∶1匹配關(guān)系的道路網(wǎng)眼的提取步驟為：

(1) 計算大比例尺基本道路網(wǎng)眼與小比例尺網(wǎng)眼的重疊率。大比例尺基本網(wǎng)眼與小比例尺網(wǎng)眼的重疊率很大程度上決定了在提取復(fù)合網(wǎng)眼時受小比例尺數(shù)據(jù)上哪一個網(wǎng)眼的約束，從而影響復(fù)合網(wǎng)眼提取的準(zhǔn)確性。重疊率計算公式為

(1)

式中，Areaoverlap是大比例尺基本道路網(wǎng)眼與小比例尺網(wǎng)眼相交部分的面積；Arealarge為大比例尺道路網(wǎng)眼面積。設(shè)閾值R0，當(dāng)R≥R0，該小比例尺道路網(wǎng)眼為約束網(wǎng)眼。

(2) 搜索大比例尺基本道路網(wǎng)眼中被同一個小比例尺網(wǎng)眼約束的所有網(wǎng)眼，放入同一個候選集。

(3) 合并同一個候選集中的網(wǎng)眼，提取出初始復(fù)合網(wǎng)眼，如圖4(c)所示。

圖4 復(fù)合網(wǎng)眼的初步提取Fig.4 Extraction of composite meshes in the first step

不同比例尺數(shù)據(jù)的同名道路之間存在位置偏差，導(dǎo)致復(fù)合道路網(wǎng)眼的提取產(chǎn)生偏差，表現(xiàn)為大比例尺道路網(wǎng)眼不在對應(yīng)的小比例尺網(wǎng)眼區(qū)域內(nèi)(具有較低的重疊率)，甚至位于相鄰的網(wǎng)眼區(qū)域內(nèi)。為了更準(zhǔn)確地提取復(fù)合網(wǎng)眼，需要對提取的初始復(fù)合網(wǎng)眼進(jìn)行評估修正，識別遺漏的網(wǎng)眼并與初始復(fù)合網(wǎng)眼合并，同時將錯誤加入的網(wǎng)眼從初始復(fù)合網(wǎng)眼中剔除，得到正確的提取結(jié)果。

以圖4為例，說明初始復(fù)合網(wǎng)眼修正的基本過程。圖4中C是在網(wǎng)眼D約束下初步提取的復(fù)合網(wǎng)眼，網(wǎng)眼A由于重疊率低于閾值在初步提取時沒被選中，B為被正確提取組成的C的大比例網(wǎng)眼，與A相鄰且面積最小。對A進(jìn)行分析，判定是否要與初始復(fù)合網(wǎng)眼C合并生成新的復(fù)合網(wǎng)眼。判定過程如下：

(1) 搜索初始復(fù)合網(wǎng)眼C內(nèi)部與A相鄰的網(wǎng)眼，選擇其中重疊率最高且面積最小的網(wǎng)眼B作為候選對象。如果重疊率最大與面積最小出現(xiàn)沖突，規(guī)定優(yōu)先考慮重疊率指標(biāo)。

(2) 將A與候選對象B合并，按式(2)求合并后整體的重疊率

(2)

式中，RAB為AB作為整體時的重疊率，Areaoverlap_A和Areaoverlap_B分別為A、B與小比例尺網(wǎng)眼的重疊面積，AreaA和AreaB分別為網(wǎng)眼A、B的面積。

(3) 比較RAB與R0，如果RAB≥R0，則網(wǎng)眼C作為與網(wǎng)眼A合并的候選對象。對與A相鄰的下一個復(fù)合網(wǎng)眼進(jìn)行同樣的判定，直到與A相鄰的所有復(fù)合網(wǎng)眼判定完畢，從網(wǎng)眼A的所有候選對象中選擇重疊率最高的復(fù)合網(wǎng)眼與網(wǎng)眼A合并。如果按照上述方法找不到可合并的復(fù)合網(wǎng)眼，則網(wǎng)眼A保持獨立現(xiàn)狀。

除了上述重新加入遺漏的道路網(wǎng)眼外，還需剔除錯誤加入的網(wǎng)眼，如圖5所示。

圖5 網(wǎng)眼錯誤提取及修正Fig.5 Wrong extraction of meshes and correction

根據(jù)認(rèn)知判斷，大比例尺道路網(wǎng)眼中的基本網(wǎng)眼G與小比例尺道路網(wǎng)眼E對應(yīng)，成為在網(wǎng)眼E約束下生成的復(fù)合網(wǎng)眼的候選對象，然而根據(jù)重疊率判斷，網(wǎng)眼G卻與網(wǎng)眼E的相鄰網(wǎng)眼F對應(yīng)，成了網(wǎng)眼F約束下的復(fù)合網(wǎng)眼的候選對象。針對這種錯誤，需要進(jìn)行修正。根據(jù)道路網(wǎng)眼的定義，道路網(wǎng)眼邊界道路的等級應(yīng)比內(nèi)部道路的等級要高，據(jù)此對錯誤匹配的小網(wǎng)眼進(jìn)行剔除。將初始復(fù)合網(wǎng)眼的邊界道路與內(nèi)部網(wǎng)眼的邊界道路進(jìn)行等級比較，如圖5(a)中，對基本網(wǎng)眼G的邊界道路l1和l2的屬性等級進(jìn)行判定，l1為高速公路，l2為等外公路，顯然，l1的等級要高于l2，說明前面得到的初始復(fù)合網(wǎng)眼F是存在問題的，應(yīng)將網(wǎng)眼G從復(fù)合網(wǎng)眼F中剔除，并入網(wǎng)眼E，完成對復(fù)合網(wǎng)眼的修正。

經(jīng)過上述步驟，完成不同比例尺道路網(wǎng)眼的匹配關(guān)系，最后必須判斷它們在大小上的相似，避免出現(xiàn)偽匹配，大小相似性計算為

(3)

式中，Y為相似性指標(biāo)，設(shè)定Y的閾值為ε0≤Y≤ε1；Area復(fù)合為初始復(fù)合網(wǎng)眼面積，Areasmall為與之匹配的小比例尺網(wǎng)眼面積。當(dāng)Y大于閾值時，最終確認(rèn)二者匹配。

通過小比例尺道路網(wǎng)眼的約束提取大比例尺網(wǎng)眼中與之相對應(yīng)的復(fù)合網(wǎng)眼，通過網(wǎng)眼之間的匹配關(guān)系實現(xiàn)道路的匹配。該方法了避免大比例尺道路數(shù)據(jù)中不相關(guān)的道路數(shù)據(jù)對匹配過程產(chǎn)生干擾，簡化了匹配過程，提高匹配的效率和準(zhǔn)確率。提取復(fù)合網(wǎng)眼的流程如圖7所示。

圖6 網(wǎng)眼偽匹配關(guān)系Fig.6 Fake matching relationship of meshes

圖7 復(fù)合網(wǎng)眼提取流程Fig.7 Extraction of composite meshes

2.1.2 提取M∶N匹配關(guān)系的復(fù)合網(wǎng)眼

在多尺度網(wǎng)眼匹配關(guān)系中，對1∶1和N∶1匹配關(guān)系處理后，剩下的還可能存在未匹配網(wǎng)眼，這部分網(wǎng)眼屬于M∶N匹配關(guān)系。存在M∶N匹配關(guān)系的網(wǎng)眼在空間上呈現(xiàn)“群落”的特點，即若干未匹配網(wǎng)眼往往聚集在一起，通過對群落區(qū)域中鄰近網(wǎng)眼的合并處理來識別網(wǎng)眼M∶N匹配關(guān)系。

對呈現(xiàn)群落特點的網(wǎng)眼聚集區(qū)域逐個區(qū)域處理，處理的過程如下：

(1) 將一個網(wǎng)眼聚集區(qū)域整體合并為一個復(fù)合網(wǎng)眼，然后對大小比例尺合并后的復(fù)合網(wǎng)眼進(jìn)行匹配，再根據(jù)前一節(jié)的匹配條件判定這對復(fù)合網(wǎng)眼是否匹配，如果匹配，則轉(zhuǎn)入下一個網(wǎng)眼聚集區(qū)域的處理，直至完成所有未匹配網(wǎng)眼的匹配，匹配過程停止；如果不匹配，則轉(zhuǎn)到步驟(1)。

(2) 任意選取小比例尺中兩個相鄰的網(wǎng)眼合并為一個復(fù)合網(wǎng)眼，將大比例尺中與之相交且重疊率達(dá)到閾值R0的網(wǎng)眼合并為一個復(fù)合網(wǎng)眼，判定二者是否匹配，若匹配，則用同樣的方法進(jìn)行余下的網(wǎng)眼匹配處理；若余下的任意兩個網(wǎng)眼的合并得到的復(fù)合網(wǎng)眼都不能完成匹配，則轉(zhuǎn)入步驟(3)。

(3) 任意選取小比例尺中3個相鄰的網(wǎng)眼合并為一個復(fù)合網(wǎng)眼，將大比例尺中與之相交且重疊率達(dá)到閾值R0的網(wǎng)眼合并為一個復(fù)合網(wǎng)眼，判定二者是否匹配，若匹配，則用同樣的方法進(jìn)行余下的網(wǎng)眼匹配處理；若余下的任意3個網(wǎng)眼的合并得到的復(fù)合網(wǎng)眼都不能完成匹配，則依次逐個增加相鄰的網(wǎng)眼按步驟(3)重新進(jìn)行，直至最后完成匹配。然后轉(zhuǎn)入下一個網(wǎng)眼聚集區(qū)域的處理，直至所有的網(wǎng)眼匹配判定完成。

2.2 利用道路網(wǎng)眼匹配進(jìn)行道路分類處理

網(wǎng)眼匹配完成后，根據(jù)道路與網(wǎng)眼的拓?fù)潢P(guān)系進(jìn)行分類匹配，待匹配道路按類別被劃分為網(wǎng)眼邊界道路和網(wǎng)眼內(nèi)部道路。原始道路數(shù)據(jù)經(jīng)過拓?fù)涮幚砗?，會在道路交點處被分段，形成節(jié)點和弧段。由于道路網(wǎng)眼之間構(gòu)成的匹配關(guān)系不僅僅只有1∶1，還存在N∶1和M∶N，因此需要對復(fù)合網(wǎng)眼中的邊界道路弧段和內(nèi)部道路弧段分別進(jìn)行合并處理，按照Gestalt視覺感知中的良好延續(xù)性(good continuation)原則將弧段合并為stroke[23-24]。為了提高道路匹配的效率，需要建立復(fù)合網(wǎng)眼與網(wǎng)眼道路之間的拓?fù)溆成潢P(guān)系。如圖8所示為某個尺度的道路網(wǎng)經(jīng)過網(wǎng)眼匹配識別后，提取得到若干復(fù)合網(wǎng)眼，復(fù)合網(wǎng)眼與其邊界道路以及內(nèi)部的拓?fù)溆成潢P(guān)系見表1。

圖8 道路網(wǎng)及匹配識別的復(fù)合網(wǎng)眼Fig.8 The road network and composite meshes by matching

表1 復(fù)合網(wǎng)眼與道路的拓?fù)溆成潢P(guān)系Tab.1 Mapping relationship between composite meshes and roads

根據(jù)網(wǎng)眼匹配結(jié)果和道路與網(wǎng)眼的拓?fù)溆成潢P(guān)系，可以快速確定匹配道路所在的網(wǎng)眼，從而大大縮小匹配搜索的范圍，提高道路匹配的效率和準(zhǔn)確性。

2.3 道路匹配的實現(xiàn)

建立匹配關(guān)系是將匹配數(shù)據(jù)映射到參考數(shù)據(jù)的過程。本文利用網(wǎng)眼匹配約束實現(xiàn)道路匹配，流程為：首先對大比例尺和小比例尺道路網(wǎng)眼進(jìn)行網(wǎng)眼匹配識別，得到相匹配的道路網(wǎng)眼(復(fù)合道路網(wǎng)眼)，然后對識別的匹配網(wǎng)眼的邊界道路進(jìn)行匹配，最后對網(wǎng)眼的內(nèi)部道路進(jìn)行匹配。首先對網(wǎng)眼邊界道路進(jìn)行匹配。對于已匹配的兩個道路網(wǎng)眼，確定網(wǎng)眼邊界道路的匹配很容易實現(xiàn)。取小比例尺已匹配道路網(wǎng)眼的某條邊(路段)，它的匹配對象一定是對應(yīng)的大比例尺相匹配的道路網(wǎng)眼中的某條邊(路段)，避免了大范圍的搜索，并且一旦確定了某條邊的匹配對象，其他邊的匹配對象可以根據(jù)網(wǎng)眼邊的連接次序通過推導(dǎo)得到。

由于網(wǎng)眼的匹配約束，網(wǎng)眼邊界道路的匹配判斷不需要復(fù)雜的相似性計算就可以實現(xiàn)。本文利用Hausdorff距離[25]對已匹配道路網(wǎng)眼的邊界道路進(jìn)行匹配判斷，選擇距離最小的道路作為匹配對象。

Hausdorff距離最初是用來測定點集之間的距離。設(shè)有兩個點集合A={a1,a2,…,am}和B={b1,b2,…,bn}，則點集A與B之間的Hausdorff距離定義為

(4)

式中

(5)

(6)

dh(A,B)表示點集合A中每一個點到點集合B最小距離的最大值。

線要素可以看作一組有序的點集，因此可以利用Hausdorff距離來衡量線要素之間距離。它反映的是線要素之間的整體距離，比單純使用歐式距離更加合理，常被用于線要素之間的匹配判斷。

已匹配網(wǎng)眼的內(nèi)部道路，存在兩種類型，一種是能夠?qū)W(wǎng)眼形成剖分的道路，另一種是未對網(wǎng)眼形成剖分的道路。第1種類型的內(nèi)部道路，沒有匹配對象，不做處理。第2種類型的道路，主要是一些懸掛道路，這類道路的匹配，在對應(yīng)的匹配網(wǎng)眼內(nèi)部搜索可能與之匹配的道路。

3 試驗與分析

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

本文的試驗，選取寧波市的1∶25萬和1∶5萬部分道路數(shù)據(jù)進(jìn)行匹配試驗。首先將兩個不同比例尺的道路網(wǎng)數(shù)據(jù)進(jìn)行投影、坐標(biāo)統(tǒng)一變換后疊加顯示，如圖9所示，其中1∶25萬道路網(wǎng)，其數(shù)據(jù)量為80 KB，382個對象；1∶5萬道路網(wǎng)，數(shù)據(jù)量為594 KB,1588個對象。

3.2 匹配試驗結(jié)果

對1∶5萬和1∶25萬道路網(wǎng)數(shù)據(jù)網(wǎng)眼匹配識別，從而提取出兩個數(shù)據(jù)集中構(gòu)成匹配關(guān)系的道路網(wǎng)眼。根據(jù)式(1)初步建立多尺度網(wǎng)眼間的匹配關(guān)系，將大比例尺中與同一小比例尺網(wǎng)眼具有匹配關(guān)系的網(wǎng)眼進(jìn)行合并生成初步的復(fù)合網(wǎng)眼，經(jīng)過多次試驗，由于試驗數(shù)據(jù)位置誤差較小，經(jīng)試驗設(shè)定重疊率R0=0.9時較為合適，生成結(jié)果如圖10的初步復(fù)合網(wǎng)眼，紅色區(qū)域為待進(jìn)一步處理的網(wǎng)眼。

圖9 多尺度道路網(wǎng)數(shù)據(jù)Fig.9 The multi-scale road networks data

圖10 復(fù)合網(wǎng)眼初步提取Fig.10 Preliminary extraction of composite meshes

1∶5萬目標(biāo)數(shù)據(jù)中的網(wǎng)眼數(shù)為1473，首先進(jìn)行復(fù)合網(wǎng)眼的粗提取，處理掉大部分的大比例尺網(wǎng)眼，得到初步的復(fù)合網(wǎng)眼，剩余79個網(wǎng)眼在初步提取復(fù)合網(wǎng)眼過程中不滿足閾值條件，需要進(jìn)一步判定處理，如圖10(c)。這部分網(wǎng)眼的判定結(jié)果如表2。

表2 待處理網(wǎng)眼處理情況Tab.2 Solving the problem of mesh’s merging

經(jīng)過進(jìn)一步的提取，79個待處理網(wǎng)眼中有75個經(jīng)判定符合合并條件，與相鄰的最優(yōu)復(fù)合網(wǎng)眼進(jìn)行合并處理，然后根據(jù)相似性指標(biāo)Y進(jìn)行檢驗，設(shè)定的閾值為0.9≤Y≤1.1，7個網(wǎng)眼被解除匹配關(guān)系，最終得到11個未匹配網(wǎng)眼，如圖11(a)。在此基礎(chǔ)上，在剩下的未匹配網(wǎng)眼中進(jìn)行M∶N匹配。

圖11 網(wǎng)眼M∶N匹配實例Fig.11 An example of many-to-many matching of meshes under different scales

在提取的復(fù)合網(wǎng)眼中，Ⅰ處的未匹配網(wǎng)眼形成聚集區(qū)域，對應(yīng)在小比例尺網(wǎng)眼中Ⅰ′處存在未匹配網(wǎng)眼X和Y，根據(jù)2.1.2節(jié)中的匹配思想，小比例尺中Ⅰ′處的未匹配網(wǎng)眼X和Y組成的復(fù)合網(wǎng)眼與大比例尺中Ⅰ處的所有網(wǎng)眼組成的復(fù)合網(wǎng)眼形成1∶1匹配，實質(zhì)上是未匹配網(wǎng)眼之間形成了9∶2的匹配關(guān)系。至此完成了不同比例尺道路網(wǎng)眼數(shù)據(jù)中所有網(wǎng)眼之間的匹配。

依據(jù)網(wǎng)眼匹配識別提取得到的大比例尺復(fù)合道路網(wǎng)眼，構(gòu)成大比例尺道路網(wǎng)的骨架網(wǎng)眼。對提取的匹配網(wǎng)眼的邊界道路和內(nèi)部道路進(jìn)行按照stroke一致性原則進(jìn)行合并，并建立道路網(wǎng)眼與道路的拓?fù)溆成潢P(guān)系。經(jīng)過處理后，原來匹配網(wǎng)眼邊界道路之間存在的N∶1或M∶N匹配關(guān)系變?yōu)椤?∶1”匹配關(guān)系，減少了待匹配對象的數(shù)量，大大簡化了匹配的難度，提高了匹配的準(zhǔn)確度。對同一數(shù)據(jù)利用陳玉敏的多尺度道路網(wǎng)的距離匹配算法[17]，試驗數(shù)據(jù)的匹配結(jié)果如圖12所示，試驗統(tǒng)計結(jié)果如表3所示。

圖12 兩種不同方法的多尺度道路匹配結(jié)果Fig.12 Results of multi-scale match of road in two different methods

表3 兩種不同匹配方法結(jié)果統(tǒng)計Tab.3 Results of the two different methods

3.3 對比分析

根據(jù)試驗結(jié)果，當(dāng)數(shù)據(jù)中出現(xiàn)小短線時，多尺度距離匹配算法在匹配過程中會出現(xiàn)小短線附近的道路與其形成錯誤匹配，出現(xiàn)這種現(xiàn)象的原因在于算法本身的缺陷，當(dāng)線要素較短小時，其本身作為點集的數(shù)量很少，造成大部分甚至所有點都落入與其相鄰的較長道路線要素的緩沖區(qū)內(nèi)，造成錯誤匹配。而在本文方法中，由于較短小的線要素也是作為網(wǎng)眼的邊界要素，在匹配時只需考慮與之所在網(wǎng)眼對應(yīng)的網(wǎng)眼的邊界要素即可，能夠出現(xiàn)有效避免這些較短小道路線要素的錯誤匹配，如圖13所示。

對于同名道路線要素差異度較大的情況，多尺度距離匹配算法也存在不足，存在無法完成匹配的情況，而本文方法，對形態(tài)相似性并沒有很高的依賴性，因此在匹配時具有一定的優(yōu)勢。如圖14，形態(tài)具有一定差異的同名道路，利用多尺度距離匹配方法未能實現(xiàn)匹配，而本文方法則利用同名要素所在網(wǎng)眼的對應(yīng)關(guān)系較容易地實現(xiàn)了二者的匹配。

圖13 兩種匹配方法實例對比Fig.13 The contrast experiment of the two matching methods

圖14 匹配方法實例對比Fig.14 The contrast experiment of the two matching methods

通過試驗的對比結(jié)果可以得出，本文所提算法在匹配率和準(zhǔn)確率上相比多尺度距離匹配算法都具有一定優(yōu)勢，原因主要在于以下兩點：第一，本文方法利用網(wǎng)眼約束道路，通過對網(wǎng)眼的匹配，使道路的模糊對應(yīng)關(guān)系轉(zhuǎn)變匹配網(wǎng)眼的道路清晰的對應(yīng)關(guān)系，縮小了匹配道路的搜索范圍，同時降低了道路本身對位置和形態(tài)相似的依賴性，在多尺度匹配中具有較好的現(xiàn)實意義；第二，分類匹配的思想，將道路分為網(wǎng)眼邊界道路和內(nèi)部道路，使匹配被限制在同類別的道路中進(jìn)行，減少了干擾，提高了匹配對應(yīng)的準(zhǔn)確性。

4 結(jié) 論

道路網(wǎng)的匹配往往采用幾何匹配的方式處理，而在多尺度道路網(wǎng)的匹配中，如果不經(jīng)過提取而直接利用幾何特征進(jìn)行匹配，匹配的效果往往很不理想，原因是道路在不同尺度下的幾何形態(tài)、拓?fù)潢P(guān)系和屬性信息存在差異，無法保證數(shù)據(jù)具有穩(wěn)定的匹配基礎(chǔ)，同時大比例尺數(shù)據(jù)中眾多其他的道路數(shù)據(jù)會對匹配過程產(chǎn)生較大干擾，導(dǎo)致匹配的不確定性增加。本文方法通過網(wǎng)眼匹配提取出主要的道路匹配候選集，排除了不相關(guān)道路要素參與到匹配過程中，同時降低了匹配時對道路幾何形態(tài)的依賴，相比于傳統(tǒng)的匹配方法，提高了匹配準(zhǔn)確率。

網(wǎng)眼匹配關(guān)系的提取是本算法的一個關(guān)鍵，如果位置偏差較大，會對匹配結(jié)果產(chǎn)生負(fù)面影響。針對這一情況，可以考慮首先選取小比例尺數(shù)據(jù)中少量高等級骨架道路，構(gòu)成更大的道路網(wǎng)眼，大網(wǎng)眼抗位置誤差的能力更強(qiáng)，首先對這些大網(wǎng)眼進(jìn)行匹配關(guān)系提取，匹配完成后，利用匹配結(jié)果進(jìn)行位置糾正，可以大大減少數(shù)據(jù)的位置誤差，可以有利于提高后續(xù)更小道路網(wǎng)眼匹配關(guān)系提取的精度。

[1] 陳俊杰.不同尺度下地理實體的一體化組織與表達(dá)方法研究[D].杭州:浙江大學(xué),2011.CHEN Junjie.Study on the Integrative Organization and Representation Method for Geographical Entity in Different Scales[D].Hangzhou:Zhejiang University,2011.

[2] 王艷慧,李小娟,宮輝力.地理要素多尺度表達(dá)的基本問題[J].中國科學(xué)E輯:技術(shù)科學(xué),2006,36(增刊):38-44.WANG Yanhui,LI Xiaojuan,GONG Huili.On Multi-scale Representations of Geographic Features[J].Science in China Series E:Technological Sciences,2006,49(S2):39-47.

[3] BALLEY S,PARENT C,SPACCAPIETRA S.Modelling Geographic Data with Multiple Representations[J].International Journal of Geographical Information Science,2004,18(4):327-352.

[4] 艾廷華,成建國.對空間數(shù)據(jù)多尺度表達(dá)有關(guān)問題的思考[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2005,30(5):377-382.AI Tinghua,CHENG Jianguo.Key Issues of Multi-scale Representation of Spatial Data[J].Geomatics and Information Science of Wuhan University,2005,30(5):377-382.

[5] 張強(qiáng),武芳,錢海忠,等.基于關(guān)鍵比例尺的空間數(shù)據(jù)多尺度表達(dá)[J].測繪科學(xué)技術(shù)學(xué)報,2011,28(5):383-386.ZHANG Qiang,WU Fang,QIAN Haizhong,et al.Milestone Scales Oriented Spatial Data Multi-representation Techniques[J].Journal of Geomatics Science and Technology,2011,28(5):383-386.

[6] 魏海平.GIS中多尺度地理數(shù)據(jù)庫的研究與應(yīng)用[J].測繪學(xué)院學(xué)報,2000,17(2):134-137.WEI Haiping.The Research and Application of Multi-scale Geographic Database in GIS[J].Journal of Institute of Surveying and Mapping,2000,17(2):134-137.

[7] 武芳,張強(qiáng),鞏現(xiàn)勇,等.一種匹配分類的空間數(shù)據(jù)多尺度表達(dá)與變換模型[J].測繪科學(xué)技術(shù)學(xué)報,2014,31(4):331-335.WU Fang,ZHANG Qiang,GONG Xianyong,et al.Matching and Classification Model for Multi-scale Transformation and Representation of Spatial Data[J].Journal of Geomatics Science and Technology,2014,31(4):331-335.

[8] 徐楓,鄧敏,趙彬彬,等.空間目標(biāo)匹配方法的應(yīng)用分析[J].地球信息科學(xué)學(xué)報,2009,11(5):657-663.XU Feng,DENG Min,ZHAO Binbin,et al.A Detailed Investigation on the Methods of Object Matching[J].Journal of Geo-Information Science,2009,11(5):657-663.

[9] 陳競男,錢海忠,王驍,等.提高線要素匹配率的動態(tài)化簡方法[J].測繪學(xué)報,2016,45(4):486-493.DOI:10.11947/j.AGCS.2016.20150074.CHEN Jingnan,QIAN Haizhong,WANG Xiao,et al.Improving the Matching Rate of Line Feature by Using Dynamic Simplification[J].Acta Geodaetica et Cartographica Sinica,2016,45(4):486-493.DOI:10.11947/j.AGCS.2016.20150074.

[10] WALTER V,FRITSCH D.Matching Spatial Data Sets:A Statistical Approach[J].International Journal of Geographical Information Science,1999,13(5):445-473.

[11] 翟仁健.基于全局一致性評價的多尺度矢量空間數(shù)據(jù)匹配方法研究[D].鄭州:信息工程大學(xué),2011.ZHAI Renjian.Research on Automated Matching Methods for Multi-scale Vector Spatial Data Based on Global Consistency Evaluation[D].Zhengzhou:Information Engineering University,2011.

[12] SAALFELD A.Conflation Automated Map Compilation[J].International Journal of Geographical Information Systems,1988,2(3):217-218.

[13] ZHANG Meng,SHI Wei,MENG Liqiu.A Generic Matching Algorithm for Line Networks of Different Resolutions[C]∥Proceedings of the 8th ICA Workshop on Generalisation and Multiple Representation.A Corua,Spain:[s.n.],2005.

[14] VOLZ S.An Iterative Approach for Matching Multiple Representations of Street Data[C]∥Proceedings of ISPRS Workshop on Multiple Representation and Interoperability of Spatial Data.Hanover,Germany:[s.n.],2006.

[15] VON G?SSELN G.A Matching Approach for the Integration,Change Detection and Adaptation of Heterogeneous Vector Data Sets[C].XXII International Cartography Conference.A Corua,Spain:The International Cartographic Association,2005.

[16] 劉海龍,錢海忠,王驍,等.采用層次分析法的道路網(wǎng)整體匹配方法[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2015,40(5):644-651.LIU Hailong,QIAN Haizhong,WANG Xiao,et al.Road Networks Global Matching Method Using Analytical Hierarchy Process[J].Geomatics and Information Science of Wuhan University,2015,40(5):644-651.

[17] 陳玉敏,龔健雅,史文中.多尺度道路網(wǎng)的距離匹配算法研究[J].測繪學(xué)報,2007,36(1):84-90.DOI:10.3321/j.issn:1001-1595.2007.01.015.CHEN Yumin,GONG Jianya,SHI Wenzhong.A Distance-based Matching Algorithm for Multi-scale Road Networks[J].Acta Geodaetica et Cartographica Sinica,2007,36(1):84-90.DOI:10.3321/j.issn:1001-1595.2007.01.015.

[18] 趙東保,盛業(yè)華.全局尋優(yōu)的矢量道路網(wǎng)自動匹配方法研究[J].測繪學(xué)報,2010,39(4):416-421.ZHAO Dongbao,SHENG Yehua.Research on Automatic Matching of Vector Road Networks Based on Global Optimization[J].Acta Geodaetica et Cartographica Sinica,2010,39(4):416-421.

[19] 欒學(xué)晨,楊必勝,李秋萍.基于結(jié)構(gòu)模式的道路網(wǎng)節(jié)點匹配方法[J].測繪學(xué)報,2013,42(4):608-614.LUAN Xuechen,YANG Bisheng,LI Qiuping.Pattern-based Node Matching Approach for Road Networks[J].Acta Geodaetica et Cartographica Sinica,2013,42(4):608-614.

[20] 趙浩.城市道路分級分類網(wǎng)眼樹的提取及其應(yīng)用[D].北京:北京建筑大學(xué),2014.ZHAO Hao.Extracting and Application on the Classification of Urban Roads Mesh Tree[D].Beijing:Beijing University of Civil Engineering and Architecture,2014.

[21] 翟仁健,武芳,黃博華,等.城市道路網(wǎng)面域?qū)哟谓Y(jié)構(gòu)特征的識別與表達(dá)[J].測繪科學(xué)技術(shù)學(xué)報,2014,31(4):413-418.ZHAI Renjian,WU Fang,HUANG Bohua,et al.A Method for Recognition and Representation of Areal Hierarchy of Urban Road Networks[J].Journal of Geomatics Science and Technology,2014,31(4):413-418.

[22] 徐柱,劉彩鳳,張紅,等.基于路劃網(wǎng)絡(luò)功能評價的道路選取方法[J].測繪學(xué)報,2012,41(5):769-776.XU Zhu,LIU Caifeng,ZHANG Hong,et al.Road Selection Based on Evaluation of Stroke Network Functionality[J].Acta Geodaetica et Cartographica Sinica,2012,41(5):769-776.

[23] THOMSON R C,RICHARDSON D E.The ‘Good Continuation’ Principle of Perceptual Organization Applied to the Generalization of Road Networks[C]∥Proceedings of the 19th International Cartographic Conference.Ottawa,Canada:ICA,1999.

[24] THOMSON R C,BROOKS R.Efficient Generalisation and Abstraction of Network Data Using Perceptual Grouping[C]∥Proceedings of the 5th International Conference on GeoComputation.United Kingdom:University of Greenwich,2000.

[25] HUTTENLOCHER D P,KLANDERMAN G A,RUCKLIDGE W J.Comparing Images Using the Hausdorff Distance[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1993,15(9):850-863.

(責(zé)任編輯：宋啟凡)

Automatic Matching of Multi-scale Road Networks under the Constraints of Smaller Scale Road Meshes

PEI Hongxing,ZHAI Renjian,WU Fang,LI Jinghan,GONG Xianyong,WU Zheng

Institute of Geospatial Information,Information Engineering University,Zhengzhou 450000,China

A new method is proposed to achieve automatic matching for multi-scale roads under the constraints of the smaller scale data.Firstly,meshes should be extracted from the two different scales road data.Secondly,several basic meshes in the larger scale road network will be merged as a composite one,which will be matched with one mesh from the smaller scale road network,so that the meshes with many-to-one and one-to-one matching relationships will be matched.Thirdly,meshes from the two different scale road data with many-to-many matching relationships will be matched.Finally,road will be classified into two categories under the constraints of meshes:mesh border roads and mesh internal roads,and then matching will be done in their own categories according to the matching relationships between the two scales meshes.The results showed that roads from different scale will be more precisely matched.

multi-scale matching; road networks matching; road meshes

The National Natural Science Foundation of China(Nos.411011362；414713869)

PEI Hongxing(1991—)，male,master,majors in multi-scale representation and cartographic generalization.

ZHAI Renjian

裴洪星，翟仁健，武芳，等.小比例尺道路網(wǎng)眼約束下的多尺度道路網(wǎng)自動匹配[J].測繪學(xué)報，2017,46(6)：760-769.

10.11947/j.AGCS.2017.20160483.PEI Hongxing,ZHAI Renjian,WU Fang,et al.Automatic Matching of Multi-scale Road Networks under the Constraints of Smaller Scale Road Meshes[J].Acta Geodaetica et Cartographica Sinica,2017,46(6):760-769.DOI:10.11947/j.AGCS.2017.20160483.

P208

A

1001-1595(2017)06-0760-10

國家自然科學(xué)基金(411011362；414713869)

2016-09-29

修回日期：2017-04-06

裴洪星(1991—)，男，碩士，研究方向為多尺度表達(dá)與制圖綜合。

E-mail：15638592360@163.com

翟仁健

E-mail：chxy_zrj@163.com