高斯函数约束下的多判别参数散乱点云边缘检测

杨文桥， 郑力新， 朱建清， 董进华， 郑义姚， 刘颖， 汪泰伸

(1. 华侨大学 工学院， 福建 泉州 362021； 2. 华侨大学 工业智能化与系统福建省高校工程研究中心， 福建 泉州 362021)

边缘检测最先是针对二维数字图像提出的，目的是对图像特性发生变化的位置进行识别与检测[1].作为图像分析和计算机视觉的重要研究领域，边缘检测受到众多学者的关注，现已发展出多种成熟的边缘检测算法.随着三维激光与计算机技术的发展，人们更多地通过激光技术获取目标的三维点云数据，得到更好的现实空间特征.点云的几何特征主要体现为扫描物体的点、线、面、体[2]，这些特征在点云精简、点云配准、点云分割等方面具有重要的意义.

不同点云数据模型的边缘特征提取方式也不相同，大致可分为基于网格和基于散乱点云的特征提取方式[3-4].基于网格的特征提取先将点云进行网格化处理，通过遍历三角化后的点云及阈值约束，最终获得点云的边缘特征.其中，最著名的三角剖分(delaunay)算法形成的三角网络简洁、直观，但在三角化的过程中，需要评估点云之间的欧氏距离，如果欧氏距离选择不合适，将会产生孔洞.此外，该方法若应用于三维点云，需要使用每个点云的法向确定投影方向，故该算法更适用于均匀、平滑的点云[5].基于散乱点云的特征提取主要从该类型的点云中提取一定规律的点、线、面等特征，所以更加注重局部特征.Song等[6]将点云每一点的向量与k邻近点的向量做均方根，以此作为提取边缘特征的标准，这种方法虽然很好地体现了点云的每个点与其邻近点法向之间的关系，但在边缘提取的结果中会检查出边缘邻近的非边缘点.Han等[7]利用边界点法向异于非边界法向的特点保留边缘特征，但得到的边缘与非边缘部分密度相同.陈龙等[8]提出多参数约束的特征提取算法，通过法向、曲率及欧式距离判断特征点.文献[9-10]采用主成分分析(PCA)和法向提取边缘特征点.基于此，本文提出一种基于高斯函数的多判别参数散乱点云边缘检测算法.

1 算法原理及方法

散乱点云边缘特征提取是以点云数据各点法向、曲率及k近邻欧式距离为基础，在高斯函数的约束下提取边缘信息，具体有以下3个步骤.

步骤1定义散乱点云数据P={pi(xi,yi,zi)|i=1,2,…,N}，构建点云拓扑结构.

步骤2定义基于k近邻计算样点pi的曲率为Ci,该点与k近邻重心的距离为di，该点与k近邻点的最远距离为dmax，该点与k近邻各点单位距离夹角均值为θi.

图1 散乱点云边缘特征提取流程图Fig.1 Flowchart of edge feature extraction of scattered point clouds

步骤3根据以上4个参数定义样点特征参数wi，结合高斯函数定义单侧σ原则的特征判别阈值W+σ，通过比较点云每点的特征参数与特征判别阈值的大小，最终确定特征点.

散乱点云边缘特征提取流程图，如图1所示.

1.1 点云拓扑关系的建立

通过三维测量设备获取的点云数据数量大、分布不均匀，不具有实体网格下的几何拓扑关系，所以在提取点云边缘特征前，需要有序地组织点云，以便查询每个点的k近邻.搜索k近邻主要有八叉树、k-d树及空间网格[11]等3种方法.空间网格法的算法简单，但不适用于非均匀点云；八叉树[4,12]和k-d树[4]采用的空间索引方式是自顶向下逐级划分的，但八叉树结构在搜索过程中会出现冗余，对于数量较多的点云，占用的存储空间较大，而k-d树不会浪费空间，搜索时间相对较少，且不受点云密度的影响.因此，采用k-d树建立点云数据之间的拓扑结构.

1.2 特征判别参数的建立

在前人研究[13-16]的基础上，提出基于高斯函数的多判别参数散乱点云边缘检测算法(文中算法)，该算法利用样点pi(i=1,2，…,N)的相关曲率、法向、重心及密度等，综合判断其是否为特征点.pi和邻近点的夹角及该点的曲率反映其周围曲面弯曲的程度；pi到该点领域重心的距离反映该点在k近邻区域内的相对位置；pi与k近邻点之间的距离反映其周围点云的密度.

1.2.1 法向及曲率的估计 选择基于局部表面拟合方法[17]对点云法向进行估计.基于局部表面拟合方法是对点云中的每一个点pi(i=1,2，…,N)，获取与其最近邻的k个点，利用这些点，通过最小二乘法拟合一个局部平面，使该平面最佳拟合数据，方法简单快速，且可以求解曲率.

对点pi(i=1,2，…,N)拟合的平面表达式为

Ax+By+Cz=D

.

(1)

式(1)中：A,B,C分别为平面方程的系数；x,y,z为坐标轴；D为常量.

(2)

将目标函数转化为求解对应的对称半正定矩阵M的特征值，M也被称为协方差矩阵，其表达式为

(3)

通过PCA方法求解矩阵M，得到M的3个特征值λ0，λ1，λ2.若λ0≥λ1≥λ2，则λ2对应的特征向量ni为点pi的法向.此时，曲率Ci可表示为

Ci=λ2/(λ0+λ1+λ2)

.

(4)

定义pi的k邻近点mj(j=1,2，…，k)的法向为ni,j(j=1,2，…，k)，则该点k近邻夹角的均值为

(5)

当点云密度不均匀时，在k近邻范围内,可能出现间隔较远，但当夹角较大的情况，为避免误判[18]，使用两点的欧式距离作为特征识别的权值，以降低距离对特征识别的影响，则法向夹角均值公式可改为

(6)

式(6)中：di,j为点pi与第j个k近邻点的欧式距离.

由Ci，θi的表达式可知：当Ci越大时，pi为特征点的可能性越大；同理，当θi越大时，pi所在的曲面就越尖锐.

1.2.2pi到k近邻重心的距离与k近邻的最远距离 点云边界是曲面模型的重要特征，但在点云获取的过程中，由于物体表面的特点，如反射、局部不遮挡等，导致获取的模型数据局部丢失，最终点云可视化中会出现孔洞[19].目前，国内外学者已针对边界检测进行了大量的研究.文献[20]利用pi邻域内的三维位置梯度几何信息，在邻域点构成的梯度协方差下，判断边界点，但该方法不适合散乱点云.文献[21]根据pi到重心的距离与样点到最远距离的比值识别边界点，这种方法对平滑边界点识别效果较好，但对尖锐点的识别效果不佳.为解决这一问题，可将曲率与法向作为点云边界特征提取的依据，以其为尖锐曲面边界点提取的主导因素，并以文献[21]方法作为识别平滑边界的因素.

定义点pi的k邻近重心οi为

(7)

点pi到k近邻重心的距离di为

di=‖pi-οi‖

.

(8)

点pi与k近邻的最远距离dmax为

dmax=max{di,j|j=1,2,…,k}.

(9)

1.3 特征点的提取

基于单位距离法向夹角的准则可以很好地弱化非均匀点对判别结果的影响；基于曲率的准则可以提取尖锐边缘特征；基于样点pi到重心的距离与k近邻最远点距离的比值可以保留平滑边界.综合以上优点，通过加权算法将3种判定准则应用于特征点的判定中，以获得更好的特征点提取效果.

通过获取点云数据中任一点pi的曲率Ci、该点单位距离k近邻夹角均值θi、样点pi到k近邻重心的距离di及最远距离dmax，计算数据点的判别参数wi为

(10)

式(10)中：α为曲率控制系数；β为法向夹角控制系数；γ为点pi的k近邻重心控制系数.

整个点云数据的特征阈值W为

(11)

式(11)中：N为点云数据量；η为点云特征点数控制系数(一般取值为1).

2 实验结果与分析

文中算法的硬件平台为Inter(R) Core(TM) i5-7300HQ 2.5 GHz，16 G内存；操作系统为Win 10；软件环境为Visual Studio 2017；开发语言为C++；测试数据为斯坦福大学modelnet40_normal_resampled图片库中的airplane模型、chair模型和bunny模型.从边缘检测效果、特征点保留数量和运行时间等3个方面，分别使用文中算法、法向算法、曲率算法、文献[8]算法及文献[18]算法对3种模型进行算法对比.

2.1 数据说明

airplane模型和chair模型的点云数量为10 000点，bunny模型的点云数量为35 946点.3种原始模型，如图2所示.

(a) airplane模型 (b) chair模型 (c) bunny模型图2 3种原始模型Fig.2 Three original models

airplane模型具有闭合特征(如机身)及非闭合特征(如螺旋桨)，点云密度不均匀，此外，还具有尖锐棱线一样的特征.airplane模型由于本身特征强弱不同，类型也不相同，特征提取较难.chair模型较为简单，具有清晰的边缘特征，点云密度不均匀，边缘特征相对容易提取.bunny模型以弱曲率特征为主，属于闭合类点云，不同部位点云密度差异较大，故点云边缘不易检测，相较于前两种模型，该模型的点云密度较大.

2.2 算法对比及分析

2.2.1 airplane模型的算法对比 airplane模型的参数设置为α=5，β=2，γ=1.分别采用法向算法、曲率算法、文献[8]算法、文献[18]算法和文中算法提取边缘特征，特征点的保留数量分别为3 611，4 437，3 606，6 823，3 394点；运行时间分别为7.501，7.345，8.945，9.754，8.711 s；每1 000点的运行时间分别为0.481,0.604,0.403,0.700,0.390 s.

airplane模型边缘检测效果对比，如图3所示.由图3可知：文中算法与法向算法、文献[8]算法的边缘提取效果的差别不大.这3种算法对螺旋桨尖锐棱线和密度较小区域的边缘提取效果较差，但文中算法特征点的保留数量少于法向算法与文献[8]算法，节省了存储空间，精简了特征点，这为后期通过特征进行检测及配准做好准备；曲率算法和文献[18]算法的边缘提取效果优于文中算法，但前两者提取的特征不够精简，包含大量非特征点，特别是文献[18]算法对机身和机翼等特征弱曲率点不够敏感，且耗时最长.

(a) 法向算法 (b) 曲率算法 (c) 文献[8]算法 (d) 文献[18]算法 (e) 文中算法图3 airplane模型边缘检测效果对比Fig.3 Edge detection effect comparison of airplane model

2.2.2 chair模型的算法对比 chair模型参数设置为α=0，β=6，γ=0.分别采用法向算法、曲率算法、文献[8]算法、文献[18]算法和文中算法提取边缘特征，特征点保留数量分别为3 841，3 685，5 982，6 798，4 938点；运行时间分别为8.879，8.598，10.292，11.125，9.934 s；每1 000点的运行时间分别为0.433,0.429,0.581,0.611,0.497 s.

chair模型边缘检测效果对比，如图4所示.由图4可知：法向算法与曲率算法可以提取强特征边缘，但这两种算法对弱边缘特征不够敏感，椅面、靠背的边缘特征有不同程度的缺失，而文中算法在边缘提取效果上优于法向算法和曲率算法，能够很好地保留靠背及椅面边的边缘特征；文献[8]算法和文献[18]算法虽然对弱边缘特征提取效果较好，但对非特征点存在误判，如靠背弱曲率非特征点的误判导致提取的特征点不够精简，而文中算法可以很好地将边缘特征与非边缘特征进行区分，且提取的特征点数量较少，所用时间相对较少.

(a) 法向算法 (b) 曲率算法 (c) 文献[8]算法(d) 文献[18]算法 (e) 文中算法图4 chair模型边缘检测效果对比Fig.4 Edge detection effect comparison of chair model

2.2.3 bunny模型的算法对比 bunny模型的参数设置为α=10，β=0，γ=0.分别采用法向算法、曲率算法、文献[8]算法、文献[18]算法和文中算法提取边缘特征，特征点的保留数量分别为8 183，9 359，8 064，6 665，6 741点；运行时间分别为23.238，24.562，24.373，24.549，24.054 s；每1 000点的运行时间分别为0.352,0.381,0.331,0.261,0.280 s.

bunny模型边缘检测效果对比，如图5所示.由图5可知：文中算法与法向算法、文献[8]算法及文献[18]算法的边缘提取效果差别不大，对bunny的尾巴、脚和耳朵等特征部位提取较好，对身体的弱特征区域提取较差；在保留相同特征效果的情况下，文中算法运行时间最少，特征点保留数量与文献[18]仅相差76点；在提取弱边缘特征时，文中算法比曲率算法差，但数据更加精简，可避免非特征点的误判，而曲率算法提取的特征包含一定数量的非边缘特征点，如bunny的腿和背部上的非特征点.

(a) 法向算法 (b) 曲率算法 (c) 文献[8]算法 (d) 文献[18]算法 (e) 文中算法图5 bunny模型边缘检测效果对比Fig.5 Edge detection effect comparison of bunny model

综上所述，在保证边缘特征(主特征和次特征)基本相同的情况下，文中算法特征点提取数量大幅减少或至最少，这有利于缩减计算和存储内存，提高运行效率；在保证主轮廓(主特征)相同的情况下，相较于文献[8]及文献[18]算法，文中算法的特征提取时间最少，降低了时间成本.综上所述，文中算法在提取特征上具有一定的优势.

3 结束语

提出一种基于高斯函数的多判别参数散乱点云边缘检测算法.利用曲率和法向提取尖锐边缘，采用文献[21]方法提取平滑边缘特征，结合高斯函数单侧σ原则减少特征点数量.实验结果表明：该算法能够对点云不同部位特征进行划分与提取，在特征点检测上更加精简、速度更快，在边缘检测、目标识别和基于点云特征配准中具有一定的实用价值.然而，该算法也需进一步改进，当点云离散程度较大，点云较稀疏时，边缘提取容易出现孤立点和孔洞，提取效果有待加强.因此，将在此算法基础上对孤立点检测进行进一步研究.