2013年数学建模b题.doc

+碎纸片的拼接复原【摘要】：碎纸片拼接技术是数字图像处理领域的一个重要研究方向，把计算机视觉和程序识别应用于碎纸片的复原，在考古、司法、古生物学等方面具有广泛的应用，具有重要的现实意义。本文主要结合各种实际应用背景，针对碎纸机绞碎的碎纸片，基于计算机辅助对碎纸片进行自动拼接复原研究。针对问题1，依据图像预处理理论，通过matlab程序处理图像，将图像转化成适合于计算机处理的数字图像，进行灰度分析，提取灰度矩阵。对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵A1，提取每个灰度矩阵的最后一列，生成新矩阵B1。建立碎纸片匹配模型:dai,bj=t=0m-1bti-atj2 ，其中i，j=0,n-1。p=0in-10jm-1mind(ai,bj)将矩阵A1中的任一列与矩阵B1中的每一列带入模型，所得p值对应的i ,j值，即为所拼接的碎片序列号。将程序进行循环操作，得到最终的碎片自动拼接结果。针对问题2，首先将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列和最后一列，分别生成新矩阵A2、B2；提取所有灰度矩阵的第一行和最后一行，分别作为新生成的矩阵C2、D2。由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型：dai,bj=t=0m-1btj-ati2 ，其中i，j=0,n-1。dci,dj=s=0n-1dsj-asi2 ，其中i，j=0,m-1。p=0in-10jm-1mind(ai,bj)，q=0in-10jm-1mind(ci,dj)将矩阵A2中的任一列分别与矩阵B2中每一列代入模型，所得p值对应的i ,j值即为横排序；将矩阵C2中的任一行分别于矩阵D2中的任一行代入模型，所得q值对应的i ,j值即为列排序。循环进行此程序，得计算机的最终运行结果。所得结果有少许误差，需人工调制，更正排列顺序，得最终拼接结果。针对问题3，基于碎纸片的文字行列特征，采用遗传算法，将所有的可能性拼接进行比较，进行择优性选择。反面的排序结果用于对正面排序的检验，发现结果有误差，此时，进行人工干预，调换碎纸片的排序。【关键词】: 灰度矩阵 欧式距离 图像匹配 自动拼接 人工干预一、 问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，大量的纸质物证复原工作都是以人工的方式完成的，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接不但耗费大量的人力、物力，而且还可能对物证造成一定的损坏。随着计算机技术的发展，人们试图把计算机视觉和模式识别应用于碎纸片复原，开展对碎纸片自动拼接技术的研究，以提高拼接复原效率。试讨论一下问题，并根据题目要求建立相应的模型和算法：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。结果表达格式说明：复原图片放入附录中，表格表达格式如下：(1)附件1、附件2的结果：将碎片序号按复原后顺序填入119的表格；(2)附件3、附件4的结果：将碎片序号按复原后顺序填入1119的表格；(3)附件5的结果：将碎片序号按复原后顺序填入两个1119的表格；(4)不能确定复原位置的碎片，可不填入上述表格，单独列表。二、问题分析碎纸片自动拼接技术是图像处理与识别领域中的一个较新但很典型的应用，是通过扫描和图像提取技术获取一组碎纸片的信息，然后利用计算机进行相应的处理，从而实现对这些碎纸片的全自动或半自动的拼接复原。碎纸片的自动拼接可以近似地看作是一个拼图问题。在机器人和计算机视觉领域中，很早就有学者对自动拼图进行了研究1，2。但是这些技术都利用了拼图游戏中的一些特殊特征及一些先验知识，而在许多实际应用中都不能满足这些条件。根据待拼接图像（输入）与拼接图像（输出）的不同类型3，可以将图像拼接分为四类：基于静态图像的静态图像拼接、基于静态图像的动态图像拼接、基于视频的序列的静态图像拼接和基于视频序列的动态图像拼接。本文主要致力于静态图像的静态图像拼接，即碎纸机绞碎的规则的碎纸片的自动拼接。问题1：根据图像预处理理论，通过程序语言将图像导入matlab程序，对图像进行预处理，将碎纸片转换成适合于计算机处理的数字图像形式，并对数字图像进行灰度分析，提取灰度矩阵。对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵A，提取每个灰度矩阵的最后一列，作为新矩阵B。建立碎纸片匹配模型。根据遗传算法的思想，将矩阵A中的任一行与矩阵B中的每一行带入模型，由最大相似性原理得s值对应的i ,j值，即为所拼接的碎片序列号。将程序进行循环操作，并最终建立对输入的解释。问题2：首先对碎纸片图像进行预处理，通过matlab程序将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列，生成新矩阵A2，提取最后一列，结合生成新矩阵B2；提取所有灰度矩阵的第一行，作为新生成的矩阵C2，提取最后一行，作为新矩阵D2。由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型。将矩阵A2中的任一列分别与矩阵B2中每一列代入模型，所得p值对应的i ,j值即为横排序；将矩阵C2中的任一行分别于矩阵D2中的任一行代入模型，所得q值对应的i ,j值即为列排序。循环进行此程序，得计算机的最终运行结果。所得结果有少许误差，需人工调制，更正排列顺序，得最终拼接结果。问题3：针对双面打印文件的碎纸片拼接处理，首先要对碎纸片两面的图像信息都进行图像预处理，运用matlab程序提取图像的灰度矩阵。基于碎纸机绞碎的碎纸片，每个碎纸片的大小是一样的,采用差距度量法。取矩阵中特征值从第一行中开始到限制条件取i行，限制条件是当取到i行时满足每行都是特征值的矩阵还有2m个矩阵，则这2m个矩阵为同一行碎片所产生的矩阵。包括正反面碎纸片。然后取其中矩阵左边列向量满足，此行矩阵所剩两个矩阵，此过程虽然误差较小，针对其他问题可能要产生误差，需要人工干预，剔除多余矩阵。然后取出两个中的一个矩阵，与产生的这一行矩阵进行匹配，获取一行排序较优的碎片链接。运用嵌套循环实现每行的排序连接。三、符号说明m提取灰度矩阵行（列）生成的新矩阵的行数n提取灰度矩阵行（列）生成的新矩阵的列数A提取灰度矩阵第一列生成的新矩阵B提取灰度矩阵最后一列生成的新矩阵C提取灰度矩阵第一行生成的新矩阵D提取灰度矩阵最后一行生成的新矩阵d(ai,bj)矩阵A中第i列与矩阵B中第j列的欧氏距离d(ci,dj)矩阵C中第i行与矩阵D中第j行的欧氏距离四、模型假设1） 同一切线处的两条边界灰度值的差别在误差范围之内。2） 所有的待拼接的碎纸片都是规则的。3） 假设不存在文件缺失、人为因素等意外因素。4） 假设所有的数字图像文件都是已整理好的，不需要再进行旋转、剪裁等操作。五、模型建立与问题解决首先，对碎纸片图像进行预处理。由于基于文字的数字图像中文字和背景的灰度值存在明显差异，运用程序把已整理好的数字图像依次导入matlab软件，根据图像显示技术，提取其灰度矩阵，改变数字图像的视觉效果，将数字图像转化成一种更适合于计算机进行分析处理的数据形式。再者，本文涉及的是无重叠的规则碎纸片拼接，因此只需处理每一张碎纸片的边缘交界处的数据，应用matlab程序对灰度矩阵进行边界数据的提取，减少了数据的处理量，为碎纸片的自动拼接节省了时间。然后，对所提取的每组数据进行相似性度量，采用二维欧式距离，即：dai,bj=t=0m-1bti-atj2 ，其中i，j=0,n-1。根据遗传算法，将提取的所有待拼接碎纸片的边界数据进行分别左右、上下交叉的两两匹配，根据最大相似性原则，建立匹配准则：p=0in-10jm-1mind(ai,bj)所得p值对应的i ,j值即为拼接序列。5.1 问题一我们依据图像预处理理论，通过matlab程序处理图像，将图像转化成适合于计算机处理的数字图像，并对数字图像进行灰度分析，提取灰度矩阵。对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵A1，提取每个灰度矩阵的最后一列，生成新矩阵B1。建立碎纸片匹配模型:dai,bj=t=0m-1bti-atj2 ，其中i，j=0,n-1。p=0in-10jm-1mind(ai,bj)将矩阵A1中的任一列与矩阵B1中的每一列带入模型，所得p值对应的i ,j值，即为所拼接的碎片序列号。将程序进行循环操作，得到最终的碎片自动拼接结果。附件1的碎纸片复原结果为：表-1008014012015003010002016001004005009013018011007017000006附件2的碎纸片复原结果为：表-20030060020070150180110000050010090130100080120140170160045.2 问题二 根据图像预处理理论，首先将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列，生成新矩阵A2，提取最后一列，结合生成新矩阵B2；提取所有灰度矩阵的第一行，作为新生成的矩阵C2，提取最后一行，作为新矩阵D2。由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型：dai,bj=t=0m-1btj-ati2 ，其中i，j=0,n-1。dci,dj=s=0n-1dsj-asi2 ，其中i，j=0,m-1。p=0in-10jm-1mind(ai,bj)，q=0in-10jm-1mind(ci,dj)将矩阵A2中的任一列分别与矩阵B2中每一列代入模型，所得p值对应的i ,j值即为横排序；将矩阵C2中的任一行分别于矩阵D2中的任一行代入模型，所得q值对应的i ,j值即为列排序。循环进行此程序，得计算机的最终运行结果。所得结果有少许误差，需人工调制，更正排列顺序，得最终拼接结果。附件3的碎纸片复原结果为：表-3049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108117004101113194119123附件4的碎纸片复原结果为：表-41910750111541901840021041800641060041490322040650390671472011481701961980941131640781030910801010261000060170281460860511070290401581860980241171500050590580920300370461270191940931410881211261051551141761821510220572020711650821591390011290631381530530381231201750850501601870972030310200411081161360730362071350150760431990451730791611791432080210070490611190331421680621690541921331181891621971120700840600140681741371950080471721560960230991220901851091321810950691671631661881111442060031300340131100250271781710420662050101570741450831340550180560350160091831520440810771282001310521251401930870890480720121771240001021155.3问题三针对双面打印文件的碎纸片拼接处理，首先要对碎纸片两面的图像信息都进行图像预处理，运用matlab程序提取图像的灰度矩阵。基于碎纸机绞碎的碎纸片，每个碎纸片的大小是一样的,采用差距度量法。取矩阵中特征值从第一行中开始到限制条件取i行，限制条件是当取到i行时满足每行都是特征值的矩阵还有2m个矩阵，则这2m个矩阵为同一行碎片所产生的矩阵。包括正反面碎纸片。然后取其中矩阵左边列向量满足，此行矩阵所剩两个矩阵，此过程虽然误差较小，针对其他问题可能要产生误差，需要人工干预，剔除多余矩阵。然后取出两个中的一个矩阵，与产生的这一行矩阵进行匹配，获取一行排序较优的碎片链接。运用嵌套循环实现每行的排序连接。附件5的碎纸片复原结果为：正面结果：表-5136a047b020b164a081a189a029b018a108b066b110b174a183a150b155b140b125b111a078a005b152b147b060a059b014b079b144b120a022b124a192b025a044b178b076a036b010a089b143a200a086a187a131a056a138b045b137a061a094a098b121b038b030b042a084a153b186a083b039a097b175b072a093b132a087b198a181a034b156b206a173a194a169a161b011a199a090b203a162a002b139a070a041b170a151a001a166a115a065a191b037a180b149a107b088a013b024b057b142b208b064a102a017a012b028a154a197b158b058b207b116a179a184a114b035b159b073a193a163b130b021a202b053a177a016a019a092a190a050b201b031b171a146b172b122b182a040b127b188b068a008a117a167b075a063a067b046b168b157b128b195b165a105b204a141b135a027b080a000a185b176b126a074a032b069b004b077b148a085a007a003a009a145b082a205b015a101b118a129a062b052b071a033a119b160a095b051a048b133b023a054a196a112b103b055a100a106a091b049a026a113b134b104b066b123b109b096a043b099b反面结果：表-6078b111b125a140a155a150a183b174b110a066a108a018b029a189b081b164b020a047a136b089a010b036a076b178a044a025b192a124b022a120b144a079a014a059a060b147a152a005a186b153a084b042b030a038a121a098a094b061b137b045a138a056b131b187b086b200b143b199b011b161a169b194b173b206b156a034a181b198b087a132b093a072b175a097a039b083a088b107a149b180a037b191a065b115b166b001b151b170b041a070b139b002a162b203b090a114a184b179b116b207a058a158a197a154b028b012a017b102b064b208a142a057a024a013a146a171b031a201a050a190b092b019b016b177b053b202a021b130a163a193b073b159a035a165b195a128a157a168a046a067a063b075b167a117b008b068b188a127a040a182b122a172a003b007b085b148b077a004a069a032a074b126b076a185a0006080b027a135b141a204b105a023b133a048a051b095a160b119a033b071b052a062a129b118b101a015b205a082b145a009b099a043a096b109a123a006a104a134a113a026b049b091a106b100b055b103a112a196b054b六、模型检验与推广碎纸片自动拼接是计算机视觉和模式识别的一个基本问题，图形预处理和碎片匹配是其中的关键技术。虽然我们本次实验的仿真所涉及的碎纸片的数量及种类不多，但是它充分表明了所进行的碎纸片自动拼接复原技术研究的可行性。目前，系统还在进一步完善阶段，主要有一下几个问题：1）边缘灰度值的精确提取从实验分析可看出，边缘灰度值的精度对减少匹配的计算量和提高匹配的准确性都非常重要。它在很大程度上决定了纸片匹配的排序问题，有时甚至会导致某些匹配的失败。2）数据库的开发管理在实际应用中，由于设备等条件的限制，一次的处理往往不能解决全部的拼接问题。因此，必须开发合理的数据库，以充分利用每一次的拼接结果。3）程序优化虽然在进行简单的拼接复原工作时，该系统可以满足要求。但是在实际的应用中，通常会涉及对大量不规则纸片或彩色碎片数据进行管理和处理工作。因此，必须继续优化程序结构，提高程序的交互能力，真正实现快速有效的计算机辅助碎纸片自动拼接复原。本文基于计算机辅助对碎纸机绞碎的碎纸片实现自动快速拼接，从图形显示技术中提取图形的灰度信息，并提出欧氏距离的配准方法，对图像中的误匹配点产生极大的抑制，求解的变换矩阵精度得到提高，大大缩短了匹配时间，在现实应用中具有重要意义，类似的研究可广泛应用到文物碎片的自动修复、司法物证修复、计算机辅助设计等领域。七、参考文献1 Wolfson H，Kalvin A，Schonberg E，Lambdan Y，Solving jigsaw puzzles by computer，Annales of Operation Research，1988，12:51-642 Freeman H，Garder L，Apictorial jigsaw puzzles:the computer solution of a problem in pattern recognition ，IEEE Trans.Elec.Comp，1964,13:118-1273 余宏生，金伟其，散字图像拼接方法研究进展口J，红外技术，2009,31（6）：348-3534 杨帆，数字图像处理与分析（第2版），北京：北京航空航天大学出版社，2010.8:205-2085 何晓群，应用多元统计分析，北京：中国统计出版社，2010.6:179-182 6 张文修，梁怡，遗传算法的数学基础，西安：西安交通大学出版社，2000.5:13-337 方贤勇，图像拼接技术研究D，杭州：浙江大学计算机学院，20058 杨翠，图像融合与配准方法研究D，西安：西安电子科技大学，20089 叶耘恺，基于边缘特征的图像配准方法研究D，重庆：重庆大学，200910 苏彦华，数字图像识别技术典型案例，人民邮电出版社，200411 Fischler M, Bolles R, Random sample consensus : A paradigm for model fitting with application to image analysis and automated cartography J, Communications of the ACM, 1981,24(6):381-395附录：附件1的复原图片：附件2的复原图片：附件3的复原图片：附件4的复原图片：附件5的复原图片：正面：反面：源程序如下：cd (C:Users127Desktop附件1); files=dir(*.bmp);for i=1:19 s(:,:,i)=imread(files(i).name);end;%将所有碎片导入一个三维数组for j=1:19n=0;for i=1:1980if s(i,1,j)=255n=n+1;end;end;if n=1980disp(j);%找出最左边的碎片break;end;end;Figure 1clear allclccell1=imread(000.bmp); cell2=imread(001.bmp); cell3=imread(002.bmp); cell4=imread(003.bmp); cell5=imread(004.bmp); cell6=imread(005.bmp); cell7=imread(006.bmp); cell8=imread(007.bmp); cell9=imread(008.bmp); cell10=imread(009.bmp); cell11=imread(010.bmp); cell12=imread(011.bmp); cell13=imread(012.bmp); cell14=imread(013.bmp); cell15=imread(014.bmp); cell16=imread(015.bmp); cell17=imread(016.bmp); cell18=imread(017.bmp); cell19=imread(018.bmp); for i=1:19 cell2i=im2bw(celli,0.5); end t=8 for x=1:18 x=sum(sqrt(cell2t(:,72)-cell2i(:,1).*(cell2t(:,72)-cell2i(:,1);j=1; for i=1:19 if i=t continue; end x1=sum(sqrt(cell2t(:,72)-cell2i(:,1).*(cell2t(:,72)-cell2i(:,1); if x1<x x=x1; j=i; end end j t=j; end结果t = 8j = 18j = 1j = 7j = 9j = 15j = 13j = 16j = 4j = 11j = 3j = 17j = 2j = 5j = 6j = 10j = 14j = 1j = 7figure2IV1=imread(008.bmp);IV2=imread(014.bmp);IV3=imread(012.bmp);IV4=imread(015.bmp);IV5=imread(003.bmp);IV6=imread(010.bmp);IV7=imread(002.bmp);IV8=imread(016.bmp);IV9=imread(001.bmp);IV10=imread(004.bmp);IV11=imread(005.bmp);IV12=imread(009.bmp);IV13=imread(013.bmp);IV14=imread(018.bmp);IV15=imread(011.bmp);IV16=imread(007.bmp);IV17=imread(017.bmp);IV18=imread(000.bmp);IV19=imread(006.bmp);PicData=IV1,IV2,IV3,IV4,IV5,IV6,IV7,IV8,IV9,IV10,IV11,IV12,IV13,IV14,IV15,IV16,IV17,IV18,IV19;imshow(PicData);附件2figure1clear allclccell1=imread(000.bmp); cell2=imread(001.bmp); cell3=imread(002.bmp); cell4=imread(003.bmp); cell5=imread(004.bmp); cell6=imread(005.bmp); cell7=imread(006.bmp); cell8=imread(007.bmp); cell9=imread(008.bmp); cell10=imread(009.bmp); cell11=imread(010.bmp); cell12=imread(011.bmp); cell13=imread(012.bmp); cell14=imread(013.bmp); cell15=imread(014.bmp); cell16=imread(015.bmp); cell17=imread(016.bmp); cell18=imread(017.bmp); cell19=imread(018.bmp); for i=1:19 cell2i=im2bw(celli,0.5); end t=7for x=1:18 x=sum(abs(cell2t(:,72)-cell21(:,1); j=1; for i=1:19 if i=t continue; end x1=sum(abs(cell2t(:,72)-cell2i(:,1); if x1<x x=x1; j=i; end end j t=j; endFigure2IV1=imread(003.bmp);IV2=imread(006.bmp);IV3=imread(002.bmp);IV4=imread(007.bmp);IV5=imread(015.bmp);IV6=imread(018.bmp);IV7=imread(011.bmp);IV8=imread(000.bmp);IV9=imread(005.bmp);IV10=imread(001.bmp);IV11=imread(009.bmp);IV12=imread(013.bmp);IV13=imread(010.bmp);IV14=imread(008.bmp);IV15=imread