2013年全国大学生数学建模竞赛国家一等奖论文B题碎纸复原模型与算法.pdf

碎纸复原模型与算法 摘要 本文围绕碎纸片拼接问题，建立了碎纸距离模型、复原TSP 模型，并设计了一维碎 纸复原算法、二维碎纸复原算法、三维碎纸复原算法等算法，利用MATLAB 实现对问 题的求解。 针对问题一，设计了一维碎纸复原算法 （见4.1.7），首先提取出附件 1 和附件 2 碎纸图片的像素矩阵，并对其进行二值化处理，然后利用MATLAB 提取碎纸图片的文 字特征，通过字符大小、行距等文字特征构造识别序列，并且利用识别序列的吻合度建 立了碎纸距离模型 （见4.1.4 ），进而将碎纸复原问题转化为复原TSP 问题 （见4.1.5 ）， 并用模拟退火法进行求解，得到了正确的复原图形及序列 （详见附录一）。 针对问题二，设计了二维碎纸复原算法 （见4.2.5 ），首先对附件3 和附件4 的碎纸 图片进行标准化，并对标准化有误的图片进行修正，然后提取标准化后图片的层次特征， 利用层次特征对图片进行初步分类，对于机器不能分类的图片，通过编制GUI 程序提高 了人工判别效率，得到相应11 类行特征相同的碎纸，进而将问题转化为11 个一维碎纸 复原问题并进行求解，得到了正确的复原图形及序列 （详见附录二）。 针对问题三，设计了三维碎纸复原算法 （见4.3.2 ），首先对附件5 的a 面与b 面的 图片进行整合，得到416 张三维碎纸图片，同样对图片进行标准化、提取层次特征、分 类等操作，将问题维度降为一维并进行求解，得到附件5 正反面的正确复原图片及序列 （详见附录三）。 考虑到算法的量化评价问题，本文在模型改进处提出最小干预度算法，即通过计算 机识别顺序与复原顺序的序列逆序数，实现了最小人工干预次数对算法优劣进行刻画。 关键词：碎纸复原算法、TSP、模拟退火法、分类降维、GUI 设计 1 一、问题重述 破碎文件的拼接在多项领域中有着重要的应用。传统的人工拼接复原，准确率较高， 但效率很低，不能在短时间内处理大数量碎片。随着计算机技术的发展，提高拼接复原 效率的碎纸片自动拼接技术被试图开发。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片 拼接复原模型和算法，并针对附件 1、附件2 给出的中、英文各一页文件的碎片数据进 行拼接复原。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附 件3、附件4 给出的中、英文各一页文件的碎片数据进行拼接复原。 3.从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件 5 给出的是一页英文印刷文字双面打印文件的碎片数据。建立相应的碎纸片拼接复原模 型与算法，并就附件5 的碎片数据给出拼接复原结果. 二、问题分析 本题是研究碎纸复原问题，问题一至三，分别研究一至三维三种不同情况的碎纸复 原，本文对问题的解答也是沿着这样的思维路线，即通过降维，使高维度问题转化为低 维度问题。 问题一是一个一维碎纸复原问题，首先从图片中提取出像素矩阵，并对其进行二值 化处理，然后根据附件碎纸均为大小、形状一致矩形选择提取其文字特征得到基于文字 特征的识别序列，由识别序列定义碎纸片之间距离，将寻找最佳吻合碎纸片组合转化为 寻找最短路径的TSP 问题，并编制一维碎纸复原算法进行求解。 问题二是一个二维碎纸复原问题，碎纸经过横切纵切之后碎片间的文字特征减少， 继续沿用第一问模型求解计算复杂度降呈指数级递增，计算精度也将下降，考虑分析碎 纸片文字行间距、大小等特点提出对应准则模型对碎纸片进行识别分类，运用问题一模 型与算法先对每一类内碎纸片进行拼接复原，而后再对得到部分拼接复原图进行拼接复 原，分类、复原过程适当进行人工干预提高复原精度。 问题三是一个三维碎纸复原问题，需要在问题二的基础上考虑碎纸片的正反面问题。 通过问题二的分类模型进行修改，对碎纸片进行分类，通过分类对问题三进行降维处理， 然后按问题二方法解决问题，复原过程中适当进行人工干预提高复原精度。 此外，本题是个实际问题，现实中需要考虑的因素远远多于题目本身，如何使模型 更加贴近实际，并提供有效的拼接信息是本文面临的一大困难，通过查阅大量资料与文