導航電子地圖中道路網增量信息的多尺度探測

王艷慧， 尹 川， 丁宇虹

(1.首都師范大學資源環境與地理信息系統北京市重點實驗室，北京 100048;2.首都師范大學三維信息獲取與應用教育部重點實驗室，北京 100048)

向用戶提供現勢性強的多尺度導航電子地圖是移動位置服務系統的重要服務內容之一.多尺度道路網增量更新數據的內業管理和相應的更新發布方法已成為制約位置服務市場發展的瓶頸之一.而利用最新的大比例尺地圖依次更新中、小比例尺地圖的多尺度地圖協同縮編更新作為當前國際GIS界研究的熱點問題之一［1］，為多尺度導航電子地圖更新提供了可供參考的思路.目前縮編更新主要存在4種模式:直接縮編替代更新、直接縮編疊加更新、增量縮編更新、新舊數據疊加縮編更新［2-3］，相關研究結合不同的應用領域和生產條件，分別選擇了不同的更新模式，并針對增量數據提取與更新操作等問題展開研究［2-8］.但這些研究一般都是針對兩個特定的比例尺，沒有考慮增量變化信息在不同比例尺序列之間的傳遞及其對多尺度協同更新效率和精度的影響.對采用縮編增量信息來更新舊的小比例尺矢量空間數據(尤其是線狀目標)的方法鮮有涉及，該方法理論上具有更新效率高、延續性強、一致性維護方便等特點，更符合位置服務中多尺度導航電子地圖的縮編更新需求.

基于上述考慮，本文擬以導航電子地圖中的主要地理框架要素——道路網要素作為主要研究對象，研究用增量多尺度縮編協同更新模式解決客戶端多尺度空間數據動態同步更新問題的關鍵技術，實現增量數據以“打補丁”的方式融合到客戶端中，為提高服務器端和客戶端多尺度空間數據庫協同更新的效率和精度，提供相應的技術參考.

1 研究方法

常規基礎地圖制圖及更新一般重點關注路網要素幾何表達，而導航電子地圖更關注路網要素的拓撲表達.針對位置服務中由道路網新建、拓寬、合并以及廢棄等物理變化引起的變化、新增、刪除等數據庫操作，基于增量信息的道路網多尺度縮編更新實質是采用“差文件”(新舊數據集之差，即增量數據集)思想，將各級比例尺下的增量變化信息以“打補丁”方式融合到客戶端各級比例尺數據集中，從而實現數據集內容的一致性.其需要解決的實際問題是聯動提取各級比例尺不同版本數據集之間的“差文件”，將“差文件”以可靠的精度“打補丁”入庫融合，并保證幾何、屬性和拓撲數據的一致性和同步性.故此處的增量縮編更新處理過程可簡化為增量信息提取、增量信息縮編融合及協調.

總體技術流程為:初始數據包括時刻t0比例尺為S1和S2的道路數據、時刻t1比例尺為S2的道路數據(t1＞t0、S1＞S2).若某時刻某一比例尺下的路網目標表達信息用F(t，S)表示，則增量更新主要包含兩個環節:增量信息的提取與縮編傳遞.

首先，針對常用增量信息提取方法中基于經驗閾值確定新舊目標匹配的不足，提出采用基于最大類間方差法自適應確定幾何匹配閾值進而探測增量信息，并利用式(1)識別不同時刻同一比例尺道路數據的增量信息ΔF(t1，S1)，

其次，基于文獻［9］提出的多比例尺表達目標之間的內連規則，搜尋變化目標對應的目標比例尺的匹配要素，利用插入、刪除等數據庫操作算子把增量信息集MyUpdateClass中的目標變化信息(ΔF(t1，S1))逐一映射到舊的對應小比例尺數據中，對新產生的數據集重新構建拓撲，并按照目標比例尺S2下的路網選取規則，即基于自適應網眼密度的增量信息選取規則，得到目標比例尺S2下現勢性較好的時刻t1的數據.以此類推，一旦增量信息可在不同比例尺之間融合，即可實現它在不同比例尺之間的傳遞.

為驗證上述方法的可行性，本文實驗測試數據源選取某地開發區2007年(時刻t0)和2010年(時刻t1)的1∶10000(比例尺S1)、2007 年1∶50000(比例尺S2)道路網矢量數據，并在前期數據預處理中基于層次語義匹配規則［9］，已建立了同一時態下數據源中的道路目標與需要更新的其它比例尺地圖中道路目標之間的映射關系.insert、delete和update數據庫操作算子也均已在前期研究中實現［10-11］.下文將重點剖析增量探測和增量信息融合的技術原理及實現細節.

2 路網增量更新信息的探測

增量信息的識別和提取其實是一個目標匹配的過程，匹配精度會直接影響數據更新的準確率.針對路網線狀要素，以目標匹配為基礎提取更新信息的研究也很多.例如，文獻［12-14］基于面積疊置率計算兩條線目標的相似度，即通過比較兩個道路緩沖區的相互重疊部分的面積占各自總面積的比值與給定閾值的大小關系來探測可能的匹配線對.其中多數學者都是根據制圖經驗來設定某個相對合理的數值作為閾值，而經驗閾值沒有考慮不同區域數據集的具體差別，匹配結果在一定程度上存在自適應性弱、誤差較大、精度相對較低的缺點［15］.

因此，根據圖像閾值分割灰度直方圖與數據更新前后路段緩沖區面積迭置率灰度直方圖表現出的高度吻合性.本文研究基于最大類間方差Ostu閾值分割算法來實現目標匹配閾值自適應精確計算的方法，嘗試在避免幾何數據的各種復雜統計量計算情況下，快速構建有效的候選匹配目標集，避免常用經驗閾值選取時的精度干擾.

2.1 基本原理與流程

基于Ostu快速構建候選匹配集，進而再采用幾何匹配算法，根據各種幾何、度量、拓撲統計量的組合判斷置信度最高的匹配對，進而從新版本中篩選出與舊版本相匹配的目標集，余下的“差文件”即為所要提取的該比例尺下的增量信息.具體算法流程為:計算同一較大比例尺下兩個不同時態的數據集中要素的面積迭置率，根據面積迭置率集合反映的灰度直方圖.利用Ostu法算出適合該數據集的最佳閾值e，以此為判據逐一探測幾何變化，即遍歷同一較大比例尺不同時刻路網要素表達的目標，對目標以一定寬度建立緩沖區，判斷緩沖區面積迭置率Ssim(Li，Oi)與幾何匹配閾值e的關系，

如果Ssim(Li，Oi)大于給定閾值，則說明兩目標關聯，則可再根據與之關聯的要素個數及Ssim(Li，Oi)值具體確定其變化類型，提取相應的變化信息.確定了匹配的目標集后，再比較目標屬性的變化，提取幾何和屬性變化信息.

2.2 基于Ostu法的類間方差閾值計算

Ostu法又稱為或大津閾值分割法，是圖像分割領域的一種常用算法.它假設圖像的灰度直方圖是由對應目標和背景的兩個單峰的直方圖混合構成，如果二者大小很接近，均值相差較大，且均方差足夠小，則其直方圖表現為較明顯的雙峰，如圖1(a)所示.Ostu法適用于區分其背景與目標，且可使圖像錯分概率最小，而最佳閾值是使兩個數據集的差異達到最大值［15］.

根據前期不同研究區不同數據集的大量實驗研究，發現更新前后道路面積迭置率按大小排序生成的數據集合的灰度直方圖(圖1(b))與通常的圖像閾值分割灰度直方圖(如圖1(a)所示)表現出高度的吻合性，據此提出用Ostu圖像分割的閾值計算方法來實現目標匹配閾值精確計算.

圖1 閾值化法圖像分割Fig.1 Histogram distributions of the thresholding-based image segmentation

如圖1(b)所示的一個研究區測算結果，橫坐標表示面積疊置率，縱坐標表示面積疊置率取值的累計個數，可以看出數據呈明顯的雙峰分布，中間部分出現了一個較明顯的峰谷拐點.進一步與實際數據比對，發現疊置率取值在拐點前的要素是由多條相交線段結點緩沖區重合引起的疊加分析誤差及地圖數據本身的誤差造成.疊置要素之間不存在匹配關系，而疊置率取值在拐點后的要素則由存在匹配關系的兩條線要素造成此分布特征.由此可以推斷該數據集存在兩類情況:一類為由非匹配關系產生的冗余數據，另一類為由匹配關系產生的有效匹配數據.因此，根據不同要素集表現出的疊置率直方圖分布特征，可用Ostu法計算出直方圖的分割閾值作為此要素集幾何匹配的最佳閾值，把圖像(待匹配數據集)的目標信息(匹配要素)和背景信息(非匹配要素)區分開來，從而達到根據不同數據集自身結構特點縮小候選匹配目標集合、提高幾何匹配精度的目的.

2.3 實驗驗證

根據前文方法與某典型研究區數據源，進行目標匹配時先建立道路網拓撲關系，進行斷鏈處理，然后度量面積疊置率，判斷道路是否存在幾何匹配關系.當緩沖區面積疊置率大于Ostu法所得閾值時，認為路段存在幾何匹配關系.并以人工匹配為參照，在不同閾值下抽樣統計不同條數的道路，驗證匹配準確率.如表1所示，選取不同的實驗閾值t，對應的匹配準確率也不相同，而采用本文Ostu法計算得到的閾值(t=29)時，無論是與經驗閾值(t=30)相比，還是與其它隨機選配閾值相比，匹配準確率均較高.由此可判斷t=29為當前條件下的最佳閾值.

表1 不同閾值匹配精度Tab.1 Matching accuracy at different thresholds

為驗證該方法的有效性和可行性，利用增補4個研究區的樣本數據進行目標匹配準確度比較.計算結果表明匹配準確率在87% ～91%之間，均優于傳統經驗閾值匹配精度.

3 增量信息的多尺度縮編傳遞

由于新增道路信息中可能包含低等級道路，相對于小比例尺制圖需求，可能存在許多不符合目標比例尺要求的冗余數據，需予以舍棄.選取數量、選取目標及選取道路的合理性和有效性，都是增量信息縮編更新過程中需要研究的問題.因此，本文考慮增量路段在整個目標比例尺圖幅中的重要程度以及圖幅負載量的總體控制，模擬縮編更新過程中人的思維過程，完善基于道路網眼密度的增量路段漸進式選取算法.

3.1 基本原理與流程

基于層次語義匹配規則［9］，建立源比例尺與目標比例尺地圖中各路網目標之間的映射關系.基于遺傳算法、連通性、網眼密度等道路選取方法［3，8］，經驗證存在不能表達出不同區域的路網密度差異、難以用于復雜路網環境、本身算法較為復雜［16］的問題.因此，本文借鑒和集成擴展現有方法，綜合考慮道路等級、長度、連通性、網眼面積、道路密度、是否為懸掛鏈等選取因素，分析相互之間的聯系及優先順序，以網眼作為選取單元，以網眼密度作為衡量路段密集程度的依據.根據不同的區域密度設置不同的網眼密度，逐級選出適合目標比例尺的路網增量目標，在此基礎上，實現多尺度變化信息不同尺度之間的垂直傳播和無縫融合.

圖2所示為縮編流程，逐一遍歷較大比例尺的增量數據文件包中的路網要素.若它為變化(刪除、幾何或屬性變更)道路，則所有較小比例尺下與之對應的路網表達目標都要做出相應更改;若它是新增加的道路，則所有較小比例尺上的對應位置都增加該道路，從而達到聯動更新的目的.當然，在此過程中，部分增量信息可能由于重要性較低而難以在小比例尺地圖上表達出來，因此，還需基于網眼密度漸進式循環迭判，逐一剝離重要程度最低的道路.使得每次循環在滿足網眼密度條件的情況下刪除該區域內重要性最低的道路［16］，并完成與鄰接網眼的合并.

3.2 路網增量目標自動選取密度閾值的確定

運用網眼密度來進行路網增量目標的縮編選取，關鍵是確定密度閾值.與目標幾何匹配閾值的設定類似，傳統方法采用制圖比例尺規范中最小制圖分辨率作為經驗閾值，雖具有通用性，但沒有考慮不同區域道路網數據集的具體分布狀況，針對性較低.因此，為了體現不同區域的路網密度差別，本文借鑒樣圖統計法［3-4］，根據不同等級道路網的網眼密度分布趨勢來動態調整密度閾值.即針對不同研究區的數據源，以網眼邊界上路段的最低等級為標準，將網眼分成不同類型，對不同等級類型的網眼設置不同的密度閾值，分別統計分析研究區內相同等級路網密度及對應道路網條數的分布規律，據此確定不同道路等級的網眼密度閾值.

圖3(a)和(b)分別為研究區2010年1∶10000和1∶50000主干道和支干道的網眼密度分布圖.圖3(a)兩條線的走勢大致相同，說明1∶10000地圖的主干道路在1∶50000地圖中多數被保留下來.同時根據1∶50000地圖制圖規范的要求，人眼能夠分辨的最大密度為0.074 m/m2，故以此作為主干道選取閾值.圖3(b)兩條線走勢差別較大，在密度0.010 ～0.350 之間，相同網眼密度下1∶10000地圖的路網數目小于1∶50000地圖的路網數目，其原因是較大比例尺下網眼合并后，密度較小的網眼增多;而在0.350～0.074之間則相反，相同網眼密度下1∶10000地圖的路網數目大于1∶50000地圖的網眼數目，同樣是由于在較大比例尺下刪除路段合并了網眼，導致網眼減少，密度同時變小.分界線在兩條線的交點0.038 m/m2處，小比例尺制圖需 選取密度大于此值的路網目標，即此值為密度閾值.

圖2 增量信息多尺度縮編更新流程Fig.2 Flowchart of multi-scale generalization for incremental information

3.3 實驗驗證

在 Windows 7/CPU 1.25 GHz、ArcGIS Engine SDK/Visual Studio.NET 2008環境下，進行增量信息的縮編提取.增量文件包中共有路段234條(見圖4)，結點數14458個，整個實驗用時823 s.用更新得到的1∶50000新數據(圖5(a))，與已有的2010年1∶50000現勢數據進行對比(圖5(b))，重要度較高的高等級路網目標全部選中，可以滿足路網數據更新的結構選取需求.與2.3節增量探測相對應，增補其它4組樣區的實驗，并定量論證了多尺度組合探測增量選取算法的可行性.

圖3 道路網眼密度分布Fig.3 Mesh density distributions of roads

圖4 增量數據Fig.4 The incremental representation data

圖5 更新的1∶50000地圖及對應的現勢1∶50000地圖Fig.5 The updated and the corresponding current 1∶50000 maps

4 結束語

基于多尺度縮編協同更新模式，實現多尺度道路網增量數據的提取和融合是導航電子地圖更新的研究熱點之一.本文提出基于Ostu法計算最佳閾值進而探測增量目標，并基于不同等級道路網的網眼密度分布趨勢動態調整密度閾值，完善了基于道路網眼密度的增量變化目標漸進式選取算法.通過實驗驗證了該方法的可行性，為聚焦候選匹配目標集及提高增量縮編更新精度提供了可行的技術參考.本研究未考慮道路網與電子地圖中其它興趣點(例如居民點)的連通情況，對可能是通向居民點唯一道路的特殊情況未進行特殊處理;且當兩個數據集的面積疊置率直方圖存在差異較大的峰谷時，有必要更客觀地定義選取規則，進一步增強算法的實用性.

［1］YE Y，CHEN B，WAN B，et al.MMS-IU model for incremental update of spatial database:geo-informatics in resource management and sustainable ecosystem［M］.Berlin:Springer Heidelberg，2013:359-370.

［2］陳軍，胡云崗，趙仁亮，等.道路數據縮編更新的自動綜合方法研究［J］.武漢大學學報:信息科學版，2007，32(11):1022-1027.CHEN Jun，HU Yungang，ZHAO Renliang，et al.Road data updating based on map generalization［J］.Geomatics and Information Science of Wuhan University，2007，32(11):1022-1027.

［3］胡云崗，陳軍，李志林，等.基于網眼密度的道路選取方法［J］.測繪學報，2007，36(3):351-357.HU Yungang，CHEN Jun，LI Zhilin，et al.Selective omission of road features based on mesh density for digitalmap generalization［J］.Acta Geodaetica et Cartographica Sinica，2007，36(3):351-357.

［4］趙彬彬.多尺度矢量地圖空間目標匹配方法及其應用研究［D］.長沙:中南大學，2011.

［5］GAVRILA D M， BAYESIAN A. Exemplar-based approach to hierarchical shape matching［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29(8):1-14.

［6］SAMAL A，SETH S，CUETO K.A feature-based approach to conflation of geospatial sources［J］.International Journal of Geographical Information Science，2004，18(5):459-489.

［7］鄧敏，徐凱，趙彬彬，等.基于結構化空間關系信息的結點層次匹配方法［J］.武漢大學學報:信息科學版，2010，35(8):913-917.DENG Min， XU Kai， ZHAO Binbin， etal. A hierarchical approach for nodes matching based on structural spatial relations［J］. Geomatics and Information Science ofWuhan University， 2010，35(8):913-917.

［8］鄧紅艷，武芳，翟仁建，等.基于遺傳算法的道路網綜合模型［J］.武漢大學學報:信息科學版，2006，31(2):164-167.DENG Hongyan，WU Fang，ZHAI Renjian，et al.A generalization model of road networks based on genetic algorithm［J］.Geomatics and Information Science of Wuhan University，2006，31(2):164-167.

［9］王艷慧，李小娟，劉曉萌.路網要素多尺度表達目標的層次關系分析［J］.中國圖象圖形學報，2007，12(8):1451-1456.WANG Yanhui， LI Xiaojuan， LIU Xiaomeng. On hierarchical relation among road multi-scale representation［J］. Journal of Image and Graphics，2007，12(8):1451-1456.

［10］尹川.導航電子地圖更新中道路網增量信息的提取與發布［D］.北京:首都師范大學，2012.

［11］丁宇紅.導航電子地圖中道路網增量縮編更新信息的提取［D］.北京:首都師范大學，2013.

［12］應申，李霖，劉萬增，等.版本數據庫中基于目標匹配的變化信息提取與數據更新［J］.武漢大學學報:信息科學版，2009，34(6):752-755.YING Shen，LI Lin，LIU Wanzeng，et al.Changeonly updating based on object matching in version databases［J］.Geomatics and Information Science of Wuhan University，2009，34(6):752-755.

［13］QIAN H Z，ZHU Q，GUO M，et al.Oriented road network macrostructure matching algorithm［J］.Physical and Numerical Simulation of Geotechnical Engineering，2011，3:18-21.

［14］MASUYAMA A. Methodsfordetectingapparent differences between spatial tessellations at different time points［J］.International Journal of Geographical Information Science，2006，20(6):633-648.

［15］尹川，王艷慧.路網增量更新中基于OSTU的目標幾何匹配閾值計算［J］.武漢大學學報:信息科學版，2014，39(9):1061-1067.YIN Chuan， WANG Yanhui. Targetgeometry matching threshold in incremental updating of road network based on OSTU［J］. Geomatics and Information Science ofWuhan University， 2014，39(9):1061-1067.

［16］張小朋，尹路明，王鵬波，等.地圖數據縮編更新中的道路自動選取研究［J］.測繪工程，2012，21(5):13-16.ZHANG Xiaopeng，YIN Luming，WANG Pengbo，et al.A study of road automatic selection in map data generalization based updating［J］. Engineering of Surveying and Mapping，2012，21(5):13-16.