814 姜荣杰 朱佳亭 金建邦(1)【公众号：数模加油站】.pdf

2013 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 承承 诺诺 书书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）：B 我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：浙江工业大学参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人 (打印并签名)：（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：5444576572013 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 编编 号号 专专 用用 页页 赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 1 题目：基于旅行商模型的文字碎纸片拼接复原 摘要 文字碎纸片拼接复原是一项在司法物证复原、历史文献修复以及军事情报获取等领域有着广泛应用的工作。所以对文字碎纸片的研究的重要性不言而喻。本文研究的目的皆在建立数学模型与算法，解决碎片复原中的三个问题，使得对三种不同特点碎片复原的人工干预次数较少，尽可能实现碎片复原的全自动化。问题一，对纵切碎片复原。我们建立模型一，给出了基于旅行商问题的拼接策略。我们发现，碎片的拼接问题就是找到碎片最好的排列，找到一个排列类似于在一个图中找到一条路径。基于此，我们将碎片拼接问题抽象为一个图论问题，将碎片看做图中的顶点，碎片与碎片之间的匹配程度（匹配距离）看做图的边权。由此我们将碎片的拼接问题转化为一个哈密尔顿路径问题（不回到源点的旅行商问题）。在问题一中的匹配距离为碎片边界横向匹配距离，即为一种衡量碎片与碎片在左右方向上边界图像匹配程度的指标，匹配距离越短，说明两碎片边界越相似，匹配程度越好。模型一可用 lingo 与 matlab 编程求解。由于旅行商问题的求解是整体寻优，得到的结果为全局最优解，所以其准确性较高。对附件 1 与附件 2 的碎片还原结果我们没有进行人工干预。问题二，对既纵切又横切的碎片复原。我们建立模型二，给出基于文本行特征的碎片行分组算法，对行分组碎片进行横向拼接得到复原的碎片行，再对碎片行进行纵向拼接，得到最终复原结果。这两种拼接策略均为模型一中基于旅行商问题的拼接策略。其中，文本行特征即为文本行之间的规整性，利用文本行的规整性不仅可以对碎片进行行分组，而且还可以提高文本纵向拼接的准确度。我们根据模型二，对附件 3 碎片还原的结果没有人工干预；在对附件 4 碎片还原时在行分组碎片横向拼接后有人工干预，即偶尔人工调整个别碎片还原结果。问题三，对双面碎片复原。我们建立模型三，该模型中对碎片的行分组以及横向拼接同模型二中的方法，但考虑到碎片有两面，所用到的匹配距离需要替换为正反面匹配（两面的匹配距离之和）。此外，在对碎片行做纵向拼接时与模型二中的方法略有不同，由于碎片有双面信息，我们将模型一中基于旅行商问题的拼接策略扩展为多旅行商（2个旅行商）问题的拼接策略，即一条旅行商路径代表纸张的一面，另一条旅行商路径代表纸张的另一面。对于模型三，由于采用了正反面匹配距离，用到了两面信息，其可用于拼接的信息量相对于单面碎片而言增大了一倍，所以对附件 5 碎片还原结果没有人工干预。综上所述，我们建立的碎片复原模型与算法人工干预次数较少，对碎片复原工作有一定的参考价值。关键词：哈密尔顿路径关键词：哈密尔顿路径 旅行商问题旅行商问题 匹配距离匹配距离 文本行特征文本行特征 碎片分组碎片分组 获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 2 问题重述问题重述 碎纸片的拼接是一项在司法物证复原、历史文献修复以及军事情报获取等领域有着广泛应用的工作。在碎片数量较小的情况下，人们可以根据碎片上的文字逻辑、形状、纹理、色彩等快速将碎片拼接成功。然而现实中，更多地是要拼接大量的碎片，这时手工的方法就不适用了，需要靠计算机辅助完成。本文研究的目的接在建立数学模型，对于给定的来自同一页印刷文字文件的碎纸机破碎纸片，主要解决文字碎片拼接中的以下 3 种情况。（1）一页单面文字文件被纵切得到的碎片还原。（2）一页单面文字文件既被纵切又被横切得到的碎片还原。（3）一页双面打印的文字文件既被纵切又被横切得到的碎片还原。模型的假设模型的假设 本文研究的碎片具有如下特征。l 所有碎片来自同一张纸。l 所有碎片能够拼出完整的一张纸。l 所有碎片尺寸大小相等，边缘轮廓为规则的矩形。l 所有碎片中的文字颜色一致，且与背景颜色有较大反差。l 所有碎片图片只有两种颜色，文字颜色与背景颜色。l 所有碎片中的文字边缘清晰，已被去除噪音。l 所有碎片中的文字是从左至右、从上至下书写的。l 所碎片都已摆放端正，即碎片中的文字端正。l 所有碎片中的文本行距相等。符号说明符号说明 本文中，用到的主要符号与说明见表 1。表 1 符号说明表 符号 说明 Ai 第 i 个碎片 某种排列 dij 碎片 j 拼接在碎片 i 后的匹配距离 rk Bl Br fri 第 k 个碎片的行距特征向量 纸张左分组碎片组成的集合 纸张右分组碎片组成的集合 碎片 Ai反面的行距特征向量 问题分析与模型概述问题分析与模型概述 问题一是对被纵切的碎片还原的问题，考虑到碎片的拼接问题是找到碎片与碎片之间最好的排列问题，由此，我们想到将碎片看做一个完全图的顶点，将碎片拼接转化为一个不回到源点的旅行商问题，即找到一条能够走过所有顶点（每个顶点只被访问一次）并且使得边权值之和符合要求的路径。基于此，我们建立了模型一，给出了基于旅行商问题的碎片拼接策略。问题二是对既被纵切又被横切的碎片还原。先考虑纵切，此时就可用问题一的解决获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 3 方法来处理，也就是说，对一些在同一行的碎片可用问题一的拼接策略解决。再考虑到横切，其实也与纵切无异，同样地，我们可以将拼接好的碎片行用问题一的拼接策略拼接起来得到最终的还原纸张。所以对问题二的处理过程中，我们首先需要先找到一些同在一行的碎片。在本文中我们结合文字行距特征给出了碎片分组的算法。基于此，我们建立了模型二。问题三是对双面碎片的还原，我们可以用解决问题二的方法得到一些拼接好的碎片行，用类似问题一的方法将碎片行拼接起来，但此时由于碎片有正反面之分，我们所用的拼接策略是基于多旅行商问题（2 个旅行商）的。基于此，我们建立了模型三。综上所述，本文所研究的三个问题是环环相扣的，由此我们对三个问题分别建立的模型也具有这样的特点。即模型二是由若干模型一构成的，而模型三是由若干模型一与变化后的模型一构成的。此外，对碎片与碎片间匹配程度的衡量，我们引入匹配距离（匹配距离越小，匹配程度越好），将匹配距离作为完全图的距离，如此一来模型一即为边权值之和最小的旅行商路径模型。而在模型二与模型三中，匹配距离根据文字特征与碎片特征而略有所不同。模型的建立与求解模型的建立与求解 5.1 问题一问题一 5.1.1 模型一主要思想模型一主要思想 模型一主要解决被纵切的碎片。考虑到碎片的拼接其实找到是碎片与碎片之间最好的排列，我们将碎片找排列问题转化为寻找一个符合特定条件的旅行商问题。5.1.2 模型一建立模型一建立 l 基于旅行商问题的拼接策略基于旅行商问题的拼接策略 首先我们将所有碎片构成一个集合，记做A0,A1 An。当所有碎片Ai能够组成一页完整的纸张A时，对碎片的拼接工作就是找到一个可以让碎片复原的排列，即找到一个排列，使得A=A(0)|A(1)|A(n)，其中“|”为连接符号。为了能够找到合适的排列，我们需要判断两个碎片能否拼接。在这里，我们用dij来衡量碎片Aj能够拼接在Ai后的可能性大小，称其为匹配距离，匹配距离越小说明匹配得越好。匹配距离的计算可以根据图片边缘的情况确定（详见后文“匹配距离”段落），一旦所有碎片之间的匹配距离确定下来后，我们的工作就是找到合适的排列使得 d(i)(i+1)i=0n1 (1)在n个碎片所有可能的排列中最小，此时这样的排列最有可能使碎片完全复原。如此一来，找到(1)式中式中最小的和就可以抽象为一个图论问题1。我们将所有的匹配度dij构成一个完全图的邻接矩阵，将碎片Ai看做图的顶点。这样，在我们所构造的这个有n条边的图中，匹配距离dij就表示为第i个顶点到第j个顶点的边权值，找到一个合适的排列就是找到一条能够走过所有顶点（每个顶点只被访问一次）并且使得边权值之和最小的路径。于是，我们的问题就等价于找到一条边权和最小的哈密尔顿路径问题，也同样是一个不回到源点的旅行商问题。若一张纸被切成五个碎片，其哈密尔顿路径示意图见图1。获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 4 图 1 五个碎片组成的完全图以及其哈密尔顿路径（A2 A4 A1A3 A5）走过的路径可以用如下序列表示：=(A(0),A(1)A(n)(2)其中A(i)表示在路径上第 i 个被访问的碎片编号，对于任意 i=0,2,n 1，满足：0 A(i)n 1,(3)且当 i j 时，A(i)A(j),(4)根据式(1)总边权 f()计算如下：f()=d(A(i)i=0n1,A(i+1)(5)其中 d(i,j)=dij表示碎片 j 拼接到碎片 i 的匹配距离。问题一的目标函数为 min f()(6)这样一来，由哈密尔顿路径找到的排列是全局最优解。l 匹配距离匹配距离 借鉴灰度图像的聚类方法中的最小色差法2，在这里，我们采用两两图像边缘像素点的差异大小作为衡量标准，以此判别两张碎纸片图像匹配的可能性。所以在这里的匹配距离等价于差异大小。首先，我们需要对图片进行采样获取信息。第n张碎纸片图像可以表示为一个RGB值的二维矩阵，记为An。An=npqnpnpnpnqnnnnqnnnnqnnnaaaaaaaaaaaaaaaa321333323122322211131211 255,0nija 其中aij的取值范围即为RGB的数字表示范围，q和p分别表示一张图片在长和宽方向获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 5 上的像素总个数。这样，一张图片就转化成为了由不同像素点组成的矩阵。在此基础上，我们对其特征进行分析判断。我们所选取的特征为图像边缘像素点的差异大小，我们记碎纸片Aj 拼接在碎纸片Ai后，边缘差异大小为dij。问题一的碎片边界匹配距离为碎片边界横向匹配距离dc(i,j)=pkjkikqaa11，q为碎片像素矩阵Ai的列数，用以表示碎纸片Ai右端边缘文字图像和碎纸片Aj左端边缘文字图像的匹配程度，匹配距离越小，则两张碎纸片越匹配。不同大小匹配度示意如下图2所示。（a）081号碎片与189号碎片匹配度大 （b）081号碎片与200号碎片匹配度小 图 2 碎片边界纵向匹配程度示意图 5.1.3 问题一的求解问题一的求解 由于问题一中，所有碎片都是纵切的，只存在纵向差异，所以我们只需要对碎片进行一维排列。首先我们用 matlab 编程将所有碎片读入，并计算出碎片与碎片之间的匹配距离。接着，为了求解旅行商的路径这样一个 NP 问题，我们根据模型一中的式(3)(4)(5)(6)，用xij=1 表示走过顶点 i 到顶点 j，xij=0 表示不选择这条路，将原模型转化得到如下旅行商问题的线性规划模型，mindijxijij (7)s.t.xijj=1n=1，i=0,1,2n 1(每个顶点只有一条边出去)(8)xiji=1n=1，j=0,1,2n1(每个顶点只有一条边进去)(9),2,1,12,1,nsnsssji（除起点和终点外，各边不构成圈）(10)xij 0,1,i,j=0,1n 1,i j(11)由此可以用善于求解规划问题的 lingo 语言(内部利用分支定界的剪枝算法)编写求解程序。由于我们将模型转化了为上式(7)(11)的形式，所以由 lingo 编程求得的结果是一个0-1 矩阵，并没有一个真正的排列。故，我们需要确定旅行商路径的源点，再根据求得的 0-1 矩阵得到最后的结果。由日常经验，我们可以知道，纸张的边界一般会有留白区域。如果碎片是属于纸张获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 6 的左右两侧，则边缘的像素值必为背景像素值（本文问题中的背景颜色为白色，像素值为 255），根据这一特点，我们将碎纸片进行分类，分为边界碎纸片和中间碎纸片。具体的算法见模型二中的边界碎片查找算法。对于问题一中的纵切碎纸片，左右侧碎片只有一张，所以设此时边界碎纸片查找算法中的 nc=1，根据该算法求得，左右侧碎纸片编号分别为 8、6，即得到碎片 8 为旅行商路径的源点。至此，我们便可再运用 matlab 软件进行处理，运行得到最终结果。附件一中文字碎片与附件二英文字碎片还原后的序号见表 2，还原图见附图一。表 2 问题一碎片还原序列 附件1 8 14 12 15 3 10 2 16 1 4 5 9 13 18 11 7 17 0 6 附件2 3 6 2 7 15 18 11 0 5 1 9 13 10 8 12 14 17 16 4 5.2 问题二问题二 5.2.1 模型二的主要思想模型二的主要思想 模型二主要解决既被纵切又被横切的碎片还原。我们先考虑纸张被纵切会有一些碎片行，所以先根据文本行特征得到碎片行分组。接着，利用模型一基于旅行商问题的拼接策略得到每个碎片行分组的拼接排列，得到被还原的碎片行。再根据模型一基于旅行商问题的拼接策略将碎片行纵向拼接。最后我们根据文本行距相等这一假设条件对所得的碎片还原进行自动调整，得到最后的就碎片还原结果。综上所述，模型二将既被纵切又被横切的碎片还原问题分解为若干模型一中的旅行商问题。对一个被切成切为 nr nc个碎片的纸张，需要做 nr次横向旅行商问题以及 1 次纵向旅行商问题。故，模型二的目标函数如下。minfk()=min=+10)1(),(nikiAiAd k=1,2 nr+1 其中 d(i,j)=dij表示碎片 j 拼接到碎片 i 的匹配距离。其中，当 k=1,2 nr时 fk()为横向旅行商问题的目标函数，其匹配距离为碎片横向匹配距离，当 k=nr+1 时 fk()为纵向旅行商问题的目标函数，其匹配距离为碎片纵向匹配距离。5.2.2 模型二的建立与求解模型二的建立与求解 l 纸张左右两侧的碎片纸张左右两侧的碎片 一般，我们在书写文章时，纸张左右两侧会留有一定的页边距，所以在纸张左右两侧会有一定的留白区。虽然我们并不清楚留白区占有多少列像素，但是我们可以肯定的是纸张左右两侧的留白一定比文字与文字或者文字与符号之间的留白要多。所以我们在这里，采取一种逐步缩小范围的搜索方法。我们以左侧留白为例，给出查找左右两侧碎片的算法及步骤。已知一张纸在列方向上可由 nc张碎片拼接成，我们记为符合纸张左侧特征的碎片组成的集合为 Bl，l为从碎片最左侧起开始编号的像素列号。获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 7 边界碎片查找算法如下。边界碎片查找算法如下。（1）初始化。Bl A0,A1 An，l 1，其中“”为赋值符号。（2）从集合 Bl中按碎片 Ak的编号顺序依次选出需要判别的碎片。若在选出的碎片在第l像素列中有任意一点像素 aijk（其中，j=l）不为背景像素值（即该列不留白），则将该碎片 Ak从集合为 Bl中去除，否则（该列留白）重复步骤（2）直至将集合 Bl中的碎片都判断完。（3）若集合 Bl中的碎片个数 nc，则l l+1，转至步骤（2）;若集合 Bl中的碎片个数=nc，则找到所有符合条件的碎片，算法终止。根据上述边界碎片查找算法，同样地，我们能够找到右侧的碎片及其集合 Br，由此得到所有左右两侧碎片。l 文本行特征文本行特征 当文字碎片即被纵切又被横切时，我们需要同时考虑其横纵拼接。在前文中我们已经考虑了纵向特征，所以在这里，我们考虑横向特征，将可能处在同一行的碎片找出。由于中文字与英文字有所区别，我们在此分别讨论其文字行的特征。中文文本行中文文本行 由于中文字非常方正，所以，对于一个中文字碎片 Ak我们按行扫描，记u为从碎片最上端起开始编号的像素行号，记 rik 为碎片 Ak在第u=i 行的特征值。对任意碎片碎片 Ak，从u=1 开始逐次以 1 递增扫描碎片的像素行，若碎片 Ak在u像素行有一个文字像素值（该行有文字笔画）则 rik=0（i=u），否则（该行无文字笔画）rik=1。这样，我们可以得到碎片 Ak的行距特征向量 rk=r1k,r2k rpkT，见示意图图 5。图 3 中文字文本行特征示意图 根据统计结果，得到上下两个文字之间的空白距离为 63 个像素距离。英文文本行英文文本行 英文字相对于中文字而言没有那么规整，但是一般英文的书写是在四线三格的中间，而英文字母的笔画一般不会超过第三条线，只有 g、j、p、q、y、Q 这六个英文字母字符超过第三条线（如图 4 所示），所以我们以第三条线作为底线判别文字行。图 4 英文字文本行 也就是说，当从上往下扫描碎片图片时，突然有 90%以上的像素点为背景像素值时，我们就认为该行为底线。根据统计，文本占底线间距的三分之二，所以我们在底线上面三分之二设为文字像素值，底线下面三分之一设为背景像素值。填充之后，同中文字碎获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 8 片，我们可以得到英文字碎片的行距特征向量 rk，见示意图图 5。111000001111q底线 图 5 英文字文本行特征示意图 根据统计结果，得到底线与底线之间的距离为 63 个像素距离。l 同一行碎片同一行碎片 有了碎片行距特征向量后，我们定义碎片 Aj归为碎片 Ai所在行后由行距特征向量ri与 rj作异或操作得到的模为文本行距匹配距离 dg(i,j)，即即 dg(i,j)=|rirj|。我们记为文本行距匹配的梯度阈值，当 dg(i,j)时，我们认为碎片 Aj归为 Ai所在行的匹配度较高。接下来，根据文本行距匹配距离我们可以通过行匹配得到同在一行的文字碎片。已知一张纸在行方向上可由 nr张碎片拼接成，以纸张右侧碎片作为行分组的标准，我们记纸张右侧碎片组成的集合为 Br，非纸张右侧且未被分组的碎片集合记为 Bu。行碎片查找算法如下。行碎片查找算法如下。在步骤（2）（5）中，我们找到的是一个粗略的行分组，在步骤（5）（6）后我们找到的是一个较精确的行分组。（1）初始化。集合 Br中的碎片 Ai所在行碎片个数(Ai)1。（2）从集合 Bu中选出一个碎片 Aj，若集合 Bu为空则转至步骤（5）。（3）从集合 Br中按碎片编号顺序依次选出碎片 Ai，求得碎片 Ai与碎片 Aj的文本行距匹配距离 dg(i,j)，放入匹配队列 Qi中。（4）将匹配队列 Qi中的 dg(i,j)排序，得到最大的 dg(i,j)，此时将碎片 Aj归为碎片Ai所在行，并将 Aj从集合 Bu中去除，转至步骤（2）。（5）从集合 Br中按碎片编号顺序依次选出碎片 Ai，若该碎片未被选出过则执行步骤（6），否则终止算法。（6）将所有归为碎片 Ai所在行的碎片 Aj按 dg(i,j)从大到小排序，若 dg(i,j)或者(Ai)=nr则转至（5）否则该行(Ai)(Ai)+1。根据上述步骤我们即可得到以纸张右侧碎片作为分组标准的行分组。l 基于纸张碎片左右分组的碎片行分组基于纸张碎片左右分组的碎片行分组 由于段落首行缩进以及段落结尾行留白，会导致在进行碎片查找算法时发生未满构成整行的碎片数 nr 就停止查找某行的碎片。为了弥补这样的分组结果，我们采用对碎片先右分组，再左分组，最后由左右分组结合的方法来对行分组，如图 6 所示。获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 9 图 6 左右分组与双侧分组算法 由纸张双侧向中间进行行分组的算法如下。由纸张双侧向中间进行行分组的算法如下。（1）以纸张右侧碎片为行分组标准，用行行碎片查找算法找到一些行分组，其集合记为 Gr，我们称其为右边分组碎片。（2）以纸张左侧碎片为行分组标准，用行行碎片查找算法找到一些行分组，其集合记为 Gl，我们称其为左边分组碎片。（3）我们将左右分组集合 Gr和 Gl中组内碎片数之和为整行的碎片数 nr的两个分组拼接在一起，形成一些完整的行。（4）将未被行分组的碎片与纸张左侧碎片进行碎片边界横向匹配距离的匹配。即将集合 Bu中的碎片与集合 Bl中的碎片进行匹配，选择边界横向匹配距离最大的作为拼接在纸张左侧碎片右侧的碎片，这些碎片即为纸张左侧第 2 列碎片。这样就避免了由段落首行缩进引起留白而无法进行分组的情形。（5）以纸张左侧第 2 列碎片为行分组标准，用行碎片查找算法，得到一些行分组，记入集合 Gl中。再重复一遍步骤（3）。下面给出一个结合左右分组对碎片行分组的具体的实例。图 7 所示为同一行的碎片分组，该图中的组内碎片已横向拼接过。(a)碎片行左分组 (b)碎片行右分组 图 7 附件三中 196 号碎片所在行的分组 图 8 附件三中 196 号碎片所在行右分组文本行距匹配梯度。图 8 中的文本行距匹配梯度曲线为图 7（b）的分组碎片的文本行距匹配梯度情况，可以看到第 19 个碎片的文本行距匹配梯度特别小，结合图 7 中我们可以看到实际情况也确实如此（左右分组衔接处匹配程度较低）。3?16?19?19?3?16?.获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 10 l 横向碎片拼接横向碎片拼接 用模型一中基于旅行商问题的拼接策略，对得到的行分组进行横拼接，得到还原后的碎片行。需要注意的是，横向碎片拼接得到的是没有关联的碎片行，碎片行与碎片行之间的排列还未找出，即纵向文本还原还没有处理。l 纵向碎片拼接纵向碎片拼接 由纸张双侧向中间拼接碎片后，我们能够得到一行一行还原后的碎片组。我们将每一行碎片组看做图的顶点，用模型一中基于旅行商问题的拼接策略，对碎片组纵向排列。在纵向排列时，我们需要用到碎片边界纵向匹配距离。碎片边界纵向匹配距离dr(i,j)=，p为碎片像素矩阵Ai的行数，用以表示碎纸片Ai下端边缘文字图像和碎纸片Aj上端边缘文字图像的匹配程度，匹配距离小，则两张碎纸片越匹配。不同大小匹配度示意如下图9所示。（a）041号碎片与081号碎片匹配度大 （b）100号碎片与081号碎片匹配度小 图 9 附件三中碎片边界横向匹配程度示意图 这样一来我们可以得到一整张还原后的纸张，但这样的排列还有一定问题，下面我们做进一步调整。l 中文字基于行距的碎片拼接中文字基于行距的碎片拼接 由纵向碎片拼接，我们可以得到一整张还原后的纸张，但是定由此拼接后纸张中的文本行距不一相等。而根据我们的假设，我们认为一般纸张中的文本行距相等，所以我们需要对纵向碎片拼接后的结果做一定调整。当一行碎片组下边缘为背景色时，另一行碎片组上边缘为背景色时，这两行碎片组边界纵向匹配程度较高，被拼接在一起，导致这两行间的行距变大。我们将这样情形的碎片组拼接断开，分成几组碎片段，每个碎片段都由一些碎片行组成。这样我们可以将碎片段重新排列组合，选出文本行距最符合文本行距相等这一条件的碎片段组合，以此组合作为最终的碎片还原结果。下面给出判别文本行距相等的方法。由于文字书写时行距一般相等，所以若按行扫描原文字文件，则其行距会呈现一定的周期规律。对于某一文字碎片，我们有行距特征的 0-1 向量，那么对某一碎片行的每个碎片行距特征向量做求和运算，就可以得到文本行距的变化曲线，见图 10。=qkjkipkaa11获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 11 图 10 附件 3 中 078 号碎片所在行的行距图（高处部分的曲线表示无文字，低处部分的曲线表示有文字）由图 10 我们可以看到该碎片行有无文字出现的交替非常规整，我们称这样的文本符合文本行距相等这一条件。若将每一碎片行首尾连接后，我们可以得到整个纸张中的文本行距变化曲线图，见图 11、图 12。图 11 文本行距周期错误曲线（附件 3 碎片错误还原结果，其还原图见附图四）图 12 文本行距周期正确曲线（附件 3 碎片还原结果）从图 11 中我们可以看到，该曲线中在像素位 350 附近、750 附近、1100 附近以及1400 附近的有无文字交替比曲线其他部分要频繁，我们认为这样的结果是不符合条件的。而图 12 中的曲线变化规律相当规整，我们认为这样的结果是正确的。l 英文字基于底线间距（行距）的碎片拼接英文字基于底线间距（行距）的碎片拼接 因为英文文字比较稀疏，横切的时候可能会有多个两端空白的碎片行在其中，利用02040608010012014016018005101520像素位数行间距020040060080010001200140016001800200005101520像素位数行间距020040060080010001200140016001800200005101520像素位数行间距获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 12 碎片纵向匹配距离 dr会出现问题。为了对其进一步优化，我们之前分析得到英文字母的底线间距一定（63 个像素单位），我们可以通过之前的方法求出每个碎片行的底线位置。如果两个碎片行相邻则其两个底线之间的距离应该尽可能逼近 63，所以我们引入一个碎片纵向逼近距离 de(i,j)=63-mod(l(i,j),63)，其中 mod(l(i,j),63)为碎片 Ai、Aj底线之间距离与 63 做取余数运算，因为 de(i,j)与 dr(i,j)的量纲不一致，所以我们可以对其先进行标准化（除以各自的最大值）得到 de*(i,j)和 dr*(i,j)，我们定义一种新的复合距离dre=dr*(i,j)+de*(i,j)，如此便可以转化为旅行商问题进行排序。5.2.3 问题二的求解结果问题二的求解结果 对于附件 3 的中文字碎片，由模型二的建立与求解，得到最后的结果见附图二（a）、附表一。对于附件 4 的英文字碎片，由模型二的建立与求解，得到最后的结果见附图二（b）、附表二。其中人工干预的时间节点为对行分组碎片横向拼接后。其人工干预方式，我们举例说明。以 191 号碎片所在行为例，利用模型一拼接策略对行分组碎片横向拼接得出的结果如下：图 13 附件 3 中 191 号碎片所在行错误序列 我们从图13中可以看出红色框的碎片拼接出现了问题。某些碎片有一个共同特征，两侧中有一侧为白色，且与其匹配的左侧或右侧碎片边缘也为白色，产生了背景色匹配背景色的情况，即匹配距离小的情况，在这种情况下，产生的答案可能是不正确的，而且同一碎片行中带有白色边缘的数量越多，错误匹配的可能性越大。在这里，我们进行人工干预，容易发现该段碎片行上面部分文字有断裂，将红色框内涉及的碎片顺序进行交换后，得到新的序列，并画出图像验证，手工调整的结果正确。正确图像如图 14 所示。图 14 附件 3 中 191 号碎片所在行正确序列 5.3 问题三问题三 5.3.1 模型三主要思想模型三主要思想 模型三主要解决碎片有双面内容的还原。该模型同模型二，将原问题分解为若干模型一中的旅行商问题，但考虑到碎片的双面问题，我们将文本行距匹配距离替换为正反文本行距匹配距离。在对碎片进行航分组与拼接等处理方法同模型二。此外，值得一提的是，由于纸张有两面，所以该模型中对碎片行纵向拼接时用到模型一的拼接策略为多旅行商的情形，即对一个被切成切为nrnc个双面碎片的纸张，需要做 nr次横向旅行商问题以及 1 次纵向多旅行商问题（2 个旅行商）。故，模型三的目标函数如下。获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 13 minfk()k=1,2 nr min f()=d(i)(i+1)1nr+d(i)(i+1)nr+12nr 其中，当 k=1,2 nr时 fk()为横向旅行商问题的目标函数，其匹配距离为正反面碎片边界横向匹配距离，当 k=nr+1 时 fk()为纵向旅行商问题（2 个旅行商）的目标函数，其匹配距离为正反面碎片边界复合匹配距离。5.3.2 模型三的建立与求解模型三的建立与求解 l 纸张左右两侧的碎片纸张左右两侧的碎片 同模型二，通过前面的方法我们可以搜索到属于左端的纸集合a54、a89、a99、a100、a114、a136、a143、a146、b3、b5、b13、b23、b35、b78、b83、b88、b90、b91、b105、b165、b172、b186、b199和右端的碎纸集合 a3、a5、a13、a23、a35、a78、a83、a88、a90、a105、a165、a172、a186、a199、b9、b54、b89、b99、b114、b136、b143、b146。因为纸面 a 面与 b 面是在一张纸的同一个地方，有其独特的性质，例如 a 纸在左上角则对应于其同一个地方的 b 面纸，则在其面的右上角。所以，我们可以通过此种方法对其集合 A、B 进行检验最后发现 A 集合多出 a100、b91，缺少 a9，B 集合正确，所以得到最终集合 A、B。l 正反匹配距离正反匹配距离 同上文中用到的一些匹配距离，我们在第三问中会用到类似的匹配距离，但其定义略有不同。正反面碎片边界横向匹配距离：正反面碎片边界横向匹配距离：dr*(i,j)=aqkia1ki+afqkiaf1kjk=1p 其中 p 为碎片像素矩阵 Ai的列数 af 为 a 的反面。正反文本行距匹配距离：正反文本行距匹配距离：dg*(i,j)=|rirj|+|frifrj|其中 fri为碎片 Ai反面的行距特征向量。正反面碎片边界复合匹配距离：正反面碎片边界复合匹配距离：dre*(i,j)=dre(i,j)+fdre(i,j)fdre(i,j)为碎片 Ai反面和碎片 Aj反面之间的复合距离 l 基于纸张碎片左右分组的碎片行分组基于纸张碎片左右分组的碎片行分组 方法同模型二 l 横向碎片拼接横向碎片拼接 我们只需要将文本行距匹配距离替换为正反文本行距匹配距离，碎片横向处理方法同模型二。l 纵向碎片拼接纵向碎片拼接 在对纵向多旅行商问题（2 个旅行商）的处理上，我们发现可以通过改变距离矩阵将 2 个旅行商的问题简化为一个旅行商的问题，只需要把不属于同一列的首尾间距离定义为 0，其意义即相当于旅行商的又一次出发，将其转化为多旅行商问题。在该问题中我们可以通过边界碎片查找算法找到该碎片行中处于原图第一行的碎片行 y1,y2和最后一行的 s1,s2。所以我们只需要令 d(y1,s1),d(y1,s2),d(y2,s1),d(y2,s2)都为 0 即可。因为该碎片行图有正反面，所以我们以正反面碎片边界复合匹配距离 d*re(i,j)来表示其两两之间的距离。因为每张碎片自身的正反面不可以相互连接，所以我们定义其间的获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657 14 距离为一个足够大的数字 M，d(i,j)的意义代表第 i、j 碎片行之间的正反匹配度距离。综上所述，我们可以得到距离矩阵中 D 中第 i 行第 j 列的元素 d(i,j)计算公式如下 d(i,j)=首尾相连碎片行为正反面第其它0,),(*jiMjidre 计算得到所有的 d(i,j)之后，只需要根据目标函数(7)，利用 lingo 求解即可。5.3.3 问题三的求解结果问题三的求解结果 对于附件 5 的碎片，由模型三的建立与求解，得到最后的结果见附图三、附表三。此外，根据模型三对问题三的求解过程中无人工干预，我们分析其原因下。l 干预分析 因为我们建立的指标包含碎片双面的信息，所以碎片可用于拼接的信息增加一倍，在之前单面的分析中，我们了解到在排行出问题的碎片中其基本特征为两边空白面积大，即被切割的地方在空白处，而在双面的碎片中，其两面都切到空白的概率很低，所以一般不会出问题。模型的优点与改进模型的优点与改进 6.1 模型的优点模型的优点 l 将碎片拼接问题抽象为旅行商问题（不回到源点的旅行商问题），有利于利用现有算法找到全局最优解，并且具有一定的扩展性。在本问的三问中，均有使用，体现出我们模型的连贯性。l 根据文本行距特征，对碎片行分组，既简化了问题便于拼接，同时体现了对文本碎片的具体的探究。6.2 模型的改进模型的改进 l 在行距调整过程中我们用调整碎片段再评判行距的方法，其实也可以直接根据碎片行的行距特征做一定计算直接拼接出结果。l 由于我们将模型一已转化为旅行商问题，而旅行商问题是一个已被证明的“NP 难”问题，当图中顶点个数很多时，传统的方法已不能在可接受的时间内给出最优解。在本文所解决的问题中均未涉及到太多的顶点，所以用 0-1 整数规划方法可以得到最优解，但是实际情况下，碎片数可能很庞大，此时借鉴遗传算法解决旅行商问题的方法可以解决，遗憾的是我们没有时间将结果实践出来。l 纸张纵切时若没有切到任何文字时，我们是人工干预完成的。改进方法为将原来 11的单个碎片组合成 21 的碎片组合，减少人工干预次数。l 对碎片分组考虑到了一些文本特征，所以除了用本文所用的