点云数据k邻域搜索方法
点云数据k邻域搜索方法
【技术领域】
[0001 ]本发明属于计算机应用技术领域，具体地说，涉及一种扫描数据三维重建技术中的点云数据κ邻域搜索方法。
【背景技术】
[0002]对点云数据进行三维重建，需要建立点云的邻域拓扑关系。Κ邻域广泛应用于海量数据点的三维重建中，能够在数据点中建立一定的邻域关系以加快搜索速度。
[0003]现有的Κ邻域搜索方法是:首先对点云数据集S={Pi}(i= l，2,...，n)进行分块，按照空间位置邻近的原则设定点Pi的近邻区域，然后在近邻区域中计算距离并排序，最后取距离Pi最近的K个点作为其K近邻。
[0004]由于要处理的点云在数量上往往是海量的，因此将其精确分块是非常耗时的，而要分块记录下来也需要复杂的数据结构，占用大量的存储空间。
【发明内容】
[0005]本发明提供了一种点云数据K邻域搜索方法，解决现有K邻域算法耗时长且占用内存空间的技术问题。
[0006]为解决上述技术问题，本发明采用以下技术方案予以实现:
提出一种点云数据K邻域搜索方法，包括:将点云数据中每个点分别从X、Y、Z三个方向进行升序排列，存入数组Px、Py和Ρζ中；取数组Ρχ中的第i点，分别向前向后按照设定步长取样，若取样点的X方向与第i点的距离小于阈值d，则将其索引存入数组TemX中，并增加一次步长取样，直至取样点X方向距离与第i点的距离大于阈值d;取数组Py中的第j点，分别向前向后按照设定步长取样，若取样点的Y方向与第j点的距离小于阈值d，则将其索引存入数组TemY中，并增加一次步长取样，直至取样点Y方向距离与第j点的距离大于阈值d;取数组Ρζ中的第k点，分别向前向后按照设定步长取样，若取样点的Ζ方向与第k点的距离小于阈值d，贝lj将其索引存入数组TemZ中，并增加一次步长取样，直至取样点Z方向距离与第k点的距离大于阈值d;基于TemX、TemY和TemZ中搜索点的交集确定搜索点集;计算搜索点与候选点之间的欧式空间距离，取距离最近的K个点组成所述候选点的K邻域;其中，数组Px中的第i点、数组Py中的第j点和数组Ρζ中的第k点对应为候选点P( i，j，k)。
[0007]进一步的，所述阈值d的取值为点云平均间距的4至5倍。
[0008]进一步的，在将点云数据中每个点分别从X、y、ζ三个方向进行升序排列之前，所述方法还包括:保存点云数据的索引值;和初始化点云数据的标识为初始值;则所述方法还包括:在确定X方向与第i点的距离小于阈值d的取样点后，将所述X方向与第i点的距离小于阈值d的取样点的标识值加1;在确定Y方向第j点的距离小于阈值d的取样点后，将所述Y方向与第j点的距离小于阈值d的取样点的标识值加1;在确定Z方向第k点的距离小于阈值d的取样点后，将所述Z方向与第k点的距离小于阈值d的取样点的标识值加1。
[0009]进一步的，所述初始值为0，则基于TemX、TemY和TemZ中索引的交集，确定搜索点，具体为:将标识值增大3的点确定为搜索点。
[0010]进一步的，在数组Px、数组Py和数组Ρζ中取样时，所述方法还包括:若第一次取样的点的个数小于设定步长，则将所有取样点的标识加1。
[0011]与现有技术相比，本发明的优点和技术效果是:
本发明实施例提出的点云数据Κ邻域搜索方法中，使用单坐标轴结合距离阈值d进行分步搜索的方法，在整体点云中限定一个候选点为中心，以边长为2倍的阈值d的立方体为限，在该立方体内沿X、Y、Z三个方向以设定步长依次向正负两个方向分段进行搜索，分别找到X、Υ、Ζ三个方向所有距离候选点单坐标距离小于阈值d的点，在这些点中求X、Y、Z三个方向搜索结果的交集，确定搜索点，最后在这个搜索点交集中找出距离候选点的欧式空间距离最小的K个点，构成候选点的K邻域。该方法使用单坐标结合阈值进行分步搜索，方法简单直观，易于实现，能够减少参与计算欧式空间距离的点数，从而减少了计算量，提高了搜索速度，也节省了内存空间。
[0012]结合附图阅读本发明实施方式的详细描述后，本发明的其他特点和优点将变得更加清楚。
【附图说明】
[0013]图1为本发明实施例提出的点云数据K邻域搜索方法的流程图。
【具体实施方式】
[0014]
下面结合附图对本发明的【具体实施方式】作进一步详细地说明。
[0015]如图1所示，为本发明实施例提出的点云数据K邻域搜索方法的流程图，包括以下步骤:
步骤SI 1:将点云数据中每个点分别从X、Υ、Z三个方向进行升序排列，存入数组Px、Py和Ρζ中。
[0016]读取点云数据，将每个点的X、y、ζ坐标值分别存入数组Px、Py和Ρζ中，同时保存点云数据的索引值，初始化点云数据的标识为初始值，例如，初始化点云数据的标识flag为0。
[0017]然后按照数组Px、Py和Ρζ中元素的坐标值对数组Px、Py和Ρζ中元素进行升序排列。
[0018]步骤S12:取数组Px中的第i点，分别向前向后按照设定步长取样，若取样点的X方向与第i点的距离小于阈值d，则将其索引存入数组TemX中，并增加一次步长取样，直至取样点X方向距离与第i点的距离大于阈值d。
[0019]在确定X方向与第i点的距离小于阈值d的取样点后，将这些取样点的标识值flag加1。若第一次取样的点的个数小于设定步长，则将所有取样点的标识加1。
[0020]步骤S13:取数组Py中的第j点，分别向前向后按照设定步长取样，若取样点的Y方向与第j点的距离小于阈值d，则将其索引存入数组TemY中，并增加一次步长取样，直至取样点Y方向距离与第j点的距离大于阈值d。
[0021]在确定Y方向第j点的距离小于阈值d的取样点后，将这些取样点的标识值flag加1。若第一次取样的点的个数小于设定步长，则将所有取样点的标识加1。
[0022]步骤S14:取数组Ρζ中的第k点，分别向前向后按照设定步长取样，若取样点的Z方向与第k点的距离小于阈值d，则将其索引存入数组TemZ中，并增加一次步长取样，直至取样点Z方向距离与第k点的距离大于阈值d。
[0023]在确定Z方向第k点的距离小于阈值d的取样点后，将这些取样点的标识值flag加
1。若第一次取样的点的个数小于设定步长，则将所有取样点的标识加1。
[0024]这其中，数组Ρχ中的第i点、数组Py中的第j点和数组Ρζ中的第k点对应为从点云中选取出的候选点P(i，j，k)。可以在数组Px中的第i点选取确定后，通过Py和Ρζ中查找i对应的索引确定j和k。
[0025]设定步长为设定的一次取样的点数;阈值d与设定步长均可调。
[0026]步骤S15:基于TemX、TemY和TemZ中搜索点的交集确定搜索点集。
[0027]具体的，数组TemX、TemY和TemZ中都存在的点，其对应的标识值flag增大3次，则可将标识值增大3的点确定为搜索点。
[0028]步骤S16:计算搜索点与候选点之间的欧式空间距离，取距离最近的K个点组成所述候选点的K邻域。
[0029]完成步骤S11至步骤S16后，将i值加1切换到下一个候选点，重复步骤12至步骤S16，直至i大于点云数量总数。
[0030]上述阈值d的取值优选为为点云平均间距的4至5倍。取值过大，会导致计算量太大，而取值过小，会导致无法取得足够的近邻点。
[0031]上述本发明实施例提出的点云数据K邻域搜索方法，使用单坐标轴结合阈值d进行分步搜索的方法，简单直观，易于实现，减少了参与计算欧式空间距离的点数，进而提高了搜索速度，也节省了内存空间的占用。该方法根据点云精度和数量确定阈值d来约束候选点前后的搜索范围，解决了对不同精度和规模的点云数据的适用性问题。
[0032]应该指出的是，上述说明并非是对本发明的限制，本发明也并不仅限于上述举例，本技术领域的普通技术人员在本发明的实质范围内所做出的变化、改型、添加或替换，也应属于本发明的保护范围。
【主权项】
1.点云数据κ邻域搜索方法，其特征在于，包括: 将点云数据中每个点分别从X、Υ、Ζ三个方向进行升序排列，存入数组Px、Py和Ρζ中；取数组Ρχ中的第i点，分别向前向后按照设定步长取样，若取样点的X方向与第i点的距离小于阈值d，则将其索引存入数组TemX中，并增加一次步长取样，直至取样点X方向距离与第i点的距离大于阈值d; 取数组Py中的第j点，分别向前向后按照设定步长取样，若取样点的Y方向与第j点的距离小于阈值d，则将其索引存入数组TemY中，并增加一次步长取样，直至取样点Y方向距离与第j点的距离大于阈值d; 取数组Ρζ中的第k点，分别向前向后按照设定步长取样，若取样点的Z方向与第k点的距离小于阈值d，则将其索引存入数组TemZ中，并增加一次步长取样，直至取样点Z方向距离与第k点的距离大于阈值d; 基于TemX、TemY和TemZ中搜索点的交集确定搜索点集； 计算搜索点与候选点之间的欧式空间距离，取距离最近的K个点组成所述候选点的K邻域； 其中，数组Px中的第i点、数组Py中的第j点和数组Ρζ中的第k点对应为候选点P( i，j，k)。2.根据权利要求1所述的点云数据K邻域搜索方法，其特征在于，所述阈值d的取值为点云平均间距的4至5倍。3.根据权利要求1所述的点云数据K邻域搜索方法，其特征在于，在将点云数据中每个点分别从x、y、z三个方向进行升序排列之前，所述方法还包括: 保存点云数据的索引值;和 初始化点云数据的标识为初始值;则所述方法还包括: 在确定X方向与第i点的距离小于阈值d的取样点后，将所述X方向与第i点的距离小于阈值d的取样点的标识值加1;在确定Y方向第j点的距离小于阈值d的取样点后，将所述Y方向与第j点的距离小于阈值d的取样点的标识值加1;在确定Z方向第k点的距离小于阈值d的取样点后，将所述Z方向与第k点的距离小于阈值d的取样点的标识值加1。4.根据权利要求3所述的点云数据K邻域搜索方法，其特征在于，所述初始值为0，则基于TemX、TemY和TemZ中搜索点的交集确定搜索点，具体为: 将标识值增大3的点确定为搜索点。5.根据权利要求3所述的点云数据K邻域搜索方法，其特征在于，在数组Px、数组Py和数组Ρζ中取样时，所述方法还包括: 若第一次取样的点的个数小于设定步长，则将所有取样点的标识加1。
【专利摘要】本发明提出一种点云数据K邻域搜索方法，将点云数据中每个点从X、Y和Z轴三个方向按升序排列存入数组Px、Py和Pz中；确定候选点P（i，j，k），在Px、Py和Pz中，分别取第i、第j和第k点，在每个点上分别向前向后按照设定步长取样，若取样点的X方向与第i点的距离小于阈值、Y方向与第j点的距离小于阈值、Z方向与第k点的距离小于阈值，则对应将索引存入数组TemX、TemY和TemZ中，继而增加一次步长继续上述步骤直至距离大于阈值；从TemX、TemY和TemZ中搜索点的交集确定搜索点集，从搜索点集中找出与候选点距离最近的K个点组成候选点的K邻域，解决了现有K邻域算法耗时长且占用内存空间的技术问题。
【IPC分类】G06F17/30
【公开号】CN105488192
【申请号】CN201510876826
【发明人】王红, 薛斌, 刘启
【申请人】青岛尤尼科技有限公司
【公开日】2016年4月13日
【申请日】2015年12月3日
【技术领域】
[0001 ]本发明属于计算机应用技术领域，具体地说，涉及一种扫描数据三维重建技术中的点云数据κ邻域搜索方法。
【背景技术】
[0002]对点云数据进行三维重建，需要建立点云的邻域拓扑关系。Κ邻域广泛应用于海量数据点的三维重建中，能够在数据点中建立一定的邻域关系以加快搜索速度。
[0003]现有的Κ邻域搜索方法是:首先对点云数据集S={Pi}(i= l，2,...，n)进行分块，按照空间位置邻近的原则设定点Pi的近邻区域，然后在近邻区域中计算距离并排序，最后取距离Pi最近的K个点作为其K近邻。
[0004]由于要处理的点云在数量上往往是海量的，因此将其精确分块是非常耗时的，而要分块记录下来也需要复杂的数据结构，占用大量的存储空间。
【发明内容】
[0005]本发明提供了一种点云数据K邻域搜索方法，解决现有K邻域算法耗时长且占用内存空间的技术问题。
[0006]为解决上述技术问题，本发明采用以下技术方案予以实现:
提出一种点云数据K邻域搜索方法，包括:将点云数据中每个点分别从X、Y、Z三个方向进行升序排列，存入数组Px、Py和Ρζ中；取数组Ρχ中的第i点，分别向前向后按照设定步长取样，若取样点的X方向与第i点的距离小于阈值d，则将其索引存入数组TemX中，并增加一次步长取样，直至取样点X方向距离与第i点的距离大于阈值d;取数组Py中的第j点，分别向前向后按照设定步长取样，若取样点的Y方向与第j点的距离小于阈值d，则将其索引存入数组TemY中，并增加一次步长取样，直至取样点Y方向距离与第j点的距离大于阈值d;取数组Ρζ中的第k点，分别向前向后按照设定步长取样，若取样点的Ζ方向与第k点的距离小于阈值d，贝lj将其索引存入数组TemZ中，并增加一次步长取样，直至取样点Z方向距离与第k点的距离大于阈值d;基于TemX、TemY和TemZ中搜索点的交集确定搜索点集;计算搜索点与候选点之间的欧式空间距离，取距离最近的K个点组成所述候选点的K邻域;其中，数组Px中的第i点、数组Py中的第j点和数组Ρζ中的第k点对应为候选点P( i，j，k)。
[0007]进一步的，所述阈值d的取值为点云平均间距的4至5倍。
[0008]进一步的，在将点云数据中每个点分别从X、y、ζ三个方向进行升序排列之前，所述方法还包括:保存点云数据的索引值;和初始化点云数据的标识为初始值;则所述方法还包括:在确定X方向与第i点的距离小于阈值d的取样点后，将所述X方向与第i点的距离小于阈值d的取样点的标识值加1;在确定Y方向第j点的距离小于阈值d的取样点后，将所述Y方向与第j点的距离小于阈值d的取样点的标识值加1;在确定Z方向第k点的距离小于阈值d的取样点后，将所述Z方向与第k点的距离小于阈值d的取样点的标识值加1。
[0009]进一步的，所述初始值为0，则基于TemX、TemY和TemZ中索引的交集，确定搜索点，具体为:将标识值增大3的点确定为搜索点。
[0010]进一步的，在数组Px、数组Py和数组Ρζ中取样时，所述方法还包括:若第一次取样的点的个数小于设定步长，则将所有取样点的标识加1。
[0011]与现有技术相比，本发明的优点和技术效果是:
本发明实施例提出的点云数据Κ邻域搜索方法中，使用单坐标轴结合距离阈值d进行分步搜索的方法，在整体点云中限定一个候选点为中心，以边长为2倍的阈值d的立方体为限，在该立方体内沿X、Y、Z三个方向以设定步长依次向正负两个方向分段进行搜索，分别找到X、Υ、Ζ三个方向所有距离候选点单坐标距离小于阈值d的点，在这些点中求X、Y、Z三个方向搜索结果的交集，确定搜索点，最后在这个搜索点交集中找出距离候选点的欧式空间距离最小的K个点，构成候选点的K邻域。该方法使用单坐标结合阈值进行分步搜索，方法简单直观，易于实现，能够减少参与计算欧式空间距离的点数，从而减少了计算量，提高了搜索速度，也节省了内存空间。
[0012]结合附图阅读本发明实施方式的详细描述后，本发明的其他特点和优点将变得更加清楚。
【附图说明】
[0013]图1为本发明实施例提出的点云数据K邻域搜索方法的流程图。
【具体实施方式】
[0014]
下面结合附图对本发明的【具体实施方式】作进一步详细地说明。
[0015]如图1所示，为本发明实施例提出的点云数据K邻域搜索方法的流程图，包括以下步骤:
步骤SI 1:将点云数据中每个点分别从X、Υ、Z三个方向进行升序排列，存入数组Px、Py和Ρζ中。
[0016]读取点云数据，将每个点的X、y、ζ坐标值分别存入数组Px、Py和Ρζ中，同时保存点云数据的索引值，初始化点云数据的标识为初始值，例如，初始化点云数据的标识flag为0。
[0017]然后按照数组Px、Py和Ρζ中元素的坐标值对数组Px、Py和Ρζ中元素进行升序排列。
[0018]步骤S12:取数组Px中的第i点，分别向前向后按照设定步长取样，若取样点的X方向与第i点的距离小于阈值d，则将其索引存入数组TemX中，并增加一次步长取样，直至取样点X方向距离与第i点的距离大于阈值d。
[0019]在确定X方向与第i点的距离小于阈值d的取样点后，将这些取样点的标识值flag加1。若第一次取样的点的个数小于设定步长，则将所有取样点的标识加1。
[0020]步骤S13:取数组Py中的第j点，分别向前向后按照设定步长取样，若取样点的Y方向与第j点的距离小于阈值d，则将其索引存入数组TemY中，并增加一次步长取样，直至取样点Y方向距离与第j点的距离大于阈值d。
[0021]在确定Y方向第j点的距离小于阈值d的取样点后，将这些取样点的标识值flag加1。若第一次取样的点的个数小于设定步长，则将所有取样点的标识加1。
[0022]步骤S14:取数组Ρζ中的第k点，分别向前向后按照设定步长取样，若取样点的Z方向与第k点的距离小于阈值d，则将其索引存入数组TemZ中，并增加一次步长取样，直至取样点Z方向距离与第k点的距离大于阈值d。
[0023]在确定Z方向第k点的距离小于阈值d的取样点后，将这些取样点的标识值flag加
1。若第一次取样的点的个数小于设定步长，则将所有取样点的标识加1。
[0024]这其中，数组Ρχ中的第i点、数组Py中的第j点和数组Ρζ中的第k点对应为从点云中选取出的候选点P(i，j，k)。可以在数组Px中的第i点选取确定后，通过Py和Ρζ中查找i对应的索引确定j和k。
[0025]设定步长为设定的一次取样的点数;阈值d与设定步长均可调。
[0026]步骤S15:基于TemX、TemY和TemZ中搜索点的交集确定搜索点集。
[0027]具体的，数组TemX、TemY和TemZ中都存在的点，其对应的标识值flag增大3次，则可将标识值增大3的点确定为搜索点。
[0028]步骤S16:计算搜索点与候选点之间的欧式空间距离，取距离最近的K个点组成所述候选点的K邻域。
[0029]完成步骤S11至步骤S16后，将i值加1切换到下一个候选点，重复步骤12至步骤S16，直至i大于点云数量总数。
[0030]上述阈值d的取值优选为为点云平均间距的4至5倍。取值过大，会导致计算量太大，而取值过小，会导致无法取得足够的近邻点。
[0031]上述本发明实施例提出的点云数据K邻域搜索方法，使用单坐标轴结合阈值d进行分步搜索的方法，简单直观，易于实现，减少了参与计算欧式空间距离的点数，进而提高了搜索速度，也节省了内存空间的占用。该方法根据点云精度和数量确定阈值d来约束候选点前后的搜索范围，解决了对不同精度和规模的点云数据的适用性问题。
[0032]应该指出的是，上述说明并非是对本发明的限制，本发明也并不仅限于上述举例，本技术领域的普通技术人员在本发明的实质范围内所做出的变化、改型、添加或替换，也应属于本发明的保护范围。
【主权项】
1.点云数据κ邻域搜索方法，其特征在于，包括: 将点云数据中每个点分别从X、Υ、Ζ三个方向进行升序排列，存入数组Px、Py和Ρζ中；取数组Ρχ中的第i点，分别向前向后按照设定步长取样，若取样点的X方向与第i点的距离小于阈值d，则将其索引存入数组TemX中，并增加一次步长取样，直至取样点X方向距离与第i点的距离大于阈值d; 取数组Py中的第j点，分别向前向后按照设定步长取样，若取样点的Y方向与第j点的距离小于阈值d，则将其索引存入数组TemY中，并增加一次步长取样，直至取样点Y方向距离与第j点的距离大于阈值d; 取数组Ρζ中的第k点，分别向前向后按照设定步长取样，若取样点的Z方向与第k点的距离小于阈值d，则将其索引存入数组TemZ中，并增加一次步长取样，直至取样点Z方向距离与第k点的距离大于阈值d; 基于TemX、TemY和TemZ中搜索点的交集确定搜索点集； 计算搜索点与候选点之间的欧式空间距离，取距离最近的K个点组成所述候选点的K邻域； 其中，数组Px中的第i点、数组Py中的第j点和数组Ρζ中的第k点对应为候选点P( i，j，k)。2.根据权利要求1所述的点云数据K邻域搜索方法，其特征在于，所述阈值d的取值为点云平均间距的4至5倍。3.根据权利要求1所述的点云数据K邻域搜索方法，其特征在于，在将点云数据中每个点分别从x、y、z三个方向进行升序排列之前，所述方法还包括: 保存点云数据的索引值;和 初始化点云数据的标识为初始值;则所述方法还包括: 在确定X方向与第i点的距离小于阈值d的取样点后，将所述X方向与第i点的距离小于阈值d的取样点的标识值加1;在确定Y方向第j点的距离小于阈值d的取样点后，将所述Y方向与第j点的距离小于阈值d的取样点的标识值加1;在确定Z方向第k点的距离小于阈值d的取样点后，将所述Z方向与第k点的距离小于阈值d的取样点的标识值加1。4.根据权利要求3所述的点云数据K邻域搜索方法，其特征在于，所述初始值为0，则基于TemX、TemY和TemZ中搜索点的交集确定搜索点，具体为: 将标识值增大3的点确定为搜索点。5.根据权利要求3所述的点云数据K邻域搜索方法，其特征在于，在数组Px、数组Py和数组Ρζ中取样时，所述方法还包括: 若第一次取样的点的个数小于设定步长，则将所有取样点的标识加1。
【专利摘要】本发明提出一种点云数据K邻域搜索方法，将点云数据中每个点从X、Y和Z轴三个方向按升序排列存入数组Px、Py和Pz中；确定候选点P（i，j，k），在Px、Py和Pz中，分别取第i、第j和第k点，在每个点上分别向前向后按照设定步长取样，若取样点的X方向与第i点的距离小于阈值、Y方向与第j点的距离小于阈值、Z方向与第k点的距离小于阈值，则对应将索引存入数组TemX、TemY和TemZ中，继而增加一次步长继续上述步骤直至距离大于阈值；从TemX、TemY和TemZ中搜索点的交集确定搜索点集，从搜索点集中找出与候选点距离最近的K个点组成候选点的K邻域，解决了现有K邻域算法耗时长且占用内存空间的技术问题。
【IPC分类】G06F17/30
【公开号】CN105488192
【申请号】CN201510876826
【发明人】王红, 薛斌, 刘启
【申请人】青岛尤尼科技有限公司
【公开日】2016年4月13日
【申请日】2015年12月3日
最新回复(0)