数学建模B题国家一等奖资料下载.pdf
- 文档编号:5971650
- 上传时间:2023-05-05
- 格式:PDF
- 页数:19
- 大小:1.31MB
数学建模B题国家一等奖资料下载.pdf
《数学建模B题国家一等奖资料下载.pdf》由会员分享,可在线阅读,更多相关《数学建模B题国家一等奖资料下载.pdf(19页珍藏版)》请在冰点文库上搜索。
2013高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛编编号号专专用用页页赛区评阅编号(由赛区组委会评阅前进行编号):
赛区评阅记录(可供赛区评阅时使用):
评阅人评分备注全国统一编号(由赛区组委会送交全国前编号):
全国评阅编号(由全国组委会评阅前进行编号):
碎纸片的拼接复原碎纸片的拼接复原摘要摘要本文要解决的是利用计算技术拼接破碎的文件,减少人工拼接的工作量,提高拼接效率。
针对问题一,发现所有汉字均占据约4141个像素点的空间。
将汉字看做4141的正方形区域,拼接纸片的过程便转化为利用计算机拼接正方形区域的过程。
首先将19个矩阵0-1化处理,统计左右两端字的长度,人工干预找出位于首列的008,其余图片与它进行匹配,判断两个纸条是否匹配的标准是拼接成的汉字长度是否接近41,选择匹配值最高的碎片与之匹配,依次匹配最终得到整张的复原图像,称为“边缘宽度匹配”法。
复原顺序为:
8141215310216145913181171706。
针对附件2,英文不具有汉字的固定长度特征。
我们对上述方法改进,采用更加精细的匹配。
将切割边缘像素点0-1化(0代表空白,1代表有文字),人工干预找出位于首列的图片003,其余图片的边界像素值与其相加匹配,判断两个纸条是否匹配的标准是2或0个数的多少,选择匹配值最高的碎片与之匹配,依次匹配最终得到整张的复原图像,称为“边缘像素点匹配”法。
3627151811051913108121417164。
针对附件2,由于横切时会使位于同一行碎片的汉字留有相同长度,所以图片矩阵0-1化我们首先通过“上边界宽度匹配”法统计上边界被截断汉字的长度或留有的空格长度,将208幅图中位于同一行的汉字分组,人工干预找出分组明显不合理的图片,再利用“边缘像素点匹配”法得到每一行图片的排序,得到11行的正确排序后利用“边缘宽度匹配”法得到最终排序图。
复原顺序为见附录2。
针对附件4,汉字的“上边界宽度匹配”不适用于英文,观察发现英文的书写分为上中结构和中下结构,可以通过图片英文中部所占得位置来确定位于同一行的图片。
208张图片0-1化分别按列求和,将矩阵中的字母全部投影到一侧,用matlab绘制每张图片的投影波峰图,根据第一簇的两个较大波峰的位置取其平均值,找到每幅图片第一行中部的位置,将图片分为11组,人工干预找出分组明显不合理的图片,再利用附件2英文的“边缘像素点匹配”法得到每一行图片的排序,得到11行的正确排序后利用附件1汉字的“边缘宽度匹配”法得到最终排序图。
针对对于附件5拼接正反两面的纵横切碎片,我们考虑仍然运用对附件4英文的投影波峰图法,matlab编写程序寻找到416个图片的匹配中部值,以此为标准按行分类。
位于同一行的图片利用“边缘像素点匹配”法得到行的图片排序,进行人工干预,再对行采用“边缘宽度匹配”法和人工干预得到最终排序表见附录2。
关键词关键词:
0-1化处理、边缘宽度匹配、边缘像素点匹配、上边界宽度匹配、投影波峰图一问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。
传统的人工拼接方法很难在短时间内完成任务。
而利用计算机技术,可以开发碎纸片的自动拼接技术,提高拼接复原效率。
现建立适当数学模型,利用计算机解决以下问题:
1.1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片拼接复原模型和算法,并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。
2.2.对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
3.3.从现实情形出发,还可能有双面打印文件的碎纸片拼接复原问题需要解决。
附件5给出的是一页英文印刷文字双面打印文件的碎片数据。
尝试设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼接复原结果。
如果复原过程需要人工干预,写出干预方式及干预的时间节点。
复原结果以图片形式及表格形式表达。
二模型假设1、假设不考虑附件中所给的所有图片的扫描误差。
2、假设对于附件中所给的汉字都是等高等宽的正方形。
3、假设不用对所有图片进行去躁处理。
三模型建立及求解3、问题一模型建立及求解:
问题分析:
附件1给出了汉字19的条碎片,需要将这19条碎片进行排序复原,观察左右边缘处,发现有很多文字被切开,因此碎片的拼接转化成,对边缘处被截断的汉字的拼接。
但计算机无法识别汉字,考虑到汉字是方正的,因此只需要拼接成一个汉字大小的文字区域,就可近似认为是拼接成一个完整的汉字。
附件2给出了英文的19条碎片,而英文单词甚至英文字母均不具有汉字的方正特点,所以采用另一种拼接方法。
因为将文字放大后,字母的形状是连续变化的,也就是说,若一个汉字被切开了,则在切断面的左右灰度值是近似相等的。
用matlab汉灰度值读取每张图片,会得到一个数字矩阵,矩阵中每个元素代表图像该点的灰度值。
3.1.1、附件、附件1汉字拼接的模型建立:
汉字拼接的模型建立:
附件1给出的是来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),用matlab打开附件1的任意一幅图,都会得到一个198072数字矩阵。
矩阵中,我们截取两个汉字观察,图1为附件1中000图中第1行的“魂”字和第12行的“国”字,发现每个汉字形成的区域大约占据4141的位置。
图图1汉字示例图汉字示例图所以将任意两个纸条拼接后,如果拼接边缘的某一对应位置的区域能够拼接为一个大约4141的正方形区域,则理解为这一位置拼接成了汉字。
按此道理得出,两个纸条的边缘能拼接成完整字的数量,记为匹配值,匹配值除以总的字数,定为匹配度。
匹配度越大,这两个纸条越匹配。
称此方法为“边缘文字长度匹配”。
1,利用matlab调用函数(附录2)将附件1中的所有图片转化为三维数字矩阵image_1,其中image_1(i,j,k)表示附件一中第k张图的i行j列的灰度值。
任取一张图片将其灰度化,即可统计出顶端空行37,汉字总行数27,空行高度为26。
2,将得到的矩阵0-1化处理,即将灰度值在200-255的数据化为0,认为此处是空白,将不是此区间的数据全部化为1,认为此处是汉字。
分析碎片产生的矩阵,锁定汉字区域的具体位置,如图2。
Matlab中提取一张碎片的第一行的汉字区域,会得到一个4172的矩阵,将矩阵按列累加化成172的和矩阵。
据第一列的位置依次找出剩下26列汉字区域,对于每一行进行与第一行相同的处理,最后有27个172的矩阵,将它们拼接成为一个2772的矩阵,令这个矩阵为(,iijA271i721jj为整数),利用的值划分汉字区域和空白区域。
ijA将矩阵0-1化处理(0表示汉字,1代表空格)图2行距ijA此处认为矩阵有连续三个以上为1处是字间距,包含最多一个为1的数字零区域为汉字域(由于某些左右偏旁的汉字偏旁与部首之间错在空隙)。
4,统计矩阵两端汉字域的长度,方法如下见图3:
若行左端长度为411=ia,则记第一幅图第i0=Z。
若,从左到右连续三个元素相加,直到其累加411ia332=+izizizaaa为止,记下此时的i值为z,记作第i行左端长度为zZ=。
若,则记第行右端长度为172=iai0=Y。
,直到其累加若11ia,从右到左连续三个元素相加3707172=+yiyiyiaaa为止,记下此时的值为为iy,记作第i行右端长度yY=。
将每一行的左右两端的长度分别放入Z、Y矩阵。
按照以上1,2,3,4步骤进行处理,只取每一行的左右端长5,对附件1中所有的图片度。
6,建立19幅图的三维矩阵U(niZ,niY,n),niz代表第n幅图片的第i行的左端长度,y代表第n幅图片的第i行的ni将处理后得出来的右端长度,所有数据导入此矩阵之中。
7,人工干预:
由于汉字1中编号008的图片。
的左对齐特点,很容易找到整篇文章的最左列,即第一列为附件8,用niz与iy8相加,合成一列矩阵,统计矩阵中和数值大小介于间的个数占所有不零数值的比例,我们命名此比例值为匹加为零的情况,排除了汉字中间有空白的情况,更加精确41和41阀值之配度(此算法我们没有统计相。
取使得匹配度最大的n对应)图型求解:
型求解:
3程序。
的片与图008匹配。
利用此算法类推可以得到附件一的复原图。
3.1.2附件附件1汉字拼接的模汉字拼接的模具体运行过程见附录对应附件一图片的复原序列编号为:
0080140120150030100020160010040050090130180110070170000063.2.1附件2英文的模型建立:
3.2.1附件2英文的模型建立:
英文不具有汉字的规范,单词长度相差很大,并且其字母长宽都不能确定,因此无完用更为精确的方法,微观上文字每一笔画可是变,个开的两近的点同。
考虑为物状变产个面。
可根据边缘像素。
19个198072的矩阵()。
法全利用处理汉字的方法。
在此问题中采以认为连续化的面每一被切笔画边靠切割处像素分布相被一切二的体(形连续化),生的两截断积相同于是以点分布情况进行匹配。
称此方法为“边缘像素点匹配”附件二中的图像像素化处理后,得到kE191k将得到的19个矩阵0-1化处理,即将数据255替换为1,其它数据替换为0。
只抽取19个矩阵的最前列和最后列,建立E(kQ,kH)矩阵,Q、H分别存储前后列矩阵,191k。
人工干预:
根据右对齐的特点找到第一列,第一列为003,即第4幅图。
用kQ矩阵与4H矩阵分别相加,对应两个元素相等的情况和为2或2与0,统计0个172附件2文拼接的模型求解:
2附件2文拼接的模型求解:
的数之和,命此值为匹配值。
选出匹配值最大的与003匹配(类似比武招亲)。
用剩余个矩阵与新的待匹配矩阵相匹配。
依次类似得到附件二的复原图。
3.2.英3.2.英再将此图片定为待匹配矩阵,统计出附件2、此时人工干预找到最左边的纸条幅图一一与碎片3、根列为:
0110000050011、对附件二中的碎片图像像素化,程序即附件1中的汉字碎片图像像素化。
2所有纸条的左右边界像素放入qian(),hou()两个矩阵中,程序见附录3(即,碎片003),用剩余的18003进行匹配。
计算匹配度见附录3据匹配度进行拼接最终得到拼接结果,程序见附录3对应附件一图片的复原序003006002007015018009013010008012014017016004运行结果的图片编号见(fj2_pinjie_jieguo)拼成的最终图片见(附录1)3.2、问题二模型建立及求解:
的方法,错误率也相当巨大。
所以考将碎行,再行,最后列排序。
排序问题均可以利用问题一决,问点在考行处理,容易看上下位置不同,但是同行碎片的文字区域对于行排序我们利用“边缘像都是行对齐,很容易产生从行间距切开的情况,采用“边缘宽度匹配”法进行列排序。
对于英文,用matlab读取附件3中208张图片,经过程序像素化处理,得到208个18072个1801的列矩阵。
假如数据为18360,则该问题分析:
对于汉字每页纸被切为1119个碎片,我们数据量较大,虑先即使按照问题中英文碎片拼接处理片分进行排序的解办法题重落在虑分出碎片是随机切割的,所以文字区域在碎片的上下位置吻合,这样就可一分辨出来哪些碎片在同一行。
素点匹配”法。
而对于列排序,由于文字无法采用“边缘像素点匹配”法,在这里3.2.1、附件3汉字拼接模型建立:
3.2.1、附件3汉字拼接模型建立:
拼接过程分为两步:
第一步,根据上边界处连续的的空白高度大小或者不完整的文字高度大小的不同,分辨出哪些碎片位于同一行称此方法为“上界截断位置匹配”;
第二步,将位于同一行的汉字碎片利用问题1中英文碎片的“边缘像素点匹配”法进行行排序,可以,将得到的11条碎片利用“边缘宽度匹配”法进行列排序,得到附件3复原图。
第一步的数学模型:
的矩阵xD(2081x)。
将208个矩阵分别按行相加,得到208行全为空格记为0,非18360的数据记为1。
对于此矩阵从上向下统计,假如第一个数据为1,则统计连续1的个数,记为v;
假如第一个数据为0,则统计连续的0的个数,记为o。
以0为标准可确定近似等于v的碎片位于同一行。
以1为标准可确定近似等于o的碎片位于同一行,如此将其分行。
第二步的数学模型:
将得到的同一行中的19个碎片条碎片利用“边缘像素点匹配”法进行行排序,得到11行的复原图,行复原图看作最终得到附件将这1111个碎片,利用“边缘宽度匹配”法进行列排序。
3完整的复原图。
据的大小分行,见图2.1。
3.2.2附件附件3汉字拼接的模型求解:
汉字拼接的模型求解:
发现三个特殊点,即编号为071、089、014的图片上界截断位置分别为68、83、93。
观察原图图像,容易看到,这三个特殊图片包含文章的段首缩进,我们在此处人工放回对应行见表2.1:
,根据上界截断位置数表表2.1按行分组后的图片序列(同一列表示同一组,共按行分组后的图片序列(同一列表示同一组,共11组)组)303995862721269016915506106351978417551743499594611786221026310823602644331321711111031214587636486972031401091801392173477871203414611419232119207758512721811511241964013011829115937133158152198314438891919816753134182155241164510411317564157183156271296656123122176195142681661854213565131125547019918841771601879314912857732012051208816119399162137947920610714110117012105168145138802817414714317729112194150139100161982081482005517210165154163153141158752179181251841971641867186213618920219043209178611101183120496用缘点”法程序附录)一行行列序,程得到每一行排序见2.程序:
程序运行后的结果为表二和19,示组像2.3)表行排果表行排果71165“边像素匹配(见3.8给每进排运行序会的结果表2.2和图3,如下幅图只展前三的图(图2.2序结序结303995862226909150651493520920111155714470129511239851397972126907745020219095159626167124169160189612311312764811071038783142931041506917834151155196200144181131981762120311011527135187451941375453199841240319207891655737288325816171511168128946813418320814352193105264415470171185156311611799982184711002061111414220411917310911671321331881862417019117210648338020114610914815966075122197164181401181921361230162438738417419551136676251251715315812018013074563614513897166182114121177293847781751632820551911692图图2.3程序排出的行程序排出的行从程序执行后的复原图中很明显看出来每一行都有几处错误,但是相对较少,人工干预工作量很小,我们人工干预将其调整。
到此时得出11行的正确排序,采用“边缘宽度匹配”法进行列排序,程序同问题一中汉字排序的程序。
联系实际问题,此处11行完整的拼接已经得出,很容易人工排序,最后得出完整的附件3统计图。
结果如下表:
表2.3最终排序结果(同列分一组)表2.3最终排序结果(同列分一组)303995862721269016915506514935209157141471295520101112478513979774668418310320216218415968133110155631601446259112770201198115143831879336486910018174131200318182122176163811851524213658491904346973412082413193113812312517574179132203188156148761041451801996714119216111956131781386416107186512041914519411354117134151109180170962078915057164171221181211351211168989473206174587402310526137154786158102196321309991657117815318211427522917310128167211662051952108921721065933532814012088116189607544197376114612419177142303995862721269016915503.2.1、附件文拼接模型建立:
4英3.2.1、附件文拼接模型建立:
4英附4英文的问题分析:
于切文们也虑20于一行组然的“上边界宽度匹配”法不适用英文。
观发现的分中和中结我们考虑可以过图英文所位确于行片。
模型建立:
1、将208张图片用0,非空记作1.2、对于中部位置的提取,根据图像投影波峰图做出投3.对于208英文的边缘像素匹配法得到每一行的排序,得到行排序复原图。
4、最后将得到的3.2.2、附件43.2.2、附件4如图2.5所示。
2、红色线记为“匹配中部线”如匹配中部线”相近,则认为这两张图片位于同一行,根据这个方法,件对纵横的英,我考先将8张归同的分。
显汉字察英文书写为上结构下构,通片中部占得置来定位同一的图考虑中部位置就可将他们分为同一组。
matlab读取后将其矩阵0-1化,空格记作我们将0-1化后的矩阵按行求和,影波峰图1,此时可以通过找出图片中出现第一行英文的中部位置来分组。
张图片处于同一行的分组后,采用附件211个完成行排序的图片采用汉字的处理方法。
英文拼接模型求解:
1、依据投影波峰图取第一行的中心位置,果两张图片的“其中心位置的确定是根据第一簇的两个较大波峰的位置取其平均值。
2、将位于同一行的图片采用“边缘像素点匹配”法,进行排列,人工干预后得到正确排序的11行复原图。
3、对于行数巨大的图片复原,可以用“上边界宽度匹配”法进行列排序,在此只有11行,人工操作更为简单。
于是我们人工对11行进行列排序,得出正确的排序矩阵。
图图2.5字符行中心位置计算图字符行中心位置计算图具体计算过程见附件3中程序。
表2.4为拼接复原图。
表2.4附件4复原序列表2.4附件4复原序列191201861915920208701321718175148511941394121841814277图2.4字符行中心位置示意图1117010793110876095661281541962914112911649146920520019019840886313661681671013118494158121138731191741631575221131861261533633137166741251041649810553207142195188145140180782415538135168811183193641
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 国家 一等奖
![提示](https://static.bingdoc.com/images/bang_tan.gif)