趙明霞　呂致　郝雅潔　史維杰　李富忠

摘要：針對(duì)部分田間圖像由于其背景復(fù)雜、光照不均勻等導(dǎo)致很難確定圖像分割的最佳閾值問(wèn)題，提出了一種基于結(jié)合遺傳算法Otsu算法改進(jìn)的圖像分割方法。首先對(duì)采集的圖像進(jìn)行預(yù)處理，基于預(yù)處理圖像通過(guò)改進(jìn)遺傳算法中的選擇、交叉、變異三種方法以及基于Otsu優(yōu)化個(gè)體適應(yīng)度函數(shù)，實(shí)現(xiàn)了可以自動(dòng)調(diào)整遺傳控制參數(shù)，既確保了物種的多樣性又加快其收斂速度，為Otsu圖像分割提供了最佳閾值，最后經(jīng)過(guò)圖像形態(tài)學(xué)對(duì)圖像進(jìn)行填充。將改進(jìn)遺傳算法的Otsu算法與基于遺傳算法+Otsu算法進(jìn)行圖像分割以及基于遺傳算法+Ksw熵值圖像分割進(jìn)行了對(duì)比，發(fā)現(xiàn)該算法得到的閾值范圍較為穩(wěn)定，使得分割后的圖像準(zhǔn)確、清晰，對(duì)于后期進(jìn)行作物株數(shù)的統(tǒng)計(jì)或者植株的覆蓋度有一定的幫助。

關(guān)鍵詞：全局閾值分割;遺傳算法;大津算法

中圖分類號(hào)：TP751? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：0439-8114（2019）15-0119-05

DOI：10.14088/j.cnki.issn0439-8114.2019.15.028? ? ? ? ? ?開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

Improved genetic algorithm combined with improved Otsu

algorithm for field crop segmentation

ZHAO Ming-xia，LYU Zhi，HAO Ya-jie，SHI Wei-jie，LI Fu-zhong

（Software College of Shanxi Agricultural University，Taigu 030801，Shanxi，China）

Abstract： For some field images， it is difficult to determine the optimal threshold problem of image segmentation due to its complicated background and uneven illumination. This paper proposes an image segmentation method based on improved Otsu algorithm optimization and improved genetic algorithm. Firstly， the acquired images are pre-processed. Based on the preprocessed images， the genetic control parameters can be automatically adjusted by improving the three methods of selection， crossover and variation in the genetic algorithm and optimizing the individual fitness function based on Otsu， so as to ensure the diversity of species and accelerate its convergence speed. The optimal threshold is provided for the Otsu image segmentation， and finally the image is filled by image morphology. In the result of the discussion， the algorithm results are compared with the Genetic Algorithm Based on the Otsu Algorithm and the Image Segmentation Based on Genetic Algorithm and KSW Entropy. It is found that the threshold range obtained by the algorithm is stable， which makes the segmented image accurate and clear. It is helpful to calculate the number of crops or the coverage of plants in the later stage.

Key words： global threshold segmentation; genetic algorithm; Otsu algorithm

圖像分割是結(jié)合圖像的強(qiáng)度、圖像的紋理特征、顏色特征以及圖像的對(duì)比度等內(nèi)在表現(xiàn)[1，2]，將圖像分割成非重疊的感興趣對(duì)象的技術(shù)。圖像分割在圖像識(shí)別、處理以及視頻解析的過(guò)程中扮演著十分重要的角色，其分割效果對(duì)于檢測(cè)目標(biāo)、識(shí)別目標(biāo)物以及跟蹤目標(biāo)的后續(xù)操作影響深遠(yuǎn)。圖像分割的主要目的是根據(jù)一定的準(zhǔn)則確定一個(gè)有效閾值（用于兩級(jí)閾值）或多個(gè)閾值（用于多級(jí)閾值）[3]。

圖像閾值分割是圖像分割中較為熱門的方法。近年來(lái)，圖像閾值分割方法不斷地創(chuàng)新，可分為固定門限閾值算法[4]、自適應(yīng)門限閾值算法[5]、最大熵法[6]和Ostu法等多種分割算法。而遺傳算法（GA）因其可作為圖像分割過(guò)程中求取最佳閾值的一種高效算法，得到了廣泛的研究和應(yīng)用。Kirkpatrick[7]提出了利用遺傳算法進(jìn)行閾值優(yōu)化的方法。文獻(xiàn)[8]提出了一種基于遺傳算法（GA）的MR圖像分割算法，用于MR圖像中未標(biāo)記像素的自動(dòng)分組。在實(shí)現(xiàn)過(guò)程中，成功地證明了迭代法和自定義法對(duì)于分割圖像給出了幾乎相同的閾值[9]。文獻(xiàn)[10]提出了一種使用遺傳算法和KSW熵法相結(jié)合的CT圖像肺部分割方法。但是，傳統(tǒng)的遺傳算法因收斂速度緩慢、易早熟等不足之處，對(duì)于最佳閾值的選擇并不是一個(gè)很好的方法。為此，研究提出了一種改進(jìn)遺傳算法同時(shí)結(jié)合改進(jìn)Otsu閾值分割的方法，有效解決了收斂慢、易早熟的問(wèn)題，從而求出最優(yōu)解。

1? 大津算法

Otsu閾值技術(shù)是由Kittler等[11]和Otsu[12]提出的。最大類間方差法（Otsu）是基于二維類間方差法以及最小二乘法進(jìn)一步推導(dǎo)得出的[13]。其核心思想是：通過(guò)設(shè)定閾值對(duì)圖像進(jìn)行分類，可分為：背景部分以及目標(biāo)物部分。最優(yōu)閾值是通過(guò)計(jì)算兩者間的方差值，即當(dāng)閾值t為某一值時(shí)，其方差值最大。此時(shí)閾值t為最佳圖像分割閾值。其原理公式如下：

假設(shè)f（x，y）為圖像M×N某一點(diǎn)的灰度值，其灰度級(jí)為L(zhǎng)，則f（x，y）∈{0，L-1}，記作：GL。

灰度值i在圖像中的概率為：

P（i）=■ i∈Gl? （1）

如上所述，設(shè)定閾值t將圖像分為前景（0，t）和背景（t，L-1）兩部分。則前景區(qū)域比例以及背景區(qū)域比例分別如下：

b0（t）=∑■p（i） （2）

d1（t）=∑■p（i）? ?（3）

前景部分以及背景部分平均灰度分別為：

u0（t）=∑■■? ?（4）

u1（t）=∑■■? （5）

圖像總體均值為：

u（t）=b0（t）u0（t）=d1（t）u1（t）? ?（6）

兩者之間的方差即最佳閾值取值，表述如下：

？啄■■=b0（u0-u）2+d1（u1-u）2? （7）

運(yùn)行過(guò)程中于GL范圍內(nèi)依次為t賦值，當(dāng)t為某一值使得？啄■■的值為最大時(shí)，表明此時(shí)的t值為最佳分割閾值。

2? 傳統(tǒng)的遺傳算法

遺傳算法作為一種基于自然選擇和遺傳進(jìn)化思想的自適應(yīng)元啟發(fā)式搜索算法，以其變異算子[14]而聞名。其核心理念可以看成是以生物學(xué)中的自然選擇以及生物遺傳機(jī)制算法為基礎(chǔ)的一種隨機(jī)搜索算法。通過(guò)模擬自然界的繁殖、交叉和變異現(xiàn)象，在每次迭代中保留一組候選解，并根據(jù)某些指標(biāo)從解組中選出較好的個(gè)體。將個(gè)體與遺傳算子相結(jié)合，生成新一代候選解，并重復(fù)此過(guò)程，直到滿足收斂指標(biāo)[14，15]。

遺傳算法的主要組成部分是：編碼機(jī)制、適應(yīng)度函數(shù)、遺傳算子（選擇、交叉和變異）和控制參數(shù)。若采用遺傳算法進(jìn)行解決問(wèn)題時(shí)，其可能的解被編碼到染色體中，即個(gè)體。幾個(gè)人組成一個(gè)初始的解決方案組。通過(guò)計(jì)算適應(yīng)度函數(shù)，輸出滿足終止條件的個(gè)體，算法結(jié)束。否則，遺傳算法使用三個(gè)基本操作符（選擇、交叉和突變）來(lái)操縱種群的遺傳組成。選擇是將當(dāng)前代中適應(yīng)度值最高的個(gè)體復(fù)制到新一代的過(guò)程。交叉操作符通過(guò)重新組合來(lái)自雙親的信息產(chǎn)生兩個(gè)后代（新的候選解決方案）。突變是個(gè)體某些基因值的隨機(jī)改變。每個(gè)基因的等位基因都是突變的候選基因，其突變概率決定了其功能。在新一代中，種群比上一代更適應(yīng)環(huán)境，進(jìn)化一直持續(xù)到滿足優(yōu)化準(zhǔn)則為止。對(duì)最后一個(gè)個(gè)體進(jìn)行解碼，得到最優(yōu)解。

3? 基于遺傳算法的閾值優(yōu)化

3.1? 改進(jìn)的遺傳算法

傳統(tǒng)的遺傳算法擁有高效的運(yùn)算優(yōu)勢(shì)之時(shí)也存在僅僅局部?jī)?yōu)化的特點(diǎn)，為了避免因此產(chǎn)生的困境，對(duì)其進(jìn)行了改進(jìn)。主要針對(duì)其中的選擇、交叉和變異算子進(jìn)行優(yōu)化。

首先，改進(jìn)遺傳算法中的輪盤選擇法?；A(chǔ)的輪盤選擇法中若變異產(chǎn)生了一個(gè)新的最大值（更接近于最優(yōu)值），但是其種群數(shù)量就只有1，遠(yuǎn)遠(yuǎn)比不上當(dāng)前的最大值（離最優(yōu)值遠(yuǎn)一點(diǎn)）。若直接使用輪盤選擇法，那么這個(gè)新變異出來(lái)的值就會(huì)被覆蓋掉。通過(guò)強(qiáng)制將上一代中最大的值進(jìn)行保留，來(lái)保證種群不會(huì)退化。核心代碼如下：

for i in range（len（fitness_list））：

if fitness_list[i] == max_fitness：

new_populations.append（self.populations[i]）

else：

remain_populations.append（self.populations[i]）

其次，傳統(tǒng)的算法中，交叉和變異值的選取是至關(guān)重要的，它們對(duì)于算法的行為或者性能有直接的影響，而且還能凸顯出算法的收斂性。傳統(tǒng)的遺傳算法通常將兩者設(shè)置為固定值（范圍0.4～0.9），其缺點(diǎn)在于最優(yōu)的圖像閾值與真實(shí)值之間存在一定的差異，從而無(wú)法進(jìn)行最優(yōu)的圖像分割。

本研究中，針對(duì)交叉算子Pc，使得Pc為兩個(gè)不同的概率值。迭代前期，為了避免淘汰過(guò)多的個(gè)體造成的搜索全局最優(yōu)困境，可將其值提高，所以前期設(shè)置為0.8;當(dāng)處于中后期時(shí)，為了增強(qiáng)其收斂速度同時(shí)保證優(yōu)秀個(gè)體，交叉概率值可適當(dāng)?shù)慕档停纯扇≈禐?.6）從而優(yōu)化全局最優(yōu)值的搜索，進(jìn)而獲得良好的分割效果。具體內(nèi)容如下：

Pc=0.8 gen≤200.6 gen>20? ?gen為迭代的次數(shù)? （8）

使得初期迭代時(shí)，個(gè)體選中的概率增大;同時(shí)后期又防止了優(yōu)秀個(gè)體的損失。

針對(duì)變異算子Pm，將Pm設(shè)置為變化的概率值：

Pm=0.02 gen≤300.03? gen>300.02? gen>50&gen≤50，gen為迭代的次數(shù)（9）

3.2? 改進(jìn)的Otsu算法

閾值法進(jìn)行圖像分割的要點(diǎn)是閾值t的選擇。若t的取值較高時(shí)，則會(huì)出現(xiàn)背景誤認(rèn)為目標(biāo)部分的現(xiàn)象，干擾了后續(xù)的一系列圖像處理操作，例如：特征的提前等;當(dāng)t的取值偏低，則會(huì)將目標(biāo)區(qū)域劃分到背景區(qū)域，從而導(dǎo)致有用信息丟失。因此，最佳閾值t的選取對(duì)于精準(zhǔn)的圖像分割尤為重要。

結(jié)合上述所言，當(dāng)（7）式？啄■■目標(biāo)物與背景區(qū)域之間的差異越顯著，圖像的分割效果越好。也可以理解為獲取的閾值使得圖像的兩部分與圖像的中心相隔較大[即u0（t）與u1（t）]。圖像兩部分之間的距離可表示為（假設(shè)度量為1個(gè)距離）：

d2（t）=[u0（t）-u1（t）]2? ?（10）

原理同上，d2（t）的取值越大，其分割效果越好。而且，兩部分中每個(gè)像素與其中心相距應(yīng)盡量降低，表明像素間的內(nèi)聚力較好。因此，提出了平均方差的理念，它可以描述像素間的內(nèi)聚力。

■02（t）=■∑■[i-u0（t）]2p（i）? （11）

■12（t）=■∑■[i-u1（t）]2p（i）? （12）

■02與■12取值越小，其每個(gè)部分的像素分布越均勻，其內(nèi)聚力越好，從而圖像的分割效果好。

結(jié)合以上兩種因素，在維持兩部分相距較大的同時(shí)保證每部分間的像素內(nèi)聚力好，從而更好地分割圖像。因此，由上述分析的Otsu基礎(chǔ)算法上衍生了一種新的最佳閾值獲取辦法。其體現(xiàn)在公式中可表示為：

G（t）=■=■（13）

可知，G（t）值為最大時(shí)，其所對(duì)應(yīng)的灰度級(jí)便是最佳閾值Th。如下：

Th=argmax[G（t）] t∈GL? （14）

3.3? 改進(jìn)遺傳算法結(jié)合改進(jìn)大津算法

大津算法獲取最優(yōu)閾值的過(guò)程等價(jià)于（14）式的求解。因此，可將其與改進(jìn)的遺傳算法相結(jié)合進(jìn)行完善。兩種算法結(jié)合的主要核心步驟表述如下。

3.3.1? 制定編碼與解碼規(guī)則? 主要使用二進(jìn)制編碼原則，基于圖像的灰度值取值范圍（0～255），選擇16位二進(jìn)制串對(duì)閾值（s，t）進(jìn)行編碼。前8位代表閾值s，而后8位則是t;通過(guò)將16位二進(jìn)制串分別解碼為0～255間的數(shù)值來(lái)獲取適應(yīng)度的取值。

3.3.2? 初始化種群? 群體的初始值對(duì)于遺傳算法的執(zhí)行效率以及運(yùn)行結(jié)果有直接影響。若取值過(guò)大，算法的復(fù)雜度增加;若取值偏小，因其空間有限，則很難獲取最優(yōu)的分割閾值。

3.3.3? 選擇適應(yīng)度函數(shù)? 通過(guò)將式（14）作為適應(yīng)度函數(shù)，求取最佳適應(yīng)度值。

3.3.4? 選擇? 針對(duì)輪盤選擇法進(jìn)行改進(jìn)。通過(guò)保留上一代中最大值來(lái)保證種群的多樣化。

3.3.5? 交叉? 設(shè)置交叉概率值為兩個(gè)不同的概率值。同時(shí)，從基因一半往后的位置開(kāi)始交換，這樣有利于保持當(dāng)前的最優(yōu)值，使得交換之后的種群不至于很差。

3.3.6? 變異? 將變異值設(shè)置為變化的概率值。但是，對(duì)于每一個(gè)個(gè)體，對(duì)任意位置產(chǎn)生一位變異，但是變異概率不宜設(shè)計(jì)的很大，這樣會(huì)導(dǎo)致種群不易收斂。

3.3.7? 終止條件? 當(dāng)滿足種群迭代的最大值且種群的98%個(gè)體都指向同一個(gè)值時(shí)，算法停止運(yùn)行，此時(shí)具有最高適應(yīng)度值的個(gè)體即為最佳閾值。

圖像分割流程如圖1所示。

4? 試驗(yàn)分析

自然環(huán)境復(fù)雜多變，想要獲取很多的作物信息，需要優(yōu)化圖像分割的效果。為了驗(yàn)證改進(jìn)遺傳算法的Otsu圖像分割算法在復(fù)雜背景下的可行性，通過(guò)相機(jī)（大疆精靈4pro）于山西農(nóng)業(yè)大學(xué)資源環(huán)境學(xué)院實(shí)驗(yàn)站采集田間返青期、七葉期小麥（圖像的像素為822×856）。在處理器Intel（R） Core（TM） i5-8300H CPU @2.30GHz，8.00GB內(nèi)存的計(jì)算機(jī)上對(duì)基于傳統(tǒng)的遺傳算法解Otsu算法以及基于遺傳算法與Ksw熵值作物圖像分割兩種方法進(jìn)行了比較。試驗(yàn)流程圖如圖2所示。

分別使用遺傳算法+Ksw熵算法、遺傳算法+Otsu算法以及改進(jìn)遺傳算法的Otsu圖像分割算法針對(duì)返青期、七葉期小麥進(jìn)行了圖像分割，結(jié)果分別見(jiàn)圖3和圖4。從最終的圖像分割圖來(lái)看，圖3和圖4均存在著過(guò)分割的情況，而改進(jìn)遺傳算法的Otsu圖像分割算法得到的分割圖像相對(duì)較好。除了使用這種定性的分析外，研究通過(guò)對(duì)比三種算法所獲得的閾值、所需時(shí)間以及精準(zhǔn)率來(lái)比較三者的區(qū)別（其中種群數(shù)量設(shè)置為20以及迭代次數(shù)為300）。結(jié)果如表1所示。結(jié)合表1與表2可發(fā)現(xiàn)，改進(jìn)遺傳算法的Otsu圖像分割算法在準(zhǔn)確率方面較另外兩種算法較高（準(zhǔn)確率可以看作是在所操作的測(cè)試數(shù)據(jù)集中，其正確分類的樣本數(shù)量占總樣本數(shù)量的比例）。因改進(jìn)遺傳算法與Otsu算法相結(jié)合，導(dǎo)致算法的復(fù)雜度增加，運(yùn)算過(guò)程耗時(shí)較長(zhǎng)，但與基本遺傳算法結(jié)合Ksw或者大津算法相比，在保持迭代次數(shù)等同的條件下，改進(jìn)遺傳算法既可以維持種群的多樣化又提高了收斂速度。

兩種改進(jìn)算法相結(jié)合與改進(jìn)前的算法以及基于遺傳算法的Ksw熵值分割算法進(jìn)行比較，其最佳閾值的獲取更加有效，在提升了圖像分割精度的同時(shí)又保證了圖像有效信息的展現(xiàn)。改進(jìn)的算法其穩(wěn)定性較好，結(jié)果精確度高，對(duì)于作物圖像分割的效果有很大的幫助。

5? 小結(jié)

通過(guò)將改進(jìn)的遺傳算法與Otsu閾值分割算法相結(jié)合對(duì)田間植物圖像進(jìn)行處理，在對(duì)適應(yīng)度函數(shù)進(jìn)行全局優(yōu)化的同時(shí)，對(duì)交叉、變異兩者的概率值有一定的改進(jìn)，達(dá)到了可以自動(dòng)調(diào)控參數(shù)且在保證群體不退化的前提下又提高了其收斂速度的目的。最終使得圖像分割的閾值范圍穩(wěn)定在2～3個(gè)像素以內(nèi)，算法的穩(wěn)定性得到進(jìn)一步加強(qiáng)，實(shí)現(xiàn)了圖像的高效分割。

改進(jìn)遺傳算法的Otsu圖像分割算法因其分割精度高、收斂速度快等特點(diǎn)，被廣泛應(yīng)用于各個(gè)領(lǐng)域的圖像識(shí)別與分析中，擁有較高的實(shí)用性。

參考文獻(xiàn)：

[1] 譚? 優(yōu)，王澤勇.圖像閾值分割算法實(shí)用技術(shù)研究與比較[J].微計(jì)算機(jī)信息，2007，23（24）：298-299，233.

[2] SHARMA S，SHAH D. A practical animal detection and collision avoidance system using computer vision technique[J].IEEE Access，2016（99）：1.

[3] HORNG M H. Multilevel thresholding selection based on the artificial bee colony algorithm for image segmentation[J].Expert Syst Appl，2011，38（11）：13785-13791.

[4] ABUTALEB AS. Automatic thresholding of gray-level pictures using two-dimensional entropy[J].Computer vision graphics and image processing，1989，47（1）：22-32.

[5] CHANG D，ZHAO Y，LIU L，et al.A dynamic niching clustering algorithm based on individual-connectedness and its application to color image segmentation[J].Pattern recognition，2016，60： 334-347.

[6] 劉桂紅，趙? 亮，孫勁光，等.一種改進(jìn)粒子群優(yōu)化算法的Otsu圖像閾值分割方法[J].計(jì)算機(jī)科學(xué)，2016，43（3）：309-312.

[7] KIRKPATRICK S. Optimization by simulated annealing： quantitative studies[J].J Stat Phys，1984，34（5-6）：975-986.

[8] SOURAV DE，BHATTACHARYYA S，PARAMARTHA D.Automatic magnetic resonance image segmentation by fuzzy intercluster hostility index based genetic algorithm：An application[J].Applied soft computing，2016，47：669-683.

[9] JUANG C F. A hybrid of genetic algorithm and particle swarm optimization for recurrent network design IEEE Trans[J].Syst Man Cybern B：Cybern，2004，34（2）：997-1006.

[10] 姚立平，潘中良.使用遺傳算法和KSW熵法相結(jié)合的CT圖像分割[J].電視技術(shù)，2018，42（11）：1-6.

[11] KITTLER J，ILLINGWORTH J. Minimum error thresholding[J]. Pattern recognition，1986，19（1）：41-47.

[12] OTSU N.A threshold selection method from gray-level histogram IEEE Trans[J].Syst Man Cybern，1979（9）：62-66.

[13] 張東生.基于閾值的圖像分割算法研究[D].黑龍江大慶：東北石油大學(xué)，2011.

[14] HOLLAND J H.Adaptation in natural and artificial systems：An introductory analysis with applications to biology，control，and artificial intelligence[M].East lansing：University michigan press，1975.

[15] AZAMATHULLA H M，WU F C，AB GHANI A，et al.Comparison between genetic algorithm and linear programming approach for real time operation[J].J Hydro-environ Res，2008，2（3）：172-181.