一种自适应的无标志点三维点云自动拼接方法

摘要

本发明属于三维测量邻域中的点云数据拼接技术，具体为一种自适应的无标志点三维点云自动拼接方法，本发明包括几何特征点的查找，图像特征点的查找，配准算法选择模型的建立，基于RANSAC的几何特征点匹配，利用RANSAC排除误匹配图像特征点，利用SVD算法求解旋转平移矩阵RT，最后利用RT矩阵完成两片点云拼接。该方法因为利用物体特征点来代替标志点进行拼接，可用于不能粘贴标记点的测量场合；同时依靠对应特征点来计算多视点云的变换矩阵，无需依赖点云的初始姿态，且配准算法选择模型的建立使系统能自适应选择合适的配准算法，实现不同被测物体的稳定拼接。

说明书

技术邻域

本发明涉及到一种自适应的无标志点三维点云自动拼接方法，它是三 维点云数据处理的一种方法，属于三维测量领域中的点云数据拼接技术。

背景技术

面结构光三维测量技术(参见文献1：李中伟.基于数字光栅投影的结 构光三维测量技术与系统研究[D][D].武汉:华中科技大学,2009)受单次 测量范围的限制，需从不同方位对被测物进行多次测量以获取完整的几何 模型，其中多视点云自动拼接是关键。

为了实现多视点云自动拼接，常用的方法有以下两种：(1)基于标志 点的自动拼接方法，该方法通过在被测物体表面粘贴人工标志点来实现辅 助拼接。其拼接精度较高，但会破坏被测物体表面的真实三维数据，同时 前期贴点增加了测量时间，而且无法测量表面不能标记的物体(如珍贵文 物，人体)，限制了使用范围。(2)无标记点的自动拼接方法。常见的无 标记点拼接方法包括迭代点最近点算法(iterative closest point，ICP)、基 于几何特征的配准算法和基于纹理的配准算法。其中，ICP算法对点云初始 姿态的要求很高，无法对初始位置相差较大的点云进行拼接。基于几何特 征的配准算法只适用于表面几何形貌比较复杂的物体，无法实现形状简单 或对称物体的点云配准。基于纹理的配准算法只适用于表面纹理丰富的物 体，在对纹理单一的物体进行测量时稳定性较差。

综上所述：现有的三维点云自动拼接方法都存在一定的局限性，尚不 能满足实际应用的要求。因此需要一种有效的稳定的点云拼接方法，能够 实现源点云和目标点云最优配准。

发明内容

本发明提出了一种自适应的无标志点三维点云自动拼接方法，该方法 可自适应的实现不同物体的无标志点三维点云自动拼接，且拼接具有良好 的稳定性。

本发明提供的一种自适应的无标志点三维点云自动拼接方法，该方法 包括下述步骤：

第1步在源点云和目标点云中利用点特征直方图法查找几何特征点； 在两次拍摄图片中查找图像特征点；

第2步利用查找出的几何特征点和图像特征点建立配准算法选择模型， 计算配准算法判断因子D_r的值，依据该值自动选择合适的配准算法：当 D_r＞0时，进入第3步，当D_r＜0时，转入第4步，当D_r＝0时，提示用户 通过引入标志点进行点云拼接；

所述配准算法选择模型为：

$D_r=\left(\begin{array}{cc}{w}_1(\frac{p_1-p}{p}-\frac{n_1-n}{n})+w_2(\frac{p_2-p}{p}-\frac{n_2-n}{n});& p_1>p,n_1>n\\ 1;& p_1>p,n_1<n\\ -1;& p_1<p,n_1>n\\ 0;& p_1\le p,n_1\le n\end{array}\right)$

其中，p₁，p₂分别代表两幅采样点云中几何特征点数目占其采样点点 数的比例；n₁，n₂分别代表两次拍摄图片中图像特征点的数目；p为几何特 征阈值，w₁和w₂是描述两个对比差值的权重因子；

第3步对于第1步查找出的几何特征点，利用RANSAC算法进行几 何特征点的匹配，得到每一个查找点对应的初匹配点集Q′，再利用SVD奇 异值分解法计算旋转矩阵R和平移矩阵T，然后进入第5步；

第4步对于第1步查找出的图像特征点，利用RANSAC算法查找对 应点，再利用SVD奇异值分解法计算旋转矩阵R和平移矩阵T；

第5步利用旋转矩阵R和平移矩阵T对目标点云进行旋转平移，完 成拼接。

本发明利用物体表面的几何特征和纹理信息建立一个配准算法选择模 型，根据该模型系统可自适应地选择合适的配准算法。在对不同物体进行 测量拼接时，利用物体表面固有的几何特征和纹理信息进行多视点云数据 的拼接，可提高拼接稳定性。与现有方法相比，本方法的优点在于：

1)利用物体特征点来代替标志点进行拼接，可用于不能粘贴标记点的 测量场合，减少了点云后处理的工作量。

2)利用物体表面的几何特征和纹理信息来实现物体特征点的查找和匹 配以实现最终拼接，不依赖点云本身初始姿态。

3)将几何特征和纹理信息相结合建立配准算法选择模型使系统能自适 应选择合适的配准算法，提高了拼接的稳定性。

附图说明

图1为本发明多视点云自适应拼接的整体流程图；

图2为查询点的点特征直方图计算区域；

图3为两点之间的固定局部坐标系定义。

具体实施方式

下面结合附图对本发明的具体实施方式作进一步说明。在此需要说明 的是，对于这些实施方式的说明用于帮助理解本发明，但并不构成对本发 明的限定。此外，下面所描述的本发明各个实施方式中所涉及到的技术特 征只要彼此之间未构成冲突就可以相互组合。

如图1所示，本发明提供的一种自适应性三维点云自动拼接方法，该 方法包括下述步骤：

S101在源点云和目标点云中利用点特征直方图法查找几何特征点。

点特征直方图为物体表面点几何特征的统计直方图表示。对点云对应 曲面的六维姿态来说它具有不变性，并且在不同的采样密度或邻域的噪音 等级下具有鲁棒性。点特征直方图法是基于点与其定义邻域之间的关系以 及他们的估计法线。具体查找步骤如下：

第1.1步对拍摄获取的两幅多视点云按比例(通常为总点数的10～ 15％)进行采样，计算每个采样点的法向量；将采样点中的每一点视为查询 点，定义半径(通常为3～4倍的点间距)确定出查询点的邻域，该邻域内 的采样点称为邻域点。图2展示了查询点p_q及其邻域点p_k的位置关系，其 中查询点p_q为采样点云中的任一点。

第1.2步为了计算邻域内任意两点s、t的位置关系及对应法线之间的 相对偏差，在其中的一个点上定义一个固定的局部坐标系，如图3所示， 其中：

$u=n_s,d=\frac{(p_t-p_s)}{{\left|\right|p_t-p_s\left|\right|}_2},v=u\times d,w=u\times v---\left(1\right)$

p_s，p_t为查询点p_q邻域内点s、t的空间坐标，n_s，n_t为点s、t相应的法 向量，||p_t-p_s||₂为该两点的空间距离，d表示该两点连线方向上的单位向量。

利用式I得到如图3所示的uvw坐标系，两点之间的位置关系和法线偏 差可以用一组角度来表示，如式(2):

其中，(w·n_t/u·n_t)表示w、n_t/u、n_t的点乘，将α，θ的取值范 围分别划分为b个子区间，则总共生成了b³个区域，判断两点的α，θ值 所处的区域，则该区域的点数目加一；计算查询点p_q邻域内每对点的α，θ值，判断其所在区域，统计落在每个区域的点数目，生成点p_q的点特征直 方图。

第1.3步利用所有采样点的点特征直方图生成平均特征直方图 u-histogram，利用式(3)将每个点的点特征直方图与u-histogram比较获取 相对KL距离。

$\mathrm{KL}={\Sigma }_{i=1}^{b^3}(p_i^f-u_i)·\ln \frac{p_i^f}{u_i}---\left(3\right)$

其中，i表示点特征直方图区域的序号，取值为1～b³，表示采样点 的点特征直方图的第i个分量，u_i表示平均特征直方图的第i个分量。计算 KL距离的平均值a和标准差σ，统计KL距离在a±σ外的三维点，视为几 何特征点。

S102在两次拍摄图片中查找图像特征点。

可以利用SIFT算法查找图像特征点，在对稳定性要求不高的情况下， 也可以采用SURF算法查找图像特征点。

S103建立配准算法选择模型。不同的被测表面在测量拼接时应采用不 同的特征点进行拼接。对于几何特征简单的物体，若利用步骤S101中的几 何特征点进行拼接，稳定性差；对于纹理简单的物体，若利用步骤S102中 的图像特征点进行拼接，稳定性差。为了提高不同测量场合的点云拼接稳 定性，遂提出如下的选择模型：

利用前述步骤查找出的几何特征点和图像特征点建立配准算法选择模 型，该模型在综合分析物体表面的几何和纹理信息的基础上生成配准算法 判断因子，并以此为依据自动选择合适的配准算法。具体评判标准如式(4)：

$D_r=\left(\begin{array}{cc}{w}_1(\frac{p_1-p}{p}-\frac{n_1-n}{n})+w_2(\frac{p_2-p}{p}-\frac{n_2-n}{n});& p_1>p,n_1>n\\ 1;& p_1>p,n_1<n\\ -1;& p_1<p,n_1>n\\ 0;& p_1\le p,n_1\le n\end{array}\right)---\left(4\right)$

其中，D_r定义为配准算法判断因子，其综合评价了物体表面几何特征 和纹理特征的相对复杂程度，系统可根据该算法因子选择合适的特征点类 型进行匹配以实现最终的拼接。p₁，p₂分别代表两幅采样点云中几何特征 点数目占其采样点点数的比例；n₁，n₂分别代表两次拍摄图片中图像特征 点的数目；p为几何特征阈值，表示利用几何特征点进行稳定拼接所需的几 何特征点比例，建议取值范围为5％～10％；n为图像特征阈值，表示利用图 像特征点进行稳定拼接所需的图像特征点数,建议取值范围为250～300。w₁和w₂是描述两个对比差值的权重因子，其和为1，通常将两者取为0.5。

当判断因子D_r大于0时，说明物体表面的几何特征相对丰富，应选择 基于几何特征点的配准算法，再进入步骤S104，得到旋转平移矩阵RT；小 于0时说明物体表面的纹理信息相对丰富，应选择基于图像特征点的配准 算法，再进入步骤S105得到旋转平移矩阵RT；若D_r等于0，证明物体表面 的几何特征和纹理信息均很少，采用基于几何特征和图像特征的配准算法 稳定性较差，提示用户通过引入标志点进行点云拼接。

本发明中的配准算法选择模型在测量几何特征明显的表面时，能自适 应地选择基于几何特征点的配准算法，避免了基于图像特征点的拼接错误； 在对几何特征少、纹理特征相对丰富的表面进行拼接时，自适应地采用基 于图像特征点的配准算法，排除了不稳定的几何特征配准算法，最终提高 了拼接的稳定性。

S104对于步骤S101查找出的几何特征点，利用RANSAC算法进行 几何特征点的匹配，得到每一个查找点对应的初匹配点集Q′，再利用SVD 奇异值分解法计算旋转矩阵R和平移矩阵T。

RANSAC算法原理为对初匹配点进行多次随机取样，每次随机抽取所 需的匹配点来确定模型参数，再根据已确定的模型计算匹配误差，将拥有 最小匹配误差的模型作为最终模型。具体步骤为：

第4.1步设定采样次数S_num，建议取值50～100。对源点云的几何特征 点进行采样，确保这些点的相互距离大于定义的最小距离阈值d_min，将采 样后的几何特征点视为查找点p_τ(τ＝1,2…r)，其中r为经采样后的几何特 征点个数。d_min建议取值范围为10～15mm。

第4.2步对于每个查找点p_τ，利用式(5)在目标点云的几何特征点 Q＝{q₁,q₂…q_n}中搜索与该查找点p_τ点特征直方图相似的点生成初匹配点 集Q′＝{q′₁,q′₂…q′_k}，其中n为目标点云中几何特征点的个数，k为每个查 找点初匹配点的个数。因源点云几何特征点经采样后有r个查找点，则生成 r个初匹配点集。

$\mathrm{Div}={\Sigma }_{i=1}^{b^3}(p_{\mathrm{\tau i}}^f-q_{\mathrm{xi}}^f)---\left(5\right)$

其中i表示区域的序号，表示查找点p_τ的点特征直方图的第i个分量， 表示目标点云几何特征点集Q中第x点(x＝1,2…n)的点特征直方图的 第i个分量，Div表示两点的点特征直方图差异。设定阈值，建议取值范围 为25～40，将Div与所取阈值进行比较，将小于阈值的点视为初匹配点存入 初匹配点集Q′中。

第4.3步对于所有查找点p_τ，从每个查找点的相应点集Q′中随机选取 一点作为该查找点的对应点q_τ，利用SVD分解法计算旋转矩阵R和平移矩 阵T，再根据式(6)计算旋转平移后的距离误差d_err,记录当前的旋转矩阵 R、平移矩阵T和误差d_err。

$d_{\mathrm{err}}=\left({\Sigma }_{\tau =1}^r{\left|\right|p_{\tau }-(R·q_{\tau }+T)\left|\right|}_2\right)/r---\left(6\right)$

第4.4步重复第4.3步，经过S_num循环后将误差d_err最小的旋转矩阵R 和平移矩阵T作为最后的旋转矩阵R和平移矩阵T，再转入S106实现两幅 点云的拼接。

利用上述RANSAC算法可提高旋转矩阵R和平移矩阵T的求解效率和 准确性，达到最终提高拼接稳定性的目的。

S105对于步骤S102查找出的图像特征点，结合RANSAC算法实现对 应点的查找，确定三维对应点后，采用SVD奇异值分解法求解多视点云之 间的旋转矩阵R和平移矩阵T，然后进入步骤S106。

对应点的查找的具体步骤如下：

第5.1步对于步骤S102查找出的图像特征点，利用SIFT匹配算法实 现图像特征点的初匹配。初匹配过程中由于计算误差和测量环境的影响， 初匹配中存在误匹配，将影响拼接的稳定性，可利用基于基本矩阵的 RANSAC算法来排除误匹配，提高基于图像特征点的拼接稳定性。

第5.2步设定采样次数S_num，建议取值50～100。

第5.3步在初匹配数据集中随机抽取8对匹配点，采用归一化8点算 法进行基本矩阵初始估计，得到基本矩阵F。

在对稳定性要求不高的情况下，也可以采用5点算法替换8点算法。

第5.4步利用式(7)计算每一对初匹配点的误差大小E_rr，m₁、m₂是 该两点的齐次坐标，上标T为转置，设定E_rr取值范围(通常取±0.3)，将 取值范围内的点视为最佳匹配点，记录当前最佳匹配点和最佳匹配点数目。

E_rr＝m₁^TFm₂    (7)

第5.5步重复第5.3步和第5.4步，始终保存最佳匹配点数目最多的情 况，直到重复次数等于随机采样次数S_num。

第5.6步将最终保留下的最佳匹配点作为正确的对应点。因采用文献 【1】中的方法获取点云数据，该点云数据中的任一三维点都有唯一图像点 与之对应，所以通过图像特征点和三维点的一一映射关系可实现三维点的 匹配。

利用第5.2步～第5.5步的RANSAC算法有效排除了初匹配中的误匹配 点，从而提高了旋转矩阵R和平移矩阵T的求解准确性，达到最终提高拼 接稳定性的目的。

S104和S105中，所述SVD奇异值分解法求解旋转矩阵R和平移矩阵 T的过程为：

第6.1步设得到的匹配后三维点为集合G＝{g₁,g₂…g_N}和G′＝ {g′₁,g′₂…g′_N}，利用式(8)计算两片点集的质心。其中为匹配点对数，g_l和 g′_l为任一对匹配三维点的三维坐标，g和g′为3×1的矩阵。

$g=\frac{1}{N}{\Sigma }_{l=1}^N{g}_l,g^{\prime }=\frac{1}{N}{\Sigma }_{l=1}^N{g}_l^{\prime }(l=\mathrm{1,2}...N)---\left(8\right)$

第6.2步利用式(9)将两片点集G和G′相对于各自质心做平移，得到 新点集J＝{j₁,j₂…j_N}和J′＝{j′₁,j′₂…j′_N}

j_l＝g_l-g,j′_l＝g′_l-g′ (l＝1,2…N)   (9)

第6.3步利用式(10)计算3×3的矩阵H。

$H={\Sigma }_{l=1}^N{j}_l{j}_l^{\prime T}---\left(10\right)$

第6.4步对H矩阵进行奇异值分解得：H＝UΛV^T，其中上标T为矩阵 转置，U、V为3×3酉矩阵，Λ为3×3对角矩阵。利用式(11)定义3×3 的对角矩阵A。

$A=\left(\begin{array}{cc}{I}^3& \det \left(U\right)\det \left(V\right)\ge 0\\ \mathrm{diag}\left(\begin{array}{cc}\mathrm{1,1},& -1\end{array}\right)& \det \left(U\right)\det \left(V\right)<0\end{array}\right)---\left(11\right)$

第6.5步利用式(12)计算3×3的旋转矩阵R和3×1的平移矩阵T，其 中上标T为矩阵转置。

R＝UAV^T,T＝g′-Rg     (12)

S106确定旋转平移矩阵RT后，源点云保持不动，利用式(13)对目 标点云进行旋转平移完成拼接。

q′_c＝R·q_c+T    (13)

其中，q_c为目标点云中任意一点的三维坐标，q′_c为经变换后的点的三维 坐标。

以上所述为本发明的较佳实施例而已，但本发明不应该局限于该实施 例和附图所公开的内容。所以凡是不脱离本发明所公开的精神下完成的等 效或修改，都落入本发明保护的范围。