碎纸的自动拼接与复原研究.doc

摘要破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域占 有重要地位因此，本文从计算机编程的角度出发，建立了不同情况下的规则碎 纸片拼接模型针对问题一，将附件中所有图片文件导入Matlab中进行数字化处理；根据 文本文件左侧端有页边距的特点，搜索出文件左侧的第一个碎片；以边缘矩阵匹 配度为搜索依据，分别计算该碎片与其余碎片的边缘矩阵匹配度，并选择与之边 缘矩阵匹配度最大的碎纸片拼接到该碎纸片的右侧，依次循环，直至实现所有图 片的拼接基于此，我们完成了对附件一、二的碎纸片的拼接，同时对结果进行 分析得到汉子字高、行距、页边距，英文字母字高、行距等有用信息针对问题二，对于中文碎纸片，首先考虑到文件左端部分第一个宽度和第二 个宽度和约为52像索的特点，搜索出文件第一列的所冇图片；然后根据每张图 片的第一个完整字（即消除误差影响后，第一个高度为41像素左右的位置所对 应的字）与图片顶端的距离，将所冇碎纸片的该距离两两绝对差值由小到大排序, 选择前18个碎纸片作为与其同一行，完成了对所有纸片进行横向分类；再运用 问题一中所提岀的边缘矩阵匹配度方法对每一行的图片进行横向排序；最后根据 行高和字高确定行与行Z间的排列顺序，并通过人工干预的方法完成拼接。

针对问题三，对于英文碎纸片，经过每一个字母高度的特点进行数据分析， 发现每一个字母的字高与其上面行高Z和横匹配常数因此，我们根据该常数作 为英文碎纸片的横向分类依据以碎纸片的单面为基础，沿用问题二的方法进行 拼接对于无法分类的图片，选取其反而的文字并计算其常数进行区分以此方 法，可在一定程度上减少拼接误差，进而减少人工干预的工作量关键词：数字化处理 边缘矩阵匹配度 人工干预 横匹配常数1 •问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都 有着重要的应用传统上，拼接复原工作需由人工完成，准确率较高，但效率很 低特别是当碎纸片数量巨大，人工拼接很难在短时间内完成任务随着计算机 技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率题口 要求尝试建立数学模型讨论下列问题：1、 对于来自同一页且仅纵切的印刷文字文件，建立碎纸片拼接复原模型和算法， 并将附件一、附件二中的碎纸片进行拼接复原拼接过程如需人工干预，则耍 求写出干预方式及干预的时间节点复原结果以图片形式及表格形式表达2、 对于纵横切的中文情形，设计碎纸片拼接复原模型和算法，并将附件三中的碎 纸片数据进行拼接复原。

同样，如需人工干预，写出干预方式及干预的时间节 点复原结果表达要求同上3、 对于纵横切的英文，以及双面打卬且纵横切的情形，设计拼接复原模型和算法 并将附件四、附件五的碎纸片进行拼接复原结果表达要求同上2•问题分析2.1问题一的分析该问题要求对來自同一页口仅纵切的由碎纸机破碎的印刷文字文件，建立碎 纸片拼接复原模型和算法，并将附件一、二中的碎纸片数据进行拼接复原如需 人工干预，则要求写岀干预方式和干预时间节点由于题中所给的文字文件均是由破碎机破碎的文件，这种破碎文件的形状是 一系列规则的图片，所以问题属于对规则碎纸片的匹配问题，而不是考虑非规则 碎纸片的匹配问题，故此不能通过碎纸的形状特征对文件进行拼接考虑到附件 一、附件二中碎纸片均为纵切，可以采用边缘矩阵匹配度的方法对其进行匹配， 将碎纸片看作矩阵，矩阵中所有的点就组成了碎纸片上所有的信息因此，如杲 两个矩阵最边缘矩阵上的所冇点相互对应的个数越多，对应的碎纸片匹配的程度 就越高此外，根据纸张的特征，纸张的最左端和最右端部分部分为空白，因此可以 找到最左端和最右端的碎纸片，而其余的碎纸片在其边缘矩阵两端都或多或少有 文字点，这部分碎纸片都位于一页文件的中间位置。

由于碎纸片均可以看作是由很多个点组成的，那么附件一和附件二中的图片 在计算机中可以用矩阵来表示，且在矩阵中可以将文件口色纸张和文字区分开 来，同时可以通过边缘矩阵对纸片进行两两匹配因此，只要判断出原文件最左 （右）侧的碎纸片，然后寻找其余碎片中左侧与该碎纸片右（左）边缘拒阵匹配 度程度最高的碎纸片，该碎纸片即可作为它的相邻碎纸片，那么该位置的碎纸片 就是固定的，再从剩余的碎纸片中继续搜索与上一张碎纸片相邻的碎纸片，如此 循环则可确定所有碎纸片的顺序，即可得岀相应原图片的序号排序最后，对拼接复原的文本文件做进一步分析，可以得到该文本文件的重要相 关信息2.2问题二的分析该问题要求对纵横切的中文文件，设计拼接复原模型和算法，并对附件三、 给出的碎纸片数据进行拼接复原同时，若需耍人工干预，则要求给出干预方式 和干预时间节点由于文字文档的行方向平行且单一，如果碎纸片内的文字在碎纸片边缘断 裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行，凭此 特征可以很容易地从众多规则碎纸片中挑选出同行碎纸片川基于此，利用碎纸 片内文字行特征拼接由碎纸机破碎的文字理论上是可行的首先，考虑到文本文件最左侧端的碎纸片有其独有的特征，即第一个宽度值 是文件的左侧页边距，第二个宽度值是一个文字的宽度值。

根据此特点，可以将 最左侧端的碎纸片与其他位置的碎纸片区分开来，也就可以把位于文字文件最左 侧端的11个碎纸片搜索出来然后，计算出所冇碎纸片（209个）的第一个（按由上往下的顺序）完整字 到碎纸片顶端的距离并将所有碎纸片的△，两两求绝对差值“， 心1,2,・・・,209,） = 1,2,・・・,209以最左侧端的11个碎纸片为依据,分别搜索出与 最左端字片的"较小的前18个碎纸片，判断这些碎纸片是否与最左边的11个碎 纸片处于同一行接着，考虑这些处于同一行的碎纸片，将其拼接匹配，与第一问将仅纵切的 碎纸片拼接问题原理一样因此，对同一行的碎纸片拼接问题可以转化为对仅纵 切的碎纸片拼接问题，可以用问题一的碎纸片拼接匹配方法将其拼接最后，根据文字行的特征，上下相邻两行之间所有断裂文字的字高之和应该 是固定的可以以此特征为依据，将行与行的碎纸片进行拼接匹配最终可以完 成对纵横切的碎纸片的拼接匹配2.3问题三的分析该问题要求对于纵横切的英文，以及双而打印月•纵横切的情形，设计拼接复 原模型和算法基丁英文的特殊性，我们决定将原问题二中的纵横切英文碎纸片放到问题三 中讨论理论上，只要对于一而的英文碎纸片拼接完成，那么另一而的碎纸片自然就 是对应拼接的。

考虑到英文字母和汉字的区别较大，对于汉字而言，汉字的字高 都是相同的，而对于英文字母而言，由于字母的不同会导致字高的不同因此， 首先需要对问题二中的同行判断条件进行改进，使改进后的条件能将位于同行的 英文碎纸片搜索出來，即可完成对英文碎纸片的同行搜索过程然后，对纵横切英文进同行的匹配对于纵横切的英文，以及双而打印且纵 横切的情形，设计拼接复原模型和算法英文同行碎纸片匹配与纵横切的中文同 行碎纸片匹配原理类似，因此，对纵横切英文同行碎纸片匹配问题也可以转化为 问题一中碎纸片匹配问题即可完成对纵横切英文同行碎纸片匹配最后，对纵横切英文进行行与行的匹配由于英文字母中存在许多类似于“j”、“f”、“p”等特殊的字母，所以，在纵横切英文行与行匹配时，需要同时 加入人工干预，方可完成单、双而纵横切英文碎纸片的拼接过程3 •模型假设1、 假设所给附件中所冇图片中的汉字字号、行距、列宽以及页边距均一样；2、 假设所给附件中所有图片中的英文单词字号、行距、列宽以及页边距均一样;3、 假设所有纸张是由同一种碎纸机切割的4.模型的建立及求解4.1问题一的模型建立与求解4.1.1基于边缘矩阵匹配度最优搜索算法的规则碎纸片拼接模型1. 边缘矩阵匹配度最优搜索算法流程图所示:根据问题分析，要对来自同一贝且仅纵切的由碎纸机破碎的文字文件进行拼 接匹配，可以用计算机将其表示为矩阵并对其进行匹配。

因此，本节讨论用 Matlab软件对附件-•和附件二的碎纸片进行处理，通过对碎纸片边缘短阵分析, 进而对碎纸片进行匹配，完成对同一页文字文件的复原模型流程图如下图1图片导入Matlab矩阵中并力台糊玄 位于一页文件最左端的碎片e与G匹配度最优的碎片0从剩余律卅山糊宓 殳上 J与上一次搜索出的碎片边缘矩阵匹配度最优的与上一次搜索出的碎片边缘矩阵匹配度最优的 已无剩余碎片可搜索时结束搜索图1：规则碎纸片拼接算法流程图2. 图片矩阵的导入与分析「255255255…255…255255255_255255255…255…255255255255255255…255…255255255• • •255• • •0• • • • • •0 …• • • • • •0 •…• • •0• • •0• • •0• • •255• • •255• • • • • •255…• • • • • •255…• • •255• • •255• • •255255255255…255…255255255_255255255…255…255255255_A)=0表示黑色由上述分析可知，对于规则碎纸片的拼接，可以通过记录和搜索与两端文字 点边缘矩阵匹配度最优的碎纸片，对碎纸片进行两两匹配，达到破碎机破碎文件 拼接的目的。

结合附件一、二的图片，用Matlab中的矩阵将图片表示出来，图 片矩阵如下所示（以附件1中000图片为例）：其小，255表示白色，木文采取搜索原木位于一页文件在Matlab中用矩阵表示出所有碎纸片后，的最左边碎纸片的方式首先判断出一页文件中最左侧端的碎纸片勺，由问题分 析可知，也最左边一列的数值均为255,对附件1中所冇碎纸片的矩阵观察得知, 只有008碎纸片矩阵满足此条件，其矩阵为：255255255255255255255255255255…255…255255255255255255…255…255255255• • •255• • •255• • • • • •255…• • • • • •0 …• • •0• • •0• • •0• • •255• • •255• • • • • •255…• • • • • •255…• • •255• • •255• • •255255255255…255…255255255255255255…255…255255255A =同理，255表示白色，0表示黑色因此,008即为q,它位于原文字文件 的最左侧端根据上述算法，寻找出q后，从剩余的碎纸片中继续搜索与q右边 缘矩阵匹配度度最优碎纸片，即为位于勺右侧端的碎纸片色。

3. 边缘矩阵匹配度最优碎纸片的选取在这里，边缘矩阵匹配度最优碎纸片的定义：只要一张碎纸片矩阵最右侧端 的一列数值与另一张碎纸片矩阵最左侧端的一列数值相同的个数最多，即认为该 两张碎纸片是彼此边缘矩阵匹配度度最优碎纸片过程如下：将图片导入matlab中得到一个1980行72列大小的矩阵这里 我们用i表示i第行，j表示第j列知表示第i个图片最右列矩阵的第i行的数据，即将以确定的图片最右端矩阵与待确定图片的最左端矩阵比较，结杲如2aij = ° 心+。