教高社杯全国大学生数学建模竞赛 碎纸片的拼接复原本科论文.doc

高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛 赛区评阅编号（由赛区组委会评阅前进行编号）： 高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 纸片的拼接复原 摘要 碎纸自动拼接复原技术计算机视觉和模式识别领域内的问题1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 编号 0 0 8 0 1 4 0 1 2 0 1 5 0 0 3 0 1 0 0 0 2 0 1 6 0 0 1 0 0 4 0 0 5 0 0 9 0 1 3 0 1 8 0 1 6 0 0 1 0 0 4 0 0 5 0 0 9 对于问题2中既纵切又横切的碎纸片，在问题一的基础上，充分考虑横向匹配和纵向匹配的要求，运用Matlab程序筛选最左列碎片成分，经过适当的人工干预根据文字行特征将所剩碎片进行行分类，大大提高拼接效率，得到意想的效果.例如文字文件的拼接结果如下表所示： 顺序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 编号 0 0 3 0 0 6 0 0 2 0 0 7 0 1 5 0 1 8 0 1 1 0 0 0 0 0 5 0 0 1 0 0 9 0 1 3 0 1 0 0 0 8 0 1 2 0 1 4 0 1 7 0 1 6 0 0 4 对于问题，建立筛选附件5碎片图的优化模型，通过Matlab编程，使用附件给的418张碎纸片图，将最终复原图划分为11个碎片横条区域，降低了拼接复原难度以及所需时间.最终复原结果见附录.最后，分析了所建立模型的优缺点以及推广，评价了文字碎纸片的拼接和复原实际情况. 碎纸自动拼接复原技术是计算机视觉和模式识别领域内的问题.它在司法物证复原、历史文献修复获取等领域都有重要的应用.传统上复原工作需由人工完成，准确率较高，但效率低特别是当碎片数量巨大，人工拼接很难在短时间内完成任务.随着计算机技术的发展，人们试图开发碎纸的自动拼接技术，以提高拼接效率.对于给定的来自同一页的片（仅纵切），建立碎纸拼接算法，附件1数据纵切横切的情形，模型和算法，对附件给出的数据进行复原.模型与算法的像素矩阵，筛选出每个像素矩阵的第一列像素矩阵值，然后运用Excel软件统计各列像素值等于255的个数，可以粗略的认为所含255个数最多的列所对应的碎片则是拼接顺序中的左边第一条（如果有必要进行人工干预，但是本文第一问没有进行人工干预）.接下来从左边开始选取第二条碎片，关于第二条待匹配的碎片，用先确定的第一条像素矩阵的最后一列，对其进行数值求和，然后将剩下的18个像素矩阵中的第一列和最后一列矩阵进行分别求和.将首先确定的最左边第一条矩阵中的最后一列矩阵与求出的18个像素矩阵中的第一列矩阵分别进行做差，然后将差值取绝对值，这样就可以得出，如果差值越小，其重叠的相似度也应该相对越高.这样可筛选得出相似度较高的碎片，即与第一个碎片相匹配，该碎片位于拼接顺序的第二条，确定第二条后，再用第二条的最右边矩阵并以此类推，逐一从左到右查询碎片，直到碎纸片的复原结果. 针对问题，碎片既横切又纵切，那么在拼接时就有方面的考虑，既要满足横向匹配，又要满足纵向匹配.在问题解决中可以分为两步进行，首先考虑横向拼接，根据碎片像素特征和行距特征将其分类，再问题的方法将各类碎片进行匹配，即可得到11个碎片横条.接着考虑纵向拼接，使用Matlab程序对得到的新的横条碎片进行像素分析，比较像素矩阵中第一行数据中255的个数，个数最多的碎片即是原文件的第一行，依次类推，同样的方法即可知道具体的排列顺序，从而碎纸片复原的结果.碎片既横切又纵切，那么在拼接时有方面的考虑，既要满足横向匹配，又要满足纵向匹配.接着考虑纵向拼接，用Matlab程序对得到的新的横条碎片进行像素分析， 三 模型假设准备与符号说明 模型的假设 假设碎纸机把一页印刷文字文件碎成形状规则，大小一样的碎片，看做形状、大小相同的长方形. 在碎纸过程中，只考虑文字被切开，不考虑文字笔画的丢失、碎片添加的任何痕迹等. 假设文档碎片的文字的方向已经确定（按照阅读标准确定，从左向左右，自上而下），不考虑碎片图像的旋转问题. 图片在复原的过程中，不考虑图片像素的改变，只考虑碎片相对应的固