基于遺傳算法的圖像分割的研究

摘 要:遺傳算法是對(duì)生物進(jìn)化論中自然選擇和遺傳學(xué)機(jī)理中生物進(jìn)化過程的模擬來計(jì)算最優(yōu)解的方法。遺傳算法具有眾多的優(yōu)點(diǎn)，如魯棒性、并行性、自適應(yīng)性和快速收斂，可以應(yīng)用在圖像處理技術(shù)領(lǐng)域中圖像分割技術(shù)來確定分割閾值。圖像分割是圖像處理技術(shù)的研究對(duì)象之一，它對(duì)于圖像特征提取、圖像識(shí)別等圖像處理技術(shù)等有著重要意義。主要研究基于遺傳算法的圖像分割效果，采用Matlab軟件進(jìn)行仿真實(shí)驗(yàn)，對(duì)不同圖像分割算法的效果進(jìn)行比較。實(shí)驗(yàn)表明，遺傳算法是處理圖像分割的優(yōu)秀算法，圖像分割效果相比于傳統(tǒng)的圖像分割算法更加優(yōu)秀。

關(guān)鍵詞:圖像分割; 閾值計(jì)算; 遺傳算法; 圖像特征

中圖分類號(hào):TP919.8 文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2010)14-0042-03

Image Segmentation Based on Genetic Algorithm

CHEN Jie， FU Yan

(Guangdong Institute of Science Technology， Guangzhou 510640， China)

Abstract: Genetic algorithm is an optimal solution method of using natural selection in biological evolution and biological evolution in genetic mechanism. Genetic algorithm has many advantages such as robustness， parallel， adaptive， and fast convergence， can be used in the field of image processing to determine the threshold value. Image segmentation is one of the objects of image processing， it is meaningful to the image feature extraction， image recognition and other image processing technologies. The image segmentation effect based on genetic algorithm of using MATLAB software to simulate the different image segmentation algorithms and compare the result .Experiments indicate that the genetic algorithm is outstanding to deal with the image segmentation ，the results is more outstanding than traditional image segmentation algorithm.

Keywords: image segmentation;threshold computation;genetic algorithm; image feature

0 引 言

圖像分割是圖像處理中的一項(xiàng)關(guān)鍵技術(shù)，隨著20世紀(jì)數(shù)字圖像處理技術(shù)的興起而受到人們的廣泛深入的研究，提出了很多優(yōu)秀的算法。但這些算法往往只在某一個(gè)方面表現(xiàn)出優(yōu)秀的解決問題的能力，在另外的一些領(lǐng)域則需要其他的圖像分割算法。因此，現(xiàn)有的圖像分割算法并沒有一般意義上的通用性。另外，圖像分割效果的評(píng)估也沒有相應(yīng)的評(píng)判標(biāo)準(zhǔn)，通常的處理方式只能是具體問題具體分析。圖像的分割是以灰度值作為分割的依據(jù)，通過各個(gè)像素的灰度值和事先確定的閾值的比較來分割圖像。從算法中可以看出，如何確定最合適的閾值成為處理好圖像分割的關(guān)鍵，這自然成為一直以來分割算法研究的焦點(diǎn)。

圖像分割是數(shù)字圖像處理技術(shù)與計(jì)算機(jī)視覺的基本問題之一，其要點(diǎn)是:把圖像劃分成若干互不交疊區(qū)域的像素的集合，這些區(qū)域要么對(duì)當(dāng)前的分割有意義，是目標(biāo)物體與背景的邊緣，要么有助于說明它們之間的對(duì)應(yīng)關(guān)系。圖像分割伴隨著數(shù)字圖像處理技術(shù)在實(shí)際中已經(jīng)得到廣泛的應(yīng)用，例如在工業(yè)工程，產(chǎn)品檢驗(yàn)，工業(yè)控制，圖像處理，衛(wèi)星圖片、生物醫(yī)學(xué)圖像分析、保安監(jiān)控以及軍事、衛(wèi)生、農(nóng)業(yè)工程等諸多領(lǐng)域[1]。概括來說，在各種圖像應(yīng)用中，只需對(duì)圖像物體目標(biāo)進(jìn)行提取、測量等進(jìn)一步操作都離不開圖像分割，圖像分割往往是這些處理步驟的準(zhǔn)備階段，圖像分割的效果直接影響后續(xù)任務(wù)的有效性，因此圖像分割具有重要的研究意義。圖像分割技術(shù)的發(fā)展和更新與許多學(xué)科和領(lǐng)域密切相關(guān)，例如數(shù)學(xué)、物理學(xué)、心理學(xué)、電子學(xué)、無線電、計(jì)算機(jī)科學(xué)等。隨著各學(xué)科不同的新理論和新方法的提出，人們也嘗試用來解決圖像分割問題，發(fā)展出許多具有特點(diǎn)理論、方法和工具的分割技術(shù)。每當(dāng)有新的數(shù)學(xué)理論、方法或工具提出來，它往往就被嘗試用于圖像分割，也因此提出了不少特殊的算法。例如利用數(shù)學(xué)形態(tài)學(xué)、模糊ART、模擬退火、遺傳算法等[2]。其中，遺傳算法具有魯棒性、并行性、自適應(yīng)性和快速收斂的突出優(yōu)點(diǎn)。遺傳算法在各個(gè)應(yīng)用領(lǐng)域取得的巨大成功引起了廣大學(xué)者的關(guān)注并開始嘗試用來解決圖像分割問題。遺傳算法是一種迭代式的優(yōu)化算法，能夠在圖像分割時(shí)來幫助合理地確定分割閾值。

圖像分割方法可以大致分為4類[3]:

(1) 利用圖像灰度值統(tǒng)計(jì)的方法，常用方法有一維直方圖閾值化方法和二維直方圖閾值化方法。

(2) 利用圖像空間域信息和光譜信息的圖像分割方法，常用的有區(qū)域分裂、合并生長法、紋理分割法和多光譜圖像分割法等。

(3) 利用圖像中灰度變化最強(qiáng)烈的區(qū)域信息方法，即邊緣檢測方法，它在圖像分割研究領(lǐng)域中占的比例最大，利用不同的算子進(jìn)行邊緣檢測，比較常用的如canny算子。

(4) 利用圖像分類技術(shù)進(jìn)行圖像分割的像素分類方法。常用的有統(tǒng)計(jì)分類方法、模糊分類方法與神經(jīng)網(wǎng)絡(luò)分類方法等。

1 圖像閥值

一幅圖像通常包括目標(biāo)物體、背景高斯噪聲、運(yùn)動(dòng)模糊等，由于目標(biāo)物體和背景的灰度有較大差異，和噪聲產(chǎn)生的麻點(diǎn)的灰度值相差更多，要從多值的灰度圖像中提取目標(biāo)物體，常用的方法就是設(shè)定某一閾值，將圖像像素分成2大部分:大于閾值的像素和小于閾值的像素即灰度圖像的二值化。二值化處理只要功能就是把目標(biāo)物體和背景灰度差異較大的圖像分成2個(gè)部分。二值化是數(shù)字圖像處理中一項(xiàng)最簡單的變換方法，通過采用固定閾值、雙固定閾值等不同算法，把一幅灰度圖變成二值圖像，將所需的目標(biāo)物體地從復(fù)雜的圖像背景中脫離出來[4]。具體的操作過程是先由通過算法找到一個(gè)合適閾值，要求是閾值處于目標(biāo)物體閾值和背景閾值之間。若圖像中的像素灰度值小于該閾值，則將該像素的灰度值設(shè)置為0或255，若圖像中的像素灰度值大于該閾值，則將該像素的灰度值設(shè)置為255或0。也就是說通過一個(gè)以閾值灰度值為跳變點(diǎn)的階躍函數(shù)來實(shí)現(xiàn)圖像處理。其中閾值灰度值需要同多合適的算法來確定。經(jīng)過處理后的圖像是一幅二值圖。

1.1 固定閾值法

固定閾值法就是為灰度圖像設(shè)定一個(gè)閾值，把灰度值小于給定閾值的像素置為0(或者255)，大于閾值的像素置為255(或者0)，從而實(shí)現(xiàn)灰度圖像到二值圖像的變換[5]。

1.2 雙固定閾值法

雙固定閾值法預(yù)先設(shè)置2個(gè)閾值，當(dāng)對(duì)圖像進(jìn)行處理時(shí)，如果某個(gè)像素的灰度值在兩者之間時(shí)置0(或者255);其余情況則置255(或者置0)。應(yīng)當(dāng)根據(jù)具體情況選擇雙固定閾值法改變圖像灰度值的方向。

2 基于遺傳算法的圖像分割

遺傳算法(genetic algorithm)最早應(yīng)用于對(duì)生物系統(tǒng)的計(jì)算機(jī)模擬，研究方面主要涉及到算法結(jié)構(gòu)，算法參數(shù)，算法適用范圍等方面。遺傳算法采用整體搜索策略和優(yōu)化搜索。遺傳算法是通用的一種方法，不涉及具體的研究領(lǐng)域和內(nèi)容，只關(guān)心相應(yīng)的目標(biāo)函數(shù)和輔助函數(shù)，即所謂魯棒性。因此廣泛應(yīng)用于工業(yè)工程、計(jì)算科學(xué)、工控系統(tǒng)、交通、計(jì)算機(jī)、通信、電子科學(xué)與技術(shù)等領(lǐng)域。在圖像分割過程中，最關(guān)鍵的就是找到最優(yōu)的閾值，遺傳算法可以說是解決這個(gè)問題的優(yōu)秀算法之一，它的整體搜索策略和優(yōu)化搜索方法能夠快速準(zhǔn)確地得到基于成個(gè)灰度圖像的閥值最優(yōu)解[6]。

遺傳算法運(yùn)算的基本流程:

(1)針對(duì)圖像分割編寫代碼:遺傳算法一般不直接處理空間的參數(shù)而是集進(jìn)行編碼，即用0和1構(gòu)成的字符串形成矩陣。

(2)隨機(jī)初始化像素群體X(0):=(x1，x2，…，xn):遺傳算法從這些群體出發(fā)，模擬生物進(jìn)化過程進(jìn)行選擇，最后得出需要的個(gè)體集合，滿足優(yōu)化搜索的要求。

(3) 對(duì)當(dāng)前像素群體X(t)中每個(gè)個(gè)體xi計(jì)算其適應(yīng)度F(xi)，適應(yīng)度表示了該像素的灰度值:遺傳算法不涉及問題的具體領(lǐng)域，只需依據(jù)適應(yīng)度函數(shù)控制像素變化。根據(jù)適應(yīng)度函數(shù)對(duì)每個(gè)像素計(jì)算其適應(yīng)度，為選擇提供依據(jù)。設(shè)計(jì)適應(yīng)度函數(shù)的方法是把問題的目標(biāo)函數(shù)轉(zhuǎn)換成合適的適應(yīng)度函數(shù)和輔助函數(shù)[7]。

(4) 應(yīng)用選擇算子產(chǎn)生Xr(t)。

(5) 對(duì)Xr(t)應(yīng)用其他的算子，產(chǎn)生新一代像素群體X(t+1)，應(yīng)用其他的算子可以擴(kuò)展圖片像素的覆蓋面，體現(xiàn)整體計(jì)算的策略。

(6)選擇:這是是遺傳算法的關(guān)鍵，它參照了適者生存的理論。

(7) 變異:模擬了生物的基因突變現(xiàn)象。對(duì)像素進(jìn)行重新評(píng)價(jià)、選擇如此循環(huán)往復(fù)，使圖像中目標(biāo)物體平均適應(yīng)度不斷提高直到上限則迭代過程收斂，算法結(jié)束。變異算子保證的是算法能搜索到圖像的每一個(gè)像素，也是體現(xiàn)全局的策略。 

遺傳算法最常用的算子:

(1)選擇算子: 選擇算子從群體中按某一概率成對(duì)選擇個(gè)體，某個(gè)體xi被選擇的概率Pi與其適應(yīng)度值成正比。最通常的實(shí)現(xiàn)方法是輪盤賭模型[8]。

(2)交叉算子: 交叉算子將被選中的2個(gè)個(gè)體的基因鏈按概率進(jìn)行交叉，生成2個(gè)新的個(gè)體，交叉位置是隨機(jī)的。其中是一個(gè)系統(tǒng)參數(shù)。

(3)變異算子: 變異算子將新個(gè)體的基因鏈的各位按概率進(jìn)行變異，對(duì)二值基因鏈來說即是取反[9]。

上述各種算子的實(shí)現(xiàn)是多種多樣的，而且許多新的算子正在不斷地提出，以改進(jìn)遺傳算法的某些性能。系統(tǒng)參數(shù)(個(gè)體數(shù)n，基因鏈長度l，交叉概率Pc，變異概率Pm等)對(duì)算法的收斂速度及結(jié)果有很大的影響，應(yīng)視具體問題選取不同的值。

遺傳算法是一種通用的算法，在程序設(shè)計(jì)應(yīng)時(shí)也應(yīng)考慮到程序的重用性，而且應(yīng)該能夠代入其他算子進(jìn)行運(yùn)算。面向?qū)ο蟮木幊讨械念惖睦^承提供了這一可能[10]。

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

仿真實(shí)驗(yàn)如圖1所示。

圖1 仿真實(shí)驗(yàn)圖示

實(shí)驗(yàn)分析:

比較未采用遺傳算法的圖像分割、遺傳算法的圖像分割的結(jié)果:

(1) 用遺傳算法做圖像分割比未采用遺傳算法的圖像分割實(shí)際視覺效果好。

(2) 遺傳算法同時(shí)對(duì)多處理，因此遺傳算法具有較好的全局性。

(3) 遺傳算法采用適應(yīng)度函數(shù)，對(duì)個(gè)體進(jìn)行分割，能求得最優(yōu)解，即獲得最佳分割點(diǎn)。

提出基于遺傳算法的圖像分割方法及適應(yīng)度選取，在Matlab平臺(tái)上對(duì)圖像進(jìn)行仿真，實(shí)驗(yàn)結(jié)果表明，圖像二值化效果優(yōu)秀。

4 結(jié) 語

(1) 圖像分割是圖像處理和計(jì)算機(jī)視覺中基本技術(shù)，是大多數(shù)圖像處理和視覺系統(tǒng)過程的重要預(yù)處理階段。圖像分割是應(yīng)用一種或多種運(yùn)算將圖像分成一些 具有相似特性的區(qū)域，主要有閾值法和區(qū)域法。前者如:直方圖法、一維二維最大熵法、最小誤差法、最大類問方差法等。后者是利用局部空間信息進(jìn)行分割，將具有相似特性的像素集合起來構(gòu)成區(qū)域，主要有區(qū)域生長法和分裂合并法。在實(shí)際應(yīng)用中應(yīng)根據(jù)實(shí)際需要選取不同的圖像分割方法。

(2) 遺傳算法是模擬自然界機(jī)制和生物進(jìn)化論而形成的一種搜索最優(yōu)解的算法。它不需要求解問題的任何信息而僅需目標(biāo)函數(shù)的信息，只關(guān)心目標(biāo)函數(shù)。通過產(chǎn)生初始群種，計(jì)算個(gè)體適應(yīng)度，依據(jù)適應(yīng)度選擇再生個(gè)體、交叉、變異生成新的個(gè)體。本文通過仿真實(shí)驗(yàn)證明，遺傳算法作為一種優(yōu)化算法在用于圖像分割時(shí)，縮短了尋找閾值的運(yùn)算時(shí)間，圖像分割處理質(zhì)量好，有著廣闊的應(yīng)用潛力。

參考文獻(xiàn)

[1]汪筱紅，須文波.基于遺傳算法的閾值圖像分割研究[J].太原師范學(xué)院學(xué)報(bào):自然科學(xué)版，2007，6(3):111-113，144.

[2]LI Wei-wei， HUANG Hui-xian， ZHANG Dong-bo， et al. A color image segmentation method based on automatic seeded region growing[C]//2007IEEE International Conference on Automation and Logistics. Washington DC: IEEE Computer Society， 2007: 1925-1929.

[3]LI Yong-cang， YIN Hai-ming， SHI Mei-hong， et al. A method of color image segmentation based on DPCNN[C]//Proceedings of the2008International Conference on Cyberworlds. Washington DC: IEEE Computer Society， 2008: 725-729.

[4]屠昂燕，陳建成.遺傳算法的收斂性研究[J].湖北第二師范學(xué)院學(xué)報(bào)，2008，25(2):49-51.

[5]李紅梅.遺傳算法概述[J].軟件導(dǎo)刊，2009(1):67-68.

[6]汪慧蘭.圖像檢索中圖像分割方法綜述[J].皖西學(xué)院學(xué)報(bào)，2009，25(2):18-21.

[7]楊金龍，張光南，厲樹忠，等.基于二維直方圖的圖像分割算法研究[J].激光與紅外，2008，38(4):400-403.

[8]葉志偉，張金平，賴旭東.基于粒子群算法的最大交叉熵的圖像分割方法[J].安徽農(nóng)業(yè)科學(xué)，2007，35(23):7037-7038，7041.

[9]張超，張家樹，賈東立.基于混沌遺傳算法的圖像閾值分割[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(2):45-47.

[10]徐小慧，張安.基于粒子群優(yōu)化算法的最佳熵閾值圖像分割[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(10):8-11.