建模优秀论文碎纸片的自动拼接复原技术研究1

2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B 我们的参赛报名号为（如果赛区设置报名号的话）：J3509所属学校（请填写完整的全名）：西安外事学院参赛队员(打印并签名)：1.胡新行2.李强3.侯奕伶指导教师或指导教师组负责人(打印并签名)：薛应珍 （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）日期：2013年92013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的自动拼接复原方法研究摘要针对碎纸片数量巨大，难以用人工进行拼接的问题，本文首先运用MATLAB软件对各图片进行了像素化处理，得到了每张图片的像素点矩阵；其次，手工提取每个像素点矩阵的首列和末列，组成像素点数组；接着，建立数学模型，运用JAVA编程对进行像素点数列组按照相似度进行自动排序；最后，根据排序结果，再次运用MATLAB软件对碎纸片做到了自动拼接复原。具体如下：问题一：对于来自同一页印刷文字文件且仅纵切的碎纸片拼接复原问题。首先，运用MATLAB对附件1，2中所有图片进行数据化（像素化处理）处理，得到了19个1980×72的矩阵；其次，手工提取每个矩阵的首列和末列，得到1个1980×38的像素点数组，接着，用JAVA编程对数据按照相似度进行自动排序；最后，根据排序结果，再次运用MATLAB软件对碎纸片做到了自动拼接复原的结果。问题二：与问题一方法类似，但是此处图片既有纵切又有横切，所以，在手工提取像素点数组、排序和拼接时，采用先考虑左右，再考虑上下的过程达到图片自动拼接的结果。问题三：针对双面打印文件横纵切的碎片，首先，运用MATLAB实现数据化之后，形成碎片文件数量相等的两部分，记录其中一部分的排序即得出原文件一面排序，另一部分排序则与前一部分每行顺序颠倒且编号为a、b相对应；接着，运用JAVA编程对所得数据进行自动排序；最后，运用MATLAB对碎纸片做到了自动拼接复原的结果。

关键字：碎纸片拼接MATLAB像素化JAVA编程相似度问题重述在当今信息大爆炸的时代，破碎文件的拼接在司法物证复原、历史文献修复、医药学以及军事情报获取等领域都有着重要的应用。拼接工作的传统做法是复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。本文就是针对碎纸片数量巨大，难以用人工进行拼接的问题，找到碎纸片自动拼接复原的方法。模型的假设1、假设碎纸片文字清晰可见；2、假设图片没有旋转；3、假设所有纸片没有丢失；4、假设没有内容重复的碎纸片；5、纸片两边衔接的时候没有任何缺损符号说明：第张图片（=1、2、3...18、19）；：第张图片（=1、2、3...18、19）；，：第张图片左右两侧数据；，：第张图片左右两侧数据；，：第张图片上下两侧数据；，：第张图片上下两侧数据；：第张图片右侧数据与第张图片左侧数据的差；：第张图片下侧数据与第张图片上侧数据的差；：的纵向和；：的横向和；：附件1、2在MATLAB中用函数imread所读取图片文件中数据；：附件3、4在MATLAB中用函数imread所读取图片文件中数据。问题分析常规文档碎纸片计算机拼接方法一般利用碎片边缘的尖点特征、尖角特征、面积特征等几何特征，搜索与之匹配的相邻碎纸片并进行拼接，这种基于边界几何特征的拼接方法并不适用于边缘形状相似的碎纸片。但是人手撕裂碎纸片时，为节省时间习惯上总是先将碎纸片重叠在一起，然后撕裂，再将碎纸片重叠起来，再继续撕裂，这样反复下去，直到得到满意大小的碎纸片为止。这种撕裂过程会产生很多形状非常相似的碎纸片，拼接时如果只利用碎片的边界特征，拼接效果并不理想。对这类边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否匹配，然而由于理论和技术的限制，让计算机具备类似人那种识别碎片边缘的字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。但是利用现有的技术，完全可以获取碎片文字所在行的几何特征信息，比如文字行的行高、文字行的间距等信息，拼接碎片时如利用这些信息进行拼接，其拼接效率无疑比单纯利用边界几何特征方法要好些。由于大多数文字文档的文字行方向和表格线方向平行且单一，如果碎片内的文字行或表格在碎片边缘断裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行或表格，凭此特征可以很容易地从形状相似的多碎片中挑选出相邻碎片。因文字行或表格线的高度特征、间距特征的识别比字迹断线识别和文字图像的理解实现起来要容易得多，利用碎片内文字行特征或表格特征拼接形状相似的碎纸片理论上是可行的。另一方面由于计算机数字分析图像能力的缺陷，让计算机对碎片进行完全意义上的自动化拼接也几乎是不太可能，为保证拼接的准确性，需要在拼接过程中加入人工干扰过程。一般而言拼接碎片时先利用计算机搜索与目标碎片匹配的未拼接碎片，并根据匹配程度按顺序显示待选碎片，操作员再根据人脑进一步分析结果舍弃或拼接待选碎片。这种半自动拼接方法综合利用了计算机高速计算能力以及人的文字图像识别和理解能力，拼接效率比纯人工高拼接准确率也好于纯计算机拼接法。本文将详细研究这种基于文字特征，表格特征的碎片半自动拼接方法。模型的建立和求解问题一：解题思路首先，对原题附件1，2中的各19张图片进行像素化处理，（所谓像素化，就是通过计算机软件把图像分割成若干个小方格,每个小方格称为一个像素点，计算机通过表示这些像素点的位置、颜色、亮度等信息,从而表示出整幅图像。）得到了每张图片的像素点矩阵；其次，提取每张图片的像素点矩阵中最左边和最右边的数据，并进行编号，得到1980×38矩阵，接着，用每张图片最右边的数据和其他图片最左边的数据进行相似度计算，并按相似度从小到大排序；最后，相似度最大两张图片就是应该拼接在一起的，再考虑剩下的其他数据就可以得到最终的拼接结果。为了清楚的描述我们的思路，建立流程图如下（图1）：图1问题处理流程图结果数组图片像素点矩阵像素化数据的提取 排序结果数组图片像素点矩阵 （二）模型的建立与求解运用MATLAB中imread函数将原题中附件1，2中每张图片进行像素化处理，得到每张图片的像素值，编程如下（表1）：将以上编程输入MATLAB，运行后得到19个1980×72的矩阵，由于数据庞大，我们这里只截取部分数据画面，截图如下（图2），。图2原题附件1中图片的像素化矩阵截图表1附件1、2中各图片像素化MATLAB程序原题附件1：原题附件2:I1=imread('附件1\000.bmp')；I2=imread('附件1\001.bmp')；I3=imread('附件1\002.bmp')；I4=imread('附件1\003.bmp')；I5=imread('附件1\004.bmp')；I6=imread('附件1\005.bmp')；I7=imread('附件1\006.bmp')；I8=imread('附件1\007.bmp')；I9=imread('附件1\008.bmp')；I10=imread('附件1\009.bmp')；I11=imread('附件1\010.bmp')；I12=imread('附件1\011.bmp')；I13=imread('附件1\012.bmp')；I14=imread('附件1\013.bmp')；I15=imread('附件1\014.bmp')；I16=imread('附件1\015.bmp')；I17=imread('附件1\016.bmp')；I18=imread('附件1\017.bmp')；I19=imread('附件1\018.bmp')I1=imread('附件2\003.bmp');I2=imread('附件2\006.bmp');I3=imread('附件2\002.bmp');I4=imread('附件2\007.bmp');I5=imread('附件2\015.bmp');I6=imread('附件2\018.bmp');I7=imread('附件2\011.bmp');I8=imread('附件2\000.bmp');I9=imread('附件2\005.bmp');I10=imread('附件2\001.bmp');I11=imread('附件2\009.bmp')；I12=imread('附件2\013.bmp')；I13=imread('附件2\010.bmp')；I14=imread('附件2\008.bmp')；I15=imread('附件2\012.bmp')；I16=imread('附件2\014.bmp')；I17=imread('附件2\017.bmp')；I18=imread('附件2\016.bmp')；I19=imread('附件2\004.bmp')数据的提取表2从19个1980×72数据矩阵中提取每个列的最左边和最右边数据得到1980×38的数据组得到这19组1980×72的矩阵后,我们手动提取每组矩阵的最左列表2从19个1980×72数据矩阵中提取每个列的最左边和最右边数据得到1980×38的数据组运用JAVA编程对表2中得到的数据组按照相似度从小到大进行自动排序，步骤为：第一步，将表2中每张图片中得到数据的最左侧和最右侧记为，；将提取到的i列右侧和j列左侧相减，得到一个新的值，记作，即。=-（ij）第二步，求出的纵向和，记作。=（1i19）第三步，运用JAVA编程（程序见附件1）对按从小到大排序，得到与相关性最大的列,进而得到结果。模型的结果根据以上模型的建立和求解过程，得到排序结果（表3，表4），拼接图见本文附件2,3.表3原题附件1的排序结果08141215031002160104050913181107170006表4原题附件2的排序结果03060207151811000501091310081214171604问题二：解题思路问题二相比问题一更麻烦一些，碎片同时涉及到横切和纵切的问题。但是因为有问题一做铺垫，运用问题中的JAVA程序仍然能轻松的做出来。首先，还是对209张图片进行像素化处理，得到了每张图片的像素点矩阵；其次，提取每张图片的像素点矩阵中最左边、最右边、最上边和最下边的数据，并进行编号，得到180×72矩阵，接着，用每张图片最右边的数据和其他图片最左边的数据进行相似度计算，并按相似度从小到大排序；然后，相似度最大两张图片就是拼接在一起的，再考虑剩下的其他数据就可以得到部分横向拼接好图片。然后，用同样的方法得到已经拼接好的图片像素点的最上边和最下边数据，进行相似度计算，并按相似度从小到大排序；然后，相似度最大两张图片就是拼接在一起的，得到最终拼接好的大图。模型的建立与求解首先，运用MATLAB中imread函数将原题中附件3，4中每张图片进行像素化处理，得到每张图的像素值。编程如下（表5）：表5附件3、4中各图片像素化MATLAB程序原题附件3：原题附件4:D1=imread('附件3\000.bmp')；D2=imread('附件3\001.bmp')；D3=imread('附件3\002.bmp')；…D208=imread('附件3\207.bmp')；D209=imread('附件3\208.bmp')D1=imread('附件4\000.bmp');D2=imread('附件4\001.bmp');D3=imread('附件4\002.bmp');…D208=imread('附件4\207.bmp')；D209=imread('附件4\208.bmp')方法同问题一，我们将以上编程输入MATLAB，运行后得到209个180×72的矩阵。得到这209组180×72的矩阵后,我们手动提取每组矩阵的最左列、最右列最上列和最下列数据，得到一个836列的数据组，由于数据庞大，故只截取部分，如表6。表6从209个1980表6从209个1980×72数据矩阵中提取每个列的最左边，最右边，最上边和最下边数据得到180×72的数据组（局部）运用JAVA编程对表6中得到的数据组进行自动排序。将从每张图片中得到数据的最左侧和最右侧记为，；最上边和最下边，，建立如下数学模型 =-（ij）=（ij）第二步，求出的纵向和及横向和，记作及。=（1i19）=（1i19）第三步，运用JAVA编程（程序见附件1）对按从小到大排序，得到与相关性最大的列,进而得到结果。（三）模型的结果根据以上模型的建立和求解过程，得到排序结果（表7，表8），拼接图见本文附件4，5.表7原题附件3的排序结果049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108117004101113194119123表8原题附件4的排序结果191075011154190184002104180064106004149032204065039067147201148170196198094113164078103091080101026100006017028146086051107029040158186098024117150005059058092030037046127019194093141088121126105155114176182151022057202071165082159139001129063138153053038123120175085050160187097203031020041108116136073036207135015076043199045173079161179143208021007049061119033142168062169054192133118179162197112070084060014068174137195008047172156096023099122090185109132181095069167163166188111144206003130034013110025027178171042066205010157074145083134055018056035016009183152044081077128200131052125140193087089048072012177124000102115问题三：针对问题三，由于碎片两面都有文字，我们用MATLAB实现数据化后用JAVA编程对数据排序，形成碎片文件数量相等的两部分，记录其中一部分的排序即得出原文件一面排序，另一部分排序则与前一部分每行顺序颠倒且编号为ab相对应，用JAVA编程对数据进行处理实现图片的排序，记录排序用MATLAB拼接碎片文件得到附件5的复原文件。表9原题附件5正面排序结果136a47b20b164a81a189a29b18a108b66b110b174a183a150b155b140b125b111a78a5b152b147b60a59b14b79b144b120a22b124a192b25a44b178b76a36b10a29b143a200a86a187a131a56a138b45b137a61a94a98b121b38b30b42a84a188b186a83b39a97b175b72a93b132a87b198a181a34b150b206a173a194a169a161b11a199a90b203a162a2b139a70a41b170a151a1a166a115a65a191b37a180b149a107b88a13b24b57b142b208b64a102a17a12b28a154a197b158b58b207b116a179a184a114b35b159b73a193a163b130b21a202b53a177a16a19a92a190a50b201b31b171a146b172b122b182a40b127b188b68a8a117a167b75a63a67b46b168b157b128b195b165a105b204a141b135a27b80a0a185b176b126a74a32b69b4b77b148b85a7a3a9a145b82a215b15a101b118a129a62b52b71a33a119b160a95b51a48b133b23a54a196a112b103b55a100a106a91b49a26a113b134b104b6b123b109b96a43b99b表10原题附件5反面排序结果78b111b125a140a155a150a183b174b110a66a108a18b29a189b81b164b20a47a136b29a10b36a76b178a44a25b192a124b22a120b144a79a14a59a60b147a152a5a186b188a84b42b30a38a121a98a94b61b137b45a138a56b131b187b86b200b143b199b11b161a169b194b173b206b150a34a181b198b87a132b93a72b175a97a39b83a88b107a149b180a37b191a65b115b166b1b151b170b41a70b139b2a162b203b90a114a184b179b116b207a58a158a197a154b28b12a17b102b64b208a142a57a24a13a146a171b31a201a50a190b92b19b16b177b53b202a21b130a163a193b73b159a35a165b195a128a157a168a46a67a63b75b167a117b8b68b188a127a40a182b122a172a3b7b85b148a77a4a69a32a74b126b176a185a0b80b27a135b141a204b105a23b133a48a51b95a160b119a33b71b52a62a129b118b101a15b215a82b145a9b99a43a96b109a123a6a104a134a113a26b49b91a106b100b55b103a112a196b54b模型检验任意选定一页中英文均有的双面文件打印出来，用碎纸机切碎纸片（横纵切），得到碎纸片若干。再将若干碎纸片完整扫描到电脑中，将碎纸片不按序随意进行编码，按处理附件5的方法进行拼接。

首先应用MLTLAB将全部碎片数据化，再用所编出可判断数据相似度的JAVA编程对数据进行处理实现图片的排序，有错的顺序进行人工干预，手动排序。按行列记录排列顺序（表格形式呈现）并运用MATLAB拼接结碎片文件得到原文件。模型的评价和推广评价对于此模型我们有以下方面：模型的优点其一是利用matlab和java等软件来处理数据简单，可以节省很多时间当然同时也可以节省人力物力；其二是此模型可以处理碎片量较大斯片复杂的纸片，更有力于我们在较短时间内拼接成功；其三是此模型注重实际用途，较大程度上适用于实际，不断的完善碎纸片拼接技术。模型的缺点是在利用软件操作时用到相似比去比较两组数据时用电脑程序可能存在着一定的误差，如果在加入一定的手工干预那可以进一步缩小误差。模型的推广：由于在此模型当中应用的有关图像处理技术各不相同，在实际应用过程中其使用的范围、效率、结果千差万别。在考证历史中有一些被人为损坏的资料在复原过程中极可能遇到工程量很大的拼接任务，如果纯人工去完成不仅耗时久且难度大。利用此模型处理可以较快完成工作，十分有利于研究历史。现实生活中会遇到许多重要的资料，例如：在工作中不慎损坏的重要文件，在破案中犯罪份子留下不完整的证据等对上述重要资料的复原也能用到此模型。八、参考文献[1]罗智中，《基于文字特征的文档碎纸片半自动拼接》《计算机工程与应用》2012[2]刘思峰，党耀国，方志耕等著《灰色系统理论及其应用》，北京：科学出版社，2005[3](美)阿诺德，KenAmold等《java程序设计语言》[M]北京：人民邮电出版社，2006九、附录附件1：JAVA程序如下：packageprocessor;importjava.util.ArrayList;importjava.util.Collections;importjava.util.List;publicclassCompare{ publicstaticfloatcompare(int[]a,int[]b){ intlength=a.length<b.length?a.length:b.length; intmaxLength=a.length<b.length?b.length:a.length; floatsampleCount=0; for(inti=0;i<length;i++){ if(a[i]==b[i]){ sampleCount++; } } returnsampleCount/maxLength; } publicstaticList<Element>compare(int[]a,int[][]