haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 初中数学初中数学

建模B题v3.0

发布时间:2013-09-18 08:47:19  

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

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

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

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

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

我们参赛选择的题号是(从A/B/C/D中选择一项填写): 我们的参赛报名号为(如果赛区设置报名号的话): 所属学校(请填写完整的全名): 参赛队员 (打印并签名) :1. 指导教师或指导教师组负责人 (打印并签名):

日期: 年 月 日

赛区评阅编号(由赛区组委会评阅前进行编号):

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

编 号 专 用 页

赛区评阅编号(由赛区组委会评阅前进行编号):

全国统一编号(由赛区组委会送交全国前编号):

全国评阅编号(由全国组委会评阅前进行编号):

碎纸片的拼接复原

摘要

碎纸片的拼接复原技术是借助计算机把大量的不规则的图像碎片拼接成初始图像的完整模型,在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

针对问题一:

针对问题二:

(1)将所有图片的像素转化为矩阵,其次采用人工干预的方式找出第一行第一张碎纸片,然后将所有图片灰度二制化,将灰色像素值转化为黑色像素值,然后由上至下找出黑白像素的分界线,根据分界线位置的差异值最小聚合出第一行所有的图片,同理聚合出第一列所有的图片,将第一行所有图片利用问题一的拼接算法求解出第一行图片拼接顺序。

(2)以第一行第一张碎纸片下侧像素点与其他碎纸片上侧像素点像素匹配差异值最小为目标函数,依次穷举第一列所有的碎纸片,从而找出第二行第一张碎纸片。

(3)根据第一行排好顺序的碎纸片以及第二行第一张碎纸片,采用上下侧边缘像素匹配以及左右侧边缘匹配,依次找出并排列好第2行,其他行依理重复步骤(2)、(3)即可。

(4)完成匹配后,进行适当的人工干预即可确定碎纸片的复原图。 针对问题三:

(1)以文字位置为标准通过聚类的方法分为多组图片,选取一组上侧有留白的图片作为首行备选图片和一组左侧有留白的图片作为首列备选图片,再选取一张左侧和上侧都有适当留白的图片作为左上角的图片;

(2)在首行备选图片中,从左侧的图片开始,以图片a、b面边缘的相似度为标准,搜索与当前图片相邻的图片,直至首行搜索完成;

(3)对于剩下的每一行,在首列备选图片中,图片以a、b面上下边缘相似度为标准,选取一张图片作为该行左侧图片;

(4)对于该行剩下的位置,以a、b面上下相似度与左右相似度为标准,匹配图片。对于其余行重复步骤3、4。匹配完成后,观察图片,并适当进行人工干预进行微调。

最后,

关键词:相似度 优化模型 聚类分析 像素匹配差异值

1

1、问题重述

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

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

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

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

2.基本假设

1、假设破碎纸片切割均匀;

2、假设人工干预找出的第一张图片是准确的;

3、假设人工干预后调整的图片顺序是准确的;

4、假设图片切割成碎纸片的过程中没有丝毫损坏;

5、假设图片切割过程中没有出现完全相同的碎纸片。

3.符号说明

2

4.问题一模型的建立与求解

4.1问题一分析

该问题的目标是建立最合适的碎纸片拼接复原模型和算法来复原仅纵向切割的图片。

首先应先对碎纸片进行预处理,将碎纸片的像素分布转换为矩阵,然后设计出匹配算法对碎纸片就行匹配,本题拟采用优化模型来拼接复原碎纸片,在此过程中,既应考虑到精确,又要考虑到高效。

考虑到高效问题,我们可从人工干预出发,采取适当的人工干预找出第一张碎纸片,这样可以减少穷举的数量,从而大大的加快执行效率。考虑到精确问题,我们可从碎纸片的边缘像素分布出发,建立优化模型,以各碎纸片的边缘像素匹配差异值最小为目标函数,依次穷举找出与前一张图片像素匹配差异值最小的图片,进而就能从左到右依次确立各碎纸片的顺序。

最后将求得的碎纸片拼接顺序拼接在一起即可得到最终结果。

4.2问题一模型准备

(1)图像像素的量化方法

此题显示的是位图,它是由像素阵列的排列来实现其显示效果的,每个像素

3

有自己的颜色信息,因此我们可以通过各个图像的像素来使各图像数字化。

考虑到matlab能够对图像进行有效的匹配,需要把碎纸片图像转换成matlab能够识别的数据,为此,我们采用了imread()函数,将各图片转化成由像素构成的矩阵,因而将图片的匹配问题转化为了对像素差异求最优解的问题。

(2)图片贴近度

模糊数学中常用贴近度来来描述两个模糊集之间的距离,在某种意义上,贴近度就是 1 - 距离(这里的距离是上述标准化意义上的距离)。而之所以应用这个变换,是考虑到“度”的概念的直觉反映——距离越近,贴近的程度显然越“高”,因此它恰为距离的反数。因此我们也可以把贴近度的概念延伸,用图片贴近度用以描述两张图片的相近程度。图片贴近度主要由两张图片的像素匹配差异值决定。两张图片像素匹配差异值越小,图片贴近度越高;反之,图片贴近度越低。

(3)图片像素匹配差异值求解方法

在图论中,一个图是一个匹配(或称独立边集)是指这个图之中,任意两条边都没有公共的顶点。这时每个顶点都至多连出一条边,而每一条边都将一对顶点相匹配。同样,我们在图像拼接中运用类似的匹配思想。把前一个图片像素点构成的矩阵最后一列与后一个图片像素点构成的矩阵的第一列对应做差后取绝对值再求和即可求得两张图片像素的匹配差异值。

(4)对碎纸片图像文字的处理。

图1:附录1中碎纸片图像的文字处理

①在逻辑上将图像划分为n*m格(n*m为碎纸片的分辨率);

②对最左边一列从上至下取各格的值,该列获得的值组成一个向量;最右边一列处理相同同,同时标记是左还是右;

③用任一左边向量和所有右边向量比较,记下每一左边向量与所有右边向量的距离,然后对距离进行排序,对于距离值较小的,可认为该距离对应的左、右边可拼接,对于距离值差距在较小范围内的为多重可拼接(拼接重码),此时需要进行人工干预。

4

4.3问题一模型的建立

图2:问题一模型求解流程图

(1) 碎纸片预处理

预处理的目的是将待处理物体表示为适合于计算机处理的形式。对于碎纸片来说,就是将其像素化、数字化,为此,我们利用Matlab软件中的imread()函数对碎纸片进行量化,由于题目中所给的碎纸片图像分辨率都是1980?72,所以我们将每张碎纸片都转换成了1980?72的矩阵。

(2) 碎纸片匹配

对于碎纸片的匹配,首先,我们利用人工干预找出了第一张纸片,然后取出第一张纸片矩阵的最后一列,利用公式依次跟其余18张纸片矩阵的第一列做差、取绝对值、求和求出第一张碎纸片跟其他碎纸片的像素匹配差异值, 以像素匹配差异值最小为目标函数,得到问题的模型如下:

min???|pti?1?phj|目标函数:

i?2j?11919 (1)

根据像素匹配差异值越小,图片贴近度越高,找出与第一张碎纸片像素差异值最小的图片作为第二张拼合的图片,其他图片的匹配以此类推。

(3) 碎纸片的拼接合并

根据匹配算法求得的图片拼接顺序,利用Matlab的imshow()方法将排好的顺序拼接成图像即可。

5

4.4问题一模型的求解

针对附件1中的碎纸片,采用上述模型运用Matlab求解,得出每张碎纸片与其他碎纸片的像素匹配差异值如下表所示:

表1:附件1中每张碎纸片与其他碎纸片的像素匹配差异值

6

根据表1中的数据结果即可得到附件1图像拼接顺序依次为:008,014,012,015,003,010,002,016,001,004,005,009,013,018,011,007,017,000,006

附件1碎纸片的复原图详见附录1图1。

按照相同的算法可求得附件2的拼接顺序为:003,006,002,007,015,018,011,000,005,001,009,013,010,008,012,007,017,000,006 附件2碎纸片的复原图详见附录2图2。

5.问题二模型的建立与求解

5.1问题二分析

该问题的目标是建立最合适的碎纸片拼接复原模型和算法来复原既纵切又横切的图片。问题二与问题一的区别在于碎纸片的切割由纵切变成了既有纵切又有横切的,所以问题一采用的人工干预找出第一张图片及简单地通过前后两张碎纸片的贴近度进行排列会产生相当大的误差,因此我们拟采用聚类分析方法建立优化模型来拼接附加2中的碎纸片。

(1)我们人工干预选出一组上侧留有空白的图片作为备选图片,以及选取一张左侧跟上侧都留有空白的图片作为拼接的第一张图片,其次将选取的第一张图片为基准采用相应的拼合算法不断的向左向下匹配下一张图片。对于碎纸片上的文字处理可采取以下方式:

7

图3:附录3碎纸片文字像素处理图

首先用Matlab中的imread()函数读取图片,将图片像素转化为相应的矩阵, 其次将矩阵中处于0~255之间的数值所在的行的全部数值转化为0(即将所有灰色像素点转换为黑色像素点,并将其所在的行全部转化为黑色像素点),然后由上至下找出黑白像素的分界线,并依次将第一张图片的分界线与其他图片的分界线进行差异匹配,从而分类聚合出第一行所有的图片。

(2)利用问题一中的拼接算法,以第一张图片右侧边缘像素点与第一行所有图片左侧边缘像素点像素匹配差异值最小为目标函数,建立优化模型,从而排列出第一行所有图片的顺序。

(3)同理,将剩余图片像素矩阵中处于0~255之间的数值所在的列的全部数值转化为0,然后由左至右找出黑白像素的分界线,并依次将第一张图片的分界线与其他图片的分界线进行差异匹配,从而分类聚合出第一列所有的图片。

(4)改进问题一中的算法,以第一张图片下侧边缘像素点与第一列所有图片上侧边缘像素点像素匹配差异值最小为目标函数,建立优化模型,从而确定出第二行第一张碎纸片,然后将第二行第一张碎纸片的右侧边缘像素点与待排图片左侧边缘像素点以及与上一行中对应图片下侧边缘像素点与待排图片上侧边缘像素点的像素匹配差异值最小为目标函数,建立优化模型,依次穷举出所有未排序的图片,找出第二行第一张碎纸片。其他行碎纸片依照此理类推即可排出顺序。

(5)所有图片匹配完成后,对于拼接错误的图片进行相应的人工干预即可求得最后的图像复原图。

5.2问题二模型准备

(1)图片像素的量化和图片贴近度

考虑到要根据图片之间的像素贴近度进行匹配,需要用Matlab软件将碎纸片像素量化,将像素分布转化为相应的数据。为此,我们采用了imread()函数,将各图片转化成由像素构成的矩阵,方便了matlab对图片匹配的处理操作。

图片贴近度用以描述两张图片的相近程度,主要由两张图片的像素决定。两张图片像素匹配差异值越小,图片贴近度越高;反之,图片贴近度越低。

8

(2)图片聚类分析方法

数学建模中,研究对样品或指标分类的一种多元统计方法,是依据研究对象的个体的特征进行分类的方法。聚类分析的基本思想是认为我们研究的样本或指标之间存在着程度不同的相似性。于是根据一批样本的观察的干茶指标,具体找出想死程度较大的样本聚为一类,关系密切的聚到一个小的分类单位,关系疏远的聚到一个大的分类单位,直到所有样本聚合完毕。这样就形成了一个个类,大大减少了数据处理的难度。在图片拼接过程中,将碎纸片图像量化得到的矩阵中数值处于0~255(白色的像素值为255,黑色的像素值为0)之间的数所在的行或列中所有的数值全部转化为0,找出黑白像素的分界线,根据分界线的匹配度进行聚合分类。

5.3问题二模型的建立

图4:问题二模型求解流程图

5.3.1 碎纸片预处理

预处理的目的是将待处理物体表示为适合于计算机处理的形式。对于碎纸片来说,就是将其像素化、数字化,为此,我们利用Matlab软件中的imread()函数对碎纸片进行量化,由于题目中所给的碎纸片图像分辨率都是1980?72,所以我们将每张碎纸片都转换成了的1980?72矩阵。

5.3.2 碎纸片聚类分析及匹配

在碎纸片聚类过程中,首先将所有图片得到的像素矩阵灰度二制化,将灰色像素值转化为黑色像素值,由上至下找出黑白像素分界线,根据上侧跟左侧都留有白的特性人工干预找到第一张图片,然后以与第一张图片黑白像素分界线与其他图

9

片黑白像素分界线差异值最小为目标函数建立优化模型,目标函数如公式(2)所示。.

目标函数:min???|pti?1?phj|

i?2j?019208(2)

我们根据分界线位置的差异值最小,对碎片预处理得到的像素矩阵,聚类分析得到第一行所有的图片,同样运用聚合分析的思想得到第一列所有的图片,根据问题一的匹配方法求出第一行图片的拼接顺序。然后以第一行第一张碎纸片下侧像素点与其他碎纸片上侧像素点像素匹配差异值最小为目标函数,目标函数如公式

(3)所示。

min???|pyh?1?pzj|

h?2j?011208目标函数: (3)

依次穷举第一列所有的碎纸片,找出第二行第一张碎纸片。其次,根据第一行排好顺序的碎纸片以及第二行第一张碎纸片,采用上下侧边缘像素匹配以及左右侧边缘匹配,目标函数如公式(4)所示。

min???(|pti?1?phj|?|pyh?1?pzj|)

h?2j?011208目标函数: (4)

依次找出并排列好第2行。重复上述两个步骤即可得到其余各行的排列顺序。

5.3.3 人工干预及绘图

观察通过Matlab的imshow()对聚类分析及匹配得到的图片顺序的图像,调整不吻合的图片,逐步使得得到的图像准确。

5.4问题二模型的求解

利用聚类分析求解出的附件3跟附件4第一行图片排列顺序见下表: 表2:附录3中采用聚合分析得出的第一行图片顺序

利用聚类分析求解出的附件3跟附件4第一列图片排列顺序见下表: 附件4图片最终拼接顺序见附录4

10

6.问题三模型的建立与求解

6.1问题三分析

该问题的目标是建立最合适的碎纸片拼接复原模型和算法来复原既纵向切割又横向切割的双面打印图片。

问题三与问题二的区别在于需要拼接的碎纸片由仅含单面打印的文字变成了双面打印的文字,如果通过问题二的方法分别对两面拼接,得到的图片很可能正反两个面的各个图片不能一一配对,鉴于此,我们拟采用如下方法拼接图片:首先通过聚类得到首行和首列以及最左上角的图片,然后从最左上角的图片开始,综合考虑a,b两面相似度,从左侧一直搜索倒右侧,逐步确定第一行的图片顺序,其次根据上下贴近度从首列备选图片中选出第二行行第一个,并依此结合上下和左右贴近度依此确定该行的其余图片顺序,重复上个步骤不断搜索,即可得到排列好的正反两面图片,通过简单地人工调整便可得到较为准确的最终两面图片。

6.2问题三模型准备

(1)模拟退火算法

模拟退火算法的目的是求解,精髓是在局部过程中跳过局部最优的陷阱来求最有解,其方法是接受不好的解,继续迭代,这样可以从整体考虑,求出最有解。此题为了避免分别求出的两面的图片不能整合成一张纸,同样可以采用模拟退火算法来求全局最优解。

(2)分叉搜索

由于此题a,b代表两面,不可以统一进行聚类,先分成各行,然后进行匹配,因此我们拟采用分叉查找来进行分类,同时兼顾剩下的另一类,得到的两类比较准确。

6.3问题三模型的建立

首先建立问题三求解的流程图,流程图内容如下图所示

11

图5:问题三模型求解流程图

6.3.1 碎纸片预处理

预处理的目的是将待处理物体表示为适合于计算机处理的形式。对于碎纸片来说,就是将其像素化、数字化,为此,我们利用Matlab软件中的imread()函数对碎纸片进行量化,由于题目中所给的碎纸片图像分辨率都是180?72,所以我们将每张碎纸片都转换成了的180?72矩阵。

6.3.2 碎纸片的匹配

首先根据文字位置,通过聚类将碎片分为多类,选取一组上侧有留白的图片作为首行备选图片和一组左侧有留白的图片作为首列备选图片,再选取一张左侧和上侧都有适当留白的图片作为左上角的图片;然后在首行备选图片中,从左侧的图片开始,利用公式(5)计算碎片的相似度

min?|pta1?pha2|?|ptb2?phb1| (5)

以图片a、b面边缘的相似度为标准,搜索与当前图片相邻的图片,直至首行搜索完成;对于剩下的每一行,在首列备选图片中,利用公式(6)计算碎片的相似度

min?|pya1?pza2|?|pyb1?pzb2| (6) 图片以a、b面上下边缘相似度为标准,选取一张图片作为该行左侧图片;对于该行剩下的位置,利用公式(7)计算相似度

min?|pta1?pha3|?|pya2?pza3|?|ptb3?phb1|?|pyb2?pzb3| (7)以a、b面上下相似度与左右相似度为标准,匹配图片。对于其余行重复上述步

12

骤。匹配完成后,观察图片,并适当进行人工干预进行微调。

6.3.3 碎纸片的拼接合并

根据匹配算法求得的图片拼接顺序,利用Matlab的imshow()方法将排好的顺序拼接成图像即可。

6.4问题三模型的求解

这里我们利用最优化的思想,利用matlab软件,对碎片进行拼接,得到如下图。 (详见附录五)

图6:问题三碎片拼接图

7.模型分析与评价

7.1模型的优点

(1)在进行拼接5张图片之前都进行了简单地人工干预来确定第一张图片,由此可以大大提高后来图片拼接模型的运行效率。

(2)问题一建立的通过像素匹配差异值最小为目标函数,通过循环来穷举剩余图片,比较相邻图片贴近度来建立模型求解,简单明了,易于理解,并且可操作性较强。

(3)问题二和问题三采取的聚类分析方法层次分明,逻辑清晰,并且能有效减少运算量,提高精确度,因此提高的拼接碎纸片的效率。

(4)总的来说,我们采用的模型理解较为容易,也便于操作,对碎纸片拼

13

接的问题有较高的参考价值。

7.2模型的缺点

(1)我们在拼接碎纸片过程当中自始至终都运用了位图像素点的概念,要理解建立的模型,需要对计算机的图像处理知识有一定的了解。

(2)我们在各个问题碎纸片拼接之前进行了人工干预选出第一张,如果选择的第一张不够准确,可能造成建立的整个模型完全错误,因此有一定的难度来选择第一张图片,这给使用此模型的人增加了对图片观察力和分析力的要求。

(3)此模型中需要适当的人工干预来调整初步确定的图片模型,因此需要使用此模型的人了解模型的细节以便进行适时的人工干预。

7.3模型的改进

(1)由于问题一要求排列的图片较少,因此可以依此选择各个图片作为第一张,自动的进行拼接,最后从每张图片作为第一张的得到图片序列中,根据总的贴近度最大原则,选出最优的排列。

(2)我们问题二和问题三中仅采用从上到下、从左到右的方法进行搜索排序,如果再进行从从上到下,从右到左进行搜索排序,应该可以通过人工干预对比来更容易的实现排序。

参考文献

[1]陈华友,《运筹学》,安徽:中国科技大学出版社,2008

[2]杨启帆,《数学建模》,北京:高等教育出版社,2005

[3]姜启源等,《数学模型(第四版)》,北京:高等教育出版社,2011

[4]吴建国,《数学建模案例精编》,北京:中国水利水电出版社,2005.

[5]Huei-Yung等,《Reconstruction of shredded document based on image feature matching》,《Expert Systems with Applications》,第39卷,第3期,3324-3332, 2012。

附录

附录1:

问题一汉字拼接源码:

for i=1:19

14

if(i<11)

imgname=strcat('00',num2str(i-1),'.bmp');

else

imgname=strcat('0',num2str(i-1),'.bmp');

end

I(:,:,i)=imread(imgname);

left(:,i)=I(:,1,i);

right(:,i)=I(:,72,i);

end

ans=zeros(1,19);

ans(1)=9;

for i=2:19

z=zeros(1,19);

for j=1:19

z(j)=sum(abs(int32(right(:,ans(i-1))-left(:,j))))

for k=1:i-1

z(ans(k))=9999999;

end

end

[ma,maid]=min(z);

ans(i)=maid;

end

ans-1

imshow([I(:,:,9) I(:,:,15) I(:,:,13) I(:,:,16) I(:,:,4) I(:,:,11) I(:,:,3) I(:,:,17) I(:,:,2) I(:,:,5) I(:,:,6) I(:,:,10) I(:,:,14) I(:,:,19) I(:,:,12) I(:,:,8) I(:,:,18) I(:,:,1) I(:,:,7)])

15

图7:附件一复原图

附录2

问题一英文拼接源码:

for i=1:19

if(i<11)

imgname=strcat('00',num2str(i-1),'.bmp'); else

imgname=strcat('0',num2str(i-1),'.bmp'); end

I(:,:,i)=imread(imgname);

left(:,i)=I(:,1,i);

right(:,i)=I(:,72,i);

end

ans=zeros(1,19);

ans(1)=4;

for i=2:19

z=zeros(1,19);

for j=1:19

z(j)=sum(abs(int32(right(:,ans(i-1))-left(:,j)))) for k=1:i-1

16

z(ans(k))=9999999;

end

end

[ma,maid]=min(z);

ans(i)=maid;

end

ans-1

imshow([I(:,:,4) I(:,:,7) I(:,:,3) I(:,:,8) I(:,:,16) I(:,:,19) I(:,:,12) I(:,:,1) I(:,:,6) I(:,:,2) I(:,:,10) I(:,:,14) I(:,:,11) I(:,:,9) I(:,:,13) I(:,:,8) I(:,:,18) I(:,:,1) I(:,:,7)])

表7: 附件二复原图碎片顺序

17

图8: 附件二复原图

附录3:

问题二汉字拼接源码:

for i=1:209

if(i<=10)

imgname=strcat('00',num2str(i-1),'.bmp'); elseif(i<=100)

imgname=strcat('0',num2str(i-1),'.bmp'); else

imgname=strcat(num2str(i-1),'.bmp'); end

I(:,:,i)=imread(imgname);

18

left(:,i)=I(:,1,i);

right(:,i)=I(:,72,i);

up(i,:)=I(1,:,i);

down(i,:)=I(180,:,i);

end

left=int32(left);

right=int32(right);

up=int32(up);

down=int32(down);

mAns=zeros(1,19);

mAns(1)=15;

for i=2:19

xsd=zeros(1,209);

for j=1:209

if j==mAns(i-1)

continue

end

xsd(j)=max(sum(abs(right(:,mAns(i-1))-left(:,j)))); for tmp_i=1:209

if sum(up(tmp_i,:)-255)~=0

xsd(tmp_i)=9999999;

end

end

for k=1:i-1

xsd(mAns(k))=999999999;

end

end

format long g

xsd;

[ma,maid]=min(xsd);

mAns(i)=maid;

%%人工干预

if mAns(i-1)==200 mAns(i)=136; end

if mAns(i-1)==204 mAns(i)=170; end

if mAns(i-1)==170 mAns(i)=135;end

if mAns(i-1)==161 mAns(i)=204; end

if mAns(i-1)==40 mAns(i)=32;end

if mAns(i-1)==32 mAns(i)=52;end

if mAns(i-1)==116 mAns(i)=177; end

end

myans=zeros(11,19);

myans(1,:)=mAns;

for hang=2:11

xsd=zeros(1,209);

19

for j=1:209

xsd(j)=max(sum(abs(down(myans(hang-1,1),:)-up(j,:))));

for tmp_i=1:209

if sum(left(:,tmp_i)-255)~=0

xsd(tmp_i)=9999999;

end

end

for tmp_i=1:hang-1

for tmp_j=1:19

xsd(myans(tmp_i,tmp_j))=99999999;

end

end

end

format long g

xsd;

[ma,maid]=min(xsd);

maid;

myans(hang,1)=maid;

if myans(hang-1,1)==95 myans(hang,1)=126;end

if myans(hang-1,1)==8 myans(hang,1)=72; end

if myans(hang-1,1)==72 myans(hang,1)=90; end

if myans(hang-1,1)==62 myans(hang,1)=169; end

for i=2:19

for j=1:209

if j==myans(hang,i-1)

continue

end

xsd(j)=max(sum(abs(right(:,myans(hang,i-1))-left(:,j)))+sum(abs(down(myans(hang-1,i-1),:)-up(j,:))));

for tmp_i=1:hang-1

for tmp_j=1:19

xsd(myans(tmp_i,tmp_j))=99999999;

end

end

for tmp_j=1:i-1

xsd(myans(hang,tmp_j))=99999999;

end

end

[ma,maid]=min(xsd);

maid;

myans(hang,i)=maid;

if myans(hang,i-1)==95 myans(hang,i)=35; end

if myans(hang,i-1)==85 myans(hang,i)=184;end

if myans(hang,i-1)==91 myans(hang,i)=48;end

20

if myans(hang,i-1)==48 myans(hang,i)=122;end if myans(hang,i-1)==125 myans(hang,i)=145; end if myans(hang,i-1)==78 myans(hang,i)=113;end if myans(hang,i-1)==113 myans(hang,i)=150;end if myans(hang,i-1)==128 myans(hang,i)=59; end if myans(hang,i-1)==59 myans(hang,i)=44;end if myans(hang-1,i)==95 myans(hang,i)=126;end if myans(hang,i-1)==14 myans(hang,i)=183;end if myans(hang,i-1)==17 myans(hang,i)=185; end if myans(hang,i-1)==205 myans(hang,i)=140; end if myans(hang,i-1)==65 myans(hang,i)=112;end if myans(hang,i-1)==112 myans(hang,i)=202;end if myans(hang,i-1)==93 myans(hang,i)=181;end if myans(hang,i-1)==76 myans(hang,i)=56;end if myans(hang,i-1)==207 myans(hang,i)=11;end if myans(hang,i-1)==11 myans(hang,i)=105; end if myans(hang,i-1)==173 myans(hang,i)=172; end if myans(hang,i-1)==209 myans(hang,i)=139;end if myans(hang,i-1)==159 myans(hang,i)=127;end if myans(hang,i-1)==127 myans(hang,i)=69;end if myans(hang,i-1)==57 myans(hang,i)=94;end if myans(hang,i-1)==94 myans(hang,i)=154; end if myans(hang,i-1)==154 myans(hang,i)=71; end if myans(hang,i-1)==71 myans(hang,i)=167; end if myans(hang,i-1)==167 myans(hang,i)=33;end if myans(hang,i-1)==157 myans(hang,i)=84;end if myans(hang,i-1)==84 myans(hang,i)=133;end if myans(hang,i-1)==18 myans(hang,i)=81;end if myans(hang,i-1)==147 myans(hang,i)=103;end if myans(hang,i-1)==152 myans(hang,i)=208;end if myans(hang,i-1)==109 myans(hang,i)=118;end if myans(hang,i-1)==118 myans(hang,i)=5;end if myans(hang,i-1)==66 myans(hang,i)=144;end if myans(hang,i-1)==96 myans(hang,i)=12;end if myans(hang,i-1)==23 myans(hang,i)=130;end if myans(hang,i-1)==79 myans(hang,i)=68;end if myans(hang,i-1)==100 myans(hang,i)=163;end if myans(hang,i-1)==80 myans(hang,i)=64;end if myans(hang,i-1)==164 myans(hang,i)=73;end if myans(hang,i-1)==73 myans(hang,i)=7;end if myans(hang,i-1)==7 myans(hang,i)=178;end if myans(hang,i-1)==53 myans(hang,i)=37;end if myans(hang,i-1)==2 myans(hang,i)=88;end if myans(hang,i-1)==88 myans(hang,i)=19;end

21

if myans(hang,i-1)==39 myans(hang,i)=149;end if myans(hang,i-1)==149 myans(hang,i)=47;end if myans(hang,i-1)==47 myans(hang,i)=162;end if myans(hang,i-1)==36 myans(hang,i)=82;end if myans(hang,i-1)==89 myans(hang,i)=168;end end end

myans1=[myans(8:11,1:19);myans(1:7,1:19)]; myans=myans1; myans-1

表8: 附件三复原图碎片顺序

22

图9: 附件三复原图

附录4:

问题二英文拼接源码:

for i=1:209

if(i<=10)

imgname=strcat('00',num2str(i-1),'.bmp'); elseif(i<=100)

imgname=strcat('0',num2str(i-1),'.bmp'); else

imgname=strcat(num2str(i-1),'.bmp'); end

I(:,:,i)=imread(imgname);

left(:,i)=I(:,1,i);

right(:,i)=I(:,72,i);

up(i,:)=I(1,:,i);

down(i,:)=I(180,:,i);

end

left=int32(left);

right=int32(right);

23

up=int32(up);

down=int32(down);

mAns=zeros(1,19);

mAns(1)=160;

for i=2:19

xsd=zeros(1,209);

for j=1:209

if j==mAns(i-1)

continue

end

xsd(j)=max(sum(abs(right(:,mAns(i-1))-left(:,j)))); for k=1:i-1

xsd(mAns(k))=999999999;

end

tmp=[183 3 87 133 68 116 19 20 150 172 21 71]; for tmp_i=1:length(tmp)

xsd(tmp(tmp_i))=9999999999;

end

end

format long g

xsd;

[ma,maid]=min(xsd);

mAns(i)=maid;

%%人工干预

if mAns(i-1)==160 mAns(i)=140; end

if mAns(i-1)==64 mAns(i)=139; end

if mAns(i-1)==154 mAns(i)=54;end

if mAns(i-1)==124 mAns(i)=121; end

if mAns(i-1)==176 mAns(i)=86;end

if mAns(i-1)==86 mAns(i)=51;end

end

myans=zeros(11,19);

myans(1,:)=mAns;

for hang=2:11

xsd=zeros(1,209);

for j=1:209

xsd(j)=max(sum(abs(down(myans(hang-1,1),:)-up(j,:)))); for tmp_i=1:209

if sum(left(:,tmp_i)-255)~=0

xsd(tmp_i)=9999999;

end

end

for tmp_i=1:hang-1

for tmp_j=1:19

24

xsd(myans(tmp_i,tmp_j))=99999999;

end

end

end

format long g

xsd;

[ma,maid]=min(xsd);

maid;

myans(hang,1)=maid;

if myans(hang-1,1)==160 myans(hang,1)=21;end

if myans(hang-1,1)==21 myans(hang,1)=209; end

if myans(hang-1,1)==209 myans(hang,1)=71; end

if myans(hang-1,1)==71 myans(hang,1)=133; end

if myans(hang-1,1)==133 myans(hang,1)=172;end

if myans(hang-1,1)==172 myans(hang,1)=82; end

if myans(hang-1,1)==82 myans(hang,1)=192; end

if myans(hang-1,1)==202 myans(hang,1)=87; end

for i=2:19

for j=1:209

if j==myans(hang,i-1)

continue

end

xsd(j)=max(sum(abs(right(:,myans(hang,i-1))-left(:,j)))+sum(abs(down(myans(hang-1,i-1),:)-up(j,:))));

for tmp_i=1:hang-1

for tmp_j=1:19

xsd(myans(tmp_i,tmp_j))=99999999;

end

end

for tmp_j=1:i-1

xsd(myans(hang,tmp_j))=99999999;

end

end

[ma,maid]=min(xsd);

maid;

myans(hang,i)=maid;

if myans(hang,i-1)==21 myans(hang,i)=42; end

if myans(hang,i-1)==117 myans(hang,i)=137;end

if myans(hang,i-1)==137 myans(hang,i)=74;end

if myans(hang,i-1)==74 myans(hang,i)=37;end

if myans(hang,i-1)==42 myans(hang,i)=22; end

if myans(hang,i-1)==22 myans(hang,i)=8;end

if myans(hang,i-1)==8 myans(hang,i)=50;end

if myans(hang,i-1)==37 myans(hang,i)=208; end

25

if myans(hang,i-1)==50 myans(hang,i)=62;end if myans(hang-1,i)==62 myans(hang,i)=120;end if myans(hang,i-1)==136 myans(hang,i)=16;end if myans(hang,i-1)==77 myans(hang,i)=44; end if myans(hang,i-1)==120 myans(hang,i)=34; end if myans(hang,i-1)==34 myans(hang,i)=143;end if myans(hang,i-1)==169 myans(hang,i)=63;end if myans(hang,i-1)==63 myans(hang,i)=170;end if myans(hang,i-1)==170 myans(hang,i)=55;end if myans(hang,i-1)==200 myans(hang,i)=46;end if myans(hang,i-1)==46 myans(hang,i)=174; end if myans(hang,i-1)==174 myans(hang,i)=80; end if myans(hang,i-1)==80 myans(hang,i)=162;end if myans(hang,i-1)==180 myans(hang,i)=144;end if myans(hang,i-1)==55 myans(hang,i)=193;end if myans(hang,i-1)==193 myans(hang,i)=134;end if myans(hang,i-1)==134 myans(hang,i)=119; end if myans(hang,i-1)==190 myans(hang,i)=163; end if myans(hang,i-1)==163 myans(hang,i)=198; end if myans(hang,i-1)==198 myans(hang,i)=113;end if myans(hang,i-1)==71 myans(hang,i)=85;end if myans(hang,i-1)==85 myans(hang,i)=61;end if myans(hang,i-1)==61 myans(hang,i)=15;end if myans(hang,i-1)==15 myans(hang,i)=69;end if myans(hang,i-1)==69 myans(hang,i)=175;end if myans(hang,i-1)==175 myans(hang,i)=138;end if myans(hang,i-1)==138 myans(hang,i)=196;end if myans(hang,i-1)==196 myans(hang,i)=9;end if myans(hang,i-1)==24 myans(hang,i)=100;end if myans(hang,i-1)==123 myans(hang,i)=91;end if myans(hang,i-1)==96 myans(hang,i)=70;end if myans(hang,i-1)==70 myans(hang,i)=168;end if myans(hang,i-1)==168 myans(hang,i)=164;end if myans(hang,i-1)==189 myans(hang,i)=112;end if myans(hang,i-1)==145 myans(hang,i)=207;end if myans(hang,i-1)==207 myans(hang,i)=4;end if myans(hang,i-1)==28 myans(hang,i)=179;end if myans(hang,i-1)==146 myans(hang,i)=84;end if myans(hang,i-1)==17 myans(hang,i)=10;end if myans(hang,i-1)==126 myans(hang,i)=141;end if myans(hang,i-1)==13 myans(hang,i)=178;end if myans(hang,i-1)==178 myans(hang,i)=125;end if myans(hang,i-1)==191 myans(hang,i)=185;end if myans(hang,i-1)==107 myans(hang,i)=5;end

26

if myans(hang,i-1)==5 myans(hang,i)=150;end if myans(hang,i-1)==150 myans(hang,i)=33;end if myans(hang,i-1)==202 myans(hang,i)=149;end if myans(hang,i-1)==171myans(hang,i)=197; end if myans(hang,i-1)==19 myans(hang,i)=199;end if myans(hang,i-1)==199 myans(hang,i)=95;end if myans(hang,i-1)==79 myans(hang,i)=104; end if myans(hang,i-1)==81 myans(hang,i)=102;end if myans(hang,i-1)==27 myans(hang,i)=101;end if myans(hang,i-1)==7 myans(hang,i)=18;end if myans(hang,i-1)==18 myans(hang,i)=29;end if myans(hang,i-1)==29 myans(hang,i)=147;end if myans(hang,i-1)==87 myans(hang,i)=52;end if myans(hang,i-1)==52 myans(hang,i)=108;end if myans(hang,i-1)==30 myans(hang,i)=41;end if myans(hang,i-1)==159 myans(hang,i)=187;end if myans(hang,i-1)==99 myans(hang,i)=25;end if myans(hang,i-1)==118 myans(hang,i)=151; end if myans(hang,i-1)==151 myans(hang,i)=6; end if myans(hang,i-1)==6 myans(hang,i)=60;end if myans(hang,i-1)==60 myans(hang,i)=59;end if myans(hang,i-1)==59 myans(hang,i)=93; end if myans(hang,i-1)==93 myans(hang,i)=31; end if myans(hang,i-1)==142 myans(hang,i)=89; end if myans(hang,i-1)==106 myans(hang,i)=156; end if myans(hang,i-1)==23 myans(hang,i)=58; end end end

myans-1

表9: 附件四复原图碎片顺序

27

图10: 附件四复原图

附录5:

问题三英文拼接核心代码:

%% 读取图片

readimage;

%% 图片数据转换

pha=int32(pha);pta=int32(pta);pza=int32(pza);pya=int32(pya);phb=int32(phb);ptb=int32(ptb);pzb=int32(pzb);pyb=int32(pyb);

%% 第一行

mAns=zeros(1,19);

mAns_zf=zeros(1,19);%a1b2

mAns(1)=79;

mAns_zf(1)=2;

for i=2:19

28

xsd=zeros(1,209);

xsd_zf=zeros(1,209);%a1b2

for j=1:209

if j==mAns(i-1)

continue

end

tmp_1=0;tmp_2=0;

if mAns_zf(i-1)==1%a

tmp_1=

max(sum(abs(pta(:,mAns(i-1))-pha(:,j))+abs(phb(:,mAns(i-1))-ptb(:,j))));%a+a tmp_2=

max(sum(abs(pta(:,mAns(i-1))-phb(:,j))+abs(phb(:,mAns(i-1))-pta(:,j))));%a+b end

if mAns_zf(i-1)==2%b

tmp_1=max(sum(abs(ptb(:,mAns(i-1))-pha(:,j))+abs(pha(:,mAns(i-1))-ptb(:,j))));%b+a

tmp_2=max(sum(abs(ptb(:,mAns(i-1))-phb(:,j))+abs(pha(:,mAns(i-1))-pta(:,j))));%b+b

end

[xsd(j),xsd_zf(j)]=min([tmp_1,tmp_2]);

for tmp_i=1:209

if sum(pza(tmp_i,:)-255)~=0

xsd(tmp_i)=9999999;

end

end

for tmp_i=1:209

if sum(pzb(tmp_i,:)-255)~=0

xsd(tmp_i)=9999999;

end

end

for k=1:i-1

xsd(mAns(k))=999999999;

end

tmp=[183 3 87 133 68 116 19 20 150 172 21 71];

for tmp_i=1:length(tmp)

xsd(tmp(tmp_i))=9999999999;

end

end

format long g

xsd;

[ma,maid]=min(xsd);

mAns(i)=maid;

29

mAns_zf(i)=xsd_zf(maid);

%%手动

ganrao1;%干扰首行

end

str='第一行'

mAns-1

mAns_zf

%% 汇总第一行答案

myans=zeros(11,19);

myans_zf=zeros(11,19);%1a2b

myans(1,:)=mAns;

myans_zf(1,:)=mAns_zf;

%% 下面的行

for hang=2:11

xsd=zeros(1,209);

for j=1:209

tmp_1=0;tmp_2=0;

if mAns_zf(i-1)==1%a

%tmp_1=max(sum(abs(py(myans(hang-1,1),:)-pz(j,:))));

tmp_1=

max(sum(abs(pya(myans(hang-1,1),:)-pza(j,:))+abs(pyb(myans(hang-1,1),:)-pzb(j,:))));%a+a

tmp_2=

max(sum(abs(pya(myans(hang-1,1),:)-pzb(j,:))+abs(pyb(myans(hang-1,1),:)-pza(j,:))));%a+b

end

if mAns_zf(i-1)==2%b

tmp_1=max(sum(abs(pyb(myans(hang-1,1),:)-pza(j,:))+abs(pya(myans(hang-1,1),:)-pzb(j,:))));%b+a

tmp_2=max(sum(abs(pyb(myans(hang-1,1),:)-pzb(j,:))+abs(pya(myans(hang-1,1),:)-pza(j,:))));%b+b

end

[xsd(j),xsd_zf(j)]=min([tmp_1,tmp_2]);

for tmp_i=1:209

if sum(phb(:,tmp_i)-255)~=0

xsd(tmp_i)=9999999;

end

end

for tmp_i=1:hang-1

for tmp_j=1:19

xsd(myans(tmp_i,tmp_j))=99999999;

end

30

end

end

format long g

xsd;

[ma,maid]=min(xsd);

maid;

myans(hang,1)=maid;

myans_zf(hang,1)=xsd_zf(maid);

%% 手动首列

ganrao2;%干扰首列

for i=2:19

for j=1:209

if j==myans(hang,i-1)

continue

end

tmp_1=0;tmp_2=0;

if myans_zf(hang,i-1)==1%左为a

if myans_zf(hang-1,i)==1%上为a

tmp_1=max(sum(abs(pta(:,myans(hang,i-1))-pha(:,j)))+sum(abs(pya(myans(hang-1,i),:)-pza(j,:)))+sum(abs(ptb(:,myans(hang,i-1))-phb(:,j)))+sum(abs(pyb(myans(hang-1,i),:)-pzb(j,:))));%a+a+a

tmp_2=max(sum(abs(pta(:,myans(hang,i-1))-phb(:,j)))+sum(abs(pya(myans(hang-1,i),:)-pzb(j,:)))+sum(abs(ptb(:,myans(hang,i-1))-pha(:,j)))+sum(abs(pyb(myans(hang-1,i),:)-pza(j,:))));%a+a+b

end

if myans_zf(hang-1,i)==2%上为b

tmp_1=max(sum(abs(pta(:,myans(hang,i-1))-pha(:,j)))+sum(abs(pyb(myans(hang-1,i),:)-pza(j,:)))+sum(abs(ptb(:,myans(hang,i-1))-phb(:,j)))+sum(abs(pya(myans(hang-1,i),:)-pzb(j,:))));%a+b+a

tmp_2=max(sum(abs(pta(:,myans(hang,i-1))-phb(:,j)))+sum(abs(pyb(myans(hang-1,i),:)-pzb(j,:)))+sum(abs(ptb(:,myans(hang,i-1))-pha(:,j)))+sum(abs(pya(myans(hang-1,i),:)-pza(j,:))));%a+b+b

end

end

if myans_zf(hang,i-1)==2%左为b

if myans_zf(hang-1,i)==1%上为a

tmp_1=max(sum(abs(ptb(:,myans(hang,i-1))-pha(:,j)))+sum(abs(pya(myans(hang-1,i),:)-pza(j,:)))+sum(abs(pta(:,myans(hang,i-1))-phb(:,j)))+sum(abs(pyb(myans(hang-1,i),:)-pzb(j,:))));%b+a+a

31

tmp_2=max(sum(abs(ptb(:,myans(hang,i-1))-phb(:,j)))+sum(abs(pya(myans(hang-1,i),:)-pzb(j,:)))+sum(abs(pta(:,myans(hang,i-1))-pha(:,j)))+sum(abs(pyb(myans(hang-1,i),:)-pza(j,:))));%b+a+b end

if myans_zf(hang-1,i)==2%上为b

tmp_1=max(sum(abs(ptb(:,myans(hang,i-1))-pha(:,j)))+sum(abs(pyb(myans(hang-1,i),:)-pza(j,:)))+sum(abs(pta(:,myans(hang,i-1))-phb(:,j)))+sum(abs(pya(myans(hang-1,i),:)-pzb(j,:))));%b+b+a

tmp_2=max(sum(abs(ptb(:,myans(hang,i-1))-phb(:,j)))+sum(abs(pyb(myans(hang-1,i),:)-pzb(j,:)))+sum(abs(pta(:,myans(hang,i-1))-pha(:,j)))+sum(abs(pya(myans(hang-1,i),:)-pza(j,:))));%b+b+b end end

[xsd(j),xsd_zf(j)]=min([tmp_1,tmp_2]);

for tmp_i=1:hang-1 for tmp_j=1:19

xsd(myans(tmp_i,tmp_j))=99999999; end end

for tmp_j=1:i-1

xsd(myans(hang,tmp_j))=99999999; end end

[ma,maid]=min(xsd); maid;

myans(hang,i)=maid;

myans_zf(hang,i)=xsd_zf(maid); %% 手动

ganrao3;%干扰中间数据 end end

myans-1 myans_zf %% 答案

32

表11: 附件五第二面复原图碎片顺序

33

图11:附件5第一面复原图

图12:附件5第二面复原图

34

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com