基于幾何拓撲維護的導航電子地圖增量更新技術(shù)研究

摘要：導航電子地圖具有地圖顯示、位置查詢、路徑規(guī)劃、距離計算、路線引導等功能。隨著我國經(jīng)濟的快速發(fā)展和城市化進程的加快，城市的道路信息變化日新月異，實現(xiàn)導航電子地圖數(shù)據(jù)的即時、高效、快速的增量式更新是解決導航電子地圖發(fā)展瓶頸的唯一途徑。鑒于此，結(jié)合某典型增量更新案例，對導航電子地圖數(shù)據(jù)的增量更新中幾何拓撲維護進行了研究，以滿足導航技術(shù)對現(xiàn)勢性的需求。

關(guān)鍵詞：導航電子地圖""幾何拓撲""增量更新"全球定位系統(tǒng)

Research"on"Incremental"Updating"Technology"of"Navigation"Electronic"Map"Based"on"Geometric"Topology"Maintenance

ZHENG"Bo1""LI"Jun2

（1"Ditu"（Beijing）"Technology"Co.，"Ltd.，"Beijing，"100089"China;"2"Beijing"Meida"Zhida"Technology"Co.，"Ltd.，"Beijing，"100020"China）

Abstract："navigation"electronic"map"has"the"functions"of"map"display，"location"query，"path"planning，"distance"calculation，"route"guidance"and"so"on."With"the"rapid"development"of"China's"economy"and"the"acceleration"of"urbanization，"the"road"information"of"cities"is"changing"rapidly."The"only"way"to"solve"the"bottleneck"of"the"development"of"navigation"electronic"map"is"to"realize"the"real-time，"efficient"and"rapid"incremental"update"of"navigation"electronic"map"data."In"view"of"this，"combined"with"a"typical"incremental"update"case，"the"geometric"topology"maintenance"in"the"incremental"update"of"navigation"electronic"map"data"is"studied"to"meet"the"current"needs"of"navigation"technology.

Keywords："Navigation"electronic"map;"Geometric"topology;"Incremental"update;"G"lobal"positioning"system

導航電子地圖是指含有空間位置地理坐標，能夠與空間定位系統(tǒng)結(jié)合，準確引導人們或交通工具從出發(fā)地到達目的地的電子地圖及數(shù)據(jù)集[1]。導航電子地圖是導航系統(tǒng)運行的核心數(shù)據(jù)基礎(chǔ)，通常記錄著各種實體地理要素的信息及與這些要素相關(guān)的附加信息。這些數(shù)據(jù)以特定的物理存儲結(jié)構(gòu)進行保存，在導航應(yīng)用中，為用戶提供便捷的地圖顯示、路徑查詢、距離測量、行程規(guī)劃、交通規(guī)則指引和警示等多項服務(wù)，堪稱導航系統(tǒng)的靈魂和關(guān)鍵所在。用戶對導航服務(wù)的滿意度與導航電子地圖的數(shù)據(jù)更新及時性有著密切關(guān)系。導航數(shù)據(jù)的現(xiàn)勢更新速度要落后于人們對它的期望與需求，這成為了導航技術(shù)進一步發(fā)展的阻礙因素[2]。為了實現(xiàn)導航數(shù)據(jù)快速、具有時效性的更新，為用戶提供更加完善的導航服務(wù)，針對現(xiàn)實世界地理要素變化信息的導航電子地圖增量式更新具有極為現(xiàn)實的意義。

1"導航電子地圖數(shù)據(jù)更新

導航電子地圖數(shù)據(jù)更新是指將通過各種數(shù)據(jù)采集手段（車載道路采集、遙感圖像、人工"POI"采集等）獲取的最新導航電子地圖數(shù)據(jù)代替舊的導航電子地圖數(shù)據(jù)，以提高導航電子地圖數(shù)據(jù)的準確性和現(xiàn)勢性。目前，導航電子地圖數(shù)據(jù)的更新方法主要有版本式更新和增量更新兩種更新方法[3]。

（1）版本式更新是指導航電子地圖數(shù)據(jù)廠商依據(jù)最新的測繪成果，對數(shù)據(jù)進行整理與轉(zhuǎn)換，生成符合設(shè)計要求的新導航數(shù)據(jù)集，并加工成不同形式的數(shù)據(jù)產(chǎn)品，以滿足各類用戶需求。（2）增量更新專注于導航電子地圖中發(fā)生變化的部分（新增、修改或刪除的要素），通過補測獲取變化的要素及其相關(guān)信息，進而生成包含這些變化的增量文件（即增量包）。增量更新的流程包括：生成增量文件，將其傳輸至用戶終端（增量傳輸），用戶將增量文件與原有導航電子地圖數(shù)據(jù)進行整合（增量融合），最終形成更新后的地圖數(shù)據(jù)。

相比于版本式更新，增量更新顯著降低了用戶更新地圖數(shù)據(jù)所需的時間和成本，同時減少了數(shù)據(jù)冗余，提高了更新效率。這種模式被認為是未來導航電子地圖數(shù)據(jù)更新的主要發(fā)展方向。

2"針對導航線的幾何拓撲維護

導航電子地圖數(shù)據(jù)可以是以空間分幅、屬性分層、時間分段來進行表示的。其中，導航電子地圖中用于導航功能實現(xiàn)的道路網(wǎng)絡(luò)圖層是比較重要的地理信息圖層，對于道路網(wǎng)絡(luò)圖層，不同的公司有不同的命名。基于拓撲關(guān)系的維護主要集中于道路網(wǎng)絡(luò)圖層的構(gòu)建，即將該層中的交叉路口和路段信息抽象，并按照結(jié)點和弧段的關(guān)系進行存儲，從而生成道路圖層數(shù)據(jù)[4]，然后，將得到的路網(wǎng)拓撲結(jié)構(gòu)保存到文件中，以便下次直接使用，從而提高使用效率。

建立所有圖幅的完整拓撲關(guān)系依然具有較高的復雜性和難度，不僅耗時較長，且執(zhí)行效率較低。然而，在增量數(shù)據(jù)的拓撲維護中，這一過程可以簡化為僅針對發(fā)生變化的增量數(shù)據(jù)進行處理。具體步驟是：判斷增量標志是否為1，若為1，則需對記錄增量的更新操作執(zhí)行局部拓撲維護，重點處理變化要素與原有地理實體要素之間的關(guān)系。這種方式大大降低了更新過程的復雜性，提升了增量更新的效率，同時對其他圖幅中的數(shù)據(jù)幾乎沒有影響。

變化信息主要包括道路信息與道路節(jié)點的增加、刪除和修改，以及信息點的增刪改。道路拓寬、合并等僅涉及屬性信息的變化，通常不會對道路的圖形信息產(chǎn)生顯著影響；對于道路的新建或刪除，需要特別關(guān)注變化道路與原有道路圖層中其他要素之間的拓撲關(guān)系調(diào)整，尤其是道路節(jié)點與弧段之間的拓撲關(guān)聯(lián)變化。

2.1"單條路段的拆分

單條路段的拆分是指，由于新建道路與原有道路產(chǎn)生交叉路口，因此，在拓撲關(guān)系的維護上應(yīng)將原有道路分開成擁有一個公用結(jié)點的兩條道路。在新產(chǎn)生的兩條路段中，新結(jié)點Node_New成為原有路段被拆分后的第一條路段的尾結(jié)點，并且成為第二條路段的首結(jié)點[5]。在這樣的拆分路段更新操作過程中，其拓撲維護主要涉及結(jié)點添加和路段改變。在更新的過程中，一定要對拆分后的路段的ID進行重新指定，以防止更新后出現(xiàn)路段ID編號沖突的現(xiàn)象。對于道路ID的編號，根據(jù)相應(yīng)的規(guī)則進行記錄。之后，將拆分后的第一條路段并入到原道路首結(jié)點Node1的鄰接路段，見拓撲維護中的道路拆分圖（如圖1所示）。

2.2"新建路段的添加

在導航電子地圖中，當新路段被添加時，可能與原有導航地圖中的結(jié)點、弧段或面域產(chǎn)生相交關(guān)系。鑒于空間數(shù)據(jù)拓撲關(guān)系的復雜性，以及導航電子地圖中道路與結(jié)點數(shù)據(jù)的緊密依賴性，此處僅對新添加路段與結(jié)點之間的空間關(guān)系進行探討，而不深入分析路段與面域之間的拓撲關(guān)系。

對于新建路段的拓撲維護，首先，需要判斷新添路段與原有路段是否存在相交關(guān)系：若無相交關(guān)系，則進一步檢查是否存在結(jié)點重合的情況；如果新添路段與舊有路段不相交但存在重合結(jié)點，則將該重合結(jié)點設(shè)為新添路段的首結(jié)點，并將新添路段整合進該結(jié)點的鄰接關(guān)系中，同時對新添路段的路段屬性和尾結(jié)點進行分配；若既無相交關(guān)系也無重合結(jié)點，則將新添路段的首點設(shè)為一個新結(jié)點，并將該路段整合至新結(jié)點的鄰接關(guān)系中，同時分配該路段的尾結(jié)點及相關(guān)屬性。

2.3"原有路段的刪除

刪除路段的操作比較簡單，主要是將地圖數(shù)據(jù)中的圖形數(shù)據(jù)和屬性數(shù)據(jù)表進行刪除操作即可。首先應(yīng)刪除路段所含的屬性數(shù)掘；然后，考慮刪除道路的結(jié)點是否與其他路段的結(jié)點重合：若重合，則僅刪除該結(jié)點關(guān)于刪除路段的鄰接路段信息；若無重合結(jié)點，則直接刪除多余和無用的結(jié)點即可，這可能會用到下面介紹的路段的合并的步驟。

2.4"兩條路段的合并

路段的合并主要是指在兩條道路路段相連且方向不發(fā)生大轉(zhuǎn)折的情況下的拓撲關(guān)系維護操作[6]。由于舊有道路路段廢棄或被占用，因此，舊有的道路可能存在無用的道路結(jié)點。這種情況下，該結(jié)點連接的鄰接路段的信息應(yīng)進行修改，并且刪除該結(jié)點的相關(guān)信息。將該結(jié)點鄰接的兩條道路合并成為一條，并且將兩條原路段的信息按照一定的命名規(guī)則合并成為一個，刪除無用的相關(guān)信息。路段的合并操作可以看作是路段拆分的反向操作，見拓撲維護中道路合并（如圖2所示）。

3"基于GPS數(shù)據(jù)包的增量更新

現(xiàn)有的研究成果中，對幾何拓撲增量更新的研究較多，比較成熟。以浮動車記錄的全球定位系統(tǒng)（Global"Positioning"System，GPS）數(shù)據(jù)為例，裝載于浮動車的GPS記錄了浮動車在某時刻的位置，基于大量的離散浮動車數(shù)據(jù)，可以反映道路網(wǎng)的詳細分布情況。通過設(shè)計相應(yīng)的算法，可以對大容量的離散GPS數(shù)據(jù)進行軌跡跟蹤、曲線擬合，然后和原有的道路數(shù)據(jù)進行匹配，根據(jù)不同的辨別原則，區(qū)分是新增、刪除還是改造的道路數(shù)據(jù)。

（1）規(guī)則一：地理底圖道路網(wǎng)之外，浮動車數(shù)據(jù)點形成明顯的道路軌跡，無相應(yīng)的道路數(shù)據(jù)匹配，即為新增道路。（2）規(guī)則二：地理地圖道路網(wǎng)上存在的道路，但是沒有浮動車數(shù)據(jù)點，即為廢棄或者限行的道路。

4"基于增量包更新的應(yīng)用案例

本實驗采用的更新數(shù)據(jù)是武漢市上百輛出租車發(fā)回來的GPS數(shù)據(jù)，其原始數(shù)據(jù)的格式為*.txt，共1"086"754條數(shù)據(jù)記錄。需要更新的地圖是湖北省武漢市的路網(wǎng)地圖，為*.shp格式。實驗中的數(shù)據(jù)處理均在MatLab中實現(xiàn)，其成果在ArcMap中顯示。將原始GPS數(shù)據(jù)導入Microsoft"Access數(shù)據(jù)庫，按GPS的數(shù)據(jù)格式給每一列賦予合適的屬性字段名。本實驗數(shù)據(jù)的屬性字段名有數(shù)據(jù)ID、車輛的ID、UTC時間、經(jīng)度坐標、緯度坐標、車輛瞬時速度、車輛瞬時方向。增量更新流程如圖3所示。

5"結(jié)語

導航電子地圖具有地圖顯示、位置查詢、路徑規(guī)劃、距離計算、路線引導等功能。隨著我國經(jīng)濟的快速發(fā)展和城市化進程的加快，道路網(wǎng)的快速更新成為迫切需求。增量式更新是解決該問題的唯一途徑，而增量更新中最為關(guān)鍵的是幾何拓撲維護，滿足導航技術(shù)對現(xiàn)勢性的需求。

參考文獻

[1]"查永超.基于眾包車輛的高精度地圖更新研究[D].北京：北京郵電大學，2023.

[2]"史雪靜.高精度地圖構(gòu)建及更新技術(shù)[J].測繪通報，2024（S1）：261-265.

[3]"周欣怡.基于多傳感器的無人車重定位與地圖更新方法研究與實現(xiàn)[D].北京：中國礦業(yè)大學，2022.

[4]"韋慶凱.封閉區(qū)域非結(jié)構(gòu)化道路數(shù)字地圖構(gòu)建及更新的研究[D].長沙：湖南大學，2021.

[5]"馮昶，杜清運，范曉宇，等.高精動態(tài)地圖基礎(chǔ)平臺眾源更新技術(shù)路線研究[J].測繪地理信息，2023，48（1）：10-15.

[6]"楊蒙蒙，江昆，溫拓樸，等.自動駕駛高精度地圖眾源更新技術(shù)現(xiàn)狀與挑戰(zhàn)[J].中國公路學報，2023，36（5）：244-259.