碎纸片的拼接复原数学建模论文.doc

碎纸片的拼接复原摘要破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用传统上，拼接复原工作由人工完成，虽准确率高，但效率很低特别是当碎片数量巨大，人工拼接难以完成任务因此随着计算机信息技术的发展，开发一个碎纸片的自动拼接技术，并建立简便的拼接复原模型，提高拼接复原效率，具有重要的实现意义文章通过对所给的附件图片数据进行分析研究，在综合考虑了碎片边缘的尖点特征、尖角特征、面积特征等几何特征下，我们将图片读入电脑，并进行二值化转换，考虑边界值的匹配，建立了图片边界匹配模型依据模型，只要边界能匹配上就可以拼接，并依次解决了如下问题对于问题一，由于给定图片来自同一页印刷文字文件仅纵切破碎纸片，针对附件1、附件2给出的碎片数据，建立了碎纸片拼接复原的边界匹配模型根据模型，我们首先对附件1、附件2中的图片用Matlab软件进行二值转化，得到一个储存图片的二值灰度矩阵，并利用边界相关性比较法判断矩阵中两边界变量是否能匹配得上，如果匹配得上就拼接在一起，按此算法，附件1、附件2中的碎纸片就能拼接成功，具体的算法结果见附录中的附件1、附件2对于问题二，由于碎纸机既有纵切又有横切的情形，算法的设计上要相对复杂一些，我们在前面模型的基础上进行了修改和补充，对图片的上下左右的边界都进行了边界提取。

首先，我们选将图片作二值转换，分别用矩阵进行保存，然后任迁一个，对其余的进行全程扫描，按照问题一中的边界匹配模型，逐一对其边界进行扫描匹配，其间，有些矩阵的边界数据可能一样（如空白时），我们便跳出模型，进行适当的人工干预，干预完成，再进入模型进行迭代，按此方法便可拼接成功，具体的算法结果见附录中的附件3对于问题三，根据现实问题中的双面打印文件的碎纸片拼接复原问题，由于多了双面的问题，在算法的设计上，我们考虑了正反两的边界匹配，在原有模型的基础上，将问题一和问题二的模型相结合，建立一个新的双面碎纸片拼接模型首先，我们随机选取一张图片，以这张图片为依据，先拼接成其所在的横条或者竖条，再以拼成的横条或者竖条像问题一中模型一样，以整条文字的信息进行拼接，直至整条文件拼接完成，然后再拓展到其它条，最后完成整个图片的拼接在此过程中要排除边界相似度很高的情况，因此，类似于问题2模型，在模型运行过程中，我们要进行适当的人工干预，具体模型算法及结果见附件5破碎文件的拼接复原模型是一个具有重要现实意义的问题，我们对问题进行初步的分析，并建立一个初步的模型，由于时间与知识能力方面的问题，模型还比较粗糙，适用性还不是很广，比如随意形状纸片的拼接我还没有考虑，在后面的不断学习过程中，我们可加强模型的完善与改进，使之具有更好的适用性和可移植性。

关键词：Matlab 自动拼接技术 模式匹配 边界提取 一、问题重述在拼接图片时，需要将所有的图片按照文字的结构以及表述的内容要流畅为依据，所以我们在寻找图片边界闭合的条件就是能拼接在一起的图片，要求其边界信息的相似度很高甚至吻合在解决规则完整清晰的破碎文件的时候，我们主要的任务就是在成功读取图片的情况下只需要解决图片边界信息的相似度比较，然后进行匹配拼接碎片对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原附件1、附件2为纵切碎片数据，每页纸被切为19条如果复原过程需要人工干预，请写出干预方式及干预的时间节点复原结果以图片形式及表格形式表达，表格形式：将碎片序号按复原后顺序填入1×19的表格；对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原附件3、附件4为纵横切碎片数据，每页纸被切为11×19个碎片如果复原过程需要人工干预，请写出干预方式及干预的时间节点复原结果以图片形式及表格形式表达，表格形式：将碎片序号按复原后顺序填入11×19的表格。

可能有双面打印文件的碎纸片拼接复原问题需要解决附件5给出的是一页英文印刷文字双面打印文件的碎片数据附件5为纵横切碎片数据，每页纸被切为11×19个碎片，每个碎片有正反两面该附件中每一碎片对应两个文件，共有2×11×19个文件请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，复原结果以图片形式及表格形式表达，表格形式：将碎片序号按复原后顺序填入两个11×19的表格二、问题分析这是一个对文字图片进行边缘提取和数值匹配组合的问题，匹配方案要达到以下要求：（1）当对附件1和附件2的匹配时，要求整条碎纸条的左右两边要匹配得上来；（2）当对附件3和附件4的匹配时，除了要考虑左右边界，还要考虑上下边界要求先做出最左边碎纸片，然后像处理附件1和附件2一样，按照整条来快速往右提取剩下的图片；（3）当对附件5做匹配的时候，实现的方式就是在问题二的基础之上要求到前后两页要满足匹配的条件三、符号说明符号符号说明，，，图片序数相关系数图片灰度分布函数图片边缘的梯度值梯度的方向相关系数最大值S图片边缘数值的集合sS集合中的数值目标函数值约束条件四、模型的假设 1.附件所给的碎纸来自原来完整的文件，不缺少，不增多。

2.碎纸图片可以二值化，可以直接提取边界3.每一个附件里面的碎纸图片都是大小一样的规则四边形，图片的内容清晰可见，不影响人工视觉，必要的时候可以进行人工手动五、模型的建立与求解5.1 问题一的模型建立与求解关于问题一，对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），我们首先假设附件1和附件2中的每张碎纸片图片都是规格大小相同四边形，切口光滑平整，表面整洁碎纸片的拼接复原就是把来自同一页的碎纸片按照一定的方法，使其拼接还原成原来的形状我们的做法是：第一，用matlab软件中的imread函数读取附件1或附件2中的碎纸片图片文件，其中每个图片文件都是以一个1980行72列的矩阵的形式来存放图片的灰度值；第二，提取每个图片左边界和右边界的灰度值，保存在同一个矩阵里，形成一个1980行38列的矩阵；第三，从所有图片里找出左边界为空白的那张碎纸片图片，把它定义为纸张的开头；第四，由第一张碎纸片的右边界的灰度值开始，利用相关系数函数corroef分别与余下的所有碎纸片的左边界的灰度值进行运算，相关值最大的，说明两张碎纸片互相吻合，可以进行拼接，两张碎纸片拼接后融为一体，再从这张大的碎纸片的右边界的灰度值开始，分别与剩下的碎纸片的左边界的灰度值进行关联度运算，得出可以拼接的碎纸片，依此类推，最终完成所有碎纸片的拼接工作，达到还原的目的。

具体流程图如图1所示，附件1的碎纸片拼接顺序如图2，附件2的碎纸片拼接顺序如图3，编程代码和复原图片见附录开始对图片的读取提取图片的左右边界灰度值，存放在矩阵里利用相关系数corroef函数对碎纸片进行关联度运算，得出匹配顺序提取左边界灰度值为空的碎纸片作为纸张的开头检查，如个别错误，手动结束流程图 图1序号1234567复原后顺序008014012015003010002序号891011121314复原后顺序016001004005009013018序号1516171819　　复原后顺序011007017000006　　附件1拼接顺序数据表图2序号1234567复原后顺序003006002007015018011序号891011121314复原后顺序000005001009013010008序号1516171819　　复原后顺序012014017016004　　附件2拼接顺序数据表图3 5.2 问题二的模型建立与求解 问题二中对于碎纸机既纵切又横切的情形，因为此时，图片的拼接不仅仅是左右两边界，还要考虑图片的上下边界，所以，问题二是对问题一的加深和修补对于这一问题，我们首先对图片的前期工作如读入和提取如前面模型一，接下来的匹配工作，我们首先做的就是先把图片左边空白的用边缘检测提取出来，然后就是上下匹配，完成一小片整条的拼接图，接下来就是按照问题一以整条为单位进行整条整条的边界匹配。

最初使用的配准方法是基于图像的像素灰度信息，直接利用两幅图像的灰度信息，建立两幅图像之间的相似性度量，然后采用某种搜索方法，求取使相似性度量最大变换模型提出的基于灰度配准方法包括归一化互相关配准方法、基于傅立叶变换的相位配准方法、基于统计矩的配准方法、基于直方图的配准方法等基于灰度的配准方法具有精度高、概念清晰等特点开始对图片的读取边界提取左边界信息为空的图片以成功匹配得的整条边的右边界为依据匹配剩下图片的左边界信息以上下边信息为依据匹配组合成最左边整条检查，如个别错误，手动结束　　　流程图 图4边缘检测技术是所有基于边界分割的图像分析方法的第一步，图像的边缘是图像最基本也是最重要的特征之一，图像的大部分信息都存在于图像的边缘中目前边缘检测方法，常用的有 Robert 算子、Sobel 算子、prewitt 算子、Gauss-Laplace 算子等在图像配准中对边缘检测算子的性能一般要求：能正确检测出有效的边缘；边缘定位精确；受噪声影响小首先检测出图像局部特性的不连续性，再将它们连成边界，这些边界把图像分成不同的区域，检测出边缘的图像就可以进行特征提取和形状分析我们运用梯度检测法：设是图片灰度分布函数；是图片边缘的梯度值；是梯度的方向。

则有： （1） （n=1,2,...） （2）式（1）与式（2）可以得到图片在（x,y）点处的梯度大小和梯度方向将式（1）改写为： 当时，图片为左边碎图片边缘特征点的检测与配准，详细研究了基于边缘轮廓提取特征点和利用提取的特征点进行配准特征点提取是基于边缘特征点图像配准方法的关键，相似性度量相似性度量是指用哪种方法来确定待配准特征之间的相似性它是以某种距离函数或代价函数的形式出现的相似性度量与特征空间是紧密相连的，因为相似性度量是利用特征提取的信息，特征提取的好坏将影响相似性度量相似性度量决定了图像配准中参与配准的因素，有利于进一步提高算法性能，常用的相似性度量有相关函数、明考夫斯基距离等相似性度量和特征空间的选择，可以有效地降低计算量和噪声、遮挡等因素带来的影响，提高配准的精度；相关关系是一种非确定性的关系，相关系数是研究变量之间线性相关程度的量由于研究对象的不同，相关系数有如下几种定义方式简单相关系数：又叫相关系数或线性相关系数，一般用字母P 表示，是用来度量变量间的线性关系的量复相关系数：又叫多重相关系数。

复相关是指因变量与多个自变量之间的相关关系例如，某种商品的季节性需求量与其价格水平、职工收入水平等现象之间呈现复相关关系典型相关系数：是先对原来各组变量进行主成分分析，得到新的线性关系的综合指标，再通过综合指标之间的线性相关系数来研究。