2013年数学建模B题概述.ppt

2013年B题 碎纸片的拼接复原 相关系数（Pearson correlation） * * 一、阅读题目 弄清已有信息；需解决的问题. 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。 附件1 中文文件，碎纸机纵向等距切成了19条 附件2 英文文件，碎纸机纵向等距切成了19条 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 附件3：纵切横切产生的209张中文碎纸片 附件4：纵切横切产生的209张英文碎纸片 3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 附件5：双面打印的英文文件，纵切横切产生了209块碎纸片 二、寻找解题思路 （一）针对附件1中由碎纸机纵向等距切成的19条中文碎纸片的情形，建立拼接复原模型和算法。 用Matlab软件中的imread函数把碎片转化为元素从0到255的数值矩阵. 0到255代表的是黑白图像中点的颜色深度， 其中纯白为255，纯黑为0. 把数值矩阵二值化即变成由元素0和1构成的数值矩阵 19条碎纸片——19个 1.碎纸片的数值化处理 2. 定义两个矩阵相似，然后进行聚类分析 根据首段特征人工挑选出第一块碎纸片，其二值化矩阵为 ,记为T1； T1矩阵的最后一列与剩余18个二值化矩阵的第一列进行 相似性分析，取相似性最强的作为第二张碎纸片 注：若满足条件的矩阵有多个，则通过文字的特征人工寻找出最佳匹配矩阵作为Tn 以此类推完成19条碎纸片的拼接复原 附件2 碎纸机纵向等距切成了19条的英文碎纸片 欧式平方距离： 相似性的度量 ——两个向量相似性的度量 附件3：纵切横切产生的209张中文碎纸片 （二）问题二的解题思路 1.利用matlab软件把图片变成二值化矩阵 2. 定义两个矩阵相似，然后进行聚类分析 根据首段特征人工确定文件拼接复原后的第一块碎片，即为 。 依次类推拼接复原第一行的碎纸片 （1）拼接第1行碎纸片的的流程图 （2）最后第一行（第11行）的拼接复原流程图 最后一行的第一张碎纸片，记为 以此类推，得到最后第一行的碎纸片拼接复原 注：若满足条件的矩阵有多个，则通过文字的特征人工寻找出最佳匹配矩阵。 （3）第二行—倒数第二行的拼接复原流程图 得到第二行的第一块碎纸片，记为 得到第二行的第二块碎纸片，记为 得到第二行的第三块碎纸片，记为 得到第二行的第四块碎纸片，记为 以此类推，得到第二行的碎纸片拼接复原 第三行、第四行……倒数第二行同理拼接复原 附件5：双面打印的英文文件，纵切横切产生了209块碎纸片 （三）问题三的解题思路 1.利用matlab软件把图片变成二值化矩阵 2. 定义两个矩阵相似，然后进行聚类分析 (1)拼接第一行的流程图 以此类推，完成第一行的拼接复原 （2）拼接第二行—倒数第二行的流程图 以此类推，完成中间行的拼接复原 （3）拼接最后一行（第11行）流程图 ） （1）通过人工干预均能准确找到拼接复原后的 第一张碎纸片； （2）一文件切碎后的碎纸片都是全等的矩形 模型检验： 自行构造碎片，检验与评价所提出的拼接复原模型的复原效果。 假设 *