1、13年全国大学生数学建模竞赛B题碎纸片的拼接复原2013高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，
2、以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 西华大学 参赛队员 (打印并签名) ：1. 杨尚安 2. 刘 洋 3. 叶 军 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改
3、。如填写错误，论文可能被取消评奖资格。） 日期： 2013 年 09 月 15 日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原摘要本文通过分析题中相关要求及条件，建立数学模型解决了各种规则碎纸片的拼接复原问题。针对问题一， 首先将题中所给图片导入matlab软件，利用imread函数得到每张图片的文字灰度像素矩阵，再取出所有矩阵左、右列，建立像
4、素绝对差拟配模型，得到拟配程度最高的两幅图片，进行拼接，出现不合理拼接情况则进行人工干预，最后重复上述过程，完成全部拼接并导出图像。针对问题二，首先将全部碎片导入matlab软件，经过处理得到每张碎片中符号距离碎片上下端的像素位，再根据分类聚类思想，利用excel表格处理，将所有具有“相同”像素位的图片分为一组，得到11个分组，然后在每一个分组中建立左右连接点数目最匹配模型，再配合人工干预，将所有碎片拼接为一行图像，最后将这11行图像利用问题一中模型拼接为最终图像并打印结果。针对问题三，首先建立一种基于K-Means局部最优性的高效聚类模型，然后根据模型利用matlab，将所给图片全部导入分类
5、，分好类并人工调整补充后再利用matlab在每一组分类中利用问题二模型在人工干预情况下得出原始图像并打印结果。关键词：像素绝对差拟配模型 左右连接点数目最匹配模型 人工干预一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文
6、各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复
7、原结果，结果表达要求同上。二、模型假设1、假设全部碎纸片边缘光滑2、假设字符色调一致3、假设字符间距相同，没有特殊情况4、假设除字符外，页面没有其他地方具有任何色彩5、假设英文字符书写标准，大小写字号均相同三、符号说明表示灰色像素矩阵表示灰色像素矩阵的列数表示灰色像素矩阵的行数表示第几个碎片表示某个像素点表示某灰度像素点为黑色还是白色表示灰色像素矩阵最右边列表示灰色像素矩阵最左边列表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值的和四、模型建立与求解4.1问题一4.1.1问题分析整体来看，本问题要求利用数学模型，改原有手动拼接技术为自动或半自动拼接技术，完成题中所给的相
8、应碎纸片的拼接复原工作。具体操作，考虑所给碎纸片内容仅有汉字或英文，而没有颜色、大小、字形之分。因此，只能利用碎纸片中相应的文字特征进行操作，考虑碎纸片扫描进入在计算机后是以图片的形式存在，而图片又是以像素的情况组成。所以，首先可将图片导入matlab中，以其像素为基点，得到每个图片的像素矩阵，每一像素矩阵即可表示该图片的特征。为了利用图片像素矩阵完成图片的拼接，考虑问题一只是将原图分为了19列，每一列具有1980像素，首先可根据左端全为空白，找出原图最左一列碎片，然后利用拼接好的图片最右列像素点去匹配未拼接图片的最左列像素点，使得拼接最为吻合的即为需要拼接的图片，然后拼接，再重复上述过程，直
9、到拼接完成。具体操作流程如下：图1 问题一解答流程图4.1.2数据处理将图片导入matlab中，然后编写程序（具体代码见附录1），可得每个碎纸片灰度像素矩阵（碎片000局部像素点如下）。图2 碎片000局部灰度像素点列4.1.3像素绝对差拟配模型建立令碎片导入matlab编程计算所得的灰色像素矩阵为：由于碎片像素为72*1980，因此矩阵也是72*1980的，矩阵每一列数据即为碎片相应列像素值，其中每个像素点表示此处为黑色或白色，用表示某灰度像素点为黑色还是白色，即：令表示灰色像素矩阵最右边列，那么令表示灰色像素矩阵最左边列，则令表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差
10、的绝对值的和。那么有根据上述模型即可确定某一碎片灰度像素矩阵最右边列与其余未拼接碎片最左边列的绝对差值，下面讨论因差值不同而产生的匹配问题。1、最左列的确定：当出现某一碎片灰度像素矩阵最左列均为255时，那么说明该碎片为原始图像的最左列。2、假设出现情况，那么首先将对应的碎片与该基准碎片进行拼接，若拼接不合适，这时就需要人工干预，换对应的碎片与基准碎片进行拼接。情况如下： 这是不确定的，而进行人工干预选择对应的碎片后，将会出现下面情况：这样就能正确的完成两个碎片的拼接。3、假设出现情况，这与上述情况相同。因此，人工干预方式及时间选择也相同。4.1.4像素绝对差拟配模型求解对于附件一中碎片复原，
11、根据上述模型，利用matlab软件，求解可得008碎片最左端矩阵列与006碎片最右端矩阵列均为：，因此，可知008碎片为复原图最左一个碎片，006碎片为复原图最右端碎片。其余求得所有最小的距离的值，根据的值，可将碎片进行复原。复原结果如下表，复原图像见附录2。008014012015003010002016001004005009013018011007017000006表1 问题一中文复原表格序列对于附录二英文复原，与上求解过程雷同，利用matlab可得复原结果如下表，复原图像见附录3。00300600200701501801100000500100901301000801201401701
12、6004表2 问题一英文复原表格序列 4.1.5问题一综合分析 综上所述，对于问题一的求解过程，未使用人工干预。本文除使用对问题所给的碎片进行复原外，同时对具有相同属性的其他图形碎片也进行了复原，效果良好，模型稳定，可推广到所有只进行竖切的文档恢复。4.2问题二中文碎片复原4.2.1问题分析综合分析。由于考虑问题二在问题一的基础上将碎片分的更加的细小，那么碎片的灰色像素矩阵数据在原有的基础上将会变得少很多，考虑使用问题一方法及模型，那么首先就要构造出与问题一相同的19个竖碎片，因此考虑将所有碎片分为19组，但经过试验分为19组后，由于空白出现太多，在每组中将11个碎片拼接在一起是相当困难的。因
13、此，转变思想，考虑将所给所有碎片分为11个组，在每个分组中将19张碎片拼接在一起，然后在将11个分组拼接在一起完成最后解答。具体操作。要想将11*19张图片分为11组，考虑文字具有行高的性质，分组中所拼接的19张碎片，所有文字具有的行高应该都是相同的。根据这一思想，可将所有碎片导入matlab中，编程计算可得每张碎片符号距离碎片上下端的像素位，并将所有结果导入excel中，然后根据分类与聚类思想，利用excel表格处理，将碎片符号距离碎片上下端的像素位“相同”（不是绝对相等，允许误差前后波动两个像素）的点分为一组，对于出现空白位置误差较大的点可根据单边距离进行分类与聚类，若根据单边无法确定具体
14、分入那组，那么就同时分入可能的分组中。分组完成后那么每个分组中的图片定能拼接为一行图片，那么我们可建立左右连接点数目最匹配模型，结合人工干预，将每个分组中图片拼接在一起。最后利用问题一中模型可将11个分组拼接在一起得到原图。具体流程如下图：图3 问题二解答流程图4.2.2数据处理将209张碎片导入matlab中，编程得到每张碎片灰色像素矩阵，然后在利用矩阵编写程序得到每张碎片字符距离上下边界的像素位，并将其导入excel中（具体代码见附录4），下表为000至016结果：（其余碎片结果见附录5）碎片编号012345678910111213141516上距离02237251200000039258
15、9316下距离150005809159600000030表3 碎片字符距离上下边界的像素位情况表得到像素位上下边缘距离后可根据上下距离“相等”（不是绝对相等，允许误差前后波动两个像素）原则，利用excel表格处理将所给数据分为11组。其中距上边缘距离为0，下边缘距离为21的一个分组为下表：（其余分组见附录6）34424347587784949718390136112127124121144149164表4 某一属于同行碎片的分组情况表在每一分组内，再利用matlab编程计算每张碎片左端与右端具有的可连接点数目（采用四舍五入原则） (具体代码见附录7) ，下表为上一分组数据的左右连接点数目：（其
16、他分组连接点数目见附录8）4(34)73(42)64(43)06(47)35(58)34(77)27(84)00(94)49(97)31(183)99(90)63(136)33(112)75(127)66(124)53(121)35(144)47(149)93(164)5表5 某一同行碎片的左右连接点数目情况表4.2.3 左右连接点数目最匹配模型本模型属于半自动模型，需人工干预，具体步骤如下：1、选取任一分组左右连接点数目情况表，观察左右连接点数；2、选取左端连接点数目为0的碎片作为最左端碎片，并将该图片作为基准图片；3、观察基准图片右端连接点数目，从未拼接图片左端连接点数目中找寻与该数目最接
17、近的碎片，人工控制，观察是否可连接。若可连接则拼接上，并将新拼接上碎片作为基本图片，若不可连接，则重新找寻符合要求的碎片，观察是否可连接；4、重复3步骤，直到将图片全部连接完成。4.2.4模型求解以上述模型为标准，考虑数据处理中那行连接过程。首先，寻找19个点钟左端连接数为0的点，找到（94）号碎片，将其作为基准图片，观察其右边连接点数为4，从其余碎片中找寻发现（34）（43）（77）左端连接数均为4，因此，通过人工干预，观察图片字样走势发现只有（34）号碎片符合要求，再将（34）号图片作为基准图片，其右端连接点数为7，从未连接碎片中找寻发现（84）（149）号均为7 ，同理（84）碎片作为基
18、准图片，以此类推即可得到该分组图片排序为：（94）（34）（84）（183）（90）（47）（121）（42）（124）（144）（77）（112）（149）（97）（136）（164）（127）（58）（43）其具体碎片拼接图形如下：然后根据上述模型，以相同的办法结合附录6中分组情况即可将全部11个分组中图片的连接情况找出，然后利用问题一中像素绝对差拟配模型即可拼接处原图，得到原图表格连接情况如下，具体图像见附录9。04905406514318600205719217811819009501102212902809118814106101907806706909916209613107906
19、311616307200617702005203616810007606214203004102314719105017912008619502600108701803814804616102403508118912210313019308816702500800910507407115608313220001708003320219801513317020508515216502706001412800315908219913501207316020316913403903105110711517609403408418309004712104212414407711214909713616
20、4127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108117004101113194119123表6 汉字碎片拼接情况表4.2.5中文碎片恢复综合分析由于解决本问题使用的左右连接点数目最匹配模型，属于半自动模型。因此，对
21、本文的恢复进行了人工干预。恢复此中文文档，本模型一共进行了9次人工干预。干预方式为：终止程序继续运行，将程序拼接过程恢复至上一步（出现碎片拼接不吻合时的前一步），然后将程序用于拼接的碎片导出，再恢复程序继续运行，找到该步拼接吻合碎片并拼接后，再将导出碎片重新导入继续运行程序。干预时间节点:干预时间节点即对每行碎片单独拼接时，出现碎片拼接不吻合情况时的节点。4.3问题二英文碎片复原4.3.1问题分析对于附录四英语碎片恢复，由于英文与汉字写法不同，英语中弧线居多，而汉字中直线居多。因此，可以采用另一种方式对英文碎片进行拼接，依然考虑问题一中的像素绝对差拟配模型，可首先任意选择一张基础碎片，然后利用
22、该模型进行适应性匹配，匹配过程中加以人工干预。具体操作流程如下：图4 英文碎片复原流程图4.3.2模型建立1.1像素绝对值拟配模型令碎片导入matlab编程计算所得的灰色像素矩阵为：由于碎片像素为72*180，因此矩阵也是72*180的，矩阵每一列数据即为碎片相应列像素值，其中每个像素点表示此处为黑色或白色。令表示灰色像素矩阵最右边列，那么令表示灰色像素矩阵最左边列，则令表示某个碎片灰色像素矩阵最左列与另一个碎片灰色像素矩阵最右列的差的绝对值的和。那么有根据上述模型即可确定某一碎片灰度像素矩阵最右边列与其余未拼接碎片最左边列的绝对差值，下面讨论因差值不同而产生的匹配问题。1、最左列的确定：当出
23、现某一碎片灰度像素矩阵最左列均为255时，那么说明该碎片为原始图像的最左列。2、假设出现情况，那么首先将对应的碎片与该基准碎片进行拼接，若拼接不合适，这时就需要人工干预，换对应的碎片与基准碎片进行拼接。情况如下：这是不确定的，而进行人工干预后将会出现下面情况：这样就能正确的完成两个碎片的拼接。3、假设出现情况，这与上述情况相同。因此，人工干预方式及时间选择也相同。1.2人工干预在进行像素绝对值拟配模型计算后，将会得到与基准碎片拼接度最大的几个碎片，然后利用这几个碎片可进行人工干预，具体人工干预模型如下：1、首先将程序计算得到的拟配程度最大的碎片与基准碎片进行拼接；2、人工判断拼接是否合理；3、
24、若拼接合理则进行下一次拟配模型计算，若拼接不合理则找寻第一步中与基准碎片拟配差一点的碎片进行拼接；4、直到找到拼接成功的点才结束本次拼接，并将新拼接上的图片作为基本图片利用模型寻找拟配度最高的碎片，返回第一步。4.3.3模型求解结合上述模型1.1及1.2可计算得到问题二英文碎片复原图表格如下，具体图像见附录10191075011154190184002104180064106004149032204065039067147201148170196198094113164078103091080101026100006017028146086051107029040158186098024117
25、150005059058092030037046127019194093141088121126105155114176182151022057202071165082159139001129063138153053038123120175085050160187097203031020041108116136073036207135015076043199045173079161179143208021007049061119033142168062169054192133118189162197112070084060014068174137195008049172156096023099
26、122090185109132181095069167163166188111144206003130034013110025027178171042066205010157074145083134055018056035016009183152044081077128200131052125140193087089048072012177124000102115表7 问题二英文碎片复原图表格表示4.2.4英文碎片恢复综合分析由于英文碎片相似程度高于中文图片。所以每一次以基准图片找寻最佳匹配图形时很多时候出现多张图片符合匹配，因此，对此英文碎片的恢复进行了人工干预。恢复此英文文档，本模型一共进
27、行了39次人工干预。干预方式为：终止程序继续运行，将程序拼接过程恢复至上一步（出现碎片拼接不吻合时的前一步），然后将该步程序用于拼接的碎片导出，再恢复程序继续运行，直到找到与该基准碎片拼接吻合碎片并拼接完成。干预时间节点:当出现与基准碎片匹配不吻合时。4.3问题三4.3.1问题分析考虑问题三附录中所给图片具有正反面，却不知每一个序号中a是正面还是b是正面，这也真是问题二英语复原与问题三双面复原的区别。因此，问题二中所用的分类与聚类的方法不能完成分组。为了完成分组，我们可考虑使用一种更加严密，严苛的分类方法，只要分类完成，那么再使用问题二连接图片的办法即可实现图片的复原。4.3.2模型建立许多聚类算法的基本框架是搜索与合并。如在层次方法中需要搜索两个距离最近的类簇然后合并；而基于
