基于主成分分析与栅格划分的点云压缩算法研究∗

付忠敏 张 星 孙志刚

（华中科技大学自动化学院 武汉 430074）

基于主成分分析与栅格划分的点云压缩算法研究∗

付忠敏 张 星 孙志刚

（华中科技大学自动化学院 武汉 430074）

三维激光扫描仪可在短时间内通过非接触测量获得大量高度密集的点云数据，针对大量数据导致的资源占用多和数据处理速度慢的问题，提出了一种基于主成分分析和空间栅格划分的点云压缩算法；该算法通过对邻域点集作主成分分析建立点的局部特征描述子，对点云空间进行栅格划分，在栅格内依据点的局部特征描述子确立特征点，剔除非特征点；实验结果表明，该算法能在保持原有模型局部细节特征的同时较大程度地压缩点云数据。

点云压缩；主成分分析；栅格划分；局部特征；特征点

1 引言

三维激光扫描技术由于其非接触性、高精度、实时性强等优点正越来越广泛的应用于空间场景信息的获取中，但是，它在短时间内通过扫描获取到的大量包含物体表面细节特征的点云数据也给后续的数据存储、处理、显示和输出带来不便［1］。动辄十几万甚至上百万的点云数据不仅会占用大量系统资源，而且还会影响特征点识别与表面重建等后续工作［2］。因此，在保持原始点云必要细节特征的前提下，对点云数据进行压缩简化显得非常必要。

文献［4］阐述了将点云空间划分为均匀大小的小包围盒，取其中心点来代替整个包围盒中点的压缩方法，简单高效。但没有考虑局部特征，容易造成细节丢失。文献［5］提出了均匀网格法，将点云数据投影到平面上已经建立好的均匀网格中，取中值点来代替所有点。这种方法同样会造成细节的丢失，仅适用于点分布均匀且表面特征变化不大的点云数据。文献［6］针对传统方法在压缩点云数据时经常丢失过多特征点的不足，提出了基于K近邻和法向精度的点云精简算法，该算法能在不丢失细节特征的同时精简点云，但运算量大，并且不适用于表面特征变化不大的普通点云数据。

本文提出了基于主成分分析与栅格划分的点云压缩算法，算法首先对输入的点云数据建立邻域索引，通过主成分分析计算点的局部特征描述子，再将点云空间划分为均匀栅格，对栅格内的点进行压缩时，以点的局部特征描述子建立判断准则，提取特征点，舍弃非特征点。

2 点云压缩算法设计

2.1 主成分分析的原理

主成分分析（Principal Component Analysis，PCA）也称主元分析，是一种数据分析技术，其最重要的应用是对原有的复杂数据降维［7］，揭示隐藏在复杂数据背后的简单结构。它的优点是简单，而且无参数限制，可以方便的应用于各个场合。这种数据分析方法能够找到原始数据中最主要的成分和结构，去除噪声和冗余。从线性代数的角度来看，主成分分析其实就是寻找另外一组正交基来重新描述数据，使得在新的一组基下，数据在各个观测方向上的变化趋势能够更明显的呈现，数据沿着哪个观测方向沿的运动最剧烈即方差最大，这个观测方向就是最重要的“主元”。

三维激光扫描仪采集到的点一般分布在物体的表面，每个点需要用三个维度值来描述。物体表面越平滑，扫描点的分布越趋向于二维平面，采用主成分分析后，点沿表面法矢方向的变化越小；物体表面形态越复杂，变化越剧烈，点在三个维度方向上的变化越均匀即点越趋向于在三维空间中均匀分布。若样本点都分布在物体形态大小变化明显的位置，则样本数据沿空间三个维度方向的变化剧烈程度相当，即方差差别很小。

点云只涉及三维空间，有三个观测方向，为了对点云作主成分分析，先要计算得到邻域点集的协方差矩阵 C3×3。样本点集 P=(p1，p2，…，pk)T，其中 pi=(xi， yi， zi)T，则

协方差矩阵包含了所有观测变量之间的相关性度量，这些相关性度量反映了数据的噪音和冗余的程度。PCA指出样本的协方差矩阵的特征值对应各主成分的方差大小，特征向量就是样本分布变化最剧烈的那些方向。

2.2 点云局部特征描述

原始点云数据是往往是散乱的，数据点之间的拓扑结构是未知的［8］。对一个点的主成分分析是基于其邻域进行的，目前，最常用的点云数据拓扑结构分别是k邻域以及r邻域，如图1所示。三维点云数据集 P={pi∈R3，i=1，2，…，n} ，点 pi的 k邻域为点云数据集P中距离 pi最近的k个点的集合，r邻域为点云数据集P中与 pi的距离小于r的所有点的集合。使用八叉树和k-d树这样特殊的数据结构对点云作划分，可以加快邻域搜索速度［9］。

图1 k邻域与r邻域

为了建立点云局部特征描述量纲，取一个点的邻域点集作主成分分析，距离目标点更近的点显然对其局部特征有更大的影响，因此算法中使用加权协方差矩阵。对于任意点 p=(x，y，z)T，其邻域点集为 P=(p1，p2，…，pk)T，定义点 p 的加权协方差矩阵如下：

式（3）中di表示邻域点集P中点 pi到目标点的距离，dˉ表示点集P中所有点到目标点距离的均值。矩阵C3×3的三个特征向量构成了线性变换后三维空间中新的坐标基，其对应的特征值从小到大依次是 λ0，λ1，λ2。定义目标点的局部特征描述子LFD（Local Feature Descriptor）：

C3×3是实对待矩阵，所以三个特征值都为正实数，则 LFD∈。以LFD为一个点的局部特征描述量纲，LFD值越小，表示该点所在的局部区域在三维空间的一个观测方向上变化很小，即区域越趋向于二维平面；LFD越大，表示该点所属局部区域形态特征变化越明显，一般是物体的边缘部分或者表面出现凹凸变化处或者多个物体的交汇处。

综合以上阐述，对点云作主成分分析建立其局部特征描述量纲的步骤如下：

1）对目标点搜索其邻域点集，k为邻域内点的个数，计算所有邻域点到目标点的距离及其均值；

2）根据式（2）、（3）、（4）得到3×3加权协方差矩阵；

3）求解加权协方差矩阵的特征值，根据式（5）计算目标点的LFD。

2.3 栅格划分

在进行点云压缩时，为了最大程度的保存原始点云中的局部特征，压缩处理并不是针对点云整体，而是针对小的空间栅格［11］。先将点云空间划分为小的栅格，对栅格内的点作压缩处理后，再将其合并为一个总体，因此栅格划分是点云数据压缩的重要一环。一种较好的空间栅格划分方法是将点云所在空间划分为许多体积相等的立体栅格，设立体栅格的长宽高依次为L、W、H。首先求出原始点云各点坐标中沿xyz三个方向的最小最大坐标值：xmin、xmax、ymin、ymax、zmin、zmax，为了让这些小的立体栅格的形状与整体点云空间包围盒的形状一致，需要确定三个方向上合理的划分间隔值，使原始点云模型沿空间三个坐标方向上划分的网格数目相等，L、W、H需满足式（6）。

式（7）中floor表示向下取整，点云模型所在空间根据式（7）被划分为div_x*div_y*div_z个小的栅格。假设点云中某一点的坐标是(x，y，z)，计算其所在空间栅格的三维索引值(Ix、Iy、Iz)

为了方便栅格的快速查找，可将空间栅格线性排列［10］，如图2 所示。根据 Ix，Iy，Iz计算出栅格索引值：

根据式（9）计算所有点的栅格索引值，点云中栅格索引值相同的点都处于同一个栅格中。这种栅格划分方法形式简单有效，而且计算复杂度低。

图2 空间栅格一维线性排列

2.4 点的提取和算法流程

点云压缩的目的是希望能在降低点的数目的同时仍然能够保留大部分的物体表面特征信息［12］。用更少的点的去展示物体表面特征信息意味着保留下的点必须比舍弃的点更有“代表性”。本文定义保留下来的点为特征点，判定一个点是否是特征点需要用到前面提出的点的局部特征描述子——LFD这个量纲。LFD越大的点，其局部特征越明显，比其他点更具“代表性”。因此，在进行数据压缩时，希望在点云LFD较大的区域也就是物体表面形态起伏比较大的地方保留较多的点，以更好地表达被扫描物体在该处的细节信息，而在点云LFD较小的区域也就是相对较平坦的地方保留较少的点，这样就可以在对点云数据进行压缩的同时最大限度地保留物体的表面特征信息。

在对栅格内的点进行压缩时，需要建立一个判断标准确定哪些点是需要保留的特征点。假设点云所有点LFD的均值是avg_LFD，栅格内的点个数为n，栅格内所有点LFD的均值grid_avg_LFD。本文取grid_avg_LFD作为整个栅格所表示的区域局部特征是否明显的度量，以avg_LFD作为阈值，若grid_avg_LFD≥avg_LFD，则认为整个栅格内的点都是特征点，全部保留；反之，计算一个压缩率CR，将栅格内的n个点按LFD大小递减排列，仅将前n*CR个点视为特征点予以保留。

由上述判断标准可知，栅格压缩率CR由点的LFD确定，二者之间存在函数关系CR=ψ(LFD)，该函数必须单调递增，在LFD增大时，CR也增大，并且随着LFD的增大，CR增大的趋势要逐渐放缓。即ψ(LFD)的导函数要单调递减。一个可以使用的压缩率公式如下：

综合以上，点云压缩算法的流程如图3所示。

结合以上流程图，下面给出使用主成分分析与栅格划分的方法进行点云压缩的程序步骤：

1）读入原始点云，建立k-d树或八叉树空间索引以加快点的邻域查找；

2）遍历点云中的所有点，选取点的一种邻域计算加权协方差矩阵，计算LFD的值并计算全局LFD均值；

3）将点云空间划分为N个均匀栅格，计算点的栅格索引值确定其所属的栅格；

4）遍历所有栅格，计算栅格内点的LFD均值，结合压缩率公式计算栅格压缩率，确定栅格内需要保留的特征点数目；

5）将所有保留下来的特征点添加到新点云中即为压缩后点云。

图3 点云压缩算法流程图

3 算法实例与实验分析

本文实验的软件环境为：Windows7 64位操作系统，Visual Studio2013集成开发环境。点云文件的输入输出使用了PCL库，矩阵运算采用Eiggen库中的API，点的邻域使用K邻域，并且K=30。

实验结果如图4所示，图（a）是原始的sofa点云，有82368个点，图（b）是压缩后的sofa点云，可以明显看出原始点云中沙发的边界轮廓、玩具娃娃、毛毯这些细节特征在压缩后点云中保存完好，而较平坦的地方保留的点较少。图（c）是原始的table点云，有156892个点，图（d）是压缩后的table点云，可以明显看出压缩后点云中桌面边缘轮廓、杯子等局部特征明显的地方保留了较多的点，而平坦的桌面上保留了很少的点。

实验中，分别计算并记录原始点云与压缩后点云中所有点的LFD数据并绘制直方图，图5是原始点云与压缩后点云LFD的分布直方图对比。图（a）是原始sofa点云的LFD分布直方图，图（b）是压缩后sofa点云的LFD分布直方图。图（c）是原始table点云的LFD分布直方图，图（d）是压缩后table点云的LFD分布直方图。各直方图中的直线指示全局LFD均值的位置。

图4 原始点云与压缩后点云对比

由图5中（a）与（b）两图的对比可知，压缩前LFD值小于全局均值的点占比极大，直方图两端相差很大。压缩后左侧LFD较小的点明显减少，这表示压缩过程舍弃了sofa点云中大量分布在坐垫与垫上的局部特征单一的点。压缩后LFD均值线右移，即LFD均值变大。（c）与（d）两图的对比结果亦表明，压缩后直方图变得更加平缓，原始点云中LFD值偏小的点大幅减少，LFD值大的点被保留，这表示压缩过程舍弃了table点云中大量分布在平坦桌面上的点。压缩前后的数据分析结果表明，本文提出的点云压缩原则通过算法得到了实现，局部特征明显的点被保留，局部特征单一的点被舍弃。

图5 原始点云与压缩后点云LFD的分布直方图对比

对两幅点云压缩前后的各项统计数据的记录如表1。

表1 点云压缩前后各项统计数据对比

4 结语

本文针对传统点云压缩算法在压缩数据的同时不能较好地保留细节特征的问题，提出了基于主成分分析和栅格划分的点云压缩算法。首先对原始点云作主成分分析建立点的局部特征描述，再将点云空间划分为立体栅格，计算栅格压缩率，保留特征点，最后将数据压缩后的栅格合并为一个整体得到压缩后点云。实验结果表明，本文提出的算法既能较大程度压缩点云数据，又不会丢失扫描物体的表面轮廓特征，算法简洁、效率高，适用于有较多形态变化的三维点云数据。

［1］邢正全，邓喀中，薛继群.基于栅格划分和法向量估计的点云数据压缩［J］.测绘通报，2012（7）：50-51.XING Zhengquan，DENG Kazhong，XUE Jiqun.Point Cloud Data Compression Based on Grid Division and Nor⁃mal Vector Estimation［J］.Bulletin of Surveying and Map⁃ping，2012（7）：50-51.

［2］解则晓，徐尚.三维点云数据拼接中ICP及其改进算法综述［J］.中国海洋大学学报，2010，40（1）：99-100.XIE Zexiao，XUE Shang.A Survey on the ICP Algorithm and Its Variants in Registration of 3D Point Clouds［J］.Journal of Ocean University of China，2010，40（1）：99-100.

［3］张会霞，朱文博.三维激光扫描数据处理理论及应用［M］.北京：电子工业出版社，2012：27-31.ZHANG Huixia，ZHU Wenbo.Theory and Application of 3D Laser Scanning Data Processing［M］.Beijing：Publish⁃ing House of Electronics Industry，2012：27-31.

［4］K.H.Lee，H.Woo and T.Suk.Data Reduction Methods for Reverse Engineering［J］.Int J Adv Manuf Technol），2001，17：735-743

［5］Sun W，Bradley C，Zhang YF，Loh HT.Cloud data model⁃ing employing a unified，non-redundant triangular mesh［J］.Comput-Aided Design，2001，33（1）：83-93.

［6］Masuda T，Yokoya N.A robust method for registration and segmentation of multiple range images［C］//Quebec City，Canada：Proceeding of the 3rd International Conference on 3D Digital Imaging and Modeling，2001：254-261.

［7］张鹏.基于主成分分析的综合评价研究［D］.南京：南京理工大学，2004：5-7.ZHANG Peng.Research on Comprehensive Evaluation Based on Principal Component Analysis［D］.Nanjing：Nanjing University of Science and Technology，2004：5-7.

［8］张顺岚，莫建文，邹路路.基于K近邻和法向精度的点云精简算法［J］.武汉理工大学学报，2014，38（3）：572-575.ZHANG Shunlan，MO Jianwen，ZHOU Lulu.Point Cloud Simplification Algorithm Based on K Neighbor and Normal Accuracy［J］.Journal of Wuhan University of Technology，2014，38（3）：572-575.

［9］王振，孙志刚.散乱点云噪声分析与降噪方法研究［J］.计算机与数字工程，2015，43（9）：1668-1672.WANG Zhen，SUN Zhigang.Denoising Methods Research on Scattered Point Cloud Based on Noise Analysis［J］.Computerand DigitalEnineering，2015，43 （9） ：1668-1672.

［10］徐翰.基于空间网格划分的点云质量检测算法［J］.东华理工大学学报（自然科学版），2015，38（1）：88-90.XU Han.A Point Cloud Quality Detection Algorithm Based on Spatial Meshing［J］.Jounal of East China Insti⁃tute of Technology（Natural Science），2015，38（1）：88-90.

［11］周波，陈银刚，顾泽元.基于八叉树网格的点云数据精简方法研究［J］.现代制程工程，2008（3）：64-67.ZHOU Bo，CHEN Yingang，GU Zeyuan.Research of Point Cloud Data Reduction Based on Octree Grid［J］.Modern Manufacturing Engineering，2008（3）：64-67.

［12］刘涛，徐铮，沙成梅，等.基于包围盒法的散乱点云数据的曲率精简［J］.科学技术与工程，2009，9（12）：3333-3335.LIU Tao，XU Zheng，SHA Chengmei，et al.Curvature Es⁃timation of Scattered Point Cloud Data Based on Bound⁃ing Box Method［J］.Science Technology and Engineer⁃ing，2009，9（12）：3333-3335.

Research on the Algorithm of Point Cloud Compression Based on Principal Component Analysis and Grid Divison

FU Zhongmin ZHANG XingSUN Zhigang
（School of Automation，Huazhong University of Science and Technology，Wuhan 430074）

Three dimensional laser scanner can obtain a large number of highly dense point cloud data through non-contact measurement in a short time.Aiming at the issue that the large amount of data leads to the high resource consumption and the slow data processing speed，a point cloud compression algorithem based on principal component analysis and space grid division is intro⁃duced.In this algorithm，local feature descriptor of point are established via principal component analysis of the neighborhood points and the point cloud space is divided into grids，the feature points defined by the local feature descriptor in the grid are retained while non-feature points are eliminated.Experimental results show that the algorithm can compress the point cloud data while pre⁃serving the local details of the original model.

point cloud compression，principal component analysis，grid division，local feature，feature point

Class Number TP391

TP391

10.3969/j.issn.1672-9722.2017.12.004

2017年6月4日，

2017年7月27日

付忠敏，男，硕士研究生，研究方向：三维数据处理，机器视觉与图像处理。张星，男，硕士研究生，研究方向：三维场景重建，计算机视觉。孙志刚，男，硕士生导师，研究方向：计算机实时控制、网络化控制、机器视觉与图像处理。