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

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

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

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

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

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

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

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

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

）日期年月日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原摘要为了将碎纸片拼接在一起，而又无需耗费大量时间和人力。

本文利用计算机将图像数字化，用otsu 算法确定出图像二值化的最佳阈值，从而便能找出只包含0和1的图像矩阵（0代表黑色，1代表白色）。

在第一问中碎片数量小，我们很容易通过人力看出第一个碎片，提取其右边界数据，和别的碎片左边界数据一一比对，找出比对率最高的碎片。

为了使结果更加明显，更直接地找出匹配碎片，我们不比对数值为1的点，只找出值为0且一一对应的点的数量k ，利用程序计算出两个边界中0值点的数量num ，则配对比为：C=%100num2k ⨯ 第二三问数量大，待比较的边界增多。

为了解决图的最优划分问题，我们应用谱聚类算法的思想，对数据进行了处理，减少计算机比对时的运算量。

首先将二值化后的图像矩阵提取边界像素点，依0,1点分布特征，将其长分为5块，宽为2块（即均为每36个像素点为一块）。

通过软件算出各块0点个数，分别将每个边界的数据作为一个向量。

找出相匹配的碎片，即找出相似度最大的向量。

向量中带比对的数值均是一一对应的，因此，很自然地想到可以用距离来度量样本点间的相似程度。

对于定量变量，常用的是 Minkowski 距离来度量样本点间的相似程度：d q （x ，y ）=qqk kk y x 1p1-⎥⎥⎦⎤⎢⎢⎣⎡∑= 当q=1时，我们得到绝对值距离：d （x ，y ）=∑=p1-k k ky x利用计算机通过枚举法比较绝对值距离的大小，便能轻松找出相互匹配的碎片了。

关键字：otsu 算法 二值化 matlab 枚举法 Minkowski 距离一．问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

传统的拼接复原工作由人工完成，准确率较高，但由于效率很低，特别是当碎片数量巨大时，人工拼接很难在短时间内完成任务。

因此我们试图在计算机高度发展的基础上，开发碎纸片的自动拼接技术，以提高拼接复原效率。

1、建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片（仅纵切)数据进行拼接复原。

并写出人工干预的方式和时间点。

2、设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片（纵切和横切）数据进行拼接复原。

并写出人工干预的方式和时间点。

3、尝试设计相应的碎纸片拼接复原模型与算法，然后将附件5给出的一页英文印刷文字双面打印文件的碎片数据进行复原。

并写出人工干预的方式和时间点。

二、问题分析2.1问题一的分析问题一要求我们建立拼接复原模型和算法，将其附件1、2给出的中、英文各一页文件的碎纸片（仅纵切）数据进行拼接复原。

碎片切痕规则，且给出的每幅图像素均为1980×72，因此假设两个碎片匹配，则当其对齐拼接时，切断的字符能完全正确地被连接。

因此我们考虑从切割处入手。

观察可得共享一个切割边的碎片，当像素点无限接近于切割处时，两者的像素点是对称的。

因此我们利用计算机软件先将图片进行二值化处理，再选取最边上的一列像素点进行提取比对，利用各种方法进行对比，找出使比对结果最明显的方法。

再利用其找出各匹配的碎片。

2.2问题二的分析此问中横切与纵切的碎片数量多，面积小和需要考虑的边界数量多。

若延用问题一的方法，直接比对像素点，则循环过后会导致预算量太大，matlab无法计算。

因此我们将图片二值化处理后，再利用噪声处理的思想，将四个边界上个的像素点分块，算出各块黑色点个数，将各图的数据储存在矩阵中，则只用比对各矩阵的数据，利用模糊聚类的方法来比较，配对的碎片。

2.3问题三的分析问题三在问题二的基础上加上了正反面，加大了运算量，但我们问题二的解法已经尽量对数据进行了处理简化，此问依旧能延用，只需改动数据便能达到解题的目的。

三、模型假设1、该文字文件被碎纸机破碎后，没有受到其它因素影响而有其它的损坏。

2、该文字文件在被破碎之前文字数据正常，没有缺印、重印或字迹模糊、数据错位等现象。

3、利用的电脑软件计算误差小，可以忽略不计。

四、符号说明Minkowski 距离d qc 改进后的陪对比c0改进前的配对比num 边界中0值点的数量n1前景的点数csum前景的质量矩阵m1前景的平均灰度n1当前阈值下的背景的点数sum-csum当前阈值下的质量矩m2当前阈值下的平均灰度t前景与背景的分割阈值w前景点数占图像比例u平均灰度w1点数占图像比例u1。

平均灰度u图像的总平均灰度g 前景和背景图象的方差k位置与值均相同的点的数量p nm，二值化处理后的灰度矩阵元素五、模型的建立及求解5.1 问题一的模型建立及求解首先将图片输入matlab软件，便自动将图片处理为数据矩阵，此时便可取出边界点进行匹配，通过程序，算出位置与值均相同的点的数量num，我们能得出直接匹配率c：c0=1980num×100%例如：匹配附件1中的“008.bmp”与“001.bmp”运行程序（程序见附录）得：c=0.7712num=1527再用枚举法匹配出合适的碎片时，数据如下：num=1862 c 0 =0.9404我们发现是否匹配所反映出的比率差异并不大，不难发现，空白处均被识别为匹配，导致匹配率都很高，因此我们需要进行改进，然后我们发现当灰度为40的点和灰度为50的点匹配时，肉眼看来没有区别，而计算机却判别为不同，此时必然也会参数误差。

要解决这个问题，我们需要将图像数据处理为只有0和1（0代表黑色，1代表白色），至于判定是0还是1的准则，通过确定图像二值化最佳阈值即能实现。

阈值将原图象分成前景，背景两个图象。

前景：用n 1,csum,m 1来表示在当前阈值下的前景的点数，质量矩，平均灰度 后景：用n 1, sum-csum,m 2来表示在当前阈值下的背景的点数，质量矩，平均灰度 当取最佳阈值时，背景应该与前景差别最大，关键在于如何选择衡量差别的标准， 在otsu 算法中这个衡量差别的标准就是最大类间方差。

记t 为前景与背景的分割阈值，前景点数占图像比例为w 0， 平均灰度为u 0；点数占图像比例为w 1，平均灰度为u 1。

则图像的总平均灰度为：u= w 0×u 0+ w 1× u 1。

前景和背景图象的方差：g= w 0 (u 0)×(u 0-u)+ w 1×(u 1-u) ×(u 1-u)=w0×w 1×(u 0- u 1) ×(u 0- u 1)我们得到阈值后便能实现二值化了：pnm ，=⎩⎨⎧≥<t)0(x x 1n m,n m,）（t得出二值化处理后的灰度矩阵：p=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⋯⋯7219801198072111p p p p ∶提取灰度矩阵左右边界构成新的匹配向量q:q=(q 11，q 21……q11980　) 或q=(q 172，q 272……q198072)接下来再来对二值化后的图片矩阵进行比对处理。

改写后的程序不再比对值为1的点了，此时利用以下公式计算：C=%100num2k ⨯ 此时我们再来看与合适碎片与不合适碎片的比对率： 不合适： K=35 C=0.14056 合适： K=176 C=0.90683由此看出差距明显，实现起来误差小，具有较高可行性。

通过编程实现循环查找，便能快速找出配对碎片了（代码见附录）。

得出的结论和人工干预方式和时间见附录。

5.2问题二、三的模型建立及求解首先处理数据，简化比对运算。

二值化处理方法同上，此问中图像像素为：180×72。

我们先从宏观观察的左右边界一般有3个字符密集处，2个空白处；上下1个密集处，1个空白处。

由此应左右边界分为5块，上下2块。

再从微观，即像素点的分配考虑，发现如此刚好每块有36个像素点。

此分法合理。

然后再由计算机算出每块0（即黑点）的个数，做好编号，依次储存在向量中。

由此，每个图像的数据我们均有记录之后，左右上下的边界都能通过比对找到匹配碎片了。

对于向量的匹配，我们通过计算出的绝对值距离来判断是否匹配：d （x ，y ）=∑=p1-k k ky x如我们在matlab 软件中输入附件4的图片“000.bmp ”和“001.bmp ” 对000的上下左右边界处理后得出的向量a ，b ，c ，d ：a=[0] [0] b=[0] [0] c=[0] [5] [0] [32] [0] d =[0] [2] [0] [33] [0]对001的上下左右边界处理后得出的向量a ，b ，c ，d ： a=[0] [0] b=[32] [4] c=[0] [3] [32] [22] [5] d =[0] [23] [30] [9] [0] 得出无论怎么摆放，均无法匹配。

通过程序枚举算出000与102左右匹配。

102的数据： a=[0] [0] b=[0] [0] c=[0] [10] [0] [0] [0] d =[0] [5] [0] [32] [0]102的左边与000的右边绝对距离为：d （x ，y ）=∑=p1-k k ky x=（0-0）+（5-5）+（0-0）+（32-32）+（0-0）=0由此例我们能看出匹配的两幅图的绝对值距离可以非常的小，我们通过多次试验发现此法可行性很高。