当前位置：文档之家 › 碎纸片的拼接复原问题

碎纸片的拼接复原问题

  • 格式：doc
  • 大小：1.07 MB
  • 文档页数：22

2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原问题摘要破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

本文针对已给图像先进行了图片灰度二值化处理得到碎纸片的像素矩阵，提取碎纸片的边缘像素矩阵，对边缘矩阵进行相似度分析，相似度的度量采用向量距离平方和最小化，在相似度度量中设置阈值、对相近相似度的候选纸片进行人工干预、对数据量较大的附件，采用文本特征，如页边距、行距进行筛选，降低计算量，提高计算精度。

使用Matlab软件编程实现了上述算法，在对附件的拼接中通过少量的人工干预，可实现纸片的完整拼接，效果较好。

关键词：相似度；文字特征；碎纸片拼接；Matlab；1 问题重述1.1 问题的描述设计一个碎纸片的自动拼接模型，以提高碎纸片的拼接复原效率。

1.2 问题的要求（1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

复原结果以图片形式及表格形式表达。

（2）对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

复原结果表达要求同上。

（3）从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。

附件5给出的是一页英文印刷文字双面打印文件的碎片数据。

请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。

1.3 问题的分析对破碎文件这类边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎纸片内的字迹断线或碎片内的文字内容是否匹配，然而由于理论和技术的限制，让计算机具备类似人那种识别破碎边缘地字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。

但是分析了基于几何特征的碎纸片自动拼接方法的缺点,研究了碎纸片内文字行特征以及行特征获取方法。

利用这些信息进行拼接，其拼接效率无疑比单纯利用边界几何特征方法要好些。

另一方面由于计算机数字分析图像能力的缺陷，让计算机对碎片进行完全意义上的自动化拼接也几乎不大可能，这就需要我们在拼接过程加入人工干扰过程，对一些碎片进一步分析结果舍弃或拼接待选。

2 模型假设和符号系统2.1 模型假设（1）假设问题中所给的碎片图像边缘没有破损； （2）假设附件中每张碎片的形状和大小都一致；（3）假设附件中的每张碎片中的字体都清楚且没有重叠部分； 2.2 符号系统i A :表示附件1中图像进行二值化处理得到的第i 个数据矩阵； i B ：表示附件2中图像进行二值化处理得到的第i 个数据矩阵； i C ：表示附件3中图像进行二值化处理得到的第i 个数据矩阵； i d :表示附件3中第i 次运行得到的数据矩阵；ij d ：表示附件3中第i 次运行第j 次人工干预得到的数据矩阵；E:表示附件5中图片009.bmp 的运行结果； K ：表示附件1复原后的碎纸片排列序号； Q ：表示附件2复原后的碎纸片排列序号。

3 模型的建立及求解3.1 模型一的建立 3.1.1 模型一的概要将附件1～2中碎纸片进行图片灰度二值化处理得到碎纸片的像素矩阵，提取碎纸片的边缘像素矩阵，对各矩阵数据进行人工遍历搜索，提取出文件左右两边的碎纸片。

对边缘矩阵进行相似度分析，相似度的度量采用向量距离平方和最小化。

利用Matlab 编程对各附件的碎纸片图像进行自动拼接。

3.1.2 模型一的分析（1）对于附件1步骤1：将附件1中碎纸片图像利用Matlab 软件进行二值化处理（源程序代码见附录1代码1），得到数据矩阵191~A A ；步骤2：对数据矩阵191~A A 的数据进行人工遍历搜索可看出矩阵9A 的前几列数据全为255，矩阵7A 的后几列数据全为255（在像素矩阵中255代表白色，0代表黑色），所以附件1中i9(008.bmp)为复原后的第一张图片，i7(006.bmp)为复原后的最后一张图片；步骤3：将i9(008.bmp)和i7(006.bmp)提取出来，用第一张图片右边缘像素值与剩余碎纸片的左边缘像素值依次进行差的平方，求相似度，得到最优解。

编写程序（源程序代码见附录1代码2），利用Matlab 软件实行碎纸片的自动拼接得到复原后碎纸片排列序号K 。

（2）对于附件2步骤1：将附件2中碎纸片图像利用Matlab 软件进行二值化处理（源程序代码见附录代码1），得到数据矩阵191~B B ；步骤2：对数据矩阵的数据191~B B 进行人工遍历搜索可看出矩阵4B 的前几列数据全为255，矩阵5B 的后几列数据全为255（在像素矩阵中255代表白色，0代表黑色），所以附件1中Name4(003.bmp)为复原后的第一张图片，Name5(004.bmp)为复原后的最后一张图片；步骤3：将Name4(003.bmp)和Name5(004.bmp)提取出来，在附件一的基础上根据碎片的文字特征即页边距进行分析，编写程序（源程序代码见附录1代码3），利用Matlab 软件实行碎纸片的自动拼接得到复原后碎纸片排列序号Q 。

3.1.3 模型一的求解附件1的求解（1）运行自动拼接源程序代码，得到K =[13 11 14 4 9 3 15 2 5 6 8 12 17 10 7 16 1]（2）第一张图为I9，最后一张图为I7，在数组K 中1～6则为图i1～i6，7为图I8，8～16则为图I10～I18,在Matlab 中运行tu=[i9 i15 i13 i16 i4 i11 i3 i17 i2 i5 i6 i10 i14 i19 i12 i8 i18 i1 i7]; imshow(tu)即可得到拼接复原图见附录图1，根据运行结果得到复员后碎纸片的排列序号见表1。

附件2的求解（1）运行自动拼接源程序代码，得到 Q =[5 3 6 14 17 10 1 4 2 8 12 9 7 11 13 16 15]（2）第一张图为Name 4，最后一张图为B5，在数组Q 中1～3则为图B1～B3，4～16则为图B6～B18,在Matlab 中运行tu=[Name4 Name7 Name3 Name8 Name16 Name19 Name12 Name1 Name6 Name2 Name10 Name14 Name11 Name9 Name13 Name15 Name18 Name17 Name5];imshow(tu)即可得到拼接复原图见附录2图2，根据运行结果得到复员后碎纸片的排列序号见表2。

3.2 模型二的建立 3.2.1 模型二的概要对于附件3～4中图片需要进行横纵切割，它的碎片复原拼接需要先把一部分图片利用Matlab 编程拼接成像附件1中那种类似的图片，然后利用文字特征中的左边距再在模型一的基础上设置相似度度量阈值，对相近相似度的候选纸片进行人工干预，从而进行碎纸片的拼接复原。

3.2.2 模型二的分析附件3的分析步骤1：同模型一一样，对所有图片进行二值化处理得到得到数据矩阵1C ～209C ； 步骤2：对数据矩阵1C ～209C 进行人工遍历搜索,由文字边缘像素矩阵两图片的相似度和页边距的特征，可得到复原后的第一列的小图片；步骤3：对得到的第一列的所有图片编写程序在Matlab 软件中拼接成12个类似附件1的长条图片；步骤4：对步骤3得到的图片利用模型一的模式进行碎纸片的拼接复原。

附件4的求解过程同附件3 3.2.3 模型二的求解附件3的求解自动拼接源程序代码见附录代码4 （1）第一次运行将代码4中的n取15运行的结果为：d=[126 130 136 144 169 129 4 160 83 200]1第一次人工干预点：136运行结果为：d=[129 4 160 83 200 136 13 74 161]11第二次人工干预点：204运行结果为：d=[40 32 52 108 116]12第三次人工干预点：177，可得到附录2图3。

（2）第二次运行将代码4中的n取8运行的结果为：d=[126 130 136 139 144 169]2第一次人工干预点：139，可得到附录2图4。

（3）第三次运行将代码4中的n取62运行的结果为：d=[126 130 136 144 169 20 79]3第一次人工干预点：68可得运行结果：d=[126 136 144 147 169 20 79 68 70 100 163 97 132 80]31第二次人工干预：64，可得附录2图5。

（4）第四次运行将代码4中的n取126运行的结果为：d=[126 130 136 144 169 14]4人工干预：183，可得附录2图6。

（5）第五次运行将代码4中的n取50运行的结果为：d=[126 130 136 144 169 55 66]5第一次人工干预点：144运行结果：d=[126 130 136 144 169 55 66 144 187 3 58 193 179 119 191 96] 51第二次人工干预点：12，可得附录2图7。

（6）第六次运行将代码4中的n取50运行的结果为：d=[126 130 136 144 169 55 66 95 35 85 12 23 130 29 92 189 142]6人工干预点56，可得附录2图8。

（7）对于剩余小图片因为部分相似度很高，需多次进行人工干预。

进行人工干预的得到附录2图9～图13。

把附录2图3～图13运用模型一的模式进行调试得到附件3碎纸片的拼接复原图（见附录2图14），根据运行结果得到复原后碎纸片的排列序号见表3。

接复原总图见附录2图15，复原后碎纸片的排列序号见表4。

15 9 13900112906313815305303812312175085051618709720303102 0 04110811613607303620713501507604319904517307916117914320 8 02100704906111903314216806216905419213311818916219711207 0 084060140681741371950080471721560960230991220918510913 2 181095069167163166188111144206003130340131102502717817 1 0420662050115707414508313405501805603501600918315204408 1 0771282013105212514193087089048072012177124001021153.3 模型三的建立3.3.1 模型三的概要附件5中碎纸片的拼接复原要求双面拼接，且碎纸片的图片是横纵切割的。

合集下载

碎纸片拼接复原的数学方法

碎纸片拼接复原的数学方法

碎纸片拼接复原的数学方法拼图游戏，一种看似简单却富含深度的游戏，给人们带来了无穷的乐趣。

然而，大家是否想过，这样的游戏其实与数学有着密切的？让我们一起探索碎纸片拼接复原背后的数学方法。

碎纸片拼接复原，其实就是一个计算几何问题。

在数学领域，欧几里得几何和非欧几里得几何是两个基本而又重要的分支。

欧几里得几何主要研究的是在平面上两点之间的最短距离，这是我们日常生活中常见的几何学。

而非欧几里得几何则研究的是曲面上的几何学，这种几何学并不符合我们日常生活中的直觉。

碎纸片拼接复原的问题就是一种非欧几里得几何问题。

在计算机科学中，图论是研究图形和网络的基本理论。

其中，图形遍历算法可以用来解决碎纸片拼接复原问题。

这种算法的基本思想是：从一点出发，尽可能多地遍历整个图形，并在遍历的过程中对图形进行重建。

对于碎纸片拼接复原问题，我们可以将每一张碎纸片看作是图中的一个节点，当两张碎纸片拼接在一起时，它们就形成了一个边。

通过这种方式，我们可以将所有的碎纸片连接起来，形成一个完整的图形。

在计算机科学中，碎纸片拼接复原问题被广泛应用于图像处理、数据恢复等领域。

例如，在数字图像处理中，如果一张图片被切割成若干块，我们可以通过类似的方法来恢复原始的图片。

在数据恢复领域，当一个文件被删除或格式化时，我们也可以通过类似的方法来恢复文件。

碎纸片拼接复原的问题不仅是一个有趣的拼图游戏，更是一个涉及计算几何、图论等多个领域的数学问题。

通过运用这些数学方法，我们可以有效地解决这个问题，从而更好地理解和应用这些数学理论。

在我们的日常生活中，我们经常会遇到一些破碎的物品，例如碎镜子、破碎的瓷器，或是碎纸片等。

这些物品的复原过程都需要一种科学的方法来帮助他们重新拼接起来。

这种科学方法就是碎纸片拼接复原技术。

碎纸片拼接复原技术是一种基于数学模型的方法，它通过比较碎纸片边缘的形状、纹理、颜色等特征，来找到碎纸片之间的相似性和关联性，从而将它们拼接起来。

碎纸片自动拼接复原模型的实现

碎纸片自动拼接复原模型的实现


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

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

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中纸片。

针对问题二，由于附件3碎片数量太多，并且碎片的拼接复原，是一个以碎纸片总匹配度为目标函数的组合优化问题。

所以本文采用遗传算法将碎纸片的编号作为基因，并将基因均匀分成19段，按顺序每一段对应一个初始纸片列位置，进行了求解。

然后，根据边缘碎纸片某些边的空白部分多的特征，对初始基因进行了优化。

接着，根据碎纸片的黑色像素密度不同的特点，将碎纸片分成三类，根据同类纸片优先匹配的原则，对遗传算法的运行过程进行了优化，拼接复原了附件3和附件4中纸片。

针对问题三，随着碎纸片量的增多，计算量急剧增加。

在上述拼接复原碎纸片的基础上，又引进了同行位置碎纸片的上部（或下部）空白位置宽度相近的聚类思想。

先对每个类内部拼接，在合并所有类并做一次整体拼接。

由于时间有限，我们未能完成最后一次的整体的拼接，但我们会在比赛后继续探究。

关键词：边缘矩阵匹配度函数遗传算法聚类一、问题重述碎片拼接实际用途已经越来越广泛，传统上拼接复原工作由人工完成，碎片拼接的准确率较高，但效率很低。

并且当碎片数量很大时，人工短时间内拼接出来几乎是不可能的。

所以开发碎纸的拼接技术，以提高拼接复原效率已成为越来越多人的期望。

现在,在碎纸片是规则的情况下，题目要求我们在以下条件建立碎纸片拼接复原模型和算法。

1.来自同一页印刷文字文件（中文、英文各一页）的碎纸机破碎纸片（仅纵切）拼接复原，并将附件1和附件2复原。

2.对碎纸机既纵切又横切文件的情形，将碎纸片拼接完整。