基于动态分层的公共标志点自动匹配方法

摘要

本发明涉及一种基于动态分层的公共标志点自动匹配方法，其特征在于：其具体的方法按以下步骤实现：设由三维扫描仪和计算机在视点处获得的待测物体的标志点集合为P；在P中搜索X轴坐标值最小的n个标志点，在Q中搜索X轴坐标值最小的n个标志点，构建Q的四个动态距离矩阵，将P的四个动态距离矩阵中的元素值与Q的四个动态距离矩阵中的元素值进行判断是否相等，由E中所有标志点构成集合E’，由F中所有标志点构成集合F’；如果标志点A到E’中所有标志点的欧式距离与标志点B到F’中所有对应标志点的欧式距离都相等。其有效的降低了匹配错误率；而且还解决了传统匹配标志点所面临的速度问题和精度问题。

说明书

技术领域

本发明涉及一种基于动态分层的公共标志点自动匹配方法，属于计算机视觉技术领域。

背景技术

三维重构是通过计算机对物体进行模拟、识别、分析后建立相应的模型来虚拟景象的一种技术，其通过测量物体的各个位置的三维信息进行建模。由于物体的大小和立体结构使得投影机不能一次获取到物体完整的三维信息，需要在多次测量后，通过点云拼接来建立整体的模型。点云拼接就是把不同部分的点云信息，通过坐标变换统一到一个坐标系下，其关键在于特征点或标志点的快速匹配。

目前的点云拼接方法大致分为两种，一种是提取物体表面具有明显几何信息的点（如曲率，法向量，二阶矩不变量等），进行分析来匹配这些特征点，再求取点云的坐标变换矩阵。如朱延娟等人根据测点及其邻域点来估算点的曲面法线矢量，并计算各个点的曲率，通过曲率和法线矢量的方向来匹配特征点对。然而这种方法会产生大量的误匹配，而且算法的计算量也很大，尤其在物体的几何信息不明显的情况下很难找到特征点对，所以该方法很难在实际应用中得到推广。第二种方法为在物体表面粘贴标志点作为物体的特征点，通过匹配标志点来解决上述问题。但是目前标志点匹配的方法基本都是采用全局搜索进行匹配各个标志点对，其利用标志点的空间特征不变性进行匹配标志点对，如许晓栋等人以一种“不太可能发生的小概率事件”来实现标志点匹配。但是这种方法需要计算大量无用标志点距离，同时还会产生很多错误点对，其计算速度和拼接精度也很难解决实际工业生产需求。本发明提出了一种基于动态分层的公共标志点自动匹配方法，该方法从点云的各个局部区域进行动态搜索标志点，引入动态距离矩阵记录分层搜索标志点间的距离，通过比较距离矩阵匹配标志点对，不仅减少搜索区域、降低匹配错误率，而且匹配算法简单，有效地降低匹配错误率，提高了匹配速度。

发明内容

本发明的目的在于提供一种基于动态分层的公共标志点自动匹配方法，其有效的降低了匹配错误率；而且还解决了传统匹配标志点所面临的速度问题和精度问题。

本发明的技术方案是这样实现的：基于动态分层的公共标志点自动匹配方法，其特征在于：三维扫描仪通过电缆与计算机连接，待测物体的外表面上贴有标志点，其具体的方法按以下步骤实现：

步骤1、设由三维扫描仪和计算机在视点处获得的待测物体的标志点集合为P；在保证三维扫描仪的参数不变的情况下，由三维扫描仪在视点处获得的待测物体的标志点集合用Q表示，P和Q中共同标志点的个数为N，N≥3，设n为3。

步骤2、在P中搜索X轴坐标值最小的n个标志点，由n个标志点构成集合P_Min_x, P_Min_x（i）为集合P_Min_x第i个元素，i=1，2,…n；在P中搜索X轴坐标值最大的n个标志点，由n个标志点构成集合P_Max_x, P_Max_x（i）为集合P_Max_x第i个元素，i=1，2,…n；在P中搜索Y轴坐标值最小的n个标志点，由n个标志点构成集合P_Min_y, P_Min_y（i）为集合P_Min_y第i个元素，i=1，2,…n；在P中搜索Y轴坐标值最大的n个标志点，由n个标志点构成集合P_Max_y, P_Max_y（i）为矩阵P_Max_y第i个元素，i=1，2,…n。

步骤3、构建P的四个动态距离矩阵，分别用S_{_}P_Min_x、S_{_}P_Max_x、S_{_}P_Min_y、S_{_}P_Max_y表示，其中S_{_}P_Min_x（i,j）为矩阵S_{_}P_Min_x第i行，第j列元素，表示P_Min_x（i）到P_Min_x（j）的欧式距离；S_{_}P_Max_x（i,j）为矩阵S_P_Max_x第i行，第j列元素，表示P_Max_x（i）到P_Max_x（j）的欧式距离；S_{_}P_Min_y（i,j）为矩阵S_P_Min_y第i行，第j列元素，表示P_Min_y（i）到P_Min_y（j）的欧式距离；S_{_}P_Max_y（i,j）为矩阵S_P_Max_y第i行，第j列元素，表示P_Max_y（i）到P_Max_y（j）的欧式距离。

步骤4、在Q中搜索X轴坐标值最小的n个标志点，由n个标志点构成集合Q_Min_x, Q_Min_x（i）为集合Q_Min_x第i个元素，i=1，2,…n；在Q中搜索X轴坐标值最大的n个标志点，由n个标志点构成集合Q_Max_x，Q_Max_x（i）为集合Q_Max_x第i个元素，i=1，2,…n；在Q中搜索Y轴坐标值最小的n个标志点，由n个标志点构成集合Q_Min_y, Q_Min_y（i）为集合Q_Min_y第i个元素，i=1，2,…n；在Q中搜索Y轴坐标值最大的n个标志点，由n个标志点构成集合Q_Max_y, Q_Max_y（i）为矩阵Q_Max_y第i个元素，i=1，2,…n。

步骤5、构建Q的四个动态距离矩阵，分别用S_{_}Q_Min_x、S_{_}Q_Max_x、S_{_}Q_Min_y、S_{_}Q_Max_y表示，其中S_{_}Q_Min_x（i,j）为矩阵S_{_}Q_Min_x第i行，第j列元素，表示Q_Min_x（i）到Q_Min_x（j）的欧式距离；S_{_}Q_Max_x（i,j）为矩阵S_Q_Max_x第i行，第j列元素，表示Q_Max_x（i）到Q_Max_x（j）的欧式距离；S_{_}Q_Min_y（i,j）为矩阵S_Q_Min_y第i行，第j列元素，表示Q_Min_y（i）到Q_Min_y（j）的欧式距离；S_{_}Q_Max_y（i,j）为矩阵S_Q_Max_y第i行，第j列元素，表示Q_Max_y（i）到Q_Max_y（j）的欧式距离。

步骤6、将P的四个动态距离矩阵中的元素值与Q的四个动态距离矩阵中的元素值进行判断是否相等，如果P_Min_x中有P_n个标志点间的所有欧式距离与Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y中P_n个标志点间的所有欧式距离都相等，且P_n≥3，那么由上述P_Min_x中的P_n个标志点构成公共标志点初始集合E，在Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y的标志点中，与E中的标志点为同一个标志点的集合构成匹配公共标志点初始集合F；否则，如果P_Max_x中有P_n个标志点间的所有欧式距离与Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y中P_n个标志点间的所有欧式距离都相等，且P_n≥3，那么由上述P_Max_x中的P_n个标志点构成公共标志点初始集合E，在Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y的标志点中，与E中的标志点为同一个标志点的集合构成匹配公共标志点初始集合F；否则，如果P_Min_y中有P_n个标志点间的所有欧式距离与Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y中P_n个标志点间的所有欧式距离都相等，且P_n≥3，那么由上述P_Min_y中的P_n个标志点构成公共标志点初始集合E，在Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y的标志点中，与E中的标志点为同一个标志点的集合构成匹配公共标志点初始集合F；否则，如果P_Max_y中有P_n个标志点间的所有欧式距离与Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y中P_n个标志点间的所有欧式距离都相等，且P_n≥3，那么由上述P_Max_y中的P_n个标志点构成公共标志点初始集合E，在Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y的标志点中，与E中的标志点为同一个标志点的集合构成匹配公共标志点初始集合F；否则，n=n+1，转而执行步骤2。

步骤7、由E中所有标志点构成集合E’，由F中所有标志点构成集合F’。

步骤8、如果E中的标志点都为P_Min_x中的标志点，那么在P中去掉E’中的标志点，构成集合P’，在P’中搜索X轴坐标值最小的标志点A；如果E中的标志点都为P_Max_x中的标志点，那么在P中去掉E’中的标志点，构成集合P’，在P’中搜索X轴坐标值最大的标志点A；如果E中的标志点都为P_Min_y中的标志点，那么在P中去掉E’中的标志点，构成集合P’，在P’中搜索Y轴坐标值最小的标志点A；如果E中的标志点都为P_Max_y中的标志点，那么在P中去掉E’中的标志点，构成集合P’，在P’中搜索Y轴坐标值最大的标志点A。

步骤9、如果F中的标志点都为Q_Min_x中的标志点，那么在Q中去掉F’中的标志点，构成集合Q’，在Q’中搜索X轴坐标值最小的标志点B；如果F中的标志点都为Q_Max_x中的标志点，那么在Q中去掉F’中的标志点，构成集合Q’，在Q’中搜索X轴坐标值最大的标志点B；如果F中的标志点都为Q_Min_y中的标志点，那么在Q中去掉F’中的标志点，构成集合Q’，在Q’中搜索Y轴坐标值最小的标志点B；如果F中的标志点都为Q_Max_y中的标志点，那么在Q中去掉F’中的标志点，构成集合Q’，在Q’中搜索Y轴坐标值最大的标志点B。

步骤10、如果标志点A到E’中所有标志点的欧式距离与标志点B到F’中所有对应标志点的欧式距离都相等，那么，将标志点A加入到E’中，将标志点B加入到F’中，并转而执行步骤8；

通过以上步骤可以两组不同视点下的公共标志点进行自动匹配。

本发明的积极效果是可以快速自动匹配重叠区域内的所有标志点，有效的降低了匹配错误率；而且还解决了传统匹配标志点所面临的速度问题和精度问题。该方法在进行三维点云拼接技术上具有实际价值，其可以在逆向工程、数字图像医学处理、计算机视觉、曲面质量检测等领域进行推广使用，其具有算法复杂性低、匹配错误率低等优点。

附图说明

图1是基于动态分层的公共标志点自动匹配方法所需设备构成图，其中：1为三维扫描仪,2为计算机，3为待测物体。

图2为动态搜索示例图。

具体实施方式

下面结合附图对本发明做进一步的描述：如图1所示，基于动态分层的公共标志点自动匹配方法，其特征在于：三维扫描仪1通过电缆与计算机2连接，待测物体3的外表面上贴有标志点，其具体的方法按以下步骤实现：

步骤1、设由三维扫描仪1和计算机2在视点1处获得的待测物体3的标志点集合为P；在保证三维扫描仪1的参数不变的情况下，由三维扫描仪1在视点2处获得的待测物体3的标志点集合用Q表示，P和Q中共同标志点的个数为N，N≥3，设n为3。

步骤2、在P中搜索X轴坐标值最小的n个标志点，由n个标志点构成集合P_Min_x, P_Min_x（i）为集合P_Min_x第i个元素，i=1，2,…n；在P中搜索X轴坐标值最大的n个标志点，由n个标志点构成集合P_Max_x, P_Max_x（i）为集合P_Max_x第i个元素，i=1，2,…n；在P中搜索Y轴坐标值最小的n个标志点，由n个标志点构成集合P_Min_y, P_Min_y（i）为集合P_Min_y第i个元素，i=1，2,…n；在P中搜索Y轴坐标值最大的n个标志点，由n个标志点构成集合P_Max_y, P_Max_y（i）为矩阵P_Max_y第i个元素，i=1，2,…n。

步骤3、构建P的四个动态距离矩阵，分别用S_{_}P_Min_x、S_{_}P_Max_x、S_{_}P_Min_y、S_{_}P_Max_y表示，其中S_{_}P_Min_x（i,j）为矩阵S_{_}P_Min_x第i行，第j列元素，表示P_Min_x（i）到P_Min_x（j）的欧式距离；S_{_}P_Max_x（i,j）为矩阵S_P_Max_x第i行，第j列元素，表示P_Max_x（i）到P_Max_x（j）的欧式距离；S_{_}P_Min_y（i,j）为矩阵S_P_Min_y第i行，第j列元素，表示P_Min_y（i）到P_Min_y（j）的欧式距离；S_{_}P_Max_y（i,j）为矩阵S_P_Max_y第i行，第j列元素，表示P_Max_y（i）到P_Max_y（j）的欧式距离。

步骤4、在Q中搜索X轴坐标值最小的n个标志点，由n个标志点构成集合Q_Min_x, Q_Min_x（i）为集合Q_Min_x第i个元素，i=1，2,…n；在Q中搜索X轴坐标值最大的n个标志点，由n个标志点构成集合Q_Max_x，Q_Max_x（i）为集合Q_Max_x第i个元素，i=1，2,…n；在Q中搜索Y轴坐标值最小的n个标志点，由n个标志点构成集合Q_Min_y, Q_Min_y（i）为集合Q_Min_y第i个元素，i=1，2,…n；在Q中搜索Y轴坐标值最大的n个标志点，由n个标志点构成集合Q_Max_y, Q_Max_y（i）为矩阵Q_Max_y第i个元素，i=1，2,…n。

步骤5、构建Q的四个动态距离矩阵，分别用S_{_}Q_Min_x、S_{_}Q_Max_x、S_{_}Q_Min_y、S_{_}Q_Max_y表示，其中S_{_}Q_Min_x（i,j）为矩阵S_{_}Q_Min_x第i行，第j列元素，表示Q_Min_x（i）到Q_Min_x（j）的欧式距离；S_{_}Q_Max_x（i,j）为矩阵S_Q_Max_x第i行，第j列元素，表示Q_Max_x（i）到Q_Max_x（j）的欧式距离；S_{_}Q_Min_y（i,j）为矩阵S_Q_Min_y第i行，第j列元素，表示Q_Min_y（i）到Q_Min_y（j）的欧式距离；S_{_}Q_Max_y（i,j）为矩阵S_Q_Max_y第i行，第j列元素，表示Q_Max_y（i）到Q_Max_y（j）的欧式距离。

步骤6、将P的四个动态距离矩阵中的元素值与Q的四个动态距离矩阵中的元素值进行判断是否相等，如果P_Min_x中有P_n个标志点间的所有欧式距离与Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y中P_n个标志点间的所有欧式距离都相等，且P_n≥3，那么由上述P_Min_x中的P_n个标志点构成公共标志点初始集合E，在Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y的标志点中，与E中的标志点为同一个标志点的集合构成匹配公共标志点初始集合F；否则，如果P_Max_x中有P_n个标志点间的所有欧式距离与Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y中P_n个标志点间的所有欧式距离都相等，且P_n≥3，那么由上述P_Max_x中的P_n个标志点构成公共标志点初始集合E，在Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y的标志点中，与E中的标志点为同一个标志点的集合构成匹配公共标志点初始集合F；否则，如果P_Min_y中有P_n个标志点间的所有欧式距离与Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y中P_n个标志点间的所有欧式距离都相等，且P_n≥3，那么由上述P_Min_y中的P_n个标志点构成公共标志点初始集合E，在Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y的标志点中，与E中的标志点为同一个标志点的集合构成匹配公共标志点初始集合F；否则，如果P_Max_y中有P_n个标志点间的所有欧式距离与Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y中P_n个标志点间的所有欧式距离都相等，且P_n≥3，那么由上述P_Max_y中的P_n个标志点构成公共标志点初始集合E，在Q_Min_x或Q_Max_x或Q_Min_y或Q_Max_y的标志点中，与E中的标志点为同一个标志点的集合构成匹配公共标志点初始集合F；否则，n=n+1，转而执行步骤2。

步骤7、由E中所有标志点构成集合E’，由F中所有标志点构成集合F’。

步骤8、如果E中的标志点都为P_Min_x中的标志点，那么在P中去掉E’中的标志点，构成集合P’，在P’中搜索X轴坐标值最小的标志点A；如果E中的标志点都为P_Max_x中的标志点，那么在P中去掉E’中的标志点，构成集合P’，在P’中搜索X轴坐标值最大的标志点A；如果E中的标志点都为P_Min_y中的标志点，那么在P中去掉E’中的标志点，构成集合P’，在P’中搜索Y轴坐标值最小的标志点A；如果E中的标志点都为P_Max_y中的标志点，那么在P中去掉E’中的标志点，构成集合P’，在P’中搜索Y轴坐标值最大的标志点A。

步骤9、如果F中的标志点都为Q_Min_x中的标志点，那么在Q中去掉F’中的标志点，构成集合Q’，在Q’中搜索X轴坐标值最小的标志点B；如果F中的标志点都为Q_Max_x中的标志点，那么在Q中去掉F’中的标志点，构成集合Q’，在Q’中搜索X轴坐标值最大的标志点B；如果F中的标志点都为Q_Min_y中的标志点，那么在Q中去掉F’中的标志点，构成集合Q’，在Q’中搜索Y轴坐标值最小的标志点B；如果F中的标志点都为Q_Max_y中的标志点，那么在Q中去掉F’中的标志点，构成集合Q’，在Q’中搜索Y轴坐标值最大的标志点B。

步骤10、如果标志点A到E’中所有标志点的欧式距离与标志点B到F’中所有对应标志点的欧式距离都相等，那么，将标志点A加入到E’中，将标志点B加入到F’中，并转而执行步骤8；

通过以上步骤可以两组不同视点下的公共标志点进行自动匹配。