论文推荐|周鑫鑫：小规模地理场景中点要素三维注记优化配置算法

《测绘学报》

构建与学术的桥梁        拉近与权威的距离

阅读以下链接
赢中图集团旅游精品！

小规模地理场景中点要素三维注记优化配置算法

周鑫鑫, 吴长彬, 孙在宏, 丁远, 贺涛     

南京师范大学虚拟地理环境教育部重点实验室, 江苏 南京 210046

收稿日期：2016-05-03； 修回日期：2016-10-11

基金项目：国家自然科学基金（41471318）

第一作者简介： 周鑫鑫(1991-),男,硕士,研究方向为三维地籍及地图制图。

E-mail:

通信作者： 吴长彬

摘要：地理场景中点要素三维注记配置规则多为“遮挡则不显示”和“遮挡直接显示”，该类规则的缺陷是注记信息丢失或存在大量遮挡，普适性不强，尤其不适用于小规模地理场景点要素三维注记配置。本文首先归纳了三维注记绘制的内容、位置及方法，并针对小规模地理场景点要素三维注记配置问题，以“信息不丢失、注记尽可能少的遮挡”为配置目标，配置规则为“遮挡后优化并显示”。算法以透视变换矩阵、逆透视变换矩阵及GRID算法为基础，以遗传算法为核心，以三维注记质量评价函数为遗传算法适应度评价函数，实现点要素三维注记的可行最优解求解。经多视角、多平台对照试验可知，本算法适用于多视角三维注记优化配置，具备普适性；与主流GIS平台（SuperMap Desktop、ArcScene）的三维注记配置效果作对比，本算法三维注记质量值分别相对提升144%、232%，符合配置目标。

关键词： 地理场景     三维注记     三维注记配置     遗传算法     注记质量评价函数     GRID算法    

A 3D Annotation Optimal Placement Algorithm for the Point Features in the Small Scale Geographic Scene

ZHOU Xinxin, WU Changbin, SUN Zaihong, DING Yuan, HE Tao     

Abstract: The 3D annotations placement rules of point features in geographic scene are "obscured then not showing" and "obscured then directly showing" normally. The defects of those rules are annotation information lost or large numbers of occlusion, so their universalities are not strong and they are not suitable for the annotation placement of small-scaled geographic scene. This paper summarizes the contents, position and placement methods of 3D annotation and takes the aim at "not loss of annotation information and less annotation obscured as far as possible" of the research problem of the annotation placement of small-scaled geographic scene. The configuration rule of 3D annotation Identifies as "obscured then optimized to display". The designed algorithm based on the perspective transformation matrix, the inverse perspective transformation matrix and the grid algorithm takes the genetic algorithm (GA) whose fitness evaluation function uses the 3D Annotation quality evaluation function as the core to realize the feasible optimal solution of 3D annotations of point features in geographic scene. By the multi-views, multi-platforms contrast experiment, this algorithm is applicable for multi-views 3D annotation placement widely. The 3D annotation effect is better than mainstream GIS platforms (such as SuperMap desktop, ArcScene), which assumes that the algorithm's 3D annotation quality value is relatively increased 144%, 232%. The algorithm fits in with the target configuration.

Key words: geographic scene     3D annotation     3D annotation placement     genetic algorithm     3D annotation quality evaluation function     GRID algorithm    

三维注记配置属于三维地理环境图形化表达中的语义信息表达研究范畴^[]。语义信息表达是采用文字、符号直观展现地物属性值，如：道路名称、建筑物名称等。注记(annotation)，或称标注(label)，是语义信息表达的直接方式，也是地图语言的重要组成部分^[]。以数据维度为标准，注记配置分为二维注记配置、三维注记配置。目前，二维注记配置研究较多，根据要素维度划分为0维、一维、二维，其中，0维地理要素的二维注记配置以优化算法研究为主，如：物理松弛法^[]、遗传算法^[]、聚类搜索算法^[]，一维、二维地理要素的二维注记配置以注记候选位置计算研究为主，如：熵心定位^[]、散列式定位^[]，此外，地图注记引擎^[]、地图注记规则库^[]、影像的注记配置^[]也得到了广泛研究。三维注记配置是对二维注记配置的维度拓展，二维的研究理论适用于三维，但三维注记配置更为复杂，表现为：渲染量大、显示呈现“近大远小”、多视角等。三维注记配置处于研究发展期，以研究注记生成过程、注记优化方法、GPU加速计算为重^[-]。

不同数据体量的地理场景，其加载机制、渲染机制、内存控制、语义信息表达机制有本质差异。大规模地理场景数据多采用分块索引加载渲染机制，按需加载，避免内存超负荷，如数据调度流水线方法^[]，软件平台如ArcGlobe平台；小规模地理场景数据一般采用直接加载渲染机制，避免频繁的调用数据进入内存，软件平台如ArcScene平台。不同规模地理场景的注记渲染方式和优化方式不同，大规模地理场景多采用屏幕空间的注记(screen space annotation)，小规模地理场景一般采用基于对象空间的注记(object space annotation)^[]。

1 小规模地理场景中的注记

小规模地理场景中点要素三维注记配置需解决3个问题：绘制内容、绘制位置及如何绘制。综述，三维注记配置研究处于发展期，其优化方法简单。将二维注记的优化配置算法推广至三维注记配置研究中，成为本文研究内容。

1.1 注记绘制内容

影响三维注记内容展示的因素有：注记文字内容、注记视觉变量、场景视觉变量。注记文字内容是指显示的属性内容，分为说明注记和名称注记两种。注记视觉变量指注记元素本身的各项属性设置，总结为9种：字体、字号、字色、字型、字列、字隔、字向、外框、图标，其样式如所示。场景视觉变量包括：光源、地图背景、垂直夸张度、观察视野等。观测视野的设置包括观测点坐标设置、目标点坐标设置、视距设置、视角设置、相机的方位角(azimuth angle)、倾角(inclination angle)设置等。

图 1 三维注记视觉变量样式图Fig. 1 Visual variables pattern of 3D annotation

1.2 注记绘制位置

三维注记因绘制位置的差异，可分为：①贴于三维模型表面栅格纹理，见；②触发后弹出框式，见；③贴于地表的栅格纹理，见；④朝屏幕方向的广告牌，见；⑤朝固定面方向的广告牌，见。其中，以③、④为常见样式。此外，三维注记绘制位置受待选注记方位影响。二维注记待选方位常见有四方位、八方位等，三维注记待选方位可沿用二维注记待选方位，但随着三维注记所处空间的维度提升，三维注记的待选方位多样性也增加。三维注记待选方位示意如所示。

图 2 三维注记分类示意图Fig. 2 Classification schematic diagram of 3D annotation

图 3 三维注记待选方位示意图Fig. 3 Schematic diagram of propositions of 3D annotation

1.3 注记绘制方法

从三维注记发生视觉上遮挡则的优化策略进行划分，分为遮挡则直接显示、遮挡则优化并显示及遮挡则不显示，3种情况各有优缺点且其适用的范畴各不相同。举例示意，为遮挡则直接显示，为遮挡则优化并显示，为遮挡则不显示。

图 4 注记遮挡后优化策略示意图Fig. 4 Schematic diagram of the optimal strategies for post annotation occlusion

遮挡则直接显示，缺点明显，要素增多后传递的语义信息急剧下降。遮挡则优化，采用注记优化配置算法计算，得到该视角下可行解，其与PFCLP问题中的MNCFLP^[]和MNCP^[]两种策略相一致，其优点是信息无丢失，语义信息完整，适用于小规模的地理场景。遮挡则不显示，采用深度检测剔除该视角下深度大且被压盖的注记，其与PFCLP问题的MISP策略^[]相一致，其优点是简洁，但缺点是信息丢失。对3种方式的概念、优化策略、优缺点、适用范畴进行了总结。

表 1 注记遮挡后优化策略对比表Tab. 1 Comparison of the optimal strategies for post annotation occlusion

对比项	遮挡则直接显示	遮挡则优化并显示	遮挡则不显示
概念	直接显示注记的方式	优化后，获得注记方位	深度检测后不显示较深注记
优化策略	无	优化配置算法	深度检测
优点	计算简单、效率快	信息不丢失，认知效果好	简洁
缺点	认知效果差	计算复杂	信息丢失
适用范畴	有比例尺控制的地理场景	小规模地理场景	大规模地理场景

2 注记配置规则

小规模地理场景中点要素三维注记配置采用基于对象空间的注记，注记遮挡后的优化策略为遮挡则优化，从而确保“注记信息不丢失、视线方向上注记遮挡尽量少”。

2.1 三维注记待选方位

小规模地理场景中点要素的注记待选方位选用三维空间中的与视线方向垂直面上的四方位待选注记方案。假设观察者的方位角和倾角为(θ,φ)，三维点要素P(x,y,z)，三维注记尺寸为(w,h)，如所示，则四方位三位注记框中心点P_i的计算见式(1)

 (1)

图 5 三维点要素四方位待选注记方案示意图Fig. 5 The 4 propositions annotation scheme of 3D point feature

2.2 三维注记质量评价函数

实现“注记信息不丢失、视线方向上注记遮挡尽量少”的配置目标，需定量化为三维注记质量评价函数，评价函数的设计直接影响注记的质量^[]。注记质量评价函数需符合：注记丢失个数越少函数值越大；注记遮挡越少函数值越大的设计原则；当注记发生丢失时，则丢失注记不会发生注记遮挡，两者具备互斥性。本文提出小规模地理场景三维注记质量评价函数E,E是E(i)的总和，见式(2)，E(i)表示第i个注记的质量值。E(i)由评价子函数组成，如式(3)所示。顾及三维点要素四方位待选注记方案中，各方位与要素关联性相同、优先级视为一致，故E(i)未将注记与要素关联性、注记方位优先级纳入子函数范畴

 (2)

 (3)

式中，E_f(i)表示注记i遮挡要素的次数；E_a(i)表示注记i遮挡其他注记的次数；E_d(i)表示注记i是否丢失，丢失则为1，否则为0；∂、η、l为权重系数。E(i)∈0,100，E(i)值越大则表明质量越好。

3 算法设计

三维点要素注记优化配置算法是一种三维注记在视线方向上发生遮挡后进行优化后重新配置注记位置的算法。该算法由二三维坐标系变换、GRID算法、遗传算法(genetic algorithm，GA)、注记质量评价函数组成，相互关系是：二三维坐标系变换和GRID算法是计算基础；用于求解的遗传算法是核心；三维注记质量评价函数是遗传算法适应度计算公式，各模块组合关系如所示。

图 6 三维注记优化配置算法结构图Fig. 6 The structure of 3D annotation optimal placement algorithm

3.1 整体流程

三维点要素注记优化配置算法的设计流程由6步组成，具体流程如下。

第1步：输入三维要素点集、三维待选注记框中心点集矩阵，记为V_wcs。

第2步：透视变换。透视变换是获得透视图像的方法，可以运用于要素、待选注记框的透视后坐标集合V_dcs计算，透视变换矩阵如式(4)所示。M_mv为模型视点矩阵，变换后得到相机坐标系；M_p为投影矩阵，得到投影坐标系；M_w窗口变换矩阵，得到设备坐标系

 (4)

式中

注:R为Camera视点到世界坐标系原点距离；θ为方位角(azimuth)，θ∈[0°，360°]；φ为倾斜角(inclination)，φ∈[-90°，360°]；D表示Camera视点到屏幕坐标系原点的距离；w表示设备宽度；h表示设备的高度。

第3步：采用GRID算法进行基础网格构建。基础网格是判别注记间压盖、注记与要素间冲突的快速方式。GRID算法包括：网格初始化、网格更新、网格读取3个算子。其中，网格初始化算子是实现要素网格化的方法集合，点要素直接网格化，线要素可采用Bresenham算法^[]等，面要素可采用点在面内算法^[]进行网格化，完成初始化，得到要素网格(GRID_Fea)，样式如所示。网格更新算子，涉及已知坐标点(x,y)，求解网格行列号(row,col)，计算见式(5)。网格读取算子，已知网格行列号(row,col)，求解坐标点(x,y)，计算公式见式(6)。

图 7 要素网格化效果图Fig. 7 Effect scheme of feature meshed

 (5)

 (6)

式中，cellsize为网格单元尺寸；y_max是指所有要素的最大外包络框的y最大值；x_min为所有二维屏幕要素的最大外包络框的x最小值。

第4步：GA算法进行最优组合解计算。GA算法是启发式算法的一种，以广泛运用于二维注记配置、TSP问题求解。其中，GA算法选择算子的适应度评价方法采用注记质量评价函数(E)。经初始化、选择算子、交叉算子及变异算子计算后，得到结果解。

第5步：逆透视变换。逆透视变换是将计算得到的二维注记结果解转换为三维注记，是透视变换的逆过程。逆透视变换公式如式(7)所示

 (7)

第6步：输出注记结果。将注记结果绘制于地理场景中。

3.2 核心算法

GA算法是模拟生物遗传机制而形成的解决复杂组合优化问题的算法^[]。基本遗传算法实现步骤是：①初始化形成初始种群；②基于适应度函数对个体符号串进行评价；③执行遗传操作生成一个新的符号串群体；重复第②、③步直到算法终止。遗传操作包括：选择算子、交叉算子及变异算子，遗传算法的关键在于染色体个体符号串的表示和遗传操作算子的设计。三维点要素注记配置的GA算法具体步骤如下：

步骤1：设置GA算法的基本参数和经透视变换后的待选注记框集合(List_ProAnno)输入、要素网格基础(GRID_Fea)输入。GA算法的基本参数设定：交叉概率(P_C)、变异概率(P_M)、种群规模(Popsize)、进化代数(Iteration)、染色体基因座数量(Count_Fea)、注记质量评价函数阈值(EValue)、基因上限值(Max_Gene)、基因下限值(Min_Gene)。

步骤2：生成初始种群。当前代数(Pop)等于1，种群中染色体数量为Popsize，每个染色体的基因座数量Count_Fea。每个基因座基因值(Value_Gene)确定为随机时间种子数，要求Value_Gene∈{N^*∩[Min_Gene,Max_Gene]}。初始种群总体产生随机数的次数为Popsize*Count_Fea。

步骤3：评价种群各染色体的适应度值(E)。复制GRID_Fea得到当前代的GRID_Temp，根据该染色体上各Value_Gene找出对应的待选注记框集合中各要素的待选注记框(ProAnno)。在GRID_Temp基础上，对ProAnno进行网格化，网格信息记录于GRID_Temp中。各基因的适应度计算等价于E(L_i)，染色体整体适应度计算等价于E。

步骤4：最优染色体选择与终止条件判别。保留种群中最优染色体及其适应度值，判别终止条件((E≥EValue)Or(Pop>Iteration))，符合则停止执行，该最优染色体为注记解；否则，执行步骤5。

步骤5：新一代种群生成。Pop自增1。调用赌轮盘算子进行父代的染色体选择。针对选择出得父本染色体与父本最优染色体进行交叉算子，选择对应基因位，采用单点交叉，若随机算子的概率值小于P_C，即认为符合交叉条件，执行交叉。针对选择出得父本染色体进行变异算子，选择有冲突的基因位，若随机算子的概率值小于P_M，则认为符合变异条件，执行变异。

步骤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用于展示小规模三维不动产场景数据。主要功能包括：试验数据加载、三维坐标轴绘制、直接注记配置、注记优化算法配置、试验参数设置等。试验数据采用三维地籍产权体^[]中的三维宗地体作为试验数据，试验数据如所示。

图 8 三维宗地体示意图Fig. 8 Schematic diagram of 3D parcel

参数设置包括注记参数、网格参数、注记质量评价函数参数、遗传算法参数。注记参数： 8号、宋体。待选注记方位取四方位。网格参数：CellSize=0.1，CellValue_Point=1，CellValue_Line= 10，CellValue_Polygon=100，CellValue_Anno= 1000。注记质量评价函数参数：∂=0.1、η=0.45、l=0.45，即认同在小规模地理场景中，注记丢失与注记遮挡其他注记的影响程度一致，次之是注记遮挡其他要素。遗传算法参数：Popsize=30，Iteration=50，P_C=0.7，P_M=0.1，EValue=30，Max_Gene=4，Min_Gene=1，Count_Fea为三维点要素个数。

4.2 多视角、多平台对照试验

为验证算法在多视角、多平台上具备普适性和优化性，试验方法采用宗地体对象，选具备代表性的GIS平台(ESRI的ArcScene平台、超图的SuperMap Desktop平台)作为对照组，设置多视角，进行三维界址点三维注记配置，对比配置效果。对照结果如所示，其中，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)为经本算法优化配置注记的效果图。

图 9 多视角、多平台三维注记配置对照效果图Fig. 9 Multi-views,multi-platforms 3D annotation placement contrast effect chart

经统计各对照组的注记信息丢失数量(T₁)、视线方向上三维注记遮挡其他三维注记数量(T₂)、视线方向上三维注记遮挡要素数量(T₃)，调用式(2)计算得注记质量评价值(E)，如所示。结合，以视角场景为横轴、E为纵轴，绘制各平台在多视角下的质量值变化折线图，如所示。

表 2 多视角、多平台对照组质量统计表Tab. 2 Multi-views,multi-platforms contrast group quality statistics table

序号	试验编号	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

图 10 各平台在多视角下的质量值变化折线图Fig. 10 The variation of the quality value of each platform in the multi-views

对照组分析得，本算法(c)在各视角下的三维注记质量值均优于SuperMap Desktop(a)、ArcScene(b)的三维注记质量值，说明本文算法具备普适性和优化性。采用((value₁-value₂)/value₂) 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算法。此外，三维注记质量评价函数可引入遮挡严重程度评价指标，以进一步优化评价效果。

【引文格式】周鑫鑫，吴长彬，孙在宏，等。 小规模地理场景中点要素三维注记优化配置算法[J]. 测绘学报，2016，45(12)：1476-1484. DOI: 10.11947/j.AGCS.2016.20160210

---

更多精彩内容:

权威 | 专业 | 学术 | 前沿

微信投稿邮箱 | [e-mail]

微信公众号中搜索「测绘学报」，关注我们，扫描上图二维码，关注学术前沿动态。

欢迎加入《测绘学报》作者QQ群： 297834524

进群请备注：姓名+单位+稿件编号