基于遗传算法和0-1规划的规则图形碎片拼接

韩盈盈，章毅鹏，沈鸿平，王义康

(中国计量学院理学院，浙江杭州 310018)

图文碎片拼接在司法物证复原、历史文献修复以及军事情报获取等领域均有着重要的应用［1］。传统的人工拼接在效率上已经不能满足实际需要，因此，借助于计算机技术的快速自动拼接方法应运而生。罗智中提出了基于线段扫描的碎纸片边界检测算法研究［2］，Nasir Memon提出了应用贪婪算法实现图形碎片的自动拼接［3］，贾海燕提出了一种碎纸自动拼接中的形状匹配方法［4］，这些方法主要是利用碎片边界几何形状实现复原;对于规则碎片拼接，刘俊玮提出基于像素点灰度值的条状碎片文件自动复原的探讨和研究［5］，王丽娜提出了基于像素索引值的规则碎纸片拼接复原［6］，沈鸿平等人提出利用0－1规划对规则中文文字碎片的拼接进行研究［7］，这些方法主要是利用碎片边缘像素特征来实现复原。而对于规则的图形碎片，由于缺少文字边界和行列特征，拼接难度大，不易实现。

规则的图形碎片，碎片边界轮廓无明显几何匹配特征信息。本文通过提取规则碎片边缘的像素特征，确立了基于图片灰度值的匹配度指标，并建立了基于0－1规划的规则碎片拼接模型。考虑到模型本身的复杂性和求解方法对复杂模型的适用性，利用无需制定确定性启发式搜索规则的遗传算法进行求解，得到碎片拼接的结果，结果表明该方法效果良好。

1 规则图形拼接原理

对于规则的图形碎片来说，两碎片之间的拼接结果是唯一的，因此假设两张碎片完全匹配取值为1，否则取为0，从而可设0－1变量为

其中，xijst表示碎片i的s边缘与碎片j的t边缘匹配变量;s，t=1，2，3，4 分别表示碎片的上、下、左、右边缘。

对于碎片i，其由m×m个像素组成，取其上、下、左、右4 条边缘的灰度向量为 ris=(ris1，ris2，L，rism)T，s=1，2，3，4，s取不同值分别表示碎片的上、下、左、右4条边缘的灰度向量。由此可构建出描述碎片i的边缘灰度矩阵Ri

当图片的内容被一次切割之后形成两张碎片i，j，如图1所示，则碎片i的右边缘与碎片j的左边缘在对应同一个像素点处的灰度值应较为接近。

图1 10号和25号碎片灰度图及其右、左边缘扫描线

因为所有碎片均为大小相同的规则正方形，故其边缘灰度矩阵R均为m×4的矩阵。为了衡量碎片i的s边缘与碎片j的t边缘的接近程度，可通过计算碎片i的s边缘的灰度向量与碎片j的t边缘灰度向量的欧氏距离来定义匹配度。定义碎片i的s边缘与碎片j的t边缘的匹配度为

rjsn表示碎片j的s边缘第n个像素点的灰度值，其中s，t=1，2，3，4，ηijst匹配度越大说明碎片 i的 s边缘与碎片j的t边缘接近程度越大，两碎片拼接吻合度越高;越小，说明碎片i的右边缘与碎片j的左边缘拼接吻合度越低。规定当时，认为两张碎片可完全匹配。

2 遗传算法的基本思想

传统的优化算法主要有枚举法、启发式算法和搜索算法。对于规则图形拼接来说，枚举空间比较大，求解效率较低;启发式算法需要寻求一种产生可行解的启发式规则，虽然求解效率得到提高，但启发式规则对其他模型使用较差，一般得到的也仅是局部最优解;当可行解的子集较大时，搜索算法也需要借助一些启发知识才能达到较高的求解效率。

遗传算法［8］最早由美国 Michigan大学的 John Holland提出，是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。其特点是自组织、自适应、自学习性，其不同于启发式算法和搜索算法，强调概率转换规则，而不是确定的转换规则，因此有较强的适用性。

遗传算法是从代表问题可能潜在解集的一个种群开始，按照适者生存和优胜劣汰的原理，逐代演化产生越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于遗传算子进行组合交叉和变异，产生代表新的解集的种群。遗传算法的基本流程如图2所示。

图2 遗传算法的基本流程图

3 样本数据及图像预处理

样本数据来自某彩色图片，彩色图片经横切和纵切，共计36张碎片，并用1，2，…，36对每张碎片编号。碎片经过扫描仪处理，以图片的形式保存。所有碎片均为大小相同的规则正方形，图3为部分碎片图样。

图3 部分碎片图样(编号:10号和25号)

扫描后保存在电脑中的图形碎片可看成是由一个个像素平铺构成。对于黑白图像而言，因是单色图像，图片可由每个像素点处的灰度值形成的灰度矩阵表示;对于彩色图片而言，则是由多幅单色图像组合形成。

在RGB彩色系统中，一幅彩色像由3张单色图像组成，这3幅图像分别称为红(R)、绿(G)、蓝(B)分量图像［9］。彩色图像在计算机存储中需要用3个矩阵来描述，这势必会使运算速度降低，增加问题的复杂性。因此，研究中运用Matlab自带的适用于RGB和灰度图像之间进行转换的工具箱函数rgb2gray，将复杂彩色图像转换为仅用一个灰度矩阵便可进行简化描述的灰度图像。

将样本数据中的36张碎片灰度化，每张碎片均可产生一个灰度矩阵，矩阵的元素为碎片在每个像素点处的灰度值，像素灰度值介于0～255之间。以33号碎片为例，图4展示了碎片由彩色图像转换成灰度矩阵再进行反演成灰度图的处理过程。

图4 第33张碎片灰度化预处理过程

4 0-1规划拼接模型的建立

当以碎片i为基准图片进行两张碎片的拼接时，以匹配度达到最大作为两张碎片拼接的目标建立优化模型，两张碎片拼接的目标函数为

对于碎片i而言，在其余35张碎片中至多只有一张碎片的某条边缘与之拼接，因此可得到拼接约束为

当拼接整幅图片时，以全局碎片拼接复原匹配度最大为目标建立优化模型，则全局目标函数为

对于每个碎片的左边缘而言，至多只有一个碎片与其进行右邻拼接;对于而对于每个碎片的上边缘而言，至多只有一个碎片与其下邻拼接。因此可得到总的拼接约束为

由式(6)，式(7)式得到碎片拼接的0－1规划模型为

5 基于遗传算法的模型求解

根据遗传算法的基本流程设计出适合求解0－1规划拼接模型的遗传算法步骤如下:

步骤1 随机产生初始种群(个体数目为M)。即产生M×36的矩阵，矩阵的每一行是1－36的数字随机排列，代表一种碎片拼接的结果，以此矩阵作为初始的种群。

步骤2 计算种群中每个个体的适应度。即每个随机排列序列对应的36张碎片的拼接结果的匹配度，并判断是否大于遗传运算的终止进化代数，若符合，输出最佳个体及其代表的最优解，并结束运算;否则转向步骤3。

步骤3 选择:依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体被淘汰。

步骤4 交叉:按照一定的交叉概率和交叉方法，生成新的个体。

步骤5 变异:按照一定的变异概率和变异方法，生成新的个体。

步骤6 由交叉和变异产生新一代的种群，返回到步骤2。

交叉过程:本文采用1985年Goldberg等针对TSP问题提出的基于路径表示的部分匹配交叉(PMX)操作，PMX要求随机选取两个交叉点，以便确定一个匹配段，根据两个父个体中两个交叉点之间的中间段给出映射关系生成两个子个体。随机选取两个交叉点用箭头表示，如图5所示。

图5 遗传算法中的交叉操作

变异过程:遗传算法中变异操作有:(1)点位变异，变异以一定概率对解的某些位做值得变异。(2)逆转变异，在某一解中随机选择两点，再将这两点内的码串按反序插入原位置。(3)随机选择两个交换点，使交换点处的码值交换。图6展示了两个位点互换的过程。

图6 遗传算法中的变异操作

对于图形样本文件的36张碎片，运用上述遗传算法进行模型求解，取初始种群个体数目M=100，得到部分拼接结果如图7所示。

图7 图形样本文件部分拼接结果

6 结束语

通过对规则图形碎片的特征与文字碎片特征进行对比，提取了图形碎片边缘像素信息，并基于碎片之间的欧氏距离建立了0－1规划拼接模型，利用遗传算法对0－1规划模型进行求解。求解结果表明，模型可准确地对规则图形碎片拼接问题进行数学描述;而遗传算法可在未设置启发式搜索规则的情况下快速实现图形碎片拼接。本文的结果是基于规则边界且大小相同的正方形的图形碎片，实际中则受破碎方式、图形内容等因素影响，碎片拼接复原过程也会因此而错综复杂。当碎片数量较多时，无需启发式规则的遗传算法会因问题规模的增大，导致收敛速度变慢，因此需要进一步深入研究，建立更精确的模型，将会有更准确、快速的拼接结果。

［1］杨洛斌.形状匹配技术在文物复原中的研究与应用［D］.西安:西北大学，2002.

［2］罗智中.基于线段扫描的碎纸片边界检测算法研究［J］.仪器仪表学报，2011，23(2):289 －294.

［3］Nasir Memon，Anandabrata Pal.Automated reassembly of file fragmented images using greedy algorithms［J］.IEEE Transactions on Image Processing，2006，15(2):385 －393.

［4］贾海燕，朱良家，周宗潭，等.一种碎片自动拼接中形状匹配方法［J］.计算机仿真，2006，23(11):180 －183.

［5］刘俊玮，宋嵩焘，王子豪.条状碎片文件自动复原的探讨和研究［J］.数学学习与研究，2014，27(1):113 －114.

［6］姜艳秋，纪艳侠，王葳，等.基于Matlab规则碎纸片拼接复原方法的研究及实现［J］.自动化与仪器仪表，2014(5):172－174.

［7］沈鸿平，章毅鹏，王义康.基于0－1规划模型的规则中文碎片拼接复原研究［J］.电子科技，2014，27(6):13 －16.

［8］王小平，曹立明.遗传算法－理论、应用与软件实现［M］.西安:西安交通大学出版社，2001.

［9］Rafael CGonzalez，Richard E Woods，Steven L Eddins.Digital image processing using Matlab［M］.北京:电子工业出版社，2013.