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