一种适用于多视角密集点云数据配准的种子点拾取方法

摘要

本发明公开了一种适用于多视角密集点云数据配准的种子点拾取方法，属于光学三维非接触式测量技术领域，该方法的实现步骤包括1)输入一幅多视角密集点云数据；2)多视角密集点云数据转化为灰度图；3)灰度图高斯金字塔分解；4)灰度图拉普拉斯金字塔分解；5)二维种子点拾取；6)二维种子点回溯；7)三维种子点映射；8)输出种子点。通过所述操作步骤，本发明可一次拾取多种尺度空间上的种子点，从而满足不同的配准需求。此外，本发明拾取的种子点包括特征种子点及非特征种子点，种子点分布更加合理。

说明书

技术领域

本发明属于光学三维非接触式测量领域，涉及一种适用于多视角密集点云数据配准的种子点拾取方法，更进一步涉及一种基于塔形分解的多尺度多分辨率种子点拾取方法。

背景技术

三维光学非接触式测量技术已经成为“实体数字化”的一种重要技术。由于物体的自遮挡、扫描范围限制等原因，三维光学非接触式测量系统单次扫描只能得到物体一个视角的点云数据，对于大尺寸、复杂型面物体，要得到其完整的点云模型，需要从不同视角进行扫描，得到多视角密集点云数据，再进行配准，从而获得坐标归一的、完整的点云模型。

多视角密集点云数据配准过程中，最为关键的一步便是种子点的拾取，所拾取的种子点质量直接影响多视角密集点云数据配准的速度及精度。文献“A method forregistration of 3D shapes”(P.J.Besl,N.D.Mckay,IEEE transactions on patternanalysis and machine intelligence,1992,14(2):239-256)将多视角密集点云数据中的全部点数据作为种子点，缺点是配准算法迭代收敛速度慢，易陷入局部最优。

文献“Efficient variants of the ICP algorithm”(S.Rusinkiewicz,M.Levoy,in:Proceedings of International Conference on 3D Digital Imaging andModeling,2001,145-152)提出一种在法向量空间中选择种子点的方法，缺点是不同法向量空间区段中的种子点均通过随机采样法拾取，可重复性差。

文献“Using retinex for point selection in 3D shape registration”(Y.Liu,R.R.Martin,L.D.Dominicis,and B.Li,Pattern Recognition,2014,47(6):2126-2142)提出一种基于Retinex理论的种子点拾取方法，缺点是只能拾取到多视角密集点云数据总数目10％左右的种子点，使用者无法改变或控制种子点数目。

发明内容

为了克服现有方法的不足，本发明提出了一种基于塔形分解的种子点拾取方法。该方法将多视角密集点云数据转化为二维灰度图，并对二维灰度图进行金字塔分解，从而实现在多种尺度上拾取种子点以满足不同的配准需求。

为达到以上目的，本发明采取的技术方案是：

步骤一，输入一幅多视角密集点云数据

输入一幅待配准的多视角密集点云数据，同时包含三维坐标信息及栅格信息；

步骤二，多视角密集点云数据转化为灰度图

对步骤一所输入的一幅多视角密集点云数据进行霍特林变换，并依据多视角密集点云数据所包含的栅格信息，将变换后的多视角密集点云数据转化为一幅二维灰度图；

步骤三，灰度图高斯金字塔分解

对步骤二所转化的二维灰度图进行高斯金字塔分解；

步骤四，灰度图拉普拉斯金字塔分解

在步骤三所分解的二维灰度图的高斯金字塔的基础上，进一步构建二维灰度图的拉普拉斯金字塔；

步骤五，二维种子点拾取

根据多视角密集点云数据配准需求，在步骤四所分解的二维灰度图的拉普拉斯金字塔不同分解层上的图像中选择灰度值大于一定阈值的像素点作为二维特征种子点；在步骤三所分解的二维灰度图的高斯金字塔不同分解层上的图像中选择灰度值大于0的像素点作为二维非特征种子点；

步骤六，二维种子点回溯

对步骤五所拾取的二维特征种子点及二维非特征种子进行回溯；

步骤七，三维种子点映射

将步骤六所回溯的二维种子点映射至步骤一所输入的一幅多视角密集点云数据中，得到三维种子点；

步骤八，输出种子点

将步骤七所映射的三维种子点输出，获得多视角密集点云数据配准所需的种子点。

进一步地，所述步骤二中多视角密集点云数据转化为灰度图的流程包括如下步骤：

2.1)为步骤一所输入的一幅多视角密集点云数据建立一棵k-d树；

2.2)在步骤2.1)所建立的k-d树的基础上，查询步骤一所输入的一幅多视角密集点云数据中每个点数据q_i＝(p_i,c_i)的k近邻，并记为{q_j}，其中，i表示步骤一所输入的一幅多视角密集点云数据中点数据的索引，1≤i≤N，N表示步骤一所输入的一幅多视角密集点云数据的数目，p_i表示点数据q_i的三维坐标向量，c_i表示点数据q_i的栅格坐标向量，j表示点数据q_i的k近邻索引，1≤j≤k，q_j表示点数据q_i的第j个近邻，符号{}表示k近邻的集合；

2.3)根据步骤2.2)所查询的每个点数据q_i的k近邻{q_j}，为每个点数据q_i构造一局部协方差矩阵：

其中，M_i表示所构造的局部协方差矩阵，p_j表示点数据q_i的第j个近邻q_j的三维坐标向量，表示点数据q_i的k近邻的重心，T表示转置；

2.4)通过雅克比法求出步骤2.3)为每个点数据q_i所构造的局部协方差矩阵M_i的按降序排列的特征值λ₁、λ₂、λ₃及对应的特征向量s₁、s₂、s₃；

2.5)对每个点数据q_i的三维坐标向量p_i进行霍特林变换：

其中，p′_i表示变换后点数据q_i的三维坐标向量，χ＝[s₁>2>3]^T表示由步骤2.4)所求解的三个相互正交的特征向量s₁、s₂、s₃构成的矩阵，×表示两矩阵相乘；

2.6)对步骤2.5)所变换的每个点数据q_i的三维坐标向量p′_i在Z轴上的分量Z′_i作进一步的变换：

其中，表示进一步变换后点数据q_i的三维坐标向量p′_i在Z轴上的分量，Z′_max与Z′_min分别表示步骤2.5)所变换的所有点数据的三维坐标向量在Z轴上的分量的最大值和最小值；2.7)将步骤2.6)所变换的每个点数据q_i的三维坐标向量p′_i在Z轴上的分量作为图像的灰度值，并将每个点数据q_i的栅格坐标c_i＝(u_i,v_i)作为该点在图像中的x、y坐标，建立一幅二维灰度图，u_i与v_i分别表示栅格行号和列号。

进一步地，所述步骤2.2)中查询每个点数据q_i＝(p_i,c_i)的k近邻时，k值的取值为：k＝9。

进一步地，所述步骤三与步骤四中高斯金字塔和拉普拉斯金字塔分解层数L的取值范围为L＝3～6。

进一步地，所述步骤五中二维种子点拾取方法如下：

5.1)根据配准需求，在步骤四所分解的拉普拉斯金字塔第t层上的图像中选择二维特征种子点：若步骤四所分解的拉普拉斯金字塔第t层上的图像LP_t中坐标为(x，y)的像素点的灰度值LP_t(x,y)大于给定阈值τ，即LP_t(x,y)>τ，则选择坐标为(x，y)的像素点为一二维特征种子点；

5.2)根据配准需求，在步骤三所分解的高斯金字塔第r层上的图像中选择二维非特征种子点：若步骤三所分解的高斯金字塔第r层上的图像G_r中坐标为(x，y)的像素点的灰度值G_r(x,y)大于零，即G_r(x,y)＞0，则选择坐标为(x，y)的像素点为一二维非特征种子点；

进一步地，所述步骤5.1)中阈值τ的取值范围为：0≤τ≤30。

进一步地，所述步骤六中二维种子点回溯方法如下：

6.1)对步骤五所拾取的拉普拉斯金字塔第t层上的二维特征种子点逐层回溯至第0层：

a)令(x^t,y^t)＝(x,y)，其中，(x^t,y^t)表示步骤五所拾取的拉普拉斯金字塔第t层上的图像中坐标为(x,y)的二维特征种子点的坐标；

b)将步骤a)中的拉普拉斯金字塔第t层上的坐标为(x^t,y^t)的二维特征种子点回溯至拉普拉斯金字塔第t-1层上：

(x^t-1,y^t-1)＝{(m,n)|(m,n)∈max(LP_t-1(m,n)),2x^t-2≤m≤2x^t+2,2y^t-2≤n≤2y^t+2}，

其中，(x^t-1,y^t-1)表示拉普拉斯金字塔第t层上的坐标为(x^t,y^t)的二维特征种子点回溯至拉普拉斯金字塔第t-1层上时的坐标，(m，n)表示像素点位置，LP_t-1(m,n)表示拉普拉斯金字塔第t-1层上的图像中坐标为(m，n)的像素点的灰度值，max()表示取最大值函数；

c)如果t＞1，令(x,y)＝(x^t-1,y^t-1)，t＝t-1，重复步骤a)至步骤c)；否则，当t＝＝1时，(x⁰,y⁰)＝(x^t-1,y^t-1)即为拉普拉斯金字塔第t层上的坐标为(x^t,y^t)的二维特征种子点回溯至拉普拉斯金字塔第0层上时的坐标，＝＝表示等于判断符号；

6.2)对步骤五所拾取的高斯金字塔第r层上的坐标为(x,y)的二维非特征种子点，采用下式一步回溯至第0层上：

(x⁰,y⁰)＝(2^r×x,2^r×y)，

其中，(x⁰,y⁰)表示步骤五所拾取的高斯金字塔第r层上的坐标为(x,y)的二维非特征种子点回溯至第0层上时的坐标，2^r表示2的r次方，×表示两整数相乘。

进一步地，所述步骤七中三维种子点映射方法如下：将步骤六所回溯至拉普拉斯金字塔及高斯金字塔第0层上的二维种子点的坐标(x⁰,y⁰)作为栅格坐标，对步骤一所输入的一幅多视角密集点云数据中的任一点数据q_i，如果其栅格坐标满足：c_i＝(u_i,v_i)＝＝(x⁰,y⁰)，那么点数据q_i就是一个三维种子点，u_i与v_i分别表示栅格行号和列号，＝＝表示等于判断符号。

与现有技术相比，本发明具有以下优点：

(1)本发明方法一次拾取多种尺度空间上的种子点，从而可满足不同的配准需求；

(2)本发明方法拾取的种子点包括特征种子点及非特征种子点，种子点分布更加合理；

(3)本发明方法拾取的种子点数目可控制，使用者通过调节阈值参数可以改变所拾取的种子点的数目；

(4)本发明方法拾取的种子点具有可重复性和可验证性。

附图说明

图1本发明具体操作步骤的流程图；

图2输入的一幅翼虎多视角密集点云数据；

图3将输入的一幅翼虎多视角密集点云数据转化为灰度图；

图4(a)-(e)分别为灰度图高斯金字塔(从左至右依次为第0层至第4层上的图像)；

图5(a)-(e)分别为灰度图拉普拉斯金字塔(从左至右依次为第0层至第4层上的图像)；

图6a拾取的三维种子点由拉普拉斯金字塔第2层上的二维特征种子点及高斯金字塔第3层上的二维非特征种子点映射所得；

图6b拾取的三维种子点由拉普拉斯金字塔第3层上的二维特征种子点及高斯金字塔第3层上的二维非特征种子点映射所得；

图6c拾取的三维种子点由拉普拉斯金字塔第3层上的二维特征种子点及高斯金字塔第4层上的二维非特征种子点映射所得。

具体实施方式

下面结合附图和实施例对发明作进一步的详细说明，但并不作为对发明做任何限制的依据。

本发明提出一种适用于多视角密集点云数据配准的种子点拾取方法，如图1所示。拾取一幅多视角密集点云数据中的种子点时，第一步，输入一幅多视角密集点云数据。要求输入的多视角密集点云数据同时包含三维坐标信息及栅格信息。也就是说输入的多视角密集点云数据中的每个点数据q_i＝(p_i,c_i)，其中，i表示输入的多视角密集点云数据中点数据的索引，1≤i≤N，N表示输入的多视角密集点云数据的数目，p_i＝(X_i,Y_i,Z_i)表示三维坐标向量，X_i、Y_i、Z_i分别表示三维坐标向量在X轴、Y轴及Z轴上的分量，c_i＝(u_i,v_i)表示栅格坐标向量，u_i与v_i分别表示栅格行号和列号。

第二步，多视角密集点云数据转化为灰度图。将第一步所输入的一幅多视角密集点云数据转化为一幅二维灰度图，转化流程包括如下步骤：

1)采用文献“Multidimensional binary search trees used for associative”(J.L.Bentley,Commun ACM 1975,18:509-517)所描述的多维二叉搜索树算法为第一步所输入的一幅多视角密集点云数据建立一棵k-d树。

2)在第1)步所建立的k-d树的基础上，查询第一步所输入的一幅多视角密集点云数据中每个点数据q_i的k近邻，并记为{q_j}，其中，i表示输入的多视角密集点云数据中点数据的索引，j表示点数据q_i的k近邻索引，1≤j≤k，q_j表示点数据q_i的第j个近邻，符号{}表示k近邻的集合，k值一般取k＝9。

3)依据第2)步所查询的每个点数据q_i的k近邻{q_j}，为每个点数据q_i构造一局部协方差矩阵：

其中，M_i表示所构造的局部协方差矩阵，p_j表示点数据q_i的第j个近邻q_j的三维坐标向量，表示点数据q_i的k近邻的重心，T表示转置；

4)通过雅克比法求出第3)步为每个点数据q_i所构造的局部协方差矩阵M_i的按降序排列的特征值λ₁、λ₂、λ₃及对应的特征向量s₁、s₂、s₃；

5)对每个点数据q_i的三维坐标向量p_i进行霍特林变换：

其中，p′_i表示变换后点数据q_i的三维坐标向量，χ＝[s₁>2>3]^T表示由第4)步所求解的三个相互正交的特征向量s₁、s₂、s₃构成的矩阵，×表示两矩阵相乘；

6)对第5)步所变换的每个点数据q_i的三维坐标向量p′_i在Z轴上的分量Z′_i作进一步的变换：

其中，表示进一步变换后点数据q_i的三维坐标向量p′_i在Z轴上的分量，Z′_max与Z′_min分别表示第5)步所变换的所有点数据的三维坐标向量在Z轴上的分量的最大值和最小值；

7)将第6)步所变换的每个点数据q_i的三维坐标向量p′_i在Z轴上的分量作为图像的灰度值，并将每个点数据q_i的栅格坐标c_i＝(u_i,v_i)作为该点在图像中的x、y坐标，建立一幅二维灰度图，u_i与v_i分别表示栅格行号和列号；

第三步，灰度图高斯金字塔分解。灰度图高斯金字塔分解流程包括如下步骤：

1)构造高斯金字塔第0层。将第二步所转化的二维灰度图作为高斯金字塔第0层上的图像：

G₀(x,y)＝I(x,y)，

其中，(x,y)表示像素点坐标，G₀(x,y)表示高斯金字塔第0层上的图像中坐标为(x,y)的像素点的灰度值，I(x,y)表示第二步所转化的二维灰度图中坐标为(x,y)的像素点的灰度值；

2)构造高斯金字塔第r层。将高斯金字塔第r-1层上的图像与一个5×5窗口函数进行卷积运算，再把卷积结果作隔行隔列的降采样便得到高斯金字塔第r层上的图像：

其中，r表示金字塔的第r层，G_r(x,y)表示高斯金字塔第r层上的图像中坐标为(x,y)的像素点的灰度值，m和n表示两个整数变量，G_r-1(2x+m,2y+n)表示高斯金字塔第r-1层上的图像中坐标为(2x+m,2y+n)的像素点的灰度值，λ(m,n)表示5×5窗口函数：

在第1)步所构造的高斯金字塔第0层的基础上，根据所述高斯金字塔第r层构造方法，可构造出高斯金字塔的第1层，以此类推，可构造出高斯金字塔的第L层，L表示金字塔分解层数，由使用者指定，通常取L＝3～6。

第四步，灰度图拉普拉斯金字塔分解。在第三步所分解的二维灰度图高斯金字塔的基础上，进一步构造二维灰度图的拉普拉斯金字塔。灰度图拉普拉斯金字塔构造流程包括如下步骤：

1)构造拉普拉斯金字塔第L层。将第三步所分解的高斯金字塔第L层上的图像作为拉普拉斯金字塔第L层上的图像：

LP_L(x,y)＝G_L(x,y)，

其中，(x,y)表示像素点坐标，L表示第三步中由使用者指定的金字塔分解层数，LP_L(x,y)表示拉普拉斯金字塔第L层上的图像中坐标为(x,y)的像素点的灰度值，G_L(x,y)表示第三步所分解的高斯金字塔第L层上的图像中坐标为(x,y)的像素点的灰度值；

2)构造拉普拉斯金字塔第t层。拉普拉斯金字塔第t层构造方法如下：

a)将第三步所分解的高斯金字塔第t+1层上的图像内插放大：

其中，t+1表示金字塔的第t+1层，表示内插放大后的图像中坐标为(x,y)的像素点的灰度值，m和n表示两个整数变量，表示第三步所分解的高斯金字塔第t+1层上的图像中坐标为的像素点的灰度值，表示一过渡变量，λ(m,n)表示第三步所述的5×5窗口函数；

b)将第三步所分解的高斯金字塔第t层上的图像与第a)步内插放大后的图像做减法运算：

其中，LP_t(x,y)表示所构造的拉普拉斯金字塔第t层上的图像中坐标为(x,y)的像素点的灰度值，G_t(x,y)表示第三步所分解的高斯金字塔第t层上的图像中坐标为(x,y)的像素点的灰度值；

根据所述拉普拉斯金字塔第t层构造方法，可依次构造出拉普拉斯金字塔的第L-1层至第0层。

第五步，二维种子点拾取。二维种子点的拾取包括二维特征种子点及二维非特征种子点的拾取。拾取方法如下：

1)根据配准需求，在第四步所分解的拉普拉斯金字塔第t层上的图像中选择二维特征种子点：若第四步所分解的拉普拉斯金字塔第t层上的图像LP_t中坐标为(x，y)的像素点的灰度值LP_t(x,y)大于给定阈值τ，即LP_t(x,y)>τ，则选择坐标为(x，y)的像素点为一二维特征种子点；

2)根据配准需求，在第三步所分解的高斯金字塔第r层上的图像中选择二维非特征种子点：若第三步所分解的高斯金字塔第r层上的图像G_r中坐标为(x，y)的像素点的灰度值G_r(x,y)大于零，即G_r(x,y)＞0，则选择坐标为(x，y)的像素点为一二维非特征种子点。

第六步，二维种子点回溯。对第五步所拾取的二维特征种子点及二维非特征种子点进行回溯。回溯方法如下：

1)对第五步所拾取的拉普拉斯金字塔第t层上的二维特征种子点逐层回溯至第0层：

a)令(x^t,y^t)＝(x,y)，其中，(x^t,y^t)表示第五步所拾取的拉普拉斯金字塔第t层上的图像中坐标为(x,y)的二维特征种子点的坐标；

b)将第a)步中的拉普拉斯金字塔第t层上的坐标为(x^t,y^t)的二维特征种子点回溯至拉普拉斯金字塔第t-1层上：

(x^t-1,y^t-1)＝{(m,n)|(m,n)∈max(LP_t-1(m,n)),2x^t-2≤m≤2x^t+2,2y^t-2≤n≤2y^t+2}，

其中，(x^t-1,y^t-1)表示拉普拉斯金字塔第t层上的坐标为(x^t,y^t)的二维特征种子点回溯至拉普拉斯金字塔第t-1层上时的坐标，(m，n)表示像素点坐标，LP_t-1(m,n)表示拉普拉斯金字塔第t-1层上的图像中坐标为(m，n)的像素点的灰度值，max()表示取最大值函数；

c)如果t＞1，令(x,y)＝(x^t-1,y^t-1)，t＝t-1，重复第a)步至第c)步；否则，当t＝＝1时，(x⁰,y⁰)＝(x^t-1,y^t-1)即为拉普拉斯金字塔第t层上的坐标为(x^t,y^t)的二维特征种子点回溯至拉普拉斯金字塔第0层上时的坐标，＝＝表示等于判断符号；

2)对第五步所拾取的高斯金字塔第r层上的坐标为(x,y)的二维非特征种子点，采用下式一步回溯至第0层上：

(x⁰,y⁰)＝(2^r×x,2^r×y)，

其中，(x⁰,y⁰)表示第五步所拾取的高斯金字塔第r层上的坐标为(x,y)的二维非特征种子点回溯至第0层上时的坐标，2^r表示2的r次方，×表示两整数相乘。

第七步，三维种子点映射。将第六步所回溯至拉普拉斯金字塔及高斯金字塔第0层上的二维种子点的坐标(x⁰,y⁰)作为栅格坐标，对第一步所输入的一幅多视角密集点云数据中的任一点数据q_i，如果其栅格坐标满足：c_i＝(u_i,v_i)＝＝(x⁰,y⁰)，那么点数据q_i就是一个三维种子点，u_i与v_i分别表示栅格行号和列号，＝＝表示等于判断符号。

第八步，输出种子点。将第七步所映射的三维种子点输出，获得用于多视角密集点云数据配准的种子点。

以下结合具体模拟实验对本发明进行说明，其中本发明方法在Matlab平台上实现相应的算法并在Intel i7-4770CPU 3.4GHz、16GB内存的PC机上运行。

一幅待配准的翼虎多视角密集点云数据如图2所示,转化为二维灰度图如图3所示。二维灰度图高斯金字塔及拉普拉斯金字塔分解结果如图4(a)-(e)及图5(a)-(e)所示。图6a至图6c为最终拾取的不同尺度上的多分辨率三维种子点。其中，图6a所示的三维种子点由拉普拉斯金字塔第2层上的二维特征种子点及高斯金字塔第3层上的二维非特征种子点映射所得，图6b所示的三维种子点由拉普拉斯金字塔第3层上的二维特征种子点及高斯金字塔第3层上的二维非特征种子点映射所得，图6c所示的三维种子点由拉普拉斯金字塔第3层上的二维特征种子点及高斯金字塔第4层上的二维非特征种子点映射所得。通过本例也可以说明，本发明方法可一次拾取多种尺度空间上的种子点，从而满足不同的配准需求。

上面结合附图对本发明的实施方式作了说明，但本发明并不限于上述实施方式，在本领域的普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前提下做出各种变化。