2013年全国大学生数学建模b题碎纸片的拼接复原.doc

2013高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛 赛区评阅编号（由赛区组委会评阅前进行编号）： 2013高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 碎纸片的拼接复原 摘要 本文从开发碎纸片的自动拼接技术，以提高拼接复原效率的角度出发，研究了不同切割方式、不同语言文字和单双面打印下的破碎文件拼接还原方面的问题。 与同类研究相比，本文旨在突出研讨自动拼接技术在生活中应用问题的重要性。 针对问题一，附件1和附件2中的碎纸片都只是纵向切割的情况，运用切割边缘灰度检测模型和图论模型，对附件1和附件2中的碎纸片进行了拼接还原，得到了附件1和附件2中破碎文件复原后的排列顺序如下所示： 附件1中碎纸片文件复原顺序表（表1） 附件2中碎纸片文件复原顺序表（表2） 针对问题二，附件3和附件4中的碎纸片是横向、纵向都切割，且附件3和附件4中碎纸片上的文字是不同语言文字的情况，运用层次聚类方法、灰度检测模型、图论模型和递归收缩算法，并且加入了人工干预的影响，对附件3和附件4中的破碎文件先进行局部还原，且进行人工干预，得到了附件3中破碎文件复原后的排列顺序表（表4）和附件4中破碎文件复原后的排列顺序表（表7）。 针对问题三，附件5中的碎纸片是横向、纵向都切，且是双面打印的英文文件，拼接复原难度大大增加，所以，将在问题一、问题二的数学模型基础上，增加识别英文字母的模型，对附件5中的破碎文件进行拼接复原。 关键词: 自动拼接 边缘灰度检测 图论模型 层次聚类 递归收缩算法 一 问题重述 破碎文件的拼接在司法物证复原、历史文献修复获取等领域都有重要的应用。传统上，复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸的自动拼接技术，以提高拼接效率。对于给定的来自同一页的片（仅纵切），建立碎纸拼接算法，并针对附件1给出的数据进行复原对于碎纸机纵切横切的情形，模型和算法，并针对附件给出的数据进行复原。从现实出发，模型与算法 K 常数，0K碎纸片总数 碎纸片P的灰度矩阵 碎纸片p左侧第一列单个像素序列 碎纸片p左侧第一列单个像素序列 T 碎纸片两两拼接的匹配值 碎纸片P与碎纸片的最大匹配值 所有碎纸片拼接起来时的最大匹配值 X 中文碎纸片上边界所截汉字高度 Y 中文碎纸片中部所截汉字高度 Z 中文碎纸片下边界所截汉字高度 C 同行截取的碎纸片集合 注：未说明符号在文中用到时注明 四 问题一的解答 由于附件1件中所给的图片均是纵向切割的，所以每张图片纵向的两条边，是判断相连图片的重要信息载体，我们运用边缘灰度检测模型和图论模型对问题一进行求解。 4.1 (单面、纵切)碎纸片纵向边缘灰度检测[1]的模型 对于给定的来自同一页的片（仅纵切），: 由于要去比较碎纸片的纵向边界，就将矩阵中的第一列（左边界单个像素灰度序列值）和最后一列（右边界单个像素灰度序列值）取出分别存为矩阵和： 要判断任意两张碎纸片（和）是否存在相连的关系，即可转变为判断两张碎纸片按第一张碎纸片（）左边匹配第二张碎纸片（）右边、第一张碎纸片右边（）匹配第二张碎纸片左边（）的方法，求出边界的匹配值T1和T2，比较T1和T2的大小，将最大的一个值确定为这两张碎纸片的最大匹配值。将所有碎纸片按两两匹配的关系进行匹配，使每张碎纸片都与其他碎纸片之间均取得最大匹配值。 4.2 (单面、纵切)碎纸拼接） 根据上图，建立如下表格，其中表格行列相交处表示它们之间的匹配最大值。 　 A B C D E A 　0 　30 95　 5　 5　 B 30　 0　 　73 3　 95　 C 95　 73　 　0 　1 2　 D 5　 　3 1　 0　 85　 E 5　 95　 　2 85　 0　 运用图论模型的知识和最优原则，可得将碎纸片（A、B、C、D、E）不同方式排序时总的匹配值，然后把不同方式下取得总的匹配值中最大的排序方式（顺序）选取出来，即为最优拼接还原顺序。 （可得顺序：A-B-C-E-D） 4.3 对附件1、附件2中的碎纸片的拼接还原 1）对附件1中的碎纸片的拼接还原 运用4.1和4.2建立的模型，通过Matlab编程实现，可以求得附件1中19张碎纸片两两拼接复原的匹配值，