三维注记配置属于三维地理环境图形化表达中的语义信息表达研究范畴[1]。语义信息表达是采用文字、符号直观展现地物属性值,如:道路名称、建筑物名称等。注记(annotation),或称标注(label),是语义信息表达的直接方式,也是地图语言的重要组成部分[2]。以数据维度为标准,注记配置分为二维注记配置、三维注记配置。目前,二维注记配置研究较多,根据要素维度划分为0维、一维、二维,其中,0维地理要素的二维注记配置以优化算法研究为主,如:物理松弛法[3]、遗传算法[4]、聚类搜索算法[5],一维、二维地理要素的二维注记配置以注记候选位置计算研究为主,如:熵心定位[6]、散列式定位[7],此外,地图注记引擎[8]、地图注记规则库[9]、影像的注记配置[10]也得到了广泛研究。三维注记配置是对二维注记配置的维度拓展,二维的研究理论适用于三维,但三维注记配置更为复杂,表现为:渲染量大、显示呈现“近大远小”、多视角等。三维注记配置处于研究发展期,以研究注记生成过程、注记优化方法、GPU加速计算为重[11-16]。
不同数据体量的地理场景,其加载机制、渲染机制、内存控制、语义信息表达机制有本质差异。大规模地理场景数据多采用分块索引加载渲染机制,按需加载,避免内存超负荷,如数据调度流水线方法[17],软件平台如ArcGlobe平台;小规模地理场景数据一般采用直接加载渲染机制,避免频繁的调用数据进入内存,软件平台如ArcScene平台。不同规模地理场景的注记渲染方式和优化方式不同,大规模地理场景多采用屏幕空间的注记(screen space annotation),小规模地理场景一般采用基于对象空间的注记(object space annotation)[12]。
1 小规模地理场景中的注记小规模地理场景中点要素三维注记配置需解决3个问题:绘制内容、绘制位置及如何绘制。综述,三维注记配置研究处于发展期,其优化方法简单。将二维注记的优化配置算法推广至三维注记配置研究中,成为本文研究内容。
1.1 注记绘制内容影响三维注记内容展示的因素有:注记文字内容、注记视觉变量、场景视觉变量。注记文字内容是指显示的属性内容,分为说明注记和名称注记两种。注记视觉变量指注记元素本身的各项属性设置,总结为9种:字体、字号、字色、字型、字列、字隔、字向、外框、图标,其样式如图 1所示。场景视觉变量包括:光源、地图背景、垂直夸张度、观察视野等。观测视野的设置包括观测点坐标设置、目标点坐标设置、视距设置、视角设置、相机的方位角(azimuth angle)、倾角(inclination angle)设置等。
1.2 注记绘制位置
三维注记因绘制位置的差异,可分为:①贴于三维模型表面栅格纹理,见图 2(a);②触发后弹出框式,见图 2(b);③贴于地表的栅格纹理,见图 2(c);④朝屏幕方向的广告牌,见图 2(d);⑤朝固定面方向的广告牌,见图 2(e)。其中,以③、④为常见样式。此外,三维注记绘制位置受待选注记方位影响。二维注记待选方位常见有四方位、八方位等,三维注记待选方位可沿用二维注记待选方位,但随着三维注记所处空间的维度提升,三维注记的待选方位多样性也增加。三维注记待选方位示意如图 3所示。
1.3 注记绘制方法
从三维注记发生视觉上遮挡则的优化策略进行划分,分为遮挡则直接显示、遮挡则优化并显示及遮挡则不显示,3种情况各有优缺点且其适用的范畴各不相同。举例示意,图 4(a)为遮挡则直接显示,图 4(b)为遮挡则优化并显示,图 4(c)为遮挡则不显示。
遮挡则直接显示,缺点明显,要素增多后传递的语义信息急剧下降。遮挡则优化,采用注记优化配置算法计算,得到该视角下可行解,其与PFCLP问题中的MNCFLP[18]和MNCP[3]两种策略相一致,其优点是信息无丢失,语义信息完整,适用于小规模的地理场景。遮挡则不显示,采用深度检测剔除该视角下深度大且被压盖的注记,其与PFCLP问题的MISP策略[19]相一致,其优点是简洁,但缺点是信息丢失。表 1对3种方式的概念、优化策略、优缺点、适用范畴进行了总结。
对比项 | 遮挡则直接显示 | 遮挡则优化并显示 | 遮挡则不显示 |
概念 | 直接显示注记的方式 | 优化后,获得注记方位 | 深度检测后不显示较深注记 |
优化策略 | 无 | 优化配置算法 | 深度检测 |
优点 | 计算简单、效率快 | 信息不丢失,认知效果好 | 简洁 |
缺点 | 认知效果差 | 计算复杂 | 信息丢失 |
适用范畴 | 有比例尺控制的地理场景 | 小规模地理场景 | 大规模地理场景 |
2 注记配置规则
小规模地理场景中点要素三维注记配置采用基于对象空间的注记,注记遮挡后的优化策略为遮挡则优化,从而确保“注记信息不丢失、视线方向上注记遮挡尽量少”。
2.1 三维注记待选方位小规模地理场景中点要素的注记待选方位选用三维空间中的与视线方向垂直面上的四方位待选注记方案。假设观察者的方位角和倾角为(θ,φ),三维点要素P(x,y,z),三维注记尺寸为(w,h),如图 5所示,则四方位三位注记框中心点Pi的计算见式(1)
2.2 三维注记质量评价函数
实现“注记信息不丢失、视线方向上注记遮挡尽量少”的配置目标,需定量化为三维注记质量评价函数,评价函数的设计直接影响注记的质量[20]。注记质量评价函数需符合:注记丢失个数越少函数值越大;注记遮挡越少函数值越大的设计原则;当注记发生丢失时,则丢失注记不会发生注记遮挡,两者具备互斥性。本文提出小规模地理场景三维注记质量评价函数E,E是E(i)的总和,见式(2),E(i)表示第i个注记的质量值。E(i)由评价子函数组成,如式(3)所示。顾及三维点要素四方位待选注记方案中,各方位与要素关联性相同、优先级视为一致,故E(i)未将注记与要素关联性、注记方位优先级纳入子函数范畴
式中,Ef(i)表示注记i遮挡要素的次数;Ea(i)表示注记i遮挡其他注记的次数;Ed(i)表示注记i是否丢失,丢失则为1,否则为0;∂、η、l为权重系数。E(i)∈0,100,E(i)值越大则表明质量越好。
3 算法设计三维点要素注记优化配置算法是一种三维注记在视线方向上发生遮挡后进行优化后重新配置注记位置的算法。该算法由二三维坐标系变换、GRID算法、遗传算法(genetic algorithm,GA)、注记质量评价函数组成,相互关系是:二三维坐标系变换和GRID算法是计算基础;用于求解的遗传算法是核心;三维注记质量评价函数是遗传算法适应度计算公式,各模块组合关系如图 6所示。
3.1 整体流程
三维点要素注记优化配置算法的设计流程由6步组成,具体流程如下。
第1步:输入三维要素点集、三维待选注记框中心点集矩阵,记为Vwcs。
第2步:透视变换。透视变换是获得透视图像的方法,可以运用于要素、待选注记框的透视后坐标集合Vdcs计算,透视变换矩阵如式(4)所示。Mmv为模型视点矩阵,变换后得到相机坐标系;Mp为投影矩阵,得到投影坐标系;Mw窗口变换矩阵,得到设备坐标系
式中
注:R为Camera视点到世界坐标系原点距离;θ为方位角(azimuth),θ∈[0°,360°];φ为倾斜角(inclination),φ∈[-90°,360°];D表示Camera视点到屏幕坐标系原点的距离;w表示设备宽度;h表示设备的高度。
第3步:采用GRID算法进行基础网格构建。基础网格是判别注记间压盖、注记与要素间冲突的快速方式。GRID算法包括:网格初始化、网格更新、网格读取3个算子。其中,网格初始化算子是实现要素网格化的方法集合,点要素直接网格化,线要素可采用Bresenham算法[21]等,面要素可采用点在面内算法[22]进行网格化,完成初始化,得到要素网格(GRIDFea),样式如图 7所示。网格更新算子,涉及已知坐标点(x,y),求解网格行列号(row,col),计算见式(5)。网格读取算子,已知网格行列号(row,col),求解坐标点(x,y),计算公式见式(6)。
式中,cellsize为网格单元尺寸;ymax是指所有要素的最大外包络框的y最大值;xmin为所有二维屏幕要素的最大外包络框的x最小值。
第4步:GA算法进行最优组合解计算。GA算法是启发式算法的一种,以广泛运用于二维注记配置、TSP问题求解。其中,GA算法选择算子的适应度评价方法采用注记质量评价函数(E)。经初始化、选择算子、交叉算子及变异算子计算后,得到结果解。
第5步:逆透视变换。逆透视变换是将计算得到的二维注记结果解转换为三维注记,是透视变换的逆过程。逆透视变换公式如式(7)所示
第6步:输出注记结果。将注记结果绘制于地理场景中。
3.2 核心算法GA算法是模拟生物遗传机制而形成的解决复杂组合优化问题的算法[23]。基本遗传算法实现步骤是:①初始化形成初始种群;②基于适应度函数对个体符号串进行评价;③执行遗传操作生成一个新的符号串群体;重复第②、③步直到算法终止。遗传操作包括:选择算子、交叉算子及变异算子,遗传算法的关键在于染色体个体符号串的表示和遗传操作算子的设计。三维点要素注记配置的GA算法具体步骤如下:
步骤1:设置GA算法的基本参数和经透视变换后的待选注记框集合(ListProAnno)输入、要素网格基础(GRIDFea)输入。GA算法的基本参数设定:交叉概率(PC)、变异概率(PM)、种群规模(Popsize)、进化代数(Iteration)、染色体基因座数量(CountFea)、注记质量评价函数阈值(EValue)、基因上限值(MaxGene)、基因下限值(MinGene)。
步骤2:生成初始种群。当前代数(Pop)等于1,种群中染色体数量为Popsize,每个染色体的基因座数量CountFea。每个基因座基因值(ValueGene)确定为随机时间种子数,要求ValueGene∈{N*∩[MinGene,MaxGene]}。初始种群总体产生随机数的次数为Popsize*CountFea。
步骤3:评价种群各染色体的适应度值(E)。复制GRIDFea得到当前代的GRIDTemp,根据该染色体上各ValueGene找出对应的待选注记框集合中各要素的待选注记框(ProAnno)。在GRIDTemp基础上,对ProAnno进行网格化,网格信息记录于GRIDTemp中。各基因的适应度计算等价于E(Li),染色体整体适应度计算等价于E。
步骤4:最优染色体选择与终止条件判别。保留种群中最优染色体及其适应度值,判别终止条件((E≥EValue)Or(Pop>Iteration)),符合则停止执行,该最优染色体为注记解;否则,执行步骤5。
步骤5:新一代种群生成。Pop自增1。调用赌轮盘算子进行父代的染色体选择。针对选择出得父本染色体与父本最优染色体进行交叉算子,选择对应基因位,采用单点交叉,若随机算子的概率值小于PC,即认为符合交叉条件,执行交叉。针对选择出得父本染色体进行变异算子,选择有冲突的基因位,若随机算子的概率值小于PM,则认为符合变异条件,执行变异。
步骤6:重新执行步骤3,直至符合步骤4的终止条件。
4 算法试验 4.1 试验环境与试验数据系统硬件环境:CPU:Intel(R)Core(TM)i5-4590,内存:8GB,GPU:NVIDIA GeForce GT730;系统软件环境:操作系统:操作系统:Windows10 64Bit,编程环境:Visual Studio 2010,编程语言:C#,GIS平台:ESRI ArcObjects 10.2、SuperMap Desktop 8C。试验系统基于ArcScene Control实现各功能,ArcScene Control用于展示小规模三维不动产场景数据。主要功能包括:试验数据加载、三维坐标轴绘制、直接注记配置、注记优化算法配置、试验参数设置等。试验数据采用三维地籍产权体[24]中的三维宗地体作为试验数据,试验数据如图 8所示。
参数设置包括注记参数、网格参数、注记质量评价函数参数、遗传算法参数。注记参数: 8号、宋体。待选注记方位取四方位。网格参数:CellSize=0.1,CellValuePoint=1,CellValueLine= 10,CellValuePolygon=100,CellValueAnno= 1000。注记质量评价函数参数:∂=0.1、η=0.45、l=0.45,即认同在小规模地理场景中,注记丢失与注记遮挡其他注记的影响程度一致,次之是注记遮挡其他要素。遗传算法参数:Popsize=30,Iteration=50,PC=0.7,PM=0.1,EValue=30,MaxGene=4,MinGene=1,CountFea为三维点要素个数。
4.2 多视角、多平台对照试验为验证算法在多视角、多平台上具备普适性和优化性,试验方法采用宗地体对象图 8(a),选具备代表性的GIS平台(ESRI的ArcScene平台、超图的SuperMap Desktop平台)作为对照组,设置多视角,进行三维界址点三维注记配置,对比配置效果。对照结果如图 9所示,其中,1序列(1-a、1-b、1-c)视角参数为θ=90°,φ=10°;2序列(2-a、2-b、2-c)视角参数为θ=185°,φ=17°;3序列(3-a、3-b、3-c)视角参数为θ=163°,φ=79°;a序列(1-a、2-a、3-a)为SuperMap Desktop的效果图、b序列(1-b、2-b、3-b)为直接配置注记的ArcScene的效果图;c序列(1-c、2-c、3-c)为经本算法优化配置注记的效果图。
经统计各对照组的注记信息丢失数量(T1)、视线方向上三维注记遮挡其他三维注记数量(T2)、视线方向上三维注记遮挡要素数量(T3),调用式(2)计算得注记质量评价值(E),如表 2所示。结合表 2,以视角场景为横轴、E为纵轴,绘制各平台在多视角下的质量值变化折线图,如图 10所示。
序号 | 试验编号 | T1 | T2 | T3 | E |
1 | 1-a | 13 | 0 | 4 | 24.24 |
2 | 1-b | 0 | 15 | 19 | 18.78 |
3 | 1-c | 0 | 2 | 10 | 51.28 |
4 | 2-a | 8 | 0 | 10 | 30.30 |
5 | 2-b | 0 | 13 | 18 | 20.73 |
6 | 2-c | 0 | 2 | 11 | 50.00 |
7 | 3-a | 18 | 0 | 13 | 17.54 |
8 | 3-b | 0 | 24 | 26 | 12.99 |
9 | 3-c | 0 | 0 | 12 | 62.50 |
对照组分析得,本算法(c)在各视角下的三维注记质量值均优于SuperMap Desktop(a)、ArcScene(b)的三维注记质量值,说明本文算法具备普适性和优化性。采用((value1-value2)/value2) 100%计算质量提升比重,在视角1下,本算法(c)相对SuperMap Desktop(a)、ArcScene(b)三维注记质量分别提升111%、173%;在视角2下,本算法(c)相对SuperMap Desktop(a)、ArcScene(b)三维注记质量分别提升65%、141%;在视角3下,本算法(c)相对SuperMap Desktop(a)、ArcScene(b)三维注记质量分别提升256%、381%;综合各视角,本算法(c)相对SuperMap Desktop(a)、ArcScene(b)三维注记质量平均提升144%、232%。以视角2为例,在J671、J670处,2-a存在三维注记信息丢失,2-c无注记信息丢失;2-b存在密集的三维注记遮挡,2-c仅存在三维注记遮挡要素,三维注记信息仍清晰可辨。综上试验对比可证,本文提出的三维点要素注记优化配置算法符合“注记信息不丢失、视线方向上注记遮挡尽量少”的配置目标,具备普适性和优化性。
5 结论本文归纳了三维注记配置的内容、位置及方法,并依据三维注记配置目标确立了三维注记质量评价函数,设计的点要素三维注记优化配置算法实现了在小规模地理场景中三维注记优化配置,符合“信息不丢失,视线方向上注记遮挡尽量少”的配置目标。算法的创新在于将启发式组合优化算法引入地理场景的三维注记配置中。经试验对比,验证了算法具备多视角普适性,且算法在小规模地理场景配置三维注记的效果优于现行的GIS平台的效果。值得指出的是,本算法目前注重配置效果,但在大规模地理场景应用上仍受限于启发式组合优化算法的求解效率,下一步研究动向为:采用GPU进行GA运算,以加速算法求解,从而拓展算法至大规模地理场景,如: GRID算法并行、基于 “岛”的GA算法。此外,三维注记质量评价函数可引入遮挡严重程度评价指标,以进一步优化评价效果。
[1] | CHEN Chen, ZHANG Liqiang, MA Jingtao, et al. Adaptive Multi-resolution Labeling in Virtual Landscapes[J]. International Journal of Geographical Information Science, 2010, 24(6): 949–964. DOI:10.1080/13658810903473205 |
[2] | 乔占明, 闫浩文. 地图标注和地图注记的探讨[J]. 测绘与空间地理信息, 2011, 34(1): 205–207. QIAO Zhanming, YAN Haowen. Discussion on Map Labeling and Map Annotation[J]. Geomatics and Spatial Information Technology, 2011, 34(1): 205–207. |
[3] | RIBEIRO G M, LORENA L A N. Lagrangean Relaxation with Clusters for Point-feature Cartographic Label Placement Problems[J]. Computers & Operations Research, 2008, 35(7): 2129–2140. |
[4] | PEREIRA G S, NOGUEIRA LORENA L A, MATTOS RIBEIRO G. A Constructive Genetic Algorithm for Discrete Dispersion on Point Feature Cartographic Label Placement Problems[J]. Geographical Analysis, 2016, 48(1): 43–58. DOI:10.1111/gean.2016.48.issue-1 |
[5] | RABELLO R L, MAURI G R, RIBEIRO G M, et al. A Clustering Search Metaheuristic for the Point-Feature Cartographic Label Placement Problem[J]. European Journal of Operational Research, 2014, 234(3): 802–808. DOI:10.1016/j.ejor.2013.10.021 |
[6] | 王昭, 吴中恒, 费立凡, 等. 基于几何信息熵的面状要素注记配置[J]. 测绘学报, 2009, 38(2): 183–188. WANG Zhao, WU Zhongheng, FEI Lifan, et al. Automatic Name Placement of Area Feature:A Metric Information Approach[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(2): 183–188. DOI:10.3321/j.issn:1001-1595.2009.02.015 |
[7] | 张志军, 李霖, 于忠海, 等. 散列式面状注记自动配置技术研究[J]. 武汉大学学报(信息科学版), 2011, 36(6): 739–742. ZHANG Zhijun, LI Lin, YU Zhonghai, et al. Auto-Labeling of Hash Anea Features[J]. Geomatics and Information Science of Wuhan University, 2011, 36(6): 739–742. |
[8] | 张志军. 基于规则引擎的地图注记自动配置方法研究[D]. 武汉:武汉大学, 2011. ZHANG Zhijun. Research on Automatic Label Placement Based on Rules-Engine[D]. Wuhan:Wuhan University, 2011. |
[9] | 吴长彬, 闾国年, 刘昱君. 基于规则库和网格算法的土地利用现状图自动数字注记[J]. 测绘学报, 2008, 37(2): 250–255. WU Changbin, LU Guonian, LIU Yujun. Automated Numeric Placement for Land Utilization Map Based on Rule Database and Grid Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2): 250–255. DOI:10.3321/j.issn:1001-1595.2008.02.021 |
[10] | RYLOV M A, REIMER A W. Improving Label Placement Quality by Considering Basemap Detail with a Raster-based Approach[J]. Geoinformatica, 2015, 19(3): 463–486. DOI:10.1007/s10707-014-0214-6 |
[11] | MAASS S, DÖLLNER J. Dynamic Annotation of Interactive Environments Using Object-integrated Billboards[C]//Proceedings of the 14th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision. Plzen, Czech Republic:WSCG, 2006:327-334. |
[12] | MAASS S, DVLLNER J. Embedded Labels for Line Features in Interactive 3D Virtual Environments[C]//Proceedings of the 5th International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa. New York, NY, USA:ACM, 2007:53-59. |
[13] | VAARANIEMI M, FREIDANK M, WESTERMANN R. Enhancing the Visibility of Labels in 3D Navigation Maps[M]//POULIOT J, DANIEL S, HUBERT F, et al. Progress and New Trends in 3D Geoinformation Sciences. Berlin Heidelberg:Springer, 2013:23-40. |
[14] | VAARANIEMI M,TREIB M, WESTERMANN R. Temporally Coherent Real-time Labeling of Dynamic Scenes[C]//Proceedings of the 3rd International Conference on Computing for Geospatial Research and Applications. New York, NY, USA:ACM, 2012:17. |
[15] | PRADO R D, RAPOSO A B. Real-time Label Visualization in Massive CAD Models[C]//Proceedings of 2013 International Conference on Computer-aided Design and Computer Graphics. Guangzhou, China:IEEE, 2013:337-344. |
[16] | 杨乃. 基于空间认知的三维地图设计若干问题的研究[D]. 武汉:武汉大学, 2010. YANG Nai. Study on Several Issues of 3D Map Design Based on Spatial Cognition[D]. Wuhan:Wuhan University, 2010. |
[17] | 胡斌, 江南, 邹志强, 等. 大规模室外动态场景调度机制研究[J]. 地球信息科学, 2007, 9(5): 8–13. HU Bin, JIANG Nan, ZOU Zhiqiang, et al. Research on Dispatch of Dynamic Scene in Large Scope Outdoor Environment[J]. Geo-information Science, 2007, 9(5): 8–13. |
[18] | RIBEIRO G M, LORENA L A N. Heuristics for Cartographic Label Placement Problems[J]. Computers & Geosciences, 2006, 32(6): 739–748. |
[19] | STRIJK T, VERWEIJ B, AARDAL K. Algorithms for Maximum Independent Set Applied to Map Labelling[J]. Utrecht:Department of Computer Science, Utrecht University, 2000. |
[20] | 樊红, 张祖勋, 杜道生. 地图注记质量评价模型的研究[J]. 测绘学报, 2004, 33(4): 362–366. FAN Hong, ZHANG Zuxun, DU Daosheng. The Study of the Evaluation Model for Map Labeling[J]. Acta Geodaetica et Cartographica Sinica, 2004, 33(4): 362–366. DOI:10.3321/j.issn:1001-1595.2004.04.016 |
[21] | PITTEWAY M L V, WATKINSON D J. Bresenham's Algorithm with Grey Scale[J]. Communications of the ACM, 1980, 23(11): 625–626. DOI:10.1145/359024.359027 |
[22] | ŽALIKB, KOLINGEROVAI. A Cell-based Point-in-polygon Algorithm Suitable for Large Sets of Points[J]. Computers & Geosciences, 2001, 27(10): 1135–1145. |
[23] | CHRISTENSEN J, MARKS J, SHIEBER S. An Empirical Study of Algorithms for Point-feature Label Placement[J]. ACM Transactions on Graphics, 1995, 14(3): 203–232. DOI:10.1145/212332.212334 |
[24] | 史云飞, 郭仁忠, 李霖, 等. 四维地籍的建立与分析[J]. 武汉大学学报(信息科学版), 2014, 39(3): 322–326. SHI Yunfei, GUO Renzhong, LI Lin, et al. Establishment and Analysis of 4D Cadastre[J]. Geomatics and Information Science of Wuhan University, 2014, 39(3): 322–326. |