承 诺 书
我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 指导教师或指导教师组负责人 (打印并签名) ： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）
日期： 年 月 日 赛区评阅编号（由赛区组委会评阅前进行编号）：
编 号 专 用 页
赛区评阅编号（由赛区组委会评阅前进行编号）：
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（全国组委会评阅前进行编号）：
碎纸片拼接复原
摘要
本文主要是研究关于分割图片处理——汉字碎片拼接问题。
针对问题一，首先将附件1图片用像素表示并进行二值化量化处理，用迭代法求出最佳阈值，将抽象的图片用具体的0-1矩阵表达；其次根据像素值分布用MATALAB 筛选出最左列碎纸片的编号为008；最后用欧氏距离法建立像素匹配模型，通过MATALAB 直接得到中文的拼接图片（见附录一）及序列（见文中表一），不需要进行人工干预。并根据像素匹配模型也完成英文图片（见附录一）的自动拼接（见文中表二），说明该模型的适用性较好。
针对问题二，首先将灰度图片用像素量化成11 19的矩阵，再将繁杂的像素矩阵通过聚类的方法利用MATALAB 分为11个集合，最后在集合范围内建立分步像素匹配模型，用MATALAB 匹配拼接出中文图片（见附录二）和序列（见文中表三）。特别地，对于英文碎纸片，需要对分步像素匹配模型的基线确定用黑色像素比例突变的原则进行改进，再用MATALAB 根据改进后模型匹配出英文图片（见附录二）和序列（见文中表四），在每行利用计算机拼接的过程中采用人工识别剔除错误的匹配，然后利用人机交互方式完成拼接。
针对问题三，在实际情况中，一张打印文件往往是正反两面，在用距离匹配法进行碎纸片的复原时使得误差增加，也增加了人工干预的次数。充分利用碎纸片有两面的特征，让其一面作为匹配面，另一面作为检验面，用求解两碎纸片灰度矩阵相邻列之间的欧式距离的思想，最终建立了双目标规划的数学模型，既要满足匹配面的约束，又要满足检验面的约束。在MATALAB 下编程求解，并加上人工干预最终得到了碎纸片的复原结果（见附录三），在每行利用计算机拼接的过程中采用人工识别剔除错误的匹配，然后利用人机交互方式完成拼接。
本文的优点在于文中的模型除了能复原题目所给定的已知行数、列数的碎纸片，还能复原出任何行数、列数的情况。
关键词：像素量化 欧氏距离 聚类分析 双目标规划
一、问题重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：
1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。
2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。
3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。
二、基本假设
1、 假设题目所给的附件中的碎纸片文件图片的切口是完全水平的； 2、 假设碎纸片与碎纸片之间不存在错位的情况；
3、 假设碎纸片切口是干净的，没有污渍，也没有噪声的污染；
4、 假设中文、英文在间距、高度以及宽度上的差异对像素匹配模型没有影响； 5、 假设在图片二值化时的灰色像素可以近似按最佳阈值归化为白色或黑色； 6、 假设英文的笔画均匀，且可以量化为固定像素值；
7、 假设一张英文碎纸片中最多可以容纳4个完整的英文字母。
三、符号说明
m x ij ：第m 个像素值量化矩阵的第i 行j 列交叉位置上的元素的值；
f (x , y )：点(x , y )的灰度值；
T ：阈值；
(j )(j )N 1, N 2：第j 次迭代时区域C 1和C 2像素个数；
d ：两像素量化矩阵的欧式距离值；
x ：像素值；
X m ：第m 个像素量化矩阵；
m h n ：像素矩阵中第m 行第n 列碎纸片基线的纵坐标；
βi ：像素矩阵中第i 行黑色像素所占总像素比例；
u ：像素量化矩阵中第i 行0的个数；
i
U i ：像素量化矩阵中第i 行像素点总数;
四、模型的分析、建立与求解
4.1问题一的模型分析、建立与求解
从附件1中我们可以得到19张仅纵切的中文碎纸片图片，首先将每个图片按像素值进行二值化量化，可以得到19个1980⨯72的矩阵，再提取每个矩阵的最左与最右的像素值用绝对值距离法建立像素匹配模型，从边界第一张编号为008入手，依次得出中文图片的顺序。由于英文和中文一样可以量化为像素，故同理可得英文拼接方案。 4.1.1图像二值化量化
二值化是图像处理的基本技术，目的是将图像增强结果转换成黑白二值图像，从而能清晰地得到边缘特征线，更好的为边缘提取、图像分割以及目标识别等后续工作服务。其原理是将所有灰度大于或等于阀值的像素判定为属于特定物体，其灰度值用1表示，否则这些像素点被排除在物体区域以外，用灰度值0表示背景或者例外的物体区域。
用x ij 表示第k 个像素值量化矩阵的第i 行j 交叉位置上的元素值，利用二值化处理可得：
k
白)⎧1(x ij =⎨
⎩0(黑)
k
f (x , y )≥T f (x , y )
(i =1, 2 1980; j =1, 2 72; k =1, 2 19)
接下来用迭代法确定阈值T ：
（1）选择图像的平均灰度值作为初始阈值T j =224，其中j 为迭代次数，初始值j =0。
（2）用T j 分割图像，将图像分割为2个区域C 1和C 2 （3）计算两区域的平均灰度值
(j )(j )
u
(j )
1
=
1
N
j 1
f (x , y )∈
∑f (x , y )
C 1
(j )
u
(j )
2
=
1
N
j 2
f (x , y )∈
∑f (x , y )
C 2
(j )
（4）再计算新的阈限值，即：
T
1=j +1
(j )
+22
(j )
（5）重复（2）~（4），直到T j 与T j +1的差几乎为0时，停止迭代，显示最佳阈值T 。
由MATALAB 循环运行此算法程序，得到最佳阈值T =250。
4.1.2建立像素匹配模型
本文首先提取每个矩阵最左边与最右边的像素值作为每个碎纸片图片的特征，利用这1980⨯1的矩阵建立像素匹配模型。
（1）由于文字文件边缘是完整且存在一定的边距，即:
x x
k i 1
=1
(k =1, 2 , 19; i =1, 2 , 1980)
筛选出编号008在该文本文件的最左边。 同理：
k i 72
=1
(k =1, 2 , 19; i =1, 2 , 1980)
可得编号006在文本文件的最右边。 （2）由于在碎纸片边缘是连续关联的，则断裂处的像素点理论上应该是完全吻合，故提取的最右边的像素值与最左边的像素值用欧式距离法建立像素匹配模型：
d =min (d
i =1
k
)
(k =1, 2 18)
其中：
d k =
∑x
k +1
-x i 1i 72k
(k =1, 2, , 18)
d
k
：
4.1.3模型的求解
根据像素匹配模型，通过MATALAB 循环匹配程序可直接得出拼接完善的中文图片，且不需要人工干预，最终拼接的中文序列见表1：（详情见附录中附件一）
（表一）
由于英文与中文一样是可以用像素量化的图片，故英文碎片可以直接用上述模型进行复原，通过MATALAB 编程可以直接得出拼接完善的英文图片，且不需要人工干预，最终拼接的英文序列见表二：（详情见附件中附录一）
（表二）
通过对英文图片的自动拼接，可以验证像素匹配模型对碎片拼接的适用性较好。
4.2问题二的模型分析、建立与求解
分析附件3中11⨯19张碎纸片，首先将图片用像素量化，由于文本既有纵切又有横切，采用二值化将图片转换为0-1矩阵的误差比较大，故优化模型采用不同灰度色阶来量化，得到相应的数学矩阵；
由于本题中的碎纸片较多，若采用模型一则工作量大且精度不高，故本文第一步将碎纸片进行聚类，第二步在聚类的基础上进行分步匹配，在计算机不能智能识别的情况下给予适当的人工干预。 4.2.1对灰度图片的像素量化
把有黑-灰-白连续变化的灰度值量化为256个灰度级，灰度值的范围为0~255，表示亮度从深到浅，对应图像中的颜色为从黑到白，即：
当像素点为白色，像素值x 为255； 当像素点为黑色，像素值x 为0；
当像素点为灰色，像素值x ∈(0, 255) 。
4.2.2筛选出边缘碎纸片
由于文字文件边缘是完整且存在一定的边距，用x ij 表示第m 个像素值量化矩阵的第i 行j 列交叉位置上的元素值，则X 矩阵所对应的前t 列向量值应该全
m
m
为255（即白色），即：
⎛m
x 11m
X = m
x 180⨯1 ⎝
其中x i 1=
m
⎫⎪ ⎪ ⎪m
x 180⨯72⎪⎭
x
m
1⨯72
x i 2= =x it =255
m m
(i =1, 2 , 180)。
确定t 值：
即筛选出符合条件的11张最左列的碎纸片，分别编号为49、61、168、38、14、94、125、29、7、71、89。
同理可得最右边列的11张碎纸片编号分别为：141、36、18、74、176、43、 145、19、196、60、123。
4.2.3模型的建立 一）聚类模型的建立 （1）数据处理
将像素量化的矩阵再坐标化，即以每个矩阵左上角为坐标原点，向右为横轴正方向，向下为纵轴正方向，以像素点作为坐标增量，可得每个像素点对应一个坐标(x , y )。
（2）确定聚类依据
由于同一字体的汉字具有相同的高度和宽度，即同一行文字的最下端都位于同一条基线上即同一高度上，该特征则可以作为聚类的依据。本文设定在像素量化矩阵中从有0（即黑色）行突变为全为255（即白色）行的界限作为汉字向下对齐的基线，并用MATALAB 记下该基线纵坐标。
由于文本文件切割为11行，则由（1）筛选出的最左边列(x m ,..., x m ) i 1180⨯1
T
作为聚类的11个起始样本，但是印刷文本段落的起始行需要空两字符才开始，若刚好从段前空的两字符出切割，则最左边列的基准线就不能作为该行的等高线来匹配，故此时需要人工干预将最左边列分为两类：
I 类→段落起始行在空格处切割的碎纸片→编号为：014、029、071、089 II 类→不存在上述情况的碎纸片→编号为：007、038、049、061、094、125、168。
针对第I 类，用（1）筛选出的最右列(x m 样本。
针对第II 类，用（1）筛选出的最左列(x m ,..., x m
i 1
180⨯1)
T
m ,..., x 180⨯72) 作为聚类的起始i ⨯72
T
作为聚类的起始样
本。
（3）建立模糊聚类模型
⎧1=1= =1
h 19
⎪h 1h 2
1⎨
⎪11=11= =11
h 19 ⎩h 1h 2
（4）模型的求解
根据模糊聚类模型，通过MATALAB 逐次循环程序可以将11⨯19的像素量化矩阵聚类到以起始样本为目标的11个集合A , B , , K 中.
所有的碎纸片聚类结
果为：
⎧⎧集合A :以编号为049为起始，141为末端的行⎪⎪
059为末端的行⎪I 类⎪集合B :以编号为029为起始，
⎪⎨集合C ：以编号为071为起始，060为末端的行⎪⎪
123为末端的行⎪⎪⎩集合D ：以编号为089为起始，
⎪196为末端的行⎧集合E :以编号为007为起始，⎪⎪
074为末端的行 ⎨⎪集合F :以编号为038为起始，
⎪⎪集合G :以编号为049为起始，141为末端的行⎪⎪II 类为起始，036为末端的行⎪⎨集合H :以编号为061⎪⎪集合I :以编号为094为起始，043为末端的行⎪⎪⎪⎪集合J :以编号为125为起始，145为末端的行⎪⎪
168为起始，018为末端的行⎩集合K :以编号为⎩
二）分步像素匹配模型的建立
碎纸片边缘是连续关联的，则断裂处的像素点理论上应该是完全吻合，因为本问题横切与纵切同时存在，则需要横向和纵向都分别匹配，首先对聚类的每一样本集用欧氏距离法通过MATALAB 来横向匹配，得到11个横向切割的碎纸条，再将碎纸条进行纵向拼接。 （1）分步像素匹配模型的建立
d =min (d )(n =1, 2 18)
n
其中：
d n =
∑x
180i =1
m 1
il
-x il 2
m
(m , m ∈A , B , , K ; n =1, 2 , 18)
1
2
d 值越小，就代表两碎纸片越匹配。
针对横向匹配，由于文本的行距要大于间距，所以在横向分割时切断白色间隔区域的概率远远大于切断黑色汉字的概率，故此时要将11行碎纸条聚类：
P 类→横向切割线位于全是白色空隔区域
Q 类→横向切割线位于黑色汉字区域
首先，运用上述模型匹配Q 类，再根据行与行之间的笔画或句意人工干预拼接P 类。
4.2.5人工干预及最终复原结果 1）时间节点：像素矩阵聚类时
干预方式：由于基线的匹配导致集合A , B , , K 不能得到预想的19个元素，
如集合A 中筛选出了24个类似与编号049同行的元素，此时就人工干预剔除不合理的5个像素矩阵。这里一共有8个矩阵不合理，故需要人工干预8次。 2) 时间节点：碎纸条纵向拼接时
干预方式：由于P 类的边缘像素值都是255（即为白色），计算机无法识别没有笔迹特征的碎纸条，故需要人工来拼接，P 类有3个元素，故需要3次人工干预。
用MATALAB 程序循环匹配得出最终汉字排序为见表三（详图见附录二）
（表三）
4.2.6英文碎纸片的拼接处理
（1）英文碎纸片拼接模型的改进 由于英文字母宽度、大小不一且高度也不相等，故不能以中文的聚类依据一概而论，必须对模型进一步的改进。
经过观察发现单词图像可以分成3个部分：上区、中区和下区，单词内绝大多数字母都处于中区，只有少数一些字母会伸展到上区或者下区。故就英文而言可以将中区字母（如a ）的底线作为英文行的基线。
由于英文单词可能由中区、上区、下区三个区域的字母组成，故在基线以下区域像素矩阵不可能全是从存在0（即黑色）突变为全为255（即白色）的情况， 但是可以根据黑色像素占总像素的比例来判断是否发生突变，即：
β
i
=
U
i i
(i =1, 2 , 180; j =1, 2 , 72)
（2）黑色像素比例的判断
通过MATALAB 统计，英文字母每画平均像素为7。当一张英文碎纸片容纳最多的3个完整的英文字母都恰好都是处于下中区时。计算此时下区的黑色像素比例：
3⨯7=βmin 72=29. 12%
由于中区英文字母大多是左右对称图片，即最大黑色像素比例是上区黑色像素比例的两倍。计算此时中区的黑色像素比例：
β
max
=2⨯β
min
=58. 24%
（3）由黑色像素比例突变选择英文基线
根据（2）所得数据，β50%是属于黑色比例较大区域。当之前的前s 行是黑色比例较大，而s +1是黑色比例较小时，即可认为第s 行为该英文行的基线。
通过以上改进和处理，接下来的拼接工作就可以沿用汉字的模型进行拼接。用MATALAB 程序循环匹配得出最终汉字排序为见表四（详图见附件中附录二）
（表四）
4.3 问题三的分析及模型的建立、求解
有了解决第一问，第二问的方法，对于复原单面打印文件碎纸片已经不存在什么问题，但是实际情况中，大部分是双面打印的文件，如果单纯的采用第一二问的方法，会使得与目标图片相关性大的图片的数量增多，这样也就会增加人工干预的次数，所以需在前面方法上加以改进。由于文件是双面打印，一张碎纸片
就有两面，那么我们可以让其中的一面作为匹配面，另一面作为检验面，这样就可以增加匹配的精度。
4.3.1 确定出第一列碎纸片
通过MATLAB 软件处理图片信息的方法得到每张碎纸片的灰度值矩阵, 取出每个矩阵的第一列每个元素的值x i 1(k 表示第k 个灰度值矩阵) ，若x i 1=255，那么该列所对应的碎纸片就是第一列碎纸片。 4.3.2 进行行匹配
匹配面：在第一列碎纸片中选取一张碎纸片作为目标碎纸片，然后计算其它碎纸片的灰度值矩阵的第一列与目标碎纸片的灰度值矩阵的最后一列的距离。用欧式距离计算：
k
k
d =
∑(x -x )
i =1
j
417
m i
2
m
求min(d ) , 当距离最小时所对应的图片与目标图片是相匹配的，其中x 表示目标碎纸片灰度值矩阵的最右边一列值，x 表示其它碎纸片灰度值矩阵最左边的一列值。
检验面：由于与目标碎纸片相匹配的碎纸片可能有多个，即存在多个相同的
min(d ) ，那么这时需要通过目标碎纸片的背面与可能相匹配的多个碎纸片的背
面进行验证，这样就可以很准确的确定哪张碎纸片是与目标碎纸片相匹配的。 需要注意的是：验证时应用目标碎纸片的灰度值矩阵的第一列与可能相匹配的多个碎纸片的灰度值矩阵的最后一列进行距离计算。在进行检验时仍然采用欧式距离计算，只不过变量减少了。
d
1
=
∑(y -y )
k =1
k
m k
2
4.3.3建立双目标模型
通过上述分析，可得双目标模型为：
) ⎧m i n d (
⎨ m i n d () 1⎩
其中
d
=1
∑(y m -y k )
k =1
k
2
，
d
4172
=∑(x m -x i ) 。
i =1
此时所对应的碎纸片才是与目标碎纸片真正相匹配。 接下来在行匹配完成的基础上，要复原出一幅完整的文件，还需对其进行列匹配，进行列匹配的方法仍用距离判别法，求目标碎纸片的灰度值矩阵的最后一行与其它碎纸片灰度值矩阵的第一行的欧式距离，与行匹配计算方法一致。
4.3.3 人工干预及最终复原结果 1）时间节点：确定第一列碎纸片时
干预方式：在MATLAB 求解的第一列碎纸片共有31张，超过了实际中正反两面 第一列共22张的碎纸片，通过人眼识别可以去除掉其中的3张。 2）时间节点：进行行匹配时
干预方式：在MATLAB 中求解出不能进行匹配的碎纸片的编号，然后在附件5中找出所对应的碎纸片，单独放在一边。 3）时间节点：进行列匹配时
干预方式: 在MATLAB 中求解出不能进列匹配的碎纸片的编号，然后在附件5中找出所对应的碎纸片，单独放在一边。
4）时间节点：对既不能作为行匹配的碎纸片，又不能进行列匹配的碎纸片（少数）
干预方式：单独放在一边作为最后的人工匹配时需要的碎纸片。 5）时间节点：大部分碎纸片已经拼接好时
干预方式：通过碎纸片上的字迹进行人工拼接
在进行行匹配和列匹配以及在人工干预的前提下我们最终得到了碎纸片的复原结果，现将复原结果的碎片序号以如下表格给出：
第一面
表五
第二面：
表六
五、模型的评价、改进
5.1模型的优点
1、问题一中，我们碎纸片的灰度值矩阵采用了二值化处理，在进行图片时，没有人工干预，加快了复原图片的速度。
2、问题二中，采用的先聚类再匹配思想将繁杂的无规则像素矩阵分到11个目标集合中再进行集合内部的匹配，降低了编程的难度，减少了匹配的次数。 并且考虑了中文与英文在筛选时的差别，将中文的匹配模型改进后再用来处理英文文本，加大了英文自动拼接的准确性。
3、对于问题三巧妙地将两面打印的文本的一面作为匹配面，另一面作为检验面，提高了碎纸片匹配的精度。
4、文中的模型除了能复原题目所给定的已知行数、列数的碎纸片，还能复原出任何行数、列数的情况。 5.2模型的缺点
二值化处理灰度值数据时存在偏差，它会将不同的灰度值归为一类，对于数据量小的碎纸片误差显然是很大的，在用聚类分析时，也有可能将不是一类的碎纸片归为一类，增加了人工干预的次数。
5.3模型的改进
对于三个问题我们采用了三种不同的办法进行求解，都能够求得相应的结果。但是由于二值化处理灰度值时存在局限性，不可作为推广模型。为了使模型具有普遍使用性，因此在求解复原碎纸片这类问题时，可以用灰度值距离来进行求解。
六、参考文献
【 1 】 Jeremy,灰度图像二值化方法
http://www.docin.com/p-413825845.html,2013/09/14
【 2 】李佳佳 何小海 吴晓红 ,基于网格模板的最小欧式距离准则图像自动拼接技术，《成都信息工程学院学报》，2007/01
【3】罗智中， 基于文字特征的文档碎纸片半制动拼接，
，2013年9月13日。 【 4 】 罗智中 ，基于线段描述的碎纸片边界检测算法研究，
，2013年9月13日。 【 5 】 钟力、胡晓峰，重叠图像拼接算法，
，2013年9月13日。 【 6 】 曾建军、李世航、王永国、叶仁玉、夏惠异，《MATLAB 语言与数学建模》，安徽大学出版社，2005年9月出版。 【 7 】 何正风，《MATLAB 在数学方面的应用》，清华大学出版社出版，最新版。
七、附件
附录一:
附录二：中中文完整的图片文完整的图片 附录三：
第1问英文结果：
附录二：
第2问中文程序结果图（人工干预前）
:
第2问中文（人工干预后）：
第2问英文图片（人工干预前）：
第2问英文结果图（人工干预后）：
附录三：
第3问结果（人工干预前）：
第3问结果（人工干预后）：
附录四：
第1问程序代码：
clear
clc
%图像导入
for i=1:19
if(i
F(:,:,i)=imread(['00',num2str(i-1),'.bmp']);
else
F(:,:,i)=imread(['0',num2str(i-1),'.bmp']);
end
%二值化
B(:,:,i)=im2bw(F(:,:,i),250/255);
%取首位列
Q(:,1,i)=B(:,1,i);
Q(:,2,i)=B(:,72,i);
end
%结果
result=zeros(19,1);
%生成全255矩阵
y=ones(1980,1);
%y=y.*255;
%找首列
% Q(:,1,i)==y
for i=1:19
if(Q(:,1,i)==y)
result(1)=i;%记录序号
end
end
%找尾列
for i=1:19
if(Q(:,2,i)==y)
result(19)=i;%记录序号
end
end
% 中间(17张) 匹配，从首至尾的方向
for i=1:17
%可能情况, 人为干预
% may=zeros(19,1);
% n=1;
d=ones(19,1);
d=d.*(-1);
for j=1:19
fg=0;
for t=1:19
if(j==result(t))
fg=1;
end
end
if(fg==0)
if(i==17)
result(i+1)=j;
break;
end
r=0;%和
for k=1:1980
r=r+(double(Q(k,2,result(i)))-double(Q(k,1,j)))^2; end
%欧氏距离
d(j)=sqrt(double(r));
end
end
%最小距离
if(i~=17)
dmax=max(d);
for k=1:19
if(d(k)==(-1))
d(k)=dmax;
end
end
dmin=min(d);
for k=1:19
if(d(k)==dmin)
result(i+1)=k;
break;
end
end
end
end
disp('最后碎片正确序列：');
result
%图片的保存和显示
picture=[];
for i=1:19
picture=[picture,F(:,:,result(i))];
end
imshow(picture)
% imwrite(picture,'C:\Users\Administrator\Desktop\结果111.bmp','bmp');
附录五
第2问中文程序代码：
clear
clc
%碎片总数
sum=209;
%图像导入
%确定行列数
%生成全255矩阵
y=ones(180,1);
y=y.*255;
raw=0;
%存中间值
temp=zeros(sum,1);
%标志
fw=0;
fb=0;
fg=0;
BW=ones(sum,2);
BW=BW.*(-1);
for i=1:sum
if(i
F(:,:,i)=imread(['00',num2str(i-1),'.bmp']);
elseif(i
F(:,:,i)=imread(['0',num2str(i-1),'.bmp']);
else
F(:,:,i)=imread([num2str(i-1),'.bmp']);
end
%取首尾列
Q(:,1,i)=F(:,1,i);
Q(:,2,i)=F(:,72,i);
%取首尾行
P(1,:,i)=F(1,:,i);
P(2,:,i)=F(180,:,i);
%对左边界空白的碎片计数
if(Q(:,1,i)==y)
raw=raw+1;
temp(raw)=i;
end
%提取碎片的White ，black 值
fw=0;
fb=0;
fg=0;
for j=1:180
%每一列
fw=1;%假设该列为白
for t=1:72
if(F(j,t,i)~=255)
fw=0;%不全白
if(fb==0)
fb=1;
BW(i,1)=j;%黑线位置
end
end
end
if(fw==1&&fg==0)%当前线为全白且没有找到全白的线
BW(i,2)=j;
fg=1;
end
if(fg==1&&fb==1)%找到了
break;
end
end
end
%分类:两类
disp(BW);
i=2;
temp(1:raw)
while mod(sum,raw)~=0
k=raw;
l=1;
del=zeros(raw,1);
for j=1:k
flag=0;
for w=1:180
if(F(w,i,temp(j))~=255)
flag=1;
break;
end
end
if(flag==1)
raw=raw-1;
del(l)=j;
l=l+1;
end
end
%删除不符合条件的碎片
l=1;
while del(l)~=0
temp(del(l))=[];
del(l)=[];
%temp(del(l))=[]会对temp 序号产生改变
while del(l)~=0
del(l)=del(l)-1;
l=l+1;
end
l=1;
end
i=i+1;
end
temp(1:raw)
result=zeros(raw,sum/raw);
result(:,1)=temp(1:raw);
for line=1:11
% 匹配，从首至尾的方向
for i=1:18
%可能情况, 人为干预
may=zeros(209,1);
d=ones(209,1);
d=d.*(-1);
n=1;
ew=0;%全白标记
if(ew==0)%非全白
for j=1:sum
fg=0;
for t=1:19
for tt=1:11
if(j==result(tt,t))
fg=1;
end
end
end
if(fg==0)%没有被选过
r=0;%和
for k=1:180
r=r+(double(Q(k,2,result(line,i)))-double(Q(k,1,j)))^2;
end
d(j)=sqrt(double(r));
end
end
%disp(d)
%最小距离
for k=1:209
if(d(k)==(-1))
d(k)=max(d);
end
end
dmin=min(d);
% disp(d)
for k=1:209
if(d(k)==dmin)
result(line,i+1)=k;
%disp([num2str(k),'d']);
end
end
else%全白，跳过该行拼下行
disp('换行');
break;
end
%结果不唯一时人工干预
end
end
disp('最后碎片正确序列：');
result
picture2=[];
for j=1:19
picture1=[];
for i=1:11
picture1=[picture1;F(:,:,result(i,j))];
end
picture2=[picture2,picture1];
end
imshow(picture2)
imwrite(picture2,'C:\Users\Administrator\Desktop\结果E2.bmp','bmp');
附录六
第2问英文程序代码：
clear
clc
%碎片总数
num=209;
%图像导入
%确定行列数
%生成全255矩阵
y=ones(180,1);
y=y.*255;
raw=0;
%存中间值
temp=zeros(num,1);
%标志
fw=0;
fb=0;
fg=0;
k=0;
m=0;
BW=ones(num,2);
BW=BW.*(-1);
A=0;
B=0;
for i=1:num
if(i
F(:,:,i)=imread(['00',num2str(i-1),'.bmp']); elseif(i
F(:,:,i)=imread(['0',num2str(i-1),'.bmp']); else
F(:,:,i)=imread([num2str(i-1),'.bmp']);
end
%取首尾列
Q(:,1,i)=F(:,1,i);
Q(:,2,i)=F(:,72,i);
%取首尾行
P(1,:,i)=F(1,:,i);
P(2,:,i)=F(180,:,i);
%对左边界空白的碎片计数
if(Q(:,1,i)==y)
raw=raw+1;
temp(raw)=i;
end
fw=0;
fb=0;
fg=0;
flag=0;
count=0;
flag=0;
for j=1:180
%每一列
fw=0;
count=0;
for t=1:72
if(F(j,t,i)~=255)
count=count+1;
end
end
if((count/72)>0.4&&flag==0)
flag=1;%经过了大多数黑色的区域
end
if((count/72)
fw=1;%已经经过大多数黑色区域，且出现少区域
end
if(fw==1&&fg==0)%当前线为全白且没有找到全白的线 fb=1;
BW(i,1)=j-1;%黑线位置
% BW(i,2)=j;
fg=1;
end
if(fg==1&&fb==1)%找到了
break;
end
end
end
for i=1:num
if(BW(i,1)==(-1))
BW(i,1)=input('输入纵坐标：');
end
i
BW(i,1)
end
abs(BW(20,1)-BW(201,1))
i=2;
temp(1:raw)
while mod(num,raw)~=0
k=raw;
l=1;
del=zeros(raw,1);
for j=1:k
flag=0;
for w=1:180
if(F(w,i,temp(j))~=255)
flag=1;
break;
end
end
if(flag==1)
raw=raw-1;
del(l)=j;
l=l+1;
end
end
%删除不符合条件的碎片
l=1;
while del(l)~=0
temp(del(l))=[];
del(l)=[];
%temp(del(l))=[]会对temp 序号产生改变
while del(l)~=0
del(l)=del(l)-1;
l=l+1;
end
l=1;
end
i=i+1;
end
temp(1:raw)
result=zeros(raw,num/raw);
result(:,1)=temp(1:raw);
result
%找每行近似相同值,
for i=1:11
t=0;
for j=1:num
if(j~=(i-1)*19+1)%自身C(j)==C((i-1)*19+1)&&
if(abs(BW(j,1)-BW(result(i,1),1))
t=t+1;
result(i,t+1)=j;
if(t==18)%满
break;
end
end
end
end
end
result
Z=ones(180,72);
Z=Z.*240;
picture2=[];
for j=1:19
picture1=[];
for i=1:11
if(result(i,j)==0)
picture1=[picture1',Z(:,:)'];
picture1=picture1';
continue;
end
picture1=[picture1',F(:,:,result(i,j))']; picture1=picture1';
end
picture2=[picture2,picture1];
end
% imshow(picture2)
%最终结果
lresult=zeros(11,19);
% 从左向右在同类型中匹配:行
for i=1:11
%首行
lresult(i,1)=result(i,1);
for j=1:18%匹配18次
if(result(i,j+1)==0)
% i,j
break;
elseif(j
disp('dd')
for t=1:j+1
flag=1;
for k=1:j+1
if(result(i,t)==lresult(i,k)) flag=0;
break;
end
end
if(flag==1)
lresult(i,j+1)=result(i,t); break;
end
end
if(flag==1)
continue;
end
end
d=zeros(19,1);
for k=1:19%求k 项对j 项的平均距离
%lresult每行中有的排除
flag=1;
for t=1:19
if(result(i,k)==lresult(i,t))
flag=0;
end
end
if(flag==1)%在未被匹配的碎片中筛选
% disp('dd')
R=Q(:,2,lresult(i,j))-Q(:,1,result(i,k)); d(k)=sum(abs(R(:)))/180;
if(d(k)==0)
d(k)=(-1);
end
end
end
dmax=max(d);
for t=1:19
if(d(t)==0)
d(t)=dmax;
elseif(d(t)==(-1))
d(t)=0;
end
end
dmin=min(d);
for t=1:19
if(d(t)==dmin)
lresult(i,j+1)=result(i,t);
break;
end
end
end
end
for i=1:11
lresult(i,:)
for j=1:19
if(lresult(i,j)~=0)
disp(BW(lresult(i,j),1))
else
disp('0');
end
end
end
%从上向下匹配
picture2=[];
for j=1:19
picture1=[];
for i=1:11
if(lresult(i,j)==0)
picture1=[picture1',Z(:,:)'];
picture1=picture1';
continue;
end
picture1=[picture1',F(:,:,lresult(i,j))'];
picture1=picture1';
end
picture2=[picture2,picture1];
end
imshow(picture2)
% imwrite(picture2,'C:\Users\Administrator\Desktop\结果EE21.bmp','bmp');
附录七
第3问程序代码：
clear
clc
num=209
raw=0;
temp=zeros(num,1);
y=ones(180,1);
y=y.*255;
for i=1:2:num*2
%奇数a 偶数b
if(ceil(i/2)
F(:,:,i)=imread(['00',num2str(ceil(i/2)-1),'a','.bmp']);
F(:,:,i+1)=imread(['00',num2str(ceil(i/2)-1),'b','.bmp']);
elseif(ceil(i/2)
F(:,:,i)=imread(['0',num2str(ceil(i/2)-1),'a','.bmp']);
F(:,:,i+1)=imread(['0',num2str(ceil(i/2)-1),'b','.bmp']); else
F(:,:,i)=imread([num2str(ceil(i/2)-1),'a','.bmp']);
F(:,:,i+1)=imread([num2str(ceil(i/2)-1),'b','.bmp']); end
end
for i=1:num*2
%首尾行
Q(:,1,i)=F(:,1,i);
Q(:,2,i)=F(:,72,i);
%对左边界空白的碎片计数
if(Q(:,1,i)==y)
raw=raw+1;
temp(raw)=i;
end
end
temp(1:raw)
raw
result=zeros(22,19);
for i=1:22
result(i)=temp(i);
end
for j=1:22
for t=1:18
d=ones(num*2,1);
d=d.*(-1);
for i=1:num*2
flag=0;
for m=1:19
if(i==result(j,m))
flag=1;
break
end
end
if(flag==0)
r=0;%和
for k=1:180
r=r+(double(Q(k,2,result(j,t)))-double(Q(k,1,i)))^2; end
d(i)=sqrt(double(r));
end
end
dmax=max(d);
for i=1:num*2
if(d(i)==(-1))
d(i)=dmax;
end
end
dmin=min(d);
for i=1:num*2
if(d(i)==dmin)
result(j,t+1)=i;
break;
end
end
end
end
result
picture2=[];
for j=1:19
picture1=[];
for i=1:11
picture1=[picture1;F(:,:,result(i,j))]; end
picture2=[picture2,picture1];
end
imshow(picture2)
imwrite(picture2,'C:\Users\Administrator\Desktop\结果E31.bmp','bmp');
picture2=[];
for j=1:19
picture1=[];
for i=12:22
picture1=[picture1;F(:,:,result(i,j))]; end
picture2=[picture2,picture1];
end
imshow(picture2)
imwrite(picture2,'C:\Users\Administrator\Desktop\结果E32.bmp','bmp');
承 诺 书
我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 指导教师或指导教师组负责人 (打印并签名) ： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）
日期： 年 月 日 赛区评阅编号（由赛区组委会评阅前进行编号）：
编 号 专 用 页
赛区评阅编号（由赛区组委会评阅前进行编号）：
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（全国组委会评阅前进行编号）：
碎纸片拼接复原
摘要
本文主要是研究关于分割图片处理——汉字碎片拼接问题。
针对问题一，首先将附件1图片用像素表示并进行二值化量化处理，用迭代法求出最佳阈值，将抽象的图片用具体的0-1矩阵表达；其次根据像素值分布用MATALAB 筛选出最左列碎纸片的编号为008；最后用欧氏距离法建立像素匹配模型，通过MATALAB 直接得到中文的拼接图片（见附录一）及序列（见文中表一），不需要进行人工干预。并根据像素匹配模型也完成英文图片（见附录一）的自动拼接（见文中表二），说明该模型的适用性较好。
针对问题二，首先将灰度图片用像素量化成11 19的矩阵，再将繁杂的像素矩阵通过聚类的方法利用MATALAB 分为11个集合，最后在集合范围内建立分步像素匹配模型，用MATALAB 匹配拼接出中文图片（见附录二）和序列（见文中表三）。特别地，对于英文碎纸片，需要对分步像素匹配模型的基线确定用黑色像素比例突变的原则进行改进，再用MATALAB 根据改进后模型匹配出英文图片（见附录二）和序列（见文中表四），在每行利用计算机拼接的过程中采用人工识别剔除错误的匹配，然后利用人机交互方式完成拼接。
针对问题三，在实际情况中，一张打印文件往往是正反两面，在用距离匹配法进行碎纸片的复原时使得误差增加，也增加了人工干预的次数。充分利用碎纸片有两面的特征，让其一面作为匹配面，另一面作为检验面，用求解两碎纸片灰度矩阵相邻列之间的欧式距离的思想，最终建立了双目标规划的数学模型，既要满足匹配面的约束，又要满足检验面的约束。在MATALAB 下编程求解，并加上人工干预最终得到了碎纸片的复原结果（见附录三），在每行利用计算机拼接的过程中采用人工识别剔除错误的匹配，然后利用人机交互方式完成拼接。
本文的优点在于文中的模型除了能复原题目所给定的已知行数、列数的碎纸片，还能复原出任何行数、列数的情况。
关键词：像素量化 欧氏距离 聚类分析 双目标规划
一、问题重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：
1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。
2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。
3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。
二、基本假设
1、 假设题目所给的附件中的碎纸片文件图片的切口是完全水平的； 2、 假设碎纸片与碎纸片之间不存在错位的情况；
3、 假设碎纸片切口是干净的，没有污渍，也没有噪声的污染；
4、 假设中文、英文在间距、高度以及宽度上的差异对像素匹配模型没有影响； 5、 假设在图片二值化时的灰色像素可以近似按最佳阈值归化为白色或黑色； 6、 假设英文的笔画均匀，且可以量化为固定像素值；
7、 假设一张英文碎纸片中最多可以容纳4个完整的英文字母。
三、符号说明
m x ij ：第m 个像素值量化矩阵的第i 行j 列交叉位置上的元素的值；
f (x , y )：点(x , y )的灰度值；
T ：阈值；
(j )(j )N 1, N 2：第j 次迭代时区域C 1和C 2像素个数；
d ：两像素量化矩阵的欧式距离值；
x ：像素值；
X m ：第m 个像素量化矩阵；
m h n ：像素矩阵中第m 行第n 列碎纸片基线的纵坐标；
βi ：像素矩阵中第i 行黑色像素所占总像素比例；
u ：像素量化矩阵中第i 行0的个数；
i
U i ：像素量化矩阵中第i 行像素点总数;
四、模型的分析、建立与求解
4.1问题一的模型分析、建立与求解
从附件1中我们可以得到19张仅纵切的中文碎纸片图片，首先将每个图片按像素值进行二值化量化，可以得到19个1980⨯72的矩阵，再提取每个矩阵的最左与最右的像素值用绝对值距离法建立像素匹配模型，从边界第一张编号为008入手，依次得出中文图片的顺序。由于英文和中文一样可以量化为像素，故同理可得英文拼接方案。 4.1.1图像二值化量化
二值化是图像处理的基本技术，目的是将图像增强结果转换成黑白二值图像，从而能清晰地得到边缘特征线，更好的为边缘提取、图像分割以及目标识别等后续工作服务。其原理是将所有灰度大于或等于阀值的像素判定为属于特定物体，其灰度值用1表示，否则这些像素点被排除在物体区域以外，用灰度值0表示背景或者例外的物体区域。
用x ij 表示第k 个像素值量化矩阵的第i 行j 交叉位置上的元素值，利用二值化处理可得：
k
白)⎧1(x ij =⎨
⎩0(黑)
k
f (x , y )≥T f (x , y )
(i =1, 2 1980; j =1, 2 72; k =1, 2 19)
接下来用迭代法确定阈值T ：
（1）选择图像的平均灰度值作为初始阈值T j =224，其中j 为迭代次数，初始值j =0。
（2）用T j 分割图像，将图像分割为2个区域C 1和C 2 （3）计算两区域的平均灰度值
(j )(j )
u
(j )
1
=
1
N
j 1
f (x , y )∈
∑f (x , y )
C 1
(j )
u
(j )
2
=
1
N
j 2
f (x , y )∈
∑f (x , y )
C 2
(j )
（4）再计算新的阈限值，即：
T
1=j +1
(j )
+22
(j )
（5）重复（2）~（4），直到T j 与T j +1的差几乎为0时，停止迭代，显示最佳阈值T 。
由MATALAB 循环运行此算法程序，得到最佳阈值T =250。
4.1.2建立像素匹配模型
本文首先提取每个矩阵最左边与最右边的像素值作为每个碎纸片图片的特征，利用这1980⨯1的矩阵建立像素匹配模型。
（1）由于文字文件边缘是完整且存在一定的边距，即:
x x
k i 1
=1
(k =1, 2 , 19; i =1, 2 , 1980)
筛选出编号008在该文本文件的最左边。 同理：
k i 72
=1
(k =1, 2 , 19; i =1, 2 , 1980)
可得编号006在文本文件的最右边。 （2）由于在碎纸片边缘是连续关联的，则断裂处的像素点理论上应该是完全吻合，故提取的最右边的像素值与最左边的像素值用欧式距离法建立像素匹配模型：
d =min (d
i =1
k
)
(k =1, 2 18)
其中：
d k =
∑x
k +1
-x i 1i 72k
(k =1, 2, , 18)
d
k
：
4.1.3模型的求解
根据像素匹配模型，通过MATALAB 循环匹配程序可直接得出拼接完善的中文图片，且不需要人工干预，最终拼接的中文序列见表1：（详情见附录中附件一）
（表一）
由于英文与中文一样是可以用像素量化的图片，故英文碎片可以直接用上述模型进行复原，通过MATALAB 编程可以直接得出拼接完善的英文图片，且不需要人工干预，最终拼接的英文序列见表二：（详情见附件中附录一）
（表二）
通过对英文图片的自动拼接，可以验证像素匹配模型对碎片拼接的适用性较好。
4.2问题二的模型分析、建立与求解
分析附件3中11⨯19张碎纸片，首先将图片用像素量化，由于文本既有纵切又有横切，采用二值化将图片转换为0-1矩阵的误差比较大，故优化模型采用不同灰度色阶来量化，得到相应的数学矩阵；
由于本题中的碎纸片较多，若采用模型一则工作量大且精度不高，故本文第一步将碎纸片进行聚类，第二步在聚类的基础上进行分步匹配，在计算机不能智能识别的情况下给予适当的人工干预。 4.2.1对灰度图片的像素量化
把有黑-灰-白连续变化的灰度值量化为256个灰度级，灰度值的范围为0~255，表示亮度从深到浅，对应图像中的颜色为从黑到白，即：
当像素点为白色，像素值x 为255； 当像素点为黑色，像素值x 为0；
当像素点为灰色，像素值x ∈(0, 255) 。
4.2.2筛选出边缘碎纸片
由于文字文件边缘是完整且存在一定的边距，用x ij 表示第m 个像素值量化矩阵的第i 行j 列交叉位置上的元素值，则X 矩阵所对应的前t 列向量值应该全
m
m
为255（即白色），即：
⎛m
x 11m
X = m
x 180⨯1 ⎝
其中x i 1=
m
⎫⎪ ⎪ ⎪m
x 180⨯72⎪⎭
x
m
1⨯72
x i 2= =x it =255
m m
(i =1, 2 , 180)。
确定t 值：
即筛选出符合条件的11张最左列的碎纸片，分别编号为49、61、168、38、14、94、125、29、7、71、89。
同理可得最右边列的11张碎纸片编号分别为：141、36、18、74、176、43、 145、19、196、60、123。
4.2.3模型的建立 一）聚类模型的建立 （1）数据处理
将像素量化的矩阵再坐标化，即以每个矩阵左上角为坐标原点，向右为横轴正方向，向下为纵轴正方向，以像素点作为坐标增量，可得每个像素点对应一个坐标(x , y )。
（2）确定聚类依据
由于同一字体的汉字具有相同的高度和宽度，即同一行文字的最下端都位于同一条基线上即同一高度上，该特征则可以作为聚类的依据。本文设定在像素量化矩阵中从有0（即黑色）行突变为全为255（即白色）行的界限作为汉字向下对齐的基线，并用MATALAB 记下该基线纵坐标。
由于文本文件切割为11行，则由（1）筛选出的最左边列(x m ,..., x m ) i 1180⨯1
T
作为聚类的11个起始样本，但是印刷文本段落的起始行需要空两字符才开始，若刚好从段前空的两字符出切割，则最左边列的基准线就不能作为该行的等高线来匹配，故此时需要人工干预将最左边列分为两类：
I 类→段落起始行在空格处切割的碎纸片→编号为：014、029、071、089 II 类→不存在上述情况的碎纸片→编号为：007、038、049、061、094、125、168。
针对第I 类，用（1）筛选出的最右列(x m 样本。
针对第II 类，用（1）筛选出的最左列(x m ,..., x m
i 1
180⨯1)
T
m ,..., x 180⨯72) 作为聚类的起始i ⨯72
T
作为聚类的起始样
本。
（3）建立模糊聚类模型
⎧1=1= =1
h 19
⎪h 1h 2
1⎨
⎪11=11= =11
h 19 ⎩h 1h 2
（4）模型的求解
根据模糊聚类模型，通过MATALAB 逐次循环程序可以将11⨯19的像素量化矩阵聚类到以起始样本为目标的11个集合A , B , , K 中.
所有的碎纸片聚类结
果为：
⎧⎧集合A :以编号为049为起始，141为末端的行⎪⎪
059为末端的行⎪I 类⎪集合B :以编号为029为起始，
⎪⎨集合C ：以编号为071为起始，060为末端的行⎪⎪
123为末端的行⎪⎪⎩集合D ：以编号为089为起始，
⎪196为末端的行⎧集合E :以编号为007为起始，⎪⎪
074为末端的行 ⎨⎪集合F :以编号为038为起始，
⎪⎪集合G :以编号为049为起始，141为末端的行⎪⎪II 类为起始，036为末端的行⎪⎨集合H :以编号为061⎪⎪集合I :以编号为094为起始，043为末端的行⎪⎪⎪⎪集合J :以编号为125为起始，145为末端的行⎪⎪
168为起始，018为末端的行⎩集合K :以编号为⎩
二）分步像素匹配模型的建立
碎纸片边缘是连续关联的，则断裂处的像素点理论上应该是完全吻合，因为本问题横切与纵切同时存在，则需要横向和纵向都分别匹配，首先对聚类的每一样本集用欧氏距离法通过MATALAB 来横向匹配，得到11个横向切割的碎纸条，再将碎纸条进行纵向拼接。 （1）分步像素匹配模型的建立
d =min (d )(n =1, 2 18)
n
其中：
d n =
∑x
180i =1
m 1
il
-x il 2
m
(m , m ∈A , B , , K ; n =1, 2 , 18)
1
2
d 值越小，就代表两碎纸片越匹配。
针对横向匹配，由于文本的行距要大于间距，所以在横向分割时切断白色间隔区域的概率远远大于切断黑色汉字的概率，故此时要将11行碎纸条聚类：
P 类→横向切割线位于全是白色空隔区域
Q 类→横向切割线位于黑色汉字区域
首先，运用上述模型匹配Q 类，再根据行与行之间的笔画或句意人工干预拼接P 类。
4.2.5人工干预及最终复原结果 1）时间节点：像素矩阵聚类时
干预方式：由于基线的匹配导致集合A , B , , K 不能得到预想的19个元素，
如集合A 中筛选出了24个类似与编号049同行的元素，此时就人工干预剔除不合理的5个像素矩阵。这里一共有8个矩阵不合理，故需要人工干预8次。 2) 时间节点：碎纸条纵向拼接时
干预方式：由于P 类的边缘像素值都是255（即为白色），计算机无法识别没有笔迹特征的碎纸条，故需要人工来拼接，P 类有3个元素，故需要3次人工干预。
用MATALAB 程序循环匹配得出最终汉字排序为见表三（详图见附录二）
（表三）
4.2.6英文碎纸片的拼接处理
（1）英文碎纸片拼接模型的改进 由于英文字母宽度、大小不一且高度也不相等，故不能以中文的聚类依据一概而论，必须对模型进一步的改进。
经过观察发现单词图像可以分成3个部分：上区、中区和下区，单词内绝大多数字母都处于中区，只有少数一些字母会伸展到上区或者下区。故就英文而言可以将中区字母（如a ）的底线作为英文行的基线。
由于英文单词可能由中区、上区、下区三个区域的字母组成，故在基线以下区域像素矩阵不可能全是从存在0（即黑色）突变为全为255（即白色）的情况， 但是可以根据黑色像素占总像素的比例来判断是否发生突变，即：
β
i
=
U
i i
(i =1, 2 , 180; j =1, 2 , 72)
（2）黑色像素比例的判断
通过MATALAB 统计，英文字母每画平均像素为7。当一张英文碎纸片容纳最多的3个完整的英文字母都恰好都是处于下中区时。计算此时下区的黑色像素比例：
3⨯7=βmin 72=29. 12%
由于中区英文字母大多是左右对称图片，即最大黑色像素比例是上区黑色像素比例的两倍。计算此时中区的黑色像素比例：
β
max
=2⨯β
min
=58. 24%
（3）由黑色像素比例突变选择英文基线
根据（2）所得数据，β50%是属于黑色比例较大区域。当之前的前s 行是黑色比例较大，而s +1是黑色比例较小时，即可认为第s 行为该英文行的基线。
通过以上改进和处理，接下来的拼接工作就可以沿用汉字的模型进行拼接。用MATALAB 程序循环匹配得出最终汉字排序为见表四（详图见附件中附录二）
（表四）
4.3 问题三的分析及模型的建立、求解
有了解决第一问，第二问的方法，对于复原单面打印文件碎纸片已经不存在什么问题，但是实际情况中，大部分是双面打印的文件，如果单纯的采用第一二问的方法，会使得与目标图片相关性大的图片的数量增多，这样也就会增加人工干预的次数，所以需在前面方法上加以改进。由于文件是双面打印，一张碎纸片
就有两面，那么我们可以让其中的一面作为匹配面，另一面作为检验面，这样就可以增加匹配的精度。
4.3.1 确定出第一列碎纸片
通过MATLAB 软件处理图片信息的方法得到每张碎纸片的灰度值矩阵, 取出每个矩阵的第一列每个元素的值x i 1(k 表示第k 个灰度值矩阵) ，若x i 1=255，那么该列所对应的碎纸片就是第一列碎纸片。 4.3.2 进行行匹配
匹配面：在第一列碎纸片中选取一张碎纸片作为目标碎纸片，然后计算其它碎纸片的灰度值矩阵的第一列与目标碎纸片的灰度值矩阵的最后一列的距离。用欧式距离计算：
k
k
d =
∑(x -x )
i =1
j
417
m i
2
m
求min(d ) , 当距离最小时所对应的图片与目标图片是相匹配的，其中x 表示目标碎纸片灰度值矩阵的最右边一列值，x 表示其它碎纸片灰度值矩阵最左边的一列值。
检验面：由于与目标碎纸片相匹配的碎纸片可能有多个，即存在多个相同的
min(d ) ，那么这时需要通过目标碎纸片的背面与可能相匹配的多个碎纸片的背
面进行验证，这样就可以很准确的确定哪张碎纸片是与目标碎纸片相匹配的。 需要注意的是：验证时应用目标碎纸片的灰度值矩阵的第一列与可能相匹配的多个碎纸片的灰度值矩阵的最后一列进行距离计算。在进行检验时仍然采用欧式距离计算，只不过变量减少了。
d
1
=
∑(y -y )
k =1
k
m k
2
4.3.3建立双目标模型
通过上述分析，可得双目标模型为：
) ⎧m i n d (
⎨ m i n d () 1⎩
其中
d
=1
∑(y m -y k )
k =1
k
2
，
d
4172
=∑(x m -x i ) 。
i =1
此时所对应的碎纸片才是与目标碎纸片真正相匹配。 接下来在行匹配完成的基础上，要复原出一幅完整的文件，还需对其进行列匹配，进行列匹配的方法仍用距离判别法，求目标碎纸片的灰度值矩阵的最后一行与其它碎纸片灰度值矩阵的第一行的欧式距离，与行匹配计算方法一致。
4.3.3 人工干预及最终复原结果 1）时间节点：确定第一列碎纸片时
干预方式：在MATLAB 求解的第一列碎纸片共有31张，超过了实际中正反两面 第一列共22张的碎纸片，通过人眼识别可以去除掉其中的3张。 2）时间节点：进行行匹配时
干预方式：在MATLAB 中求解出不能进行匹配的碎纸片的编号，然后在附件5中找出所对应的碎纸片，单独放在一边。 3）时间节点：进行列匹配时
干预方式: 在MATLAB 中求解出不能进列匹配的碎纸片的编号，然后在附件5中找出所对应的碎纸片，单独放在一边。
4）时间节点：对既不能作为行匹配的碎纸片，又不能进行列匹配的碎纸片（少数）
干预方式：单独放在一边作为最后的人工匹配时需要的碎纸片。 5）时间节点：大部分碎纸片已经拼接好时
干预方式：通过碎纸片上的字迹进行人工拼接
在进行行匹配和列匹配以及在人工干预的前提下我们最终得到了碎纸片的复原结果，现将复原结果的碎片序号以如下表格给出：
第一面
表五
第二面：
表六
五、模型的评价、改进
5.1模型的优点
1、问题一中，我们碎纸片的灰度值矩阵采用了二值化处理，在进行图片时，没有人工干预，加快了复原图片的速度。
2、问题二中，采用的先聚类再匹配思想将繁杂的无规则像素矩阵分到11个目标集合中再进行集合内部的匹配，降低了编程的难度，减少了匹配的次数。 并且考虑了中文与英文在筛选时的差别，将中文的匹配模型改进后再用来处理英文文本，加大了英文自动拼接的准确性。
3、对于问题三巧妙地将两面打印的文本的一面作为匹配面，另一面作为检验面，提高了碎纸片匹配的精度。
4、文中的模型除了能复原题目所给定的已知行数、列数的碎纸片，还能复原出任何行数、列数的情况。 5.2模型的缺点
二值化处理灰度值数据时存在偏差，它会将不同的灰度值归为一类，对于数据量小的碎纸片误差显然是很大的，在用聚类分析时，也有可能将不是一类的碎纸片归为一类，增加了人工干预的次数。
5.3模型的改进
对于三个问题我们采用了三种不同的办法进行求解，都能够求得相应的结果。但是由于二值化处理灰度值时存在局限性，不可作为推广模型。为了使模型具有普遍使用性，因此在求解复原碎纸片这类问题时，可以用灰度值距离来进行求解。
六、参考文献
【 1 】 Jeremy,灰度图像二值化方法
http://www.docin.com/p-413825845.html,2013/09/14
【 2 】李佳佳 何小海 吴晓红 ,基于网格模板的最小欧式距离准则图像自动拼接技术，《成都信息工程学院学报》，2007/01
【3】罗智中， 基于文字特征的文档碎纸片半制动拼接，
，2013年9月13日。 【 4 】 罗智中 ，基于线段描述的碎纸片边界检测算法研究，
，2013年9月13日。 【 5 】 钟力、胡晓峰，重叠图像拼接算法，
，2013年9月13日。 【 6 】 曾建军、李世航、王永国、叶仁玉、夏惠异，《MATLAB 语言与数学建模》，安徽大学出版社，2005年9月出版。 【 7 】 何正风，《MATLAB 在数学方面的应用》，清华大学出版社出版，最新版。
七、附件
附录一:
附录二：中中文完整的图片文完整的图片 附录三：
第1问英文结果：
附录二：
第2问中文程序结果图（人工干预前）
:
第2问中文（人工干预后）：
第2问英文图片（人工干预前）：
第2问英文结果图（人工干预后）：
附录三：
第3问结果（人工干预前）：
第3问结果（人工干预后）：
附录四：
第1问程序代码：
clear
clc
%图像导入
for i=1:19
if(i
F(:,:,i)=imread(['00',num2str(i-1),'.bmp']);
else
F(:,:,i)=imread(['0',num2str(i-1),'.bmp']);
end
%二值化
B(:,:,i)=im2bw(F(:,:,i),250/255);
%取首位列
Q(:,1,i)=B(:,1,i);
Q(:,2,i)=B(:,72,i);
end
%结果
result=zeros(19,1);
%生成全255矩阵
y=ones(1980,1);
%y=y.*255;
%找首列
% Q(:,1,i)==y
for i=1:19
if(Q(:,1,i)==y)
result(1)=i;%记录序号
end
end
%找尾列
for i=1:19
if(Q(:,2,i)==y)
result(19)=i;%记录序号
end
end
% 中间(17张) 匹配，从首至尾的方向
for i=1:17
%可能情况, 人为干预
% may=zeros(19,1);
% n=1;
d=ones(19,1);
d=d.*(-1);
for j=1:19
fg=0;
for t=1:19
if(j==result(t))
fg=1;
end
end
if(fg==0)
if(i==17)
result(i+1)=j;
break;
end
r=0;%和
for k=1:1980
r=r+(double(Q(k,2,result(i)))-double(Q(k,1,j)))^2; end
%欧氏距离
d(j)=sqrt(double(r));
end
end
%最小距离
if(i~=17)
dmax=max(d);
for k=1:19
if(d(k)==(-1))
d(k)=dmax;
end
end
dmin=min(d);
for k=1:19
if(d(k)==dmin)
result(i+1)=k;
break;
end
end
end
end
disp('最后碎片正确序列：');
result
%图片的保存和显示
picture=[];
for i=1:19
picture=[picture,F(:,:,result(i))];
end
imshow(picture)
% imwrite(picture,'C:\Users\Administrator\Desktop\结果111.bmp','bmp');
附录五
第2问中文程序代码：
clear
clc
%碎片总数
sum=209;
%图像导入
%确定行列数
%生成全255矩阵
y=ones(180,1);
y=y.*255;
raw=0;
%存中间值
temp=zeros(sum,1);
%标志
fw=0;
fb=0;
fg=0;
BW=ones(sum,2);
BW=BW.*(-1);
for i=1:sum
if(i
F(:,:,i)=imread(['00',num2str(i-1),'.bmp']);
elseif(i
F(:,:,i)=imread(['0',num2str(i-1),'.bmp']);
else
F(:,:,i)=imread([num2str(i-1),'.bmp']);
end
%取首尾列
Q(:,1,i)=F(:,1,i);
Q(:,2,i)=F(:,72,i);
%取首尾行
P(1,:,i)=F(1,:,i);
P(2,:,i)=F(180,:,i);
%对左边界空白的碎片计数
if(Q(:,1,i)==y)
raw=raw+1;
temp(raw)=i;
end
%提取碎片的White ，black 值
fw=0;
fb=0;
fg=0;
for j=1:180
%每一列
fw=1;%假设该列为白
for t=1:72
if(F(j,t,i)~=255)
fw=0;%不全白
if(fb==0)
fb=1;
BW(i,1)=j;%黑线位置
end
end
end
if(fw==1&&fg==0)%当前线为全白且没有找到全白的线
BW(i,2)=j;
fg=1;
end
if(fg==1&&fb==1)%找到了
break;
end
end
end
%分类:两类
disp(BW);
i=2;
temp(1:raw)
while mod(sum,raw)~=0
k=raw;
l=1;
del=zeros(raw,1);
for j=1:k
flag=0;
for w=1:180
if(F(w,i,temp(j))~=255)
flag=1;
break;
end
end
if(flag==1)
raw=raw-1;
del(l)=j;
l=l+1;
end
end
%删除不符合条件的碎片
l=1;
while del(l)~=0
temp(del(l))=[];
del(l)=[];
%temp(del(l))=[]会对temp 序号产生改变
while del(l)~=0
del(l)=del(l)-1;
l=l+1;
end
l=1;
end
i=i+1;
end
temp(1:raw)
result=zeros(raw,sum/raw);
result(:,1)=temp(1:raw);
for line=1:11
% 匹配，从首至尾的方向
for i=1:18
%可能情况, 人为干预
may=zeros(209,1);
d=ones(209,1);
d=d.*(-1);
n=1;
ew=0;%全白标记
if(ew==0)%非全白
for j=1:sum
fg=0;
for t=1:19
for tt=1:11
if(j==result(tt,t))
fg=1;
end
end
end
if(fg==0)%没有被选过
r=0;%和
for k=1:180
r=r+(double(Q(k,2,result(line,i)))-double(Q(k,1,j)))^2;
end
d(j)=sqrt(double(r));
end
end
%disp(d)
%最小距离
for k=1:209
if(d(k)==(-1))
d(k)=max(d);
end
end
dmin=min(d);
% disp(d)
for k=1:209
if(d(k)==dmin)
result(line,i+1)=k;
%disp([num2str(k),'d']);
end
end
else%全白，跳过该行拼下行
disp('换行');
break;
end
%结果不唯一时人工干预
end
end
disp('最后碎片正确序列：');
result
picture2=[];
for j=1:19
picture1=[];
for i=1:11
picture1=[picture1;F(:,:,result(i,j))];
end
picture2=[picture2,picture1];
end
imshow(picture2)
imwrite(picture2,'C:\Users\Administrator\Desktop\结果E2.bmp','bmp');
附录六
第2问英文程序代码：
clear
clc
%碎片总数
num=209;
%图像导入
%确定行列数
%生成全255矩阵
y=ones(180,1);
y=y.*255;
raw=0;
%存中间值
temp=zeros(num,1);
%标志
fw=0;
fb=0;
fg=0;
k=0;
m=0;
BW=ones(num,2);
BW=BW.*(-1);
A=0;
B=0;
for i=1:num
if(i
F(:,:,i)=imread(['00',num2str(i-1),'.bmp']); elseif(i
F(:,:,i)=imread(['0',num2str(i-1),'.bmp']); else
F(:,:,i)=imread([num2str(i-1),'.bmp']);
end
%取首尾列
Q(:,1,i)=F(:,1,i);
Q(:,2,i)=F(:,72,i);
%取首尾行
P(1,:,i)=F(1,:,i);
P(2,:,i)=F(180,:,i);
%对左边界空白的碎片计数
if(Q(:,1,i)==y)
raw=raw+1;
temp(raw)=i;
end
fw=0;
fb=0;
fg=0;
flag=0;
count=0;
flag=0;
for j=1:180
%每一列
fw=0;
count=0;
for t=1:72
if(F(j,t,i)~=255)
count=count+1;
end
end
if((count/72)>0.4&&flag==0)
flag=1;%经过了大多数黑色的区域
end
if((count/72)
fw=1;%已经经过大多数黑色区域，且出现少区域
end
if(fw==1&&fg==0)%当前线为全白且没有找到全白的线 fb=1;
BW(i,1)=j-1;%黑线位置
% BW(i,2)=j;
fg=1;
end
if(fg==1&&fb==1)%找到了
break;
end
end
end
for i=1:num
if(BW(i,1)==(-1))
BW(i,1)=input('输入纵坐标：');
end
i
BW(i,1)
end
abs(BW(20,1)-BW(201,1))
i=2;
temp(1:raw)
while mod(num,raw)~=0
k=raw;
l=1;
del=zeros(raw,1);
for j=1:k
flag=0;
for w=1:180
if(F(w,i,temp(j))~=255)
flag=1;
break;
end
end
if(flag==1)
raw=raw-1;
del(l)=j;
l=l+1;
end
end
%删除不符合条件的碎片
l=1;
while del(l)~=0
temp(del(l))=[];
del(l)=[];
%temp(del(l))=[]会对temp 序号产生改变
while del(l)~=0
del(l)=del(l)-1;
l=l+1;
end
l=1;
end
i=i+1;
end
temp(1:raw)
result=zeros(raw,num/raw);
result(:,1)=temp(1:raw);
result
%找每行近似相同值,
for i=1:11
t=0;
for j=1:num
if(j~=(i-1)*19+1)%自身C(j)==C((i-1)*19+1)&&
if(abs(BW(j,1)-BW(result(i,1),1))
t=t+1;
result(i,t+1)=j;
if(t==18)%满
break;
end
end
end
end
end
result
Z=ones(180,72);
Z=Z.*240;
picture2=[];
for j=1:19
picture1=[];
for i=1:11
if(result(i,j)==0)
picture1=[picture1',Z(:,:)'];
picture1=picture1';
continue;
end
picture1=[picture1',F(:,:,result(i,j))']; picture1=picture1';
end
picture2=[picture2,picture1];
end
% imshow(picture2)
%最终结果
lresult=zeros(11,19);
% 从左向右在同类型中匹配:行
for i=1:11
%首行
lresult(i,1)=result(i,1);
for j=1:18%匹配18次
if(result(i,j+1)==0)
% i,j
break;
elseif(j
disp('dd')
for t=1:j+1
flag=1;
for k=1:j+1
if(result(i,t)==lresult(i,k)) flag=0;
break;
end
end
if(flag==1)
lresult(i,j+1)=result(i,t); break;
end
end
if(flag==1)
continue;
end
end
d=zeros(19,1);
for k=1:19%求k 项对j 项的平均距离
%lresult每行中有的排除
flag=1;
for t=1:19
if(result(i,k)==lresult(i,t))
flag=0;
end
end
if(flag==1)%在未被匹配的碎片中筛选
% disp('dd')
R=Q(:,2,lresult(i,j))-Q(:,1,result(i,k)); d(k)=sum(abs(R(:)))/180;
if(d(k)==0)
d(k)=(-1);
end
end
end
dmax=max(d);
for t=1:19
if(d(t)==0)
d(t)=dmax;
elseif(d(t)==(-1))
d(t)=0;
end
end
dmin=min(d);
for t=1:19
if(d(t)==dmin)
lresult(i,j+1)=result(i,t);
break;
end
end
end
end
for i=1:11
lresult(i,:)
for j=1:19
if(lresult(i,j)~=0)
disp(BW(lresult(i,j),1))
else
disp('0');
end
end
end
%从上向下匹配
picture2=[];
for j=1:19
picture1=[];
for i=1:11
if(lresult(i,j)==0)
picture1=[picture1',Z(:,:)'];
picture1=picture1';
continue;
end
picture1=[picture1',F(:,:,lresult(i,j))'];
picture1=picture1';
end
picture2=[picture2,picture1];
end
imshow(picture2)
% imwrite(picture2,'C:\Users\Administrator\Desktop\结果EE21.bmp','bmp');
附录七
第3问程序代码：
clear
clc
num=209
raw=0;
temp=zeros(num,1);
y=ones(180,1);
y=y.*255;
for i=1:2:num*2
%奇数a 偶数b
if(ceil(i/2)
F(:,:,i)=imread(['00',num2str(ceil(i/2)-1),'a','.bmp']);
F(:,:,i+1)=imread(['00',num2str(ceil(i/2)-1),'b','.bmp']);
elseif(ceil(i/2)
F(:,:,i)=imread(['0',num2str(ceil(i/2)-1),'a','.bmp']);
F(:,:,i+1)=imread(['0',num2str(ceil(i/2)-1),'b','.bmp']); else
F(:,:,i)=imread([num2str(ceil(i/2)-1),'a','.bmp']);
F(:,:,i+1)=imread([num2str(ceil(i/2)-1),'b','.bmp']); end
end
for i=1:num*2
%首尾行
Q(:,1,i)=F(:,1,i);
Q(:,2,i)=F(:,72,i);
%对左边界空白的碎片计数
if(Q(:,1,i)==y)
raw=raw+1;
temp(raw)=i;
end
end
temp(1:raw)
raw
result=zeros(22,19);
for i=1:22
result(i)=temp(i);
end
for j=1:22
for t=1:18
d=ones(num*2,1);
d=d.*(-1);
for i=1:num*2
flag=0;
for m=1:19
if(i==result(j,m))
flag=1;
break
end
end
if(flag==0)
r=0;%和
for k=1:180
r=r+(double(Q(k,2,result(j,t)))-double(Q(k,1,i)))^2; end
d(i)=sqrt(double(r));
end
end
dmax=max(d);
for i=1:num*2
if(d(i)==(-1))
d(i)=dmax;
end
end
dmin=min(d);
for i=1:num*2
if(d(i)==dmin)
result(j,t+1)=i;
break;
end
end
end
end
result
picture2=[];
for j=1:19
picture1=[];
for i=1:11
picture1=[picture1;F(:,:,result(i,j))]; end
picture2=[picture2,picture1];
end
imshow(picture2)
imwrite(picture2,'C:\Users\Administrator\Desktop\结果E31.bmp','bmp');
picture2=[];
for j=1:19
picture1=[];
for i=12:22
picture1=[picture1;F(:,:,result(i,j))]; end
picture2=[picture2,picture1];
end
imshow(picture2)
imwrite(picture2,'C:\Users\Administrator\Desktop\结果E32.bmp','bmp');