基于網(wǎng)格模型的導(dǎo)航道路圖漸進(jìn)式化簡(jiǎn)方法

郭慶勝，劉 洋，李 萌，程曉茜，何 捷，王慧慧，魏智威

1. 武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079； 2. 北京四維圖新科技股份有限公司，北京 100094； 3. 武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢430079

隨著高精度導(dǎo)航地圖的推廣應(yīng)用，直接從該數(shù)據(jù)集中自動(dòng)生產(chǎn)出較低精度的導(dǎo)航地圖是當(dāng)前亟待解決的問(wèn)題，其中就涉及導(dǎo)航道路圖形化簡(jiǎn)。已有的線圖形簡(jiǎn)化算法很多，國(guó)內(nèi)外學(xué)者在這方面已取得豐碩的研究成果，主要分為全域性算法和局域性算法。全域性算法以經(jīng)典的Douglas-Peucker算法為代表[1]，隨后有些學(xué)者對(duì)此方法進(jìn)行了改進(jìn)[2-3]。為了使線的簡(jiǎn)化達(dá)到最優(yōu)化效果，文獻(xiàn)[4—7]提出了線簡(jiǎn)化的最優(yōu)化算法和智能化方法。局域性算法將線圖形劃分為一定數(shù)量的基本組成單元，然后分別對(duì)每個(gè)組成單元進(jìn)行化簡(jiǎn)[7-10]，如文獻(xiàn)[10]提出了用斜拉式彎曲劃分的曲線化簡(jiǎn)方法。在線的簡(jiǎn)化過(guò)程中可能會(huì)引起空間關(guān)系的破壞，因此有些學(xué)者就研究了解決這些空間關(guān)系沖突的方法[11-12]，如文獻(xiàn)[11]研究了采用彎曲進(jìn)行道路化簡(jiǎn)沖突避免的方法。線在不同尺度下需要保留必要的特征點(diǎn)，線的這些特征點(diǎn)識(shí)別方法很多[13-16]，如文獻(xiàn)[14]提出了曲線形態(tài)的結(jié)構(gòu)化表達(dá)方法，文獻(xiàn)[15]提出了基于拐點(diǎn)和極值點(diǎn)等局部特征點(diǎn)的線彎曲識(shí)別方法，文獻(xiàn)[16]研究了基于曲率法的曲線特征點(diǎn)選取方法。

對(duì)于導(dǎo)航道路數(shù)據(jù)而言，其圖形簡(jiǎn)化需要考慮導(dǎo)航需求和地圖制圖規(guī)則的約束。當(dāng)前，在導(dǎo)航空間定位數(shù)據(jù)中，高精度導(dǎo)航地圖的數(shù)據(jù)要求必須保留到小數(shù)點(diǎn)7位數(shù)。為了從7位數(shù)的導(dǎo)航道路數(shù)據(jù)中自動(dòng)提取5位數(shù)的導(dǎo)航道路數(shù)據(jù)，本文采用網(wǎng)格模型表達(dá)導(dǎo)航地圖數(shù)據(jù)，試圖提出一種漸進(jìn)式的道路圖形化簡(jiǎn)方法，并協(xié)同處理導(dǎo)航道路網(wǎng)上的導(dǎo)航方向信息和可視化效果。

1 導(dǎo)航道路數(shù)據(jù)表達(dá)與需求

導(dǎo)航道路網(wǎng)是一個(gè)圖結(jié)構(gòu)，圖由節(jié)點(diǎn)和邊組成，其中道路為邊，道路交叉口為節(jié)點(diǎn)。一條道路可以用一串坐標(biāo)進(jìn)行描述，例如P={(x1,y1),…,(xi,yi),…,(xn,yn)}，其中，(x1,y1)和(xn,yn)為首末點(diǎn)，(xi,yi)(i≠1,i≠n)表示頂點(diǎn)，因此，設(shè)道路的內(nèi)域?yàn)镻°，道路的首末點(diǎn)為?P。本文采用網(wǎng)格模型[17]表示化簡(jiǎn)前后的導(dǎo)航數(shù)據(jù)。如圖1所示，實(shí)線為7位精度的道路，而同一條道路在5位精度下是圖中的虛線。

基于網(wǎng)格模型的導(dǎo)航道路圖形化簡(jiǎn)的約束條件如下：

(1) 位置精度約束:道路立體交叉點(diǎn)和首末點(diǎn)在導(dǎo)航道路圖形化簡(jiǎn)中不能刪除,只能移動(dòng)，而頂點(diǎn)則可以刪除或移動(dòng)，點(diǎn)移動(dòng)距離應(yīng)該小于導(dǎo)航數(shù)據(jù)精度。

圖1 不同層次網(wǎng)格模型上的道路Fig.1 Roads mesh models with different levels

(3) 空間方向關(guān)系約束：導(dǎo)航道路圖形化簡(jiǎn)前后要保持道路走向的相似性。如圖2(a)所示，化簡(jiǎn)前的道路上的3個(gè)頂點(diǎn)A、B、C，在化簡(jiǎn)后每個(gè)頂點(diǎn)的可選擇位置為其所在的網(wǎng)格單元的4個(gè)角點(diǎn)之一，無(wú)論選擇哪一個(gè)點(diǎn)，化簡(jiǎn)后的道路圖形走向都可能發(fā)生變化，但是，化簡(jiǎn)前后道路(圖2(a)中虛線為化簡(jiǎn)后的道路)走向應(yīng)當(dāng)盡量相似。因此，當(dāng)A∈P°時(shí)，A點(diǎn)處轉(zhuǎn)角變化最??；當(dāng)A∈?P時(shí)，與A點(diǎn)關(guān)聯(lián)的所有道路的方位角變化之和最小。

圖2 約束條件示意圖Fig.2 Sketch map of constraint conditions

(4) 空間拓?fù)潢P(guān)系約束：導(dǎo)航道路化簡(jiǎn)前后的空間拓?fù)潢P(guān)系不能被破壞。如圖2(b)所示，若線L1上刪除i點(diǎn)，則會(huì)導(dǎo)致L1與L2相交，破壞了這兩條線間的空間拓?fù)潢P(guān)系。因此，道路網(wǎng)中任意兩直線段之間的拓?fù)潢P(guān)系在綜合前后應(yīng)該保持一致。

(5) 視覺(jué)光滑程度約束：導(dǎo)航中要考慮化簡(jiǎn)后道路的可視化效果。如圖2(c)所示，虛線轉(zhuǎn)為5位精度的道路實(shí)線后，可能會(huì)產(chǎn)生一些急拐彎和抖動(dòng)現(xiàn)象，針對(duì)這種情況就需要進(jìn)行光滑處理。

2 道路頂點(diǎn)漸進(jìn)式刪除的算法

2.1 基本思想

在導(dǎo)航道路化簡(jiǎn)過(guò)程中，需要維護(hù)道路空間方向關(guān)系和空間拓?fù)潢P(guān)系，同時(shí)還要顧及導(dǎo)航時(shí)的可視化效果，因此，本文采用漸進(jìn)式圖形綜合的思想[18-19]對(duì)道路圖形進(jìn)行簡(jiǎn)化。這種漸進(jìn)式思想主要體現(xiàn)在：對(duì)道路上的每一個(gè)頂點(diǎn)依據(jù)約束按順序決策能否被刪除，如果遇到不滿足約束的頂點(diǎn)，則不立即處理該點(diǎn)，而是先將該點(diǎn)標(biāo)記為問(wèn)題點(diǎn)，然后順序處理剩下的頂點(diǎn)，直到所有頂點(diǎn)都處理完畢，并同時(shí)更新所有被影響的頂點(diǎn)形狀特征。然后逐個(gè)處理問(wèn)題點(diǎn)，此時(shí)，可能這些頂點(diǎn)的形狀特征發(fā)生改變，而不必再處理，需要按此過(guò)程對(duì)單條道路和整個(gè)道路網(wǎng)進(jìn)行迭代處理。若一次迭代處理過(guò)程中仍然存在問(wèn)題點(diǎn)，則需要繼續(xù)迭代處理這些問(wèn)題點(diǎn)，直到所有問(wèn)題點(diǎn)全部處理完畢。

2.2 道路頂點(diǎn)的刪除方法

為了能夠保持化簡(jiǎn)前后道路的局部形狀特征，需要對(duì)道路的局部形狀特征進(jìn)行描述，本文采用道路上相鄰頂點(diǎn)之間的距離和頂點(diǎn)處的轉(zhuǎn)向角來(lái)描述該點(diǎn)的幾何形狀特征。如圖3(a)所示，Vi為當(dāng)前的頂點(diǎn)，Vi-1和Vi+1分別為前后頂點(diǎn)，θi為頂點(diǎn)Vi處的轉(zhuǎn)向角，D[i-1,i]和D[i,i+1]分別表示Vi與Vi-1和Vi+1之間的距離。在道路圖形化簡(jiǎn)過(guò)程中也需要顧及道路的語(yǔ)義特征，以便在頂點(diǎn)刪除過(guò)程中根據(jù)不同的語(yǔ)義特征進(jìn)行處理。線的語(yǔ)義特征識(shí)別方法有很多[13-15]，如文獻(xiàn)[13]采用彎曲作為線的基本單元構(gòu)建二叉樹(shù)表達(dá)線結(jié)構(gòu)的語(yǔ)義特征。對(duì)導(dǎo)航道路而言，直線型道路是一個(gè)比較重要的特征，因此，本文在計(jì)算局部幾何特征的基礎(chǔ)上將道路線結(jié)構(gòu)的語(yǔ)義特征分為直線段和彎曲段兩大類(lèi)。若轉(zhuǎn)向角小于一個(gè)很小的角度，且頂點(diǎn)偏移量小于一個(gè)很小的距離值，則提取道路中較長(zhǎng)的直線段，將直線段外的部分都看作曲線型道路段。如圖3(b)所示，其中從1號(hào)點(diǎn)到3號(hào)點(diǎn)之間為直線型道路段；4號(hào)點(diǎn)處為右拐，6號(hào)點(diǎn)處為左拐，依據(jù)這些特征也可以劃分出彎曲[15]。另外，在頂點(diǎn)刪除過(guò)程中不能破壞線之間的空間關(guān)系，如同3(c)所示，可以通過(guò)柵格索引計(jì)算當(dāng)前頂點(diǎn)與前后兩頂點(diǎn)構(gòu)成的三角形內(nèi)是否包含其他頂點(diǎn)來(lái)判斷頂點(diǎn)的刪除是否會(huì)破壞空間關(guān)系。

圖3 頂點(diǎn)刪除的約束Fig.3 Constraints on vertex deletion

在提取了道路幾何特征和語(yǔ)義信息基礎(chǔ)后，可對(duì)道路頂點(diǎn)進(jìn)行刪除。設(shè)β為距離閾值。對(duì)于直線型道路段，如圖4(a)所示，其兩端的頂點(diǎn)(A和B)不能刪除。對(duì)于位于直線型道路段內(nèi)部的點(diǎn)，若D[i-1,i]>β且D[i,i+1]>β，則按照導(dǎo)航要求保留該頂點(diǎn)，如圖4(b)中的C點(diǎn)，否則就刪除，如圖4(a)中的D點(diǎn)和E點(diǎn)。對(duì)于曲線型道路段部分上的頂點(diǎn)，在頂點(diǎn)刪除過(guò)程中需要考慮其周?chē)目臻g環(huán)境，處理方法如下:

(1) 當(dāng)D[i,i-1]<β時(shí)，如圖5(a)所示，可以直接刪除Vi點(diǎn)；若在刪除Vi點(diǎn)后會(huì)破壞線之間的空間關(guān)系，如圖5(b)所示，則不能刪除Vi點(diǎn)，此時(shí)應(yīng)將Vi點(diǎn)標(biāo)記為“問(wèn)題點(diǎn)”，正常處理完所有道路之后進(jìn)行迭代處理。

(2) 當(dāng)D[i,i-1]>β且D[i,i+1]<β時(shí)，需要在Vi和Vi+1兩個(gè)點(diǎn)內(nèi)刪除一個(gè)點(diǎn)。計(jì)算Vi+1點(diǎn)后段直線段的長(zhǎng)度D[i+1,i+2]，若D[i+1,i+2]>β，則比較Vi點(diǎn)和Vi+1點(diǎn)處的轉(zhuǎn)向角的大小，如圖5(c)所示。當(dāng)在Vi點(diǎn)處的轉(zhuǎn)向角θi小于Vi+1點(diǎn)處的轉(zhuǎn)向角θi+1時(shí)，刪除Vi點(diǎn)，否則如圖5(d)所示，暫不刪除Vi點(diǎn)，將Vi點(diǎn)標(biāo)記為問(wèn)題點(diǎn)，待迭代時(shí)再進(jìn)行判斷。若D[i+1,i+2]<β時(shí)，在兩種情況下可以刪除Vi點(diǎn)，如圖5(e)所示。當(dāng)Vi點(diǎn)處的轉(zhuǎn)向角θi小于導(dǎo)航規(guī)定的閾值，即Vi點(diǎn)與前后兩個(gè)頂點(diǎn)近似在一條直線上時(shí)，可以刪除Vi點(diǎn)；當(dāng)Vi+1點(diǎn)處的轉(zhuǎn)向角θi+1大于定義的閾值時(shí)，如圖5(f)所示，可以刪除Vi點(diǎn)。其他情況下均不能刪除Vi點(diǎn)，需將Vi點(diǎn)標(biāo)記為問(wèn)題點(diǎn)，待迭代時(shí)再進(jìn)行判別。

圖4 直線型道路頂點(diǎn)壓縮Fig.4 Compression of vertices on linear roads

圖5 彎曲型道路頂點(diǎn)刪除Fig.5 Deletion of vertices on curved roads

對(duì)于已標(biāo)記的所有問(wèn)題點(diǎn)，需要迭代處理，重新對(duì)上一輪處理時(shí)不滿足約束條件，且暫時(shí)沒(méi)有處理的頂點(diǎn)進(jìn)行判斷。根據(jù)約束條件，迭代處理所有問(wèn)題點(diǎn)，直至滿足約束條件。在迭代時(shí)需要重新對(duì)問(wèn)題點(diǎn)Vi計(jì)算其特征信息，根據(jù)問(wèn)題點(diǎn)不同的空間環(huán)境進(jìn)行處理，處理方法如下：

(1) 若問(wèn)題點(diǎn)滿足條件：D[i,i-1]>β且D[i,i+1]>β，就不再刪除該點(diǎn)，取消Vi的問(wèn)題標(biāo)記。否則，仍按照彎曲部分的處理方式進(jìn)行處理。

(2) 對(duì)于Vi點(diǎn)，如圖6(a)所示，D[i,i-1]>β且D[i,i+1]<β，并且刪除Vi點(diǎn)后不再破壞道路之間的空間拓?fù)潢P(guān)系，刪除Vi點(diǎn)。

(3) 若刪除Vi點(diǎn)后會(huì)破壞道路之間的空間拓?fù)潢P(guān)系，如圖6(b)所示，則刪除Vi點(diǎn)兩側(cè)的點(diǎn)；但是，若Vi點(diǎn)兩側(cè)的點(diǎn)中也不滿足刪除條件，如圖6(c)所示，則不刪除Vi點(diǎn)兩側(cè)的點(diǎn)，并將Vi點(diǎn)標(biāo)記為問(wèn)題點(diǎn),留待移位或人工編輯處理。

圖6 迭代處理Fig.6 Iterative processing

2.3 道路局部空間方向關(guān)系維護(hù)

在5位精度下，原始7位精度的一個(gè)點(diǎn)的可選位置有4個(gè)。道路內(nèi)部空間方向關(guān)系的維護(hù)就是在這4個(gè)位置中選擇最優(yōu)的位置，使維護(hù)后的線同原始精度下的線在空間方向關(guān)系上最相似。本文采用導(dǎo)航數(shù)據(jù)精度降低前后的頂點(diǎn)轉(zhuǎn)向角偏差或節(jié)點(diǎn)(道路交叉點(diǎn))關(guān)聯(lián)的直線段方位角偏差和點(diǎn)的位置偏差作為局部空間方向關(guān)系相似程度的評(píng)價(jià)指標(biāo)。

對(duì)于一般頂點(diǎn)Vi，如圖7(b)所示，按照頂點(diǎn)編號(hào)順序進(jìn)行處理。設(shè)Vi-1點(diǎn)的5位精度位置已經(jīng)確定，則當(dāng)前頂點(diǎn)Vi的空間方向關(guān)系受Vi-1和Vi+1的5位精度位置影響。首先，對(duì)Vi點(diǎn)的4個(gè)可能的5位精度位置，計(jì)算對(duì)應(yīng)的Vi-1點(diǎn)處的轉(zhuǎn)向角偏差Δθi-1，選取其中滿足約束條件的位置作為可選的一個(gè)或多個(gè)位置。然后，對(duì)于每個(gè)可選的位置，再與Vi+1點(diǎn)的4個(gè)可能5位精度位置相連接，計(jì)算每個(gè)連接在Vi點(diǎn)處轉(zhuǎn)向角的7位精度與5位精度之間的轉(zhuǎn)向角偏差Δθi，選擇其中偏差最小的位置作為調(diào)整后的位置。同理，若有多個(gè)轉(zhuǎn)向角偏差都與最小偏差相當(dāng)，則選擇在5位精度下點(diǎn)位置偏差最小的點(diǎn)作為調(diào)整后的優(yōu)選位置。

圖7 道路局部空間方向關(guān)系維護(hù)Fig.7 Maintenance of local spatial directional relations of roads

另外，在道路局部空間方向關(guān)系調(diào)整的過(guò)程中，可能會(huì)出現(xiàn)與原始點(diǎn)處的道路轉(zhuǎn)向相反，這不符合約束條件。但是，若原始點(diǎn)在近似一條直線上，調(diào)整前后的轉(zhuǎn)向角偏差Δθi很小，即使道路轉(zhuǎn)向相反，也認(rèn)為符合約束條件，其中，轉(zhuǎn)向角偏差Δθi的閾值為一個(gè)大于0的很小的值。若Δθi大于閾值，就按照前文所提到的方法處理。道路局部空間方向關(guān)系維護(hù)的目標(biāo)函數(shù)和約束條件見(jiàn)式(1)

(1)

2.4 道路局部的視覺(jué)光滑

當(dāng)導(dǎo)航道路數(shù)據(jù)的精度降低時(shí)，在道路局部可能存在尖角點(diǎn)和抖動(dòng)點(diǎn)，在導(dǎo)航道路數(shù)據(jù)可視化時(shí)就需要進(jìn)行光滑處理。已有許多曲線光滑算法，其中比較常見(jiàn)的方法是用擬合的曲線逼近原始曲線[25-26]，但是在網(wǎng)格模型中由于受到網(wǎng)格精度的限制，新生成的5位精度曲線無(wú)法實(shí)現(xiàn)數(shù)學(xué)意義上的光滑。本文從道路視覺(jué)光滑的角度，提出了一種顧及道路局部視覺(jué)認(rèn)知規(guī)律的光滑算法。

首先，需要提取5位精度下道路的尖角點(diǎn)和抖動(dòng)點(diǎn)，在Vi點(diǎn)處為尖角點(diǎn)的判定條件為：|θi|>β，其中，β為轉(zhuǎn)向角閾值。當(dāng)與Vi點(diǎn)相鄰的頂點(diǎn)的轉(zhuǎn)向角方向同時(shí)變化時(shí)，則認(rèn)為在該點(diǎn)處發(fā)生了抖動(dòng)，Vi點(diǎn)為抖動(dòng)點(diǎn)。但是，從道路可視化上看，若Vi點(diǎn)兩側(cè)直線段的長(zhǎng)度都比較長(zhǎng)，則該點(diǎn)就不是抖動(dòng)點(diǎn)。抖動(dòng)點(diǎn)的條件見(jiàn)式(2)

其次，閱讀作為作文素材的來(lái)源，需要學(xué)生在平時(shí)課外閱讀或是看到課文中的好的詞語(yǔ)和句子時(shí)，摘抄到一個(gè)本子上，收集起來(lái)，便于使用時(shí)查找，例如“問(wèn)渠那得清如許？為有源頭活水來(lái)”的名詩(shī)。又如朱自清在《春》中是這么描寫(xiě)南方春雨的，“看，像牛毛，像花針，像細(xì)絲，密密地斜織著，人家屋頂上全籠著一層薄煙”。胸中有墨水，下筆之時(shí)才能夠信手拈來(lái)、旁征博引。

(2)

式中，θi為i點(diǎn)處的轉(zhuǎn)向角；D[i,i-1]和D[i,i+1]為當(dāng)前點(diǎn)Vi前后兩條直線段的長(zhǎng)度；d為長(zhǎng)度閾值。

尖角點(diǎn)處的光滑插值方法如圖8(a)所示。設(shè)∠COD為需要光滑的尖角，O點(diǎn)處的道路轉(zhuǎn)向角為θi，A和B為待插入的點(diǎn)，|OA|和|OB|為插入線段的長(zhǎng)度，β2和β3分別為插入線段OA和OB與直線L2的夾角，L1為∠COD的角平分線，L2垂直于L1,并相交于O點(diǎn)。下面以A點(diǎn)的位置計(jì)算為例，說(shuō)明插入A點(diǎn)的過(guò)程：

(1) 計(jì)算OA與OC向量的夾角，β5=90°-β1/2-β2。

(2) 將O設(shè)為坐標(biāo)原點(diǎn)，以O(shè)C為X軸的正方向構(gòu)建臨時(shí)坐標(biāo)系，則可用式(3)計(jì)算點(diǎn)A在該臨時(shí)坐標(biāo)系中的坐標(biāo)

(3)

(3) 將臨時(shí)坐標(biāo)系下的坐標(biāo)轉(zhuǎn)換為原始坐標(biāo)系下的坐標(biāo)，見(jiàn)式(4)

(4)

式中，X、Y為原始坐標(biāo)系下點(diǎn)的坐標(biāo)；θ為臨時(shí)坐標(biāo)系下向量OC與原始X軸正方向的夾角；a、b為臨時(shí)坐標(biāo)系原點(diǎn)O平移到原坐標(biāo)系原點(diǎn)在X、Y軸方向上的平移距離。

(4) 計(jì)算所得的點(diǎn)為7位精度，需要轉(zhuǎn)換為5位精度，并從4個(gè)可能位置中選擇最優(yōu)的位置，條件是：①OA的長(zhǎng)度大于導(dǎo)航需求中的距離閾值；②OA與OC之間夾角最??；③插入點(diǎn)A后,β6應(yīng)反映局部形狀特征，即β6×θi>0;對(duì)于B點(diǎn)而言，則是β7×θi>0。

抖動(dòng)點(diǎn)的處理如圖8(b)所示。設(shè)長(zhǎng)度閾值為dis；Vi點(diǎn)前后兩條直線段的長(zhǎng)度分別為D[i,i-1]和D[i,i+1]。抖動(dòng)點(diǎn)處理方法是：若D[i,i-1]>dis，且D[i,i+1]>dis，則不處理，如圖8(b)的第4號(hào)點(diǎn)；否則，用短直線段的中點(diǎn)代替原始的頂點(diǎn)，如圖8(b)中帶圓圈的第1、2、3、5、6號(hào)點(diǎn)分別代替原始的第1、2、3、5、6號(hào)點(diǎn)。

圖8 道路視覺(jué)光滑的計(jì)算方法Fig.8 Calculation method on visual smoothing of roads

3 節(jié)點(diǎn)處空間方向關(guān)系維護(hù)

導(dǎo)航中道路網(wǎng)節(jié)點(diǎn)處的道路走向十分重要。如圖9所示，道路節(jié)點(diǎn)A與3條道路線相關(guān)聯(lián)，當(dāng)導(dǎo)航道路數(shù)據(jù)從7位精度降為5位精度時(shí)，需要保持節(jié)點(diǎn)A處3條道路之間的空間方向關(guān)系。這種空間方向關(guān)系，本文用各條道路繞節(jié)點(diǎn)A的空間方位間接表達(dá)，并只考慮與節(jié)點(diǎn)A直接關(guān)聯(lián)的直線段(AA1、AA2、AA3)的空間方位。從圖9可以看出，這里之所以用AA3，而不是AA4，是因?yàn)樾枰紤]到道路段AD是一條直線，這是一個(gè)非常重要的導(dǎo)航信息。

如圖10所示，道路網(wǎng)節(jié)點(diǎn)A與點(diǎn)B關(guān)聯(lián)，A點(diǎn)和B點(diǎn)在5位精度下的可能位置均為4個(gè)，因此A點(diǎn)和B點(diǎn)的可能連接方式共有4×4=16個(gè)。計(jì)算所有連接方式的方位角，將所得的16個(gè)方位角同原始的7位精度下AB的方位角進(jìn)行比較，優(yōu)選偏差最小的連接。當(dāng)有多個(gè)可能的連接都與原始直線段AB的空間方向關(guān)系非常相似時(shí)，則比較這些連接與原始直線段AB之間的位置偏差。這里的位置偏差定義為節(jié)點(diǎn)A的可能位置同原始精度位置之間的距離。同理，對(duì)于B點(diǎn)的5位精度位置也是按照這種條件判斷，從而間接控制線段AB的長(zhǎng)度偏差盡量小。如圖10所示，藍(lán)色的A2B2連接和紅色的A1B1連接都與原始直線段AB的空間方向關(guān)系非常相似，但是，A1離A更近，因此選擇A1B1連接方式。

圖9 道路網(wǎng)節(jié)點(diǎn)處的空間場(chǎng)景Fig.9 Spatial scene at the junction of a road network

當(dāng)?shù)缆肪W(wǎng)節(jié)點(diǎn)關(guān)聯(lián)多個(gè)點(diǎn)時(shí)，就需要考慮與道路網(wǎng)節(jié)點(diǎn)A關(guān)聯(lián)的所有直線段與原始直線段之間空間方向關(guān)系的整體相似程度。設(shè)節(jié)點(diǎn)A與M條直線段相關(guān)聯(lián)，這些原始直線段的方位角為AZ(i)，其中，i=1,2,…,M；5位精度下可能形成的直線段方位角為AZP(i，k,j)，其中，i=1,2,…,M；k為節(jié)點(diǎn)A的可能位置，k=0,1,2,3;j為與節(jié)點(diǎn)A相鄰的點(diǎn)(i=1,2,…,M)的可能位置，j=0,1,2,3。當(dāng)數(shù)據(jù)精度降低時(shí)，在節(jié)點(diǎn)A處空間場(chǎng)景中具有空間方向關(guān)系最相似程度的優(yōu)選點(diǎn)位置的計(jì)算方法見(jiàn)式(5)

(5)

式中，f1(k)為點(diǎn)A在k位置下與M條直線段方位角偏差之和；f2(i，k)為點(diǎn)A在k位置下與第i條直線段的方位角偏差；f3(k)為點(diǎn)A在k位置下7位精度與5位精度的距離偏差，V5(i,k)為點(diǎn)A在k位置下5位精度的坐標(biāo)，V7(i)為點(diǎn)A在7位精度下的坐標(biāo)；β為角度閾值，當(dāng)f1(k)≤β時(shí)，即當(dāng)方位角偏差之和變化都比較小時(shí)，優(yōu)選點(diǎn)A位置偏差最小的位置。

為了使得整個(gè)道路網(wǎng)所有節(jié)點(diǎn)處的空間方向關(guān)系整體上盡量保證與原始精度時(shí)的空間方向關(guān)系最相似，本文先對(duì)節(jié)點(diǎn)的連接度進(jìn)行排序，然后優(yōu)先處理連接度較大的節(jié)點(diǎn)。另外，在數(shù)據(jù)處理的過(guò)程中，由于當(dāng)前處理的節(jié)點(diǎn)可能關(guān)聯(lián)了已經(jīng)處理的節(jié)點(diǎn)或被動(dòng)處理的交叉點(diǎn)，因此對(duì)于已經(jīng)處理過(guò)的節(jié)點(diǎn)位置就不再調(diào)整。算法流程如下：

(1) 掃描所有道路節(jié)點(diǎn)，獲取與每個(gè)節(jié)點(diǎn)相連接的所有道路直線段。

(2) 根據(jù)節(jié)點(diǎn)所關(guān)聯(lián)的道路直線段的數(shù)量(節(jié)點(diǎn)連接度)，對(duì)節(jié)點(diǎn)進(jìn)行排序。

(3) 按順序選取要處理的節(jié)點(diǎn)。

(4) 計(jì)算當(dāng)前節(jié)點(diǎn)與關(guān)聯(lián)點(diǎn)在精度降低時(shí)的所有可能連接方式，對(duì)每種連接方式計(jì)算方位角偏差，利用式(5)判斷當(dāng)前節(jié)點(diǎn)的最優(yōu)位置。

4 生產(chǎn)試驗(yàn)與分析

筆者采用C#開(kāi)發(fā)了用于導(dǎo)航道路數(shù)據(jù)綜合(從7位精度轉(zhuǎn)為5位精度)的算法試驗(yàn)軟件，已用于多個(gè)城市的5位精度導(dǎo)航數(shù)據(jù)試生產(chǎn)。本文選取重慶市主城區(qū)7位精度的導(dǎo)航道路網(wǎng)數(shù)據(jù)用于算法分析。該數(shù)據(jù)集共包含道路53 525條和233 584個(gè)點(diǎn)，其中，道路網(wǎng)節(jié)點(diǎn)有8514個(gè)。圖11為生產(chǎn)試驗(yàn)中的部分?jǐn)?shù)據(jù)，整個(gè)數(shù)據(jù)處理流程見(jiàn)圖12。

為了滿足導(dǎo)航道路數(shù)據(jù)從7位精度降為5位精度的需要，在生產(chǎn)試驗(yàn)中設(shè)置了相應(yīng)的參數(shù)和閾值，設(shè)判定直線的轉(zhuǎn)向角閾值為2°；點(diǎn)之間的最小距離閾值為2 m；最大距離閾值設(shè)為5 m；轉(zhuǎn)向角偏差閾值為6°；判定“尖角”的角度閾值為30°；7位精度下插入線段的長(zhǎng)度為2.5 m。圖13是圖11中方框區(qū)域的試驗(yàn)結(jié)果，黑色表示7位精度的目標(biāo)，綠色表示5位精度的目標(biāo)。

圖14為圖13中紅色方框區(qū)域的放大圖。圖14(a)為道路頂點(diǎn)漸進(jìn)式刪除的結(jié)果，紅色表示綜合后的目標(biāo)；圖14(b)為道路空間方向維護(hù)的結(jié)果，藍(lán)色表示空間方向關(guān)系維護(hù)后的目標(biāo)；圖14(c)為道路視覺(jué)光滑后的結(jié)果，黃色表示光滑后的目標(biāo)。

圖11 高精度的道路網(wǎng)數(shù)據(jù)Fig.11 Road network data with high precision

圖12 導(dǎo)航道路圖形化簡(jiǎn)的流程Fig.12 Flow chart of graphic simplification for navigation roads

圖13 導(dǎo)航道路圖形化簡(jiǎn)的結(jié)果Fig.13 The result of graphic simplification for navigation roads

圖14 綜合過(guò)程中各階段的指定局部放大圖Fig.14 Enlarged maps of the given local region in each stage of generalization

在道路圖形簡(jiǎn)化過(guò)程中，空間方向關(guān)系維護(hù)是非常重要的一個(gè)環(huán)節(jié)，在點(diǎn)之間的最小距離閾值為2 m的情況下，本文分別統(tǒng)計(jì)了試驗(yàn)結(jié)果中道路網(wǎng)節(jié)點(diǎn)和道路頂點(diǎn)處的空間方向關(guān)系維護(hù)效果。圖15是道路網(wǎng)節(jié)點(diǎn)處空間方向關(guān)系維護(hù)結(jié)果的統(tǒng)計(jì)圖，橫軸表示與節(jié)點(diǎn)連接的道路直線段方位角在空間方向關(guān)系維護(hù)前后的角度變化區(qū)間；縱軸表示在角度變化區(qū)間內(nèi)的直線段統(tǒng)計(jì)數(shù)量；藍(lán)色表示調(diào)整前；橘黃色表示調(diào)整后。圖16是道路頂點(diǎn)處空間方向關(guān)系維護(hù)結(jié)果的統(tǒng)計(jì)圖，橫軸表示道路頂點(diǎn)處轉(zhuǎn)向角在空間方向關(guān)系維護(hù)前后的角度變化區(qū)間；縱軸表示在角度變化區(qū)間內(nèi)的頂點(diǎn)統(tǒng)計(jì)數(shù)量；藍(lán)色表示調(diào)整前；橘黃色表示調(diào)整后。從統(tǒng)計(jì)圖表中可以看出，本文的空間方向關(guān)系維護(hù)算法使得道路網(wǎng)節(jié)點(diǎn)處和道路頂點(diǎn)處的空間方向變化比直接使用四舍五入轉(zhuǎn)換方法的空間方向變化明顯減少。

圖15 節(jié)點(diǎn)處空間方向關(guān)系維護(hù)結(jié)果的統(tǒng)計(jì)Fig.15 Statistics of results at nodes after maintaining spatial directional relations

圖16 道路頂點(diǎn)處空間方向關(guān)系維護(hù)結(jié)果的統(tǒng)計(jì)Fig.16 Statistics of results at vertices after maintaining spatial directional relations

當(dāng)最小距離閾值為2 m時(shí)，本試驗(yàn)結(jié)果中沒(méi)有出現(xiàn)拓?fù)潢P(guān)系方面的問(wèn)題點(diǎn)。當(dāng)設(shè)置最小距離閾值為5 m時(shí)，就出現(xiàn)了拓?fù)潢P(guān)系方面的問(wèn)題點(diǎn)。如圖17所示(7位精度的線為綠色；5位精度的線為棕色)，問(wèn)題點(diǎn)A不滿足最小距離閾值條件，但是若刪除該點(diǎn)，在點(diǎn)C2處就會(huì)出現(xiàn)拓?fù)潢P(guān)系錯(cuò)誤。圖17中藍(lán)色線表示刪除A點(diǎn)后出現(xiàn)的拓?fù)潢P(guān)系破壞情況，從B1到B14是不可以刪除的道路立體交叉點(diǎn)，C1和C2是導(dǎo)航地圖模型中定義的不可刪除點(diǎn)。在5位精度的導(dǎo)航地圖數(shù)據(jù)生產(chǎn)中，點(diǎn)之間的距離有嚴(yán)格規(guī)定，若道路簡(jiǎn)化后存在點(diǎn)之間的距離小于設(shè)置的距離閾值，就標(biāo)識(shí)這些點(diǎn)為問(wèn)題點(diǎn)，以便有針對(duì)性地進(jìn)行人工數(shù)據(jù)編輯。當(dāng)導(dǎo)航地圖數(shù)據(jù)可視化時(shí)，若道路頂點(diǎn)處轉(zhuǎn)彎很急，符號(hào)化后的道路圖形就顯得不光滑，本文所提出的視覺(jué)光滑算法能很好地解決這個(gè)問(wèn)題。將本文方法與ArcGIS中常用的PAEK光滑算法進(jìn)行對(duì)比，結(jié)果如圖18所示。

圖17 存在拓?fù)潢P(guān)系錯(cuò)誤的問(wèn)題點(diǎn)Fig.17 Points with questions about topological errors

圖18 兩種光滑結(jié)果的對(duì)比Fig.18 Comparison between two kinds of smoothing results

5位精度的導(dǎo)航地圖數(shù)據(jù)生產(chǎn)有嚴(yán)格的要求，相關(guān)的導(dǎo)航需求是：點(diǎn)之間的距離大于2 m；道路網(wǎng)節(jié)點(diǎn)處關(guān)聯(lián)的道路之間的空間方向關(guān)系變形最??；道路頂點(diǎn)處的轉(zhuǎn)向角變化最小；所有點(diǎn)的位置誤差小于1.42 m；空間目標(biāo)之間的拓?fù)潢P(guān)系應(yīng)該與7位精度的導(dǎo)航地圖原始數(shù)據(jù)一致；簡(jiǎn)化后的道路不能出現(xiàn)抖動(dòng)和急轉(zhuǎn)彎情況；點(diǎn)之間的距離也需要小于5 m(用戶定義的最大距離閾值)。這些要求在整個(gè)道路網(wǎng)圖形簡(jiǎn)化過(guò)程中都需要進(jìn)行判斷，若存在不滿足要求的點(diǎn)，筆者所開(kāi)發(fā)的軟件就自動(dòng)進(jìn)行標(biāo)記，說(shuō)明是問(wèn)題點(diǎn)。

在試驗(yàn)中也使用ArcGIS10.2的兩種線化簡(jiǎn)方法(點(diǎn)刪除方法和彎曲化簡(jiǎn)方法)對(duì)同樣的數(shù)據(jù)集進(jìn)行了處理。以四維圖新導(dǎo)航地圖的需求為標(biāo)準(zhǔn)，對(duì)比分析了ArcGIS的處理結(jié)果和本文算法軟件試生產(chǎn)的結(jié)果。

試驗(yàn)用的計(jì)算機(jī)配置條件是：Intel(R) Core(TM)i7-4790 CPU@3.60 GHz,RAM: 8 GB,windows10,64位。ArcGIS的彎曲化簡(jiǎn)方法在無(wú)選項(xiàng)，閾值為5 m的條件下，耗時(shí)60 s；ArcGIS的點(diǎn)刪除方法在無(wú)選項(xiàng)、閾值為2 m的條件下，耗時(shí)54 s；本文的化簡(jiǎn)算法耗時(shí)172.39 s，空間方向關(guān)系維護(hù)耗時(shí)238.13 s，空間拓?fù)潢P(guān)系維護(hù)耗時(shí)25.97 s，視覺(jué)光滑耗時(shí)17.07 s。由此可以看出，本文算法耗時(shí)比較多。主要原因是本文算法在化簡(jiǎn)階段需要判斷和維護(hù)空間拓?fù)潢P(guān)系，為了滿足導(dǎo)航需求，還需要維護(hù)空間方向關(guān)系和視覺(jué)光滑效果。而ArcGIS的這兩種方法都沒(méi)有考慮這些空間關(guān)系的維護(hù)。

在原始試驗(yàn)數(shù)據(jù)(重慶市主城區(qū))中道路有233 584個(gè)點(diǎn)，用本文算法簡(jiǎn)化后，保留了119 938個(gè)點(diǎn)，光滑后有129 884個(gè)點(diǎn)。按照本文描述的5位精度下的導(dǎo)航要求，檢查了這3個(gè)試驗(yàn)結(jié)果，產(chǎn)生差異的原因是：點(diǎn)刪除方法只考慮了點(diǎn)的偏移量，彎曲化簡(jiǎn)方法只考慮了彎曲的大小，它們都沒(méi)有考慮保留點(diǎn)之間的距離應(yīng)該在導(dǎo)航規(guī)定的距離閾值范圍內(nèi)。圖19是這3種方法所得結(jié)果的局部放大圖，可以直觀地了解它們之間的差異。在圖形化簡(jiǎn)算法的對(duì)比試驗(yàn)中，ArcGIS的兩個(gè)線圖形化簡(jiǎn)工具無(wú)法直接表達(dá)導(dǎo)航道路數(shù)據(jù)生產(chǎn)的要求，本文依據(jù)5位數(shù)據(jù)精度導(dǎo)航道路數(shù)據(jù)生產(chǎn)對(duì)點(diǎn)之間距離的要求，設(shè)置了近似的閾值。

在生產(chǎn)試驗(yàn)中，道路圖形化簡(jiǎn)算法和空間拓?fù)潢P(guān)系維護(hù)算法的參數(shù)是按照四維圖新5位數(shù)據(jù)精度導(dǎo)航地圖生產(chǎn)的具體要求設(shè)置；空間方向關(guān)系維護(hù)算法和視覺(jué)光滑算法的有關(guān)角度的閾值是按照生產(chǎn)單位對(duì)導(dǎo)航道路數(shù)據(jù)的要求在進(jìn)行了多次試驗(yàn)和調(diào)整后確定，是經(jīng)驗(yàn)值。

圖19 3種方法所得結(jié)果的局部放大圖Fig.19 Enlarged maps of partial results of three kinds of methods

在試驗(yàn)中所使用的漸進(jìn)式道路圖形簡(jiǎn)化方法充分利用了道路頂點(diǎn)漸進(jìn)式刪除、空間方向關(guān)系維護(hù)和視覺(jué)光滑等操作。這里的“漸進(jìn)式”主要體現(xiàn)在：當(dāng)?shù)缆讽旤c(diǎn)刪除時(shí)，必須保證滿足道路圖形簡(jiǎn)化的約束條件；若無(wú)法滿足這些約束條件，就需要臨時(shí)標(biāo)記該頂點(diǎn)為問(wèn)題點(diǎn)，并記錄其位置，然后在空間上下文關(guān)系發(fā)生變化后再回頭來(lái)處理這些問(wèn)題點(diǎn)，該過(guò)程是一個(gè)迭代過(guò)程。當(dāng)需要從7位精度的道路數(shù)據(jù)綜合為5位精度的道路數(shù)據(jù)時(shí)，在試驗(yàn)中并不是先綜合為6位精度的道路數(shù)據(jù)，再綜合為5位精度的道路數(shù)據(jù)。

5 總 結(jié)

本文基于網(wǎng)格模型有效表達(dá)了高精度導(dǎo)航數(shù)據(jù)向低精度導(dǎo)航數(shù)據(jù)的轉(zhuǎn)換過(guò)程，詳細(xì)說(shuō)明了5位數(shù)據(jù)精度導(dǎo)航道路數(shù)據(jù)生產(chǎn)的特殊要求，將道路圖形化簡(jiǎn)、導(dǎo)航地圖要素之間空間拓?fù)潢P(guān)系維護(hù)、道路本身和道路網(wǎng)交叉點(diǎn)處空間方向關(guān)系維護(hù)以及道路數(shù)據(jù)可視化的視覺(jué)光滑等算法協(xié)同在一起，提出了一種基于網(wǎng)格模型的導(dǎo)航道路圖形漸進(jìn)式協(xié)同化簡(jiǎn)方法。在該方法中，網(wǎng)格模型體現(xiàn)了導(dǎo)航數(shù)據(jù)的表達(dá)需求；在道路圖形化簡(jiǎn)過(guò)程中強(qiáng)調(diào)了漸進(jìn)式質(zhì)量控制；協(xié)同了空間關(guān)系維護(hù)和視覺(jué)光滑；在點(diǎn)刪除過(guò)程中綜合考慮了點(diǎn)之間的距離、點(diǎn)的語(yǔ)義特征和點(diǎn)附近的空間關(guān)系；依據(jù)導(dǎo)航數(shù)據(jù)網(wǎng)格模型表達(dá)的特征和視覺(jué)認(rèn)知規(guī)律，設(shè)計(jì)了道路的視覺(jué)光滑方法。從試驗(yàn)結(jié)果看，本文所提出的方法顧及了導(dǎo)航需求，能夠維護(hù)好道路網(wǎng)在數(shù)據(jù)精度降低時(shí)的空間方向關(guān)系，圖形的可視化效果好。但是，本文所提出的方法在導(dǎo)航道路網(wǎng)向更低精度轉(zhuǎn)換時(shí)如何與道路選取相結(jié)合還有待進(jìn)一步的研究。該方法是針對(duì)5位精度的導(dǎo)航道路數(shù)據(jù)生產(chǎn)特點(diǎn)所提出的，制圖綜合的約束主要是點(diǎn)之間的最小距離、原始點(diǎn)的最大偏移距離、道路轉(zhuǎn)彎方向和大小、道路連接關(guān)系、視覺(jué)光滑程度等，道路圖形簡(jiǎn)化的主要任務(wù)是在保留道路(網(wǎng))的導(dǎo)航所需要信息條件下刪除多余的道路頂點(diǎn)。因此本文所提出的方法并不直接適用于制圖約束條件性質(zhì)不同的線圖形簡(jiǎn)化任務(wù)。