B题碎纸片的拼接复原.doc

B题 碎纸片的拼接复原摘要图像碎片拼接复原是借助计算机把大量的图像碎片重新拼接成初始图像的完整模型。这一问题在考古、刑侦、古生物学以及壁画保存等方面具有广泛的应用。要从成千上万的图像碎片中找到相互邻接的图像碎片，并最终拼接成完整的模型，需要用计算机和人工干预辅助相结合的方式来完成。本文就对碎纸片的拼接复原问题进行分析研究，针对单面纵切，单面既纵切又横切，双面既纵切又横切纸片等情况的拼接复原问题，建立了相应的数学模型，并运用、等数学软件，分别对题目所提出的问题进行求解。对于问题一，我们将碎纸片信息导入软件中，得到每个碎纸片的像素值，并利用该像数值计算出碎纸片间拼接的候选权重，再以该权重值为依据对碎纸片进行配对，得到了碎纸片的拼接顺序，进而实现了仅纵切纸片时中、英文碎片的拼接复原。对于问题二，我们首先筛选出了左右两侧有空白的碎片,并把剩余碎片的信息导入中,按照问题一中的方法计算出候选权重；利用该候选权重对碎片的编号进行定位，得到了一个定位矩阵并将其导入到中，在中分析该矩阵，可得到一个最优的拼接次序；再进行人工干预，找到左页边的碎片编号并将其置于第一位，然后按照最优连接次序将碎片进行拼接，得一个完整的行碎片。再对行碎片进行拼接，最优选择标准为：同一段落内行间距相同。可以得到按段落划分的几个碎片。此时进行人工干预，人为拼接为完整图片。在本问中，由于中、英文字的差异，在对英文碎片拼接时本文只采用了候选权重法进行处理。对于问题三，考虑到英文双面的数据过于庞大，本文先对数据进行分类，用软件将处于同一行的碎片提取出来，分别存放在不同的文件夹中；然后再对文件夹内的数据进行候选权重的处理，按照问题二中的方法得到最优排列次序，按该排列次序拼接碎片得到了22个横向碎片，其中有11对正反面，再对这些横向碎片进行计算候选权重的处理，然后确定一个最优排列次序，完成图片的拼接。关键词：候选权重 最优排列次序 行间距 像素 一、问题重述1.1问题背景破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技自的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。1.2问题提出根据题意本文需要解决的问题有：（1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。（2）对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。（3）上述所给碎片数据均为单面打印文件，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。二、问题分析2.1问题的重要性分析(社会背景) 众所周知,破碎文件的拼接在一些司法物证复原和军事情报等领域有着重要的应用,重要文件的复原有时能够发挥很大的作用,但是破碎文件拼接复原需由人工完成,准确率虽然很高,可是浪费时间,效率也很低。如何解决以上一系列问题变得非常重要。2.2有关方面在这个问题上做过的研究现有文献大部分都是针对二维（或三维）非规则碎片匹配算法的研究，针对碎纸机破碎的规则文件的拼接方面的文献极少，本文基于对所给五个附件碎片数据的处理和分析，针对各具体问题提出了若干数学模型得到了较为满意的解答。2.3对问题的分析针对问题一，首先考虑将碎片导入中，并提取出每张碎纸片边缘上的像素值，然后利用这些像素值寻找到与某单个碎片左右两边相匹配的碎片，最后再进行图片的拼接，得到完整的图片。针对问题二，考虑到当前的切割方式，首先进行碎片的横向拼接：先提取出碎片左右边缘的像素值寻找某个碎片左右两侧最匹配的碎片，拼接在一行内。然后再对已拼接完成的行碎片进行纵向拼接，最终得到完整图片。针对问题三，由于问题三在横纵切割的基础上又加上了正反面，数据庞大，所以可以先对数据进行分类，将数据按行分类，把处于同一行的数据分在一组。再在组内进行数据处理，来完成行的拼接。最后将拼接好的行组合为完整文章。三、模型假设1.破碎纸片的形状规则；2破碎纸片的信息未丢失；3本文引用数据、资料均真实可靠。四、符号说明1符号名称第个碎片的最后一列像素第个碎片的第一列像素行像素的个数碎片排列在碎片右边的权重所组成的矩阵纸张的第个碎片候选权重矩阵中某一行最小候选权重值的位置由组成的矩阵五、 模型的建立与求解5.1问题一的求解 5.1.1模型一的概述将单个图片A分割成碎片集合,为确定碎片的顺序,需识别原始图像中的相邻碎片对,用表示碎片接在后面的可能性,称为候选权重。所有的候选权重组成一个阶的非负矩阵。在所有的碎片序列中，候选权重和为最大（或最小）的序列是接近正确重组的碎片序列。寻找最大（或最小）权重值的碎片序列，对序列中的数值进行分析后，即可确定碎片的排列顺序，进而解决碎片拼接复原的问题。5.1.2碎片的拼接复原问题求解步骤如下：步骤1：将碎片导入中，确定出每个碎片的像素值。步骤2：利用碎片转化后的像素值，计算出碎片间的候选权重。步骤3：在已得权重矩阵中寻找最大（或最小）权重值，组成两两配对。步骤4：将已配对完成的碎片按顺序整合为完整图片。5.1.3候选权重的计算2准确率高的候选权重技术可减少重组次数，提高图像重组效率。本文选择简化相似系数匹配的权重计算方式进行处理。下面给出两个碎片相似系数的定义。碎片和碎片相邻边界像素的候选权重为：= (1)则当最小时，表示碎片对为最优配对组。5.1.4中文碎片重组步骤1：将碎片按照附件1中所给顺序导入到中，得到数组为，碎片像素为。步骤2：取第个碎片的第72列像素值，设为。第个碎片的第1列像素值，设为。利用5.1.2中的权重计算公式计算权重，得。矩阵见附录1步骤3：定位中每行元素的最小值位置，将输入到矩阵中，导出到表格中。此位置表示第个碎片右边所接最优碎片为。矩阵见附录2步骤4：在中分析，可得有个最优链接次序。此时进行人工干预，找到左页边的碎片的编号，并将其置于第一位，然后按照最优次序排列即可。如下表表1：表1：中文复原后碎片序号0080140120150030010 02016001004005009013018011007017000006步骤5：用按照此最优次序拼接图片，得到完整的最优结果。所得复原后图片见附录3各步骤在3中的程序语句见附录45.1.5英文碎片重组英文碎片中的字母与汉字相比变化较少，同样长度的语句中，英文字母可以多次重复，由于汉字变化多的特点，即使被切割成碎片，也很容易通过辨别汉字的一部分来确定，但是一个英文字母在不同的英文单词出现的概率极大，所以切割之后字母重组很容易产生错误的匹配。但是本题中，每列像素值有1980个，数量巨大，足以抵消英文特点所造成错误匹配概率大的问题。所以上述中文处理的方式在这里仍然适用。方法同上，经过处理可得碎片最优次序排列如下表表2：表2：英文复原后碎片序号0030060020070015018011000005001009013010008012014017006004用按照此最优次序拼接图片，得到完整的最优结果。所得复原后图片见附录5。5.2问题二的模型建立与求解5.2.1中文碎片的拼接复原碎片的横向拼接：步骤1：将碎片中左右两侧有空白的碎片筛选出来。（原因见注1）步骤2：将剩余碎片导入到中4，得到数组,其像素为。步骤3：取第个碎片的第最后一列像素值，设为。第个碎片的第一列像素值，设为。利用5.1.2中的权重计算公式计算权重，得。矩阵的一部分见附录6。步骤4：定位中每行元素的最小值位置，将输入到矩阵中，5导出到表格中。此位置表示第x个碎片右边所接最优碎片为。步骤5：在中分析，可得一个最优链接次序。此时进行人工干预，找到左页边的碎片的编号，并将其置于第一位，然后按照最优次序排列即可（特殊情况见注2）。步骤6：整合步骤4中序列，用拼接碎片，可得11个横向碎片。例：见下图： 1 2 3 4箭头表示拼接方向4321。其中图3是通过候选权重法所得。其余3块拼接方式为人工干预。碎片的纵向拼接：步骤7：根据同一段落文字间行间距相同原理，可设计一个程序寻找到4个段落。然后再进行人为干预，对4个段落进行排序，最终得到最优结果。步骤8：将此11个横向图片左旋90。步骤9：用编程，见附录7，将11个横向碎片拼接为一个完整图片，在右旋90即可。排列顺序表格如下表3：表3：第二问中文碎片排列次序表049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196071156083132200017080033202198015113170205085152165027060089146102154114040151207155140185108117004101113194119123步骤10：按照矩阵中的数据，可得排列顺序，见附录8。附件3的复原图片见附录9注1：先分析白边出现的原因，有两点，一是碎片为页边角，二是切割时恰好从2个汉字中间切割。若不剔除白边，在进行权重值计算过程中，会遇到一种情况：在寻找碎片的右边正确拼接碎片时，会出现多个相同的最小值。无法唯一确定谁为正确的。且程序在此处就会中断，无法继续运行。经分析得出原因为：假设寻找碎片的右边正确拼接碎片，此时有2个（或3个及3个以上）碎片、左边为完全白边，则在进行权重计算过程中会出现，假设为碎片所有配对权重中的最小值，则此时碎片右边所拼接的最优碎片就不能唯一确定，那么在运行找出最小值位置的程序时，会在此处就会中断，无法继续运行。所以要剔除白边进行计算。例如：附件3中的065与014、071。碎片014、071与碎片065的权重相等，无法唯一确定谁是正确的，抑或是都为非正确的。注2：排列最优次序过程中会遇到一种情况：假设第个碎片的右边可接碎片有、,为正确碎片，为错误碎片。而系统根据权重所确定的右边所接最优碎片为错误碎片而不是正确的。经分析得出原因为：若一个汉字的某个笔画恰好被分割在2个碎片中，得到左边碎片的笔画位置处为完全白边是碎片，一边为笔画位置完全黑边的碎片。这就导致了次2个正确组合的碎片间的误差计算较大，而错误碎片（假设有部分完全白边与的白边位置几乎吻合）与间的误差较小，这就导致了计算结果为与接，而非与接。此时只能进行人工干预进行人为拼接。例如：附件3中的001与087为正确配对组，但是经程序进行计算得001与003为最优配对组。5.2.2英文碎片的拼接复原由于英文的另一特点，既不像中文一样方正，经常出现、等不规则字母，若在同一段落继续使用段落间行间距相同原理，误差会较大。所以选择用候选权重法进行拼接。具体步骤如下:步骤1步骤6与中文碎片拼接相同。步骤7：将11个横向碎片左旋90，用候选权重法进行计算，方法同5.1.3.步骤8：用编程，将11个横向碎片拼接为一个完整图片，再右旋90即可。排列顺序表格如下表4：表4：第二问英文碎片排列次序表191075011154190184002104180064106004149032204065039067147201148170196198094113164078103091080101026100006017028146086051107029040158186098024117150005059058092030037046127019194093141088121126105155114176182151022057202071165082159139001129063138153053038123120175085050160187097203031020041108116136073036207135015076043199045173079161179143208021007049061119033142168062169054192133118189162197112070084060014068174137195008047172156096023099122090185109132181095069167163166188111144206003130034013110025027178171042066205010157074145083134055018056035016009183152044081077128200131052125140193087089048072012177124000102115附件4的复原图片见附录105.3问题三的模型建立与求解因为考虑到英文双面，数据过于庞大，可以先对数据进行分类，用将可能是同一行的碎片提取行出来。分别存放在不同的文件夹。然后再对文件夹内的数据进行候选权重处理。具体步骤如下：步骤1：将所有碎片导入到中4，得到数组,其像素为。步骤2：在中设计一个程序，寻找到为同一行中的碎片。并分别存放在文件夹中。程序见附录11。步骤3：取出一个文件夹中的碎片，取其中第个碎片的第最后一列像素值，设为。第个碎片的第一列像素值，设为。利用5.1.2中的权重计算公式计算权重，得。步骤4：定位中每行元素的最小值位置，将输入到矩阵中，5导出到表格中。此位置表示第个碎片右边所接最优碎片为。步骤5：在中分析，可得一个最优链接次序。此时进行人工干预，找到左页边的碎片的编号，并将其置于第一位，然后按照最优次序排列即可。步骤6：整合步骤4中序列，用拼接碎片，可得一个横向序列。步骤7：对剩余文件夹重复步骤36。可得到22个横向碎片。其中有11对正反面。步骤8：对上述22对横向碎片进行候选权重处理。操作同5.2.2中步骤78。最终得到排列顺序表格如下表5和表6：表5：第三问A面复原后次序表125a140a155a150a183b174b110a066a108a018b029a189b81b164b020a047a136b036a076b178a044a25b192a124b022a120b144a079a014a059a060b147a152a005a084b042b030a038a121a098a094b061b137b045a138a056b131b187b086b200b143b161a169b194b173b206b156a034a181b198b087a132b093a072b175a097a039b083a149b180a037b191a065b115b166b001b151b170b041a070b139b002a162b203b090a179b116b207a058a158a197a154b028b012a017b102b064b208a142a057a024a013a031a201a050a190b092b019b016b177b053b202a021b130a163a193b073b159a035a128a157a168a046a067a063b075b167a117b008b068b188a127a040a182b122a172a085b148b077a004a069a032a074b126b176a185a000b080b027a135b141a104b105a048a51b095a160b119a033b071b052a062a129b118b101a015b205a082b145a009b096b109a123a006a104a134a113a026b049b091a106b100b055b103a112a196b054b表6：第三问B面复原后次序表136a047b020b164a081a189a029b018a108b066b110b174a183a150b155b140b125b111a078a005b152b014b060a059b014b070b144b120a022b124a192b025a044b178b076a036b010a089b143a200a086a187a131a056a138b045b137a061a094a098b121b038b030b042a084a153b186a083b039a097b175b072a093b132a087b198a181a034b156b206a173a194a169a161b011a199a090b203a162a002b139a070a041b170a151a001a166a115a065a191b037a180b149a107b088a013b024b057b142b208b064a102a017a012b018a154a197b158b058b207b116a179a184a114b035b159b073a193a163b130b021a202b053a177a016a019a092a190a050b201b031b171a146b173b122b182a040b127b188b068a08a117a167b075a063a067b046b168b157n128b195b165a105b104a141b135a027b080a000a185b176b126a074a032b069b004b077b148b085a007a003a009a145b082a205b015a101b118a129a062b052b071a033a119b160a095b051a048b133b023a054a196a112b103b055a100a106a091b049a026a113b134b104b006b123b109b096a043b099b附件5的复原图片见附录12，未做出附件6的复原图片。六、模型评价及不足与改进6.1.1模型评价：1. 本文中的所有图片碎片都用了MATLAB 软件进行处理，而MATLAB软件功能十分强大，精确度也很高，从这个角度可证明我们结果的可靠性与方法的合理性。2.本文采用的是半自动的拼接复原的方法，能解决大多数碎纸片的拼接问题，在实践中能广泛运用。3.本文在对于中、英文碎纸片的拼接复原时，考虑到了中、英文字的差异，进而采用了一些不同的处理方法对其进行拼接复原，具有很强的实际意义。6.1.2模型不足与改进:1.在对既纵切又横切碎片的拼接复原问题时，采用了较多的人工干预过程，这还有待改善。七、参考文献1肖华勇，数学建模竞赛优秀论文精选与点评，西安：西安工业大学出版社，2011.11.2王东平，王清贤，罗永军，李炳龙,等，BMP图像碎片重组中的候选权重方法，计算机应用，2007,27（12）:3062-3066,2007年12月.3贺超英，应用与实验教程，北京：电子工业出版社，2010.1.4周品，赵新芬，数学建模与仿真，北京：国防工业出版社，2009.4.5董臻圃，数学建模方法与实践，北京：国防工业出版社，2006.8.八、附录附录清单:1矩阵;2. 矩阵;3.附件1中文复原图片;4.各步骤在中的程序语句;5.附件2英文复原图片;6. 矩阵;7 程序;8矩阵;9附录3中文复原图片;10附录4英文复原图片;11程序;12附录五正反两面复原图片;附录1112.3459120.8996114.9578126.6207105.124111.851942.60172107.734699.3832114.7145119.7585117.81115.809247.90416101.4045109.2452112.9893100.6577120.9301112.986117.7008107.5949108.4917103.9839117.9902100.002598.76083108.5703119.993104.5071121.059113.3355110.1409111.6208107.075299.33728112.2661114.9464107.6551114.5804106.575841.63389116.6729109.171482.24051115.1034110.8628107.915117.0128112.9062103.8362116.044295.8175495.4564498.75677111.47494.18159115.7737100.957473.92847107.044184.016330111.1499111.16110.9544124.0391106.2927111.4473108.7329100.847598.71193102.6073110.7935115.431117.6599109.100790.84483111.8284104.19881.41191112.3737114.999111.6659116.7014115.919108.0175118.6887106.2086103.14122.3476115.927842.11871117.8924122.0595109.9219116.5402102.7474100.4623104.7834108.6389106.3843117.276110.630499.40817112.304440.5593283.6098895.90978115.8533106.1609115.6317104.667191.13685108.716493.3199661.15976104.0513113.0854111.2921117.2086115.382899.35757106.6052102.391686.04162104.7384116.208292.59138121.558198.9501894.53684104.796895.646168.28884116.0205117.8526115.531941.87958117.2027109.6844126.4885115.5341112.06119.595848.2864121.9164119.1123121.766109.1397127.1795110.2417114.70744.4603119.0411117.3941123.5749120.3958109.105122.0065105.8216102.827104.8356114.5495106.1822116.026116.641897.26355111.8859105.231190.4411110.7108102.5867115.681299.25932116.8045107.996105.35116.5057106.782999.208107.9652102.555116.055599.48999113.8598105.0069104.3503105.1805112.729109.6861106.5305107.0091107.3578107.8081109.9786114.945798.4670931.44308111.3206114.4523112.691149.68623112.927595.17482113.1675105.8095108.9691114.352106.3034115.8604108.3925104.682295.87635103.9424114.987990.5852796.27031109.123118.3216100.263942.40399108.6785112.8852100.8233108.2596107.067199.43637104.7656110.7235106.969696.2336494.1560183.5234675.4309598.8461978.6557560.3734997.99353101.127887.40991111.8088106.7827114.494799.76742109.6398110.3247102.0536107.66950.99001109.7866110.9796103.9651101.1288104.4516115.714547.2968396.1671112.4946110.496296.96066113.9912117.5845101.2205108.747543.91419118.6412104.4648112.2458112.5453117.7723105.4954106.6786110.4204101.1433109.8639113.2392109.3983116.34115.6976113.2987101.3262107.6532102.092298.51557106.1933104.449992.19517101.8265103.9772101.69194.70926103.655688.5899695.93368101.512792.1957228.16653100.3531100.50395.90968109.1832109.4418100.5829109.3706113.804199.7602690.60139112.4344109.211540.21859106.25187.7464102.115537.9349103.226995.9736890.1161106.4321102.0023105.6789117.7372114.6209110.0391114.875113.0443116.6394112.9159108.9474123.6196119.0649113.5192120.394116.3288121.7629117.1971111.8704117.0739112.3284119.8949114.3899116.7027114.1665105.0307108.859105.8658105.1242101.2799121.4651109.7855111.1301107.1126109.379443.4976108.1771105.956103.177889.30672106.3831115.5797102.634附录2xy1725317411566107981891510141131281316141915131641721811912附录3附录4程序如下：步骤2：求候选权重矩阵语句： square_matrix = zeros(19, 19); for i=1:19 col1=x1i(:,72); for j=1:19 col2=x1j(:,1); minus = double(col1)-double(col2); square = minus*minus; square_matrix(i,j)=square; end end square_matrix=sqrt(square_matrix/1980);(即为C1) 步骤3：求位置矩阵B的语句： A= square_matrix Amin=min(A)； for i=1:19 x,y=find(A=Amin(i,1); B(i,1)=x; B(i,2)=y; End 3步骤5：拼接图片语句： h=imread(C:UsersxiayangDesktop附件1008.bmp); n=imread(C:UsersxiayangDesktop附件1014.bmp); l=imread(C:UsersxiayangDesktop附件1012.bmp); o=imread(C:UsersxiayangDesktop附件1015.bmp); c=imread(C:UsersxiayangDesktop附件1003.bmp); j=imread(C:UsersxiayangDesktop附件1010.bmp); b=imread(C:UsersxiayangDesktop附件1002.bmp); q=imread(C:UsersxiayangDesktop附件1016.bmp); a=imread(C:UsersxiayangDesktop附件1001.bmp); d=imread(C:UsersxiayangDesktop附件1004.bmp); e=imread(C:UsersxiayangDesktop附件1005.bmp); i=imread(C:UsersxiayangDesktop附件1009.bmp); m=imread(C:UsersxiayangDesktop附件1013.bmp); s=imread(C:UsersxiayangDesktop附件1018.bmp); k=imread(C:UsersxiayangDesktop附件1011.bmp); g=imread(C:UsersxiayangDesktop附件1007.bmp); r=imread(C:UsersxiayangDesktop附件1017.bmp); x=imread(C:UsersxiayangDesktop附件1000.bmp); f=imread(C:UsersxiayangDesktop附件1006.bmp); y=h n l o c j b q a d e i m s k g r x f; imwrite(y,C:UsersxiayangDesktop附件11000.bmp);附录5附录6130.03178.75161.15149.19147.88152.87149.26142.36148.52146.91129.91120.8480.10188.525114.34108.59107.91105.5137.98134.79101.7472.03885.65103.96112.7384.04684.735156.7397.326119.59113.97101.291.255125.15123.76124.57136.86117.09119.0793.64591.85195.507118.6999.452103.38128.53127.8786.51581.87380.261100.49109.6467.54575.773115.78122.51110.7299.33883.292107.41107.65108.31110.95117125.97101.572.90469.79193.332102.5775.76735.975118.11124.9990.58575.6872.895.516105.178.14234.99128.1123.79100.4364.46562.77686.89995.78973.78875.2129.86144.72112.31121.19118.91116.03141.44105.4108.4115.76125.3895.55569.77169.27181.436100.9375.64672.783119.49113.7192.18644.98444.20473.61685.68566.47869.506139.64132.59137.19110.84100.39125.47117.36117.86123.111