2013国赛B题碎纸片的拼接复原

基于最小二乘法的碎纸片拼接复原数学模型摘要首先对图片进行灰度化处理,然后转化为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该模型的优点是将图片分为具体的几类，大大的减少了工作量，缺点是针对英文文章的误差比较大。

关键字：灰度处理，图像二值化，最小二乘法，聚类分析，碎纸片拼接一、问题重述碎纸片的拼接复原技术在司法鉴定、历史文献修复与研究、军事情报获取以及故障分析等领域都有着广泛的应用。

近年来，随着德国“斯塔西”文件的恢复工程的公布，碎纸文件复原技术的研究引起了人们的广泛关注。

传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。

特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。

承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。

如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员 (打印并签名) ：1.2.3.指导教师或指导教师组负责人 (打印并签名)：（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。

以上内容请仔细核对，提交后将不再允许做任何修改。

如填写错误，论文可能被取消评奖资格。

）日期： 2013 年 9 月 10 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原模型摘要：本文针对碎纸片的拼接复原问题，提出了互相关匹配模型。

首先对附件图片数值化处理并建立矩阵；然后根据图像页边距特点定位最左边和最右边的碎片；按照每张碎片中的文字部分所在位置，提取同一行碎片，利用互相关函数横向拼合。

在第一问中，附件一、二仅作横向相关性比较即可；在第二、三问中，需要提取同一行碎片横向拼接，并将横向拼合完整的碎片进行竖向拼合，经过人工干预得到结果。

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程序，对图像进行预处理，将碎纸片转换成适合于计算机处理的数字图像形式，并对数字图像进行灰度分析，提取灰度矩阵。

基于灰度矩阵的中文碎纸片的拼接复原算法作者：王欣洁来源：《智能计算机与应用》2013年第06期摘要：主要对碎纸片的拼接复原问题进行分析，分别对仅纵切和横纵切两种切割方式建立了模型进行求解，主要思想是对碎片的灰度值矩阵进行处理，利用文字所处的位置信息、空格的分布情况、碎片的边界信息（文字的链接情况）等信息，对所给的碎纸片进行拼接复原。

对2013年“高教社杯”大学生数学建模竞赛B题附件中的中文碎片进行拼接，拼接效率高，算法可行。

关键词：灰度值矩阵；差异度量；贪心算法；相容性；边界特征中图分类号：TP312 文献标识码：A文章编号：2095-2163（2013）06-0095-040问题提出破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

为了提高拼接复原效率，人们试图利用计算机，实现碎纸片的自动拼接。

本文对2013高教社杯全国大学生数学建模竞赛B题中提出的碎纸片拼接复原问题进行研究，主要研究其中中文碎片的拼接复原。

1模型假设和符号说明研究前，需要做出如下假设：假设所给碎片均无噪声污染；各碎片之间互有关联；并且只考虑打印稿，而不涉及手写稿；同时也要假设文件中的文字行间距确定；没有相同的两个碎片；以及附件所给碎片的原文件页边距不为零。

本文中用到的符号如下：Ai：第i个碎片图像的灰度值矩阵；aikm：第i个碎片图像的灰度值矩阵中第k行m列元素；d（Ai，Aj）：两矩阵的列差异度；N1：附件1、2碎片个数；N2 ：附件3、4碎片个数；F：复原序列；d（r）（Ai，Aj）：两矩阵的行差异度；S1R：排在左侧的第R张碎片；GR：第R个相容的碎片集合2问题分析2.1仅纵切问题的分析对于仅纵切的情形，各碎片的边界特征信息（文字的链接情况）较为丰富，故可以利用边界特征进行拼接复原。

首先根据左侧的第一张碎片通常存在着左边的页边距的特点，即其灰度值矩阵中左边几列的元素均为255，从而可以找出排在左边的第一张碎片。

承诺书我们认真阅读了《全国大学生数学建模比赛章程》和《全国大学生数学建模比赛参赛规则》（以下简称为“比赛章程和参赛规则” ，可从全国大学生数学建模比赛网站下载）。

我们完好理解，在比赛开始后参赛队员不可以以任何方式（包含电话、电子邮件、网上咨询等）与队外的任何人（包含指导教师）研究、议论与赛题有关的问题。

我们知道，剽窃他人的成就是违犯比赛章程和参赛规则的，假如引用他人的成就或其余公然的资料（包含网上查到的资料），一定依据规定的参照文件的表述方式在正文引用途和参照文件中明确列出。

我们郑重承诺，严格恪守比赛章程和参赛规则，以保证比赛的公正、公正性。

若有违犯比赛章程和参赛规则的行为，我们将遇到严肃办理。

我们受权全国大学生数学建模比赛组委会，可将我们的论文以任何形式进行公然展现（包含进行网上公示，在书本、期刊和其余媒体进行正式或非正式发布等）。

我们参赛选择的题号是（从A/B/C/D 中选择一项填写）： B我们的参赛报名号为（假如赛区设置报名号的话）：所属学校（请填写完好的全名）：楚雄师范学院参赛队员(打印并署名 ) ： 1.陈志明2.施明杰3.阮秀婷指导教师或指导教师组负责人(打印并署名 )：（论文纸质版与电子版中的以上信息一定一致，不过电子版中无需署名。

以上内容请认真查对，提交后将不再同意做任何改正。

如填写错误，论文可能被撤消评奖资格。

）日期： 3013年9月16日赛区评阅编号（由赛区组委会评阅行进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅行进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国一致编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅行进行编号）：碎纸片的拼接还原算法及MATLAB实现纲要：关于只有纵切的情况，文章经过比较目前待拼碎片与节余碎片的信噪比psnr[1,3,4]的值来确立两碎片能否为毗邻碎片；拼接算法第一连续调用右拼函数直到拼接到原图右界限，而后连续调用左拼函数直到拼接到原图左界限，进而获得整幅还原图像；关于单面纵横交织切的情况，文章对第一采纳纵切拼接算法将碎片拼接成多幅横条图片，而后将各横条图片矩阵转置[2]，再次采纳纵切拼接算法拼接；两种情况的拼接，都存在人为参加；实考证明，我们的算法对纵切情况是有效的，对纵横切状况是可行的。

数学建模中的碎纸片拼接复原要点研究基于模拟退火算法与系统聚类法，文章首先依次介绍了仅纵切、既有横切又有纵切、双面打印三种情形下的碎纸片拼接复原要点，然后对全文进行了总结与展望。

标签：碎片；拼接；复原；模拟退火算法；系统聚类法碎纸片拼接复原工作在诸多领域中有着极其重要的应用，如历史文物的考证、司法鉴定以及情报获取等。

在计算机技术发展起来之后，传统的人工复原方式导致效率低下的弊端日益凸显，因此，通过数学建模的方法得到碎纸片自动拼接复原模型以提高拼接效率显得尤为重要，已有文献对此做了一些研究[1-3]。

文章以2013年全国大学生数学建模竞赛B题为例，基于模拟退火算法与系统聚类分析，依次介绍仅纵切、既有横切又有纵切、双面打印三种情形下的碎纸片拼接复原要点。

1 仅纵切的碎纸片拼接复原要点步骤6：降温。

选定降温系数θ（一般取为接近1的数）进行降温，即用θT 取代T，从而得到新的温度。

步骤7：算法终止条件。

用选定的终止温度Te，判断退火过程是否结束。

若T<Te，算法结束并输出当前的状态。

这样，由于碎纸片较大，图片信息较明显，因此不需要人工干预，复原率可达100%。

附件2中的英文图片可类似处理。

2 有横、纵切的碎纸片拼接复原要点对于既有横切又有纵切的碎纸片拼接复原，若利用上一问的方法直接对全部的209张图片进行拼接，一方面必然会导致算法运行效率大大降低；另一方面，由于区分各图片间边界差异的灰度值信息较少，易导致拼接时重码率高而复原率低。

因此，我们采用的方法是，首先提取出所有图片的行特征；然后对209张图片建立行聚类模型，对各行聚类依据上一问的方法将其中图片重排；最后对排好序的各行类似的作横向排序即可将碎片拼接复原。

具体的步骤如下：第一步，提取图片的行特征。

利用Matlab读入图片，将每张图片转化为一个180*72的灰度值矩阵；再用Matlab可计算出中文字符高为40像素点，行间距为31像素点。

第二步，建立行聚类模型。

2013年全国赛B题讨论
——姜广该题是在给出已知的碎纸片的前提下求解纸片复原图，第一题只是在纸片被单一的方向切割后的纸片复原。

可以将每条纸片横向划分为一个个的小方块，这样的目的是为了更好地采集纸片边缘是否有字迹，若有则记为1，否则记为0；然后将任意的两条纸片进行拼接，当拼接处的两条纸片为有无字迹情况相同时时记为1，否则记为0，然后对其求和，当求出的和越大时表明，两条纸片相邻的可能性越大，然后通过大量的次数拼接，找到最大的和，此时的组合就是和原纸片最接近的组合方式。

对于第二题，应该先拼接出类似于第一题的单方向切割的纸片，在按照第一题的方法求出最优的组合方式。

本题应该是属于组合优化类的问题，其中比较重要是找到衡量最优的标准，在本题中利用了0-1规划再求和的方法作为比较最优的标准。

基于数字图像的碎纸复原模型与算法--2013年全国大学生数学建模B题碎纸片的拼接复原问题
刘铁
【期刊名称】《重庆理工大学学报（自然科学版）》
【年(卷),期】2015(000)003
【摘要】传统的拼接复原工作需由人工完成，准确率较高，但效率很低。

针对该问题，借助数字图像处理技术，建立了关于图片匹配度函数的优化模型，依据穷举思想设计了求解算法，可大幅提高复原效率，但在处理复杂问题时，准确性有所下降，需要一定的人工介入。

通过对复原后图片的验证结果可知，碎纸片复原拼接模型具有可行性。

【总页数】6页(P83-88)
【作者】刘铁
【作者单位】安康学院数学与统计系数学与应用数学研究所，陕西安康 725000【正文语种】中文
【中图分类】TP393;O221
【相关文献】
1.基于数学模型的碎纸片拼接复原问题研究 [J], 周千;李文胜;朱熙
2.基于数字图像的碎纸复原模型与算法——2013年全国大学生数学建模B题碎纸片的拼接复原问题 [J], 刘铁;
3.基于SACO算法的碎纸片拼接复原模型 [J], 杨凌;王琳琳;刘冲冲;苏思美
4.基于数学模型的碎纸片拼接复原问题研究 [J], 周千;李文胜;朱熙;
5.基于量子算法的碎纸片拼接复原问题 [J], 王彦超;刘鑫磊;武良隆;刘晓东;范兴奎因版权原因，仅展示原文概要，查看原文内容请购买。

2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：重庆邮电大学参赛队员(打印并签名) ：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期： 2013 年 9 月 13 日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原摘要本文研究的是碎纸片的拼接复原问题。

由于人工做残片复原虽然准确度高，但有着效率低的缺点，仅由计算机处理复原，会由于各类条件的限制造成误差与错误，所以为了解决题目中给定的碎纸片复原问题，我们采用人机结合的方法建立碎纸片的计算机复原模型解决残片复原问题，并把计算机通过算法复原的结果优劣情况作为评价复原模型好坏的标准，通过人工后期的处理得到最佳结果。

面对题目中给出的BMP格式的黑白文字图片，我们使用matlab软件的图像处理功能把图像转化为矩阵形式，矩阵中的元素表示图中该位置像素的灰度值，再对元素进行二值化处理得到新的矩阵。

题目每一个附件中的碎纸片均为来自同一页的文件，所以不需考虑残片中含有未知纸张的残片以及残片中不会含有公共部分。

承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。

如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：吉林医药学院参赛队员(打印并签名)：1.徐曦2.贾赟光3.武松浩指导教师或指导教师组负责人(打印并签名)：吴希（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。

以上内容请仔细核对，提交后将不再允许做任何修改。

如填写错误，论文可能被取消评奖资格。

）日期：2013年09月16日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原摘要本文通过对图片像素点灰度值的分析，研究碎纸片的拼接复原。

针对问题一，利用Matlab 软件求出附件1、2图片的像素点灰度值分布矩阵，提取每张图片的左右边缘的灰度值向量，根据图片像素点灰度值的不同，并据此建立spearman 相关系数模型[1]2361i s d n nρ=--∑利用SPSS 对边缘灰度值进行相关性分析，根据相关系数的大小得到两两匹配的纸片对，采用人工干预的方式将纸片左右边缘逐次进行拼接，得到附件1、附件2图片拼接的顺序，具体结果见表3、表5：表3附件1拼接顺序表5附件2拼接顺序针对问题二，在问题一的基础上，利用Matlab 软件求出附件3、4图片边缘像素点灰度值分布矩阵，提取每张图片的上、下、左、右边缘的灰度值向量，由于初始数据庞大，运用逐一比较像素点灰度值的思想设计算法，结合C 语言设计程序[2]，实现快速拼接功能，得到附件3、附件4图片拼接的顺序，见正文表6、表7，此处列举部分数据，如下所示：针对问题三，在问题二的基础上，利用Matlab 软件求出附件5图片边缘像素点灰度值分布矩阵，提取每张图片的上、下、左、右边缘的灰度值集合，从解决问题的实际角度出发，对于双面打印文件，运用特殊点灰度值比较法设计算法，结合C 语言设计程序，实现拼接功能，得到附件5图片拼接顺序，见正文表8、表9。

碎纸片拼接复原的数学方法
薛毅
【期刊名称】《数学建模及其应用》
【年(卷),期】2013(002)005
【摘要】就2013年“高教社杯”全国大学生数学建模竞赛B题“碎纸片的拼接复原”提出了一种用“纯数学手段”完成拼接复原的方法,可概括为3步:TSP,聚类分析和双面信息的利用.根据题目要求给出了3个步骤中人工干预的方式与时间节点.
【总页数】5页(P9-13)
【作者】薛毅
【作者单位】北京工业大学应用数理学院,北京100124
【正文语种】中文
【中图分类】O221.7;O212.4;TP391.41
【相关文献】
1.基于数字图像的碎纸复原模型与算法--2013年全国大学生数学建模B题碎纸片的拼接复原问题 [J], 刘铁
2.基于数字图像的碎纸复原模型与算法——2013年全国大学生数学建模B题碎纸片的拼接复原问题 [J], 刘铁;
3.碎纸片拼接复原的数学方法 [J], 薛毅;
4.基于MATLAB的碎纸片拼接复原技术研究 [J], 唐巧玲;陈佳
5.基于量子算法的碎纸片拼接复原问题 [J], 王彦超;刘鑫磊;武良隆;刘晓东;范兴奎
因版权原因，仅展示原文概要，查看原文内容请购买。

承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括、电子、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。

如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：西华大学参赛队员(打印并签名) ：1. 尚安2. 洋3. 叶军指导教师或指导教师组负责人(打印并签名)：（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。

以上容请仔细核对，提交后将不再允许做任何修改。

如填写错误，论文可能被取消评奖资格。

）日期：2013 年09 月15 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原摘要本文通过分析题中相关要求及条件，建立数学模型解决了各种规则碎纸片的拼接复原问题。

针对问题一，首先将题中所给图片导入matlab软件，利用imread函数得到每图片的文字灰度像素矩阵，再取出所有矩阵左、右列，建立像素绝对差拟配模型，得到拟配程度最高的两幅图片，进行拼接，出现不合理拼接情况则进行人工干预，最后重复上述过程，完成全部拼接并导出图像。

2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题.我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性.如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理.我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）.我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（即电子文件名）：B0813所属学校（请填写完整的全名）：广西师范大学参赛队员 (打印并签名) ：1.杨凯2.周志恒3.陈锦丽指导教师或指导教师组负责人 (打印并签名)：日期2013年9月16日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国评阅编号（由全国组委会评阅前进行编号）：纸片的拼接复原摘要碎纸自动拼接复原技术现今可以归结到计算机视觉和模式识别领域内的问题，它在司法物证复原、历史文献修复等重要领域都起着重要的作用.本文主要分析了文字的拼接技术，通过研究碎纸片内的像素矩阵和文字行特征特点，提出了基于文字图形的半自动拼接算法.对于问题1中的这种单面的仅纵向切碎的文字文件，通过Matlab 程序分析附件中每个碎片的像素矩阵，确定拼接的第一个碎片（自左向右拼接），再根据两列像素矩阵的像素绝对差的和来确定相邻碎片的编号，从而得到完整的拼接方案.例如文字文件的拼接结果如下表所示：对于问题2中既纵切又横切的碎纸片，在问题一的基础上，充分考虑横向匹配和纵向匹配的要求，运用Matlab程序筛选最左列碎片成分，经过适当的人工干预根据文字行特征将所剩碎片进行行分类，大大提高拼接效率，得到意想的效果.例如文字文件的拼接结果如下表所示：对于问题3，在前两问的基础上，建立筛选附件5碎片图的优化模型，通过Matlab编程，使用附件给的418张碎纸片图，将最终复原图划分为11个碎片横条区域，降低了拼接复原难度以及所需时间.最终复原结果见附录.最后，分析了所建立模型的优缺点以及推广，评价了文字碎纸片的拼接和复原实际情况.关键词文字图形碎片半自动拼接像素灰度 MATLAB程序一问题的重述碎纸自动拼接复原技术是计算机视觉和模式识别领域内的问题.它在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统意义上的拼接复原工作需由人工完成，准确率较高，但效率非常低，特别是当碎片数量巨大时，人工拼接很难在短时间内完成任务.随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率.本文主要讨论：首先，对于给定的来自同一页单面印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，同时对题目中的附件1和附件2给出的中、英文各一页文件的碎片数据进行拼接复原.其次，对于同样是单面印刷文件既纵切又横切的情形，在第一问的基础上设计出碎纸片拼接复原模型和算法，对附件3和附件4给出的中、英文各一页文件的碎片数据进行拼接复原.最后，联系现实中的情况，对还有可能出现双面打印文件的碎纸片进行拼接复原.在前两问的基础上，设计出相应的碎纸片拼接复原模型与算法，并附件5中双面打印文件的碎片数据给出拼接复原结果.在上述复原过程中，由于计算机的识别可能会出现偏差，那么就需要在拼接过程中进行必要的人工干预，在适当的时候我们会用干预的方式给出复原过程.并最终以图片形式及表格形式完成给出复原结果.具体结果在附件中给出.二问题的分析破碎文件的复原，最直接及最精确的就是人工拼接，但是当碎片的数量巨大时，人工方式就显得效率低下，所以就考虑把破碎文件运用计算机技术来帮助人们进行破碎文件的复原，让计算机在这个过程中发挥主要作用，但是用计算机处理，又不是百分之一百完美，因此在适当的时候也需要进行人工干预.本文运用碎纸片的自动拼接技术，对每个附件给出的碎片文字材料进行分析，尽可能减少人工干预，本文给出的图像数据均为形状、大小一样的规则长四边形，由于形状的一致性，所以在拼接时如果只考虑利用碎片的边界特征，直接拼接，显然效果不理想.考虑到使用计算机的拼接过程应该与人工拼接过程是相类似的，即拼接时不但考虑碎片边缘是否匹配，还要判断碎片内的字迹断线和文字内容是否匹配.然而根据现在已有的技术，实现计算机智能识字是几乎不可能的.但是我们可以获取图片所提供的像素信息，将其转化为矩阵，根据图像的像素矩阵值进行碎片拼接，用计算机去运行处理数据，可以想象其拼接效率无疑比单纯利用边界特征的方法好很多.以下是对各问题的详细分析：针对问题1，对附件1和附件2提供的数据，每页纸被切为19条碎片，对于这种单面的仅纵向切碎的文字文件，我们仅考虑碎片左右两侧的拼接.首先，在转换中发现，像素图片矩阵的值是介于0到255之间的一个像素矩阵，随着像素矩阵值的增加，我们发现随着像素矩阵数值的增大，所代表的区域越来越浅，最后255这个数值，代表了白色区域.其次，对于问题1中的附件1和附件2图片，由于仅纵向切碎的文字文件，仅考虑碎片左右两侧的拼接.需运用Matlab程序分别对附件1和附件2中的19个碎片计算其像素矩阵，将每个附件中19条图像转换的像素矩阵，筛选出每个像素矩阵的第一列像素矩阵成19个198072值，然后运用Excel软件统计各列像素值等于255的个数，可以粗略的认为所含255个数最多的列所对应的碎片则是拼接顺序中的左边第一条（如果有必要进行人工干预，但是本文第一问没有进行人工干预）.接下来从左边开始选取第二条碎片，关于第二条待匹配的碎片，用先确定的第一条像素矩阵的最后一列，对其进行数值求和，然后将剩下的18个像素矩阵中的第一列和最后一列矩阵进行分别求和.将首先确定的最左边第一条矩阵中的最后一列矩阵与求出的18个像素矩阵中的第一列矩阵分别进行做差，然后将差值取绝对值，这样就可以得出，如果差值越小，其重叠的相似度也应该相对越高.这样可筛选得出相似度较高的碎片，即与第一个碎片相匹配，该碎片位于拼接顺序的第二条，确定第二条后，再用第二条的最右边矩阵并以此类推，逐一从左到右查询碎片，直到碎纸片的复原结果.针对问题2，在问题1的基础上，继续对所给的附件3和附件4进行分析.针对附件3和附件4的特点，附件3和附件4给出了碎片既横切又纵切的中英文图像，那么在拼接时就有两方面的考虑，既要满足横向匹配，又要满足纵向匹配.那么我们就考虑在问题解决中可以分为两步进行，首先考虑横向拼接，一旦横向拼接完成了，纵向拼接自然相对就好解决了.根据碎片像素矩阵特征和行距特征将其分类，再结合问题1的方法将各类碎片进行匹配，即可得到11个碎片横条.接着考虑纵向拼接，使用Matlab程序对得到的新的横条碎片进行像素分析，比较像素矩阵中第一行数据中255的个数，个数最多的碎片即是原文件的第一行，依次类推，同样的方法即可知道具体的排列顺序，从而得到碎纸片复原的结果.针对问题3，在问题1和问题2的基础上，继续对所给的附件5进行分析.实际生活中存在很多双面打印的文件，这些双面文件的碎纸片混合在了一起，当对其进行拼接复原时，首先要判断同一面的文字碎片，然后再进行拼接.附件5给出了碎片既横切又纵切的英文文字图像，那么在拼接时依旧有两方面的考虑，既要满足横向匹配，又要满足纵向匹配.首先考虑横向拼接，转换得到180x72的像素矩阵，这些是介于0到255之间的一个像素矩阵，随着图片的增加，相应的增多转换得到的像素矩阵，在问题2的基础上继续进行检验所给的碎纸片图，运用Matlab读取了418张碎片图后，将每张碎片转换得的像素矩阵的第一列以及最后一列各自取出，通过程序进行验证，可以算出匹配度高的相邻碎片，此时进行一次人工干预，拼接出位于同一行的碎片横条；接着考虑纵向拼接，运用Matlab程序对得到的新的横条碎片进行像素分析的提取，配准各个横条的像素矩阵的第一行与最后一行的相关度，综合分析碎纸片上英文之间的行距，进而确定拼接的碎片横条位于哪一行，得到最终的复原结果.综上所述，以上三个问题的解决流程可用下面的流程图表示：图2 问题解决流程图三模型假设准备与符号说明3.1模型的假设1、假设碎纸机把一页印刷文字文件碎成形状规则，大小一样的碎片，看做形状、大小相同的长方形.2、在碎纸过程中，只考虑文字被切开，不考虑文字笔画的丢失、碎片添加的任何痕迹等.3、假设文档碎片的文字的方向已经确定（按照阅读标准确定，从左向左右，自上而下），不考虑碎片图像的旋转问题.4、图片在复原的过程中，不考虑图片像素的改变，只考虑碎片相对应的固定像素值的匹配问题.3.2 模型准备不规则几何文档碎纸片计算机拼接的方法一般利用碎片边缘的尖角特征、尖点特征、面积特征等一些几何特征，搜索与之匹配的相邻碎纸片进行拼接，这种基于边界的几何特征的拼接方法并不适用于边缘的形状相似的碎纸片.对于这类边缘相似的碎纸片的拼接问题，理想的计算机拼接的过程与人工拼接的过程类似，即拼接时不仅要考虑拼接碎纸片的边缘是否匹配，还要判断碎纸片内的文字字迹断线或文字内容是否匹配，但是由于理论和技术的限制，让计算机具备类似于人的的那种识别碎纸片边缘字迹断线、以及理解碎纸片内文字图像的含义的智能几乎是不太可能的.但是利用现在已有的技术，完全可以获取到碎纸片文字所在行的几何特征信息，如文字行的行高及间距等信息.如果利用这些信息进行碎纸片拼接，其拼接的效率就比单纯利用边界的几何特征方法更好.根据本文题设要求，经考虑分析，本文采取转换矩阵数组元素拼接的技术对破碎的文字文档进行拼接复原.由于计算机数字分析图像能力方面的存在一定的缺陷，让计算机对碎纸片进行完全意义上的自动化拼接页几乎是不太可能，为保证其拼接的准确性，需要在拼接的过程中加入一定的人工干扰过程.一般来说，先利用计算机搜索出于目标碎纸片相匹配的未拼接碎纸片，并根据匹配的程度按顺序到得待选的碎纸片，然后人为地进一步分析结果进行舍弃或拼接待选碎纸片[3].一页文字文件的碎片拼接复原相当于全景图的生成技术，而相邻图像的配准及拼接是该技术的关键.图像的拼技术一般分为基于图像特征的方法和基于图像灰度的方法.特征提取的方法通常涉及大量的几何与图像形态学的计算，计算量大，没有一般的模型可遵循，但需要针对不同的应用场景来选择各自适合的特征，所提取的图像特征包括更高层的语义信息，基于特征的方法具有尺度不变性和放射不变形.然而基于图像灰度的拼接方法简单简单易行，并且其数字统计模型以及收敛速度、定位精度等均具有定量的分析和研究结果，此类方法得到了广泛的应用.本文中的文字图像中文字区域的文字结构相对单一，并可能出现相同或相似的字符，因此文字容易出现匹配出现误差.对于文字左右拼接的情况，可以对图片中划分的每行文字进行分析处理，通过提取文字图片的边缘像素矩阵，得到文字出现在图片边缘的那一行高，进一步对一行行的文字拼接复原，这也有利于获取更精确的配准结果.基于文字的图像灰度的方法不需要提取文字图像的相应的特征，只以两幅图像相连接部分对应的像素灰度的相似性准则来寻找图像的匹配位置.待匹配的图像，首先求出图像中最左边一列的像素矩阵值之和，和最右边一列像素矩阵之和。