本文描述了為有效提高車載自導航系統(tǒng)的運行效率，所建立的一套嵌入式車載導航電子地圖。該地圖針對嵌入式系統(tǒng)運行速度低，存儲空間有限的特點對路網數據結構和表示方式進行了精簡，采用分層模式管理地圖，試驗表明該地圖可以很好地適合于車載導航系統(tǒng)。
關鍵詞：電子地圖 路網模型 汽車導航
1 引言
近些年來，車載自主導航系統(tǒng)得到了迅猛的發(fā)展，該系統(tǒng)主要是利用GPS/DR(全球定位系統(tǒng)/航位推算)導航定位器提供的位置、速度信息，以地理信息數據為平臺，實現自主導航的車輛信息系統(tǒng)，它是一種為駕駛員提供信息服務的系統(tǒng)，它主要為使用者解決三個方面的問題：目前在哪里；目的地在哪里；如何才能抵達目的地。在此基礎上，它還可以向使用者提供諸如地理環(huán)境查詢、車輛狀況報告、數字地圖更新，甚至通訊及娛樂等功能。
在這種導航系統(tǒng)中，數字地圖是車載導航系統(tǒng)的基礎，導航系統(tǒng)的絕大部分功能都必須依賴數字地圖才能夠實現。同時，并非所有數字地圖都適用于車載導航系統(tǒng)。車載自主導航系統(tǒng)特殊的軟硬件條件對數字地圖有著特殊的要求。目前，絕大多數車載導航系統(tǒng)的設計采用嵌入式系統(tǒng)方案。嵌入式系統(tǒng)是指將應用程序和操作系統(tǒng)與計算機硬件集成在一起的系統(tǒng)。簡單的說就是系統(tǒng)的應用軟件與系統(tǒng)的硬件一體化。
這種系統(tǒng)具有高度自動化，可靠性高等特點，但同時由于嵌入式系統(tǒng)硬件的處理能力限制，這種系統(tǒng)的處理能力和存儲空間非常有限，因而它對應用于車載嵌入式系統(tǒng)的電子地圖要求必須具備精練的數據結構、較高的數據處理效率，能滿足系統(tǒng)的快速反應，同時考慮導航系統(tǒng)要能實現自動躲避交通擁堵，還要求電子地圖能夠有效反映交通狀況，這就是嵌入式車載導航電子地圖。
2 嵌入式車載電子地圖模型
嵌入式車載導航電子地圖采用分層方法管理地圖數據。根據交通導航應用目標，將地圖數據可以歸類為路網層、地物層、背景層三大類。背景類層對導航應用來講，主要目的是起到地圖的美觀直觀作用，方便司機定位自己的位置，在地圖中屬于修飾類數據，其數據精度要求較低。地物類層是為用戶提供導航、尋路以及查詢目的地，是導航中必不可少的輔助數據，該類數據要求數量比較豐富，覆蓋面廣，但對數據的精度要求不高，在地圖顯示時，該類數據不是完全顯示，而是針對用戶的需求有針對性地顯示部分數據，在地圖中，地物類層內的數據間不存在相互之間的邏輯關系，但這些數據之間可以通過路網層數據建立起邏輯關系。
路網層是整個地圖的核心，車輛的定位導航完全依靠路網層來實現，該層數據的精度要求最高，同時該層地圖還必須具備完整的數學邏輯模型，該層數學邏輯模型的好壞往往就決定了整個車載導航系統(tǒng)軟件的效率高低。
路網層的數學模型描述的就是路網層中所有道路線和道路路口之間的數學邏輯關系。它需要解決兩個問題：一是正確的描述道路網絡在空間上的連通性，即拓撲關系；另一個問題是正確描述道路網絡的實際連通性，即汽車是否能夠從路網中的某條道路行駛到其他道路上去。
路網的基本元素和拓撲關系。道路交叉口、道路盡頭、或者道路屬性改變的地方的點都可以用節(jié)點來描述[1][2]，比如圖中的節(jié)點4 代表了道路②、道路③、道路④和道路⑥交匯的地方，而節(jié)點1則代表了道路②的盡頭；道路則可以用折線來描述，它實際上表述了節(jié)點與節(jié)點之間在物理上的連通關系，比如圖中道路③就表示節(jié)點3 和節(jié)點4 之間的通路；折線的形狀是可以通過轉折處的頂點(圖中黑色實心點)來描述，稱這種頂點為形值點[3]。形值點結合節(jié)點，就可以描述出道路的位置和幾何形狀了，比如圖中的道路④的位置和形狀就可以用節(jié)點4、角點i、角點ii 和節(jié)點5 來描述。
有了節(jié)點和道路，就可以描述出道路網絡的形狀、位置以及道路間在物理上的連通關系。但是，光有這些還不足以描述實際的道路網絡，因為實際的道路網絡中具有各種交通限制信息。如圖2，箭頭方向表示汽車可以沿著此方向行駛，箭頭上打×表示這個方向是禁止行駛的。則圖中道路①是兩個方向都能通行的，當車輛從道路①經過節(jié)點2 時，可以右拐進入道路②，也可以直行進入道路④，但是不能進入道路③，即此處是禁止左拐的；道路②是單行線，車輛只能沿著從節(jié)點2 到節(jié)點3 的方向行駛；道路③也是兩個方向都能通行的，而且當車輛從道路③經過節(jié)點2 時，沒有如何轉彎限制，可以右拐進入道路①，也可以直行進入道路②，也可以左拐進入道路④；道路④的情況與道路①類似。
由此可知，交通限制可以分成兩種：一種是道路本身的單行限制，另一種是交叉道口的轉彎限制。
(1) 道路本身的單行限制
為了描述道路的單行信息，采用有序節(jié)點對<首節(jié)點，尾節(jié)點>的方式來描述道路的方向性，再通過在道路的屬性中引入一個布爾變量B 的方式來描述道路是否為單行。稱這個布爾變量B 為單行標志，若此道路為單行線，則變量為TRUE（B 值為1），反之為FALSE（B 值為0）。如圖3，R1、R2 為兩種基本道路類型，R2 是單行線而R1 不是。則R1 可以用< N1，N2>來表示，且B=0，表示R1 的兩個方向都能通行；而R2 可以用< N3，N4>來表示，且B=1，表示R2 的方向是由首節(jié)點N3 指向尾節(jié)點N4，而且只有這個方向可以通行，反方向是禁行的。
(2)交叉道口的轉彎限制
采用道路有序對的形式來描述交叉道口的轉彎限制。圖4 中畫出了從道路經過節(jié)點到道路和的兩種情況：可以通行和不能通行。從R1 到R3 是不能通行的，則采用有序對[R1，R3]來描述這個轉彎限制信息，從R1 到R2 是可以通行的，不存在轉彎限制。
綜上所述，整個道路網絡可以由三個集合來描述：節(jié)點集N ，道路集R 以及轉彎限制集。
設路網為Rw ，則：
Rw = (N, R, ф)
其中，N 代表節(jié)點集；R 代表道路集合，其元素是有序對< n1, n2 >2，其中n1屬于N，n2屬于N，表示由n1到n2存在一條汽車可以行駛的有向通路。
? 代表轉彎限制集集合，其元素是有序對[r1, r2]，其中r1屬于R，r2屬于R，表示雖然r1 和r2 在地理上是相通的兩條道路，但汽車不能從道路 r1 駛向道路 r2 。
以路網結構為例，則
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é)點1、節(jié)點2、節(jié)點3、節(jié)點4、節(jié)點5；①，②，③，④分別代表道路1、道路2、道路3、道路4。
可以看到，采用這種方式的數學邏輯模型，不僅可以清楚地表示出道路之間的連接關系，而且能夠很好地描述清楚交通限制信息，并可以實現利用單線有效表示雙向行車信息。不僅能夠滿足導航的需要，還可以有效地壓縮地圖數據，提高運算效率，大大縮小地圖的存儲空間。使其成為真正的交通車載電子地圖。
3 交通車載電子地圖的應用
為對以上所描述的交通車載電子地圖的可行性進行驗證，以該方式加工了一幅北京地區(qū)（五環(huán)范圍內）的地圖，應用于一款導航器。
在該地圖上進行的尋路操作，圖中以“！”圖標表示出目的地（目的地），“小人” 圖標表示出發(fā)點（清華大學西門），圖中黑色加粗線條為最佳路徑的規(guī)劃結果（在實際系統(tǒng)中，用綠色線路代表最佳路線），圖8 為在該地圖上進行的導航引導操作。
4 結論
試驗及實際應用證明，基于本文方法建立的北京市區(qū)數字地圖信息豐富、占用空間較少、道路數據合法，可以滿足地圖縮放、漫游、地物查詢以及尋路和導航等操作，是一種高效、實用的地圖數據組織方式，適合于車載導航使用。
（轉載）
