碎纸片的拼接复原程序

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

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

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

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

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

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

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

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

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

）日期： 3013 年 9 月 16 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原算法及MATLAB实现摘要：对于只有纵切的情形，文章通过比较当前待拼碎片与剩余碎片的信噪比psnr[1,3,4]的值来确定两碎片是否为邻接碎片；拼接算法首先连续调用右拼函数直到拼接到原图右边界，然后连续调用左拼函数直到拼接到原图左边界，从而得到整幅复原图像；对于单面纵横交错切的情形，文章对首先采用纵切拼接算法将碎片拼接成多幅横条图片，然后将各横条图片矩阵转置[2]，再次采用纵切拼接算法拼接；两种情形的拼接，都存在人为参与；实验证明，我们的算法对纵切情形是有效的，对纵横切情况是可行的。

式） ａ ＝（ ａ ， １ ， …， 口 ： ） 与ａ ， ＝（ 日 ， 以 １一 ， ）， 我们定义相似度：
通过对图 中碎片的观察与分析 ， 我们发现这些碎片具有共同的
特征。 如图 ４ ６ ） 中碎片上被标记的部分所示。 ｌ ８ Ｏ ∑ｎ ０ ｎ 由图 ４ ６ ） 可以看出， 这些图片都是有一行 缺少英文字符 ， 使得碎片 （ ， Ｚ ） 这些特殊的５ ＇ ， － ￣ ｌ ｔ 图片都是可以人工干预处理的。 （ ２ ） 对应的模式比较异常。 在 此基 础上 考虑 碎 片拼接 过程 ， 先 对分 类 的碎 片左 右 拼接 ， 匹配 仅 其中 为临界值。若 ， ｘ ｏ 则我们认为 与 同属一类， 对于 在所在行匹配合成 。 上下匹配还要考虑行内其他元素的上下匹配。 合成 那些存在特殊情况的碎片 ， 我们在分好类的基础上 ， 再进行人工干预处 时整行都要合成。 综合考虑以上因素 ， 我们对所有可以拼接的数据进行 理。ｃ 同 类碎片拼接。 按照单面纵向拼接方法对每—类中的所有碎片进 拼接整 合 。（ 图５ ） 行拼接 ，则可得到 同一类中碎片的拼接方案 ，进而得到横 向的 “ 大碎 在这里，处理特殊碎片需遵循 的原则 ：以第二次拼接 的图片为底 片” 。ｃ Ｌ 不同类“ 大碎片” 的拼接。“ 大碎片” 为横向的， 但此 问题－ 仍 属于单 图， 剩下的 １ ８ 块依次和底图匹配 ， 匹配原则包含经此处理之后便于观 面单向的拼接问题 ， 因此可采用计算灰度值耦合度的方法进行拼接。 察整体拼接隋况， 但是拼接后在合成部分已做断开划线处理 ， 这样便于 ２ ． ２ ． ２英文单面纵横切碎片拼接。 考虑到英文的特殊 陛， 根据英文的 将剩下 的碎片进行拼接分析。 经过此次拼接过程 ， 可以观察已组合部分 书写版式原则 ， 可以将整篇文章放在带有英文四线格的底面中。 既然可 是否匹配正确 ， 若不匹配 的话 ， 可 以暂时先将那块碎片剔除， 放到第 三 以放在 四线格中， 这里我们把一行四线格看成一行， 可以确定每相邻行 部分再进行匹配组合。 碎片四边都要依次匹配 ， 匹配度最高的就是缺少 的行间距是一定的。行宽也是一定的， 考虑字母仅占有上中、 中、 中下 、 块部分。按 以上方法对样本文件 ４中的碎片进行拼接 ，结果见图 ５所 上中下等几种情况 ， 可 以确定每一个字母都是在中间有书写笔画的， 四 不 。 线格中上下行都具有英文笔画的是少数。 结束 语 基于这种考虑， 可以对每一行四线格的中间内容进行求和， 当其和 通过 研究 规 则切割 碎 纸片 的拼 接复原 问题 ，我们 针 对单 面 中英 文 的值小于某一值的时候我们忽略四线格上面和下面的内容 ，进而只考 纵向切割碎片以及单面中英文纵横双向切割碎片提 出了不同的拼接复 虑 四线 格 的中 间部 分 。 对 于那些 特殊 的碎 片 ， 我们 可采用 人 工干预 的方 原模型以及方法。该方法将一张张碎片文件转换成 了一个个像素点值 式将其挑出， 所以将英文中四线格的上半部分和下半部分的内容忽略 ， 矩阵， 对于计算机来说 ， 碎片文件 的处理就变成了矩阵集合 的操作 ； 另 可以采取中文碎片模式转换的类似方法， 从而到英文碎片的模式。 外引入欧式距离将图像的拼接转化为耦合度的计算 ；接着考虑到印刷 ３ 实验 结果 及分析 文本文件的排版特点 ， 引入模式识别的概念 ， 可 以将大量杂乱碎片进行 实验是在 Ｍｉ ｃ ｒ ｏ ｓ ｏ ｆ ｔ Ｗｉ ｎ ｄ ｏ ｗ ｓ ７系统上进行 ，内存限定是 ２ Ｇ Ｂ ， 算 分类 ， 然后逐类拼接 ， 最终将双向拼接问题转化为单 向拼接问题 ； 最后 法实现语言为 Ｍ Ａ Ｔ Ｌ Ａ Ｂ ７ ． ０版本。根据不同的样本文件使用相应的拼 所建立的模型效率好 ， 精度高， 从实验结果上可以看 出该模型的可行性 接算 法 ， 从 而得到 下面 的模拟 结果 。 和有 效 胜。 ３ ． １ 中英文单面纵切拼接实验。 样本文件 １ 和２ 分别为中英文单面 致谢 纵切碎片数据 ，其中每页纸被切为 １ ９ 条碎片 ，分别用 Ｏ ０ ０ ． ｂ ｍｐ 一 ０ １ ８ ． 感谢对此项研究工作提供基金资助的西北民族大学 中央高校基本 ｂ ｍｐ 编号命名。利用 ＭＡ Ｔ Ｌ Ａ Ｂ工具中的 自 带 函数 ｉ ｍ２ ｂ ｗ和 ｉ ｍ ｒ ｅ ａ ｄ ， 将 科研业务费专项资金 Ｎ ｏ ． ３ １ ９ ２ ０ １ ３ ０ ０ ０ ８ ） ｔ ） ２ 及西北民族大学科研创新 团 图像转化为仅包含 ０和 １ 的向量 ，接着根据中英文单面纵切算法可以 队计划 ， 同时感谢参与本论文讨论的赵习猛 、 任宗秀和王本涛。 得到碎片的耦合度矩阵 ， 由此可得样本文件 １ ， 即中文单面纵切碎片的 参考 文献 拼接 复 利ｌ 赙 为：

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.假设所有附件中给出的碎纸片图像不存在重叠部分；
2
2.假设文件中的碎纸片没有缺失； 3.假设全部碎纸片形状相同且规整。
三.符号说明及有 i 个像素点 每张碎片横向有 j 个像素点
i
j
lij
d ij
Xk
i , j 处图象的灰度值
两碎纸片边缘灰度的偏差距离 任意纸片的右特征向量 任意纸片的左特征向量 中文碎片中心位置的高度
4.3 基于模式相似性测度的偏差距离模型 模式识别中最基本的研究问题是样品与样品之间或类与类之间相似性测度 3 的问 题， 我们采用近邻准则判断两张碎纸片图像边缘灰度信息的相似性， 将任意纸片 k k n 的右特征向量 X k 作为模板，用其他每一张纸片的左特征向量 Yt 模板做比较，观察与哪 个与模板最相似，就是模板的近邻，即 t 纸片排在 k 纸片的右边。 计算模式相似性测度的距离算法有欧式距离、马氏距离、夹角余弦距离等，针对中 英文文本，我们分别测试了不同的距离算法：
次优解 次优解
最优解
最优解
绝对距离在中文识别中的效果评价图
欧式距离在中文识别中的效果评价图
图 1 纸片特征匹配中最优解区分度对比 （横坐标为进行匹配的纸片序号，纵坐标为匹配距离）
当我们对中文碎纸片进行匹配时， 采用绝对距离及欧氏距离作为距离函数都具有较 好的区分度。从图像上可以看出，采用欧式距离，使得每张纸片的期望拼接对象，与潜 在会引起匹配错误的次优匹配对象具有更大的区分度，所以，一般情况下，采用欧式距 离作为距离函数会使得匹配效果更好，有趣的是，在作英文内容的纸片匹配时，情况相 反。 因此， 在之后的算法中， 我们将更灵活的使用这两种距离函数， 而不会固定为一种。 最终得到的附录一及附录二的图片排序表格如下所示：