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

2013高教社杯全国大学生数学建模竞赛

承诺书

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

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

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

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

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

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：

所属学校（请填写完整的全名）：西华大学参赛队员(打印并签名)：1.杨尚安

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

日期：2013年09月15日

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

2013高教社杯全国大学生数学建模竞赛

编号专用页

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

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

全国评阅编号（由全国组委会评阅前进行编号）：

碎纸片的拼接复原

摘要

针对问题一，首先将题中所给图片导入matlab软件，利用imread函数得到每张图片的文字灰度像素矩阵，再取出所有矩阵左、右列，建立像素绝对差拟配模型，得到拟配程度最高的两幅图片，进行拼接，出现不合理拼接情况则进行人工干预，最后重复上述过程，完成全部拼接并导出图像。

针对问题二，首先将全部碎片导入matlab软件，经过处理得到每张碎片中符号距离碎片上下端的像素位，再根据分类聚类思想，利用excel表格处理，将所有具有“相同”像素位的图片分为一组，得到11个分组，然后在每一个分组中建立左右连接点数目最匹配模型，再配合人工干预，将所有碎片拼接为一行图像，最后将这11行图像利用问题一中模型拼接为最终图像并打印结果。

针对问题三，首先建立一种基于K-Means局部最优性的高效聚类模型，然后根据模型利用matlab，将所给图片全部导入分类，分好类并人工调整补充后再利用matlab在每一组分类中利用问题二模型在人工干预情况下得出原始图像并打印结果。

关键词：像素绝对差拟配模型左右连接点数目最匹配模型人工干预

1

一、问题重述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：

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

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

3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。

二、模型假设

1、假设全部碎纸片边缘光滑

2、假设字符色调一致

3、假设字符间距相同，没有特殊情况

4、假设除字符外，页面没有其他地方具有任何色彩

5、假设英文字符书写标准，大小写字号均相同

三、符号说明

ai表示灰色像素矩阵

n表示灰色像素矩阵的列数

m表示灰色像素矩阵的行数

i表示第几个碎片

ai

mn表示某个像素点

b表示某灰度像素点为黑色还是白色

right(i)表示灰色像素矩阵最右边列

left(k)表示灰色像素矩阵最左边列

w表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值的和

四、模型建立与求解

4.1问题一

4.1.1问题分析

整体来看，本问题要求利用数学模型，改原有手动拼接技术为自动或半自动拼接技术，完成题中所给的相应碎纸片的拼接复原工作。

具体操作，考虑所给碎纸片内容仅有汉字或英文，而没有颜色、大小、字形之分。

2

因此，只能利用碎纸片中相应的文字特征进行操作，考虑碎纸片扫描进入在计算机后是以图片的形式存在，而图片又是以像素的情况组成。所以，首先可将图片导入matlab中，以其像素为基点，得到每个图片的像素矩阵，每一像素矩阵即可表示该图片的特征。为了利用图片像素矩阵完成图片的拼接，考虑问题一只是将原图分为了19列，每一列具有1980像素，首先可根据左端全为空白，找出原图最左一列碎片，然后利用拼接好的图片最右列像素点去匹配未拼接图片的最左列像素点，使得拼接最为吻合的即为需要拼接的图片，然后拼接，再重复上述过程，直到拼接完成。具体操作流程如下：

图1问题一解答流程图

4.1.2数据处理

将图片导入matlab中，然后编写程序（具体代码见附录1），可得每个碎纸片灰度像素矩阵（碎片000局部像素点如下）。

图2碎片000局部灰度像素点列

3

4.1.3像素绝对差拟配模型建立

令碎片导入matlab编程计算所得的灰色像素矩阵为：

iia11a12a1iniiia22a2naai21,n72,m1980,1i19

iiaiaam2mnm1

由于碎片像素为72*1980，因此矩阵ai也是72*1980的，矩阵每一列数据即为碎片相应列像素值，其中每个像素点ai

mn表示此处为黑色或白色，用b表示某灰度像素点为黑色

还是白色，即：

0表示此处为黑色即有图像b0amn255表示此处在有图像与没图像之间255表示此处为白色即无图像

其中0m1980,0n72

令right(i)表示灰色像素矩阵最右边列，那么

a1iniaright(i)2n,n72,m1980,1i19

aimn

令left(k)表示灰色像素矩阵最左边列，则

ka11kaleft(k)21,n72,m1980,1k19

akm1

令w表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值的和。那么有

wright(i)left(k)

119800i19,0k19

根据上述模型即可确定某一碎片灰度像素矩阵最右边列与其余未拼接碎片最左边列的绝对差值，下面讨论因差值不同而产生的匹配问题。

1、最左列的确定：当出现某一碎片灰度像素矩阵最左列均为255时，那么说明该碎片为原始图像的最左列。

2、假设出现w1w2w3wk情况，那么首先将wk对应的碎片与该基准碎片进行拼接，若拼接不合适，这时就需要人工干预，换wk1对应的碎片与基准碎片进行拼接。情况如下：

4

这是不确定的，而进行人工干预选择wk1对应的碎片后，将会出现下面情况：

这样就能正确的完成两个碎片的拼接。

3、假设出现w1w2w3wk情况，这与上述情况相同。因此，人工干预方式及时

间选择也相同。

4.1.4像素绝对差拟配模型求解

对于附件一中碎片复原，根据上述模型，利用matlab软件，求解可得008碎片最

255左端矩阵列与006碎片最右端矩阵列均为：，因此，可知008碎片为复原图最左

255

一个碎片，006碎片为复原图最右端碎片。其余求得所有最小的距离w的值，根据w的

值，可将碎片进行复原。复原结果如下表，复原图像见附录2。

对于附录二英文复原，与上求解过程雷同，利用matlab可得复原结果如下表，复原图

4.1.5问题一综合分析

综上所述，对于问题一的求解过程，未使用人工干预。

碎片进行复原外，同时对具有相同属性的其他图形碎片也进行了复原，效果良好，模型

稳定，可推广到所有只进行竖切的文档恢复。

5

4.2问题二——中文碎片复原

4.2.1问题分析

综合分析。由于考虑问题二在问题一的基础上将碎片分的更加的细小，那么碎片的灰色像素矩阵数据在原有的基础上将会变得少很多，考虑使用问题一方法及模型，那么首先就要构造出与问题一相同的19个竖碎片，因此考虑将所有碎片分为19组，但经过试验分为19组后，由于空白出现太多，在每组中将11个碎片拼接在一起是相当困难的。因此，转变思想，考虑将所给所有碎片分为11个组，在每个分组中将19张碎片拼接在一起，然后在将11个分组拼接在一起完成最后解答。

具体操作。要想将11*19张图片分为11组，考虑文字具有行高的性质，分组中所拼接的19张碎片，所有文字具有的行高应该都是相同的。根据这一思想，可将所有碎片导入matlab中，编程计算可得每张碎片符号距离碎片上下端的像素位，并将所有结果导入excel中，然后根据分类与聚类思想，利用excel表格处理，将碎片符号距离碎片上下端的像素位“相同”（不是绝对相等，允许误差前后波动两个像素）的点分为一组，对于出现空白位置误差较大的点可根据单边距离进行分类与聚类，若根据单边无法确定具体分入那组，那么就同时分入可能的分组中。分组完成后那么每个分组中的图片定能拼接为一行图片，那么我们可建立左右连接点数目最匹配模型，结合人工干预，将每个分组中图片拼接在一起。最后利用问题一中模型可将11个分组拼接在一起得到原图。具体流程如下图：

图3问题二解答流程图

4.2.2数据处理

将209张碎片导入matlab中，编程得到每张碎片灰色像素矩阵，然后在利用矩阵编写程序得到每张碎片字符距离上下边界的像素位，并将其导入excel中（具体代码见

6

得到像素位上下边缘距离后可根据上下距离“相等”（不是绝对相等，允许误差前后波动两个像素）原则，利用excel表格处理将所给数据分为11组。其中距上边缘距离为0，

在每一分组内，再利用matlab编程计算每张碎片左端与右端具有的可连接点数目（采用四舍五入原则）(具体代码见附录7)，下表为上一分组数据的左右连接点数目：（其

4.2.3左右连接点数目最匹配模型[1]

本模型属于半自动模型，需人工干预，具体步骤如下：

1、选取任一分组左右连接点数目情况表，观察左右连接点数；

2、选取左端连接点数目为0的碎片作为最左端碎片，并将该图片作为基准图片；

3、观察基准图片右端连接点数目，从未拼接图片左端连接点数目中找寻与该数目最接近的碎片，人工控制，观察是否可连接。若可连接则拼接上，并将新拼接上碎片作为基本图片，若不可连接，则重新找寻符合要求的碎片，观察是否可连接；

4、重复3步骤，直到将图片全部连接完成。

4.2.4模型求解

以上述模型为标准，考虑数据处理中那行连接过程。首先，寻找19个点钟左端连

接数为0的点，找到（94）号碎片，将其作为基准图片，观察其右边连接点数为4，从其余碎片中找寻发现（34）（43）（77）左端连接数均为4，因此，通过人工干预，观察图片字样走势发现只有（34）号碎片符合要求，再将（34）号图片作为基准图片，其右端连接点数为7，从未连接碎片中找寻发现（84）（149）号均为7，同理（84）碎片作为基准图片，以此类推即可得到该分组图片排序为：（94）（34）（84）（183）（90）（47）（121）（42）（124）（144）（77）（112）（149）（97）（136）（164）（127）（58）（43）其具体碎片拼接图形如下：

然后根据上述模型，以相同的办法结合附录6中分组情况即可将全部11个分组中

7

图片的连接情况找出，然后利用问题一中像素绝对差拟配模型即可拼接处原图，得到原

4.2.5中文碎片恢复综合分析

由于解决本问题使用的左右连接点数目最匹配模型，属于半自动模型。因此，对

干预方式为：终止程序继续运行，将程序拼接过程恢复至上一步（出现碎片拼接不吻合时的前一步），然后将程序用于拼接的碎片导出，再恢复程序继续运行，找到该步拼接吻合碎片并拼接后，再将导出碎片重新导入继续运行程序。

干预时间节点:干预时间节点即对每行碎片单独拼接时，出现碎片拼接不吻合情况时的节点。

4.3问题二——英文碎片复原4.3.1问题分析

对于附录四英语碎片恢复，由于英文与汉字写法不同，英语中弧线居多，而汉字中直线居多。因此，可以采用另一种方式对英文碎片进行拼接，依然考虑问题一中的像素绝对差拟配模型，可首先任意选择一张基础碎片，然后利用该模型进行适应性匹配，匹图4英文碎片复原流程图

8

4.3.2模型建立

1.1像素绝对值拟配模型

令碎片导入matlab编程计算所得的灰色像素矩阵为：

iia11a12a1iniiia21a22a2nai,n72,m180,1i19iiaim1am2amn

由于碎片像素为72*180，因此矩阵ai也是72*180的，矩阵每一列数据即为碎片相应列像素值，其中每个像素点ai

mn表示此处为黑色或白色。

令right(i)表示灰色像素矩阵最右边列，那么

a1iniaright(i)2n,n72,m180,1i19

aimn

令left(k)表示灰色像素矩阵最左边列，则

ka11kaleft(k)21,n72,m180,1k19

akm1

令w表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值的和。那么有

wright(i)left(k)

1180

其中0i19,0k19

根据上述模型即可确定某一碎片灰度像素矩阵最右边列与其余未拼接碎片最左边列的绝对差值，下面讨论因差值不同而产生的匹配问题。

1、最左列的确定：当出现某一碎片灰度像素矩阵最左列均为255时，那么说明该碎片为原始图像的最左列。

2、假设出现w1w2w3wk情况，那么首先将wk对应的碎片与该基准碎片进行拼接，若拼接不合适，这时就需要人工干预，换wk1对应的碎片与基准碎片进行拼接。情况如下：

这是不确定的，而进行人工干预后将会出现下面情况：

9

这样就能正确的完成两个碎片的拼接。

3、假设出现w1w2w3wk情况，这与上述情况相同。因此，人工干预方式及时

间选择也相同。

1.2人工干预

在进行像素绝对值拟配模型计算后，将会得到与基准碎片拼接度最大的几个碎片，

然后利用这几个碎片可进行人工干预，具体人工干预模型如下：

1、首先将程序计算得到的拟配程度最大的碎片与基准碎片进行拼接；

2、人工判断拼接是否合理；

3、若拼接合理则进行下一次拟配模型计算，若拼接不合理则找寻第一步中与基准碎片

拟配差一点的碎片进行拼接；

4、直到找到拼接成功的点才结束本次拼接，并将新拼接上的图片作为基本图片利用模

型寻找拟配度最高的碎片，返回第一步。

4.3.3模型求解

结合上述模型1.1及1.2可计算得到问题二英文碎片复原图表格如下，具体图像见

4.2.4英文碎片恢复综合分析

由于英文碎片相似程度高于中文图片。所以每一次以基准图片找寻最佳匹配图形时

很多时候出现多张图片符合匹配，因此，对此英文碎片的恢复进行了人工干预。恢复此

英文文档，本模型一共进行了39次人工干预。

干预方式为：终止程序继续运行，将程序拼接过程恢复至上一步（出现碎片拼接不

10

吻合时的前一步），然后将该步程序用于拼接的碎片导出，再恢复程序继续运行，直到找到与该基准碎片拼接吻合碎片并拼接完成。

干预时间节点:当出现与基准碎片匹配不吻合时。

4.3问题三

4.3.1问题分析

考虑问题三附录中所给图片具有正反面，却不知每一个序号中a是正面还是b是正面，这也真是问题二英语复原与问题三双面复原的区别。因此，问题二中所用的分类与聚类的方法不能完成分组。为了完成分组，我们可考虑使用一种更加严密，严苛的分类方法，只要分类完成，那么再使用问题二连接图片的办法即可实现图片的复原。

4.3.2模型建立[2]

许多聚类算法的基本框架是搜索与合并。如在层次方法中需要搜索两个距离最近的类簇然后合并；而基于密度的聚类算法则不断地搜索高密子区域，然后利用连通性将其合并到当前聚类结果中。很明显，搜索过程需要面对整个样本集合，通常会导致算法低效。如DBSCAN需要测试每个对象是否是核心对象，并对每个核心对象搜索其直接密度可达的对象，如果没有空间索引的辅助，DBSCAN算法的复杂度为O(n2)。实际上，现有的很多聚类算法已经关注到这个问题，如CURE算法利用采样方法减小搜索空间，而Chameleon算法则通过图划分算法将样本对象聚类为大量相对较小的子簇。具体到

K-Means算法实质上是一种将聚类视为密度估计问题的概率方法。在概率方法中，假设样本来自于如下形式的混合模型:

p(x|)jkp(cj)pj(x|j,cj)

式中，(1,,k)是待估计的参数向量；条件概率密度p(x|j,cj)，称为分量密度，表示类别j的概率密度形式，且参数向量j未知；先验概率p(cj)称为混合因子。为了简化问题，K-Means算法进一步假设:(1)每个类别的概率密度形式为球形高斯分布，即j(j,)且122，j,2未知，（2）每个样本唯一地属于一个类别；(3)假设所有类别的混合因子相等。于是,混合模型简化为

112p(x|)max(x|j,,cj)maxexp(||x||)(1)j2d/222j1:kj1:k(2)

该简化模型可以通过最大似然方法求解,对于观测样本X(x1,,xn)X=(x1,„,xn),相应的对数似然函数为：

xicj

最大化该对数似然函数等价于最小化上式的欧氏距离平方项,即得到K-Means的误差平方和准则:i1j1l(X)lnp(xi)nln[(2)n2d/2]122k||2||xij(2)

11

Jck

j1xjcj||xij||2(3)

通过迭代优化上述的误差平方和准则,K-Means算法最终可以估计出每个高斯分量的均值向量和协方差矩阵2I。式中,nj是类簇cj的样本数目。

Jc1k2||x||ijndj1xjcjnd2(4)

要获得更有效的样本密度估计,Je的值自然是越小越好.但是,Je的值不仅取决于样本的分类情况,而且与类别数目k有关.当类别数目k给定时,Je的值由样本的分类情况所决定,且存在一个最小值Jkmin对应于最优的样本类别划分.如果类别数目k和高斯混合模型假设与实际问题相匹配时,最小值Jkmin必定很小,从而可以很好地近似样本密度;而如果模型假设不合理,则最小值Jkmin可能依然很大,对样本分布的近似效果较差。

对于任意形状的类簇,很明显不能直接要求数据分布满足高斯混合模型的假设,否则会导致最小的误差平方和Jkmin很大.实际上,高斯混合模型具有很强的表达能力,如果高斯分量密度的数目k足够大,则高斯混合模型几乎可以近似任意一种概率分布。换言之,随着类别数目k的增加,相应的Jkmin会减小。简单证明如下:

类别数目k的增加,必然导致最终每个类簇的形状缩小,对应于高斯分量的2减小；而从公式(3)和公式(4)可以得出Jkminnd2,即最小的误差平方和正比于2；因此,k的增加会导致最小的误差平方和Jkmin的减小。极端情况下,kn,则每个样本点都是一个类簇,即Jkmin0,说明此时的经验误差为0,但是此时,模型的推广能力极差。根据统计学习理论,经验误差最小并不等于期望误差最小,经验风险只有在样本数无穷大时才趋近于期望风险.因此,经验误差最小不能保证分类器的推广能力,需要找到经验风险最小和推广能力最大的平衡点。同样,利用足够多的高斯分量组成的混合模型来描述数据会导致过拟合的问题,影响模型的推广能力。因此,在K-MeanSCAN算法中,我们采用过拟合-剪枝的策略进行聚类,即首先使用分量足够多的高斯混合模型来较好地近似样本分布,然后通过合并一些高斯分量的剪枝策略来处理过拟合问题。

4.3.3模型求解

根据上述K-Means局部最优性的高效聚类模型，利用matlab编程计算后结合人为

4.3.4最终求解

上述模型求解结束后，结合问题二英文求解模型及人工干预时机，可将原图还原，其具体还原图像见附录12，具体还原图像表格如下：

12

4.3.5问题三综合分析

对于本问题，由于英语碎片出现正反两面，分类时情况复杂。因此，恢复原文时进行了多次人工干预。

干预方式：对正反英文碎片进行分类结束后，对未归类的碎片，采用人工归类方法，进行多次干预。在每一类中进行碎片拼接时，出现拼接不匹配时，终止程序继续运行，将程序拼接过程恢复至上一步（出现碎片拼接不吻合时的前一步），然后将程序用于拼接的碎片导出，再恢复程序继续运行，找到该步拼接吻合碎片并拼接后，再将导出碎片重新导入继续运行程序。

干预时间节点：分类完成后，对未进行归类的碎片进行人工分类时，还有当进行拼接出现拼接碎片不吻合时。

五、模型评价与推广

5.1模型的优点

使用该模型，可以很好的提高工作效率，将原来使用纯手工拼接过程变得简单合理，而且拼接过程全部在计算机上进行，使得结果更加准确，从碎片出发复原原图像，以点代面的做法，使思路更加简单明了；运用matlab计算及绘出图形，用数形结合的方法来进行分析，模型思路更加清晰，更有说服力。5.2模型的缺点

模型求解过程中，很多地方使用了人工干预，使得整个过程不能实现完全的智能化。有时的四舍五入也可能是结果有些偏差。5.3模型的推广

该题所建模型求解的是与相似图形的匹配问题，在实际生活中，与图像相似，匹配，识别相关的问题，均可以使用该模型进行运算。

对于本题问题三，我们也可从另一方面入手考虑，由于每个碎片为180*72像素的，所含信息量较少，因此，使用问题一的方法直接求解不行。如果我们在保证图片大小不变的情况下，增加图片的像素或者寻求另一种模式使碎片分组更加细，那么直接运用方法一求解规则碎片复原将变得相当的容易。

六、参考文献

[1]/view/5c6a7fc8102de2bd96058886.html.2013.09.15[2]/1000-9825/19/1683.pdf.2013.09.15

14

七、附录

附录1，使用软件名称：matlab(daima1)A=imread(‘附件1\000.bmp’);%区图片的相对路径

附录2，使用软件名称：matlab(daima2)functionPho1

clc

clearall

A=imread(‘附件1\000.bmp’);%区图片的相对路径

[m,n]=size(A);

pho=ones(m,1)*255;

sort=zeros(1,19);

x=0;

15

left=zeros(m,1);

right=zeros(m,1);

local=0;

Used=zeros(19,1);

B=zeros(1,19);

fori=1:19%首先找到最左两边的碎片

ifi<11

str=strcat(‘附件1\00’,num2str(i-1),’.bmp’);

else

str=strcat(‘附件1\0’,num2str(i-1),’.bmp’);

end

a=imread(str);

left=a(:,1);%取第一列

iflength(find(left>250))>1700%当第一列所有数据为白色时，就定义为这个碎片在图片的最左边

pho=cat(2,pho,a);

Used(i)=1;

x=x+1;%图片的顺序

sort(x)=i-1;

right=a(:,n);%取最后一列

break;

end

end

fori=1:18

min=999999999999999999;

fork=1:19

ifUsed(k)~=1

ifk<11

str=strcat(‘附件1\00’,num2str(k-1),’.bmp’);%拼接图片路径

else

str=strcat(‘附件1\0’,num2str(k-1),’.bmp’);

end

a=imread(str);

left=a(:,1);%取第一列

distance=abs(right-left);

temp=sum(sum(distance));

iftemp<min

max=temp;

local=k;

end

end

ifUsed(local)~=1&&k==19

iflocal<11

str1=strcat(‘附件1\00’,num2str(local-1),’.bmp’);

else

str1=strcat(‘附件1\0’,num2str(local-1),’.bmp’);

end

goal=imread(str1);

pho=cat(2,pho,goal);%将得到的碎片加入到图片中

right=goal(:,n);%取右边

16

Used(local)=1;%将这个碎片设置为已经使用x=x+1;%图片的顺序

sort(x)=local-1;

end

end

end

pho(:,1)=[];

imshow(pho)

imwrite(pho,’附件1\true1.bmp’,’bmp’)

sort

end

附件3，使用软件名称：matlab(daima3)

17

%--------附件一拼接---------%

functionPho2

A=imread(‘附件2\000.bmp’);%取图片的相对路径

[m,n]=size(A);

pho=ones(m,1)*255;

sort=zeros(1,19);

x=0;

left=zeros(m,1);

right=zeros(m,1);

local=0;

Used=zeros(19,1);

fori=1:19%首先找到最左两边的碎片

ifi<11

str=strcat(‘附件2\00’,num2str(i-1),’.bmp’);

else

str=strcat(‘附件2\0’,num2str(i-1),’.bmp’);

end

a=imread(str);

left=a(:,1);%取第一列

iflength(find(left>250))>1900%当第一列所有数据为白色时，就定义为这个碎片在图片的最左边

pho=cat(2,pho,a);

Used(i)=1;

x=x+1;%图片的顺序

sort(x)=i-1;

right=a(:,n);%取最后一列

break;

end

end

x

fori=1:18

min=999999999999999;

fork=1:19

ifUsed(k)~=1

ifk<11

str=strcat(‘附件2\00’,num2str(k-1),’.bmp’);%拼接图片路径

else

str=strcat(‘附件2\0’,num2str(k-1),’.bmp’);

end

a=imread(str);

left=a(:,1);%取第一列

distance=abs(right-left);

temp=sum(sum(distance));

iftemp<min

min=temp;

local=k;

end

end

ifUsed(local)~=1&&k==19

iflocal<11

str1=strcat(‘附件2\00’,num2str(local-1),’.bmp’);

else

18

str1=strcat(‘附件2\0’,num2str(local-1),’.bmp’);end

goal=imread(str1);

pho=cat(2,pho,goal);%将得到的碎片加入到图片中right=goal(:,n);%取右边

Used(local)=1;%将这个碎片设置为已经使用x=x+1;%图片的顺序

sort(x)=local-1;

end

end

end

pho(:,1)=[];

imshow(pho)

imwrite(pho,’附件2\true.bmp’,’bmp’)

sort

附录4，使用软件：matlab（daima4）

%-----对应图片上下边缘的高度---------%

functionread_height

clc

TotleUD=zeros(3,208);

TotleLR=zeros(3,208);

Up_H=zeros(2,208);

Dw_H=zeros(2,208);

L_H=zeros(2,208);

R_H=zeros(2,208);

A=imread(‘附件3\003.bmp’);

[m,n]=size(A);

temp=ones(1,n)*255;

temp1=ones(m,1)*255;

fori=1:209

Up_height=0;

Dw_height=0;

L_height=0;

R_height=0;

ifi<11

str=strcat(‘附件3\00’,num2str(i-1),’.bmp’);elseifi>=11&i<101

str=strcat(‘附件3\0’,num2str(i-1),’.bmp’);else

str=strcat(‘附件3\’,num2str(i-1),’.bmp’);end

a=imread(str);

%计算上方高度

k=1;

whilea(k,:)==temp

Up_height=Up_height+1;

k=k+1;

end

%计算下方高度

19

x=m;

whilex~=0&a(x,:)==tempDw_height=Dw_height+1;x=x-1;end

%计算左边高度forj=1:n

ifa(:,j)==temp1

L_height=L_height+1;else

break;endendj=n;

whilej~=0&a(:,j)==temp1;R_height=R_height+1;j=j-1;end

Dw_H(1,i)=i-1;

Dw_H(2,i)=Dw_height;Up_H(1,i)=i-1;

Up_H(2,i)=Up_height;L_H(1,i)=i-1;

L_H(2,i)=L_height;R_H(1,i)=R_height;R_H(2,i)=R_height;TotleUD(1,i)=i-1;

TotleUD(2,i)=Up_height;TotleUD(3,i)=Dw_height;TotleLR(1,i)=i-1;

TotleLR(2,i)=L_height;TotleLR(3,i)=R_height;end

TotleUD;TotleLR;

%xlswrite(‘附件3\上下边界.xls’,TotleUD);%xlswrite(‘附件3\左右边界.xls’,TotleLR);End

20

21

附录7，使用软件：matlab(daima5)%计算左右节点clc;clearall;

22

A=imread(‘附件3\000.bmp’);

[m,n]=size(A);

countTotle=0;%黑色点的总个数

countSame=0;%相同点的个数

Used=zeros(209,1);

x=0;

pho=ones(m,n)*255;

sort=zeros(1,209);

local=0;

Left=zeros(1,209);

Right=zeros(1,209);

b=zeros(209,1);

fori=1:209;

ifi<11

str=strcat(‘附件3\00’,num2str(i-1),’.bmp’);

elseifi>=11&&i<101

str=strcat(‘附件3\0’,num2str(i-1),’.bmp’);

elsei>=101

str=strcat(‘附件3\’,num2str(i-1),’.bmp’);

end

a(:,:,i)=imread(str);%第i张图片的像素矩阵

left(:,1,i)=a(:,1,i);%第i张图片的左边第一列

right(:,1,i)=a(:,n,i);%第i张图片的右边第一列

Left(1,i)=length(find(left(:,1,i)==0))/3.2;

Right(1,i)=length(find(right(:,1,i)==0))/3.2;

end

Left

Right

left(:,1,1)’;

right(:,1,1)’;

pic=cat(2,a(:,:,1),a(:,:,2));

%imshow(pic)

附录8，使用软件：matlab所有节点左右节点数目

Left=

Columns1through9

7.18759.37505.31251.25000.93753.12503.437501.8750Columns10through18

2.18759.06250.937512.18755.000002.50009.68758.1250Columns19through27

5.312513.12502.81252.18755.62500.937511.25008.437517.1875Columns28through36

13.75007.187503.43755.00003.125010.31254.68752.1875Columns37through45

3.75008.125007.187510.625012.500012.500011.87507.5000Columns46through54

9.06250.31254.687513.437502.18755.000014.062512.5000Columns55through63

5.93754.06252.50002.812516.25001.87503.437500Columns64through72

5.00005.31254.68752.1875010.62505.62503.12500Columns73through81

23

5.62502.81254.375012.18756.87503.43752.18756.87500Columns82through90

1.87507.50001.25004.06255.31252.81256.56254.37500Columns91through99

8.75005.62504.375012.500008.43754.375015.31254.0625Columns100through108

8.43756.25004.687506.87500.93752.187505.3125Columns109through117

5.93752.812515.31251.25005.31256.25002.500010.62506.5625Columns118through126

1.56250.62501.87502.18753.43752.81250.93756.87500Columns127through135

5.00003.75004.062508.750019.37502.50006.87501.5625Columns136through144

01.875013.12500.31251.25001.56254.37509.06250Columns145through153

9.06251.87500.62505.00005.00006.56254.37503.437512.1875Columns154through162

2.50004.06253.125010.31256.56253.12504.06256.56251.8750Columns163through171

3.43751.56259.37505.31254.06250.625009.06259.0625Columns172through180

3.75004.06252.812511.87501.25002.18754.687514.06258.4375Columns181through189

3.750012.8125000.62503.12507.50003.12505.0000Columns190through198

5.31254.06259.68758.12504.37503.43753.12506.56254.0625Columns199through207

5.62501.87509.68758.125012.187515.31253.12503.750010.0000Columns208through209

0.62504.3750

Right=

Columns1through9

15.93754.37504.06253.75004.06252.18754.68755.31251.5625Columns10through18

2.18751.25008.43751.875003.43756.56250.62500Columns19through27

02.187512.50002.81251.25004.68752.81251.87505.0000Columns28through36

3.43755.31253.750011.25006.87502.187514.68754.06252.1875Columns37through45

012.81259.06255.93752.500012.18755.625009.6875Columns46through54

22.50001.87503.12505.00004.37508.43759.68753.12503.4375Columns55through63

4.68757.18753.43758.43753.4375003.43758.7500Columns64through72

6.25000.625