改進遺傳算法結(jié)合Ｏｔｓｕ算法的大田作物分割

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

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

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

中圖分類號：TP751? ? ? ? ?文獻標識碼：A

文章編號：0439-8114（2019）15-0119-05

DOI：10.14088/j.cnki.issn0439-8114.2019.15.028? ? ? ? ? ?開放科學（資源服務）標識碼（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é)合圖像的強度、圖像的紋理特征、顏色特征以及圖像的對比度等內(nèi)在表現(xiàn)[1，2]，將圖像分割成非重疊的感興趣對象的技術(shù)。圖像分割在圖像識別、處理以及視頻解析的過程中扮演著十分重要的角色，其分割效果對于檢測目標、識別目標物以及跟蹤目標的后續(xù)操作影響深遠。圖像分割的主要目的是根據(jù)一定的準則確定一個有效閾值（用于兩級閾值）或多個閾值（用于多級閾值）[3]。

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

1? 大津算法

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

假設(shè)f（x，y）為圖像M×N某一點的灰度值，其灰度級為L，則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）

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

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

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

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

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

3.1? 改進的遺傳算法

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

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

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)重要的，它們對于算法的行為或者性能有直接的影響，而且還能凸顯出算法的收斂性。傳統(tǒng)的遺傳算法通常將兩者設(shè)置為固定值（范圍0.4～0.9），其缺點在于最優(yōu)的圖像閾值與真實值之間存在一定的差異，從而無法進行最優(yōu)的圖像分割。

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

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

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

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

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

3.2? 改進的Otsu算法

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

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

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

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

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

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

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

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

G（t）=■=■（13）

可知，G（t）值為最大時，其所對應的灰度級便是最佳閾值Th。如下：

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

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

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

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

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

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

3.3.4? 選擇? 針對輪盤選擇法進行改進。通過保留上一代中最大值來保證種群的多樣化。

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

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

3.3.7? 終止條件? 當滿足種群迭代的最大值且種群的98%個體都指向同一個值時，算法停止運行，此時具有最高適應度值的個體即為最佳閾值。

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

4? 試驗分析

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

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

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

5? 小結(jié)

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

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

參考文獻：

[1] 譚? 優(yōu)，王澤勇.圖像閾值分割算法實用技術(shù)研究與比較[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] 劉桂紅，趙? 亮，孫勁光，等.一種改進粒子群優(yōu)化算法的Otsu圖像閾值分割方法[J].計算機科學，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].黑龍江大慶：東北石油大學，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.