1智能車第6章電子地圖

第六章 電子地圖與地圖匹配6.1 導(dǎo)航電子地圖簡介6.2 導(dǎo)航電子地圖的數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)模型6.3 電子地圖數(shù)據(jù)的生成6.4 地圖匹配6.1 導(dǎo)航電子地圖簡介

在人們的日常生活中，地圖發(fā)揮著重要的作用，作為模擬地圖的紙質(zhì)地圖很早就廣泛應(yīng)用于導(dǎo)航、旅游、航海、勘探等領(lǐng)域。隨著計(jì)算機(jī)軟硬件技術(shù)的飛速發(fā)展，尤其是大容量存儲(chǔ)設(shè)備、圖形圖像卡的發(fā)展，美日歐等發(fā)達(dá)國家和地區(qū)早在20世紀(jì)80年代就開始了以導(dǎo)航、查詢、管理為目的，應(yīng)用于車輛導(dǎo)航、交通管理和安全保衛(wèi)等領(lǐng)域的數(shù)字化道路地圖（DigitalRoadMap，DRM）的研制，DRM應(yīng)用于導(dǎo)航，故又稱為導(dǎo)航電子地圖。有關(guān)的機(jī)構(gòu)與組織也紛紛成立，并開發(fā)了相應(yīng)的產(chǎn)品投放市場，如美國Etak公司、NavTech公司，日本電子地圖聯(lián)盟、歐洲電子地圖聯(lián)盟等。

導(dǎo)航電子地圖在車輛定位導(dǎo)航系統(tǒng)中的應(yīng)用可分為以下幾種情況：（1）自導(dǎo)航系統(tǒng)： 有導(dǎo)航設(shè)備和電子地圖組成，導(dǎo)航設(shè)備確定車輛的位置，電子地圖用于顯示、信息查詢、路徑選擇等；（2）管理系統(tǒng)：由管理中心和移動(dòng)車輛組成，導(dǎo)航電子地圖安裝在管理中心，各移動(dòng)車輛的位置有無線數(shù)據(jù)傳輸設(shè)備傳輸?shù)焦芾碇行?，管理中心的電子地圖用來顯示各車輛的位置，從而實(shí)現(xiàn)對(duì)移動(dòng)車輛的管理；（3）組合系統(tǒng)：上述兩類系統(tǒng)的結(jié)合。電子地圖既配置在管理中心，也配置在移動(dòng)車輛上，因此該系統(tǒng)具有上述兩類系統(tǒng)的功能。

導(dǎo)航電子地圖主要用來對(duì)車輛進(jìn)行導(dǎo)航，其主要特征為（1）能實(shí)時(shí)準(zhǔn)確地顯示車輛位置，跟蹤車輛行駛過程；（2）數(shù)據(jù)庫結(jié)構(gòu)簡單，拓?fù)潢P(guān)系明確，可計(jì)算出發(fā)地和目的地之間的最佳線路；（3）數(shù)據(jù)存儲(chǔ)冗余小，軟件運(yùn)行速度快，空間數(shù)據(jù)處理與分析操作時(shí)間短；（4）包含車輛導(dǎo)航所需的交通信息，如限速標(biāo)志、交叉口轉(zhuǎn)彎限制、信號(hào)燈等；（5）信息查詢靈活、方便。6.2 導(dǎo)航電子地圖的數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)模型6.2.1電子地圖的數(shù)據(jù)類型及其特征1、數(shù)據(jù)類型 電子地圖中的數(shù)據(jù)可分為空間數(shù)據(jù)和非空間數(shù)據(jù)兩大類?？臻g數(shù)據(jù)又叫幾何數(shù)據(jù)，用來表示物體的位置、形態(tài)、大小和分布等特征信息，根據(jù)空間數(shù)據(jù)的幾何特點(diǎn)，它又分為圖形數(shù)據(jù)和圖像柵格。

在地圖的數(shù)據(jù)結(jié)構(gòu)中不僅包含空間對(duì)象的坐標(biāo)、角度、方向、距離、周長和面積等幾何形態(tài)參數(shù)，而且包含對(duì)象之間存在的相連、相鄰、相交等拓?fù)潢P(guān)系，該數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)是通過圖形數(shù)據(jù)來完成的。圖形數(shù)據(jù)是用點(diǎn)、線、面等地理原形來描述空間對(duì)象，由這些元素可以表示簡單和復(fù)雜的對(duì)象以及空間對(duì)象的拓?fù)潢P(guān)系，如圖6.1位某區(qū)域的拓?fù)潢P(guān)系示意圖，表6.1為其分類表示。車輛導(dǎo)航中的路徑規(guī)劃就是通過圖形數(shù)據(jù)來實(shí)現(xiàn)的。圖5.1空間數(shù)據(jù)拓?fù)潢P(guān)系示意圖表6.1拓?fù)潢P(guān)系的分類表示

圖像柵格是用像素來描述空間對(duì)象，像素的灰度和顏色值表示空間對(duì)象的特征。 非空間數(shù)據(jù)主要包括專題屬性數(shù)據(jù)、質(zhì)量描述數(shù)據(jù)和時(shí)間因素等語義信息，是空間數(shù)據(jù)的語義描述，反映了空間實(shí)體的本質(zhì)特征。非空間數(shù)據(jù)在車輛導(dǎo)航中用于信息查詢和數(shù)據(jù)分析。 空間數(shù)據(jù)和非空間數(shù)據(jù)在導(dǎo)航電子地圖中是通過標(biāo)示符連接的。2、數(shù)據(jù)特征

電子地圖中的數(shù)據(jù)特征包含以下幾個(gè)方面：（1）質(zhì)量特征：如地圖要素分類，目標(biāo)在物理、化學(xué)、人文、自然、經(jīng)濟(jì)等多個(gè)方面的特征；（2）數(shù)量特征：如居民地人口、線狀地物長度、面狀地物的面積、土壤的酸堿度、腐殖質(zhì)含量、雨量、溫度等；（3）時(shí)間特征：各種地圖對(duì)象均有其產(chǎn)生、存在及消失的時(shí)間，地圖數(shù)據(jù)的時(shí)間特征直接反映了地圖對(duì)象的時(shí)間變化規(guī)律；（4）空間特征：即地圖對(duì)象在地理空間的分布及相互關(guān)系。6.2.2空間數(shù)據(jù)結(jié)構(gòu)

空間數(shù)據(jù)結(jié)構(gòu)包括圖形數(shù)據(jù)結(jié)構(gòu)、圖像柵格結(jié)構(gòu)及圖形柵格一體化結(jié)構(gòu)三種。1、圖形數(shù)據(jù)結(jié)構(gòu)圖形數(shù)據(jù)結(jié)構(gòu)用空間坐標(biāo)及其關(guān)系描述空間對(duì)象，單個(gè)空間對(duì)象是圖形數(shù)據(jù)的基本邏輯單位。根據(jù)數(shù)據(jù)結(jié)構(gòu)中空間對(duì)象的組織形式與聯(lián)系程度，圖形數(shù)據(jù)結(jié)構(gòu)可以有多種構(gòu)建方式，下面就二維空間的圖形結(jié)構(gòu)進(jìn)行說明。（1）描述結(jié)構(gòu)

該結(jié)構(gòu)用代碼表示空間對(duì)象的類型，用坐標(biāo)（x，y）表示對(duì)象的空間位置，具體結(jié)構(gòu)定義如下： 節(jié)點(diǎn)結(jié)構(gòu)：

Node { #Node_Code; Pointpoint; }線段結(jié)構(gòu)Line{ #Line_Code; PointLine_from; PointLine_to;}曲邊結(jié)構(gòu)Polygon{ #Polygon_Code; point_Number; Pointpoint1; Pointpoint2;

… PointpointN;}其中，Point結(jié)構(gòu)定義為Point{ x；

y；}

描述結(jié)構(gòu)是最簡單的圖形數(shù)據(jù)結(jié)構(gòu)，實(shí)際上是一種無結(jié)構(gòu)信息的數(shù)據(jù)結(jié)構(gòu)，具有數(shù)據(jù)簡單、顯示快等特點(diǎn)，但僅適用于簡單的圖形再現(xiàn)，不能用于空間分析。對(duì)圖形中的公共對(duì)象存儲(chǔ)有數(shù)據(jù)冗余，例如二線段的交點(diǎn)在兩條線段的數(shù)據(jù)結(jié)構(gòu)中都有存儲(chǔ)，從而在復(fù)雜的圖形中數(shù)據(jù)冗余較大。（2）整體多邊形結(jié)構(gòu)

該數(shù)據(jù)結(jié)構(gòu)面向多邊形，每個(gè)多邊形由其封閉的邊界表示，并在數(shù)據(jù)庫中獨(dú)立存儲(chǔ)。圖形中的公共邊界被多個(gè)多邊形（其圍成的區(qū)域稱為曲面）重復(fù)存儲(chǔ)，從而產(chǎn)生數(shù)據(jù)冗余，如圖6.2所示。圖6.2整體多邊形圖形數(shù)據(jù)結(jié)構(gòu)（3）DIME結(jié)構(gòu)DIME結(jié)構(gòu)即為對(duì)偶獨(dú)立地圖編碼（DualIndependentMapEncode）結(jié)構(gòu)，該結(jié)構(gòu)最早被美國統(tǒng)計(jì)局應(yīng)用于城鎮(zhèn)的信息統(tǒng)計(jì)系統(tǒng)，具體結(jié)構(gòu)如圖6.3所示。DIME結(jié)構(gòu)的最簡單方式是存儲(chǔ)起始節(jié)點(diǎn)、終止節(jié)點(diǎn)和數(shù)字化方向，由于節(jié)點(diǎn)單獨(dú)存儲(chǔ)，故減少了數(shù)據(jù)冗余，但是對(duì)復(fù)雜對(duì)象的操作較為困難。圖6.3DIME數(shù)據(jù)結(jié)構(gòu)（4）ARC_NODE結(jié)構(gòu)ARC_NODE結(jié)構(gòu)是應(yīng)用最廣泛的地圖數(shù)據(jù)庫結(jié)構(gòu)，它具有完整的矢量弧線-節(jié)點(diǎn)拓?fù)潢P(guān)系，每一空間對(duì)象用一特定的數(shù)字或編碼標(biāo)識(shí)并置于選定的位置，相應(yīng)的屬性數(shù)據(jù)存儲(chǔ)在關(guān)系表格中。圖6.4為ARC_NODE數(shù)據(jù)結(jié)構(gòu)示意圖，其中交通控制設(shè)備定義在相關(guān)的節(jié)點(diǎn)中，路長定義在相應(yīng)的弧線上，使屬性數(shù)據(jù)和空間對(duì)象有明確的對(duì)應(yīng)關(guān)系，可用于實(shí)現(xiàn)路徑選擇、空間分析等功能。圖6.4ARC-NODE數(shù)據(jù)結(jié)構(gòu)2、圖像柵格數(shù)據(jù)結(jié)構(gòu)

圖像柵格數(shù)據(jù)結(jié)構(gòu)是用像素來表示空間對(duì)象，不同的像素存儲(chǔ)結(jié)構(gòu)及空間單元對(duì)應(yīng)不同的柵格結(jié)構(gòu)。（1）柵格矩陣結(jié)構(gòu) 柵格數(shù)據(jù)是二維表面上地理數(shù)據(jù)的離散量值，所有的像元值組成像元陣列，其中行、列號(hào)表示像元的位置。例如，圖6.5所示圖像的柵格矩陣可表示為圖6.5黑白柵格圖像

其中，1表示圖像中的像元為黑色，0表示白色。在柵格圖像數(shù)據(jù)結(jié)構(gòu)中，像元的存儲(chǔ)數(shù)由圖像的類型決定，如黑白圖像的像元位數(shù)為1bit，而256色圖像的像元數(shù)用1byte表示。6.2.3非空間數(shù)據(jù)的數(shù)據(jù)模型

數(shù)據(jù)模型是數(shù)據(jù)結(jié)構(gòu)的抽象，用于描述數(shù)據(jù)對(duì)象及其操作，指導(dǎo)數(shù)據(jù)庫開發(fā)人員選擇合適的數(shù)據(jù)結(jié)構(gòu)。對(duì)數(shù)據(jù)庫的用戶而言，數(shù)據(jù)模型是提供獨(dú)立于具體實(shí)現(xiàn)形式的數(shù)據(jù)結(jié)構(gòu)描述。隨著數(shù)據(jù)庫技術(shù)的發(fā)展，導(dǎo)航電子地圖中可以采用層次模型、網(wǎng)絡(luò)模型、關(guān)系模型、面向?qū)ο竽Ｐ偷榷喾N非空間數(shù)據(jù)模型。1、層次模型

非空間數(shù)據(jù)的層次模型是以記錄為結(jié)點(diǎn)的有向樹,樹的主要特征之一是除根結(jié)點(diǎn)以外,任何結(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)。層次模型應(yīng)用較早,1968年IBM公司開發(fā)的IMS系統(tǒng)采用的就是該模型,對(duì)數(shù)據(jù)庫的發(fā)展有重大影響,但是該模型不能用來表示多點(diǎn)對(duì)多點(diǎn)的聯(lián)系。2、網(wǎng)絡(luò)模型

網(wǎng)絡(luò)模型是繼層次模型之后由CODASYL(ConferenceonDataSystemsandLanguages)發(fā)展起來的一種數(shù)據(jù)模型,該模型是以記錄類型為結(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)。在網(wǎng)絡(luò)模型中,一個(gè)子結(jié)點(diǎn)可以有兩個(gè)或多個(gè)父結(jié)點(diǎn),任何兩個(gè)結(jié)點(diǎn)之間可以有兩種或多種聯(lián)系,因此該模型可用來表示多點(diǎn)對(duì)多點(diǎn)的聯(lián)系。3、關(guān)系模型

關(guān)系模型是1970年由E.F.Codd提出的,由于它以關(guān)系代數(shù)為基礎(chǔ)、具有良好的用戶接口以及對(duì)查詢語言的快速響應(yīng),因此一度成為事實(shí)上的工業(yè)標(biāo)準(zhǔn)。以關(guān)系模型構(gòu)成的數(shù)據(jù)庫由兩維表格化的關(guān)系組成,每一關(guān)系包含有一組屬性,在表格中占用一行(稱為一條記錄),其中每一列表示一個(gè)屬性。具有相同屬性的不同表格可通過該屬性建立鏈接,同一條查詢語句也可以同時(shí)對(duì)多個(gè)表格進(jìn)行操作,其操作算子均來源于關(guān)系代數(shù)中的算子,如兩個(gè)表格的并、交、和、差等,而所有操作算子的實(shí)現(xiàn)均由標(biāo)準(zhǔn)的結(jié)構(gòu)化查詢語言(StructuredQueryLanguages，SQL）完成。

表6.2(a)和(b)為城市信息關(guān)系模型的游覽區(qū)關(guān)系和行政區(qū)關(guān)系兩個(gè)具體實(shí)例。其中游覽區(qū)關(guān)系包含游覽類型、名稱、所屬行政區(qū)、門票價(jià)格;行政區(qū)關(guān)系包含行政區(qū)名稱、所屬城市名稱,兩個(gè)表格都包含三條不同的記錄。

表5.2(a)行政區(qū)關(guān)系 表5.2(b)游覽區(qū)關(guān)系4、面向?qū)ο蟮臄?shù)據(jù)模型及混合模型

自從關(guān)系模型提出以來,20世紀(jì)70年代出現(xiàn)了多種關(guān)系數(shù)據(jù)庫的操作語言如SQL,QUEL(QueryLanguage)以及實(shí)用化的關(guān)系數(shù)據(jù)庫系統(tǒng)如IBM的R系統(tǒng)和加州大學(xué)伯克利分校的INGRES(InteractiveGraphicsandRetrievalSystems)系統(tǒng)。隨著社會(huì)信息化程度的提高和計(jì)算機(jī)語言的發(fā)展,80年代出現(xiàn)了面向?qū)ο蟮木幊陶Z言,之后面向?qū)ο蟮母拍畋灰氲綌?shù)據(jù)庫中,出現(xiàn)了面向?qū)ο蟮臄?shù)據(jù)模型以及相應(yīng)的數(shù)據(jù)庫系統(tǒng)如02和ORION。

面向?qū)ο蟮臄?shù)據(jù)模型是基于對(duì)象而不是基于記錄(關(guān)系模型為基于記錄的數(shù)據(jù)模型)的,在對(duì)象中不僅包含數(shù)據(jù),而且包含對(duì)數(shù)據(jù)的操作;對(duì)象中未包含的操作不能用于對(duì)其中的數(shù)據(jù)進(jìn)行操作。對(duì)象之中可以包含其他對(duì)象,也可以被其他對(duì)象所包含,因此面向?qū)ο蟮臄?shù)據(jù)模型中可以定義非常復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。該模型基于封裝、繼承、子類、超類等概念,從而豐富了數(shù)據(jù)庫系統(tǒng)的語義內(nèi)容,方便了數(shù)據(jù)庫的應(yīng)用開發(fā)。

但是,面向?qū)ο蟮臄?shù)據(jù)模型沒有完善的理論基礎(chǔ),缺乏易于使用的標(biāo)準(zhǔn)化查詢語言。因此,90年代又出現(xiàn)了基于對(duì)象而不是基于記錄的關(guān)系模型——面向?qū)ο蟮年P(guān)系模型(即混合模型)?；旌夏Ｐ涂梢酝ㄟ^在已有的關(guān)系模型中添加面向?qū)ο蟮母郊訉?或者將關(guān)系模型中的關(guān)系擴(kuò)展到對(duì)象數(shù)據(jù)中來實(shí)現(xiàn)。6.2.4面向弧線的空間數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

1、導(dǎo)航電子地圖數(shù)據(jù)庫設(shè)計(jì)原則在車輛定位和導(dǎo)航的相關(guān)應(yīng)用中,電子地圖一般工作于實(shí)時(shí)、多任務(wù)環(huán)境下,圖形顯示、刷新、信息查詢、拓?fù)潢P(guān)系等是數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)必須考慮的重要因素。電子地圖數(shù)據(jù)庫設(shè)計(jì)主要考慮以下原則:(1)圖形結(jié)構(gòu)簡單電子地圖主要包含點(diǎn)、線、面等空間對(duì)象,簡單的圖形結(jié)構(gòu)具有數(shù)據(jù)量小、刷新快、圖形剪裁方便等特點(diǎn)。(2)冗余度小地圖數(shù)據(jù)的冗余度小將使信息查詢、路徑搜索的速度得以提高,也將減少數(shù)據(jù)的存儲(chǔ)空間。(3)拓?fù)潢P(guān)系簡單在車輛定位與導(dǎo)航中,電子地圖的拓?fù)潢P(guān)系用于路徑搜索、最優(yōu)路徑規(guī)劃,因此簡單明了的拓?fù)潢P(guān)系將縮短路徑搜索的時(shí)間。(4)空間信息查詢與分析速度快空間信息查詢主要包括單個(gè)空間對(duì)象的查詢和多個(gè)對(duì)象之間的拓?fù)洳樵?良好的數(shù)據(jù)結(jié)構(gòu)將使空間查詢與分析速度快,結(jié)果準(zhǔn)確。(5)開放的數(shù)據(jù)接口電子地圖中的非空間數(shù)據(jù)具有良好的數(shù)據(jù)接口,能夠兼容商用的非空間數(shù)據(jù)。

2、電子地圖數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

導(dǎo)航電子地圖的基本元素為點(diǎn)、線、面,在連續(xù)歐氏空間中,點(diǎn)為零維元素、線為一維元素、面為二維元素。為實(shí)現(xiàn)實(shí)時(shí)的路徑搜索與信息查詢功能,點(diǎn)、線之間需要具有簡單的拓?fù)潢P(guān)系,因此,整個(gè)地圖平面可視為點(diǎn)、線組成的網(wǎng)絡(luò),而面由封閉的線段組成。具體說來,電子地圖數(shù)據(jù)包含:1)節(jié)點(diǎn):表示空間對(duì)象所在的位置,或者線段的起始、終止點(diǎn),它具有特定的拓?fù)湫再|(zhì);2)孤立點(diǎn):表示線、面經(jīng)過的點(diǎn),不具有拓?fù)湫再|(zhì);3)線(弧線):起始與終止點(diǎn)為節(jié)點(diǎn),并且具有若干孤立點(diǎn)的有序點(diǎn)集;

4)面:由若干弧線相連的封閉曲線圍成的區(qū)域稱為面,面以弧線的形勢表示,但通過代碼與弧線區(qū)別,且其內(nèi)部填充方式可以設(shè)置。包含以上數(shù)據(jù)的電子通圖數(shù)據(jù)結(jié)構(gòu)稱為面向弧線的數(shù)據(jù)結(jié)構(gòu),其圖形文件有ARC,NOD,IDX等三種。

ARC文件既包括了弧線的幾何參數(shù),也包括弧線與節(jié)點(diǎn)、弧線與弧線之間的拓?fù)潢P(guān)系,其數(shù)據(jù)格式為

ARC_IDCODEFrom_NODTo_NODHead_ARCTail_ARCPoint_Number(x,y)坐標(biāo)串其中：

ARC_ID表示 弧線標(biāo)示號(hào)；

CODE表示 弧線編碼；

From_NOD表示 起始節(jié)點(diǎn)；

To_NOD表示 終止節(jié)點(diǎn)；

Head_ARC表示 指向弧線起始節(jié)點(diǎn)的下一弧線（入弧線）；

Tail_ARC表示 以弧線終止點(diǎn)為起始的下一弧線（出弧線）；

Point_Number表示 弧線包含的點(diǎn)數(shù)； （x，y）坐標(biāo)串表示 各點(diǎn)的空間坐標(biāo)。

NOD文件表示了節(jié)點(diǎn)的幾何參數(shù)及節(jié)點(diǎn)與弧線的拓?fù)潢P(guān)系，通過節(jié)點(diǎn)標(biāo)示號(hào)，還可以實(shí)現(xiàn)節(jié)點(diǎn)與非空間數(shù)據(jù)鏈接，其數(shù)據(jù)格式為其中

NOD_ID表示 節(jié)點(diǎn)標(biāo)示號(hào)；

IN_ARC表示 以該節(jié)點(diǎn)為終止的第一弧線（入弧線）；

OUT_ARC表示 以該節(jié)點(diǎn)為起始的第一弧線（出弧線）；（x，y）表示 該節(jié)點(diǎn)的空間坐標(biāo)。NOD_IDIN_ARCOUT_ARC(x,y)

IDX文件表示地圖中路的映射。一條路由若干條弧線構(gòu)成，通過IDX文件可以進(jìn)行索引，同時(shí)Key_Item可用于實(shí)現(xiàn)與非空間數(shù)據(jù)的鏈接，其數(shù)據(jù)格式為其中

Key_Item表示 道路名稱；

ARC_Number表示 包括的弧線數(shù)；

ARC_1表示 第一條弧線的標(biāo)示號(hào)；

ARC_2表示 第二條弧線的標(biāo)示號(hào)；

…Key_ItemARC_NumberARC_1ARC_2…

圖6.6為點(diǎn)、線、面組成的某地圖區(qū)域，其中A，E，B為節(jié)點(diǎn)，C，D為孤立點(diǎn)，ACB，BDA，AE，EB為四條弧線，對(duì)應(yīng)于該地圖的面向弧線的數(shù)據(jù)結(jié)構(gòu)文件非別如表6.3(a),(b),(c)所示。圖6.6面向弧線的地圖示意圖表6.3（a） ARC文件數(shù)據(jù)結(jié)構(gòu)表6.3（b）NOD文件數(shù)據(jù)結(jié)構(gòu)表6.3（c）IDX文件數(shù)據(jù)結(jié)構(gòu)6.3電子地圖數(shù)據(jù)的生成

電子地圖數(shù)據(jù)的生成包含兩大部分：數(shù)據(jù)采集和拓?fù)潢P(guān)系的建立。數(shù)據(jù)采集的主要途徑有數(shù)字化儀和掃描儀輸入，利用數(shù)字化儀輸入耗時(shí)多，但事后處理簡單，輸出的為矢量化地圖，而掃描儀輸入雖然速度快、效率高，但其后處理復(fù)雜，還需要進(jìn)一步對(duì)柵格圖形矢量化。1、地圖數(shù)據(jù)采集原則

原始地圖所包含信息的種類和數(shù)量很多,既有各種空間對(duì)象的幾何信息,如公路、鐵路、建筑物、公園等的位置,也包括各種標(biāo)注信息。在導(dǎo)航電子地圖中如果包含以上所有信息,將使地圖數(shù)據(jù)庫容量大、相互關(guān)系復(fù)雜,不利于數(shù)據(jù)庫的管理和分析,對(duì)車輛導(dǎo)航來說,也沒有必要。在面向弧線的電子地圖中,構(gòu)成地圖的基本要素可以分為公路和一般地物兩類,為滿足導(dǎo)航需要,數(shù)據(jù)采集應(yīng)遵循以下原則:

(1)選取主要公路公路是導(dǎo)航地圖數(shù)據(jù)操作與分析的主體,按照其等級(jí)、與重要地物的相連情況、與其他公路的相連情況分為主要公路和次要公路,對(duì)其選取應(yīng)分別進(jìn)行。主要公路全部選取,與之相沖突的地圖要素全部挪位或刪除。(2)選取次要公路次要公路主要選取:①與主要公路相連的;②與重要地物相連的;③正確反映公路網(wǎng)特征,反映城市居民區(qū)外部輪廓形狀的;④使公路網(wǎng)分布合理,利于路網(wǎng)分析的。(3)選取一般地物根據(jù)地物是否影響車輛導(dǎo)航、是否為特殊建筑、是否為特別標(biāo)識(shí)物等來判斷其重要性,重要地物全部選取,次要地物選取與否主要考慮是否正確反映地圖特征和地圖中地物布局的合理性。2、地圖信息的數(shù)字化過程

地圖信息的數(shù)字化過程可用如圖6.7所示的流程說明,其步驟如下:(1)數(shù)據(jù)準(zhǔn)備根據(jù)地圖采集原則,在數(shù)字化之前首先檢查地圖是否具有所需要的信息,如公路線、公路交叉口、重要的建筑物等,并輸入必要的控制點(diǎn)坐標(biāo)與圖幅號(hào)。

(2)數(shù)字化儀狀態(tài)設(shè)置數(shù)字化儀的分辨率、數(shù)據(jù)傳輸速率、數(shù)據(jù)傳送格式、通信接口狀態(tài)等的設(shè)置直接決定了數(shù)據(jù)傳輸?shù)接?jì)算機(jī)時(shí)的數(shù)字化精度和數(shù)據(jù)處理方式。因此,在數(shù)字化之前,必須設(shè)置這些參數(shù)。(3)地圖分塊如果一張地圖幅面大于數(shù)字化儀桌面的有效區(qū)域,則采用四叉樹分塊法將一幅圖分成多塊并分別數(shù)字化。如圖6.8所示,各分塊編號(hào)為1,2,3和4,如果每一塊幅面仍然大于數(shù)字化儀桌面,則再分為11,12,13,14,21,22,23,24…。在存儲(chǔ)數(shù)據(jù)文件時(shí),以圖幅號(hào)加分塊號(hào)作為文件名,以便地圖拼接。圖6.8地圖分塊的四叉數(shù)方法(4)圖紙定向圖紙定向是利用仿射變換將數(shù)字化儀坐標(biāo)系變換到地圖參考坐標(biāo)系。變換公式為式中,X,Y為地圖參考坐標(biāo)系,x,y為數(shù)字化儀坐標(biāo)系,ai,bi為仿射變換系數(shù),該變換需要6個(gè)已知點(diǎn)的數(shù)字化儀坐標(biāo)系坐標(biāo)和地圖參考坐標(biāo)系坐標(biāo)。(5)地圖分層地圖上信息種類很多,可根據(jù)空間對(duì)象的位置或?qū)傩苑殖刹煌膶?layer),以利于顯示和查詢管理。電子地圖常用的層有:公路層(主要公路層和次要公路層)、建筑層、游覽層等。

(6)數(shù)字化按照地圖采集原則,應(yīng)用于扶方法采集地物幾何數(shù)據(jù),并存入磁盤。(7)圖形檢查與編輯在數(shù)字化的同時(shí),作業(yè)員需及時(shí)檢查已經(jīng)數(shù)字化了的部分,并對(duì)錯(cuò)誤或遺漏的信息進(jìn)行及時(shí)修正,以防止整個(gè)地圖完成后因信息量較大而不便于檢查。

公路的數(shù)字化有兩種方法,一是只數(shù)字化公路中心軸線,根據(jù)路寬計(jì)算出街道邊線;二是分別數(shù)字化公路的兩條邊線。方法一計(jì)算量小,但計(jì)算出的邊線可能與其他地物發(fā)生沖突,如公路與河流并行時(shí)可能交叉,給后續(xù)處理帶來困難。方法二工作量大,故對(duì)車輛定位導(dǎo)航來說,多采用第一種方法。經(jīng)過數(shù)字化儀采集得到的數(shù)據(jù),一般需經(jīng)過格式化轉(zhuǎn)換,將數(shù)據(jù)文件轉(zhuǎn)換為面向弧線的數(shù)據(jù)結(jié)構(gòu),即生成NOD,ARC文件,IDX文件主要存儲(chǔ)空間對(duì)象與屬性的映射關(guān)系,需要單獨(dú)建立。在格式化轉(zhuǎn)化的過程中,同時(shí)生成導(dǎo)航所需的拓?fù)潢P(guān)系。3、拓?fù)潢P(guān)系生成

空間對(duì)象的拓?fù)潢P(guān)系是電子地圖用于車輛導(dǎo)航的基礎(chǔ),其中主要有路段交叉節(jié)點(diǎn)拓?fù)?、?jié)點(diǎn)-弧線拓?fù)?所有這些拓?fù)潢P(guān)系都可以利用數(shù)字化的圖形數(shù)據(jù)導(dǎo)出,下面分別介紹。

(1)節(jié)點(diǎn)拓?fù)渖蓴?shù)字化得到的地圖中,不可避免地存在有弧線交叉點(diǎn)。對(duì)于相交的弧線,需要求出相交的節(jié)點(diǎn),生成節(jié)點(diǎn)拓?fù)潢P(guān)系,將弧線分成不相交的若干段,才能進(jìn)一步建立節(jié)點(diǎn)-弧線拓?fù)潢P(guān)系。節(jié)點(diǎn)拓?fù)渖刹襟E如下:1）讀出所有弧線的起始和終止節(jié)點(diǎn);2）讀出一弧線，計(jì)算該弧線上除節(jié)點(diǎn)外的所有點(diǎn)到其他弧線節(jié)點(diǎn)之間的距離；3）如果某個(gè)距離小于給定的閾值，則用當(dāng)前弧線上的當(dāng)前點(diǎn)對(duì)該弧線進(jìn)行分割；4）重復(fù)2）、4），直至所有弧線分割完畢。（2）節(jié)點(diǎn)-弧線拓?fù)涞纳?/p>

節(jié)點(diǎn)-弧線拓?fù)渖傻闹饕康氖墙⒐?jié)點(diǎn)與弧線的鏈接關(guān)系，即計(jì)算出節(jié)點(diǎn)的入弧線（IN-ARC）、出弧線（OUT-ARC）及與弧線相連的其他弧線（Head-ARC，Tail-ARC）。節(jié)點(diǎn)-弧線拓?fù)潢P(guān)系是空間網(wǎng)絡(luò)分析的基礎(chǔ)，是路徑導(dǎo)航主要的操作對(duì)象。

面向弧線的圖形數(shù)據(jù)文件已在前面做了詳細(xì)定義，在此僅寫出參與拓?fù)溆?jì)算的相關(guān)項(xiàng)，弧線相關(guān)項(xiàng)為：

typedefstructARC { longARC_ID;

… longFrom_NOD; longTo_NOD; longHead_ARC; longTail_ARC;

… }節(jié)點(diǎn)相關(guān)項(xiàng)為

typedefstructNOD { longNOD_ID; longIN_ARC; longOUT_ARC;

… }

在地圖數(shù)字化和節(jié)點(diǎn)生成拓?fù)溆?jì)算以后，已經(jīng)記錄下節(jié)點(diǎn)與弧線的所屬關(guān)系，在此基礎(chǔ)上即可建立節(jié)點(diǎn)-弧線拓?fù)潢P(guān)系，具體算法可以利用相應(yīng)的程序來實(shí)現(xiàn)。6.4地圖匹配

前面詳細(xì)介紹了導(dǎo)航電子地圖及其管理系統(tǒng),其中包含詳細(xì)的道路網(wǎng)信息,這些信息不僅可用于顯示,也能夠用來改善系統(tǒng)定位精度。如果能夠根據(jù)定位軌跡和電子地圖中的道路網(wǎng)信息確定出車輛所行駛的道路和其在道路上的準(zhǔn)確位置,則一方面可以滿足導(dǎo)航功能的需要,另一方面還可以利用較高精度的道路信息來修正定位系統(tǒng)的誤差,從而使系統(tǒng)性能得到改善,而這正是地圖匹配模塊所要解決的問題。

地圖匹配是一種基于軟件技術(shù)的定位修正方法,其基本思想是將車輛定位軌跡與數(shù)字地圖中的道路網(wǎng)信息聯(lián)系起來,并由此確定車輛相對(duì)于地圖的位置。地圖匹配技術(shù)的應(yīng)用有兩個(gè)前提,即

1）用于匹配的數(shù)字地圖包含高精度的道路位置坐標(biāo);2)被定位車輛正在道路網(wǎng)中行駛。

當(dāng)上述條件滿足時(shí),就可以把定位數(shù)據(jù)和車輛運(yùn)行軌跡同數(shù)字化地圖所提供的道路位置信息相比較,通過適當(dāng)?shù)钠ヅ溥^程確定出車輛最可能的行駛路段以及車輛在該路段中的最大可能位置。如果上述假設(shè)不成立,則地圖匹配將產(chǎn)生錯(cuò)誤的位置輸出,并可能導(dǎo)致系統(tǒng)性能的嚴(yán)重下降。一般認(rèn)為用于匹配的數(shù)字地圖誤差不應(yīng)超過15m。由于陸地車輛在除了進(jìn)入停車場等之外的絕大多數(shù)時(shí)間內(nèi)都位于公路網(wǎng)絡(luò)中,因此使用地圖匹配技術(shù)的條件是滿足的。6.4.1地圖匹配的基本方法

導(dǎo)航電子地圖的道路網(wǎng)數(shù)據(jù)以若干節(jié)點(diǎn)(node)的形式存儲(chǔ),在每兩個(gè)節(jié)點(diǎn)之間,道路都以直線近似,忽略道路的寬度。在每個(gè)節(jié)點(diǎn)處設(shè)立一個(gè)判斷區(qū)域,當(dāng)車輛在域外行駛時(shí),可以認(rèn)為其運(yùn)動(dòng)軌跡是一條直線;當(dāng)進(jìn)入判斷域時(shí),車輛將有可能作角運(yùn)動(dòng)。此時(shí),利用定位傳感器的輸出來判斷汽車是否開始轉(zhuǎn)彎,若沒有,則認(rèn)為汽車還沒有達(dá)到路口,進(jìn)行地圖匹配修正;若有角運(yùn)動(dòng),則在更小的判斷域內(nèi)作進(jìn)一步判斷。當(dāng)汽車開出判斷域后,根據(jù)轉(zhuǎn)彎的角度和路網(wǎng)信息確定下一條行駛路線,在新路線上進(jìn)行位置匹配。地圖匹配的原理示意圖如圖6.9所示。

假設(shè)車輛從A點(diǎn)出發(fā),在行駛過程中某一時(shí)刻,定位系統(tǒng)輸出的定位位置在B點(diǎn),未進(jìn)入判斷域內(nèi),因此車輛仍在A-E路段上,利用一定規(guī)則把B點(diǎn)技影到A-E段上即可;當(dāng)車輛繼續(xù)行駛進(jìn)入判斷域內(nèi)時(shí),假定定位系統(tǒng)輸出的定位位置在H點(diǎn),若方位角的變化在一定范圍內(nèi)則車輛仍在A-E路段或其延長線上,按規(guī)則把H點(diǎn)向A-E線段投影即可;若方位角的變化大于某范圍,則車輛作轉(zhuǎn)彎運(yùn)動(dòng)。如果還沒有進(jìn)入判斷小域,則直接把H點(diǎn)定位到路口E點(diǎn);如果已經(jīng)進(jìn)入了判斷小域,則首先記憶該點(diǎn)直到新的定位點(diǎn)F不在判斷小域內(nèi),把E和F之間的定位點(diǎn)用光滑的曲線連接形成軌跡。同時(shí)進(jìn)入判斷域后,利用已知的當(dāng)前位置對(duì)定位系統(tǒng)輸出的定位數(shù)據(jù)進(jìn)行修正,達(dá)到對(duì)定位系統(tǒng)誤差修正的目的。判斷域的選擇由定位系統(tǒng)的定位精度和定位系統(tǒng)傳感器的誤差模型共同決定。6.4.2誤差區(qū)域的選擇

進(jìn)行地圖匹配的第一步是要確定誤差區(qū)域(即判斷域),以便從地圖數(shù)據(jù)庫中提取候選匹配道路的信息。一般地按概率準(zhǔn)則定義誤差區(qū)域,即誤差區(qū)域必須以一定的概率包含車輛的實(shí)際位置。假設(shè)定位系統(tǒng)的方差、協(xié)方差矩陣為

式中,σx和σy是定位傳感器東向和北向的測量標(biāo)準(zhǔn)差,σx2和σy2

是方差,σxy和σyx是協(xié)方差,則可按下式定義定位誤差橢圓:

式中,a是橢圓半長軸,b是橢圓半短軸,φ是橢圓半長袖取向與正北方向的夾角,是單位權(quán)值的后驗(yàn)方差,橢圓中心是當(dāng)前的車輛定位位置(見圖6.10)。通過改變的值可以調(diào)整誤差橢圓的大小以獲得不同的可信度。在基于GPS的車輛導(dǎo)航系統(tǒng)中,利用GPS的參數(shù)即可獲得誤差橢圓。對(duì)導(dǎo)航型GPS接收機(jī),其定位誤差參數(shù)由下式確定。

式中,對(duì)角線元素為定位解(xk,yk,zk)和鐘差bk的方差,其余元素是各參量之間的協(xié)方差,σ02為偽距觀測方差。由于GPS具有穩(wěn)定的定位精度,且其誤差不隨時(shí)間增加,在應(yīng)用GPS的車輛定位導(dǎo)航系統(tǒng)中可采用GPS的定位誤差參數(shù)定義誤差橢圓。

對(duì)于采用Kalman濾波技術(shù)設(shè)計(jì)的GPS/DR組合導(dǎo)航系統(tǒng),由于在濾波計(jì)算的結(jié)果中包含估計(jì)誤差,因此獲取定義誤差區(qū)域的參數(shù)也非常方便。在GPS定位失效的情況下,為了保證匹配過程的連續(xù)性,必須依靠DR定位參數(shù)來代替GPS參數(shù)完成誤差區(qū)域的定義。但是,DR系統(tǒng)只能提供位置估計(jì)而不能輸出誤差參數(shù),因此只能采用近似的處理方法。通常的做法是沿用上一時(shí)刻的系統(tǒng)誤差參數(shù),只將區(qū)域中心點(diǎn)移動(dòng)到當(dāng)前的推算定位位置。由于DR推算的誤差隨時(shí)間不斷增大,因此在定義誤差區(qū)域時(shí)還應(yīng)乘上適當(dāng)?shù)臄U(kuò)展因子以反映誤差累積的影響,擴(kuò)展因子的取值也隨推算定位的進(jìn)行而增大。6