面向嵌入式gis應(yīng)用的地圖標(biāo)注算法設(shè)計課件

面向嵌入式GIS

地圖標(biāo)注算法設(shè)計與實現(xiàn)2007年04月中山大學(xué)智能交通實驗室1.地圖標(biāo)注的相關(guān)概念2.標(biāo)注算法研究現(xiàn)狀3.基于柵格的地圖標(biāo)注算法4.試驗結(jié)果主要內(nèi)容1.地圖標(biāo)注的相關(guān)概念2.標(biāo)注算法研究現(xiàn)狀3.基于柵格的地圖標(biāo)注算法4.試驗結(jié)果主要內(nèi)容地圖標(biāo)注的相關(guān)概念

地圖標(biāo)注的評價方式標(biāo)注位置的是否選擇恰當(dāng)是否排列美觀是否清晰易讀

地圖標(biāo)注的研究重點如何控制標(biāo)注的位置和布局解決標(biāo)注之間的沖突和壓蓋問題

地圖標(biāo)注間沖突與壓蓋沖突：標(biāo)注與其它標(biāo)注之間出現(xiàn)重疊情況壓蓋：標(biāo)注遮擋關(guān)鍵地圖要素的情況

電子地圖使用價值地圖標(biāo)注的基本原則

地圖標(biāo)注可分為點、線、面三類考慮，都應(yīng)遵循的基本原則：“所屬關(guān)系”

確定標(biāo)注與被標(biāo)注目標(biāo)之間的所屬關(guān)系“避讓”

避開重要地物，尤其不能壓蓋同種顏色的其它地物“習(xí)慣”

標(biāo)注的字位、字序、排列方式要符合讀圖習(xí)慣1.地圖標(biāo)注的相關(guān)概念2.標(biāo)注算法研究現(xiàn)狀3.基于柵格的地圖標(biāo)注算法4.試驗結(jié)果主要內(nèi)容-

-

-

貪婪算法模擬退火窮盡搜索其它啟發(fā)算法回溯算法

經(jīng)典算法研究現(xiàn)狀

標(biāo)注算法回顧經(jīng)典標(biāo)注算法貪婪算法:優(yōu)點是運算速度快，對每個要素只標(biāo)注一次，但對于被壓蓋的標(biāo)注并沒有重新定位。回溯算法:

補償了貪婪算法的不足，對被壓蓋的標(biāo)注通過回溯處理來重新定位，雖然可通過限定候選位置個數(shù)與回溯深度來加快標(biāo)注位置計算，但其時間上的開銷仍然不利于在嵌入式GIS系統(tǒng)中應(yīng)用。目前研究成果表明：質(zhì)量最高的是模擬退火算法。其標(biāo)注效率要優(yōu)于上述其它算法，但模擬退火的時間消耗大。模擬退火算法模擬退火算法是解決地圖標(biāo)注問題的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地將其應(yīng)用在組合最優(yōu)化問題中。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解→計算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值,基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。算法終止條件:當(dāng)前解即為所得近似最優(yōu)解模擬退火算法該算法將地圖各要素注記的配置作為一個統(tǒng)一的整體來對待，從而避免了一般局部搜索法可能終止于一個局部最優(yōu)解的缺點，這樣可使自動注記配置的結(jié)果更趨合理化。用模擬退火算法進行注記自動配置，機理簡單，通用性強，其缺點在于配置速度較慢。其它標(biāo)注算法StevenZoroaster提出的整數(shù)規(guī)劃法武漢大學(xué)的樊紅提出的神經(jīng)網(wǎng)絡(luò)法等算法

特點：針對點狀地物的標(biāo)注都具有一定的實用性標(biāo)注輸出合理、美觀相對當(dāng)前嵌入式系統(tǒng)的運算能力而言，計算時間較長1.地圖標(biāo)注的相關(guān)概念2.標(biāo)注算法研究現(xiàn)狀3.基于柵格的地圖標(biāo)注算法4.試驗結(jié)果主要內(nèi)容注記沖突與壓蓋檢測策略

采用將屏幕柵格化的方法進行整體檢測地圖數(shù)據(jù)量很大，若逐個檢測，則一個城市就需要處理成千上萬條道路，處理將很耗費時間

處理屏幕柵格化步驟：根據(jù)標(biāo)注字體大小定義柵格邊長進行柵格化

假定標(biāo)注字體大小為8x8象素，屏幕分辨率80x40，

方格邊長定為8個象素，1個方格容納一個標(biāo)注字體定義狀態(tài)數(shù)組描述屏幕各方格裝載的地物要素信息

BYTEGridArray[nRow*nCol]

狀態(tài)數(shù)組中各元素與各個方格一一對應(yīng)，

該元素值表示該方格地圖要素狀態(tài)與類型，其定義如： 0表示可作為候選區(qū)域，1表示已被標(biāo)注區(qū)域， 10表示點狀物，20表示一般道路 30表示高速道路,40表示河流區(qū)域,………..

例如“31”表示該方格為高速道路且已被標(biāo)注。注記沖突與壓蓋檢測策略狀態(tài)數(shù)組初始化在進行注記的搜索前，需要針對不能壓蓋的地圖要素類型，搜索矢量地圖數(shù)據(jù)，對狀態(tài)數(shù)組進行初始化，確定每個方格的類型值搜索狀態(tài)數(shù)組

在進行標(biāo)注位置搜索時可按狀態(tài)數(shù)組的順序進行搜索，遇到對應(yīng)的非0類型值方格，則需要根據(jù)標(biāo)注原則自動避讓，否則將不可避免地注記沖突或壓蓋問題。注記位置的搜索策略先定義一個格子編碼集合VecGridCode：typedefstruct{ DWordnGridCol; //方格列號 DWordnGridRow; //方格行號}GridCode; Vector<GridCode>VecGridCode； //表示候選標(biāo)注位置的方格集合注記位置的搜索策略對于點狀地圖要素標(biāo)注位置的搜索步驟： (1)根據(jù)該點位置,得到其標(biāo)注的四個方向候選位置起始位置

位置優(yōu)先級從高至低為A區(qū)域、B區(qū)域、C區(qū)域、D區(qū)域

(2)判斷各個候選位置是否可用

如圖，以“中”字為例，在其候選區(qū)域間的區(qū)域標(biāo)注中，搜索到一塊連續(xù)的間距合理的標(biāo)注區(qū)域

(3)最后根據(jù)得到的標(biāo)注區(qū)域

根據(jù)得到的標(biāo)注區(qū)域:柵格編碼集合，計算具體的標(biāo)注坐標(biāo)值注記位置的搜索策略對于線狀地圖要素標(biāo)注位置的搜索步驟： (1)獲得道路各弧段的各個關(guān)鍵點，計算其外接矩形內(nèi)部的方格集合

如圖,對于關(guān)鍵點m和關(guān)鍵點n的外接矩形ABCD，其方格編碼集合:{(3,2),(3,3)} (2)

為各弧段尋找足夠的連續(xù)標(biāo)注空間

如圖，以“中山八路”弧段為例，在其所有關(guān)鍵點間的外接矩形候選標(biāo)注區(qū)域中，搜索到一塊連續(xù)的間距合理的標(biāo)注區(qū)域。

間距=整數(shù)倍柵格邊長

(3)計算具體標(biāo)注位置

根據(jù)得到標(biāo)注方格集合，計算標(biāo)注坐標(biāo)值注記位置的搜索策略對于面狀地圖要素的處理方法

與線狀要素相似，同樣是根據(jù)其關(guān)鍵點的外接矩形得到其標(biāo)注候選區(qū)域；

不同的是候選區(qū)域還需要加上面狀要素內(nèi)部區(qū)域和標(biāo)注位置盡可能靠內(nèi)部中央?yún)^(qū)域。

如圖所示，“麓景湖”面狀要素的標(biāo)注區(qū)域落在其內(nèi)部區(qū)域中。若可標(biāo)注的區(qū)域沒有與其它標(biāo)注沖突和受到壓蓋，則可合理地加大標(biāo)注的字體。算法實現(xiàn)步驟創(chuàng)建標(biāo)注字體,將屏幕柵格化,并計算出柵格邊長柵格邊長=字體大小邊長定義一維數(shù)組描述整個屏幕各個小方格狀態(tài)將數(shù)組中每個元素清零從矢量數(shù)據(jù)中尋找不可被壓蓋的地圖要素類型的位置,初始化相應(yīng)的元素計算一條線狀元素的標(biāo)注位置函數(shù):ArrangeArcAnnoPos(DISPARCRECORD&OneArcRecord)以像素為單位，計算標(biāo)注的長度判斷標(biāo)注的大致走向

CRect&rectMBR=OneArcRecord.MBR; if(rectMBR寬度<rectMBR高度) ndirection=TOPDOWN; else ndirection=LEFTRIGHT;得到這一條線狀元素覆蓋的所有小方格計算該道路上可以開始標(biāo)注的位置開始計算標(biāo)注的具體位置計算地圖中所有線狀元素的標(biāo)注位置得到這一條線狀元素覆蓋的所有小方格for(對于線狀元素的每一段短線){for(inti=0;i<nPointNum-1;i++){ArcBeginPoint.x=pPoint[i].x;ArcBeginPoint.y=pPoint[i].y;ArcEndPoint.x=pPoint[i+1].x;ArcEndPoint.y=pPoint[i+1].y; //nLen每個小方格的寬度dColStart=(ArcBeginPoint.x-BoundRect.left)/nLen; //線段覆蓋的起始列號dColEnd=(ArcEndPoint.x-BoundRect.left)/nLen; //線段覆蓋的終止列號 dRowStart=(ArcBeginPoint.y-BoundRect.top)/nLen; ///線段覆蓋的起始行號dRowEnd=(ArcEndPoint.y-BoundRect.top)/nLen; //線段覆蓋的終止行號 for(row=nRowStart;row<=nRowEnd;row++){for(col=nColStart;col<=nColEnd;col++){GridCode.nGridRow=row;GridCode.nGridCol=col;vecGridCode.push_back(GridCode); //存儲覆蓋格子的行號和列號}}}}計算該道路上可以開始標(biāo)注的位置nStart=0; //起始點假設(shè)從第vecGridCode[0]個格子開始nSize=vecGridCode.size(); //得到線狀元素覆蓋的格子個數(shù)for(inti=0;i<nSize;i++) //順序處理覆蓋線狀元素的每一個格子{GRIDCODE&LocalGrid=vecGridCode[i]; //得到這個格子號if(annoMatch[這個格子]!=0) //若非零，表示已經(jīng)被其他標(biāo)注占用{if(道路為東西走向)計算當(dāng)前列與起始列的距離nLengthelse//道路為南北走向計算當(dāng)前行與起始行的距離nLengthif(nLength<=標(biāo)注需要的長度)nStart=i; //從當(dāng)前所處的格子開始，尋找合適的長度進行標(biāo)注else //找到足夠的標(biāo)注位置，則退出break; }}//此時，表示從第nStart格子開始標(biāo)注開始計算標(biāo)注的具體位置intiGridSeq=0; //定義格子序號for(inti=0;i<nAnnoNum;i++) //循環(huán)取得各個字的位置{ //得到這個漢字占用的第一個格子號,其后定長的連續(xù)的格子號均用于標(biāo)注該線狀道路

GridSeq=2*i*GRIDFORHANZI+2*GRIDFORHANZI+nStart; LocalGrid=vecGridCode[iGridSeq]; //相應(yīng)柵格狀態(tài)置1,表示該格子已經(jīng)被標(biāo)注占用,防止標(biāo)注間的沖突 annoMatch[iGridSeq]=1; //計算這個漢字的屏幕坐標(biāo)

PtPos.x=LocalGrid.nGridCol*m_nAnnoGridLen; PtPos.y=LocalGrid.nGridRow*m_nAnnoGridLen; //將得到的屏幕坐標(biāo),作為線狀元素的屬性進行存儲 OneArcRecord.AnnoPosition.push_back(PtPos);}計算地圖中所有線狀元素的標(biāo)注位置

具體步驟：if（當(dāng)前線狀元素不顯示）return;得到當(dāng)前視圖范圍內(nèi)的所有線狀元素設(shè)置文本的背景為透明色，并設(shè)置顏色為黑

for(對于地圖中的每一條長線狀元素) {if(標(biāo)注的長度<=1) continue;ArrangeArcAnnoPos(DISPARCRECORD&OneArcRecord);//即依次計算每條道路的標(biāo)注位置坐標(biāo)，順序存儲到OneArcRecord.AnnoPosition集合中 }1.地圖標(biāo)注的相關(guān)概念2.標(biāo)注算法研究現(xiàn)狀3.基于柵格的地圖標(biāo)注算法4.試驗結(jié)果主要內(nèi)容3.基于柵格的地圖標(biāo)注算法試驗

應(yīng)用上述的設(shè)計思想和實現(xiàn)方法，設(shè)計了基于嵌入式GIS的車輛監(jiān)控系統(tǒng)，提供基本的地圖繪制、信息查詢、GPS定位導(dǎo)航等功能。

系統(tǒng)已經(jīng)實現(xiàn)的功能： (1)基本的地圖操作 (2)空間數(shù)據(jù)信息查詢 (3)距離測算 (4)GPS定位

該系統(tǒng)對標(biāo)注的配置，采用上述的基于柵格的地圖標(biāo)注算法。試驗結(jié)果試驗軟硬件環(huán)境：基于WinCE的PocketPC系統(tǒng)本算法試驗效果：輸出注記密度維持在一定的合理水平地圖標(biāo)注總體效果較好運行速度快，且易于實現(xiàn)總結(jié)

由以上結(jié)果和分析可以看出,該算法特點：(1)在標(biāo)注分布上，采用該算法的標(biāo)注效果較好，標(biāo)注排列較為整齊、分布較為協(xié)調(diào)、數(shù)量適中。 (2)算法思想簡便、計算簡單、易于實現(xiàn)。尤其在嵌入式應(yīng)用中具有一定的實用價值。 (3)本算法在設(shè)計中遵照了電子地圖制圖上的標(biāo)注規(guī)則,實現(xiàn)了將各種要素統(tǒng)一進行動態(tài)標(biāo)注，從而有效地解決了壓蓋和沖突問題。

算法不足之處：

(1)該算法相比回溯算法而言，沒有充分利用屏幕顯示最多的信息，應(yīng)該尋找一個平衡點，改進該算法使之能顯示更多的標(biāo)注信息； (2)沒有形成對標(biāo)注效果的評價函數(shù)，如對標(biāo)注密度的計算與衡量、對標(biāo)注分布的評價等。參考文獻[1]杜世宏,王橋,杜道生：地圖注記質(zhì)量評價模型的研究。測繪學(xué)報[J]，2004,33(4)：362-363.[2]陳孔哲,朱欣陷,張銀州,蘇光奎：地圖漢字注記的自動定位研究。武漢測繪科技大學(xué)學(xué)報[J]，1997,22(2)：137-139.[3]杜世宏,王橋,杜道生,樊紅：地名注記的自動配置研究。地理學(xué)與國土研究[J]，2002,18(4)：14-17.[4]樊紅,張祖勛,杜道生,張劍清,：基于神經(jīng)網(wǎng)絡(luò)模型求取注記配置最優(yōu)解。武漢測繪科技大學(xué)學(xué)報[J]，1998,23(1)：32-35[5]盧英,劉金義,高輝,路宏：地圖中點狀要素標(biāo)注算法設(shè)計。計算機與數(shù)字工程[J]，2006,34(5)：97-98.[6