沈阳建筑大学_徐俊杰郭书恒唐杰

2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：沈阳建筑大学参赛队员(打印并签名)：1.徐俊杰2.郭书恒3.唐杰指导教师或指导教师组负责人(打印并签名)：徐启程（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）日期：2013年9月16日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：-1-碎纸片的拼接复原摘要碎纸自动拼接技术是图像处理与模式识别领域中的一个较新但是很典型的应用，它是通过扫描和图像提取技术获取一组碎纸片的各种特征信息，然后利用计算机进行相应的处理从而实现对这些碎纸片的全自动或半自动拼接还原，其在现实生活中的许多领域都有着重要的应用。针对问题一，由于边界规则，无法利用边缘特征，因此本文提取图像灰度值这一特征。通过matlab软件对附件一中的图片进行预处理，得出矩阵编码。其中破损文字相同位置的灰度值相同，运用这一个切合点，使边界处的一列矩阵对应相减并取绝对值相加，取其最小值排序模拟拼接，首次方法的模拟结果并不理想，对模型进行改进。这次先用matlab挑选出左右两边界图像，再运用上述模型进行模拟，而此次中文拼接准确率高达100%，英文也达到94.7%；针对问题二，在问题一的基础上加大了信息的不完整度，需要更多的限制条件来约束模型的运行，进而模拟出真实文件的实际效果。对此，本文加入横向，纵向信息综合判断，在结果不清晰的情况下，又加入自创的累加器原理加以模拟，使附件3和附件4的准确率差强人意；针对问题三，问题二的研究方法已不能成功模拟文件的拼接，因此，引入聚类分析这一概念，将所有图片综合分类，再在每种类别中加入问题二的分析，综合两面信息的完整度，整合灰度差值，进而完善附件5的拼接工作。最后，对模型中运用的方法进行了科学性分析，讨论模型的创新与失败之处，综合分析，本文的模型比较完美。关键字：图像处理灰度值累加器原理聚类分析-2-1.问题的提出与重述1.1问题的提出司法物证复原、历史文献修复和军事情报获取等领域中，破碎文件的拼接起着非常重要的作用。在计算机还不发达的过去，破碎文件的拼接复原工作都需要人工来完成，虽然有着较高的准确率，但是需要花费的时间很长，效率很低。碎片数量的增加，也会加倍的增大人工任务，很难做到在短时间内完成任务。计算机技术的发展给自动拼接技术带来了希望。为了提高拼接复原效率，人们开始试图开发碎纸片的自动拼接技术。1.2问题的重述碎纸片的自动拼接技术的研究和开发具有极其重要的意义，为提高拼接复原效率，针对以下问题，讨论和建立相关碎纸片拼接模型和算法。1、对给定来自同一页印刷文字文件的仅纵切的破碎机破碎纸片，建立碎纸片拼接复原模型和算法。并运用所建立的模型和算法，对附件1和附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，需要写出干预方式及干预的时间节点。2、对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。3、前两问均为单面打印文件，现实情形中，有可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出一页英文印刷文字双面打印文件的碎片数据。设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。2.问题分析目前碎纸的拼接工作大部分都是靠人工的方式完成。虽然国外对这项工作进行了一些研究，但是由于碎纸的自动修复技术应用背景的特殊性，目前几乎没有公开的研究资料可以参考。类似的研究主要是集中在文物碎片的自动修复、虚拟考古、故障分析以及计算机辅助设计、医学分析等领域。碎纸自动拼接可以近似看作是一个拼图问题(jigsawpuzzleproblem)。在机器人和计算机视觉领域中，很早就有学者对自动拼图问题进行了研究[1,2]。H.Wolfson等人[3]开发了一套机器人系统，能让机器人在标准的拼图游戏中找到各个对应的匹配块，并操作机器人进行自动拼图。但是，这些技术都利用了拼图游戏中的一些特殊特征(如平滑的轮廓，显著的角点等)以及一些先验知识。而在许多实际应用中都不能满足这些条件，碎纸机剪出的纸片的形状一般都是规则的，无法运用轮廓这一特征，因此先前也没有什么先验知识可以利用。问题一的的分析以图像灰度值作为切合点，利用破损文件的同一部位的灰度值相同这一特征，对边界处灰度矩阵对应值做差，得到一个新的灰度偏置矩阵，再令其取绝对值加和，取其中最小值，运用matlab进行第一次模拟匹配拼接。在实际操作过程中我们发现，文字拼接出现误差，且英文误差过大。因此，对该模型进行改进。通过已完成的拼接发现发生错误的部位是由于边界处灰度值相同，导致左右边界相连错误，对此，运用matlab先选出左右边界后再次进行模拟，结果第二次的模拟结-3-果较出色。问题二的分析由于第一问中的文件只有纵向切割，横向信息完善，所以只需寻找纵向特征即可完成拼接。但附件3和附件4中文件既有纵向切割又有横向切割，单纯依据纵向特征数据已不能保证完整的模拟以及准确率的要求，因此，我们对模型加入更多的限制条件。对于附件3和4我们首先加入的单行灰度性质条件，进而进一步完善加入多行特征，完成行匹配后，加入列的匹配，拼接出单行的正确顺序，进而转换思想，将第一问的纵向匹配转换为横向行间匹配，运用matlab进行模拟。本题的关键在于选定文件拼接匹配的限制条件。问题三的分析问题三在前两问的基础上加以深入研究，这无疑又增添了文件拼接的难度。因此加入新的约束分析，设想可以采用聚类分析确定文字所在行的位置分出组别，然后采用问题一和问题二的方法进行连续拼接。此时进行人工干预，确定每一行正反两面的内容。最后，利用字母灰度的连续性纵向复原出纸张碎片。3.模型假设为了简化计算，给出如下模型合理性的假设：1.假设附件中图片源文件都为打印字体，非手写或其他模糊不清的版本；2.假设纸张上没有污点，或者污点不影响图片信息导入；3.假设纸张沿平行或垂直纸的边缘方向切割；4.假设图片边缘即为纸片切割边缘。4.符号说明为了简化对问题的分析和对数字的处理，做出如下符号规定：nx：图片最右一列灰度值ny：图片最左一列灰度值()fx：处理后的转换值g：灰度值T：阈值-4-5.模型的建立与求解5.1问题一的模型建立与求解5.1.1模型准备运用matlab软件，分别对附件1、附件2中给出的图片进行预处理，转换成灰度矩阵，提取每张图片中处于边界的两列矩阵，再基于灰度信息对原文进行拼接。图5.1附件3，001的灰度概率密度图5.1.2模型的原理说明现存的碎纸拼接方法大多是图片边缘特征进一步抽象，基于一套相应的或已有的边缘检测结果加以改进，进行拼接。然而，被碎纸机粉碎的文件边缘整齐，破损程度大，用边缘检测的理论已不能完成拼接工作，因此，本文以照片灰度值作为特征来完成碎纸拼接工作。SSDA(sequentialsimilaritydetectionalgorithm)序列相似性检测算法是一种快速图像匹配算法,它使用下式作为相似性度量：,111(,)(,)(,)NNijmnDijsmnTmnmn(5-1)SSDA以随机不重复的顺序选取像元对(m,n),在进行上述求和时不需要计算所有像素。一方面,这是一个计算更为简单的相似性度量准则,这一准则即使在非归一化情况下仍可在匹配处获得极小值,并且没有乘法运算。另一方面,这种方法采用了序贯搜索策略。SSDA的基本思想是：如果窗口内所有点被检验完之前该误差过早地达到预定的门限值,便认为该窗位置不是匹配点,无须继续检验窗内的剩余点,停止本次运算,而转向计算下一窗口位置,直到找到匹配点为止,记录其值,从而省去大量的在非匹配位置处的无用运算量。该准则实际上是一个误差绝对值的累加和,在图像不匹配的位置,累加时误差增长的很快,而在图像匹配位-5-置上的误差随着累加次数增长缓慢。5.1.3模型的建立与求解上述模型原理说明的算法主要利用相似面积来判断，而对于文字拼接来说面积方面的要求就过于严苛。因此，本文在原算法上联想并加以创新，利用破损文字的破损部位的灰度值相同来判别。对于碎纸机纵向切割后的文件灰度处理后，提取边界矩阵，如果是相连文件，那么边界处矩阵对应行相减应该为0，但由于图片提取及噪点等原因，并不能完全实现差值为0，即完全吻合的情况，采取如下处理方式：(1)取每张图片的最后一列灰度矩阵进行两两对应行数相减，得到新的数据矩阵，对该矩阵中的数字分别取绝对值，再进行求和；01nxxx01nyyyiisumxy(5-2)(2)接下来从每个结果中找寻绝对值最小的结果进行拼接，得到如下结果：表5.1Matlab第一次模拟结果中文拼接6081412153102161459131811717英文拼接5191310812141716403627151811(3)通过计算机模拟，以中文文件为例，见图5.2，不难看出只有前两列拼接错误，且第3列为原文件首列，将前两列取下，从第17列开始，再次运用matlab模拟，得到正确顺序，如下：图5.2通过matlab第一次模拟的中文文件-6-5.1.4模型的改进通过上述模型，得出中文拼接错误率为10.5%，英文拼接错误率为42.1%，在实际操作中，此方案的准确率并不算高，实现文件拼接问题仍有待商榷。然而，通过表5.2发现，边界处不止一列灰度矩阵为相同值，基于此特征对模型加以改进，模型的改进步骤如下：(1)仍提取所有图片文件的灰度矩阵，找出每张图片从边界算起灰度值相同的矩阵列数，分别找出从左边和右边边界起灰度值相同列数最多的图片，作为原文件的左边界；(2)在确定左边界后，将所有图片信息再次录入，通过matlab模拟，比较边界差值的绝对值大小进行原文件拼接。表5.2Matlab第二次模拟结果中6081412153102161459131811717英5191310812141716403627151811经过人工干预后的正确顺序如下：表5.3经人工干预后的正确结果中8141215310216145913181171706英36271518115191310812141716405.1.5误差分析图5.3改进前后的Matlab模拟拼接准确率对比图5.4中、英文文件边界处灰度值比较图5.5中文文件较英文文件灰度触点数量相比-7-模型改进后，中文文件的拼接准确率高达100%，英文文件拼接准确率也达到94.7%，符合实际需求。通过上述模型模拟出的数据结果可知，此模型对中文文件的识别率更好，模拟率更高。将z中文文件与英文文件各提取出相同的数量，取边界矩