本发明涉及三维碎片拼接技术领域，尤其涉及一种基于断裂面形状特征的三维碎片拼接重组方法。
背景技术：
由于野外考古学中三维扫描设备的使用越来越广泛，断裂三维物体的全自动拼接重组问题越来越受到重视，当器具碎片的数量很大并且多个器具碎片混合时，手动拼接重组是繁重而且单调的工作。同样，对于数量庞大、极其珍贵的文物，人工参与修复以及修复人员的缺失也是一个非常严重的问题。因此，计算机辅助器具碎片拼接重组对于文物修复重组来说非常重要。现有技术大多都只针对同一种器具的碎片进行拼接重组。
技术实现要素：
根据现有技术存在的问题，本发明公开了一种基于断裂面形状特征的三维碎片拼接重组方法，具体采用如下步骤：
根据碎片边缘的特征组合提取碎片断裂面的三维轮廓；
根据碎片断裂面三维轮廓的多尺度形状特征进行断裂面匹配，得到碎片间的两两匹配结果；
筛选未匹配碎片，获取未匹配碎片碎片边缘的四种不同组合特征分别为lle四维特征、pca二维特征、混合特征和lle二维特征，采用四种不同组合特征重复上述两个步骤进行断裂面匹配得到初始碎片匹配结果；
对未完成匹配的碎片进行异常处理：对于仍未匹配的碎片，增加碎片边缘的聚类数目从而得到多数量的断裂面轮廓，将多个断裂面轮廓与其他碎片的未标记断裂面进行匹配输出匹配矩阵；
优化匹配矩阵：判断每组碎片的数量是否小于设定阈值，如果小于则将该组碎片与其他组碎片进行轮廓匹配，并将符合标准的两组碎片合并，对于同组碎片根据碎片周围的其他碎片调整当前碎片的位置，直到该组碎片之间的距离值小于设定阈值为止从而得到优化后的匹配矩阵,根据优化后的匹配矩阵进行碎片间的拼接重组。
本发明公开的一种基于断裂面形状特征的三维碎片拼接重组方法，可以直接将三维碎片进行重组、不需要对碎片数据进行预先处理，不仅对单一器物(盘子)适用，并且可以对多器物混合碎片(盘子、碗等)进行拼接重组，该方法重组准确且运行时间短。
附图说明
为了更清楚地说明本申请实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请中记载的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1为本发明中方法的简单流程图；
图2为本发明中碎片断裂面提取的示意图；
图3为本发明中碎片拼接重组的示意图；
图4为本发明中点的线形几何特征的示意图。
具体实施方式
为使本发明的技术方案和优点更加清楚，下面结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚完整的描述：
如图1所示的一种基于断裂面形状特征的三维碎片拼接重组方法，具体采用如下步骤：
s1:根据碎片边缘的特征组合提取碎片断裂面的三维轮廓具体采用如下方式：根据三维碎片中点的曲率值获取碎片的边缘点集，采用kmeans方法对碎片边缘点进行预聚类得到合适的聚类数目，提取碎片边缘点的特征，根据碎片边缘特征和聚类数目进行贝叶斯高斯混合聚类得到碎片断裂面的三维轮廓。本步骤利用聚类的方法提取三维轮廓(如图2所示)，具体步骤为：
s11:曲率提取。对于每一个碎片，计算碎片模型中每个点的最大曲率，并提取最大曲率值大于阈值c的点组成点集s，这些点大部分是碎片的边缘点。
s12:聚类得到断裂面的轮廓。对于提取的碎片点集s进行聚类以分离碎片的断面轮廓。具体步骤为：
s121:确定聚类数目。首先，根据点的三维坐标，使用kmeans聚类对点集s进行预聚类。我们根据对碎片的观察得出：点集s的聚类数目一般在3-7类。所以，我们对每一个聚类数目都进行kmeans聚类，并将每个点与其聚类中心的平方距离累计得到差距平方和[d1,d2,d3,d4,d5]，进一步得到相邻平方和之间的差值[cd1,cd2,cd3,cd4]，(其中，cd1＝d1-d2，其他以此类推)。比较每个聚类数目下的差距平方和，找到差距平方和di低于阈值d且cdi/cdi 1<＝2.5的聚类数目作为最后的聚类数目。
s122:使用碎片边缘点的四种特征组合中的一种。
s123:贝叶斯高斯混合聚类。根据前面步骤得到的聚类数目和点的特征对点集s进行贝叶斯高斯混合聚类，得到聚类结果之后统计每个类里的点数量。如果出现某一类包括了大部分点的情况，这说明点集中有聚集的异常点群，该聚类结果不是我们期望的，这时我们使用异常情况下的点特征进行重新聚类；如果未出现异常情况，我们保留原有的聚类结果。
s2:根据碎片断裂面轮廓的多尺度形状特征进行断裂面匹配，得到碎片间的两两匹配结果具体方式为：对断裂面的三维轮廓点进行数据预处理得到单点、等距的轮廓点云，选择三维轮廓的预匹配断面集，提取轮廓点云中点的多尺度线形特征，不同尺度特征的断裂面匹配得到不同的匹配结果，根据第一匹配占据绝对优势方法将符合标准的匹配结果记录下来，并将对应的断裂面和碎片进行标记。本步骤利用点的线形几何特征对碎片的断裂面进行匹配(如图3所示)，具体步骤为：
s21：数据预处理。对于碎片断面分割部分得到的轮廓点云进行采样，得到类似于珍珠项链一样的单点、等距(近似)的轮廓。对每个点以该点为球心，10.0为半径计算该点的密度，并对所有点的密度值进行统计。一般选取点集里密度值频率最高的一个点作为起点，沿着左侧或右侧方向，以大于0.5的间距，以与上一个加入点夹角最小的方向寻找下一个待加入点(已经过路径中的点会被标记)，直到最后一个加入点与起点的距离小于等于1.5。
断裂面匹配有两种情况：一个断裂面与另一个断裂面完全匹配(简称“一对一匹配方式”)和一个断裂面与多个断裂面匹配(简称“一对多匹配方式”)。
s22：提取点的多尺度特征，并对每一尺度的特征进行断裂面中的“一对一”匹配方式，“一对一匹配方式”匹配的具体方法如下：
s221：使用包围盒法找到轮廓fi的预匹配集合。
s222：找到断面轮廓fi中的特征角点集。对于fi的特征角点集中的每个角点h，在fq的特征角点集中找到最佳对应点，得到fi与fq的匹配点对集合。计算最佳对应点的方法为：计算角点h的大(中、小)尺度特征与fq中所有角点的大(中、小)尺度特征的兰氏距离，选择距离最小的点作为最佳对应点。
s223：对fi与fq的匹配点对进行ransac消除误匹配，根据ransac得到的旋转平移矩阵进行icp精确匹配得到旋转平移矩阵bestt记录下来，并记录经过bestt后的fi与fq对应点的距离小于0.5的轮廓点的数量num。
s224：对断面轮廓fi的预匹配集合中的每一个断面都计算该断面与断面轮廓fi的旋转矩阵bestt和匹配点对数num，将匹配点对数num按照从大到小排序，如果第一匹配点对数num满足如下设定要求：第一匹配点对数num>a且第一匹配点对数num>第二匹配点对数num*b，b可以取值为1.5，则记录对应的断面和碎片。(其中m的大小与断面点数有关)。
s23:使用三种尺度的特征重复步骤s22。
s24：断裂面中的“一对多”匹配方式，具体步骤如下：
s241：选出一部分断面作为那个“多”的集合smallf，其余断面则归为“一”的断面集合bigf。选取规则为：
其中，l,w,h是断面包围盒的长宽高，m是断面的数量。
s242：对于smallf中的断面sfi，根据特征法计算预匹配集合。
s243：找到断面轮廓fi中的特征角点集，并计算1邻近特征集和2邻近特征集。
s244：使用断面的特征角点的中(小)尺度特征，计算sfi和它的预匹配集合中的每一个断面之间的特征角点的匹配点对集合，并进一步得到符合标准的匹配对，计算方法与前面的“一对一匹配方式”的情况一致(即s22下的一对一情况下的子步骤s223-s234)。
s25：使用中尺度和小尺度特征重复步骤s24。
s3:依次使用碎片边缘的不同特征组合(共四种)，重复上述两个步骤，得到初始碎片匹配结果具体采用如下方式：碎片边缘的四种特征组合分别为lle四维特征、pca二维特征、混合特征、lle二维特征。对前一次迭代中未被标记的碎片使用新的碎片边缘特征提取得新的断裂面轮廓，对新的轮廓和前一次迭代中未标记的旧轮廓进行断裂面轮廓多尺度匹配。综合四次匹配得到初始碎片匹配结果，将相互之间有匹配关系的碎片放到同一组中，得到互不交叉的多组碎片。具体方法如下：
s31:从同一组碎片的匹配中选取匹配点数最多的一对碎片，其中固定的碎片当做最先加入该组的碎片，等级为0，将与该碎片有直接匹配关系的碎片加入，等级为1，与等级1有直接匹配关系的记为等级2，以此类推，直到该组碎片都加入。
s4:对仍未匹配的碎片进行异常处理，得到最终匹配结果具体采用如下方式：(1)对于仍未匹配的碎片，增加碎片边缘的聚类数目，得到更小的断裂面轮廓，与其他碎片的未标记断裂面进行匹配；(2)将整个碎片的轮廓分别与已有的多组碎片轮廓进行匹配。将满足标准的匹配关系记录下来，并标记对应的断面和碎片。具体方法为：
s41：在步骤s121中我们假设点集s的聚类数目一般在3-7类，这限制了碎片最少分成3个轮廓，最多分成7个轮廓。对于未匹配的碎片，我们可以增加轮廓的个数，细分轮廓(比如分成5-10类等等)，将细分的轮廓与上述步骤中未标记的断面轮廓进行多尺度匹配。将满足标准的匹配关系记录下来，并标记对应的断面和碎片。
s42:步骤s3得到的互不交叉的多组碎片，我们记为g1，g2...gi等，将gi中的碎片轮廓点集按照得到的匹配关系，拼接到一起形成一个新的轮廓点集，对于新点集中的每一点，如果周围没有来自其他碎片的点的存在(即该区域没有匹配碎片)，那么将该点保存，计算所有点得到未匹配的轮廓区域记为该组碎片的碎片轮廓。
s43：将经过s41仍未匹配的碎片的整体边缘轮廓与gi的碎片轮廓进行多尺度匹配，将满足标准的匹配关系记录下来，并标记对应的碎片和碎片组。
s44:对于不满足标准的碎片记录在未匹配碎片中。
s5:优化碎片间的匹配矩阵具体采用如下方式：如果某一组碎片的数量小于4，将该组与其他组进行轮廓匹配，并将符合标准的两组合并；对于同组碎片，根据碎片周围的其他碎片来调整当前碎片的位置，迭代多次，得到优化的匹配矩阵。具体方法为：
s51:对于同组碎片，计算碎片间最大的缝的大小c，然后从最后加入的碎片开始，根据与该碎片轮廓距离不超过c的点集来调整该碎片的位置，用调整后的碎片代替原来的碎片位置，依次调整前一个加入的碎片，直到第一个加入的碎片，完成一次迭代。
s52:迭代k次，得到优化后的结果(k取5-10之间)。
本发明提供的一种基于断裂面形状特征的三维碎片拼接重组方法，该方法可以实现属于多个器具的三维碎片的拼接重组；相比现有技术，本方法的精确度有很大提高。
以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。
1.一种基于断裂面形状特征的三维碎片拼接重组方法，其特征在于包括以下步骤：
根据碎片边缘的特征组合提取碎片断裂面的三维轮廓；
根据碎片断裂面三维轮廓的多尺度形状特征进行断裂面匹配，得到碎片间的两两匹配结果；
筛选未匹配碎片，获取未匹配碎片碎片边缘的四种不同的组合特征，该组合特征分别为lle四维特征、pca二维特征、混合特征和lle二维特征，采用四种不同的组合特征重复上述两个步骤进行断裂面匹配得到初始碎片匹配结果；
对未完成匹配的碎片进行异常处理：对于仍未匹配的碎片，增加碎片边缘的聚类数目从而得到多数量的断裂面轮廓，将多个断裂面轮廓与其他碎片的未标记断裂面进行匹配输出匹配矩阵；
优化匹配矩阵：判断每组碎片的数量是否小于设定阈值，如果小于则将该组碎片与其他组碎片进行轮廓匹配，并将符合标准的两组碎片合并，对于同组碎片根据碎片周围的其他碎片调整当前碎片的位置，直到该组碎片之间的距离值小于设定阈值为止从而得到优化后的匹配矩阵，根据优化后的匹配矩阵进行碎片间的拼接重组。
2.根据权利要求1所述的方法，其特征在于：根据三维碎片中点的曲率值获取碎片的边缘点集，采用kmeans方法对碎片边缘点进行预聚类得到满足要求的聚类数目，提取碎片边缘点的特征，根据碎片边缘特征和聚类数目进行贝叶斯高斯混合聚类得到碎片断裂面的三维轮廓。
3.根据权利要求2所述的方法，其特征在于：对断裂面的三维轮廓进行数据预处理得到单点、等距的轮廓点云，选择三维轮廓的预匹配断面集，提取轮廓点云中点的多尺度线形特征，不同尺度特征的断裂面匹配得到不同的匹配结果，根据第一匹配占据绝对优势方法删除错误的匹配结果，记录符合标准的匹配结果，并标记对应的断裂面和碎片从而得到碎片间的两两匹配结果。
4.根据权利要求3所述的方法，其特征在于：所述第一匹配占据绝对优势方法为：对断面轮廓fi的预匹配集合中的每一个断面都计算该断面与断面轮廓fi的旋转矩阵bestt和匹配点对数num，将匹配点对数num按照从大到小排序，如果第一匹配点对数num满足如下设定要求：第一匹配点对数num>a且第一匹配点对数num>第二匹配点对数num*b，则记录对应的断面和碎片。
5.根据权利要求1所述的方法，其特征在于：采用四种不同组合特征进行断裂面匹配时：对前一次迭代中未被标记的碎片使用新的碎片边缘特征提取获得新的断裂面轮廓，对新的断裂面轮廓和前一次迭代中未标记的旧断裂面轮廓进行断裂面轮廓多尺度匹配，综合四次匹配得到初始碎片匹配结果，将相互之间有匹配关系的碎片放到同一组中，得到互不交叉的多组碎片。
6.根据权利要求5所述的方法，其特征在于：对未完成匹配的碎片进行异常处理时还包括：将整个碎片的轮廓分别与已有的多组碎片轮廓进行匹配，将满足标准的匹配关系记录下来，并标记对应的断面和碎片。
7.根据权利要求1-6任意一项权利要求所述的方法，其特征还在于：断裂面轮廓的特征包括：
对于轮廓中的一点p，沿着轮廓在点p的左右两侧各取k个邻近点(l1,l2,l3,.......,lk-1,lk)和(r1,r2,r3,.......,rk-1,rk)，其中每个点的间距设为m，对2k个邻近点与点p的关系构造特征，具体如下：
对于左侧k个点，计算这k个点与点p的欧式距离得到k维特征|l1p|,|l2p|...|lkp|；
计算向量pl1和l1l2的余弦值，l1l2和l2l3的余弦值，……，lk-2lk-1和lk-1lk的余弦值，即相邻三个点之间的夹角余弦得到k-1维特征cos(∠pl1l2),cos(∠l1l2l3)...cos(∠lk-2lk-1lk)；
右侧k个点同理计算得到另外2k-1维特征；
计算l1和r1，l2和r2......，lk和rk之间的横向距离等k维特征|l1r1|,|l2r2|...|lkrk|；
最后加上cos(∠l1pr1)和cos(∠lkprk)即总共得到5k维特征。
8.根据权利要求3所述的方法，其特征还在于：所述预匹配断面集的选取方式为：当一个断面与一个断面匹配时采用包围盒法，当一个断面与多个断面匹配时采用特征法；
所述包围盒法方式为：计算每个断面轮廓fi的包围盒得到长、宽、高(l,w,h)三个数据，计算断面轮廓fi的(l,w,h)向量与其他断面轮廓的(l,w,h)的l2距离，并按照从小到大的规则排序，从距离fi最小的断面fq开始，如果fq的长、宽、高三项中有两项以上都与fi的差距小于等于p，则fi与fq在形状上相似，将fq加入到fi的预匹配集合中，直到集合中加入断面的数量为n；
所述特征法方式为：计算断面与其他断面的特征角点集的第一邻近特征集之间的hausdorff距离，并按照从小到大的顺序将其排序，选择距离最小的n个断面；同理计算第二邻近特征集之间的hausdorff距离，选择距离最小的n个断面，将此2n个断面组成该断面的预匹配集合；
所述特征角点定义为：对于轮廓中的一点p，选取∠l1pl2在20°到160°之间的点作为特征角点，所有特征角点组成该断面轮廓fi的特征角点集；
所述第一邻近特征为(∠l1pl2,|pl1| |pr1|)；
所述第二邻近特征为(∠l1pl2,|l1r1|,|pl2| |pr2|,-cos(∠l1l2l3)-cos(∠r1r2r3))；
所有特征角点的第一或第二邻近特征组成断面的第一或第二邻近特征集。
9.根据权利要求5所述的方法，其特征还在于：碎片边缘的四种特征组合具体为：
所述lle四维特征为：将点的三维坐标进行lle降维，得到前两维特征(xlle,ylle)，原始的三维坐标由pca降维得二维坐标，对每个点根据二维坐标找到距离该点最近的r个点组成点集进行最小二乘拟合得到该点的估计斜率m和截距b，将(xlle,ylle)与(m,b)拼接得到点的四维特征；
所述pca二维特征为：将点的三维坐标进行pca降维得到点的二维特征；
所述混合特征为：pca二维特征和lle四维特征的组合；
lle二维特征：将点的三维坐标进行lle降维得到点的二维特征。
技术总结