移动GIS多层空间非线性抽稀回溯算法分析

潘 翔

(广西经济管理干部学院 计算机系，广西 南宁 530007)

0 引言

移动互联网由于地理信息系统(Geographic Information System，GIS)的加入已发展成为一个全息位置服务(Location Based Services，LBS)的可视化时代，目前已广泛应用于国土管理、城市规划、交通运输等各个领域［1］。移动GIS是一个物联网(The Internet of things，IOT)热点，催生了GIS技术创新与优化，ArcGIS、超图等不断地改进其抽稀算法，以高速的数据流转与可视化信息交互适应随时随地的被标签上LBS业务应用互联互通［2］。

移动GIS的移动性、实时性要求其能够高效、准确地加载地图。DP算法(Douglas－Peucker)［3］、基于三角网的抽稀方法［4］、金字塔切片构建算法［5］等从阀值比较与判断空间数据点取舍、保留地形特征、解决可视高度调整显示问题等方面实现了抽稀，但各有不同程度无法满足实时数据处理需求的问题。针对系列算法存在的缺点，设计一种GIS多层空间非线性数据抽稀算法，能够按步长、线段长度、垂距等定义抽稀因子，减少数据中的冗余，在相邻的抽取点间以直线连续或曲线拟合、瓦片数据回溯融合的方式，加快地图的在线加载速率。

1 算法设计

移动GIS多层空间非线性抽稀回溯算法是根据移动互联网应用特点，在GIS引擎提供API数据接口，运用非线性数学模型建立一种针对数据源类型结合业务数据类型(道路、河流、桥梁、绿地、建筑物等)多级扩展细分图层进行分层抽稀、瓦片数据回溯的数据融合与加载方法。算法的核心是改进的非线性抽稀，根据GIS数据源类型划分基础层，在各层采用以步长、线段长度、垂距为抽稀因子的旋转坐标轴方法对曲线上各空间数据点到水平轴的距离进行度量，对距离小于阀值的数据点进行直线拟合，用拟合直线代替待删数据点与保留点相连，在此过程中阀值的选取是动态非线性的，避免因为阀值的区分度太低而造成抽稀失真。

非线性抽稀回溯算法可分为准备阶段和抽稀回溯阶段，准备阶段有三个过程:一是对原始地图空间数据进行切割，并记录已切割好的数据块各顶点坐标值;二是根据地图可以将加载的各类数据源分为N个基础层:Ⅰ层、Ⅱ层…N层(II≤N≤X);三是对原始数据进行分层抽稀，抽稀率最低的是第Ⅰ层，依次递增，最高的是第N层。将这N个基础层的第一次抽稀结果作为下一个阶段的输入，为二次抽稀与回溯计算阀值依据。算法框架如图1所示。

图1 算法框架

多层空间非线性抽稀回溯算法抽稀阶段是根据实际加载地图时所调用的图层数量及其对应的图层编号换算成对应的层次，对其上一邻层进行二次抽稀，同时对其下一邻层进行回溯，再将抽稀与回溯结果进行数据融合与瓦片数据拼接存储。算法过程假设经过对具体图层的转换和计算，得到层数为n(i＜n＜i+1，其中i为某个基础层，i+1为与其相邻的下一基础层)，介于i层与i+1层之间，于是对i层进行第二次抽稀，同时采用反距离加权插值法对i+1层进行回溯，最后将抽稀和回溯的结果做数据融合处理，把各个处理好的空间数据块重新以瓦片形式拼接存储。

2 算法流程

2.1 数据切割与分层算法改进

GIS地图的总体数据量非常庞大，直接对原始空间数据进行抽稀将会使矢量计算初始化过程非常缓慢［6］。因此，在抽稀前首先对空间数据进行非线性切割，使用二维表格记录切割好的每个数据块各个顶点的坐标值，用于在抽稀后对空间数据块进行瓦片拼接还原。

为了在任意业务需求下都能够快速显示数据，采取分层策略。分层以数据源类型和业务数据类型为依据，如建筑物数据(点数据)，道路数据、河流数据(线数据)，绿地、地块数据(面数据)。将具备最少数据的图层设置为Ⅰ层，最多数据的图层设置为N层，N的取值根据图层总数的大小而定，最高不超过X层。将中间的部分图层均匀设置为Ⅱ、Ⅲ、…、N－1层。可见I层的抽稀率最低，保留的数据点最多;N层的抽稀率最高，保留的数据点最少。N个层次的抽稀结果将会作为其他图层的抽稀，以及非线性阀值和空间数据反距离加权插值实现回溯算法的依据。

切割后针对不同的层次空间数据分别进行抽稀，采用改进的非线性抽稀算法:首先进行曲线距离度量，以曲线两端连线方向作为横轴，对原坐标系进行旋转，利用旋转的角度快速计算出曲线上各个数据点到新的横轴之间的距离;然后进行动态非线性阀值选取，根据相邻空间数据点之间的间距与数据总数可以计算出每个数据块的密集度，将所有密集度进行分级，设定最低为0级，最高为10级，结合要抽稀的目标层数进行阀值选取，除了0级I层和10级N层的阀值需要进行实验选取以外，其余阀值均通过计算得到;最后进行直线拟合，将度量出来的各个距离与对应阀值进行对比，判断出保留点与待剔除点，将相邻保留点之间的待剔除点用直线进行拟合，即各待删点到该直线的距离之和最小;将所有拟合直线与保留点相连，即为曲线抽稀结果，并直接为回溯提供依据。

2.2 算法实现

2.2.1 曲线距离度量

在原始空间矢量数据中建立x、y坐标，之后在算法曲线的两个端点之间设定一条连线建立曲线距离度量。以该连线作为新的横轴，建立新的直角坐标系。新的坐标系根据空间数据选取值是在旧的坐标系基础上进行了θ角度旋转，原点为O，两个端点分别为P1和PM，曲线上的点可表示为Pi和Pj(1≤i≤M，1≤j≤M)。曲线度量新的坐标轴表示为x'Oy'，如图2所示。

图2 曲线距离度量示意

非线性抽稀曲线度量依据几何原理旋转角度正弦、余弦，判断了新象限与距离，设定步骤如下:

Step1:计算点Pi在新坐标系下的坐标(xi'，yi')。根据几何原理，得到旋转角度θ的正弦、余弦值:

将向量OPi旋转θ度，即相当于让其与矩阵A右乘，设Pi的新坐标为(xi'，yi')，则有:

Step2:根据(xi'，yi')的值可以判断点Pi在新坐标系下的象限，从而得到Pi到x'轴的距离li。

(1)当 x'i＞0，y'i＞0，Pi属于第Ⅰ'象限，此时 li=+x'i－ xN/cosθ

(2)当 x'i＜0，y'i＞0，Pi属于第Ⅱ'象限，此时 li=－x'i

(3)当 x'i＜0，y'i＜0，Pi属于第Ⅲ'象限，此时 li=－x'i+xN/cosθ

(4)当 x'i＞0，y'i＜0，Pi属于第Ⅳ'象限，此时 li=

Step3:计算点Pi的相邻点Pi+1在新坐标系下的坐标(xi+1'，yi+1')。令△P为两个相邻点之间的直线向量，则其在新坐标系下表示为△P'。有:

Step4:重复Step2的步骤，得到Pi+1到x'轴的距离li+1。

Step5:重复Step3和Step4的步骤，得到曲线上所有点到x'轴的距离。

上述进行曲线距离度量的方式充分利用了前一个点的计算结果，除了第一个点的距离计算稍微复杂以外，后续计算比较简单，避免了传统的距离计算需要反复开方的方式，降低了算法的复杂度，提高了算法的效率。

2.2.2 动态非线性阀值选取

移动GIS多层空间抽稀曲线上各数据点的距离度量出来后，将依次与阀值进行对比，距离大于阀值的将保留，距离小于阀值的将被剔除。可见阀值的大小决定了空间数据点是否会被剔除:阀值太大会造成大量数据被删除，其中很有可能包括GIS热点数据;阀值太小则会造成冗余数据没有被删除，抽稀效果不好。考虑到移动GIS地图中不同的区域热点数据的密集程度不同，且经过分层后，每一层的抽稀程度也有区别，因此采用动态非线性阀值选取方式，最大程度保留有用数据，剔除冗余数据。

对空间数据点的密集程度进行分级，分析每个数据块中各相邻点之间的间距，结合数据块中数据点的个数，可以得到数据点的密集度。空间数据密集度可以表示为:

其中Dij(x)为编号第ij号的空间数据块数据密集度，N为该数据块中相邻数据对的个数，d(xi，xi+1)为相邻数据对之间的间距，M为该数据块中数据点总个数。将密集度最高的数据块设为10级，密集度最低的数据块设为0级，则其余数据块的级数表示为:

将数据块的级数与要抽稀的层数之和作为选定阀值的依据，首先对0级数据块Ⅰ层抽稀目标进行阀值选取，根据大量实验结果得到最合适的阀值ε1;再对10级数据块Ⅳ层抽稀目标进行阀值选取，得到阀值εN(N为数据块总个数)。剩余级别与层数结合所选取的阀值将以ε1和εN作为参考依据，计算公式如下:

其中L为抽稀的目标层数(Ⅰ≤L≤Ⅳ)，εi为级数为Si进行L层抽稀的阀值。可见阀值的选取是非线性的，当同级别同层次抽稀时，阀值不变;但级别或层次有变化时，阀值会相应进行动态改变，以便适应不同的抽稀需求。

2.2.3 直线拟合

经过阀值对比后，GIS待剔点理应被删掉。然而，非性线GIS抽稀与回溯若直接将保留点用直线连接，将导致剔除点所在的区域误差较大，因此采用直线拟合的方式对所有待删点的整体进行逼近。拟合前后的效果如图3所示。

图3 拟合前后效果对比

选取各点的距离最大值lmax与给定阀值ε进行比较。若lmax＜ε，则将该点记为Qi，否则保留该点的记法。被保留记法的点将曲线分成了两部分，分别对这两部分重复上述操作，直到将曲线上所有的数据点重新处理。

经过处理的数据点分为保留点集合P和待删点集合Q。设两个相邻保留点之间的待删点集合为Q1，Q2…QN，分别将待删点Qi(1≤i≤N)集合进行直线拟合，方法如下。

设待删点集合 Qi中各点的坐标分别为(x1'，y1')、(x2'，y2')…(xM'，yM')，其几何中心点坐标为:

设u为矩阵XTX最小特征值所对应的特征向量，则=λu(λ为令的最后一个值为－1的常量)时，目标函数F(X，Y)取值最小。

将各个相邻保留点之间的待删点全部进行直线拟合后，选取抽稀层数与阀值最佳值，使各段拟合直线与保留点连接起来，删除待删点，获得曲线抽稀结果，并为高层的空间数据回溯提供反距离加权插值依据。

2.3 回溯与数据融合拼接

在移动GIS多层空间矢量抽稀过的数据，可能会有数据抽稀过多或过少的情况，为保证抽稀算法的精确度，在上一邻层抽稀的同时依托曲线度量、动态非线性阀值与直线拟合的最优计算进行下一邻层的数据回溯。此时并非将数据还原为原始数据，而是将其还原到目标图层的层次(介于标准层次之间)。采用空间数据反距离加权插值对高层数据进行回溯。

选取圆形作为搜索区域，半径为R。设S为数据块面积，M为数据块在该层的数据点总数，Mmin为搜索区域内数据点最少的点数，则存在πR2=SMmin/M。设MR为以搜索半径为R的搜索区域内的数据点数，已知数据点为 Pi(xi，yi)(1≤i≤MR)，则待插点 Pj(xj，yj)的计算公式如下:

式中γ取值为0至5的整数，dij为已知点Pi到待插点Pj的距离。

同一个空间数据块经过抽稀与回溯后，将抽稀结果与回溯结果进行融合，目的是提高数据保真度，同时实现以瓦片数据形式存储，减少矢量高能耗计算，提升移动GIS加载速度。融合过程可简单描述如下:设GIS抽稀结果数据集为 V{v1，v2，…，vN}，回溯结果数据集为 B{b1，b2，…，bN};初始化令结果集 R=V，依次取出集合B中的元素与集合V中的元素进行匹配，若发现无匹配的数据项，则证明该元素是被误删的数据，将其加入集合R中，反复上述步骤直到集合B中的最后一个元素匹配完毕;得到的结果集R即为对该数据块进行某层次抽稀的最终结果。

GIS图层按照切割时所记录的顶点坐标值进行扫描匹配，对数据块进行拼接与瓦片数据存储，完成整个抽稀与回溯过程。

3 算法测试

算法测试采用仿真测试和ArcGIS引擎实际开发测试两种形式，对单次抽稀算法和多层抽稀回溯算法进行对比。其中单次抽稀算法包括DP算法、垂距限值法、金字塔切片法、线段过滤法。同时使用ArcGIS Runtime SDK for Andriod应用开发工具包，对各类单次抽稀算法和多层空间非线性抽稀回溯算法进行编程实现，同时编写一段检测代码测试每个算法的性能指标。首先使用MATLAB对各算法理论进行仿真，理想条件下多层空间非线性抽稀回溯算法与各个单次抽稀算法的仿真曲线如图4所示，算法加载时间与处理能力对比如图5所示。

图4 算法仿真曲线图

图5 算法加载时间与处理能力仿真对比图

图4表明抽稀后的数据以使用多层空间非线性抽稀回溯算法与原数据的拟合程度最高，图5表明同样的数据量，抽稀回溯算法所采用的加载时间最短，除了刚开始对基础层的抽稀耗时较多外，后续的数据量增大并不会对加载时间造成太大影响。加载速度的提高得益于抽稀回溯数据融合与拼接瓦片数据存储，极大减少了矢量计算所耗费的资源。

4 结束语

移动GIS多层空间非线性抽稀回溯算法是在移动互联网、北斗卫星导航、GPS等物联网技术进一步高精度融合，交通、物流、生活应用GIS移动化趋于普适而提出的一种叠加于多业务功能的空间数据抽稀算法。它通过动态非线性阀值的选取、原数据的直线拟合等对远程加载GIS空间数据进行分层抽稀，减少数据流量与提高加载速度。算法进行多层数据空间二次抽稀与回溯，将抽稀结果和回溯结果进行融合与拼接，采用瓦片数据形式存储，保证最终抽稀效果最大程度保留原始数据，提升加载速度。实验表明从加载时间、抽稀率和还原率等方面，该算法都优于传统的单次抽稀算法，能很好地满足移动GIS的应用需求。

［1］李晓军，吴金辉，吴啸，等.基于Android的移动监察GIS平台研发与分析［J］.测绘通报，2012(10):637－639.

［2］潘翔.基于GIS的交通物流预警图像传输优化［J］.河池学院学报，2014，34(2):65－70.

［3］卢银宏，岳东杰.基于总体最小二乘的Douglas－Peucker算法在多波束测深数据抽稀中的应用［J］.水利与建筑工程学报，2012，10(2):4－5.

［4］Shen Yunzhong，Li Bofeng，Chen Yi.An iterative solution of weighted total least－ squares adjustment［J］.Journal of Geodesy，2010，85(4):229－238.

［5］冯宇瀚，殷晓冬，王少帅，等.基于三角网构建海底DEM的抽稀算法［J］.海洋测绘，2012，32(6):33－35.

［6］龚健雅，李小龙，吴华意.实时GIS时空数据模型［J］.测绘学报，2014.43(3):226－232，275.