免疫遺傳算法在圖像分割設(shè)計(jì)中的實(shí)現(xiàn)研究

陳熙，劉皎

（商洛學(xué)院 電子信息與電氣工程學(xué)院，陜西商洛，726000）

0 引言

隨著科學(xué)技術(shù)的快速發(fā)展，圖像處理成為當(dāng)前的一個(gè)熱門研究方向。其技術(shù)已經(jīng)應(yīng)用在我們生活的各個(gè)方面。例如支付寶上的人臉識(shí)別系統(tǒng)、攝像頭上的目標(biāo)檢測(cè)系統(tǒng)、機(jī)器人的路徑識(shí)別系統(tǒng)等等[1～2]。圖像分割技術(shù)作為圖像處理學(xué)科中的重要研究領(lǐng)域，未來(lái)必將發(fā)展成為一個(gè)熱門的學(xué)術(shù)研究課題，如何更好的提升圖像分割的速度和準(zhǔn)確率已成為當(dāng)前研究的熱點(diǎn)問題。當(dāng)前，常用的圖像分割算法有基于圖像閾值分割的最大類間方差(OTSU)法、遺傳算法，邊緣檢測(cè)算法[3]。然而，圖像分割算法也存在著眾多問題和缺點(diǎn)，例如，常見的遺傳算法在分割目標(biāo)和背景差別不大的圖像時(shí)，會(huì)出現(xiàn)分割效果不明顯的情況。故引進(jìn)了免疫遺傳算法來(lái)進(jìn)行圖像分割，該算法加入了免疫算子，從而保持了種群進(jìn)行交叉變異不會(huì)產(chǎn)生退化的現(xiàn)象。免疫遺傳最大的特點(diǎn)是引入了濃度調(diào)節(jié)機(jī)制，通過適應(yīng)度的大小來(lái)判斷選擇的種群，對(duì)于適應(yīng)度高且濃度大的個(gè)體，得到的選擇越大，適應(yīng)度低濃度低的個(gè)體，得到選擇的大小越小，通過遺傳算法的交叉變異操作，使得種群的進(jìn)化方向朝著適應(yīng)度較高的方向進(jìn)行，從而得到最優(yōu)解。

1 遺傳算法的基本原理

遺傳算法是一種仿照自然界生物進(jìn)化、演變過程的模型算法，該算法通過進(jìn)行遺傳操作，子代遺傳父代大量信息的同時(shí)保留優(yōu)良品質(zhì)，不斷遺傳，組合產(chǎn)生最佳個(gè)體，從而實(shí)現(xiàn)尋找最優(yōu)解的目的。

它是運(yùn)用數(shù)學(xué)的形式，用計(jì)算機(jī)仿真運(yùn)算，將求解問題的過程轉(zhuǎn)變成生物進(jìn)化中染色特體基因間交叉和變異的過程，因?yàn)檫z傳算法不能直接對(duì)圖像進(jìn)行處理，先需要通過編碼的方式將圖像的參數(shù)信息轉(zhuǎn)變成遺傳空間的染色體和個(gè)體。

遺傳算法第一個(gè)階段就是對(duì)目標(biāo)問題和函數(shù)變量進(jìn)行編碼，在對(duì)圖像進(jìn)行編碼時(shí)的實(shí)現(xiàn)方式一般主要可以分為兩種，即一類采用二進(jìn)制進(jìn)行編碼和一種采用多位實(shí)數(shù)進(jìn)制編碼。編碼完成后，進(jìn)行第二個(gè)階段的操作，也就是對(duì)編碼的選擇階段。選擇操作其實(shí)就是按某種規(guī)則將其中的優(yōu)良個(gè)體遺傳給下一代的操作，這種操作可以用來(lái)確定用于交叉的個(gè)體，以及被選中的個(gè)體將會(huì)產(chǎn)生多少個(gè)子代個(gè)體。第三個(gè)階段為交叉過程。交叉是交換兩對(duì)編碼染色體的某個(gè)編碼位置，從而形成兩個(gè)新的個(gè)體的過程。交叉包括單點(diǎn)交叉，多點(diǎn)交叉等。第四個(gè)階段是變異。變異就是使用其他的染色體或者編碼串中的某些基因代替染色體上所需要發(fā)生的變異而操作出來(lái)的基因，形成一個(gè)新的細(xì)胞或者個(gè)體。

在上述進(jìn)行編碼、選擇、交叉、變異操作完成后，則要開始進(jìn)行適應(yīng)度的計(jì)算，適應(yīng)度是基于目標(biāo)函數(shù)確定后用來(lái)區(qū)分人們?cè)谌后w中各種個(gè)體的好壞的一個(gè)參數(shù)。通常這個(gè)過程就是先將個(gè)體的編碼字符串進(jìn)行譯碼操作，得到具有個(gè)體特征性的字符串。再通過各種個(gè)體的表現(xiàn)形式進(jìn)行計(jì)算得出目標(biāo)函數(shù)。根據(jù)目標(biāo)函數(shù)所對(duì)應(yīng)的問題種類，目標(biāo)函數(shù)會(huì)計(jì)算得出每一個(gè)體的適應(yīng)性。而后根據(jù)適應(yīng)度在進(jìn)行下次迭代，直到達(dá)到最優(yōu)的結(jié)果。

在遺傳算法中，選擇、交叉、變異三個(gè)算子的設(shè)定需要依靠經(jīng)驗(yàn)，很難保證參數(shù)的品質(zhì)。其不能應(yīng)用于大規(guī)模的問題，容易過早收斂，達(dá)不到最優(yōu)解?；谶@些問題，對(duì)遺傳算法進(jìn)行了改進(jìn)，將其與免疫算法相結(jié)合，形成了免疫遺傳算法，該算法能夠克服簡(jiǎn)單遺傳算法的一些不足之處，且其在分割圖像上達(dá)到了較好的分割效果。

2 免疫遺傳算法的基本原理

免疫遺傳算法則是在傳統(tǒng)遺傳算法的基礎(chǔ)之上引進(jìn)了生物免疫機(jī)制，并利用先驗(yàn)知識(shí)構(gòu)造出免疫疫苗，主要借鑒免疫系統(tǒng)具有產(chǎn)生并維持多樣性抗體以及自我調(diào)節(jié)的能力，在整體框架上引入免疫機(jī)制[4]，形成算法。其流程圖如圖1所示。

圖1 免疫遺傳算法流程圖

從圖1 可以清楚地看出，免疫遺傳算法主要目的就是在遺傳算法為研究基礎(chǔ)，增加了對(duì)抗體濃度概率的計(jì)算、抗體的促進(jìn)和抑制、抗體的傳播三個(gè)功能模塊，進(jìn)一步地提高了求解的方法多樣性。對(duì)這三個(gè)模塊給出的解釋如下。

（1）抗體的濃度是指相近的個(gè)體在種群中所占的比例，將適應(yīng)程度相同的個(gè)體看做相同個(gè)體。

（2）抗體的促進(jìn)和抑制代表個(gè)體的選擇概率增加和減少。一般而言,個(gè)體的選擇包括個(gè)體對(duì)抗體的適應(yīng)程度和個(gè)體抗體濃度的概率兩個(gè)方面,個(gè)體在高濃度適應(yīng)性和低濃度種群中被選定的機(jī)會(huì)較大。

（3）抗體的散布性是指抗體在某個(gè)種群中的分布較好。免疫遺傳算法和免疫算法的基本構(gòu)成也各不相同,其中包含了幾個(gè)主要的基本構(gòu)成元素,主要包括疫苗提取、疫苗接種、免疫檢測(cè)、免疫均衡等算子。

下面將介紹一下這些算子的概念以及在免疫遺傳算法中的作用。

（1）疫苗提取。在免疫算法中,疫苗指的是通過對(duì)目標(biāo)問題進(jìn)行先驗(yàn)性知識(shí)分析提取與其相關(guān)的特征信息。

（2）疫苗接種算子。疫苗是一種來(lái)自于問題的科學(xué)先驗(yàn)知識(shí)，其中包括的信息量和數(shù)據(jù)庫(kù)準(zhǔn)確度對(duì)該算法的特征和性能有著重大的影響。其是以樣品之間的特征值之差累計(jì)和作為先驗(yàn)知識(shí)，構(gòu)造疫苗表，再根據(jù)疫苗表修改抗體，得到更好的結(jié)果。

（3）免疫檢測(cè)算子。是指抗體在接種疫苗之后，用于判斷接種疫苗前后的抗體親和度的高低高。如果接種后抗體親和度高，就將接種后的抗體放入新的種群之中；如果接種后抗體親和度抵，則會(huì)用接種前父代抗體來(lái)代替新抗體。

（4）免疫平衡算子。其主要用來(lái)計(jì)算每個(gè)抗體濃度的概率。通過求解抗體濃度概率，以便于在系統(tǒng)中適應(yīng)度高但濃度的抗體的濃度不斷提高，適應(yīng)度低的但濃度高的抗體濃度降低。該機(jī)制保證了抗體群體更新中的抗體多樣性，在一定程度上有效的避免了未成熟的收斂。

3 免疫遺傳算法和遺傳算法的比較

免疫遺傳算法與傳統(tǒng)遺傳算法相比，具有以下幾方面的特點(diǎn)。

在個(gè)體更新方面：免疫遺傳算法引入疫苗接種算子。疫苗接種算子會(huì)隨機(jī)的選出個(gè)體的某些基因位，將選出的基因位用疫苗的信息進(jìn)行替代，而使得個(gè)體向最優(yōu)解逼近，這樣就可以加快算法的收斂速度，從而實(shí)現(xiàn)個(gè)體更新。

在選擇算子方面：在遺傳算法中個(gè)體更新之后并不去判斷其是否得到了優(yōu)化；但是在免疫遺傳算法中，經(jīng)過了交叉、變異、疫苗和接種算子的相互作用之后，會(huì)對(duì)新個(gè)體會(huì)進(jìn)做免疫檢驗(yàn)和算子操作，則可以判斷其對(duì)人類身體的適應(yīng)度是否優(yōu)于父代個(gè)體。

在維持多樣性方面：在遺傳算法中適應(yīng)度高的個(gè)體在一代中會(huì)被選中的概率高，其對(duì)應(yīng)的濃度就高，反之一樣；而在免疫遺傳算法中，除了抗體的適應(yīng)度還引入了免疫平衡算子。免疫平衡算子會(huì)抑制高濃度的抗體，對(duì)低濃度的抗體進(jìn)行促進(jìn)。

4 算法測(cè)試

為了驗(yàn)證免疫遺傳算法在圖像閾值分割中的高效性，本文重點(diǎn)將免疫遺傳算法和傳統(tǒng)遺傳算法做了測(cè)試比較。在傳統(tǒng)遺傳算法的測(cè)試中，相關(guān)參數(shù)設(shè)定如下：分割閾值設(shè)為8位二進(jìn)制編碼，群體規(guī)模n 設(shè)為10，變異概率Pm 設(shè)為0.08，交叉概率Pc 設(shè)為0.7，則其適應(yīng)度函數(shù)如式(1)所示：

在(1)式中，W1(M)、W2(M) 分別為目標(biāo)圖像和背景圖像中所包含的像素，U1(M)、U2(M) 分別為目標(biāo)圖像和背景圖像的所有像素灰度平均值。在測(cè)試實(shí)驗(yàn)中，分別應(yīng)用傳統(tǒng)遺傳算法和免疫遺傳算法來(lái)實(shí)現(xiàn)圖像分割，群體規(guī)模、變異概率和交叉概率均采用相同的參數(shù)。又考慮到當(dāng)?shù)鷶?shù)相同時(shí)，傳統(tǒng)遺傳算法獲得的最優(yōu)分割閾值精度較差，因此，在實(shí)驗(yàn)中將傳統(tǒng)遺傳算法和免疫遺傳算法的迭代代數(shù)分別設(shè)為100 和50。待分割的原始單目標(biāo)和多目標(biāo)圖像如圖2 所示。在傳統(tǒng)的遺傳算法進(jìn)行圖像分割時(shí)，主要利用遺傳算法尋優(yōu)的特點(diǎn)來(lái)實(shí)現(xiàn)分割操作，首先，將圖片轉(zhuǎn)換為灰度圖而后再實(shí)現(xiàn)分割，通過遺傳操作的尋優(yōu)算法，進(jìn)行了單目標(biāo)和多目標(biāo)圖片的分割，其分割的效果如圖3(a)和圖3(b)所示。

圖2 原始圖像

圖3 遺傳算法圖像分割效果

免疫遺傳算法主要是在遺傳算法的基礎(chǔ)上增加了免疫遺傳算子。加入了免疫遺傳算子，相當(dāng)于加入了先驗(yàn)知識(shí)，是一種多峰值的搜索算法，能夠更加精確的收斂到全局最優(yōu)值，不會(huì)出現(xiàn)遺傳算法中早熟的現(xiàn)象，導(dǎo)致過早的收斂從而變成局部最優(yōu)。免疫遺傳算法實(shí)現(xiàn)單目標(biāo)和多目標(biāo)的圖像分割如圖4(a)和圖4(b)所示。

圖4 免疫遺傳算法圖像分割效果

從分割效果來(lái)看，免疫遺傳算法能夠更加完善地保留圖像的細(xì)節(jié)，并且可以精確地分割出目標(biāo)圖像；而傳統(tǒng)的遺傳算法會(huì)存在一定的過分割，其最優(yōu)閾值的精確度沒有免疫遺傳算法的精度高。免疫遺傳算法能夠以較小的迭代代數(shù)獲得較優(yōu)的圖像分割閾值，這就說(shuō)明了免疫遺傳算法的穩(wěn)定性、收斂性都是優(yōu)于相應(yīng)的傳統(tǒng)遺傳算法的。

對(duì)比圖3 和圖4 可以看出，免疫遺傳算法不管是對(duì)單目標(biāo)的還是多目標(biāo)的圖像，都已經(jīng)能夠?qū)崿F(xiàn)效果比較好的分割，使用免疫遺傳算法來(lái)求取圖像閾值化分割的最優(yōu)閾值比相應(yīng)的傳統(tǒng)遺傳算法更為有效。

5 結(jié)論

綜上，使用遺傳算法分割圖像能夠避免手動(dòng)設(shè)置閾值的問題，通過搜索尋優(yōu)的操作不但能快速的找到圖像需要分割的區(qū)域，而且也實(shí)現(xiàn)了比較好的分割效果；免疫遺傳算法相比于傳統(tǒng)的遺傳算法添加了一種免疫遺傳算子，相當(dāng)于給了遺傳算法一個(gè)先驗(yàn)知識(shí)，通過這個(gè)先驗(yàn)知識(shí)來(lái)使用遺傳算法，不僅能夠比遺傳算法更快的收斂到想要分割的區(qū)域，而且因?yàn)槠湎闰?yàn)知識(shí)，其分割效果也要比免疫遺傳算法要好。