《破碎文件的拼接数学建模论文》由会员分享，可在线阅读，更多相关《破碎文件的拼接数学建模论文（32页珍藏版）》请在金锄头文库上搜索。
1、破碎文件的拼接数学建模论文摘要破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域占有重要地位。因此，本文从计算机编程的角度出发，建立了不同情况下的规则碎纸片拼接模型。针对问题一，将附件中所有图片文件导入Matlab中进行数字化处理；根据文本文件左侧端有页边距的特点，搜索出文件左侧的第一个碎片；以边缘矩阵匹配度为搜索依据，分别计算该碎片与其余碎片的边缘矩阵匹配度，并选择与之边缘矩阵匹配度最大的碎纸片拼接到该碎纸片的右侧，依次循环，直至实现所有图片的拼接。基于此，我们完成了对附件一、二的碎纸片的拼接，同时对结果进行分析得到汉子字高、行距、页边距，英文字母字高、行距等有用信息。针对问题
2、二，对于中文碎纸片，首先考虑到文件左端部分第一个宽度和第二个宽度和约为52像素的特点，搜索出文件第一列的所有图片；然后根据每张图片的第一个完整字（即消除误差影响后，第一个高度为41像素左右的位置所对应的字）与图片顶端的距离，将所有碎纸片的该距离两两绝对差值由小到大排序，选择前18个碎纸片作为与其同一行，完成了对所有纸片进行横向分类；再运用问题一中所提出的边缘矩阵匹配度方法对每一行的图片进行横向排序；最后根据行高和字高确定行与行之间的排列顺序，并通过人工干预的方法完成拼接。针对问题三，对于英文碎纸片，经过每一个字母高度的特点进行数据分析，发现每一个字母的字高与其上面行高之和横匹配常数。因此，我们
3、根据该常数作为英文碎纸片的横向分类依据。以碎纸片的单面为基础，沿用问题二的方法进行拼接。对于无法分类的图片，选取其反面的文字并计算其常数进行区分。以此方法，可在一定程度上减少拼接误差，进而减少人工干预的工作量。关键词：数字化处理 边缘矩阵匹配度 人工干预 横匹配常数1.问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎纸片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。题目要求尝试建立数学模型讨论下列问题:（1） 对于
4、来自同一页且仅纵切的印刷文字文件，建立碎纸片拼接复原模型和算法，并将附件一、附件二中的碎纸片进行拼接复原。拼接过程如需人工干预，则要求写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。（2） 对于纵横切的中文情形，设计碎纸片拼接复原模型和算法，并将附件三中的碎纸片数据进行拼接复原。同样，如需人工干预，写出干预方式及干预的时间节点。复原结果表达要求同上。（3） 对于纵横切的英文，以及双面打印且纵横切的情形，设计拼接复原模型和算法。并将附件四、附件五的碎纸片进行拼接复原。结果表达要求同上。2.问题分析2.1问题一的分析该问题要求对来自同一页且仅纵切的由碎纸机破碎的印刷文字文件，建立碎
5、纸片拼接复原模型和算法，并将附件一、二中的碎纸片数据进行拼接复原。如需人工干预，则要求写出干预方式和干预时间节点。由于题中所给的文字文件均是由破碎机破碎的文件，这种破碎文件的形状是一系列规则的图片，所以问题属于对规则碎纸片的匹配问题，而不是考虑非规则碎纸片的匹配问题，故此不能通过碎纸的形状特征对文件进行拼接。考虑到附件一、附件二中碎纸片均为纵切，可以采用边缘矩阵匹配度的方法对其进行匹配，将碎纸片看作矩阵，矩阵中所有的点就组成了碎纸片上所有的信息。因此，如果两个矩阵最边缘矩阵上的所有点相互对应的个数越多，对应的碎纸片匹配的程度就越高。此外，根据纸张的特征，纸张的最左端和最右端部分部分为空白，因此
6、可以找到最左端和最右端的碎纸片，而其余的碎纸片在其边缘矩阵两端都或多或少有文字点，这部分碎纸片都位于一页文件的中间位置。由于碎纸片均可以看作是由很多个点组成的，那么附件一和附件二中的图片在计算机中可以用矩阵来表示，且在矩阵中可以将文件白色纸张和文字区分开来，同时可以通过边缘矩阵对纸片进行两两匹配。因此，只要判断出原文件最左（右）侧的碎纸片，然后寻找其余碎片中左侧与该碎纸片右（左）边缘矩阵匹配度程度最高的碎纸片，该碎纸片即可作为它的相邻碎纸片，那么该位置的碎纸片就是固定的，再从剩余的碎纸片中继续搜索与上一张碎纸片相邻的碎纸片，如此循环则可确定所有碎纸片的顺序，即可得出相应原图片的序号排序。最后，
7、对拼接复原的文本文件做进一步分析，可以得到该文本文件的重要相关信息。2.2问题二的分析该问题要求对纵横切的中文文件，设计拼接复原模型和算法，并对附件三、给出的碎纸片数据进行拼接复原。同时，若需要人工干预，则要求给出干预方式和干预时间节点。由于文字文档的行方向平行且单一，如果碎纸片内的文字在碎纸片边缘断裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行，凭此特征可以很容易地从众多规则碎纸片中挑选出同行碎纸片1。基于此，利用碎纸片内文字行特征拼接由碎纸机破碎的文字理论上是可行的。首先，考虑到文本文件最左侧端的碎纸片有其独有的特征，即第一个宽度值是文件的左侧页边距，第二个宽度值是一个文
8、字的宽度值。根据此特点，可以将最左侧端的碎纸片与其他位置的碎纸片区分开来，也就可以把位于文字文件最左侧端的11个碎纸片搜索出来。然后，计算出所有碎纸片（209个）的第一个（按由上往下的顺序）完整字到碎纸片顶端的距离，并将所有碎纸片的两两求绝对差值，。以最左侧端的11个碎纸片为依据，分别搜索出与最左端字片的较小的前18个碎纸片，判断这些碎纸片是否与最左边的11个碎纸片处于同一行。接着，考虑这些处于同一行的碎纸片，将其拼接匹配，与第一问将仅纵切的碎纸片拼接问题原理一样。因此，对同一行的碎纸片拼接问题可以转化为对仅纵切的碎纸片拼接问题，可以用问题一的碎纸片拼接匹配方法将其拼接。最后，根据文字行的特征
9、，上下相邻两行之间所有断裂文字的字高之和应该是固定的。可以以此特征为依据，将行与行的碎纸片进行拼接匹配。最终可以完成对纵横切的碎纸片的拼接匹配。2.3问题三的分析该问题要求对于纵横切的英文，以及双面打印且纵横切的情形，设计拼接复原模型和算法。基于英文的特殊性，我们决定将原问题二中的纵横切英文碎纸片放到问题三中讨论。理论上，只要对于一面的英文碎纸片拼接完成，那么另一面的碎纸片自然就是对应拼接的。考虑到英文字母和汉字的区别较大，对于汉字而言，汉字的字高都是相同的，而对于英文字母而言，由于字母的不同会导致字高的不同。因此，首先需要对问题二中的同行判断条件进行改进，使改进后的条件能将位于同行的英文碎纸
10、片搜索出来，即可完成对英文碎纸片的同行搜索过程。然后，对纵横切英文进同行的匹配。对于纵横切的英文，以及双面打印且纵横切的情形，设计拼接复原模型和算法。英文同行碎纸片匹配与纵横切的中文同行碎纸片匹配原理类似，因此，对纵横切英文同行碎纸片匹配问题也可以转化为问题一中碎纸片匹配问题。即可完成对纵横切英文同行碎纸片匹配。最后，对纵横切英文进行行与行的匹配。由于英文字母中存在许多类似于“j”、“f”、“P”等特殊的字母，所以，在纵横切英文行与行匹配时，需要同时加入人工干预，方可完成单、双面纵横切英文碎纸片的拼接过程。3.模型假设1、 假设所给附件中所有图片中的汉字字号、行距、列宽以及页边距均一样；2、
11、假设所给附件中所有图片中的英文单词字号、行距、列宽以及页边距均一样；3、 假设所有纸张是由同一种碎纸机切割的。4.模型的建立及求解4.1问题一的模型建立与求解4.1.1基于边缘矩阵匹配度最优搜索算法的规则碎纸片拼接模型（1）边缘矩阵匹配度最优搜索算法流程图与上一次搜索出的碎片边缘矩阵匹配度最优的碎片已无剩余碎片可搜索时结束搜索图片导入Matlab矩阵中与匹配度最优的碎片位于一页文件最左端的碎片与上一次搜索出的碎片边缘矩阵匹配度最优的碎片开始搜索从剩余碎片中搜索从剩余碎片中搜索从剩余碎片中搜索根据问题分析，要对来自同一页且仅纵切的由碎纸机破碎的文字文件进行拼接匹配，可以用计算机将其表示为矩阵并对
12、其进行匹配。因此，本节讨论用Matlab软件对附件一和附件二的碎纸片进行处理，通过对碎纸片边缘矩阵分析，进而对碎纸片进行匹配，完成对同一页文字文件的复原。模型流程图如下图1所示：图1：规则碎纸片拼接算法流程图（2）图片矩阵的导入与分析由上述分析可知，对于规则碎纸片的拼接，可以通过记录和搜索与两端文字点边缘矩阵匹配度最优的碎纸片，对碎纸片进行两两匹配，达到破碎机破碎文件拼接的目的。结合附件一、二的图片，用Matlab中的矩阵将图片表示出来，图片矩阵如下所示（以附件1中000图片为例）：其中，255表示白色，0表示黑色。在Matlab中用矩阵表示出所有碎纸片后，本文采取搜索原本位于一页文件的最左边
13、碎纸片的方式。首先判断出一页文件中最左侧端的碎纸片，由问题分析可知，最左边一列的数值均为255，对附件1中所有碎纸片的矩阵观察得知，只有008碎纸片矩阵满足此条件，其矩阵为：同理， 255表示白色，0表示黑色。因此，008即为，它位于原文字文件的最左侧端。根据上述算法，寻找出后，从剩余的碎纸片中继续搜索与右边缘矩阵匹配度度最优碎纸片，即为位于右侧端的碎纸片。（3） 边缘矩阵匹配度最优碎纸片的选取在这里，边缘矩阵匹配度最优碎纸片的定义：只要一张碎纸片矩阵最右侧端的一列数值与另一张碎纸片矩阵最左侧端的一列数值相同的个数最多，即认为该两张碎纸片是彼此边缘矩阵匹配度度最优碎纸片。过程如下：将图片导入m
14、atlab中得到一个1980行72列大小的矩阵。这里我们用表示第行，表示第列表示第个图片最右列矩阵的第行的数据，即将以确定的图片最右端矩阵与待确定图片的最左端矩阵比较，结果如下：则本文定义匹配度为：以编号为008的碎纸片为例，结果如下：表1：与008碎纸片边缘矩阵的匹配度图片编号000001002003004005006007009匹配度156185671651331191479598图片编号001000110012001300140015001600170018匹配度1509959982563299138144由上表可知，编号014的碎纸片边缘矩阵与008边缘矩阵的匹配度最优，则014就作为
15、与008边缘矩阵匹配度最优的碎纸片，也即在原来同一页文件上的左侧端位置相邻的两张碎纸片和分别是008和014。（4）规则碎纸片拼接复原过程由边缘矩阵匹配度最优碎纸片的选取可知，只要搜索出第一张碎纸片，则与之边缘矩阵匹配度最优的碎纸片的编号也就是固定的，如此循环则可确定所有纸片的顺序，即可得出相应原图片排序。基于这种边缘矩阵匹配度最优搜索算法，本文从剩余的碎纸片中继续搜索与边缘矩阵匹配度最优的一张碎纸片，并对，完成拼接复原。用此方式不断地搜索直至所有碎纸片的边缘矩阵匹配度最优碎纸片全部拼接完时为止，或直到搜索到与匹配的时停止搜索，即可完成对碎纸片的拼接复原。规则碎纸片的拼接匹配过程可以表示为：Step1： 搜索出第一张碎纸片（原文字文件最左边的碎纸片）；Step2： 搜索出与边缘矩阵匹配度最优碎纸片，并将和进行拼接；Step3： 搜索出与边缘矩阵匹配度最优碎纸片，并将和进行拼接；Step4： 继续搜索与上一张匹配度最优的碎纸片并进行拼接，直至搜索到与匹配度最优的时停止。此时，所有碎纸片均已拼接完成。4.1.2结果根据上述边缘矩阵匹配度最优搜索算法，用Matlab软
