文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.190452
中文引用格式: 安霆. 基于遺傳算法的圖像分割處理技術(shù)研究[J].電子技術(shù)應(yīng)用,2019,45(10):92-95,99.
英文引用格式: An Ting. Research on image segmentation technology based on genetic algorithms[J]. Application of Electronic Technique,2019,45(10):92-95,99.
0 引言
圖像分割是圖像處理中的一個關(guān)鍵步驟,也是圖像分析和理解的基礎(chǔ),對圖像目標進行提取、測量都離不開圖像分割[1]。
目前,國內(nèi)外學(xué)者采用不同方法對圖像分割問題做了大量研究[2-3],這些方法各有優(yōu)勢,也存在一些問題。例如,基于圖論的圖像分割是一個研究熱點,但此法屬于NP-hard問題,也就是隨著圖中節(jié)點數(shù)的增大,問題的求解將變得復(fù)雜耗時。另外,目前還沒有能夠精確求出最優(yōu)解的算法,實際中一般采用近似的求解算法,這使得圖像分割中不可避免地存在一些誤差,從而影響圖像處理的效果。而遺傳算法能使這些誤差最小,從而使計算機視覺達到實用化的要求。而且,遺傳算法進行圖像處理時不像傳統(tǒng)算法那樣局限于鄰域特性的最佳,而是考慮整幅圖像的最佳,使圖像處理效果接近人眼的觀察效果[4-6]。
1 使用遺傳算法進行圖像分割的思路
圖像分割關(guān)鍵因素是獲得灰度圖片的分割閾值。因此,在用遺傳算法處理時,首先要用染色體表示閾值,目標是選出最佳閾值染色體。同時,應(yīng)確立最佳閾值的評價指標,也就是適應(yīng)度函數(shù)的建立。
圍繞這個主題,首先要建立染色體初始種群;而后,調(diào)用適應(yīng)度計算模塊,計算種群中各個染色體的適應(yīng)度值,接著按照適應(yīng)度值對種群中的染色體進行排序,并記錄該代種群的最佳閾值;在選擇步驟中,按照一定規(guī)則用上一代適應(yīng)度大的個體替代當前代適應(yīng)度小的個體組成新的種群;進入交叉處理環(huán)節(jié)后,按照設(shè)定的比例采用某種方式(例如隨機方式)選擇需要進行交叉的染色體對,在此過程中將產(chǎn)生不同于前輩的新的染色體個體;執(zhí)行變異步驟,在此步,將按照設(shè)定的概率,以一定的方式(例如隨機)找出發(fā)生變異的染色體基因位置,這個過程同樣會產(chǎn)生全新的個體;當變異步驟執(zhí)行完后,再次回到適應(yīng)度計算步驟循環(huán)進行,直到達到設(shè)定的遺傳代數(shù)[7-8];最后,依據(jù)算法給出的最佳閾值對圖片進行處理并顯示。算法的流程如圖1所示。
2 算法中主要模塊的設(shè)計
2.1 預(yù)處理和初始種群生成模塊
在預(yù)處理步驟中需要設(shè)計染色體表示方法。由于本文中灰度圖的閾值最高限為255,是一個數(shù)值,因此這里采用二進制表示法即可[9]。二進制的位數(shù)由式(1)確定。
其中,bj、aj分別表示染色體描述變量區(qū)間的最大和最小值,mj表示采用的二進制位數(shù)。本文中閾值的取值范圍為[0,255],代入式(1)可以求得mj=8,也即本文中用8位二進制表示染色體個體。為考慮整幅圖像最佳,這里判別染色體個體優(yōu)劣的適應(yīng)度函數(shù)采用式(2)來描述。
其中,p1、p2分別表示目標像素和背景像素的個數(shù),μ1、μ2分別表示目標像素和背景像素的平均灰度值,f表示適應(yīng)度值。
在算法的初始化操作中,采用隨機生成的方案隨機生成10個8位的染色體,構(gòu)成初始種群。交叉概率和變異概率分別設(shè)置為0.7和0.2。
2.2 適應(yīng)度計算模塊
在此操作過程中要設(shè)置代溝,這里設(shè)置為0.9,也就是將要淘汰10%的較差個體[10]。在第二代以后的群體中,將90%的更優(yōu)秀的個體保留進入后續(xù)處理程序;對群體中保留下來的個體計算其對應(yīng)的閾值;分別統(tǒng)計低于和高于閾值的灰度值的總個數(shù)和總和,繼而求出兩類灰度的平均值,根據(jù)式(2)計算出對應(yīng)于每條染色體的適應(yīng)度值;對于本代和上一代,根據(jù)適應(yīng)度值由小到大對染色體進行排序;統(tǒng)計每一代的最佳閾值和最佳適應(yīng)度值。閾值到灰度值的轉(zhuǎn)化見式(3)。
式中,h是灰度值,c是染色體對應(yīng)的十進制數(shù)值,l是二進制染色體長度。
本步驟的算法流程如圖2所示。
2.3 選擇模塊、交叉模塊和變異模塊
在選擇步驟中,首先計算前一代中適應(yīng)度值比當前群體適應(yīng)度值大的個體及其數(shù)量;而后,用上一代適應(yīng)度比當前代更大的個體隨機取代當前代的個體;最后,將當前代的各項數(shù)據(jù)保存。
在交叉操作中,首先依據(jù)交叉概率隨機地選出參與交叉的染色體對;然后,按照隨機選擇方案選出交叉點位置進行交叉,這里的交叉選用單點交叉即可[11]。
在變異操作中[12],首先依據(jù)設(shè)置的變異概率計算出在群體中所有的基因里參與變異的基因數(shù)量;使用隨機選取的方式確定變異基因所在的行列位置,然后對選擇的變異基因進行取反操作;保存處理過的種群;最后,用上一代中最優(yōu)的染色體補充到當前代群體中,以維持種群中染色體的數(shù)量。
上述幾部分操作的流程圖如圖3所示。
3 使用傳統(tǒng)遺傳算法進行圖像分割的實例
為驗證上述傳統(tǒng)遺傳算法的效果,應(yīng)用該法對某帶有底部噪聲的電力電子逆變系統(tǒng)圖片進行了處理。
原始圖像如圖4所示,處理后的圖像如圖5所示,最佳適應(yīng)度值進化曲線如圖6所示。
由處理結(jié)果可見,傳統(tǒng)遺傳算法在進化過程執(zhí)行到20代左右就已經(jīng)收斂到最佳值了,而且能將底部顏色和文字噪聲徹底清除,比較清晰地分割出目標圖像。但是,傳統(tǒng)算法處理的時間過長,系統(tǒng)顯示運算時間為7.416 s,這么長的處理時間是無法滿足需求的。
4 遺傳算法的改進及算法改進前后圖像實際處理效果的比較
4.1 算法的改進
遺傳算法若要收斂到全局最優(yōu)解必須具備拓展性和收斂性,而這些性能與交叉概率pc和變異概率pm密切相關(guān)[13-14]。增大pc的值,雖然加強了對新的解空間拓展能力,但增大了高適應(yīng)度的染色體結(jié)構(gòu)被破壞的可能性;反之則會減緩算法的搜索進程,甚至停滯。如果pm的值設(shè)定得過小,則可能造成早熟收斂;反之,則會使算法變成一個純粹的隨機過程。傳統(tǒng)遺傳算法的pc和pm值在算法的運行過程中是固定不變的。同時,從上面的算例可以看出,傳統(tǒng)的遺傳算法在圖像分割中用時較長,難以滿足現(xiàn)代社會對高效運行的需求。因此,為了提高運算效果和效率,需要對算法做出改進。
為了克服存在的問題,在前人工作的基礎(chǔ)上,運用一種自適應(yīng)方法對傳統(tǒng)算法進行了改進[15]。它根據(jù)進化的代數(shù)自適應(yīng)地調(diào)整種群的pc和pm。在進化初期取較大pc的值,利用其全局搜索能力加強對新的解空間的拓展,從而使種群進行全局進化;隨著進化的進行,高性能的解開始增多,這時應(yīng)逐步減少pc值以減少對這些解的破壞,同時,應(yīng)逐步提高pm的值來維持種群的多樣性,避免收斂到局部最優(yōu)解;在進化后期,搜索已經(jīng)接近最優(yōu)解鄰域,這時應(yīng)主要利用pm的局部搜索能力,使種群在局部重點進化,加速算法向最優(yōu)解收斂。
同時,pc和pm還應(yīng)與個體的適應(yīng)度值相關(guān)。對于同一代中的所有個體,適應(yīng)度高的和低的個體發(fā)生交叉和變異的可能性應(yīng)有差異。這能避免一些問題,例如,高性能的解不會和其他解一樣受到同樣的破壞,低性能的解不會和其他解一樣被保留,這樣就就確保了遺傳算法能如預(yù)期一樣在交叉的作用下接近最優(yōu)解鄰域,再在變異的作用下收斂到最優(yōu)解。為此,應(yīng)根據(jù)遺傳代數(shù)和適應(yīng)度值共同自適應(yīng)地調(diào)整pc、pm。對于適應(yīng)度高于種群平均水平的個體,應(yīng)設(shè)定較小的pc和pm,使它們在進化中能得到較好的保護;反之亦然,使低適應(yīng)度個體在進化中更可能被淘汰。
在用傳統(tǒng)算法進行圖片處理時發(fā)現(xiàn)pc和pm的設(shè)置大小對運行速度影響較大,尤其是pm。因此,若開始pm較小,會加快算法的運算速度。結(jié)合上述分析,這里給出改進后的自適應(yīng)遺傳算子(pc和pm)的計算公式如式(4)、式(5)所示。
另外,為了使進化過程更好地體現(xiàn)優(yōu)勝劣汰,并加快算法的收斂速度,在選擇模塊,根據(jù)進化代數(shù)分段選擇了替換染色體的方法。具體為,在前三分之一代,采用最優(yōu)個體隨機替換前代個體的方法;在中間進化段,采用前代最優(yōu)個體替換當代最差個體的方法;在后三分之一代,使用上一代一半最優(yōu)個體替代當前代中最差的一半的方法,加速算法尋優(yōu)過程。
4.2 圖像處理實例及算法改進前后處理效果的比較
為驗證改進后的遺傳算法的效果,仍然使用圖4所示原始照片,并應(yīng)用改進后的算法對圖片進行處理。處理后的圖像和圖5相似,目標圖像被完全剔除了噪聲,變得非常清晰。改進算法的最佳適應(yīng)度值進化曲線如圖7所示。
由處理結(jié)果可知,改進后的遺傳算法在進化過程執(zhí)行到8代左右就已經(jīng)收斂到最佳值了,收斂更快。相比較前面的分割效果而言,處理的時間較短,僅為0.751 s,運算效率提高了近10倍,改進效果顯著。
5 結(jié)束語
本文結(jié)合圖像分割詳細闡述了傳統(tǒng)遺傳算法的設(shè)計思想及其主要構(gòu)成模塊的工作機制。在此基礎(chǔ)上,結(jié)合前人的工作給出了遺傳算法的改進算法。傳統(tǒng)遺傳算法對噪聲圖片的分割處理表明遺傳算法可以將目標圖像從存在噪聲和底色的背景中分離出來,而改進的遺傳算法則擁有更好的效果和更高的效率。這說明遺傳算法可以成功應(yīng)用于圖像處理技術(shù)中,改進的遺傳算法可以有效地應(yīng)用于更為深入的圖像處理研究中。
參考文獻
[1] 周莉莉,姜楓.圖像分割方法綜述研究[J].計算機應(yīng)用研究,2017,34(7):1921-1928.
[2] 唐思源,楊敏,苗玥,等.區(qū)域生長和水平集相融合的肺部CT圖像分割[J].電子技術(shù)應(yīng)用,2018,44(5):135-139.
[3] 張瑞華.基于ECCC的細胞圖像分割算法[J].電子技術(shù)應(yīng)用,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] 游培寒,畢篤彥,馬時平.自適應(yīng)權(quán)值調(diào)整GS圖像分割算法[J].中國圖象圖形學(xué)報,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.
作者信息:
安 霆
(臨沂大學(xué) 自動化與電氣工程學(xué)院,山東 臨沂276000)