张大伟 张婷婷 秦瑜

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

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

0 前言

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

1 遗传算法的原理

首先对具体的问题进行分析，尝试去建立表现型与基因型的潜在关系，制定一套针对具体问题的“数字化”编码的方案；……