2013年数学建模B题碎纸片的拼接复原
- 格式:pdf
- 大小:1.46 MB
- 文档页数:31
基于最小二乘法的碎纸片拼接复原数学模型摘要首先对图片进行灰度化处理,然后转化为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该模型的优点是将图片分为具体的几类,大大的减少了工作量,缺点是针对英文文章的误差比较大。
关键字:灰度处理,图像二值化,最小二乘法,聚类分析,碎纸片拼接一、问题重述碎纸片的拼接复原技术在司法鉴定、历史文献修复与研究、军事情报获取以及故障分析等领域都有着广泛的应用。
近年来,随着德国“斯塔西”文件的恢复工程的公布,碎纸文件复原技术的研究引起了人们的广泛关注。
传统上,拼接复原工作需由人工完成,准确率较高,但效率很低。
特别是当碎片数量巨大,人工拼接很难在短时间内完成任务。
碎纸片的拼接复原 2013全国数学建模竞赛——碎纸片拼接复原导读:就爱阅读网友为您分享以下“2013全国数学建模竞赛——碎纸片拼接复原”的资讯,希望对您有所帮助,感谢您对的支持!2013高教社杯全国大学生数学建模竞赛重庆工商大学姜木北小组作品编号专用页赛区评阅编号(由赛区组委会评阅前进行编号):赛区评阅记录(可供赛区评阅时使用):全国统一编号(由赛区组委会送交全国前编号):全国评阅编号(由全国组委会评阅前进行编号)碎纸片的拼接复原摘要目前,“碎片拼接复原”技术在司法物证复原、历史文物修复及社会生活各项领域扮演着重要角色,对于碎片数量特别巨大而人工又难以在短时间内完成碎片拼接时,要找到一种高效快捷的自动拼接方法已变得尤为重要。
本文针对只有中英文的碎片拼接问题,综合分析了从单一的纵切到纵横切以及纵横切双面碎片这三个不同的情况,提出了碎片拼接复原的解决方案.在问题一中,对于仅有“纵切”且数量相对较少的碎纸片,我们基于边缘去噪和采用构建碎纸图片的左右边缘二值矩阵提取相似度分析的方法,再通过两张图片左右相似度匹配排序,得到附件1和附件2中的碎纸排序(见表2和表3),并运用Matlab的图像处理工具箱,按排列顺序导入碎纸片得到相应拼接结果(见附录附件一).在问题二中,由于碎纸片数量相对较多,同时存在横切和纵切的情况,在问题一的基础上增加了碎纸片的上下边缘相似度匹配。
在进行人工干预,找到第一张起始碎纸片作为匹配起点后,我们基于索贝尔算子的原理,对碎纸片灰度值进行边缘相似度的旋转检测和比较匹配,最后进行二叉树搜索排序(见表4和表5)。
对附件3和4的碎纸图片拼接出的结果详见附录中的附件二.在问题三中,由于碎纸片是两面的并且碎纸片数量更多,若采用第二问的求解方案则加大了求解难度同时也存在较大误差。
因此,我们基于蚁群算法(ACA)的SIFT特征点匹配原理来求解。
先提取碎纸图片特征点,然后基于蚁群算法的最优化快速比对匹配,最后基于ACA的搜索排序对碎纸片拼接。
碎纸片的拼接复原
摘要
碎纸片的拼接复原主要采集碎纸片边缘信息的挖掘,利用碎纸片边缘构造特征因子,利用特征因子来描述碎片边缘的行列特征,然后根据碎纸片边缘提供的信息进行调整,并对贪心算法进行改进,找到有效克服局部最优解的拼接算法。
问题1:首先,纸片采取的是纵向切割,利用matlab软件对纸片左右边缘提取1980×2个像素点,直接利用边缘像素点的差异性来定义匹配度。
然后用改进贪心算法寻找最短路径,最后碎片复原时进行部分人工干预,成功复原附件1和附件2的碎纸片。
问题2:对附件3,4中的张碎片边缘提取180×72个像素点,对此,为了提高碎纸片的匹配精度,本文引入评估函数区别对待黑白区内的不同匹配,借助评估函数重新定义匹配度,使得较少的边缘信息将碎片分为19类,同时采用问题1与改进的贪心算法寻找捷径,将这一类的碎片复原,其他18类同理。
最后整理剩下的19类的碎片,采取好19类上下边缘的灰度矩阵和行距特征,利用以上的特征,引用人机交互拼接方法,成功复原附件3,附件4的碎纸片。
问题3:
关键词:特征因子,灰度矩阵,贪心算法,拼接,人工干预
问题的重述与分析。
2013高教社杯全国大学生数学建模竞赛B题碎纸片的拼接复原首先分析问题:对于第一问分析如下对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片拼接复原模型和算法,并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预,请写出干预方式及干预的时间节点。
求matlab图像拼接程序clear;I=imread('xingshi32.bmp');if(isgray(I)==0)disp('请输入灰度图像,本程序用来处理128 *128的灰度图像!');elseif (size(I)~=[128,128])disp('图像的大小不合程序要求!');elseH.color=[1 1 1]; %设置白的画布figure(H);imshow(I);title('原图像');zeroImage=repmat(uint8(0),[128 128]);figure(H); %为分裂合并后显示的图设置画布meansImageHandle=imshow(zeroImage);title('块均值图像');%%%%%设置分裂后图像的大小由于本图采用了128像素的图blockSize=[128 64 32 16 8 4 2];%%设置一个S稀疏矩阵用于四叉树分解后存诸数据S=uint8(128);S(128,128)=0;threshold=input('请输入分裂的阈值(0--1):');%阈值threshold=round(255*threshold);M=128;dim=128;%%%%%%%%%%%%%%%%% 分裂主程序%%%%%%%%%%%while (dim>1)[M,N] = size(I);Sind = find(S == dim);numBlocks = length(Sind);if (numBlocks == 0)%已完成break;endrows = (0:dim-1)';cols = 0:M:(dim-1)*M;rows = rows(:,ones(1,dim));cols = cols(ones(dim,1),:);ind = rows + cols;ind = ind(:);tmp = repmat(Sind', length(ind), 1);ind = ind(:, ones(1,numBlocks));ind = ind + tmp;blockValues= I(ind);blockValues = reshape(blockValues, [dim dim numBlocks]);if(isempty(Sind))%已完成break;end[i,j]=find(S);set(meansImageHandle,'CData',ComputeMeans(I,S));maxValues=max(max(blockValues,[],1),[],2);minValues=min(min(blockValues,[],1),[],2);doSplit=(double(maxValues)-double(minValues))>threshold;dim=dim/2;Sind=Sind(doSplit);Sind=[Sind;Sind+dim;(Sind+M*dim);(Sind+(M+1)*dim)];S(Sind)=dim;end对于第二问于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
精心整理碎纸片的拼接复原【摘要】:碎纸片拼接技术是数字图像处理领域的一个重要研究方向,把计算机视觉和程序识别应用于碎纸片的复原,在考古、司法、古生物学等方面具有广泛的应用,具有重要的现实意义。
本文主要结合各种实际应用背景,针对碎纸机绞碎的碎纸片,基于计算机辅助对碎纸片进行自动拼接复原研究。
针对问题1,依据图像预处理理论,通过matlab程序处理图像,将图像转化成适合于计算机处理的数字图像,进行灰度分析,提取灰度矩阵。
对于仅纵切的碎纸片,根据矩阵的行提取理论,将。
建中的任一列与矩阵值,序列号。
将程序进行循环操作,得到最终的碎片自动拼接结果。
、;分别作为新生成的矩阵、。
,将矩阵中的任一列分别与矩阵中每一列代入模型,所得p值对应的值即为横排序;将矩阵中的任一行分别于矩阵中的任一行代入模型,所得q值对应的值即为列排序。
循环进行此程序,得计算机的最终运行结果。
所得结果有少许误差,需人工调制,更正排列顺序,得最终拼接结果。
针对问题3,基于碎纸片的文字行列特征,采用遗传算法,将所有的可能性拼接进行比较,进行择优性选择。
反面的排序结果用于对正面排序的检验,发现结果有误差,此时,进行人工干预,调换碎纸片的排序。
【关键词】:灰度矩阵欧式距离图像匹配自动拼接人工干预一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。
传统上,大量的纸质物证复原工作都是以人工的方式完成的,准确率较高,但效率很低。
特别是当碎片数量巨大,人工拼接不但耗费大量的人力、物力,而且还可能对物证造成一定的损坏。
随着计算机技术的发展,人们试图把计算机视觉和模式识别应用于碎纸片复原,开展对碎纸片自动拼接技术的研究,以提高拼接复原效率。
试讨论一下问题,并根据题目要求建立相应的模型和算法:、附件4(1)(2)(3)(4)纸片的自动拼接。
问题1:根据图像预处理理论,通过程序语言将图像导入matlab程序,对图像进行预处理,将碎纸片转换成适合于计算机处理的数字图像形式,并对数字图像进行灰度分析,提取灰度矩阵。
数学建模中的碎纸片拼接复原要点研究基于模拟退火算法与系统聚类法,文章首先依次介绍了仅纵切、既有横切又有纵切、双面打印三种情形下的碎纸片拼接复原要点,然后对全文进行了总结与展望。
标签:碎片;拼接;复原;模拟退火算法;系统聚类法碎纸片拼接复原工作在诸多领域中有着极其重要的应用,如历史文物的考证、司法鉴定以及情报获取等。
在计算机技术发展起来之后,传统的人工复原方式导致效率低下的弊端日益凸显,因此,通过数学建模的方法得到碎纸片自动拼接复原模型以提高拼接效率显得尤为重要,已有文献对此做了一些研究[1-3]。
文章以2013年全国大学生数学建模竞赛B题为例,基于模拟退火算法与系统聚类分析,依次介绍仅纵切、既有横切又有纵切、双面打印三种情形下的碎纸片拼接复原要点。
1 仅纵切的碎纸片拼接复原要点步骤6:降温。
选定降温系数θ(一般取为接近1的数)进行降温,即用θT 取代T,从而得到新的温度。
步骤7:算法终止条件。
用选定的终止温度Te,判断退火过程是否结束。
若T<Te,算法结束并输出当前的状态。
这样,由于碎纸片较大,图片信息较明显,因此不需要人工干预,复原率可达100%。
附件2中的英文图片可类似处理。
2 有横、纵切的碎纸片拼接复原要点对于既有横切又有纵切的碎纸片拼接复原,若利用上一问的方法直接对全部的209张图片进行拼接,一方面必然会导致算法运行效率大大降低;另一方面,由于区分各图片间边界差异的灰度值信息较少,易导致拼接时重码率高而复原率低。
因此,我们采用的方法是,首先提取出所有图片的行特征;然后对209张图片建立行聚类模型,对各行聚类依据上一问的方法将其中图片重排;最后对排好序的各行类似的作横向排序即可将碎片拼接复原。
具体的步骤如下:第一步,提取图片的行特征。
利用Matlab读入图片,将每张图片转化为一个180*72的灰度值矩阵;再用Matlab可计算出中文字符高为40像素点,行间距为31像素点。
第二步,建立行聚类模型。