TIN压缩技术方法研究

王 璇，朱 映，王 玮

(1.中山市基础地理信息中心，广东中山528400;2.江苏省基础地理信息中心，江苏南京210013)

一、引 言

随着地理信息系统、遥感、虚拟地理环境等技术的发展，数字高程模型(DEM)得到了广泛的应用。DEM数据处理、传输速度与用户需求之间的矛盾日益突出，DEM数据压缩技术便顺应时势成为当今研究的热点。DEM有许多种表示方法，其中不规则三角网模型(即TIN模型)相对于DEM中的其他模型有着不可替代的优点［1］。地理信息数据量的增大，对空间数据的存储和传输提出了很高的要求，除了提高硬件设备，开发DEM的压缩算法也成为一种迫切的需求。因此，研究TIN的建立和压缩是非常有意义的［2］。

二、顶点聚合法和基于中心点的顶点消去算法介绍

1.顶点聚合法

顶点聚合的方法是由 Rossignac和Borrel［3］最先提出的。其基本思想是将输入模型的顶点坐标量化成整数，这相当于在几何上建立了一个方格坐标，而将所有落在一个方格内的顶点合并(聚合)为一个代表该方格的顶点，被完整地包含在一个方格中的所有三角形和边也都被合并为一个点，从而简略掉这些三角形和边。

阈值为10的顶点聚合如图1所示。

图中，点A、B、C将被聚合到点D的位置，也就是虚拟网格的交点，从而简化三角网。此时，需要对点D进行高程预测。本文采用反距离加权的方法，公式如下

式中，Zi是i点的高程;Si是i点到网格交点的距离。

图1 阈值为10的顶点聚合

2.基于中心的顶点消去算法

介于上面的方法要进行高程的插值，笔者提出一种无需插值、可以直接快速压缩三角网的方法，过程类似于顶点消去法，基于某中心点为基础进行点的消去。

该方法原理简单，以某个点为中心，基于某种消去条件，删除周围该条件下指标小于该阈值的点。一般最简单的情况是以距离作为消去条件，即离目标点小于某阈值的点删除。

阈值为R的基于中心的顶点消去算法如图2所示，离中心点A的距离小于R的点B、C、D将被消去。

图2 阈值为R的基于中心的顶点消去算法原理

三、系统的总体框架设计与主要功能实现

系统的总体框架设计如图3所示。

图3 系统总体框架设计

软件主要实现以下功能:

1)数据录入:通过两种方式录入数据，第一种是以类似数字化的方式从屏幕直接通过鼠标点击录入数据点;第二种是通过外部文件(*.txt)直接载入文件。

2)TIN建立:该软件的TIN建立方法为静态三角网生长算法［4］，内部算法结构采用队列法。

3)TIN压缩:该软件实现了两种TIN压缩方法，即顶点聚合法和基于中心点的顶点消去法。

4)结果评估:该软件可以对压缩前后的顶点数和三角形数进行统计，用于压缩评价指标;另外，通过从外部录入的校正点，可以计算高程误差和高程中误差。

5)数据点管理与操作:软件对于数据点的管理与操作通过内置的顶点数组来实现，通过在数组中添加删除点，然后进行三角网的实时重绘，来实现数据点的管理。

四、不同算法各阈值下压缩结果分析

选取南京紫金山试验区的1∶5万地形图等高线数据。通过软件的即时输入方法(数字化)构网后，节点个数为52，三角形个数为82。原始数据生成的TIN如图4所示。

图4 原始数据生成的TIN

1.基于中心点的顶点消去法

对建立的TIN采用基于中心点的顶点消去法进行压缩，分别取阈值为10、20、30、40个像素，压缩结果(即重新构网的结果)如图5所示。其中，(a)、(b)、(c)、(d)分别为阈值10、20、30、40 压缩后的三角构网。从图中可以看出，随着阈值的增大，压缩后TIN的三角网密度在减小，精度在降低。

图5 基于中心点的顶点消去法压缩结果图

在10、20、30、40个像素的阈值下的TIN数据压缩后，各阈值下的压缩结果统计见表1，各阈值下的高程误差统计见表2。从表1可以看出，随着阈值的增大，数据量、节点数、三角形个数都在减少，数据量压缩比、点压缩比和三角形压缩比迅速增大，但三角网产生的特征形变不大。

表1 各阈值下的压缩结果统计表

表2 各阈值下的高程误差统计表

2.顶点聚合法

对建立的TIN采用基顶点聚合压缩方法进行压缩，分别取阈值为10、20、30、40个像素。压缩结果(即重新构网的结果)如图6所示。其中，(a)、(b)、(c)、(d)分别为阈值 10、20、30、40 压缩后的三角构网。从图中可以看出，随着阈值的增大，压缩后TIN的三角网密度在减小，精度在降低，同时，产生了很大的变形。

图6 顶点聚合法压缩结果图

利用顶点聚合法，可以看出，随着阈值的增大，高程中误差增大较快，三角网的形状变化非常大，但三角形数量的减少并不显著。各阈值下的压缩结果统计见表3，各阈值下的高程误差统计见表4。

表3 各阈值下的压缩结果统计表

表4 最大高程误差和中误差差值表

五、两种方法的比较及结论

通过上面的比较可以看出，顶点消去法的压缩比率非常大，三角网的变形不大;顶点聚合法的压缩比增大并不多，但三角网产生的特征形变却很大。基于给定数据点的特征，得出以下结论:

从压缩结果来看，顶点消去法更能适合试验区域。它产生的三角网形状变化和高程误差比顶点聚合法都要小一些。由于高程点比较稀疏，随着阈值的增大，顶点聚合法的网格效应非常明显，可见此方法不适用于采集点过于稀疏的情况。虽然顶点消去法的高程中误差较小，但并不能完全说明它的绝对优越性。该方法的压缩过程不经过插值，也没有点的移动，因此在误差计算时可能会出现一些与校正点重合的高程点，这些点的高程误差是0，从而使整个三角网的误差偏低。顶点消去法不经过插值，所以使一些不该删去的点被删去，可能会丢失一些重要的高程点，且一些重要的地形特征被当作冗余信息被压缩，故仍需要在程序中加以控制，强制保留重要高程点。

对于顶点聚合法，考虑到采集点的密度不大，在进行强制性的网格转换时每个点移位都比较大，从而产生了较大的误差。另外，大量的插值导致误差的累积，也是该方法产生较大误差的原因。顶点聚合法的优点在于，压缩后三角网中的每一个点都保留了原始三角网中相邻数据点的信息，从而在反映特殊地貌上不存在丢失重要高程点的缺点，但仍然需要提高插值的精度，以降低高程误差。

六、结束语

本次试验通过对比基于中心点的顶点消去法和顶点聚合法对同一地区TIN的压缩，分析二者产生误差的不同原因及优缺点，并提出相应的解决方案如下:

对于基于中心点的顶点消去法，由于该方法不经过插值，其精确度很大程度取决于各中心点的选取。在实际操作中，应该对高程点进行预处理，找出对地形影响较大的高程点和一些重要的、标志性的高程点，强制使其成为中心点，从而在压缩过程中不被删去。这样将显著提高该方法的误差。

对于顶点聚合法，由于在实际工作和研究中，高程采集点的密度会比本文的试验中大很多，因此，该方法的主要误差来源是插值方法。从便于研究的方便出发，本文选择了简单易行的反距离加权插值。在实际应用中，则应该针对不同的地形特征，研究更加精确、更加适合于试验区地形的插值方式。

［1］李志林，朱庆.数字高程模型［M］.武汉:武汉大学出版社，2001.

［2］蔡先华，郑天栋.数字高程模型数据压缩及算法研究［J］.测绘通报，2003(12):16-18.

［3］ROSSIGNAC J，BORREL P.Multi-Resolution 3D Approximations for Rendering Complex Scenes［C］∥Geometric Modeling in Computer Graphics.［S.l.］:Springer Berlin Heidelberg 1993:455-465.

［4］林报嘉，叶燕林，赵建伟.三角网的生成与简化算法［J］.地理学与国土研究，2001，17(1):69-71.