1 引言

三维点云分割一般根据三维点云信息的空间特征、几何特征或纹理特征等对其进行区分,使得同一片区域内的点具有相同的属性,分割后的结果可用于识别和分类等^[1]。受点云数据规模较大、采样密度不均匀以及点云数据几何结构不清晰等因素的影响,点云分割具有一定的挑战性。比较有效的分割方法是联合点云内部骨架和外部特征点进行分割。

对于三维点云的骨架提取,目前常用的方法有:1)对称轴分析法。该方法由Blum^[2]提出,以视觉特征为基础,通过处理点云的中轴信息来提取骨架。该方法多用于处理多边形模型或参数曲线曲面模型,使用此方法能够获取精确度较高的骨架。对于复杂的动植物模型,该方法的计算比较复杂,精度较低,很难在实际应用中实现^[3]。2)基于拉普拉斯(Laplace)收缩的三维点云骨架提取方法。该方法由Cao等^[4]提出,其先对点云进行Laplace算子收缩,从外围向内部迭代收缩从而提取出骨架。这种方法容易在局部点云上出现过收缩。此外,该方法的准确性很大程度上依赖于如何设定Laplace算子的参数,Laplace算子参数的细小偏差都将导致点云的分割结果达不到预期要求。3)基于数学结构上的分析方法。这类方法中比较典型的有Reeb图法和Voronoi图法。Reeb图法是由Shinagawa等^[5]提出的,该方法利用输入数据点上的标量函数,对数据边缘点与点之间的关系进行映射,构造出一种数学结构关系图。Dey等^[6]则是利用Voronoi图的特性对点云进行骨架提取,但是在处理一些有噪声的点云数据时Voronoi图法的效果一般。4)基于L₁-中心骨架提取方法。该方法由Huang等^[7]提出,主要是利用L₁-中值定理进行骨架收缩,可以很好地避免野点对骨架提取过程的干扰,具有很好的稳健性。

一些研究团队对骨架分割进行了积极探索。Zhan等^[8]提出一种基于颜色的点云分割方法。该方法是一种依据色度相似性和空间接近性的分割方法,具有一定的局限性。Wang等^[9]提出了一种基于聚类的分割方法。该方法首先将输入点云的正态线映射到高斯球上,然后使用平移聚类算法将其划分为组,最后基于欧氏聚类算法处理数据。该方法能够分割出建筑物、树木、路灯和其他物体,其主要是用于处理大型城市建筑物数据。Rabbani等^[10]提出了一种使用平滑约束度分割点云的方法。该方法使用局部表面法线和点连接,使用k-邻近或固定距离实现。不足之处是,该方法需要手动调整参数。Wang等^[11]提出了一种利用相似群建议网络(SGPN)的语义分割方法。该方法在各种三维场景下的实验效果都很好,但是该方法还不适用于结构复杂的数据。在2015年的国际信息处理会议(ICIP)会议上,Vo等^[12]介绍了一种在图像分割领域的区域增长算法。Vo等使用基于八叉树(octree)的区域生长算法对点云数据进行处理,首先把点云数据分割成子数据块,然后对得到的不完整的数据进行细化处理,最终得到了平滑的骨架。对于数据结构较为简单的骨架来说,该方法操作简单,效果也较好。本文将就如何进行点云的内部骨架分割展开研究。

2 算法流程图

本文算法的基本思路是:首先利用L₁-中心骨架算法提取点云数据的骨架点,然后利用基于octree的区域增长算法对其进行分割,最后利用OpenGL编程进行骨架点连线。算法流程图如图1所示。

图 1. 算法流程图

Fig. 1. Flow chart of algorithm

下载图片 查看所有图片

3 点云骨架提取

3.1 点云随机下采样

通过随机下采样把采样点收缩为骨架点,从而生成骨架点。一般来说,采样点越多,稳健性越好,但是计算量也越大。实验发现采样点过多或过少对结果的影响均不大,这里采样点的数量设置为总数的10%。对于采样点的位置,可以通过洗牌算法来选定采样点的位置。

为直观展示洗牌算法的步骤,以表1为例加以说明。设采样点的数量n=8,即初始采样点的顺序为1,2,3,4,5,6,7,8。

表1中,第一行表示,从1到8中随机选择一个数,得到6,则交换当前数组中第8和第6个数;第二行表示,从剩下的数中随机选择一个数,得到2,则交换当前数组中第7和第2个数;第三行表示,剩下的数中随机选择的刚好是6,这意味着只需把当前线性表中的第6个数留在原位置,接着进行下一步;以此类推,直到整个排列完成。得到的采样点的位置为7,5,4,3,1,8,2,6。

3.2 采样点收缩形成骨架

得到一系列采样点后利用L₁-中心骨架算法进行骨架收缩提取。骨架收缩提取的基本思想是通过选取一系列点的中值而不是平均值进行收缩,产生新的骨架点,不停地迭代并重新将其分配到所在区域的输入点的中心。直接应用L₁-中值算法往往会产生稀疏分布^[7],造成结果中的一些中心点产生一团点簇。为了避免这种现象,首先需要进行条件正则化,然后进行骨架收缩,最后基于密度进行加权。对于有缺失的点云数据,还需增加一步——定义中心位置,才能完成整个过程。

1)条件正则化

给出一系列乱序的点集Q= {qj}j∈J⊂Ω³,以及从Q中随机下采样得到的点集X= {xi}i∈I⊂Ω³,利用最优化公式可得出一系列骨架点集,其中最优化公式为

argminX∑i∈I∑j∈J‖xi-qjθ‖xi-qj‖+R(X),(1)

式中:I和J分别为点集Q和X中的点数;R(X)代表点X的邻域点分布度量;θ(r)是高斯权重函数,θ(r)=exp[-4(r/h)²]。

当(1)式中的能量梯度为0时,代入μ= γi∑i'∈I\{i}βii'σi∑j∈Jαij,其中α_ij= θ(‖xi-qj)‖xi-qj‖,β_ii'= θ‖xi-xi'‖‖xi-xi'‖2,即可得到

(1-μσi)xi+μσi∑i'∈I\{i}xi'βii'∑i'∈I\{i}βii'=∑j∈Jαijqj∑j∈Jαij,(2)

式中:γ_i是控制输入点的引力和采样点的斥力之间的平衡参数;σ_i为分布度量。

在(2)式中,根据线性代数可得到关于X的解集为X=A^-1BQ,然后进行迭代,其中X^k={ xik},且k=0,1,…,可得到

xik+1=∑j∈Jαijqj∑j∈Jαij+μσik∑i'∈I\{i}(xik-xi'k)βii'k∑i'∈I\{i}βii'k。(3)

接下来,通过设置参数的取值即可完成条件正则化。

2) 迭代收缩骨架

给定邻域大小h,即可生成一系列点X={x_i},i∈I,这些点代表了局部邻域的L₁中值点。在一些情况下,这些点可以直接代表骨架点。在复杂数据的条件下,这些点仅代表骨架的分支点,还需要进行迭代收缩才能代表骨架点。为了确定标记的点是否为收缩后的点,先计算所有的非分支点x_i,然后对这些点进行平滑处理并剔除其中的噪声点。

3) 基于密度的加权

对于一些点云密度不均匀的数据,局部中心往往会偏向于密度较高的区域,导致输出的点云骨架点的位置在切面方向上发生位移,因此需要对密度进行加权。

将输入的点云集中的每个点q_j的加权局部密度定义为

dj=1+∑j'∈J\{j}θ(‖pj-pj'‖)。(4)

将其代入到(3)式中,即可得到

xik+1=∑j∈Jαijkqj/dj∑j∈Jαijk/dj+μσik∑i'∈I\{i}(xik-xi'k)βii'k∑i'∈I\{i}βii'k。(5)

通过第一项中的加权局部密度可以有效地减小密度不均匀区域对收缩结果的影响。此外,局部点的密度由函数θ(‖p_j-p_j'‖)决定。

4) 再次定义中心位置

在正常条件下,生成的L₁中心是在输入点云的中心点附近,但是如果输入点云有缺失,可以通过重新定义中心位置来进行收缩骨架。为了增强系统的稳健性,在进行下采样后分别在每个分支上对采样数据重新对齐,然后对弯曲的分支作平滑处理,最终重新定义中心位置。

4 对骨架点进行分割

4.1 点云体素化

将输入点云体素化,利用八叉树算法覆盖输入点云^[13],如图2所示。选择基于指针区域的八叉树进行实验,这样做可达到如下3个目的:1)把点云数据组织好(索引数据);2)对点P进行光栅化处理(简化数据);3)为特征点估计定义邻域点。在这种八叉树结构中,输入点云所占空间上的所有节点都被分解成8个一样的子节点,并且在这个空间上的所有体素的几何信息是一致的。

图 2. 八叉树实例

Fig. 2. Example of octree

下载图片 查看所有图片

体素化确定了在图2(c)中的包围P的最小立方体边界框,称之为0级节点,对应图2(b)中的level 0。0级节点再分裂成8个小体素,重复上述步骤直至满足要求的判别条件。目前,已有的判别条件有3种方案:Ayala等^[14]于1985年提出的最小体素值判定;Pulli等^[15]提出的预先确定的最大深度树方案以及Wang等^[16]于2005年提出的体素最大采样数量方案。采用残差阈值r_th和最小体素值d_min判定的方法作为判别条件。先把0级节点分割成一个特定的体素大小,并将其定义为d_U,即可用体素网格代表输入点云的局部表面特征。初始分割后,非空的体素将被继续分割,直至满足判别要求。由于在使用此方法过程中,大体素会出现在平滑区域以内,小体素出现在边缘区域,故该方法可以显著地减少体素数量,减少迭代步骤,提高分割效率。

4.2 点云特征估计

研究人员除了可从三维激光扫描仪中获取一些诸如几何坐标^[17]、RGB颜色信息等,还可从点云数据的分布中获取一些有价值的信息,例如围绕中心的各个方向的数据以及每个主方向上数据点的方差。在三维点云中,通常把最小的方差对应的方向称为平面法向量的近似值。本研究所使用的区域增长算法主要是利用法向量的特征进行信息处理,这些信息都根据体素中的点进行计算。利用基于主成分分析(PCA)算法对以上法向量特征进行分析。

4.3 区域增长

利用基于八叉树的区域增长算法逐步将有相似特征的体素分组,在分组的过程中会产生一些体素簇,每一个体素簇都代表着平滑表面的一个部分。利用八叉树进行区域增长有以下3点好处:1)先对点云进行体素化,减少了后续进行区域增长的工作量;2)相邻体素点涉及到的邻域算法有助于减少对原始点云数据的k-邻域搜索^[18];3)体素网格本身有着一定的空间结构,允许快速并相对容易地搜索相邻体素。该算法的核心是把所有法向量相近的点全部提取出来,形成点簇,将每一个点簇都可看作是相似的一部分,即被分割出来。该算法的具体步骤如下:

1) 输入原始点云集,将整个点云按照每个点的曲率进行排序,搜索出曲率最小的点,并将其添加为种子点。

2) 搜寻种子点邻域的点,若邻域内某一点的法向量与种子点的法向量的差值小于一定的范围,则计算该点的曲率。若该点的曲率小于设定的阈值,则该点属于当前的部分。

3) 从原始点云中去除已经通过第二步测试后的点。

4) 根据点云中点的数量设置最小点云簇(分割出的最小数量)和最大点云簇(分割出的最大数量)。

5) 重复以上步骤,原始点云将会被分割成满足以上最小和最大点云簇的部分。对每个部分进行染色,使用不同颜色对不同部分加以区分。

6) 当剩余点的数量小于设置的最小点云簇时,停止分割。

5 实验结果及分析

实验所用计算机的CPU为Intel Core i5-7300HQ,CPU的主频为2.50 GHz,电脑内存为8 GB,操作系统为Windows10 64位。实验所用软件为Visual Studio 2013 Visual C++ 控制台应用程序,开源库为OpenGL,开源点云库为PCL1.8.0。首先利用L₁-中心骨架算法对输入的点云数据进行骨架点的提取,然后利用基于八叉树的区域增长算法对已经提取出的骨架点进行有效的分割,其中选取曲率阈值为0.7。因为之前的步骤都是对点进行处理,输出的分割结果也将都是点的集合,所以需要利用OpenGL库对这些点进行连线,以达到更好的显示效果。采用树枝(有叶)模型、树枝(无叶)模型、字母模型、人物模型以及动物模型对本文算法的稳健性进行验证。如图3~图8所示,其中树枝(有叶)模型含有40551个点,树枝(无叶)模型含有11004个点,字母模型含有7029个点,人物模型含有43545个点,珊瑚模型含有14207个点,动物模型含有25713个点。在骨架点提取部分,图3~图7的结果对原始三维点云的骨架点提取的效果最好。从视觉上看,图3~图7的结果更靠近点云骨架的位置,也很好地契合了输入点云的拓扑结构。即使是对于有大量噪声点的字母模型(图5),本文算法也取得了很好的效果,能够准确地表达出字母“Y”的特征,这表明该算法具有较强的稳健性。但是对于图8的动物模型,本文算法的结果还有些许瑕疵。实验结果显示,图8中的恐龙的尾部和身体、四肢和身体相结合部分的骨架点过于稀疏。这主要是由于该动物模型的身体部分的横截面较大,在进行骨架点提取时本文采用了一种收缩的方法,收缩后的骨架点会在整个身体的中心位置产生。同理,恐龙四肢的骨架点也是在其中心位置。本来恐龙四肢是和身体相连接,但是本研究采取的收缩方法增大了这两部分的距离,导致最终提取出的恐龙骨架的四肢和身体产生了较为明显的空隙。需在下一步的工作中继续改进算法,解决这类问题。

图 3. 树枝(有叶)模型。(a)原数据;(b)骨架点;(c)结果

Fig. 3. Tree (with leaf) model. (a) Raw data; (b) skeleton point; (c) result

下载图片 查看所有图片

图 4. 树枝(无叶)模型。(a)原数据;(b)骨架点;(c)分割结果

Fig. 4. Tree (without leaf) model. (a) Raw data; (b) skeleton point; (c) result

下载图片 查看所有图片

图 5. 字母模型。(a)原数据;(b)骨架点;(c)分割结果

Fig. 5. Alphabet model. (a) Raw data; (b) skeleton point; (c) result

下载图片 查看所有图片

图 6. 人体模型。(a)原数据;(b)骨架点;(c)分割结果

Fig. 6. People model. (a) Raw data; (b) skeleton point; (c) result

下载图片 查看所有图片

图 7. 珊瑚模型。(a)原数据;(b)骨架点;(c)分割结果

Fig. 7. Coral model. (a) Raw data; (b) skeleton point; (c) result

下载图片 查看所有图片

图 8. 动物模型。(a)原数据;(b)骨架点;(c)分割结果

Fig. 8. Animal model. (a) Raw data; (b) skeleton point; (c) result

下载图片 查看所有图片

从分割层面来讲,图3和4的植物模型、图5的字母模型、图7的珊瑚模型以及图8的动物模型的分割结果都比较好,这主要是因为本研究所用到的分割方法是根据点云的曲率参数进行区域增长分割。若是前一个点的曲率和后一个点的曲率相近,则会把两个点划分为同一区域。对于这些不同部分曲率差异较大的点云模型来讲,本文算法均能取得较好分割结果。然而,对于图6的双人人体模型,如果从人眼视觉层面来讲,分割的结果是有偏差的。图6的人体模型展现的是两个人头对头,手对手,分割的结果显然不符合常理,如图6(c)所示,这是由于算法是按照点的曲率进行分割的,此过程过于复杂。实际上,把图6的人体模型从中间直接进行切割,效果应会更好。在实际应用中,要先根据模型的结构特点选择合适的方法。表2中显示了各算法的运行时间,从表中可知,对于图3的树枝模型(有叶)与图6的人体模型,算法的运行时间接近;对于图7的珊瑚模型和图8的动物模型,算法的运行时间接近;对于图4的树枝模型(无叶)与图5的字母模型,算法的运行时间相近。结合每个模型点的数量可知,在提取骨架点的过程中,影响算法运行时间的决定性因素是点云模型点的数量,与点云模型自身的空间结构关系不大。图3和图4两个模型虽然结构上相似,但是最终算法的运行时间相差很大,图7和图8两个模型尽管结构大不相同,但是因为两个模型点的数量相近,所以算法的运行时间也相近。从整体上看,上述模型处理的时间都有些缓慢,反观分割时间,几组数据的分割时间均是毫秒量级的,速度较快。如何提高骨架点的提取速度将是下一步要继续进行的工作。

此外,将本文算法与传统的Laplace收缩方法进行对比,结果如图9所示。通过图9的结果可知,应用本文算法的图9(b)和(e)相比于应用Laplace收缩方法的图9(c)和(f)能更好地保持骨架点的完整性。本文算法能够有效地保持原有数据的几何拓扑结构,并且提取出的骨架点更能贴合原始数据的自然骨架,所得结果符合人眼的视觉习惯,不会产生错位的问题,准确性更好。

图 9. 骨架点提取对比实验。(a)(d)原始数据;(b)(e)本文算法;(c)(f)拉普拉斯算法

Fig. 9. Comparative experiment of skeleton point extraction. (a)(d) Raw data; (b)(e) our method; (c)(f) Laplacian method

下载图片 查看所有图片

6 结论

针对三维点云内骨架分割计算量大,且已有的方法存在一定的局限性的问题,提出一种针对点云内骨架的分割方法。利用L₁-中心算法对输入点云进行点云数据的内骨架点提取,然后利用基于八叉树的区域增长算法对提取后的点云骨架点进行分割,最后利用OpenGL库完成对骨架点的连线。实验结果表明,对于环状点云模型或是比较细的点云模型(模型的切面半径较小),本文算法对点云骨架点的提取效果较好。对于不同位置切面半径变化较大的点云模型,本文算法还需继续改进。从分割的层面上讲,对于曲率变化较为明显的点云数据,应用本文的分割方法能够取得较好的分割效果。该方法可以快速准确地分割点云数据。本文所提出的方法利用了体素模型,可以简化数据、索引数据以及定义计算局部表面属性的邻域组,但是体素的大小仍需要手动决定。另外,对于各点曲率差值较小的模型,本文所提出的算法也不能取得最佳效果。在下一步的工作中,需对该算法进行进一步改进。