本发明属于图像和可视化领域，具体涉及一种基于层次b样条的多尺度点云特征点检测与匹配。
背景技术：
三维几何模型已成为继声音、图像和视频之后一种重要的数字媒体。点云模型是以离散采样点为基元的几何模型，是三维几何模型的一种自然表示方式。特征点检测与匹配是点云数据处理过程中重要的一环，在多视角数据对齐、三维模型检索、曲面重建与简化等领域都有广泛应用。但是，受到传感器噪声、数据缺失以及采样密度变化等因素的影响，在特征度量指标的选取，特征点检测与描述的重复性以及特征匹配的准确性等方面，仍面临巨大挑战。
特征点提取与匹配可分为特征度量、特征点检测、特征描述符构建与匹配三个步骤。针对上述三个步骤，当前已有大量的法向量估算方法被提出。
特征度量反应的是曲面变化程度。相关算法可分为两类：一种是根据曲率求得，但是准确性容易收到噪声和离群点的影响；另一种是近似算法，即不按标准定义计算曲率，而采用如邻域点的法向量变化近似替代曲率，但是该方法不能表达曲面的凹凸性。
特征点检测是选取度量指标下取得局部极值的点集合。相关算法可分为两类：一种是单尺度特征点检测，但是准确性容易受到噪声和离群点的影响；另一种是多尺度特征点检测，但该方法需要对每一个点进行多次特征计算，计算效率低。
特征描述符构建是在特征点检测完成后，赋予其编码信息，构建出区分性良好的特征描述符。相关算法有spin图像及其改进算法，但由于将三维数据投影到一个平面上，容易丢失曲面信息，造成描述符区分性不佳；tombari等人为每个特征描述符关联一个基于最大主曲率方向构建的局部坐标系，但是主曲率方向的计算准确性容易受到噪声影响；mian给出了一种在等距变形下保持稳定的特征描述符，但是该算法的描述符维度很高，影响了匹配效率。
综上所述，在点云的特征点检测与匹配领域仍有一些问题需要研究员来攻克。
技术实现要素：
本发明提出了基于层次b样条的多尺度点云特征点检测与匹配算法，以实现在受到噪声、数据缺失以及采样密度变化等因素的影响下，依然能够提取出高重复性的特征点以及构建出具有良好区分性的描述符，实现点云的鲁棒配准。
为达到此目的，本发明提供如下的技术方案：
基于层次b样条的多尺度点云特征点检测与匹配，包括以下步骤：
1)构建一种曲面变化度量指标δp；
2)根据步骤1)所构建的曲面变化度量指标将点云分为潜在特征点和非潜在特征点两类，并根据非潜在特征点估算点云噪声水平；
3)采用层次b样条多尺度算法对步骤2)中所划分的潜在特征点进行拟合；
4)在步骤3)拟合过程中，记录曲面变化信息以及曲率尺度空间，构建稳定局部坐标系的显著特征点；
5)根据层次b样条控制点分布信息以及控制点间曲率大小构建二进制特征描述符；
6)根据步骤5)所构建的特征描述符的相似性，依靠特征点的拓扑关系在模型点云中搜索对应特征点，最终实现特征点匹配。
进一步的，所述步骤1)中构建一种曲面变化程度的度量指标δp的方法为：
任意一点p的k邻域点重心
其中，i表示第i个邻近点；ε表示点云中包含的噪声，当点云中的噪声为零均值时，任意一点p的邻近点重心
式(1)同时还是对点云进行均值平滑的公式，因此利用平滑收缩幅值来构建一种曲面变化程度的度量指标δp，计算公式如式(2)所示：
其中，
其中，wdi是距离加权的权重。
进一步的，真实扫描点云具有非均匀采样的特性，为了克服采样密度带来变化的影响，采用式(4)所示的方法对每一邻域点进行加权，即：
其中，权值wsi取为pi到其最近的5个邻近点的平均距离；np为p的法向量。
对上述曲面变化程度的度量指标δp添加符号，使δp具有表现曲面凹凸的能力，符号的确定准则如下：
如果向量
其中δp的取值具有正负变化并且能够表达曲面弯曲程度，即平滑收缩指数ssi。
进一步的，所述步骤2)中，潜在特征点与非潜在特征点的划分是根据平滑收缩指ssi计算之后，利用||ssi||的平均值倍数确定的；由于平坦区域估算的噪声水平比从尖锐特征处估算出的噪声水平具有更高的可信度，在平坦区域主要分布非潜在特征点，因此利用非潜在特征点估算噪声水平。
进一步的，所述步骤3)中，采用层次b样条算法对步骤2)中所划分的潜在特征点进行拟合包括两个步骤：
31)将局部数据参数化；
311)建立z轴垂直于微切平面，x、y方向任意的局部直角坐标系；
312)将邻域数据通过旋转变化矩阵变换到该局部坐标系下；
313)以该局部坐标系的x、y方向作为样条曲面的u、v方向；
32)利用层次b样条拟合曲面；
321)在u、v方向上定义一系列密度逐层加倍的网格状控制点φ0,φ1,…,φn；
322)在拟合的开始用最稀疏的控制点φ0拟合从真实曲面f获得的采样数据，得到拟合结果f0，并计算拟合误差e＝f-f0；
323)用密度加倍的控制点φ1对误差e进行二次拟合，得到曲面f1；
324)重复步骤323)，直到拟合均方差小于步骤2)中所求取的噪声水平；
325)最终曲面f表示为各次拟合曲面的加和，即
进一步的，所述步骤4)中，利用在步骤3)拟合过程中记录的曲面变化信息以及曲率尺度空间，构建稳定局部坐标系的显著特征点，包括以下步骤：
41)基于层次b样条拟合过程构建曲率尺度空间；
42)邻域和曲率空间多尺度特征点检测；
43)滤除曲率分布方向性不明确的特征点；
44)滤除边界点附近的特征点；
45)得到能够建立良好区分性特征描述符的特征点。
进一步的，在所述步骤42)之后，还包括一个验证环节，对任意一个备选特征点进行验证，滤除虚假特征点，以保证特征描述符所用局部坐标系的稳定性；
所述对任意一个备选特征点进行验证包括以下步骤：
①对由当前备选特征点及其邻域点构成的点集u进行坐标变换，使变换后的备选特征点法向量与z轴平行；
②将xoz平面绕z轴旋转15°，利用旋转后的平面将点集u划分为a、b两个子集，即a∪b＝u；
③计算子集a、b中各点高斯曲率的均值
④从子集a中筛选出与备选特征点高斯曲率差别小于一定阈值γ的点，称为曲率邻域点，并对曲率邻域点进行pca分析，然后，计算最大的两个pca特征值之间的比例ηai，以度量子集a曲率邻域点的线性程度；对子集b进行同样的计算得到ηbi；
⑤重复执行步骤②～④，直到xoz平面绕z轴旋转12次共旋转了180°；
⑥找到△max＝max(△1,△2,......,△12)和
这样可以保证曲率邻域点呈线性分布，并具有良好的指向性，有利于建立稳定可靠的局部坐标系。
进一步的，所述步骤5)中中直接对局部曲面信息进行二进制编码的方式构建特征描述符，即用1个bit数据表示特征描述符的一个维度，进而采用hamming距离进行描述符的相似性度量。特征描述符支撑邻域半径为平均曲率倒数的10倍。特征描述符构建方法包括以下步骤：
51)在拟合过程中进行误差阈值截断，形成控制点分布图；
52)以是否需要进一步细化为准则考察各个控制点，形成二进制编码，其中0表示无需进一步细化即能够达到拟合精度，1表示需要进一步细化达到拟合精度；
53)将编码值按照逐层细化结果的行优先顺序排列，得到一个二进制特征描述符。
进一步的，所述步骤6)中，如果特征点检测具有良好的重复性，那么，从两个视角数据检测出的特征点将具有相似的拓扑关系，即在局部坐标系下每个特征点与距离其最近的k个特征点之间的距离和方位保持不变。上述不变量为特征点的匹配提出额外的约束条件。
特征点匹配包括以下步骤：
61)基于传统特征点匹配方法进行初始匹配；
62)基于特征点拓扑关系进行验证，滤除初始匹配中存在的虚假匹配点；
63)对于步骤61)，62)中没有匹配的特征点，采用拓扑关系进行二次匹配。
进一步的，所述步骤6)中，依靠拓扑关系在模型点云中搜索对应特征点，包括以下步骤：
①设从数据点云中检测到的特征点个数为m 1，计算任意数据点云中的任意特征点
②设从模型点云中检测到的特征点个数为n 1，对于模型点云中每一个特征点，计算其到其他特征点的距离和方位，得到如下拓扑矩阵d2：
③将
其中δ1和δ2分别为距离和方位特征容忍度；
④找到向量n中最大元素的标号k，如果该元素取值大于3则，判定pi1与模型点云中的第k个特征点匹配关系成立。
有益效果
本发明能够在有噪声和非均匀采样条件下，提高特征点采样的准确性和重复性，并且二进制特征描述符相较于已有的特征描述符有更高的区分度和匹配成功率。
附图说明
图1.本发明的流程图。
图2.平滑收缩与曲面变化之间的关系。
图3.层次b样条拟合示意图；图(a)是层次b样条基本拟合流程，图(b)带有控制点细化的拟合流程。
图4.误差阈值下层次b样条控制点分布于曲面变化关系。
图5.控制点分布与二进制编码。
具体实施方式
下面结合附图和实施例详细说明本发明技术方案中所涉及的各个细节问题。
本发明提供一种基于层次b样条的多尺度点云特征点检测与匹配算法，包括以下步骤：
1)构建一种曲面变化度量指标δp。相较于计算曲率所用到的微分运算，积分的加和或平均操作使其对噪声表现出更好的鲁棒性。如式(1)所示，求取局部点云数据重心就是一种典型的积分性质的运算。
其中，i表示第i个邻近点；ε表示点云中包含的噪声；通过式(1)可以得到，如果点云中包含的噪声是零均值的，那么其中任意一点p的k邻域点重心
式(1)同时还是对点云进行均值平滑的公式。均值平滑不仅会增加点云数据的光滑程度，还会引起模型体积收缩。如图2所示，模型收缩程度是与该处点云的尖锐程度成正比的，即在模型平坦处，进行均值平滑后，点云收缩幅值减小，而在尖锐特征处，进行均值平滑后，模型收缩幅值较大。因此利用平滑收缩幅值来构建一种曲面变化程度的度量指标δp，如式(2)所示：
其中，
其中，wdi是距离加权的权重。根据式(1)和式(3)可知，对于包含零均值噪声的点云
但是真实扫描点云往往具有非均匀采样的特性，为了克服采样密度带来变化的影响，采用式(4)所示的方法对每一邻域点进行加权，权值wsi取为pi到其最近的5个邻近点的平均距离。为了进一步增强这种趋势，基于式(3)中的距离权值对邻域点进行加权pca分析，求取p的法向量np，然后强制收缩发生在法向量方向上，即：
式(4)能够对零均值噪声表现出足够的鲁棒性，同时消除非均匀采样带来的影响。
进一步，为了使δp具有表现曲面凹凸的能力，对其添加符号，符号的确定准则如下：如果向量
式(5)中δp的取值具有正负变化并且能够表达曲面弯曲程度，我们称其为平滑收缩指数ssi(smoothshrinkindex)。
2)根据曲面变化度量指标将点云分为潜在特征点和非潜在特征点两类，并根据非潜在特征点估算点云噪声水平。在步骤1)中计算完成后，根据其绝对值大小(具体阈值可利用||ssi||的平均值的倍数确定)可将整体点云分为潜在特征点和非潜在特征点两类。又平坦区域估算的噪声水平比从尖锐特征处估算出的噪声水平具有更高的可信度，在平坦区域主要分布非潜在特征点，因此还可以从非潜在特征点估算出噪声水平。
3)采用层次b样条算法对步骤2)中所划分的潜在特征点进行拟合包括两个步骤：
31)将局部数据参数化；
311)建立z轴垂直于微切平面，x、y方向任意的局部直角坐标系；
312)将邻域数据通过旋转变化矩阵变换到该局部坐标系下；
313)以局部坐标系的x、y方向作为样条曲面的u、v方向；
32)利用层次b样条拟合曲面；
321)在u、v方向上定义一系列密度逐层加倍的网格状控制点φ0,φ1,…,φn；
322)在拟合的开始用最稀疏的控制点φ0拟合从真实曲面f获得的采样数据，得到拟合结果f0，并计算拟合误差e＝f-f0；
323)用密度加倍的控制点φ1对误差e进行二次拟合，得到曲面f1；
324)重复步骤323)，直到拟合均方差小于步骤2)中所求取的噪声水平；
325)最终曲面f表示为各次拟合曲面的加和，即
图3(b)是为了提高后续计算效率和方便特征计算通过控制点细化操作将基于低层次控制点的b样条曲面表达式转换为基于高层次控制点的b样条曲面表达式，从而得到一个统一的基于最高层次控制点的b样条表达式。
4)在步骤3)拟合过程中，记录曲面变化信息以及曲率尺度空间，构建稳定局部坐标系的显著特征点，包括以下5个步骤：
41)基于层次b样条拟合过程构建曲率尺度空间；
42)邻域和曲率空间多尺度特征点检测；
43)滤除曲率分布方向性不明确的特征点；
44)滤除边界点附近的特征点；
45)得到能够建立良好区分性特征描述符的特征点。
为了保证特征描述符所用局部坐标系的稳定性，本项目在多尺度检测后，加入一个验证环节，滤除虚假特征点。对任意一个备选特征点进行验证流程如下：、
①对由当前备选特征点及其邻域点构成的点集(记为u)进行坐标变换，使变换后的备选特征点法向量与z轴平行；
②将xoz平面绕z轴旋转15°，利用旋转后的平面将点集u划分为a、b两个子集(a∪b＝u)；
③计算子集a、b中各点高斯曲率的均值
④从子集a中筛选出与备选特征点高斯曲率差别小于一定阈值γ的点(称为曲率邻域点)，并对曲率邻域点进行pca分析，然后，计算最大的两个pca特征值之间的比例ηai，以度量子集a曲率邻域点的线性程度；对子集b进行同样的计算得到ηbi；
⑤重复执行步骤②～④，直到xoz平面绕z轴旋转180°(共12次旋转)；
⑥找到△max＝max(△1,△2,......,△12)和
这样可以保证曲率邻域点呈线性分布，并具有良好的指向性，有利于建立稳定可靠的局部坐标系。
5)根据层次b样条控制点分布信息以及控制点间曲率大小构建二进制特征描述符。即用1个bit数据表示特征描述符的一个维度，进而采用hamming距离进行描述符的相似性度量。特征描述符支撑邻域半径为平均曲率倒数的10倍。特征描述符构建方法可以分为如下3个步骤：
51)如图4所示，在拟合过程中进行误差阈值截断，形成控制点分布图；
52)如图5所示，以是否需要进一步细化为准则考察各个控制点，形成二进制编码，其中0表示无需进一步细化即可达到拟合精度，1表示需要进一步细化达到拟合精度；
53)将编码值按照逐层细化结果的行优先顺序排列，得到一个二进制描述符。
6)如果特征点检测具有良好的重复性，那么，从两个视角数据检测出的特征点将具有相似的拓扑关系，即在局部坐标系下每个特征点与距离其最近的k个特征点之间的距离和方位保持不变。上述不变量为特征点的匹配提出额外的约束条件。根据步骤5)所构建的特征描述符的相似性，依靠特征点的拓扑关系在模型点云中搜索对应特征点，最终实现特征点匹配，匹配方案如下：
61)基于传统特征点匹配方法进行初始匹配；
62)基于特征点拓扑关系进行验证，滤除初始匹配中存在的虚假匹配点；
63)对于步骤61)，62)中没有匹配的特征点，采用拓扑关系进行二次匹配。
假设从数据点云和模型点云中检测到的特征点个数分别为m 1和n 1，那么，对于任意数据点云中的任意特征点
①计算
②对于模型点云中每一个特征点，计算其到其他特征点的距离和方位，得到如下拓扑矩阵d2：
③将
④找到向量n中最大元素的标号k，如果该元素取值大于3则，判定
1.基于层次b样条的多尺度点云特征点检测与匹配，其特征在于，包括以下步骤：
1)构建一种曲面变化度量指标δp；
2)根据步骤1)所构建的曲面变化度量指标将点云分为潜在特征点和非潜在特征点两类，并根据非潜在特征点估算点云噪声水平；
3)采用层次b样条多尺度算法对步骤2)中所划分的潜在特征点进行拟合；
4)在步骤3)拟合过程中，记录曲面变化信息以及曲率尺度空间，构建稳定局部坐标系的显著特征点；
5)根据层次b样条控制点分布信息以及控制点间曲率大小构建二进制特征描述符；
6)根据步骤5)所构建的特征描述符的相似性，依靠特征点的拓扑关系在模型点云中搜索对应特征点，最终实现特征点匹配。
2.根据权利要求1所述的基于层次b样条的多尺度点云特征点检测与匹配，其特征在于：所述步骤1)中构建一种曲面变化程度的度量指标δp的方法为：
任意一点p的k邻近点重心
其中，i表示第i个邻近点；ε表示点云中包含的噪声，当点云中的噪声为零均值时，任意一点p的邻近点重心
式(1)同时还是对点云进行均值平滑的公式，因此利用平滑收缩幅值来构建一种曲面变化程度的度量指标δp，计算公式如式(2)所示：
其中，
任意一点p的距离加权k邻域点重心
其中，wdi是距离加权的权重。
3.根据权利要求2所述的基于层次b样条的多尺度点云特征点检测与匹配，其特征在于：真实扫描点云具有非均匀采样的特性，为了克服采样密度带来变化的影响，采用式(4)所示的方法对每一邻域点进行加权，即：
其中，权值wsi取为pi到其最近的5个邻近点的平均距离；np为p的法向量；
对上述曲面变化程度的度量指标δp添加符号，使δp具有表现曲面凹凸的能力，符号的确定准则如下：
如果向量
其中δp的取值具有正负变化并且能够表达曲面弯曲程度，即平滑收缩指数ssi。
4.根据权利要求1或3所述的基于层次b样条的多尺度点云特征点检测与匹配，其特征在于：所述步骤2)中，潜在特征点与非潜在特征点的划分是根据平滑收缩指ssi计算之后，利用||ssi||的平均值倍数确定的；由于平坦区域估算的噪声水平比从尖锐特征处估算出的噪声水平具有更高的可信度，在平坦区域主要分布非潜在特征点，因此利用非潜在特征点估算噪声水平。
5.根据权利要求1所述的基于层次b样条的多尺度点云特征点检测与匹配，其特征在于所述步骤3)中，采用层次b样条算法对步骤2)中所划分的潜在特征点进行拟合包括两个步骤：
31)将局部数据参数化；
311)建立z轴垂直于微切平面，x、y方向任意的局部直角坐标系；
312)将邻域数据通过旋转变化矩阵变换到该局部坐标系下；
313)以该局部坐标系的x、y方向作为样条曲面的u、v方向；
32)利用层次b样条拟合曲面；
321)在u、v方向上定义一系列密度逐层加倍的网格状控制点φ0,φ1,…,φn；
322)在拟合的开始用最稀疏的控制点φ0拟合从真实曲面f获得的采样数据，得到拟合结果f0，并计算拟合误差e＝f-f0；
323)用密度加倍的控制点φ1对误差e进行二次拟合，得到曲面f1；
324)重复步骤323)，直到拟合均方差小于步骤2)中所求取的噪声水平；
325)最终曲面f表示为各次拟合曲面的加和，即
6.根据权利要求1所述的基于层次b样条的多尺度点云特征点检测与匹配，其特征在于：所述步骤4)中，利用在步骤3)拟合过程中记录的曲面变化信息以及曲率尺度空间，构建稳定局部坐标系的显著特征点，包括以下步骤：
41)基于层次b样条拟合过程构建曲率尺度空间；
42)邻域和曲率空间多尺度特征点检测；
43)滤除曲率分布方向性不明确的特征点；
44)滤除边界点附近的特征点；
45)得到能够建立良好区分性特征描述符的特征点。
7.根据权利要求6所述的基于层次b样条的多尺度点云特征点检测与匹配，其特征在于：在所述步骤42)之后，还包括一个验证环节，对任意一个备选特征点进行验证，滤除虚假特征点，以保证特征描述符所用局部坐标系的稳定性；
所述对任意一个备选特征点进行验证包括以下步骤：
①对由当前备选特征点及其邻域点构成的点集u进行坐标变换，使变换后的备选特征点法向量与z轴平行；
②将xoz平面绕z轴旋转15°，利用旋转后的平面将点集u划分为a、b两个子集，即a∪b＝u；
③计算子集a、b中各点高斯曲率的均值
④从子集a中筛选出与备选特征点高斯曲率差别小于一定阈值γ的点，称为曲率邻域点，并对曲率邻域点进行pca分析，然后，计算最大的两个pca特征值之间的比例ηai，以度量子集a曲率邻域点的线性程度；对子集b进行同样的计算得到ηbi；
⑤重复执行步骤②～④，直到xoz平面绕z轴旋转12次共旋转了180°；
⑥找到△max＝max(△1,△2,......,△12)和
8.根据权利要求1所述的基于层次b样条的多尺度点云特征点检测与匹配，其特征在于：所述步骤5)中，特征描述符构建方法包括以下步骤：
51)在拟合过程中进行误差阈值截断，形成控制点分布图；
52)以是否需要进一步细化为准则考察各个控制点，形成二进制编码，其中0表示无需进一步细化即能够达到拟合精度，1表示需要进一步细化达到拟合精度；
53)将编码值按照逐层细化结果的行优先顺序排列，得到一个二进制特征描述符。
9.根据权利要求1所述的基于层次b样条的多尺度点云特征点检测与匹配，其特征在于：所述步骤6)中，特征点匹配包括以下步骤：
61)基于传统特征点匹配方法进行初始匹配；
62)基于特征点拓扑关系进行验证，滤除初始匹配中存在的虚假匹配点；
63)对于步骤61)，62)中没有匹配的特征点，采用拓扑关系进行二次匹配。
10.根据权利要求书1所述的基于层次b样条的多尺度点云特征点检测与匹配，其特征在于：所述步骤6)中，依靠拓扑关系在模型点云中搜索对应特征点，包括以下步骤：
①设从数据点云中检测到的特征点个数为m 1，计算任意数据点云中的任意特征点
②设从模型点云中检测到的特征点个数为n 1，对于模型点云中每一个特征点，计算其到其他特征点的距离和方位，得到如下拓扑矩阵d2：
③将
其中δ1和δ2分别为距离和方位特征容忍度；
④找到向量n中最大元素的标号k，如果该元素取值大于3则，判定
