2014年基于结构特征的碎纸片的拼接复原问题.doc

2013高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛 赛区评阅编号（由赛区组委会评阅前进行编号）： 2013高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）：  基于结构特征的碎纸片的拼接复原问题 摘要 碎纸自动拼接技术是图像处理与模式识别领域中的一个典型的应用，该技术通过扫描和图像提取技术获取一组碎纸片的形状、纹理及内容等信息，然后利用计算机进行相应理解从而实现对这些碎纸片的全自动或半自动拼接还原。 　　针对问题一，考虑到纵切的碎纸片所含有的信息量较大，利用图像处理中的信号匹配方法，结合左右两个碎纸片的灰度像素矩阵的边缘特征，建立基于结构特征的灰度匹配模型，对英文字母制定了灰度相似的配准规则，使待拼接的碎纸片边缘的对应行像素之差的平方和最小；而结合中文字符的横笔结构特征，对中文字制定了“横笔”匹配相似度的配准规则，并给出了最终的碎纸拼接图和拼接次序，拼接的正确率是100%。 　　针对问题二，对于既纵切又横切的情形，每一个纸片的边缘所含的信息量相对较少，故对中、英文碎片的拼接复原需各自建模分析。首先利用“分而治之”的思想，将一个难以直接解决的大问题，分割成一些规模较小的相同问题。对于中文碎片拼接复原，根据中文的方块特点，给出了中文的文字结构特征向量及其边缘像素的特征向量。根据这些结构特征向量对所有的碎纸片进行粗分类，在此基础上设计了基于边缘特征的匹配规则集，对每一行从左到右在进行细匹配。利用等距序列图像的快速拼接技术拼出左边第一列，基于灰度匹配，将图像转化为二值图像并对每行进行最优匹配。先按照行配准，然后再进行列配准，最终匹配出误差最小的图像；对于英文碎片复原同样采取人工干预粗分类，粗匹配后，采用神经网络算法对碎片图像训练、学习构建BP网络对英文字母进行匹配识别，结合剪枝定界法实现英文碎片的拼接复原。发现每行匹配率为78.85%，整篇匹配率大约为68.73%。 　　针对问题三，由于碎片数据均为双面打印文件，文字特征相同，仅用问题二中的方法产生的误差太大，仍沿用粗分类特点通过神经网络拼接、灰度匹配修正、人工干预，结合等距序列拼接技术实现单面拼接，然后验证反面的正确性并修正。 关键词：图像拼接，灰度配准， 结构特征，配准规则，神经网络 一、问题重述 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。拼接复原工作若由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。现试图开发碎纸片的自动拼接技术，以提高拼接复原效率。我们需要建立数学模型解决以下问题： 　　1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。 　　2. 对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。 3. 现实情形中可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。 二、问题分析 碎纸自动拼接复原技术在司法鉴定，历史研究等领域都有着广泛的应用。近年来,随着德国斯塔西文件的恢复工程的公布,碎纸文件复原技术的研究引起了人们的广泛关注。碎纸自动拼接技术是模式识别领域中的一个很典型的应用。涉及数字图像处理，机器学习等多个学科，充分体现了当下多学科相互融合的学科特点，这也正说明了碎纸自动拼接本身具有一定的难度。 匹配技术是碎纸自动拼接技术的关键，它可以分为两个步骤：局部拼接和全局恢复。局部拼接是指碎片两两之间的拼接问题，全局拼接是关于一组碎片之间的匹配问题。局部匹配技术可以分为两类，一类比较具体，多对应图像低层像素或像素的集合，统称为图像匹配；另一类则比较抽象，主要与图像或目标的性质有关统称为广义匹配。图像匹配包括模板匹配、目标匹配和动态模式匹配。广义匹配包括关系匹配、线图同构和特征内