一种基于遗传规划算法的图形图像分类方法

摘要

本发明属于图像处理技术领域，具体公开了一种基于遗传规划算法的图形图像分类方法，其步骤包括：(1)构造图像特征集和训练特征集；(2)设定第一阶段相关参数；(3)提取图像特征；(4)初始化种群并评估适应度；(5)对个体优胜劣汰，优胜个体进行交叉变异,评估适应度；(6)对个体进行局部搜索；(7)种群评估,判断是否完成交叉变异操作；(8)种群选优，判断是否终止进化；(9)根据新特征重新初始化种群；(10)种群选优,交叉变异；(11)依据最优个体输出图像匹配模型,解码个体树,获得新的图像特征。本发明产生的训练模型，能够有效的提高图像分类的准确度。

说明书

技术领域

本发明涉及图像处理技术领域，具体是一种基于遗传规划算法的图形 图像分类方法，能够应用于对数字图像的分类。

背景技术

人类接收的信息中有80％来自视觉或图像信息，有图像、图形、动画、 视频、文本数据等。这是最有效和最重要的信息获取和交流方式。随着计 算机的普及，人们越来越多地利用计算机来帮助人类获取与处理图像信息。 图像处理、图像分析和图像理解，这三个层次的有机结合称为图像工程。

图像分类有基于内容的图像分类与基于文本的图像分类之分，基于文 本的图像分类技术，将每幅图像加上相关标签，分类时，只需根据标签内 容的匹配，输出标签对应的图像，属于人工干预较多的分类方式。然而随 着时代的发展，无法完成对所有图像数据标注标签信息，因此，基于文本 的图像分类有其自身的局限性。基于内容的图像分类是将图像本身的信息 作为分类内容，根据图像像素间的内在联系，即可完成分类任务，人工干 预大大降低，因此成为许多领域的一项重要技术。

基于内容的图像分类技术，在建立图像数据库时，系统对输入的图像 进行分析并分类统一建模，然后根据各种图像模型提取图像特征存入特征 库，而用户在通过用户接口设置查询条件时，可以采用一种或几种的特征 组合来表示，然后系统采用相似性匹配算法计算关键图像特征与特征库中 图像特征的相似度，然后按照相似度从大到小的顺序将匹配图像反馈给用 户。在此过程中分类系统会根据不同的特征采用不同的匹配算法，不同的 特征匹配算法大不相同，匹配算法需经过精心设计才能达到较好的结果。

发明内容

本发明的目的在于克服已有技术的不足，提出一种基于遗传规划算法 的图形图像分类方法，通过该方法提高图形图像的分类效果。

为此，本发明提供了一种基于遗传规划算法的图形图像分类方法，包 括如下步骤：

(1)根据图像库中的图像，随机挑选出总数的50％组成训练集图像，其中 每类图像幅数均等于该类在图像库中总数的半数；

(2)设定第一阶段的操作符集终止符集交叉概率变异 概率种群规模变异步长因子step，迭代次数gen₁；第二阶 段的操作符集终止符集变异概率交叉概率迭 代次数gen₂、种群规模

(3)采用“组合矩”方法提取训练集图像的特征；

(4)依据操作符集终止符集初始化个个体的种群pop₁， 计算每个个体的适应度；

(5)依据适应度大小评价个体优劣：适应度高的个体视为优胜个体；采 用锦标赛策略选择种群pop₁中个个体；对优胜个体组成的种群 进行交叉变异操作；

(6)对交叉变异后的个体进行局部搜索，设定较小的变异步长s^'，根据此 步长对种群进行较密集的变异操作；

(7)对局部搜索后的种群个体进行适应度评估，若种群中最大适应度大 于0.85或迭代次数达到gen时，则执行步骤(8)，否则，执行步骤(5)；

(8)从迭代终止的种群中选择适应度最高的个体，即为最优个体；解码 最优个体表达式树，获得新特征；

(9)依据操作符集终止符集和新特征，初始化个个体的 种群pop₂，对个体评估适应度；

(10)根据评估结果优选种群pop₂，获得优选种群交叉概率对进行交叉，变异操作；

(11)对交叉变异后的个体进行适应度评估。若迭代次数少于gen_N时，则 返回执行步骤(10)；否则按照适应度最大原则选出现有种群中的最 优个体，输出最优个体的解码结果，获得匹配函数，据此函数得到图 像匹配模型。

上述的步骤(3)中所说的组合矩方法，按照如下步骤完成：

1)用canny边缘检测算法获取图像边缘；

2)获取边缘点的坐标值{(x(i),y(i)),i＝1,2,...,N}，计算边缘的重心$\bar{x}=m_{10}/m_{00},\bar{y}=m_{01}/m_{00},$轮廓不变矩$m_{\mathrm{pq}}={\Sigma }_x{\Sigma }_y{x}^p{y}^q,$计算每个边缘点与重 心的距离量$z\left(i\right)=\sqrt{{(x_i-\bar{x})}^2{(y_i-\bar{y})}^2};$

3)依据中心矩和归一化中心矩计算图 像边缘区域的重心的归一化中心矩η₂₀、η₀₂、η₁₂、η₃₀、η₁₁、η₂₁；其中阶数 γ＝(p+q)2+1，p+q＝2,3,...；

4)计算图像的CHEN不变矩高阶矩T1、T2、T3；其中${\phi }_2={({\eta }_{20}-{\eta }_{02})}^2+{4\eta }_{11}^2,{\phi }_3={({\eta }_{30}-{3\eta }_{12})}^2+{({3\eta }_{21}-{\eta }_{03})}^2,{\phi }_4={({\eta }_{30}+{\eta }_{12})}^2+{({\eta }_{20}-{\eta }_{02})}^2,$T₁＝μ₂(M₁)²，T₂＝μ3(M₁)³，T₃＝μ₄(M₁)⁴。其中(p＝1,2,...) 为边界几何矩,μ_p为图像轮廓的p阶中心矩。

上述步骤(4)的计算个体适应度，是按照如下方式进行：

$\mathrm{fitness}=1/N\times {\Sigma }_{i=1}^N({\mathrm{precision}}_i+{\mathrm{recall}}_i)/2$用来计算个体a_i(t)的适应度； precision_i与recall_i分别为以第i幅图像为被分类图像情况下的分类精度与回 调率，N为训练集中图像的个数。

计算时，为了降低计算复杂度，将待输出的图像幅数与相关图像个数 设置为训练集中的相关图像数的半数。为 基于距离的一种划分，其中{x₁,x₂,x₃,...,x_k}为进化得到的最优个体解码， {F₁,F₂,F₃,...,F_k}为图像的某一原始特征。F_ki为第i福图像的第k个特征值。

上述的步骤(5)中所说的交叉变异操作，按如下步骤完成：

1)对于种群中的被选择到的个体ind₁与ind₂，二者的叶子节点个数均为 N，对ind₁与ind₂进行交叉操作，首先产生一个位于[1,N]的随机数字 rand，将个体ind₁的第rand到第N个叶子节点的值赋给ind₂的对应位 置；将个体ind₂的第rand到第N个叶子节点的值赋给ind₁的对应位置， 完成交叉操作；

2)对种群中某个体ind₃进行变异操作，首先确定个体的叶子节点个数 _N，然后产生一个位于区间[1,N]的随机整数R_index，两个位于区间[0,1]的 随机数R_step,R_style：

①若R_step＞0.4则：

若R_style≥0.5则x_Rindex＝x_Rindex+step；

若R_style≥0.5则x_Rindex＝x_Rindex+step；

②若R_step≤0.4则：

若R_style≥0.5则x_Rindex＝x_Rindex+step*rand*5；

若R_style≥0.5则x_Rindex＝x_Rindex+step*rand*5；；

其中rand为0到1之间的随机数，x为节点数值。

上述的步骤(8)中所说的获取新特征，按如下方式进行：

用{F₁,F₂,F₃,...,F_k}表示某图像的某一原始特征，个体解码后得到 {x₁,x₂,x₃,...,x_k}，则该图像的新特征为{x₁×F₁,x₂×F₂,x₃×F₃,？,x_k×F_k}。

上述的步骤(10)中所说的交叉变异操作，按如下方式进行：

1)对于种群中被选择到的个体ind₁，ind₂进行交叉操作，首先计算出ind₁与ind₂中个体表达树的节点个数N₁，N₂；产生两个随机整数r₁,r₂分 别位于区间[1,N₁]，[1,N₂]中；在个体表达树中分别找到第r₁个和第r₂个 节点的位置；交换两个位置处的子树；

2)对于种群中的个体ind₃进行变异操作，首先计算个体树的节点个数 N；产生位于[1,N]之间的随机整数r₁；找到个体表达树中的第r₁个节 点；产生位于[0,1]区间的随机数rand； 若rand＜0.5则从操作符与终止符中随机挑选一个运算符替换个体表 达树中的第r₁个运算符，并根据该运算符的目数，生成相应的个体子 树，完成变异操作；

若rand≥0.5则首先获取第r₁个节点处的运算符的目数T；然后从运算 符中随机挑选目数为T的运算符替换r₁节点处的运算符，完成变异。

本发明的有益效果是：利用分类思想，采用遗传规划算法和现有的简 单匹配算法，对图像库中的训练集建模，产生划分模型，根据划分模型， 将训练集中的每幅图像作为分类对象，测试分类模型的性能；反复改进所 产生的分类模型，最终得到一个满意的模型。并利用该模型预测图像与图 像库图像之间的匹配问题，根据匹配程度输出最佳匹配的图像，从而实现 图像分类。本发明的方法克服了已有技术的不足，实现分类效果的提高。 本发明产生的训练模型，能够有效的提高图像分类的准确度。

附图说明

图1是本发明的流程框图；

图2是本发明提出的新编码方式下的变异操作的示意图；

图3是本发明提出的新编码方式下的交叉操作的示意图；

图4是本发明的仿真效果与原方法的对比图。

具体实施方式

遗传规划算法处理图像分类问题，可以抽象为对图像库特征集进行分 类的问题。

本发明设计的基于遗传规划算法的图形图像分类方法，参见图1，其具 体实施步骤如下：

(1)根据图像库中的图像，随机挑选出总数的50％组成训练集图像，其中 每类图像幅数均等于该类在图像库中总数的半数；

(2)设定第一阶段的操作符集终止符集交叉概率变异 概率种群规模变异步长因子step，迭代次数gen₁；第二阶 段的操作符集终止符集变异概率交叉概率迭 代次数gen₂、种群规模

(3)采用“组合矩”方法提取训练集图像的特征；

(4)依据操作符集终止符集初始化个个体的种群pop1， 计算每个个体的适应度；

(5)依据适应度大小评价个体优劣：适应度高的个体视为优胜个体；采 用锦标赛策略选择种群pop₁中个个体；对优胜个体组成的种群 进行交叉变异操作；

(6)对交叉变异后的个体进行局部搜索，设定较小的变异步长s^'，根据此 步长对种群进行较密集的变异操作；

(7)对局部搜索后的种群个体进行适应度评估，若种群中最大适应度大 于0.85或迭代次数达到gen时，则执行步骤(8)，否则，执行步骤(5)；

(8)从迭代终止的种群中选择适应度最高的个体，即为最优个体；解码 最优个体表达式树，获得新特征；

(9)依据操作符集终止符集和新特征，初始化个个体的 种群pop₂，对个体评估适应度；

(10)根据评估结果优选种群pop2，获得优选种群按照变异概率交叉概率对进行交叉，变异操作；

(11)对交叉变异后的个体进行适应度评估。若迭代次数少于gen_N时，则 返回执行步骤(10)；否则按照适应度最大原则选出现有种群中的最 优个体，输出最优个体的解码结果，获得匹配函数，据此函数得到图 像匹配模型。

步骤2中所说的参数设置。

(1)设定交叉概率P_c，变异概率P_m，种群规模Pop_size，变异步长因子s， 迭代次数gen；

(2)依据(1a)中的图像特征，及种群规模n，产生初始种群： A(t)＝{a₁(t),a₂(t),a₃(t),...,a_n(t)t＝0}，其中a_i(t)为初始种群中的第i个个 体，可以用深度为二的树来表示，i∈[1,n]。

步骤3中所说的组合矩方法，按照如下步骤完成：

1)用canny边缘检测算法获取图像边缘；

2)获取边缘点的坐标值{(x(i),y(i)),i＝1,2,...,N}，计算边缘的重心$\bar{x}=m_{10}/m_{00},\bar{y}=m_{01}/m_{00},$轮廓不变矩$m_{\mathrm{pq}}={\Sigma }_x{\Sigma }_y{x}^p{y}^q,$计算每个边缘点与重 心的距离量$z\left(i\right)=\sqrt{{(x_i-\bar{x})}^2{(y_i-\bar{y})}^2};$

3)依据中心矩和归一化中心矩计算图 像边缘区域的重心的归一化中心矩η₂₀、η₀₂、η₁₂、η₃₀、η₁₁、η₂₁；其中阶数 γ＝(p+q)2+1，p+q＝2,3,...；

4)计算图像的CHEN不变矩高阶矩T1、T2、T3；其中${\phi }_2={({\eta }_{20}-{\eta }_{02})}^2+{4\eta }_{11}^2,{\phi }_3={({\eta }_{30}-{3\eta }_{12})}^2+{({3\eta }_{21}-{\eta }_{03})}^2,{\phi }_4={({\eta }_{30}+{\eta }_{12})}^2+{({\eta }_{20}-{\eta }_{02})}^2,$T₁＝μ₂(M₁)²，T₂＝μ₃(M₁)³，T₃＝μ₄(M₁)⁴。其中(p＝1,2,...) 为边界几何矩,μ_p为图像轮廓的p阶中心矩。

步骤4中所说的计算种群的适应度

$\mathrm{fitness}=1/N\times {\Sigma }_{i=1}^N({\mathrm{precision}}_i+{\mathrm{recall}}_i)/2$用来计算个体a_i(t)的适应度； precision_i与recall_i分别为以第i幅图像为被分类图像情况下的分类精度与回 调率，N为训练集中图像的个数。

计算时，为了降低计算复杂度，将待输出的图像幅数与相关图像个数 设置为训练集中的相关图像数的半数。为 基于距离的一种划分，其中{x₁,x₂,x₃,...,x_k}为进化得到的最优个体解码， {F₁,F₂,F₃,...,F_k}为图像的某一原始特征。F_ki为第i福图像的第k个特征值。

步骤5中的种群选择操作

根据个体适应度进行种群选择操作。采用锦标赛策略，锦标赛每轮大 小为5，产生n*p_c±1个配对个体，对剩余的个体进行变异操作。再根据精 英策略，从种群中选择n*p_e个精英个体。

步骤5中的交叉变异操作，按如下步骤完成：

(1)对于种群中的被选择到的个体ind₁与ind₂，二者的叶子节点个数均为 N，对ind₁与ind₂进行交叉操作。首先产生一个位于[1,N]的随机数rand， 将个体ind₁的第rand到第N个叶子节点交换到ind₂的对应位置；将个 体ind₂的第rand到第N个叶子节点交换到ind₁的对应位置。如附图3 所示，两个体Abs(0.32,0.65,0.51,0.87,...,0.12)和Abs(0.48,3.1,0.83,5.0,...,-1.2) 进行交叉操作，产生交叉点位置为3，然后交换两个体交叉点处右侧 的所有节点，完成交叉操作。原个体一、个体二分别变化为： Abs(0.32,0.65,0.51,5.0,...,-1.2)和Abs(0.48,3.1,0.83,0.87,...,0.12)。完成交叉操 作。

(2)对种群中某个体ind3进行变异操作。首先确定个体的叶子节点个数 N，然后产生一个位于区间[1,N]的随机整数R_index，两个位于区间[0,1]的 随机数R_step,R_style：

①若R_step≥0.4则：

若R_style＜0.5则x_Rindex＝x_Rindex-step；

若R_style≥0.5则x_Rindex＝x_Rindex+step；

②若R_step＜0.4则：

若R_style＜0.5则x_Rindex＝x_Rindex-step*rand()*5；

若R_style≥0.5则x_Rindex＝x_Rindex+step*rand()*5；；

其中rand()为0到1之间的随机数，x为节点数值。

如附图2所示，个体Abs(0.65,0.65,0.51,0.87,1.5,4.3,0.12)参加变异，当产生 随机变异点为3，步长控制参数R_step＞0.4，变异方式控制参数R_style≥0.5 时，变异将是步长为0.5的加性变异。个体自左向右的第三个子节点 处的值转化为0.51+0.5即1.01，个体变异后为 Abs(0.65,0.65,1.01,0.87,1.5,4.3,0.12)。完成变异操作。

步骤6中的局部搜索操作

对交叉变异个体进行适应度计算，根据优胜劣汰法则选出两代间较优 秀的个体。对个体进行局部搜索，搜索步长step为变异中步长的0.1倍；局 部搜索针对每个个体进行五次，每次产生一个随机变异点，改变异点处变 异方法如下：

产生随机数R∈[0,1]；变异位置R_index

若R＜0.5则R_index＝R_index+step；

若R≥0.5则R_index＝R_index-step。

对比变异前后的个体的适应度，保留适应度最大的数量为Pop_size的个 体，构成新的种群。

步骤7中的判断终止条件

若进化中种群进化代数等于gen或者种群个体的适应度最大值达到 0.85，则终止种群进化，执行步骤8；否则，转步骤5。

步骤8中的最优个体解码

种群中的最优个体将被选为划分结果，个体解码方式为依次读取个体 树上的N个叶子节点，组成一个1×N的向量，N同时为图像特征的维数， 如解码向量{x₁,x₂,...,x_N}；新的特征构造方法为： {F1',F2',...,F'N}＝{F₁x₁,F₂x₂,...,F_Nx_N}，其中为新特征的第i位，F_i为原始特征的 第i位。

步骤8中的针对新特征的再次建模

(1)再次建模使用操作符多样、深度变化的表达式树。首先选择操作符， 终止符，进化中的最大深度，初始最大深度，最小深度，初始化方式， 种群规模，进化代数gen_N，设定种群规模交叉概率，变异 概率，精英概率，操作符集set_f，终止符集set_t；

(2)初始化种群，种群初始化方式有两种，一种采用固定深度的方式， 即个体树的深度固定，且所有叶子节点处于同一层深度。一种使用生 长的方式，即个体树的深度随机变化。在此，使用1:1混合法完成初 始化。

步骤10中的交叉变异操作。

(1)对于种群中被选择到的个体ind₁，ind₂进行交叉操作，首先计算出ind₁与ind₂中个体表达树的节点个数N₁，N₂；产生两个随机整数r₁,r₂分别 位于区间[1,N₁]，[1,N₂]中；在个体表达树中分别找到第r₁个和第r₂个节 点的位置；交换两个位置处的子树；

(2)对于种群中的个体ind₃进行变异操作，首先计算个体树的节点个数 N；产生位于[1,N]之间的随机整数r₁；找到个体表达树中的第r₁个节 点；产生位于[0,1]区间的随机数rand；

若rand＜0.5则从操作符与终止符中随机挑选一个运算符替换个体表 达树中的第r₁个运算符，并根据该运算符的目数，生成相应的个体子 树，完成变异操作；

若rand≥0.5则首先获取第r₁个节点处的运算符的目数T；然后从运算 符中随机挑选目数为T的运算符替换r₁节点处的运算符，完成变异。

步骤11中的进化与终止条件

(1)对已初始化个体评估适应度，评估方式按照以每幅为分类图像的 precision与recall平均值来计算，与步骤四中的相同；根据每个个体的 适应度，进行种群选择，被选择到的个体进行交叉变异操作；

(2)对交叉变异后的种群再次进行适应度评估，并根据评估结果选择即 将保留下来的个体，组成新的种群，并进化下一代；直至达到进化代 数gen_N为止。

步骤11中的解码最优个体，得到最终分类模型

从最终种群中选择适应度最高个体，对其进行前序遍历，解码为函数 解析式f(I₁,I₂)，即为训练最终结果模型。其中I₁、I₂为两幅待匹配的图像。 利用该模型，将每幅图像库中的图像与分类图像进行f运算，对运算结果进 行排序，根据排序结果即可获得分类结果。

本发明克服了已有技术的不足，提出一种改进的遗传规划算法来实现 图形图像分类方法，实现分类效果的提高。本发明产生的训练模型，能够 有效的提高图像分类的准确度。如附图4所示，通过由1开始逐渐增加分 类输出数目，分别统计每个数目下的precision和recall值。绘制出分类算法的 precision-recall曲线。在该曲线中，当precision值较大时recall值亦较大，则 说明分类方法较优，否则较差。从附图4中可以看出，选用两组不同的图 像库，分别使用本文提出的算法与原算法分类图像中的每一幅图像，绘制 出算法的precision-recall均值曲线。新方法的曲线明显在原方法曲线的上方， 因而说明本文提出的方法较原方法有较大的提高。

以上仅仅是对本发明的举例说明，并不构成对本发明的保护范围的限 制，凡是与本发明相同或相似的设计均属于本发明的保护范围之内。