基于模拟退火的空白填补碎片自动拼接算法❋

侯蓓蓓，于红斌，王鲜芳，王 鑫，孙广月，陈林林

（河南师范大学计算机与信息工程学院，新乡453007）

基于模拟退火的空白填补碎片自动拼接算法❋

侯蓓蓓，于红斌，王鲜芳，王 鑫，孙广月，陈林林

（河南师范大学计算机与信息工程学院，新乡453007）

针对形状规则的双面灰度碎片，建立了一种基于模拟退火的依次空白填补的拼接复原算法。以碎片的灰度矩阵建立距离矩阵，通过降温退火，逐次填补空白，得到碎片的大概排序结果，然后依据文意进行适当的人工干预，得到最终的拼接结果。逐次空白填补过程中对碎片不断进行修正检验，保证了拼接的准确性。仿真模拟证明了算法能完成对碎片的自动拼接，对比试验证明算法是相对高效和有效的。

空白填补；模拟退火；自动拼接

1 引 言

碎片拼接在日常生活中应用广泛，如考古工作，情报获取，司法取证等，自动拼接算法已经成为研究热点。如基于OpenCV和图像角点的拼接算法［1］，可以完成对二维不规则图像碎片的轮廓检测、角点提取、角点序列匹配、图像拼接及缺失修复；基于尺度不变特征的自动拼接技术［2］实现传感器网络中的图像拼接；基于Freeman练码的二维碎片拼接［3］，降低了算法的时间和空间复杂度；改进的遗传算法［4］和蚁群优化算法［5］，实现了碎片的全局拼接，提高了算法效率。在此采用基于物理统计力学的模拟退火算法，通过依次空白填补，实现了二维规则碎片的全局拼接，算法简单易于实现，相对其他算法人工干预减少，提高了算法性能。

源于统计力学的模拟退火算法通过不同温控改变粒子的能量，从而使粒子可以自由运动和重新排列。高温粒子的缓慢降温（即退火），使得不同温度下粒子热平衡点不同，系统完全冷却后，粒子将成为处于低能状态的晶体。

根据Metropolis算法描述的退火过程。当材料由高温转换为低温时，以概率1全部接受；而由低温转换为高温时，以概率接受转换。

2 基于模拟退火算法的碎片自动拼接复原

规则的双面碎片，无法确定碎片所属（正、反面），所以假设拼接目标是一张双倍大小单面纸，即由两张单面纸首尾相接而成。

2.1 数据处理

（1）碎片数据采集

每张碎片的数字图像信息可以矩阵A来表示：

其中aij是每个碎片相应点的灰度值。

（2）边界灰度矩阵

两片相连碎片必然具有相似的边缘，因此边界灰度值将是确定碎片顺序的重要参考，于是可以根据A矩阵构造碎片的首列信息矩阵Cs，尾列信息矩阵Cw，首行信息矩阵Rs，尾行信息矩阵Rw，即相应边界灰度矩阵。

2.2 算法思想

根据印刷习惯，纸张边缘会有一定空白，据此特点可以首先提取出边界碎片以提高算法自动搜索效率。

（1）定义距离矩阵

原本属于一体的两个碎片必然具有相似的边缘，因此可以基于碎片的边界灰度值确定碎片的顺序。

定义：距离矩阵d：

d（i，j）表示第i个碎片的尾端接第j个碎片的首端时的相似度。

（2）确定解空间和目标函数

假设规则有k个碎片，则一个有效的解空间具有如下结构：

使得该排列下，满足：

（3）代价差函数

任选序号m，n（m＜n）交换其顺序，产生新解：

则有代价差函数：

（4）接受准则

根据模拟退火思想，若Δf小于0，则以概率1接受新路径；否则，以概率e-Δf／T接受新路径，即：

（5）降温与退火过程结束

利用降温系数进行降温，即T＝aT，用选定的终止温度来判断退火过程是否结束。

（6）人工干预

将填补出来的纸张按照其文意，及正反面特征将其复原成双面。

2.3 算法流程图

算法流程图，如图1所示。

图1 算法流程图

3 仿真结果

依据上述提出的算法，通过MATLAB实现了对文献［7］中实验数据的分析，文献为双面英文碎片，横切11片，纵切19片，共形成规则碎片2×11× 19＝418个。

模拟退火要满足在每一温度下都达到热平衡，则降温过程需足够缓慢。在取值上，通过仿真实验发现，如果降温过程过慢，即a接近1，得到的结果比较精确，但效率太低，较其它搜索算法并不占优势；如果降温速度过快，即a接近0，则很可能得不到全局最优解。表1为a取0.999和0.95时，10次相同情况下降温的人工干预情况和降温时间对比。

表1 a不同值的人工干预和对比降温时间

为了提高精确度，仿真时采用降温系数a＝0.999，终止温度e＝10-30进行降温。通过模拟退火，得到最左端碎片的大概排序为：009a、083b、003b、143a、054a……114a、146a、165b、199b、088b，接着按空白填补算法依次填补拼接，并在适当位置进行人工干预，则最终拼接结果如图2所示。同时，将数据应用于文献的基于文字信息的拼接算法［8］，其拼接结果如图3所示。

图2 上述算法的部分拼接结果

图3 基于文字信息的部分拼接结果

在文意衔接上，可以直接看出，该算法更加准确。

表2是两种算法的时间对比，可以看出基于模拟退火算法的空白填补模型速度相对较快，效率较高。

表2 算法时间对比

4 结束语

通过碎片数字化处理，采用基于模拟退火算法的空白填补方法，借助计算机实现了碎片的自动拼接复原。但由于碎片数量大，需加入适当的人工干预来进一步提高其准确性，但相较于其他算法，效率和准确性相对较高。

［1］董乾，黄晓鸣.基于OpenCV的图像碎片拼接［J］.科学技术与工程，2010，10（22）：5429-5432.

［2］李铁军，陈哲，王任享.基于尺度不变特征变换的图像快速拼接算法［J］.微计算机信息，2008，24（4-3）：282-283，259.

［3］汪剑，皮佑国，刘明友.基于Freeman链码的汉字图像轮廓曲线拐角点检测方法［J］.自动化技术与应用，2009，28（1）：88-92.

［4］郑蓓蓓，郭立本.改进的遗传算法应用于碎片拼接［J］.计算机与现代化，2011（5）：52-56.

［5］何鹏飞，周宗潭，胡德文.基于蚁群优化算法的碎纸拼接［J］.计算机工程与科学，2011，33（7）：69-73.

［6］全国大学生数学建模（官网）.2013赛题：［DB／OL］.教育部高等教育司和中国工业与应用数学协会，2013［2013-9-11］.http：／／www.mcm.edu.cn／problem／2013／2013.html.

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

Automatic Stitching Algorithm of Debris by Gap-filling Based on Simulated Annealing

HOU Bei-bei，YU Hong-bin，WANG Xian-fang，WANG Xin，SUN Guang-yue，CHEN Lin-lin
（College of Computer and Information Engineering，Henan Normal University，Xinxiang 453007，China）

In order to stitch double gray debriswith regular shape，an automatic algorithm based on simulated annealing is proposed.It gives a distance matrix based on the gray matrix of the debris，fills the gaps through successive cooling annealing，and obtains the approximate order of the debris accordingly.Then，appropriate artificial intervention is performed according to the text to generate the final result of stitching.During the process of gap filling，the debris＇order is constantly revised to ensure the veracity of stitching.The simulation proves that the algorithm can achieve the automatic stitching of debris and the contrast experiment shows that the algorithm is efficient and effective.

Automatic stitching；Filled gaps；Simulated annealing

10.3969／j.issn.1002-2279.2014.03.010

TP301

：A

：1002-2279（2014）03-0033-03

河南师范大学青年科学基金（2013QK19）

侯蓓蓓（1993-），女，河南武陟人，本科生，主研方向：数字图像处理。

2013-12-04