碎纸片拼接复原算法研究

摘要

现实中获取的碎纸片多种多样,因此,对碎纸片进行拼接复原非常具有挑战性.本文针对规则切割的碎纸片复原问题提出了基于碎纸片自身携带信息的启发式算法.提出的模型考虑了原始文档的布局和排版信息,提出的模型引入了基线的概念对碎纸片按行归类.本文提出了将碎纸片拼接复原问题转换为非对称旅行商问题,并采用Lin-Kernighan算法对旅行商问题求解,从而得到碎纸片的正确排列顺序.针对中文和英文两种类型的碎纸片采用了一致的分析方法.实验表明上述问题通过算法得到了很好的解决,本文的方法比单纯地基于边缘像素的复原算法表现出色.本文提出了一种新的碎纸片拼接复原算法,通过引入基线概念对中文和英文碎纸片采用一致的分析方法.实验结果表明,算法对基于中英文碎纸片的文档重建具有较好的自适应性,能够最大限度地复原原始文档.