2013B题一等奖论文

2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：5060所属学校（请填写完整的全名）：广东财经大学参赛队员(打印并签名)：1.陈佳润2.谢天旺3.王行志指导教师或指导教师组负责人(打印并签名)：胡桂武（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）日期：2013年09月15日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1碎纸复原模型与算法摘要本文围绕碎纸片拼接问题，建立了碎纸距离模型、复原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设计2一、问题重述破碎文件的拼接在多项领域中有着重要的应用。传统的人工拼接复原，准确率较高，但效率很低，不能在短时间内处理大数量碎片。随着计算机技术的发展，提高拼接复原效率的碎纸片自动拼接技术被试图开发。请讨论以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。3.从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。建立相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果.二、问题分析本题是研究碎纸复原问题，问题一至三，分别研究一至三维三种不同情况的碎纸复原，本文对问题的解答也是沿着这样的思维路线，即通过降维，使高维度问题转化为低维度问题。问题一是一个一维碎纸复原问题，首先从图片中提取出像素矩阵，并对其进行二值化处理，然后根据附件碎纸均为大小、形状一致矩形选择提取其文字特征得到基于文字特征的识别序列，由识别序列定义碎纸片之间距离，将寻找最佳吻合碎纸片组合转化为寻找最短路径的TSP问题，并编制一维碎纸复原算法进行求解。问题二是一个二维碎纸复原问题，碎纸经过横切纵切之后碎片间的文字特征减少，继续沿用第一问模型求解计算复杂度降呈指数级递增，计算精度也将下降，考虑分析碎纸片文字行间距、大小等特点提出对应准则模型对碎纸片进行识别分类，运用问题一模型与算法先对每一类内碎纸片进行拼接复原，而后再对得到部分拼接复原图进行拼接复原，分类、复原过程适当进行人工干预提高复原精度。问题三是一个三维碎纸复原问题，需要在问题二的基础上考虑碎纸片的正反面问题。通过问题二的分类模型进行修改，对碎纸片进行分类，通过分类对问题三进行降维处理，然后按问题二方法解决问题，复原过程中适当进行人工干预提高复原精度。此外，本题是个实际问题，现实中需要考虑的因素远远多于题目本身，如何使模型更加贴近实际，并提供有效的拼接信息是本文面临的一大困难，通过查阅大量资料与文献，并进行适当的、合理的假设，对碎纸复原方式进行研究。3三、符号说明与模型假设3.1符号说明符号说明符号说明ijq二值化前的像素值iR碎片A的右识别序列ijP二值化后的像素值C字符的宽度abd碎片A到碎片B的距离DTSP路径的总距离iL碎片B的左识别序列n识别序列长度3.2模型假设3.2.1假设文字方向是水平的3.2.2假设正反面打印的页边距等格式相同3.3假设说明假设3.2.1是为了保证问题一中识别序列的有效性，与实际中大多数情况相符。假设3.2.2是为了简化问题三，当页边距等打印格式相同时，正反面的层次特征会相同，可以进行降维，与实际中大多数情况是相符的四、模型的建立与求解4.1一维碎纸复原模型4.1.1图像的预处理根据计算机图形学的相关知识，划分空白位置和字符位置前，需对图片像素的处理，一般是通过灰度化，将图片像素值定位为[0,255]区间内，再通过设定阀值，区分空白位置和字体，最后进行二值化。但对于非彩色的图片，仅需区分空白与非空白两种情况即可。为了使图片能够清晰地描述空白位置与字符位置，首先利用数学软件MATLAB对图像进行预处理。首先将图片导入MATLAB，得到对应的像素矩阵，由计算机图形学相关知识可知，空白位置的像素值为255，为了使像素矩阵特征更为明显，需将其二值化，即1,255255,ijijqP其它式中，ijq为二值化前的像素值ijP为二值化后的像素值通过对每张图片进行二值化，得到一系列的像素矩阵，可用于图像的特征提取。4.1.2碎纸特征的提取一般来说，碎纸特征的提取大致分为两类，一类是提取碎纸的轮廓，通过外形特征进行拼接，如文献[1][2]，另一类是通过提取碎纸上的文字特征，基于文字特征进行拼接，如文献[3][4]，根据题意，本文探讨的碎纸片外形皆为长方形，故属于第二类。一维碎纸，是指切割时，仅进行横或纵的切割，形状如图4-1所示。4图4-1一维碎纸示意图通过观察图4-1可以看出，碎纸可以提取出的特征有字符宽度、字距、上空、下空和行距等，见图4-2.图4-2字符的特征综上所述，文字特征的提取方式如下：提取步骤：步骤一：对图片进行二值化，文字为白色，空白为黑色步骤二：找出图片所有行距、上空、下空，并标记其为灰色步骤三：找出图片中所有的字距，并标记其为灰色步骤四：通过行距、上空、下空、字距等特征计算出字符宽度。根据题意，本文通过导入碎纸片图像的像素，并编写MATLAB程序对文字特征进行提取（代码见附录四getLandR.m）.4.1.3基于文字特征的识别序列通过分析汉字与英文字母被分割的情况可以发现，对于每个被切割开的字符，如图4-3所示，记字符的宽度为C，被分割后的两部分宽度分别为CR和R，而对于没被切割的字符，依旧保留宽度C。图4-3字符分割示意图基于汉字分割的定义，可构造基于文字特征的识别序列，如图4-4所示。5图4-4识别序列示意图对于图4-4中的识别序列，其中无字符位置数值为0，其它数字节点代表对应的字符长度（完整的为C，不完整的为CR或R）。4.1.4碎纸距离的定义基于4.1.3识别序列的定义，本文定义碎纸A到碎纸B的距离模型为21()01nABiiiiidLRCXX或（4.1.4）式中，abd为碎纸A到碎纸B的距离iL为碎纸B的左识别序列iR为碎纸A的右识别序列C为字符的宽度iX为表示序列L或R的第i位是否都有字符,是则为1n为序列长度由距离的定义公式可以看出，两个识别序列的吻合程度越大，识别序列的距离越小，理想状况下，当两个识别序列完全吻合时，距离为0（实际情况中，由于二值化，损失了部分精度，所以不会为0）。4.1.5复原TSP问题TSP问题是数图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。若将每个碎纸看成一个点，由4.1.4距离的定义可知，点与点之间存在距离，可以看出，两张碎纸如果吻合度低，那对应的距离也大，所以寻找吻合率最高的组合方式，实质就是寻找总距离最小的路径，也就是寻找一条最佳TSP路径。图4-5复原TSP问题示意图6将碎纸复原抽象成复原TSP问题，即11121min()..01niiinABiiiiiDddLRCXSTX或（4.1.5）式中，D为TSP路径的总距离1iid为碎纸i到碎纸i+1的距离通过求解复原TSP问题，可以得到每个点的访问顺序，即碎纸片的拼接序列，最后利用MATLAB图像拼接，得到复原了的纸片。4.1.6模拟退火法模拟退火法是一种通用概率算法，用来在一个大的搜寻空间内寻找问题的最优解，具有能有效地解决NP难问题、避免陷入局部最优、对初值没有强依赖性等特点，在各领域已获得了广泛地应用。算法步骤[5]：步骤一:令当前温度0TT，即开始退火的初始温度,随机生成一个初始解0x，并计算相应的目标函数值0()Ex。步骤二：令T等于冷却进度表的下一个值iT。步骤三：根据当前解ix进行扰动，产生一个新解jx，计算相应的目标函数值()jEx，得到()()jiEExEx。步骤四：若0E,则新解jx被接受，作为新的解；若0E，则新解按概率iETe接受(即Metropoils准则)，iT为当前温度。步骤五：在温度iT下，重复kL次扰动和接受过程（kL为Markov链的长度），即执行步骤三和步骤四。步骤六：判断温度T是否等于fT，是则终止算法；否则转到步骤二继续执行。利用模拟退火法求解求解TSP问题，将一个序列当成一个解，每个解对应一个目标函数值，通过二次交换、三次交换等扰动方式不断产生新解，从而搜索解空间，寻找最优的调度序列。4.1.7一维碎纸复原算法综上所述，通过一维碎纸复原算法，可以实现一维碎纸的自动复原，相应的算法步骤如下：算法步骤：步骤一：提取出碎纸图像的像素矩阵，并进行二值化处理步骤二：提取出二值化处理后碎纸图像的文字特征步骤三：利用步骤二的文字特征构造识别序列，并转化为TSP问题步骤四：利用模拟退火法求解TSP问题74.1.8模型求解利用Matlab对图片像素进行分析，得到汉字大小4040（单位：像素），考虑到英文字符的特殊性，受文献[3]的启示，将其视为3030（单位：像素）；通过模拟退火法求解TSP问