拟合复杂形状主骨架的颜色渐变填充

王家润，任 菲，荣 明，罗童心

(1.华北计算技术研究所 基础三部，北京 100083； 2. 国防大学 信息作战与指挥训练教研部，北京 100091)

0 引言

人类的视觉大部分来自于形状及颜色等视觉感知因素[1]。在军事作战符号体系中，不同国家对作战符号颜色的使用等都有明确的规定[2-3]，作战符号颜色的渐变填充具有重要的视觉增强作用：增强与背景的对比度，更加突出显示作战符号；增强进攻类作战符号等的作战方向意图的视觉表现等。

在二维图形QT(一种跨平台C++图形用户界面软件)或图形设备接口(Graphics Device Interface, GDI+)中，一般提供常用的中心径向渐变、线性渐变等颜色渐变填充效果，但在三维图形中没有该类算法(一般采用扫描线种子填充算法等)，而且针对比较复杂的形状，这些填充算法无法较好地实现沿形状的主要延伸方向的颜色渐变填充效果。骨架(或中轴)能较好地表达形状(或区域)的整体延伸趋势，描述形状的主要几何特征，反映形状的整体拓扑结构[4]；因此，针对复杂形状的研究，通过其骨架可得到较大的简化。文献[5]对骨架提取进行了比较全面的论述；文献[6]对在地理信息系统(Geographic Information System, GIS)中基于约束Delaunay三角剖分(Constrained Delaunay Triangulation, CDT)提取骨架进行了比较研究；文献[7]对图像处理中的骨架提取算法进行了分类并比较了优缺点。骨架提取算法中存在的共性问题是骨架对轮廓细节过于敏感，从而产生很多的细小分枝[8-10]，这些细小分枝的存在给实际应用带来较大的困难，因此，冗余分枝的裁剪成为骨架提取研究中的难点。文献[11]采取符合视觉特性的弯曲度比率(Bending Potential Ratio, BPR)抑制分枝，大部分的骨架提取算法采用的策略与之类似：在提取的过程中对骨架分枝按照一定的规则进行裁剪。本文的主要工作有：

1)基于骨架路径评价向量的骨架冗余分枝裁剪。

基于视觉显著性评价向量，优选出少量的骨架路径，较好地抑制了骨架的冗余分枝。这种基于骨架路径的整体选优策略，与常用的基于骨架分枝进行局部裁剪的方法不同。

2)基于形状主骨架的颜色渐变填充。

对主骨架进行颜色渐变计算，并将颜色计算拓展到整个形状区域，实现了沿形状延伸变化的渐变填充。而常用的中心径向、线性渐变等填充样式，一般较难实现该种效果。

1 形状主骨架优化及颜色渐变填充算法

1.1 算法整体流程

约束条件：限定形状(或区域)为无洞的简单多边形[4]；形状的边界点依次相连构成封闭多边形。

1) 输入形状的边界点集合；颜色渐变开始与结束颜色。

2)过程如下：

①分解复杂区域为较简单区域；

②对各区域进行约束Delaunay三角剖分；

③对三角形进行分类，采用三角形中线法提取骨架构建骨架二叉树；

④采用路径栈及搜索栈，提取骨架路径集合；

⑤依据视觉显著性评价向量，对骨架路径进行评价；

⑥依据评价结果，优选出主骨架；

⑦对主骨架进行几何调整优化；

⑧对主骨架进行颜色渐变插值计算；

⑨依据主骨架，将区域边界点分类，采用分组计算及点到线段的投影插值进行渐变颜色拓展映射计算；

⑩将各区域进行整体合成。

3)输出与形状的边界点集合对应的颜色集合。

1.2 算法详细解析

1.2.1 CDT三角形中线法骨架提取

1)约束Delaunay三角剖分。

针对复杂形状，可采用区域分解策略分解为比较简单的形状[4]。在三维中的简单多边形，如果存在凹点则不能进行正确的渲染，需要进行凸分解。三角形是最简单的凸多边形，而且在三维图形中渲染时，三角形是最基本的处理单元，显卡也对三角形处理有一定的优化。约束Delaunay三角剖分较好地解决了凹多边形的凸分解问题，在计算机图形中有广泛的应用，相关理论及算法也比较成熟[4,12]，而且Delaunay三角形的最小角最大特性使剖分产生的三角形避免了狭长三角形，趋向等边三角形，较大程度上保证了剖分的趋向均匀性，可使提取出的骨架抖动性较小，更好地逼近理想的骨架。

2)CDT三角形中线法骨架提取。

CDT产生的三角形分为三种类型：Ⅰ类型，只有一条边与其他三角形相邻(虚线表示该边与其他三角形相邻)，如图1(a)；Ⅱ类型，只有两条边与其他三角形相邻，如图1(b)；Ⅲ类型，每条边都与其他三角形相邻，如图1(c)。基于上述分类，采用三角形中线(或重心)法提取三角形的骨架，参见图1中三类三角形内部各骨架线段，其中Ⅲ类型内部含三段骨架线段。

从图2中内部较粗的骨架线可看出，骨架的端点是Ⅰ类三角形的边界顶点；骨架的连接点是Ⅱ类三角形非边界的内部边中点；骨架的分枝点是Ⅲ类三角形的重心。由文献[12]可知，该方法提取的骨架不是严格意义上的骨架(或中轴)，只是近似骨架，但与三角形外心法骨架提取方法相比，该方法可保证骨架点在三角形内部。使用角平分线方法[4]提取的骨架，一般在每一个凸点产生一个细小骨架分枝，图2中至少会有8个细小骨架分枝，而CDT三角形中线法提取的骨架分枝则仅有3个，这说明CDT对骨架冗余分枝具有一定的裁剪能力。总体来看，CDT三角形中线法骨架提取方法具有计算简单、冗余骨架分枝较少、逼近理论骨架等优点。

图2 CDT三角形中线法提取骨架的示意图 Fig. 2 Skeleton extraction by CDT triangular midline

1.2.2 骨架二叉树构建及遍历

从CDT三角形中线法可看出，骨架在Ⅰ、Ⅱ类三角形内部以一线段(该线段称为骨架线段，线段的端点称为骨架点)表示，在Ⅲ类三角形内部由3个线段组成。下面采用骨架节点对骨架线段进行逻辑表达，骨架节点与骨架点、骨架线段、所在的三角形及出入边等有关，整个骨架在逻辑上可组织为二叉树。

1)骨架节点数据结构。

SkeletonNode

{

/*骨架节点所在的约束三角形索引，用于建立骨架节点与约束三角形的关联*/

unsigned int triIndex;

/*骨架节点的2个端点在骨架点集中的索引，用于建立骨架节点与骨架点集的联系*/

unsigned int skIndex1;

unsigned int skIndex2;

/*骨架线段方向标志：当所在的三角形为Ⅰ类型，从顶点到对边置为1，否则为-1；当所在的三角形为Ⅲ类型，从中心点到对边置为-1，否则为1*/

int flag;

/*当所在的三角形为Ⅱ类型，用ed1记录入边信息，ed2记录出边信息；当所在的三角形为Ⅰ、Ⅲ类型时，只使用ed1，用于建立骨架节点与所在的三角形边的联系*/

Edge ed1;

Edge ed2;

//父子节点指针

SkeletonNode* pParent;

SkeletonNode* pLeft;

SkeletonNode* pRight;

//是否访问标志

bool visited;

}

2)骨架二叉树的构建。

a) //设置队列qe，用于广度优先遍历

std:: queue< SkeletonNode *> qe.

b) /*从CDT三角形集合中查找一个Ⅰ类三角形，取骨架线段，建立骨架节点pRoot，作为骨架二叉树根节点，并将该骨架根节点入队列qe*/

pRoot =createRootNode(CDT三角形集合);

qe.push(pRoot).

c) while(qe非空)

{

//获取队列前端节点指针

SkeletonNode* pCurNode = qe.front();

//队列前端节点出队列

qe.pop();

/*从节点pCurNode出发，依骨架走向，检查相邻的三角形：Ⅰ、Ⅱ类型生成1个骨架节点；Ⅲ类型生成3个骨节点，依据骨架生成走向将入段设为父节点，其余2段设为子节点。建立与节点pCurNode的父子关系，并将生成的节点加入到队列qe中*/

pushSkeletonNode(pCurNode, qe).

}

3)骨架二叉树的遍历。

a) //设置栈sk，用于深度优先遍历

std::stack sk.

b)//将骨架二叉树根节点入栈

sk.push(pRoot);

c)while(sk非空)

{

//获取栈顶节点指针

SkeletonNode* pCurNode = sk.top();

//栈顶节点出栈

sk.pop();

//右子节点入栈

sk.push(pCurNode->pRight);

//左子节点入栈

sk.push(pCurNode->pLeft);

//访问节点pCurNode中的信息

//pCurNode->visited…

}

1.2.3 骨架路径双栈跟踪提取

骨架路径[10]可采用骨架节点队列、骨架点列等表示。从骨架二叉树中根节点的选择可看出，根节点只有1个孩子节点，从几何的角度来看骨架的各分枝端点，骨架根节点与叶子节点是相同的，因此提取骨架路径时把根节点与叶子节点等同处理。

1)骨架路径提取。

两节点之间的骨架路径双栈跟踪提取过程如下。

a) std::vector< SkeletonNode*> path，保存输出的骨架径上的节点；std::stack ps(用于跟踪骨架路径，简称路径栈)；std::stack ss(用于放置搜索节点，简称搜索栈)。

b) 骨架路径的双栈跟踪提取基本流程，如图3所示。

c) 补充说明。

对节点pNext进行双栈出入操作：

对pNext设置已访问标志；将pNext入路径栈ps；将pNext未访问过的所有相邻节点加入到搜索栈ss。

双栈相邻检查：

检查路径栈ps栈顶节点与搜索栈ss栈顶节点是否相邻，如果非相邻，将ps栈顶节点出栈，直至ps栈顶节点与ss栈顶节点相邻为止。

双栈过滤处理：

如果ps非空，检查ps栈顶节点pTmp；ps出栈；ps非空，检查ps栈顶pPre，检查ss的栈顶pSS，如果pPre不是pTmp的子节点且pSS不是pTmp的子节点，将pTmp重新入栈ps。该处理主要是消除骨架分枝点的干扰，因为在Ⅲ类三角形中，有三段骨架线段，因此需要沿骨架路径的走向，过滤掉不符合走向的骨架线段。

图3 骨架路径的双栈跟踪提取流程 Fig. 3 Flow chat of extracting skeleton path by double stacks

2)骨架路径表达方式转换。

在1)中获取的是采用骨架节点表示的骨架路径，在骨架绘制等应用中也采用骨架点列的表示方式。从骨架路径中的开始节点开始，按骨架节点中的骨架线段的走向及骨架端点信息，跟踪出每一骨架线段的骨架端点索引，因为每一相邻骨架点重复两次，故最后需要把中间的重复点索引删除，即得到骨架路径的骨架点列表示。

1.2.4 骨架路径评价向量

已有的轮廓曲线演化骨架提取算法[13]中对边界的轮廓点给出评价，度量该点对形状的贡献度，依据贡献度简化轮廓。借鉴上述思想，针对骨架路径也引入评价标准，主要选用骨架路径面积(A)、骨架路径长度[10](L)、骨架路径跨度(S) 3个指标，组成骨架路径评价向量M=(A,L,S)。

骨架路径面积：骨架路径中各节点所在的三角形的面积之和。特别注意，如果是该骨架节点所在的三角形是Ⅲ类型，则计算该骨架节点所在的三角形重心与关联的边构成的小三角形的面积。

骨架路径跨度：骨架路径首尾两个端点间的欧氏距离。

设计思想如下。

已有的视觉显著性认知研究[14]认为：区域尺寸、突出等，是区域形状显著性的重要特征。骨架面积测量了该骨架路径在视觉上占据的视觉范围；骨架长度刻画了形状的总体延伸变化；骨架跨度度量了形状的某延伸方向的伸展程度，该思想来源于凸壳直径概念。总体来看，这3个几何测量指标一定程度上可对骨架路径进行较好的整体性评价。

计算骨架的所有骨架路径，计算出最大长度、最大面积、最大跨度，对每条骨架路径的3个测量指标进行归一化处理，可使得骨架路径评价向量具有平移、缩放、旋转等不变性。

1.2.5 主骨架的优选及几何优化

本文主骨架是指从骨架路径集合中筛选出的较优的骨架路径，与传统的已裁剪掉细小分枝的主骨架不同。

1)视觉显著度及主骨架优选。

从骨架路径的构建可知，骨架路径的首尾两个端点也是形状的边界点，因此可通过对骨架路径评价向量评价形状的边界点，引入视觉显著度来测量形状上各边界点的视觉显著性。形状上各边界点的骨架视觉显著度初始设为0，将最长骨架路径两个端点对应的边界点的视觉显著度增加1；将最大跨度的骨架路径两个端点对应的边界点的视觉显著度增加1；将最大面积的骨架路径两个端点对应的边界点的视觉显著度增加1，形状的各边界点视觉显著度≥0。

通过引入边界点的视觉显著度，能较好地筛选出较优的骨架路径，辅助用户更好地选择出理想的骨架路径。一般来说，主骨架基本可从视觉显著度比较高的形状边界点筛选出，而这种较优的视觉显著点相对是比较少的。

2)主骨架的几何优化方法。

从骨架路径筛选出的主骨架，从几何的角度来看，主骨架应该是形状的“对称轴”，一般针对主骨架需要进一步进行几何调整优化，才能实现视觉上更好的对称。具体有3种几何优化方式。

a)端点删除：一般主骨架端点附近骨架细小分枝变化较大，通过端点删除可消除这类细小分枝，提取出的主骨架能更好地能反映形状的主要几何变化趋势。在选择删除的端点时，可参考格式塔理论中的对称性原则[1]成对地进行选择。

b)端点中移：将骨架端点进行调整，如图4中的A调整到邻边的中点A1、B调整到B1，从几何的角度来看，更符合主骨架的“对称轴”几何特点。

c)中间弯曲消除：在主骨架的分枝点附近通常会有一个抖动，如图4中的D点，将D点消除，即将骨架线段ED、DF两段采用新的线段EF替换，在几何上会更光顺。

图4 主骨架的几何优化处理示意图 Fig. 4 Main skeleton geometric optimization processing

通过对主骨架的几何优化，消除了骨架的细小分枝干扰等，主骨架更加简洁，也更加符合人类的视觉感知，可更好地服务于主骨架的颜色渐变插值计算。

1.2.6 主骨架的颜色渐变插值计算

设置颜色BeginColor、EndColor，对应主骨架的首末端点，颜色采用四维向量(R，G，B，A)描述，分量取值范围[0,1]，A是透明度。

1) 计算出主骨架的全长skL；

2) 计算主骨架上各骨架点的颜色：

沿主骨架开始点到当前骨架点的累加长度skSum；主骨架上各点的颜色：

Color=BeginColor+(EndColor-BeginColor)*

skSum/skL

即对主骨架上各点的颜色进行线性插值。

1.2.7 主骨架到形状边界的颜色映射

借鉴文献[15]中的双缓冲区、文献[16]中的边界向量及形态学细化算法[9]处理的思想，设计形状内部的主骨架到形状边界的整体区域的颜色填充。基本思想：将形状的边界点分为两类：与主骨架直接关联和非直接关联。对直接关联采用按关联分组计算平均颜色的计算方法，对非直接关联采用逐步由内层向外层拓展的颜色计算方法；因此，将主骨架到形状边界的颜色映射过程也对应划分为Ⅰ、Ⅱ两个阶段。

主骨架到形状边界的颜色映射过程如下。

1)输入形状的边界点集B；主骨架上各点颜色集C(依据1.2.6节，预先计算完成)。

2)主骨架到形状边界的颜色映射基本流程(包含第Ⅰ、Ⅱ两个阶段)，如图5所示。

3)补充说明。

构建边界点pt关联的约束骨架点集S：

在CDT分解的三角形集合中，搜索边界点pt所在的三角形的边，构建pt关联的约束边集；在主骨架点集中，筛选出落在pt关联的约束边集上的主骨架点，构建pt关联的约束骨架点集S。

设置点pt的颜色ptColor为主骨架路径端点的颜色：

取主骨架端点的颜色，并以该颜色作为C中与pt对应的边界点的颜色ptColor。

使用S计算点pt的颜色ptColor：

计算S中各点对应的主骨架上的各点颜色的平均值，作为pt的颜色ptColor。

构建index关联的三角形集合T：

收集index对应点所在的CDT分解三角形，构建三角形集合T。

三角形tri中index点的颜色计算可行性判断：

三角形tri中除index外的另外两个顶点的颜色已全部计算过，且index对应点的颜色计算还未完成，则返回True，可进行颜色计算，否则，返回False。

特别注意：三角形tri中另两个顶点颜色还没有完成计算时，则无法计算index点的颜色，暂时先出队列，重新追加到队列Q的尾端，延迟这两个顶点的颜色计算完成后再进行计算。上述处理保证了从形状内层往外层逐步扩展颜色计算，主要是解决非主骨架的骨架分枝上的各边界点的颜色计算。

插值计算三角形tri中index点的颜色：

在三角形tri中index点的颜色计算已可行的前提下，则可直接使用三角形tri中另两个顶点的颜色，通过插值计算index点的颜色ptColor。具体过程：计算该点到这两个点组成线段的最近点，如果最近点是这两个点中的某一个，直接取该点的颜色为ptColor，如果不是端点，则将该点投影到该线段上，在该线段上进行颜色插值，计算出该投影点的颜色ptColor。

图5 主骨架到形状边界的颜色映射流程 Fig. 5 Color computing from main skeleton to boundary

2 实验及分析

2.1 实验环境

显卡：NVIDIA GeForce GTX 650 Ti；处理器：Intel Core 2 Quad CPU Q9500，2.83 GHz，内存3.00 GB； 三维图形引擎OSG[17]3.0.1；Visual Studio 2010 C++。

2.2 结果及分析

参考文献[2]中的部分军事作战符号，构建一般封闭多边形、单箭头、双箭头、集结地域等图形作为实验对象。其中，针对双箭头进行了形状分解，利用左右两部分几何上的对称性，在底部中间进行分割，最后对双箭头左右两部分进行合成。

2.2.1 骨架提取及骨架路径评价

1)基于CDT的三角形中线法提取骨架。

采用基于CDT的三角形中线法提取的各图形骨架，如图6中的各图形内部黑色粗线所示。

在表1中，角平分线法按边界凸点数目统计骨架分枝，该方法提取的骨架分枝数目可代表理论骨架分枝的数目，带*数字表示真实数值不小于此处值，例如单箭头中部的弯曲部分还存在凸点等。通过表1中骨架分枝数目对比可看出，CDT三角形中线法对骨架细小分枝具有一定的裁剪能力。

图6 骨架提取及视觉显著性显示效果 Fig. 6 Skeleton extraction and visual saliency display effects 表1 不同骨架提取算法骨架分枝数目对照 Tab. 1 Skeleton branch number of different skeleton extraction methods

形状名称角平分线法CDT三角形中线法(相对比值)一般多边形83(37.5%)单箭头5*3(60.0%)双箭头(左、右)6*4(66.6%)集结区域11*11(100.0%)

基本结论：提取的骨架基本符合图形的几何中轴；骨架提取完整，验证了三角形中线法骨架提取算法的正确性。CDT三角形中线法具有一定的骨架冗余分枝裁剪能力。

2)骨架路径评价及优选比。

表2 骨架路径优选前后数目统计表Tab. 2 Total number and ratio of optimized skeleton path

基本结论：通过对骨架路径的面积、长度、跨度等的评价，优选出的骨架路径基本符合人们对主骨架的选择；较好地消除了大部分的骨架冗余分枝；集结区域图形的优选比已达5.5%，优选出的骨架路径数目有非常明显的减少。实验结果验证了骨架路径评价向量设计的合理性。

2.2.2 主骨架几何优化及颜色渐变插值计算

从优选出的骨架路径中，用户可非常方便地选出主骨架。从图6可看出，骨架端点附近及骨架分枝点附近，骨架抖动比较大，为进行颜色渐变填充，可进一步简化，进行一定的几何调整，该阶段可通过人机交互界面进行辅助处理。对比图6与图7中的各对应图形，可看出几何优化前后的较大差异。具体采用的几何优化措施如下：

在一般多边形(对比图6(a)、图7(a))中，对主骨架的两个端点进行了端点中移，中间的骨架分枝点处进行了中间弯曲消除；在单箭头(对比图6(b)、图7(b))中，在箭头部分的两个骨架端点进行了端点删除，删除了端点附近的细小骨架分枝，对箭头尾部的骨架端点进行了端点中移；在双箭头(左)(对比图6(c)、图7(c))，对箭头部分的两个骨架端点进行了端点删除，对箭头尾部的骨架端点进行了端点中移；在双箭头(右)(对比图6(d)、图7(d))，对箭头部分的两个骨架端点进行了端点删除，对箭头尾部的骨架端点进行了端点中移，其中头部增加了一个非视觉显著点的删除，尾部没有选择最优的较大球端点，而是选择了一个较小球端点，这样可保证尾部的颜色计算与双箭头(左)的尾部一致；在集结地域(对比图6(e)、图7(e))中，选择了接近较长路径的端点，明显可看出原有较多的非显著骨架路径端点已被过滤掉。

图7 主骨架几何优化及颜色渐变效果 Fig. 7 Main skeleton geometric optimization and color gradient filling

基本结论：通过比较几何优化前后效果，可看出这几种几何调整方式的合理性：经过几何优化后，消除了较多的细小骨架分枝，几何对称性较好，主骨架更加简洁、对称、美观，符合对称性美学原则，也满足格式塔理论中的对称性原则[1]，更加符合人类视觉感知，基本拟合形状的主要延伸变化趋势。

2.2.3 形状整体的颜色渐变填充

1)单颜色透明度渐变填充。

采用红色且只对透明度变化(双颜色渐变处理过程相同)，参见图8效果。

图8 单颜色的形状颜色透明度渐变效果 Fig. 8 Single color gradient filling effect

2)渐变填充样式效果比较。

基于主骨架的渐变填充与线性渐变填充比较，参见图9中虚线范围部分。图9(a)采用了基于主骨架的渐变填充，箭头部分渐变自然，而且两个箭头头部的颜色保证了一致性，满足了实际应用中箭头部分颜色要求一致的需求；而图9(b)中使用了从上到下的颜色线性渐变，两个箭头颜色无法保证，线性渐变填充在表达这种效果时比较困难。图9(c)采用主骨架线性渐变，颜色变化沿主骨架走向变化，比较自然，符合人类的视觉感知；而图9(d)中的颜色从右到左线性渐变，尾部的透明度变化没有沿箭头弯曲方向。从整体来看，图9(c)的渐变填充效果比图9(d)的效果更好。

图9 两种颜色渐变填充方法对比 Fig. 9 Comparison of main skeleton and linear color gradient filling methods

基本结论：基于主骨架的颜色渐变填充能拟合形状的延伸走势，验证了形状的颜色渐变计算的合理性。与线性渐变填充相比，基于主骨架的颜色渐变填充对弯曲的条带类等复杂区域的渐变填充效果更自然，但处理过程相对比较复杂，尤其是主骨架的选择及几何调整环节，需要较多的人机交互参与处理。在实际使用中，使用者可根据实际情况选择适配的颜色渐变填充算法：形状接近圆或矩形等，可采用中心径向、线性渐变等颜色渐变填充；弯曲条带类等复杂区域，宜采用基于主骨架的颜色渐变填充算法。

3 结语

本文基于CDT三角形中线法提取骨架，较好地裁剪了部分骨架冗余分枝；采用双栈跟踪技术提取出了骨架的全部路径，基于提取的骨架路径评价向量，对骨架路径评价优选，较好地抑制了骨架的冗余分枝，给骨架提取算法中冗余分枝裁剪这一共性难点的研究提供了一种新的思路；通过引入视觉显著性，对主骨架进行符合视觉感知的几何优化调整，并由主骨架的颜色渐变逐步外拓到整个区域的颜色映射，实现了一种基于主骨架的颜色渐变填充新样式，具有较好的沿形状延伸方向的颜色渐变填充效果。实验结果也进一步验证了本文方法的有效性，但是基于主骨架的颜色渐变填充，处理过程相对复杂，应用条件也有一定的局限，下一阶段将主要研究：1)主骨架几何优化调整的自动化处理，减少了人机交互，进一步降低了复杂性；2)带孔洞等复杂区域的颜色渐变填充，需将骨架的二叉树拓展为更加通用的图，以便进一步拓展适用范围。

参考文献(References)

[1] 陈为,沈则潜,陶煜波.数据可视化[M].北京:电子工业出版社,2014: 47-81. (CHEN W, SHEN Z Q, TAO Y B. Data Visualization [M]. Beijing: Publishing House of Electronics Industry, 2014:47-81.)

[2] 王飞,吴官祥,闵连权,等.军用地图与军事要图[M].北京:解放军出版社,2013:213-215.(WANG F, WU G X, MIN L Q, et al. Military Map and Military Plotting [M]. Beijing: Chinese Peoples Liberation Army Publishing House, 2013: 213-215.)

[3] ESRI. Military analyst and Military OverLay Editor (MOLE)[EB/OL].[2017- 07- 03]. http://www.esri.com/industries/defense.

[4] 周培德.计算几何——算法设计与分析[M].北京:清华大学出版社,2005: 43-206.(ZHOU P D. Computational Geometry—the Design and Analysis of Computer Algorithms [M]. Beijing: Tsinghua University Press, 2005:43-206.)

[5] 廖志武.2-D骨架提取算法研究进展[J].四川师范大学学报(自然科学版),2009,32(5):676-688.(LIAO Z W. A survey of 2-D skeletonization algorithm [J]. Journal of Sichuan Normal University (Natural Science), 2009, 32(5): 676-688.)

[6] 邵春丽.GIS中多边形中轴问题和算法研究[D].武汉:武汉大学,2004:12-39.(SHAO C L. Problems of medial axis of a simple polygon in GIS and its algorithm [D]. Wuhan: Wuhan University, 2004: 12-39.)

[7] 刁智华,吴贝贝,毋媛媛,等.基于图像处理的骨架提取算法的应用研究[J].计算机科学,2016,43(6A): 232-235.(DIAO Z H, WU B B, WU Y Y, et al. Application research of skeleton extraction algorithm based on image processing[J]. Computer Science, 2016, 43(6A): 232-235.)

[8] 孙德超,辛士庆,周亚训,等.重要性驱动的中轴线[J].计算机辅助设计与图形学学报,2016,28(12):2107-2113.(SUN D C, XIN S Q, ZHOU Y X, et al. Importance driven medial axis [J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(12): 2107-2113.)

[9] 王婉心,贾立锋.骨架提取中的毛刺去除方法[J].广东工业大学学报,2014,31(4):90-94.(WANG W X, JIA L F. The method of removing burrs in skeleton extraction [J]. Journal of Guangdong University of Technology, 2014, 31(4): 90-94.)

[10] 郑加宽.基于骨架特征的形状识别方法研究[D].南昌:南昌航空大学,2014:1-44.(ZHENG J K. Research on shape recognition method based on skeleton features [D]. Nangchang: Nanchang Hangkong University, 2014:1-44.)

[11] 周丹凤.视觉显著性特征约束下的形状骨架提取与分解研究[D].合肥:合肥工业大学,2013:10-45.(ZHOU D F. Shape skeleton extraction and shape decomposition based on visual saliency features [D]. Hefei: Hefei University of Technology, 2013:10-45.)

[12] 王晓燕,罗静,郭光毅,等.一种构建复杂平面图形中轴的方法[J].地理空间信息,2015, 13(4):120-122.(WANG X Y, LUO J, GUO G Y, et al. Constructing method for approximate medial axis of planar free-form shape [J]. Geospatial Information, 2015, 13(4): 120-122.)

[13] 高立青,王延章.基于截线法的快速骨架提取算法[J].自动化学报, 2016, 42(7): 1100-1112.(GAO L Q, WANG Y Z. A fast algorithm of skeleton extraction based on secant line method [J]. Acta Automatica Sinica, 2016, 42(7): 1100-1112.)

[14] 刘雨.基于边界特征点提取的网格分割[D].长春:吉林大学,2016:1-31.(LIU Y. Mesh segmentation via boundary feature points extraction [D]. Changchun: Jilin University, 2016: 1-31.)

[15] 刘小凤,吴艳兰,胡海.面状要素的多层次骨架线提取[J].测绘学报,2013,42(4):588-594.(LIU X F, WU Y L, HU H. A method of extraction multiscale skeletons for polygonal shapes [J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(4): 588-594.)

[16] 胡斯淼,任洪娥,于鸣,等.基于向量内积的新型骨架提取方法[J].液晶与显示,2015,30(5):844-850.(HU S M, REN H E, YU M, et al. A new skeleton extraction method based on vector inner production [J]. Chinese Journal of Liquid Crystals and Displays, 2015, 30(5): 844-850.)

[17] OpenSceneGraph (OSG) [EB/OL]. [2017- 07- 03]. http://www.openscenegraph.com.

This work is partially supported by the National Natural Science Foundation of China (61703412), the China Postdoctoral Science Foundation (2016M602996).

WANGJiarun, born in 1968, M. S., senior engineer. His research interests include virtual reality, high performance computing, data visualization.

RENFei, born in 1985, M. S., engineer. Her research interests include virtual reality, data visualization.

RONGMing, born in 1978, Ph. D., lecturer. His research interests include war simulation, strategic war game, weapons and equipment system simulation.

LUOTongxin, born in 1994, M. S. candidate. Her research interests include virtual reality, data visualization.