一种基于法向量的点云自动配准方法

摘要

一种基于法向量的点云自动配准方法，处理对象为两幅及两幅以上相互间有重叠部分的三维点云数据，处理步骤为：(1)根据点云局部法向量的变化选取特征点；(2)设计一种直方图特征量对获得的每个特征点进行特征描述；(3)通过比较特征点的直方图特征向量获得初始匹配点对；(4)运用刚性距离约束条件结合RANSAC算法获取精确匹配点对，并利用四元素法计算得到初始配准参数；(5)采用改进的ICP算法对点云精确配准。按照上述步骤可对点云进行自动配准，本发明提出的特征描述简单且辨识度高，同时具有较高的鲁棒性，配准精度和速度都有一定的提高。

主权项

1.一种基于法向量的点云自动配准方法，其特征在于：包括以下步骤：步骤1：基于法向量信息获取待匹配两个点云中的特征点集,具体步骤如下：步骤1.1：采用三维扫描仪获取带有法向量信息的多视角点云数据,且相邻视角获得的点云间有重叠部分，定义点云中重叠部分的某一点p_i的特征度f_i为点p_i的法向量与其k个近邻点法向量夹角的算术平均值：$f_i=\frac{1}{k}{\Sigma }_{j=1}^k{\theta }_{\mathrm{ij}}$   （1）式其中某一点p_i的k个近邻点是指与点p_i欧氏距离最近的k个点，θ_ij为点p_i的法向量与其近邻点p_j的法向量的夹角,k为5≤k≤20的自然数；步骤1.2：选取阈值ε₁，去掉点云中f_i≤ε₁的平坦部分，保留f_i＞ε₁的点，对于保留点中的任一点p_m，若其满足：f(p_m)＝max(f(p_m1),f(p_m2),…,f(p_mk))  （2）式则将p_m作为特征点,其中f(p_m1),f(p_m2),…,f(p_mk)为点p_m的k个近邻点的特征度，其中阈值ε₁取值范围为5°≤ε₁≤10°；步骤1.3：利用步骤1.1和步骤1.2所述的特征点提取方法，分别对两个点云进行特征点提取，设待配准的两个点云数据分别为点集P和点集Q，其中点集Q为参考点云数据，得到待配准点云的特征点集为Pt＝{pt₁,pt₂,pt₃,…pt_m′}，参考点云的特征点集为Qt＝{qt₁,qt₂,qt₃,…qt_n′}，其中m′和n′分别为P和Q的特征点的个数；步骤2：建立特征点集的直方图特征描述，方法如下：步骤2.1：对于特征点集Pt中的每个点pt_i，在点集P中以pt_i为原点，半径为γ的球域内的点作为pt_i的邻近点，标记为N(pt_i)，其中γ取值范围为点云的平均点间距离的5～10倍；步骤2.2：根据点pt_i与邻近点N(pt_i)之间的几何关系，建立三种特征描述：f₁＝acos<n_i,v_k>  （3）式f₂＝<n_i,(s_k-pt_i)>  （4）式f₃＝||s_k-pt_i||  （5）式其中n_i为点pt_i的法向量，v_k为pt_i邻近某个点N(pt_i)的法向量，s_k为pt_i某个邻近点N(pt_i)的三维坐标；其中，式（3）中特征值f₁是点集Pt中一点pt_i的法向量与其邻近一点N(pt_i)的法向量的夹角，根据夹角大小将其分成[0,20]、(20,40]、(40,60]和(60,180]4个间隔；式（4）中特征值f₂是两个向量点积，其中一个是点pt_i的法向量，另一个是该点pt_i与其邻近一点N(pt_i)之间的点间向量，根据f₂是否大于0，将f₂分成2个间隔；式（5）中特征值f₃是一点pt_i与其邻近点中一点N(pt_i)间的欧氏距离，根据阈值将其分成2个间隔；根据这三个特征值的间隔分类，我们可建立一个间隔数为4×2×2＝16的直方图，对应地得到一个16维的特征向量，其中γ取值范围为点云的平均点间距离的5～10倍；步骤2.3：根据所述步骤2.2中三个特征值f₁、f₂、f₃，定义idex＝k₁+k₂·4+k₃·4·2；若特征值f₁落入[0,20]间隔中则对应地将k₁记为1，若特征值f₁落入(20,40]间隔中则对应地将k₁记为2，若特征值f₁落入(40,60]间隔中则对应地将k₁记为3，若特征值f₁落入(60,180]间隔中则对应地将k₁记为4；若特征值f₂的值小于0，则将k₂记为1，否则记为0；若特征值f₃的值大于则将k₃记为1，否则记为0；根据idex的值确定N(pt_i)中一点属于直方图中的间隔位置，遍历一个点pt_i的所有邻近点N(pt_i)，得到落入每个间隔中的邻近点N(pt_i)的数量，以N(pt_i)中落入每个间隔中的点数占其总数的百分比作为对应间隔的值，记此值为特征向量h1_i；步骤2.4：根据所述步骤2.1至2.3，建立点集Pt和Qt中每个点的特征向量，得到点集Pt和Qt的特征向量集h1和h2；步骤3：采取特征向量间的欧氏距离作为比较准则，比较所述步骤2中获得的特征向量集h1和h2中的特征向量，在点集Qt中为点集Pt中每个点找到其初始匹配点：选取阈值ε₂，特征向量的距离小于ε₂时，该特征向量所对应点集Pt和Qt中的点作为初始匹配点对，记为：$\mathrm{Matchdots}=\left\{(s_i^1,s_i^2)\right|s_i^1\in \mathrm{Pt},s_i^2\in \mathrm{Qt},i=\mathrm{1,2,3}···\mathrm{num}\left(\mathrm{Matchdots}\right)\}$其中num(Matchdots)是初始匹配点对的数量，ε₂取0.05；步骤4：结合刚性距离约束条件，使用一种自适应的RANSAC算法获取精确匹配点对，具体步骤如下：步骤4.1：Matchdots中的任意两个点对和如果是正确的匹配点对，那么根据刚体变换的距离不变性得到：其中dist表示两点间的距离；选取ε₃＞0，对每个点对计算Matchdots中除点对以外与该点对符合刚性距离约束的点对的数目num_i，若Matchdots中一个点对满足下式：$\frac{|\mathrm{dist}(s_i^1,s_j^1)-\mathrm{dist}(s_i^2,s_j^2)|}{\mathrm{dist}(s_i^1,s_j^1)+\mathrm{dist}(s_i^2,s_j^2)}<{ϵ}_3$   （6）式则将点对记为相对于点对的符合距离约束的点对，同时将的num_i值加1，其中ε₃取0.02；步骤4.2：对Matchdots中每个点对根据所述步骤4.1计算num_i值，然后按照num_i值从大到小对Matchdots中点对进行排序，选取前N个点对，N为N≤num(Matchdots)的自然数；使用RANSAC算法对这N个点对检验是否为正确匹配点对，具体检验方法为：步骤4.2.1：从这N个点对中随机选取3个点对作为一个样本；步骤4.2.2：假设这3个点对为正确匹配点对，计算刚体变换矩阵T；步骤4.2.3：判断其余N-3个点对在此刚体变换矩阵T下是否为正确匹配：如果小于预定义的阈值ε₄，则认为是正确的匹配点对，记为内点；如果大于等于预定义的阈值ε₄，则认为是错误的匹配点对，记为外点；所有内点组成本次采样的一致集；其中，ε₄取值范围为点云的平均点间距离的2倍；步骤4.2.4：重复所述步骤4.2.1至步骤4.2.3，直到N个点中所有3点组合的样本都遍历了，循环次数达到采样次数上限后，将内点数目最多的刚体变换矩阵作为正确的刚体变换矩阵，据此变换矩阵求得初始匹配点对中的内点作为最终的精确匹配点对，记为：Matchdots1＝{(m_i,m′_i)|m_i∈P,m′_i∈Q,i＝1,2,3…n}其中n为精确匹配点对的数目；步骤5：利用四元素法计算初始配准参数，具体步骤如下：步骤5.1：计算点集{m_i|m_i∈P，i＝1,2,...,n}的质心μ和{m′_i|m′_i∈Q，i＝1,2,...,n}的质心μ′：$\left\{\begin{array}{c}\mu =\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{m}_i\\ {\mu }^{\prime }=\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{m^{\prime }}_i\end{array}\right.$   （7）式式（7）中，n为精确匹配点对的数目；步骤5.2：将点集{m_i|m_i∈P，i＝1,2,...,n}和{m′_i|m′_i∈Q，i＝1,2,...,n}做相对于质心μ、μ′的平移，设平移后的点集分别为{h_i}和{h′_i}：$\left\{\begin{array}{c}{h}_i=m_i-\mu \\ {h^{\prime }}_i={m^{\prime }}_i-{\mu }^{\prime }\end{array}\right.$   （8）式步骤5.3：根据平移后的所得点集{h_i}和{h′_i}计算相关矩阵K：$K=\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{h}_i{\left({h^{\prime }}_i\right)}^T$   （9）式式（9）中，n为精确匹配点对的数目；步骤5.4：由相关矩阵K中各元素K_ij(i,j＝1,2,3,4)构造出四维对称矩阵K_a：$K_a=\left[\begin{array}{cccc}{K}_{11}+K_{22}+K_{33}& K_{32}-K_{23}& K_{13}-K_{31}& K_{21}-K_{12}\\ K_{32}-K_{23}& K_{11}-K_{22}-K_{33}& K_{12}+K_{21}& K_{31}+K_{13}\\ K_{13}-K_{31}& K_{12}+K_{21}& {-K}_{11}+K_{22}-K_{33}& K_{23}+K_{32}\\ K_{21}-K_{12}& K_{31}+K_{13}& K_{23}+K_{32}& {-K}_{11}-K_{22}+K_{33}\end{array}\right]$   （10）式步骤5.5：计算K_a的最大特征根所对应的单位特征向量q：$q={\left[\begin{array}{cccc}{q}_0& q_1& q_2& q_3\end{array}\right]}^T$   （11）式步骤5.6：由步骤5.5中计算所得单位特征向量q，计算旋转矩阵R：$R=\left[\begin{array}{ccc}{q}_0^2+q_1^2-q_2^2-q_3^2& 2(q_1{q}_2-q_0{q}_3)& 2(q_1{q}_3+q_0{q}_2)\\ 2(q_1{q}_2+q_0{q}_3)& q_0^2+q_2^2-q_1^2-q_3^2& 2(q_2{q}_3-q_0{q}_1)\\ 2(q_1{q}_3-q_0{q}_2)& 2(q_2{q}_3+q_0{q}_1)& q_0^2+q_3^2-q_1^2-q_2^2\end{array}\right]$   （12）式步骤5.7：由步骤5.6计算所得旋转矩阵R，求解平移矢量T：T＝μ′-Rμ  （13）式步骤6：采用改进的ICP算法对点云精确配准，具体步骤如下：步骤6.1：利用步骤5中获得的配准参数R和T，根据式（14）将待配准点云P中的每个点p_i变换到参考点云Q所在的坐标系下得到点p_0i，将转换后得到的初始配准后的点云记为P₀；其中：p_0i＝R·p_i+T  （14）式步骤6.2：令目标点集为P_m,参考点集为Q,取m＝0,利用改进的ICP算法进行精确配准：步骤6.2.1：计算最近点：对目标点集P_m中任一点p_mi,计算该点与参考点集Q中每个点间的欧氏距离,对于点集Q中与其欧氏距离最小的点q_j，选取阈值σ,若：两者间欧氏距离||p_mi,q_j||²＜σ，则将p_mi作为内点并记为并将q_j作为其对应匹配点并记为这样便得到一组内点匹配点对否则将其作为外点去除；其中当m＝0时,阈值σ取为点云Q点间平均距离的3倍；对目标点集P_m中所有点作以上操作，最终得到内点匹配点集，记为：$M^m=\left\{(p_i^m,q_i^m)\right|p_i^m\in P_m,q_i^m\in Q,i=\mathrm{1,2,3}···n_p\},$其中n_p为点对数目；步骤6.2.2：利用步骤6.2.1中获得内点匹配点集来计算配准参数：计算使得式（15）中err取得最小时的旋转矩阵R_m和平移矩阵T_m作为新的配准参数：$\mathrm{err}=\frac{1}{n_p}\underset{i=1}{\overset{n_p}{\Sigma }}{\left|\right|q_i^m-(R_m{p}_i^m+T_m)\left|\right|}^2$   （15）式其中err为本次配准的误差，n_p为点对数目；步骤6.2.3：将计算得到的配准参数用于点集P_m中的每个点p_mi得到新的点集P′$p_i^{\prime }=R_m{p}_{\mathrm{mi}}+T_m$   （16）式其中，为点集P′中的点；步骤6.2.4：检验迭代终止的条件：设定阈值τ=0.00001，当满足：σ-err＜τ，则迭代过程结束；否则令m＝m+1，σ＝err,P_m＝P′转步骤6.2.1；迭代过程结束后得到的点集P′即为最终的精确配准结果。