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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 基本思想

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

2.2 道路頂點的刪除方法

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

圖3 頂點刪除的約束Fig.3 Constraints on vertex deletion

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

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

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

圖4 直線型道路頂點壓縮Fig.4 Compression of vertices on linear roads

圖5 彎曲型道路頂點刪除Fig.5 Deletion of vertices on curved roads

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

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

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

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

圖6 迭代處理Fig.6 Iterative processing

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

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

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

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

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

(1)

2.4 道路局部的視覺光滑

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

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

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

(2)

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

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

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

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

(3)

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

(4)

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

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

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

圖8 道路視覺光滑的計算方法Fig.8 Calculation method on visual smoothing of roads

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

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

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

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

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

(5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總 結(jié)

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