年全国大学生数学建模竞赛—B题—碎纸片的拼接复原.doc

2 0 1 3 高 教 社 杯 全 国 大 学 生 数 学 建 模 竞 赛 承 诺 书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛

规则》（以下简称为“竞赛章程和参赛规则” ，可从全国大学生数学建模竞赛网站下载） 。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上 咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其

他公开的资料 （包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违 反竞赛章程和参赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示 （包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等） 。 我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话） ：

所属学校（请填写完整的全名） ： 西华大学

参赛队员 ( 打印并签名 ) ：1. 杨尚安

2. 刘 洋

3. 叶 军

指导教师或指导教师组负责人 ( 打印并签名 ) ： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 2013 年 09 月 15 日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2013 高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 碎纸片的拼接复原 摘要 本文通过分析题中相关要求及条件， 建立数学模型解决了各种规则碎纸片的拼接复原问题。 针对问题一， 首先将题中所给图片导入 matlab 软件，利用 imread 函数得到每张图片的文字灰度像素矩阵，再取出所有矩阵左、右列，建立像素绝对差拟配模型，得到 拟配程度最高的两幅图片，进行拼接，出现不合理拼接情况则进行人工干预，最后重复上述过程，完成全部拼接并导出图像。 针对问题二，首先将全部碎片导入 matlab 软件，经过处理得到每张碎片中符号距离碎片上下端的像素位，再根据分类聚类思想，利用 excel 表格处理，将所有具有“相同”像素位的图片分为一组，得到 11 个分组，然后在每一个分组中建立左右连接点数 目最匹配模型，再配合人工干预，将所有碎片拼接为一行图像，最后将这 11 行图像利 用问题一中模型拼接为最终图像并打印结果。 针对问题三，首先建立一种基于 K-Means局部最优性的高效聚类模型，然后根据模 型利用 matlab ，将所给图片全部导入分类，分好类并人工调整补充后再利用 matlab 在 每一组分类中利用问题二模型在人工干预情况下得出原始图像并打印结果。 关键词：像素绝对差拟配模型 左右连接点数目最匹配模型 人工干预一、问题重述 破碎文件的拼接在司法物证复原、 历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切） ，建立碎纸片拼接复原模型和算法，并针对附件 1、附件 2 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结 果以图片形式及表格形式表达（见【结果表达格式说明】 ）。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。 附件 5 给出的是一页英文印刷文字双面打印文件的 碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件 5 的碎片数据给出拼接复原结果，结果表达要求同上。 二、模型假设 1、假设全部碎纸片边缘光滑 2、假设字符色调一致 3、假设字符间距相同，没有特殊情况 4、假设除字符外，页面没有其他地方具有任何色彩 5、假设英文字符书写标准，大小写字号均相同 三、符号说明 ai 表示灰色像素矩阵 n 表示灰色像素矩阵的列数 m 表示灰色像素矩阵的行数 i 表示第几个碎片 a im n 表示某个像素点

b 表示某灰度像素点为黑色还是白色 right (i ) 表示灰色像素矩阵最右边列 left (k) 表示灰色像素矩阵最左边列 w 表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值的和 四、模型建立与求解 4.1 问题一 4.1.1 问题分析 整体来看，本问题要求利用数学模型，改原有手动拼接技术为自动或半自动拼接技术，完成题中所给的相应碎纸片的拼接复原工作。

具体操作，考虑所给碎纸片内容仅有汉字或英文，而没有颜色、大小、字形之分。因此，只能利用碎纸片中相应的文字特征进行操作，考虑碎纸片扫描进入在计算机后是 以图片的形式存在，而图片又是以像素的情况组成。所以，首先可将图片导入 matlab 中，以其像素为基点，得到每个图片的像素矩阵， 每一像素矩阵即可表示该图片的特征。 为了利用图片像素矩阵完成图片的拼接，考虑问题一只是将原图分为了 19 列，每一列具有 1980 像素，首先可根据左端全为空白，找出原图最左一列碎片，然后利用拼接好的图片最右列像素点去匹配未拼接图片的最左列像素点， 使得拼接最为吻合的即为需要 拼接的图片，然后拼接，再重复上述过程，直到拼接完成。具体操作流程如下：

碎 纸 导入 Matla

像素矩阵 取出最 左 与最 像素绝对差拟配模型 求解程序 不

吻 判断吻合程 合

吻合

拼接 导 出 结 图 1 问题一解答流程图 4.1.2 数据处理 将图片导入 matlab 中，然后编写程序（具体代码见附录 1），可得每个碎纸片灰度像素矩阵（碎片 000 局部像素点如下）。 图 2 碎片 000 局部灰度像素点列 4.1.3 像素绝对差拟配模型建立 令碎片导入 matlab 编程计算所得的灰色像素矩阵为： 由于碎片像素为 72*1980，因此矩阵 ai 也是 72*1980 的，矩阵每一列数据即为碎片相应

列像素值，其中每个像素点 a im n 表示此处为黑色或白色，用 b 表示某灰度像素点为黑色还是白色，即： 令 right (i ) 表示灰色像素矩阵最右边列，那么 令 left (k ) 表示灰色像素矩阵最左边列，则 令 w 表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对 值的和。那么有 根据上述模型即可确定某一碎片灰度像素矩阵最右边列与其余未拼接碎片最左边 列的绝对差值，下面讨论因差值不同而产生的匹配问题。 1、最左列的确定：当出现某一碎片灰度像素矩阵最左列均为 255 时，那么说明该碎片

为原始图像的最左列。 2、假设出现 w1 w 2 w3 wk 情况，那么首先将 wk 对应的碎片与该基准碎片进行 拼接，若拼接不合适，这时就需要人工干预，换 wk 1

对应的碎片与基准碎片进行拼接。

情况如下： 这是不确定的，而进行人工干预选择 wk 1

对应的碎片后，将会出现下面情况：

这样就能正确的完成两个碎片的拼接。 3、假设出现 w1 w2 w3 wk 情况，这与上述情况相同。因此，人工干预方式及时 间选择也相同。 4.1.4 像素绝对差拟配模型求解 对于附件一中碎片复原，根据上述模型，利用 matlab 软件，求解可得 008 碎片最 255 左端矩阵列与 006 碎片最右端矩阵列均为： ，因此，可知 008 碎片为复原图最左 255 一个碎片， 006 碎片为复原图最右端碎片。其余求得所有最小的距离 w 的值，根据 w 的 值，可将碎片进行复原。复原结果如下表，复原图像见附录 2。 008 014 012 015 003 010 002 016 001 004 005 009 013 018 011 007 017 000 006 表 1 问题一中文复原表格序列 对于附录二英文复原，与上求解过程雷同，利用 matlab 可得复原结果如下表，复原图像见附录 3。 003 006 002 007 015 018 011 000 005 001 009 013 010 008 012 014 017 016 004

表 2 问题一英文复原表格序列 4.1.5 问题一综合分析 综上所述，对于问题一的求解过程，未使用人工干预。本文除使用对问题所给的碎片进行复原外，同时对具有相同属性的其他图形碎片也进行了复原，效果良好，模型稳定，可推广到所有只进行竖切的文档恢复。 4.2 问题二——中文碎片复原 4.2.1 问题分析 综合分析。由于考虑问题二在问题一的基础上将碎片分的更加的细小，那么碎片的灰色像素矩阵数据在原有的基础上将会变得少很多，考虑使用问题一方法及模型，那么