基于TSP和模拟退火算法的碎纸拼接模型

肖松平 张立臣 冉庆波 张丽颖 王立亚

摘 要：本文围绕碎纸片拼接问题，建立了碎纸片复原模型、复原 TSP 模型、降维模型、改进的模拟退火算法模型并成功的运用到了纸片的拼接问题中，利用降维的思想将问题二维问题转化成一维问题，并运用 MATLAB 编程求解出最终结果。

针对一维问题，设计了一维碎纸片复原算法，首先提取出图像的像素矩阵，根据像素矩阵特征建立识别数字a ，分别求出最左和最右识别数字，然后将碎纸片复原问题转化为复原 TSP 问题。针对二维问题，运用降维的思想设计了二维碎纸复原法，由于汉字的字高和字宽是确定的，而英文字母的高度不一致，所以先对英文的碎纸片进行标准化，人工对标准化有误的图片进行修正，然后分别提取碎纸片的像素矩阵，用 MATLAB 编程对他们进行初步分类，得到 11 类特征相同的碎纸片，然后将问题转化为 11 个一维碎纸片问题的求解，带入到模拟退火算法中得到正确的复原图形及序列。

最后，本文对所建模型进行了客观的评价，并结合实际对模型的推广加以分析。

关键词：碎纸片拼接；复原TSP模型；改进的模拟退火算法模型；降维模型

1.算法方法理论基础

1.1 TSP问题

TSP问题就是旅行商问题，它是最基本的求解线路问题。这个问题简单的来说，就是“假设有一个旅行商要拜访n个城市，他必须选择好要走的路径，路径的限制条件是每个城市只能拜访一次，而且商人最后要回到从开始出发的那个城市。”路径的选择目标是求选择的路径的路程是所有路径路程中的最小值[5]。

1.2 模拟退火算法

模拟退火算法原理来自于固体退火原理，是一种通用的随机搜索算法。其原理是将固体加热是温度上升到到充分高，再让其慢慢冷却，加温的时候，随着温度的升高固体内部的粒子会变为无序状，内能增大，而慢慢冷却时粒子渐渐趋向有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。优化问题和固体退火过程之间有一定的相似性。把对用固体在恒定问题下达到热平衡过程的模拟引入优化过程中。即如果：

则接受新的状态，否则按概率 接受新的状态。

为一个随时间t增加而下降的参变量，相当于退火过程中的温度。这种利用优化问题求解与物理系统退火过程的相似性，使用Metropolis算法，适当地控制温度的下降过程，实现模拟退火，达到求解全局优化问题的随机方法称为“模拟退火算法”[6]。

2.算法方法理论基础

2.1 信息的提取

根据计算机图形的相关知识，划分空白位置和字符位置前，需要对图片像素进行处理，通过灰度化，将图片像素定位为[0，255]区间内，再通过设定阀指，区分空白位置和字体， 为了更加准确的识别出每幅图片的最大像素之和a，只取最大像素 255 作为计数点，其他像素不予考虑。因为图片是非彩色的所以仅需考虑空白和非空白情况。为了使图片能够清晰的描述空白位置和字符位置，利用数学软件 MATLAB 对图像进行预处理，将图片导入 MATLAB，得到对应的像素矩阵，由计算机图形学知识可知，空白位置的像素值为 255，为了使像素矩阵更明显，能更加清晰的看出像素之间的区别， 我们将矩阵中 0 和 255 的颜色进行互换，得到的一系列的像素矩阵，可用于像素的特征提取。

2.2 复原 TSP 问题

TSP 问题即旅行商问题是数学领域中最著名的问题之一。“假设有一个旅行商人要连续拜访 n 个城市，他需要选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到开始出发的城市。” 路径的选择目标是要求得的路径路程为所有路径之中的最小值。示意图如下：

图 2 TSP问题示意图

若将每个碎纸看成一个城市，碎片和碎片之间存在吻合度，如果两张碎纸的吻合度低，那么他们对应的距离也大，当吻合度为0时，所对应距离为 。所以寻找吻合率最高的的碎纸片组合方式，其实质就是寻找总距离最小的路径，也就是找寻一条最佳TSP商旅路径，只不过最后不再要求回到最初的城市（即第一张纸片）。示意图如下：

图 3 碎纸片拼接示意图

将碎纸片复原抽象成复原TSP问题，总的距离（符合度）公式如下：

其中R（i） 第i 块碎纸片的右识别数字，L（i+1） 代表第i 块碎纸片的左识别数字。

2.3 改进模拟退火算法模型的建立

2.3.1 编码选择

TPS 的编码策略上有近邻编码，次序编码，二进制编码，和路径编码等。近邻编码必须考虑算法的合理性；次序编码不利于全局优化；二进制编码不自然，且需附加修正算子来保证解得合法性。基于此，路径编码最符合本文环境。为了算法的简便，对图片重新进行编号，将 000 号改为 19 号，其余不变。编码类似于 1-2-3-4？？？ -17-18-19。

通过求解复原TSP问题，可以得到每个碎纸片的访问顺序，即碎纸片的拼接序列，利用改进模拟退火算法得到复原纸片[6]。

3 结论

本文对碎纸片拼接技术的背景及现状进行了简单的介绍，探讨了对于碎纸片拼接技术研究的重要性和现实意义，提出了一种基于TSP模型和改进的模拟退火算法相结合的拼接模型。可以为有关部门进行纸片拼接时提供科学的参考，缩短拼接时间，提高拼接准确率。

本文的主要工作和创新点有：

（1）将碎纸片拼接和TSP商旅模型联系在一起，找出二者之间的联系，建立复原TSP模型，缩小计算量。

（2）对于复原的TSP模型，采用改进的模拟退火算法进行求解，改变新解的产生方式，加快收敛的速度，缩短计算时间，提高了计算精度。

（3）对于高维问题，提出降维模型，使得本文中的模型可以处理数量更多，更复杂的复原问题，从而拓展了本文的适用范围。

参考文献：

[1] 劉令， 刘元， 孟凡清. 浅谈基于矩阵运算的碎纸片拼接问题[J]. 山东工业技术， 2014（12）：202-202.

[2] 罗智中. 基于文字特征的文档碎纸片半自动拼接[J]. 计算机工程与应用， 2012， 48（5）：207-210.