基于旅行商模型的文字碎纸片拼接复原-浙江工业大学.rar

2013 高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参

赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网

上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： B

我们的参赛报名号为（如果赛区设置报名号的话）：

所属学校（请填写完整的全名）： 浙江工业大学

参赛队员 (打印并签名) ：1.

2.

3.

指导教师或指导教师组负责人 (打印并签名)：

（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容

2013 高教社杯全国大学生数学建模竞赛

编 号 专 用 页

赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

全国统一编号（由赛区组委会送交全国前编号）：

题目：基于旅行商模型的文字碎纸片拼接复原

摘要

域有着广泛应用的工作。所以对文字碎纸片的研究的重要性不言而喻。本文研究的目的

皆在建立数学模型与算法，解决碎片复原中的三个问题，使得对三种不同特点碎片复原

的人工干预次数较少，尽可能实现碎片复原的全自动化。

我们发现，碎片的拼接问题就是找到碎片最好的排列，找到一个排列类似于在一个图中

找到一条路径。基于此，我们将碎片拼接问题抽象为一个图论问题，将碎片看做图中的

顶点，碎片与碎片之间的匹配程度（匹配距离）看做图的边权。由此我们将碎片的拼接

行人工干预。

片行分组算法，对行分组碎片进行横向拼接得到复原的碎片行，再对碎片行进行纵向拼

接，得到最终复原结果。这两种拼接策略均为模型一中基于旅行商问题的拼接策略。

进行行分组，而且还可以提高文本纵向拼接的准确度。

在行分组碎片横向拼接后有人工干预，即偶尔人工调整个别碎片还原结果。

接同模型二中的方法，但考虑到碎片有两面，所用到的匹配距离需要替换为正反面匹配

一定的参考价值。

广泛应用的工作。在碎片数量较小的情况下，人们可以根据碎片上的文字逻辑、形状、

纹理、色彩等快速将碎片拼接成功。然而现实中，更多地是要拼接大量的碎片，这时手

工的方法就不适用了，需要靠计算机辅助完成。

破碎纸片，主要解决文字碎片拼接中的以下 3 种情况。

! 所有碎片尺寸大小相等，边缘轮廓为规则的矩形。

! 所有碎片中的文字颜色一致，且与背景颜色有较大反差。

! 所有碎片图片只有两种颜色，文字颜色与背景颜色。

! 所有碎片中的文字边缘清晰，已被去除噪音。

! 所有碎片中的文字是从左至右、从上至下书写的。

! 所碎片都已摆放端正，即碎片中的文字端正。

! 所有碎片中的文本行距相等。

本文中，用到的主要符号与说明见表 1。

k

l

r

横切，其实也与纵切无异，同样地，我们可以将拼接好的碎片行用问题一的拼接策略拼

接起来得到最终的还原纸张。所以对问题二的处理过程中，我们首先需要先找到一些同

在一行的碎片。在本文中我们结合文字行距特征给出了碎片分组的算法。基于此，我们

建立了模型二。

行，用类似问题一的方法将碎片行拼接起来，但此时由于碎片有正反面之分，我们所用

的拼接策略是基于多旅行商问题（2 个旅行商）的。基于此，我们建立了模型三。

程度越好），将匹配距离作为完全图的距离，如此一来模型一即为边权值之和最小的旅

5.1 问题一

5.1.1 模型一主要思想

的排列，我们将碎片找排列问题转化为寻找一个符合特定条件的旅行商问题。

5.1.2 模型一建立

! 基于旅行商问题的拼接策略