1、 題 目：遺傳算法在圖像處理中的應(yīng)用研究課 程: 計(jì)算智能 姓 名： 學(xué) 號： 專 業(yè)：模式識別與智能系統(tǒng)遺傳算法在圖像處理中的應(yīng)用摘要 遺傳算法是一種基于生物自然選擇與遺傳機(jī)理的隨機(jī)搜索與優(yōu)化方法。近年來，由于遺傳算法求解復(fù)雜優(yōu)化問題的巨大潛力，廣泛應(yīng)用在生物信息學(xué)、系統(tǒng)發(fā)生學(xué)、計(jì)算科學(xué)、工程學(xué)、經(jīng)濟(jì)學(xué)、化學(xué)、制造、數(shù)學(xué)、物理、藥物測量學(xué)和其他領(lǐng)域之中，這種算法受到了國內(nèi)外學(xué)者的廣泛關(guān)注，尤其是在計(jì)算機(jī)科學(xué)人工智能領(lǐng)域中。本文介紹了遺傳算法基本理論，描述了它的主要特點(diǎn)和基本性質(zhì)；重點(diǎn)綜述遺傳算法在圖像處理中的主要應(yīng)用，特別是在圖像分割、圖像壓縮、圖像增強(qiáng)等方面的作用；深入研究目前遺傳算法在圖

2、像處理領(lǐng)域中存在的問題，并結(jié)合自己的研究方向，對這些問題提出了一些深刻的見解，展望了今后遺傳算法在圖像處理應(yīng)用的發(fā)展方向。關(guān)鍵詞 ：遺傳算法，數(shù)字圖像處理1.背景介紹遺傳算法(Genetic Algorithm, GA)是一種自適應(yīng)啟發(fā)式群體型概率性迭代式的全局收斂搜索算法,其基本思想來源于生物進(jìn)化論和群體遺傳學(xué),體現(xiàn)了適者生存、優(yōu)勝劣汰的進(jìn)化原則。使用遺傳算法求解科學(xué)研究工作和工程技術(shù)中各種組合搜索和優(yōu)化計(jì)算問題這一基本思想早在20世紀(jì)60年代初期就由美國Michigan大學(xué)的Holland教授提出,其數(shù)學(xué)框架也于20世紀(jì)60年代中期形成。由于GA的整體搜索策略和優(yōu)化計(jì)算

3、不依賴于梯度信息,所以它的應(yīng)用范圍非常廣泛,尤其適合于處理傳統(tǒng)方法難以解決的高度復(fù)雜的非線性問題。它在自適應(yīng)控制、組合優(yōu)化、模式識別、機(jī)器學(xué)習(xí)、規(guī)劃策略、信息處理和人工生命等領(lǐng)域的應(yīng)用中越來越展示出優(yōu)越性。 圖像處理(image processing)，用計(jì)算機(jī)對圖像進(jìn)行分析，以達(dá)到所需結(jié)果的技術(shù)。又稱影像處理。圖像處理一般指數(shù)字圖像處理。數(shù)字圖像是指用數(shù)字?jǐn)z像機(jī)、掃描儀等設(shè)備經(jīng)過采樣和數(shù)字化得到的一個大的二維數(shù)組，該數(shù)組的元素稱為像素，其值為一整數(shù)，稱為灰度值。圖像處理技術(shù)的主要內(nèi)容包括圖像壓縮，增強(qiáng)和復(fù)原，匹配、描述和識別3個部分。 常見的處理有圖像數(shù)字化、圖像編碼、圖像增強(qiáng)、圖像復(fù)原、圖

4、像分割和圖像分析等。圖像處理一般指數(shù)字圖像處理。圖像處理是計(jì)算機(jī)視覺中德一個重要研究領(lǐng)域，然而，在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會存在一些誤差，從而影響圖像的效果。于是，研究者就開始探索怎么樣才能使這些誤差最小從而使計(jì)算機(jī)視覺達(dá)到實(shí)用化的重要要求，最終，遺傳算法憑借其在這些圖像處理中的優(yōu)化計(jì)算方面獨(dú)特的優(yōu)勢成為各種算法的佼佼者，得到了廣泛的應(yīng)用。2.遺傳算法的原理和基本步驟遺傳算法是一個不斷迭代過程的搜索算法，它的基本處理流程如下圖所示。由上圖可知，遺傳算法模擬了自然選擇和遺傳進(jìn)化中發(fā)生的繁殖、交配和突變現(xiàn)象，從任意一個初始種群出發(fā)，通過隨機(jī)選擇、交叉和變異操作，產(chǎn)生新

5、的更適應(yīng)環(huán)境的個體，使群體進(jìn)化到搜索空間中越來越好的區(qū)域。這樣一代一代不斷繁殖、進(jìn)化，最后收斂到一群最適應(yīng)環(huán)境的個體上，求得問題的最優(yōu)解。遺傳算法對于復(fù)雜的優(yōu)化問題無需建模和復(fù)雜運(yùn)算，只要利用遺傳算法的三種算子就能得到最優(yōu)解。GA結(jié)構(gòu)較為簡單，算法也不復(fù)雜，但是又具有良好的選擇效果，具有自適應(yīng)性、子組織性和自學(xué)習(xí)性等特點(diǎn)，具有許多其它算法沒有的優(yōu)點(diǎn)，主要有：（1）GA 是對參數(shù)編碼進(jìn)行操作, 而非對參數(shù)本身, 減少約束條件的限制, 如連續(xù)性、可導(dǎo)性、單峰性等。（2）GA 是多點(diǎn)搜索, 減少了陷于局部優(yōu)解的風(fēng)險(xiǎn)。（3）GA 僅用適應(yīng)度函數(shù)來指導(dǎo)搜索, 不需要其他推導(dǎo)和附加信息, 對問題依賴性小。

6、（4） GA 的尋優(yōu)規(guī)則是概率性的而非確定性的。研究者們在應(yīng)用GA 過程中也不斷研究改進(jìn)GA的性能，使GA更能滿足時代的需要，比如在選擇策略中提出了精英選擇、穩(wěn)態(tài)選擇和競爭選擇等新的機(jī)制; 在變異環(huán)節(jié)提出了兩點(diǎn)、多點(diǎn)和一致變異作為傳統(tǒng)一點(diǎn)變異的改進(jìn)和補(bǔ)充; 在編碼環(huán)節(jié)中應(yīng)用格雷碼和動態(tài)編碼等克服傳統(tǒng)二進(jìn)制編碼和定點(diǎn)十進(jìn)制整數(shù)編碼所就帶來的問題; 此外, 還提出自適應(yīng)技術(shù)動態(tài)改變GA 控制參數(shù), 克服采取傳統(tǒng)的靜態(tài)控制參數(shù)策略引起的多樣性和收斂性不均衡問題, 以及用梯度方法、單純型法或模擬退火方法精細(xì)調(diào)整的混合GA, 以提高算法的收斂速度; 用均勻分布的初始群體代替隨機(jī)產(chǎn)生的初始種群; 研究了分

7、布式GA、遷徙GA 和并行GA等, 進(jìn)一步推動了GA 的發(fā)展。3.遺傳算法在圖像處理中的應(yīng)用3.1基于遺傳算法的圖像增強(qiáng)圖像增強(qiáng)技術(shù)是將不清晰的圖像經(jīng)過優(yōu)化處理變成一張比之前更加清楚，或者變成一張使得特點(diǎn)更加鮮明的照片，以便于對圖像再進(jìn)行后期的加工。目前圖像增強(qiáng)方法主要包括將圖像進(jìn)行某種變換的頻域法和對直接對原始圖像進(jìn)行處理的空域法兩種。而基于遺傳算法的圖像增強(qiáng)技術(shù)的實(shí)現(xiàn)則是利用遺傳的選擇方法找到一個最優(yōu)或者局部最優(yōu)的方法。具體的操作方法是，首先將每一個目標(biāo)值設(shè)置一個基位，用實(shí)數(shù)進(jìn)行編碼，這樣問題就轉(zhuǎn)化成求解這個目標(biāo)基位組合的題目。然后，對適應(yīng)度進(jìn)行設(shè)計(jì)，適應(yīng)度設(shè)計(jì)為個體進(jìn)化提供動力，在設(shè)置適

8、應(yīng)度的時候既要考慮圖像的整體和局部的質(zhì)量問題，也要將結(jié)構(gòu)和細(xì)節(jié)考慮進(jìn)去。再后，對遺傳算子進(jìn)行設(shè)計(jì)，先根據(jù)前面設(shè)置的適應(yīng)度值將個體從大到小進(jìn)行排列，從中選擇優(yōu)秀的個體進(jìn)入下一個程序當(dāng)中；為了防止遺傳算法在計(jì)算的過程中過早收斂，對種群的多樣性進(jìn)行保護(hù)，在計(jì)算過程中采用交叉操作的方法產(chǎn)生新的個體；對進(jìn)化方向進(jìn)行微調(diào)，采用變異操作的方法，對一個被選中的變異操作來說，就是采用“1”“0”和“1”“0”的方式進(jìn)行變異。最后，設(shè)置算法的結(jié)束條件，一般算法的結(jié)束條件就是迭代次數(shù)達(dá)到了最大進(jìn)化代數(shù)或者最大適應(yīng)度的值變化不明顯。例如，對于一幅數(shù)字圖像f(.),f(x,y)是圖像在x行y列的像素值。f(x,y)為增

9、強(qiáng)后的圖像在對應(yīng)點(diǎn)的像素值。則有：其中g(shù)(.)是一個對比度擴(kuò)展函數(shù)。m(x,y)為x行y列處像素值占在它的某個鄰域內(nèi)的局部均值。K>0是一個控制參數(shù)，其大小直接影響到圖像的處理質(zhì)量。因此，數(shù)字圖像的增強(qiáng)過程可以轉(zhuǎn)化為尋找求最優(yōu)參數(shù)k的過程。進(jìn)而，可用遺傳算法按照上述過程進(jìn)行尋優(yōu)。3.2基于遺傳算法的圖像恢復(fù)圖像恢復(fù)就是把一個退化(或劣化)圖像盡量恢復(fù)到它的原始面目, 是數(shù)字圖像處理中的一個重要分支。目前已提出許多有效的圖像恢復(fù)方法, 如逆濾波法、維納濾波法、奇異值分解偽逆法、最大熵恢復(fù)法等 。由于引起圖像退化的原因未知或不能用函數(shù)表達(dá), 使得上述方法面臨較多的約束問題或是計(jì)算量過大問題,

10、 由于難以確定退化函數(shù)h, 限制了其實(shí)際應(yīng)用的效果。GA 用于灰度圖像的恢復(fù), 一般將染色體編碼成以各像素的灰度值為元素的2維矩陣, 即一個染色體就代表一幅圖像, 每個基因?qū)?yīng)一個像素, 采用自然數(shù)編碼。每個個體的適應(yīng)度函數(shù)中f i 為個體i代表的推測恢復(fù)圖像, g 為觀測到的退化圖像, h 為退化過程, 函數(shù)值越大表示個體越好。在交叉操作時一般采用窗口交叉, 即在父代染色體矩陣中選擇相同大小的窗口, 進(jìn)行交換。變異操作采用臨近小范圍內(nèi)的平均值替換需要變異的某一基因值。此外，GA也用于彩色圖像的恢復(fù)，并且取得了很好的效果?；贕A 的圖像恢復(fù)方式, 突破了原有的理論,而且其開放的結(jié)構(gòu)易于與其他

11、方式融合, 如與模糊邏輯相結(jié)合的模糊GA 等。利用GA 恢復(fù)圖像不僅較好的克服了噪聲的影響, 而且使圖像更平滑, 邊緣沒有條紋效應(yīng), 視覺效果好。強(qiáng)大的全局搜索能力是遺傳算法圖像恢復(fù)方法行之有效的主要原因。3.3 基于遺傳算法的圖像分割圖像分割是自動目標(biāo)識別的關(guān)鍵和首要步驟，其目的是將目標(biāo)和背景分離，為計(jì)算機(jī)視覺的后續(xù)處理提供依據(jù)。目前圖像分割的方法很多，常用的包括閾值法、邊緣檢測法和區(qū)域跟蹤法。其中域值法是圖像分割的最常用方法。當(dāng)前常用的域值分割方法如最小誤差閾值法、最大類別方差法（Otsu 法）以及最佳直方圖熵法。下面我們以Kapur 等人提出的最佳熵法（KSW 熵法）為例討論遺傳算法在圖

12、像分割中的應(yīng)用。KSW熵法是一種不需要先驗(yàn)知識，而且對于非理想雙峰直方圖的圖像也可以較好分割的方法。其缺點(diǎn)是在確定閾值時，尤其是確定多閾值時，計(jì)算量很大。將信息論中Shannon 熵概念用于圖像分割時，測量圖像灰度直方圖的熵，由此找出最佳閾值，其出發(fā)點(diǎn)是使圖像中目標(biāo)與背景的信息量最大。根據(jù)shannon 熵的概念，對于灰度范圍0,1,255的直方圖，其熵測量為其中pi為第i個灰度出現(xiàn)的概率。設(shè)閾值t將圖像劃分為目標(biāo)與背景兩類，則令 由閾值t 分為A,B 兩類后，兩類的概率分布分別為p0/pt, pt, ,pl/pl; pt+1/(1-pt),pt-2/(1-pt), , pt-1/(1-pt)

13、, 與每個分布有關(guān)的熵分別為HA(t)和HB(t)圖像的總熵H(t)為HA(t)和HB(t)之和，即：當(dāng)該函數(shù)取最大值時即為圖像的最佳分割，因此將其作為遺傳算法中的適應(yīng)度函數(shù)。(1) 編碼。我們選取有255 個灰度級的灰度圖，由于圖像灰度值在0-255 之間，故將各個染色體編碼為8 位二進(jìn)制編碼，代表某個分割閾值。初始代個體的值為隨即產(chǎn)生，其對應(yīng)的適應(yīng)度值也各有高低。(2) 群體體模型。若個體數(shù)過多，則每一代適應(yīng)度值的計(jì)算機(jī)過大，因此個體數(shù)應(yīng)設(shè)置合理。我們在此將個體數(shù)設(shè)為10, 最大繁殖代數(shù)為50.(3) 解碼。對二進(jìn)制染色體數(shù)組解密為0-255 之間的值，以求其適應(yīng)度值。(4) 適應(yīng)度函數(shù)。

14、采用H（t）式作為適應(yīng)度函數(shù)。(5) 算法的基本操作：選擇：遺傳算法的收斂定義指出保留最優(yōu)個體（精英策略的遺傳算法全局收斂。因此本文在進(jìn)行選擇操作時，先進(jìn)行輪盤賭選擇法（蒙特卡羅法），再采用精英策略。交叉：交叉互換的目的是產(chǎn)生不同于父體的子體。交叉率越大，交叉操作的可能性也越大；如果交叉率太低，收斂速度可能降低。單閾值分割由于只有一個參數(shù)，所以采用單點(diǎn)交叉，在此設(shè)交叉率為0.6。變異：變異是子代基因按小概率擾動產(chǎn)生的變化。本文選取變異概率為0.1。終止準(zhǔn)則：規(guī)定算法執(zhí)行到最大代數(shù)（50 代）或經(jīng)過某些代進(jìn)化，群體的最高適應(yīng)度不再發(fā)生變化（穩(wěn)定條件），算法停止，具有最高適應(yīng)度值的個體即為分割閾值

15、。3.4 基于遺傳算法的圖像壓縮圖像壓縮技術(shù)最主要的原理就是將擁有自相似性的對象用這一組簡單的代數(shù)關(guān)系式進(jìn)行表達(dá)的過程。將互相不重疊的小塊定義為值域塊，然后進(jìn)行編碼，并使經(jīng)過映射后的定義域塊與值域塊的距離在某種度量值下最小，在分解和處理過程中，由于值域塊的數(shù)量過于龐大，壓縮搜索過程任務(wù)繁重，遺傳算法的強(qiáng)大全局搜索能力就能很好的派上用場，發(fā)揮良好的效果。有研究者用區(qū)域塊左上角的坐標(biāo)x, y 和區(qū)域塊的旋轉(zhuǎn)變換z (共有8 種旋轉(zhuǎn))進(jìn)行染色體編碼，在搜索最優(yōu)定義域塊時使用的兩個參數(shù)是定義域塊相對于值域塊位移的水平和垂直分量( xi, yi ), 用10位二進(jìn)制串對其進(jìn)行編碼, 每個參數(shù)用5位編碼;

16、有一種帶分類的編碼法, 這樣的編碼具有特征集中, 搜索速度快的特點(diǎn),能夠改進(jìn)遺傳算法的速度, 克服壓縮中分類匹配算法的局部最優(yōu)和隨機(jī)搜索問題。3.5 基于遺傳算法的圖像匹配圖像匹配是圖像處理中一個重要的課題,在計(jì)算機(jī)視覺、運(yùn)動目標(biāo)跟蹤與識別、序列圖像壓縮中運(yùn)動補(bǔ)償、醫(yī)學(xué)圖像處理等領(lǐng)域有廣闊的應(yīng)用前景.在對圖像的理解中,匹配技術(shù)起著重要的作用,是實(shí)現(xiàn)圖像理解的基礎(chǔ)。下面介紹一種基于遺傳算法的圖像校準(zhǔn)函數(shù)辨識方法。假設(shè)灰度圖像A 上一點(diǎn)（x，y）的灰度為A（x，y）。定義下面的非線性變換：經(jīng)過以上變換，得到圖像A?，F(xiàn)在要考慮的是確定系數(shù)a0，a1，a2，a3，和b0，b1，b2，b3，使圖像A與歪

17、斜圖像B 之間的誤差最小，則我們根據(jù)獲得的變換圖像推斷歪斜圖像B 中發(fā)生了變化的部分。將遺傳算法應(yīng)用于變換函數(shù)的辨識， 考慮對系數(shù)(a0,a1,a2,a3,b0,b1,b2,b3)進(jìn)行個體染色體編碼，個體的適應(yīng)度可根據(jù)其系數(shù)計(jì)算變換后圖像A與歪斜圖像B 之間的誤差進(jìn)行評價(jià)，誤差值可按下式計(jì)算。個體的誤差值越小，則其適應(yīng)度越大。由于未考慮歪斜圖像灰度的變化（除局部的變化外），在對于歪斜之外的變化很大的場合，用這種方法進(jìn)行圖像校準(zhǔn)是不合適的。4.遺傳算法在圖像處理中的缺陷及改進(jìn)（1）遺傳算法用于圖像增強(qiáng)技術(shù)能夠很好的達(dá)到預(yù)期效果，但是在時間上進(jìn)行考量，目前的方法在尋找最優(yōu)解方面速度好比較慢，可以考慮在運(yùn)算過程中使用并行遺傳算法，是未來遺傳算法在這個領(lǐng)域的發(fā)展方向。（2）在圖像恢復(fù)技術(shù)中，遺傳算法的計(jì)算量相對較大，而且解不止一個，未來要在編碼技術(shù)上多投入精力，解決遺傳算法早熟的問題。（3）遺傳算法在圖像重建過程中還沒能形成一個成