0 引言

    圖像分割是圖像處理中的一個關鍵步驟，也是圖像分析和理解的基礎，對圖像目標進行提取、測量都離不開圖像分割^[1]。

    目前，國內外學者采用不同方法對圖像分割問題做了大量研究^[2-3]，這些方法各有優勢，也存在一些問題。例如，基于圖論的圖像分割是一個研究熱點，但此法屬于NP-hard問題，也就是隨著圖中節點數的增大，問題的求解將變得復雜耗時。另外，目前還沒有能夠精確求出最優解的算法，實際中一般采用近似的求解算法，這使得圖像分割中不可避免地存在一些誤差，從而影響圖像處理的效果。而遺傳算法能使這些誤差最小，從而使計算機視覺達到實用化的要求。而且，遺傳算法進行圖像處理時不像傳統算法那樣局限于鄰域特性的最佳，而是考慮整幅圖像的最佳，使圖像處理效果接近人眼的觀察效果^[4-6]。

1 使用遺傳算法進行圖像分割的思路

    圖像分割關鍵因素是獲得灰度圖片的分割閾值。因此，在用遺傳算法處理時，首先要用染色體表示閾值，目標是選出最佳閾值染色體。同時，應確立最佳閾值的評價指標，也就是適應度函數的建立。

    圍繞這個主題，首先要建立染色體初始種群；而后，調用適應度計算模塊，計算種群中各個染色體的適應度值，接著按照適應度值對種群中的染色體進行排序，并記錄該代種群的最佳閾值；在選擇步驟中，按照一定規則用上一代適應度大的個體替代當前代適應度小的個體組成新的種群；進入交叉處理環節后，按照設定的比例采用某種方式（例如隨機方式）選擇需要進行交叉的染色體對，在此過程中將產生不同于前輩的新的染色體個體；執行變異步驟，在此步，將按照設定的概率，以一定的方式（例如隨機）找出發生變異的染色體基因位置，這個過程同樣會產生全新的個體；當變異步驟執行完后，再次回到適應度計算步驟循環進行，直到達到設定的遺傳代數^[7-8]；最后，依據算法給出的最佳閾值對圖片進行處理并顯示。算法的流程如圖1所示。

2 算法中主要模塊的設計

2.1 預處理和初始種群生成模塊

    在預處理步驟中需要設計染色體表示方法。由于本文中灰度圖的閾值最高限為255，是一個數值，因此這里采用二進制表示法即可^[9]。二進制的位數由式(1)確定。

其中，b_j、a_j分別表示染色體描述變量區間的最大和最小值，m_j表示采用的二進制位數。本文中閾值的取值范圍為[0，255]，代入式(1)可以求得m_j=8，也即本文中用8位二進制表示染色體個體。為考慮整幅圖像最佳，這里判別染色體個體優劣的適應度函數采用式(2)來描述。

其中，p₁、p₂分別表示目標像素和背景像素的個數，μ₁、μ₂分別表示目標像素和背景像素的平均灰度值，f表示適應度值。

    在算法的初始化操作中，采用隨機生成的方案隨機生成10個8位的染色體，構成初始種群。交叉概率和變異概率分別設置為0.7和0.2。

2.2 適應度計算模塊

    在此操作過程中要設置代溝，這里設置為0.9，也就是將要淘汰10%的較差個體^[10]。在第二代以后的群體中，將90%的更優秀的個體保留進入后續處理程序；對群體中保留下來的個體計算其對應的閾值；分別統計低于和高于閾值的灰度值的總個數和總和，繼而求出兩類灰度的平均值，根據式(2)計算出對應于每條染色體的適應度值；對于本代和上一代，根據適應度值由小到大對染色體進行排序；統計每一代的最佳閾值和最佳適應度值。閾值到灰度值的轉化見式(3)。

式中，h是灰度值，c是染色體對應的十進制數值，l是二進制染色體長度。

    本步驟的算法流程如圖2所示。

2.3 選擇模塊、交叉模塊和變異模塊

    在選擇步驟中，首先計算前一代中適應度值比當前群體適應度值大的個體及其數量；而后，用上一代適應度比當前代更大的個體隨機取代當前代的個體；最后，將當前代的各項數據保存。

    在交叉操作中，首先依據交叉概率隨機地選出參與交叉的染色體對；然后，按照隨機選擇方案選出交叉點位置進行交叉，這里的交叉選用單點交叉即可^[11]。

    在變異操作中^[12]，首先依據設置的變異概率計算出在群體中所有的基因里參與變異的基因數量；使用隨機選取的方式確定變異基因所在的行列位置，然后對選擇的變異基因進行取反操作；保存處理過的種群；最后，用上一代中最優的染色體補充到當前代群體中，以維持種群中染色體的數量。

    上述幾部分操作的流程圖如圖3所示。

3 使用傳統遺傳算法進行圖像分割的實例

    為驗證上述傳統遺傳算法的效果，應用該法對某帶有底部噪聲的電力電子逆變系統圖片進行了處理。

    原始圖像如圖4所示，處理后的圖像如圖5所示，最佳適應度值進化曲線如圖6所示。

    由處理結果可見，傳統遺傳算法在進化過程執行到20代左右就已經收斂到最佳值了，而且能將底部顏色和文字噪聲徹底清除，比較清晰地分割出目標圖像。但是，傳統算法處理的時間過長，系統顯示運算時間為7.416 s，這么長的處理時間是無法滿足需求的。

4 遺傳算法的改進及算法改進前后圖像實際處理效果的比較

4.1 算法的改進

    遺傳算法若要收斂到全局最優解必須具備拓展性和收斂性，而這些性能與交叉概率p_c和變異概率p_m密切相關^[13-14]。增大p_c的值，雖然加強了對新的解空間拓展能力，但增大了高適應度的染色體結構被破壞的可能性；反之則會減緩算法的搜索進程，甚至停滯。如果p_m的值設定得過小，則可能造成早熟收斂；反之，則會使算法變成一個純粹的隨機過程。傳統遺傳算法的p_c和p_m值在算法的運行過程中是固定不變的。同時，從上面的算例可以看出，傳統的遺傳算法在圖像分割中用時較長，難以滿足現代社會對高效運行的需求。因此，為了提高運算效果和效率，需要對算法做出改進。

    為了克服存在的問題，在前人工作的基礎上，運用一種自適應方法對傳統算法進行了改進^[15]。它根據進化的代數自適應地調整種群的p_c和p_m。在進化初期取較大p_c的值，利用其全局搜索能力加強對新的解空間的拓展，從而使種群進行全局進化；隨著進化的進行，高性能的解開始增多，這時應逐步減少pc值以減少對這些解的破壞，同時，應逐步提高p_m的值來維持種群的多樣性，避免收斂到局部最優解；在進化后期，搜索已經接近最優解鄰域，這時應主要利用p_m的局部搜索能力，使種群在局部重點進化，加速算法向最優解收斂。

    同時，p_c和p_m還應與個體的適應度值相關。對于同一代中的所有個體，適應度高的和低的個體發生交叉和變異的可能性應有差異。這能避免一些問題，例如，高性能的解不會和其他解一樣受到同樣的破壞，低性能的解不會和其他解一樣被保留，這樣就就確保了遺傳算法能如預期一樣在交叉的作用下接近最優解鄰域，再在變異的作用下收斂到最優解。為此，應根據遺傳代數和適應度值共同自適應地調整p_c、p_m。對于適應度高于種群平均水平的個體，應設定較小的p_c和p_m，使它們在進化中能得到較好的保護；反之亦然，使低適應度個體在進化中更可能被淘汰。

    在用傳統算法進行圖片處理時發現p_c和p_m的設置大小對運行速度影響較大，尤其是p_m。因此，若開始p_m較小，會加快算法的運算速度。結合上述分析，這里給出改進后的自適應遺傳算子(p_c和p_m)的計算公式如式(4)、式(5)所示。

    另外，為了使進化過程更好地體現優勝劣汰，并加快算法的收斂速度，在選擇模塊，根據進化代數分段選擇了替換染色體的方法。具體為，在前三分之一代，采用最優個體隨機替換前代個體的方法；在中間進化段，采用前代最優個體替換當代最差個體的方法；在后三分之一代，使用上一代一半最優個體替代當前代中最差的一半的方法，加速算法尋優過程。

4.2 圖像處理實例及算法改進前后處理效果的比較

    為驗證改進后的遺傳算法的效果，仍然使用圖4所示原始照片，并應用改進后的算法對圖片進行處理。處理后的圖像和圖5相似，目標圖像被完全剔除了噪聲，變得非常清晰。改進算法的最佳適應度值進化曲線如圖7所示。

    由處理結果可知，改進后的遺傳算法在進化過程執行到8代左右就已經收斂到最佳值了，收斂更快。相比較前面的分割效果而言，處理的時間較短，僅為0.751 s，運算效率提高了近10倍，改進效果顯著。

5 結束語

    本文結合圖像分割詳細闡述了傳統遺傳算法的設計思想及其主要構成模塊的工作機制。在此基礎上，結合前人的工作給出了遺傳算法的改進算法。傳統遺傳算法對噪聲圖片的分割處理表明遺傳算法可以將目標圖像從存在噪聲和底色的背景中分離出來，而改進的遺傳算法則擁有更好的效果和更高的效率。這說明遺傳算法可以成功應用于圖像處理技術中，改進的遺傳算法可以有效地應用于更為深入的圖像處理研究中。

參考文獻

[1] 周莉莉，姜楓.圖像分割方法綜述研究[J].計算機應用研究,2017，34(7)：1921-1928.

[2] 唐思源，楊敏，苗玥，等.區域生長和水平集相融合的肺部CT圖像分割[J].電子技術應用，2018，44(5)：135-139.

[3] 張瑞華.基于ECCC的細胞圖像分割算法[J].電子技術應用，2016，42(7)：126-129.

[4] LI Q，URAL S，ANDERSON J，et al.A fuzzy Mean-Shift approach to lidar waveform decomposition[J].IEEE Transactions on Geoscience & Remote Sensing，2016，54(12)：7112-7121.

[5] DU Z，ZHANG G，WANG C.Research on algorithm of small target detection and preprocessing in infrared image[J].Computer & Digital Engineering，2003(4)：31-34.

[6] HU X.Image segmentation based on graph theory in multicolor space for maize leaf disease[J].Transactions of the Chinese Society for Agricultural Machinery，2013，44(2)：177-181.

[7] YANG J A，TAO L，ZHUANG Z，et al.Research and realization of image separation method based on independent component analysis and genetic algorithm[J].Proceedings of SPIE，2002，4875(2)：575-582.

[8] GOLDBERG D E.Genetic algorithms in search, optimization and machine learning[M].Addison-Wesley Professional，1989.

[9] TIAN F，YAO A M，SUN X P，et al.Dual population genetic algorithm based on individual similarity[J].Computer Engineering and Design，2011，32(5)：1989-1993.

[10] ANDERSON-COOK C M.Practical genetic algorithms[J].Publications of the American Statistical Association，2004，100(471)：1099-1099.

[11] ZENG X Y，CHEN Y W，NAKAO Z，et al.Signal separation by independent component analysis based on a genetic algorithm[C].International Conference on Signal Processing.IEEE，2000.

[12] SRINIVAS M，PATNAIK L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems Man & Cybernetics，2002，24(4)：656-667.

[13] 游培寒，畢篤彥，馬時平.自適應權值調整GS圖像分割算法[J].中國圖象圖形學報，2018，11(7)：959-964.

[14] WANG B，YAN P，ZHOU Q，et al.State recognition method for machining process of a large spot welder based on improved genetic algorithm and hidden Markov model[J].Proceedings of the Institution of Mechanical Engineers，2017，231(11)：2135-2146.

[15] CANTU-PAZ E.On random numbers and the performance of genetic algorithms[J].Computer Science Preprint Archive，2002(10)：203-210.

作者信息:

安  霆

(臨沂大學 自動化與電氣工程學院，山東 臨沂276000)