《碎纸片的拼接复原-数学建模b题》由会员分享，可在线阅读，更多相关《碎纸片的拼接复原-数学建模b题（26页珍藏版）》请在金锄头文库上搜索。
1、2013高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛
2、规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 长春工业大学 参赛队员 (打印并签名) ：1. 指导教师或指导教师组负责人 (打印并签名)： 郭明浩 日期： 2013 年 9 月 15 日2013高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评
3、分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：摘 要传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。BMP图像越来越多地被各种应用程序所支持，这种文件格式就是每一个像素用8bit表示，显示出来的图像是黑白效果，最黑的像素的扶度值为“0”，最白的像素的灰度值为“255”，整个图像各个像素的灰度值随机地分布在“0”到“255”的区间中，越黑的像素，其灰度值越接近于“0”，越白(即越亮)的像素，其扶度值越接近于“255”。所以图像由一个矩阵描述出来，该矩阵的结构由图像的高度、宽及每点bit
4、数决定。图像的数字化拼接的实质就是根据每幅图片接口像素的相似性来对每个图片进行拼接。首先我们对多个碎片同时扫描或拍照，得到256级的灰度BMP图像，然后通过MATLAB的图像处理工具箱中的ImMatrix函数对BMP文件进行矩阵数字化，得到每幅图片的像素矩阵图，但是由于数码相机自身和拍照时光线阴暗程度的影响，所得到的数据本身或多或少会存在一定的误差，测得的数据往往会存在误差，所以需要进行数据预处理，而“高斯滤波数据预处理”往往可以使数据变得平滑、排除噪声数据和异常数据、压缩和归并冗余数据、遗失点补齐、数据分块保持原数据的形貌等，然后将处理完的数据运用c语言编程的算法来进行图片的拼接，如果多个图
5、片的断面处刚好处在空白的时候，其接口的像素矩阵会完全相同，这时会出现误配的情况，所以在这种情况下我们必须在拼接的过程中加入人工干预。这种半自动拼接方法综合利用了计算机高速计算能力以及人的文字图像识别和理解能力，拼接效率比纯人工高，拼接准确性也好于纯计算机拼接法。我们利用图像的图像矩阵数字化处理思想，根据已有的附件资料，将碎纸片的拼接问题转化成了像素矩阵相似的问题，并给出了矩阵相似度对比依据和算法，并且进行了实验，证明了图像的数字化拼接的合理性和可行性。关键词：图像的数字化拼接；矩阵的相似度；ImMatrix函数；人工干预；像素矩阵；B题 碎纸片的拼接复原一：问题重述破碎文件的拼接在司法物证复原
6、、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型
7、和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二问题分析对于本题目类边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否匹配，然
8、而由于理论和技术的限制，让计算机具备类似人那种识别碎片边缘的字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。现在利用MATLAB和相应的图像处理工具，完全可以获取碎片文字图像所在接口特征信息转化为图片上的像素矩阵数字特征，拼接碎片时如利用这些信息进行拼接，其拼接效率无疑比单纯利用边界几何特征方法要好些。由于大多数文字文字行方向和表格线方向平行，如果碎片内的文字碎片边缘断裂，那么与它相邻的碎纸片在边缘处的像素矩阵一定有高度的相似度，凭此特征可以很容易地从形状相似的多碎片中挑选出相邻碎片。因文字间的像素数字矩阵相似度的识别比字迹断线识别和文字图像的理解实现起来要容易得多，利用碎片内文字像素
9、数字矩阵特征拼接形状相似的碎纸片理论上是可行的。另一方面由于计算机数字分析图像能力的缺陷，让计算机对碎片进行完全意义上的自动化拼接也几乎不太可能，为保证拼接的准确性，需要在拼接过程中加入人工干扰过程。一般而言拼接碎片时先利用计算机搜索与目标碎片匹配的未拼接碎片，并根据匹配程度按顺序显示待选碎片，操作员再根据人脑进一步分析结果舍弃或拼接待选碎片。对于图像的数字化拼接的合理性可通过对题目所给附件的数据处理，并用MATLAB进行算法的编程，对附件来进行图片拼接训练，来验证其合理性。三模型假设（1）设图像的像素足够大；（2）碎纸片边缘整齐、平滑；（3）碎纸片的文字的方向是可识别和确定的；（4）附件提供
10、的图片边缘像素与实际碎纸片无差异；（5）碎纸片中的文字高度、大小、间距保持一致；（6）附件中的碎纸片都来源于同一张纸；四符号说明：图片数字化处理后得到的左边缘矩阵：图片数字化处理后得到的右边缘矩阵：图片数字化处理后得到的上边缘矩阵：图片数字化处理后得到的下边缘矩阵其中 五模型的建立与求解5.1 问题1的模型建立与求解5.1.1数据的获取通过对问题一的题设和对附件一和附件二的图片进行分析和编号后，可使用MATLAB调用ImMatrix函数或者使用图像工具箱里的Image Tool对各个BMP图片文件进行矩阵数字化，得到19组矩阵图。如图一就是附件一图片000进行数字化处理后的结果。图一：图片00
11、0数字化处理结果图当对图一局部进行放大我们就会看到如图二的结果：图图二：图一局部放大结果图MATLAB调用的ImMatrix函数和图像工具箱里的Image Tool会将图片数字化，从图中可看出最黑的像素的扶度值为“0”，最白的像素的灰度值为“255”，整个图像各个像素的灰度值随机地分布在“0”到“255”的区间中，越黑的像素，其灰度值越接近于“0”，越白(即越亮)的像素，其扶度值越接近于“255”。所以附件一和二的图片都可以用矩阵的形式描述了出来。每个图片的矩阵第一列和最后一列相当于每个图片切口边缘处，所以矩阵的边缘处对碎纸片的拼接起着重要的作用，但是由于外界的各种因素的干扰和测量仪器本身因素
12、影响的存在，边缘的扶度值字样中会存在各种误差，对这些数据进行取样研究之前首先要对数据进行预处理。5.1.2数据的预处理噪音的处理：由采样点所建立的计算机模型把它叫做数字样件。对提取的数字样件进行滤波主要有两个目的：（1）去除毛刺和噪音。由于受各种因素的影响，物理的因素(小的碎片的丢失，磨损、边缘的腐蚀以及表面的不规则)，仪器的因素(视觉、阴影、图像的量化)，这样在数字样件中会存在各种误差(如数据、噪音数据等)，如不消除，这些误差数据将会直接影响重建模型的质量，从而影响匹配，因此在模型重建之前，就要对数字进行滤波等处理。数据的简化和数据的光顺是数据预处理的两个重要组成部分。数字化样件中包含各种不
13、理想的数据。对错误的数据，可用交互处理的方法迸行去除；对于误差数据，大体可分为毛刺数据和噪音两种。对于毛刺数据，可以直接删除；将这点移到一个中值点；在允许的误差范围内，将其沿某一方向移动一段距离。（2）简化模型。滤波可以简化模型的复杂程度，减少工作量，提高匹配的运算速度。现有针对数据点的滤波方法有很多本文实现的有序数据的滤波与数据的组织形式无关，其基础是k，邻近的建立。滤波后的数据点的新点可用矢量表示为： （1）其中为所调整的距离向量，为调整的步长参数。待过滤波的数据点作切线，则-邻近点集中的数据点到此切线的有向距离为。通过对有向距离的滤波，可实现数据点的滤波。滤波器的阶数据可取不大于的整数。
14、平均滤波：平均滤波也叫均值滤波，是一种简单的的线性滤波。一次滤波后数据点的法矢取为点集的数据点法矢的平均值；相应的，式中的有向距离向量可取为： （2）在实际计算是采用取均值的方法进行化简。值得注意的是：当的取值很大时，均值滤波会使数据趋于平坦，丢失匹配信息，可以通过调整的取值，在细节保留与滤波效果之间达到平衡，能较好地消除噪声数据的影响，同时它的滤波阶数也为重新采样提供了统一的步长。二值化处理：设定一个全局的阈值T，用T将图像的数据分成两部分：大于T的像素群和小于T的像素群。将大于T的像素群的像素值设定为白色（像素为255），小于T的像素群的像素值设定为黑色（像素为零）。5.1.3问题一的求解由于外界环境和测量仪器自身的误差的影响，仅仅取一列边缘的数字矩阵是不够的，数据经过去噪音和二值化处理后，我们取每幅图片相邻的两列边缘矩阵并相互进行对比，根据这两列的边缘矩阵数字的相似性进行匹配和相应的c语言算法（C+程序一）计算，发现附件一的图片004的右边矩阵边缘数字与图片005左边边缘、010右边边缘和002左边和附件二的015右边和003左边的矩阵相识度最大。如图三：
