13年碎纸片拼接复原数模论文B

承诺书

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

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

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

我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

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

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B

我们的参赛报名号为（如果赛区设置报名号的话）：

所属学校（请填写完整的全名）：重庆XX大学

参赛队员(打印并签名) ：1. 祝XX

2. 冯XX

3. 周XX

指导教师或指导教师组负责人(打印并签名)：张XX

（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）

日期： 20XX 年 X 月 XX 日赛区评阅编号（由赛区组委会评阅前进行编号）：

编号专用页

赛区评阅编号（由赛区组委会评阅前进行编号）：

全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：

碎纸片的拼接复原

摘要

图像碎片自动拼接复原是需要借助计算机把大量碎片重新拼接复原成初始图像的完整模型，这一研究在考古、刑侦犯罪、古生物学、医学图像分析、遥感图像处理以及壁画保存复原等方面具有广泛、实际的应用[1].

本文主要解决碎纸机破碎文档的自动拼接复原问题.我们利用图像数字化技术，借助Matlab软件将图像转化为矩阵.通过建立数学模型，运用矩阵论、聚类分析方法、自定义相似度方法、遗传算法、字符分割和字符识别等方法，对数据进行处理，实现对图像碎片自动拼接，从而将所给碎片拼接复原为完整图像.

问题一，我们首先把碎片图形进行二值化处理，根据所给纵切黑白碎片边缘的像素关系(相邻两张碎片，一张碎片矩阵右边的像素与另一张碎片左边的像素相同 )，我们采和自定义相似度算法，利用附件一和附件二求出碎片间的相似度，然后根据所需要满足的条件即相似度最大原则，建立了纵切碎片拼接模型一及其算法，运用Matlab编程实现该模型，并得到碎片复原结果（见表一表二）.

问题二，要实现快速准确的拼接复原纵横切碎片，在问题一的思路基础上，我们采用了模糊C的均值聚类方法，先对附件三所有碎片进行初步的分类，然后在自定义相似度算法上增加了约束条件，以此来排除有若干碎片在匹配时相似度相同的情形，建立了改进的中文纵横切碎片拼接模型二，同样利用Matlab软件求得碎片的复原结果（见表三）.

对于英文纵横切碎片的拼接问题，我们采用了字符切割和字符识别思想，即在碎片的二值化矩阵中选取适当大小的行与列，对碎片边缘的英文字母进行切割，与其他图片匹配合并，提取切割字母的特征（统计特征或结构特征），再利用字符识别的方法从得到的特征库中找到与待识别字符相似度高的字符，将两张碎片拼接在一起，先一行一行地进行拼接，再利用模型二横切碎片方法，利用Matlab软件求得碎片的复原结果（见表四）.

问题三，在处理双面打印纵横切碎片时，经分析发现两面图片最大的区别在于光滑度的不同，纸张的正面比反面要光滑，因此在模型二的基础上还需增加一步筛选工作，就是采用傅里叶变换将图像的二值矩阵从“空域”变为“频域”，再根据不同页面的频率范围，设定一段频率值，借助计算机将双面打印的碎片进行分类，分离出在同一页面的碎片.分离成功后再采用模型二对于英文碎片的拼接方法将碎片进行复原即可，通过这种方法求得碎片的复原结果.

关键词：碎片拼接均值聚类方法相似度模型傅里叶变换

一、问题重述

1.1背景：破碎文件的拼接和复原对于司法物证复原、历史文献再现和军事情报获取等方面都有极其重要的作用.于是碎纸片的拼接复原技术便成为图像处理与模式识别领域中的一个崭新典型的应用.图像配准是图像拼接复原的基础，而且图像配准算法的计算量一般非常大，因此图像拼接复原技术的发展很大程度上取决于图像配准技术的创新.本文将通过图像提取技术获取一组碎纸片的形状、颜色、文字等信息，然后利用计算机进行相应的处理从而实现对这些碎纸片的自动拼接复原.

1.2重述：该题研究的是如何对碎纸片进行拼接复原.传统上，拼接复原工作需由人工完成，准确率较高，但是效率低.随着计算机技术的发展，当碎纸片数量巨大的时候，人们试图开发碎纸片的自动拼接技术，以提高拼接复原的效率.

问题1 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点.

问题2 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、4给出的中、英文各一页文件的碎片数据进行拼接复原.如果复原过程需要人工干预，写出干预方式及干预的时间节点.

问题 3 对于双面打印文件的碎纸片拼接复原问题设计碎纸片拼接复原模型和算法，并针对附件5给出的一页英文印刷文字双面打印文件的碎片数据进行拼接复原，结果表达同上.

二、问题分析

碎纸机破碎纸片的拼接复原，都需要经过获取图像，导入图像，图像预处理，图像配准，和图像的拼接复原步骤.其中图像配准是碎纸片拼接复原技术中最重要的环节之一.针对本题中给出的三种不同的情况，需采用不同的模型和算法来提高拼接复原的效率和准确度[2]：

对于问题1 所需要拼接复原的碎纸片为纵向切割的小纸条，通过Matlab软件将所给图片转换成为198072

?的二值矩阵，先随机选择一个碎片的矩阵作为基本矩阵，将剩余矩阵与基本矩阵作比较，通过matlab软件计算出相比较矩阵的相似度，再根据模型一的匹配方法将碎纸片进行拼接复原,此拼接模型不需要人工干预.

对于问题2 对于碎纸机既横切又纵切的情形，所得碎片的像素较低，采用模型一的算法无法完全拼接复原19

11?个碎片，需要先对碎片进行聚类分析，筛选出特征相同的碎片，再根据二重判别标准的相似度刻画原则，将碎片进行横向和纵向的拼接复原. 对中文碎片进行拼接时，先通过二值矩阵找出字间距和一个字的间距，通过聚类分析法先将所有碎片分行找出，把横纵切拼接问题转化为横切碎片拼接，再利用行间距和字的行高约束条件，运用遗传算法拼接复原整个图片.

英文碎片拼接与中文碎片拼接不同，在拼接碎片时，需要采用字符切割的方法，提取英文字母的特征，根据碎片边缘字母的特征，再利用字符识别的方法，寻找相匹配的碎片，根据这一原则运用遗传算法的匹配方法拼接复原英文碎片.

对于问题3 要想拼接复原双面打印碎片，必须先将所有碎片进行分类.把同一页的碎片分离出来.经过分析可得，两面打印的纸张的粗糙度不同，正面比反面光滑，根据这一特征，需要采用傅里叶变换处理图像，从而得到碎纸片的“频率”图.高频代表图像的细节、纹理信息，低频代表图像的轮廓信息.对所有碎纸片进行高频滤波.滤波后可得图像的纹理信息.运用Matlab软件计算若干碎纸片的频率信息，设定频率范围，将所有碎纸片分为正反页面图片两类.再采用模型二的算法拼接复原整个图片.

三、基本假设

1、碎纸机破碎的每个纸片的长、宽和厚度均相同；

2、所有碎片是黑白图片，图片清晰；

3、碎片完整没有缺损缺失，可以完全拼接复原；

4、碎纸片的正反两方面的印刷效果都一样，互不影响；

5、扫描图片没有变异，文字与图片上边界平行；

6、文件页边距和行距固定；

7、碎片中的文字方向相同，不需要考虑碎片拼接时需要旋转拼接复原.

五、模型的建立与求解

通过我们建立的自动拼接模型，在图片拼凑过程中，我们可以预测图片的拼接大致需进行图片处理、边界比较、图片输出等步骤.

通过我们所得的模型预测，可以得出预测方程.具体流程图如图5-1所示：

图5-1 模型方法预测

（一）问题一模型的建立与求解

5.1.1 图像的导入 运用Matlab 软件采用二值法原理将碎片的图像转换成为198072?的（0,1）矩阵，记为i A )19,,2,1( =.

5.1.2图像的去噪边缘处理 采用中值滤波的原理对图像边缘进行去噪.中值滤波就是

用相邻像素的中值来替代该像素的值，利用Matlab 对图像所成二值矩阵进行光滑处理，以此提高碎片匹配时的相似度.

中值滤波法是一种非线性平滑技术，它将每一象素点的灰度值设置为该点某邻域窗口内的所有象素点灰度值的中值.

中值滤波是基于排序统计理论的一种能有效抑制噪声的非线性信号处理技术，中值滤波的基本原理是把数字图像或数字序列中一点的值用该点的一个拎域中各点值的中值代替，让周围的像素值接近的真实值，从而消除孤立的噪声点。方法是去某种结构的二维滑动模板，将板内像素按照像素值的大小进行排序，生成单调上升（或下降）的为二维数据序列。二维中值滤波输出为)},(),,({),(w l k l y k x f med y x g ∈--=，其中，),(y x f ，),(y x g 分别为原始图像和处理后图像。W 为二维模板，通常为33,22??区域，也可以是不同的的形状，如线状，

圆形，十字形，圆环形等

中值滤波的函数为：

∑∈=

)

,(),(),(1

),('y x f y x t s g m y x f 5.1.3图像的配准

1）遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种有效的解最优化问题的方法.借助计算机选取第一张碎片作为第一张图，采用遗传算法，将该图片的右边缘矩阵与剩下的18张图的相对应的左边缘矩阵随机的根据相似度进行比较，然后把相似度最高的图片作为第二张图并与第一张图片拼接起来.将第一张图作为基准图，向右匹配，若右方向的匹配完成，再朝左方向匹配，以此类推，直到将所有图片拼接复原完成.问题一不需要进行人工干预.

图5-2 遗传算法流程图

2）相似度的计算方法：计算机自动选择一张碎片为第一张碎片（此处就以000.bmp

为第一张），具体实现算法为用嵌套循环，第一重循环取出每张图片最右边（第72列）的像素矩阵，第二重循环取出每张图片最左边（第1列）的像素矩阵，然后作这两个矩阵的比较，结果相同为1不同为0，对其结果矩阵求和作为刻画相似度的标准，如果是自身比较则置为0，当结果中出现1980（说明两张图片是100%匹配，可以判断出第一张和最后一张），用这种方法就可以得到完整的拼接图像，剩余图片的矩阵随机编号为i A ，利用Matlab 软件选取矩阵中的n 行运用同或运算法则进行相似度的计算.

假设 100010100A ????????=???????? 01101101i A ??????

??=????????

.

让1A 的最右列与i A 的最左列的元素一一对应作比较，同行的两元素相同则为,1，不同记为0，从第一行开始累加，累加的结果记为i m . 相似度记为：100%i b n

m =? （n=1980）.

5.1.4图像的导出

1）根据配准结果进行矩阵的拼接.

2）运用Matlab 软件编程实现图像的导出.

表一 附件一图片排序

表二 附件二图片排序

（二）问题二模型的建立与求解

问题二为纵横切有1119?个碎片，每个碎纸片的边缘像素相对于问题一来说要少很多，无法直接利用模型一求解问题二.在模型一的基础上，我们首先对中文碎片进行拼接复原，根据图片的特征对图片进行分类，然后再采用双重标准定义相似度的算法来进行图片的拼接.拼接英文碎片时，采用字符切割和字符识别的方法，问题二需要人工介入.

5.2.1 图像导入

同样采用二值法，运用Matlab 软件将碎纸片的图像转换为18072?的（0,1）矩阵. 5.2.2图像边缘处理

采用模型一的中值滤波的方法对209张图片的边缘进行光滑处理，以提高图片在匹配时的相似度，排除噪声对图片的影响. 5.2.3图像配准（拼接中文碎片）

1）采用模糊C 均值聚类方法根据同行图片的特征，同一行图片的同列字间的间距相同，缺损字的上边缘或下边缘与碎片的边缘之间的距离相同.还可以根据字的最左端到图片边缘之间的距离相等筛选出文章最左列碎片，运用Matlab 软件编程将209张碎片进行初步分类，再利用Matlab 软件建立元胞数组，将碎片分行导入元胞数组，同行碎片不分顺序[3].

模糊C 均值聚类：设R

X X X P

N X ?

=},,,{21 ,R P

表示P 维实数向量空间.令u ik

表示第k 个样本属于第i 类的隶属度，10≤≤u ik ，∑=c

i ik u 1

=1，N N

k ik u <<∑=1

0，c i N k ≤≤≤≤1,1。记v i 为第i 类的聚类中心.则X 的一个模糊C 均值聚类就是求如下目标函数的最小值：

∑∑===N

k c

i m

d u ik ik V U J 112

)

()

(),(.

其中||||v x d i

k

ik -=为第k 个序列到第i 类中心的欧式距离。

聚类准则取为求J(U,V)的极小值：min{J(U,V)}.

求模糊C 均值聚类的具体步骤如下：

（1） 取定c,m 和初始隶属度矩阵U 0

，迭代步数I=0. （2） 计算聚类中心V 为：

∑∑===

N k m

N

k k

m

l i

u x

u v

l ik

l ik 11

)()()()

()( )1;,,2,1(m c i <= .

（3） 修正U ：

∑=-+=

c

j m l ik

d d u

jk

ik 1

1

2)1()(1

.,k i ??.

（4）对给定的0>ε，实际计算时应对取定的初始值进行迭代计算直至

ε<--|}max{|

1

u u t ik t ik ，则算法终止，并得到结果。若}max{u u jk jk =，则∈x k 第j 类.

如：

其中可判定图片5-3与5-4为同一行，图片5-3与图片5-5不在同一行.

2）因用人工干预找出完整图片的左下角的碎片，先只拼接这一行，由于明确了方

向两两图片只需单向作比较，可将已确定的图片标记为1不再被比较。因图片可能有孤立两点和黑点，为忽略像素间的比较那些点的影响，采用绝对值来控制同行或同列像素间其比较结果取值范围。有采用模型一的贪婪算法和每张图片做相似度的大小比较并在此基础上加上这张图片的特性约束及深度比较和中途的人工干预可正确筛选出一行完整图片。以此思想继而课求出此图片的纵列，以后以纵列的每张图片再进行此算法的类推可拼接完整图片.

例：

（1）中文版

确定007.bmp为开头的所在行

确定029.bmp为开头的所在行

（2）英文版

确定081.bmp为开头的所在行

确定191.bmp为开头的所在行

3）定义相似度：

约束一：与模型一的相似度算法近似.

约束二：用以上得出的字与字，字与页边距的规律求出要拼接的这行为首图片的特征来加以约束要比较的图片.

约束三：当有多个像素相似度值很接近和相等时再精确深入作比较，利用同一行碎片的二值矩阵的特征即上下两个字的间距为28个像素点，左右两个字6个像素点，进

一步比较.

如果出现异常情况，人工干预进行修正.在对英文碎片进行拼接时采用同样的方法，只是需要改变它们之间的行间距与字间距的约束条件.

4）通过以上步骤将每行的碎片拼接完成，并确定了最后一行的图片，将1119

个碎片拼接复原问题转换为11个碎片拼接问题.横切碎片比纵切碎片拼接复原的要复杂，

所以还需另一种二重约束的相似度算法.取约束一条件下相似度最高的碎片，如有相同

的再运用约束二的条件进行匹配，横向拼接的方法为模型一的遗传算法，从完整图片的

最后一行向上进行拼接。如果出现异常情况，人工干预进行修正.

5.2.4图像配准（拼接英文碎片）

1、字符切割：选取碎片二值矩阵边缘的若干列（一个字符间距加一个字母的像素），分

离出单个字符，选取的若干列中会有一个或多个完整或不完整的字符，这就相当于多个

约束条件的匹配.

2、特征提取：从切割的字符中提取统计特征或结构特征，进行归一化、细化处理.

3、字符识别：先借助计算机构建52个字母（大小写）的特征库（用1,0矩阵构造的字

母图样），根据特征库的信息，对于同一字母进行识别，从而挑选出相匹配的拼接碎片.

4、拼接算法：采用中文拼接的方法（遗传算法），即先拼接行，再拼接列.

5）图像的导出

表三附件三的复原结果

49 54 65 143 186 2 57 192 178 118 190 95 11 22 129 28 91 188 141 61 19 78 67 69 99 162 96 131 79 63 116 163 72 6 177 20 52 36 168 100 76 62 142 30 41 23 147 191 50 179 120 86 195 26 1 87 18 38 148 46 161 24 35 81 189 122 103 130 193 88 167 25 8 9 105 74 14 128 3 159 82 199 135 12 73 160 203 169 134 39 31 51 107 115 176 94 34 84 183 90 47 121 42 124 144 77 112 149 97 136 164 127 58 43 125 13 182 109 197 16 184 110 187 66 106 150 21 173 157 181 204 139 145 29 64 111 201 5 92 180 48 37 75 55 44 206 10 104 98 172 171 59 7 208 138 158 126 68 175 45 174 0 137 53 56 93 153 70 166 32 196 71 156 83 132 200 17 80 33 202 198 15 133 170 205 85 152 165 27 60 89 146 102 154 114 40 151 207 155 140 185 108 117 4 101 113 194 119 123

表四 附件四的复原结果

191 75 11 154 190 184 2 104 180 64 106 4 149 32 204 65 39 67 147 201 148 170 196 198 94 113 164 78 103 91 80 101 26 100 6 17 28 146 86 51 107 29 40 158 186 98 24 117 150 5 59 58 92 30 37 46 127 19 194 93 141 88 121 126 105 155 114 176 182 151 22 57 202 71 165 82 159 139 1 129 63 138 153 53 38 123 120 175 85 50 160 187 97 203 31 20 41 108 116 136 73 36 207 135 15 76 43 199 45 173 79 161 179 143 208 21 7 49 61 61 33 142 168 62 169 54 192 133 118 189 162 197 112 70 84 60 14 68 68 137 195 8 47 172 156 96 23 99 122 90 185 109 132 181 95 69 167 163 166 188 111 144 206 3 130 34 13 110 25 27 178 171 42 66 205 10 157 74 145 83 134 55 18 56 35 16 9 183 152 44 81 77

128 200 131 52 125 140 193 87

89 48 72 12 177 124 0 102 115

（三）问题三的求解

5.3.1傅里叶变换处理图像

通过对问题三的分析可得双面印刷碎片的特征，即为不同面的碎纸片的光滑度不同，所以需要利用傅里叶变换将图像从“空域”变为“频率”，再根据不同页面的频率范围，设定一段频率值，借助计算机将双面打印的碎片进行分类，分离出在同一页面的碎片，以此降低碎片拼接复原的难度.

快速傅里叶变换(FFT)是计算离散傅里叶变换(DFT)的快速算法.离散傅里叶变换运算量巨大，计算时间长，即运算时间很长.而快速傅里叶变换的提出将傅里叶变换的复杂度由降到了，很大程度上减少了计算量.

∑-==1

202)(21)(M x ux M W x f M u F

∑∑-=+-=++=10

)

12(210)2(2})12(1)2(1{21M x x u M M x x u M W x f M W x f M . 令∑-==10)2(1)(M x ux M e W x f M u F ，∑-=+=10

)12(1)(M x ux

M o W x f M u F ，u=0，1，2，…，M-1. 则 []

u M o e W u F u F u F 2)()(21)(+=，[]

u M o e W u F u F M u F 2)()(2

1

)(-=+ .

5.3.2 采用模型二拼接英文碎片的算法

借助Matlab 软件将所有碎片分为两类，分类完成后就与问题二拼接英文碎片相同了，因此可采用模型二拼接因为碎片的方法将碎片一页一页地拼接完成.

六、误差分析

虽然我们建立了针对不同情况碎片拼接的模型，也得到了碎片的复原结果，但是模型是建立在理想的假设基础之上的，实际上碎片不全是非常清晰的，也有不明朗的模糊灰色区域，特别是在碎片的边缘处，在对这些区域计算相似度时会由于阀值的不稳定性产生一些误差，可能导致图像拼接时出现错误拼接现象.除此之外，在问题二、三中采用聚类分析法对碎片分类时，可能得到的结果与主成分分析的结果有一定差异，就会导致分类时有些行的碎片会有多余的情况出现，从而无法完整拼接复原图片，所以实际与理论之间总会存在一定的误差，这是难以避免的.

七、模型的优缺点讨论

7.1模型的优点

通过对模型的分析，验证了模型的可靠性，模型过程清晰明了，并且可用Matlab 软件快速求解，为此类碎片的拼接复原提供了方便可行的设计方法，具有重要的实际意义和较高的应用价值.

模型一研究的是对纵切碎片的拼接复原，该模型简单方便，误差小，在没有异常情况下，无需人工干预，并且拼接效果优良.自定义的相似度算法简单可靠，还考虑到噪声对碎片边缘的影响，采用中值滤波方法对碎片边缘进行光滑处理能提高匹配的相似度，采用这种方法更符合实际情况.

模型二研究的是对横纵切碎片的拼接复原，该模型较模型稍复杂，考虑到碎片匹配时可能有多个碎片与之匹配的相似度相同，从而计算机无法选择的情况，采用了先分类后匹配的方法，不仅可以排除这种计算机无法选择的情况，还提高碎片拼接的效率.在现实生活中，碎纸机破碎文件时常为纵横切碎片，所以模型二具有更大实际意义.

模型三研究的是对双面打印的纵横切碎片的拼接复原，借助傅里叶变换将图像由“空域”转换为“频域”，经过分析提取出图像的纹理特征，这种方法可靠性强，能够较强地判别出不同页面的碎片.模型三采用二次分类的算法，提高了碎片配准的精确度和效率.

7.2模型的缺点

三个模型在对碎片拼接复原时都没有考虑碎片的方向问题，没有采用坐标旋转的方法来拼接碎片.模型二中采用的模糊C均值聚类方法，可能得到的结果与主成分分析综合的结果有一定的差异，导致分类不够精确，并且模型二、三步骤较多，程序较为复杂，在碎片拼接时具有一定的难度.

八、模型的改进与推广

8.1模型的改进

在实际生活中，一方面，碎纸片中文字的方向是不定的而且纸片数量大，所以在建模拼接碎片时应考虑将碎片旋转拼接.在解决实际问题的过程中，我们可能发现利用经典的模糊C均值聚类所得到的结果与主成分分析综合的结果有一定的差异，故我们在此可对模糊C均值聚类加以改进，使得聚类的结果与主成分分析的效果基本一致，将聚类迭代公式中的欧式距离改为加权欧式距离，其中的权向量采取主成分分析的方法计算，采用这种加权模糊C均值聚类的迭代算法可使分类更加精确.

另一方面，图像的拼接不仅仅限制于文档型，可以运用于真彩型图片拼接.在建模时可以考虑基于模板彩色图像拼接模型.对两幅具有重叠区域的彩色图像,先利用图像特征信息从一幅图像的重叠区域中自动寻找一小块模块图像,然后根据最大相似性准则在另一幅图像中重叠区域里搜索,找到最佳图像配准点,最后利用平滑因子对两幅图像的重叠区域图像数据进行数据融合操作,去掉重叠部分,以实现彩色图像自动快速地无缝拼接.

8.2模型的推广

所有模型的建立、方案的确定、碎片的分析，数据量较大（碎片多）。对于碎片的拼接复原问题的解决，我们考虑了多方面因素，同时也对一些因素做了假设.通过改进，该模型的拼接复原精确度就越高。我们可将该方法推广到医学图像分析，遥感图像处理，彩色图像复原和视频监控等领域，具有重要的实际意义.

参考文献

[1] 蔡丽欢，廖英豪，郭东辉，图像拼接方法及其关键技术研究[J]，计算机技术与发

展，2008/03：67-81,2008年.

[2] 余宏生，金伟其，数字图像拼接方法与研究进展[J]，红外技术，

2009/06:74-102,2009年.

[3] 杨桂元，黄几立，数学建模[M]，合肥：中国科学技术大学出版社，2008年.

[4] 薛毅，数学建模基础[M]，北京：北京工业大学出版社，2004年.

[5] 谢兆鸿，范正森，王艮远，数学建模技术[M]，北京：中国水利水电出版社，2003

年.

[6] 景振毅，张泽兵，董霖，MATLAB7.0实用宝典[M]，北京：中国铁道出版社，2009

年.

[7] 杨启帆，何勇，数学建模竞赛[M]，杭州：浙江大学出版社，2005年.

[8] 张铮，王艳平，薛桂香，数字图像处理与机器视觉——Visual C++与Matlab实现

[M]，北京：人民邮电出版社.

[9] 张跃辉，矩阵理论与应用 [M]，北京：科学出版社，2011年.

[10] 吴石林，误差分析与数据处理[M]，北京：清华大学出版社，2010年.

[11] 王，任嘉辰，图论算法理论、实现及应用 [M]，北京：北京大学出版社，2011年.

附录

附录1 求解问题一的相关程序

clc

clear

for i = 0:18

image{i+1} = imread(['F:\B\附件

2\',sprintf('%03d',i),'.bmp'],'bmp');

image{i+1}=im2bw(image{i+1});

end

relat=zeros(19);

for x=1:19

for y=1:19

image{y}(:,1);

end

image{x}(:,72);

for z=1:19

if(x==z)

relat(x,z)=0;

else

bef_back=image{x}(:,72)==image{z}(:,1);

bef_like_back=sum(bef_back);

relat(x,z)=bef_like_back;

end

end

end

SUCCESS=xlswrite('C:\Users\lenovo\Documents\MATLAB\Emach2.xls' ,relat,'A2:S20')

global max clo row;

result=zeros(1,19);

for(x=1:19)

for (y=1:19)

if(relat(x,y)==1980)

max=relat(x,y);

row=x;

clo=y;

end

end

if(max==1980)

fprintf('图片%d为最后一张图片\n',row);

fprintf('图片%d为第一张图片\n',clo);

result(1,1)=clo;

result(1,19)=row;

break;

end

end

disp(max)

for(x=1:19)

max=relat(clo,clo);

for (y=1:19)

if(max

max=relat(clo,y);

row=y;

end

end

fprintf('图片%d后接图片%d\n',clo,row);

for i=1:18

if(result(1,i)==clo)

result(1,i+1)=row;

end

end

clo=row;

end

result=result';

c1

=[ image{result(1)},image{result(2)},image{result(3)},image{re sult(4)},image{result(5)},image{result(6)}];

c2

=[image{result(7)},image{result(8)},image{result(9)},image{res ult(10)},image{result(11)},image{result(12)}];

c3=[image{result(13)},image{result(14)},image{result(15)},imag e{result(16)},image{result(17)},image{result(18)},image{result (19)},];

e=[c1,c2,c3];

imshow(e)

附录2问题一中的计算中文图像的相似度表格

中文图像拼接的相似度表格（前10列）

0 1472 1511 1412 1583 1525 1878 1564 1637 1521 1489 0 1471 1456 1863 1611 1504 1510 1617 1553 1469 1530 0 1560 1571 1601 1492 1620 1655 1583 1559 1462 1595 0 1533 1549 1534 1572 1651 1539 1537 1508 1587 1522 0 1899 1504 1570 1755 1569 1493 1508 1492 1537 0 1486 1640 1663 1867 1646 1551 1684 1527 1650 1788 0 1739 1980 1658 1544 1529 1554 1451 1574 1542 1549 0 1660 1540 1600 1533 1504 1481 1560 1674 1543 1593 0 1536 1536 1511 1554 1499 1522 1574 1483 1585 1632 0 1448 1497 1898 1483 1470 1544 1501 1597 1638 1586 1579 1550 1575 1492 1553 1611 1524 1896 1731 1599 1638 1499 1592 1505 1600 1680 1563 1669 1852 1648 1580 1525 1556 1487 1532 1626 1575 1607 1728 1552 1593 1496 1683 1460 1633 1661 1592 1656 1817 1585 1494 1469 1504 1883 1484 1548 1403 1493 1552 1476 1459 1856 1447 1456 1455 1555 1406 1510 1521 1491 1878 1475 1504 1443 1482 1550 1455 1577 1626 1496 1564 1471 1564 1467 1492 1606 1515 1551 1668 1542

中文图像拼接的相似度表格（后9列）

1570 1496 1616 1495 1569 1579 1492 1550 1616 1554 1484 1604 1493 1561 1567 1560 1484 1512 1568 1574 1568 1561 1523 1639 1932 1522 1522 1852 1530 1648 1537 1587 1569 1524 1572 1506 1598 1650 1602 1517 1687 1661 1568 1494 1628 1544 1522 1618 1573 1557 1619 1594 1534 1556 1677 1741 1783 1656 1774 1852 1657 1631 1715 1567 1519 1637 1562 1552 1616 1563 1821 1551 1587 1609 1583 1516 1868 1652 1539 1545 1637 1495 1617 1573 1860 1498 1606 1543 1519 1507

0 1547 1613 1548 1532 1566 1505 1489 1529

1560 0 1628 1567 1591 1663 1608 1570 1602 1591 1705 0 1622 1682 1946 1623 1607 1653 1557 1609 1561 0 1634 1686 1533 1559 1903 1704 1614 1902 1607 0 1697 1582 1588 1584 1503 1543 1499 1514 1498 0 1539 1425 1463 1456 1498 1452 1473 1529 1491 0 1436 1492 1503 1593 1561 1582 1584 1624 1473 0 1539 1511 1875 1529 1538 1582 1664 1547 1453 0

附录3 问题一中的计算英文图像的相似度表格

英文图像拼接相似度表格（前10列）

0 1631 1645 1682 1652 1884 1586 1622 1641 1611 1722 0 1661 1780 1684 1572 1630 1686 1709 1915 1758 1727 0 1822 1726 1620 1676 1898 1721 1697 1724 1727 1693 0 1678 1616 1878 1682 1665 1681 1862 1817 1759 1980 0 1652 1740 1800 1759 1763 1754 1909 1677 1796 1686 0 1660 1708 1661 1705 1730 1673 1913 1780 1732 1638 0 1704 1681 1663 1705 1678 1680 1745 1655 1607 1691 0 1670 1700 1746 1731 1693 1820 1696 1658 1650 1714 0 1665 1703 1686 1674 1767 1659 1589 1625 1635 1648 0 1659 1678 1686 1755 1669 1607 1619 1689 1898 1712 1926 1743 1719 1858 1734 1616 1688 1744 1673 1699 1657 1668 1670 1725 1685 1645 1569 1691 1672 1616 1770 1723 1707 1810 1728 1618 1658 1722 1695 1645 1739 1716 1730 1779 1743 1633 1655 1717 1654 1656 1744 1737 1697 1802 1714 1624 1688 1754 1669 1673 1713 1670 1704 1763 1887 1655 1659 1701 1640 1656 1750 1689 1649 1802 1690 1594 1624 1728 1663 1671 1707 1696 1678 1793 1687 1599 1679 1717 1706 1666

英文图像拼接相似度表格（后9列）

1623 1615 1665 1657 1672 1665 1618 1618 1624 1693 1643 1657 1671 1664 1731 1674 1738 1674 1739 1731 1729 1701 1690 1721 1732 1700 1752 1679 1733 1671 1675 1636 1691 1674 1676 1734 1803 1775 1803 1807 1754 1819 1802 1780 1802 1699 1669 1709 1703 1698 1711 1700 1694 1750 1711 1665 1731 1679 1696 1723 1656 1700 1702 1646 1668 1718 1642 1635 1860 1661 1637 1683 1691 1729 1893 1693 1662 1749 1704 1694 1716 1692 1662 1656 1852 1651 1666 1685 1709 1665

0 1678 1678 1680 1713 1696 1635 1705 1675 1749 0 1741 1735 1686 1793 1774 1724 1752 1682 1610 0 1698 1905 1664 1617 1639 1667 1847 1743 1715 0 1710 1753 1688 1686 1718 1700 1650 1702 1700 0 1676 1659 1873 1733 1693 1691 1731 1695 1682 0 1714 1702 1926 1724 1658 1696 1684 1673 1694 0 1691 1703 1693 1665 1687 1703 1658 1699 1928 0 1708 1700 1890 1710 1692 1641 1702 1691 1687 0

2013年数学建模碎纸片的拼接复原模型

承诺书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 2013 年 9 月 10 日赛区评阅编号（由赛区组委会评阅前进行编号）：

编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 碎纸片的拼接复原模型 摘要：本文针对碎纸片的拼接复原问题，提出了互相关匹配模型。首先对附件图片数值化处理并建立矩阵；然后根据图像页边距特点定位最左边和最右边的碎片；按照每张碎片 中的文字部分所在位置，提取同一行碎片，利用互相关函数 横向拼合。 在第一问中，附件一、二仅作横向相关性比较即可；在第二、三问中，需要提取同一行碎片横向拼接，并将横向拼合完整的碎片进行竖向拼合，经过人工干预得到结 果。 最终结果见附录。 关键词：拼接复原；互相关；矩阵；数值化；人工干预

规则碎纸片的拼接复原

论 文 检 测 报 告 报告编号： 5d95e0aadf5149a5a9ef1ecb397c466d 送检文档： 规则碎纸片的拼接复原 论文作者： 陈芳芳 文档字数： 2981 检测时间： 2015-01-07 12:39:34 检测范围： 论文库，中文期刊库（涵盖中国期刊论文网络数据库、中文科技期刊数据库、中文重要学术期刊库、中国重要社科期刊库、中国重要文科期刊库、中国中文报刊报纸数据库等），Tonda论文库（涵盖中国学位论文数据库、中国优秀硕博论文数据库、部分高校特色论文库、重要外文期刊数据库如Emerald、HeinOnline、JSTOR等），资源共享库。 一、检测结果： 总相似比： 36.05% [即复写率与引用率之和] 检测指标： 自写率 63.95%复写率 36.05%引用率 0.0% 相 似 比： 互联网 36.05% 学术期刊 0.0% 学位论文 0.0% 资源共享 0.0% 其他指标： 表格 0 个 脚注 0 个 尾注 0 个

章节抄袭比 36.05% 规则碎纸片的拼接复原 二、相似文献汇总： 序号标题文献来源作者出处发表时间11213年碎纸片拼接复原数模论文互联网互联网 213年碎纸片拼接复原数模论文-豆丁网互联网互联网 32013年全国大学生数学建模竞赛国家一等奖论文B题碎纸片的拼接...互联网互联网 4【图】科密碎纸机 深圳碎纸机 黑金刚碎纸机 可碎光碟 - 罗湖办公...互联网互联网 5一种碎纸自动拼接中的形状匹配方法-《计算机仿真》2006年11期-...互联网互联网 6国家奖碎纸片的拼接还原_百度文库互联网互联网

7基于蚁群优化算法的碎纸拼接-豆丁网互联网互联网 8求2013数学建模题B题(2)的中文原题以及附件3不胜感激_百度知道互联网互联网 9沈阳建筑大学_徐俊杰.郭书恒.唐杰_百度文库互联网互联网 10碎纸机批发,厂家,图片,商贸城-马可波罗网互联网互联网 三、全文相似详情： （红色字体为相似片段、浅蓝色字体为引用片段、深蓝色字体为可能遗漏的但被系统识别到与参考文献列表对应的引用片段、黑色字体为自写片段） 碎纸机，是用来切碎销毁纸张的机器，为了达到废弃文件保密的目的，要把纸张分割成很多的细小纸片，碎纸机切割的纸粒工整利落，能达到保密的效果。随着数据时代发展，大量的政府机关、企事业单位都采用了碎纸机对废弃文件或失效的机密文件进行破碎处理。碎纸方式是指当纸张经过碎纸机处理后被碎纸刀切碎后的形状。市面上有些碎纸机可选择两种或两种以上的碎纸方式。不同的碎纸方式适用于不同的场合，如果是一般性的办公场合则选择段状、粒状、丝状，条状的就可以了。但如果是用到一些对保密要求比较高的场合就一定要用沫状的。随着现代技术的不断发展和市场的需求，现在的碎纸机，除了对纸张的处理，也可以对信用卡、光盘等进行切割。本文研究的只是针对印刷文字文件在碎纸机中被切割的碎片，它是规则的黑白图片，对于非印刷文字文件的碎纸片、彩色碎纸片、形状不规则或边缘有破损的碎纸片等都是该碎纸片拼接技术的重要影响因素。随着科学技术的不断发展，人们对信息交流、存储和销毁的需求也不断的增加。目前，大量政府机关、企事业单位都是用打印机来打印文件，也都采用了碎纸机对废弃文件或失效的机密文件进行破碎处理。当遇到误销毁的文件时，就要靠人工对碎纸片进行拼接，而人工拼接工作量大 ，不仅费力耗时，可能还会出现拼接错误等情况。如果应用当前的图像处理与模式识别技术来开发碎纸片的自动拼接技术，用计算机对所有碎片进行搜索和筛选，对能够在某种指标上匹配的碎片进行拼接复原。这样会大大的提高拼接复原的效率，从而降低了人工的工作量和难度。目前在情报资料碎片整理、司法技术鉴定等领域中, 碎纸的拼接工作大部分都是靠人工的方式完成。虽然国外对这项工作有进行了一些研究, 但是由于碎纸的自动修复技术应用背景的特殊性, 目前几乎没有公开的研究资料可以参考。类似的研究主要是集中在文物碎片的自动修复、虚拟考古、故障分析以及计算机辅助设计、医学分析等领域。所以对规则碎片自动拼接问题的研究，不仅具有广阔的应用前景，而且具有很强的理论意义。问题1：对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（纵切），建立碎纸片拼接复原模型和算法，针对附件1、附件2针对文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。分析：针对问题1，在附件一及附件二中，碎纸片仅纵切 ，则纸片边缘的字有可能出现完整、残缺、标点符、空格四种情况，每个字又由多个像素点组成，故我们利用Matlab图像处理函数imread（）将各个碎片文字像素二值化，并取出代表各个碎片左右两边缘的像素点的列向量，如此在每张碎片左右两边缘所获的值都可组成一组向量，且分别设左边缘 ,右边缘 （ ）。设复原图像的第1列像素为 向量，第72列像素为 向量列，以此类推直到最后一列像素为 。因为原图像的第一列像素全为255（白色），所以可找出 ，从而可以确定 和 对应的 和 ，将该碎纸片数据放入向量A中，再将列向量 逐一与剩下的所有图片的列向量 元素作差，列方向绝对值求和，则和最小的就是能与 匹配的碎片，以此类推。匹配完成后用Matlab图像处

碎纸片的拼接复原数学模型的构建

碎纸片的拼接复原数学模型的构建 发表时间：2014-11-27T14:26:53.797Z 来源：《价值工程》2014年第9月上旬供稿作者：毕楷明[导读] 以纵横方式破碎纸片，利用同行文字行间距一致性的主要特性可解决横向碎纸片的拼接复原问题。Construction of Mathematical Model of Splicing Scrap Recovery毕楷明BI Kai-ming（东北大学理学院，沈阳110819）（NEU College of Sciences，Shenyang 110819，China） 摘要院本文讨论在碎纸机以不同方式破碎纸片的情况下建立碎纸片的拼接复原模型，以解决碎片数量巨大时人工拼接的难题，本文建立了三个具有针对性的模型。 模型一：方差分析法下的碎纸片拼接模型。在以纵切方式破碎纸片的情况下，提取碎纸片左右边缘的灰度列向量，利用碎纸片边缘处为单边同宽空白区域的特殊性对碎纸片进行定位，再利用方差分析法和欧式距离解决了纵切碎纸片的拼接复原问题。模型二：文字行间距一致性的碎纸片拼接模型。以纵横方式破碎纸片，利用同行文字行间距一致性的主要特性可解决横向碎纸片的拼接复原问题，简化了模型，将离散的像素灰度矩阵平均化处理，进而利用欧氏距离对碎纸片进行匹配，得到了碎纸片复原后的完整图片。模型三：二值化Otsu 算法的碎纸片拼接复原模型。本文从双面纵横破碎纸片的问题出发，建立了纸片二值化Otsu 法拼接模型，先对碎纸片分组预处理，为将复杂模型简单化，再利用全局阈值方法中典型的Otsu 法求取碎纸片的最佳阈值，以该阈值对碎纸片中所含灰度值信息进行划分实现二值化处理，将边缘区域明显化，利用统计学方法求取拼接后的纸片间成功匹配的像素点占纸片边缘的概率，最终双面纵横破碎纸片的拼接复原问题得以解决。Abstract: This paper discusses the construction of splicing scrap recovery model under the condition of shredder breaking paper intopieces in different ways, so as to solve the problem of artificial splicing when there is a great amount of pieces. This paper establishes threecorresponding model.Model One: Paper Scrap Splicing Model under Analysis of Variance.Shredding paper through longitudinal mode, the paper selects the gray scraps of paper around the edge extraction column vector,locates the paper scrap by using edge of paper scraps as blank area with same width, then solves the problem of reconstruction of thelongitudinal cutting paper splicing through analysis of variance method and Euclid Distance.Model Two: Paper Scrap Splicing Model with Consistency of Text Line Spacing.Shredding paper through vertical and horizontal mode, its main characteristics of peer text line spacing consistency can solve theproblem of reconstruction of splicing transverse paper scraps, simplifies the model, processes the pixel matrix of discrete in average andmatches the paper scraps through Euclid Distance and then gets the complete picture of paper scrap after recovery.Model Three: Paper Scrap Splicing Model Based on Binaryzation Otsu Algorithm.This paper firstly expounds the double side's vertical and horizontal mode, establishes the paper scrap splicing model based onbinaryzation Otsu algorithm. The paper firstly does preconditioning for paper scraps into groups, simplifies the complex model, and then getsthe optimal threshold of the paper scraps by using typical Otsu algorithm of global threshold method. The paper classifies the gray valueinformation of paper scraps through this threshold to realize binaryzation processing, specifies the edge area, evaluates the probability ofsuccessful matching pixels on edge of splicing paper, and finally solves the mosaic and restoration problems of double side's vertical andhorizontal mode. 关键词院离散；方差分析；置信区间；阈值；Otsu 算法Key words: discrete；analysis of variance；confidence interval；threshold；Otsu algorithm中图分类号院TQ018 文献标识码院A 文章编号院1006-4311（2014）25-0238-031 模型一考虑以为空间拼接情况，为了获取拼接图像所必须的数据，文章以像素为单位离散所得碎片：利用VC++使用了Windows.H 头文件并调用RGB 等结构定义获得不同像素点的g 值[1]，生成了多个灰度矩阵。由于本题主要研究碎片的拼接，故只需考虑碎片的边缘部分，故分别提取全部碎片的最左侧和最右侧的g 值列向量：文章分别找出其中最左侧g 值列向量的值全为255（即像素全白）的和最右侧g 值列向量的值全为255 的两个碎片，于是左侧g 值全为255 的碎片对应左一位置，同理右侧g 值全为255 的碎片对应左一位置。再考虑剩余的碎片（本文中考虑18 个碎片）的对号入座问题，使最左侧碎片分别与其他碎片的最左侧灰度g 值列向量进行相同y 值下作差，得到不同碎片的G 差。先求出左一位置碎片最右侧g 值列向量：

碎纸片拼接复原问题研究

基于旅行商规划模型的碎纸片拼接复原问题研究 摘要 本文分别针对RSSTD(Reconstruction of Strip Shredded Text Document）、RCCSTD(Reconstruction of cross-cut Shredded Text Document)和Two-Sides RCCSTD三种类型的碎纸片拼接复原问题进行了建模与求解算法设计。首先我们对于RSSTD问题，建立了基于二值匹配度的TSP模型，并将其转化为线性规划模型，利用贪心策略复原了该问题的中文和英文碎片；然后对于RCCSTD问题，由于中英文字的差别，我们分别建立了基于改进误差评估的汉字拼接模型和基于文字基线的误差评估的英文字拼接模型，并利用误差评估匹配算法，复原了该问题的中文和英文碎片；随后我们针对正反两面的RCCSTD 问题，利用基线的概念将正反两面分行，转化为RCCSTD问题，并复原了该问题的英文碎片。最后，我们对模型的算法和结果进行了检验和分析。 ◎问题一：我们针对仅纵切的情况，首先将图像进行数字化处理，转换为了二值图像，然后得到各图像的边缘，并计算所有碎片与其他碎片边缘的匹配程度。然后，根据两两碎片之间的匹配程度建立了TSP模型，并将其划归为线性规划模型。最终，我们根据左边距的信息确定了左边第一碎片，随后设计了基于匹配度的贪心算法从左向右得到了所有碎片的拼接复原结果。结果表明我们的方法对于中英文

两种情况适用性均较好，且该过程不需要人工干预。 ◎问题二：我们针对既纵切又横切的情况，由于中英文的差异性，我们在进行分行聚类时应采用不同的标准。首先根据左右边距的信息确定了左边和右边的碎片，随后分别利用基于改进误差评估的汉字拼接模型和基于文字基线的误差评估模型，将剩余的碎片进行分行聚类，然后再利用基于误差评估的行内匹配算法对行内进行了拼接，最终利用行间匹配算法对行间的碎片进行了再拼接，最终得到了拼接复原结果。对于拼接过程中可能出现误判的情况，我们利用GUI 编写了人机交互的人工干预界面，用人的直觉判断提高匹配的成功率和完整性。 ◎问题三：我们针对正反两面的情况，首先根据正反基线信息，分别确定了左右两边的碎片，然后利用基线差值将其两两聚类，聚类以后其正反方向也一并确定，随后我们将其与剩余碎片进行分行聚类，最终又利用行内匹配和行间匹配算法得到了最终拼接复原结果。其中，对于可能出现的误判情况，我们同样在匹配算法中使用了基于GUI的人机交互干预方式，利用人的直觉提高了结果的可靠性和完整性。 关键字：碎片复原、TSP、误差评估匹配、基线误差、人工干预

碎纸片的拼接复原的数学模型

碎纸片的拼接复原 摘要 本文主要采用了模糊模型识别、灰度相关、傅里叶变换等方法对碎纸自动拼接进行了深入探讨。 文中主要结合司法物证复原、历史文献修复、军事情报获取这一背景，针对横纵切碎自动拼接展开探究。提出一种基于最大梯度和灰度相关的全景图拼接法。同时采用边界提取法使图像预处理达到最好的效果，期间采用傅里叶变换对图像进行处理，最后再利用匹配准则等方法处理图像的拼接。最终应用模糊模型识别法建立模型，通过隶属函数的建立实现最终的碎纸拼接。期间有些碎纸片计算机无法识别，需要进行人工干预，从而才能得到一副完整的复原图。 图像拼接的主要工作流程可以概括为以下三个步骤： （1） 对图像碎片进行预处理，即对物体碎片数字化，得到碎片的数字图像。 （2） 图像碎片匹配，通过匹配算法找到相互匹配的图像碎片。 （3） 图像碎片的拼接合并，将相互匹配的图像碎片拼接在一起得到最终结果。 ! 针对问题一：将图像导入MATLAB 进行相应的转化，由于数据量较大，所以 对数据进行优化提取。计算提取数据的均值与方差，找出其模糊集，建立符合题意的隶属函数。由于模糊集的边界是模糊的，如果要把模糊概念转化为数学语言，需要选取不同的置信水平(01)λλ≤≤ 来确定其隶属关系，从而实现纵切图像的全景拼接。（如表一、表二） 针对于问题二：由于是横纵切碎纸片，所得图像较多，采用提取像素法对图片进行灰度分析，通过中介量阈值的确定来找出像素点的差别，梯度值在这一过程中也是作为衡量两张碎纸片是否匹配的标准。从而对数据进行处理，最后导入MATLAB 软件实现拼接。（如表三、表四） 针对问题三：它是在问题一和问题二上加深了难度，采用提取像素点，傅里叶变换，灰度相关、模糊相似优先比等方法对问题进行分析，通过（0,1）矩阵的简化运算以及傅里叶变换得到最后的结果，但对于傅里叶变换需说明一点，变换之后的图像在原点平移之前四角是低频，最亮，平移之后中间是低频最亮，也就是说幅角比较大。此过程中同时也需要人工干预，最终实现拼接。（如表五、表六）

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

2013高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：西华大学 参赛队员 (打印并签名) ：1. 杨尚安 2. 刘洋 3. 叶军 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 2013 年 09 月 15 日赛区评阅编号（由赛区组委会评阅前进行编号）：

2013高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国评阅编号（由全国组委会评阅前进行编号）：

碎纸片的拼接复原

全国大学生数学建模竞赛论文格式规范 本科组参赛队从A、B题中任选一题，专科组参赛队从C、D题中任选一题。（全国评奖时，每个组别一、二等奖的总名额按每道题参赛队数的比例分配；但全国一等奖名额的一半将平均分配给本组别的每道题，另一半按每题论文数的比例分配。） 论文用白色A4纸打印；上下左右各留出至少2.5厘米的页边距；从左侧装订。 ●论文第一页为承诺书，具体内容和格式见本规范第二页。 ●论文第二页为编号专用页，用于赛区和全国评阅前后对论文进行编号，具体内容和 格式见本规范第三页。 ●论文题目、摘要和关键词写在论文第三页上（无需译成英文），并从此页开始编写 页码；页码必须位于每页页脚中部，用阿拉伯数字从“1”开始连续编号。注意：摘要应该是一份简明扼要的详细摘要，请认真书写（但篇幅不能超过一页）。 ●从第四页开始是论文正文（不要目录）。论文不能有页眉或任何可能显示答题人身 份和所在学校等的信息。 ●论文应该思路清晰，表达简洁（正文尽量控制在20页以内，附录页数不限）。 ●引用别人的成果或其他公开的资料(包括网上查到的资料) 必须按照规定的参考文 献的表述方式在正文引用处和参考文献中均明确列出。正文引用处用方括号标示参考文献的编号，如[1][3]等；引用书籍还必须指出页码。参考文献按正文中的引用次序列出，其中书籍的表述方式为： [编号] 作者，书名，出版地：出版社，出版年。 参考文献中期刊杂志论文的表述方式为： [编号] 作者，论文名，杂志名，卷期号：起止页码，出版年。 参考文献中网上资源的表述方式为： [编号] 作者，资源标题，网址，访问时间（年月日）。 ●在论文纸质版附录中，应给出参赛者实际使用的软件名称、命令和编写的全部计算 机源程序（若有的话）。同时，所有源程序文件必须放入论文电子版中备查。论文及源程序电子版压缩在一个文件中，一般不要超过20MB，且应与纸质版同时提交。 （如果发现程序不能运行，或者运行结果与论文中报告的不一致，该论文可能会被认定为弄虚作假而被取消评奖资格。） ●本规范中未作规定的，如排版格式（字号、字体、行距、颜色等）不做统一要求， 可由赛区自行决定。 ●在不违反本规范的前提下，各赛区可以对论文增加其他要求（如在本规范要求的第 一页前增加其他页和其他信息，或在论文的最后增加空白页等）。 ●不符合本格式规范的论文将被视为违反竞赛规则，无条件取消评奖资格。 ●本规范的解释权属于全国大学生数学建模竞赛组委会。 [注] 赛区评阅前将论文第一页取下保存，同时在第一页和第二页建立“赛区评阅编号”（由各赛区规定编号方式），“赛区评阅纪录”表格可供赛区评阅时使用（各赛区自行决定是否在评阅时使用该表格）。评阅后，赛区对送全国评阅的论文在第二页建立“全国统一编号”（编号方式由全国组委会规定，与去年格式相同），然后送全国评阅。论文第二页（编号页）由全国组委会评阅前取下保存，同时在第二页建立“全国评阅编号”。 全国大学生数学建模竞赛组委会 2013年8月26日修订

碎纸片拼接复原数模论文b

碎纸片拼接复原数模论 文b Revised as of 23 November 2020

2013高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：重庆XX大学 参赛队员 (打印并签名) ：1. 祝XX 2. 冯XX 3. 周XX 指导教师或指导教师组负责人 (打印并签名)：张XX （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 20XX 年 X 月 XX 日赛区评阅编号（由赛区组委会评阅前进行编号）：

碎纸片的拼接复原论文

碎纸片的拼接复原 摘要 本题旨在解决碎纸片拼接问题。在本题中我们使用 MATLAB软件，首先对图像进行数据化处理和标准化处理。 一：只有纵切情况，且所有的切口都切到了字，建立差和法检验模型，应用枚举法，用MATLAB计算任意两张碎纸片灰度矩阵中最左、最右列灰度值的差方和，将差方和最小的两张碎纸片拼接在一起.中间不经过人工干预。最后得到中英文碎纸片的排列顺序，从左到右依次为： 中文：08,14,12,15,03,10,02,16,01,04,05,09,13,18,11,07,17,11,06; 英文：03,06,02,7,15,18,11,00,05,01,09，13,10,08,12,14,17,16,04。 二：首先对中英文碎纸片分别提取行间距相同和英文字符三线分割后空白带宽相同的特征，根据这些特征我们初步筛选出可能处于同一“行”的碎纸片，为了不与原文中书写的字的“行”发生误会，我们称其为组，然后分别依次进行“组内调整和组间拼接”工作。中文文件拼接复原过程中采用差方法计算出关联度，然后利用改进的匈牙利算法选出全局中的局部最佳拼接，再结合人工干预，实现组内拼接和组间拼接；英文文件拼接复原与中文的略有不同，首先分析图像选出可能成为最左边的碎纸片，采用以相关系数法，，从而从左向右拼接，最后完成拼接复原。下面分别选取中英文碎纸片拼接复原后的第一行碎纸片的序号作为样品。按照从左到右的顺序： 中文：49，54，65，143，186，2，57，192,178,118,190,95,11,22,129,28,91,188,141；英文：191，75,11，154,190,184,2,104,180,64,106,4,149,32,204,65,39,67,147。 三：考虑到问题二中对英文碎纸片的拼接所提取的特征在大量数据时会 产生分组效果不佳的问题，采用新的方法重新提取行间距特征：靠近碎片底端最 近的一行中完整字母集中分布的最低点到碎纸片底端的距离。并在求解模型基础 上通过定义匹配错误率。建立利用双面打印文件的其中一面作为拼接面，另一面 作为验证面对分组结果交叉检验的拼接检验交互模型，从而有效完成并验证拼接 双面打印文件的拼接复原任务。 关键字：差方法匈牙利算法相关系数行间距特征拼接检验交互模型 1

2013国赛B题碎纸片的拼接复原

2013高教社杯全国大学生数学建模竞赛题目 （请先阅读“全国大学生数学建模竞赛论文格式规范”） B题碎纸片的拼接复原 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 【数据文件说明】 (1)每一附件为同一页纸的碎片数据。 (2)附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。 (3)附件3、附件4为纵横切碎片数据，每页纸被切为11×19个碎片。 (4)附件5为纵横切碎片数据，每页纸被切为11×19个碎片，每个碎片有正反两面。该附 件中每一碎片对应两个文件，共有2×11×19个文件，例如，第一个碎片的两面分别对应文件000a、000b。 【结果表达格式说明】 复原图片放入附录中，表格表达格式如下： (1)附件1、附件2的结果：将碎片序号按复原后顺序填入1×19的表格； (2)附件3、附件4的结果：将碎片序号按复原后顺序填入11×19的表格； (3)附件5的结果：将碎片序号按复原后顺序填入两个11×19的表格； (4)不能确定复原位置的碎片，可不填入上述表格，单独列表。

碎纸片的拼接复原问题

2013高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：

碎纸片的拼接复原问题 摘要 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。本文针对已给图像先进行了图片灰度二值化处理得到碎纸片的像素矩阵，提取碎纸片的边缘像素矩阵，对边缘矩阵进行相似度分析，相似度的度量采用向量距离平方和最小化，在相似度度量中设置阈值、对相近相似度的候选纸片进行人工干预、对数据量较大的附件，采用文本特征，如页边距、行距进行筛选，降低计算量，提高计算精度。使用Matlab软件编程实现了上述算法，在对附件的拼接中通过少量的人工干预，可实现纸片的完整拼接，效果较好。 关键词：相似度；文字特征；碎纸片拼接；Matlab；

1 问题重述 1.1 问题的描述 设计一个碎纸片的自动拼接模型，以提高碎纸片的拼接复原效率。 1.2 问题的要求 （1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。 （2）对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 （3）从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 1.3 问题的分析 对破碎文件这类边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎纸片内的字迹断线或碎片内的文字内容是否匹配，然而由于理论和技术的限制，让计算机具备类似人那种识别破碎边缘地字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。但是分析了基于几何特征的碎纸片自动拼接方法的缺点,研究了碎纸片内文字行特征以及行特征获取方法。利用这些信息进行拼接，其拼接效率无疑比单纯利用边界几何特征方法要好些。 另一方面由于计算机数字分析图像能力的缺陷，让计算机对碎片进行完全意义上的自动化拼接也几乎不大可能，这就需要我们在拼接过程加入人工干扰过程，对一些碎片进一步分析结果舍弃或拼接待选。 2 模型假设和符号系统

碎纸片拼接复原的数学模型与实现

碎纸片拼接复原的数学模型与实现 摘要碎纸拼接,就是利用计算机将碎片复原.如果碎片的数量过大,手工拼接会费时费力. 本文利用MATLAB实现碎片自动拼接,解决了如何复原一个纵切印刷文字文件破碎纸片,如何复原一个即纵切又横切的印刷文字文件破碎纸片,如何复原一个即纵切又横切的双面印刷文字文件破碎纸片. 关键词碎纸片;像素;灰度;邻接;MATLAB;复原. 中图分类号0141.41 Mathematical model stitching scraps of paper and achieve recovery （School of Mathematics and Statistics，Hexi University，Zhangye，Gansu，734000）Abstract:Shredding splicing, is to use the computer to recover the debris. If the number of fragments is too large, hand-stitching dues when consuming. In this paper, using Matlab automatic mosaic fragments, Addresses how to recover a broken piece of paper slitting printing text documents, How to recover a longitudinal and transverse to that file fragmentation paper printed text, How to recover a longitudinal and cross that double-sided printed paper text file fragmentation. Keywords:Scraps of paper; Pixel; Grayscale; Adjacency; Matlab; Recovery. 1 问题重述 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统上,拼接复原工作需由人工完成,准确率较高,但效率很低.特别是当碎片数量巨大,人工拼接很难在短时间内完成任务.随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率.现给出下列三种情形 (1)对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切）,建立碎纸片拼接复原模型和算法,如针对给出的同一页中文文件（图片集1）的碎片数据进行拼接复原. (2)对于碎纸机既纵切又横切的情形,建立碎纸片拼接复原模型和算法,如针对给出的同一页中文文件（图片集2）的碎片数据进行拼接复原. (3)上述所给碎片数据均为单面打印文件,从现实情形出发,还可能有双面打印文件的碎纸片拼接复原问题需要解决.现给出一页英文印刷文字双面打印文件（图片集3）的碎片数据. 图片文件说明： (1)每一图片集为同一页纸的碎片数据. (2)图片集1为纵切碎片数据,每页纸被切为19条碎片（随机编号为00-19）. ?个碎片（随机编号为(3)图片集2为纵横切碎片数据,每页纸被切为1119 000-208）. (4)图片集3为纵横切碎片数据,每页纸被切为1119 ?个碎片,每个碎片有正反两面.

2013年数学建模B题碎纸片的拼接复原

B题　碎纸片的拼接复原 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： 1．对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。 2．对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3．上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 【数据文件说明】

（1）每一附件为同一页纸的碎片数据。 （2）附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。 （3）附件3、附件4为纵横切碎片数据，每页纸被切为 11×19个碎片。 （4）附件5为纵横切碎片数据，每页纸被切为11×19个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有2×11×19个文件，例如，第一个碎片的两面分别对应文件 000a、000b。 【结果表达格式说明】 复原图片放入附录中，表格表达格式如下： （1）附件1、附件2的结果：将碎片序号按复原后顺序填入 1×19的表格； （2）附件3、附件4的结果：将碎片序号按复原后顺序填入11×19的表格； （3）附件5的结果：将碎片序号按复原后顺序填入两个 11×19的表格；

碎纸片的拼接复原问题大学生数学建模全国一等奖论文

碎纸片的拼接复原问题 摘要 为解决碎纸片的拼接复原问题，我们通过定义差异度指数、高度差，建立0-1规划模型，使用聚类分析、MATLAB搜索算法和人工干预等相结合，得到了所有附件复原序号和复原图片。 针对问题一，首先提取附件1、2中所有碎片左侧和右侧边缘灰度，通过任意列碎片右侧和任意列碎片左侧的边缘灰度差值可以定义差异度指数，从而得到差异度特征矩阵，然后建立0-1规划模型，以第i张碎片右侧与第j张碎片左侧差异度最小为目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件。算法为先提取任意张碎片边缘灰度值，得到差异度矩阵，带入规划模型中，通过LINGO软件找到中英文碎片的拼接方法，得到复原序号如表一、表二，从而得到出中文与英文复原图片。 表一:中文碎片的复原序号 表二：英文碎片的复原序号 片拼接方法。结果表明两种方法得出的中英文复原顺序相同，复原图片相同，同时人工检验中英文复原图片中无明显语法、单词错误，证明复原图片准确。 针对问题二，由于每张碎片有左侧、右侧和上侧、下侧，与问题一相同，可以定义两个差异度指数，建立双目标0-1规划模型。但由于差异度矩阵过大，决策变量复杂，我们又建立了改进的简化模型，定义高度差，运用聚类分析方法，按照高度不同将所有碎片分为18类，然后再以第j块碎片左侧与第i块碎片右侧的差异度最小为目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量，以每块碎片右侧一定与某块碎片左侧相连、每块碎片左侧一定与某块碎片右侧相连，满足高度差阈值为约束条件，建立单目标0-1规划模型。算法为先提取任意块碎片边缘灰度值和高度，得到差异度矩阵，编程将中文碎片按高度分为18类，人工干预分为11行，再利用问题一中碎片纵向复原方法，得到中文复原序号，画出中文复原图片。（英文复原模型相似，仅高度差阈值不同） 针对问题三，对于双面英文碎片的复原问题，我们提出了单词残缺程度的定义，定量的描述了英文碎片的特征信息，构成了算法的核心内容，运用编程和人工干预将碎纸片分为11类，每类19个碎片，在此基础上利用前两问所建的0-1规划模型，再加上双面的一些约束条件，得到双面英文复原序号，并绘出英文双面复原图片。 关键词：差异度指数；0-1规划；LINGO软件；聚类分析；高度差；残缺程度；

碎纸片的拼接复原.

碎纸片的拼接复原 摘要 本文利用MATLAB软件将附件图像数字化，把图像转化为灰度矩阵进行处理。 问题一，本文利用边缘匹配模型和灰度匹配模型对碎纸片的边缘作分析。基于，边缘部分的黑白分布越相近，两者相连的可能性越高的原理，得到附件1的排序是008，014，012，015，013，010，002，016，001，004，005，009，013，018，011，007，017，000，006 。附件2的排序是003，006，002，007，015，018，011，000，005，001，009，013，010，008，012，014，017，016，004。 问题二，本文首先按行将小块进行分类，以简化模型。在附件3中，将碎纸片分组，对分完组后的碎纸片采用字体矩形模型，实现同行间排序，将得到的行再通过匹配模型，从而拼出原文。而对于附件4，本文建立四线格位置模型，将碎纸片进行分组。计算过程中发现部分标号基线相同，但却与不同的行对应匹配，此时进行人工干涉。然后运用行内匹配模型，对同行间的碎纸片排序。附件3、附件4的排序结果见附录一。 关键词：灰度矩阵，匹配模型,相关性分析,三线格基线,人工干涉,最优化

一.问题重述 破碎文件的拼接一直以来都以人工为主，其准确度较高，但效率较为低下，不能承担短时间内完成巨大数量的碎片拼接任务，遏制了在司法物证复原、历史文献修复以及军事情报获取等领域的进一步发展。随着计算机技术的发展，我们尝试运用计算机软件来实现对破碎文件的迅速拼接。现问题如下： （1）、对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。 （2）、对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 说明：附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。附件3、附件4为纵横切碎片数据，每页纸被切为11×19个碎片。其中每一附件为同一页纸的碎片数据。 二.模型假设 1.附件中所给的拼接碎纸片毫无缺失。 2.附件中的英文严格按照四线格方式打印。 3.机器印刷时的字间距和行间距大致相同。 4.碎纸机切割图片是垂直的。 5.碎纸机切割的碎纸片大小相同、质地均匀。 6.所有的碎纸片由同一碎纸机切割。 7.每个附件中所有的碎纸片来自于同一页文字文件。 三．符号说明 符号符号说明 ,R r相关系数 M灰度矩阵 Y碎纸片左边缘矩阵 1 Y碎纸片右边缘矩阵 2 ai编号为i的碎纸片，第j行k列的灰度值 ,j k (), R u v相关系数 四．问题分析 碎纸片拼接技术是模式识别领域中一个较为新颖但很典型的应用。他涉及到数字图