一种基于萤火虫优化的点云分步配准方法

1.本发明涉及数据处理的技术领域，尤其涉及一种基于萤火虫优化 的点云分步配准方法。


背景技术：

2.一种基于萤火虫优化的点云分步配准方法，可以很好地配准点云， 该方法可应用于遥感遥测、军事科学、医学影像、交通监控等领域中。
3.点云配准是一种估计两帧扫描点云之间变换矩阵的问题。根据变 换矩阵，我们可以将同一个三维场景或物体的部分扫描点云合并成一 个完整的三维点云，点云配准的价值在于它在众多计算机视觉应用中 的独特而关键的作用。
4.迭代最小误差的配准方法中经典的配准算法是icp(iterativeclosest point)算法。besl和mckay(参考：besl p j,mckay h d.amethod for registration of 3-d shapes[j].ieee transactions on patternanalysis&machine intelligence,1992,14(2):239-256.)在1992年提出 了icp算法，该算法遍历并寻找两片点云之间距离最近的点，并将其 称为对应点对，寻找对应点的空间距离，使距离最小从而让目标函数 收敛从而求出刚性矩阵，直到匹配误差小于阈值或者已经到了最大循 环次数，但该方法对目标点云的一开始的空间位置有较大的约束，目 标点云与源点云的重叠度必须达到一定比例，达到大致重合时才能获 得较好的匹配效果，否则该方法会在局部收敛而忽略整体的匹配效果， 导致最终的配准效果不理想，并且icp算法也存在着计算成本大， 计算复杂度较高的缺陷。chen和medioni及bergevin等人(参考： yang c,medioni g.object modeling by registration of multiple rangeimages[j].image and vision computing,2002,10(3):145-155.)把目标 点之间的切平面距离代替了icp算法中点到点的距离，极大地降低 了算法的时间复杂度。mitra(参考：mitra n j,nguyen a,guibas l. estimating surface normal in noisy point cloud data[j].internationaljournalofcomputationalgeometry&applications,2004,14(4-5):261-276..) 提出点到点(point to point)和点到面(point to plane)的关键点定义，把 icp算法对点云的重叠度要求较高的约束彻底解决了，点云开始的空 间位置较差时也能表现出较好的配准效果，但该方法对点云中的点都 遍历一遍然后计算曲率，大大降低了配准效率。granger和pennec(参 考：granger s,pennec x.multi-scale em-icp:a fast and robustapproach for surface registration[c]//computer vision-eccv 2002, 7th european conference on computer vision,copenhagen,denmark, may 28-31,2002,proceedings,part iv.dblp,2002.)把统计概率方法 与icp结合在一起，设计了基于似然估计的em-icp的改进算法。 上述基于icp算法虽然配准速度快，但是很容易陷入局部最优解。并 且要剔除不合适的点对(点对距离过大、包含边界点的点对)，由于 icp算法基于点对的配准，并没有包含局部形状的信息，导致每次迭 代都要搜索最近点，计算代价高昂。


技术实现要素：

[0005]
针对上述问题，本发明的目的是提供一种防止陷入局部最优的快 速准确的点云配准方法。
[0006]
为实现上述目的，本发明采用的技术路线是：
[0007]
一种基于萤火虫优化的点云分步配准方法，用于实现点云数据配 准，所述的一种基于萤火虫优化的点云分步配准方法包含以下步骤：
[0008]
s1：预处理，对原始点云使用预处理操作，其目的是去除原始点 云中具有噪声得点云以及离群点，并且降低原始点云的存储；
[0009]
s2：粗配准；采用基于4pcs(4-points congruent sets)的方法，对 待配准点云进行初始对齐，将两个待配准点云大致对齐到一起；
[0010]
s3：精确配准：采用基于萤火虫优化的最近点迭代算法，通过找 到全局最优解，来实现精确配准。
[0011]
所述步骤s1中预处理具体步骤为:
[0012]
步骤1.1：对原始点云进行滤波操作用于平滑点云密度以及处理 离群点与噪声点；
[0013]
步骤1.2：对滤波处理过后的点云进行下采样操作用于减少原始 点云的储存空间，得到待粗配准的点云。
[0014]
所述步骤1.1中采用直通滤波方式对原始点云进行点云去噪处理； 所述步骤1.2中采用均匀下采样法对去除噪声点云进行下采样处理。
[0015]
所述步骤s2中4pcs粗配准具体步骤为:
[0016]
步骤2.1：首先在源点云中随机选择四个共面不共线的四个点。 相互连接并分别计算对应点比率；
[0017]
步骤2.2：在目标点云中，将所有点两两相连，根据上述计算的 比率，分别在每条连接线上计算可能存在的交点；
[0018]
步骤2.3：若在目标点云中，存在两交点在空间中位置是相等的, 同时两点之间的距离和源点云上的对应点之间的距离相等，其余两点 同理，我们认为在目标点云中成功找到对应点；
[0019]
步骤2.4：进而将两个点云按照两个对应点关系进行刚性变换， 计算源点云和经过变换矩阵变换后的目标点云中，最近点距离小于某 个阈值的点的数目，该数目用来表征变换矩阵的质量，然后迭代上面 的四个步骤，至到变换矩阵的质量最佳。此时的变换矩阵就是两幅点 云之间的粗配准的结果。
[0020]
所述步骤2.1中，首先在源点云中随机选择四个共面不共线的四 个点。分别连接a，b和成c，d，相交于点e，计算相对应的比率， 其方法为：
[0021][0022][0023]
其中r1、r2所述步骤2.1中源点云中对应点比率。
[0024]
所述步骤2.2中，在目标点云中，将所有点两两相连，根据这两 个比率，分别在每条连接线上计算可能存在的交点的e1和e2，其公 式为：
[0025]
e1＝q1+r1(q
2-q1)
ꢀꢀꢀꢀ
(3)
[0026]
e2＝q1+r1(q
2-q1)
ꢀꢀꢀꢀ
(4)
[0027]
所述步骤s3中精确配准具体步骤为：
[0028]
步骤3.1：在目标点云的解空间中随机散布多个萤火虫个体；
[0029]
步骤3.2：每只萤火虫个体其所处位置不同而发出不同强度的荧 光亮度，以此计算荧光亮度；
[0030]
步骤3.3：比较目标点云中每只萤火虫亮度，亮度高的萤火虫个 体能够吸引亮度低的萤火虫个体朝自己移动；
[0031]
步骤3.4：计算更新后的位置并且经过多次个体位置迭代后，所 有萤火虫都将聚集在亮度最高的萤火虫个体的位置上，从而寻找到目 标函数的最优值。
[0032]
所述步骤3.2中，计算萤光亮度的方法为：
[0033][0034]
其中，i0是萤火虫个体的自身荧光亮度，也是该个体的最大 荧光亮度；γ为光强吸收系数，体现了荧光随距离增加和传播媒介的 吸收逐渐减弱的特性，一般情况下设置为常数；r
ij
为萤火虫i与萤火 虫j间的距离。
[0035]
所述步骤3.3中，计算萤火虫吸引度方法为：
[0036][0037]
式中，β0代表光源处(r＝0)的吸引度，也是该个体的最大吸引 度；γ、r
ij
意义同上。吸引度与亮度相关，萤火虫个体的亮度越亮， 其吸引力越高，越能吸引周围亮度较弱的萤火虫朝该方向移动，当发 光亮度相同时，萤火虫个体进行随机移动。
[0038]
所述步骤3.4中，计算萤火虫更新位置方法为：
[0039]
xi＝xi+β
×
(x
j-xi)+α
×
(rand-1/2)
ꢀꢀꢀꢀ
(7)
[0040]
式中，xi、xj为萤火虫i和j所处的空间位置；α为步长因子， 取值为[0，1]上的常数；rand是随机因子，在[o，1]上服从均匀分布。
[0041]
由于上述技术方案运用，本发明与现有技术相比具有下列优点： 本发明能够快速、精准的实现点云配准，在保证精度的前提下，防止 配准陷入局部最优。
附图说明
[0042]
图1是本发明的一种基于萤火虫优化的点云分步配准算法的流程 图；
具体实施方式
[0043]
下面参见图1对本发明所述一种基于萤火虫优化的点云分步配准 方法进行详细说明。
[0044]
如图1所示，为了得到更好的点云配准效果，提供了一种基于萤 火虫优化的点云分步配准算法方法，包括步骤如下：
[0045]
s1：预处理，对原始点云使用预处理操作，其目的是去除原始点 云中具有噪声得
点云以及离群点，并且降低原始点云的存储；
[0046]
s2：粗配准；采用基于4pcs的方法，对待配准点云进行初始对 齐，将两个待配准点云大致对齐到一起；
[0047]
s3：精确配准：采用基于萤火虫优化的最近点迭代算法，通过找 到全局最优解，来实现精确配准。
[0048]
所述步骤s1中预处理具体步骤为:
[0049]
步骤1.1：对原始点云进行滤波操作用于平滑点云密度以及处理 离群点与噪声点；
[0050]
步骤1.2：对滤波处理过后的点云进行下采样操作用于减少原始 点云的储存空间，得到待粗配准的点云。
[0051]
所述步骤1.1中采用直通滤波方式对原始点云进行点云去噪处理； 所述步骤1.2中采用均匀下采样法对去除噪声点云进行下采样处理。
[0052]
1.去噪
[0053]
在获取数据过程中，因为人为的扰动或者扫描仪本身的缺陷使得生 成的三维数据往往带有噪声，从而使所获得的测量数据与实物存在一 定的偏差，因此在对实测三维数据进行相关数字几何处理和应用之前 必须对其进行去噪，目的是有效剔除噪声点、使重建表面模型光顺平 滑，并保持采样表面原有的拓扑和几何特征不变。本文采用直通滤波 法对原始点云进行剔除噪声操作。
[0054]
通过在点云的指定维度上设置一个阈值范围，将这个维度上的数据 分为在阈值范围内与不在阈值范围内，从而选择过滤与否。
[0055]
2.下采样
[0056]
由于点云的海量和无序性，直接处理的方式在对邻域进行搜索时 需要较高的计算成本。一个常用的解决方式就是对点云进行下采 样，将对全部点云的操作转换到下采样所得到的点上，降低计算 量。本文采用均匀下采样法对点云进行处理。
[0057]
首先需要选取一个种子点，并设置一个内点集合，每次从点云中 不属于内点的集合找出一点距离内点最远的点，这里的距离计算 方式为该点至内点所有点的最小距离。
[0058]
所述步骤s2中4pcs粗配准具体步骤为:
[0059]
步骤2.1：首先在源点云中随机选择四个共面不共线的四个点。 相互连接并分别计算对应点比率；
[0060]
步骤2.2：在目标点云中，将所有点两两相连，根据上述计算的 比率，分别在每条连接线上计算可能存在的交点；
[0061]
步骤2.3：若在目标点云中，存在两交点在空间中位置是相等的, 同时两点之间的距离和源点云上的对应点之间的距离相等，其余两点 同理，我们认为在目标点云中成功找到对应点；
[0062]
步骤2.4：进而将两个点云按照两个对应点关系进行刚性变换， 计算源点云和经过变换矩阵变换后的目标点云中，最近点距离小于某 个阈值的点的数目，该数目用来表征变换矩阵的质量，然后迭代上面 的四个步骤，至到变换矩阵的质量最佳。此时的变换矩阵就是两幅点 云之间的粗配准的结果。
[0063]
所述步骤2.1中，首先在源点云中随机选择四个共面不共线的四 个点。分别连接
a，b和成c，d，相交于点e，计算相对应的比率， 其方法为：
[0064][0065][0066]
其中r1、r2所述步骤2.1中源点云中对应点比率。
[0067]
所述步骤2.2中，在目标点云中，将所有点两两相连，根据这两 个比率，分别在每条连接线上计算可能存在的交点的e1和e2，其公 式为：
[0068]
e1＝q1+r1(q
2-q1)
ꢀꢀꢀꢀ
(3)
[0069]
e2＝q1+r2(q
2-q1)
ꢀꢀꢀꢀ
(4)
[0070]
所述步骤s3中精确配准具体步骤为：
[0071]
步骤3.1：在目标点云的解空间中随机散布多个萤火虫个体；
[0072]
步骤3.2：每只萤火虫个体其所处位置不同而发出不同强度的荧 光亮度，以此计算荧光亮度；
[0073]
步骤3.3：比较目标点云中每只萤火虫亮度，亮度高的萤火虫个 体能够吸引亮度低的萤火虫个体朝自己移动；
[0074]
步骤3.4：计算更新后的位置并且经过多次个体位置迭代后，所 有萤火虫都将聚集在亮度最高的萤火虫个体的位置上，从而寻找到目 标函数的最优值。
[0075]
所述步骤3.2中，计算萤光亮度的方法为：
[0076][0077]
其中，i0是萤火虫个体的自身荧光亮度，也是该个体的最大 荧光亮度；γ为光强吸收系数，体现了荧光随距离增加和传播媒介的 吸收逐渐减弱的特性，一般情况下设置为常数；r
ij
为萤火虫i与萤火 虫j间的距离。
[0078]
所述步骤3.3中，计算萤火虫吸引度方法为：
[0079][0080]
式中，β0代表光源处(r＝0)的吸引度，也是该个体的最大吸引 度；γ、r
ij
意义同上。吸引度与亮度相关，萤火虫个体的亮度越亮， 其吸引力越高，越能吸引周围亮度较弱的萤火虫朝该方向移动，当发 光亮度相同时，萤火虫个体进行随机移动。
[0081]
所述步骤3.4中，计算萤火虫更新位置方法为：
[0082]
xi＝xi+β
×
(x
j-xi)+α
×
(rand-1/2)
ꢀꢀ
(7)
[0083]
式中，xi、xj为萤火虫i和j所处的空间位置；α为步长因子， 取值为[o，1]上的常数；rand是随机因子，在[0，1]上服从均匀分布。
[0084]
由于上述技术方案运用，本发明与现有技术相比具有下列优点： 本发明能够快速、精准的实现点云配准，在保证精度的前提下，防止 配准陷入局部最优。
[0085]
以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在 本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均 应包含在本发明的保护范围之内。

技术特征：
1.一种基于萤火虫优化的点云分步配准方法，其特征在于，包含以下步骤：s1：预处理，对原始点云使用预处理操作，其目的是去除原始点云中具有噪声得点云以及离群点，并且降低原始点云的存储；s2：粗配准；采用基于4pcs(4-points congruent sets)的方法，对待配准点云进行初始对齐，将两个待配准点云大致对齐到一起；s3：精确配准：采用基于萤火虫优化的最近点迭代算法，通过找到全局最优解，来实现精确配准。2.根据权利要求1所述所述基于萤火虫优化的点云分步配准方法，其特征在于，步骤s1中预处理包含以下步骤:步骤1.1：对原始点云进行滤波操作用于平滑点云密度以及处理离群点与噪声点；步骤1.2：对滤波处理过后的点云进行下采样操作用于减少原始点云的储存空间，得到待粗配准的点云。3.根据权利要求2所述所述基于萤火虫优化的点云分步配准方法，其特征在于，所述步骤1.1中采用直通滤波方式对原始点云进行点云去噪处理；所述步骤1.2中采用均匀下采样法对去除噪声点云进行下采样处理。4.根据权利要求1所述所述基于萤火虫优化的点云分步配准方法，其特征在于，所述步骤s2中4pcs粗配准包含以下步骤:步骤2.1：首先在源点云中随机选择四个共面不共线的四个点。相互连接并分别计算对应点比率；步骤2.2：在目标点云中，将所有点两两相连，根据上述计算的比率，分别在每条连接线上计算可能存在的交点；步骤2.3：若在目标点云中，存在两交点在空间中位置是相等的,同时两点之间的距离和源点云上的对应点之间的距离相等，其余两点同理，我们认为在目标点云中成功找到对应点；步骤2.4：进而将两个点云按照两个对应点关系进行刚性变换，计算源点云和经过变换矩阵变换后的目标点云中，最近点距离小于某个阈值的点的数目，该数目用来表征变换矩阵的质量，然后迭代上面的四个步骤，至到变换矩阵的质量最佳。此时的变换矩阵就是两幅点云之间的粗配准的结果。5.根据权利要求4所述所述基于萤火虫优化的点云分步配准方法，其特征在于，所述步骤2.1中，首先在源点云中随机选择四个共面不共线的四个点。分别连接a，b和成c，d，相交于点e，计算相对应的比率，其方法为：其方法为：其中r1、r2所述步骤2.1中源点云中对应点比率。6.根据权利要求4所述所述基于萤火虫优化的点云分步配准方法，其特征在于，所述步骤2.2中，在目标点云中，将所有点两两相连，根据这两个比率，分别在每条连接线上计算可
能存在的交点的e1和e2，其公式为：e1＝q1+r1(q
2-q1)
ꢀꢀꢀꢀ
(3)e2＝q1+r1(q
2-q1)
ꢀꢀꢀꢀꢀ
(4)。7.根据权利要求1所述所述基于萤火虫优化的点云分步配准方法，其特征在于，所述步骤s3中精确配准包含以下步骤:步骤3.1：在目标点云的解空间中随机散布多个萤火虫个体；步骤3.2：每只萤火虫个体其所处位置不同而发出不同强度的荧光亮度，以此计算荧光亮度；步骤3.3：比较目标点云中每只萤火虫亮度，亮度高的萤火虫个体能够吸引亮度低的萤火虫个体朝自己移动；步骤3.4：计算更新后的位置并且经过多次个体位置迭代后，所有萤火虫都将聚集在亮度最高的萤火虫个体的位置上，从而寻找到目标函数的最优值。8.根据权利要求7所述所述基于萤火虫优化的点云分步配准方法，其特征在于，所述步骤3.2中，计算萤光亮度的方法为：其中，i0是萤火虫个体的自身荧光亮度，也是该个体的最大荧光亮度；γ为光强吸收系数，体现了荧光随距离增加和传播媒介的吸收逐渐减弱的特性，一般情况下设置为常数；r
ij
为萤火虫i与萤火虫j间的距离。9.根据权利要求7所述所述基于萤火虫优化的点云分步配准方法，其特征在于，所述步骤3.3中，计算萤火虫吸引度方法为：式中，β0代表光源处(r＝0)的吸引度，也是该个体的最大吸引度；γ、r
ij
意义同上。吸引度与亮度相关，萤火虫个体的亮度越亮，其吸引力越高，越能吸引周围亮度较弱的萤火虫朝该方向移动，当发光亮度相同时，萤火虫个体进行随机移动。10.根据权利要求7所述所述基于萤火虫优化的点云分步配准方法，其特征在于，所述步骤3.4中，计算萤火虫更新位置方法为：x
i
＝x
i
+β
×
(x
j-x
i
)+α
×
(rand-1/2)
ꢀꢀꢀꢀꢀ
(7)式中，x
i
、x
j
为萤火虫i和j所处的空间位置；α为步长因子，取值为[0,1]上的常数；rand是随机因子，在[0,1]上服从均匀分布。由于上述技术方案运用，本发明与现有技术相比具有下列优点：本发明能够快速、精准的实现点云配准，在保证精度的前提下，防止配准陷入局部最优。

技术总结
一种基于萤火虫优化的点云分步配准方法，属于数据处理的技术领域。该方法首先根据输入的原始点云进行去除噪声平滑点云密度以及降低点云储存的预处理；再对预处理过后的待配准点云进行4点全等集法(4PCS)进行变换，通过刚性变换将待配准点云位置大致对齐；最后采用基于萤火虫优化的最近点迭代方法对粗配准后点云进行精细配准，得到最终配准点云。本发明能够快速、精准配准原始点云数据，在保证速度精度的前提下，避免优化求解过程中受初始变换矩阵影响从而陷入局部最优解。阵影响从而陷入局部最优解。阵影响从而陷入局部最优解。


技术研发人员：王宏达 钱建国
受保护的技术使用者：辽宁工程技术大学
技术研发日：2022.03.16
技术公布日：2022/7/5