【導(dǎo)讀】嚴峻的交通和環(huán)境污染問題。智能交通系統(tǒng)的開發(fā)和應(yīng)用對緩解和改善城市交通狀況、促進行車安全和提高道路的通行效率具有重要意義。中一個重要的組成部分，由車載移動終端、無線通信鏈路和車輛監(jiān)控中心三個部分組成。3S技術(shù)的應(yīng)用是車載導(dǎo)航系統(tǒng)功能實現(xiàn)的重要基礎(chǔ)。了GPS及GIS的工作原理。通過分析GPS接收機的數(shù)據(jù)格式，研究了GPS數(shù)據(jù)的采集和處理。論文探討了車載電子地圖的設(shè)計與制作過程，探討了簡單電子地圖功能，如電子。地圖的放大、縮小、漫游、距離和面積的量測等的實現(xiàn)方法。論文重點研究了地圖匹配

　　

【正文】 地圖信息系統(tǒng)的基礎(chǔ)和關(guān)鍵。 要建立用于汽車導(dǎo)航的數(shù)字電子地圖信息系統(tǒng)必須 : （ 1） 將紙質(zhì)地圖矢量化，建立圖形數(shù)據(jù)庫。 （ 2） 建立導(dǎo)航數(shù)據(jù)庫和屬性數(shù)據(jù)庫。 （ 3） 建立圖形數(shù)據(jù)庫、導(dǎo)航數(shù)據(jù)庫、屬性數(shù)據(jù)庫之間的聯(lián)系。 紙質(zhì)地圖的矢量化可采用數(shù)字化儀、掃描儀將紙質(zhì)地圖數(shù)字化成數(shù)字地圖 ，再用手 23 工或采用專用的軟件矢量化成顯示用的數(shù)字電子地圖。目前，都是采用掃描儀和專用軟件來進行地圖的矢量化。 電子地圖系統(tǒng)的組成 電子地圖系統(tǒng)由硬件和軟件兩大部分組成，如下圖所示： 圖： 電子地圖系統(tǒng)組成 地圖數(shù)據(jù)源為系統(tǒng)提供信息，它主要包括市區(qū)交通地圖和相關(guān)地圖數(shù)據(jù)文件 。 地圖輸入設(shè)備負責從地圖數(shù)據(jù)源中采集各種數(shù)據(jù)，采集的數(shù)據(jù)經(jīng)編輯、格式轉(zhuǎn)換等處理后存儲到地圖數(shù)據(jù)庫中 .輸入設(shè)備主要是掃描儀和數(shù)字化儀 。 地圖輸出設(shè)備主要用于 顯示地圖，常用的是計算機顯示器等 。 地圖數(shù)據(jù)庫是本系統(tǒng)的核心，它是按一定結(jié)構(gòu)存在磁盤上的地圖數(shù)據(jù)集，是系統(tǒng)分析處理的重要對象 。 控制軟件是系統(tǒng)的主體，負責控制調(diào)整整個系統(tǒng)的運行 。 地圖掃描和矢量化 地圖掃描采用光柵掃描的方法，所用軟件可為 等，采用掃描儀進行 ，并且 根據(jù)地圖的印刷質(zhì)量作相應(yīng)的調(diào)整。掃描后，為了減少文件存儲量的大小，采用 Index Color 方式將圖象格式轉(zhuǎn)換為 256 色，采用該方式，可以減少約三分之二的存儲量，最后將圖象以不壓縮的 TIFF 方式存儲。 數(shù) 據(jù)庫的建立 路網(wǎng)數(shù)據(jù)庫的建立 通過建立路網(wǎng)數(shù)據(jù)庫來管理數(shù)字電子地圖中的實體信息與坐標信息， 可以 實現(xiàn)數(shù)據(jù)的連續(xù)性。由于 駕駛者 對道路信息的需求是復(fù)雜多樣的 ：他們不僅 需要當前目標的位置地圖數(shù)據(jù)源 輸入設(shè)備 地圖數(shù)據(jù)庫 計算機 系統(tǒng)控制軟件 輸出設(shè)備 24 等信息，還需要了解目標所在路段的交通狀況，所以需要對道路中不同層次的實體分別進行描述，提供所需的各類信息。還由于道路信息特別是實時路況信息更新比較頻繁，需要對己有數(shù)據(jù)實時更新 。 需要更新的數(shù)據(jù)中，既有大范圍信息 (如 ： 整條路塞車嚴重 )，也有針對個別位置的信息 (如 ： 某點在施工 )。要能實現(xiàn)快速更新相應(yīng)的數(shù)據(jù)，只有對不同的實體分別 描述，根據(jù)實體之間的關(guān)系，查找到相應(yīng)的實體后進行更新?？梢姡肪W(wǎng)數(shù)據(jù)庫除了必須提供實體 信息 和坐標信息之外，還必須提供復(fù)雜多樣的道路信息 ， 如道路的擁擠、堵塞、施工、事故等信息，并能方便地對己有的信息進行實時更新。為此，路網(wǎng)數(shù)據(jù)庫必須由節(jié)點 表 、線 表 、路段 表 、節(jié)點信息 表 、路段信息 表 等 組成。 在道路中，節(jié)點分為一般節(jié)點和交叉路節(jié)點。其中連接路段中兩條線的節(jié)點為一般節(jié)點，而連接兩個路段的節(jié)點就為交叉路節(jié)點。交叉路節(jié)點還可以分為各種類型，例如城市交叉路節(jié)點就又有標志控制交叉口、信號控制交叉口、環(huán)形交叉口等，這些在數(shù)據(jù)庫 中都可以用代碼加以標示。 路況信息主要包括 ： 路長、道路等級、行車走向信息等，這些信息由于確定性比較高，故在數(shù)據(jù)庫中采用專門字段描述。下面 以路長為例 說明這些數(shù)據(jù)的確定方法 ： 道路采用的是以折線近似表示，每條路可以分為若干路段，而每條路段又可以分為若干線。每條線的長度就可以由該線的節(jié)點坐標來確定。假設(shè)一條線的起始坐標為（ 11,xy），終節(jié)點坐標為（ 22,xy）那么該線的長度 l 為： 222 1 2 1( ) ( )l x x y y? ? ? ? 如果一路段由 N條線組成，每條線長度分別為 1 2 3, nl l l l??? ，那么這條路段的長度 L 為： 1nkkLl??? 又如果一條路是由 M條路段組成，每條路段的長度分別為 1 2 3 MLL L L??? ,那么這條路的長度為： miiiDL??? 綜上所述，只要獲得了組成路段的節(jié)點， 就 可以計算出線路、路段、路的長度。 接下來具體說明道路網(wǎng)數(shù)據(jù)庫的建立。主要是利用已經(jīng)建立顯示用的數(shù)字電子地圖并依 賴于程序自動判讀，通過數(shù)據(jù)庫查詢語言查找已有的數(shù)據(jù)，用以組成或生成新的數(shù)據(jù)。 具體建立流程圖如下： 25 圖：路網(wǎng)數(shù)據(jù)庫建立流程圖 開始 在屏幕上采集各點，輸入節(jié)點表各項 生成線表，填充線表各項 生成路段表，填充路段表各項 生成路表，填充路表各項 生成線 生成路段 生成路 是否結(jié)束 結(jié)束 加入已有路段修 改線表中相應(yīng)項 加入已有路修 改 路段表中相應(yīng)項 否 是 否 是 是 是 否 否 26 具體方法為：將制作出來的顯示用的數(shù)字電子地圖顯示在屏幕上，運用屏幕數(shù)字化的方法采集節(jié)點，生成節(jié)點的各種數(shù)據(jù)，再將數(shù)據(jù)輸入節(jié)點表中。然后詢問是否形成線 ，若是，找出己存在于節(jié)點表中的形成線的節(jié)點信息，自動填充線表中的各 相應(yīng)項并提示輸入線表中 的其他信息。 繼而詢問是否形成新的路段，若是，就生成新的路段，填充各項信息并更新線段信息中的相應(yīng)項。之后進一步詢問是否生成新的路 ， 若是，則生成新的的路，填充各項信息并更新路段信息 中的相應(yīng)項 ，最后完成任務(wù)。 屬性數(shù)據(jù)庫的建立 為了實現(xiàn)地址匹配，必須建立屬性數(shù)據(jù)庫，將地圖上重要的物標的位置信息與物標的屬性信息聯(lián)系起來。 主要常用的物標有：道路網(wǎng)上的重要節(jié)點、收費站、加油站、汽車維修點、醫(yī)院、交通事故處理點、旅游景點、賓館、旅館、旅行社、重要建筑物等。為了便于查詢，將這些物標分 為： （ 1） 駕駛員行車信息，用于給駕駛員查詢的信息。如路網(wǎng)上的重要節(jié)點、收費站、加油站、停車場、汽車維修點、交通事故處理點等 。 （ 2） 旅行信息，用于為旅客提供與旅行有關(guān)的服務(wù)以及使用有關(guān)的設(shè)施。如飯店、賓館、旅館、車站、售票處、機場、碼頭、醫(yī)院、警察局等 。 （ 3） 旅游服務(wù)信息，用于給游客提供有關(guān)旅游的信息。如旅行社、旅游公司、公園、樂園、動物園、渡假村、各種展館、游樂場所、旅游商店等 。 以上物標均可以在數(shù)據(jù)庫中用代碼表示出來。 接下來具體說明屬性數(shù)據(jù)庫的建立。 屬性數(shù)據(jù)庫的數(shù)據(jù)的 讀 入可根據(jù)顯示用的數(shù)字電子 地圖，利用屏幕數(shù)字化技術(shù)采集物標的屏幕坐標并輸入數(shù)據(jù)庫表的相應(yīng)字段，再由駕駛員行車指南、旅游指南、市區(qū)各種服務(wù)設(shè)施的介紹等等，查找有關(guān)重要物標的資料輸入數(shù)據(jù)庫記錄。建立上述物標的屬性數(shù)據(jù)庫將能方便地用各種方法實現(xiàn)數(shù)字電子地圖的咨詢服務(wù)，如用戶可按物標名稱查詢，也可用電話號碼查詢，還可按用戶指定的地理位置查詢，當然還可使用計算機圖形學中的物標拾取技術(shù)，根據(jù)鼠標的位置實現(xiàn)物標的查找，獲取有關(guān)該物標的各種信息。 綜上所述，最后建立圖形數(shù)據(jù)庫、導(dǎo)航數(shù)據(jù)庫、屬性數(shù)據(jù)庫之間的關(guān)系，便可以生成數(shù)字電子地圖，從而為駕駛者的 出行實現(xiàn)汽車導(dǎo)航服務(wù)。 27 第 6 章 地圖匹配與路徑規(guī)劃 地圖匹配 地圖匹配原理概述 通過 GPS 得到的定位數(shù)據(jù)有一定的誤差，它一方面影響導(dǎo)航系統(tǒng)的視覺效果，另一方面影響到空間運算、分析、查找等。由于矢量化數(shù)字電子地圖的道路對象的地理位置是相對精確的，利用數(shù)字電子地圖的地理數(shù)據(jù)對得到的汽車定位數(shù)據(jù)進行配準糾正，相對地提高當前定位數(shù)據(jù)的精度。 所以 地圖匹配的基本思想是通過汽車的 GPS 接收到的定位信息與數(shù)字電子地圖上矢量化的路段相近匹配，尋找當前行駛的道路，并將汽車當前的 GPS 定位點投影道路 上。這樣既保證了不會因為定位誤差使汽車定位點偏離汽車當前行駛的道路，而且通過投影使汽車定位數(shù)據(jù)僅殘留定位誤差在汽車前進方向上的徑向分量，從而提高汽車的定位精度。 地圖匹配的過程及誤差分析 在地理信息系統(tǒng)中， 由于 道路是由一些線段 (路段 )組成的，所以 地圖匹配的算法就可以充分利用道路的數(shù)據(jù)特點， 其 基本思想 就 是利用點到直線 (線段 )的垂直 (即投影 )距離最短，并利用以前的定位坐標作參考與分析，得出當前接收位置的定位坐標。 具體 可以分為兩個過程 ： （ 1） 尋找汽車當前行駛的道路 (如果當前道路為己知，則可以省略這一 步驟 )。 （ 2） 將當前定位點投影到汽車行駛的道路上 。 在地圖匹配的過程中，必須按照以下原則進行： （ 1）最近道路原則。也就是將車輛定位到距離最近的道路上，這是目前比較常用的原則。 （ 2）方為匹配。就是選擇的路段必須和車輛的行駛方向大致相同。 （ 3）路段的邏輯連通性。 （ 4）根據(jù)地圖數(shù)據(jù)消除數(shù)據(jù)的輸出誤差。 接下來進行匹配過程的誤差分析。由于實際道路的狀況不同，所以直接回關(guān)系到匹 28 配過程的誤差狀況。 對于城市市區(qū)內(nèi)道路密集和路口較多的情況，對匹配的可靠性影響較大。當兩條平行的路線非常接近，恰好定位點持續(xù)地落在這 兩條路中間時，可能會出現(xiàn)行車路線的誤判。同時，對于數(shù)據(jù)量很大的道路網(wǎng)進行搜索，系統(tǒng)的運算量比較大。對這種問題可采取的有效方法是對道路網(wǎng)進行分級管理，因為市區(qū)內(nèi)的交通干道是汽車行駛的主要路線，在實現(xiàn)汽車路徑定位時可以對主干 道優(yōu)先搜索，計算匹配度量，只有當匹配度量值超過一定的經(jīng)驗值時，才去搜索較低等級的道路。這一方面有效減少了判斷失誤另一方面也降低了地圖搜索的匹配的運算量。對于定位點歸結(jié)到己知道路路段的投影點，其實是對定位結(jié)果的適時垂線改正，結(jié)果是消去了與道路垂線方向的誤差分量，只保留了沿道路路段方向的部分誤差 分量。 路徑規(guī)劃 最短路徑概述 路徑規(guī)劃被認為是汽車導(dǎo)航領(lǐng)域中的一個基本問題，實際就是協(xié)助司機在出行前或行駛中規(guī)劃自己行駛路線的過程，從而可以選擇出行駛的最短路徑。規(guī)劃的路線一旦確定，系統(tǒng)級可以根據(jù)所設(shè)定的行車路線，搜索汽車的行進指令，也就是地理信息系統(tǒng)的有條件查詢，合理、有效地引導(dǎo)汽車的行駛，提高汽車的運行效率，避免駕駛者走錯路。汽車導(dǎo)航中的最短路徑的算法問題具有一定的復(fù)雜性，所以本文主要討論單節(jié)點最短路徑的問題。 所謂最短路徑，我們不能單純地將其理解為距離最短或者行駛的時間最短，因為 一條路徑的選擇一般取決于多種因素，例如距離、時間和交通燈的數(shù)量和動態(tài)交通信息。有時司機愿意選擇行駛距離最短，而有時則愿意選擇行駛時間最短，這些選擇的標準則通常取決于系統(tǒng)的設(shè)計和駕駛者的選擇。因此我們將其理解為所謂的最短路徑在某種程度上 指的是最優(yōu)路徑也許更加貼切。但在本文中將其一律稱為最短路徑，并且主要解決在兩個規(guī)定點之間的最短路徑問題。 最短路徑算法 原理 最短路徑問題的解決方法很多，但在實際應(yīng)用中，以迪杰斯特拉（ Dijkstra）算法最為廣泛，因為該算法所解決的問題是 給定一個帶正權(quán)的有向圖 D（ V,E）和起始點 0V , 29 求從該起始點 0V 到 D中其余各頂點間的最短路徑。這種算法的主要原理是： 首先定義一個有 n個節(jié)點的加權(quán)圖 G，可用一個 n 階矩陣表示 : []ijDd? 式中 0ijd? ； ijd? 由點 i 到 j 之間有向邊的距離 (或權(quán) )， ijd ? 0； 如果由點 i 到 j 之間沒有邊 ,則 ijd?? ； 此算法的思想是：由于 ij jkdd? 可能小于 ikd ，因而認為兩節(jié)點間最佳路徑要么是直接相連，要么是通過其它己找到與源點的最佳路徑的中轉(zhuǎn)節(jié)點。該算法保存一個節(jié)點集合，開始時，這個集合僅包含源節(jié)點，其它節(jié)點為“剩余節(jié)點”。在每一步，向集合加入 一個“剩余節(jié)點”，它的費用相對于源節(jié)點的費用在剩余節(jié)點中最小。假如所有線段的費用都是非負的，總能找到一條從源節(jié)點到目的節(jié)點之間的最短路徑。在算法的每一步，用一個數(shù)組記錄每一個節(jié)點的最短路徑長度。一旦該集合包含所有的節(jié)點，則該數(shù)組記錄了從源節(jié)點到各節(jié)點的最短距離 。 具體的搜索步驟為： 把給出的有向圖的各 點標以數(shù)字，我們將其稱為標數(shù)。在算法的每一個階段，有些點是固定標數(shù)，而另外一些點是臨時標數(shù)。在算法的開始時，我們可以這樣定義：起始點我們給定一個固定標數(shù)，為了計算方便，我們將其定義為 0，而其余各點我們則給定一個臨時標數(shù)，我們將它們一致定義為 ? 。然后在算法進行中，我們可以給其余各點給定一個固定標數(shù)，具體方法如下： （ 1） 按照求 ??m in ( )j ij的 舊 標 數(shù) ） ， (i 的 舊 標 數(shù) +d，即求 j的舊標數(shù)和 i的舊標數(shù) +dij中最小值的 方法定出新的固定標數(shù)，其中， i 是前一次計算所固定的標號，而 dij是點 i和點 j之間的直接距離，如果 i 和 j 之間沒有一條邊相連，則定 dij=? 。 （ 2） 找出所有臨時標數(shù)中的最小數(shù)，定為這個點對應(yīng)的固定標數(shù)。當出現(xiàn)同樣值的標數(shù)點時，則任選其一，給以固定標數(shù)。 以上兩步循環(huán)進行，一直到終點得到固定標數(shù)為止，那么，第一個固定標數(shù)的點距離起始點的最短距離為 0，則第二個得到固定標數(shù)的點就是距離起始 點最近的點，第三個得 30 到固定標數(shù)的點則為距離起始點第二近的點，同理，依次類推，每一個點的固定標數(shù)，就是該點和起始點的最短距離了。那么從起始點到終止點的最短路徑所經(jīng)過的節(jié)點集合就是就是依次獲得固定標數(shù)的節(jié)點集的子集。 最短路徑算法程序?qū)崿F(xiàn) 以有向圖為例，圖中的每個頂點表示一個地點，邊表示兩點之間的距離，路徑長度指的是路徑上各邊的加權(quán)和，路徑的起點是源點，最后點是終點 ，如圖所示， 5 個頂點分別表示 5 個地點，他們分別是 1 2 3 4 5,