年数学建模b题

1、碎纸片的拼接复原【摘要】：碎纸片拼接技术是数字图像处理领域的一个重要研究方向，把计算机视觉 和程序识别应用于碎纸片的复原，在考古、司法、古生物学等方面具有广泛的应用，具有 重要的现实意义。本文主要结合各种实际应用背景，针对碎纸机绞碎的碎纸片，基于计算 机辅助对碎纸片进行自动拼接复原研究。针对问题1,依据图像预处理理论，通过 matlab程序处理图像，将图像转化成适合于 计算机处理的数字图像，进行灰度分析，提取灰度矩阵。对于仅纵切的碎纸片，根据矩阵 的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵 Ai,提取每个灰度矩阵的最后 一列，生成新矩阵Bi。建立碎纸片匹配模型：?-1G i 2d(?

2、 = VE (?- ?)，其中 i, j = 0,?n- 1?=0P= 0w?1?闻?)0< ?< ?-1将矩阵Ai中的任一列与矩阵B1中的每一列带入模型，所彳4 P值对应的i ,j值，即为所拼 接的碎片序列号。将程序进行循环操作，得到最终的碎片自动拼接结果。针对问题2,首先将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又横切的碎 纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列和最后一列，分别生成 新矩阵A2、B2；提取所有灰度矩阵的第一行和最后一行，分别作为新生成的矩阵C2、D2。由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎 纸片排

3、序。在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型：?-12d(? = VE (?- ?)，其中 i, j = 0,?n- 1?=0?-1，其中 i, j= 0,?m- 1。d(? = VS (?- ?%)?=0P= 0V?(?,0v ?v ?-1q = 0v ?"(?)0v ?v ?-1将矩阵A2中的任一列分别与矩阵B2中每一列代入模型，所彳4 P值对应的i ,j值即为横排 序；将矩阵C2中的任一行分别于矩阵D2中的任一行代入模型，所得q值对应的i ,j值即为 列排序。循环进行此程序，得计算机的最终运行结果。所得结果有少许误差，需人工调制， 更正排列顺序，得最终拼接

4、结果。针对问题3,基于碎纸片的文字行列特征，采用遗传算法，将所有的可能性拼接进行 比较，进行择优性选择。反面的排序结果用于对正面排序的检验， 发现结果有误差，此时， 进行人工干预，调换碎纸片的排序。【关键词】：灰度矩阵欧式距离图像匹配自动拼接人工干预一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，大量的纸质物证复原工作都是以人工的方式完成的，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接不但耗费大量的人力、物力，而且还可能对物证造成一定的损坏。 随着计算机技术的发展， 人们试图把计算机视觉和模式识别应用于碎纸片复原，开展对碎纸片自动

5、拼接技术的研究，以提高拼接复原效率。试讨论一下问题，并根据题目要求建立相应的模型和算法：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切) ，建立碎纸片拼接复原模型和算法，并针对附件 1、附件 2 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打

6、印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。 附件 5 给出的是一页英文印刷文字双面打印文件的碎片数据。 请尝试设计相应的碎纸片拼接复原模型与算法， 并就附件 5 的碎片数据给出拼接复原结果，结果表达要求同上。结果表达格式说明：复原图片放入附录中，表格表达格式如下：(1)附件1、附件2的结果：将碎片序号按复原后顺序填入1X19的表格；(2)附件3、附件4的结果：将碎片序号按复原后顺序填入11X19的表格；(3)附件5的结果：将碎片序号按复原后顺序填入两个11 X 19的表格；4. ) 不能确定复原位置的碎片，可不填入上述表格，单独列表。二、问题分析碎纸片自动拼接技

7、术是图像处理与识别领域中的一个较新但很典型的应用，是通过扫描和图像提取技术获取一组碎纸片的信息，然后利用计算机进行相应的处理，从而实现对这些碎纸片的全自动或半自动的拼接复原。碎纸片的自动拼接可以近似地看作是一个拼图问题。在机器人和计算机视觉领域中，很早就有学者对自动拼图进行了研究1 ， 2 。但是这些技术都利用了拼图游戏中的一些特殊特征及一些先验知识， 而在许多实际应用中都不能满足这些条件。根据待拼接图像(输入)与拼接图像(输出)的不同类型3 ，可以将图像拼接分为四类：基于静态图像的静态图像拼接、基于静态图像的动态图像拼接、基于视频的序列的静态图像拼接和基于视频序列的动态图像拼接。 本文主要致

8、力于静态图像的静态图像拼接，即碎纸机绞碎的规则的碎纸片的自动拼接。问题 1：根据图像预处理理论，通过程序语言将图像导入 matlab 程序，对图像进行预处理，将碎纸片转换成适合于计算机处理的数字图像形式， 并对数字图像进行灰度分析， 提取灰度矩阵。对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵A,提取每个灰度矩阵的最后一列，作为新矩阵B。建立碎纸片匹配模型。根据遗传算法的思想， 将矩阵 A 中的任一行与矩阵B 中的每一行带入模型， 由最大相似性原理得 s 值对应的 i ,j 值， 即为所拼接的碎片序列号。 将程序进行循环操作， 并最终建立对输入的解释。问题 2

9、：首先对碎纸片图像进行预处理，通过matlab 程序将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列，生成新矩阵A2,提取最后一列，结合生成新矩阵B2；提取所有灰度矩阵的第一 行，作为新生成的矩阵C2,提取最后一行，作为新矩阵D2。由于纸质文件边缘空白处的灰 度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。在此基础上，采用 从局部到整体，从左到右的方法，建立匹配筛选模型。将矩阵A2中的任一列分别与矩阵B2 中每一列代入模型，所彳4 P值对应的i ,j值即为横排序；将矩阵C2中的任一行分别于矩阵D2 中的任一行代入

10、模型，所彳4q值对应的i值即为列排序。循环进行此程序，得计算机的最 终运行结果。所得结果有少许误差，需人工调制，更正排列顺序，得最终拼接结果。问题3:针对双面打印文件的碎纸片拼接处理，首先要对碎纸片两面的图像信息都进行图像预 处理，运用matlab程序提取图像的灰度矩阵。基于碎纸机绞碎的碎纸片，每个碎纸片的 大小是一样的，采用差距度量法。取矩阵中特征值从第一行中开始到限制条件取i行，限制条件是当取到i行时满足每行都是特征值的矩阵还有 2m个矩阵，则这2m个矩阵为同一 行碎片所产生的矩阵。包括正反面碎纸片。然后取其中矩阵左边列向量满足，此行矩阵所 剩两个矩阵，此过程虽然误差较小，针对其他问题可能

11、要产生误差，需要人工干预，剔除 多余矩阵。然后取出两个中的一个矩阵，与产生的这一行矩阵进行匹配，获取一行排序较 优的碎片链接。运用嵌套循环实现每行的排序连接。三、符号说明m提取灰度矩阵行（列）生成的新矩阵的行数n提取灰度矩阵行（列）生成的新矩阵的列数A提取灰度矩阵第一列生成的新矩阵B提取灰度矩阵最舟-列生成的新矩阵C提取灰度矩阵第一行生成的新矩阵D提取灰度矩阵最舟-行生成的新矩阵d(?2?矩阵A中第i列与矩阵B中第j列的欧氏距离d(?矩阵C中第i行与矩阵D中第j行的欧氏距离四、模型假设1）同一切线处的两条边界灰度值的差别在误差范围之内。2）所有的待拼接的碎纸片都是规则的。3）假设不存在文件缺失

12、、人为因素等意外因素。4）假设所有的数字图像文件都是已整理好的，不需要再进行旋转、剪裁等操作。五、模型建立与问题解决首先，对碎纸片图像进行预处理。由于基于文字的数字图像中文字和背景的灰度值存 在明显差异，运用程序把已整理好的数字图像依次导入 matlab软件，根据图像显示技术, 提取其灰度矩阵，改变数字图像的视觉效果，将数字图像转化成一种更适合于计算机进行 分析处理的数据形式。再者，本文涉及的是无重叠的规则碎纸片拼接，因此只需处理每一 张碎纸片的边缘交界处的数据，应用 matlab程序对灰度矩阵进行边界数据的提取，减少 了数据的处理量，为碎纸片的自动拼接节省了时间。然后，对所提取的每组数据进行

13、相似 性度量，采用二维欧式距离，即：?-1d(?a? = VE (?- ?)2 ，其中 i, j = 0,?n- 1?=0根据遗传算法，将提取的所有待拼接碎纸片的边界数据进行分别左右、上下交叉的两两匹配，根据最大相似性原则，建立匹配准则：p= 0V?物（?溜0V ? V ?-1所彳导p值对应的i ,j值即为拼接序列。5.1问题一我们依据图像预处理理论，通过 matlab程序处理图像，将图像转化成适合于计算机 处理的数字图像，并对数字图像进行灰度分析，提取灰度矩阵。对于仅纵切的碎纸片，根 据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵Ai,提取每个灰度矩阵的最后一列，生成新矩阵Bi。

14、建立碎纸片匹配模型：?-iG i 2d(? = VE (?- ?)，其中 i, j = 0,?n- 1?=0P= 0v?物（?溜0v ? v ?-1将矩阵Ai中的任一列与矩阵Bi中的每一列带入模型，所彳4 P值对应的i ,j值，即为所拼 接的碎片序列号。将程序进行循环操作，得到最终的碎片自动拼接结果。附件i的碎纸片复原结果为：表-i0080i40i20i50030i00020i600i0040050090i30i80ii0070i7000006附件2的碎纸片复原结果为：表-20030060020070i50i80ii00000500i009 0i30i0 0080i20i4 0i70i6 00

15、45.2问题二根据图像预处理理论，首先将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又 横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列，生成新矩阵 A2,提取最后一列，结合生成新矩阵B2；提取所有灰度矩阵的第一行，作为新生成的矩阵 C2,提取最后一行，作为新矩阵D2。由于纸质文件边缘空白处的灰度值为常量，通过对灰 度矩阵的检验提取，确定最左列的碎纸片排序。在此基础上，采用从局部到整体，从左到 右的方法，建立匹配筛选模型：?-iii 2d(? = VE (?- ?)，其中 i, j = 0,?n- i?=0?-i/ce sc 2d(? = VE (?- ?),其中 i, j

16、= 0,?m- i?=0P= ov?；?(?, q= ov?电(?羽?) 0v?v?-i0v?v?-i将矩阵A2中的任一列分别与矩阵B2中每一列代入模型，所彳4 P值对应的i ,j值即为横排 序；将矩阵C2中的任一行分别于矩阵D2中的任一行代入模型，所得q值对应的i ,j值即为 列排序。循环进行此程序，得计算机的最终运行结果。所得结果有少许误差，需人工调制， 更正排列顺序，得最终拼接结果。附件3的碎纸片复原结果为：表-3049054065143186002057192178118190095011022129028091188141061019：078067069：09916209613107

17、9:063116163r 072006177020052036168100076062142030041023147191050179120086195026 0010870180381480461610240350811891221031301930881670250080091050740711561 083132200。170800332021981 0151331701 205085152165027060014128003159082199135012073160203169134039031051107115176094034084183090：047121042124144:07

18、7112149r 097136164127058043125013182109197：016184110187066106150021I173157181204139145029064111201005092180048037075055044206010104098172171059007208：138158126068175045174000：1370530561093153070166032196089146102154114040151207155140185108117004101113194119123附件4的碎纸片复原结果为:表-4191075011154190184002104

19、180064106004149032204065 0390671472011481701961981094113164078103:091080101r 026100006 017028146086051107029040158186098024117150005059058092030037046127019194093141088121126105155114176182151022057202:0711650821591391 0011290631 1381530530381231 1201750851 050160187097203031020041108116136073036207

20、13501507604319904517307916117914320802110070490611119033142168062r 169054192r 1331181891621971120700840600140681 174137195008047172156096I 02309912210901851091321810950691671631661881111442060031300340131100250271781710421066205010P157074145083134r 055018056r 0350160091831520440810771282001310521251

21、401930870890480720121771240001021155.3问题三针对双面打印文件的碎纸片拼接处理，首先要对碎纸片两面的图像信息都进行图像预 处理，运用matlab程序提取图像的灰度矩阵。基于碎纸机绞碎的碎纸片，每个碎纸片的 大小是一样的，采用差距度量法。取矩阵中特征值从第一行中开始到限制条件取i行，限制条件是当取到i行时满足每行都是特征值的矩阵还有 2m个矩阵，则这2m个矩阵为同一 行碎片所产生的矩阵。包括正反面碎纸片。然后取其中矩阵左边列向量满足，此行矩阵所 剩两个矩阵，此过程虽然误差较小，针对其他问题可能要产生误差，需要人工干预，剔除 多余矩阵。然后取出两个中的一个矩阵，

22、与产生的这一行矩阵进行匹配，获取一行排序较 优的碎片链接。运用嵌套循环实现每行的排序连接。附件5的碎纸片复原结果为：正面结果：表-5136a047b020b164a081a189ao29b018a108b066b110b174a183a150b155)b140b125ib1a078a005b152b147b060a059b014b079b144b120a022b124a192 b025a044b178)b076a036ib01()a089b143a200a086a187a131a056a138b045b137a061a094a098 b121b038b030b042a084a153；b18&#

23、163;a083b039a097b175b072a093b132a087b198a181S034b156 b206a173a194Ia169a161b011a199a090b203a162S002b139a070a041b170a151a001a166a115a065a191b037'a180b149)a107'b088a013b024b057b142b208b064a102a017a012b028a154a197 b158b058b207'b116a179)a184a114b035b159b073a193a163b130 b021a202b053a177S016a01

24、Sa092a190a050b201b031b171a146b172b122b182S040b127b188b068a008a117a167b075a063a067b046b168；b157b128；b195ib165105b204a141b135a027b080a00Ca185b176b126S074a032b069b004b077b148a085is007'a003009a145b082a205b015a101b118a129a062b052b071a033a119b160a095ib051a048ib13-；b023054a196a112b103b055a100a106a091b0

25、49a026a113b134b104b066b123；b109b096M43；b099反面结果：表-6078b111b125a140a155a150a183b174b110a066a108a018b029a189b081b164b020)0047a136089a010b036S076b178S044a025b192a124b022a120b144S079a014S059a060b147'a152Ia005186b153a084b042b030S038a121a098S094b061b137b045a138a056b131b187b086it20()b143199b011b161a169

26、b194b173b206b156S034a181b198b087a132b093a072b175a097'S039Ib083088b107a149b180a037b191a065b115b166b001b151b170b041a070b139b002a162!b20-；b09(114a184b179b116b207S058a158a197a154b028b012a017b102b064b208a142a057'S024a013146a171b031s201a050a190b092b019b016b177b053b202S021b130a163a193b073；b159)a035

27、165b195a128a157a168S046a067a063b075b167a117b008b068b188a127a040a182!b122Ia17：003b007b085b148b077S004a069a032S074b126b076027a135b141a204b105023b133a048S051b095a160b119a033b071b052a062a129b118b101S015b205a082!b145ia009099弓43a096b109a123S006a104a134a113a026b049b091a106b100b055b103a112!a196

28、ib054六、模型检验与推广碎纸片自动拼接是计算机视觉和模式识别的一个基本问题，图形预处理和碎片匹配是 其中的关键技术。虽然我们本次实验的仿真所涉及的碎纸片的数量及种类不多，但是它充分表明了所进行的碎纸片自动拼接复原技术研究的可行性。目前，系统还在进一步完善阶段，主要有一下几个问题：1）边缘灰度值的精确提取从实验分析可看出，边缘灰度值的精度对减少匹配的计算量和提高匹配的准确性都非 常重要。它在很大程度上决定了纸片匹配的排序问题，有时甚至会导致某些匹配的失败。2）数据库的开发管理在实际应用中，由于设备等条件的限制，一次的处理往往不能解决全部的拼接问题。因此，必须开发合理的数据库，以充分利用每一次

29、的拼接结果。3）程序优化虽然在进行简单的拼接复原工作时，该系统可以满足要求。但是在实际的应用中，通常会涉及对大量不规则纸片或彩色碎片数据进行管理和处理工作。因此，必须继续优化程序结构，提高程序的交互能力，真正实现快速有效的计算机辅助碎纸片自动拼接复原。本文基于计算机辅助对碎纸机绞碎的碎纸片实现自动快速拼接，从图形显示技术中提 取图形的灰度信息，并提出欧氏距离的配准方法，对图像中的误匹配点产生极大的抑制， 求解的变换矩阵精度得到提高，大大缩短了匹配时间，在现实应用中具有重要意义，类似 的研究可广泛应用到文物碎片的自动修复、司法物证修复、计算机辅助设计等领域。七、参考文献1WolfsonH , K

30、alvinA , SchonbergE, LambdanY Solvingjigsawpuzzlesbycomputer , AnnalesofOperationResearch , 1988, 12:51-642FreemanH, GarderL,Apictorialjigsawpuzzles:thecomputersolutionofaprobleminpatternrecognition,IEEE, 1964,13:118-1273 余宏生，金伟其，散字图像拼接方法研究进展口 J ，红外技术， 2009,31 ( 6) ： 348-3534 杨帆，数字图像处理与分析(第 2 版) ，北京

31、：北京航空航天大学出版社，2010.8:205-2085 何晓群，应用多元统计分析，北京：中国统计出版社， 2010.6:179-1826 张文修，梁怡，遗传算法的数学基础，西安：西安交通大学出版社， 2000.5:13-337 方贤勇，图像拼接技术研究D ，杭州：浙江大学计算机学院， 20058 杨翠，图像融合与配准方法研究D ，西安：西安电子科技大学， 20089 叶耘恺，基于边缘特征的图像配准方法研究D ，重庆：重庆大学， 200910 苏彦华，数字图像识别技术典型案例，人民邮电出版社， 200411FischlerM,BollesR,Randomsampleconsensus:Apar

32、adigmformodelfittingwithapplicationtoimageanalysisandautomatedcartographyJ,CommunicationsoftheACM,19 81,24(6):381-395附录：附件 1 的复原图片：附件 2 的复原图片：附件3 的复原图片：附件4 的复原图片：附件 5 的复原图片：正面： 反面： 源程序如下：附件 1');files=dir('*.bmp'); fori=1:19s(:,:,i)=imread(files(i).name);end;%等所有碎片导入一个三维数组forj=1:19 n=0;fo

33、ri=1:1980ifs(i,1,j)=255 n=n+1;end;end;ifn=1980 disp(j);% 找出最左边的碎片 break;end;end;Figure1 clearall clccell1=imread('000.bmp');cell2=imread('001.bmp');cell3=imread('002.bmp');cell4=imread('003.bmp');cell5=imread('004.bmp');cell6=imread('005.bmp');cell7=im

34、read('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(

35、'015.bmp');cell17=imread('016.bmp');cell18=imread('017.bmp');cell19=imread('018.bmp');fori=1:19cell2i=im2bw(celli,0.5);endt=8forx=1:18x=sum(sqrt(cell2t(:,72)-cell2i(:,1).'*(cell2t(:,72)-cell2i(:,1);j=1;fori=1:19ifi=tcontinue;endx1=sum(sqrt(cell2t(:,72)-cell2i(:,1)

36、.'*(cell2t(:,72)-cell2i(:,1) ;ifx1<xx=x1;j=i;endendt=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(

37、'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

38、('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);附件 2figure1clearallclccell1=imread('000.bmp');cell2=imread('001.bm

39、p');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');ce

40、ll12=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');fori=1:19cell2i=im2bw(celli,0.5);endt=7forx=1:18x=sum(abs(cell2t(:,72)-cell21(:,1);