文档介绍：该【新编碎纸片拼接 】是由【朱老师】上传分享，文档一共【23】页，该文档可以免费在线阅读，需要了解更多关于【新编碎纸片拼接 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1第2页,共3页2024高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了?全国大学生数学建模竞赛章程?和?全国大学生数学建模竞赛参赛规那么?〔以下简称为“竞赛章程和参赛规那么〞,可从全国大学生数学建模竞赛网站下载〕。我们完全明白,在竞赛开始后参赛队员不能以任何方式〔包括电话、电子邮件、网上咨询等〕与队外的任何人〔包括指导教师〕研究、讨论与赛题有关的问题。我们知道,抄袭别人的成果是违反竞赛章程和参赛规那么的,如果引用别人的成果或其他公开的资料〔包括网上查到的资料〕,必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺,严格遵守竞赛章程和参赛规那么,以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规那么的行为,我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展示〔包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等〕。我们参赛选择的题号是〔从A/B/C/D中选择一项填写〕:2024B 我们的参赛报名号为〔如果赛区设置报名号的话〕:所属学校〔请填写完整的全名〕:西京学院参赛队员(打印并签名):(打印并签名):张培军 〔论文纸质版与电子版中的以上信息必须一致,只是电子版中无需签名。以上内容请仔细核对,提交后将不再允许做任何修改。如填写错误,论文可能被取消评奖资格。〕日期:2024年8月7日1第2页,共3页赛区评阅编号〔由赛区组委会评阅前进行编号〕:1第2页,共3页2024高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号〔由赛区组委会评阅前进行编号〕:赛区评阅记录〔可供赛区评阅时使用〕:评阅人评分备注全国统一编号〔由赛区组委会送交全国前编号〕:全国评阅编号〔由全国组委会评阅前进行编号〕:基于0-1规划碎纸片的拼接复原分析模型摘要本文是对碎纸片的拼接复原问题进行分析。通过提取碎片间的边缘灰度特征和文字行列位置特征差异,建立以总体差异程度的最小范数值为目标函数的0-1规划模型,运用MATLAB软件进行求解,配合少量人工干预,可实现单面与双面文件既被纵切又被横切的碎纸片的二维拼接复原的目标。我们先将题目中给出的附件一至附件五的碎纸片进行分析,对三个问题进行算法分析和建立数学模型,解决碎纸片复原中的三个问题。对于问题一,由于是单面文件且大小相同的碎片,利用MATLAB软件将各碎纸片分别转化为其灰度值矩阵,然后转化为二值矩阵,得出两碎纸片左右边缘二值向量矩阵差异与文字行列位置差异,经过显示,复原效果很好。对于问题二,我们采用0-1规划拼接模型分析,方法和问题一的处理方法相同,并提出利用欧氏距离和贪婪算法进行模型的修改与完善,同时利用由碎片组成的文件数据进行模拟仿真处理,配合少量人工干预,可实现单面既被纵切又被横切后的碎纸片的二维拼接复原的目标,最后再建立一个优化模型进行复原过程的修复,使复原率到达100%。对于问题三,我们在问题一和问题二的0-1规划拼接模型的根底上,充分利用双面文本的特征信息,在MATLAB中建立碎纸片的聚类模型,这样可大大提高复原率,最后配合少量人工干预,实现双面文件既被纵切又被横切后的碎纸片的二维拼接复原的目标。最后,要对三种不同的特征碎片在复原的过程人工干预次数较少,尽可能实现碎片复原的全自动化。这时我们对三维的碎片进行复原,在问题三的根底上自行构造碎片和对考古中的文物进行拼接复原,用来检验与评价本文的算法与模型。经过复原比照,效果很理想。关键词:0-1规划模型优化模型仿真处理贪婪算法聚类算法第2页,共3页一、问题重述破碎文件的拼接在物证司法复原、历史文献修复以及军事情报获取等领域都有着重要的应用。随着计算机技术的开展,提高拼接复原效率的碎纸片自动拼接技术被试图开发,讨论问题如下:〔仅纵切〕,建立碎纸片拼接复原模型和算法,如果复原过程需要人工干预,请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。,请设计碎纸片拼接复原模型和算法,复原结果表达要求同上。,从现实情形出发,还可能有双面打印文件的碎纸片拼接复原问题需要解决。并就附件5的碎片数据给出拼接复原结果。二、问题分析问题一是对被纵切的碎片复原的问题,考虑到碎片的拼接问题是找到碎片与碎片之间最好的排列问题,利用MATLAB软件将各碎纸片分别转化为其灰度值矩阵,得出两碎纸片左右边缘灰度值向量差异与文字行位置的差异,最后再建立一个优化模型进行复原过程的修复。问题二是对既被纵切又被横切的碎片复原。先考虑纵切,对一些在同一行的碎片可用问题一的拼接策略解决。再考虑到横切,我们采用0-1规划拼接模型分析,我们可以将拼接好的碎片用拼接策略拼接起来得到最终的复原纸张。并提出利用贪婪算法进行模型求解,同时利用由碎片组成的文件数据进行模拟仿真处理。问题三是对双面碎片的复原,我们可以用解决问题二的方法得到一些拼接好的碎片行,用类似问题一的方法将碎片行拼接起来,但此时由于碎片有正反面之分,所以我们在0-1规划拼接模型的根底上充分利用双面文本的特征信息,建立碎片的聚类算法模型,这样可大大提高复原率。三、。。,边缘轮廓为规那么的矩形。,且与背景颜色有较大反差。、从上至下书写的。,即碎片中的文字端正。第2页,共3页四、定义与符号说明符号符号说明二值化后矩阵后侧的图片矩阵左侧图片矩阵数减右侧图片矩阵数之差横纵矩阵的的匹配值碎片左右上下欧氏距离W总体欧氏距离a,b行列上端裁截处裁接的字体长度行间距图片上端文字与切割线之间的空白距离字体高度梯度算子〔用于形态边界的提取〕五、。现在要建立数学模型将碎纸片进行拼接。问题所给附件1、附件2图片碎片上的文字都是黑色,纸都是白色,此外没有其他颜色,且文字被切开,可以用灰度匹配的方法寻找匹配图片,借用MATLAB软件进行编程求解。模型一:利用MATLAB软件将各碎纸片分别转化为其灰度值矩阵,得出两碎纸片左右边缘灰度值向量差异与文字行位置的差异。建模思路:碎纸片为白纸黑字,只有黑白两种颜色,可建立其灰度值模型,然后根据灰度化后的碎纸片,进行碎片的复原。最后再建立一个优化模型进行复原过程的修复。首先将每幅图片依次进行灰度级处理,由于图片为198072的尺寸,故得到的灰度值矩阵为1980行72列。碎纸片的寻找方向为从左向右,左边碎纸片的灰度矩阵的最后一列要找右边碎纸片的第一列使这两列的相似度相等,那么这两个碎片为相邻图片。每个碎片如此循环往复比较,直到判断出碎纸片的正确顺序。:〔1〕首先选取一个图片〔图一〕,先将它进行格式转化,将其灰度化。第2页,共3页图1:转化格式前的原图图2:转化后的局部图像〔2〕将这些灰度后的图片进行二值化,二值化之后产生矩阵局部矩阵不予给出,最后得到全部矩阵。①形态滤波处理。首先对图像进行滤波,滤出噪声及平滑图像处理;②形态边界提取。根据形态梯度算子,采用如下3*3的8个连通结构元素分别对f进行边界提取,得到8幅不同的边界图像,将这些图像对应位置上的像素值进行或运算得到新的边界图像e1;③采用全局阈值化法(如直方图阈值化方法),对图像进行二值化,可得到二值化图像。④采用统计方法对图像e1进行阈值化,形成二值图像e2;⑤对图像e2的每个像素进行位反运算,得到新的二值图像e3;⑥输出二值图像g。〔3〕二值化后的碎纸片边缘矩阵如下表示:①设第张图片的二值化后的矩阵为,取左侧第1列数组,记为右侧的第1列数组为。②利用MATLAB软件编程找出可能位于复原图片首位的碎纸片,令该纸片序号为第2页,共3页,图片二值化矩阵为,假设为的矩阵其元素均为255,那么图片位于复原图片首位。③确定首位图片后,采取依次向右寻找的方法,以作为起始列,寻找位于图片右侧的图片为,使与匹配再寻找位于图片右侧的图片,以此类推,直至将19幅图片全部遍历。④匹配时采取以下方法,令,对累加求和,〔1〕令中最小的元素为,求出该元素下标,那么第幅图位于图片右侧。〔4〕按照此方法依次对碎纸片进行处理,分别求得每一幅图片右侧吻合度最高的图片,最后读取十九张图片之后得到全部的边缘距离矩阵,详见附录一,然后依据这些边缘距离矩阵求出和纸片右相邻的纸片,最后求出文件中最左边的碎片,从而记录上一张碎纸条,然后记录下一张碎纸片。最后存取整张图片,得到复原图。详见附录三。。先考虑纵切,对一些在同一行的碎片可用问题一的拼接策略解决。再考虑到横切,我们采用0-1规划拼接模型分析,我们可以将拼接好的碎片用拼接策略拼接起来得到最终的复原纸张。并提出利用贪婪算法进行模型求解,同时利用由碎片组成的文件数据进行模拟仿真处理。,我们先利用模型一中的灰度化后的模型进行二值化处理,得到相对应的二值化模型,进行碎片的复原。然后将拼接好的碎片拼接起来得到最终的复原纸张,利用由碎片组成的文件数据进行模拟仿真处理。第2页,共3页逆变换后图像反演原图灰度化二值化图3:碎片数字化处理及反演过程示意图对于拼接复原该中文文件碎片,考虑到碎片拼接的唯一性,设定假设两片碎片可拼接那么取值为1,否那么取为0,从而可设0-1变量为〔2〕对于提取边缘特征信息的碎片,其是否匹配可利用碎片边缘信息的关联性来描述,常用的描述方法可用欧氏距离来描述,因此本文采用欧氏距离来描述两张碎片的匹配度。碎片左右灰度二值化数据向量的欧氏距离可定义为〔3〕其中,是左端碎片的右边界像素向量,是右端碎片的左边界像素向量。同理,两张碎片上下灰度二值化数据向量的欧氏距离为〔4〕其中,是上端碎片的下边界像素向量,是下端碎片的上边界像素向量由欧氏距离定义得知,假设值越小,那么意味着匹配度越高。横向拼接总欧氏距离为,而纵向拼接欧氏距离为。以全局碎片拼接复原匹配度最大为目标建立优化模型,即以横纵两个方向的总体欧氏距离最小为目标,那么目标函数为〔5〕第2页,共3页对于每个碎片的左端而言,至多只有一个碎片与其进行右邻拼接;而对于每个碎片的上端而言,至多只有一个碎片与其下邻拼接因此可得到拼接约束为〔6〕假设209张碎片样本构成的文本为行列,即每一行的碎片为张,每一列为张那么每一行有对碎片匹配,同样每一列有对碎片匹配,从而可得到总匹配拼接约束为〔7〕〔8〕得到碎片拼接的0-1规划模型为〔9〕由于这种自由拼接方式对于每一种情况计算每张碎片和其近邻碎片的欧氏距离从而得到总体匹配度,再对其进行比较,那么计算量过大,难以实现。对于碎片量较多,求精确解较为困难时,我们提出了贪婪算法能够较快的实现碎片拼接复原。贪婪算法根本思想是对所有碎片先按行拼接,待每行均拼接完成后,再按列拼接复原成完整的图片文件对于行拼接过程,那么按行向欧氏距离总和最小进行匹配,考虑左右两张碎片的拼接仍采用模型(9)中两两欧氏距离作为指标,以任意一张碎片开始,先按向右方向进行拼接,假设左右碎片的欧氏距离lr最小时恰好是相邻关系,那么将其拼接在一起,否那么将进行人工干预,即将欧氏距离次小的碎片作为右端碎片,再与左端碎片进行拼接并进行文本内容判别,直到找到最符合该端碎片的右端碎片如此循环,直到将所有碎片行进行拼接完成得到行碎片后再进行列拼接,按纵向欧氏距离总和第2页,共3页