激光雷达数据的Delaunay三角网格简化算法研究进展分析

侯竞夫

（诺丁汉大学，英国诺丁汉，NG7 2RD）

0 引言

激光雷达（LIDAR）作为观测技术的一种，其可以通过激光扫描得到距离、角度等庞大的数据，进而通过算法来分析观测对象的形状、结构，构建出三维图形。激光雷达相较于其他的观测技术具有较高的自动化程度，可以对地表纹理信息不符合要求的区域进行数据测量[1]。值得注意的是，激光雷达扫描所得数据信息量庞大，而且相互交错，进行算法分析难度较高，目前主要通过Delaunay三角剖分算法来完成激光雷达扫描所得数据的分析，这种算法类型构建出了三角网格模型，具有“元规则”、“最大最小角规则”等基本原理，进行数据分析时可以有效避免尖锐内角的产生，确保了数据分析结果的准确性，但考虑到激光雷达扫描所得数据复杂程度高等问题，采用这种模型进行数据分析的耗时较长，需要积极探索合适的手段进行网格模型的简化，进一步缩短计算耗时、降低存储要求[2]。

国内外就网格模型的简化研究已经取得不错进展，如国外学者ECK就曾提出将小波技术用于网格模型的简化，Schroeder提出了删除顶点进行网格模型优化的手段，均取得良好的应用效果[3]。顶点是网格模型的重要单位，采用Delaunay三角剖分法进行数据分析时，需要搭配一定数量的顶点，进行网格模型的简化工作时，可以从顶点去除的角度出发，即按照相应的准则依次将顶点从模型中去除，目前提出并得到应用的顶点去除准则有Schroeder的平面准则、Hamann的曲率准则[4]，本文讨论了常见的网格简化算法和网格简化过程中的部分基本准则，并且展望了针对激光雷达数据处理的Delaunay三角网格简化算法的发展。

1 激光雷达数据的Delaunay三角网格简化算法的研究意义

网格简化算法不仅仅局限于激光雷达扫描所得数据的简化，其他计算机图像学中也有关于这方面的应用，以至于可以高效率、低成本地呈现出图像，供给人们了解研究对象，甚至与研究对象之间进行交互。针对目前激光雷达数据处理使用到的Delaunay三角网格模型，其目的是对收集到的数据进行处理并进行三维实体呈现，但实际激光雷达收集到的数据相对较大，利用这种方法进行处理，最终会得到数十万个、数百万个甚至上亿个三角网格，如此庞大的数据量，对于进行计算处理的计算机的数据分析功能、显示功能以及存储功能来说都是巨大的挑战。就目前关于三角网络算法的研究来看，其带来的问题主要体现在四个方面：

（1）数据分析的耗时较长，绘制三维图形的速度明显较低；

（2）大量的数据需要通过硬件设施存储下来，需要占用相当大的存储空间；

（3）最终得到三维模型的分析、处理、编辑难度较高；

（4）多数网格简化方法以网格模型的几何特性和属性为基准，通常不关注网格模型的感知逼真度、封闭性、用户需求。

基于以上问题，进行激光雷达扫描所得数据算法分析时，需要积极探索合适的手段，对算法处理的流程进行简化，确保其处理所得图像保持较高的真实感。正常情况下虚拟空间中的三维模型都基于多边形网络模型，为了提升其真实度和准确性，都尽可能地希望其组成部分拥有更多的多边形面片，但构成对象的多边形数据越多，数据处理时间也就越长，因此对必要的网格模型进行保留，用于计算机的分析计算，其他网格模型则可以予以删除，激光雷达数据的Delaunay三角网格模型也应当遵循这一原则进行简化。其意义主要体现在在[5]：

（1）提高了算法的实时性，特别对于部分情况下的实时动态显示；可以通过选择性地忽略部分细节，保证前期计算速度，当计算能力足够时，再逐步补充细节模型；

（2）减少了计算量，节约了储存空间；

（3）可以实现对算法的加速，提高曲面处理和碰撞检测的能力。

2 常用网格简化算法

2.1 体数据简化法

体数据，又称格点数据。体数据与面数据的最大差别在于是否包含体细节，而体素则是体数据的最小单元，使用空间体素数据缓存的好处是可以直接通过删除小体积体素来减少数据量。因为体数据间隔区域内的值可以用距该值最近的格点数值近似表示，也可使用数学方法模拟生成，而小体积体素的信息熵更低，删除小体积体素所获得的简化网格模型更加贴近原网格模型。但是该方法局限性较强，仅适合用于以体素形式储存的网格模型；如果用于处理非体素网格模型，效率较低，数据处理速度较慢。此外，体数据简化法最终获得的简化网格质量受删除标准的影响较大。

2.2 顶点删除法

该方法最早由Schroeder提出，通过遍历网格模型内的所有顶点，选择重要程度较低的点和三角形删除，然后重新三角化。具体操作时，首先根据几何结构和拓扑结构，将网格模型内的所有顶点分为五类：简单形、复杂形、边界形、内部边形和角点形。[16]除复杂形顶点外，其他类型顶点都可在需要的情况下删去。图1展示了五类顶点的基本特征：

图1 顶点删除法顶点分类

顶点删除法计算速度较快，产生的网格质量较好。但顶点删除法只适合于流形网格。因为非流形网格中复杂顶点的删除不产生一个空洞，即不可进行重新三角化。而且这种方法改变了原网格的拓扑特征[6]。图2展示的即是顶点删除法：

图2 顶点删除法

2.3 顶点聚类法

顶点聚类法的基本思路与体素降采样的思路类似，此方法用一个包围盒来包围网格模型，包围盒的形状可以是长方体或者球形，将包围盒分割成若干个区域并赋予权值，尽可能地使相似的原始网格模型元素位于同一区域，而不相似的原始网格模型元素则划分到不同区域。然后使用一个特定的代表顶点表示特定区域内的所有点，该代表顶点与所代表区域内所有点的权值近似等价，使用代表顶点构建新的简化网格模型，减少了点的数量，从而简化了原始网格模型。顶点聚类法的优点在于可以一次性处理大量顶点，效率较高，而且对于任意网格模型都有不错的简化效果。但是该方法将原网格模型分割，改变了原始网格模型的连接结构，其简化模型可能丢失部分拓扑特征信息[11]。面片聚类法与顶点聚类法的思路和优缺点大体相同，只是面片聚类法是选择相似多边形进行合并，从而减少面片数量，达到简化网格模型的目的。

图3和图4分别展示了两个由顶点聚类法得出的简化网格模型。图3中的简化网格模型未丢失拓扑特征信息；而图4中的简化网格模型的拓扑特征发生了明显变化。

图3 拓扑特征信息未丢失的顶点聚类法

图4 拓扑特征信息丢失的顶点聚类法

2.4 包络法

在建立简化网格后，定义误差度量，即简化网格顶点与原网格的距离，设置需要的距离误差，构造两个包络网格，一个向外偏移，一个向内偏移，然后使用两个包络网格作为基准进行简化。但是包络法因为要构造两个额外的包络网格，极大地增加了计算量。

而且，在处理多雷达问题时，包络法存在信息冗余的问题，因为不同雷达包络可能在空间相交，不利于形成统一的雷达网探测态势。如果想要解决这个问题，那么就需要依次分析所有的雷达包络采样点，判断是否有雷达包络采样点同时位于多个雷达包络网格模型内，必然会极大地增加计算时间和难度，尤其是在三维空间中，雷达包络数据量更大，采样点更多，结构更为复杂，加之可能出现的干扰问题，会使对于雷达包络采样点的判定更加困难。刘彦君等人针对这一问题，提出了基于投影网格的雷达包络融合方法，在雷达包络相交区域构建小面积网格，对每组相交雷达包络对做竖投影和侧投影，过滤得到重叠区探测点和非重叠区探测点，从而实现包络融合，进而使用包络法处理原始网格模型，获得简化网格模型。因为投影算法对于构建的小面积网格的网格长度和投影策略比较敏感，所以采用标准重叠区探测点对比库方式得到最优的网格长度，使用成对投影降低计算复杂度[17]。虽然刘彦君等人的方法受网格长度影响较大，最终得到的包络网格质量可能并不理想，但该方法可以满足一般情况下的需求，并且为多雷达包络法的进一步优化奠定了基础。图5展示了基于投影网格的雷达包络融合算法的基本思路。

图5 基于投影网格的雷达包络融合算法

此外，在实际应用中，往往存在大量的自交网格模型，但是包络法处理自交网格模型的能力较弱。针对包络法无法处理自交网格模型的问题，张明敏等人提出了一种基于超包络的网格简化算法[19]，可以处理任意类型的网格模型，包括自交网格模型，而且张明敏等人的算法还简化了包络构造，减少了计算量。

2.5 渐进网格法

渐进网格法首先使用边折叠的方式将原始网格模型变为一个分辨率极低的基网格模型。之后进行顶点分裂操作，即根据在边折叠操作中获得的细节信息，逐步更新基网格。顶点分裂操作在某种程度上可以视为之前进行的边折叠操作的逆操作。如果将所有细节信息用于基网格模型，即可将基网格模型回复为原始网格模型；如果只使用部分细节信息，便可以得到一个简化后的网格模型。图6展示了边收缩与点分裂操作。

图6 边收缩与点分裂操作

上述过程可以表述如下：

边收缩过程：

点分裂过程：

这种方法可以有效降低网格模型对储存空间的需求，实现层次细节模型。但是渐进网格法在边收缩过程中，每次都需要搜索选择删除的边，计算时间较长。针对这一问题，谷东东[20]等人优化了边收缩过程中的权值公式，使渐进网格法可以更加高效地搜索选择需要删除的边。顾耀林等人则在生成基网格时，记录所有三角形的权值和细节，在边收缩过程中搜索选择需要删除的边时，可以直接根据之前的记录读出最小权值三角形[21]进行删除。虽然顾耀林等人的方法需要在每一次边收缩后修正收缩边的相邻三角形权值，并用权值重新为三角形排序，但相比于使用全局搜索搜寻需要删除的边，这种这种局部调整耗时较少。

2.6 重新布点法

重新布点法是一种最小误差简化算法，该算法的优点在于可以根据需要设置简化模型的顶点数量。该方法在原始网格模型上随机生成一定数量的顶点，生成的顶点将作为基准最终生成简化网格模型，简化网格模型顶点数量可自行指定。然后根据顶点斥力重新划分原始网格模型上的顶点和生成的简化网格模型顶点，并进行三角剖分生成过渡网格模型。最终删除过渡网格模型中的所有原始网格模型顶点，对简化网格模型顶点进行三角剖分，生成简化网格模型。但该方法步骤较为繁琐。Taosong He等人将重新布点法与体数据简化法结合，提出了一种自适应表面生成算法用于网格简化，但是该方法可能会改变原始网格模型的拓扑结构[17]。

2.7 小波方法

一般情况下，小波方法将原始网格模型分解为两个部分，第一个部分是只包含原始网格模型最基本要素的极简网格模型，另一个部分为从极简网格模型中剔除的原始网格模型细节，然后通过两部分的合成生成相应的简化模型。但是小波方法的每个曲面都需要通过小波表达式进行构建，这种算法复杂度较高，而且只可用于具有细分连续性的网格。虽然改进后地ECK算法可以使用小波表达式构建任意网格模型，但是该算法通常只会保留连续特征区域，而且因为需要使用调和映射，计算量很大。但该算法所生成的模型可以在保证过渡和网格质量的前提下保持较高的压缩率，是某些情况下的理想选择。

3 网格简化的准则介绍

网格简化，即通过近似的方式将多边形网格模型简化，简化模型仍具备原网格模型的基本可视特征，但其数据量远小于原始模型。常用方法是通过赋予权值、定义误差等方式来评价原网格模型中的元素，然后选择性地移除重要程度较低、对模型整体影响较小的元素。而评价元素的方式即是所用算法的简化准则。下面是部分常用的简化准则：

（1）通过计算顶点与平均平面的距离。距离越小，则顶点越密集，信息熵越大，顶点的重要性越低。该简化准则常见于顶点删除法中。

（2）通过顶点曲率来判断元素的重要程度。对于曲线曲面造型，曲率越低，则区分度越低，也就越不重要。

（3）通过特征角判断元素的重要程度。给定特征角角度后，则该特征角内包含最多的原始网格模型信息，相对的，其他非特征边及顶点中的信息相对较少，所以重要程度偏低，可以删除。此外，还可以通过定义顶点的特征角进行简化，其主要特点是在所有包含该顶点的三角面中，该顶点的特征角夹角最大，信息量最丰富。而顶点的特征角越大，说明其包含的信息越丰富，所以可以删除特征角较小的顶点，实现网格简化的目的[7]。

（4）使用二次误差度量评价元素的重要程度。对于一个顶点u，顶点u连接的的边的集合为S，设顶点集合T，顶点u与集合T中的顶点都可通过集合S可达，设顶点集合T中所有顶点的有序三角形环的集合为N，计算顶点u与集合N中所有有序三角形环的距离平方和，作为边折叠简化的评价方法。该算法时间复杂度较低，且拥有优异的简化质量。

4 激光雷达数据Delaunay三角网格简化算法的发展展望

4.1 提高简化后的外观相似性

网格简化的目的是通过近似的方式将多边形网格模型简化并保留原网格模型的基本可视特征。但现有的多数网格简化方法并不是特别关注外观相似性，比如顶点聚类法得出的简化模型就可能发生变形。若简化模型与原网格模型的可视特征差异较大，最终会影响激光雷达探测的准确性。

4.2 提高简化后的实时性

激光雷达数据的处理对于实时性有较高要求。可以考虑优化模型数据结构和存储方式，提高数据存储与索引的速度，减少耗时。也可进一步提高简化模型的压缩率，略去次要细节，采用渐进显示的方式，提高简化模型的实时性。

4.3 提高简化后的通用性

针对已知的特定网格模型进行简化处理并不困难，但激光雷达需要面对的环境较为复杂、突发情况较多，往往难以预测。因此，设计出可使用于任何网格模型的通用简化算法有着重要意义。而且，因为数据量大且复杂，又受到计算机硬件技术的限制，对激光雷达的数据处理通常很难在单一设备上完成，往往需要使用分布式技术或并行技术协同多设备运作，而开发通用简化算法有助于减少设备间的通信开销，提高激光雷达数据处理的效率，减少数据处理时间。

5 结束语

激光雷达数据的Delaunay三角网格分析方法尚存在一定的不足，需要积极研究并探索简化手段。这对于计算机处理速度的提升、内存空间的节省都具有积极作用，也有利于推动激光雷达测量技术的革新。