Fast template matching for laser cutting based on niche genetic algorithm

模板匹配是根据已知的模板图像在另一幅图像中通过逐像素比较的方法寻找与模板相似的子图像。在工件的制造、传送、组装过程中，能否对工件进行准确定位，直接影响制造质量^[1-2]。以往采用人眼定位工件位置，此种方法不但效率低下，而且成本较高。对此，研究人员提出了计算机视觉技术，代替人眼定位工件，把数据传输给设备，不仅精度高，而且效率也明显提高^[3-6]。

激光切割快速有效地切割目标的基础是快速精确地定位目标的位置。近些年来，有多目标匹配研究较少，大多数算法均是对所有可能的匹配位置进行全部搜索之后，给出一个全局最优值作为匹配点，这样势必难以提高匹配速度。对于该行业目前所应用的小幅面视觉识别切割系统和大幅面视觉识别切割系统出现的问题，本文中对其进行了扩展研究，提出了一种大幅面多目标匹配的快速匹配算法，即在满足识别率要求的前提下，提高了计算速度，具有很好的实用性。

对一张图像使用傅里叶变换把其分解成正弦和余弦两部分，也就是将图像从空间域转换到频域。频域图像能很好地反映图像的能量分布，利用傅里叶变换进行图像的校正主要是在频域对频谱图像进行校正，然后再把图像从频域转换到空域^[7]。一幅普通静止的数字图像就是一个离散的2维数据矩阵，则数字图像可以看作是对离散2维数据矩阵的处理。

2维图像的傅里叶变换可以用以下数学公式表达^[7]:

式中，x, y, u, v等变量的取值范围为[0, N-1], 其中N为图像的宽和高, f(x, y)是图像空间域值, F(u, v)是图像频域值。

在目前面向激光布料切割行业中布料中的多目标普遍为紧密均匀地分布在布料上，因此获取图像做傅里叶变换后，从傅里叶谱中可以明显地看到一条过中心点的倾斜直线或在水平纹理和垂直纹理会大致映射成两条线和一条过中心点的倾斜直线，而这条过中心点的倾斜直线的斜角正是作者要找的图像旋转角度。可采用霍夫(Hough)变换来检测这条直线并计算出其倾斜角。将图像的中心坐标值和图像倾斜角输入OpenCV中求解图像绕某一点的旋转矩阵函数get Rotation Matrix2D()，求出一个2×3的仿射变换矩阵。再把这个矩阵输入OpenCV中的仿射变换函数warpAffine()进行图像仿射变换校正。为了节省篇幅，下面直接给出傅里叶变换获取旋转角度的各过程结果。图 1所示是一幅带有旋转角度的激光切割布料图案的图像傅里叶变换后的频域图。

Figure 1.  Original image and frequency domain diagram

图 2所示为频域图二值化后用OpenCV中检测直线的函数HoughLines()检测到的一条明显的直线。这条直线正是作者所需要的。

Figure 2.  Hough test chart

图 3所示为傅里叶变换获取的图像旋转角度和仿射变换校正的结果。

Figure 3.  Map after image correction

在校正后的图像基础上去创建模板图像，并对源图像和模板图像按一定的比例来以双线性插值方式^[8]缩小图像进行归一化积相关粗匹配。设定匹配相关阈值来循环获取所有的粗匹配点, 以粗匹配的匹配点为中心，在一定的矩形区域内进行精匹配以寻找最优匹配点。先进行粗匹配，缩小搜索范围，然后进行由粗到精的匹配，最后精确找到搜索目标。

用遗传算法求解多峰函数的优化时，只能找到个别的最优解，甚至只是局部最优解，有时人们希望算法能够找到全部的最优解，引进小生境的概念有助于解决此问题。小生境技术通过促成在多个最优解的邻域内形成稳定的子种群来扩展遗传算法，使遗传算法能应用于在搜索空间中具有多个局部最优解的问题^[9]。因此，作者将小生境遗传算法与图像多目标识别有机结合起来，提出一种在精匹配阶段基于小生境遗传算法的模板匹配方法。

假设原始图像的大小为m×m，m较大时，经过双线性插值方式按一定的比例来缩小图像粗匹配，由于得出最后精确结果的精匹配运算需要在分辨率最高的原始图像上进行，所以对于多目标模板匹配的精匹配过程的计算量仍然会比较大, 故引入小生境遗传算法。该算法具有能够快速地找出全部的最优解的特点，可以大大提高求解速度。本文中在进行模板匹配时采用了归一化积相关匹配法。该方法是一种典型的基于灰度相关的算法，具有不受比例因子误差的影响和抗白噪声干扰能力强等优点。通过比较模板图像和原图像在各个位置的相关系数，相关值最大的点就是最佳匹配位置。其数学公式如下所示：

式中，(x, y)表示目标图像像素坐标，(x′, y′)表示模板像素坐标，T(x′, y′)表示模板，I(x, y)是目标图像，I(x+x′, y+y′)是对应于和原图像配准位置偏差(x′, y′)个像素的子图，R(x, y)是相似度的函数。

小生境遗传算法实现步骤如下^[10]：

(1) 在可行解区域生成S个个体作为初始种群，并求S个个体的适应度F_i(i=1，2，…，S);

(2) 根据适应值降序排序个体，并记录前T个个体(T＜S);

(3) 对种群进行交叉、变异和选择运算得到S个个体;

(4) 小生境运算：将步骤(3)的S个个体和步骤(2)的T个个体合并成一个S+T个个体的新种群, 求取种群中的每两个个体X_S和X_T之间的相似度D_{S, T}; 当D_{S, T}＜L时，L为预先设定的距离，比较其适应度值大小，并施加一个较强的罚函数Penalty赋予适应度小的个体，使得其适应度极大的降低;

(5) 按照S+T个个体的新适应度值降序排序个体，记住前T个个体;

(6) 结束条件：若T个个体中最小的适应度值大于或等于设定获取粗匹配点的阈值时，满足结束条件。否则，取步骤(5)排序个体中前S个个体构成子代新的种群，之后跳到步骤(3)，直到满足结束条件。

模板匹配是欲求出目标所在位置的实数坐标(i, j)，本文中引入实数编码方法。由于本文中粗匹配是原图像在x和y方向以1/4的缩放比例双线性插值缩放后进行，因此精匹配时以粗匹配的匹配点为中心，在8×8的矩形区域内进行实数编码寻找最优匹配点。为了省略解码这一过程，本文中直接以粗匹配点为中心的8×8矩形区域内的像素坐标为实数编码。

遗传算法的种群进化操作主要由交叉和变异算子组成。

交叉算子起到全局搜索的作用，而变异算子是一种背景操作或辅助操作^[11]。本文中交叉算子采用单点交叉，即交叉点是在固定在两个自然数之间。如坐标为(20，30)和(10，25)的双亲，在交叉后产生的新个体为(20，25)和(10，30)。交叉完成后采用(μ+λ)进行选择，即在μ个父代交叉产生的λ个子个体中选出μ个最佳个体。

变异算子采用随机变异，具体方法是在实数基因位上加上一个微小的值，该值的正负由计算机决定。当变异后的个体为子种群中的最佳个体时，对该最佳个体及由其变异所得的新个体进行(1+1)选择，即选择两者中的最优个体，以保证最优个体留到下一代。

终止条件是决定遗传算法什么时候停止进化。本文中采用全局最优点处的目标函数值为大于或等于设定获取粗匹配点的阈值作为进化终止条件。这样能涵盖到所有的全局最优点。由于归一化积相关匹配法的相关值为1时表示完美匹配，-1时表示糟糕的匹配。因此阈值的取值范围为[-1, 1]。

本文中的小生境遗传匹配算法的适应度函数采用归一化积相关匹配的数学判定函数，如(3)式所示。

距离准则用于区分相似与不相似个体。比较种群两个个体之间的距离，假如距离在设定的L范围内，则比较适应度值大小，对适应值较小的个体施加一个罚函数Penalty，使其适应度降低^[12]，在后期进化中其被淘汰的概率也就越大。即在L范围内只存在一个最佳个体，从而形成一种小生境环境，又保持了群体的多样性。本文编码方法以像素坐标实数编码，采用欧氏距离来求取个体x₁和x₂的相似度^[13]，其公式如下所示：

式中，n是指编码参量的个数, 本文中取n=2;F_i(x₁)和F_i(x₂)是指个体x₁和x₂各自的第i个编码参量。

基于小生境遗传算法的激光切割快速模板匹配的算法流程如图 4所示。

Figure 4.  Algorithm flow of template matching

从匹配结果映射图中获取最大值点的坐标后，以该点为中心的两倍模板宽度和高度的矩形内部区域设置为最小值，使得以后找的最大值不会位于该区域，避免找到重叠的目标。

阈值设定：通过阈值来循环判断找出所有的匹配位置坐标。由于归一化积相关匹配法的相关值取值范围为[-1, 1]，因此阈值设定范围为[0, 1]，1表示最佳匹配，0表示不相关。用户可根据目标的匹配率来调节阈值，当匹配率低时阈值调低，反之阈值调大。本文算法的阈值设为0.75。

(1) 随机生成的M个初始种群，在第1次对各个个体适应度进行降序排列后记录前N(N < M)个个体，本文中N等于粗匹配点数。

(2) 对初始种群进行小生境选择、交叉和变异操作后得到的M个个体并和N个个体合并成M+N个个体的新群体。

(3) 对着M+N个个体，按照(4)式计算两个个体之间的欧氏距离D(x₁, x₂)，当D(x₁, x₂) < L(L为预先设定的距离，本文中设定L=3)时，比较两者之间的适应度大小，并对其中适应度较低的个体处以罚函数(本文中的罚函数为Penalty(0.5))。

(4) 重新根据M+N个个体的新适应度值进行降序排列，记录前N个个体。当N个个体中的最小适应度值大于或等于粗匹配时循环获取所有的匹配位置坐标所设定的阈值时，满足终止条件，输出N个最佳的匹配坐标。否则，将排列中的前M个个体作为新的下一代群体，重复小生境选择、交叉和变异操作以及后面步骤，直至满足终止条件。

为了验证算法的实用性，本文中以有旋转角度和没有旋转角度的两种目标图像进行仿真实验，记录算法的识别率和总匹配时间，并将其与传统归一化积相关算法和基于双线性插值缩放后由粗到精的匹配算法的实验结果进行对比。

根据参考文献[13]~参考文献[17]中对遗传算法的研究和本文中算法的试验结果，将小生境遗传算法的实验参量设置总迭代次数为200，初始种群个数为粗匹配点个数，种群大小为30，交叉率为0.8，变异率为0.1，小生境之间的距离参量L=3。

具有旋转角度的目标图像，原图像分辨率为5148pixel×3456pixel，模板图像分辨率为645pixel×253pixel，仿真实验结果如图 5所示，实验数据如表 1所示。

Figure 5.  Target recognition effect with rotation angle

无旋转角度的目标图像，原图像分辨率为685pixel×675pixel，模板图像分辨率为133pixel×106pixel，仿真实验结果如图 6所示，实验数据如表 2所示。

Figure 6.  Effect of target recognition without rotation angle

从表 1和表 2中的数据可以看出，在同等条件下，当目标图像无旋转时，各匹配算法的目标识别率相同，但基于小生境遗传算法的归一化积相关算法所消耗的匹配时间最少。当目标图像有旋转时，传统匹配方法已无法识别目标，而另外两种方法在傅里叶变换校正的基础上仍然能识别目标，但在匹配时间上基于小生境遗传算法的归一化积相关算法仍然占优。因此，在面对带有旋转角度的多目标时，本文中所提出的算法在识别率和实时性上的表现都取得了满意的效果。

对目前激光切割机结合视觉切割行业来说，现有的大幅面视觉识别切割系统识别过程实时性差，对带有偏角的目标识别率低，甚至出现无法识别等问题。本文中采用对傅里叶变换矫正后的图像作双线性插值方式缩放进行粗匹配，再基于小生境遗传算法的归一化积相关算法的迭代寻优搜索策略来加速精匹配过程。实验数据表明：作者所提出的算法在运算速度上比传统的灰度归一化积相关算法快5倍~10倍，且能识别带有偏角的目标。这表明该算法可以有效地克服以上这些问题。