王寶紅，李宏升，呂 臻，季 鋼

（1.黃淮學院，河南駐馬店463000；2.河南省通信管理局，河南鄭州450008；3.駐馬店供電公司，河南駐馬店463000）

基于基因進化分支樹算法的圖像分割研究

王寶紅1，李宏升1，呂 臻2，季 鋼3

（1.黃淮學院，河南駐馬店463000；2.河南省通信管理局，河南鄭州450008；3.駐馬店供電公司，河南駐馬店463000）

針對圖像分割的特點，采用基因進化分支樹算法。首先構造基因，對基因的節(jié)點進行數(shù)學運算生成基因分支；接著在基因建樹中，采用基于特征的構建基因樹法，通過節(jié)點順序來構建樹，對分支采取最小支持項方法進行剪支和增支；最后把基因分支周圍領域內的像素合并，圖像中的所有的特征信息都分布在不同的區(qū)域中，給出了算法流程。實驗仿真結果顯示本文算法對圖像分割效果連續(xù)，性能指標好。

基因樹；結構進化；分割

1 前 言

圖像分割是把整幅圖像分為多個圖像子區(qū)域的過程，能夠在處理區(qū)域中從復雜背景中分離出來目標，是視覺、圖像理解的基礎。

目前使用的圖像分割算法主要有：基于K－均值聚類法，在聚類準則函數(shù)下能夠使分割的誤差較小，但是其分割質量取決于最初的一組集群和K值，對參數(shù)要求比較高［1］；水平集方法參數(shù)自由，能很自然地處理圖像區(qū)域界面拓撲變化，但是易于出現(xiàn)欠分割、過分割和溢出現(xiàn)象［2］；智能算法比如量子、粒子算法，在處理數(shù)據(jù)后期出現(xiàn)早熟現(xiàn)象［3］。

本文采用基因進化分支樹算法對圖像進行分割，在基因中即使相同的終結符號，改變數(shù)學運算符號的位置，則結果也不相同，在基因建樹中，采用基于特征的構建基因樹法，通過節(jié)點順序來構建樹，考慮慮到基因樹隨機生成的某些分支可能無效以及構建圖像目標函數(shù)的需要，采取最小支持項方法對分支進行剪支和增支，實驗仿真結果顯示本文算法對圖像分割效果連續(xù)，性能指標好。

2 基因進化分支樹算法模型

2.1 基因組成

設G＝{Ga，Gb，…}是一組n個基因的域集，第l個基因對應于的節(jié)點為i，i＝1，2，…，m，則對應的基因分支可為如下方式：

其中，Ga1i（xi，yi）為第a個基因第1代在第i個節(jié)點的分支，這是一代節(jié)點基因生成二代節(jié)點基因的過程，如果是生成多代節(jié)點，則需要依次進行基因頭部中的數(shù)學運算［4］。在生成多代節(jié)點過程中，比如在生成第k代中，其中第（k－1）代可有部分分支參與再次生成運算。

2.2 基因建樹過程

在基因建樹中，推斷并評價基因的生成節(jié)點關系，并用分支圖的形式表現(xiàn)出來，采用基于特征的構建基因樹法，不需要規(guī)定節(jié)點距離和計算節(jié)點距離矩陣，而是直接通過節(jié)點順序來構建樹［5］。圖1給出了3種基因樹分支圖結構。

圖1 基因樹3種分支圖結構

A、B、C、D的基因分支可能包含節(jié)點為：

基因分支之間的關系為：

s（t）為從第一節(jié)點生成目標分支的t時間均值；p（t）為t時間內為C、D相對A、B的保持概率為：

如果生成分支的時間均值越長，則在基因運算符號作用下保持概率越小。

2.3 基因樹結構進化過程

2.3.1 剪支策略

考慮到基因樹隨機生成的某些分支可能無效以及構建圖像目標函數(shù)的需要［6］，對基因樹結構進行剪支，以保持有效數(shù)據(jù)的進行。采用最小支持項方法對分支進行剪支，若子支點i的左右子支支持圖像分割目標函數(shù)項的數(shù)目都大于δ，則剪去支點i；如果子支點i的左（右）子支支持大于δ，而右（左）子支點的支持項數(shù)目不小于δ，則剪除左（右）子支剪除，而將右（左）子支替代子支點i的位置。

2.3.2 增支策略

有時基因樹隨機生成的某些分支可能無法滿足數(shù)據(jù)處理的需要。采用最小支持項方法對分支進行剪支，若子支點i的左右子支支持圖像分割目標函數(shù)項的數(shù)目都小于δ，則增加支點i的生成分支；如果子支點i的左（右）子支支持大于δ，而右（左）子支點的支持項數(shù)目不小于δ，則增加左（右）子支。

剪支、增支策略滿足了數(shù)據(jù)處理量的需要。

2.4 圖像分割過程

把在空間位置和灰度值相同的像素點作為同一個分支，則背景與目標之間的差異作為不同的分支，將該分支周圍的領域內的與這個像素具有相似的性質的像素一起合并在該區(qū)域中，在基因樹進化過程過后，圖像中的所有的特征信息都分布在不同的區(qū)域中［7］。

圖像的連通域為G＝（V，E，W），其中V＝(v1，v2，…vn)是連接點的集合，E是邊的有限集合，W＝(wij)n×n表示權重，且wij＝wji，并設連接點的度約束為bi（i＝1，…，n），則數(shù)學模型為：

這里，變量xij＝1表示邊(i，j)在基因樹中，xij＝0為非生成樹中；s為集合s中所含圖連通域G的個數(shù)為度限制保證了基因樹分支的生成［8－9］。

把基因樹的分支到節(jié)點的距離比作為圖像質量評價正確，其目標函數(shù)為：

把信息熵作為分割評價效果函數(shù)：

其中，N為圖像灰度值，kli為分割區(qū)域中分支間i個節(jié)點中灰度值為l出現(xiàn)的概率，信息熵H越大越好。

3 實驗仿真

本文采用matlab進行編程，計算機硬件為目前常用配置，為了減少數(shù)據(jù)誤差，采取多次蒙特卡羅取均值方法，本文參數(shù)設置設為30個基因的域集，每個基因每代最大可對應5個節(jié)點。圖像灰度級為255，大小為30 mm×30 mm，根據(jù)本文提出的方法以及和其他方法進行對比實驗，其仿真結果如圖2所示。

圖2 仿真結果對比圖

從圖2的仿真結果對比中，我們可以發(fā)現(xiàn)基因進化分支樹算法能夠把紅外圖像中細小的樹葉分割出來，分割精度較好，這是因為基因樹中的節(jié)點可以在數(shù)學運算符號下產(chǎn)生不同的分支，把圖像中的所有的特征信息分布在不同的分支區(qū)域后再分割。

針對圖2分割前后的信息熵比較，如表1所示。

表1 分割前后信息熵比較

從表1中可以得知，基因進化分支樹算法對圖像分割前后的信息熵改變不大，可以保持原始圖像的信息，這是因為基因樹在處理過程可調節(jié)分支的數(shù)量，選擇適量的分割區(qū)域。

4 總 結

本文采用基因進化分支樹算法對圖像進行分割，在基因建樹中，采用基于特征的構建基因樹法，通過節(jié)點順序來構建樹，考慮到基因樹隨機生成的某些分支可能無效以及構建圖像目標函數(shù)的需要，采取最小支持項方法對分支進行剪支和增支，實驗仿真結果顯示本文算法對圖像分割效果連續(xù)，性能指標好。

［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）朱秋煜，李琦銘，陳岳川.基于視差和幀差的圖割優(yōu)化運動目標分割算法［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）鄧玥，王延杰，李靜，等.天空區(qū)域圖像的增強算法的改進［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實現(xiàn)復雜函數(shù)的自動建模［J］.系統(tǒng)仿真學報，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多目標優(yōu)化的代價敏感決策樹構建方法［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］.計算機研究與發(fā)展，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