《2013高教社杯全国大学生数学建模竞赛题目》由会员分享，可在线阅读，更多相关《2013高教社杯全国大学生数学建模竞赛题目（22页珍藏版）》请在金锄头文库上搜索。
1、基于最小匹配误差的碎纸片拼接复原模型 摘要 对碎片的拼接复原工作在司法、军情获取、历史文献修复等方面具有举足轻重 的地位。人们为了使碎片的拼接复原工作效率更为高效，尝试开发利用计算机 拼接碎片技术。这往往需要人为的对碎片进行一些加工处理，然后再结合计算 机技术，来实现对碎片的拼接复原工作。 针对问题一，首先对碎片进行灰度处理，然后对数据进行二值化处理。问题一 是对纵切碎片的拼接复原问题，碎片边缘信息较多，故我们只需要考虑每张碎 片的边缘信息，使其生成边缘矩阵就好。对碎片进行二值化处理，用0,1来表 示边缘像素点的值，大大简化了问题一的求解。利用二值化处理出的数据，建 立旅行商问题模型，即 TS
2、P 模型，使得碎片匹配误差最小，从而完成碎片的拼 接复原。 针对问题二，考虑到是在问题一的基础上对纸张再进行横切的碎片的拼接复原 问题。首先我们还是对碎片进行灰度处理和数据二值化处理，由于纵切和横切 使得碎片变小，碎片所含信息变少，故我们提取碎片四周的边缘信息。附件 3、4 中所给碎片数量多，碎片的边缘信息总量比较大，所以我们利用 SPSS 软 件对碎片上边缘进行聚类分析，想要达到简化问题二求解的目的。通过对附件 3、4 中大量碎片进行观察，我们根据碎片上边缘的空白截距、文字截距和行间 距，将碎片大致分为三类，然后利用碎片上边缘的裁截距对碎片进行聚类分析， 从而将大量碎片进行分类，简化问题的求
3、解。首次聚类并未得到理想的分类， 故我们在第一次聚类的基础上，根据上边缘是否为文字，对碎片再次进行分类， 并借助一定程度的人工干预，使得碎片平均分为 12 组。根据得到的 12 组碎片， 利用问题一建立的模型使得碎片之间匹配误差最小，分别对 12 组内的碎片进行 拼接。然后利用问题一的求解方法，对 12 组间的碎片进行拼接复原，问题二碎 片的具体拼接复原结果详见附录。 针对问题三，考虑到对双面打印文件的纵切和横切的到碎片的拼接复原问题， 我们采用一步步简化的思想，把该问题分解为在问题二的求解基础上增加难度 和复杂度的双面打印文件碎片的拼接复原问题。首先还是要对附件中碎片进行 灰度处理和数据二值
4、化处理。由于问题三中碎片面积太小，所含边缘信息太少， 故我们同问题二一样，利用 SPSS 软件对碎片进行聚类分析。然而第一次的分类 结果却不是很理想，故我们考虑下边缘信息，再次进行聚类分析。加以一定的 人工干预，直至将碎片平均分为 11 组。再利用模型二中匹配误差最小原则，寻 找每张碎片的最优匹配的碎片，最终结果详见附录。关键字： 灰度处理 二值化处理 TSP 聚类分析 匹配误差 一.问题重述 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有 着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很 低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着
5、计算机 技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请 建立以下问题模型： 1.1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切） ，建立碎 纸片拼接复原模型和算法，并针对附件 1、附件 2 给出的中、英文各一页文件 的碎片数据进行拼接复原。如果复原过程需要人工干预，要求写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。 2.2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针 对附件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。要求 同问题一。 3.3. 上述所给碎片数据均为单面打印文件，从现实情形出发，
6、还可能有双面打印 文件的碎纸片拼接复原问题需要解决。附件 5 给出的是一页英文印刷文字双面 打印文件的碎片数据。设计相应的碎纸片拼接复原模型与算法，要求同上。 二问题分析 2.1 问题一的分析 由于考虑纵切碎片的拼接复原问题，碎纸片的边缘信息量比较大，因此仅利用 边缘信息进行求解。在本题中，我们将每一个碎片看做一个完全图的顶点，将 问题转化为一个旅行商的模型，即 TSP 问题模型。寻找一条经过每个顶点（仅 经过一次） ，不回到原点的最短路径，使得边权值之和达到最小。其中，边权值 为相邻两个碎片之间的匹配误差。对碎片进行二值化处理，可以大大简化该问 题的求解。首先我们根据数据二值化处理结果，可以
7、找到纸张最左边的碎片， 而后以最左边的碎片为起点，利用遍历法求解出第二张碎片。依次进行下去， 我们可以得到纸张碎片的整体排序。对于为正确处理的碎片，我们要采取一定 的人工干预进行调整求解。 2.2 问题二的分析 由于问题二考虑的是对碎纸片既纵切又横切拼接复原问题，根据附件信息可知， 纸张被分别切成 1224 个碎片和 1018 个碎片，碎片太小，所含边缘信息量 太少。所以利用 SPSS 软件，采用聚类分析方法，对大量的碎片进行分类。其中， 纵切碎片的拼接复原问题的求解同问题一，在此基础上，我们只考虑碎片的横 切拼接复原问题。提取碎片四周的边缘信息，首先，根据上下边缘信息对碎片 进行分类，对于其
8、中未正确处理的碎片进行一定程度的人工干预。处于同行中 的碎片拼接问题，求解同问题一模型。 2.3 问题三的分析 由于问题三考虑的是对英文双面打印纸张既纵切又横切的碎片的拼接复原问题， 根据附件 5 中 21119 个碎片，每个碎片的面积变小，碎片数量太多，这对 于我们对双面打印文件的拼接复原感到更困难。故我们还是采用聚类分析，首 先将附件 5 中正反面分开，然后再分别对正反面碎片进行聚类分析。由于英文 字体的特殊性，我们需要利用碎片的上、下边缘信息，对碎片进行两次聚类分 析，并加以一定的人工干预，分别将正反面碎片平均分为 11 组。然后，同问题 一一样，对这 11 组碎片进行组间之间的匹配，遵
9、循匹配误差最小的原则对碎片 进行拼接，此处也会用到人工干预，最后达到合理的结果，详细结果见附录。 三模型假设 1.假设每一附件为同一页纸的碎片数据。 2.假设对于同一附件的碎片拼接复原，碎片中的文字字体格式，行间距相同。 3.假设碎片中文字颜色与背景颜色相差很大。 4.假设纸张的左右边距均为固定值。 四符号说明 碎片 i 和碎片 j 之间的匹配误差 (,)碎片 i 的信息矩阵第 k 行最后一列 (,1)碎片 j 的信息矩阵第 k 行第一列ai碎片由上边缘向下边缘由白过渡到黑的距离 bi字符高度 c1碎片由上边缘向下边缘由黑过渡到白的距离 d1行间距 第张图片的裁截距 五模型建立与求解 5.1
10、问题一的求解 5.1.1 问题一的数据处理 (1)二值化处理 由于纵切碎片的边缘信息量比较大，因此我们采用二值化的方法对图片进行处 理，这种方法简化了对题目一的求解。用 matlab 编程，我们可以得到每张碎片 边缘的像素矩阵信息。像素点值取0,1，其中黑色用 1 表示，白色用 0 表示。 具体编程如下：(2)边缘矩阵的建立 因为是对每条碎片进行拼接，故我们只考虑边缘信息就好。对每条碎片进行边 缘信息处理，利用上述的二值化处理，具体编程如下：(3)寻求纸张最左边和最右边的碎片 我们的思想是从大量碎片中寻找出纸张最左边的碎片，然后用其他剩下的碎片 的左边的的边缘信息与纸张最左边碎片的右边的边缘信
11、息进行匹配。同样的， 找出纸张最右边的碎片，用其左边缘信息与其他剩余碎片的右边缘信息进行匹 配。用 matlab 编程寻找纸张最左边和最右边的碎片的过程如下：5.1.2 匹配误差的定义用一张碎纸片的右边缘信息和另外一张碎纸片的左边缘信息进行匹配误差计算， 两者之间的匹配误差越小，匹配度越高。 为此提取每张碎片左右边缘信息矩阵，对每两张纸片进行分析判断，遵循匹配 误差最小的原则，求得最匹配的碎纸片拼接方案。 为了衡量两个碎片之间的匹配程度，我们定义匹配误差作为评价的标准，其中为碎片 i 和碎片 j 之间的匹配误差，其计算公式如下：= = 1|(,) (,1)|注：q 为碎纸片 i 的像素信息的最
12、后一列。5.1.3 模型建立 首先，对于被纵切的碎纸片的拼接复原问题，其实是找到它们之间一个最好的 排列顺序，使得每一个拼接处都尽量达到 100%的正确。为了寻找最好的排列， 就要使每两个相邻碎片之间匹配的可能性最大，因此可以利用碎片的左右边缘 信息，使得碎片 j 拼接在碎片 i 后面的可能性最大，即为他们之间的匹配误差最 小。 由以上分析，我们可以把此问题转化为一个图论问题。把碎片看作一个完全图 的顶点，其中的边权值为碎片之间的匹配距离，即匹配误差，在此用表示顶点 i 与顶点 j 之间的匹配距离，匹配距离越小，表示匹配误差越小，两个碎片匹 配的越好。 为了寻找使所有碎片之间的匹配最好，将此问
13、题转化为一旅行商问题，即寻找 一条经过每一个顶点（且仅经过一次） ，最终不回到原点的路径，使得边权值之 和达到最小的 TSP 问题。 如下图所示，以五个顶点的碎片为例：(1) 其中，顶点表示碎片，有向线段指向表示从前一个碎片的右边缘到下一个碎 片的左边缘，有向线段的长度表示前后两个碎片的匹配距离，即匹配误差。 (2) 现在要寻找一条经过每一个顶点的回路，使总匹配误差最小。 为了解决以上 TSP 问题，建立如下模型: 假设图 E 中存在哈密尔顿回路，有 n 个顶点，其中边(i，j )的权重为，设 01 变量为=1，表示边(i，j)在图的回路中，则模型如下：Min (i，j ) s.t. =1(i
14、，j ) =1(， ) ，(i，j)0?,1 求解该问题即为线性规划中的 01 规划问题。 5.1.4 模型求解 根据问题一的模型，我们设计了如下算法： (1) 先选出左侧均为白色像素的碎片 i，并从碎片集合中剔除； (2) 依次计算碎片 i 的右侧边缘与剩余碎片的左侧边缘的匹配误差；(3) 选取使最大的碎片 j，拼接在碎片 i 的右侧，并记其为碎片 i，将其从碎片集合中剔除； (4) 重复操作(2)(3)，直到碎片集合中没有碎片剩余为止。 算法的流程图如下所示：根据以上问题一的模型与算法，我们进行了 Matlab 编程与求解，最终得到了碎 片之间的排列，并再次用 Matlab 软件进行编程，
15、使碎片进行拼接，最终得到附件 1 和附件 2 中碎片的排雷序列如下所示：通过求解结果发现，附件 1 得到的结果非常好，即中文图片用此方法可以得到 很好的拼接复原。但是，附件 2 中英文图片在序号 10 之后出现了重复，没有得 到完整的复原图。分析原因可能是，此英文图片的边缘信息量太少，导致匹配 误差变大。 为了得到附件 2 的完整图片，我们对其进行了人工干预。 首先将前六个未出现重复的排列正确的碎片拼接在一起，得到图片 1 如下：接着把一直出现重复的碎片 4、5、11 按照此顺序拼接成为一张图片 2。 剩余的图片仍按照以上编程进行排列求解与拼接，得到一张图片 3，排序如下：剩余碎片 8 记为图
16、片 4，将以上四张图片经过人工干预，最终拼接为一个整体 的图片，排序如下：5.2 问题二的求解 5.2.1 模型准备 (1)信息提取 首先在画图工具中，将附件 2 中的图片格式由 png 转化为 jpg 格式，其次对图 片进行灰度处理，最后进行二值化处理（方法同问题一） 。我们对每张碎片上下 左右四个边缘进行信息提取。 (2)聚类分析 由于既纵切又横切的碎片太小，边缘所含信息较少，故不能直接求解问题二， 我们采用聚类分析的方法，对碎片进行分类。在此处，我们先以中文的碎片拼接复原问题进行分析，英文的碎片拼接复原问题与中文的问题分析过程大同小 异。 首先，我们通过对附件 3 中的大量图片进行观察分析，发
