关于碎纸片自动拼接的数学模型_数学建模竞赛优秀论文

碎纸片的拼接复原模型摘要本文主要问题是将附件中的所给的碎纸片按照一定的方法拼接复原。

通过一定的方法把碎纸片进行分组：题目给了四种类型的碎片，有长条形的，即全是竖切的中英文碎片，也有横竖都切的中文碎片，有横竖都切的单面英文碎片和横竖都切的双面英文碎片。

对于中英文长碎纸片分组拼接的问题，我们直接通过观察法，按照文字和字母的结构很容易完成了拼接。

对与中文横竖碎纸片拼接的问题，我们利用Matlab 编程并加入人工干预。

本文的主要拼接过程都是通过Matlab 软件实现的，通过Matlab 软件读取图片的信息，根据图像灰度的原理，图片包含着灰度信息，碎纸片左右的文字在纵切面上的灰度应该是完全对应的。

但把所有图片的灰度拿出来匹配是很不现实的。

于是我们想到可以通过灰度赋值，由于碎片中间文字的信息对于拼接是没有太大用途的，我们更关心左右切面的文字信息，即灰度信息。

因此将纵切面上的灰度矩阵的第一列和最后一列单独抽出，形成矩阵，然后设定一定的算法，通过Matlab 进行编程，相邻的两张碎纸片左右边缘信息匹配度非常高，其差值接近于0。

,,|p(i)p(j)|m n m n ρ=-编写的程序完全可以对所分的各组碎纸片进行拼接，而且效果非常明显。

对于英文碎纸片问题，我们采用了同样方法的分组，只是按照上下切掉的英文部分所占四线格的比例进行分组，此分组方法分组快且相对准确。

我们第二问中所编程序对英文碎纸片的拼接也完全适用。

对于双面英文的情况，也是按照上述思想方法进行分组，只是工作量稍微大些。

分组后我们也通过所编程序实现了双面英文的拼接复原。

关键词：碎纸片；拼接；图像灰度；灰度矩阵；分组1、问题重述论题给出了5个附件——反应了几种不同纸片破碎的情况，要求我们构建相应的碎纸片复原模型，以解决实际生活中出现的需要我们进行碎纸片复原的问题。

首先进行简单情况的碎纸片复原，即附件1中和附件2中的仅纵切的中英文19个碎纸片。

构建一个可以操作的拼接模型，将附件中的纵切纸片拼接。

基于灰度像素理论的碎纸片拼接方法摘要常规的二维碎片拼接技术一直受到科研领域重视，它在司法鉴定、文物修复、图像处理等领域有着广泛的应用。

本文研究的是二维碎片拼接技术中最典型的文档类碎纸片拼接问题。

基于文档纸片色彩明确、方向一致、无重叠等特点，利用灰度理论对问题作出解决。

通过图形扫描得到图像，然后通过二值化，Sobel[]3梯度算进行预处理，并运用皮尔逊相关性度量及方差分析算法进行匹配，以实现对纸片进行还原。

本文通过MATLAB程序模型，以及图片像素灰度理论实现文档碎片的重新拼接。

对于问题1，应用图像处理技术中的灰度理论建立了灰度模型I。

在对得到灰度模型进行Sobel梯度边缘化预处理的方法进行模型改进，建立了边缘灰度模型II。

然后借助于皮尔逊相关系数算法和MATLAB软件，对附件中所提供的碎片进行排列拼接。

对于问题2，采用化归思想，将二维问题渐变为一维问题。

首先归纳碎片特征运用MATLAB软件对碎片进行同行分类，得到11行19列的元素；采用方差分析算法和人工干预对各行中元素进行排列，得到11条横切的图形；采用方差分析算法和人工干预对其进行排列，得以还原。

本文的亮点在于对各行中元素采用方差分析算法进行左侧到右侧匹配后，同时增加了右侧到左侧的匹配检验，大大减少了人工干预的工作。

关键字：灰度理论；皮尔逊相关系数算法；Sobel梯度边缘化；方差分析算法；人工干预一、问题的重述问题一、对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

复原结果以图片形式及表格形式表达。

问题二、对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题.我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性.如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理.我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）.我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（即电子文件名）：B0813所属学校（请填写完整的全名）：广西师范大学参赛队员 (打印并签名) ：1.杨凯2.周志恒3.陈锦丽指导教师或指导教师组负责人 (打印并签名)：日期2013年9月16日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国评阅编号（由全国组委会评阅前进行编号）：纸片的拼接复原摘要碎纸自动拼接复原技术现今可以归结到计算机视觉和模式识别领域内的问题，它在司法物证复原、历史文献修复等重要领域都起着重要的作用.本文主要分析了文字的拼接技术，通过研究碎纸片内的像素矩阵和文字行特征特点，提出了基于文字图形的半自动拼接算法.对于问题1中的这种单面的仅纵向切碎的文字文件，通过Matlab 程序分析附件中每个碎片的像素矩阵，确定拼接的第一个碎片（自左向右拼接），再根据两列像素矩阵的像素绝对差的和来确定相邻碎片的编号，从而得到完整的拼接方案.例如文字文件的拼接结果如下表所示：对于问题2中既纵切又横切的碎纸片，在问题一的基础上，充分考虑横向匹配和纵向匹配的要求，运用Matlab程序筛选最左列碎片成分，经过适当的人工干预根据文字行特征将所剩碎片进行行分类，大大提高拼接效率，得到意想的效果.例如文字文件的拼接结果如下表所示：对于问题3，在前两问的基础上，建立筛选附件5碎片图的优化模型，通过Matlab编程，使用附件给的418张碎纸片图，将最终复原图划分为11个碎片横条区域，降低了拼接复原难度以及所需时间.最终复原结果见附录.最后，分析了所建立模型的优缺点以及推广，评价了文字碎纸片的拼接和复原实际情况.关键词文字图形碎片半自动拼接像素灰度 MATLAB程序一问题的重述碎纸自动拼接复原技术是计算机视觉和模式识别领域内的问题.它在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统意义上的拼接复原工作需由人工完成，准确率较高，但效率非常低，特别是当碎片数量巨大时，人工拼接很难在短时间内完成任务.随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率.本文主要讨论：首先，对于给定的来自同一页单面印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，同时对题目中的附件1和附件2给出的中、英文各一页文件的碎片数据进行拼接复原.其次，对于同样是单面印刷文件既纵切又横切的情形，在第一问的基础上设计出碎纸片拼接复原模型和算法，对附件3和附件4给出的中、英文各一页文件的碎片数据进行拼接复原.最后，联系现实中的情况，对还有可能出现双面打印文件的碎纸片进行拼接复原.在前两问的基础上，设计出相应的碎纸片拼接复原模型与算法，并附件5中双面打印文件的碎片数据给出拼接复原结果.在上述复原过程中，由于计算机的识别可能会出现偏差，那么就需要在拼接过程中进行必要的人工干预，在适当的时候我们会用干预的方式给出复原过程.并最终以图片形式及表格形式完成给出复原结果.具体结果在附件中给出.二问题的分析破碎文件的复原，最直接及最精确的就是人工拼接，但是当碎片的数量巨大时，人工方式就显得效率低下，所以就考虑把破碎文件运用计算机技术来帮助人们进行破碎文件的复原，让计算机在这个过程中发挥主要作用，但是用计算机处理，又不是百分之一百完美，因此在适当的时候也需要进行人工干预.本文运用碎纸片的自动拼接技术，对每个附件给出的碎片文字材料进行分析，尽可能减少人工干预，本文给出的图像数据均为形状、大小一样的规则长四边形，由于形状的一致性，所以在拼接时如果只考虑利用碎片的边界特征，直接拼接，显然效果不理想.考虑到使用计算机的拼接过程应该与人工拼接过程是相类似的，即拼接时不但考虑碎片边缘是否匹配，还要判断碎片内的字迹断线和文字内容是否匹配.然而根据现在已有的技术，实现计算机智能识字是几乎不可能的.但是我们可以获取图片所提供的像素信息，将其转化为矩阵，根据图像的像素矩阵值进行碎片拼接，用计算机去运行处理数据，可以想象其拼接效率无疑比单纯利用边界特征的方法好很多.以下是对各问题的详细分析：针对问题1，对附件1和附件2提供的数据，每页纸被切为19条碎片，对于这种单面的仅纵向切碎的文字文件，我们仅考虑碎片左右两侧的拼接.首先，在转换中发现，像素图片矩阵的值是介于0到255之间的一个像素矩阵，随着像素矩阵值的增加，我们发现随着像素矩阵数值的增大，所代表的区域越来越浅，最后255这个数值，代表了白色区域.其次，对于问题1中的附件1和附件2图片，由于仅纵向切碎的文字文件，仅考虑碎片左右两侧的拼接.需运用Matlab程序分别对附件1和附件2中的19个碎片计算其像素矩阵，将每个附件中19条图像转换的像素矩阵，筛选出每个像素矩阵的第一列像素矩阵成19个198072值，然后运用Excel软件统计各列像素值等于255的个数，可以粗略的认为所含255个数最多的列所对应的碎片则是拼接顺序中的左边第一条（如果有必要进行人工干预，但是本文第一问没有进行人工干预）.接下来从左边开始选取第二条碎片，关于第二条待匹配的碎片，用先确定的第一条像素矩阵的最后一列，对其进行数值求和，然后将剩下的18个像素矩阵中的第一列和最后一列矩阵进行分别求和.将首先确定的最左边第一条矩阵中的最后一列矩阵与求出的18个像素矩阵中的第一列矩阵分别进行做差，然后将差值取绝对值，这样就可以得出，如果差值越小，其重叠的相似度也应该相对越高.这样可筛选得出相似度较高的碎片，即与第一个碎片相匹配，该碎片位于拼接顺序的第二条，确定第二条后，再用第二条的最右边矩阵并以此类推，逐一从左到右查询碎片，直到碎纸片的复原结果.针对问题2，在问题1的基础上，继续对所给的附件3和附件4进行分析.针对附件3和附件4的特点，附件3和附件4给出了碎片既横切又纵切的中英文图像，那么在拼接时就有两方面的考虑，既要满足横向匹配，又要满足纵向匹配.那么我们就考虑在问题解决中可以分为两步进行，首先考虑横向拼接，一旦横向拼接完成了，纵向拼接自然相对就好解决了.根据碎片像素矩阵特征和行距特征将其分类，再结合问题1的方法将各类碎片进行匹配，即可得到11个碎片横条.接着考虑纵向拼接，使用Matlab程序对得到的新的横条碎片进行像素分析，比较像素矩阵中第一行数据中255的个数，个数最多的碎片即是原文件的第一行，依次类推，同样的方法即可知道具体的排列顺序，从而得到碎纸片复原的结果.针对问题3，在问题1和问题2的基础上，继续对所给的附件5进行分析.实际生活中存在很多双面打印的文件，这些双面文件的碎纸片混合在了一起，当对其进行拼接复原时，首先要判断同一面的文字碎片，然后再进行拼接.附件5给出了碎片既横切又纵切的英文文字图像，那么在拼接时依旧有两方面的考虑，既要满足横向匹配，又要满足纵向匹配.首先考虑横向拼接，转换得到180x72的像素矩阵，这些是介于0到255之间的一个像素矩阵，随着图片的增加，相应的增多转换得到的像素矩阵，在问题2的基础上继续进行检验所给的碎纸片图，运用Matlab读取了418张碎片图后，将每张碎片转换得的像素矩阵的第一列以及最后一列各自取出，通过程序进行验证，可以算出匹配度高的相邻碎片，此时进行一次人工干预，拼接出位于同一行的碎片横条；接着考虑纵向拼接，运用Matlab程序对得到的新的横条碎片进行像素分析的提取，配准各个横条的像素矩阵的第一行与最后一行的相关度，综合分析碎纸片上英文之间的行距，进而确定拼接的碎片横条位于哪一行，得到最终的复原结果.综上所述，以上三个问题的解决流程可用下面的流程图表示：图2 问题解决流程图三模型假设准备与符号说明3.1模型的假设1、假设碎纸机把一页印刷文字文件碎成形状规则，大小一样的碎片，看做形状、大小相同的长方形.2、在碎纸过程中，只考虑文字被切开，不考虑文字笔画的丢失、碎片添加的任何痕迹等.3、假设文档碎片的文字的方向已经确定（按照阅读标准确定，从左向左右，自上而下），不考虑碎片图像的旋转问题.4、图片在复原的过程中，不考虑图片像素的改变，只考虑碎片相对应的固定像素值的匹配问题.3.2 模型准备不规则几何文档碎纸片计算机拼接的方法一般利用碎片边缘的尖角特征、尖点特征、面积特征等一些几何特征，搜索与之匹配的相邻碎纸片进行拼接，这种基于边界的几何特征的拼接方法并不适用于边缘的形状相似的碎纸片.对于这类边缘相似的碎纸片的拼接问题，理想的计算机拼接的过程与人工拼接的过程类似，即拼接时不仅要考虑拼接碎纸片的边缘是否匹配，还要判断碎纸片内的文字字迹断线或文字内容是否匹配，但是由于理论和技术的限制，让计算机具备类似于人的的那种识别碎纸片边缘字迹断线、以及理解碎纸片内文字图像的含义的智能几乎是不太可能的.但是利用现在已有的技术，完全可以获取到碎纸片文字所在行的几何特征信息，如文字行的行高及间距等信息.如果利用这些信息进行碎纸片拼接，其拼接的效率就比单纯利用边界的几何特征方法更好.根据本文题设要求，经考虑分析，本文采取转换矩阵数组元素拼接的技术对破碎的文字文档进行拼接复原.由于计算机数字分析图像能力方面的存在一定的缺陷，让计算机对碎纸片进行完全意义上的自动化拼接页几乎是不太可能，为保证其拼接的准确性，需要在拼接的过程中加入一定的人工干扰过程.一般来说，先利用计算机搜索出于目标碎纸片相匹配的未拼接碎纸片，并根据匹配的程度按顺序到得待选的碎纸片，然后人为地进一步分析结果进行舍弃或拼接待选碎纸片[3].一页文字文件的碎片拼接复原相当于全景图的生成技术，而相邻图像的配准及拼接是该技术的关键.图像的拼技术一般分为基于图像特征的方法和基于图像灰度的方法.特征提取的方法通常涉及大量的几何与图像形态学的计算，计算量大，没有一般的模型可遵循，但需要针对不同的应用场景来选择各自适合的特征，所提取的图像特征包括更高层的语义信息，基于特征的方法具有尺度不变性和放射不变形.然而基于图像灰度的拼接方法简单简单易行，并且其数字统计模型以及收敛速度、定位精度等均具有定量的分析和研究结果，此类方法得到了广泛的应用.本文中的文字图像中文字区域的文字结构相对单一，并可能出现相同或相似的字符，因此文字容易出现匹配出现误差.对于文字左右拼接的情况，可以对图片中划分的每行文字进行分析处理，通过提取文字图片的边缘像素矩阵，得到文字出现在图片边缘的那一行高，进一步对一行行的文字拼接复原，这也有利于获取更精确的配准结果.基于文字的图像灰度的方法不需要提取文字图像的相应的特征，只以两幅图像相连接部分对应的像素灰度的相似性准则来寻找图像的匹配位置.待匹配的图像，首先求出图像中最左边一列的像素矩阵值之和，和最右边一列像素矩阵之和。

碎纸片的拼接复原【摘要】：碎纸片拼接技术是数字图像处理领域的一个重要研究方向，把计算机视觉和程序识别应用于碎纸片的复原，在考古、司法、古生物学等方面具有广泛的应用，具有重要的现实意义。

本文主要结合各种实际应用背景，针对碎纸机绞碎的碎纸片，基于计算机辅助对碎纸片进行自动拼接复原研究。

针对问题1，依据图像预处理理论，通过matlab程序处理图像，将图像转化成适合于计算机处理的数字图像，进行灰度分析，提取灰度矩阵。

对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵A1，提取每个灰度矩阵的最后一列，生成新矩阵B1。

建立碎纸片匹配模型: dai,bj=t=0m-1bti-atj2 ，其中i，j=0,⋯n-1。

p=0≤i≤n-10≤j≤m-1mind(ai,bj)将矩阵A1中的任一列与矩阵B1中的每一列带入模型，所得p值对应的i ,j 值，即为所拼接的碎片序列号。

将程序进行循环操作，得到最终的碎片自动拼接结果。

针对问题2，首先将图像信息进行灰度分析，提取灰度矩阵。

基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列和最后一列，分别生成新矩阵A2、B2；提取所有灰度矩阵的第一行和最后一行，分别作为新生成的矩阵C2、D2。

由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。

在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型：dai,bj=t=0m-1btj-ati2 ，其中i，j=0,⋯n-1。

dci,dj=s=0n-1dsj-asi2 ，其中i，j=0,⋯m-1。

p=0≤i≤n-10≤j≤m-1mind(ai,bj)，q=0≤i≤n-10≤j≤m-1mind(ci,dj)将矩阵A2中的任一列分别与矩阵B2中每一列代入模型，所得p值对应的i ,j 值即为横排序；将矩阵C2中的任一行分别于矩阵D2中的任一行代入模型，所得q值对应的i ,j值即为列排序。

基于最小二乘法的碎纸片拼接复原数学模型摘要首先对图片进行灰度化处理,然后转化为0-1二值矩阵，利用矩阵行（列）偏差函数，建立了基于最小二乘法的碎纸片拼接数学模型，并利用模型对图片进行拼接复原。

针对问题一，当两个数字矩阵列向量的偏差函数最小时，对应两张图片可以左右拼接。

经计算，得到附件1的拼接结果为：08,14,12,15,03,10,02,16,01,04,05,09,13,18,11,07,17,00,06。

附件2的拼接结果为:03,06,02,07,15,18,11,00,05,01,09,13,10,08,12,14,17,16,04。

针对问题二，首先根据每张纸片内容的不同特性，对图片进行聚类分析，将209张图片分为11类；对于每一类图片，按照问题一的模型与算法，即列偏差函数最小则进行左右拼接,对于没有拼接到组合里的碎纸片进行人工干预，我们得到了11组碎纸片拼接而成的图片；对于拼接好的11张图片，按照问题一的模型与算法，即行偏差函数最小则进行上下拼接,对于没有拼接到组合里的碎纸片进行人工干预。

我们最终经计算，附件3的拼接结果见表9，附件4的拼接结果见表10。

针对问题三，由于图片区分正反两面，在问题二的基础上，增加图片从下到上的裁截距信息，然后进行两次聚类，从而将所有图片进行分类，利用计算机自动拼接与人工干预相结合，对所有图片进行拼接复原。

经计算，附件5的拼接结果见表14和表15该模型的优点是将图片分为具体的几类，大大的减少了工作量，缺点是针对英文文章的误差比较大。

关键字：灰度处理，图像二值化，最小二乘法，聚类分析，碎纸片拼接一、问题重述碎纸片的拼接复原技术在司法鉴定、历史文献修复与研究、军事情报获取以及故障分析等领域都有着广泛的应用。

近年来，随着德国“斯塔西”文件的恢复工程的公布，碎纸文件复原技术的研究引起了人们的广泛关注。

传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。

特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。

承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。

如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：重庆XX大学参赛队员(打印并签名) ：1. 祝XX2. 冯XX3. 周XX指导教师或指导教师组负责人(打印并签名)：张XX（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。

以上内容请仔细核对，提交后将不再允许做任何修改。

如填写错误，论文可能被取消评奖资格。

）日期： 20XX 年 X 月 XX 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原摘要图像碎片自动拼接复原是需要借助计算机把大量碎片重新拼接复原成初始图像的完整模型，这一研究在考古、刑侦犯罪、古生物学、医学图像分析、遥感图像处理以及壁画保存复原等方面具有广泛、实际的应用[1].本文主要解决碎纸机破碎文档的自动拼接复原问题.我们利用图像数字化技术，借助Matlab软件将图像转化为矩阵.通过建立数学模型，运用矩阵论、聚类分析方法、自定义相似度方法、遗传算法、字符分割和字符识别等方法，对数据进行处理，实现对图像碎片自动拼接，从而将所给碎片拼接复原为完整图像.问题一，我们首先把碎片图形进行二值化处理，根据所给纵切黑白碎片边缘的像素关系(相邻两张碎片，一张碎片矩阵右边的像素与另一张碎片左边的像素相同 )，我们采和自定义相似度算法，利用附件一和附件二求出碎片间的相似度，然后根据所需要满足的条件即相似度最大原则，建立了纵切碎片拼接模型一及其算法，运用Matlab编程实现该模型，并得到碎片复原结果（见表一表二）.问题二，要实现快速准确的拼接复原纵横切碎片，在问题一的思路基础上，我们采用了模糊C的均值聚类方法，先对附件三所有碎片进行初步的分类，然后在自定义相似度算法上增加了约束条件，以此来排除有若干碎片在匹配时相似度相同的情形，建立了改进的中文纵横切碎片拼接模型二，同样利用Matlab软件求得碎片的复原结果（见表三）.对于英文纵横切碎片的拼接问题，我们采用了字符切割和字符识别思想，即在碎片的二值化矩阵中选取适当大小的行与列，对碎片边缘的英文字母进行切割，与其他图片匹配合并，提取切割字母的特征（统计特征或结构特征），再利用字符识别的方法从得到的特征库中找到与待识别字符相似度高的字符，将两张碎片拼接在一起，先一行一行地进行拼接，再利用模型二横切碎片方法，利用Matlab软件求得碎片的复原结果（见表四）.问题三，在处理双面打印纵横切碎片时，经分析发现两面图片最大的区别在于光滑度的不同，纸张的正面比反面要光滑，因此在模型二的基础上还需增加一步筛选工作，就是采用傅里叶变换将图像的二值矩阵从“空域”变为“频域”，再根据不同页面的频率范围，设定一段频率值，借助计算机将双面打印的碎片进行分类，分离出在同一页面的碎片.分离成功后再采用模型二对于英文碎片的拼接方法将碎片进行复原即可，通过这种方法求得碎片的复原结果.关键词：碎片拼接均值聚类方法相似度模型傅里叶变换一、问题重述背景：破碎文件的拼接和复原对于司法物证复原、历史文献再现和军事情报获取等方面都有极其重要的作用.于是碎纸片的拼接复原技术便成为图像处理与模式识别领域中的一个崭新典型的应用.图像配准是图像拼接复原的基础，而且图像配准算法的计算量一般非常大，因此图像拼接复原技术的发展很大程度上取决于图像配准技术的创新.本文将通过图像提取技术获取一组碎纸片的形状、颜色、文字等信息，然后利用计算机进行相应的处理从而实现对这些碎纸片的自动拼接复原.重述：该题研究的是如何对碎纸片进行拼接复原.传统上，拼接复原工作需由人工完成，准确率较高，但是效率低.随着计算机技术的发展，当碎纸片数量巨大的时候，人们试图开发碎纸片的自动拼接技术，以提高拼接复原的效率.问题1 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、2给出的中、英文各一页文件的碎片数据进行拼接复原。

关于碎纸片的自动拼接复原的数学模型问题摘要本文根据碎纸片内的文字特征、图片像素特征特点提出了基于文字特征的文档碎纸片自动拼接复原模型。

根据碎纸拼接模型提出了基于MATLAB[1]语言为核心的自动拼接算法，并用该算法的程序对碎纸机碎纸的实际例子进行了拼接实验。

对这类边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否匹配。

然而由于理论和技术的限制，让计算机具备类似人类那种识别碎片边缘的字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。

但是利用现有的计算机技术，完全可以获取碎片文字所在行的几何特征信息，比如文字行的行高、文字行的间距等信息。

拼接碎片时如利用这些信息进行拼接，其拼接效率无疑比单纯手工拼接要高。

针对问题一，由于碎纸片数量比较少且只有纵向切割，采用比较简单的二值模型进行碎纸配对。

由于图像都具有三颜色RGB，扫描之后的碎纸片需要对其进行灰度处理得到一张灰度值图像，若定义原点之后，每一个像素点都具有X、Y坐标值，碎纸片的灰度值可构成一个二维矩阵。

二维矩阵的每一个元素都代表着碎纸片的特征值，根据图片每一个灰度值的大小即可判断出碎纸图片边界特性。

对于一个选定的纸片，将每一个待拼接碎纸片的二维矩阵的最左一列与其二维矩阵的最右一列进行差值比较，再求把所有的差值求和，生成一个相应的矩阵。

将该矩阵的最小值来作为相似度矩阵的判断条件，以此便可求出该图片是否能够成功拼接。

最后利用加权平均的融合方法进行图像无缝平滑，得到无缝拼接[2]图像。

针对问题二：根据附件3和附件4给出的碎片资料可以看出，碎片除了有纵向切割之外还有横向切割，这给单一的拼接算法带来了一定的困难。

本文根据图片的质量与清晰度可以将问题简化，将附录所给出的碎纸片用简单的算法进行分组归类，使得拼接问题变得单一化，先使用第一问的模型进行纵向拼接成11行之后，再以第一问的模型进行横向拼接。

大学生数学建模竞赛优秀论文关于碎纸片自动拼接的数学模型摘要本文针对生活中破碎文件的拼接难度大，效率低等现象，从题目所给的情形出发，利用计算机软件把碎纸片图像转化为数字图像，综合运用matlab 软件中的数字图像处理方法，建立了以图与图之间的相似程度为基准的数学模型。

这个模型的评价标准很简单，就是相似度函数的值。

通过比较图像与图像之间的相似度函数的值的大小，就可以得出碎纸片的具体拼接序列。

对于问题（1），首先，用matlab 软件的imread 函数对图像的进行读取，得到数据矩阵为),(y x F i 。

其次，根据模型的假设（1），找到最右端的碎纸片，并记为),(1y x F 。

然后，以数据矩阵),(y x F i 为基础，引入相似度函数)(b sim ，并求 出相似度函数值。

最后，用matlab 工具箱中的sort 函数把所得到的相似度函数值进行排序，所得到的相似度函数值最小的图像即为与最右端的碎纸片匹配的图像。

如此重复18次，即可得附件1的中文图像的排列序号，结果如表1所示。

同理可得附件2的英文图像排列序号，结果如表2所示。

复原结果图片见论文附件的图1和图2。

对于问题（2），同样先找到最右端的11张图像和最上方的19张图像，根据图像的页边距特性确定原图像右上角的第1张图像。

利用问题（1）的算法可得最右端的11张图像和最上方的19张图像的排列序号。

然后，在问题（1）的算法的基础上，利用图像中的文字的固定间距去改进算法，缩小搜索范围，并在拼接完一行后显示一次结果，由于近似距离计算公式与人主观视觉差异，所以需要人机交互调整结果。

如此重复18次，即可得附件3的中文图像的排列序号，结果如表3所示。

同理可得附件4的英文图像排列序号，结果如表3所示。

对于问题（3），与问题（2）相似，只是碎纸片由单面变为双面。

因此在匹配图像时，引入两重相似度函数)(Q sim ，以确保正反两面能同时匹配。

同时每匹配5张图像显示一次结果，以增加人工干预次数。

数学论文基于图像处理的碎纸片拼接数学模型分析1.问题背景目前碎纸的拼接工作大部分是靠人工的方式完成，但是当碎纸片的数量巨大的时候，要人工拼接完成就很困难了。

国内对此技术的研究主要是集中于文物碎片的自动修复、虚拟考古、故障分析以及计算机辅助设计、医学分析等领域，除此之外，破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域也有只重要的应用。

常规的碎纸片拼接方法一般是基于碎纸片的边缘的形状特征比如尖点、尖角、面积等几何特征，再进行搜索与之相匹配的纸片从而完成拼接。

但是这种基于纸片边缘几何特征的拼接方法，当存在许多边缘几何特征相似的纸片的情况下，这种拼接方法就不适用了，因此，本文重在建立一种基于纸片中文字特征的模型来完成碎纸片的拼接。

2.问题分析碎纸片自动拼接技术是图象处理与模式识别领域中的一个较新但是很典型的应用，它是通过计算机扫描和图像提取技术获取一组碎纸片的形状、颜色、文字特征等信息，然后利用计算机进行相应的处理从而实现对这些纸片自动和半自动的拼接还原。

碎纸片自动拼接技术的关键包括图像的预处理和匹配，其中预处理的目的是把碎纸片表示为适合于利用计算机处理的形式。

预处理包括图像的获取和处理，对于边界特征明显的纸片可以进行边界检测，轮廓提取和表示。

而纸片的匹配技术是碎纸自动拼接中关键之关键，即利用建立好的模型并设计出算法对纸片进行特征识别和自动拼接。

问题中的碎纸片由于具有同样的边缘几何特征，因此不能采用常规的靠提取碎片边缘尖点、尖角以及面积的方式来对不同的碎片进行区分。

对于这类边缘相似的碎纸片拼接，理想的计算机拼接过程应与人工拼接过程类似，及拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否匹配，然而由于理论和技术的限制，让计算机具备类似人那种识别碎片边缘的字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。

但是，利用现有的技术，完全可以获取碎纸片内部及边缘的文字几何特征以及纸片不同部分的颜色等信息，在自动拼接时，只要寻找到具有相同边缘特征的纸片即可。

数学建模碎纸片拼接复原题目《数学建模碎纸片拼接复原：一场奇妙的探索之旅》我呀，最近在学校里遇到了一个超级有趣又超级难的事儿，那就是关于数学建模里的碎纸片拼接复原题目。

这可不是一般的题目，就像是一个超级复杂的拼图游戏，但又比普通拼图难上好多好多倍呢！咱们先来说说这个碎纸片是怎么回事吧。

想象一下，有好多好多的碎纸片，就像被大风吹散了的树叶一样，到处都是。

每一片碎纸片都像是一个小秘密，它上面只有一部分的文字或者图案。

这些碎纸片有的边缘是平滑的，有的却是弯弯曲曲的，就像不同形状的小云朵在纸上飘着。

我和我的小伙伴们刚开始看到这个题目的时候，都瞪大了眼睛，嘴巴张得能塞下一个大鸡蛋。

“这可怎么拼啊？”我的小伙伴小明忍不住叫了出来。

我也在心里直犯嘀咕，这简直就像是要把散落在地上的星星重新组合成原来的星座一样困难。

不过，我们可没有被这个难题吓倒。

我们就像一群勇敢的小探险家，准备去解开这个谜题。

我们首先想到的是从碎纸片的边缘入手。

就好比我们在搭积木的时候，先找那些有特殊形状的积木块一样。

那些边缘有独特形状的碎纸片，可能就是我们找到拼接复原方法的关键。

我拿起一片碎纸片，上面有一点点像是字母“e”的半边。

我就大声地对小伙伴们说：“你们看，这个会不会和另一片能组成一个完整的‘e’呢？”大家都围了过来，眼睛里闪烁着兴奋的光芒。

小红说：“那我们快找找看呀！”于是我们就开始在那一堆碎纸片里翻找起来。

这感觉就像是在寻宝，每一片碎纸片都可能是宝藏的一部分。

可是，找了半天，我们发现事情并没有那么简单。

有好多碎纸片的边缘看起来好像能拼接在一起，但实际上它们的内容却对不上。

这就像你以为你找到了两块合适的拼图，结果发现上面的图案根本不是一回事儿。

我有点沮丧地说：“这也太难了吧，感觉就像在黑暗里摸东西，怎么也找不到正确的方向。

”这时候，聪明的小刚说话了：“我们不能只看边缘呀，还得看看纸片上的文字或者图案的内容呢。

比如说，如果一片碎纸片上有一个单词的开头部分，那我们就得找有这个单词结尾部分的碎纸片。