一种三维点云采样方法

1.本发明属于模式识别和人工智能技术领域，特别涉及一种三维点云采样方法。


背景技术：

2.随着激光扫描技术的大力发展，三维点云数据已广泛应用于计算机视觉机器人、三维建模和自动驾驶等领域。三维点云采样的目的是利用相关方法对三维点云数据进行压缩，提取点云中能够描述目标形状的关键点，降低原始点云规模，从而提高计算效率。
3.现有的三维点云采样方法主要有启发式采样方法和基于学习的采样方法两大类。基于启发式的采样方法主要包括：(1)最远点采样(fps)，通过不断计算已采样点与点云中其他点的最短距离，选择距离最远的点进行采样；(2)反密度重要性采样(idis)，根据每个点的密度进行排序，选择密度低的点进行采样；(3)随机采样(rs)，随机选取点云中的点进行采样；(4)体素下采样(vfd)，将点云进行空间体素划分，在每个单位体积内进行采样。基于学习的采样方法主要包括：(1)基于生成式采样(gs)，通过学习生成一个子集来近似表征原始的点云；(2)基于策略梯度下采样，将降采样操作表示为一个马尔科夫决策过程，旨在学习到一种有效的降采样策略。
4.三维点云采样的难点在于需要兼顾所保留点的精度的同时，尽可能减少采样后的点数，以提高后续三维点云处理的效率。最远点采样(fps)每次需要重新计算被选点集与其他所有点的距离，并选择距离被选点集最远的点加入被选列表，是目前被广泛使用的采样方法，如pointnet++、pointcnn、pointconv等。该方法能够保证采样点的平均分布，但其采样过程耗时大，其计算代价较高。反密度重要性采样(idis)对噪声比较敏感。随机采样(rs)的采样速度快，内存占用较少，但其易造成关键点的遗漏。体素下采样(vfd)与空间分布有关，对外点不敏感。基于生成式采样(gs)的验证阶段需要将生成的子集与原始点云进行匹配，其计算量较大。基于策略梯度下采样(pgs)对于点云较多的点云，其网络难以收敛。目前基于机器学习的点云采样方法其计算资源消耗较大，训练时间长，难以学习到有效的采样策略。


技术实现要素：

5.本发明的目的在于克服现有技术中存在的缺陷，提供一种三维点云采样方法。
6.本发明提供了一种三维点云采样方法，包括以下步骤：
7.s1、对于待采样的原始点云每个点表示为每个点表示为n0为原始点云的点数，对所述原始点云进行预处理，得到处理后的点云p＝{p1,p2,...,pn}；
8.s2、计算点云p中各点的平均距离,得到点云p中各点的平均距离集合d＝{d1,d2,...,dn}；
9.s3、根据点云p中各点的平均距离集合d，对各点按平均距离从小到大进行排序，作
为初始备选点云令初始采样点云
10.s4、选取备选点云中平均距离最小的点将所述平均距离最小的点加入至采样点云o
l
中，即并将及其所有nj个近邻点从备选点云中删除；
11.步骤s5：判断采样点云o
l
中的点数是否达到设定点数，若小于设定点数，则转至步骤s4；否则，转至步骤s6；
12.步骤s6：输出采样点云o
l
。
13.进一步的方案为，所述s1中点云数据的预处理栅格采样和kd-tree处理，包括：
14.s1.1：设置栅格采样中栅格尺寸、kd-tree的维度k
dim
＝3和选取的邻近点数k，平均距离的计算半径r，采样点云的点数n1，其中kd-tree是一种对k
dim
维空间实例点进行快速存储以便于对其快速检索的树形数据结构，在三维点云中空间维度为x、y、z三个维度，因此k
dim
设置为3。
15.s1.2：栅格采样；
16.利用栅格采样方法，根据栅格尺寸，对原始点云q进行栅格采样，获得栅格采样后的点云p＝{p1,p2,...,pn}，其中n为栅格采样后点云的点数；
17.s1.3：建立栅格采样后点云p的kd-tree；
18.根据kd-tree的维度k
dim
＝3，建立栅格采样后点云p的kd-tree。
19.进一步的方案为，所述s2中平均距离的计算过程为：对于栅格采样后点云p中各点pj(j＝1,2,
…
n)，根据平均距离的计算半径r和栅格采样后点云p的kd-tree，计算以点pj为中心、r为半径的球域δ(pj,r)＝{s||s-pj||≤r}内点pj的所有nj个近邻点采用公式(1)计算pj平均距离dj，进而得到点云p中各点的平均距离集合d＝{d1,d2,...,dn}，所述公式(1)为：
[0020][0021]
与现有技术相比，本发明的有益效果在于：
[0022]
本发明在基于栅格采样的预处理基础上，将各点在设定邻域内的平均距离作为采样标准，平均距离越小，被选为关键点的概率越大，并将已采样点的邻域所有点变为非关键点，邻域点个数为0则被当作异常点，将其平均距离值设为较大常数。本发明旨在保证采样中提高关键点的选取概率，降低异常点的影响，从而最大程度地减少采样误差，节省计算资源，实现高效、精确的采样。本发明关键点选取率较高，且耗时少。主要由于采样中构造了简单高效的平均距离作为采样依据，认为采样过程需要满足：(1)点的平均距离越小，被选为关键点的概率越大；(2)关键点邻域内的其他所有点为非关键点，将不再被采样。另外，本发明使用栅格采样和kd-tree的建立作为预处理，使点云中各点分布均匀，在采样过程中能较快地获取邻域点，减少了过多计算量。
附图说明
[0023]
以下附图仅对本发明作示意性的说明和解释，并不用于限定本发明的范围，其中：
[0024]
图1：本发明流程示意图；
[0025]
图2：栅格采样预处理后结果图；
[0026]
图3：采样方法对比结果图，其中，a为原始点云，b为随机采样结果，c本发明采样结果。
具体实施方式
[0027]
为了使本发明的目的、技术方案、设计方法及优点更加清楚明了，以下结合附图通过具体实施例对本发明进一步详细说明。应当理解，此处所描述的具体实施例仅用于解释本发明，并不用于限定本发明。
[0028]
本发明提供了一种三维点云采样方法，首先利用栅格采样点云数据进行预处理，在此基础上，对预处理后的点云生成kd-tree，计算各点在其邻域内的平均距离并将其作为采样标准，即对各点按其平均距离从小到大进行排序，依次判断并选择采样点，平均距离越小的点为关键点的可能性越大，随着某关键点被选，其邻域点又变为非关键点，最终输出采样结果。本方法具有关键点选取率高，对噪声和异常点鲁棒，计算复杂度低等优点。本方法的具体流程图如图1所示，包括以下步骤：
[0029]
步骤s1：参数初始化
[0030]
对于待采样的原始点云每个点表示为i＝1,2,
…
n0，n0为原始点云的点数。设置栅格采样中栅格尺寸sample_size、kd-tree的维度k
dim
＝3和选取的邻近点数k，平均距离的计算半径r，采样点云的点数n1。
[0031]
步骤s2：栅格采样
[0032]
利用栅格采样方法，根据栅格尺寸sample_size，对原始点云q进行栅格采样，获得栅格采样后的点云p＝{p1,p2,...,pn}，其中n为栅格采样后点云的点数。
[0033]
步骤s3：建立栅格采样后点云p的kd-tree
[0034]
根据kd-tree的维度k
dim
＝3，建立栅格采样后点云p的kd-tree。
[0035]
步骤s4：计算点云p中各点的平均距离
[0036]
对于点云p中各点pj(j＝1,2,
…
n)，根据平均距离的计算半径r和点云p的kd-tree，计算以点pj为中心、r为半径的球域δ(pj,r)＝{s||s-pj||≤r}内点pj的所有nj个近邻点计算点pj的平均距离：
[0037][0038]
由此，获得点云p中各点的平均距离集合d＝{d1,d2,...,dn}。
[0039]
步骤s5：对点云p进行采样；
[0040]
步骤s5-1：根据点云p中各点的平均距离集合d，对各点按平均距离由小到大进行排序，作为初始备选点云令初始采样点云
[0041]
步骤s5-2：选取备选点云中平均距离最小的点将该点加入至采样点云中，
即并将及其所有nj个近邻点从备选点云中删除。
[0042]
步骤s5-3：判断采样点云o
l
中的点数是否达到设定点数n1。若小于设定点数，则转至步骤s5-2；否则，转至步骤s5-4。
[0043]
步骤s5-4：输出采样点云o
l
。
[0044]
为了验证本发明的有效性，使用the stanford 3d scanning repository中“bunny”模型进行实验。已知原始点云数量为40097，目标采样至180个点，即设定点数n1为180，预处理中栅格尺寸设置为0.002。
[0045]
利用栅格采样方法，根据栅格尺寸0.002，对原始点云进行栅格采样，获得栅格采样后的点云如图2所示，基于kd-tree的维度k
dim
＝3，建立栅格采样后点云的kd-tree。采样过程中平均距离半径r设置为0.01，利用公式(1)计算点云中各点的平均距离，得到平均距离集合，对各点按平均距离由小到大进行排序，得到初始备选点云。使用本发明与随机采样对比，对比效果如图3所示。由图3可知，本发明的采样结果能够描述原始点云形状，采样过程中保留了更多的关键点，其采样结果优于随机采样方法。
[0046]
以上已经描述了本发明的各实施例，上述说明是示例性的，并非穷尽性的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或对市场中的技术改进，或者使本技术领域的其它普通技术人员能理解本文披露的各实施例。

技术特征：
1.一种三维点云采样方法，其特征在在于，包括以下步骤：s1、对原始点云q进行预处理，得到采样点云p；s2、计算所述点云p中各点的平均距离,得到点云p中各点的平均距离集合d；s3、根据点云p中各点的平均距离集合d，对点云p中的点进行筛选，到采样点云o
l
；s4、在采样点云o
l
内点的个数满足设定要求后，输出采样点云o
l
，完成点云采样。2.根据权利要求1所述的一种三维点云采样方法，其特征在于，所述s1中对原始点云q进行预处理，包括：对原始点云q进行栅格采样，得到采样点云p。3.根据权利要求2所述的一种三维点云采样方法，其特征在于，在计算点云p中各点的平均距离之前，还包括：建立点云p的kd-tree；所述kd-tree的维度k
dim
＝3。4.根据权利要求3所述的一种三维点云采样方法，其特征在于，所述s2中平均距离的计算过程为：对于点云p中各点p
j
，其中j＝1,2,
…
n，n为整数，设定计算半径r，根据所述计算半径r和点云p的kd-tree，计算以点p
j
为中心、r为半径的球域δ(p
j
,r)＝{s|||s-p
j
||≤r}内点p
j
的所有n
j
个近邻点m
j,x
,其中x＝1,2
…
n
j
，形成点p
j
的近邻点集合m
j
，其中，|| ||表示计算欧式距离，δ()表示球域范围，s表示此范围内的其他点；计算点p
j
的平均距离d
j
，进而得到点云p中各点的平均距离集合d＝{d1,d2,...,d
n
}。5.根据权利要求4所述的一种三维点云采样方法，其特征在于，所述平均距离d
j
采用下式(1)计算得到：其中m
j
表示近邻点集合m
j
中的点。6.根据权利要求1所述的一种三维点云采样方法，其特征在于，对点云p中的点的筛选过程为：对平均距离集合d内各点按平均距离从小到大进行排序，作为初始备选点云令初始采样点云选取备选点云中平均距离最小的点将所述点加入采样点云o
l
中，即并将点及其所有n
j
个近邻点从备选点云中删除，其中n
j
表示点在半径r内近邻点的个数。

技术总结
本发明属于模式识别和人工智能技术领域，具体公开了一种三维点云采样方法，首先利用栅格采样点云数据进行预处理，在此基础上，对预处理后的点云生成KD-tree，计算各点在其邻域内的平均距离并将其作为采样标准，即对各点按其平均距离从小到大进行排序，依次判断并选择采样点，平均距离越小的点为关键点的可能性越大，随着某关键点被选，其邻域点又变为非关键点，最终输出采样结果。本方法具有关键点选取率高，对噪声和异常点鲁棒，计算复杂度低等优点。点。点。


技术研发人员：汪霖 马东晗 彭进业 祝轩 彭盛霖 赵万青 姜博 陈圣梅
受保护的技术使用者：西北大学
技术研发日：2023.03.10
技术公布日：2023/9/13