2013年数学建模b题

精心整理精心整理碎纸片的拼接复原【摘要】：碎纸片拼接技术是数字图像处理领域的一个重要研究方向，把计算机视觉和程序识别应用于碎纸片的复原，在考古、司法、古生物学等方面具有广泛的应用，具有重要的现实意义。本文主要结合各种实际应用背景，针对碎纸机绞碎的碎纸片，基于计算机辅助对碎纸片进行自动拼接复原研究。针对问题1，依据图像预处理理论，通过matlab程序处理图像，将图像转化成适合于计算机处理的数字图像，进行灰度分析，提取灰度矩阵。对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵，提取每个灰度矩阵的最后一列，生成新矩阵。建立碎纸片匹配模型:将矩阵中的任一列与矩阵中的每一列带入模型，所得p值对应的值，即为所拼接的碎片序列号。将程序进行循环操作，得到最终的碎片自动拼接结果。针对问题2，首先将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列和最后一列，分别生成新矩阵、；提取所有灰度矩阵的第一行和最后一行，分别作为新生成的矩阵、。由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型：，将矩阵中的任一列分别与矩阵中每一列代入模型，所得p值对应的值即为横排序；将矩阵中的任一行分别于矩阵中的任一行代入模型，所得q值对应的值即为列排序。循环进行此程序，得计算机的最终运行结果。所得结果有少许误差，需人工调制，更正排列顺序，得最终拼接结果。精心整理精心整理针对问题3，基于碎纸片的文字行列特征，采用遗传算法，将所有的可能性拼接进行比较，进行择优性选择。反面的排序结果用于对正面排序的检验，发现结果有误差，此时，进行人工干预，调换碎纸片的排序。【关键词】:灰度矩阵欧式距离图像匹配自动拼接人工干预一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，大量的纸质物证复原工作都是以人工的方式完成的，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接不但耗费大量的人力、物力，而且还可能对物证造成一定的损坏。随着计算机技术的发展，人们试图把计算机视觉和模式识别应用于碎纸片复原，开展对碎纸片自动拼接技术的研究，以提高拼接复原效率。试讨论一下问题，并根据题目要求建立相应的模型和算法：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。结果表达格式说明：复原图片放入附录中，表格表达格式如下：(1)附件1、附件2的结果：将碎片序号按复原后顺序填入1×19的表格；(2)附件3、附件4的结果：将碎片序号按复原后顺序填入11×19的表格；(3)附件5的结果：将碎片序号按复原后顺序填入两个11×19的表格；(4)不能确定复原位置的碎片，可不填入上述表格，单独列表。二、问题分析碎纸片自动拼接技术是图像处理与识别领域中的一个较新但很典型的应用，是通过扫描和图像提取技术获取一组碎纸片的信息，然后利用计算机进行相应的处理，从而实现对这些碎纸片的全自动或半自动的拼接复原。碎纸片的自动拼接可以近似地看作是一个拼图问题。在机器人和计算机视觉领域中，很早就有学者对自动拼图进行了研究[1，2]。但是这些技术都利用了拼图游戏中的一些特殊特征及一些先验知识，而在许多实际应用中都不能满足这些条件。根据待拼接图像（输入）与拼接图像（输出）的不同类型[3]，可以将图像拼接分为四类：基于静态图像的静态图像拼接、基于静态图像的动态图像拼接、基于视频的序列的静态图像拼接和基于视频序列的动态图像拼接。本文主要致力于静态图像的静态图像拼接，即碎纸机绞碎的规则的碎纸片的自动拼接。问题1：根据图像预处理理论，通过程序语言将图像导入matlab程序，对图像进行预处理，将碎纸片转换成适合于计算机处理的数字图像形式，并对数字图像进行灰度分析，提取灰度矩阵。对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵A，提取每个灰度矩阵的最后一列，作为新矩阵B。建立碎纸片匹配模型。根据遗传算法的思想，将矩阵A中的任一行与矩阵B中的每一行带入模型，由最大相似性原理得s值对应的值，即为所拼接的碎片序列号。将程序进行循环操作，并最终建立对输入的解释。精心整理精心整理问题2：首先对碎纸片图像进行预处理，通过matlab程序将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列，生成新矩阵，提取最后一列，结合生成新矩阵；提取所有灰度矩阵的第一行，作为新生成的矩阵，提取最后一行，作为新矩阵。由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型。将矩阵中的任一列分别与矩阵中每一列代入模型，所得p值对应的值即为横排序；将矩阵中的任一行分别于矩阵中的任一行代入模型，所得q值对应的值即为列排序。循环进行此程序，得计算机的最终运行结果。所得结果有少许误差，需人工调制，更正排列顺序，得最终拼接结果。问题3：针对双面打印文件的碎纸片拼接处理，首先要对碎纸片两面的图像信息都进行图像预处理，运用matlab程序提取图像的灰度矩阵。基于碎纸机绞碎的碎纸片，每个碎纸片的大小是一样的,采用差距度量法。取矩阵中特征值从第一行中开始到限制条件取i行，限制条件是当取到i行时满足每行都是特征值的矩阵还有2m个矩阵，则这2m个矩阵为同一行碎片所产生的矩阵。包括正反面碎纸片。然后取其中矩阵左边列向量满足，此行矩阵所剩两个矩阵，此过程虽然误差较小，针对其他问题可能要产生误差，需要人工干预，剔除多余矩阵。然后取出两个中的一个矩阵，与产生的这一行矩阵进行匹配，获取一行排序较优的碎片链接。运用嵌套循环实现每行的排序连接。三、符号说明m提取灰度矩阵行（列）生成的新矩阵的行数n提取灰度矩阵行（列）生成的新矩阵的列数提取灰度矩阵第一列生成的新矩阵B提取灰度矩阵最后一列生成的新矩阵C提取灰度矩阵第一行生成的新矩阵D提取灰度矩阵最后一行生成的新矩阵矩阵A中第列与矩阵B中第列的欧氏距离矩阵C中第行与矩阵D中第行的欧氏距离四、模型假设1）同一切线处的两条边界灰度值的差别在误差范围之内。2）所有的待拼接的碎纸片都是规则的。3）假设不存在文件缺失、人为因素等意外因素。4）假设所有的数字图像文件都是已整理好的，不需要再进行旋转、剪裁等操作。五、模型建立与问题解决首先，对碎纸片图像进行预处理。由于基于文字的数字图像中文字和背景的灰度值存在明显差异，运用程序把已整理好的数字图像依次导入matlab软件，根据图像显示技术，提取其灰度矩阵，精心整理精心整理改变数字图像的视觉效果，将数字图像转化成一种更适合于计算机进行分析处理的数据形式。再者，本文涉及的是无重叠的规则碎纸片拼接，因此只需处理每一张碎纸片的边缘交界处的数据，应用matlab程序对灰度矩阵进行边界数据的提取，减少了数据的处理量，为碎纸片的自动拼接节省了时间。然后，对所提取的每组数据进行相似性度量，采用二维欧式距离，即：根据遗传算法，将提取的所有待拼接碎纸片的边界数据进行分别左右、上下交叉的两两匹配，根据最大相似性原则，建立匹配准则：所得p值对应的值即为拼接序列。5.1问题一我们依据图像预处理理论，通过matlab程序处理图像，将图像转化成适合于计算机处理的数字图像，并对数字图像进行灰度分析，提取灰度矩阵。对于仅纵切的碎纸片，根据矩阵的行提取理论，将每个灰度矩阵的第一列提取，作为新矩阵，提取每个灰度矩阵的最后一列，生成新矩阵。建立碎纸片匹配模型:将矩阵中的任一列与矩阵中的每一列带入模型，所得p值对应的值，即为所拼接的碎片序列号。将程序进行循环操作，得到最终的碎片自动拼接结果。附件1的碎纸片复原结果为：表-1008014012015003010002016001004005009013018011007017000006附件2的碎纸片复原结果为：表-20030060020070150180110000050010090130100080120140170160045.2问题二根据图像预处理理论，首先将图像信息进行灰度分析，提取灰度矩阵。基于既纵切又横切的碎纸片，根据矩阵的行列提取理论，分别提取每个灰度矩阵的第一列，生成新矩阵，提取最后一列，结合生成新矩阵；提取所有灰度矩阵的第一行，作为新生成的矩阵，提取最后一行，作为新矩阵。由于纸质文件边缘空白处的灰度值为常量，通过对灰度矩阵的检验提取，确定最左列的碎纸片排序。在此基础上，采用从局部到整体，从左到右的方法，建立匹配筛选模型：精心整理精心整理，将矩阵中的任一列分别与矩阵中每一列代入模型，所得p值对应的值即为横排序；将矩阵中的任一行分别于矩阵中的任一行代入模型，所得q值对应的值即为列排序。循环进行此程序，得计算机的最终运行结果。所得结果有少许误差，需人工调制，更正排列顺序，得最终拼接结果。附件3的碎纸片复原结果为：表-3049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108117004101113194119123附件4的碎纸片复原结果为：表-41910750111541901840021041800641060041490322040650390671472011481701961980941131640781030910801010261000060170281460860511070290401581860980241171500050590580920300370461270191940931410881211261051551141761821510220572020711650821591390011290631381530530381231201750850501601