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

關(guān)鍵詞：導(dǎo)航電子地圖""幾何拓?fù)?"增量更新"全球定位系統(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

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

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

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

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

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

2"針對(duì)導(dǎo)航線的幾何拓?fù)渚S護(hù)

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

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

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

2.1"單條路段的拆分

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

2.2"新建路段的添加

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

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

2.3"原有路段的刪除

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

2.4"兩條路段的合并

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

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

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

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

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

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

5"結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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