2013高教社杯全国大学生数学建模竞赛
承 诺 书
我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： J3705 所属学校（请填写完整的全名）： 西京学院 参赛队员 (打印并签名) ：1. 郑 浩 2. 蒲 骏 3. 章锦炜 指导教师或指导教师组负责人 (打印并签名)： 刘苍毅
（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容
请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）
日期： 2013 年 9 月 13 日 赛区评阅编号（由赛区组委会评阅前进行编号）：
2013高教社杯全国大学生数学建模竞赛
编 号 专 用 页
评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
碎纸片的拼接复原模型
摘要
碎纸片的拼接复原问题，是随着计算机的发展和碎纸机的应用在图像识别和处理方面的一个新课题。破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域具有广阔应用，用计算机代替人工拼接是提高拼接效率的最有效途径。
针对问题一，我们运用特征匹配的排序思想编程。分析碎片页面的左页边距特征，首先确定序首；根据不同碎片边缘之间像素的差异，记录并分析碎片的边缘数值特征，用禁忌搜素算法编程，从而实现了无人工干预复原碎片。
问题二分两个部分，对于中文碎片，用Matlab分析其页面汉字的位图和边缘特征，用页边距把碎片分作11行，再根据汉字中心确定每一行所包含碎片，继而根据文字边缘特征信息配合人工干预复原碎片。对于英文碎片，由于英文字母的四线三格的特性，我们根据页边距将碎片分划为11行，再利用碎片中英文的像素分布求出四线三格的位置，继而根据边缘特征信息配合手工干预完成拼接。但由于英文碎片变小后边缘特征匹配的算法存在一定局限性，所以人工干预次数达到百次。
问题三是对双面碎片拼接还原。由于大量的隐形的四线三格信息很难精确的统计，所以我们在完成了基本的页边距匹配、位图信息匹配、边缘特征匹配后仍存在大量未定型数据，由于碎片包含有效信息不足，双面碎片牵扯过多，导致后面的人工干预量较大。
关键词：特征匹配，Matlab，禁忌搜素算法，碎片还原，位图特征，边缘特征
1
一、问题重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：
1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。
二、模型假设
1、假设碎纸机破碎纸片时纸片没有任何损耗。
2、假设所有碎纸片的原文档均有页边距且页边距大于字间距。 3、假设所有碎纸片的源文档页面没有污点。
4、假设属于同一张文档的所有碎纸片上显示内容的字号和字体是相同的。
三、符号说明 A L 碎纸片图像在Matlab中对应的矩阵 矩阵左侧空白列的个数 汉字的高度 有效汉字的中心 英文字母的中心 汉字的实际高度像素值 H Pc Pe Max(Height)、Min(Height) 2
四、问题一 模型的建立与求解
4.1 模型分析
常规碎纸片拼接复原方法一般利用碎片边缘的尖点特征、尖角特征、面积特征等集合特征，搜索与之匹配的相邻碎纸片并拼接[1]，而这种方法并不适用于本题中所有碎纸片形状完全一样的情况。
由于本问题中碎纸片均来自同一页印刷文字文件，碎纸片之间没有任何损耗，且仅考虑纵切的情况。根据观察，我们假设原文档存在页边距，且页边距大于字间距，所以我们首先遍历每一张碎纸片，选取左侧空白列最大的碎纸片作为最左一列；其次，根据每一张碎纸片的最右侧列与其他碎纸片进行相似匹配，选取相似度最高的一组，即两张碎纸片连接处同一行像素差值最小；最后按照相似度高低从左到右依次进行匹配。
4.2 模型建立
1、用Matlab读取碎片图像，每个碎片图像生成一个i行j列的矩阵A，矩阵每一个元素对应图像的RGB值，取值范围0~255。
2、按列遍历每一张碎片图像的矩阵，记录矩阵左侧空白列的个数为Ln，选取列数最多的碎片图像max为复原图象的最左列。左页边距示意如图1： （Ln）图1 左页边距示意图
3