2013年数学建模论文.doc

2013高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 039B001 所属学校（请填写完整的全名）： 泰山学院 参赛队员 (打印并签名) ：1. 胡善成 2. 周航 3. 陈政 指导教师或指导教师组负责人 (打印并签名)： 房亮 （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 2013 年 9 月 16 日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的半自动拼接摘 要破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的作用。由于计算机数字分析图像能力的缺陷，目前尚不可能实现完全意义上的拼接，因此，本文试图解决在人工干预下的碎纸片的半自动复原问题，拼接时先用计算机搜索与目标碎片匹配的未拼接碎片，并根据匹配程度按顺序显示待选碎片，操作员再根据人脑进一步分析碎片的字形和字义舍弃或拼接待选碎片。这种半自动的拼接方法既提高传统上全由人工拼接时的工作效率，又能拥有较高的准确度。在解决所给问题之前，我们做了些预处理，用拉普拉斯算子法可以改善因光的漫反射造的图像模糊，另外也可用巴特沃斯高通滤波器对图像进行锐化，另需将碎片数字化，即将纸片表示为适合计算机处理的形式。经过对所给碎片的分析，我们将网格（尽可能小）覆盖在碎纸条上，记录边界0,1的排列序列并作为一个向量（取白色为0，黑色为1，只要出现黑色）。具体可见附录1。在切割的边界处，对应向量应该相等。因此，针对问题（1）我们采用最短距离聚类法，建立数学模型。先将19个纸片样本做好标记，记为并各自归为一类，先随机选取一个样本记下它的右边界向量，从其余样本的左边界中选择与之距离最小的另一个样本，并归为一个新类，再计算这个新类与其他样本的距离，选择距离最小的两个样本（或两个新类）归为一个新类，每次合并缩小一个类，直到所有样本都划入一个类为止，以最小距离作为匹配的准则。对于碎片内有英文单词可以做同样的处理。当出现最小距离不只一个时，需要人工干扰，根据文字做出最优决策。在模型的改进过程中我们引人相似度来刻画两边界的吻合程度，在改进部分会给出具体说明。拼接的结果见附录1。问题（2）中纸片加上横切，与问题（1）相比多了两个方向，于是我们给碎纸片定义方向，如表示第张碎纸片度方向上，按顺时针排序0,1时的边界向量，方向确定后，其余碎片与固定碎片的特定方向上能与之匹配的方向也就相应固定，这样多方向问题就会转化为单方向问题。考试期间由于条件限制，和计算机尚未实现自动识别、标记功能。未能实现碎片四个方向上所有的0,1排序，我们只记录了不同方向上，按顺时针方向记录前14位0,1的序列。具体的数据可见附录3。这样问题（2）同样可以用问题（1）的算法给予解决。具体的算法不再赘述，参考问题（1）的算法。为了提高拼接时的工作效率，我们在引入相似度的同时，编写了相应程序来比较相似度的大小，来自动筛选。具体见附录（2）.这样拼接效率会有所提高。拼接的结果见附录1。 问题（3）在问题（2）的基础上只需对碎纸片的正反两面做上标记，如来刻画碎纸片的正面，然后用网格覆盖，标记0,1序列，将碎纸片的一面逐步聚类，当一面完成分类后，另一面自然也会拼接成功。此问题同样可以用形似度来拼接，在改进部分我们给出了计算相似度的程序。关键词： 最短距离聚类法，网格覆盖，匹配准则，相似度1 问题重述 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。2 模型的假设与符号说明2.1 模型的假设假设1： 在切割过程中不存在纸条的缺损，切割均为垂线或水平直线假设2： 文字方向均为沿水平方向，各行之间等间距。假设3： 切割时没切中文字的张数不超过总数的10%。假设4： 保证切割的碎片之间的长宽对应相等，即碎片基本相同。假设5： 每个碎片的四个方向固定，与之相匹配的碎片方向唯一。2.2 符号说明符号符号说明表示第张左边界上的向量。表示第张右边界上的向量。表示两向量之间的距离。表示第个样本表示中的最短距离。表示与合并后的一个新类。表示边界向量作差后，0的个数。表示边界向量作差后，0和1的总数。表示相似度。分别表示第张碎片方向上的向量。表示第张，面度上的边界的向量3 问题分析 要将碎纸片复原，就得找到切割后，对应碎纸片之间的不变量，我们称之为碎纸片的吻合特征，经过分析我们发现，如果将碎纸片放在网状方格中，只要每个方格足够小，那么透过方格就可发现切割后的字，在分裂处对应位子上黑，白点的数目应该是相等的，于是我们做上标记，出现黑点记为1，出现白点记为0，在保证每张碎纸片切割均匀，大小基本相等的前提下，在切割的边界处按照一定的方向都能得到一组0,1序列，类似基因的碱基序列。我们将得到的0,1序列用向量表出，看作独立的样本，通过计算固定样本于其余样本之间距离的极小值，将距离较近的归为一类，这样通过逐步并类法，经过有限次的类聚就能将分裂的纸片归为到一类。于是，接下来我们建立聚类模型。总体思路如下程序图。4 模型建立与求解 问题1算法步骤(1)规定两点间的距离为，两类间的距离，即与的距离为：=min(,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18。m,n1,2，)(2)计算各样本间的距离，并记在分类距离对称表中，并记为,算作第0步分类，此时(3)选择表中的最短距离，设为，则将，合并成一个新类，记为(4)计算新类与其他类之间的距离，定义表示新类与之间的距离 （5）作表，将中的第行和列删去，加上第行，第列，其中元素由（4）确定，这样得到一个新的分类距离对称表，并记为,表示一次类聚后的距离表。（6）对按3,4，5重复类似的工作，得。 （7）一直重复直到最后只剩下两类为止，并做类聚图。下面我们给出与的类聚结果，与可以做类似处理。运算相对复杂，下面只给出运算的结果，用类聚图表示。 经人工干预可以明显发现，作为文字的最左边，在计算的时候我们以作为基准，分别记下其余碎片与其之间的距离，出现最小距离的那个样本与之拼接，并作为新的一个样本参比较。重复这这个过程即可将所有碎片拼接。结果为8-14-12-15-3-10-2-16-1-4-5-13-18-11-7-17-0-6答案详见附录15 模型的评价、改进及推广5.1 模型评价 优点：（1）本模型可以处理任何规则切割下的碎片拼接问题，通过有限次聚类即可将所有的碎纸片归为一类。 （2）算法简洁，具有可操作性。与完全人工相比，工作效率大为改善，且具有较高的准确度。 缺点; (1)目前，计算机尚不能自动数点，识别点的颜色并记录点的序列，人工数点相对费力耗时，对不规则碎片难以处理。5.2模型改进和推广 （1）模型的改进：在人工干预的前提下，确定各边界的0,1序列。我们引入相似度来刻画边界吻合程度，来作为匹配的准则,。我们根据网格覆盖原理，当网格足够小，0,1的序列足够长，吻合度就越大。按照假设，与固定碎片4个方向匹配的其余碎片方向唯一，即，相匹配，如图。我们给出相似度公式：。为了提高拼接时的效率，我们编写了相关程序来记录和统计相似度的大小。具体程序见附录2。经过模型的改进，问题（1）到问题(3),在拼接时就会更加方便和准确。具体的操作过程，由于数据较多不再演示。（2）模型的推广： 我们在参阅了众多有关碎纸复原问题的论文并比较了每一种方法的优缺点之后，完善自身碎纸复原的数学模型并使其脱离先前理想假设，将模型方法应用于一般的不规则且大小不一的碎纸复原问题。首先，通过参考其他有关碎纸复原问题的论文，我们发现大部分实际的碎纸复原问题的解决都需要克服碎纸片的外形无规则与大小不同的问题。在现阶段，通过计算机智能识别纸片原有图文并将其组合十分困难。所以，一般的实际碎纸复原问题基本采用外形几何法匹配并通过碎纸片上文字的排布（文字的行数、行高、排布位置）等加之人工干预而实现的半自动碎纸复原。但这些方法并不能有效的实现碎纸片的复原问题。其原因主要有以下方面：其一，对于碎纸片的先期预处理太过复杂，并且工程量巨大。对于不规则纸片需要通过预处理实现由纸片事物向虚拟图像的过渡，并且将图像补添或删减部分，将其归为几何图形。工程繁复且易出现误差，在执行过程中不易控制。其二，在人们撕纸的过程中，为了简便一般会将撕过纸片折叠再次撕碎。这样便会出现一系列外形相似的图片。在对碎纸片几何化处理的过程中会出现大量几何外形相似的纸片。在之后利用文字排布进行组合的过程中也面临相似问题。基于以上分析所得到的信息，我们将碎纸复原问题的数学模型在不改变模型主题的条件下进行适当的改进，使其更加符合实际碎纸复原问题解决的要求。在进行碎纸复原过程中，往往忽略边缘色彩问题。忽略每一张碎片边缘都位于文字间隔部分的极限情况，在撕纸过程中将纸上文字（或图画）撕开后，两张纸对侧边缘的色彩排布基本一致。但在实际中因为人为或是纸张自身缺陷问题，致使碎纸片边缘参差不齐甚至出现毛边造成色彩损坏失真问题。其次考虑色彩问题时一般会使用像素这一判别量，但像素表示的单位太小致使在任何涉及边缘的出现误差的情况下都会是边缘像素出现极大误差，从而影响碎纸复原。在前面的数学模型理论中，我们引入了网格覆盖碎纸片并记录边缘表格黑白变量的方法。在处理实际问题的过程中，我们所得到的切割边界的（0,1）序列是不等长的。也就是说我们不能使用向量这一数学量去比较两张纸片边缘分向量差值的最小值而判断两张纸片是否放置一起。为此，我们根据生物学中DNA的转录问题设计以下针对实际碎纸复原问题的解决方法。1. 使用扫描仪或数码相机等录入设备将碎纸实物转化为电子图像。2. 运用二值化及锐化技术使碎纸图像边缘清晰。将网格覆盖于碎纸图像上，记录边缘0（白色）、1（黑色）的排布序列。3. 不同纸张比较，以较短边的0,1排布序列为基准。与较长边的0，1排布序列相比较，不相符时使较短边沿较长边序列移动，记录较长边每段0,1排布序列与较短边0,1排布序列的相似度，将相似度较大的碎片放在一起。除此外，在碎纸复原时，可以外加使用几何相似及文字排布等图像辨别方法综合复原碎纸片。随着计算机技术和图像识别技术的发展，依据边缘色彩相似度复原的方法复原碎纸片的精确度会逐步提高。参考文献1 陶波，于志伟图像的自动拼接中国生物医学工程学报，1997,16（4）:29-352 朱延娟，周来水二维非规则碎片的匹配算法。计算机工程，2007,33(24):7-93 陈光亭，裘哲勇，数学建模高等教育出版社。4 贾海燕。碎纸自动拼接关键技术研究。长沙：国防科技大学，20055 王晓东算法设计与分析.第二版，北京：电子工业出版社，2004 48-516 王爱民，孙兰荪，图像研究综述，测控技术，2000019（5）：1-619附录1（1）附件1给出的中文文件的碎片数据拼接复原结果的表格形式：8141215310216145913181171706复原结果的图片形式：（2）附件2给出的英文文件的碎片数据拼接复原结果的表格形式：3627151811051913108121417164复原结果的图片形式：第二问：附件3给出的中文文件的碎片数据拼接复原结果的表格形式：4954651431862571921781181909511221292891188141611978676999162961317963116163726177205236168100766214230412314719150179120861952618718381484616124358118912210313019388167258910574141283159821991351273160203169134393151107115176943484183904712142124144771121499713616412758431251318210919716184110187661061502117315718120413914529641112015921804837755544206101049817217159720813815812668175451740137535693153701663219671156831322001780332021981513317020585152165276089146102154114401512071551401851081174101113194119123复原结果的图片形式：第二问：附件4给出的英文文件的碎片数据拼接复原结果的表格形式：1234567891011121314151617181911917511154190184210418064106414932204653967147220114817019619894113164781039180101261006172814638651107294015818698241171505595892303746127419194931418812112610515511417618215122572027116582515913911296313815353381231201758550160187972033162041108116136733620713515764319945173791611791437208217496111933142168621695419213311818916219711287084601468174137195847172156962399122901851099132181956916716316618811114420631303413110252717810171426620510157741458313455185635169183152441181771282001315212514019387894872121771240102115复原结果的图片形式：第3问：给出的英文文件的碎片数据拼接复原结果的表格形式复原结果的图片形式（转下页）：12345678910111213141516171819178b111b125a140a155a150a183b174b110a66a108a18b29a189b81b164b20a47a136b289a10b36a76b178a44a25b192a124b22a120b144a79a14a59a60b147a152a5a3186b153a84b42b30a38a121a98a94b61b137b45a138a56b131b187b86b200b143b4199b11b161a169b194b173b206b156a34a181b198b87a132b93a72b175a97a39b83a588b107a149b180a37b191a65b115b166b1b151b170b41a70b139b2a162b203b90a6114a184b179b116b207a58a158a197a154b28b12a17b102b64b208a142a57a24a13a7146a171b31a201a50a190b92b19b16b177b53b202a21b130a163a193b73b159a35a8165b195a128a157a168a46a67a63b75b167a117b8b68b188a127a40a182b122a172a93b7b85b148b77a4a69a32a74b126b176a185a0b80b27a135b141a204b105a1023b133a48a51b95a160b119a33b71b52a62a129b118b101a15b205a82b145a9b1199a43a96b109a123a6a104a134a113a26b49b91a106b100b55b103a112a196b54b附录21.计算两0,1序列相似度#includestdio.hvoid main(void)int i,j,k=0;float m;bool x48=1,1,1,1;bool y48=1,0,1,0;bool s48;for(i=0;i48;i+)si=xiyi;printf(%d ,si);if(si=0)k+;printf(%d ,k);m=float(k)/48;printf(%f,m);printf(n);scanf(d,j);2. 附件1：I1=imread(008.bmp);I2=imread(014.bmp);I3=imread(012.bmp);I4=imread(015.bmp);I5=imread(003.bmp);I6=imread(010.bmp);I7=imread(002.bmp);I8=imread(016.bmp);I9=imread(001.bmp);I10=imread(004.bmp);I11=imread(005.bmp);I12=imread(009.bmp);I13=imread(013.bmp);I14=imread(018.bmp);I15=imread(011.bmp);I16=imread(007.bmp);I17=imread(017.bmp);I18=imread(000.bmp);I19=imread(006.bmp);I=I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,I17,I18,I19;imshow(I)附件2I1=imread(003.bmp);I2=imread(006.bmp);I3=imread(002.bmp);I4=imread(007.bmp);I5=imread(015.bmp);I6=imread(018.bmp);I7=imread(011.bmp);I8=imread(000.bmp);I9=imread(005.bmp);I10=imread(001.bmp);I11=imread(009.bmp);I12=imread(013.bmp);I13=imread(010.bmp);I14=imread(008.bmp);I15=imread(012.bmp);I16=imread(014.bmp);I17=imread(017.bmp);I18=imread(016.bmp);I19=imread(004.bmp);I=I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,I17,I18,I19;imshow(I)附件34954651431862571921781181909511221292891188141611978676999162961317963116163726177205236168100766214230412314719150179120861952618718381484616124358118912210313019388167258910574141283159821991351273160203169134393151107115176943484183904712142124144771121499713616412758431251318210919716184110187661061502117315718120413914529641112015921804837755544206101049817217159720813815812668175451740137535693153701663219671156831322001780332021981513317020585152165276089146102154114401512071551401851081174101113194119123I11=imread(049.bmp);I12=imread(054.bmp);I13=imread(065.bmp);I14=imread(143.bmp);I15=imread(186.bmp);I16=imread(002.bmp);I17=imread(057.bmp);I18=imread(192.bmp);I19=imread(178.bmp);I110=imread(118.bmp);I111=imread(190.bmp);I112=imread(095.bmp);I113=imread(011.bmp);I114=imread(022.bmp);I115=imread(129.bmp);I116=imread(028.bmp);I117=imread(091.bmp);I118=imread(188.bmp);I119=imread(141.bmp);I21=imread(061.bmp);I22=imread(019.bmp);I23=imread(078.bmp);I24=imread(067.bmp);I25=imread(069.bmp);I26=imread(099.bmp);I27=imread(162.bmp);I28=imread(096.bmp);I29=imread(131.bmp);I210=imread(079.bmp);I211=imread(063.bmp);I212=imread(116.bmp);I213=imread(163.bmp);I214=imread(072.bmp);I215=imread(006.bmp);I216=imread(177.bmp);I217=imread(020.bmp);I218=imread(052.bmp);I219=imread(036.bmp);I31=imread(168.bmp);I32=imread(100.bmp);I33=imread(076.bmp);I34=imread(062.bmp);I35=imread(142.bmp);I36=imread(030.bmp);I37=imread(041.bmp);I38=imread(023.bmp);I39=imread(147.bmp);I310=imread(191.bmp);I311=imread(050.bmp);I312=imread(179.bmp);I313=imread(120.bmp);I314=imread(086.bmp);I315=imread(195.bmp);I316=imread(026.bmp);I317=imread(001.bmp);I318=imread(087.bmp);I319=imread(018.bmp);I41=imread(038.bmp);I42=imread(148.bmp);I43=imread(046.bmp);I44=imread(161.bmp);I45=imread(024.bmp);I46=imread(035.bmp);I47=imread(081.bmp);I48=imread(189.bmp);I49=imread(122.bmp);I410=imread(103.bmp);I411=imread(130.bmp);I412=imread(193.bmp);I413=imread(088.bmp);I414=imread(167.bmp);I415=imread(025.bmp);I416=imread(008.bmp);I417=imread(009.bmp);I418=imread(105.bmp);I419=imread(074.bmp);I51=imread(014.bmp);I52=imread(128.bmp);I53=imread(003.bmp);I54=imread(159.bmp);I55=imread(082.bmp);I56=imread(199.bmp);I57=imread(135.bmp);I58=imread(012.bmp);I59=imread(073.bmp);I510=imread(160.bmp);I511=imread(203.bmp);I512=imread(169.bmp);I513=imread(134.bmp);I514=imread(039.bmp);I515=imread(031.bmp);I516=imread(051.bmp);I517=imread(107.bmp);I518=imread(115.bmp);I519=imread(176.bmp);I61=imread(094.bmp);I62=imread(034.bmp);I63=imread(084.bmp);I64=imread(183.bmp);I65=imread(090.bmp);I66=imread(047.bmp);I67=imread(121.bmp);I68=imread(042.bmp);I69=imread(124.bmp);I610=imread(144.bmp);I611=imread(077.bmp);I612=imread(112.bmp);I613=imread(149.bmp);I614=imread(097.bmp);I615=imread(136.bmp);I616=imread(164.bmp);I617=imread(127.bmp);I618=imread(058.bmp);I619=imread(043.bmp);I71=imread(125.bmp);I72=imread(013.bmp);I73=imread(182.bmp);I74=imread(109.bmp);I75=imread(197.bmp);I76=imread(016.bmp);I77=imread(184.bmp);I78=imread(110.bmp);I79=imread(187.bmp);I710=imread(066.bmp);I711=imread(106.bmp);I712=imread(150.bmp);I713=imread(021.bmp);I714=imread(173.bmp);I715=imread(157.bmp);I716=imread(181.bmp);I717=imread(204.bmp);I718=imread(139.bmp);I719=imread(145.bmp);I81=imread(029.bmp);I82=imread(064.bmp);I83=imread(111.bmp);I84=imread(201.bmp);I85=imread(005.bmp);I86=imread(092.bmp);I87=imread(180.bmp);I88=imread(048.bmp);I89=imread(037.bmp);I810=imread(075.bmp);I811=imread(055.bmp);I812=imread(044.bmp);I813=imread(206.bmp);I814=imread(010.bmp);I815=imread(104.bmp);I816=imread(098.bmp);I817=imread(172.bmp);I818=imread(171.bmp);I819=imread(059.bmp);I91=imread(007.bmp);I92=imread(208.bmp);I93=imread(138.bmp);I94=imread(158.bmp);I95=imread(126.bmp);I96=imread(068.bmp);I97=imread(175.bmp);I98=imread(045.bmp);I99=imread(174.bmp);I910=imread(000.bmp);I911=imread(137.bmp);I912=imread(053.bmp);I913=imread(056.bmp);I914=imread(093.bmp);I915=imread(153.bmp);I916=imread(070.bmp);I917=imread(166.bmp);I918=imread(032.bmp);I919=imread(196.bmp);I101=imread(071.bmp);I102=imread(156.bmp);I103=imread(083.bmp);I104=imread(132.bmp);I105=imread(200.bmp);I106=imread(017.bmp);I107=imread(080.bmp);I108=imread(033.bmp);I109=imread(202.bmp);I1010=imread(198.bmp);I1011=imread(015.bmp);I1012=imread(133.bmp);I1013=imread(170.bmp);I1014=imread(205.bmp);I1015=imread(085.bmp);I1016=imread(152.bmp);I1017=imread(165.bmp);I1018=imread(027.bmp);I1019=imread(0