基于局部熵的点云精简算法

董嘉敏 田华

摘  要： 针对目前流行的三维物体激光扫描仪获取的点云数据量大，冗余度高等问题，提出一种基于信息熵的点云精简算法。首先，定义数据点的曲率、点到邻域点重心的距离、点到邻域点的平均距离的倒数，三者乘积为权值积;然后，使用K?means聚类算法划分点云数据，根据类内估计曲率差值区分特征区域与非特征区域;最后，针对特征区域，利用提出的精简方法精简点云。实验结果表明，该方法计算相对简单，能够有效避免孔洞现象，同时，更好地保留了点云数据的原始物理特征。

关键词： 点云精简; 信息熵; K?means算法; 特征区域区分; 点云数据; 曲率估计

中图分类号： TN911?34; TP391.9                   文献标识码： A                    文章编号： 1004?373X（2020）01?0020?04

A point cloud reduction algorithm based on local entropy

DONG Jiamin， TIAN Hua

Abstract： A point cloud reduction algorithm based on information entropy is proposed to deal with the large amount of point cloud data and high redundancy produced by the popular three?dimensional laser scanner. Firstly， the product of curvature of the data points， the distance from the points to the center of gravity of the neighborhood points， and the reciprocal of the average distance from the points to the neighborhood points is defined as the product of weight; secondly， the K?means clustering algorithm is used to classify the point cloud data， and the characteristic region and the non?characteristic region are distinguished according to the estimated curvature difference; finally， for the characteristic region， the proposed reduction algorithm is used to reduce the point cloud. The experimental results show that the calculation process of the proposed algorithm is relatively simple， which can effectively avoid the hole phenomenon， and preserve the original physical characteristics of the point cloud data better.

Keywords： point cloud reduction; information entropy; K?means algorithm; characteristic region distinction; point cloud data; curvature estimation

0  引  言

三维重建技术一直是计算机视觉、逆向工程学和计算机图形学等热门研究领域的研究重点[1]。关于点云技术三维重建，已经有不少的研究工作和成果[2?3]。随着FreeScanX3等三維物体激光扫描仪不断推陈出新，点云数据的获得变得更加方便，同时点云数据的精度也非常高。然而，如此密集的点云数据中却存在着大量的冗余数据，这些冗余数据极大地增加了点云数据的存储开销和计算开销，从而影响到曲面拟合和模型生成等重要后续工作的效率。综上所述，点云数据的精简工作对于物体的三维重建和绘制工作是非常重要的[4]。

近年来，许多学者对点云精简的研究做出了贡献并取得了很大的成功。根据对点云数据精简的原则，现有的点云精简方法可以分为两类：基于网格的简化和基于点的简化。基于网格的简化方法主要通过构造多边形网格（三角形网格或四边形网格），依据一些规则来判定这些网格的重要性，删除冗余网格的边来实现精简。这些方法的不足之处在于网格的生成需要花费大量的时间和存储。相比较这类方法而言，基于点的简化方法直接对点云数据进行精简而不用构建任何网格。文献[5]采用K均值聚类算法在空间域中将相似点聚集在一起，并使用最大法向量偏差作为聚类分散的度量，将聚集的点集划分为特征域中的一系列子聚类，提出一种新的划分和细分方法，实现对点云的精简;文献[6]针对散乱点云简化中易丢失几何特征及潜在曲面形状信息的问题，采用基于泊松分布的区域生长法自适应检测特征点，通过设定不同的聚类阈值，运用不同的简化策略简化点云数据;文献[7]运用多判别参数混合的方法首先识别特征点并保留，然后对剩余点云数据K?means聚类，根据类内最大曲率差作为细分标准，最终完成特征保持的点云数据精简。

这些不同的基于点的简化方法有一个共同点，就是先评估点云数据中每个点的重要性，通过删除不重要的点完成点云数据的精简，因此评估参数就显得尤为重要。本文提出一种基于信息熵的点云精简算法，针对以往最小二乘法拟合曲面计算曲率过于复杂耗时，提出一种新的曲率估计方法，并定义数据点的曲率、点到邻域点重心的距离、点到邻域点的平均距离的倒数，三者乘积为权值积，以权值积衡量点的重要性，降低曲率估计误差影响，然后结合K?means聚类算法和权值积的信息熵保留特征点，完成点云数据的精简。

1  权值积的计算

定义曲率[H]、点到邻域点重心的距离[S]、点到邻域点的平均距离的倒数[1A]的乘积为权值积[w]，即：

[w=H?S?1A] （1）

式中：[1A]与[S]可通过欧氏距离的简单计算获得，此处不再赘述。

众所周知，曲率是曲面的基本信息，反映曲面的局部几何特征。因此根据曲率的大小可以反映面的弯曲程度。在三维欧氏空间中，一般使用高斯曲率来反映某点的弯曲程度。一般实现方法是将此点和邻域内的点拟合成曲面，再求取曲面的主曲率和高斯曲率。设[P]点为点云中的一点，使用K?D树算法寻得[P]点的8近邻[（P1，P2，…，P8）]。

1.1  传统最小二乘法求解曲率[8]

建立二次曲面的参数方程：

[ru，v=i，j=02qijuivj] （2）

令：

[  a=[a00 a01 a02 a10 a11 a12 a20 a21 a22]  b=[b00  b01  b02  b10  b11  b12  b20  b21  b22]  c=[c00  c01  c02  c10  c11  c12  c20  c21  c22]  l=[u0v0  u0v1  u0v2  u1v0  u1v1  u1v2  u2v0  u2v1  u2v2]  Q=[a  b  c]] （3）

式（2）可改写为：

[r（u，v）=[x（u，v）y（u，v）z（u，v）]=[lTalTblTc]=lTQ]   （4）

引入两个矩阵：

[B=x0y0z0x1?y1?z1?xkykzk，       l=lT0lT1?lTk] （5）

待测点[P]的坐标为[（x0，y0，z0）]，这里[k=8]。逼近曲面和数据点的误差函数为：

[Ω=lQ-B]   （6）

运用最小二乘法，推导出系数矩阵[Q]为：

[Q=（lTl）-1lTB] （7）

从而求出曲面[r（u，v）]的偏导数[ru]，[rv]，[ruu]，[ruv]，[rvv]，曲面的单位法矢[n]为：

[n=ru×rvru×rv] （8）

曲面的第1、第2基本量为：

[E=r2u，F=rurv，G=r2，L=nruu，M=nruv，N=nrvv] （9）

求出高斯曲率[K]和平均曲率[H]为：

[K=LN×l2EG-F2，    H=LG-2MF+NE2（EG-F2）] （10）

由于三维扫描的数据量往往很大，因此对每个点拟合曲面将会耗费大量的内存和时间，所以本文根据点云间的三角拓扑关系提出一种新的曲率估计方法。

1.2  新的曲率估计方法

如图2所示，首先找到待测点[P]的8近邻[P1～P8]，根据这9个点最小二乘拟合确定平面[S]，向量[α]表示平面[S]的法向量。估计曲率的计算过程如下：

1） 首先连接[P]与其余8个点，分别得到向量：[PP1]，[PP2]，[PP3]，[PP4]，[PP5]，[PP6]，[PP7]和[PP8]。

2） 向量[α]与向量[PP1]的余弦值为：

[cosθ1=α×PP1α·PP1]  （11）

圖1中，实心点为待测点，空心点为邻近点。角[θ]的余弦值的大小反映了两个向量夹角的大小，由图1可知，待测点附近的凹凸情况可由余弦值的绝对值来说明，若余弦值的绝对值越大，说明两向量的夹角越大或越小，而这两种情况都说明[P]点附近的曲面凹凸程度越大，是特征区域。根据式（11），同样可得[cos θ2]，[cos θ3]，[cosθ4]，[cos θ5]，[cos θ6]，[cos θ7]和[cos θ8]。令曲率估计值为：

[H=i=18cos θi] （12）

[H]的大小反映了点云数据在待测点[P]附近的凹凸程度。[H]越大，表明在[P]点附近凹凸程度越大，[H]越小表示在[P]点附近的凹凸程度越小。权值积的另两个参数，[S]越大说明[P]点附近几何特征越明显;[1A]越大说明[P]点附近点云密度较为稀疏，应该保存较多的点以保护原始点云特征。

完整的待测点曲率估计示意图如图2所示。

2  本文算法

2.1  K?means聚类算法

K?means聚类算法是典型的基于欧氏距离的聚类算法。在点云的分割过程中，能够保持稳定和快速的优点。若原始点集是位于[N]维空间中的点集，表示为[Pi]，[i∈{1，2，…，m}]。首先找到[K]个聚类中心[{C1，C2，…，Ck}]，然后通过迭代计算移动[K]个聚类中心，最终使得[D]值最小：

[D=argmini=1kj=1uPj-Ci] （13）

式中：[u]表示以[Ci]为聚类中心的簇中的点的个数;[Pj]表示属于以[Ci]为聚类中心的簇中的点。由于[K?D]树方法的特殊性，点云依照[K?D]树划分后会非常均匀，即可以由[K?D]树的叶节点决定聚类重心，该算法计算过程如下：

1） 选定聚类[K]值的大小，[K?D]树划分点云数据，直到叶节点的数目最接近[K]时，初始的聚类中心选择[K?D]树的叶节点;

2） 根据点到聚类中心的欧氏距离将点云划分为[K]个簇;

3） 計算各个簇的重心代替原来簇中心;

4） 按照新的聚类中心重新聚类;

5） 重复步骤3）和步骤4），直到簇的中心不再发生变化，得到[K]个簇。

2.2  信息熵理论

信息熵是一种非常重要的系统科学理论，是系统的一个状态函数，其含义非常丰富，最初由著名科学家香农（Shannon）于1948年在其《A Mathematical Theory of Communication》一文中提出，又称为Shannon熵，用来度量通信中的不确定性和信息量。Shannon给出了信息熵的定量表述[9]：

[H（X）=-Ki=1nPilog Pi]  （14）

式中：[K]为某个固定正常数;[Pi]是事件[Xi]出现的概率，满足条件[0≤Pi（i=1，2，…，n）]和[i=1nPi=1]。

根据信息熵理论，本文将信息熵引入点云精简算法之中，在数据点权值积的特征表达上，信息熵理论可用于将某一数据点权值积表征为对某类特征的隶属程度。对于点云中一点[P]，它的信息熵可由下式计算：

[I（P）=-Pwlog Pw-i=1kPwi]  （15）

其中：

[Pw=ww+i=1kwi，  Pwi=wiw+i=1kwi] （16）

式中：[Pw]是点[P]的权值积概率;[Pwi]是第[i]个相邻点的权值积概率。较大[I（P）]值意味着该点位于凹陷和凸起明显变化的区域中，如果移除此点，则局部几何图形将发生变化，因此应该保留信息熵较大值的点云数据。

2.3  保持特征的精简算法流程

设聚类后得到[n]个簇（[S1]～[Sn]），针对每一个簇[Si]，给定权值[λ]用来定义点云特征保持度，将权值积之差与[λ]比较，若[λ]越小则特征保持效果越好，[λ]越大则特征保持越小但精简程度更高。算法步骤流程如图3所示，具体步骤如下：

1） 计算簇中每个点的权值积[wi]，其中，估计曲率最大值为[Hmax]，最小值为[Hmin];

2） 若簇中[Hmax-Hmin<λ]，则认为此簇处于比较平坦的区域，即用簇中心代替此簇;

3） 若簇中[Hmax-Hmin>λ]，则判断此簇为特征区域，计算此簇中各点权值积的信息熵，求得平均值，信息熵大于平均值的点予以保留。

通过以上算法即可实现对点云数据的精简，相对平滑区域，使用簇中心替代整个簇，不会造成几何特征的明显变化;特征区域由于使用信息熵值来衡量点的重要性，保留了最重要的点，因此保留了原始点云的几何特征。

3  实验结果及分析

本文使用Matlab对算法进行实现。实验用到的点云数据为斯坦福大学建立的3D点云数据库中的斯坦福兔子Buuny和Dragon点云数据模型，格式均为PLY。本文算法有两个变量需要自行确定，初始聚类数目[k]和权值[λ]。本次实验取初始聚类数[k]为2 048，[λ]分别取0.6，0.1。

图4所示为原始点云由Matlab的呈现结果，其中图4a）为Buuny模型，共有35 947个点，图4b）为有10 248个点的Dragon模型。为了对点云原始数据和精简后数据进行定量分析，本文采用Geomagic Studio软件实现对点云数据的重构[10]，依此衡量精简结果的优劣。图5为原始点云数据的重构结果。

图6a）和图7a）为[λ=]0.1时的精简结果，图6b）和图7b）为[λ=]0.6时的精简结果。Buuny模型精简后点的个数为7 271，3 571，Dragon模型精简后点的个数为177 416，8 654。

精简后的模型重建结果如图8所示。与原始模型进行比较，在[λ=]0.1时可以较好地保留其特征信息;在[λ=]0.6时，由于精简度过高，会丢失部分特征信息。

4  结  语

针对最小二乘法拟合曲面计算数据点曲率过于复杂和费时，本文提出一种新的点云数据点曲率估计方法，并将信息熵的理论引入点云精简的过程中，更好地保留了特征点。经过实验证明，该算法精简效果较好，保留了原始数据的基本几何特征，精简后的点云数据用于重建，效果良好。

注：本文通讯作者为田华。

参考文献

[1] THANOU D， CHOU P A， FROSSARD P. Graph?based compression of dynamic 3D point cloud sequences [J]. IEEE tran?sactions on image processing， 2016， 25（4）： 1765?1778.

[2] M BERGER， A TAGLIASACCHI， L SEVERSKY， et al. State of the art in surface reconstruction from point cloud [J]. Eurographics star reports， 2014， 1（1）： 161?185.

[3] NAGAI Y， OHTAKE Y， SUZUKI H， et al. Tomographic surface reconstruction from point cloud [J]. Computers & graphics， 2015， 46： 55?63.

[4] SANCHEZ G， LEAL E， LEAL N. A linear programming approach for 3D point cloud simplification [J]. Iaeng international journal of computer science， 2017， 44（1）： 60?67.

[5] SHI B Q， LIANG J， LIU Q. Adaptive simplification of point cloud using k?means clustering [J]. Computer?aided design， 2011， 43（8）： 910?922.

[6] ZHANG Y， GENG G， WEI X， et al. A statistical approach for extraction of feature lines from point clouds [J]. Computers & graphics， 2016， 56： 31?45.

[7] 陈龙，蔡勇，张建生.自适应K?means聚类的散乱点云精简[J].中国图象图形学报，2017，22（8）：1089?1097.

[8] 周煜，张万兵，杜发荣，等.散乱点云数据的曲率精简算法[J].北京理工大学学报，2010，30（7）：785?789.

[9] 姜茸，廖鸿志，杨明.信息熵在软件领域中的应用研究现状[J].自动化技术与应用，2015，34（4）：1?6.

[10] 郭培闪，杜黎明.运用Geomagic Studio实现点云数据的曲面重建及误差分析[J].地理信息世界，2015，22（1）：57?60.

作者简介：董嘉敏（1993—），男，山西运城人，硕士研究生，研究方向为虚拟现实。

田  华（1983—），女，山西晋城人，博士，硕士生导师，主要研究方向为计算材料。