基于旅行商规划模型的碎纸片拼接复原问题研究

摘要

本文分别针对 RSSTD(Reconstruction of Strip Shredded Text Document）、 RCCSTD(Reconstruction of cross-cut Shredded Text Document) 和 Two-Sides RCCSTD 三种类型的碎纸片拼接复原问题进行了建模与求解算法设计。首先我们对于 RSSTD 问题，建立了基于二值匹配度的 TSP 模型，并将其转化为线性规划模型，利用贪心策略复原了该问题的中文和英文碎片；然后对于 RCCSTD 问题，由于中英文字的差别，我们分别建立了基于改进误差评估的汉字拼接模型和基于文字基线的误差评估的英文字拼接模型，并利用误差评估匹配算法，复原了该问题的中文和英文碎片；随后我们针对正反两面的 RCCSTD 问题，利用基线的概念将正反两面分行，转化为 RCCSTD 问题，并复原了该问题的英文碎片。最后，我们对模型的算法和结果进行了检验和分析。

◎问题一：我们针对仅纵切的情况，首先将图像进行数字化处理，转换为了二值图像，然后得到各图像的边缘，并计算所有碎片与其他碎片边缘的匹配程度。然后，根据两两碎片之间的匹配程度建立了 TSP 模型，并将其划归为线性规划模型。最终，我们根据左边距的信息确定了左边第一碎片，随后设计了基于匹配度的贪心算法从左向右得到了所有碎片的拼接复原结果。结果表明我们的方法对于中英文两种情况适用性均较好，且该过程不需要人工干预。

◎问题二：我们针对既纵切又横切的情况，由于中英文的差异性，我们在进行分行聚类时应采用不同的标准。首先根据左右边距的信息确定了左边和右边的碎片，随后分别利用基于改进误差评估的汉字拼接模型和基于文字基线的误差评估模型，将剩余的碎片进行分行聚类，然后再利用基于误差评估的行内匹配算法对行内进行了拼接，最终利用行间匹配算法对行间的碎片进行了再拼接，最终得到了拼接复原结果。对于拼接过程中可能出现误判的情况，我们利用 GUI 编写了人机交互的人工干预界面，用人的直觉判断提高匹配的成功率和完整性。

◎问题三：我们针对正反两面的情况，首先根据正反基线信息，分别确定了左右两边的碎片，然后利用基线差值将其两两聚类，聚类以后其正反方向也一并确定，随后我们将其与剩余碎片进行分行聚类，最终又利用行内匹配和行间匹配算法得到了最终拼接复原结果。其中，对于可能出现的误判情况，我们同样在匹配算法中使用了基于 GUI 的人机交互干预方式，利用人的直觉提高了结果的可靠性和完整性。

关键字：碎片复原、TSP、误差评估匹配、基线误差、人工干预