基于基因进化分支树算法的图像分割研究

王宝红，李宏升，吕 臻，季 钢

（1.黄淮学院，河南驻马店463000；2.河南省通信管理局，河南郑州450008；3.驻马店供电公司，河南驻马店463000）

基于基因进化分支树算法的图像分割研究

王宝红1，李宏升1，吕 臻2，季 钢3

（1.黄淮学院，河南驻马店463000；2.河南省通信管理局，河南郑州450008；3.驻马店供电公司，河南驻马店463000）

针对图像分割的特点，采用基因进化分支树算法。首先构造基因，对基因的节点进行数学运算生成基因分支；接着在基因建树中，采用基于特征的构建基因树法，通过节点顺序来构建树，对分支采取最小支持项方法进行剪支和增支；最后把基因分支周围领域内的像素合并，图像中的所有的特征信息都分布在不同的区域中，给出了算法流程。实验仿真结果显示本文算法对图像分割效果连续，性能指标好。

基因树；结构进化；分割

1 前 言

图像分割是把整幅图像分为多个图像子区域的过程，能够在处理区域中从复杂背景中分离出来目标，是视觉、图像理解的基础。

目前使用的图像分割算法主要有：基于K－均值聚类法，在聚类准则函数下能够使分割的误差较小，但是其分割质量取决于最初的一组集群和K值，对参数要求比较高［1］；水平集方法参数自由，能很自然地处理图像区域界面拓扑变化，但是易于出现欠分割、过分割和溢出现象［2］；智能算法比如量子、粒子算法，在处理数据后期出现早熟现象［3］。

本文采用基因进化分支树算法对图像进行分割，在基因中即使相同的终结符号，改变数学运算符号的位置，则结果也不相同，在基因建树中，采用基于特征的构建基因树法，通过节点顺序来构建树，考虑虑到基因树随机生成的某些分支可能无效以及构建图像目标函数的需要，采取最小支持项方法对分支进行剪支和增支，实验仿真结果显示本文算法对图像分割效果连续，性能指标好。

2 基因进化分支树算法模型

2.1 基因组成

设G＝{Ga，Gb，…}是一组n个基因的域集，第l个基因对应于的节点为i，i＝1，2，…，m，则对应的基因分支可为如下方式：

其中，Ga1i（xi，yi）为第a个基因第1代在第i个节点的分支，这是一代节点基因生成二代节点基因的过程，如果是生成多代节点，则需要依次进行基因头部中的数学运算［4］。在生成多代节点过程中，比如在生成第k代中，其中第（k－1）代可有部分分支参与再次生成运算。

2.2 基因建树过程

在基因建树中，推断并评价基因的生成节点关系，并用分支图的形式表现出来，采用基于特征的构建基因树法，不需要规定节点距离和计算节点距离矩阵，而是直接通过节点顺序来构建树［5］。图1给出了3种基因树分支图结构。

图1 基因树3种分支图结构

A、B、C、D的基因分支可能包含节点为：

基因分支之间的关系为：

s（t）为从第一节点生成目标分支的t时间均值；p（t）为t时间内为C、D相对A、B的保持概率为：

如果生成分支的时间均值越长，则在基因运算符号作用下保持概率越小。

2.3 基因树结构进化过程

2.3.1 剪支策略

考虑到基因树随机生成的某些分支可能无效以及构建图像目标函数的需要［6］，对基因树结构进行剪支，以保持有效数据的进行。采用最小支持项方法对分支进行剪支，若子支点i的左右子支支持图像分割目标函数项的数目都大于δ，则剪去支点i；如果子支点i的左（右）子支支持大于δ，而右（左）子支点的支持项数目不小于δ，则剪除左（右）子支剪除，而将右（左）子支替代子支点i的位置。

2.3.2 增支策略

有时基因树随机生成的某些分支可能无法满足数据处理的需要。采用最小支持项方法对分支进行剪支，若子支点i的左右子支支持图像分割目标函数项的数目都小于δ，则增加支点i的生成分支；如果子支点i的左（右）子支支持大于δ，而右（左）子支点的支持项数目不小于δ，则增加左（右）子支。

剪支、增支策略满足了数据处理量的需要。

2.4 图像分割过程

把在空间位置和灰度值相同的像素点作为同一个分支，则背景与目标之间的差异作为不同的分支，将该分支周围的领域内的与这个像素具有相似的性质的像素一起合并在该区域中，在基因树进化过程过后，图像中的所有的特征信息都分布在不同的区域中［7］。

图像的连通域为G＝（V，E，W），其中V＝(v1，v2，…vn)是连接点的集合，E是边的有限集合，W＝(wij)n×n表示权重，且wij＝wji，并设连接点的度约束为bi（i＝1，…，n），则数学模型为：

这里，变量xij＝1表示边(i，j)在基因树中，xij＝0为非生成树中；s为集合s中所含图连通域G的个数为度限制保证了基因树分支的生成［8－9］。

把基因树的分支到节点的距离比作为图像质量评价正确，其目标函数为：

把信息熵作为分割评价效果函数：

其中，N为图像灰度值，kli为分割区域中分支间i个节点中灰度值为l出现的概率，信息熵H越大越好。

3 实验仿真

本文采用matlab进行编程，计算机硬件为目前常用配置，为了减少数据误差，采取多次蒙特卡罗取均值方法，本文参数设置设为30个基因的域集，每个基因每代最大可对应5个节点。图像灰度级为255，大小为30 mm×30 mm，根据本文提出的方法以及和其他方法进行对比实验，其仿真结果如图2所示。

图2 仿真结果对比图

从图2的仿真结果对比中，我们可以发现基因进化分支树算法能够把红外图像中细小的树叶分割出来，分割精度较好，这是因为基因树中的节点可以在数学运算符号下产生不同的分支，把图像中的所有的特征信息分布在不同的分支区域后再分割。

针对图2分割前后的信息熵比较，如表1所示。

表1 分割前后信息熵比较

从表1中可以得知，基因进化分支树算法对图像分割前后的信息熵改变不大，可以保持原始图像的信息，这是因为基因树在处理过程可调节分支的数量，选择适量的分割区域。

4 总 结

本文采用基因进化分支树算法对图像进行分割，在基因建树中，采用基于特征的构建基因树法，通过节点顺序来构建树，考虑到基因树随机生成的某些分支可能无效以及构建图像目标函数的需要，采取最小支持项方法对分支进行剪支和增支，实验仿真结果显示本文算法对图像分割效果连续，性能指标好。

［1］ Zhu Qiuyu，Li Qiming，Chen Yuechuan.Moving object segmentation algorithm based on graph cut optimization integrating disparity and frame difference［J］.Video Engineering，2012，36（13）：135－139.（in Chinese）朱秋煜，李琦铭，陈岳川.基于视差和帧差的图割优化运动目标分割算法［J］.电视技术，2012，36（13）：135－139.

［2］ Wu Yingyue，Tang Xinyi，Liu Shijian，et al.A method forsea-sky-line detection based on image division［J］.Infrared Technology，2012，34（10）：584－587.（in Chinese）吴滢跃，汤心溢，刘士建，等.一种基于图像分割的海天线提取算法［J］.红外技术，2012，34（10）：584－587.

［3］ Deng Yue，Wang Yanjie，Li Jingyu，et al.Improvement of enhancement algorithm for aerial image［J］.Laser＆Infrared，2012，42（9）：1080－1085.（in Chinese）邓玥，王延杰，李静，等.天空区域图像的增强算法的改进［J］.激光与红外，2012，42（9）：1080－1085.

［4］ Mo Haifang，Kang Lishan.Automaticmodeling of complex functions based on gene expression programming［J］. Journal of System Simulaton，2008，20（11）：2828－2831.（in Chinese）莫海芳，康立山.用GEP实现复杂函数的自动建模［J］.系统仿真学报，2008，20（11）：2828－2831.

［5］ Shao Mingsheng，Wang Qihua.Blurred image restoration based on frog Leaping algorithm［J］.Laser＆Optoelectronics Progress，2012，49（2）：0210031－0210036.（in Chinese）邵明省，王其华.基于蛙跳算法的模糊图像复原［J］.激光与光电子学进展，2012，49（2）：0210031－0210036.

［6］ Zhao Shiwei，Zhuo Li，Wang Suyu，et al.A multi-objective optimization based constructing cost-sensitive decision treesmethod［J］.电子学报，2011，39（10）：2348－2352.（in Chinese）赵士伟，卓力，王素玉，等.一种基于NNIA多目标优化的代价敏感决策树构建方法［J］.电子学报，2011，39（10）：2348－2352.

［7］ Zhang Jianmei，Sun Zhitian，Yu Xiuping.Image segmentation based on graph theory algorithm simulation research［J］.Computer Simulation，2011，28（12）：268－271.（in Chinese）张建梅，孙志田，余秀萍.基于图论的图像分割算法仿真研究［J］.计算机仿真，2011，28（12）：268－271.

［8］ Wang Pengjie，Pan Zhigeng，Xu Mingliang，etal.A fastand lossless compression algorithm for point-based models based on localminimal spanning tree［J］.Journal of Computer Research and Development，2011，48（7）：1263－1268.（in Chinese）王鹏杰，潘志庚，徐明亮，等.基于局部最小生成树的点模型快速无损压缩算法［J］.计算机研究与发展，2011，48（7）：1263－1268.

［9］ Zhao Ling，Liu Sanyang.An improved ant search algorithm for degree-constrained minimum spanning tree［J］.Ccmputer Simulation，2006，23（10）：164－166.（in Chinese）赵玲，刘三阳.基于蚂蚁搜索度约束最小生成树的改进算法［J］.计算机仿真，2006，23（10）：164－166.

［10］Zhou Huiwei，Huang Degen，Gaojie，et al.Combining MST algorithm and deterministic algorithm for chinese dependency parsing［J］.Journal of Chinese Information Processing，2012，26（3）：16－21.（in Chinese）周惠巍，黄德根，高洁，等.最大生成树算法和决策式算法相结合的中文依存关系解析［J］.中文信息学报，2012，26（3）：16－21.

Infrared image segmentation based on gene evolutionary branch tree algorithm

WANG Bao-hong1，LIHong-sheng1，LÜZhen2，JIGang3
（1.Huanghuai University，Zhumadian 463000，China；2.Henan Communications Administration，Zhengzhou 450008，China；3.Zhumadian Power Supply Company，Zhumadian 463000，China）

Aiming at the characteristics of infrared image segmentation，the gene tree algorithm is proposed.Firstly the gene is constructed，gene branch is generated throughmathematical operations for gene node；Then in the genetic contribution，the gene tree is constructed based on the characteristics，a tree branch is built by the nodes order，the branches are sheared and increased by theminimum supportmethod.Finally the pixels near the gene branches are incorporated，all the characteristic information of the images distributes in differentareas，and the algorithm flow is given.Simulation results show this algorithm segments continuous infrared image，and has good performance.

gene tree；structure evolution； segmentation

TP391.4

A

10.3969／j.issn.1001-5078.2013.08.021

1001-5078（2013）08-939-04

王宝红（1979－），女，讲师，研究方向为计算机应用技术。E-mail：wangbaohong2013＠foxmail.com

2013-01-03