大学生数学建模B题-碎纸片的拼接复原.doc

-全国大学生数学建模竞赛碎纸片的拼接复原摘要本文从开发碎纸片的自动拼接技术，以提高拼接复原效率的角度出发，研究了不同切割方式、不同语言文字和单双面打印下的破碎文件拼接复原方面的问题。与同类研究相比，本文旨在突出研讨自动拼接技术在生活中应用问题的重要性。针对问题一，附件1和附件2中的碎纸片都只是纵向切割的情况，运用切割边缘灰度检测模型和图论模型，对附件1和附件2中的碎纸片进展了拼接复原，得到了附件1和附件2中破碎文件复原后的排列顺序如下所示：附件1中碎纸片文件复原顺序表表1附件2中碎纸片文件复原顺序表表2 针对问题二，附件3和附件4中的碎纸片是横向、纵向都切割，且附件3和附件4中碎纸片上的文字是不同语言文字的情况，运用层次聚类方法、灰度检测模型、图论模型和递归收缩算法，并且参加了人工干预的影响，对附件3和附件4中的破碎文件先进展局部复原，且进展人工干预，得到了附件3中破碎文件复原后的排列顺序表表4和附件4中破碎文件复原后的排列顺序表表7。针对问题三，附件5中的碎纸片是横向、纵向都切，且是双面打印的英文文件，拼接复原难度大大增加，所以，将在问题一、问题二的数学模型根底上，增加识别英文字母的模型，对附件5中的破碎文件进展拼接复原。关键词:自动拼接 边缘灰度检测 图论模型 层次聚类 递归收缩算法一问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间完成任务。随着计算机技术的开展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片仅纵切，建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进展拼接复原。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进展拼接复原。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。二模型假设1、不考虑扫描破碎文件储存为图片时，光线强度对碎纸片灰度的影响。2、假设碎纸片的扫描图片转存为灰度矩阵时，图片信息无缺失。3、假设需要拼接复原的碎纸片均为同一规格。三 符号说明P碎纸片的编号K常数，0<K<碎纸片总数碎纸片P的灰度矩阵碎纸片p左侧第一列单个像素序列碎纸片p左侧第一列单个像素序列T碎纸片两两拼接的匹配值碎纸片P与碎纸片的最大匹配值所有碎纸片拼接起来时的最大匹配值X中文碎纸片上边界所截汉字高度Y中文碎纸片中部所截汉字高度Z中文碎纸片下边界所截汉字高度C同行截取的碎纸片集合注：未说明符号在文中用到时注明四 问题一的解答由于附件1件中所给的图片均是纵向切割的，所以每图片纵向的两条边，是判断相连图片的重要信息载体，我们运用边缘灰度检测模型和图论模型对问题一进展求解。4.1 (单面、纵切)碎纸片纵向边缘灰度检测1的模型对于给定的来自同一页印刷文字文件的碎纸机破碎纸片仅纵切，每一碎纸片都存有各不一样的信息，而每块纸片的纵向切口是互相连接的关键，我们经分析，对于仅纵切的情况，主要分析切口边界的单个像素灰度序列值进展比拟。将碎纸片信息转为灰度存为矩阵:由于要去比拟碎纸片的纵向边界，就将矩阵中的第一列左边界单个像素灰度序列值和最后一列右边界单个像素灰度序列值取出分别存为矩阵和：要判断任意两碎纸片和是否存在相连的关系，即可转变为判断两碎纸片按第一碎纸片左边匹配第二碎纸片右边、第一碎纸片右边匹配第二碎纸片左边的方法，求出边界的匹配值T1和T2，比拟T1和T2的大小，将最大的一个值确定为这两碎纸片的最大匹配值。将所有碎纸片按两两匹配的关系进展匹配，使每碎纸片都与其他碎纸片之间均取得最大匹配值。4.2 (单面、纵切)碎纸片拼接复原的模型通过上一步骤的处理，我们可以得到碎纸片两两拼接时的最大匹配值，因为需要拼接复原的碎纸片来自同一页印刷文字文件，所以拼接复原出来的页面应该是完整的一页，且碎纸片的拼接顺序按从左至右或从右至左是唯一的，从而可知有最优的拼接复原顺序。运用图论模型2，可以得到碎纸片的最正确排序。假设某页印刷文字文件被切割成了五块A、B、C、D、E其编号是任意的，两碎纸片连线上的数是它们之间的最大匹配值，如下列图所示：根据上图，建立如下表格，其中表格行列相交处表示它们之间的匹配最大值。ABCDEA0309555B30073395C9573012D531085E5952850运用图论模型的知识和最优原那么，可得将碎纸片A、B、C、D、E不同方式排序时总的匹配值，然后把不同方式下取得总的匹配值中最大的排序方式顺序选取出来，即为最优拼接复原顺序。可得顺序：A-B-C-E-D4.3 对附件1、附件2中的碎纸片的拼接复原1对附件1中的碎纸片的拼接复原运用4.1和4.2建立的模型，通过Matlab编程实现，可以求得附件1中19碎纸片两两拼接复原的匹配值，经过对19碎纸片两两拼接复原的匹配值的筛选，可得下表：根据上表，按照左右关系排序可以得到附件1中19碎纸片拼接复原的顺序从左到右：附件1中碎纸片文件复原顺序表表1附件1中的碎纸片拼接复原的全图见附录 1.12对附件2中的碎纸片的拼接复原运用4.1和4.2建立的模型，通过Matlab编程实现，可以求得附件2中19碎纸片两两拼接复原的匹配值，经过对19碎纸片两两拼接复原的匹配值的筛选，可得下表：根据上表，按照左右关系排序可以得到附件2中19碎纸片拼接复原的顺序从左到右：附件2中碎纸片文件复原顺序表表2附件2中的碎纸片拼接复原的全图见附录 1.2五 问题二的解答针对附件3、附件4中横、纵都切的来自同一页印刷文字文件的碎纸片，由于分割出的碎纸片数量超过200，数量较多，各图片之间的切割边界上的信息有限，假设采用问题一中建立的模型求解，结果不理想。经过分析，对于像附件3类似的横纵都切，且来自同一页的中文文件，由于中文在打印排版时是按点阵的方式进展的，其每个汉字所占长和宽均相等特殊汉字除外，所以我们采用层次聚类方法、灰度检测方法和图论模型相结合，对附件3中的碎纸片进展拼接复原。5.1(单面、横纵都切)中文碎纸片拼接复原的模型运用层次聚类方法中的AGNES (AGglomerative NESting)算法3将(单面、横纵都切)中文碎纸片进展分类。利用中文打印排版时是点阵的规律和特点，可知，假设碎纸片属于同一行的话，其文字被截断的横、纵位置一样，如下所示：假设两碎纸片不是同一行的，那么X、Y、Z将不会对应相等，如下所示：由此可以通过对碎纸片两两比拟进展行聚类，模型如下：经过行聚类模型，可得到m类碎纸片，到此，把每一类看做是一整页，即第m类中的碎片只用考虑纵向切割，借助问题一中的模型求解，把每一类中的碎纸片进展左、右连接顺序匹配，根据得到的匹配关系加与人工干预可得到复原文件。(单面、横纵都切)中文碎纸片拼接复原的人工干预1干预时间节点：得到每一类中的碎纸片的匹配关系后，进展人工干预，得到每一类的拼接复原顺序；然后将每一类看作整体进展纵向拼接，进展人工干预。2干预方式：根据此类中的碎纸片的匹配关系进展拼接，假设发现拼接无错位且词或句语义合理，那么认为是正确拼接；假设发现此类中的碎片不适合在此类中拼接，那么将其选出，在其他类别中进展拼接。当横向拼接完后，在进展纵向拼接，此时拼接量就很小了，手工拼接即可完成得到复原文件。3干预方法：递归收缩算法4假设A、B、C、D来自同一类的四碎纸片，人工拼接时A和C可以拼在一起，那么把A和C拼接后看作是一个整体，然后在和B、D拼接，一直拼接下去，这样需要拼接的块数不断减少，直到这一类碎纸片全都拼接复原出来。 (单面、横纵都切)中文碎纸片的拼接复原根据上面的模型可得附件3中碎纸片的初步类别此处运用Matlab编程得到初步类别，然后经人工干预合并类别后可得表3 ，如下所示：附件3中的碎纸片类别表 表3将表3 的每一类运用问题一中的模型可得到从左向右拼接的顺序表 ，然后进展了人工干预加之对问题一中模型的应用，可以得到附件3中碎纸片的复原顺序表，如下所下示:附件3中破碎文件的复原顺序表 表4附件3中的破碎文件拼接复原后的全图如件附录 1.35.2(单面、横纵都切)英文碎纸片拼接复原的模型运用层次聚类方法中的AGNES (AGglomerative NESting)算法3将(单面、横纵都切)英文碎纸片进展分类。利用英文打印排版时和书写英文的规律可知：英文假设用四条线段将其横向分割开的化，其信息主要集中在侧的两条横线，如下所示：根据此特点可知，假设碎纸片属于同一行的话，其英文单词被截局部信息集中的位置处于同一水平高度，如下所示：灰色局部表示信息集中的区域，由此可以运用第二问中处理中文碎纸片的模型进展初步分类，可得下表：附件4中的碎纸片类别表 表5将表中的每一类运用问题一中的模型可得到从左向右拼接的顺序表如下所示：附件4中的破碎文件类别拼接复原表 (表6)由于英文的拼接复原比中文的要复杂，得到上表后需进展人工干预，将空缺的局部拼接上去。经此过程可得附件4中破碎文件的最终拼接顺序表：附件4中破碎文件的复原顺序表 表7附件4中的破碎文件拼接复原后的全图如件附录 1.4六 问题三的解答6.1 (双面、横纵都切)英文碎纸片拼接复原的模型 对问题三进展分析，可知附件5中的碎纸片是横向、纵向都切，且是双面打印的英文文件，拼接复原难度大大增加，所以，将在问题一、问题二的数学模型根底上，增加识别英文字母的模型，对附件5中的破碎文件进展拼接复原。 首先对英文字母大、小写的特点和图片中字母间距、高度、宽度等进展统计分析，得出相应结论，然后对碎纸片进展识别，在运用图论模型中的收缩算法对碎纸片进展拼接复原。七 模型的检验与评价7.1 模型的检验方法通过对复原出的破碎文件进展语意、语法和文件完整与否等方面的检查，可验证问题一、问题二的解答结果是否正确，以及模型的合理性。通过编程，附件1用程序fujian1_2gaij.m见附录2.10进展检验、附件2用程序fujian2_2gaij.m见附录2.11进展检验，也可得到附件1、附件2碎纸片拼接复原的顺序和完整的复原图。7.2 模型的评价优点： 1、运用问题一的模型对类似附件1中的破碎文件进展拼接复原时快速、方便，合理。2、问题二中的模型参加了人工干预的成分，是的拼接复原的结果更加准确、可靠。缺点：由于本文建立的模型主要运用了边缘灰度检测和图论模型，在一定程度上没有充分利用碎片的信息，从而导致拼接复原过程中需要参加适当的人工干预，自动化、智能化水平降低，建立的模型还需要进一步的完善和优化 。绘制破碎文件复原的全图时，编写的程序过长。八 模型的改良和推广8.1 模型的改良经过分析和比拟，对于问题一和问题二所建立的模型的缺乏改良方案有：1、可以考虑采用提取、识别汉字和字母的算法，对碎纸片进展更高层次的匹配，减小匹配时的误差，充分利用碎纸片的灰度信息。2、对于模型求解时参加了人工干预，可以在进一步优化和完善程序，尽量降低人工干预在模型求解中占的比例，使其更加接近自动化、智能化的要求。8.2 模型的推广本模型可以推广到彩色图片的复原，和考古时发现的大量瓷碎片和大量其它文件碎片进展复原，不规那么碎纸片。图片的复原运的可行性。 参考文献1 了了，邓善熙，MATLAB在图像处理技术方面的应用，2013/9/13。2 建,蕊,图论模型的建立及转化方法,，2013/9/13。3 不详 ,层次聚类算法PPT，wenku.baidu./view/3f5070986bec0975f465e225.html，2013/9/13。4 梁勇强 , 钟艳如 , 庆霞,生成有向装配连接图有向割集的递归收缩算法,，2013/9/14。附录附录一：附录1.1附件1中破碎文件的拼接复原全图附录 1.2 附件2中破碎文件的拼接复原全图附录 1.3 附件3中破碎文件的拼接复原全图附录 1.4 附件4中破碎文件的拼接复原全图附录二：文中所涉及的程序所有程序均用到 Matlab R2011b附录 2.1% 求附件1中碎纸片两两拼接的匹配值 (fujian_1.m)clc,clear,close allk=1;for i=0:18 N=sprintf('%03d.bmp',i); a=imread(N); %循环导入18图片 n=size(a,2); A(:,k)=a(:,1); %分别取出每图片首列和尾列的灰度值 k=k+1; A(:,k)=a(:,n); k=k+1;endn=size(A);t=0;C=zeros(38);for i=1:2:n(1,2)for j=2:2:n(1,2) t=0;if(j=(i+1)&j=i)for k=1:n(1,1)if(A(k,i)<122&A(k,j)<122) t=t+1; C(i,j)=t; endendendendend m=size(C); r=0; for i=1:2:m(1,1) r=r+1; k=C(i,1);for j=2:m(1,2) if (C(i,j)>k) k=C(i,j); D(r,1)=i; D(r,2)=j; D(r,3)=k;endendendnd=size(D,1);for i=1:nd G(i,2)=(D(i,1)-1)/2; %图片序号 G(i,1)=(D(i,2)-2)/2; %图片序号 G(i,3)=D(i,3);end附录 2.2%附件1中碎纸片复原全图文件fujian1_1huatu.mclc,clearx1 = imread('008.bmp');x2 = imread('014.bmp');x3= imread('012.bmp');x4= imread('015.bmp');x5= imread('003.bmp');x6= imread('010.bmp');x7= imread('002.bmp');x8= imread('016.bmp');x9= imread('001.bmp');x10= imread('004.bmp');x11= imread('005.bmp');x12= imread('009.bmp');x13= imread('013.bmp');x14= imread('018.bmp');x15= imread('011.bmp');x16= imread('007.bmp');x17 = imread('017.bmp');x18= imread('000.bmp');x19= imread('006.bmp');z = x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19;imshow(z)附录 2.3%求附件2中碎纸片两两拼接的匹配值 (fujian_2.m)clc,clear,close allk=1;for i=0:18 N=sprintf('%03d.bmp',i); a=imread(N); n=size(a,2); A(:,k)=a(:,1); k=k+1; A(:,k)=a(:,n); k=k+1;endn=size(A);t=0;C=zeros(38);for i=1:2:n(1,2)for j=2:2:n(1,2) t=0;if(j=(i+1)&j=i)for k=1:n(1,1)if(A(k,i)<122&A(k,j)<122) t=t+1; C(i,j)=t; endendendendendm=size(C); r=0; for i=1:2:m(1,1) r=r+1; k=C(i,1);for j=2:m(1,2) if (C(i,j)>k) k=C(i,j); D(r,1)=i; D(r,2)=j; D(r,3)=k;endendend nd=size(D,1);for i=1:nd G(i,2)=(D(i,1)-1)/2; G(i,1)=(D(i,2)-2)/2; G(i,3)=D(i,3);end附录 2.4%附件2碎纸片复原全图文件fujian2_1_huatu.mclc,clearx1 = imread('003.bmp');x2 = imread('006.bmp');x3= imread('002.bmp');x4= imread('007.bmp');x5= imread('015.bmp');x6= imread('018.bmp');x7= imread('011.bmp');x8= imread('000.bmp');x9= imread('005.bmp');x10= imread('001.bmp');x11= imread('009.bmp');x12= imread('013.bmp');x13= imread('010.bmp');x14= imread('008.bmp');x15= imread('012.bmp');x16= imread('014.bmp');x17 = imread('017.bmp');x18= imread('016.bmp');x19= imread('004.bmp');z = x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19;imshow(z)附录 2.5%对附件3中的碎纸片进展初步分类 (fujian_3_fl.m)clc,clear,close allt=0;for i= 0:208 N=sprintf('%03d.bmp',i); a=imread(N); n=size(a); t=t+1;for j=1:n(1,1)for k=1:n(1,2)if (a(j,k)>=122) a(j,k)=0; %将白点赋值为0else a(j,k)=1; %将黑点赋值为1endif (a(j,k)=1) b(1,t)=i; b(j+1,t)=1;endendendendnb=size(b);A=zeros(nb(1,2);for i=1:nb(1,2)for j=1:nb(1,2) A(i,j)=inf;endendfor j=1:nb(1,2)-1for k=j+1:nb(1,2) A(j,k)=t; t=0;for i=2:nb(1,1)if(b(i,j)=b(i,k) t=t+1;endendendendn=size(A);for i=1:n(1,1) t=0; B(i,1)=i-1;for j=1:n(1,2)if (A(i,j)<15) t=t+1; B(i,t+1)=j-2; endendend附录 2.6%对附件3中初步分类的结果进展行排列 (fujian_3_zx.m)clc,clear,close allB=load('shuju2.txt'); %shuju2.txt中的数据为初步分类后位于同一行的图片编号A=zeros(180,418);nA=size(A);for i=1:nA(1,1)for j=1:nA(1,2) A(i,j)=inf;endendn=size(B,2); for i=1:n j=B(1,i); N=sprintf('%03d.bmp',j); a=imread(N); n=size(a,2); x=2*j-1; A(:,x)=a(:,1); A(:,x+1)=a(:,n);endn=size(A); t=0;C=zeros(418);for i=1:2:n(1,2)for j=2:2:n(1,2) t=0;if(j=(i+1)&j=i)for k=1:n(1,1)if( A(k,i)<122&A(k,j)<122) t=t+1; C(i,j)=t; endendendendendm=size(C); r=0; for i=1:2:m(1,1) r=r+1; k=C(i,1);for j=2:m(1,2) if (C(i,j)>k) k=C(i,j); D(r,1)=i; D(r,2)=j; D(r,3)=k;endendendnd=size(D,1);for i=1:nd G(i,2)=(D(i,1)+1)/2; G(i,1)=D(i,2)/2; G(i,3)=D(i,3);end附录 2.7%附件3 碎纸片复原全图文件fujian3_huatu.mclc,clearx1 = imread('049.bmp');x2 = imread('054.bmp');x3= imread('065.bmp');x4= imread('143.bmp');x5= imread('186.bmp');x6= imread('002.bmp');x7= imread('057.bmp');x8= imread('192.bmp');x9= imread('178.bmp');x10= imread('118.bmp');x11= imread('190.bmp');x12= imread('095.bmp');x13= imread('011.bmp');x14= imread('022.bmp');x15= imread('129.bmp');x16= imread('028.bmp');x17 = imread('091.bmp');x18= imread('188.bmp');x19= imread('141.bmp');x20 = imread('061.bmp');x21= imread('019.bmp');x22= imread('078.bmp');x23= imread('067.bmp');x24= imread('069.bmp');x25= imread('099.bmp');x26= imread('162.bmp');x27= imread('096.bmp');x28= imread('131.bmp');x29= imread('079.bmp');x30= imread('063.bmp');x31= imread('116.bmp');x32= imread('163.bmp');x33= imread('072.bmp');x34= imread('006.bmp');x35= imread('177.bmp');x36 = imread('020.bmp');x37= imread('052.bmp');x38= imread('036.bmp');x39= imread('168.bmp');x40= imread('100.bmp');x41= imread('076.bmp');x42= imread('062.bmp');x43= imread('142.bmp');x44= imread('030.bmp');x45= imread('041.bmp');x46= imread('023.bmp');x47= imread('147.bmp');x48= imread('191.bmp');x49= imread('050.bmp');x50= imread('179.bmp');x51= imread('120.bmp');x52= imread('086.bmp');x53= imread('195.bmp');x54= imread('026.bmp');x55 = imread('001.bmp');x56= imread('087.bmp');x57= imread('018.bmp');x58= imread('038.bmp');x59= imread('148.bmp');x60= imread('046.bmp');x61= imread('161.bmp');x62= imread('024.bmp');x63= imread('035.bmp');x64= imread('081.bmp');x65= imread('189.bmp');x66= imread('122.bmp');x67= imread('103.bmp');x68= imread('130.bmp');x69= imread('193.bmp');x70= imread('088.bmp');x71= imread('167.bmp');x72= imread('025.bmp');x73= imread('008.bmp');x74 = imread('009.bmp');x75= imread('105.bmp');x76= imread('074.bmp');x77= imread('071.bmp');x78= imread('156.bmp');x79= imread('083.bmp');x80= imread('132.bmp');x81= imread('200.bmp');x82= imread('017.bmp');x83= imread('080.bmp');x84= imread('033.bmp');x85= imread('202.bmp');x86= imread('198.bmp');x87= imread('015.bmp');x88= imread('133.bmp');x89= imread('170.bmp');x90= imread('205.bmp');x91= imread('085.bmp');x92= imread('152.bmp');x93 = imread('165.bmp');x94= imread('027.bmp');x95= imread('060.bmp');x96= imread('014.bmp');x97= imread('128.bmp');x98= imread('003.bmp');x99= imread('159.bmp');x100= imread('082.bmp');x101= imread('199.bmp');x102= imread('135.bmp');x103= imread('012.bmp');x104= imread('073.bmp');x105= imread('160.bmp');x106= imread('203.bmp');x107= imread('169.bmp');x108= imread('134.bmp');x109= imread('039.bmp');x110= imread('031.bmp');x111= imread('051.bmp');x112 = imread('107.bmp');x113= imread('115.bmp');x114= imread('176.bmp');x115 = imread('094.bmp');x116 = imread('034.bmp');x117= imread('084.bmp');x118= imread('183.bmp');x119= imread('090.bmp');x120= imread('047.bmp');x121= imread('121.bmp');x122= imread('042.bmp');x123= imread('124.bmp');x124= imread('144.bmp');x125= imread('077.bmp');x126= imread('112.bmp');x127= imread('149.bmp');x128= imread('097.bmp');x129= imread('136.bmp');x130= imread('164.bmp');x131 = imread('127.bmp');x132= imread('058.bmp');x133= imread('043.bmp');x134 = imread('125.bmp');x135= imread('013.bmp');x136= imread('182.bmp');x137= imread('109.bmp');x138= imread('197.bmp');x139= imread('016.bmp');x140= imread('184.bmp');x141= imread('110.bmp');x142= imread('187.bmp');x143= imread('066.bmp');x144= imread('106.bmp');x145= imread('150.bmp');x146= imread('021.bmp');x147= imread('173.bmp');x148= imread('157.bmp');x149= imread('181.bmp');x150= imread('204.bmp');x151= imread('139.bmp');x152= imread('145.bmp');x153 = imread('029.bmp');x154 = imread('064.bmp');x155= imread('111.bmp');x156= imread('201.bmp');x157= imread('005.bmp');x158= imread('092.bmp');x159= imread('180.bmp');x160= imread('048.bmp');x161= imread('037.bmp');x162= imread('075.bmp');x163= imread('055.bmp');x164= imread('044.bmp');x165= imread('206.bmp');x166= imread('010.bmp');x167= imread('104.bmp');x168= imread('098.bmp');x169 = imread('172.bmp');x170= imread('171.bmp');x171= imread('059.bmp');x172 = imread('007.bmp');x173 = imread('208.bmp');x174= imread('138.bmp');x175= imread('158.bmp');x176= imread('126.bmp');x177= imread('068.bmp');x178= imread('175.bmp');x179= imread('045.bmp');x180= imread('174.bmp');x181= imread('000.bmp');x182= imread('137.bmp');x183= imread('053.bmp');x184= imread('056.bmp');x185= imread('093.bmp');x186= imread('153.bmp'