杨蒙

问题一中，本文用傅里叶变换来分析碎片图像之间的相关性，首先选取某图像作为模板图像，并在其一侧上选取字母图像作为临时图像，将临时图像与所有碎片图像进行傅里叶变换，并得到极限相关图;然后通过极限相关图得到其间的相关程度，将相关程度最接近的图像作为模板图像对应边缘的拼接图像;如果存在多个图像与模板图像相关程度接近，则重新选择模板图像边缘的字母，直到发现唯一的拼接图像。

问题二中，首先采用基于拉普拉斯算子的Canny法提取出各个碎片文件的边缘特征，然后通过检测随机二个碎片文件接缝处像素的灰度值是否是连续变化来确定这二个碎片文件是否可以拼接在一起。将碎片文件拼接的问题转换为检测碎片文件接缝处灰度值的连续性，当所像素间距足够小时，文字的曲线近似看做直线;最后将问题变成检验接缝处像素点灰度值是否在同一条直线上，并用Hough变换实现该过程。

问题三中，在对双面碎片文件进行拼接时，首先选取二张碎片文件图像作为原图像和目标图像，分别用SIFT来描述这二个图像，提取他们的特征点，将二者的特征点进行匹配，同时完成匹配点的矫正，最后通过图像的匹配点完成图像的融合，实现图像拼接。

一、問题重述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：

1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。

3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。

二、问题分析

问题一中，在对英文碎片文件进行拼接时，本文用傅里叶变换来分析碎片图像之间的相干性，具体操作为选取某个碎片文件作为模板图像，选取该图像一侧上的字母图像作为临时图像，将该字母图像与所有字母图像进行傅里叶变换，并得到极限相关图，通过极限相关图可以得到所有图像与临时图像的相关程度，将相关程度与模板图像相关程度最接近的图像作为模板图像对应边缘的拼接图像;如果存在多个图像与模板图像相关程度接近，则重新选择模板图像边缘的字母，直到发现唯一的拼接图像为止。同理在对中文碎片文件进行拼接时采用相同的方法，由于汉字偏旁部首较多，因此在拼接时有别于英文碎片文件拼接的是在选取临时图像时，需要尽量选取能够根据偏旁部首可以推断出来的汉字作为临时图像，而且该汉字所在的碎片中应该最好只显示一半，这样在进行傅里叶变换的图像匹配时，该汉字能够均衡的分在二个碎片文件中，进而能够较容易地找出可以拼接的二个碎片文件。

问题二中，首先提取出各个碎片文件的边缘特征，即边缘处的汉字形状，如果二个碎片文件是可以拼接在一起的，那么它们边缘特征图像的接缝处的灰度值应该是连续变化的，由此，可以通过检测二个碎片文件接缝处像素的灰度值是否是连续变化来确定这二个碎片文件是否可以拼接在一起。因此，碎片文件拼接的问题就变为如何检测二个碎片文件接缝处灰度值是否连续的问题，无论是汉字还是字母，都可以看做是曲线，当所分析的距离足够小时，可以将曲线近似看做直线，这样问题就变成了检验接缝处像素点灰度值是否在同一条直线上。该过程可以用Hough变换实现。

问题三中，利用SIFT提取碎片文件局部特征，建立尺度空间，寻找候选点、精确确定关键点，剔除不稳定点、确定关键点的方向、提取特征描述符，在对双面碎片文件进行拼接时，首先选取一张碎片文件图像作为原图像，选取另一张碎片文件图像作为目标图像，然和分别用SIFT来描述这二个图像，提取他们的特征点，接着将二者的特征点进行匹配，同时完成匹配点的矫正，最后通过图像的匹配点完成图像的融合，即图像的拼接。

三、模型优缺点分析

在模型一中，将碎片文件图像进行傅里叶图像变换，经过变换后的图像更为方便、容易地处理和操作。通过傅里叶卷积图像、极限相关图像可以得到临时图像与碎片文件的相关程度，选取相关程度最接近的二个碎片文件进行拼接。模型存在的不足是有时会存在多张碎片文件图像的相关程度均接近，此时需要重新选取临时图像，重新进行操作。因此增加了程序的复杂度。

在模型二中，利用Canny方法对图片进行基于拉普拉斯算子的边缘特征分析，旨在找出各个碎片文件图像边缘部分的文字形状，然后利用Hough变换检验二个碎片文件接缝处像素点的灰度值是否连续来判断这二个图片是否可以拼接，在此过程中将短距离内文字图像的曲线近似为直线，这样讲拼接问题转化为寻找二个碎片文件接缝处像素点灰度值是否在通一条直线上，模型在不失正确解决问题的情况下，更加容易理解。模型存在的缺点即是需要将所有碎片文件进行拼接搜索，这使得程序的执行效率有所降低。

在模型三中，首先选取一张碎片文件图像作为原图像，选取另一张碎片文件图像作为目标图像，然和分别用SIFT来描述这二个图像，提取他们的特征点，接着将二者的特征点进行匹配，同时完成匹配点的矫正，最后通过图像的匹配点完成图像的融合，即图像的拼接。模型存在的缺点是在进行匹配时采用穷举匹配法，需要将所有碎片文件与原图像进行匹配，在算法上削弱了程序的执行效率。

参考文献：

[1] 罗智中，基于线段扫描的碎纸片边界检测算法研究，仪器仪表学报，第32卷 第2期，2011年2月

[2] 赵书兰，《MATLAB数字图像处理与分析实例教程》，化学工业出版社，2009年6月