1
题目：基于旅行商模型的文字碎纸片拼接复原
摘要
文字碎纸片拼接复原是一项在司法物证复原、历史文献修复以及军事情报获取等领
域有着广泛应用的工作。所以对文字碎纸片的研究的重要性不言而喻。本文研究的目的
皆在建立数学模型与算法，解决碎片复原中的三个问题，使得对三种不同特点碎片复原
的人工干预次数较少，尽可能实现碎片复原的全自动化。
问题一，对纵切碎片复原。我们建立模型一，给出了基于旅行商问题的拼接策略。
我们发现，碎片的拼接问题就是找到碎片最好的排列，找到一个排列类似于在一个图中
找到一条路径。基于此，我们将碎片拼接问题抽象为一个图论问题，将碎片看做图中的
顶点，碎片与碎片之间的匹配程度(匹配距离)看做图的边权。由此我们将碎片的拼接
问题转化为一个哈密尔顿路径问题(不回到源点的旅行商问题)。
在问题一中的匹配距离为碎片边界横向匹配距离，即为一种衡量碎片与碎片在左右
方向上边界图像匹配程度的指标，匹配距离越短，说明两碎片边界越相似，匹配程度越
好。
模型一可用 lingo 与matlab 编程求解。由于旅行商问题的求解是整体寻优，得到的
结果为全局最优解，所以其准确性较高。对附件1与附件2的碎片还原结果我们没有进
行人工干预。
问题二，对既纵切又横切的碎片复原。我们建立模型二，给出基于文本行特征的碎
片行分组算法，对行分组碎片进行横向拼接得到复原的碎片行，再对碎片行进行纵向拼
接，得到最终复原结果。这两种拼接策略均为模型一中基于旅行商问题的拼接策略。
其中，文本行特征即为文本行之间的规整性，利用文本行的规整性不仅可以对碎片
进行行分组，而且还可以提高文本纵向拼接的准确度。
我们根据模型二，对附件3碎片还原的结果没有人工干预；在对附件4碎片还原时
在行分组碎片横向拼接后有人工干预，即偶尔人工调整个别碎片还原结果。
问题三，对双面碎片复原。我们建立模型三，该模型中对碎片的行分组以及横向拼
接同模型二中的方法，但考虑到碎片有两面，所用到的匹配距离需要替换为正反面匹配
(两面的匹配距离之和)。此外，在对碎片行做纵向拼接时与模型二中的方法略有不同，
由于碎片有双面信息，我们将模型一中基于旅行商问题的拼接策略扩展为多旅行商(2
个旅行商)问题的拼接策略，即一条旅行商路径代表纸张的一面，另一条旅行商路径代
表纸张的另一面。
对于模型三，由于采用了正反面匹配距离，用到了两面信息，其可用于拼接的信息
量相对于单面碎片而言增大了一倍，所以对附件5碎片还原结果没有人工干预。
综上所述，我们建立的碎片复原模型与算法人工干预次数较少，对碎片复原工作有
一定的参考价值。
关 键 词 ： 哈 密 尔 顿 路 径 旅 行 商 问 题 匹 配 距 离 文 本 行 特 征 碎 片 分 组
