电子版稿子碎纸片拼接复原

1、碎纸片的拼接复原鞠安然，李宇航，蒋 旭（哈尔滨工程大学 船舶工程学院，黑龙江 哈尔滨 150001）摘 要：本文针对不同形式的碎纸片的拼接复原进行建模分析，在分析题目所给要求及所给数据特点后，我们针对不同问题突出了相应的解决方案。在对模型误差分析和稳定性估计时，我们计算了问题1的错误率为1.09%，可以很好地拟合；对于汉字部分由于纵向边界数据减少，所以错误率有所上升；而对于英文边界识别率又会降低，所以拼接效果不是特别好；对于双面数据又加大了数据干扰，进一步降低了匹配率，仅仅完成了部分的匹配。我们进行了合理的假设，建立了合理的模型，并编写了普适性较好的程序，最大程度上对碎片进行了拼接。本文模型合

2、理地忽略了一些因素，在实际中能够很好地得到近似结果。最后还对模型的优缺点进行了分析，得到所建模型和编写的程序具有一定的现实意义，在一定程度上可以推广。关键词：碎片拼接；RGB矩阵；特征数据匹配；阈值 Splicing Bits Of Paper RecoveryJU Anran，LI Yuhang，JIANG Xu（College of Shipbuilding Engineering, Harbin Engineering University, 150001, China）Abstract: In this paper, scraps of paper mosaic of differen

3、t forms of recovery modeling analysis, the analysis of the subject requirements and given the characteristics of the given data, we propose the following solution. When the error analysis and stability of the model estimates, we calculate the error rate of 1.09% on Problem 1, which can be a good fit

4、 for the characters .due in part to reduction of the vertical boundary data, the error rate increases. As the English border recognition rate reduces,the mosaic effect is not particularly good. The data for double-sided data increases the data interference, which reduces the matching rate and just c

5、ompletes a portion of matching . After making a reasonable assumption, we establish a reasonable model and program a generally applicable program to put the fragments together to the maximum extent. Proposed model reasonably ignored factors, in practice can be obtained very similar results. Finally,

6、 on the advantages and disadvantages of the model were analyzed, and the preparation of the model program has some practical significance, to some extent, can be extended. Keywords: debris stitching; RGB matrix; characteristic data matching; threshold1 问题的重述1.1 问题背景文件碎片的拼接复原技术在情报资料整理、司法技术鉴定、历史文物考察等众

7、多领域中都有重要而又广泛的应用，情报信息、司法物证、历史文献等众多资料有时会遭到损坏，对文件资料碎片的拼接复原已经成为需要研究的重要问题，而单一的只靠人工的方法来进行碎片的拼接复原不仅费时间、费人力，而且还会在面对大量碎片时出现极大的困难，因此，利用高端的计算机技术来实现自动拼接复原就可以提高效率，节省人力、时间。自动拼接复原技术是通过建立模型、设计算法并利用特定的计算机软件来使 碎纸片自动（半自动）完成拼接复原的一种技术，对于该种技术的研究是极为必要的。1.2 需要解决的问题问题1：设计一种自动拼接复原的模型和算法，将纵切的单面印刷文件进行拼接复原，并且以附件1，附件2中的碎片文件为例进行拼

8、接复原，给出拼接复原结果（图片形式、表格形式），来检验该模型和算法的正确性。问题2：设计一种自动拼接复原的模型和算法，将既纵切又横切的单面印刷文件行拼接复原，并且以附件3、附件4中的碎片文件为例进行拼接复原，给出拼接复原结果（图片形式、表格形式），来检验该模型和算法的正确性。问题3：设计一种自动拼接复原的模型和算法，将既纵切又横切的双面印刷文件进行拼接复原，并且以附件5中的碎片文件为例进行拼接复原，给出拼接复原结果（图片形式、表格形式），来检验该模型和算法的正确性。2 模型准备2.1 主要变量符号说明总体符号说明：1表示第i个碎纸RGB值矩阵中的最左侧一列数据组成的矩阵；2表示第i个碎纸RGB

9、值矩阵中的从左至右第二列数据组成的矩阵；3表示第i个碎纸RGB值矩阵中的最右侧一列数据组成的矩阵；4表示第i个碎纸RGB值矩阵中的最上侧一列数据组成的矩阵；5表示第i个碎纸RGB值矩阵中的最下侧一列数据组成的矩阵。问题一中的符号说明：6表示第i个碎纸RGB值矩阵中的最左侧一列数据组成的矩阵；7表示第i个碎纸RGB值矩阵中的最右侧一列数据组成的矩阵； 8，其中 QUOTE 是 QUOTE 矩阵中的第k个元素， QUOTE 矩阵中共有910个元素。问题二中的符号说明：9表示第i个碎纸RGB值矩阵中的最左侧一列数据组成的矩阵；10表示第i个碎纸RGB值矩阵中的最右侧一列数据组成的矩阵；11，其中，

10、QUOTE 是 QUOTE 矩阵中的第k个元素， QUOTE 矩阵中共有90个元素。问题三中的符号说明：12表示第i个碎纸正面RGB值矩阵中的最左侧一列数据组成的矩阵；13表示第i个碎纸正面RGB值矩阵中最右侧一列数据组成的矩阵；14表示第i个碎纸反面RGB值矩阵中的最左侧一列数据组成的矩阵；15表示第i个碎纸反面RGB值矩阵中的最右侧一列数据组成的矩阵，即正号表示左面，负号表示右面。3.2 相关名词说明RGB即是代表红、绿、蓝三个通道的颜色，电脑屏幕上的所有颜色，都由这红色绿色蓝色三种色光按照不同的比例混合而成的。屏幕上的任何一个颜色都可以由一组RGB值来记录和表达。 在电脑中，RGB的所谓

11、“多少”就是指亮度，并使用整数来表示。通常情况下，RGB各有256级亮度，用数字表示为从0、1、2.直到255。表1 黑色与白色的RPG值16 3.3 模型假设1)纸片断痕足够小，使得纸片破碎前后对纸片断痕上下左右的RGB不产生影响；2)纸片边缘能被完全扫描，不会发生信息遗漏；3)Matlab能够精确读取断痕边缘的RGB值；4)忽略RGB相差小于5以下的差距。3 问题的分析图像经matlab读取数据之后，会将图片离散化，读出各个离散点的RGB值，然后将RGB值以矩阵的形式输出。输出三个矩阵分别对应图片的R值矩阵、G值矩阵、B值矩阵，因为本问题的碎片全都是黑白图像，输出的的R值矩阵、G值矩阵、B

12、值矩阵都是一样的。因此只需选取其中的一个矩阵就能代替图片的特征。下文都用R值代表RGB值。 纸张经粉碎后，形成规整的纸条或纸片。将纸片或纸片扫描成图片格式，读取图片的数据即RGB值，相邻纸片断痕处的RGB值必然存在一定的相似度，通过这种关系就可以找出纸片相邻位置关系，进而可以将纸片拼接出来。另一方面由于计算机数字分析图像能力的缺陷，让计算机对碎片进行完全意义上的自动化拼接也几乎不太可能，为保证拼接的准确性，需要在某些特定的条件下以某种方式在拼接过程中加入人工干扰过程。 由于题设中所提供的内容是图片信息，所以要对图像数据进行处理，进而转化成数字数据来解决问题。17 图1 图像处理方案4 模型建立

13、与求解4.1 问题一根据题意，将一张纸分成19个细长的纸条，将纸条重新组合成原来的形式。纸条只有左右两端，因此纸条边缘的RGB值是本模型的关键。将纸条图像离散化，用matlab提取离散点的RGB值并组成矩阵，从所得矩阵中提取第一列与最近一列并分别组成矩阵。这样问题就转化为如何用各个纸条所产生的矩阵通过一定关系进行匹配的问题。如果两纸条所产生的矩阵匹配成功，则两纸条必然相邻，以此类推，可以找到所有纸条的相邻关系，从而达到问题的求解成功。下面是矩阵匹配的过程。矩阵匹配的原则说明：根据假设，纸条断痕左右的RGB值基本吻合，RGB值矩阵差别最小的则具有相邻关系。其中 QUOTE 和 QUOTE 不需要

14、考虑，因此可简化为：18（第i个碎纸RGB值矩阵中的最左侧一列数据组成的矩阵）， 19（第i个碎纸RGB值矩阵中的最右侧一列数据组成的矩阵）， 20，其中， QUOTE 是 QUOTE 矩阵中的第k个元素， QUOTE 矩阵中共有910个元素。匹配算法：现在计取 QUOTE 这一矩阵中的元素等于0的个数，记为X，当X大于900时，即认为强相关关系，就是两纸条具有相邻关系。下一步，则利用matlab实现上述模型。程序实现过程中，matlab从图像中获得边缘RGB值的矩阵后，通过上述模型遍历实现匹配排序，从而达到碎纸条拼接的效果。4.2 问题二4.2.1问题二分析问题二不同于问题一，问题一中一张纸

15、经纵切变成19个长条状碎片，而问题二中一张纸经在纵切的基础上加入横切，长条状的碎片变成了矩形状，且数量变成了201个碎片。 而且对于小块的英文碎纸片其识别特征并不明显，所以会带来一些误差。针对问题二的特殊情况，我们采用先找最左侧一列所有纸片，再根据第一题的基础，以第一列的每一快碎纸逐项遍历找到横向相邻的碎纸。每一横行确定以后，人工干预手动将每一横行排序，从而最终达到拼接的目的。21 图2 模型实现的流程图4.2.1问题二模型建立附件三和四的最左侧和最右侧一列的碎纸在全部碎纸中特征最明显，最左侧一列碎纸的左侧以及最右侧一列碎纸的最右侧为空白，即RGB值为255*90。利用这一特征，可以将最左侧一

16、列的全部纸片全部找出来。1)最左端图片查找模型 如下图，以碎纸014号以及006号为例，由于图像背景颜色与文档背景颜色相同，因此改变图像的背景颜色。明显可以看出014号碎纸属于最左侧一列，而006属于中间的某一列。在两图块的左侧区域分别等间距的画两条竖直直线将图块分为左右两个区域，明显014号碎纸左侧区域空白，即RGB值为0；而006号碎纸左侧区域有文字，即RGB值不为0；明显最左侧一列其余列的区别可以用各个碎纸左侧区域的RGB值矩阵区别开来。22 014号 006号图3 背景颜色对比 通过matlab可以将左侧11个碎纸找出来，其对应RPG如下表。表2 左侧11个碎纸RPG值232)横行图片

17、查找拼接模型中因为问题二中的碎纸相较于问题一的纸条比较复杂，碎纸的位置难以确定，因此我们在类似于问题一的模型基础上增加位置变量对匹配拼接的影响因子，两个匹配原则产生的解，我们取最优解。然后以各列的第一个纸片作为初始纸片顺次进行匹配。最终实现每一横行的拼接。具体的匹配算法如下：匹配算法一：计取 QUOTE 这一矩阵中的元素小于某一阈值的个数，记为Xij。其中阈值根据数据之间的比对分析选取。由于每一个位置处的RGB值得差值在0到255之间，要选取一个阈值可以大概取其中的1/4处的一个数暂作为阈值，输入写好的matlab程序中进行运行，根据输出的图片的整齐度进行微调阈值，经过几次调试之后可得到最终的

18、阈值为70。经上述分析可知Xij越大说明匹配度越好，容易知道Xij的量级大概为10-90。设匹配算法1的判据条件即为Xij。匹配算法二：在匹配算法中增加碎纸的位置因素，以保证在进行匹配拼接时碎纸的位置得到考虑，从而增加拼接的效率与准确性。24其中， QUOTE 是匹配算法一中的 QUOTE 中的元素， QUOTE 的取值范围是0-255， QUOTE 元素的个数是90。Y1越小则表示匹配程度越好，其量级在0.1-0.9之间。算法一和二的整合：要将两种模型中的筛选条件进行综合，一个是最大值一个是最小值，现做如下处理：对Y1做进一步的处理 QUOTE 25现在Y的值越大则表示匹配程度越好，其量级仍

19、在0.1-0.9之间。设匹配算法2的判据条件即为Yij。 一般而言，都是根据两种算法在匹配过程中所占的比重加权找到其中的最优解。本问题中是根据X、Y量级上的差别来进行加权,因为从各自算法的重要公式来看，X、Y的主要差别在于匹配的有效离散点的个数。而量级的差别与有效离散点的个数基本相符。因此可以将X、Y的权重比设为1:100（其权重比例的微调方式同阈值的微调方式相同）因此最优解的筛选变量为26 容易知道Zij越大，那么就是证明其匹配程度越好。通过上述模型编写程序用matlab遍历查找并排列就可以将每一横行碎纸的排列顺序找出来。自动输出图像后，并截图保存。4.2.2 问题二模型的求解1)横行图片查

20、找拼接后的人工干预对于排列出来的每一个横行其中由于边界是全白的干扰所以有一些地方的排列会出现一些偏差（如图4），此时要对matlab程序排好的图片利用photoshop根据图片中的文字内容将横行中有偏差的图片碎片移动到对应位置，并输出保存。2728图4 横行图片2)利用模型一中的程序进行横行排序将人工干预后的正确的横行排列图片作为基准，根据问题一中的模型进行相关的筛选排列，即可得到最终的正确排列顺序和图片输出。4.3 问题三对于附件三碎片两面都有的字母信息，我们提出以下建模思路：通过问题二中的模型以及具体操作流程将附件五中的两面的图片拼接问题当成一个518个图片碎片的拼接问题，我们根据问题二中

21、的模型增加matlab程序中的遍历数对518个图片分别进行排列筛选，即可理论上得到图片的排列顺序和输出结果。但是由于除了英文图片的边界判断依据少之外还有双面因素的干扰，所以此问题仅仅拼出部分的源文件。5 模型的评价与改进5.1 模型的整体实现效果问题一具体实现结果：附件一与附件二经过上述模型以及Mathlab的程序的实现均得到非常好的结果。问题二具体实现结果：对于附件三能实现拼接，且仅仅发生少量错误，经过后期的人工干预修正可以实现完整的拼接，因此模型对于问题二中的文字部分来说建立成功。而对于英文部分，在第一次的循环拼接后匹配率并没有附件三种的图片匹配的那样好，因此在二次循环拼接前要进行比较多的

22、人工干预，但是整体的人工工作量还是远远小于纯手动拼接的工作量。问题三具体实现结果：由于英文字母一共就有52（算大小写），所以在边界处的RGB值差别甚微，所以对模型中的筛选判别条件要求更高，此外双面的信息量更是加大了筛选拼接的难度，所以建立的模型的通过更改其中的阈值只能最大程度上的减少错误率，但是还是仅仅能实现碎片的部分拼接。5.2 模型误差分析问题一中对附件1,2矩阵910组对应元素的差值超过900个等于0，即910组超过900组的数值均相等，这样的相关性已经很强了。犯错可以认为是小概率事件。验证：犯错误的概率为 QUOTE * MERGEFORMAT 29 ,可以看出犯错误的概率很低。本模型

23、的误差主要产生于综合算法中将一二两种算法加权综合取最优的加权部分，根据量纲来确定权重是一种定性的方法，没有采用定量的方法，因此会产生一定的误差。但通过附件三和四的运行结果来看，这种做法是能够达到类似问题求解的要求的。本模型的误差主要产生于：由于问题三在问题二的模型进行建立模型的，问题二所产生的误差在问题三并没有得到解决，而是被放大。从而只是实现部分拼接复原成功。 5.3 模型的优缺点优点：1)适用性强。针对不同的规整碎片有不同的模型与算法，例如问题一的模型专门针对于一般粉碎机将文件粉碎成纸条的形式，对于此类问题模型一可以快速高效的将碎片拼接还原；而对于机密性粉碎机将文档粉碎成矩形纸片的形式，则可以用问题二中的半自动模型辅助人工干预可以快速将文档拼接复原； 2)模型灵活。针对不同粉碎机的规格可以设定模型中几个参数的值，就可以将纸片快速复原； 3)准确性高。模型能够准确识别并排出纸片的顺序，很少会发生误判。在各个模型误差分析中既已给出模型的出错率，出错率很小； 4)高效方便。除个别复杂情况基本不需要人为