本发明属于计算机图形学处理，具体涉及一种基于轮廓提取与角点检测的二维碎片拼接方法。
背景技术：
1、文物作为一种在古代社会生活中所留存下来的事物，反映了历史上不同时期下人们的生活情况，具有很强的历史性、人文性和不可再生性，对历史研究有着极大的意义。但由于时间流逝等自然因素以及某些人为因素影响，相当一部分文物在现代社会往往已经遭受了不同程度的损伤，这种损伤会对了解文物原本的风貌带来或多或少的影响，通常需要经过文物修复后才能变成我们日常博物馆里看到的精美模样。
2、文物修复是一门综合性很强的技术科学，横跨多领域多学科，以保存和认知文物的历史原貌、艺术价值和科学价值为目标，对文物的保存、传承、展示等具有重要意义。文物修复的综合性很大一部分来自于文物材质的多样性，如书画、金石、瓷器、纺织品等不同材质的修复技术往往有着很大差异。其中陶瓷器由于其硬度高、质地脆、多考古出土等原因更容易面临因外力作用产生的破碎问题，也正因此在陶瓷文物修复上碎片拼接始终是一个重要问题。
3、传统的手工拼接方法只能依靠于修复人员的技术与经验去进行不断的尝试，对修复人员的技术水平和专业素养要求较高；同时依靠人工进行拼接需要大量的时间与精力，对于出土的大量文物往往需要不菲的人工和成本；而且手工拼接在拼接过程中不可避免要与文物碎片产生频繁接触，极有可能对文物产生二次损伤。
4、随着近年来信息技术的不断发展，利用计算机辅助文物碎片进行数字化拼接的技术也取得了长足的进步。数字化拼接技术相比于传统的手工拼接技术有着诸多优点，如：通过三维扫描、数值计算等方法可以对文物碎片进行精确测量和分析，从而实现高精度的拼接操作；将文物碎片数字化在虚拟空间中进行拼接不需要对文物进行物理接触，避免了对文物碎片造成二次损伤；也可以利用计算机的计算能力缩短拼接的时间周期同时降低所需花费的成本，能够极大提高修复效率。
5、对出土文物碎片进行数字化拼接具有重要的价值与意义，国内外诸多学者在这方面做出了自己的尝试与贡献。其中不同类型的文物碎片由于其性质通常也会有不同的拼接方法。一种比较普遍的分类方式是按照文物碎片厚度不同分为非薄壁型碎片和薄壁型碎片，其中薄壁型碎片又可分为薄壁平面类碎片与薄壁旋转类碎片。非薄壁型碎片的空间特征更为突出，为了能够获取更多的空间特征，往往通过激光扫描采集点云作为数据，拼接时更依赖于断裂面的信息，是曲面匹配问题。薄壁平面类碎片则可以通过二维图片获取信息，更依赖于轮廓形状与表面特征，是曲线匹配问题。而薄壁旋转类碎片的匹配本质上也是曲线匹配，只是在平面类碎片的基础上引入了旋转轴/母线、曲面等要素，比起平面类有着更高的匹配自由度。
6、对于薄壁平面类碎片而言，早期的匹配通常依靠计算曲率与挠率等二维下的旋转不变量，通过串匹配搜索或动态规划等方法确定碎片邻接关系，这类方法往往需要较大的计算量。kong等人通过分别在粗粒度与细粒度两方面分别计算轮廓亲密度确定拼合关系最终实现拼合，进一步提高了计算速度。谭鑫刚等人通过提取角点并将角点转化为弦长序列，对两个弦长序列进行最长公共子串求解寻找共有曲线段完成匹配，但仅考虑了角点间弦长信息。廖海波等人在考虑角点间距离的基础上，引入了角点角度信息。周丰等人选择基于轮廓线生成相应的角序列，通过多尺度匹配减少匹配时间，有效解决了尖角问题。靳秋霞等人使用边界曲线的freeman链码上发生急剧变化的点作为拐角点，根据曲线长度和曲率等信息去除伪角点，对得到的特征点序列曲率归一进行粗匹配，对特征线段的距离归一进行精确匹配。
7、综上，目前已有的方法中虽取得了较好的结果，但依旧存在很多问题以及挑战。首先，薄壁文物碎片通常表面纹理颜色信息薄弱，需要充分利用边缘轮廓等信息才能达成较好效果；其次，文物碎片边缘会存在磨损缺失等现象，同时还会有噪声引起的量化误差，碎片间不是完全匹配。通常情况下匹配问题与拼接问题会分开考虑，这样不能充分利用匹配时计算的中间数据，在效率上有所欠缺。
技术实现思路
1、本发明的目的在于，提供一种基于轮廓提取与角点检测的二维碎片拼接方法，该方法将匹配问题与拼接问题统一考虑，充分利用匹配时计算的中间数据，以提高拼接的效率。
2、为了实现上述目的，本发明采用以下技术方案予以实现：
3、一种基于轮廓提取与角点检测的二维碎片拼接方法，具体包括以下步骤：
4、步骤1：对原始碎片图像进行滤波；
5、步骤2：提取碎片的外轮廓；
6、步骤3：对提取到的外轮廓进行角点检测，得到角点集合p；
7、步骤4：对不在外轮廓上的角点，通过将搜索路径的坐标偏移量预先设置到数组中的广度优先搜索重定位到外轮廓上，最终得到包含多条子轮廓线的线集；
8、步骤5：在步骤4得到的包含多条子轮廓线的线集中，对每条子轮廓线建立其局部坐标系，并提取建立局部坐标系时的旋转平移矩阵；
9、步骤6：对于步骤5中完成局部坐标系建立的子轮廓线，通过剪枝的方式剔除其中不可能匹配的子轮廓线对；
10、步骤7：对于步骤6剪枝后得到的子轮廓线对集，计算子轮廓线对的两子轮廓线之间的相似度；
11、步骤8：通过步骤7得到的子轮廓线间的相似度寻找匹配子轮廓线对，随后通过步骤5中得到的旋转平移矩阵，分别将匹配子轮廓线对中的子轮廓线所对应的步骤1中的两张原始图片在同一坐标系下进行变换，达成预拼接的效果。
12、进一步的，步骤1中，采用的滤波方法为双边滤波。
13、进一步的，步骤2中，通过canny边缘检测算法提取碎片外轮廓。
14、进一步的，步骤3中，使用shi-tomasi算法进行角点检测。
15、进一步的，步骤4包括如下子步骤：
16、步骤41，根据搜索范围预生成偏移量数组moffset[n]，数组moffset[n]中顺序保存了广度优先搜索的坐标偏移量；
17、步骤42，对不在轮廓线上的原角点坐标[x,y]遍历：
18、[x’,y’]＝[x,y]+moffset[i]，i∈(0,n)
19、当检测到[x’,y’]在外轮廓上时，退出遍历并记录[x’,y’]；
20、步骤43，更新[x,y]＝[x’,y’]，在重定位完成后，n个角点将轮廓线划分为包含n条子轮廓线的线集l。
21、进一步的，步骤5包括如下子步骤：
22、步骤51，定义角点pi为坐标原点，角点pi和pj所在直线为x轴，pi到pj方向为x轴正方向，过坐标原点pi作x轴垂线为y轴，向上为正方向，为该子轮廓线的局部坐标系；
23、步骤52，提取旋转平移子轮廓线使得该子轮廓线坐标符合局部坐标系要求所需的旋转平移矩阵mij：
24、
25、式中，(xi,yi)为角点pi在变换到坐标原点前的坐标，用作平移变换；θ为将角点pi平移变换至坐标原点后，将向量逆时针旋转至与x轴正方向重合的角度，用作旋转变换。
26、进一步的，步骤6包括如下子步骤：
27、步骤61，选择归属于不同碎片的子轮廓线进行两两组合作为子轮廓线对，得到子轮廓线对集；
28、步骤62，计算步骤61得到的子轮廓线对的角点间距离的百分比误差，用于后续进行剪枝操作：
29、
30、式中，lena、lenb分别代表子轮廓线a和子轮廓线b的角点间距离，为a、b两子轮廓线的角点间距离的百分比误差；
31、步骤63，对满足下式的剪枝条件的子轮廓线对进行剔除：
32、
33、式中，τ为设定的剪枝阈值，设为0.1。
34、进一步的，步骤7包括如下子步骤：
35、步骤71，将参与计算的子轮廓线按照在x轴上的投影进行等距离散，得到一系列离散点；i同时作为离散点的序列索引与x轴上的坐标值，当取值为i时，若两子轮廓线均有对应值时，使用离散点间的到x轴距离的差值作为x轴坐标为i时的差异值，若仅有一子轮廓线有对应值时，使用该离散点到x轴的距离作为差异值进行加权，公式如下：
36、
37、式中，表示匹配子轮廓线对中两子轮廓线间的差异度，minc与maxc分别为两子轮廓线的离散点在x轴坐标上可取到的最大值，其中minc为较小值而maxc为较大值；i取值在0～minc间两子轮廓线均有对应值，i取值在minc到maxc间仅有一子轮廓线有对应值；disx(i)表示x轴坐标为i时对应的离散点到x轴的距离，其下标表示为不同子轮廓线；
38、步骤72，逆向其中一条子轮廓再重复执行步骤7.1进行一次差异值计算，选取较小差异值，公式如下：
39、
40、式中，-b为将子轮廓线b沿x轴负方向平移lenb距离并逆时针旋转180°得到的曲线；
41、步骤73，采用下式计算步骤72得到匹配的两子轮廓线的相似度
42、
43、进一步的，步骤8中，计算公式如下：
44、a'＝ma*a
45、b'＝mb*b
46、式中，a和b分别代表了匹配子轮廓线对中两子轮廓线所对应的原始碎片图像，ma和mb代表匹配子轮廓线对在步骤5中计算得出的旋转平移矩阵。a’和b’为原始碎片图像a和b旋转平移后的图像，旋转平移后找到的匹配子轮廓线的划分角点会在各自局部坐标系x轴上，且在各自局部坐标系原点处的角点为对应的匹配角点，对原始图像在同一坐标系下进行旋转平移变换，得到预拼接结果。
47、本发明具有以下有益效果：
48、1、在碎片的匹配与拼接中使用碎片的单张图片信息，相较于多张图片或点云等其它方式更易于获取；
49、2、在碎片匹配阶段计算了标准化旋转矩阵，对寻找到的匹配对可以通过两碎片的旋转矩阵进行快速的粗精度拼接；
50、3、考虑到边缘会存在磨损等情况，通过相似度在子轮廓对中寻找更有可能互相匹配的碎片对。
51、4、利用角点分割子轮廓，并计算子轮廓对应旋转矩阵在匹配阶段寻找可能匹配对，并在拼接阶段利用计算好的旋转矩阵信息进行预拼接。
52、5、本发明综合考虑了匹配阶段与拼接阶段，在拼接阶段通过匹配阶段的矩阵信息能快速完成预拼接得到结果，拼接的效率高，在需要较快直接看到结果的场景下有一定优势，并且数据源仅需要大小可以不同的二维图片，数据获取较为简单。
1.一种基于轮廓提取与角点检测的二维碎片拼接方法，其特征在于，具体包括以下步骤：
2.如权利要求1所述的基于轮廓提取与角点检测的二维碎片拼接方法，其特征在于，步骤1中，采用的滤波方法为双边滤波。
3.如权利要求1所述的基于轮廓提取与角点检测的二维碎片拼接方法，其特征在于，步骤2中，通过canny边缘检测算法提取碎片外轮廓。
4.如权利要求1所述的基于轮廓提取与角点检测的二维碎片拼接方法，其特征在于，步骤3中，使用shi-tomasi算法进行角点检测。
5.如权利要求1所述的基于轮廓提取与角点检测的二维碎片拼接方法，其特征在于，步骤4包括如下子步骤：
6.如权利要求5所述的基于轮廓提取与角点检测的二维碎片拼接方法，其特征在于，步骤5包括如下子步骤：
7.如权利要求6所述的基于轮廓提取与角点检测的二维碎片拼接方法，其特征在于，步骤6包括如下子步骤：
8.如权利要求7所述的基于轮廓提取与角点检测的二维碎片拼接方法，其特征在于，步骤7包括如下子步骤：
9.如权利要求8所述的基于轮廓提取与角点检测的二维碎片拼接方法，其特征在于，步骤8中，计算公式如下：
