2013年全国数学建模B题省一等奖

2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）B我们的参赛报名号为（如果赛区设置报名号的话）：024B03所属学校（请填写完整的全名）：山东科技大学参赛队员(打印并签名)：1.张鑫2.吕彦全3.孙红华指导教师或指导教师组负责人(打印并签名)：赵文才（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）日期：2013年9月16日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1基于最小二乘法的碎纸片拼接复原数学模型摘要首先对图片进行灰度化处理,然后转化为0-1二值矩阵，利用矩阵行（列）偏差函数，建立了基于最小二乘法的碎纸片拼接数学模型，并利用模型对图片进行拼接复原。针对问题一，当两个数字矩阵列向量的偏差函数最小时，对应两张图片可以左右拼接。经计算，得到附件1的拼接结果为：08,14,12,15,03,10,02,16,01,04,05,09,13,18,11,07,17,00,06。附件2的拼接结果为:03,06,02,07,15,18,11,00,05,01,09,13,10,08,12,14,17,16,04。针对问题二，首先根据每张纸片的内容不同的特性，对图片进行聚类分析，将209张图片分为11类；对于每一类图片，按照问题一的模型与算法，即列偏差函数最小则进行左右拼接,对于没有拼接到组合里的碎纸片进行人工干预，我们得到了11组碎纸片拼接而成的图片；对于拼接好的11张图片，按照问题一的模型与算法，即列偏差函数最小则进行上下拼接,对于没有拼接到组合里的碎纸片进行人工干预。我们最终经计算，附件3的拼接结果见表9，附件4的拼接结果见表10。针对问题三，由于图片区分正反两面，在问题二的基础上，增加图片从下到上的裁截距信息，然后进行两次聚类，从而将所有图片进行分类，利用计算机自动拼接与人工干预相结合，对所有图片进行拼接复原。经计算，附件5的拼接结果见表14和表15该模型的优点是将图片分为具体的几类，大大的减少了工作量，缺点是针对英文文章的误差比较大。关键字：灰度处理，图像二值化，最小二乘法，聚类分析，碎纸片拼接2一、问题重述碎纸片的拼接复原技术在司法鉴定、历史文献修复与研究、军事情报获取以及故障分析等领域都有着广泛的应用。近年来，随着德国“斯塔西”文件的恢复工程的公布，碎纸文件复原技术的研究引起了人们的广泛关注。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。对于一页印刷文档，针对不同的破碎方法，讨论下列三个问题：（1）将给定的一页印刷文字文件纵切，建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。（2）对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。（3）对于双面打印文档，研究如何进行碎纸片的拼接复原问题。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。要求尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。二、模型的基本假设（1）待拼接的碎纸片来自同一页印刷文字文件。（2）待拼接复原的碎纸片是规整的矩形。（3）模型中的碎纸片长度、宽度和面积都相等。（4）附件中照片都是同标准拍摄。三、符号说明表1符号说明符号符号说明Gray灰度值r红色g绿色b蓝色A,B矩阵3iD裁截距ia裁截文字长度ib行间距ic裁截空白距离id字体高度四、问题分析将不规则的文档碎纸片进行拼接，一般是利用碎纸片的边缘曲线，尖点、尖角、面积等几何特征，搜索与之匹配的相邻碎纸片。但对于边缘形状相似的碎纸片，这种基于边界几何特征的拼接方法失效，拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否匹配。本问题给定的碎纸片有以下几个特点：1、每一张碎纸片都是规整的矩形；2、所有的碎纸片的长度、宽度都相等，形状是完全一样的；3、每一张碎纸片里都包含着文字（汉字、英文），不存在空白的碎纸片；4、不同的碎纸片之间没有重叠部分。由于碎纸片的形状相同，因而不能针对碎纸片的几何特征建立数学模型；碎纸片间无重叠，也不能利用图像融合技术进行图像配准。根据上述分析，我们考虑将图片进行数字化处理，根据每张碎纸片上的边缘文字特征进行匹配，也就是利用图片边缘文字的像素进行最优化匹配。五、模型的建立与求解5.1问题一的建模与算法由于碎纸片本身不具有体现其拼接特性的数字特征，我们需要将其数字化、矩阵化，将问题转化为矩阵之间的相关性。5.1.1图片的灰度处理利用photoshop软件，将附件中所给的BMP格式的图片转化成JPG格式，去除图片的多彩性。为了对碎纸片进行数字化，我们将图像进行灰度处理，取出图像中每一个像素的灰度值，灰度值的大小与像素点颜色的红绿蓝成分有关。4根据文献[1]，每个像素点的=0.30+0.59+0.11灰度值红色绿色蓝色，即0.300.590.11Grayrgb，其中，,,rgb的取值范围是0~255。问题一将同一页印刷文字文件纵切为19张图片（见图1），根据实际情况，我们将每张图片设置为198072格式，于是，每张图片对应一个198072的灰度矩阵。图1附件1未进行拼接的19张碎纸片5.1.2图片的二值化处理将图片进行灰度处理以后，每个像素的灰度值介于0~255之间。灰度值不能直接用于文字图片的拼接，还须进行二值化处理。将图片放入直角坐标系，规定：若(,)xy点的像素灰度值大于或等于T，该点用数值1表示，并将其设定为白色；若(,)xy点的像素灰度值小于T，该点用数值0表示，并将其设定为黑色。由此得到像素点的二值化函数：51,(,),(,)0,(,),GrayxyTwxyGrayxyT其中，T为预先设定的全局灰度阈值。于是，每张图片的灰度矩阵转化为下列198072的0,1数字矩阵：1117219801198072aaAaa,其中1,1,0,0.ija代表空白的像素点代表有文字的像素点5.1.3最小二乘法1、图片左右拼接的数学模型设,AB分别表示左右放置的两张图片对应的数字矩阵，定义前一个矩阵的最后一列与后一个矩阵的第一列之间的偏差函数为：198021(,)(,72)(,1),ifABAiBi其中，(,72),(,1)AiBi分别表示矩阵,AB第72列和第1列的元素。对于给定的矩阵A，若存在矩阵B，使得A与B之间的偏差函数(,)fAB达到最小，则称A与B可以匹配，此时A与B对应的图片可以左右拼接。2、图片上下拼接的数学模型类似地，设,CD分别表示上下放置的两张图片对应的数字矩阵，定义上面矩阵的最后一行与下面矩阵的第一行之间的偏差函数为：7221(,)(1980,)(1,),jhCDCjDj其中，(1980,),(1,)CjDj分别表示矩阵,CD第1980行和第1行的元素。对于给定的矩阵C，若存在矩阵D，使得C与D之间的偏差函数(,)hCD达到最小，则称C与D可以匹配，此时C与D对应的图片可以上下拼接。我们称上述基于数字矩阵之间列（或行）距离的图片拼接模型为最小二乘法拼接复原模型。5.1.4算法与求解（一）算法思想6第一步，对附件中的19幅图片分别进行灰度处理，然后取灰度阈值125T，进行二值化，得到19个0,1数字矩阵，即图片的数字化。第二步，对上述19个数字矩阵进行检测，若存在一个矩阵的最左侧一列元素全是1，根据破碎图片的特点，则该图片即为从左边起第一张碎纸片，记为1A。第三步，计算1A与其余18张图片对应矩阵的列偏差值。19802111(,)(,72)(,1),ifABAiBi若存在2A，使得12(,)fAA达到最小，则2A即位第二张图片。重复上述的步骤，依次得到所有碎纸片的排列，即可拼接成完整图片。（二）附件1、2的拼接复原结果附件1和附件2的拼接顺序如下表：（附件1的算法程序见附录一，复原图片见附录二；附件2的算法程序见附录三，复原图片见附录四）表2附件1拼接顺序8141215310216145913181171706表3附件2拼接顺序36271518110519131081214171645.2问题二的模型建立与算法5.2.1图片的数字化处理步骤一：将附件所给的BMP格式图片转换成JPG格式的图片；步骤二：对图片进行灰度处理；步骤三：然后进行二值化处理；最后，得到209张图片的数字化矩阵。5.2.2聚类分析对于碎纸机既纵切又横切的情形，与问题一仅纵切相比，图片变小，因而每张图片包含的信息量明显变小，如果仅利用最小二乘法，碎片之间的匹配不唯一。为了解决这个问题，我们利用聚类分析法，对碎片先进行分类。经观察测试，原始文档碎片具有下列特点：（1）字体大小：字体的最大高度和最大宽度一致。（2）切割的均匀性：同方向的切割线平行，图片大小均相等，沿纵横方向按直线切割。（3）文字的行距：文字的行间距等同，段落间距为定值。为了对209幅图片进行聚类分析，如图2所示，我们定义聚类指标如下：7ia表示图片上端裁接处的字体长度，我们称之为裁截文字长度；ib为行间距；ic表示图片上端文字与切割线之间的空白距离，我们称之为裁截空白距离；id为字体高度，其中，=1,2,,209i。图2图片聚类指标示意图令iiiDab或iiiDcd，称iD为第i张图片的裁截距(=1,2,,209)i，由图2，如1212,aabb，则12DD。一般地，图片从上往下看，不同的裁截线形成的裁截文字长度不同，文字间的行间距相同，所以，如果裁接处的文字长度不相等，那么文字与空白间距之和就不相等。根据iD的不同取值，下面对图片进行分类。根据二值化矩阵的特点以及文字的特征，只要存在文字，则矩阵的某一行元素一定存在0元素，且在文字之间的元素为1。如下图所示：图3文字特征图利用matlab软件进行编程，将每个图片的裁截文字长度、行间距、裁截空白距离、字体高度以及裁截距的结果以excel的形式输出到表格之中。（程序见附录五）按裁接距进行聚类分析，使用spss软件分析处理后，得到聚类中心分布图如下所示：表4聚类中心聚类中心聚类1234567891011V17523212044581336410969788根据表4所示的聚类中心，对表格中裁截距进行初步分类。得到聚类结果如下表所示：表5每个聚类中的案例数每个聚类中的案例数聚类12.000236.000318.00041.000546.000638.00071.000836.00091.0001011.0001119.000有效209.0