一种面向点云数据最远点采样的优化方法

1.本发明涉及点云数据采样的技术领域，具体涉及一种面向点云数据最远点采样的优化方法。


背景技术：

2.点云是表示物理对象或三维场景的点的集合。点云可以反映物体的空间特征，因此在机器人、自动驾驶、增强现实(ar)和虚拟现实(vr)等领域有着广泛应用。与图像处理领域类似，点云处理也有多种具体应用，如即时定位与地图构建(slam)、物体分类、语义分割以及目标检测等。
3.然而，典型的自动驾驶情景需要程序在1/10秒内处理约12万个点组成的点云，对点云处理的实时性要求很高。同时，随着技术的进步，需要处理的点云的规模也在不断增大。目前，最新一代传感器每秒生成高达480万个点。如此大规模的点云又进一步对点云处理的实时性、计算效率以及硬件能耗提出了更高要求。
4.大规模点云处理中，下采样是必不可少的步骤。而最远点采样是最常用的一种下采样算法，它能够最大程度地保留点云的原始空间特征。而目前最远点采样往往采用双重循环的暴力算法，即在每轮采样迭代中都遍历整个点云，计算点云到采样集合的距离，取最大者作为采样点。这种方法虽简单，但是计算的时间复杂度高，处理效率低。相关技术通过gpu或是专用加速器来处理上述算法中的第二重循环，使计算效率有一定的提升。但是当点云规模较大时，由于上述算法没有利用好点云数据的局部性，两种方法均需要频繁地读写内存以读写点云数据，进而提高了计算延迟与硬件能耗。


技术实现要素：

5.针对现有点云最远点采样方法的高时间复杂度，以及算法部署于硬件引起读写内存性能瓶颈的问题，本发明提供一种面向点云数据最远点采样的优化方法。
6.本发明解决技术问题所采用的技术方案为：
7.对点云数据划分为多个空间独立且局部聚集的点云桶；随机选取一个点云桶的随机点作为初始采样集合；开始k轮采样，其中，在第i轮采样迭代过程中，首先，根据i-1轮的采样结果，更新点云桶的状态信息，然后，选取各点云桶中具有最大距离的局部远点作为本轮采样点，最后，将此采样点加入到采样集合中；采样集合中的k+1个点即为采样结果。
8.优选地，将点云划分为多个空间独立且局部聚集的点云桶的方法包括：使用kd树算法递归地将点云划分为多个点云子集合，并存储点云子集合的三维边界信息、局部远点信息、局部远点距离信息、隶属于此点云子集的点云信息、合并点集合；遍历点云数据，计算点云数据各维度的极差，并计算点云数据在此维度下投影距离的算术平均值，根据此算术平均值将点云数据分为两部分，并依次递归至预设最大深度h，获得2h个空间独立且局部聚集的点云子集。创建2h个点云桶对象数据结构，将各点云子集内的点依次存入相应的点云桶对象数据结构中，获取各点云子集内的点数据各维度的最大值与最小值，更新点云桶对
象数据结构的三维边界信息；局部远点和局部远点距离置为初始化状态，合并点集合置空。
9.进一步地，在第i轮采样迭代过程中，根据i-1轮的采样结果，更新点云桶的状态信息，方法包括：基于历史信息更新点云桶对象的局部远点和局部远点距离信息，首先判断该点云桶和i-1轮采样点s(i-1)是否满足合并计算条件，若不满足，则将s(i-1)加入合并点集合，并计算合并点集合内的所有点与该点云桶的隶属点的距离，选取距离最大值的隶属点作为该点云桶的局部远点，将距离最大值作为该点云桶的局部远点距离，清空合并点集合；否则，判断该点云桶和i-1轮采样点s(i-1)是否满足隐式计算条件，若不满足，则将s(i-1)加入合并点集合。
10.进一步地，所述合并计算条件判断过程包括：计算该点云桶的局部远点与i-1轮采样点s(i-1)的距离，记作当前采样最大距，判断该点云桶的局部远点距离是否有效且小于当前采样最大距，若是，则满足合并计算条件，否则不满足。
11.进一步地，所述隐式计算条件判断过程包括：计算该点云桶的三维边界信息与i-1轮采样点s(i-1)的距离，记作当前采样边界距，判断该点云桶的局部远点距离是否有效且小于当前采样边界距，若是，则满足隐式计算条件，否则不满足。
12.本发明的有益效果如下：本发明利用kd树算法将点云划分为多个点云子集合，在算法主过程中只需遍历这些子集对应的点云桶对象数据结构，进一步只需遍历不满足合并计算条件的点云桶中的所有点，相比于相关方法总是需要遍历整个点云中的所有点，降低了时间复杂度。同时，本方法将满足合并计算的点云桶对象数据结构以及对应的采样点(即前述“合并点”)的距离计算合并在一起同时计算，使得该计算过程以及引起的访存具有时间聚集性，从而可以降低计算的时间延迟以及硬件能耗。
附图说明
13.图1是本发明所提供的面向点云数据最远点采样的优化方法的流程图。
14.图2是本发明一个实施例的将点云划分为多个空间独立且局部聚集的点云桶的流程示意图。
15.图3是本发明一个实施例的第1个采样迭代的运行过程示意图。
16.图4是本发明一个实施例的第2个采样迭代过程示意图(部分)。
具体实施方式
17.下面结合本发明实施例的附图，对本发明中的技术方案进行清楚、完整地描述。应当注意，所描述的实施例只是本技术一部分实施例，而不是全部的实施例，基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本发明的保护范围。
18.参照图1所示的流程图，本发明提供了一种面向点云数据最远点采样的优化方法，包括：首先，将无序的点云数据划分为多个空间独立且局部聚集的点云桶结构；然后，在每轮采样点生成过程中，依据所提出的合并计算和隐式计算规则，基于历史数据关系，更新各点云桶的局部远点和局部远点距离等信息。最后，遍历各点云桶的局部远点，生成一轮采样过程的采样点。当采样点个数达到要求时结束。本发明提供的方法可以降低点云最远点采样的时间复杂度，并可提高计算访存的时间聚集性。
19.图2是本发明一个实施例的将点云划分为多个空间独立且局部聚集的点云桶的流程示意图。为表示方便，该实施例为二维点云。需强调，本发明的典型应用常为三维点云，方法同理。将本发明应用于图2(a)所示的32个点组成的二维点云，以参数规定kd树算法分割点云时，最大的递归深度h＝2。在首次分割时，以x维作为分割维度，对整个点云在该维度下的坐标中取算数平均数，为x＝30。继而以x＝30为阈值，x坐标小于等于该阈值的点组成一个点云子集，而x坐标大于该阈值的点组成另一个点云子集。如图2(b)所示，点云被图中虚线分割为两个点云子集合，此时递归深度为1。之后再递归地将图中左、右两个点云子集合按照y维度再分别分割为新的两个点云子集合。其中左侧点云子集中取所有点在y维度下的坐标中取算数平均数，为y＝33，而右侧点云子集在y维度下的算数平均数则计算得y＝32。如图2(c)所示，左、右侧点集分别以y＝33，y＝32为阈值进行分割。此时递归深度为2，递归过程结束，整个点云被分割为4个点云子集，如图2(d)所示。为便于叙述与管理，依次将4个点云子集编号并命名为：点云桶0、点云桶1、点云桶2与点云桶3。得到需要的点云子集合后，对4个点云子集合分别建立点云桶对象数据结构，存储内容包括：点云子集合的三维边界信息、局部远点信息、局部远点距离信息、隶属于此点云子集的点云信息、合并点集合。完成后，得到4个点云桶对象数据结构。点云桶对象数据结构的初始化方法如下：初始化二维边界信息为点云子集合中x、y坐标的最大值与最小值；初始化局部远点为无效点；初始化局部远点距离为一无效值(一般选取32位有符号整数最大值2147483647)；初始化点云坐标信息为隶属于对应点云子集合中各个点的坐标；初始化点云各点到采样集合的距离信息为一无效值(一般也选取2147483647)；初始化合并点集合为空集合。
20.图3是本发明一个实施例第一个采样迭代的运行过程示意图。对图2的样例数据，kd树分割以及点云桶对象数据结构初始化结束后，采样集合将被初始化，在点云中随机选取一个点加入采样集合。如图3(a)所示，星标点即为选取的首个采样点s(0)。之后进入第一轮采样迭代以选取第一个采样点s(1)。由于点云桶结构仅被初始化而从未被更新，最大距离仍保持初始化时赋予的无效值，各个点云桶结构均不满足合并计算条件，将把首个采样点添加入各个点云桶结构的合并点集合，进一步遍历各个点云桶结构以进行信息更新。具体地，将依次对每个点云桶结构逐个读出点云桶点的坐标，再逐个读出当前点云桶结构的合并点(本例中仅有s(0)一个合并点)，以如下距离公式计算该点云桶点到合并点的距离：d(xm，yn)＝∑
维度i
(x
m，i-y
n，i
)221.其中，d(
·
，
·
)即表示所求距离；xm，yn分别表示第m个点云桶点与第n个合并点；x
m，i
，y
n，i
分别表示第m个点云桶点与第n个合并点在第i维的坐标值。
22.取该点云桶点到各个合并点距离的最小值，与当前所存储的该点云桶点到采样集合的距离信息，两者比较，取较小者更新该点云桶点到采样集合的距离，用公式表示如下：
[0023][0024]dsamp
(xm)＝min(d
samp
(xm)，d
now
(xm))
[0025]
其中，d
now
(xm)表示当前第m个点云桶点xm到合并点集的距离；d
samp
(xm)表示点云桶结构中存储的点云桶点xm到采样集合的距离信息。
[0026]
更新的同时记录下每个点云桶结构中，距离采样集合最远的点云桶点，利用这个点云桶点以及相应的到采样集合的距离，分别更新该点云桶的局部远点以及局部远点距离，即：
[0027][0028]
distk＝d
now
(fpk)
[0029]
其中，fpk为第k个点云桶结构的局部远点；distk为第k个点云桶结构的局部远点距离。
[0030]
如图3(b)中的三角形标记点即为更新4个点云桶结构后，计算得到的各个点云桶结构的局部远点，对应的局部远点距离如图所注。
[0031]
所求的本轮采样点s(1)即为4个点云桶结构中，局部远点距离最大的点云桶结构的局部远点，即
[0032]
maxidx＝argmaxk(distk)
[0033]
s(i)＝fp
maxidx
[0034]
其中，maxidx为最大距离最大的点云桶结构的下标，s(i)为第i轮采样的采样点。
[0035]
如图3(c)中，由于第3个点云桶结构的局部远点距离为57.45，为四个点云桶结构中最大。因此第3个点云桶结构的局部远点，即图中星型标记点，被选中作为第一轮采样点s(1)，加入采样集合。第一轮采样到此结束。选中的局部远点成为了采样点，故该点到采样集合的距离变为0，相应地要将该点云桶结构的局部远点距离更新为0。
[0036]
图4是本发明一个实施例的第2个采样迭代过程示意图(部分)。对图2的样例点云数据，第1个采样迭代中，图3(c)中x型标记的点被选中，该点也即图4中的星型标记点。在第2个采样迭代过程中，首先需要遍历各个点云桶结构，判断各个点云桶结构对第1轮采样点s(1)是否满足合并条件。如图4(a)，对第0个点云桶结构判断合并条件时，需要计算第1轮采样点到点云桶的局部远点的距离，即所谓“当前采样最大距”，在图中为星型标记点到三角形标记点的距离，按照前述点的距离公式算得为68.12。由于该距离大于当前第0个点云桶结构的局部远点距离22.56(该值在第1轮采样时计算得到)，故满足合并计算条件，这意味着该采样点的加入不会引起这个点云桶结构的局部远点以及局部远点距离发生变化。可以将该点云桶结构内点的距离的更新操作合并至未来的采样迭代中。其后还需要判断是否满足隐式计算条件。在判断之前需要先计算第1轮采样点s(1)到点云桶结构的二维边界的距离，即所谓“当前采样边界距”，(对第i轮采样)计算公式为：
[0037][0038]
其中，d
bounding
(s(i-1)，bk)表示第i-1轮采样点s(i-1)到点云桶结构bk的当前采样边界距。若第i-1轮采样点s(i-1)在bk中或其二维边界上，则值取0；否则s(i-1)在bk外部，取s(i-1)到bk边界上的所有点的距离的最小值为当前采样边界距。实际计算时，利用存储的点云桶的边界信息，即点云桶对应的点云子集合中各个点在x、y坐标上的最大值与最小值，与s(i-1)的相应维度的坐标比较，再辅之以分类讨论与计算，即可得到该距离。
[0039]
图4(a)所示的实例中，第1轮采样点s(1)(即星标点)在第0个点云桶结构外，距离为s(1)到该点云桶结构二维边界的右下角点的距离，计算得该距离为41.87，此即当前采样边界距。因此当前采样边界距也大于该点云桶结构的局部远点距离，满足隐式计算条件。这意味着s(1)到点云桶结构内的所有点的距离(以当前采样边界距为下界)均大于该点云桶
结构中各个点到当前采样集合的距离(以该点云桶结构的局部远点距离为上界)，因此s(1)加入采样集合并不会对当前点云桶中的任何点到采样集合的距离造成影响，故无需以该采样点更新该点云桶结构中的点的距离信息。因此也就无需做任何操作，继续下一个点云桶结构的计算即可，节约了计算时间与空间。
[0040]
图4(b)则展示了在第2轮采样过程中，对第1个点云桶结构的更新时的计算过程与结果。需要对该点云桶结构与第1轮采样点s(1)判别是否满足合并计算条件与隐式计算条件。合并计算条件的判断需要计算当前采样最大距，计算为41.29；而第1个点云桶结构的局部远点距离为34.93。局部远点距离小于当前采样最大距，满足合并计算条件。之后再计算当前采样边界距，为图中星标点到点云桶下方边界的垂线段长，为32。最大距离大于当前采样边界距，故不满足隐式计算条件。因此需要将s(1)加入该点云桶结构的合并点集合，等待未来某轮采样不满足合并计算时一并更新距离，使得计算访存具有时间聚集性。但是该点云桶的局部远点和局部远点距离则不变，继而可以直接继续下一个点云桶结构的计算。
[0041]
以上运用具体实施例对本发明进行了详细的阐述。需要指出的是，上述内容仅为本发明的具体实施例，而不应用于限制本发明范畴。在本发明的设计思想之内的任何修改、替换、改进等都应在本发明的保护范围之内。

技术特征：
1.一种面向点云数据最远点采样的优化方法，其特征在于，包括以下步骤：对点云数据划分为多个空间独立且局部聚集的点云桶；随机选取一个点云桶的随机点作为初始采样集合；开始k轮采样，其中，在第i轮采样迭代过程中，首先，根据i-1轮的采样结果，更新点云桶的状态信息，然后，选取各点云桶中具有最大距离的局部远点作为本轮采样点，最后，将此采样点加入到采样集合中；采样集合中的k+1个点即为采样结果。2.根据权利要求1中所述的面向点云数据最远点的采样方法，将点云划分为多个空间独立且局部聚集的点云桶，其特征在于，使用kd树算法递归地将点云划分为多个点云子集合，并存储点云子集合的三维边界信息、局部远点信息、局部远点距离信息、隶属于此点云子集的点云信息、合并点集合；遍历点云数据，计算点云数据各维度的极差，并计算点云数据在此维度下投影距离的算术平均值，根据此算术平均值将点云数据分为两部分，并依次递归至预设最大深度h，获得2
h
个空间独立且局部聚集的点云子集；创建2
h
个点云桶对象数据结构，将各点云子集内的点依次存入相应的点云桶对象数据结构中，获取各点云子集内的点数据各维度的最大值与最小值，更新点云桶对象数据结构的三维边界信息；局部远点和局部远点距离置为初始化状态，合并点集合置空。3.根据权利要求1中所述的面向点云数据最远点的采样方法，在第i轮采样迭代过程中，根据i-1轮的采样结果，更新点云桶的状态信息，其特征在于，基于历史信息更新点云桶对象的局部远点和局部远点距离信息，首先判断该点云桶和i-1轮采样点s(i-1)是否满足合并计算条件，若不满足，则将s(i-1)加入合并点集合，并计算合并点集合内的所有点与该点云桶的隶属点的距离，选取距离最大值的隶属点作为该点云桶的局部远点，将距离最大值作为该点云桶的局部远点距离，清空合并点集合；否则，判断该点云桶和i-1轮采样点s(i-1)是否满足隐式计算条件，若不满足，则将s(i-1)加入合并点集合。4.根据权利要求3所述的面向点云数据最远点的采样方法，其特征在于，所述合并计算条件判断过程包括：计算该点云桶的局部远点与i-1轮采样点s(i-1)的距离，记作当前采样最大距，判断该点云桶的局部远点距离是否有效且小于当前采样最大距，若是，则满足合并计算条件，否则不满足。5.根据权利要求3所述的面向点云数据最远点的采样方法，其特征在于，所述隐式计算条件判断过程包括：计算该点云桶的三维边界信息与i-1轮采样点s(i-1)的距离，记作当前采样边界距，判断该点云桶的局部远点距离是否有效且小于当前采样边界距，若是，则满足隐式计算条件，否则不满足。

技术总结
本发明提供了一种面向点云数据最远点采样的优化方法，包括：首先，将无序点云数据划分为多个空间独立且局部聚集的点云桶结构；然后，在每轮采样点生成过程中，提出了合并计算和隐式计算规则，基于历史数据关系，更新各点云桶的局部远点和局部远点距离等信息。最后，遍历各点云桶的局部远点，生成一轮采样过程的采样点。当采样点个数达到要求时结束。本发明提供的方法可以降低点云最远点采样的时间复杂度，并可提高计算访存的时间聚集性。并可提高计算访存的时间聚集性。并可提高计算访存的时间聚集性。


技术研发人员：肖利民 张昊 韩萌 王良 徐家乐 张晨浩 徐向荣 谢喜龙
受保护的技术使用者：北京航空航天大学
技术研发日：2023.03.07
技术公布日：2023/8/21