向量相似度可复原三维点云压缩算法*

张旭康，牛保宁，张锦文

太原理工大学 信息与计算机学院，太原 030000

1 引言

三维激光扫描技术又被称为实景复制技术，激光扫描系统可以快速、自动、实时地获取目标物体表面的高精度三维点云数据。该技术被广泛应用于文物古迹保护、建筑、规划、医学、土木工程、工厂改造、室内设计等领域[1-5]。三维激光扫描仪扫描物体产生的数据量十分庞大，含有大量冗余数据。后期的数据处理、传输和使用要耗费大量的时间和空间资源。因此，在保留重要模型特征的前提下，压缩点云数据，减少点云数据量，成为目前点云数据处理的主要任务之一。

当前的点云压缩算法主要有三类[6]：概率压缩、网格压缩、曲率压缩。概率压缩算法随机地剔除模型中一部分点，每个点的剔除概率相同，只需进行一次点云遍历，实现简单，运行速度快，时间和空间复杂度低。但此类算法没有考虑模型特征点区域，无法保证模型特征的完整性和精度。网格压缩算法，使用六面体或者四面体等形状的网格，将模型分为多个部分分别压缩。该类算法为了保证模型压缩精度，需要增加网格的个数，导致算法时间和空间复杂度高，网格数据也会占用大量的内存空间。曲率压缩算法，根据模型表面的曲率大小和变化幅度来提取三维模型的细节特征，特征保留效果较好，但是在模型表面平缓、变化幅度小的部位，不能很好地控制点的留存度。由于三维模型的表面特征复杂，被去除的点可能跨越多个复杂曲面或多层曲面，造成被压缩的点集合杂乱、无规律，难以组织用于复原，因此这些点云压缩算法没有对应的点云复原算法。

针对点云压缩算法存在的以上问题，本文提出一种易于实现、能够保留模型重要特征的向量相似点云压缩算法，以及与该压缩算法对应的点云复原算法CVS（compression based on vector similarity）。CVS 能够较好地保留模型的细节特征，复原精度高，时间复杂度为O(n2)。

本文的创新如下：

（1）提出一种新的向量相似度度量——L3A 相似度。对于两个从原点出发的向量，L（length）是它们长度差值的绝对值，3A（angle）是它们与三个坐标轴夹角余弦的差的绝对值。L3A 用来判断点云的稠密程度。

（2）CVS 压缩算法根据L3A 相似度，生成覆盖整个模型的参考向量采样空间集合，对每个采样空间按照其曲面曲率，确定剔除数据点的概率，以保留模型的细节特征。

（3）CVS 复原算法利用压缩算法在压缩时生成的曲率信息，对压缩后点云进行增厚增稠处理，可有效复原点云模型细节。

2 相关工作

基于曲率的点云压缩算法主要通过度量曲面的变化程度来判断模型的特征区域，尽可能地保留特征点。Han 等人[7]利用边缘点和非边缘点法向量的不同，保留模型边缘点，维持点云的细节特征。符晨曦等人[8]提出法向量夹角法和曲率采样法协同的压缩算法，减少平坦区域内的点，保留高曲率区域内的点，来保证细节特征不丢失。陈朋等人[9]提出点到平面距离的点云数据压缩方法，该方法计算每个模型点到其最近三个点组成平面的距离，通过距离的大小来判断模型表面的复杂程度。基于曲率的算法提取特征点的效果较好，但是不能控制平坦区域的压缩程度，容易出现过压缩现象，而且这些压缩算法均没有对应的点云复原方法。

基于网格的点云压缩主要通过创建多个体积相同的网格将模型分为多块，进行分块压缩，同时结合曲率、聚类等算法来提高特征保留度。付忠敏等人[10]提出基于主成分分析与栅格划分的压缩算法，用栅格划分模型，用主成分分析算法保留模型特征区域不被压缩。但是此算法容易在模型平缓部位产生过度压缩现象。姚顽强等人[11]提出基于改进八叉树的三维点云压缩算法，能够有效地去除离群点，较完整地保留关键信息。陈龙等人[12]使用八叉树创建聚类中心，然后使用K-means 聚类算法确认特征区域，并计算区域中点的曲率法向量与邻域点法向量夹角的平均值等多个参数来提高特征点的保留效果。叶珉吕等人[13]使用KDtree 构建邻域，创建拓扑，计算模型曲率压缩点云。这些基于网格的算法在构建网格时需要消耗较多的时间和空间，尤其是使用较复杂的算法如聚类算法、主成分分析算法提取特征区域时，随着模型数据量的增加，压缩时间显著增加。

3 CVS 压缩算法

CVS 压缩算法的核心是L3A 相似度。

3.1 L3A 相似度

如图1 所示，V1、V2是两个从原点出发的向量，标号①、⑤分别代表向量V1、V2的长度，记作L(V1)、L(V2)。标号②、③、④分别代表向量V1与坐标轴X、Y、Z的夹角的余弦，记作A(V1,X)、A(V1,Y)、A(V1,Z)。标号⑥、⑦、⑧分别代表向量V2与坐标轴X、Y、Z的夹角的余弦值，记作A(V2,X)、A(V2,Y)、A(V2,Z)。

Fig.1 Definition of L3A similarity图1 L3A 相似度定义

四元组(Δlength,ΔangleX,ΔangleY,ΔangleZ)表示向量V1和V2的相似程度，被称作L3A 相似度。判别V1和V2相似与否的函数定义如下：

ΔL是V1和V2长度差的绝对值上限，ΔAX、ΔAY、ΔAZ分别是V1和V2与坐标轴X、Y、Z的夹角余弦的差的绝对值上限。如果四元组中四个值均分别小于或等于四个阈值，函数值为1，表示向量V1与V2相似。否则，输出0，表示两个向量不相似。

图2 是将点云中每个点与原点连接形成向量后的示意图。区域①和②点云较密，向量之间的长度和夹角都相近。区域③点云较疏，向量之间的长度相差较大，夹角相近。区域④点云较疏，向量之间长度相近，夹角相差较大。在三维模型的一个稠密点云区域中，会存在大量的位置相近的点，这些点分成多个相邻的子区域并映射到向量空间，每个子区域会呈现出上图标号①、②区域周围向量的特点，即向量之间的L3A 相似度四元组中的四个值的变化范围均很小。而稀疏点云区域中的点映射到向量空间，每个子区域的向量之间的L3A 相似度四元组中的四个值的变化范围均很大。

Fig.2 Vector graph formed by coordinates of multiple clusters of point clouds connected to origin图2 多团点云坐标与原点连接形成的向量图

3.2 参考向量采样空间生成

函数f()有6 个参数，4 个阈值可以分别被看作是一个向量的长度值与X、Y、Z坐标轴角度余弦的最大变化范围。给定向量V1和4 个阈值，所有与V1相似的向量V2构成了一个相似向量空间。向量V1被称为参考向量，阈值确定时，向量V1生成的相似向量空间被称为采样空间。

CVS 选取多个参考向量，并设定阈值，使得这些参考向量生成的采样空间集合能够覆盖整个点云。在每个采样空间中根据曲率大小使用概率算法保留或者剔除其中包含的点。图3 是使用小车模型生成若干个参考向量的示意图。参考向量选取可以通过算法自动生成，其数量因模型而异，详细算法在第3.6节介绍。

Fig.3 Reference vectors generated in car model图3 在小车模型中生成若干个参考向量

采样区域的大小与参考向量对应的四个阈值的大小成正比。当参考向量对应的四个阈值确定时，长度越大的参考向量生成的采样空间越大，这样会导致模型边界区域的采样空间压缩掉过量的点。因此需要建立阈值ΔAX、ΔAY、ΔAZ与向量长度L(V)的约束关系。使得参考向量长度变化时，形成的参考向量区域大小基本保持不变。

3.3 参考向量采样空间形状与阈值的关系

参考向量生成的采样空间形状取决于阈值。通常三个角度阈值取相同的值，用ΔA表示。ΔA影响采样区域坐标轴方向扩展的广度。ΔL影响采样区域向量方向拉伸的深度。ΔL、ΔA越大，采样空间体积越大；反之越小。ΔL增大ΔA减小，采样空间变长；ΔL减小ΔA增大，采样空间变扁。

图4（a）的阈值参数为ΔL=13，ΔA=1（大距离、大角度），整个空间的点都和向量相似，点云压缩变成了全局压缩。图4（b）的阈值参数为ΔL=0.1，ΔA=1（小距离、大角度），采样区域形成“洋葱”，即分层压缩的形式。图4（c）的阈值参数为ΔL=0.11，ΔAY=0.08，ΔAX=ΔAZ=0.5，压缩空间呈带状。图4（d）的阈值参数为ΔL=0.1，ΔA=0.05（大距离小角度），采样区域呈棒状。

Fig.4 Relation between shape of reference vector sampling space and threshold value图4 参考向量采样空间形状与阈值的关系

3.4 曲面信息的计算

本文使用最小二乘曲面拟合方法计算采样区域包含曲面的曲面方程[14]。使用式（9）计算采样区域曲面曲率值[15]。

三维模型点云表面划分为多个区域，每个区域的点云构成一个简单的曲面等值面，这些曲面等值面用一个简单的隐式二次方程近似表示。如下式：

用最小二乘拟合曲面法，用至少7 个曲面等值面中的点云坐标，求解线性方程组，得出曲面方程的6个系数，最终得到曲面等值面的二次隐式方程的近似表示。

曲面曲率反映曲面的弯曲程度。可通过计算曲面曲率来判断三维点云模型中曲面变化波动较大的区域，即特征区域。特征区域压缩时可采用较低的压缩率，或者不压缩，以保留模型的细节特征。使用下面的曲率计算式（7）、式（8）、式（9）和二次隐式曲面方程的6 个系数，可以计算该曲面的平均曲率Km、高斯曲率Kg、极大曲率Kmax。

计算曲面系数需要生成并求解六元一次非齐次方程组，该方程组各系数的计算需要累加曲面等值面的点云坐标求出。CVS 算法利用方程组系数计算需要累加的特点，每读入一个点可动态实时完成采样区域中已生成但不完整的等值面曲面方程与曲面曲率计算，并根据计算的曲面曲率的大小，设定曲率阈值动态实时调整各采样区域中点云压缩程度。如计算出的曲面曲率大于某个阈值，则降低点云压缩程度。当所有点云被读完，每个采样区域中的等值面曲面即生成完毕。记录最终生成的曲面方程以及坐标范围参数，形成点云复原信息文档，用来复原点云。

CVS 使用最小二乘法计算曲面方程。曲面方程的计算从采样空间集齐6 个坐标开始。根据文献[14]中的二次曲面拟合方法可知，6 个以上的曲面坐标可导出曲面方程系数为未知数的六元一次方程组，使用高斯消元解方程组即可得出曲面方程。曲面曲率极大值曲率可根据式（7）、式（8）、式（9）直接由曲面方程系数计算得出。

CVS 采用最小二乘法拟合二次曲面得出曲面方程，然后直接用曲面方程的6 个参数计算出曲面曲率极大值。因此曲率的计算准确度取决于拟合曲面的拟合效果。如果在采样区域内拟合的二次曲面能紧紧贴合到采样区域中散点组成的曲面，说明拟合效果较好，计算的曲率值较准确。而拟合效果取决于参考向量参数阈值的选取。调小参数阈值，可以降低参考向量采样区域中包含曲面的复杂程度，以提高该采样区域的曲面拟合效果。

3.5 CVS 参数阈值的设定与调整

由3.2 节可知，合理地选择参考向量采样空间使用的阈值可使稀疏区域选取的向量生成的采样空间所含点的密度较低，甚至不含点；稠密区域选取的向量生成的采样空间中，所含点的密度较高；使得在相同压缩概率下，稠密区域被剔除点的数目大于稀疏区域的剔除点的数目。在采样区域中可设置多级曲率阈值，以使曲率越高的曲面被剔除的点越少，甚至不剔除。

参数阈值的选取和三维模型本身的性质有关。目前参数的选取通过实验来设置。ΔA按照实验经验值其初始值一般设为0.03。这个阈值下生成的采样区域基本不会跨越模型多个曲面。ΔL初始值与模型点坐标值的数量级有关，其初始值设为模型中所有的坐标值中最低数量级的低一个数量级乘一。如三维模型中每一个坐标点的坐标值的数量级是10-1，则将ΔL设置为0.01。调低ΔA、ΔL可使得采样区域更小更精细，曲面采样越不容易跨越复杂曲面，从而保留更多复杂特征，但会增加采样区域个数，降低算法效率。反之，调高ΔA、ΔL会使得采样区域大而少，在提升算法效率的同时也会让特征保留效果变差。可以根据模型的形状特点适当调整采样区域使其变长或者变扁来调整压缩效果。根据CVS 中曲面信息计算方法计算各个采样区域的曲率并计算均值来选取曲率阈值初始值。ΔA与向量长度的反比关系可以采用反比例函数，如ΔA=factor/L(V)，其factor值由模型离原点最近点与原点连接生成向量的长度乘ΔA的初始值得到。

3.6 CVS 压缩算法

CVS 压缩算法如算法1 所示。CVS 压缩需要循环从文件中读入PS 中的三维坐标点，并将这些点转换为向量SP，查看这些向量是否属于已有的参考向量S的采样空间S.Samplespace。如果不属于任何采样空间，则将此向量归入采样空间数组REF，并生成采样空间，否则将向量归入其所属采样空间S.Samplespace。此方法可使得模型所有的坐标点要么被转化为参考向量，要么就归入其所属的参考向量采样空间中，实现自动选取一组参考向量并生成采样空间集合以覆盖整个模型区域的功能。在采样空间S.Samplespace 内计算当前采样点云生成的曲面等值面的曲面方程和曲率极大值，并统计各种复原信息S.Info。函数Adramrange 根据曲面曲率阈值调整随机数接受阈值R，并使用Proramvalue 函数产生随机数r。如果曲率的极大值超出了设定的曲率阈值的设定范围，说明该曲面曲率较大，属于复杂曲面，则降低该曲面的点压缩概率。需要保留的点会被写入压缩点云文件CPS。所有点读入并处理后，将每个采样空间的统计信息Ref.Rec.Info 输出到文件中形成复原信息文件Reci，最后将所有的参考向量Ref.Rec输出到压缩点云文件中，并在文件中做出标示。

算法1 CVS 压缩算法

由算法1 可知，压缩算法中存在双重循环。第一重循环用来遍历三维模型中的坐标。第二重循环用来为每个坐标查找其所属的采样空间。最坏情况下，每个坐标点都无法找到其所属的采样空间，即所有的坐标都被转换为参考向量。则读入n个坐标需要查找n2次采样空间，时间复杂度为O(n2)。曲面方程计算的高斯消元时间复杂度是O(n3)，CVS 中n为定值6，因此CVS 中高斯消元的时间复杂度为O(1)。CVS 每读入m个模型点，其所属的采样空间就会计算一次曲面方程，可知CVS 中曲面方程计算的时间复杂度为，即O(n)。由式（7）、式（8）、式（9）可看出，曲率计算可直接由曲面方程系数计算得出，其在CVS 中的时间复杂度为O(n)。因此CVS 压缩算法的复杂度是O(n2)。方程拟合和曲率的计算不影响CVS 压缩算法整体的时间复杂度。

4 CVS 点云复原算法

CVS 点云复原需要使用CVS 点云压缩阶段产生的复原信息数据。

4.1 CVS 点云复原算法原理

点云复原算法是点云压缩算法的逆过程。点云压缩算法剔除冗余点并存储曲面信息，点云复原算法利用曲面信息，生成符合曲面方程的坐标点添加到被简化的模型中。为了让点云复原算法达到最佳效果，要求点云压缩时每个采样区域不能跨越多个曲面，这可以通过调整点云压缩参数阈值，使得采样区域的曲面等值面光滑、规则。

点云复原信息在点云压缩阶段产生，包括点云压缩的4 个参数阈值、每个采样区域的压缩点云个数、拟合的曲面方程的6 个系数、曲面上点X坐标的最小最大值、曲面上点Y坐标的最小最大值、曲面上点Z坐标的最小最大值、采样区域两两向量之间长度差值绝对值最大值。点云复原以参考向量作为参照，完成点云复原。被标示出的参考向量连同复原信息中保存的各个参数阈值在点云压缩的时候记录和统计，点云压缩完成后，记录为文件并保存。

4.2 三维坐标点的产生和添加

C是一个点云添加器，S是某采样区域添加点云集合，有：

P是一个立方体点云产生器，设立方体点云集合为L，则有：

其中，XS、YS、ZS是X、Y、Z轴数值范围的下限，XE、YE、ZE是X、Y、Z轴数值范围的上限，SX、SY、SZ是X、Y、Z从下限增长到上限的步长。Select是一个点筛选器，Method是筛选方法。式（6）是计算曲面Z坐标的计算式。V(x,y,z)是三维坐标的转换器，该转换器将三维坐标转换为过原点的向量。设xi∈[XS,XE]，yi∈[YS,YE]，zi∈[ZS,ZE]，P会产生所有符合上述条件的(xi,yi,zi)∈L。且有：

使用一个点产生器P产生一个以曲面上点的X坐标变化范围数值为长，Y坐标变化范围为宽，Z坐标变化范围为高的一个实心立方体点云。该立方体点云可以完全包含被采样曲面中的所有点。Method通过复原信息中的曲面方程系数可以组建方程，并根据产生器中每个点的xi和yi，计算出对应的曲面Z坐标值zi，进而得曲面向量的长度。然后使用Select将曲面上计算出的向量长度和产生点对应的向量长度相减取绝对值，这个绝对值和向量长度变化区间max进行比较，1 表示留下，0 表示剔除。通过调整变化值的大小，可以实现添加点云层的厚薄控制。通过调整点产生器P中SX、SY、SZ步长大小，控制产生点云的疏密程度。

4.3 CVS 复原算法

CVS 复原算法由算法2 所示，函数Getvector 从压缩文件CPS 中读入参考向量或者普通向量P，如果P是参考向量则算法需要通过函数Getreinfo 从复原信息Reci 中读入与该参考向量相关的所有参数阈值P.Info，生成采样空间，否则将点输出到复原点云文件Rec。然后点云产生器Pointsgen 根据复原信息P.Info产生点云集合，根据采样空间中的曲面信息选取产生器中的点形成集合p，并输出到复原点云文件Rec中。所有的向量处理完后模型复原结束。

算法2 CVS 复原算法逻辑

5 实验分析

本章通过一组实验验证本文所提出的算法的压缩效果、压缩速度和复原效果。

实验环境：本文算法通过C 语言编程实现，实现平台为Intel®CoreTMi5-4670 CPU @3.4 GHz 处理器，4 GB 内存，1 TB 硬盘。使用软件Meshlab 建模。

实验模型数据：为了验证算法的有效性，本文使用斯坦福兔子模型、维纳斯模型、人头骨模型、龙模型、佛模型进行实验。兔子、维纳斯、人头骨模型数据量小，特征区域多且易辨别，容易显示算法压缩和复原效果。龙模型和佛模型数据量大，且表面复杂，可用于研究算法对于大数据量模型的压缩效率和效果。表1 是模型自身参数。

Table 1 Model information used in experiment表1 实验模型信息

5.1 实验设计

5.1.1 点云压缩实验

压缩实验数据和参数：点云压缩运行时间与模型文件数据量、压缩参数的设置有关。模型压缩时使用参数ΔA和向量长度关系ΔA=factor/L(V)。表2是五个模型在本文压缩算法中使用的参数表。ΔC代表曲率阈值，CP表示采样区域计算出的曲率值达到曲率阈值时的点保留概率，NCP表示采样区域计算出的曲率值未达到曲率阈值时点保留概率。

Table 2 Parameter table of five models used in CVS compresion in this paper表2 五个模型在本文压缩算法中使用的参数表

对比算法如下：

（1）PCL（point cloud library）开源点云库[16]中基于八叉树的区域重心点云降采样算法，简称PCL，该算法是常用的点云压缩算法，压缩时间短，效率高。

（2）K-means 点云压缩算法[12]，简称K-means，该算法使用基于K-means 聚类的方法判断特征区域，模型特征保留效果较好。

（3）本文的CVS 压缩算法。

压缩效果实验：分别用CVS、PCL 降采样、Kmeans 算法压缩斯坦福兔子模型、维纳斯模型、头骨模型、龙模型和佛模型的点云图，通过观察点云图中的点云密度分布和建模后模型的表面积变化来比较压缩效果。

压缩速度实验：分别用CVS、PCL 降采样、Kmeans 算法压缩斯坦福兔子模型、维纳斯模型、头骨模型的点云图，比较压缩时间。

5.1.2 点云压缩复原实验

点云压缩复原实验数据和参数：点云复原需要一定的条件才能够达到最佳效果，即采样区域未跨越多个曲面，且采样区域中的曲面不难拟合。因此算法中L3A 相似度中的四个阈值取值越大，越不利于点云的复原。因此压缩复原算法中三个模型的压缩率较低。在CVS 点云压缩和复原实验中，兔子、维纳斯、头骨模型的还原效果最为明显。Bunny和Skull模型压缩使用的角度阈值与向量长度关系是ΔA=factor/L(V)。Venus 压缩使用的关系是ΔA=factor/L(V)2。表3 列出了三个模型在CVS 压缩复原算法中使用的参数表。

Table 3 Parameter table of three models used in CVS compression and restoration表3 三个模型在CVS 压缩复原算法中使用的参数表

点云压缩复原效果实验：先使用CVS 压缩算法压缩斯坦福兔子模型、维纳斯模型、头骨模型。然后使用CVS 复原算法复原三个模型。通过观察压缩复原前后模型的点云密度分布以及根据建模后模型的表面积变化情况来比较点云复原效果。

5.2 算法效果分析

5.2.1 点云压缩实验结果分析

（1）CVS、K-means、PCL 压缩效果分析

图5 是斯坦福兔子模型、维纳斯模型、头骨模型的点云原图。图6 的（a）、（b）、（c）三列是兔子、维纳斯、头骨三个模型分别经CVS 压缩算法、PCL 降采样算法、K-means 算法压缩后的点云图。图7、图8 各自的（a）、（b）、（c）、（d）图分别是龙模型和佛模型的点云原图、经CVS 压缩算法、PCL 降采样算法、K-means 算法压缩后的点云图。表4 列出了各模型分别在三类压缩算法中压缩后的点数和压缩率。

Fig.5 Point cloud of Bunny,Venus and Skull图5 兔子、维纳斯、头骨模型点云原图

Fig.6 Point cloud of CVS,PCL and K-means compression algorithm experimental results图6 CVS、PCL、K-means压缩算法实验结果点云图

Fig.7 Point cloud of Dragon model compression experiment result图7 龙模型压缩实验结果点云图

Fig.8 Point cloud of Buddha model compression experiment result图8 佛模型压缩实验结果点云图

表4 列出了各模型在三类算法中的压缩率，说明算法对比是在两者压缩率相近的前提下进行。从图6 的斯坦福兔子模型点云分布可看出，CVS 和Kmeans 压缩产生的模型，在模型细节区域保留了较多的点，对应模型的细节显示更加明显。而PCL 降采样算法产生的大密度点云区域相对较少。从图6 的维纳斯模型点云分布图可以看出，CVS 和K-means 算法的大密度点区域集中在人物的面部，使得人物面部的细节更加明显。而PCL 降采样算法在人物面部的眉毛、嘴唇部位的点云密度较低，导致对应模型中的相应部位的建模不是很清晰。从人头骨点云分布图中可看出，CVS 和K-means 算法在人头骨模型的牙齿、额头图案、头上文字处等特征细节处保留了较多的点，所建模型相应细节显示效果增强。从图7 和图8 的复杂龙模型和佛模型的压缩效果来看，CVS 和Kmeans 在特征区域均保留了较多的点，而平缓区域点较少，但是不会使得平缓区域的点云过度稀疏。

Table 4 Compression ratio of each model in three types of algorithms表4 各模型在三类算法中的压缩率

表5 列出了三类压缩算法的表面积变化情况。PCL 压缩的模型表面积变化均比其余算法的变化大，说明本文压缩算法与K-means 算法对于模型的整体改变小于PCL 算法。且CVS 算法与K-means 的压缩效果相当。

Table 5 Change of surface area of each model in three types of algorithms表5 各模型在三类压缩算法中表面积变化

（2）CVS、K-means、PCL 压缩速度分析

表6 是各模型分别在三个压缩算法下的压缩用时。可以看出，在相同压缩率下，PCL 降采样处理时间最短，K-means 最长，CVS 介于两者之间。PCL 降采样对于点云的处理较为简单，它只将每个网格中的点云用这些点云的重心替代，故处理时间短，但是特征保留效果差。K-means 算法包含了聚类算法以及多重特征点判断方法，虽然特征保留效果好，但是随着点云数据量和模型复杂度的增加，特征提取聚类中心个数以及聚类的样本数目也增加，使得算法的时间复杂度显著增加，不适合用于大数据量的点云数据的处理。CVS 压缩算法在小数据量和大数据量的处理中均使用了较少的时间，而且还保证了与K-means算法相近的特征保留效果。

Table 6 Compression time of each model in three types of algorithms表6 各模型在三类压缩算法中压缩用时

5.2.2 点云压缩复原实验结果分析

图9、图10 分别是三个模型在CVS 压缩复原算法下的实验结果建模图和点云图，第一行是斯坦福兔子模型，第二行是维纳斯模型，第三行是头骨模型。

Fig.9 Model of CVS compression and restoration algorithm图9 CVS 压缩复原算法模型图

Fig.10 Point cloud of CVS compression and restoration algorithm图10 CVS 压缩复原算法点云图

表7 提供了本实验中模型的压缩程度以及模型复原时添加的点的数目。图10 的斯坦福兔子点云分布说明，点云复原后，复原模型的点云分布基本与原模型相当，模型细节有了大幅度的恢复，尤其是兔子耳朵部分与原模型相差无几。从图10 的维纳斯点云分布图可以看出，复原模型成功填补了压缩模型中密度小的点云区域，如嘴部，使得相应部位的细节更加明显细腻。图10 的人头骨图点云分布图表明复原算法成功复原增加了模型细节部分以及大量平坦部分区域的点的密度。从图11 人头骨建模图可看出，人头骨额头的图案有了明显恢复。表8 的数据表明了复原后的模型表面积变化率变小，说明复原算法对模型表面积的恢复起到了一定的作用。

Table 7 Point numbers of three models in CVS compression and restoration表7 三个模型在CVS 算法中的压缩复原点数

Fig.11 Enlarged detail of CVS compressed and restored skull model图11 CVS 压缩和复原头骨模型的细节放大图

Table 8 Model change in surface area in CVS compression and restoration表8 模型在CVS 压缩复原算法中表面积变化

由以上实验结果可以得出，CVS 算法通过调整阈值，可以生成覆盖整个模型点云的采样空间，使得点云稀疏的区域中，参考向量包含的点云较少，甚至不包含点云，而点云稠密的区域的参考向量包含较多的点云，然后根据点云疏密程度进行点云压缩。而且CVS 在采样空间中，根据曲率大小决定剔除的点云比率，实现模型平缓稠密区域的点云精简，稀疏区域的点云保留，复杂稠密部位的点云低压缩率，尽可能保留模型的细节特征。CVS 压缩是在原模型的基础上减少点云个数，不会从整体上修改模型点云的坐标，不会较大程度改变模型的整体形态。在CVS点云复原阶段，可根据复原信息生成贴合模型外表的点云，恢复并增强模型的细节特征。

6 结束语

本文提出了一种新的向量间相似度L3A，并提出了使用该向量相似度实现点云模型压缩复原的CVS算法。该算法能够通过调节参数使得点云的压缩和复原达到一个较好的效果。CVS 能够很好地保留模型细节特征，有效地去除冗余点，且能使得点云密度较为稀疏的区域不会被过度压缩而产生孔洞。通过三个模型的实验结果和与PCL 点云库使用的降采样算法和K-means 点云压缩算法进行对比分析，表明本文压缩算法不但可以保留模型特征信息，还能尽量减少模型的表面积变化，压缩时间短，适合处理大数据量的点云模型。CVS 点云复原也能有效恢复大量模型细节，使得点云模型更精细。