碎纸拼接_1210522_何厚华.doc

数据结构课程设计实习报告 题 目：碎纸片的拼接复原学 号：1210522姓 名：何厚华年 级：大二学 院：计算机与控制工程学院专 业：计算机科学与技术完成日期：2014年6月14日授课教师：辛运帏目录1. 题目.22. 问题重述.33. 问题分析.44. 模型假设.45. 算法实现.4 5.1问题1.4 5.1.1算法评价.5 5.1.1.1准确率.5 5.1.1.2平滑性.5 5.1.1.3 复杂度.6 5.2问题2.6 5.2.1算法评价.8 5.2.1.1准确率.8 5.2.1.2平滑性.8 5.2.1.3 复杂度.8 5.3问题3.86. 算法推广.8 1. 题目 碎纸片的拼接复原破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。针对上述3个问题，详细分析需求，给出各自的算法概述（不要求写程序代码）。【数据文件说明】(1) 每一附件为同一页纸的碎片数据。(2) 附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。(3) 附件3、附件4为纵横切碎片数据，每页纸被切为1119个碎片。(4) 附件5为纵横切碎片数据，每页纸被切为1119个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有21119个文件，例如，第一个碎片的两面分别对应文件000a、000b。2.问题重述 碎纸自动拼接复原技术是计算机视觉和模式识别领域内的问题.它在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统意义上的拼接复原工作需由人工完成，准确率较高，但效率非常低，特别是当碎片数量巨大时，人工拼接很难在短时间内完成任务.随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率.本文主要讨论：首先，对于给定的来自同一页单面印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法。其次，对于同样是单面印刷文件既纵切又横切的情形，在第一问的基础上设计出碎纸片拼接复原模型和算法。再者，联系现实中的情况，对还有可能出现双面打印文件的碎纸片进行拼接复原.在前两问的基础上，设计出相应的碎纸片拼接复原模型与算法。最后，给出评判拼接结果好坏的定量分析。在上述复原过程中，由于计算机的识别可能会出现偏差，并且这个偏差会对后面的结果产生非常大的影响，在拼接过程中可能需要进行必要的人工干预。3.问题分析以下分析是针对题目给出的三个问题的。破碎文件的复原，最直接及最精确的就是人工拼接，但是当碎片的数量巨大时，人工方式就显得效率低下，所以就考虑把破碎文件运用计算机技术来帮助人们进行破碎文件的复原，让计算机在这个过程中发挥主要作用，但是用计算机处理，又不是百分之一百完美，因此在适当的时候也需要进行人工干预.由于题目所给的纸片形状大小比较一致，差异仅仅在于纸片的内容也就是像素值上。所以传统的碎片拼接可以考虑纸片的几何特征，比如角点检测，计算面积等在这里不适用，这里只需要考虑这些碎纸片的各个像素即可，而一个碎纸片里面在拼接时起到关键性作用的则是这些碎纸片的边界点，因此可以把每一个碎纸片抽象成一个矩阵。事实上，由于碎纸片数量的有限性，因此，这些纸片之间的邻接关系有限，可以把这些可能性一一列举，然后用定量分析的方法依次得出每个结果对应的一个数值，然后在这些数值里面找到最优的一个即可。但是由于这种方法需要考虑所有的情况，而碎纸片的数目是上百计的（即使是最简单的第一个问题，仍然有种情况），所以这种方法必然是高时间-空间复杂度的算法， 拼接起来成本远高于人工拼接。因此需要考虑更优的算法。在纸片拼接开始前，需要进行一定的预处理，由于只有黑白两种颜色，而实际纸片像素的灰度值不可能只有0和255两种，因此需要先把图像二值化成0-1矩阵，处理方法如下：如果某像素值大于某个阈值（例如200），就把矩阵相应元素置成1，否则如果小于某个阈值（例如50）置成0，如果有介于两个阈值之间的像素点，则要进行人工干预，判断纸片是否已经损坏并作出相应处理。这就是预处理。经过预处理后，每个纸片都被数字化成一个只有0和1两种取值的二值矩阵。这个矩阵不妨叫做纸片的特征矩阵（由于后面要用到这个名词，所以用红色底纹标记，下同）。 纸片的拼接问题转化为特征矩阵的邻接问题。4.模型假设1、 假设碎纸机把一页印刷文字文件碎成形状规则，大小一样的碎片，看做形状、大小相同的长方形.2、 假设印刷文字的颜色都是黑色的，就是说只有黑白两种颜色，不存在第三种颜色，可以用一个单通道图像来表示。3、 在碎纸过程中，只考虑文字被切开，不考虑文字笔画的丢失、碎片添加的任何痕迹等.4、 假设文档碎片的文字的方向已经按照阅读标准确定，从左向左右，自上而下的确定，不考虑碎片图像的旋转问题.5、 图片在复原的过程中，图片的像素值不会随着拼接过程的进行而改变。5.算法实现5.1 问题1 针对问题一，作出两个特征矩阵和邻接性的定义： 其中表示同或运算，其运算规则如下：由定义可以知道表示最后一列和第一列相应相应位置相等元素的个数。越大，表明它们邻接的可能性越大。由于碎纸片数目比较少，并且纸片为纵切的，每列像素数目较多，因此采用启发式的搜索策略（也就是贪心策略）从左到右拼接就可以得到较好解决。假设这些纸片对应的特征矩阵集合为由于打印文档的页左侧存在相应的页边距，因此可以认为前10列全为0的特征矩阵就是最左边的纸片对应的特征矩阵并记为，并且把从特征矩阵集合去掉。如果求得，那么可以这么求： 在特征矩阵集合里面，寻找使得最小的和使得次小的，（如果，那么直接进行语义层面的人工干预）如果（其中是一个阈值，这个阈值可以根据拼接结果人工调整），那么选取作为，然后把从去掉。如果，那么可以由人工进行干预，根据语义或者碎片的词组在这两个碎片中选择最优的一个作为，然后把从去掉。这样下去，候选集合的元素越来越少，直到候选集合只剩下一个元素，那个元素就作为最右边的一个纸片。依次得到序列，碎纸片拼接至此完成。说明： 其中是一个阈值，这个阈值可以根据拼接结果人工调整，直到得到满意的结果。5.1.1算法评价 5.1.1.1准确率 根据算法，写出程序代码。随机选取一个足够大的数据集（比如1000页带有单面打印文字的纸），用程序模拟碎纸机对每张纸进行切割，然后对切割的碎纸片进行拼接，对比拼接得到的纸片与原纸片，计算准确率,对同样的样本，越大，算法准确率越高。5.1.1.2.平滑率平滑率的衡量不需要用到数据集。对一次拼接，平滑率这样定义：（其中表示特征矩阵的列数，表示纵切后的碎片总数），这样定义的能很好的反映拼接结果的平滑率。需要说明的是，越大，平滑率越好，正确的拼接不一定是。5.1.1.3算法复杂度分析 容易知道，算法复杂度为。5.2 问题2 针对问题二，可以用基于问题的方法。两个特征矩阵和列邻接性的定义跟问题1差不多： 越大，表明它们邻接的可能性越大。在此基础上，为了应对更复杂的情况，对特征矩阵的每一行定义特征函数定义两个特征矩阵的行相似度为其中表示特征矩阵的列数。可以看到，越小，两行的行相似度越高。下面介绍拼接算法：首先在这个集合里面考虑跟问题1一样，由于打印文档的页左侧存在相应的页边距，因此可以认为前10列全为0的特征矩阵就是某一行最左边的纸片，对应的特征矩阵并记为，然后用问题1的贪心策略，尝试依次寻找某一碎片右侧的图片。依次向右寻找与其最有可能有邻接关系的最优特征矩阵。如果求得，那么可以这么求： 如果，则认为此处得到的最优解是完全可靠的，不需要进行下一步匹配，而直接寻找最有可能与这个最优解有邻接关系的特征矩阵。这时选取作为，然后把从去掉。 如果，从所有碎纸片的集合里面选出小于或者等于15个（如果所剩小于15个的话，全部作为最优解候选）最优解作为候选。可以从这些候选结果中筛选出行相似度与目标碎片行相似度最小的一个结果以及次小的结果如果远小于，则这个结果认为是最佳匹配结果。作为，然后把从去掉。否则可以由人工进行干预，根据语义或者碎片的词组在这两个碎片中选择其中最优的一个作为，然后把从去掉。这样下去，候选集合的元素越来越少，直到。这时候得到了某一行的碎片然后选取，用同样的方法，得到另外一行的碎片重复上述步骤，依次得到到这里就实现了所有碎纸片的横向拼接，接着再次利用问题1类似的方法（之所以这样说是因为问题1是横向拼接，而这里是纵向拼接，大体方法类似）完成这些已经横向拼接好的碎片的纵向拼接。碎纸片拼接至此完成。假设最终拼出来的结果排列成这样一个矩阵：5.2.1算法评价 5.2.1.1准确率 准确率定义跟问题1一样：对同样的样本，越大，算法准确率越高。5.2.1.2.平滑率平滑率的衡量不需要用到数据集。对一次拼接，平滑率这样定义：（其中表示特征矩阵的列数，19-1表示纵切后的碎片总数是18），这样定义的能很好的反映拼接结果的平滑率。需要说明的是，越大，平滑率越好，正确的拼接不一定是。5.2.1.3算法复杂度分析 容易知道，算法复杂度为并没有质的变化依然为。5.3 问题3问题3是考虑到双面的印刷文字纸片的拼接，数据仅仅给出了某一面的纸片以及其对面的纸片，但是并不知道这两个面到底是正面还是反面。比如000a.bmp跟00