2013关于数学建模B题碎纸片拼接技术.docVIP

纸片的拼接复原 摘 要 本文主要结合司法鉴定这一应用背景，对于给定的来自同一页印刷文字的碎纸机破碎纸片，建立模型，并对其进行拼接复原。 针对问题一：首先，拼接碎片前对碎片图像要进行灰度处理。其次，利用Matlab编程获取碎纸片边界特征，进而获取碎纸片内文字行方向、间距等文字行特征。再次，利用最小二乘原理对碎纸片边界进行差值处理，同时，对处理后的数据进行了筛选，剔除异常数据，筛选出最小数据。最后，对所筛选出的数据进行人工干预。 针对问题二：对于碎纸机既纵切又横切的情形，碎片内文字图像的个数是获取文字行方向的关键。首先，对碎纸片进行预处理，即对物体碎片灰度处理，得到碎纸片的数字图像；其次，利用算法进行碎纸片匹配，通过匹配算法找到相互匹配的碎纸片；最后进行碎纸片的拼接复原，将相互匹配的碎纸片拼接在一起，得到最终的结果。 针对问题三：由于该碎片数据是英文印刷文字双面打印文件的碎片数据，故首先对碎纸片进行灰度处理,拼接出复原图的边界，其次进行碎纸片的相互匹配，通过匹配算法找到相互匹配的碎纸片，接着进行拼接复原，最后对异常数据进行整理。 该题的关键是，建立稳定性模型，利用计算机编程，研究碎纸片的拼接复原，这些方法所得出的结果与实际情况较符合，因此我们可以对这些模型的应用作出一定的推广。但是由于数据量比较大，人工干预又占有一定的比重，所以在现实生活中还有一定的局限性。 关键词：拼接还原 灰度处理 筛选 匹配算法 人工干预 最小二乘法 一、问题重述 1.1问题背景 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。 1.2问题提出 请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 二、模型假设 1、碎纸机切割图片是垂直的。 2、碎纸机切割的碎纸片大小相同、质地均匀。 3、所有的碎纸片由同一碎纸机切割。 4、每个附件中所有的碎纸片来自于同一页文字文件。 三、问题分析 3.1问题一的分析 问题一的关键在于建立碎纸片拼接复原模型以及算法。首先，对于附件1,2中的图片进行灰度处理，破碎图片仅为纵切，故将图片的边界进行差值和处理，匹配度最高的差值和为0，进而可以对所有数据进行筛选，最终得到复原图。 3.2问题二的分析 与问题一相比较，问题二中对碎纸片采取既纵切又横切的切割方式，而且相对于附件1,2，附件3,4的数据量比较大，但总体原理和问题一基本一致，只需在考虑纵切后再进行横切即可。 3.3问题三的分析 与问题一、二相比较，问题三中给出的附件5中图片来源于双面打印文件的碎片数据，并且数据量与上述相比更海量。所以本题首先考虑的是将大量数据导入到计算机中，然后将边界部分筛选出来，剩下的图片按照匹配算法进行进一步拼接，最后对异常数据进行人工干预即可。 四、建模过程 4.1问题一 4.1.1.1附件1建模过程 对附件1中的图片进行灰度处理，再进行差值、求和等运算，从而取出最匹配两张图片，以此循环、比较下去，从而得到匹配的排列顺序。具体Matlab程序见附件一。 4.1.1.2求解过程 c矩阵中第7行元素全部为0，为异常数据，所以首先进行c(7,:)=[]对数据进行筛选，接下来在Matlab中运行出的min(c)是1×18的矩阵，将得到的矩阵中的数字在原始的矩阵c（即还未提取第7行元素）中找到对应数字，进而找到该数字在矩阵中的序列，如第一个数字是第一列中第18个数，即18-1。第二个数字是第二列中第17个数，即17-2。依次类推，得到所有序列，即 18-1,17-2,11-3,16-4,2-4,5-6,1-7,12-8,13-9,6-10, 4-11,19-12,1