面向嵌入式gis应用的地图标注算法设计课件

面向嵌入式GIS

地图标注算法设计与实现2007年04月中山大学智能交通实验室1.地图标注的相关概念2.标注算法研究现状3.基于栅格的地图标注算法4.试验结果主要内容1.地图标注的相关概念2.标注算法研究现状3.基于栅格的地图标注算法4.试验结果主要内容地图标注的相关概念

地图标注的评价方式标注位置的是否选择恰当是否排列美观是否清晰易读

地图标注的研究重点如何控制标注的位置和布局解决标注之间的冲突和压盖问题

地图标注间冲突与压盖冲突：标注与其它标注之间出现重叠情况压盖：标注遮挡关键地图要素的情况

电子地图使用价值地图标注的基本原则

地图标注可分为点、线、面三类考虑，都应遵循的基本原则：“所属关系”

确定标注与被标注目标之间的所属关系“避让”

避开重要地物，尤其不能压盖同种颜色的其它地物“习惯”

标注的字位、字序、排列方式要符合读图习惯1.地图标注的相关概念2.标注算法研究现状3.基于栅格的地图标注算法4.试验结果主要内容-

-

-

贪婪算法模拟退火穷尽搜索其它启发算法回溯算法

经典算法研究现状

标注算法回顾经典标注算法贪婪算法:优点是运算速度快，对每个要素只标注一次，但对于被压盖的标注并没有重新定位。回溯算法:

补偿了贪婪算法的不足，对被压盖的标注通过回溯处理来重新定位，虽然可通过限定候选位置个数与回溯深度来加快标注位置计算，但其时间上的开销仍然不利于在嵌入式GIS系统中应用。目前研究成果表明：质量最高的是模拟退火算法。其标注效率要优于上述其它算法，但模拟退火的时间消耗大。模拟退火算法模拟退火算法是解决地图标注问题的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地将其应用在组合最优化问题中。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值,基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。算法终止条件:当前解即为所得近似最优解模拟退火算法该算法将地图各要素注记的配置作为一个统一的整体来对待，从而避免了一般局部搜索法可能终止于一个局部最优解的缺点，这样可使自动注记配置的结果更趋合理化。用模拟退火算法进行注记自动配置，机理简单，通用性强，其缺点在于配置速度较慢。其它标注算法StevenZoroaster提出的整数规划法武汉大学的樊红提出的神经网络法等算法

特点：针对点状地物的标注都具有一定的实用性标注输出合理、美观相对当前嵌入式系统的运算能力而言，计算时间较长1.地图标注的相关概念2.标注算法研究现状3.基于栅格的地图标注算法4.试验结果主要内容注记冲突与压盖检测策略

采用将屏幕栅格化的方法进行整体检测地图数据量很大，若逐个检测，则一个城市就需要处理成千上万条道路，处理将很耗费时间

处理屏幕栅格化步骤：根据标注字体大小定义栅格边长进行栅格化

假定标注字体大小为8x8象素，屏幕分辨率80x40，

方格边长定为8个象素，1个方格容纳一个标注字体定义状态数组描述屏幕各方格装载的地物要素信息

BYTEGridArray[nRow*nCol]

状态数组中各元素与各个方格一一对应，

该元素值表示该方格地图要素状态与类型，其定义如： 0表示可作为候选区域，1表示已被标注区域， 10表示点状物，20表示一般道路 30表示高速道路,40表示河流区域,………..

例如“31”表示该方格为高速道路且已被标注。注记冲突与压盖检测策略状态数组初始化在进行注记的搜索前，需要针对不能压盖的地图要素类型，搜索矢量地图数据，对状态数组进行初始化，确定每个方格的类型值搜索状态数组

在进行标注位置搜索时可按状态数组的顺序进行搜索，遇到对应的非0类型值方格，则需要根据标注原则自动避让，否则将不可避免地注记冲突或压盖问题。注记位置的搜索策略先定义一个格子编码集合VecGridCode：typedefstruct{ DWordnGridCol; //方格列号 DWordnGridRow; //方格行号}GridCode; Vector<GridCode>VecGridCode； //表示候选标注位置的方格集合注记位置的搜索策略对于点状地图要素标注位置的搜索步骤： (1)根据该点位置,得到其标注的四个方向候选位置起始位置

位置优先级从高至低为A区域、B区域、C区域、D区域

(2)判断各个候选位置是否可用

如图，以“中”字为例，在其候选区域间的区域标注中，搜索到一块连续的间距合理的标注区域

(3)最后根据得到的标注区域

根据得到的标注区域:栅格编码集合，计算具体的标注坐标值注记位置的搜索策略对于线状地图要素标注位置的搜索步骤： (1)获得道路各弧段的各个关键点，计算其外接矩形内部的方格集合

如图,对于关键点m和关键点n的外接矩形ABCD，其方格编码集合:{(3,2),(3,3)} (2)

为各弧段寻找足够的连续标注空间

如图，以“中山八路”弧段为例，在其所有关键点间的外接矩形候选标注区域中，搜索到一块连续的间距合理的标注区域。

间距=整数倍栅格边长

(3)计算具体标注位置

根据得到标注方格集合，计算标注坐标值注记位置的搜索策略对于面状地图要素的处理方法

与线状要素相似，同样是根据其关键点的外接矩形得到其标注候选区域；

不同的是候选区域还需要加上面状要素内部区域和标注位置尽可能靠内部中央区域。

如图所示，“麓景湖”面状要素的标注区域落在其内部区域中。若可标注的区域没有与其它标注冲突和受到压盖，则可合理地加大标注的字体。算法实现步骤创建标注字体,将屏幕栅格化,并计算出栅格边长栅格边长=字体大小边长定义一维数组描述整个屏幕各个小方格状态将数组中每个元素清零从矢量数据中寻找不可被压盖的地图要素类型的位置,初始化相应的元素计算一条线状元素的标注位置函数:ArrangeArcAnnoPos(DISPARCRECORD&OneArcRecord)以像素为单位，计算标注的长度判断标注的大致走向

CRect&rectMBR=OneArcRecord.MBR; if(rectMBR宽度<rectMBR高度) ndirection=TOPDOWN; else ndirection=LEFTRIGHT;得到这一条线状元素覆盖的所有小方格计算该道路上可以开始标注的位置开始计算标注的具体位置计算地图中所有线状元素的标注位置得到这一条线状元素覆盖的所有小方格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); //存储覆盖格子的行号和列号}}}}计算该道路上可以开始标注的位置nStart=0; //起始点假设从第vecGridCode[0]个格子开始nSize=vecGridCode.size(); //得到线状元素覆盖的格子个数for(inti=0;i<nSize;i++) //顺序处理覆盖线状元素的每一个格子{GRIDCODE&LocalGrid=vecGridCode[i]; //得到这个格子号if(annoMatch[这个格子]!=0) //若非零，表示已经被其他标注占用{if(道路为东西走向)计算当前列与起始列的距离nLengthelse//道路为南北走向计算当前行与起始行的距离nLengthif(nLength<=标注需要的长度)nStart=i; //从当前所处的格子开始，寻找合适的长度进行标注else //找到足够的标注位置，则退出break; }}//此时，表示从第nStart格子开始标注开始计算标注的具体位置intiGridSeq=0; //定义格子序号for(inti=0;i<nAnnoNum;i++) //循环取得各个字的位置{ //得到这个汉字占用的第一个格子号,其后定长的连续的格子号均用于标注该线状道路

GridSeq=2*i*GRIDFORHANZI+2*GRIDFORHANZI+nStart; LocalGrid=vecGridCode[iGridSeq]; //相应栅格状态置1,表示该格子已经被标注占用,防止标注间的冲突 annoMatch[iGridSeq]=1; //计算这个汉字的屏幕坐标

PtPos.x=LocalGrid.nGridCol*m_nAnnoGridLen; PtPos.y=LocalGrid.nGridRow*m_nAnnoGridLen; //将得到的屏幕坐标,作为线状元素的属性进行存储 OneArcRecord.AnnoPosition.push_back(PtPos);}计算地图中所有线状元素的标注位置

具体步骤：if（当前线状元素不显示）return;得到当前视图范围内的所有线状元素设置文本的背景为透明色，并设置颜色为黑

for(对于地图中的每一条长线状元素) {if(标注的长度<=1) continue;ArrangeArcAnnoPos(DISPARCRECORD&OneArcRecord);//即依次计算每条道路的标注位置坐标，顺序存储到OneArcRecord.AnnoPosition集合中 }1.地图标注的相关概念2.标注算法研究现状3.基于栅格的地图标注算法4.试验结果主要内容3.基于栅格的地图标注算法试验

应用上述的设计思想和实现方法，设计了基于嵌入式GIS的车辆监控系统，提供基本的地图绘制、信息查询、GPS定位导航等功能。

系统已经实现的功能： (1)基本的地图操作 (2)空间数据信息查询 (3)距离测算 (4)GPS定位

该系统对标注的配置，采用上述的基于栅格的地图标注算法。试验结果试验软硬件环境：基于WinCE的PocketPC系统本算法试验效果：输出注记密度维持在一定的合理水平地图标注总体效果较好运行速度快，且易于实现总结

由以上结果和分析可以看出,该算法特点：(1)在标注分布上，采用该算法的标注效果较好，标注排列较为整齐、分布较为协调、数量适中。 (2)算法思想简便、计算简单、易于实现。尤其在嵌入式应用中具有一定的实用价值。 (3)本算法在设计中遵照了电子地图制图上的标注规则,实现了将各种要素统一进行动态标注，从而有效地解决了压盖和冲突问题。

算法不足之处：

(1)该算法相比回溯算法而言，没有充分利用屏幕显示最多的信息，应该寻找一个平衡点，改进该算法使之能显示更多的标注信息； (2)没有形成对标注效果的评价函数，如对标注密度的计算与衡量、对标注分布的评价等。参考文献[1]杜世宏,王桥,杜道生：地图注记质量评价模型的研究。测绘学报[J]，2004,33(4)：362-363.[2]陈孔哲,朱欣陷,张银州,苏光奎：地图汉字注记的自动定位研究。武汉测绘科技大学学报[J]，1997,22(2)：137-139.[3]杜世宏,王桥,杜道生,樊红：地名注记的自动配置研究。地理学与国土研究[J]，2002,18(4)：14-17.[4]樊红,张祖勋,杜道生,张剑清,：基于神经网络模型求取注记配置最优解。武汉测绘科技大学学报[J]，1998,23(1)：32-35[5]卢英,刘金义,高辉,路宏：地图中点状要素标注算法设计。计算机与数字工程[J]，2006,34(5)：97-98.[6