一种基于自适应烟花与KD树算法的三维点云配准方法

摘要

本发明公开了一种基于自适应烟花与KD树算法的三维点云配准方法，包括确定目标点集与参考点云重叠点并在目标点集中查找重叠点的最近邻点集，粗配准采用一种自适应烟花算法进行随机配准优化，而精配准使用KD树搜索算法改进的近点迭代的算法进行点云的精确配准。本文提出的点云配准方法减少了配准的时间同时提高了配准的精度。

说明书

技术领域

本发明涉及三维点云配准算法领域。具体涉及到立体腹腔镜增强现实导航系统中多模态医学图像通过三维重建后进行的3D-3D特征点云刚性配准。

背景技术

随着计算机技术的不断发展，医学技术也随之有了长足的进步。在过去的几十年里，微创手术已经逐渐变得比开放手术更受欢迎，因为相比于开放手术，微创手术有减小创伤面积、降低感染率，缩短住院时间，患者康复快等特点。腹腔镜手术是应用最多的微创手术形式。但是，这种手术方式会使外科医生失去对现场的直接视觉反馈，并且还具有术中视野范围过小，需要来回查看术前图像等问题。因此，增强现实导航技术就成了缓解这些缺陷的一个可行的解决方案。利用这种技术能够让医生在术中得到更多的术前图像信息，增加手术的精度，减轻医生需要多次切换屏幕查看图像的负担。

虽然腹腔镜手术增强现实导航系统有众多优点，但是系统中图像配准过程耗时长，精度低的问题依然存在，需要对配准的算法进行优化。目前对多模态图像配准可分为基于优化方法的和基于机器学习方法的。而在基于优化方法里又可细分为基于最大期望方法、非线性优化方法、基于分支与边界方法、随机配准方法和运动框架多视图配准方法。

本发明提出的基于自适应烟花与KD树算法的三维点云配准方法，是一种粗配准与精配准相结合的三维点云配准方法，粗配准属于一种基于优化方法的随机配准优化，而精配准使用KD树搜索改进近点迭代的算法。本文提出的点云配准方法减少了配准的时间同时提高了配准的精度。

发明内容

本发明提出了一种基于自适应烟花与KD树算法的三维点云配准方法。该算法主要分为两个部分组成，首先通过自适应烟花算法对两个点云集进行粗配准，然后使用基于KD树搜索算法的改进近点迭代算法进行精配准。

一种基于自适应烟花与KD树算法的三维点云配准方法，具体包括如下步骤：

步骤1：输入两个点云集P和Q，确定P中与Q点集重叠区域的点集p，Q点集建立KD 树并在其中搜索点集p的最近邻点集q；

步骤2：确定烟花算法的适应度函数为：

式中d即为适应度，n为p点集中的点的个数，p

步骤3：通过上一步优化得到的R、T变换p点集得到p′，设置迭代次数k值(初始值k＝1) 并在Q点集的KD树数据结构中重新搜索与p′点集对应的最近邻点集q′；

步骤4：利用四元数法计算p′点集到q′点集的变换矩阵R

最小的值，其中利用解得的R

步骤5：计算p″点集与q′点集在这一代平均距离d

判断是否满足收敛条件||d

步骤6：根据求得的变换矩阵变换点云P到点云Q得到最终配准结果。

进一步地，所述的一种基于自适应烟花与KD树算法的三维点云配准方法，其特征在于：所述自适应烟花算法步骤如下：

步骤1：建立适应度函数，确定优化目标，设置初始位置，种群个数等参数；

步骤2：计算初始适应度及初始自适应半径；

步骤3：计算爆炸火花数以及爆炸半径(不包括自适应半径)；

步骤4：产生火花及高斯变异火花；

步骤5：评估所有火花适应度并计算自适应爆炸半径；

步骤6：保留最佳个体，随机精选策略产生其余烟花；

步骤7：判断是否满足迭代条件；

步骤8：输出最优解及对应的适应度。

进一步地，所述的自适应烟花算法，其特征在于：

引入了一种自适应爆炸半径机制，利用已经生成的火花计算最佳烟花的爆炸半径，选择一个个体计算其与最优个体的距离作为下一代最佳烟花的半径，被选的个体它的适应度要比这一代的烟花差，并且其到最优个体的距离为最短距离，即：

f(s

s

与现有三维配准方法相比，本发明的优点和有益效果是：可以较少点云配准所需的时间，提高点云配准的精度。

附图说明

图1为本发明的整体算法流程；

图2为本发明的自适应烟花算法粗配准流程；

图3为本发明的四元数法求解变换矩阵流程。

具体实施方式

为了使本发明所解决的技术问题、技术方案及有益效果更加清楚明白，下面将结合附图及实施例，对本发明做进一步的详细说明。

如图1所示，本发明的一种基于自适应烟花与KD树算法的三维点云配准方法，共有6 个步骤：

步骤1：输入两个点云集P和Q，确定P中与Q点集重叠区域的点集p，Q点集建立KD 树并在其中搜索点集p的最近邻点集q；

步骤2：确定烟花算法的适应度函数为：

式中d即为适应度，n为p点集中的点的个数，p

步骤3：通过上一步优化得到的R、T变换p点集得到p′，设置迭代次数k值(初始值k＝1) 并在Q点集的KD树数据结构中重新搜索与p′点集对应的最近邻点集q′；

步骤4：利用四元数法计算p′点集到q′点集的变换矩阵R

最小的值，其中利用解得的R

步骤5：计算p″点集与q′点集在这一代平均距离d

判断是否满足收敛条件||d

步骤6：根据求得的变换矩阵变换点云P到点云Q得到最终配准结果。

如图2所示，本发明的自适应烟花算法具体实施步骤如下：

步骤1：建立适应度函数，确定优化目标为：

设置n个初始位置，种群个数设置为m个；

步骤2：计算初始适应度及初始自适应半径；

步骤3：计算爆炸火花数以及爆炸半径(不包括自适应半径)，爆炸火花数目的计算公式为：

式中S

为了限制烟花爆炸产生的火花数量过大或过小，我们设置了以下限制公式来计算每个烟花产生的火花数量：

式中

基础的爆炸半径计算公式为：

在自适应烟花算法中引入了最小爆炸半径检测策略。k为第k维处爆炸半径最小的检测阈值：

式中，A

式中，t为当前迭代的求值号，E

步骤4：产生火花及高斯变异火花，爆炸火花通过移动算子在爆炸半径内移动，移动算子为：

式中，

高斯火花的产生方式为：

x

式中，g是均值为0，方差为1的高斯随机变量，x

步骤5：评估所有火花适应度并计算自适应爆炸半径，自适应爆炸半径机制，利用已经生成的火花计算最佳烟花的爆炸半径，选择一个个体计算其与最优个体的距离作为下一代最佳烟花的半径，被选的个体它的适应度要比这一代的烟花差，并且其到最优个体的距离为最短距离，即：

f(s

s

步骤6：保留最佳个体，随机精选策略产生其余烟花，随机精选策略首先找出适应度值最佳的个体，然后对其他个体采用随机选择策略，作为下一代的烟花种群进行迭代；

步骤7：判断是否满足迭代条件，

步骤8：输出最优解及对应的适应度。

如图3所示，本发明的四元数法求解变换矩阵实施步骤如下：

步骤1：求解点集p′和q′的质心坐标O

步骤2：对点集p′和q′进行集中，加入质心坐标的影响，生成新的点集：

式中x

步骤3：建立对称矩阵Q：

其中x、y、z为新生成的点集中某个点的坐标值，下标m、n分别为由点集p′和q′生成的新点集坐标点标识；

步骤4：求解Q的最大特征值和最大特征值对应的特征向量(w,m,n,p)；

步骤5：构造旋转矩阵：

步骤6：求解平移向量T：

T＝O

R'是矩阵R的转置矩阵。

本发明的上述实施例是为了清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定，对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动，这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所做的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。