一种新的三维点云兴趣点提取算法

2023-04-07郭建华吕常魁

计算机应用与软件 2023年3期

郭建华吕常魁

(南京航空航天大学机电学院江苏南京 210016)

0 引言

与2D视觉相比,3D视觉具有信息更为丰富全面、光照变化鲁棒性强、目标空间信息更为直观准确等优势。随着3D数据获取传感器技术的迅猛发展,以及机器学习、机器视觉等领域算法技术的进一步成熟,基于3D视觉的物体识别、场景理解等方面研究热度与年俱增,其成果在自动化作业、工业检测、机器人导航、虚拟现实、人机交互、遥感测量等领域逐渐得以普及应用[1-3]。

兴趣点(Interest Point)也称关键点(Key Point),兴趣点提取是3D视觉核心基础技术之一。3D点云数据兴趣点提取即通过一定的检测算法,从目标点云数据中提取稳定的、标志性的特征点,为后续的物体跟踪[4]、目标配准[5]、目标建模[6]、空间结构描述[7]、物体识别[8]等高层视觉算法服务。

针对三维模型兴趣点的提取,研究人员做了大量的相关工作。Lee等[9]提出了Mesh Saliency算法,模型中每个顶点的显著性特征是基于由高斯滤波器加权得到的平均曲率,根据所有模型顶点的显著性特征的局部最大值选择兴趣点。Castellani等[10]提出的Salient Points算法则直接对模型顶点的三维位置进行高斯滤波,其显著性特征取决于经高斯滤波后的顶点与原模型顶点的位移量。Novatnack等[11]提出了尺度依赖(Scale-Depended)的特征检测方法SD-corner,将三维网格嵌入到二维平面,在二维平面上进行特征检测后再将特征映射回三维模型,最终识别出模型特征角点,该角点即为兴趣点。Sun等[12]提出基于热量扩散理论的多尺度特征描述算法HKS(Heat Kernel Signature),在模型上采用Laplace-Beltrami算子计算其热核特征。Sipiran等[13]将经典的Harris角点检测算法扩展到三维上,通过在当前顶点及其邻域上构建局部坐标系并拟合二次曲面来计算该顶点的Harris响应,之后根据局部最大原则选择兴趣点。Godil等[14]也提出了3D Sift算法,该算法首先将3D模型体素化,然后通过高斯差分(Difference of Gaussian,DoG)检测极值点,最后选择合适的极值点后将其映射到原模型上作为兴趣点。这些算法中常用于点云兴趣点检测的算法是3D Harris和3D Sift算法。为了评价这些算法的性能,Dutagaci等[15]提出了一种评估策略,将算法检测到的兴趣点集与人工标注的真实兴趣点集相比较。评估结果表明,3D Sift算法会检测到许多偏离物体的重要位置的兴趣点;HKS算法检测的兴趣点过少;3D Harris 、Mesh Saliency、SD-corners、Salient Points等算法则会漏检一些重要兴趣点。

为了设计一种更加符合人眼视觉注意力机制的兴趣点提取算法,提出一种新的三维点云模型兴趣点提取算法。参考人眼识别物体的一些特点,我们认为,锥体是物体边角的基元特征,点云物体局部几何特征均可近似表达为该局部区域的锥度特征:对于物体的型面特征,平面可认为是局部锥度特征为0的特征体,曲面则可认为是由等值或不等值的局部锥度特征集组成的特征体;对于物体的边角特征,物体的边缘、棱角、拐角等,均可认为是系列假想椎体(面)的组合,这些椎体(面)可以是规则的,也可以是不规则的(图1)。基于这个思想,本文:

1) 提出一种新的三维点云数据点特征的表达算法,并命名为突出度特征(Saliency Degree,SD)。该特征算法计算点云数据中心点与其k近邻归一化向量集的平均合向量,搜索归一化向量集中与合向量最大的夹角,应用该夹角与平均合向量二范数联合表达突出度特征,来描述三维点云物体的局部区域的锥度特征。

2) 提出一种新的兴趣点选取算法。算法全局与局部相结合,分为三步:(1) 基于全局阈值的一次筛选:在突出度特征服从高斯分布的假设下,设置经验阈值为均值与标准差的和,突出度特征大于阈值的点为初始兴趣点。(2) 基于局部最大原则的二次筛选:基于初始兴趣点,选取当前点及其k近邻点中具有最大突出度特征的点,作为代表当前点的候选兴趣点。每次候选兴趣点提取操作后给予该兴趣点1次投票。(3) 基于投票数的最终筛选:设定票数阈值,按得票数量进行最终兴趣点筛选。

(a) 平面 (b) 曲面

1 算法描述

1.1 计算点的突出度特征

设点云数据集P={pm,m=0,1,…,n-1},当前点为Pi,首先使用KD-Tree算法[16]获得其k个近邻点,设其近邻点集合为N(i),则分三步计算该点的突出度特征:

第1步计算点Pi与其近邻点的平均合向量,对于N(i)中每一点Pj,设点Pj指向当前点Pi的向量为vji,将vji归一化为单位向量uji,获得向量集V={uji,pj∈N(i),j≠i},设当前点Pi的k个近邻点的平均合向量为vi(如图2所示),则:

图2 合向量示意图

第2步计算点Pi的局部锥度特征,将vi归一化为单位向量ui,分别计算V中各向量与ui的内积(即V中各向量与ui的夹角余弦值),获得内积集合I={cji,pj∈N(i),j≠i}。

选择I中的最小值ci:

ci为点Pi与其近邻点的差向量中偏离其平均合向量的最大夹角的余弦值(见图2)。称ci为点Pi的局部锥度特征(Local Conicity,LC)。ci是一个重要的特征,其大小近似反映了锥面锥度的大小,其正负则反映了锥面的外凸或内凹特征,如果ci>0表示Pi点附近区域具有外锥面特征,如果ci<0则表示Pi点附近区域具有内锥面特征。

第3步计算点Pi的突出度特征,定义点Pi的突出度特征(Saliency Degree)Sdpi为:

1.2 选择兴趣点

按上述步骤计算所有点的Sd值后,从全局和局部两方面比较各点Sd值选择最终的兴趣点。

首先计算全局阈值,确定初始兴趣点。由于兴趣点是那些几何特征比较明显的点,所以先从全局考虑,选择那些突出度特征值(Sd)较大的点作为初始的兴趣点。假设三维点云物体各点Sd值近似服从高斯分布N(μ,σ2),计算整个点云中Sd值的均值μ与标准差σ,定义全局阈值t为:

t=μ+σ

(4)

获得初始的兴趣点集合:

S1={pm|pm∈P,Sdpm≥t}

(5)

然后按局部最大原则,确定候选兴趣点。对于S1中每一点pm,搜索其自身及其k个近邻点中Sd值最大的点,作为该点的代表兴趣点。pm的代表兴趣点表示为:

将所有代表点作为候选兴趣点集合S2。易知当pm的Sd值在其近邻区域中最大时,pmax(m)即为pm自身。而且会出现多个点拥有同一个代表点的情况,一个点被当作代表点的次数越多,说明该点在其局部区域内越重要。在得到pm的代表兴趣点的同时,将点pmax(m)的票数vote(pm)加1,投票之前,先将所有初始兴趣点pm的票数vote(pmax(m))设置为0。

最后我们根据得票数量进行最终兴趣点的筛选,与物体表面非特征候选兴趣点相比,物体的边缘、边角、拐角等部分的候选兴趣点一般具有较高的得票。根据经验,将兴趣点票数阈值设为k/5,其中k为近邻点的个数。则最终兴趣点集合S表示为:

1.3 算法流程

综上所述,算法具体步骤如下:

(1) 对于点云数据P,搜索每个点的k近邻,构建邻接矩阵An×n,计算得到向量差矩阵Bn×n×3。

(3) 计算近邻差向量的平均合向量二范数张量Vn×1,及合向量归一化矩阵Un×3。

(5) 计算Vn×1与Cn×1的Hadamard积,得突出度特征张量Sdn×1。

(6) 获得Sd张量的均值与标准差,确定阈值t←μ+σ。

(9) 搜索S″中vote值大于k/5的点,获得兴趣点集张量S。

2 基于单位圆的点云突出度相关特征模拟

由于本文算法首先将点云数据每一点与其近邻的差向量归一化后再进行计算,这里以分布于单位圆上的点来模拟当前点的近邻点,以该单位圆圆心表示当前点,此时差向量均为单位向量。

采用两种方式对算法性能进行了模拟:

图3 方法1示意图

图4 方法1模拟结果

方法2:仍以1°为步长,选取一差向量为0°起始边,分别计算0°～359°锥角下方法1中所列的参数。计算某一锥角θ的系列参数值时,以在单位圆上按1°步长均布的360个点为候选近邻点,设定近邻数k,在确定了锥角θ的起始、终止向量边(近邻点)后,在锥角θ所包络的候选点中随机选取k-2个近邻点,由于选取过程随机,故极有可能产生点的复选现象,进而有可能导致近邻点分布的极度不均(图5),这有利于检验算法的鲁棒性。模拟结果如图6所示。

图5 方法2示意图(k=10)

图6 方法2模拟结果

由图3可看出,随着锥角θ的增大,当前点位置的局部锥度在减小,其对应的突出度特征值也在减少(见图4),当θ接近360°时,表示当前点位于锥度为0的平面,图4中算法的各项参数值也达到最小。图6显示,在近邻点分布极度不均的情况下,算法的各项参数对应的曲线会有较大的波动,但是所有曲线的整体趋势仍与原曲线相同,其中,突出度特征值对应的曲线所受影响最小。

由两种方法的模拟结果可以看出,本文算法所描述锥度特征较为准确。方法2的随机模拟中,在近邻点分布极度不均的情况下,大多数情况下仍能获得正确的特征描述结果。

3 点云物体兴趣点检测实验

3.1 算法评价模型

为评估三维点云兴趣点提取算法的性能,采用Dutagaci等[4]提出的评价模型。将算法检测到的兴趣点集与人工标注的真实兴趣点集相比较,若两者越接近,则算法的性能越优秀。通过缺失率(False Negative Errors,FNE)和误报率(False Positive Errors,FPE)两个指标来衡量算法提取的兴趣点集与真实兴趣点集的接近程度。

以真实兴趣点集为基准,计算算法的缺失率(FNE)和误报率(FPE)。由于算法提取的兴趣点与对应位置的真实兴趣点往往存在小的位置偏差,即相互近邻但不是同一点。鉴于此,对模型中的真实兴趣点g,定义容忍半径系数r,则点g的近邻点集合Gr(g)为:

Gr(g)={p∈M}|d(g,p)≤rR

(8)

式中:R为点云模型的半径(三维点云模型中相距最远的两个点的距离的一半);d(g,p)为点g和点p之间的距离。若点云中某点a被算法提取到,a与真实值中点g的距离最近,且a∈Gr(g),则表明该算法成功提取到真实兴趣点g。

设在容忍半径系数为r时,算法A成功提取到的真实兴趣点数量为NC,真实兴趣点的个数为NG,算法提取到的兴趣点的总个数为NA,则算法A的缺失率(FNE)为没有被算法所提取到的真实兴趣点的个数与真实兴趣点个数的比率:

算法A的误报率(FPE)为算法提取的非真实兴趣点的个数与算法提取的所有兴趣点个数的比率:

3.2 实验结果分析

选取普林斯顿大学视觉与机器人实验室发布的3D点云数据集ModelNet40[17]中的部分物体进行测试。该数据集含40个类别11 308个3D点云模型,选择其中的四个模型,飞机、椅子、电脑和人。

参照Dutagaci等提出的方法[4],组织22名志愿者对选取的点云物体进行了真实值标注。由于志愿者对三维模型兴趣点标注具有较大的主观性,不同的志愿者可能会标注同一个位置而非同一个点,为综合考虑各个志愿者的意见,得到最符合人类视觉的兴趣点集,将相互距离小于0.04r的兴趣点(由不同志愿者标注)合并为一组,若组中兴趣点被标记的总次数少于7,则丢弃该组。在兴趣点组中选择一个中心点设置为该组的代表兴趣点,该中心点到组中其余兴趣点之间的距离之和最小。将这些代表点作为最终的人工标注的真实兴趣点集(Ground Truth)。

基于真实兴趣点集,对本文算法以及常用的点云兴趣点检测算法3D-Sift和3D-Harris算法进行了测试,检测效果如图7-图10所示,依次为Ground Truth和各算法在飞机、椅子、电脑、人模型上所提取的兴趣点。

(a) Ground Truth (b) 3D-Sift算法

可以看出,Ground Truth中绝大多数的点都位于物体边缘和拐角位置,如飞机机翼、椅子和电脑的边缘和顶点处、人的头部和脚部的位置,本算法(Sd)基本能够全部检测到这些兴趣点,而3D-Sift和3D-Harris算法对于这些兴趣点却多有漏检的情况。由于这些点的位置的锥度特征明显,突出度特征值比较大,因而容易被本文算法检测到。少量真实兴趣点位于物体表面比较平缓的位置,如飞机机身、电脑屏幕和椅子靠背中央处的点,这些点的锥度特征并不明显,但是在表达整个物体结构时具有重要作用,由于其突出度特征值比较小,本文算法并不能够很好地检测到。

图11-图14依次显示了各算法的兴趣点提取性能在四个模型上的定量比较结果。FNE反映算法提取真实兴趣点的能力,其值越低,表明算法提取到的真实兴趣点就越多,提取能力越强。而FPE反映算法提取真实兴趣点的错误率,其值越低,表明算法提取到的非真实兴趣点越少。随着容忍半径系数r的增大,真实兴趣点能被检测到的范围扩大,因此各算法的FNE和FPE值也随之降低。

(a) 缺失率(FNE)

(b) 误报率(FPE)图11 各算法在飞机模型上的定量比较结果

(a) 缺失率(FNE)

(b) 误报率(FPE)图12 各算法在椅子模型上的定量比较结果

(a) 缺失率(FNE)

(b) 误报率(FPE)图13 各算法在电脑模型上的定量比较结果

(a) 缺失率(FNE)

可以看出,本文算法(Sd)的FNE曲线要明显低于3D-Sift和3D-Harris算法。这是由于绝大多数真实兴趣点都位于物体的边缘和拐角处,而这些点能够全部被本文算法检测到,只有极少数锥度特征不明显的兴趣点被本文算法漏检,3D-Sift和3D-Harris算法漏检的兴趣点则比较多。而且在多数情况下本文算法的FPE值也要略低于3D-Sift和3D-Harris算法。因此,整体上本文算法要明显优于3D-Sift和3D-Harris算法,所提取的兴趣点与Ground Truth更接近,更符合人类视觉。

4 结语

本文提出锥体为三维物体边角基元特征的思想,基于点云数据点与其k近邻归一化向量集的合向量,构建突出度特征值,对点云物体的局部锥度进行描述。将全局阈值与局部最大原则相结合,应用投票方式进行趣点的选取。实验结果表明,本文算法能够较好地检测到大部分真实兴趣点(位于物体边缘和拐角处的兴趣点),算法整体性能要优于3D-SIFT和3D-Harris算法,所提取的兴趣点与Ground Truth更加接近。

未来主要考虑开展两个方面的工作:(1) 优化算法,有效提取到锥度特征不明显但在表达整个物体的结构时具有重要作用的兴趣点;(2) 借鉴人眼视觉边缘感知机制,设计兴趣点连接算法,以提取物体边缘轮廓、纹理等特征。