破碎文件的拼接数学建模论文.doc

《破碎文件的拼接数学建模论文.doc》由会员分享，可在线阅读，更多相关《破碎文件的拼接数学建模论文.doc（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）规则碎纸片拼接复原过程由边缘矩阵匹配度最优碎纸片的选取可知，只要搜索出第一张碎纸片，则与之边缘矩阵匹配度最优的碎纸片的编号也就是固定的，如此循环则可确定所有纸片的顺序，即可得出相应原图片排序。基于这种边缘矩阵匹配度最优搜索算法，本文从剩余的碎纸片中继续搜索与边缘矩阵匹配度最优的一张碎纸片，并对，完成拼接复原。用此方式不断地搜索直至所有碎纸片的边缘矩阵匹配度最优碎纸片全部拼接完时为止，或直到搜索到与匹配的时停止搜索，即可完成对碎纸片的拼接复原。规则碎纸片的拼接匹配过程可以表示为：S

16、tep1： 搜索出第一张碎纸片（原文字文件最左边的碎纸片）；Step2： 搜索出与边缘矩阵匹配度最优碎纸片，并将和进行拼接；Step3： 搜索出与边缘矩阵匹配度最优碎纸片，并将和进行拼接；Step4： 继续搜索与上一张匹配度最优的碎纸片并进行拼接，直至搜索到与匹配度最优的时停止。此时，所有碎纸片均已拼接完成。4.1.2结果根据上述边缘矩阵匹配度最优搜索算法，用Matlab软件对破碎文件进行匹配，复原后的图片详见附录1，复原后的碎纸片序号见下表2：表2：中文碎纸片复原后的碎纸片序号814121531021614591318117170对于英文碎纸片即附件2中的碎纸片，本文采用与中文相同的边缘矩阵

17、匹配度最优搜索算法进行搜索拼接。同样，复原后的图片详见附录2，复原后的碎纸片序号见下表3:表3：英文碎纸片复原后的序号表36271518110519131081214171644.1.3 结果分析（1）中文文件复原结果分析由上述搜索方法完成了附件1和附件2中的碎纸片的拼接复原工作，本文对拼接匹配后完整的一页文件进行分析。首先，对整张图片横向分析，令所有有字的行为1，没字的行为0。通过统计连续的0或1的个数，可以得到没有文字和有文字的高度，即空白与文字的高度，统计结果如下图2：图2：完整的中文文件各部分的高度图在上图中： 横轴表示连续的空白行和文字行的编号，纵轴表示其对应的高度，单位以像素表示；

18、 有字与无字相间，而字高与行间距不同，故成折线； 第一个和最后一个分别为整个页面的上下页边距； 由于每个像素点都是由0255的数字，故有字与无字的边界没有一个明确的界限，所以我们统计的高度可能会有一定误差； 除第一个数据和最后一个数据外，偶数编号的代表有字，奇数编号的代表行间距。由上图可以得出以下结论： 每行字高像素； 行间距像素； 上边距像素； 下边距像素。其次，以附件1文件中复原后的第二行（下图3所示）为例，对其由左至右进行统计连续空白与非空白的个数。图3：中文碎纸片拼接后的第二行然后，对第二行进行由左至右统计后，计算出空白列即左右页边距和字间距，以及文字的字宽并记录下来。对应的记录该行空

19、白列和文字列（包括标点符号）的列宽，用Matlab作图表示如下：图4：中文碎纸片复原后第二行各部分的列宽图其中，横轴表示文件复原后分解的空白列和文字列的编号，纵轴表示其对应的宽度。由上图可得出以下结论： 字宽像素； 字间距像素； 句号宽度约12（用“*”表示）像素，句号之后的空白列宽度约16像素； 左边距像素； 右边距像素。注：编号36至56之间的文字为“村里村北响缲车”，这些字多数为“左右结构”，这些表现为“左右结构”的文字在计算的时候被分为两部分，其中“响”字的“口”子部大小约与“句号”相等，故第四个“*”（高度为12像素）不表示句号。（2）英文文件复原结果分析同中文文件复原结果分析类似，

20、首先，将整个英文文件由上至下进行统计，计算出空白行与文字行的高度，并记录下来。分解结果如下图5所示：图5：完整英文文件各部分高度图同理，横轴表示对附件1文件复原后分解的空白行和文字行的编号，纵轴表示其对应的高度，单位以像素表示。由上图可得： 上边距约为37像素； 下边距约为61像素； 三格单词约为51像素； 净行距约为12像素； 一二格约为38像素，空约为25像素； 二三格约为44像素，空约为18像素。其次，以附件2文件复原后的第四行（下图6所示）为例，对其由左至右进行分解。图6：英文文件复原后第四行同理，计算出空白列和文字列的宽度，并将其记录下来，结果如下图:7所示：图7：英文碎纸片复原后第

21、四行各部分的宽度图其中，横轴表示文件复原后分解的空白列和文字列的编号，纵轴表示其对应的宽度。由上图可得出以下结论： 单词内部字母间隔约为1像素，这里描述的是单词的宽度而不是字母的宽度； 页面左边距约为11，右边距约为19像素； 标点前宽度约为3像素，标点宽度约为6像素，标点后一单词宽度约为35像素； 单词间间隔约为19像素； 图中波峰的顶点高度表示单词的宽度。4.2问题二的模型建立与求解4.2.1基于绝对差值搜索算法的纵横切碎纸片拼接模型（1）最左侧端11个碎纸片的确定根据问题分析，用Matlab对所有碎纸片的两个宽度（碎纸片左侧端空白列以及文字列）进行分析，会出现两种情况： 碎纸片左端第一个

22、宽度是空白列的宽度，即像素，第二个宽度是文字宽度，即像素，其宽度和像素； 碎纸片左端第一个宽度是断裂文字的宽度（），第二个宽度是字间距，即像素，其宽度和小于45像素。因为文件最左端的碎纸片拥有其独特的特点，即最左端的碎纸片一定有左边距，紧接着才是正文部分，所以，只有第一种情况下的碎纸片才是位于文件最左端的碎纸片。因此，本文将第一种情况作为判断最左侧11个碎纸片的筛选条件。用Matlab对所有的碎纸片进行筛选，我们得到了且仅得到了11个碎纸片，这也很好地证明了我们选择的筛选条件是正确的。11个碎纸片的编号如下表4所示：表4：最左端的11个碎纸片的编号11个碎纸片1234567891011编号00

23、7029038049061071094125135143168对应的563144376268508933718注：上述表格中的第一行与第二行、第一行与第三行没有对应关系（2）同一行碎纸片的筛选首先，我们求出每个碎纸片由上到下的所有文字行和空白行的高度，并将其记录下来。这里，我们以附件3中的010图片为例，其图片如下图8所示： 图8:附件3的010图片由上图可看出，该图可分为9个部分（附件中的所有碎纸片最多被分为9部分），其中“翁”字是上下结构的字，其在Matlab中上部分的“公”和下部分的“羽”被拆开了，所以该字被分为了3部分。在我国的汉字结构中，有很多上下结构的字，如“吴”、“呈”、“志”等

24、等。2这种结构的字有可能在碎纸片中出现。对图8的9部分记录高度，结果如下图9所示：图9:附件3中010图片文字行和空白行的高度图图中，横轴表示各部分的编号，纵轴表示其对应的高度。观察上图可知,该图9部分的高度分别为：表5:010图片的各部分高度编号123456789高度（像素）4274127191212812由上表可知：第3部分的高度为41像素，所以该编号所对应的字应该是图8中的第一个字“试”字。根据文献2可知，碎纸片中可能会存在第一个完整字是上下结构的情况，这种情况下，我们对第一个字的判断就会失真，为了避免这种判断误差，我们采取以下步骤消除该误差：Step1：判断连续3个高度值都小于25像素

25、的位置；Step2：将该3个高度值相加求和，将该结果替换第一个高度值小于25像素位置上的高度值；Step3：将该3部分后的所有高度值位置均往前移动2个位置；Step4：新得到的一列高度值作为原碎纸片的高度值。这里，仍以010碎纸片为例，对其进行误差消除处理：Step1：由表5可以看出，3个高度值均小于25像素的位置位于编号为5、6、7的列；Step2：将编号为5、6、7所在列的高度相加求和，将编号为5所在列的高度值替换为41；Step3：将编号为8、9所在列的高度值往前移动至编号为6、7所在列的高度值；Step4：新得到的高度值作为图7各部分的高度值。如下表6所示：表6：消除误差后010图片的

26、各部分高度编号1234567高度（像素）4274127412812用以上方法，我们消除由上下结构字体引起的误差影响。对于其他碎纸片，我们也采用同样的方法，消除误差影响。求出所有碎纸片的各部分真实高度值后，接着我们求出所有碎纸片（共209个）的，表示第个碎纸片按由上往下的顺序判断其第一个完整字体与碎纸片最顶端的距离。其中，最左端的11个碎纸片的值见表4的第三行。这里，我们这样定义第一个完整字体：即消除误差影响后，第一个高度为41像素左右的位置所对应的字就是第一个完整字体。然后将所有碎纸片的两两作差取绝对值，即绝对差值，并将所有的放入的矩阵里。其部分结果如下表7所示（全部结果详见附件1）：表7：部

27、分碎纸片的0371931442560121325370186712433725241219180122562519766316120136373119186447251301950443231192512661903125131206432537503106181931037193144256012132512257193213181201131324618311219131012251266190312513120上表中，只列出了前11个编号碎纸片的绝对差值。由上表可以看出，所有碎纸片的有较小值1,6,7等，也有较大的值25,37,44等。根据问题分析，处于同一行的字体具有相同的高度值，因此

28、，我们以最左端的11个碎纸片的为参照，先搜索出所有碎纸片与其中任意一个碎纸片（如007）的的绝对差值，并将其按从小到大的顺序排列，选择处于排序前面的18个碎纸片，则该18个碎纸片与其（007）位于原文件中的同一行。如下表7所示：表7：对007的前20个碎纸片排序12345678910编号032456813713815816617453排序11121314151617181920编号709312615317519620856164131由表7可以看出：与007的的的绝对差值按从小到大的顺序排列后，位于前18个的碎纸片的编号分别为：0,32,45,68,137,138,158,166,174,53

29、,70,93,126,153,175,196,208,56该18个编号对应的碎纸片与007对应的碎纸片是位于原文件的同一行的。接着分别以剩余的10个碎纸片为依据，搜索与其处于同一行的碎纸片的编号（与其他最左端的10个碎纸片做差的的前20个碎纸片详见附件1）。这里，为了避免重复搜索，我们在每次搜索后，都对的矩阵进行替换，具体替换思路为：找到搜索到的与之处于同一行的18个碎纸片在矩阵中所处位置，将该18个碎纸片的编号所在行（或列）的用一个人极大的值（这里用1000）进行替换。（3）同一行碎纸片的拼接根据问题分析可知，对同一行碎纸片的拼接问题与问题一的原理一样，因此，可以将同一行碎纸片的拼接问题转化

30、为问题一中对仅纵切的碎纸片拼接问题。具体拼接匹配过程，参照问题一的“基于边缘矩阵匹配度最优搜索算法的规则碎纸片拼接模型”模型建立与求解过程。其中，同一行碎纸片的部分拼接结果如下图10、图11所示：图10：字体几乎完整的同一行匹配结果图由上图10看出，用问题一中的方法可以完成对搜索出来的19个碎纸片，可以完成拼接匹配过程。该19个碎纸片的编号顺序为：62,20,79,68,70,100,163,97,132,80,64,117,164,73,7,178,21,53,37。对于字体部分断裂较多的同一行碎纸片拼接匹配结果如下图10所示：图11：字体部分完整的同一行匹配结果图与图10的结果相同，用问题

31、一中的方法可以达到对同一行碎纸片的拼接匹配的目的，该19个碎纸片的编号顺序为：39,149,47,162,25,36, 82,190,123,104,131,194,89,168,26,9,10,106,75。（4）行与行的拼接由问题分析可知，由于文字行的特征，上下相邻两行之间所有断裂的文字的字高之和应该是固定的，且等于字高像素。因此，本文通过对所有行进行分析，计算出所有行最上端和最下端的非完整字体的高度，按照最优匹配行原则，逐行进行筛选，这里，我们这样定义最优匹配行：一行文字上端的非完整字体高度与另一行文字下端的非完整字体高度和满足42像素左右的字体个数最多，则称该两行文字是彼此的最优匹配行

32、。基于此，我们首先判断出位于原文件最顶端图片，再从剩余的图片中搜索与该图片最底行匹配最优的行所在的图片，依次搜索。限于篇幅原因，将不在此叙述具体实现过程。其部分拼接结果如下图12所示：图12：部分行匹配结果至此，我们已经完成了中文纵横切碎纸片的匹配。4.2.2结果根据上述基于绝对差值搜索算法，本文用Matlab完成了对中文纵横切的碎纸片的拼接。按照要求，我们将复原后的图片放入附件4中，复原后的碎纸片序号见下表8：表8：中文碎纸片拼接复原后的序号4123147191501791208619526187188118912210313019388167258910574135127316020316

33、9134393151107115176121421241447711214997136164127584318411018766106150211731571812041391451804837755544206101049817217159175451740137535693153701663219680332021981513317020585152165276015120715514018510811741011131941191234.3问题三的模型建立及求解4.3.1基于绝对差值搜索算法模型的改进根据问题分析，对于英文碎纸片拼接与中文的情况既有相似之处也有不同之处。考虑到英文字母和汉

34、字的不同，汉字的字高都是一样的，而对于英文字母，不同字母会导致不同的字高。因此，本节主要讨论针对问题二中的模型改进。首先，根据问题一中对英文结果作进一步分析可知（详见图5）：(1) 对于像等字母，其高度大约为26像素，而对于等字母，其高度大约为38像素；(2) 对于行间距，如果是等字母，其行间距大致为38像素，如果是等字母，其高度大致为26像素；据上数据分析我们发现，除一些特殊的字母（如“”之类）之外，每一个字母的字高与其上面的行间距之和为一个65的常数，定义该常数为横匹配常数。 因此，我们将一个字母的字高和其上面的行高看作一个整体求和，本文中，我们将纵横切的英文碎纸片上端第一个和作为同行碎纸

35、片的筛选条件，对附件四中的碎纸片进行同行筛选，得到位于同一行的碎纸片的编号，其中部分结果如下图13所示：图13：处于同行的英文碎纸片由上图可以看出，我们的改进模型对纵横切的英文碎纸片拼接复原有很大的缺陷。其中，对应的碎纸片编号顺序为：82,49,73,125,126,194,53,79,180,50,51,54,81,86,90,130,132,139,1435.模型评价与推广5.1模型优点(1) 根据实际情况，本文提出了对“翁”字等特殊结构的字的处理方法，并能够推广到其他类似结构的字；(2) 对问题一的结果进行了深入的挖掘，得到了页边距、字体大小等信息，能够应用于之后的模型；(3) 在对横纵

36、切的碎片分类时，提出了利用第一个完整高度的字的位置来描述碎片特征的方法，该方法能够很好地对碎片进行分类；(4) 在处理横纵切碎片时，采用先横向分类，然后纵向排序，最后进行横向排序的步骤，思路清晰，避免了盲目寻找，也不必直接使用模拟煺火或遗传算法等智能算法，程序简单；(5) 在横向排序时，采用问题一的算法，模型延续性强。5.2模型缺点(1) 本模型只适用于规则的纸片拼接问题，不能很好地适用于不规则纸片拼接；(2) 由于英文的字母高度、行间距均有多个数值情况复杂，没有很好地对英文横纵切碎片拼接；(3) 由于时间问题，没有对各个部分程序进行整合，所以只有各个模块的程序；(4) 对拼接效果不理想的部分

37、，本文采用人工干预的方法处理，人工工作量较大。5.3模型推广在本文中，定义了边缘矩阵匹配度用来对每行进行排序，还用到字高和行高来进行不同行之间的划分，这两个量在一定程度上分别能够反映各个碎片之间的区别。对于形状规则的碎纸片而言，与纯粹的人工拼接相比我们的模型能够大大节省时间，提高效率。具有一定的推广性。但是，对图片的边缘匹配度的定义以及对行分类时所用到的约束条件不足，因此得到的结果并非最优，需要加入人工干预才能够实现完整拼接。如果能找到最能够反应边缘匹配程度的函数，以及反映不同行之间的区别参数，那么模型的效率将会更高，结果也会更优，需要人工干预的部分就会减少，模型可进一步推广。参考文献1罗智中

38、. 基于文字特征的文档碎纸片半自动拼接J. 计算机工程与应用,2012,05:207-210.2梁添才,皮佑国,丘志文,王素利. 基于简易网格的汉字结构识别方法J. 华中科技大学学报(自然科学版),2008,06:40-42.附录1：附件1中碎纸片复原后的图附件2中碎纸片复原后的图附件3中的碎纸片复原后的图附录2：程序1.found.mfunction pp,index,m=found(images,t,num)for i=1:length(num) m(i)=sum(t(:,end)=images(:,1,i) & t(:,end)=255 ); mm,index=max(m); pp=im

39、ages(:,:,index);endU1.mclose allclear,clcimages=;%导入图像得到高维矩阵% images=dir(C:UsershpDesktop新建文件夹附件3*.bmp);for i = 0:9str = strcat (00,num2str(i), .bmp) ; % 连接字符串形成图像的文件名。img = imread(str);images(:,:,i+1)= img; endfor i = 10:18str = strcat (0,num2str(i), .bmp) ; % 连接字符串形成图像的文件名。img = imread(str);images

40、(:,:,i+1) = img; endimages(images=255)=0;%将矩阵变为只含有0和255的%x,y,z=size(images);newI=;num=1:z;shunxu=;%显示第一列for i=1:z if images(:,1,i)=255 p=i; shunxu=shunxu p; newI(:,1:y)=images(:,:,i); t=images(:,:,i);% num(p)=;%确定位置的去掉 endend% for i=1:z-1i=1; pp,index,m=found(images,t,num); shunxu=shunxu index; newI

41、=newI,pp; t=images(:,:,index);% num(index)=;%确定位置的去掉% endimshow(newI)2.yingwen.mclose allclear,clcimages=;%导入图像得到高维矩阵for i = 0:9str = strcat (00,num2str(i), .bmp) ; % 连接字符串形成图像的文件名。img = imread(str);images(:,:,i+1)= img; endfor i = 10:18str = strcat (0,num2str(i), .bmp) ; % 连接字符串形成图像的文件名。img = imrea

42、d(str);images(:,:,i+1) = img; endimages(images=255)=0;%将矩阵变为只含有0和255的%x,y,z=size(images);newI=;num=1:z;shunxu=;%显示第一列for i=1:z if images(:,1,i)=255 p=i; shunxu=shunxu p; newI(:,1:y)=images(:,:,i); t=images(:,:,i);% num(p)=;%确定位置的去掉 endend%for i=1:z-1 pp,index=found(images,t,num); shunxu=shunxu index; newI=newI,pp; t=images(:,:,index);% num(index)=;%确定位置的去掉endimshow(newI)found.mfunction pp,index=found(images,t,num)for i=1:length(num) m(i)=sum(t(:,end)=images(:,1,i) & t(:,end)=255 ); mm,index=max(m); pp=images(:,:,index);end3ee.mclear;clcn=209;B=cell(1,n);