1 引言

通过三维测量技术可以获得复杂物体的点云数据,其中常见的方法有激光三维测量法^[1-2]和光栅投影测量法^[3-4]。然而随着技术的发展,测量设备的精度也随之提高,获取物体的三维数据数量级也越来越大,这给后续的传输和储存都带来了挑战。为了节省存储空间和提高传输效率,众多学者开始对数据压缩领域展开研究。相比较目前已经较为成熟的多边形网格压缩领域,三维点云压缩是一个比较新的概念,考虑到在实际应用中,用多边形网格来表示高精度模型需要数量级较大的网格,维护和存储都将消耗较多的内存和时间。同时,当投影转换到平面的多边形数目比平面像素还多时,多边形网格在平面上的投影将会比一个平面像素更小,此时利用点来替代网格作为模型的基本单元将更有优势。因此基于点的图形学成为了近些年的研究热点^[5-7]。而根据编译解码后数据精度或点云个数是否损失,可以将压缩算法分为有损点云压缩和无损点云压缩。在工程上,点云模型的位置信息和属性信息都使用浮点数进行表示,而浮点数的精度较大,实际工程中并不需要这么高的精度,因此目前提出的多数算法都属于有损范围。

Kalaiah等^[8]利用k-means聚类的方法对点云空间进行层次划分,然后采用主成分分析(PCA) 将点云的几何信息及属性信息划分为一系列的高斯概率函数,通过对这些概率分布函数进行随机采样实现重构和绘制,构建并实现了一个可以在各种平台上运行的点云压缩传输和绘制框架;Botsch等^[9]提出了一种针对点采样曲面区域进行编码绘制的算法,存储和绘制点云数据。算法将点坐标p编码为递归子分八叉树中最小包围单元的中心,每次细分的字节编码提供每个节点的树平衡信息;Peng等^[10]将类似的八叉树编码方法运用到网格模型压缩中,将掩码压缩分为两步并引入预测技术,在第二步预测时运用了模型中的拓扑关系;Schnabel等^[11]运用了与文献[ 10]相似的方法,与之不同的是,该算法在第一步也引入了预测技术,针对密集采样的点云数据算法取得了较为理想的像素深度(bpp)和峰值信噪比(PSNR)值; Huang等^[12]也提出了基于八叉树结构的压缩算法,该算法利用重新排序的掩码来预测八叉树中非空子节点的概率,从而将掩码中的1推到一端,使得利用算术编码时掩码的熵值减小,从而提高压缩率;根据点集的几何结构,Bordignon等^[13]提出了一种自适应的二叉空间分割(BSP)压缩算法。为了充分利用几何信息,在空间剖分过程中,确保BSP中每个单元的切面与单元中点的主方向垂直,然后采用渐进编码的方法将几何编码的开销分布在每个点上。

与此同时,在利用三维系统获取点云数据的过程中,由于采集设备精度、操作者经验、采集环境因素以及被测物体表面变化和数据拼接配准等操作的影响,采集得到的点云数据往往存在一些离主体点云即离被测物体点云较远的离散点,即离群点^[14-15]。不同的设备获取的离群点结构也有不同。原始点云中离群点的干扰,会使得点云的处理变得困难。目前,离群点移除也受到了国内外很多研究人员的重视,提出了基于局部点云特征移除方案,对采样点处曲率变化率或法向量进行运算,但是该类计算量较大且复杂,很有可能得到错误的数值,最终可能引发点云后期处理的失败。

在上述研究的基础上,针对目前所存在的问题,本文利用改进的八叉树算法对数据进行分割,从实际应用角度出发采用统计的方法去除离群点,并且在后续操作中优化了数据点的位置编码。通过压缩与解压缩后的效果以及与其他现有压缩算法的对比实验可以看出所提算法在保证了原始数据精度的前提下,有效地提高了压缩率,降低了压缩时间。

2 算法简介

基于无序的点云模型,所提出的压缩算法主要步骤如下:

1) 八叉树分割:根据读入点云数据坐标的X、Y、Z的最大最小值构造包围盒,根据八叉树划分条件划分包围盒。

2) 离群点移除:在分割的基础上,建立K邻域,并在八叉树最深处叶子节点分配位掩码,根据点的邻域的统计分析和位操作移除离群点。

3) 点位置细节编码和区间编码:为了提高解压精度,对每个体素所占有的点做处理。在执行序列化的同时,利用广度优先遍历查询和编码点的局部细节,对含有超过一个点的体素,计算点和体素中心的拓扑关系,产生与各自体素中心相关的位置细节参数流。最后利用区间编码输入至集合输入流,输出的点云压缩数据被写至一个文件中。

算法流程如图1所示。

图 1. 本文算法流程图

Fig. 1. Flowchart of the proposed algorithm

下载图片 查看所有图片

3 基于改进八叉树的点云压缩算法

3.1 八叉树分割

3.1.1 简单八叉树结构

八叉树结构在空间划分上有很强的优势。先在空间形成包围盒,八叉树将包围盒分成八个相同时间空间复杂度的子区间。八叉树的存储方式沿用了二维四叉树的有关方法。存储方法充分利用了八叉树结构在空间的相关性。因此,所占存储空间比三维体素阵列要少。八叉树的主要优点在于可以方便地对编码之后的点进行集合计算(例如求交、并、异或),这大大提高了计算效率,这也是其他方法难以与之匹敌的地方。不仅如此,由于通过八叉树划分之后的空间具有良好的有序性和分层性,也提高了点云的计算精度和速度。

八叉树结构通过对三维空间的几何实体进行空间划分,通过循环递归的方法对大小为2ⁿ×2ⁿ×2ⁿ的八叉树空间进行8等分划分,经过划分所得的空间具有相同的时间和空间复杂度,如果划分所得的最小包围盒具有相同的属性,则包围盒构成八叉树的一个节点;否则将继续对空间进行划分,对于2ⁿ×2ⁿ×2ⁿ大小的空间对象,最多剖分n次。图2为在某一分割停止条件下八叉树分割的点云模型的包围盒示意图及其局部放大细节。

图 2. 包围盒示意图及局部放大细节。(a)水壶模型包围盒示意图;(b)水壶模型的局部放大细节;(c)兔子模型包围盒示意图;(d)兔子模型的局部放大细节

Fig. 2. Bounding box schematic and local enlargement details. (a) Bounding box schematic of kettle model; (b) local enlargement details of kettle model; (c) bounding box schematic of bunny model; (d) local enlargement details of bunny model

下载图片 查看所有图片

在完成逐层划分之后,对数据进行编码,编码方式为:假设点云坐标P(x,y,z)和树中节点(a,b,c)相对应且树中任一个节点都与一个最小包围盒一一对应;节点的编码为M=m_n-1…m₂m₁m₀,m_n-1为节点在n层的节点序号。

首先利用空间坐标计算出节点索引值:

a=intx-xminλb=inty-yminλc=intz-zminλ,(1)

式中x、y、z为点在空间的坐标,x_min、y_min、z_min为点云在空间中的最小坐标值,λ为八叉树分辨率,int表示计算结果取整。

其编码可用二进制表示为

a=an-12n-1+an-22n-2+an-32n-3+…+a020b=bn-12n-1+bn-22n-2+bn-32n-3+…+b020c=cn-12n-1+cn-22n-2+cn-32n-3+…+c020。(2)

节点序号m_i和a_i,b_i,c_i之间的关系可表示为

mi=ai+bi·2+ci·4。(3)

若知道八叉树某一节点序号m_i,利用m_i和a_i,b_i,c_i之间的关系得出:

ai=(mimod2),bi=[(mi/2)mod2],ci=[(mi/4)mod2],(4)

式中mod为取模运算符,利用上述公式可以由点A包围盒邻接的立方体求出节点在树中的编码,即可从根节点沿路径检测出节点,按此规则,在点A搜索出距离最近的K个点,并得到点A的K邻域N|A|。

通过八叉树结构对每个点搜索其邻域。查询非空叶子节点所在立方体的数据点和周围26个叶子节点立方体中的数据点,找到最近的K个点作为点云的K邻域,如果邻域内点的个数不足K个,则扩大搜索范围至124个立方体,最终完成K邻域的建立。

3.1.2 分割停止条件

在实际操作中,对于分割停止条件,并无确定的标准。目前一般使用八叉树分辨率进行限制。但当分辨率过小时,过多的分割会造成内存浪费;当分辨率过大时,体素就越大,由于利用体素形心近似表示原始点,因此造成的误差越大。本文提出了一种新的分割停止条件。以构造的包围盒为划分对象,根据分割停止标准划分最小包围盒,其中分割停止标准的建立基于叶子节点/点云比率、八叉树分辨率λ、层数之间的关系,计算点云总数和非空节点之间的差值与点云总数的比值,即在划分过程中所产生的一定精度损失率,表示为

λ3>Vcube8n2Vcube3≥λ≥λ1t=M-PM,(5)

式中P表示空间中最小包围盒的数量,M为当前层点云中点的数量,λ为八叉树分辨率,λ₁为扫描仪精度,t为精度损失率,n为层数,V_cube为包围盒的体积。调节分辨率λ,确保t在[0,0.1]之间,图3为调整λ时,不同层数n所对应的分割示例,P_voxel为当前层所对应的最小包围盒。

图 3. 八叉树分割,每个体素至少含一个点。(a) n=1, Pvoxel=9; (b) n=2, Pvoxel=40; (c) n=3, Pvoxel=137; (d) n=4, Pvoxel=435; (e)n=5, Pvoxel=1426; (f) n=6, Pvoxel=4815; (g) n=7, Pvoxel=15845; (h) n=8, Pvoxel=45859

Fig. 3. Octree segmentation, each voxel containing at least one point. (a) n=1, Pvoxel=9; (b) n=2, Pvoxel=40; (c) n=3, Pvoxel=137; (d) n=4, Pvoxel=435; (e)n=5, Pvoxel=1426; (f) n=6, Pvoxel=4815; (g) n=7, Pvoxel=15845; (h) n=8, Pvoxel=45859

下载图片 查看所有图片

3.2 离群点移除

对于完成分割后的数据,利用熊邦书等^[15]的方法建立K邻域,然后对每个点的邻域进行统计分析。通过计算点云集中点到邻域的距离来处理离群点。针对空间的每一个点,得到其所在邻域内点的平均距离和标准差。假设所得数值呈高斯形态分布,设定离群点的阈值,平均距离在阈值之外的点,将其定义为离群点并移除点云空间。

算法首先通过广度遍历对八叉树分层遍历,对最深层的叶子节点添加掩码。如图4所示,假设八叉树只分为2层,最深层点的掩码可表示为1000010001001000。

图 4. 两层八叉树掩码结构

Fig. 4. Mask architecture of two layer octree

下载图片 查看所有图片

节点N的位掩码表示为S^N,遍历查询的离群点K的位掩码表示为

SN={SiN}={S1NS2N…S7NS8N},(6)

式中S^N的长度为8。如果给定节点S^N=1表示节点包围盒至少有一个点。S^N=0表示包围盒为空。

离群点去除的方法如下:设N_n为新八叉树S_n的根部,当判断八叉树S_n没有遍历至底端时,N_n赋值为有遍历顺序S_n的非空节点,如果S_n的节点N_n满足N_K一样的离群点条件则S^K=bitewiseAND(S^K,0),否则继续遍历并将N_n赋值为S_n的新的非空节点,直到遍历完八叉树为止。其中bitewiseAND为按位与操作。

3.3 点位置细节编码

根据八叉树特性,所有被分配到一个特定体素的点只会被体素中心表示。在实际处理中,并不能保证100%的分割(即每个体素只含一个点),因此采用额外的点位置编码来提高精度。

对于八叉树分割之后含有超过一个点的体素,采用点位置编码,并计算每个点坐标X、Y、Z与体素中心A之间的距离,把A点与每个点之间的矢量关系编码存储起来,因此解码时可以准确地还原位置。如图5所示,基于扫描目标的获取精度,离散化的局部点坐标用正整数表示,整数值受体素分辨率和特定精度的限制。在随后的区间编码时,点位置参数能够有效地被较小的位表示。该技术可有效减少计算复杂度,尤其适用于点密集并且曲率面较大的点云。

图 5. 点位置细节编码

Fig. 5. Detail encoding of point position

下载图片 查看所有图片

3.4 区间编码

最后对输入的数据流进行熵编码,常用的方法有哈夫曼编码、算术编码和区间编码。综合考虑结合效率和压缩率,选择了区间编码。

区间编码是在整数区间上进行整数运算,区间长度为s或表示为b^d,其中b为基数。设有一整数区间i∈[L,H),L为区间下沿,H为区间上沿。区间范围R=H-L+1。T为符号的总计频率。f_S为符号S的频率。令F_S为符号S的累计频率。累积频度是符号小于S的其他符号的频率总和:

FS=∑x<Sfx。(7)

假设A_i是信息中的第i个想要编码的字母,1≤i≤k。根据频率表选择s大小的长度编码A₁,留下R₁的区间长度编码A₂,留下R₂的区间长度编码A₃,以此类推, 区间长度的计算公式为

R(0)=s,Ri=R(i-1)T·(FS+fS)-R(i-1)T·FS,(8)

如果 Bj=∑i=1jR(i-1)T·FS在长度s上的完整范围是[Bk,Bk+Rk),当Rk小于一定阈值时,从[B_k,B_k+R_k)中提取一个数值来表示整个压缩数据。

4 实验

本文算法实验仿真编译结果在Microsoft Visual Studio 2012 32位win7系统上进行,并对八叉树分割、离群点移除以及最后的压缩结果进行了分析。结合实验室在点云处理中常用的点云模型,验证了本文算法的实用性和有效性。点云模型如图6所示,图6(a)为Stanford大学所提供的兔子模型,图6(b)为三维重建实验中常用的3D模型,图6(c)为水壶模型经过离群点移除后的模型,图6(d)、(e)分别为人脸模型和塑料模型利用实验室光栅投影三维测量得到的点云模型。

图 6. 实验所用点云模型。(a)兔子模型,点数为31607;(b)猫模型,点数为10000;(c)水壶模型,点数为19062;(d)人脸模型,点数为46111;(e)塑料模型,点数为24673

Fig. 6. Point cloud models used in experiment. (a) Bunny model, point is 31607; (b) cat model, point is 10000; (c) kettle model, point is 19062; (d) face model, point is 46111; (e) plastic model, point is 24673

下载图片 查看所有图片

表1为不同模型的八叉树分割,选择合适的λ值,使得在八叉树最深层满足t∈[0,0.1],意味着基本实现了每个最小体素包含一个点,t值越小,在近似和后期操作时造成的误差越小。λ值需要通过(5)式不断逼近。对实验室的点云设置λ=0.0018 m。

完成八叉树分割之后,为了保证表面平滑和不受噪声点干扰,在所建立的K邻域内进行离群点移除。移除原则为:确保所滤除点中离群点占绝大多数,一般离群点分布在边缘处以及在光栅投影黑影处。对K值和a值的选取视所拍摄的物体表面复杂度和大小而定,对于同一物体,一般选择相同的K值和a值,首先确定K值大小,a值受K值限制。目前并没有针对K值的一个自动预测器,因此K值一般选择经验值。以塑料模型为例,选择K=50,a=3.0,滤除点数为274,离群点移除结果如图7所示。

图 7. 离群点移除结果。(a)原始数据;(b)移除离群点后的点云数据;(c)移除的离群点

Fig. 7. Results of removing outliers. (a) Initial data; (b) point cloud data after removing outliers; (c) removed outliers

下载图片 查看所有图片

从图7可以看出,离群点主要分布在模型的下侧和表面附近,为了更好地观察移除效果,对点的大小放大一倍。在确保点的低损失率的前提下,利用本文算法可有效滤除离群点。因为造成了点的损失,本文算法对于实验室点云属于有损压缩。不过对于点云模型兔子、猫和水壶,在进行解压缩之后,点的个数没有损失,且损失的精度也在可控范围内,可以与其他无损压缩技术相比较。

图8为兔子模型的解压缩示意图,根据(5)式设置不同的λ得到的t值不同。图8(a)~(e)为解压缩前后的兔子模型,图8(b)~(f)为模型背部的细节放大。解压缩前后的点云在整体上基本没有变化,但由于解压缩计算过程中,在最小包围盒内部使用中心点近似取代原始点,因此不可避免地造成了点位置精度的损失。通过图8(d)可以观察得到,当t∉[0,0.1] 时,点的偏移会比较大,较大的偏移破坏了区域平滑性和曲率一致性。红色标记区域点的位置具有较为明显的偏移。可以通过(5)式调节λ值使得t满足t∈[0,0.1]来降低偏移量,提高解压缩精度,图8(f)中t∈[0,0.1],可以看出点的偏移明显减小,点云区域的特性得以较好的保留。

图 8. 兔子模型解压缩示意图。(a)解压缩前的兔子模型;(b)图(a)局部放大细节;(c) t=0.25时解压缩结果;(d)图(c)局部放大细节;(e) t=0.005时解压缩结果;(f)图(e)局部放大细节

Fig. 8. Decompression schematic of bunny model. (a) Bunny model before decompression; (b) local amplification details of Fig. (a); (c) decompression result when t=0.25; (d) local amplification details of Fig. (c); (e) decompression result when t=0.005; (f) local amplification details of Fig. (e)

下载图片 查看所有图片

图 9. 压缩率及压缩时间对比

Fig. 9. Comparison of compression ratio and compression time

下载图片 查看所有图片

另外还将本文算法与文献[ 16]、[17]算法进行了性能对比。文献[ 16]算法利用生成树划分空间,并对浮点数做处理;在压缩时间和压缩率上都逊于文献[ 17]算法,其中压缩率采用字节每点(Bpp)为单位。文献[ 17]中采用八叉树对空间划分,主要应用于动态点云压缩,不过利用该算法对静态点云也取得了较好的压缩率。

由图9可知,文献[ 17]和本文算法对比于文献[ 16]算法无论是在压缩率还是压缩时间上都取得了极高的提升。主要是因为文献[ 16]算法构造最小生成树并分块对浮点数进行处理,算法的关键放在了浮点数的分析,因而对空间拓扑分析不足,导致空间冗余处理的效果不理想。而本文算法和文献[ 17]算法利用八叉树进行空间划分并建立了清晰的拓扑关系,当确定点坐标精度(稍小于光栅采集精度)时,与文献[ 17]算法相比,针对静态点云压缩,本文算法并不考虑时间冗余,并且在划分时引入了掩码编码,方便在查询和遍历八叉树时访问和删除点。在相同点坐标精度的情况下,本文算法取得了和文献[ 17]算法同样优秀的压缩效果,并减少了压缩时间。而且在点的细节方面多做了处理,增加了空间复杂度,因此在解码时,能根据点坐标精度更加准确地还原点的位置和个数。

5 结论

现代化点云采集设备所得到的点云数据量越来越庞大,如何在实际应用中高效地对数据进行传输和存储是目前的热点研究问题。针对静态点云,实现了一种基于改进八叉树的点云有损压缩算法,该算法能够有效地快速实现点云模型的压缩。该算法改进了八叉树的分割条件,优化了后续的区间编码。由实验结果可知,该算法具有良好的压缩率和较理想的压缩时间,后续将采用车辆、船只以及现代城市的部分等三维数据对算法进行进一步的测试及改进,以验证其能否真正满足实际应用中对三维点云数据的压缩处理需求。后续研究将会增加在区间编码中频率模型的复杂性,如果再结合有序点云,有望实现更高的压缩效率。