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

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

基于基因進(jìn)化分支樹算法的圖像分割研究

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

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

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

基因樹；結(jié)構(gòu)進(jìn)化；分割

1 前 言

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

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

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

2 基因進(jìn)化分支樹算法模型

2.1 基因組成

設(shè)G＝{Ga，Gb，…}是一組n個(gè)基因的域集，第l個(gè)基因?qū)?yīng)于的節(jié)點(diǎn)為i，i＝1，2，…，m，則對(duì)應(yīng)的基因分支可為如下方式：

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

2.2 基因建樹過程

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

圖1 基因樹3種分支圖結(jié)構(gòu)

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

基因分支之間的關(guān)系為：

s（t）為從第一節(jié)點(diǎn)生成目標(biāo)分支的t時(shí)間均值；p（t）為t時(shí)間內(nèi)為C、D相對(duì)A、B的保持概率為：

如果生成分支的時(shí)間均值越長(zhǎng)，則在基因運(yùn)算符號(hào)作用下保持概率越小。

2.3 基因樹結(jié)構(gòu)進(jìn)化過程

2.3.1 剪支策略

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

2.3.2 增支策略

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

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

2.4 圖像分割過程

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

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

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

把基因樹的分支到節(jié)點(diǎn)的距離比作為圖像質(zhì)量評(píng)價(jià)正確，其目標(biāo)函數(shù)為：

把信息熵作為分割評(píng)價(jià)效果函數(shù)：

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

3 實(shí)驗(yàn)仿真

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

圖2 仿真結(jié)果對(duì)比圖

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

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

表1 分割前后信息熵比較

從表1中可以得知，基因進(jìn)化分支樹算法對(duì)圖像分割前后的信息熵改變不大，可以保持原始圖像的信息，這是因?yàn)榛驑湓谔幚磉^程可調(diào)節(jié)分支的數(shù)量，選擇適量的分割區(qū)域。

4 總 結(jié)

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

［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)化運(yùn)動(dòng)目標(biāo)分割算法［J］.電視技術(shù)，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］.紅外技術(shù)，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ū)域圖像的增強(qiáng)算法的改進(jìn)［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實(shí)現(xiàn)復(fù)雜函數(shù)的自動(dòng)建模［J］.系統(tǒng)仿真學(xué)報(bào)，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）邵明省，王其華.基于蛙跳算法的模糊圖像復(fù)原［J］.激光與光電子學(xué)進(jìn)展，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］.電子學(xué)報(bào)，2011，39（10）：2348－2352.（in Chinese）趙士偉，卓力，王素玉，等.一種基于NNIA多目標(biāo)優(yōu)化的代價(jià)敏感決策樹構(gòu)建方法［J］.電子學(xué)報(bào)，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］.計(jì)算機(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）王鵬杰，潘志庚，徐明亮，等.基于局部最小生成樹的點(diǎn)模型快速無損壓縮算法［J］.計(jì)算機(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ìn)算法［J］.計(jì)算機(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）周惠巍，黃德根，高潔，等.最大生成樹算法和決策式算法相結(jié)合的中文依存關(guān)系解析［J］.中文信息學(xué)報(bào)，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－），女，講師，研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)。E-mail：wangbaohong2013＠foxmail.com

2013-01-03