碎纸片的拼接复原分析(最终)甄选范文

基于改进的BFS算法的碎纸片拼接复原终期研究报告书一、课题研究的主要进展和结果图象拼接是一个日益流行的领域，已经成为照相绘图学、计算机视觉、图像处理和计算机图形学研究中的热点。

图像拼接解决的问题一般式，通过对齐一系列空间重叠的图像，构成一个无缝的、高清晰的图像，它具有比单个图像更高的分辨率和更大的视野。

本文的主要工作：(1) 总结了前人在图像拼接方面的技术发展历程和研究成果。

(2) 学习和研究了前人的图像配准算法。

(3)学习和研究了常用的图像融合算法。

(4) 用matlab实现本文中的图像拼接算法(5)总结了图像拼接中还存在的问题，对图像拼接的发展方向和应用前景进行展望。

我们的项目预期目标是运用改进的BFS算法逐层深入地解决了仅纵切、既横切又纵切以及双面拼接的碎纸片复原问题，并且将得到碎纸片的拼接复原位置和复原图像。

为司法物证复原、历史文献修复以及军事情报获取领域提供新的理论方法，同时，避免了人工来进行图象拼接复原的复杂性。

本文根据题目要求，针对具体问题建立相应的数学模型和设计相应的算法，逐层深入地解决了仅纵切、既横切又纵切以及双面拼接的碎纸片复原问题，最后得到了附件1—5的的碎纸片的拼接复原位置和复原图像。

结果见附录中的正文。

二、课题研究问题的叙述2.1 问题一的分析问题一要求仅对纵切的中英文碎纸片进行拼接复原，这是典型的图像匹配问题。

首先按照附件中的图片顺序，依次编号为1~19，然后我们对碎纸片的文字特征进行分析，用将碎纸片数字化，提取其灰度值，再读取每张碎纸片的左右边界灰度值，计算碎纸片之间左右边界灰度值的差的平方值越小，则相似性度量越高。

然后判断边界碎纸片，边界的碎纸片的判定可以根据每张纸片的左右边界灰度值是否为空白，左边界灰度值为空白的碎纸片的顺序即为1，右边界灰度值为空白的顺序即为19.从而建立搜索策略模型，用广度搜索优先算法找到每张碎纸片与相似性度量越高的匹配对象即为最佳匹配对象，如果还有小数碎片不能确定其复原位置，单独列出，最后根据文字特征及常识进行人工拼图。

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

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

针对问题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值即为列排序。

碎纸片的拼接复原摘要碎纸片的拼接复原是一门借助计算机，把大量碎纸片重新拼接成初始纸张的技术。

针对问题一，本文首先利用碎纸片图像灰度矩阵的边缘矩阵，建立了两个碎纸片之间的匹配度函数，求得了每一张图片之间左右边缘匹配度矩阵。

然后根据左边边缘位置的碎片的左边空白部分最多的特点，确定了左边位置的碎纸片。

接着根据拼接碎纸片的拼接复原时，所有碎纸片匹配度之和取极大值的原则，采用贪心算法，得到了所有碎纸片的初始位置，拼接复原了附件1和附件2中纸片。

针对问题二，由于附件3碎片数量太多，并且碎片的拼接复原，是一个以碎纸片总匹配度为目标函数的组合优化问题。

所以本文采用遗传算法将碎纸片的编号作为基因，并将基因均匀分成19段，按顺序每一段对应一个初始纸片列位置，进行了求解。

然后，根据边缘碎纸片某些边的空白部分多的特征，对初始基因进行了优化。

接着，根据碎纸片的黑色像素密度不同的特点，将碎纸片分成三类，根据同类纸片优先匹配的原则，对遗传算法的运行过程进行了优化，拼接复原了附件3和附件4中纸片。

针对问题三，随着碎纸片量的增多，计算量急剧增加。

在上述拼接复原碎纸片的基础上，又引进了同行位置碎纸片的上部（或下部）空白位置宽度相近的聚类思想。

先对每个类内部拼接，在合并所有类并做一次整体拼接。

由于时间有限，我们未能完成最后一次的整体的拼接，但我们会在比赛后继续探究。

关键词：边缘矩阵匹配度函数遗传算法聚类一、问题重述碎片拼接实际用途已经越来越广泛，传统上拼接复原工作由人工完成，碎片拼接的准确率较高，但效率很低。

并且当碎片数量很大时，人工短时间内拼接出来几乎是不可能的。

所以开发碎纸的拼接技术，以提高拼接复原效率已成为越来越多人的期望。

现在,在碎纸片是规则的情况下，题目要求我们在以下条件建立碎纸片拼接复原模型和算法。

1.来自同一页印刷文字文件（中文、英文各一页）的碎纸机破碎纸片（仅纵切）拼接复原，并将附件1和附件2复原。

2.对碎纸机既纵切又横切文件的情形，将碎纸片拼接完整。

碎纸片的拼接复原分析最终引言碎纸片的拼接复原是一项有趣且具有挑战性的任务。

无论是为了还原重要文件还是拼接有意义的图像，我们都需要使用各种技巧和方法来完成这项任务。

本文将介绍一种基于分析的碎纸片拼接复原方法，通过对碎纸片的形状、颜色和纹理等特征进行分析，最终达到拼接复原的目标。

碎纸片的特征提取在进行碎纸片的拼接复原之前，首先需要提取碎纸片的特征。

这些特征包括碎纸片的形状、颜色和纹理等。

形状特征提取为了提取碎纸片的形状特征，可以通过计算碎纸片的边界和角度来获得。

首先，使用图像处理技术，如Canny边缘检测算法，将碎纸片的边缘提取出来。

然后，使用霍夫变换来检测碎纸片的直线和角点，从而计算出角度和边界。

颜色特征提取碎纸片的颜色特征可以通过计算图像的颜色直方图来得到。

颜色直方图表示了图像中每个颜色的像素数量。

我们可以使用像素级别的颜色分布来比较不同碎纸片的颜色特征，并找到相似的碎纸片来进行拼接。

纹理特征提取碎纸片的纹理特征可以通过计算图像的纹理描述符来得到。

纹理描述符是用于描述图像纹理的数值特征。

其中，最常用的纹理描述符包括灰度共生矩阵（GLCM）和局部二值模式（LBP）。

通过计算碎纸片的纹理描述符，我们可以比较不同碎纸片之间的纹理相似度，并选择相似的碎纸片进行拼接。

碎纸片的拼接策略在完成碎纸片特征提取后，接下来需要制定碎纸片的拼接策略。

拼接策略将基于碎纸片的特征相似度和拼接的整体目标来确定。

相似度匹配根据碎纸片的形状、颜色和纹理特征，我们可以计算两个碎纸片之间的相似度。

一种常用的相似度计算方法是使用余弦相似度，它衡量两个向量之间的夹角。

通过计算碎纸片之间的相似度，我们可以找到最相似的碎纸片来进行拼接。

拼接顺序在进行碎纸片的拼接时，需要制定一个拼接顺序。

一种常用的策略是首先选择与已拼接部分最相似的碎纸片进行拼接，然后逐渐增加已拼接部分的面积，直到最终完成拼接。

拼接约束为了保证拼接的准确性，我们需要制定一些拼接约束。

碎纸片的拼接复原摘要本文研究了碎纸片的复原问题。

对已有的碎纸片，我们利用Matlab求碎纸片边各侧边线的灰度值，通过最小偏差平方和法进行碎纸片间的相互匹配，中间加入人工干预进行筛选，将附件中的碎纸片全部还原。

之后，我们将该方法进行推广，可用以处理更复杂形状碎图片的的还原问题。

对问题一：首先假定附件一所给仅纵切的碎纸片的行文方向与各碎纸片两侧边线垂直，在此基础上先人工干预，根据碎纸片的剪切规范，甄选出原始图片的第一张和最后一张碎纸片，编号分别为008和006。

其次通过Matlab求出图片边线处各小网格点的灰度值，采用最小偏差平方和法，对编号008碎片右边线处的灰度值和其它碎纸片的左边线处的灰度值进行对应网格点的数值匹配，找到最匹配的碎纸片。

附件二碎片的处理进行了类似处理，给出的复原图片见附表4。

对问题二：附件三文本既纵切又横切，同样我们假设所给附件三中碎纸片的行文方向与碎纸片的上下左右边线分别平行或垂直。

在问题一的算法基础上，通过Matlab求出各碎纸片的4条边线的边界灰度值，然后利用最小偏差平方和法，对上下左右四边进行灰度值匹配，当结果多个时，我们进行了人工干预。

附件四依照附件三的方法类似处理，最终的复原见附表7和附表9。

对问题三：附件五中的图片既纵切又横切而且是正反面。

我们参照问题一、二的处理方法，加入反面的灰度值测算，随机选择一张碎纸片与其他碎纸片进行遍历匹配，得出4张匹配的碎纸片后，以这4张碎纸片为下一起点，扩张匹配，最终给出的复原图见附表12。

为适应更一般的情形，我们在模型改进部分，给出了当碎纸片的文字行文方向与碎纸片两侧边线不垂直时的处理方法（只处理了边线为直线的情形）。

首先是通过测算出的碎纸片灰度值确定出碎纸片的边缘线，其次定出碎纸片边缘线附近网格点的灰度值，最后完成边线的的匹配。

关键词：人工干预灰度矩阵灰度值最小偏差平方和法一问题重述1.1问题背景纸片文字是人们获取和交换信息的主要媒介，尤其是在计算机技术飞速发展、数码产品日益普及的今天。

撕纸复原的作文
这确实是一次有趣的经历!前几天老师交给我们一篇作文,题目是"我最难忘的一件事"。

我当时正沉浸在回忆之中,突然一阵风吹来,把我的作文稿纸给撕碎了!纸张四处飞散,我傻了眼,一时间不知所措。

就在我准备放弃重写的时候,我的好朋友凯文走了过来。

"嘿伙计,怎么了?发生什么事了?"他关切地问。

我把遭遇告诉了他,他听后哈哈大笑起来:"没问题的!我们一起把它重新拼起来吧!"
于是我们开始在教室里东翻西找,把那些零零散散的纸片一一捡起。

有的被风吹到了窗台上,有的掉进了桌缝里,还有一些被人踩在了脚底。

最终,我们居然把所有的碎片都找全了!
接下来就是最考验耐心的部分了。

我们得按照原来的顺序,一点一点将纸片拼凑起来。

不得不说,这项工作着实费神。

有几处撕裂的地方,我们根本分不清到底哪一段该排在前面。

还好凯文提出了一个小诀窍,就是先从最长的那几段开始拼,然后再慢慢把其他的部分填补进去。

就这样,在我们一起的努力下,这篇作文终于又重生了!虽然纸张上多了一些折痕,但那无疑见证了我们这次"撕纸复原"的奇遇。

最后,我在作文的最后一行,特意写下了"感谢凯文的帮助"。

因为正是他的及时相助,才让这篇作文得以保留下来。

这次插曲给了我一个难忘的经历和教训。

有时候,当我们遇到困难的时候,不要轻易放弃,多求助于身边的人,或许就能找到出路。

朋友的力
量是无穷的,就像我和凯文一起"复活"了这篇作文一样。

高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题.我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性.如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理.我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）.我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（即电子文件名）： B0813 所属学校（请填写完整的全名）：广西师范大学参赛队员 (打印并签名) ：1.2.3.指导教师或指导教师组负责人 (打印并签名)：日期2013年 9 月16日赛区评阅编号（由赛区组委会评阅前进行编号）：高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：纸片的拼接复原摘要碎纸自动拼接复原技术现今可以归结到计算机视觉和模式识别领域内的问题，它在司法物证复原、历史文献修复等重要领域都起着重要的作用.本文主要分析了文字的拼接技术，通过研究碎纸片内的像素矩阵和文字行特征特点，提出了基于文字图形的半自动拼接算法.对于问题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].一页文字文件的碎片拼接复原相当于全景图的生成技术，而相邻图像的配准及拼接是该技术的关键.图像的拼技术一般分为基于图像特征的方法和基于图像灰度的方法.特征提取的方法通常涉及大量的几何与图像形态学的计算，计算量大，没有一般的模型可遵循，但需要针对不同的应用场景来选择各自适合的特征，所提取的图像特征包括更高层的语义信息，基于特征的方法具有尺度不变性和放射不变形.然而基于图像灰度的拼接方法简单简单易行，并且其数字统计模型以及收敛速度、定位精度等均具有定量的分析和研究结果，此类方法得到了广泛的应用.本文中的文字图像中文字区域的文字结构相对单一，并可能出现相同或相似的字符，因此文字容易出现匹配出现误差.对于文字左右拼接的情况，可以对图片中划分的每行文字进行分析处理，通过提取文字图片的边缘像素矩阵，得到文字出现在图片边缘的那一行高，进一步对一行行的文字拼接复原，这也有利于获取更精确的配准结果.基于文字的图像灰度的方法不需要提取文字图像的相应的特征，只以两幅图像相连接部分对应的像素灰度的相似性准则来寻找图像的匹配位置.待匹配的图像，首先求出图像中最左边一列的像素矩阵值之和，和最右边一列像素矩阵之和。

碎纸片的拼接复原作者：刘垚杉王智刚范博来源：《电子技术与软件工程》2015年第10期在人们的生活和工作中破碎文件的拼接复原都起着重要作用，但人工拼接的效率低下，为解决此问题，本文基于图像的数字化处理以及碎片文字的边缘特征和行特征，建立以碎片的匹配度为目标的单目标规划模型，实现文字文件碎片的拼接复原。

本问题需要考虑横纵两种切碎方式，由于碎片的数量增多，碎片边缘特征相近的情况增多，所以考虑用文字的边缘特征和行特征共同表征文字特征，并将同一行特征的碎片先聚类分解、简化问题，再利用最短路径算法建立各行的最优拼接模型完成11行的横向拼接，最后根据行碎片的横向边缘特征的匹配度以及上下片碎片相对行特征的地推关系完成纵向拼接，实现文件复原。

具体结果见正文部分。

【关键词】碎纸版拼接数字化处理1 问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

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

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

随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。

请讨论以下问题：对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件给出的一页文件的碎片数据进行拼接复原。

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

复原结果表达要求同上。

2 问题分析问题中的碎片考虑横纵两种切碎方式，由于碎片的数量增多且增加了上、下两个边缘，此时单以文字的左右边缘特征的匹配度来确定碎片的拼接顺序容易出错，所以考虑模拟人工拼接过程，不仅考虑碎片的边缘匹配，还考虑碎片的文字行特征，并将横向切与纵向切分层考虑。

因为附件中的碎片及文字都是正向水平放置的，同一行碎片上的行间距，字与边界间的距离应当是几乎一致的，所以利用文字的行特征，先将同一行的碎片聚类。

利用该行碎片的左、右边缘特征的匹配情况和最短路径算法建立优化模型将该行的碎片拼接，完成11行的横向拼接，最后根据吻合拼接的上片碎片与下片碎片的文字行特征的递推关系完成纵向拼接，实现文件的复原。

关于碎纸片的拼接复原探讨摘要对碎纸片进行还原与拼接，在我们的日常生活中具有重要的意义，特别是在对一些重要的领域如军事情报的获取以及历史文献的修复。

本文主要讨论了对破碎纸片进行自动拼接的复原技术，通过对破碎的纸片进行图像扫描后，得到了碎纸片的位图图像，用matlab对位图进行读取处理后，得到了图片文件的数据，图片的文件数据简单地说来，就是上面存储着一张图片各个像素点的灰度值的一个二维数组。

经过对图像进行中值滤波去噪的处理后，提取出每张图片的边缘灰度值，得到了一个边缘矩阵，通过对图片边缘的灰度值进行比较，找到差最小即为相匹配的图片,最后把找到相邻的图片进行拼接复原工作。

针对各个问题，建立了具体的模型来求解，最后得出碎纸片拼接复原的方法。

针对问题一，由于纸片只进行了纵向方向上的切割，所以我们只需要考虑其左右边缘的像素灰度值是否相吻合，如果纸片相吻合，则相邻的纸片灰度差的平方和应该为最小。

相吻合时我们把相邻的切片进行链接后拼接复原得到了原图形。

在分析过程中我们发现最边缘的一列下来是基本上是空白，因此在边缘矩阵提取找到值全只有255或者0的纸条，确定为起始的碎片。

以此张碎片为标准，拿其他的图片与其进行比较。

怎样才能算是相吻合的情况，我们根据边缘矩阵像素的灰度值来进行比较，如果碎片为相邻的情况，其边缘的像素值是连续的，由此我们把矩阵Y求出来后，进行比较找到最小值的列就是与其相匹配的碎纸片。

针对问题二，由于碎纸片既有纵切又有横切的情形，故我们除了要考虑纸片的左右边缘相互匹配的情况外还要考虑纸片上下边缘的匹配情况，即在问题一的基础上增加了对纸片上下边缘的像素灰度匹配的情形的考虑。

也就是增加多了两个矩阵U和B，分别保存每一张图片的第一行和最后一行的信息。

首先也是进行找到边缘的碎片片，因此我们在进行完左右纸片的拼接后，然后再考虑上下相邻纸片边缘的拼接情形。

这时可以用到问题一的模型来参照计算得出左右碎纸片的匹配情况，之后进行行的拼接。