基于改进遗传算法的自动拼图

张大伟 张婷婷 秦瑜

摘 要：针对传统自动拼图算法在处理过程中出现还原速度慢和匹配精度低的问题，利用遗传算法有效搜索全局最优解的特点，提出一种基于改进遗传算法的自动拼图方案。由于图像数据信息的特殊性，在使用遗传算法处理图像时出现收敛速度慢和奇异数据导致无法收敛的情况。所提方案通过对图像边缘数据差进行归一化处理，加速遗传算法的收敛速度；通过增添阈值，控制所得最小度量值与次度量值的比值来提高自动拼图的准确率。实验结果表明，改进遗传算法在自动拼图中计算速度和匹配准确度方面都有明显的提高。

关键词：自动拼图；遗传算法；归一化；阈值

0 前言

拼图源于将一张完整的图像，按一定规则随机切块（包括有几何形状的碎片和方形碎片两种），各碎片互相不重叠，并且可以按照一定的链接方式，将其还原成未切块前的完整图像。随着计算机技术的发展，可以借助计算机强大的计算能力进行智能还原图片，因此拼图算法如何设计显得尤为重要。为了实现拼图误差最小化和提高图像匹配的速度，本文在Pomeranz和Gallagher算法的基础上作了改进，并结合GA是全局搜索最优解的算法，提出一种边缘度量信息的归一化和最优选择阈值的方法，可以快速全自动的还原拼图。

1 遗传算法的原理

首先对具体的问题进行分析，尝试去建立表现型与基因型的潜在关系，制定一套针对具体问题的“数字化”编码的方案；然后根据实际情况设定一个数值，作为初始化种群，种群里面的个体信息映射出的就是方案中数字化的编码信息；最后，使用合理的的解码方式，用适应性函数按照某种规定择优选择，让个体基因交叉变异，得到新的种群。

GA的優点：1）整体搜索，并行化处理简单，更容易得到最优解；2）不是盲目穷举，而是启发式搜索；3）适应度函数不受约束，适用范围很广；4）容易实现，对于处理一个新的问题，只需要一套合适的基因编码方案，以及合理准确的适应度函数，对遗传算法的程序稍微的做改动就可以。

终止条件：在程序中是采用了两个停止准则。1）最大代数为20，为了防止出现不收敛或者迭代次数过多的现象，所以设定最大的执行次数。2）当适应度函数值变化小于设定的阈值时，运算将停止，如果始终达不到这个条件，就达到最大迭代次数时停止进化迭代。

2 基于遗传算法的智能拼图

拼图问题的解决主要经历了三个阶段，第一阶段是完全使用碎片的形状信息，第二阶段是利用碎片的形状信息以及颜色信息的混合信息，第三阶段是方形碎片的拼图算法研究，方形碎片可以任意旋转，没有可用的形状信息，只能使用颜色信息。

将使用碎片差异度量SSD（Sum of Squared Distance Scoring）来进行选择相邻碎片，这是最简单的度量方式，仅使用碎片边缘的像素信息之间的差异计算。计算速度快，但是不够准确，如果直接使用还原图像往往无法达到预期的效果。SDD的公式为

MGC（Mahalanobis Gradient Compatibility）将马氏距离运用到碎片之间，不仅考虑最边缘的像素信息，还加入了边缘的梯度信息，使度量更准确，该方法虽然提高了准确率，但同时大大的增加了运算时间。MGC的公式为

为了后面数据处理的方便，加速GA 的收敛速度，对图像RGB三个通道的边缘数据的差进行归一化处理，使得所得到的均值都在0-1之间。改进的适应度函数为

交叉算子引入了“best buddies”概念，如果最优的碎片存在，则选择最优碎片；如果不存在最优的碎片则挑选满足“best buddies”关系的碎片；如果不存在则随机选择。 “best buddies”关系式为

3 实验结果

本文以Pycharm为软件开发平台，基于python语言来模拟以上拼图算法，所有的参数都相同，初始种群设定为600，最大迭代次数设定为20。改进的遗传算法（Improved Genetic Algorithm，IGA）即：同时添加归一化和阈值。在不同改进算法下还原拼图所用的平均速率和准确率的比较结果。通过比较分析，当对数据进行归一化处理时加快了还原速度，但准确率不变；添加阈值之后，还原速度基本不变，但准确率明显提高；采用AGA，自动拼图在还原速度和准确率上都明显的改善。使用不同算法还原拼图的准确率的对比。从图可知，本文所使用的IGA算法在碎片尺寸小于30*30的时候，准确率比MGC算法要略低；但是碎片尺寸大于30*30时，准确率明显优于其他方法。

解决智能拼图的过程中，最重要的是解决碎片之间的信息度量和最优匹配的问题。本文使用归一化和增添阈值结合的方案，有效的解决了这两个问题，从而提高拼图速度和质量。

4 结语

本文介绍改进的遗传算法主要是对适应度函数和交叉算子进行改进。GA的早熟现象主要表现为当还未达到全局最优解，群体中不能产生超越父代的子代，把局部的最优解作为全局解，故添加了归一化处理和最优阈值相结合可以更好地找到全局最优解。将改进GA运用到自动拼图不仅加快了还原拼图的速度，还提高了准确率。目前，拼块的尺寸越小，准确率也会直线下降，并且对于有部分信息缺失的图片，还是做不到百分之百的准确，为了更好的提高自动拼图的速度和准确度，后期会结合机器学习和深度学习的知识，搭建一个神经网络，利用深度网络去进行测试，或许会有更好的结果。相信不久的将来，可以做到百分之百的准确拼图。

参考文献：

[1] 鱼滨，张善文，郭竟等.基于MATLAB 和遗传算法的图像处理 [M]. 西安 ： 西安电子科技大学出，2015.

[2] 曹戴. 智能数字拼图算法研究及其应用[D]. 江南大学硕士学位论文. 2017，6.

[3] 田莹，苑玮琦.遗传算法在图像处理上的应用[J].中国图象图形学报.2007，12（3）：389～396.

[4] 朱陈柔玲，张达敏，张慕雪，杨菊蜻. 遗传算法在图像处理上的应用* [J]. 通信技术.

作者简介：

姓名：张大伟 （1992.04--） 性别：男，山西省运城市人，学历：硕士，专业：信息与通信工程。