1 引言

三维激光扫描技术的发展拓展了三维图形的应用领域,使得虚拟现实(VR)、增强现实(AR)技术得到了快速的发展。尤其是便携式三维数据采集设备的出现,例如Microsoft公司生产的Kinect和Hololens,促使了大量、多样的三维(3D)模型的涌现。在这种情况下,3D计算受到了人们的关注。

点云数据是三维扫描设备提供的最基础的数据形式,具有散乱、无序以及数据量大等特点。以Kinect V2为例,每秒可以采集到12MB的点云数据。面对海量的、散乱的点云数据,数据分析和数据处理都会消耗大量的系统资源和时间。因此,构建点云的拓扑结构并实现数据分割(将数据划分为独立的区域),是提高3D数据重建速度和质量的基础与保证。

点云数据分割算法是点云计算的基础。点云分割算法的实现效果和运行效率,在3D对象获取、对象识别以及目标跟踪等应用中起到至关重要的作用。通常,点云分割算法是利用点云特征提取技术获取数据的法向量^[1-2]、颜色^[3-4]以及反射光强弱度^[5]等特征参数,依据特征参数实现分割。然而,随着3D数据量的增大,扩充了现有的3D数据模型,例如,Trimble 3D Warehouse 就包含了超过220万的3D 模型数据(https://3dwarehouse.sketchup.com/)。大量的3D数据模型为点云数据分割提供了新的方法和途径。与传统的方法不同,本文从数据模型的角度出发,通过计算点云数据和数据模型的形状特征,实现模型与数据的匹配,从而建立点云分割区域。基于模型的分割可以发现分割区域的几何规则,为数据精简提供帮助,进而加速数据重建和对象识别的速度。主要包含以下几个方面:

1) 创建了基于形状的点云数据分割(SS)方法。该方法以形状相关的特征为驱动,获取数据的结构信息,将点云数据分割成不同的部件,分割后的部件可以使用规则形状进行数学描述。

2) 点云数据的数据量大,为了提高算法的执行效率,改进了八叉树算法,并在此基础上构建了数据索引。首先,利用数据密度值的变化率,沿着两个线性方向向量重组数据。其次,利用重组后的数据参与点云分割,提高了算法的执行效率。此外,重组算法对多目标的场景中不同对象的边界数据敏感,可以有效提取某一对象的边界。

3) 在八叉树数据索引之上,建立了基于法向量参数的一致性分割算法。使用该算法可以提高分割区域内点的相似度,减少形状分割的迭代次数,提高形状分割的效率。此外,该算法可以提高分割区域形状参数估算的准确度。

4) 基于随机抽样一致性(RANSAC)^[6]算法,定义了形状匹配算法的目标函数,并利用八叉树索引,迭代式地实现3D形状分割,进而提取区域形状参数。

2 相关工作

数据区域分割问题属于点云应用系统中的基础研究部分;分割算法的精度和速度起着关键的作用。目前,有关点云区域分割算法有很多,例如Edge-based算法、区域增长法、聚类分析、模型匹配方法等。Edge-based算法是在1987年由Fan等^[7]提出,该算法复杂度大,而且边识别的准确度对分割效果影响很大,近几年与之相关的研究较少。

区域增长法,首先选取“种子”数据,通过曲面的平滑度,迭代式地调整区域大小,从而实现点云分割。胡怀宇等^[8]利用曲率信息分割成七种不同的表面类型,通过区域增长的方法发现每一个种子区域中曲率近似平面的区域。庞世燕等^[9]通过主成分分析(PCA)提出平面特征,并利用区域增长的方法提取凸壳,结合凸壳算法提取三角面片的轮廓数据。Dimitrov等^[10]考虑了数据的多特征实现的分割。Nurunnabi等^[11]利用最小协方差行列式(MCD)结合区域增长法实现分割;2015年提出利用最大一致性与最小距离(MCMD)测量区域数据一致性并实现分割^[12]。Vo等^[13]利用八叉树重采样技术结合区域增长法实现分割。区域增长法的优点是稳定性好,缺点是参数调整不够灵活,分割可控性差。

聚类分析法是多元统计学方法的一种,以“物以类聚”的原则进行划分。点云的聚类分割算法是将点云数据看作具有一定关联属性的多维度数据集合,按照多维度属性聚类划分,实现点云数据分割。Velmurugan等^[14]利用K-means方法完成点云聚类分割。王帅等^[15]通过谱聚类实现分割。熊风光等^[16]通过K-means算法实现关键点剔除及匹配等。Yan等^[17]利用具有噪声的基于密度的聚类方法(DBSCAN)实现点云数据分割。为了优化点云分割算法,相关学者使用多个步骤混合分割数据,比如基于边的分割算法与RG方法相结合,通过领域关系以及几何特征建立分割区域等^[18-20]。基于聚类的点云数据分割算法具有参数设置灵活,算法稳健性好等特点,但收敛过程慢,点云分割算法的时间复杂度大。

模型匹配方法也被称为体分割方法,该方式常用于man-made^[21]的数据集。该类算法是利用数学表达式的方式描述分割区域集,例如圆柱、平面等。其中,以RANSAC和霍夫变换 (HT)算法应用最为广泛。RANSAC算法最早由Bolles等^[6]于1981年提出,目前多应用于3D平面的检测和识别,识别效果较好,但效率不高。例如,文献[ 22-25]利用RANSAC方法分析点云的平面特征,实现平面的提取和分割。为了获得精准的分割效果,2010年Biegelbauer等^[26]利用分层的RANSAC算法完成建筑物立体面的提取工作。该研究按照低分辨率到高分辨率的方式,分层完成分割,并通过投票和排名等方法给出最终分割结果。颜色属性作为分割的依据,提高了算法的精准度。例如,Zhang等^[27]通过将Meanshift算法扩展到3D颜色树上,以聚类算法改进RANSAC迭代执行,使其找到更准确的分割区域。为了降低噪声对分割效果的影响,Kang等^[28]提出利用Bayesian 采样一致性 (BaySAC)算法改进RANSAC,文献通过统计候选数据集的直方图表示分割原语,通过分层、并行化的方式完成数据分割。Li等^[29]通过正态分布变换(NDT)提高了RANSAC算法对平面识别的正确性。

HT方法经常应用于图像中几何形状的识别。2004年,Overby等^[30]通过3DHough变换实现了地面建筑物的分割工作。2005年,Rabbani等^[31]又通过3DHough变换识别了众多物体中的圆柱。Tarsha-Kurdi等^[32]比较了RANSAC和Hough在平面分割方面的性能,指出RANSAC时间消耗相对较低,此外,还通过实验证明了Hough算法对参数的依赖性较大。Liu等^[33]利用Hough变换分析点云数据中直线的提取技术。Hulik等^[34]提出利用Hough检测点云的连续平面,并将其和PCL的RANSAC算法对比,结果表明该算法可以得到更小的角度和距离误差。

与3DHough点云分割算法比较,RANSAC算法具有较高的稳健性;然而面对散乱的、不规则的数据时,RANSAC算法时间消耗较大。不幸的是,通过3D扫描仪采集获取的点云数据往往是不完整的、散乱的、并且无任何结构信息。另外,被测对象,尤其是自然对象,其形状是无规则的,很难通过数学的方式去描述与表达。因此,利用RANSAC算法完成形状提取和识别,不但成功率低,而且时间消耗大。为了将RANSAC算法应用到自然对象的点云数据集中,从而使得被测对象中满足或者近似满足规则形状的分割区域被获取,并参与点云的精简和重建过程。本文尝试建立形状模型库,提取点云数据与形状相关的几何特征,重新组织点云数据,并完成模型与数据集的匹配操作。在此基础之上,改进RANSAC算法,提高算法的执行效率以及提高形状识别的成功率。利用改进的RANSAC算法实现基于形状的数据分割,使得分割区域的形状特征可以用数据的方法描述,从而为点云精简和重建提供理论支撑。

3 问题描述和方法概览

3.1 问题描述

点云分割作为点云数据的一个核心计算,其应用范围相当广泛。例如提取被测对象,即在扫描场景将某一个或多个目标对象从背景中提取出来。此外,针对某单一对象实现点云分割也是很有意义的。例如,针对斯坦福大学著名的扫描数据集bunny、dragon等。将其分割成有意义的部件,从而为数据精简、数据重建服务。本文分割算法的目的就是将数据划分为有意义的部件,其部件的特征可以使用数学方式进行描述。

1996年,Hoover等^[35]提出三维点云分割的形式化描述。点云数据分割的形式化定义中,假设点云数据集用R表示,点云分割将会获得n个R的子集R_i,使得R_i内的数据集具有相同的或者相似的特征。面对不同的点云分割应用需求,数据特征的描述也不尽相同。

设计基于形状的点云分割,需提取数据集中与形状相关的点云属性,计算与形状相关的数据特征。因此,在文献[ 35]的基础上,按照形状分割的要求,对基于形状的点云分割进行了形式化描述。假设点云数据为R,将数据集进行SS分割成子集R_i(i=1,2,…,n),假设f(x)为R_i数据集的形状特征函数,g(x)为规则模型的形状特征函数,则R_i需满足:

1) R_i={xx∈R,f(x)-g(x)<σ}。

2) ∪i=1nR_i=R;数据分割应该考虑的对象是点云数据的全集,而非局部数据。

3) R_i∩R_j=Φ(i≠j,∧j=1,2,…n)。

4) R_i内的数据集在空间上是联通的。

5) R_i内的数据集具有相同形状特征。

6) 不同的两个子集满足特征属性不相同。

3.2 方法概览

SS根据形状信息,完成散乱点云数据的部件分割。首先通过点云数据的几何特征,提取并计算点云数据的形状特征。其次建立形状模型,并提出了形状模型与点云数据之间的模型匹配算法。最后,在此基础上,实现基于形状的点云数据分割,从而为精简和重建提供规则。如图1所示,SS的具体实施步骤如下。

1) 数据预处理。首先对数据归一化处理,通过损失函数,自动过滤离群点,从而避免噪声对分割效果的干扰。其次,实现数据配准并建立规范化的、统一的坐标系;提取点云数据的主成分方向,根据主成分方向建立坐标系,并将点云数据投影到此坐标系中,从而实现数据方向的调整。

2) 初始化分割。沿着主成分方向,依据数据之间的近邻关系,建立初始化分割盒子。如图1所示,产生若干盒子B(p₁,p₂),盒子以对角线距离最远的点对(p₁,p₂)为边界。根据盒子的体积和盒子内点的数量估算点云的密度。

3) 依据B(p₁,p₂)的密度,按照双方向,线性地调整分割盒B(p₁,p₂),并按照B(p₁,p₂)的中心,重新组织点云数据,建立有序的数据集。

4) 建立规则图形的3D形状库。按照3D形状库中的模型,建立与尺度无关的几何特征,包括曲率方差、法向的方向向量的余弦距离等,实现基于几何特征的一致性分割。

5) 建立快速RANSAC算法,从而实现基于3D形状的分割,并提取匹配参数用于指导点云精简和重建等应用。

图 1. 基于3D形状匹配的区域分割方法概览

Fig. 1. Schematic of region segmentation based on 3D shape matching

下载图片 查看所有图片

综上所述,SS首先根据规则形状,建立了形状的模型库作为分割的依据。其次,利用形状库的模型特征g(x),计算g(x)与数据集R_i的几何特征f(x)之间的距离,并实现与尺度无关的一致性分割,从而满足“R_i内的数据集具有相同的属性”的要求。

4 SS分割方法

SS目的是将点云数据按照数据的形状特征相似性进行分割,分割成不同的区域,分割区域的特征可以用规则形状的几何描述来近似表示。本节详细介绍了SS关键步骤,包括数据预处理、基于密度的双向线性八叉树数据组织算法以及参数一致性分割和基于形状约束的分割算法。

4.1 数据预处理

三维激光扫描设备采集获取的数据是一系列距离值的集合,为了实现采集对象的逆向重建,不得不将其转换成点云的数据形式,并变换到统一的坐标系中,使其参与点云分割、点云重建等过程。统一坐标系后的数据,由于数据尺度的不同,给数据处理,尤其是参数调整,制造了很大的困难。因此,首先对数据进行归一化处理,并通过数据过滤技术去除噪声的干扰。此外,通常三维激光扫描设备所建立的坐标系是以设置中心为坐标原点,而数据分割算法是在数据对象自身基础上展开的。为了实现高精度的计算,本文通过PCA提取数据对象的主成分方向,并利用数据投影技术调整数据方向。

4.2 基于密度的双向线性八叉树数据组织方法

点云数据的数据量大,在实现形状特征提取和数据区域分割时,算法执行耗时很大。因此,为了提高算法的执行效率,在已有的八叉树算法基础上,提出了基于密度的双向线性八叉树数据组织方法,并建立数据索引。该方法的目的是发现数据集之间的近邻关系,并利用近邻关系建立数据索引,减少SS执行时间。基于密度的双向线性八叉树数据组织方法按照包围盒组织数据集,设定坐标系的原点为整个数据的中心,按照坐标系三个正交方向以及数据中心建立包围盒。图2为基于密度的双向线性八叉树数据组织方法的示意图,其中种子节点是包含数据中心的节点,在图2中用绿色标出。双向线性八叉树的建立是从种子节点出发,沿着两个线性方向,依据包围盒的密度变化率,进行数据重组。

图 2. 双向线性八叉树数据组织示意图

Fig. 2. Schematic of bidirectional linear octree data organization

下载图片 查看所有图片

假设点云数据集合为R,n=R1。经过预处理后R满足:

R={(xi,yi,zi)x<1,y<1,z<1,i<n}。(1)

针对R建立根节点的包围盒B(l,w,h),包围盒的中心为坐标原点,l、 w、 h分别为包围盒的长、宽、高,则其应满足:

l=maxi=0,…,n-1xiw=maxi=0,…,n-1yih=maxi=0,…,n-1zi。(2)

通过包围盒B(l,w,h),建立八叉树的根节点为N_Rootbox,即:

NRootbox=(x,y,z)(x,y,z)∈B(l,w,h)∧(x,y,z)∈R。(3)

按照八叉树的规则构建下一层子结点。假设子节点的中心坐标表示为N_Centerboxi,子节点相对于父节点的偏移距离设为d,那么d=(d_x,d_y,d_z),并且:

(dxdydz)B=(imod8)-1B,(4)

式中B表示二进制数。

中心坐标N_Centerboxi为

NCenterboxi=NCenterbox「|(i-1)/8⌉-d→×l2H,w2H,h2H→。(5)

子节点N_Nextboxi即为R的一个分割子集R_i,即:

NNextboxi=(x,y,z)(x,y,z)∈Bil2H,w2H,h2H,i=0,1,...,7,(6)

式中H为构建八叉树的深度。

利用八叉树中包围盒的相邻关系,通过双方向线性的方式获取初始化分割数据集。分为以下几个步骤来完成。

1)按照(7)式估算每一个包围盒的数据密度:

P(Ri)=‖Ri‖1f(H),(7)

式中 ‖Ri‖1为集合元素的个数。

2) 根据包围盒的数据密度P(R_i),删除冗余包围盒。其中冗余包围盒即为满足P(R_i)=0的包围盒。

3) 通过双方向线性的方式,合并相邻且密度相近的包围盒。

4) 找到密度值小或区域面积变化率大的区域作为初始化分割的边界盒子。

5) 生成若干初始化分割盒子,将盒子的中心点作为数据的索引。

图3是进行基于密度的双向线性八叉树组织后,边界数据的效果图。其中边界数据在图中用黄色标记标出。

图 3. 边界盒与原图对应位置的对比

Fig. 3. Comparison of the position of the boundary box and the original image

下载图片 查看所有图片

4.3 SS点云分割算法

通过上述步骤,点云数据可以实现噪声过滤、建立投影以及数据索引等预处理。预处理后的点云数据减少了噪声的干扰,并具有相对一致的方向向量。除此之外,利用4.2节建立的数据索引,能够获取数据之间空间距离的相近度,为SS的实施奠定了基础。SS的目的是通过规则形状模型去近似地描述分割区域。因此,SS要求能够用数学方法来表达规则模型,并且这些规则模型能够描述足够全面的分割区域。然而,自然对象是多样的,满足上述要求的规则模型很难找到。

Várady等^[36]根据多数计算机辅助设计/计算机辅助工程 (CAD/CAM) 系统中所提供的曲面设计手段,将曲面分为主要曲面和次要曲面两类。主要曲面决定了对象的主体部分以及基本形状特征,主要曲面包括简单曲面和自由曲面两部分。最常出现的简单曲面为二次曲面;其中,球面、圆柱面和圆锥面被称为自然二次曲面。在实际工程应用中,产品的表面通常是由平面和自然二次曲面构成的,一般二次曲面很少出现。

为了实现满足上述要求的规则模型,主要以自然二次曲面作为点云分割的形状库。SS与其他分割算法最大的不同在于,SS目的是建立分割区域与规则模型之间的对应关系,从而利用规模模型指导点云精简和重建等。因此,SS依赖于形状特征的检测和匹配。现实中,对象表面形状变化多样,极少有规则形状的对象模型。在进行规则形状检测和匹配之前,SS先提取形状特征的关键点,并对对象模型的连续性和参数一致性进行检查和一致性分割,之后利用RANSAC算法确定分割区域,并提取分割区域的形状参数。

4.3.1 模型的一致性分割

与曲面不同,点云数据是散乱的、离散的。点云数据不适合用曲面、曲线的光滑度参数(G⁰~G⁴)来表示。由4.2节得到基于密度的八叉树方法重组后的点云数据,数据集按照空间相邻关系,以B(l,w,h)为单位进行重新组织。然而,将B(l,w,h)内部的数据子集实施重建,重建后的曲面不一定是连续和光滑的。这给该区域的形状特征提取和分析造成了一定的困难。例如,图4(a)中{points1}和{points2},按照基于密度的八叉树方法进行重组。重组后的按彩图展示如图4(b)所示。图4(b)黑色圈内是包含{points1,points2}的盒子(盒子中的数据用绿色标识)。如图4(b)所示,{points1}和{points2}被包含在相同的盒子中。图4(a)的数据被重建之后结果如图4(c)所示。图4(c)中{points1}和{points2}对应于重建区域area1和area2,这两个区域是连续的,两区域的切平面并不连续。因此,其形成曲面后,曲面参数并不一致,而这个不一致性利用4.2节的方法也无法辨识出来。

图 4. 点云参数不一致示例图。(a)点云数据;(b)重组后的数据;(c)曲面

Fig. 4. Diagram of inconsistent point cloud parameters. (a) Point clouds data; (b)reorganized data; (c) curved surface

下载图片 查看所有图片

为了满足准确的基于形状的区域分割,本节计算点云数据特征点,按照特征点和主成分方向建立一致性分割线,并对数据集进行一致性分割。在上述基于密度约束的八叉树数据组织基础之上,依据相邻数据集的法向量夹角,检测分割后模型的连续性和一致性,如图5所示。通过一致性检测后,找到区域分割的关键点,最终实现一致性分割。

1) 一致性分割算法随机选取n个不同的{B_Box}作为B_Boxbase,并通过B_Boxi的N_centerboxi(x,y,z)计算距离值:

Ddistance=‖BBoxi-BBoxbase‖2=‖Ncenterboxi-Ncenterboxbase‖2。(8)

2) 设定扇形的角度α,α∈(0,2π]。按照主方向,利用分割关键点,建立以B_Boxbase为中心的扇形区域,并对扇形区域内的数据投票计数。

3) 算法通过n次投票的统计结果来确定区域的一致性分割,分割结果存储为R={R_i}

Ri={pi(x,y,z)roll(pi)=roll(pj)},(pj∈Ri,i≠j),(9)

式中 roll(pi)表示 pi的投票数。

图4中点云数据按照一致性分割后效果如图6所示。图6中 Ri数据集使用9种不同的颜色循环展示效果图。如图6黑色椭圆标识出的区域,一致性分割后,可以识别出位置相邻而曲面参数不连续的数据集。

图 5. 法式夹角判断连续性

Fig. 5. Inconsistent estimated by angle of normal

下载图片 查看所有图片

图 6. 一致性分割后效果图

Fig. 6. Effect of consistence segmentation

下载图片 查看所有图片

4.3.2 基于RANSAC的形状分割算法

SS算法在一致性分割后,可以获取的分割模型用R_i表示。受RANSAC算法的启发,建立规则形状的数据库,数据库中的形状M可以利用k个变换参数θ_k来表示,M(θ_k)。SS算法为了找到R_i与M(θ_k)的相似性,提取了形状特征,并根据形状特征建立了目标函数C。

1) M_plane的目标函数C。建立模型M的曲率特征。图7为标准二次曲面的曲率特征直方图。 M_plane代表标准的平面模型,即:

Mplane(θk)=θ0x+θ2y+θ3z+θ4。(10)

M_plane与图7中的其他规则模型的曲率特征存在显著的差异,M_plane的曲率绝对值接近于0。因此,通过曲率特征可以辨识出。SS算法通过PCA获得三个主成分方向及其对应的特征值λ₀、λ₁、λ₂,其中最小值为λ₀。分割子集R_i的曲率值c(R_i)可以表示为

c(Ri)=Epλ0pλ0+pλ1+pλ2,(11)

式中p为 pt(x,y,z)pt(x,y,z)∈Ri,E为R_i中各点曲率的均值函数。

R_cur为进行曲率值过滤后的数据集合,即:

Rcur={Ric(Ri)<ε}。(12)

目标函数C为 Rcur1,ε为曲率阈值。

图 7. 规则形状的曲率特征直方图

Fig. 7. Histogram of curvature of regular shape

下载图片 查看所有图片

2) 除M_plane外,其他M模型的目标函数为C。其他M模型的生成和匹配是通过改进的RANSAC算法实现的。RANSAC算法的正确执行在一定程度上依赖于采样点的质量。因此为了提高采样点的质量,避免采样点集中在某一个分割区域,从而造成分割结果陷入局部最优。本文选择{N_centerbox}中的m个最小采样点,m 的大小刚好满足计算θ的个数即可。通过采样点估算模型获取M(θ_k),并建立基于形状的分割子集R_conicoid:

Rconicoid={Ri‖p-M(θk)‖<ζ},(13)

式中p表示为 pt(x,y,z)pt(x,y,z)∈Ri,ζ为用户定义的阈值。

目标函数C为 Rconicoid1。

5 SS算法实验及实验分析

5.1 实验环境及数据集介绍

实验环境:CPU,Intel(R) Core(TM) i5-5200U,频率为2.3 GHZ,系统内存8.0 G。软件平台采用QT5.6.2+PCL1.8+VS2015。数据集使用MySql管理。实验选择三种数据集,分别是单对象、多对象以及模型数据,具体数据信息如表1所示。

5.2 基于形状的分割实验的执行

5.2.1 基于密度的双向线性八叉树数据组织算法的实验

本实验验证了基于密度的双向线性八叉树数据组织算法的可行性。本实验利用数据集Buuny和Dragon建立数据组织{B_Boxi}以及{N_centerboxi},并按

照{N_centerboxi}建立数据索引。其中图8(a)是Buuny数据集的重组结果;图中按照不同的盒子重建组织数据集的结果展示。图8(b)是Buuny数据的{N_centerboxi}展示。图8(c)、(d)是Dragon数据的盒子以及{N_centerboxi}结果展示。

本实验验证了基于密度的双向线性八叉树点云数据组织算法的执行效果。本实验利用八叉树算法建立数据索引如图9(a)所示,八叉树算法产生505个体素(voxel)。计算每个voxel的数据密度,并建立密度直方图如图9(a)所示。利用基于密度的双向线性八叉树点云数据组织算法,算法执行后生成{B_Boxi}集合,集合大小为77,并建立密度直方图如图9(b)所示。

图 8. 基于密度的双向线性八叉树数据组织实验效果展示。(a) Bunny={BBoxi};(b) Bunny: {Ncenterboxi};(c) Dragon={BBoxi};(d) Dragon: {Ncenterboxi}

Fig. 8. Effect of bidirectional linear octree data organization. (a) Bunny={BBoxi}; (b) Bunny: {Ncenterboxi}; (c) Dragon={BBoxi}; (d) Dragon: {Ncenterboxi}

下载图片 查看所有图片

图 9. 数据预处理前、后密度对比图。(a) Voxel;(b) box

Fig. 9. Comparison of density before and after data preprocessing. (a) Voxel; (b) box

下载图片 查看所有图片

图9是数据预处理前、后的密度直方图。图9(b)是对数据进行基于密度的双向八叉树算法后的数据密度直方图。由图9可以看出,图9(b)将密度相近的邻域数据进行重新组织。重组后的数据并没有改变数据的密度分布变化,却减少了索引数,从510个voxel减少到77个盒子。

针对多场景数据,本实验使用基于密度的双向线性八叉树点云数据组织算法,发现满足边界条件的盒子集合采用红色区域标识。效果如图10所示。

采用基于密度的双向八叉树算法应用于多对象的点云数据应用场景,数据密度参数对不相同的数据对象较为敏感。图10所示为应用基于密度的双向八叉树算法,并按盒子的区域面积以及密度值从小到大进行排序,取前500的盒子,如图10(a)所示。从图10可以看出,这些盒子包含了托盘、订书器和手电筒的边界。此外,在图10(a)右上方,对应于图10(b)的墙拐角和墙面的踢脚线处,也存在对数据密度敏感的数据集。

图 10. 多目标场景中不同对象的分界盒子。(a)不同对象的分界盒子;(b)原始图片

Fig. 10. Boundary box for different objects in a multi-object scenario. (a) Boundary box for different objects; (b) original image

下载图片 查看所有图片

5.2.2 SS与其他分割算法对比实验

1) 分割效果对比实验

本实验使用区域增长法、K-means算法、RANSAC算法和SS算法在Bunny和Coal数据集上进行分割,分割效果如图11和12所示。

图 11. Bunny数据集分割效果图。 (a)区域增长法;(b) RANSAC(平面);(c) RANSAC(球体);(d) RANSAC(圆柱体);(e) K-means;(f) SS

Fig. 11. Results of segmentation algorithms using Bunny data set. (a) Region growing; (b) RANSAC (plane); (c) RANSAC (sphere); (d) RANSAC (cylinder); (e) K-means; (f) SS

下载图片 查看所有图片

图 12. Coal数据集分割效果图。(a)区域增长法;(b) RANSAC(平面);(c) RANSAC(球体);(d) RANSAC(圆柱体);(e) K-means;(f) SS;(g)被测对象

Fig. 12. Results of segmentation algorithms using Coal data set. (a) Region growing; (b) RANSAC (plane); (c) RANSAC (sphere); (d) RANSAC (cylinder); (e) K-means; (f) SS; (g) measured object

下载图片 查看所有图片

图11、12的(a)是基于区域增长法的分割效果图。可以看出,算法执行后,曲面的边界点和特征点被划分为一个个单独的分割区域。例如,图11(a)中兔子耳朵及其边缘,就被分割为两个不同的区域。因此区域增长法算法不能保证分割区域在形状上是完整的。

图11、12的(b)~(d)是应用RANSAC分割算法执行后的效果图。同时,本实验还对RANSAC (圆锥)进行了测试,RANSAC (圆锥)算法执行后没有生成满足要求的分割区域,因此算法执行失败。失败的原因与实验数据集自身形状特征有关,由于数据集自身不存在满足或者近似满足“圆锥”形状的数据区域。通过实验表明,使用RANSAC只能针对某一个3D形状进行分析和计算,不能同时获取符合多个3D形状的分割区域。因此,同时处理多规则形状的计算时,该算法不适用。图11(e)是K-means算法的分割效果图,该算法不能实现基于形状特征的分割。图11(f)是SS分割算法实施后的效果图。可以看出,SS算法分割后的区域包含了形状特征点,因此保障了分割区域在3D形状上的完整性。和RANSAC算法相比,SS算法可以对同一对象,同时展开多个形状区域的分割。

2) 分割区域曲面曲率方差对比实验

为了量化基于形状的区域分割算法的执行效果,本实验分别利用K-means算法、区域增长法、八叉树法和SS算法进行分割,并统计了分割区域内曲面的曲率方差。如图13所示。其中区域增长法受算法的参数精度限制,分割区域数量范围为10~50,分割数据集的曲率方差范围为(0.003,0.07)。K-means分割后区域设定为70,曲率方差范围为(0.003,0.07),而八叉树算法分割后数据的曲率方差的变化平稳,曲率方差范围为(0.005,0.07)。SS算法曲面的曲率方差范围为(0.0002,0.06 )。通过对比,SS算法分割后的数据集曲面变化平稳,曲面参数一致性优于其他算法。

图 13. 分割曲面一致性的对比图

Fig. 13. Contrast of consistency among the regions

下载图片 查看所有图片

3) 分割区域形状相似度对比实验

实验验证了SS算法分割区域内数据集的形状相似性。实验采用SS算法,K-means算法以及区域增长算法对Bunny数据集进行数据分割。实验设定分割区域中满足目标形状的数据集的大小与分割数据集的大小比值作为形状的不确定值。形状不确定值范围为[0,1],形状不确定值表明了分割区域与目标形状的相似程度。不确定值越大,说明目标形状与分割区域的形状越接近。从图14可以看出,SS分割算法,形状相似度为1的分割区域在数量上多于其他算法,分割效果优于其他分割算法。

图 14. 分割曲面形状不确定性对比

Fig. 14. Contrast of shape uncertainty among the regions

下载图片 查看所有图片

4) 算法运行时间对比实验

对不同算法的运行时间进行了对比,如图15所示。可以看出,区域增长法的运行时间最短,该分割算法的灵活性差,分割区域数量范围为10~50。K-means算法可以分割成不同大小的数据集,算法灵活性好,但运行时间长。与K-means算法相比,本文算法提高了分割算法灵活性的同时,减少了算法的执行时间。

图 15. 分割算法执行时间对比

Fig. 15. Contrast of algorithm running time

下载图片 查看所有图片

6 结论

从三维形状分析的角度出发,对点云对象实施分割,使得分割后的数据包含3D形状信息,而该形状信息可用于指导点云数据的精简和重建,从而提高点云数据的计算速度和准确度。为了达到点云分割的要求,需定义3D形状特征,并在此形状特征基础上实现点云数据分割。由于点云数据的散乱性,通过数据之间的近邻关系和数据密度,提出了基于密度的双向线性八叉树的点云据组织算法,利用线性八叉树的结构重新组织点云数据;重组后的数据集使用{B_Boxi},{N_centerboxi}建立数据索引。实验证明该算法有效降低了数据的散乱性,使得{B_Boxi }内部数据分布均匀、一致;尤其是当算法在应用于多对象的场景中时,算法对不同对象之间的分割区域较为敏感,对不同的对象有较好的区分度。其次,为了使分割后的数据在形状上相似,对重组后的点云数据展开一致性分割,使得分割区域内数据的曲面特征相似或相近,能够识别出曲面变化率较大的交界区域。最后,建立规则点云库,在一致性分割的基础上根据点云库中的3D形状,进行基于形状的数据分割,并提取出与规则库中的形状相似的分割区域及其规则形状参数。

提出的基于形状的区域分割算法可以有效提取出被测对象的形状特征。分割区域内的数据具有一定的形状相似度。因此,在对点云精简和压缩过程中,可以通过形状模型的特征,有针对性地识别出精简部分。同时,形状参数可以作为先验知识,提高曲面重建的效率。

本文算法存在一定的局限性。建立的规则形状库有限,分割区域与形状的映射关系少。此外算法的分割是以点云的位置关系作为依据而实施的,并未涉及到颜色等其他信息。今后的工作:1) 扩展3D规则形状模型,使得形状更为丰富,与真实的被测对象更接近,提高分割的精准度;2) 为了减少算法的执行时间,将在分割算法的并行化方面进行优化;3)基于形状的3D点云分割算法在点云精简和重建等应用上进行更多的探索和尝试。