数学建模竞赛—B题—碎纸片的拼接复原.pdf

13年全国大学生数学建模竞赛一B题一碎纸片的拼接复原2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规 则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨 询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他 公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处 和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反 竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如 果赛区设置报名号的话）：所属学校（请填写完整的全名）：西华大学参赛队员（打印并签名）：1.杨尚安指导教师或指导教师组负责人（打印并签名）：（论文纸质版与电子版中的以上信息必 须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格日期：2013年09月15日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：评阅人评分备注全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原摘要本文通过分析题中相关要求及条件，建立数学模型解决了各种规则碎纸片的拼接复原问 题。针对问题一，首先将题中所给图片导入matl ab软件，利用imread函数得到每张图片 的文字灰度像素矩阵，再取出所有矩阵左、右列，建立像素绝对差拟配模型，得到拟配程 度最高的两幅图片，进行拼接，出现不合理拼接情况则进行人工干预最后重复上述过 程，完成全部拼接并导出图像。针对问题二，首先将全部碎片导入matl ab软件，经过处理得到每张碎片中符号距离碎 片上下端的像素位，再根据分类聚类思想，利用excel表格处理，将所有具有“相同”像 素位的图片分为一组，得到11个分组，然后在每一个分组中建立左右连接点数目最匹配 模型，再配合人工干预，将所有碎片拼接为一行图像，最后将这11行图像利用问题一中 模型拼接为最终图像并打印结果。针对问题三，首先建立一种基于K-Mean s局部最优性的高效聚类模型，然后根据模型利 用matl ab,将所给图片全部导入分类，分好类并人工调整补充后再利用matl ab在每一组 分类中利用问题二模型在人工干预情况下得出原始图像并打印结果。关键词：像素绝对差拟配模型左右连接点数目最匹配模型人工干预1一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的 应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数 量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸 片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼 接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼 接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图 片形式及表格形式表达（见【结果表达格式说明】）。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件 3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工 干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的 碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数 据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原 结果，结果表达要求同上。二、模型假设1、假设全部碎纸片边缘光滑2、假设字符色调一致3、假设字符间距相同，没有特殊情况4、假设除字符外，页面没有其他地方具有任何色彩5、假设英文字符书写标准，大小写字号均相同三、符号说明ai表示灰色像素矩阵n表示灰色像素矩阵的列数m表示灰色像素矩阵的行数i表示第几个碎片aimn表示某个像素点b表示某灰度像素点为黑色还是白色right表示灰色像素矩阵最右边列l eft（k）表示灰色像素矩阵最左边列w表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值的 和四、模型建立与求解4.1问题一4.1.1问题分析整体来看，本问题要求利用数学模型，改原有手动拼接技术为自动或半自动拼接技术，完成题中所给的相应碎纸片的拼接复原工作。具体操作，考虑所给碎纸片内容仅有汉字或英文，而没有颜色、大小、字形之分。2因此，只能利用碎纸片中相应的文字特征进行操作，考虑碎纸片扫描进入在计算机后是 以图片的形式存在，而图片又是以像素的情况组成。所以，首先可将图片导入mat l ab 中，以其像素为基点，得到每个图片的像素矩阵，每一像素矩阵即可表示该图片的特征。为了利用图片像素矩阵完成图片的拼接，考虑问题一只是将原图分为了 19歹U,每一列具 有1980像素，首先可根据左端全为空白，找出原图最左一列碎片，然后利用拼接好的图 片最右列像素点去匹配未拼接图片的最左列像素点，使得拼接最为吻合的即为需要拼接的 图片，然后拼接，再重复上述过程，直到拼接完成。具体操作流程如下：图1问题一解答流程图4.1.2数据处理将图片导入matl ab中，然后编写程序（具体代码见附录1）,可得每个碎纸片灰度像素 矩阵（碎片000局部像素点如下）。图2碎片000局部灰度像素点列255 2S5 265”5 溺 15844 0 0 059 182：55 255 2S5 湖 25534.1.3像素绝对差拟配模型建立令碎片导入matl ab编程计算所得的灰色像素矩阵为：ii al l al 2 al in i iia2 2 a2 n aai 2 1,n 72,m 1980,1 i 19ii aia am2 mn ml由于碎片像素为72*1980,因此矩阵ai也是72*1980的，矩阵每一列数据即为碎片相应 列像素值，其中每个像素点aimn表示此处为黑色或白色，用b表示某灰度像素点为黑色还是白色,即：0表示此处为黑色即有图像 b 0 amn 255表示此处在有图像与没图像之间255表示此处为白色即无图像其中 0 m 1980,0 n 72令right(i)表示灰色像素矩阵最右边列，那么al in i a right(i)2 n,n 72,m 1980,1 i 19ai mn令l eft(k)表示灰色像素矩阵最左边列，则k al l k a l eft(k)2 1,n 72,m 1980,1 k 19ak ml令w表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值 的和。那么有w right(i)l eft(k)119800 i 19,0 k 19根据上述模型即可确定某一碎片灰度像素矩阵最右边列与其余未拼接碎片最左边列的绝 对差值，下面讨论因差值不同而产生的匹配问题。1、最左列的确定：当出现某一碎片灰度像素矩阵最左列均为255时，那么说明该碎片 为原始图像的最左列。2、假设出现wl w2 w3 wk情况，那么首先将wk对应的碎片与该基准碎片进行 拼接，若拼接不合适，这时就需要人工干预，换wk 1对应的碎片与基准碎片进行拼接。情况如下：4这是不确定的，而进行人工干预选择wk 1对应的碎片后，将会出现下面情况：这样就能正确的完成两个碎片的拼接。3、假设出现wl w2 w3wk情况，这与上述情况相同。因此，人工干预方式及时间选择也相同。4.1.4像素绝对差拟配模型求解对于附件一中碎片复原，根据上述模型，利用matl ab软件，求解可得008碎片最255 左端矩阵列与006碎片最右端矩阵列均为：，因此，可知008碎片为复原图最左一个碎片，006碎片为复原图最右端碎片。其余求得所有最小的距离w的值，根据w的值，可将碎片进行复原。复原结果如下表，复原图像见附录2。对于附录二英文复原，与上求解过程雷同，利用matl ab可得复原结果如下表，复原图008014012015003010002016001004005009003006002007015018011000005001009013叱”目n匕，目 而无+间=两无:间4 萧萧。萧萧。悔隹凭走梅笆凭主g北，何，北，何而无十,据。=沟无据。萧萧活L萧萧乱梅隹i烟悔隹，烟4.1.5问题一综合分析综上所述，对于问题一的求解过程，未使用人工干预。本文除使用对问题所给的碎片进行复原外，同时对具有相同属性的其他图形碎片也进行了复原，效果良好，模型 稳定，可推广到所有只进行竖切的文档恢复。54.2问题二中文碎片复原4.2.1问题分析综合分析。由于考虑问题二在问题一的基础上将碎片分的更加的细小，那么碎片的灰色 像素矩阵数据在原有的基础上将会变得少很多，考虑使用问题一方法及模型，那么首先就 要构造出与问题一相同的19个竖碎片，因此考虑将所有碎片分为19组，但经过试验分为 19组后，由于空白出现太多，在每组中将11个碎片拼接在一起是相当困难的。因此，转 变思想，考虑将所给所有碎片分为11个组，在每个分组中将19张碎片拼接在一起，然后 在将11个分组拼接在一起完成最后解答。具体操作。要想将11*19张图片分为H组，考虑文字具有行高的性质，分组中所拼接 的19张碎片，所有文字具有的行高应该都是相同的。根据这一思想，可将所有碎片导入 matl ab中，编程计算可得每张碎片符号距离碎片上下端的像素位，并将所有结果导入 excel中，然后根据分类与聚类思想，利用excel表格处理，将碎片符号距离碎片上下端 的像素位“相同”（不是绝对相等，允许误差前后波动两个像素）的点分为一组，对于出 现空白位置误差较大的点可根据单边距离进行分类与聚类，若根据单边无法确定具体分入 那组，那么就同时分入可能的分组中。分组完成后那么每个分组中的图片定能拼接为一行 图片，那么我们可建立左右连接点数目最匹配模型，结合人工干预，将每个分组中图片拼 接在一起。最后利用问题一中模型可将11个分组拼接在一起得到原图。具体流程如下 图：图3问题二解答流程图4.2.2数据处理将209张碎片导入matl ab中，编程得到每张碎片灰色像素矩阵，然后在利用矩阵编写 程序得到每张碎片字符距离上下边界的像素位，并将其导入excel中（具体代码见63442434758778494901361121271241211441494(34)73(42)64(43)06(47)35(58)34(77)27(84)9(90)63(136)33(112)75(127)66(124)53(121)35(144得到像素位上下边缘距离后可根据上下距离“相等”(不是绝对相等，允许误差前后波 动两个像素)原则，利用excel表格处理将所给数据分为11组。其中距上边缘距离为0,1=1 口工1左木N 1口,壮牙入网“I丈七1q、!A=U 力J/切清润潘郎，又是何郎婿:记取钗头新利市,莫将分付东邻子;西 鹭飞，散花洲外片帆微。桃花流水鳏鱼肥.主人瞋小，欲向东1在每一分组内，再利用matl ab编程计算每张碎片左端与右端具有的可连接点数目(采 用四舍五入原则)(具体代码见附录7),下表为上一分组数据的左右连接点数目：(其4.2.3左右连接点数目最匹配模型1本模型属于半自动模型，需人工干预，具体步骤如下：1、选取任一分组左右连接点数目情况表，观察左右连接点数；2、选取左端连接点数目为。的碎片作为最左端碎片，并将该图片作为基准图片；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图片的连接情况找出，然后利用问题一中像素绝对差拟配模型即可拼接处原图，得到原碎片编号01234567891011121上距离0223725120000003925下距离150005809159600000490540651431860020571921781181900950610190780670690991620961310790631161681000760621420300410231471910501790381480461610240350811891221031301930711560831322000170800332021980151330141280031590821991350120731602031690940340841830900471210421241440771121250131821091970161841101870661061500290641112010050921800480370750550440072081381581260681750451740001370530891461021541140401512071551401851084.2.5中文碎片恢复综合分析由于解决本问题使用的左右连接点数目最匹配模型，属于半自动模型。因此，对本文的 恢复进行了人工干预。恢复此中文文档，本模型一共进行了 9次人工干预。干预方式为：终止程序继续运行，将程序拼接过程恢复至上一步（出现碎片拼接不吻合 时的前一步），然后将程序用于拼接的碎片导出，再恢复程序继续运行，找到该步拼接吻 合碎片并拼接后，再将导出碎片重新导入继续运行程序。干预时间节点:干预时间节点即对每行碎片单独拼接时，出现碎片拼接不吻合情况时的 节点。4.3问题二英文碎片复原4.3.1问题分析对于附录四英语碎片恢复，由于英文与汉字写法不同，英语中弧线居多，而汉字中直线 居多。因此，可以采用另一种方式对英文碎片进行拼接，依然考虑问题一中的像素绝对差 拟配模型，可首先任意选择一张基础碎片，然后利用该模型进行适应性匹配，匹图4英文 碎片复原流程图84.3.2模型建立1.1 像素绝对值拟配模型令碎片导入matl ab编程计算所得的灰色像素矩阵为：ii al l al 2 al in i ii a2 1a2 2 a2 n ai,n 72,m 180,1 i 19 ii ai ml am2 amn由于碎片像素为72*180,因此矩阵ai也是72*180的，矩阵每一列数据即为碎片相应列 像素值，其中每个像素点aimn表示此处为黑色或白色。令right(i)表示灰色像素矩阵最右边列，那么al in i a right(i)2 n,n 72,m 180,1 i 19ai mn令l eft(k)表示灰色像素矩阵最左边列，则k al l k a l eft(k)2 1,n 72,m 180,1 k 19ak ml令w表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值 的和。那么有w right(i)l eft(k)1180其中 0 i 19,0 k 19根据上述模型即可确定某一碎片灰度像素矩阵最右边列与其余未拼接碎片最左边列的绝 对差值，下面讨论因差值不同而产生的匹配问题。1、最左列的确定：当出现某一碎片灰度像素矩阵最左列均为255时，那么说明该碎片 为原始图像的最左列。2、假设出现wl w2 w3 wk情况，那么首先将wk对应的碎片与该基准碎片进行 拼接，若拼接不合适，这时就需要人工干预，换wk 1对应的碎片与基准碎片进行拼接。情况如下：这是不确定的，而进行人工干预后将会出现下面情况:d a i e e；d a ie e；l il i/：s t l=l il ies H 2d.md.9这样就能正确的完成两个碎片的拼接。3、假设出现wl w2 w3 wk情况，这与上述情况相同。因此，人工干预方式及时间选择也相同。1.2 人工干预在进行像素绝对值拟配模型计算后，将会得到与基准碎片拼接度最大的几个碎片，然后利用这几个碎片可进行人工干预，具体人工干预模型如下：1、首先将程序计算得到的拟配程度最大的碎片与基准碎片进行拼接；2、人工判断拼接是否合理；3、若拼接合理则进行下一次拟配模型计算，若拼接不合理则找寻第一步中与基准碎片拟配差一点的碎片进行拼接；4、直到找到拼接成功的点才结束本次拼接，并将新拼接上的图片作为基本图片利用模 型寻找拟配度最高的碎片，返回第一步。4.3.3模型求解结合上述模型L1及L 2可计算得到问题二英文碎片复原图表格如下，具体图像见191075011154190184002104180064106004201148170196198094113164078103091080086051107029040158186098024117150005019194093141088121126105155114176182159139001129063138153053038123120175020041108116136073036207135015076043208021007049061119033142168062169054070084060014068174137195008049172156132181095069167163166188111144206003171042066205010157074145083134055018081077128200131052125140193087089048d a i iyo d a nyo iil ij+en=l il igen4.2.4英文碎片恢复综合分析由于英文碎片相似程度高于中文图片。所以每一次以基准图片找寻最佳匹配图形时很多时候出现多张图片符合匹配，因此，对此英文碎片的恢复进行了人工干预。恢复此英文文档，本模型一共进行了 39次人工干预。干预方式为：终止程序继续运行，将程序拼接过程恢复至上一步（出现碎片拼接不10吻合时的前一步），然后将该步程序用于拼接的碎片导出，再恢复程序继续运行，直到 找到与该基准碎片拼接吻合碎片并拼接完成。干预时间节点：当出现与基准碎片匹配不吻合时。4.3问题三4.3.1问题分析考虑问题三附录中所给图片具有正反面，却不知每一个序号中a是正面还是b是正面，这也真是问题二英语复原与问题三双面复原的区别。因此，问题二中所用的分类与聚类的 方法不能完成分组。为了完成分组，我们可考虑使用一种更加严密，严苛的分类方法，只 要分类完成，那么再使用问题二连接图片的办法即可实现图片的复原。4.3.2模型建立2 许多聚类算法的基本框架是搜索与合并。如在层次方法中需要搜索两个距离最近的类簇 然后合并；而基于密度的聚类算法则不断地搜索高密子区域，然后利用连通性将其合并到 当前聚类结果中。很明显，搜索过程需要面对整个样本集合，通常会导致算法低效。如 DBSCAN需要测试每个对象是否是核心对象，并对每个核心对象搜索其直接密度可达的对 象，如果没有空间索引的辅助，DBSCAN算法的复杂度为0(n 2)。实际上，现有的很多聚类 算法已经关注到这个问题，如CURE算法利用采样方法减小搜索空间，而Chamel eon算法 则通过图划分算法将样本对象聚类为大量相对较小的子簇。具体到本文，我们采用了随机 采样和K-Mean s算法高效地聚出大量的高密子簇，后续处理都基于这些构造出的高密子簇 进行，无须直接面对所有的样本。我们称这种算法框架为构造与合并。因此，K-Mean SCAN 算法的处理流程为：随机采样、预聚类、合并和后处理。聚类算法的本质是密度估计问 题，K-Mean SCAN算法的核心思想是，增加K-Mean s算法中高斯混合模型的高斯分量数目以 提升密度估计的精度，并利用K-Mean s聚类的局部最优和结果敏感性的特征进行高斯分量(即高密子簇)的合并剪枝，克服过拟合问题，最终实现有效的聚类。K-Mean s算法实质上是一种将聚类视为密度估计问题的概率方法。在概率方法中，假设 样本来自于如下形式的混合模型：p(x|)j kp(cj)pj(x|j,cj)式中，(1,，k)是待估计的参数向量；条件概率密度p(x|j,cj),称为分量 密度，表示类别j的概率密度形式，且参数向量j未知；先验概率p(cj)称为混合因 子。为了简化问题，K-Mean s算法进一步假设：(1)每个类别的概率密度形式为球形高斯分 布，即j(j,)且1 2 2,j,2未知，(2)每个样本唯一地属于一个类别；(3)假设所有类别的混合因子相等。于是，混合模型简化为112 p(x|)max(x|j,cj)max exp(|x|)(1)j2 d/2 2 2 j l:kj l:k(2)该简化模型可以通过最大似然方法求解,对于观测样本X(xl,xn)X=(xl,xn),相应 的对数似然函数为：xi cj最大化该对数似然函数等价于最小化上式的欧氏距离平方项，即得到K-Mean s的误差平 方和准则：i l j 11(X)In p(xi)n l n(2)n 2 d/2 12 2 k|2|xij(2)l lJc kJ Ixj cj|xi j|2(3)通过迭代优化上述的误差平方和准则,K Mean s算法最终可以估计出每个高斯分量的均值 向量和协方差矩阵 21。式中,n j是类簇cj的样本数目。Jcl k2|x|ijn dj Ixj cjn d2(4)要获得更有效的样本密度估计,Je的值自然是越小越好.但是，Je的值不仅取决于样本 的分类情况，而且与类别数目k有关.当类别数目k给定时，Je的值由样本的分类情况所决 定,且存在一个最小值Jk min对应于最优的样本类别划分.如果类别数目k和高斯混合模 型假设与实际问题相匹配时,最小值Jk min必定很小,从而可以很好地近似样本密度;而 如果模型假设不合理,则最小值Jk min可能依然很大,对样本分布的近似效果较差。对于任意形状的类簇，很明显不能直接要求数据分布满足高斯混合模型的假设,否则会导 致最小的误差平方和Jk min很大.实际上,高斯混合模型具有很强的表达能力，如果高斯 分量密度的数目k足够大,则高斯混合模型几乎可以近似任意一种概率分布。换言之,随着 类别数目k的增加，相应的Jk min会减小。简单证明如下：类别数目k的增加，必然导致最终每个类簇的形状缩小，对应于高斯分量的2减小；而 从公式和公式可以得出Jk min n d 2,即最小的误差平方和正比于2；因此，k 的增加会导致最小的误差平方和Jk min的减小。极端情况下，k n,则每个样本点都是 一个类簇，即Jk min 0,说明此时的经验误差为0,但是此时，模型的推广能力极差。根据 统计学习理论,经验误差最小并不等于期望误差最小,经验风险只有在样本数无穷大时才趋 近于期望风险.因此,经验误差最小不能保证分类器的推广能力，需要找到经验风险最小和 推广能力最大的平衡点。同样,利用足够多的高斯分量组成的混合模型来描述数据会导致 过拟合的问题,影响模型的推广能力。因此在K-Mean SCAN算法中，我们采用过拟合-剪枝 的策略进行聚类,即首先使用分量足够多的高斯混合模型来较好地近似样本分布,然后通过 合并一些高斯分量的剪枝策略来处理过拟合问题。4.3.3模型求解根据上述K-Mean s局部最优性的高效聚类模型，利用matl ab编程计算后结合人为108a110a125a066a047a020a150a029111b136b174b183b164b189b018b0814.3.4最终求解上述模型求解结束后，结合问题二英文求解模型及人工干预时机，可将原图还原，其具 体还原图像见附录12,具体还原图像表格如下：12345678078bUlb125a140a155a150a183b174089a010b036d076b178a044a025b19212186b153a084b042b030a038a121a098199b011b161a169b194b173b206b156088b107a149b180a037b191a065b115114a184b179b116b207a058a158a197146a171b031a201a050a190b092b019165b195a128a157a168a046a067a063003b007b085b148b077a004a069a032023b133a048a051b095a160b119a033099a043a096b109a123a006a104a1341112131415161718108a018b029a189b081b164b020a04120b144a079a014a059a060b147a15137b045a138a056b131b187b086b20198b087a132b093a072b175a097a03151b170b041a070b139b002a162b20012a017b102b064b208a142a057a02053b202a021b130a163a193b073b15117b008b068b188a127a040a182b12176a185a000b080b027a135b141a20062a129b118b101a015b205a082b14049b091a106b100b055b103a112a194.3.5问题三综合分析12345678136a047b020b164 a081a189a029b018005b152b147b060a059b014b079b144143a200a086a187a131a056a138b045083b039a097b175b072a093b132a087090b203a162a002b139a070a041b170013b024b057b142b208b064a102a017035b159b073a193a163b130b021a202172b122b182b040b127b188b068a008105b204a141b135a027b080a000a185009a145b082a205b015a101b118a129054a196a112b103b055a100a106a0911112131415161718110b174a183a150b155b140b125b111124a192b025a044b178b076a036b01C094a098b121b038b030b042a084a153034b156b206a173a194a169a161bOil166a115a065a191b037a180b149a107154a197b158b058b207b116a179a184016a019a092a190a050b201b031b171对于本问题，由于英语碎片出现正反两面，分类时情况复杂。因此，恢复原文时进行了 多次人工干预。干预方式；对正反英文碎片进行分类结束后，对未归类的碎片，采用人工归类方法，进 行多次干预。在每一类中进行碎片拼接时，出现拼接不匹配时，终止程序继续运行，将程 序拼接过程恢复至上一步（出现碎片拼接不吻合时的前一步），然后将程序用于拼接的碎 片导出，再恢复程序继续运行，找到该步拼接吻合碎片并拼接后，再将导出碎片重新导入 继续运行程序。干预时间节点：分类完成后，对未进行归类的碎片进行人工分类时，还有当进行拼接出 现拼接碎片不吻合时。五、模型评价与推广5.1模型的优点使用该模型，可以很好的提高工作效率，将原来使用纯手工拼接过程变得简单合理，而 且拼接过程全部在计算机上进行，使得结果更加准确，从碎片出发复原原图像，以点代面 的做法，使思路更加简单明了；运用matl ab计算及绘出图形，用数形结合的方法来进行 分析，模型思路更加清晰，更有说服力。5.2模型的缺点模型求解过程中，很多地方使用了人工干预，使得整个过程不能实现完全的智能化。有 时的四舍五入也可能是结果有些偏差。5.3模型的推广该题所建模型求解的是与相似图形的匹配问题，在实际生活中，与图像相似，匹配，识 别相关的问题，均可以使用该模型进行运算。对于本题问题三，我们也可从另一方面入手考虑，由于每个碎片为180*72像素的，所 含信息量较少，因此，使用问题一的方法直接求解不行。如果我们在保证图片大小不变的 情况下，增加图片的像素或者寻求另一种模式使碎片分组更加细，那么直接运用方法一求 解规则碎片复原将变得相当的容易。六、参考文献1 wen ku.baidu/view/5c6 a7fc8102 de2 bd96 058886.html.2 013.09.15 2 jos.org/1000-982 5/19/16 83.pdf.2 013.09.1514075a063a067b046b168b157b128b195074a032b069b004b077b148a085a007071a033a119b160a095b051a048b132113b134b104b006b123b109b096a043七、附录附录L使用软件名称:matl ab(daimal)A=imread(附件l 000.bmp);%区图片的相对 路径附录 2,使用软件名称:mat l ab(daima2)fun ction Pholcl ccl ear al lA=imreadC附件l 000.bmp);外区图片的相对路径m,n=size(A);pho=on es(m,1)*2 55;sort=zeros(1,19);x=0;15l eft=zeros(m,1);right=zeros(m,1);城上层楼叠题城下清淮古汴，举手携吴云.人与暮天俱达魂断e 魂断.，后夜松江月满“籁簌衣巾花零花.村里村北响缉车“牛衣古秘套黄 瓜，海棠珠墙一重重.清晓近帘it胭脂诙与匀淡，偏向脸边漆一小郑非 常强记.二南依旧能诗举更有妒生堪切脍，儿髯要教却，自古相从体务 日，何妨低唱读吟二天垂后里作春阴3生中人半解，帘外旨将率.双空绿 坠 娇眼横波眉篇聚,妙舞踽迎,掌上身轻意态妍赳雾轮笼两风，寒烟 淡拂双鸡“为谯潦赚不白家错认门前过马“我劝辑张白去好，从来自己忘情。尘心消感道心平，江南与靠北，何 处不堪行q闲离随e谍念窠损襄王，何曾梦云雨，IB恨前欢,心事两无据.要知欲见无由.痴心犹自.倩人道.一声传语，风看珠帝自上物.访东乱 叶报新秋一独展轩手上高楼.I髭水纵横回晚腔归来转宽情怀动.梅笛烟 中闻几弄，秋阴直西山雷淡云凝床，梵高跳远.见长至万里，云无图遴,桂蝶飞来先用处.冷澧天秋A,玉宇琼楼,熏蜜来去,人在清凉国：江 山如（1,建中烟树历历，省可清音挥玉尘.更须保器全真r凤漉何道家 空不应同/客，性漫卓文君自情风流云雨依“美山有限情无限待君 重见寻芳伴。为说相思，目断西楼蒋，莫恨黄花未吐，且救红粉相扶.酒 用不必善来5L能10人同今古；玉骨那愁施雾，冰姿自有仙风，海勃时遣 标君丛,面接璋毛么凤，定豆炭桑真过矣，凭君说与南蔑，愿加冕越报辛登 君王如有间，结 林赖王生。师唱谁家曲，宗风洞网谁口借名拍板与门SL我也逢场作戏、真相St晕唇爆枕印。印枕瞬感晕；南照除收?旗救IR患闲二可惘相邃 能几日，不知重会是何年一菜黄仔军更重lh与夜凤日幔.三更月到庠.瞿纹如水玉肌潦.何枷与侬归去有残妆，金炉抗映曲爆浅 惜香更想宝 钗翻，堂闻处，余里在，这一番、气昧胜从前，声暗荷林一夜需一新也嫌 叶照林光。竹簿茅舍出青黄。霜降水痕收,浅野经经言逸涮。酒力渐消风 力软.同JT破幅多情却恋头，妙彩耀风.一枕伤春施.归不去.凤楼何 处 芳草迷归踏，.汤发云腰那白，餐浮花乳轻EL人间谯般更争妍，斗取 红腐粉面“炙手无人傍厘头:萧萧晚而脱梧利L推怜季子激韶装.l ocal=0;Used=zeros(19,1);B=zeros(l,19);for i=l:19%首先找到最左两边的碎片 if i2 50)1700%当第一列所有数据为白色时，就定义为这个碎片在 图片的最左边pho=cat(2,phoa);Used(i)=l;x=x+l;%图片的顺序sort(x)=i-l;right=a(:,n);%取最后一列break;en den dfor i=l:18min=999999999999999999;for k=l:19if Used(k)=lif kl lstr=strcat C 附件 l 00,n um2 str(k-1),.bmp);%拼接图片路径 el sestr=strcat(附件 l 0,n um2 str(k-1),.bmp);en da=imread(str);l eft=a(:,1);%取第一列distan ce=abs(right-l eft);temp=sum(sum(distan ce);if tempminmax=temp;l ocal=k;en den dif Used(l ocal)=1&k=19if l ocaKHstrl=strcat(附件 l 00,n um2 str(l ocal-1),.bmp);el sestrl=strcat(附件 l 0,n um2 str(l ocal-1),*.bmp);en dgoal=imread(str1);pho=cat(2,pho,goal);%将得到的碎片加入到图片中right=goal(:,n);%取右边 16Used(l ocal)=l;%将这个碎片设置为已经使用x=x+l;%图片的顺序 sort(x)=l ocal-l;en den den dpho(:,1)=口;imshow(pho)imwrite(pho,附件 l truel.bmpbmp)sorten d附件3,使用软件名称：matl ab(daima3)fa ir o f fa c e.Th e c ust o mer is a l wa ys r igh t.Ea st,west,h o mes best.Lifes no t a l l beer a nd sk it t l es.Th e d ev il l o o k s a ft er h is o wn.Ma nner s ma k et l i ma n.Ma ny a mic k l e ma k es a muc k l e.A ma n wh o is h is o wn l a wyer h a s a fo o l fo r h is c l ient.Yo u c a nt ma k e a sil k pur se fr o m a so ws ea r.As t h ic k a s t h iev es.Cl o t h es ma k e t h e ma n.Al l t h a t gl ist er s is no t go l d.Th e pen is migh t ier t h a n swo r d.Is f