本文描述了為有效提高車載自導(dǎo)航系統(tǒng)的運(yùn)行效率，所建立的一套嵌入式車載導(dǎo)航電子地圖。該地圖針對(duì)嵌入式系統(tǒng)運(yùn)行速度低，存儲(chǔ)空間有限的特點(diǎn)對(duì)路網(wǎng)數(shù)據(jù)結(jié)構(gòu)和表示方式進(jìn)行了精簡(jiǎn)，采用分層模式管理地圖，試驗(yàn)表明該地圖可以很好地適合于車載導(dǎo)航系統(tǒng)。

關(guān)鍵詞：電子地圖 路網(wǎng)模型 汽車導(dǎo)航

1 引言

近些年來，車載自主導(dǎo)航系統(tǒng)得到了迅猛的發(fā)展，該系統(tǒng)主要是利用GPS/DR(全球定位系統(tǒng)/航位推算)導(dǎo)航定位器提供的位置、速度信息，以地理信息數(shù)據(jù)為平臺(tái)，實(shí)現(xiàn)自主導(dǎo)航的車輛信息系統(tǒng)，它是一種為駕駛員提供信息服務(wù)的系統(tǒng)，它主要為使用者解決三個(gè)方面的問題：目前在哪里；目的地在哪里；如何才能抵達(dá)目的地。在此基礎(chǔ)上，它還可以向使用者提供諸如地理環(huán)境查詢、車輛狀況報(bào)告、數(shù)字地圖更新，甚至通訊及娛樂等功能。

在這種導(dǎo)航系統(tǒng)中，數(shù)字地圖是車載導(dǎo)航系統(tǒng)的基礎(chǔ)，導(dǎo)航系統(tǒng)的絕大部分功能都必須依賴數(shù)字地圖才能夠?qū)崿F(xiàn)。同時(shí)，并非所有數(shù)字地圖都適用于車載導(dǎo)航系統(tǒng)。車載自主導(dǎo)航系統(tǒng)特殊的軟硬件條件對(duì)數(shù)字地圖有著特殊的要求。目前，絕大多數(shù)車載導(dǎo)航系統(tǒng)的設(shè)計(jì)采用嵌入式系統(tǒng)方案。嵌入式系統(tǒng)是指將應(yīng)用程序和操作系統(tǒng)與計(jì)算機(jī)硬件集成在一起的系統(tǒng)。簡(jiǎn)單的說就是系統(tǒng)的應(yīng)用軟件與系統(tǒng)的硬件一體化。

這種系統(tǒng)具有高度自動(dòng)化，可靠性高等特點(diǎn)，但同時(shí)由于嵌入式系統(tǒng)硬件的處理能力限制，這種系統(tǒng)的處理能力和存儲(chǔ)空間非常有限，因而它對(duì)應(yīng)用于車載嵌入式系統(tǒng)的電子地圖要求必須具備精練的數(shù)據(jù)結(jié)構(gòu)、較高的數(shù)據(jù)處理效率，能滿足系統(tǒng)的快速反應(yīng)，同時(shí)考慮導(dǎo)航系統(tǒng)要能實(shí)現(xiàn)自動(dòng)躲避交通擁堵，還要求電子地圖能夠有效反映交通狀況，這就是嵌入式車載導(dǎo)航電子地圖。

2 嵌入式車載電子地圖模型

嵌入式車載導(dǎo)航電子地圖采用分層方法管理地圖數(shù)據(jù)。根據(jù)交通導(dǎo)航應(yīng)用目標(biāo)，將地圖數(shù)據(jù)可以歸類為路網(wǎng)層、地物層、背景層三大類。背景類層對(duì)導(dǎo)航應(yīng)用來講，主要目的是起到地圖的美觀直觀作用，方便司機(jī)定位自己的位置，在地圖中屬于修飾類數(shù)據(jù)，其數(shù)據(jù)精度要求較低。地物類層是為用戶提供導(dǎo)航、尋路以及查詢目的地，是導(dǎo)航中必不可少的輔助數(shù)據(jù)，該類數(shù)據(jù)要求數(shù)量比較豐富，覆蓋面廣，但對(duì)數(shù)據(jù)的精度要求不高，在地圖顯示時(shí)，該類數(shù)據(jù)不是完全顯示，而是針對(duì)用戶的需求有針對(duì)性地顯示部分?jǐn)?shù)據(jù)，在地圖中，地物類層內(nèi)的數(shù)據(jù)間不存在相互之間的邏輯關(guān)系，但這些數(shù)據(jù)之間可以通過路網(wǎng)層數(shù)據(jù)建立起邏輯關(guān)系。

路網(wǎng)層是整個(gè)地圖的核心，車輛的定位導(dǎo)航完全依靠路網(wǎng)層來實(shí)現(xiàn)，該層數(shù)據(jù)的精度要求最高，同時(shí)該層地圖還必須具備完整的數(shù)學(xué)邏輯模型，該層數(shù)學(xué)邏輯模型的好壞往往就決定了整個(gè)車載導(dǎo)航系統(tǒng)軟件的效率高低。

路網(wǎng)層的數(shù)學(xué)模型描述的就是路網(wǎng)層中所有道路線和道路路口之間的數(shù)學(xué)邏輯關(guān)系。它需要解決兩個(gè)問題：一是正確的描述道路網(wǎng)絡(luò)在空間上的連通性，即拓?fù)潢P(guān)系；另一個(gè)問題是正確描述道路網(wǎng)絡(luò)的實(shí)際連通性，即汽車是否能夠從路網(wǎng)中的某條道路行駛到其他道路上去。

路網(wǎng)的基本元素和拓?fù)潢P(guān)系。道路交叉口、道路盡頭、或者道路屬性改變的地方的點(diǎn)都可以用節(jié)點(diǎn)來描述[1][2]，比如圖中的節(jié)點(diǎn)4 代表了道路②、道路③、道路④和道路⑥交匯的地方，而節(jié)點(diǎn)1則代表了道路②的盡頭；道路則可以用折線來描述，它實(shí)際上表述了節(jié)點(diǎn)與節(jié)點(diǎn)之間在物理上的連通關(guān)系，比如圖中道路③就表示節(jié)點(diǎn)3 和節(jié)點(diǎn)4 之間的通路；折線的形狀是可以通過轉(zhuǎn)折處的頂點(diǎn)(圖中黑色實(shí)心點(diǎn))來描述，稱這種頂點(diǎn)為形值點(diǎn)[3]。形值點(diǎn)結(jié)合節(jié)點(diǎn)，就可以描述出道路的位置和幾何形狀了，比如圖中的道路④的位置和形狀就可以用節(jié)點(diǎn)4、角點(diǎn)i、角點(diǎn)ii 和節(jié)點(diǎn)5 來描述。

有了節(jié)點(diǎn)和道路，就可以描述出道路網(wǎng)絡(luò)的形狀、位置以及道路間在物理上的連通關(guān)系。但是，光有這些還不足以描述實(shí)際的道路網(wǎng)絡(luò)，因?yàn)閷?shí)際的道路網(wǎng)絡(luò)中具有各種交通限制信息。如圖2，箭頭方向表示汽車可以沿著此方向行駛，箭頭上打×表示這個(gè)方向是禁止行駛的。則圖中道路①是兩個(gè)方向都能通行的，當(dāng)車輛從道路①經(jīng)過節(jié)點(diǎn)2 時(shí)，可以右拐進(jìn)入道路②，也可以直行進(jìn)入道路④，但是不能進(jìn)入道路③，即此處是禁止左拐的；道路②是單行線，車輛只能沿著從節(jié)點(diǎn)2 到節(jié)點(diǎn)3 的方向行駛；道路③也是兩個(gè)方向都能通行的，而且當(dāng)車輛從道路③經(jīng)過節(jié)點(diǎn)2 時(shí)，沒有如何轉(zhuǎn)彎限制，可以右拐進(jìn)入道路①，也可以直行進(jìn)入道路②，也可以左拐進(jìn)入道路④；道路④的情況與道路①類似。

由此可知，交通限制可以分成兩種：一種是道路本身的單行限制，另一種是交叉道口的轉(zhuǎn)彎限制。

(1) 道路本身的單行限制

為了描述道路的單行信息，采用有序節(jié)點(diǎn)對(duì)<首節(jié)點(diǎn)，尾節(jié)點(diǎn)>的方式來描述道路的方向性，再通過在道路的屬性中引入一個(gè)布爾變量B 的方式來描述道路是否為單行。稱這個(gè)布爾變量B 為單行標(biāo)志，若此道路為單行線，則變量為TRUE（B 值為1），反之為FALSE（B 值為0）。如圖3，R1、R2 為兩種基本道路類型，R2 是單行線而R1 不是。則R1 可以用< N1，N2>來表示，且B=0，表示R1 的兩個(gè)方向都能通行；而R2 可以用< N3，N4>來表示，且B=1，表示R2 的方向是由首節(jié)點(diǎn)N3 指向尾節(jié)點(diǎn)N4，而且只有這個(gè)方向可以通行，反方向是禁行的。

(2)交叉道口的轉(zhuǎn)彎限制

采用道路有序?qū)Φ男问絹砻枋鼋徊娴揽诘霓D(zhuǎn)彎限制。圖4 中畫出了從道路經(jīng)過節(jié)點(diǎn)到道路和的兩種情況：可以通行和不能通行。從R1 到R3 是不能通行的，則采用有序?qū)?/SPAN>[R1，R3]來描述這個(gè)轉(zhuǎn)彎限制信息，從R1 到R2 是可以通行的，不存在轉(zhuǎn)彎限制。

綜上所述，整個(gè)道路網(wǎng)絡(luò)可以由三個(gè)集合來描述：節(jié)點(diǎn)集N ，道路集R 以及轉(zhuǎn)彎限制集。

設(shè)路網(wǎng)為Rw ，則：

Rw = (N, R, ф)

其中，N 代表節(jié)點(diǎn)集；R 代表道路集合，其元素是有序?qū)?/SPAN>< n1, n2 >2，其中n1屬于N，n2屬于N，表示由n1到n2存在一條汽車可以行駛的有向通路。

? 代表轉(zhuǎn)彎限制集集合，其元素是有序?qū)?/SPAN>[r1, r2]，其中r1屬于R，r2屬于R，表示雖然r1 和r2 在地理上是相通的兩條道路，但汽車不能從道路 r1 駛向道路 r2 。

以路網(wǎng)結(jié)構(gòu)為例，則

Rw = (N, R, ф)

其中N = {1，2，3，4，5}；

R = {①，②，③，④}

其中①=<1，2>且B1 = 0，

②=<2，3>且B2 = 1，

③=<2，4>且B3 = 0，

④=<2，5>且B4 = 0；

ф = {[①，③]，[④，②]}

上式中：1，2，3，4，5 分別代表節(jié)點(diǎn)1、節(jié)點(diǎn)2、節(jié)點(diǎn)3、節(jié)點(diǎn)4、節(jié)點(diǎn)5；①，②，③，④分別代表道路1、道路2、道路3、道路4。

可以看到，采用這種方式的數(shù)學(xué)邏輯模型，不僅可以清楚地表示出道路之間的連接關(guān)系，而且能夠很好地描述清楚交通限制信息，并可以實(shí)現(xiàn)利用單線有效表示雙向行車信息。不僅能夠滿足導(dǎo)航的需要，還可以有效地壓縮地圖數(shù)據(jù)，提高運(yùn)算效率，大大縮小地圖的存儲(chǔ)空間。使其成為真正的交通車載電子地圖。

3 交通車載電子地圖的應(yīng)用

為對(duì)以上所描述的交通車載電子地圖的可行性進(jìn)行驗(yàn)證，以該方式加工了一幅北京地區(qū)（五環(huán)范圍內(nèi)）的地圖，應(yīng)用于一款導(dǎo)航器。

在該地圖上進(jìn)行的尋路操作，圖中以“！”圖標(biāo)表示出目的地（目的地），“小人” 圖標(biāo)表示出發(fā)點(diǎn)（清華大學(xué)西門），圖中黑色加粗線條為最佳路徑的規(guī)劃結(jié)果（在實(shí)際系統(tǒng)中，用綠色線路代表最佳路線），圖8 為在該地圖上進(jìn)行的導(dǎo)航引導(dǎo)操作。

4 結(jié)論

試驗(yàn)及實(shí)際應(yīng)用證明，基于本文方法建立的北京市區(qū)數(shù)字地圖信息豐富、占用空間較少、道路數(shù)據(jù)合法，可以滿足地圖縮放、漫游、地物查詢以及尋路和導(dǎo)航等操作，是一種高效、實(shí)用的地圖數(shù)據(jù)組織方式，適合于車載導(dǎo)航使用。

（轉(zhuǎn)載）