基于遺傳算法的最大類間方差法圖像分割畢業(yè)設(shè)計(jì)論文

哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文哈爾濱工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）-PAGEII--PAGEI-畢業(yè)設(shè)計(jì)論文基于遺傳算法的最大類間方差法圖像分割摘要本文研究的是遺傳算法的基本原理和算法的應(yīng)用，分析了遺傳算子的特性，主要講述了基本遺傳算法的應(yīng)用步驟，并將其應(yīng)用于圖像處理中的圖像分割技術(shù)中，用MATLAB軟件編程實(shí)現(xiàn)遺傳算法得出分割閾值數(shù)據(jù)，利用MATLAB軟件強(qiáng)大的仿真功能，編程進(jìn)行圖像分割仿真實(shí)驗(yàn)，將得出的幾組圖像進(jìn)行對(duì)比。首先分析了最大類間方差閾值圖像分割算法的基本原理，然后結(jié)合遺傳算法及其特點(diǎn)提出了一種自動(dòng)閾值選取的圖像分割算法，在本算法中對(duì)傳統(tǒng)最大類間方差圖像分割的算法及遺傳算法進(jìn)行了改進(jìn)，提高了傳統(tǒng)算法的速度，改善了遺傳算法的收斂速度與最優(yōu)解的協(xié)調(diào)關(guān)系，最后從速度及性能上進(jìn)行了分析比較，并對(duì)實(shí)際圖像分割做了實(shí)驗(yàn)。結(jié)果表明，本遺傳算法的圖像分割方法在圖像分割過程中具有速度快，效果好的特點(diǎn)。關(guān)鍵詞圖像分割；遺傳算法；閾值；方差；適應(yīng)度函數(shù)AbstractThisthesismainlystudiesthebasicprincipleofthegeneticalgorithmsandtheapplicationsofthealgorithms.Thecharacteristicofthegeneticoperatorhasanalyzed,mainlydiscussedtheapplicationstepsofthesimplegeneticalgorithms.TheGAsareappliedtotheimagesegmentationtechnique,WiththestrongfunctionofMATLAB,IprogrammedtheGAemulationandgavethefinaldata,then,comparedthepicturesshowedbytheemulationexperimentoftheimagesegmentation.Firstly,developedanewautomaticthresholdimagesegmentationalgorithmaftercomprehensivelystudyingthemethodwithmaximumvariancebetweentwoclassandGAprinciple.Then,withthechangeoftheGA,thealgorithmdevelopsthecomputespeedandresultstability.Finally,theresultsoftheexperimentsbythealgorithmareshowingtocomparewiththetraditionmethod,itisconcludethatthealgorithmisnotonlyhigherqualitybutalsoquickercomputespeed.Keywordsimagesegmentationthegeneticalgorithmthresholdvariancefitnessfunction哈爾濱工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）-PAGE10--PAGE54-目錄摘要 IAbstract II第1章緒論 31.1課題背景 31.2遺傳算法的生物學(xué)基礎(chǔ) 41.2.1遺傳與變異 41.2.2進(jìn)化 51.2.3遺傳與進(jìn)化的系統(tǒng)觀 51.3遺傳算法的發(fā)展史 6第2章基于灰度的圖像分割 82.1圖像分割概述 82.1.1圖像分割的應(yīng)用領(lǐng)域 82.1.2圖像分割的通用定義 92.2灰度門限法 102.2.1灰度門限法簡(jiǎn)介 102.2.2灰度門限的確定 112.2.3最大類間方差閾值分割法 122.3本章小結(jié) 15第3章遺傳算法 163.1遺傳算法概述 163.2遺傳算法的特點(diǎn) 173.3遺傳算法的應(yīng)用 173.4基本遺傳算法 193.4.1基本遺傳算法的構(gòu)成要素 193.4.2基本遺傳算法的形式化定義 203.4.3基本遺傳算法的實(shí)現(xiàn) 203.4.4基本遺傳算法的應(yīng)用步驟 233.5本章小結(jié) 26第4章軟件實(shí)現(xiàn)與分析 274.1用MATLAB實(shí)現(xiàn)遺傳算法 274.2最大類間方差圖像分割中的遺傳算法 304.3圖像分割遺傳算法的性能分析 324.4實(shí)驗(yàn)結(jié)果分析 334.5本章小結(jié) 35結(jié)論 36致謝 37參考文獻(xiàn) 38附錄1 39附錄2 45附錄3 51緒論課題背景圖像分割是計(jì)算機(jī)視覺及模式識(shí)別中一個(gè)非常困難的研究?jī)?nèi)容，是視覺圖像理解，如目標(biāo)檢測(cè)、特征提取、目標(biāo)識(shí)別操作的基礎(chǔ)，圖像分割的好壞直接影響到圖像理解[6]。最簡(jiǎn)單的圖像分割方法是采用對(duì)比度、邊緣、灰度檢測(cè)的方法，這些方法利用了前景與背景的灰度變化來進(jìn)行分割，其前提是假設(shè)目標(biāo)與背景相比有明顯的灰度對(duì)比或顏色變化，但在實(shí)際處理中，由于受到光照不均等因素的影響，其對(duì)比特征并不明顯，因此上述算法存在許多局限性。采用灰度直方圖統(tǒng)計(jì)的分割方法利用了圖像整體的灰度特征，使得圖像分割性能得到了很大程度的改進(jìn)，如雙峰法及P-tile法，特別是1980年由日本的大津展之提出的最大類間方差動(dòng)態(tài)閾值圖像分割方法，使圖像分割的效果得到了明顯的提高[13]。它利用圖像的灰度值，通過計(jì)算目標(biāo)與背景兩大類間的最大方差而動(dòng)態(tài)得到圖像分割的閾值，然后據(jù)此進(jìn)行圖像分割。但這種算法對(duì)于每一灰度值都要反復(fù)計(jì)算其對(duì)應(yīng)方差，計(jì)算量非常大，例如對(duì)于灰度為256級(jí)的圖像而言，設(shè)每計(jì)算一個(gè)方差的時(shí)間為T，則總的方差運(yùn)算時(shí)間為256T。為了消除光照不均的影響，對(duì)圖像采用局部閾值分割方法，其運(yùn)算時(shí)間將會(huì)更多，因此，按傳統(tǒng)的方法計(jì)算最大類間方差已經(jīng)限制了這種算法的發(fā)展。1990年Flavagetto提出將圖像單元分成一個(gè)個(gè)子區(qū)，然后進(jìn)行代運(yùn)算計(jì)算區(qū)間的可信度，最后保留可信度高區(qū)域作為最后的分割結(jié)果，這種方法比前一種方法性能要好。一般而言，并不能求出最佳的分割結(jié)果。為了加快求最優(yōu)解的速度，對(duì)上述過程采用適應(yīng)于并行計(jì)算的遺傳算法，但傳統(tǒng)的GA算法會(huì)因收斂性與最優(yōu)解之間的矛盾使得求解過程很難達(dá)到速度與最優(yōu)解穩(wěn)定兩全，在決定收斂速度時(shí)，只是采用一個(gè)不變的概率進(jìn)行遺傳運(yùn)算，其求解過程并不穩(wěn)定，特別是對(duì)于直方圖異常復(fù)雜的情況，圖像處理的效果并不理想。本文結(jié)合遺傳算法的特點(diǎn)對(duì)其進(jìn)行改進(jìn)，提出了一種新的求解類間方差最大值的遺傳算法，改進(jìn)后的遺傳算法能非線性快速穩(wěn)定地查找到最優(yōu)的分割閾值，從而有效分割了背景與目標(biāo)，使圖像的分割達(dá)到最佳效果。遺傳算法的生物學(xué)基礎(chǔ)生物在自然界中的生存繁衍，顯示出了其對(duì)自然環(huán)境的優(yōu)異自適應(yīng)能力。受其啟發(fā)，人們致力于對(duì)生物各種生存特性的機(jī)理研究和行為模擬，為人工自適應(yīng)系統(tǒng)的設(shè)計(jì)和開發(fā)提供了廣闊的前景。遺傳算法(GeneticAlgorithms,GAs)就是這種生物行為的計(jì)算機(jī)模擬中令人注目的重要成果?；趯?duì)生物遺傳和進(jìn)化過程的計(jì)算機(jī)模擬，遺傳算法使得各種人工系統(tǒng)具有優(yōu)良的自適應(yīng)能力和優(yōu)化能力[9]。遺傳算法所借鑒的生物學(xué)基礎(chǔ)就是生物的遺傳和進(jìn)化。遺傳與變異世間的生物從其親代繼承特性或形狀，這種生命現(xiàn)象就稱為遺傳(Heredity)，研究這種生命現(xiàn)象的科學(xué)叫做遺傳學(xué)(Genetics)。由于遺傳的作用，使得人們可以種瓜得瓜、種豆得豆，也使得鳥仍然是在天空中飛翔，與仍然是在水中遨游[5]。構(gòu)成生物的基本機(jī)構(gòu)和功能是細(xì)胞(Cell)。細(xì)胞中含有的一種微小的絲狀化合物成為染色體(Chromosome)，生物的所有遺傳信息都包含在這個(gè)復(fù)雜而微小的染色體中。遺傳信息是由基因(Gene)組成的，生物的各種性狀由其相應(yīng)的基因所控制，基因是遺傳的基本單位。細(xì)胞通過分裂具有自我復(fù)制的能力，在細(xì)胞分裂的過程中，其遺傳基因也同時(shí)被復(fù)制到下一代，從而其形狀也被下一代繼承?；蚓褪荄NA或RNA長(zhǎng)鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位。DNA中，遺傳信息在一條長(zhǎng)鏈上按照一定的模式排列，亦即進(jìn)行了遺傳編碼。一個(gè)基因或多個(gè)基因決定了組成蛋白質(zhì)的20種氨基酸的組成比例及其排列順序。遺傳基因在染色體中所占據(jù)的位置成為基因座(Locus)，同一基因座可能有的全部基因座稱為等位基因(Allele)。細(xì)胞在分裂時(shí)，遺傳物質(zhì)DNA通過復(fù)制(Reproduction)而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新細(xì)胞就繼承了舊細(xì)胞的基因。有性生殖生物在繁衍下一代時(shí)，兩個(gè)同源染色體之間通過交叉(Crossover)而重組，亦即在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合而形成兩個(gè)新的染色體。另外，在行細(xì)胞復(fù)制時(shí)，雖然概率很小，但也有可能產(chǎn)生某些復(fù)制差錯(cuò)，從而使DNA發(fā)生某種變異(Mutation)，產(chǎn)生出新的染色體。這些染色體表現(xiàn)出新的性狀。如此這般，遺傳基因或染色體在遺傳的過程中由于各種各樣的原因而產(chǎn)生變化。進(jìn)化生物在其延續(xù)生存的過程中，逐漸適應(yīng)于其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化(Evolution)。生物的進(jìn)化是以集團(tuán)的形式共同進(jìn)行的，這樣的一個(gè)團(tuán)體稱為群體(Population)，組成群體的單個(gè)生物稱為個(gè)體(Individual)，每一個(gè)個(gè)體對(duì)其生存環(huán)境都有不同的適應(yīng)能力，這種適應(yīng)能力稱為個(gè)體的適應(yīng)度(Fitness)。達(dá)爾文(Darwin)的自然選擇學(xué)說(NaturalSelection)構(gòu)成了現(xiàn)代進(jìn)化論的主體。自然選擇學(xué)說認(rèn)為，通過不同的生物間的交配以及其他一些原因，生物的基因有可能發(fā)生變異而形成一種新的生物基因，這部分變異了的基因也將傳到下一代。雖然這種變化的概率是可以預(yù)測(cè)的，但具體哪一個(gè)個(gè)體發(fā)生變化卻是偶然的。這種新的基因其與環(huán)境的適應(yīng)程度決定其增殖能力，有利于生存環(huán)境的基因逐漸增多，而不利于生存環(huán)境的基因逐漸減少。通過這種自然的選擇，物種將逐漸的向適應(yīng)于其生存環(huán)境的方向進(jìn)化，從而產(chǎn)生出優(yōu)良的物種。遺傳與進(jìn)化的系統(tǒng)觀雖然人們還未完全揭開遺傳與進(jìn)化的奧秘，既沒有完全掌握其機(jī)制，也不完全清楚染色體編碼和譯碼過程的細(xì)節(jié)，更不完全了解其控制方式，但遺傳與進(jìn)化的以下幾個(gè)特點(diǎn)卻為人們所共識(shí)：(1)生物的所有遺傳信息都包含在其染色體中，染色體決定了生物的性狀。(2)染色體是由基因及其有規(guī)律的排列所組成的，遺傳和進(jìn)化過程發(fā)生在染色體上。(3)生物的繁殖過程是由其基因的復(fù)制過程完成的。(4)通過同源染色體之間的交叉或染色體的變異會(huì)產(chǎn)生新的物種，使生物呈現(xiàn)新的性狀。(5)對(duì)環(huán)境適應(yīng)性好的基因或染色體比適應(yīng)性差的基因或染色體有更多機(jī)會(huì)遺傳到下一代。遺傳算法的發(fā)展史遺傳算法起源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究。早在本世紀(jì)年代40年代，就有學(xué)者開始研究如何利用計(jì)算機(jī)進(jìn)行生物模擬技術(shù)，他們從生物的角度進(jìn)行了生物的進(jìn)化模擬、遺傳過程模擬等研究工作[10]。進(jìn)入60年代后，美國密執(zhí)安大學(xué)的Holland教授及其學(xué)生們受到這種生物模擬技術(shù)的啟發(fā)，創(chuàng)造出了一種基于生物遺傳和進(jìn)化機(jī)制的適合于復(fù)雜系統(tǒng)優(yōu)化計(jì)算的自適應(yīng)概率優(yōu)化技術(shù)，即遺傳算法。下面是在遺傳算法發(fā)展進(jìn)程中的關(guān)鍵人物做出的一些主要貢獻(xiàn)。(1)J.H.Holland60年代，Holland認(rèn)識(shí)到了生物的遺傳和自然進(jìn)化現(xiàn)象與人工自適應(yīng)系統(tǒng)的相似關(guān)系，運(yùn)用生物遺傳和進(jìn)化的思想來研究自然和人工自適應(yīng)系統(tǒng)的生成以及它們與環(huán)境的關(guān)系，提出在研究和設(shè)計(jì)人工自適應(yīng)系統(tǒng)時(shí)，可以借鑒生物遺傳機(jī)制，以群體的方法進(jìn)行自適應(yīng)搜索，并且充分認(rèn)識(shí)到了交叉、變異等運(yùn)算策略在自適應(yīng)系統(tǒng)中的重要性[5]。70年代初，Holland教授提出了遺傳算法的基本定理——模式定理(SchemaTheorem)，從而奠定了遺傳算法的理論基礎(chǔ)。1975年，Holland發(fā)表了第一本比較系統(tǒng)論述遺傳算法的專著《AdaptationinNaturalandArtificialSystems》。80年代，Holland教授實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)——分類器系統(tǒng)(ClassifierSystems，簡(jiǎn)稱CS)，開創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念，為分類器系統(tǒng)構(gòu)造出了一個(gè)完整的框架。(2)J.D.Bagley1967年，Holland的學(xué)生Bagley在其博士論文中首次提出了“遺傳算法”一詞，他發(fā)展了遺傳算子，在個(gè)體編碼上采用了雙倍體的編碼方式。他還敏銳地意識(shí)到了在遺傳算法執(zhí)行的不同階段可以使用不同的選擇率，這將有利于防止遺傳算法的早熟現(xiàn)象，從而創(chuàng)立了自適應(yīng)遺傳算法的概念。(3)K.A.DeJong1975年，DeJong在其博士論文中結(jié)合模式定理進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算試驗(yàn)，樹立了遺傳算法的工作框架，得到了一些重要且具有指導(dǎo)意義的結(jié)論。例如，對(duì)于規(guī)模在50～100的群體，經(jīng)過10～20代的進(jìn)化，遺傳算法都能以很高的概率找到最優(yōu)或近似最優(yōu)解。(4)D.J.Goldberg1989年，Goldberg出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法(GeneticAlgorithmsinSearch,OptimizationandMachineLearning)》。該書系統(tǒng)總結(jié)了遺傳算法的研究成果，全面而完整地論述了遺傳算法的基本原理及其應(yīng)用。(5)L.Davis1991年，Davis編輯出版了《遺傳算法手冊(cè)(HandbookofGeneticAlgorithms)》一書，書中包括了遺傳算法在科學(xué)計(jì)算、工程技術(shù)和社會(huì)經(jīng)濟(jì)中的大量應(yīng)用實(shí)例。(6)J.R.Koza1992年，Koza將遺傳算法應(yīng)用于計(jì)算機(jī)程序的優(yōu)化設(shè)計(jì)及自動(dòng)生成，提出了遺傳編程(GeneticProgramming,GP)的概念。并成功地把遺傳編程的方法應(yīng)用于人工智能、機(jī)器學(xué)習(xí)、符號(hào)處理等方面?；诨叶鹊膱D像分割圖像分割概述圖像分割是圖像處理與機(jī)器視覺的基本問題之一，其任務(wù)是把圖像劃分成互不交迭區(qū)域的集合。這些區(qū)域的劃分是有實(shí)際意義的，他們或者代表不同的物體，或者代表物體的不同部分。圖像分割的一個(gè)難點(diǎn)在于，在劃分前，不一定能夠確定圖像區(qū)域的數(shù)目。當(dāng)人們觀察景物時(shí)，在視覺系統(tǒng)中對(duì)景物進(jìn)行分割的過程是必不可少的。這個(gè)過程非常有效，以至于使人所看到的并不是一個(gè)復(fù)雜的景物，而不過是一種物體的集合。但是使用數(shù)字處理必須設(shè)法分離圖像中的物體，把圖像分裂成像素的集合，每個(gè)集合代表一個(gè)物體的圖像。盡管數(shù)字圖像分割的任務(wù)在人類視覺感受中很難找到對(duì)照，在數(shù)字圖像分析中它是一個(gè)并非輕而易舉的任務(wù)。圖像分割的應(yīng)用領(lǐng)域圖像分割是模式識(shí)別領(lǐng)域中的一個(gè)重要內(nèi)容。在一幅給定含有多個(gè)物體的數(shù)字圖像的條件下，模式識(shí)別由三個(gè)主要階段組成(見圖1-1)。第一個(gè)階段稱為圖像分割階段。在該階段中檢測(cè)出各個(gè)物體，并把它與其他景物分離。第二個(gè)階段稱為特征抽取階段。在該階段中進(jìn)行度量。一個(gè)度量是指一個(gè)物體某個(gè)可度量性質(zhì)的度量值，而特征是一個(gè)或多個(gè)度量的函數(shù)。計(jì)算特征是為了對(duì)物體的一些重要特征進(jìn)行度量估計(jì)。特征抽取過程產(chǎn)生了一組特征，把它們組合在一起就形成了特征向量。這種被大大減少了的信息（與原始圖像相比）代表了后續(xù)分類決策必須依靠的全部知識(shí)。引進(jìn)一個(gè)n維空間的概念是很有益的，這個(gè)空間包含了所有可能的n維特征向量。因此任意一個(gè)特定物體都對(duì)應(yīng)于特征空間中的一點(diǎn)。模式識(shí)別的第三個(gè)階段是分類。它的輸出僅僅是一種決策，確定每一個(gè)物體應(yīng)該屬于的類別。每個(gè)物體被識(shí)別為某一特定的類型，它是通過一個(gè)分類過程加以實(shí)現(xiàn)的。每個(gè)物體被指定屬于若干預(yù)先定義好的組（類）中的某一組。這些組代表了預(yù)期存在于圖像中物體的所有可能類別。如果把指派物體歸到一個(gè)不正確的類，就產(chǎn)生一個(gè)分類錯(cuò)誤。圖1-1模式識(shí)別的三個(gè)階段圖像分割的用途非常廣泛，幾乎涉及有關(guān)圖像處理的所有領(lǐng)域，應(yīng)用于各種類型的圖像。例如，在醫(yī)學(xué)應(yīng)用中，腦部核磁共振(MR)圖像分隔成灰質(zhì)、白質(zhì)、腦脊髓等腦組織和其他非腦組織區(qū)域等；在交通圖像分析中，把車輛目標(biāo)從背景中分隔出來；在面向圖像的圖像壓縮和基于內(nèi)容的圖像數(shù)據(jù)庫查詢中，將圖像分隔成不同的對(duì)象區(qū)域作為基元進(jìn)行處理；在遙感云圖中利用紋理的差別分隔不同背景分布的云系等。在這些應(yīng)用中，分隔通常用來對(duì)圖像進(jìn)行進(jìn)一步的分析、識(shí)別及壓縮編碼等，分割的準(zhǔn)確性直接影響后續(xù)任務(wù)的有效性，因此具有十分重要的意義。圖像分割的通用定義按照通用的分隔定義，分割出的區(qū)域需要同時(shí)滿足均勻性和連通性的條件。其中均勻性是指該區(qū)域中的所有像素點(diǎn)都滿足基于灰度、紋理、顏色等特征的某種相似性準(zhǔn)則，而連通性是指在該區(qū)域內(nèi)任意兩點(diǎn)存在相互連通的途徑[6]。設(shè)F表示一幅圖像中所有像素的集合，P(·)是某個(gè)均勻性的假設(shè)，分割就是把F化分成若干子集(S1,S2,…,Sn),其中各子集構(gòu)成一個(gè)空間連通區(qū)域，且滿足以下條件:且，P(·)滿足P()=true,P()=false,若與在空間相鄰?fù)耆仙鲜龆x的分割計(jì)算十分復(fù)雜，目前大部分研究都是針對(duì)某一類型圖像或者某一具體的分割，人們?nèi)栽趯?duì)圖像分割的通用方法和策略進(jìn)行研究。通常情況下，利用目標(biāo)區(qū)域和背景區(qū)域在灰度方面的差異，可以實(shí)現(xiàn)對(duì)圖像的分割，即基于灰度的圖像分割?；叶乳T限法灰度門限法簡(jiǎn)介適用閾值是一種區(qū)域分割技術(shù)，它對(duì)物體與背景有較強(qiáng)對(duì)比的景物的分割特別有用。它計(jì)算簡(jiǎn)單，而且總能用封閉而且連通的邊界定義不交疊的區(qū)域。當(dāng)使用閾值規(guī)則進(jìn)行圖像分割時(shí)，所有灰度值大于或等于某閾值的像素都被判為屬于物體。所有灰度值小于該閾值的像素被排除在物體之外。于是，邊界就成為這樣一些內(nèi)部點(diǎn)的集合，這些點(diǎn)都至少有一個(gè)鄰點(diǎn)不屬于該物體。如果感興趣的物體在其內(nèi)部具有均勻一致的灰度值并分布在一個(gè)具有另一個(gè)灰度值的均勻背景上，使用閾值方法效果就很好。如果物體同背景的差別在于某些性質(zhì)而不是灰度值（如紋理等）,那么，可以首先把那個(gè)性質(zhì)轉(zhuǎn)化成灰度，然后利用灰度閾值化技術(shù)分割待處理的圖像。設(shè)圖像f(x,y)的灰度范圍屬于[z1,z2]，根據(jù)一定的經(jīng)驗(yàn)及知識(shí)確定一個(gè)灰度的門限，或者根據(jù)一定的準(zhǔn)則確定[z1,z2]的一個(gè)劃分Z1，Z2，其中Z1代表目標(biāo)，Z2代表背景。根據(jù)像素的灰度屬于這個(gè)劃分的那個(gè)部分來將其分類，稱為灰度門限法，即：如果f(x,y)屬于Z1，判斷(x,y)像素屬于目標(biāo)。如果f(x,y)屬于Z2，則判斷(x,y)像素屬于背景。根據(jù)劃分方法的不同，可以將灰度門限法分為:(1)直接門限法如果在目標(biāo)區(qū)域和背景區(qū)域的內(nèi)部，像素間的灰度都基本一致，而目標(biāo)和背景區(qū)域的像素灰度有一定差異，可以根據(jù)灰度不同直接設(shè)定灰度門限進(jìn)行分割。例如對(duì)于含有細(xì)胞的醫(yī)學(xué)圖像，細(xì)胞的灰度通常比背景低得多，這時(shí)可以根據(jù)某種準(zhǔn)則求出一個(gè)門限，當(dāng)像素的灰度低于門限時(shí)，判斷像素屬于目標(biāo)，即可將細(xì)胞提取出來。(2)間接門限法在有些情況下，如果對(duì)圖像做一些必要的預(yù)處理然后再運(yùn)用門限法，可以有效的實(shí)現(xiàn)圖像分割。例如，圖像只有黑色和白色兩個(gè)灰度，但白色像素在目標(biāo)區(qū)域中出現(xiàn)的概率比在背景區(qū)域中出現(xiàn)的概率大，即目標(biāo)區(qū)域的平均灰度高于背景區(qū)域，可以先對(duì)圖像進(jìn)行鄰域平均運(yùn)算，再對(duì)新圖運(yùn)用門限法進(jìn)行分割。又如，圖像中目標(biāo)區(qū)域灰度變化劇烈，而背景區(qū)域變化平緩，可以先對(duì)原圖像進(jìn)行拉氏運(yùn)算，突出目標(biāo)區(qū)域的特征，然后對(duì)新圖運(yùn)用鄰域平均技術(shù)，最后運(yùn)用門限法實(shí)行有效的分割。(3)多門限法有時(shí)候一幅圖像含有兩個(gè)以上不同類型的區(qū)域，用直接或者間接單門限的方法無法將兩個(gè)以上的目標(biāo)區(qū)域提取出來，這時(shí)可以使用多個(gè)門限將這些區(qū)域劃分開。對(duì)于只有兩個(gè)類型區(qū)域的圖像有時(shí)也要使用多門限的方法，例如圖像是在照度不均勻條件下提取的，若使用單一門限對(duì)整幅圖像進(jìn)行分割，可能發(fā)生在圖像的一邊能精確的把目標(biāo)和背景分開，而在另一邊可能把太多的背景當(dāng)作目標(biāo)點(diǎn)保留下來的情況，或者正好相反，得不到好的分割結(jié)果。在這種情況下，可以運(yùn)用同態(tài)濾波技術(shù)校正灰度，然后再單一門限進(jìn)行分割，這相當(dāng)于對(duì)圖像進(jìn)行預(yù)處理的間接門限法。同時(shí)還可以把圖像分成若干個(gè)子圖，各自圖像中目標(biāo)和背景相對(duì)差別比較分明，可以分別對(duì)每個(gè)子圖進(jìn)行單門限分割，再將分割結(jié)果綜合起來。使用雙門限法也可以提高對(duì)兩類區(qū)域的圖像的分割精度。方法是設(shè)置一高一低兩個(gè)門限t1、t2，不妨設(shè)t1<t2。選擇t2使有些目標(biāo)點(diǎn)的灰度大于t2，選擇t1應(yīng)使每個(gè)目標(biāo)點(diǎn)的灰度均高于t1。在進(jìn)行分割時(shí)，把灰度大于t2的像素點(diǎn)作為“核心”目標(biāo)點(diǎn)，對(duì)于灰度超過t1的像素再根據(jù)它和核心目標(biāo)點(diǎn)的距離判斷，如果相鄰則將其當(dāng)作目標(biāo)點(diǎn)。這種分割方式除了利用灰度信息還使用了空間距離信息，因此分割效果好?；叶乳T限的確定分割門限選擇的準(zhǔn)確性直接影響分割的精度及圖像描述分析的正確性。門限選擇的太高容易把大量的目標(biāo)判為背景，定的太低又會(huì)把大量的背景判為目標(biāo)。因此正確分割門限是很重要的。通常采用根據(jù)先驗(yàn)知識(shí)確定門限，或者利用灰度直方圖特征和統(tǒng)計(jì)判決方法確定灰度分割門限。如果已知被處理圖像的一些先驗(yàn)信息，可以利用試探的方法確定門限。例如已知一幅文字圖像中文字占的比例為x，可以選這樣一個(gè)門限，使得對(duì)圖像進(jìn)行門限化處理后，灰度小于門限的像素的數(shù)目約占總像素的百分之x。很多時(shí)候并沒有關(guān)于圖像充分的先驗(yàn)知識(shí)，因此只能從圖像本身的特征出發(fā)來確定門限。圖像的統(tǒng)計(jì)特性可以提供分割的依據(jù)。利用灰度直方圖特征確定灰度分割門限的原理是：如果圖像所含的目標(biāo)區(qū)域和背景區(qū)域大小可比，而且目標(biāo)區(qū)域和背景區(qū)域在灰度上有一定的差別，那么該圖像的灰度直方圖會(huì)直接呈現(xiàn)雙峰一谷，其中一個(gè)峰值對(duì)應(yīng)于目標(biāo)的中心灰度，另一個(gè)峰值對(duì)應(yīng)于背景的中心灰度。由于目標(biāo)邊界點(diǎn)較少且其灰度介于它們之間，所以雙峰之間的谷點(diǎn)對(duì)應(yīng)著邊界的灰度，可以將谷點(diǎn)的灰度作為分割的門限。由于直方圖的參差性，實(shí)際上尋找谷值并不是一個(gè)簡(jiǎn)單的過程，需要設(shè)計(jì)一定的準(zhǔn)則進(jìn)行搜索。假設(shè)圖像的直方圖為h，確定直方圖谷點(diǎn)的位置方法之一是通過搜索找出直方圖的局部最大值，設(shè)他們的位置是Z1和Z2，并且要求這兩點(diǎn)的距離大于某一設(shè)定的距離，然后求Z1和Z2之間直方圖的最低點(diǎn)Zm，用h(Zm)/min(h(Z1))，h(Z2)測(cè)量直方圖的平坦性，若這個(gè)之很小，則表示直方圖是雙峰一谷狀，可將Zm最為分割門限。尋找分割門限也可以用一個(gè)解析函數(shù)來擬合直方圖雙峰間的部分，然后再用函數(shù)求極值的方法找出這個(gè)這個(gè)解析函數(shù)最小值的位置作為谷點(diǎn)。例如可用二次曲線：2(2-1)來擬合雙峰間的直方圖，求得擬合系數(shù)，則可作為分割門限。類似的也可以使用兩個(gè)高斯函數(shù)的兩個(gè)峰，然后求出兩個(gè)高斯函數(shù)的交點(diǎn)來確定門限。需要指出的是，由于直方圖是個(gè)灰度的像素統(tǒng)計(jì)，未考慮圖像其他方面的知識(shí)，只靠直方圖分割的結(jié)果有可能是錯(cuò)誤的。即使直方圖是典型的雙峰一谷特性，這個(gè)圖像也未必含有和背景有反差的目標(biāo)。例如一幅左邊是黑色而右邊是白色的圖像和一幅黑白像點(diǎn)隨機(jī)分布的圖像具有相同的直方圖，但是后者就不包含有意義的目標(biāo)。另外還可以利用統(tǒng)計(jì)判決門限，比如利用最小誤判概率準(zhǔn)則確定分割的最佳門限。最大類間方差閾值分割法在不知道圖像分布的情況下，還可以采用模式識(shí)別中最大類間方差準(zhǔn)則確定分割的最佳門限。其基本思想是對(duì)像素進(jìn)行劃分，通過使劃分得到的各類之間的距離達(dá)到最大，來確定合適的門限。這種算法是由日本大津展之在1980年提出的，它是從最小二乘法原理的基礎(chǔ)上推導(dǎo)出來的，其基本思路是將圖像的直方圖以某一灰度為閾值將圖像分成兩組并計(jì)算兩組的方差，當(dāng)被分成的兩組之間的方差最大時(shí)，就以這個(gè)灰度值為閾值分割圖像。設(shè)一幅圖像的灰度值為m個(gè)，灰度值為i的像素?cái)?shù)為ni，則得到：總像素?cái)?shù)N=(2-2)各灰度值的概率Pi=(2-3)然后用k值將其分成兩組C0=[1…k]和C1=[k+1...m]，則各組產(chǎn)生的概率如下：C0組產(chǎn)生的概率0==(2-4)C1組產(chǎn)生的概率1===1-0(2-5)C0組的平均灰度值0==(2-6)C1組的平均灰度值1==(2-7)整體平均灰度值=(2-8)其中閾值為k時(shí)灰度的平均值(k)=(2-9)所以采樣的灰度平均值為μ=(2-10)兩組間的方差公式如下d(k)==(2-11)從1-m之間改變k值，求k使得d(k)=max(d(k))，然后，以k為閾值分割圖像，這樣就得到最佳的分割效果。圖2-4是利用最大方差法求出灰度門限對(duì)一幅圖像進(jìn)行分割的結(jié)果，可以看出分割效果令人滿意，細(xì)胞灰度較低，因此可以和背景區(qū)分開來。但是由于細(xì)胞中心灰度較亮，因此分割是被歸入背景。這不是由于門限選擇不正確，而是由于同一物體有不同的灰度造成的。圖2-2原始圖像的直方圖圖2-3原始圖像圖2-4最大方差法分割后圖像本章小結(jié)本章介紹了圖像分割的基本知識(shí)，詳述了其原理和應(yīng)用領(lǐng)域。以數(shù)學(xué)形式表示了圖像分割的定義，主要內(nèi)容是描述利用目標(biāo)區(qū)域和背景區(qū)域在灰度方面的差異的基于灰度的圖像分割，其應(yīng)用領(lǐng)域廣泛?；诨叶确指畹年P(guān)鍵是灰度門限的確定，著重介紹最大類間方差準(zhǔn)則確定分割的最佳門限，推導(dǎo)出公式，本方法是本次設(shè)計(jì)的基礎(chǔ)。遺傳算法遺傳算法概述遺傳算法(GeneticAlgorithms,GAs)是以自然選擇和遺傳理論為基礎(chǔ)，將生物過程中適者生存的規(guī)則與群體內(nèi)部的隨機(jī)信息交換機(jī)制相結(jié)合的搜索算法，能夠?qū)崿F(xiàn)全局并行搜索，對(duì)搜索空間無特殊要求，不需要人為干預(yù)，可以根據(jù)搜索空間的特征，自動(dòng)將搜索引向最佳點(diǎn)，因而具有了很強(qiáng)的智能性以及較高的搜索效率，是一種有效的解決最優(yōu)化問題的方法。它逐漸發(fā)展成為一種通過模擬自然進(jìn)化過程解決最優(yōu)化問題的計(jì)算模型，在計(jì)算上具有通用、穩(wěn)定、簡(jiǎn)單、并行處理的特點(diǎn)。遺傳算法從80年代末及90年代初開始流行，在大型工業(yè)自動(dòng)化處理上得到了廣泛的應(yīng)用。遺傳算法主要借用生物進(jìn)化中“適者生存”的規(guī)律[7]?！斑m者生存”揭示了大自然生物進(jìn)化過程中的一個(gè)規(guī)律：最適合自然環(huán)境的群體往往產(chǎn)生了更大的后代群體。在介紹遺傳算法之前，先了解生物的進(jìn)化過程，見圖3-1。圖3-1生物進(jìn)化循環(huán)圖遺傳算法主要借鑒了生物進(jìn)化的一些特征，其主要特征體現(xiàn)為：(1)進(jìn)化發(fā)生在解的編碼上。這些編碼按生物學(xué)的術(shù)語稱為染色體。由于進(jìn)行了編碼，優(yōu)化問題的一切性質(zhì)都通過編碼來研究。編碼和解碼是遺傳算法的一個(gè)主題。(2)自然選擇規(guī)律決定哪些染色體產(chǎn)生超過平均數(shù)的后代。遺傳算法中，通過優(yōu)化問題的目標(biāo)而人為的構(gòu)造適應(yīng)函數(shù)以達(dá)到好的染色體產(chǎn)生超過平均數(shù)的后代。(3)當(dāng)染色體結(jié)合時(shí)，雙親的遺傳基因的結(jié)合時(shí)的子女保持父母的特征。(4)當(dāng)染色體結(jié)合后，隨機(jī)的變異會(huì)造成子代同父代的不同。表3-1生物遺傳概念在遺傳算法中的對(duì)應(yīng)關(guān)系生物遺傳概念遺傳算法中的作用適者生存在算法停止時(shí)，最優(yōu)目標(biāo)值的解有最大可能被留住個(gè)體(individual)解染色體(chromosome)解的編碼（字符串，向量等）基因(gene)解中每一分量的特征（如各分量的值）適應(yīng)性(fitness)適應(yīng)函數(shù)值群體(population)選定的一組解（其中解的個(gè)數(shù)為群體的規(guī)模）種群(reproduction)根據(jù)適應(yīng)函數(shù)值選取的一組新解的過程交配(crossover)通過交配原則產(chǎn)生一組新解的過程變異(mutation)編碼的某一個(gè)分量發(fā)生變化的過程遺傳算法的特點(diǎn)遺傳算法的特點(diǎn)可被歸納為:(1)遺傳算法利用目標(biāo)函數(shù)變量的編碼方式，而不像傳統(tǒng)方法用變量本身。(2)遺傳算法，在解空間中，從多點(diǎn)尋找問題的解，而不像某些傳統(tǒng)方法從某一點(diǎn)尋找解。(3)遺傳算法直接應(yīng)用目標(biāo)函數(shù)的函數(shù)值信息，而非函數(shù)的導(dǎo)數(shù)或其它輔助信息。(4)遺傳算法，引用了概率轉(zhuǎn)換規(guī)則，而不采用確定性的轉(zhuǎn)換規(guī)則。遺傳算法的應(yīng)用遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對(duì)問題的種類有很強(qiáng)的魯棒性[11]，所以廣泛應(yīng)用于很多學(xué)科。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域：(1)函數(shù)優(yōu)化。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果。(2)組合優(yōu)化。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇增大，有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或不可能求出其精確最優(yōu)解。對(duì)于這類復(fù)雜問題，人們意識(shí)到把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。(3)生產(chǎn)調(diào)度問題。生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學(xué)模型難以精確求解，目前在現(xiàn)實(shí)生產(chǎn)中也主要是靠一些經(jīng)驗(yàn)來進(jìn)行調(diào)度?，F(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。(4)自動(dòng)控制。在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在其中得到了初步的應(yīng)用，并顯現(xiàn)出了良好的效果。例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法進(jìn)行空間交匯控制器、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計(jì)等，都顯示出了遺傳算法在這些領(lǐng)域中應(yīng)用的可行性。(5)機(jī)器人學(xué)。機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對(duì)人工自適應(yīng)系統(tǒng)的研究。例如遺傳算法己經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到了研究和應(yīng)用。(6)圖像處理。圖像處理是計(jì)算機(jī)視覺中的一個(gè)重要研究領(lǐng)域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免的會(huì)存在一些誤差，這些誤差會(huì)影響到圖像處理的效果。如何使這些誤差最小是使計(jì)算機(jī)視覺達(dá)到實(shí)用化的重要要求。遺傳算法在這些圖像處理中的優(yōu)化計(jì)算方面找到了用武之地，目前已在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用。(7)人工生命。人工生命是用計(jì)算機(jī)、機(jī)械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學(xué)習(xí)能力是人工生命的兩大主要特征?；谶z傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。(8)遺傳編程。Koza發(fā)展了遺傳編程的概念，它使用了以LISP語言所表示的編碼方法，基于一種樹型結(jié)構(gòu)所進(jìn)行的遺傳操作來自動(dòng)生成計(jì)算機(jī)程序。(9)機(jī)器學(xué)習(xí)。學(xué)習(xí)能力是高級(jí)自適應(yīng)系統(tǒng)所具備的能力之一?；谶z傳算法的機(jī)器學(xué)習(xí)，特別是分類器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用?；具z傳算法基于對(duì)自然界中生物遺傳與進(jìn)化機(jī)理的模仿，針對(duì)不同的問題，很多學(xué)者設(shè)計(jì)了許多不同的編碼方式來表示問題的可行解，開發(fā)出了許多不同的遺傳算子來模仿不同環(huán)境下的生物遺傳特性。這樣，由不同的編碼方式和不同的遺傳算子就構(gòu)成了各種不同的遺傳算法。但這些遺傳算法都有共同的特點(diǎn)，即通過對(duì)生物的遺傳和進(jìn)化中選擇、交叉、變異機(jī)理的模仿，來完成對(duì)問題最優(yōu)解的自適應(yīng)搜索過程?；谶@個(gè)共同特點(diǎn)，Goldberg總結(jié)出了一種統(tǒng)一的最基本的遺傳算法——基本遺傳算法(SimpleGeneticAlgorithms,SGA)?；具z傳算法只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其遺傳進(jìn)化操作過程簡(jiǎn)單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算子提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值?；具z傳算法(SGA)的操作對(duì)像是一群二進(jìn)制串（稱為染色體、個(gè)體），即種群。這里每個(gè)染色體都對(duì)應(yīng)于問題的一個(gè)解。從初始種群出發(fā)，采用基于適應(yīng)值比例的選擇策略在當(dāng)前種群中選擇個(gè)體，使用雜交(Crossover)和變異(Mutation)，來產(chǎn)生下一代種群。如此一代代演化下去，直到滿足期望的終止條件。基本遺傳算法的構(gòu)成要素(1)染色體編碼方法?；具z傳算法使用固定長(zhǎng)度的二進(jìn)制符號(hào)串來表示群體中的個(gè)體，其等位基因是由二值符號(hào)集{0，1}所組成的。初始群體中各個(gè)個(gè)體的基因之可用均分布的隨機(jī)數(shù)來生成。如：X=100111001000101101就可以表示一個(gè)個(gè)體，該個(gè)體的染色體長(zhǎng)度是n=18。(2)個(gè)體適應(yīng)度評(píng)價(jià)?；具z傳算法按與個(gè)體成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。為正確計(jì)算這個(gè)概率，這里要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。這樣，根據(jù)不同種類的問題，必須預(yù)先確定好由目標(biāo)函數(shù)到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)律，特別是要預(yù)先確定好目標(biāo)函數(shù)為負(fù)數(shù)時(shí)的處理方法。(3)遺傳算子。基本遺傳算法使用下述三種遺傳算子：選擇運(yùn)算使用比例選擇算子；交叉運(yùn)算使用單點(diǎn)交叉算子；變異運(yùn)算使用基本位變異算子或均勻變異算子。(4)基本遺傳算法的運(yùn)行參數(shù)。基本遺傳算法有下述3個(gè)運(yùn)算參數(shù)需要提前設(shè)定：M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取為20～100。T：遺傳算法的終止進(jìn)化代數(shù)，一般取為100～500。Pc：交叉概率，一般取為0.4～0.99。Pm：變異概率，一般取為0.0001～0.1。需要說明的是，這4個(gè)運(yùn)行參數(shù)對(duì)遺傳算法的求解結(jié)果和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據(jù)。在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍?；具z傳算法的形式化定義基本遺傳算法可以定義為一個(gè)8元組：SGA=(C，E，P0，M，，，，T)式中C——個(gè)體的編碼方法；E——個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)；P0——初始群體；M——群體大??；Φ——選擇算子；?！徊嫠阕?；Ψ——變異算子；T——遺傳算終止條件。基本遺傳算法的實(shí)現(xiàn)根據(jù)基本遺傳算法構(gòu)成要素的分析和描述，可以很方便的用計(jì)算機(jī)語言來實(shí)現(xiàn)這個(gè)基本遺傳算法。(1)個(gè)體適應(yīng)度評(píng)價(jià)在遺傳算法中，以個(gè)體適應(yīng)度的大小來確定該個(gè)體被遺傳到下一代群體的概率。個(gè)體的適應(yīng)度越大，該個(gè)體被遺傳到下一代的概率也越大；反之，個(gè)體的適應(yīng)度越小，該個(gè)體被遺傳到下一代的概率也越小。基本遺傳算法使用比例選擇算子來確定群體中各個(gè)個(gè)體遺傳到下一代群體中的數(shù)量。為正確計(jì)算不同情況下各個(gè)個(gè)體的遺傳概率，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)。對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，理論上只需簡(jiǎn)單的對(duì)其增加一個(gè)負(fù)號(hào)就可將其轉(zhuǎn)化為目標(biāo)函數(shù)最大值的優(yōu)化問題，即：min=max(-)(3-1)當(dāng)優(yōu)化目標(biāo)是求函數(shù)最大值，并且目標(biāo)函數(shù)函數(shù)總?cè)≌禃r(shí)，可以直接設(shè)定個(gè)體的適應(yīng)度(X)就等于相應(yīng)的目標(biāo)函數(shù)值(X)，即：(X)=(3-2)但實(shí)際優(yōu)化問題中的目標(biāo)函數(shù)值有正也有負(fù)，優(yōu)化目標(biāo)有求函數(shù)最大值，也有求函數(shù)最小值，顯然上面兩式保證不了所有情況下個(gè)體的適應(yīng)度都是非負(fù)數(shù)這個(gè)要求。所以必須尋求出一種通用且有效的由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換關(guān)系，由它來保證個(gè)體適應(yīng)度總?cè)》秦?fù)值。為滿足適應(yīng)度取非負(fù)值的要求，基本遺傳算法一般采用下面兩種方法之一將目標(biāo)函數(shù)值f(X)變換為個(gè)體適應(yīng)度F(X)。方法一：對(duì)于求目標(biāo)函數(shù)值最大值的優(yōu)化問題，變換方法為：(X)＝(3-3)式中，為一個(gè)適當(dāng)?shù)南鄬?duì)比較小的數(shù)，它可以用下面幾種方法之一來選取。預(yù)先指定的一個(gè)較小的數(shù).進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。方法二：對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，變換方法為：(X)＝(3-4)式中，為一個(gè)適當(dāng)?shù)南鄬?duì)比較大的數(shù)，它可以用下面幾種方法之一來選取。預(yù)先指定的一個(gè)較大的數(shù)。進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。當(dāng)前代或最近幾代群體中的最大目標(biāo)函數(shù)值。(2)比例選擇算子選擇算子或復(fù)制算子的作用是從當(dāng)前代群體中選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代群體中。最常用和最基本的選擇算子是比例選擇算子。所謂比例選擇算子，是指?jìng)€(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。比例選自算子實(shí)際上是一種有退還隨機(jī)選擇，也叫賭盤(RouletteWheel)選擇，因?yàn)檫@種選擇方式與賭博中的賭盤操作原理頗為相似。圖3-2賭盤示意圖如圖3-2所示為一賭盤示意圖。整個(gè)賭盤被分為大小不同的一些扇面，分別對(duì)應(yīng)著價(jià)值不同的一些賭博品。當(dāng)旋轉(zhuǎn)著的賭盤自然停下來時(shí)，其指針?biāo)干让嫔系奈锲肪蜌w賭博者所有。雖然賭博的指針具體停止在哪一個(gè)扇面是無法預(yù)測(cè)的，但指針指向各個(gè)扇面的概率是可以估計(jì)的，它與各個(gè)扇面的圓心角大小成正比：圓心角越大，停在該扇面的可能性也越大；圓心角越小，停在該扇面的可能性也越小。與此類似，在遺傳算法中，整個(gè)群體被各個(gè)個(gè)體所分割，各個(gè)個(gè)體的適應(yīng)度在全部個(gè)體的適應(yīng)度之和中所占比例也大小不一，這個(gè)比例值瓜分了整個(gè)賭盤盤面，它們也決定了各個(gè)個(gè)體被遺傳到下一代群體中的概率。比例選擇算子的具體執(zhí)行過程是：先計(jì)算出群體中所有個(gè)體的適應(yīng)度的總和。其次計(jì)算出每個(gè)個(gè)體的相對(duì)適應(yīng)度的大小，它即為各個(gè)個(gè)體被遺傳到下一代群體中的概率。最后再使用模擬賭盤的操作（即0到1之間的隨機(jī)數(shù)）來確定各個(gè)個(gè)體被選中的次數(shù)。(3)單點(diǎn)交叉算子單點(diǎn)交叉算子是最常用和最基本的交叉操作算子。單點(diǎn)交叉算子的具體執(zhí)行過程如下：對(duì)群體中的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)。若群體大小為M，則共有[M/2]對(duì)相互配對(duì)的個(gè)體組。其中[x]表示不大于x的最大整數(shù)。對(duì)每一對(duì)相互配對(duì)的個(gè)體，隨機(jī)設(shè)置某一基因座之后的位置為交叉點(diǎn)。若染色體的長(zhǎng)度為n，則共有(n-1)個(gè)可能的交叉點(diǎn)位置。對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率Pc在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。單點(diǎn)交叉運(yùn)算的示意如下所示：：1011011100單點(diǎn)交叉：1011011111：0001110011：0001110000交叉點(diǎn)(4)基本位變異算子基本位變異算子是最簡(jiǎn)單和最基本的變異操作算子。對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將該基因值變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)?。基本位變異算子的具體執(zhí)行過程是：對(duì)個(gè)體的每一個(gè)基因座，依變異概率Pm指定其為變異點(diǎn)。對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值作取反運(yùn)算或用其他等位基因值來代替，從而產(chǎn)生出一個(gè)新的個(gè)體?；疚蛔儺愃阕舆\(yùn)算的示意如下所示：：1010101010基本位變異：1010001010變異點(diǎn)基本遺傳算法的應(yīng)用步驟遺傳算法是一個(gè)群體優(yōu)化過程，為了達(dá)到目標(biāo)函數(shù)的最大值，或者最小值，從一組初值(即一個(gè)群體)出發(fā)進(jìn)行繁衍優(yōu)化，這過程包括了群體的繁衍競(jìng)爭(zhēng)、雜交與變異，把優(yōu)化問題的解的空間映射為遺傳空間，把每一個(gè)可能的解編碼作為一個(gè)稱為染色體的二進(jìn)制串。染色體的每一位稱為一個(gè)基因，每個(gè)染色體稱為一個(gè)解。一定數(shù)量的個(gè)體組成種群，它是遺傳算法的搜索空間。在搜索過程中，用適應(yīng)度函數(shù)來評(píng)價(jià)每個(gè)染色體的優(yōu)劣，其值越大，適應(yīng)度越大，染色體解最優(yōu)。選擇適應(yīng)度大的染色體進(jìn)行再生，通過交換、變異兩種操作產(chǎn)生新的一代更適應(yīng)環(huán)境的染色體群。如此反復(fù)操作，一代一代不斷向最優(yōu)化方向進(jìn)化從而得到問題的最優(yōu)解。遺傳算法有以下的幾種基本運(yùn)算:(1)定義染色體及其表達(dá)式，即把問題的解數(shù)值化(又稱為編碼)，在對(duì)問題解的編碼過程中，必須合理安排其編碼結(jié)構(gòu)，一個(gè)染色體表示一種可能的解，因此所有的染色體集合應(yīng)能表示問題的所有解空間。如進(jìn)行二進(jìn)制的編碼，形成二進(jìn)制的串，一個(gè)這樣的二進(jìn)制串就表示一條染色體，當(dāng)然這樣的染色體并不是問題的一個(gè)直接解，還必須把它還原成為一個(gè)實(shí)際值，還原過程稱為解碼。(2)初始化群體：初始化的過程較為簡(jiǎn)單，隨機(jī)產(chǎn)生幾條染色體組成一個(gè)種群體，設(shè)定一種群的規(guī)模(包含的染色體的個(gè)數(shù))為popsize，一般從運(yùn)算的角度來考慮，種群的規(guī)模不要選取過大也不能太少，其選取與實(shí)際問題有關(guān)。(3)適應(yīng)度函數(shù)：遺傳算法中定義了一個(gè)與實(shí)際問題相關(guān)的適應(yīng)度函數(shù)，對(duì)每一個(gè)染色體，都按照適應(yīng)度函數(shù)計(jì)算一個(gè)值，表示這個(gè)染色體對(duì)于實(shí)際總題的適應(yīng)度。適應(yīng)度函數(shù)在遺傳算法中起到一個(gè)環(huán)境的作用，其值用于評(píng)價(jià)潛在解，值越大的染色體也就越好，說明其生存能力就越強(qiáng)。(4)遺傳種子的選取根據(jù)上述的適應(yīng)度函數(shù)按照染色體適應(yīng)值定義一個(gè)選擇概率，對(duì)于整個(gè)種群建立一個(gè)累計(jì)概率，每一個(gè)染色體按照隨機(jī)方式選擇，得到一個(gè)用于遺傳運(yùn)算的種子，每一染色體都可能被選取，而選擇概率大的可能有多次被選取的機(jī)會(huì)，這符合于自然界中適者生存的道理。(5)對(duì)新的遺傳種子進(jìn)行遺傳運(yùn)算——雜交與變異：對(duì)于雜交運(yùn)算，按照雜交概率Pc，對(duì)染色體中的一些位進(jìn)行交換，產(chǎn)生兩個(gè)新的染色體，變異是按照變異率Pm對(duì)染色中一位進(jìn)行變異，這樣對(duì)于一個(gè)種群的染色體經(jīng)過上述過程后便得到了新染色體種群。(6)繁衍:按上面的遺傳算子，產(chǎn)生了一個(gè)新的種群，然后按照新的種群，反復(fù)地進(jìn)行，隨著新種群的產(chǎn)生，從而得到新的值，遺傳算法在不斷繁衍中求得最優(yōu)解，但沒有必要讓程序永遠(yuǎn)進(jìn)行下去，當(dāng)遺傳到一定代數(shù)后，其值已經(jīng)達(dá)到期望值，可以終止程序，從而實(shí)現(xiàn)了問題的優(yōu)化。由此可知，遺傳算法是非線性求解的過程，其速度顯然是優(yōu)于線性求解的。對(duì)于每一染色體其評(píng)價(jià)函數(shù)的求解是分開的。下面手工模擬一個(gè)簡(jiǎn)單的遺傳算法:設(shè)求一個(gè)二次函數(shù)的最大值maxf(x)=x20≤x≤31成員編號(hào)(1)初始群體(2)i(2)(i)(2)/∑(2)/(2)Mp1234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201總和平均值最大值11702395761.000.250.494.001.001.97412(3)再生產(chǎn)(3)配對(duì)(3)位選擇(3)新一代群體(2)i(2)(i)0110-11100-011-00010-011214311330110011001110111000012252716144625729256總和平均值最大值1754439729表3-2簡(jiǎn)單基因算法的手工模擬(無個(gè)體變異)其中，表示當(dāng)前這一代第i個(gè)成員的函數(shù)值；表示當(dāng)前這一代全體成員函數(shù)值的平均值；Mp表示傳遞到下一代的成員，由/來決定；表中的(1)，(2)，(3)分別表示算法的各個(gè)步驟。從表3-2可以看出，在產(chǎn)生出來的第2代的群體成員中，它們所代表的函數(shù)f(x)的最大值大大好于第1代，從576增加到了729，平均值也從293增至439，總和從1170增至1754。以此方式，遺傳算法一代一代地改善所代表的解的質(zhì)量，第3代的群體成員，將優(yōu)于第2代，直至第n代為止，最后從第n代群體成員中選擇優(yōu)良的個(gè)體作為問題的解。其遺傳運(yùn)算相對(duì)獨(dú)立，這一點(diǎn)適應(yīng)用于并行計(jì)算。本章小結(jié)本章簡(jiǎn)述了遺傳算法的基本理論和方法，它是一種更為宏觀意義上的仿生算法，并詳述了應(yīng)用比較廣泛的基本遺傳算法，通過對(duì)生物的遺傳和進(jìn)化中選擇、交叉、變異機(jī)理的模仿，來完成對(duì)問題最優(yōu)解的自適應(yīng)搜索過程。并得出算法的特點(diǎn)和應(yīng)用，強(qiáng)調(diào)了此算法在圖像處理方面的應(yīng)用，為下一章軟件的實(shí)現(xiàn)打好了基礎(chǔ)。本章詳細(xì)分析了遺傳算子的原理和應(yīng)用，及遺傳編程的構(gòu)成要素和基本步驟。用實(shí)例試驗(yàn)了簡(jiǎn)單的遺傳算法。說明了遺傳在并行非線性求解方面的優(yōu)越性。軟件實(shí)現(xiàn)與分析用MATLAB實(shí)現(xiàn)遺傳算法遺傳算法是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法。它借用了生物遺傳學(xué)的觀點(diǎn)，通過自然選擇、遺傳和變異等作用機(jī)制，使每個(gè)個(gè)體的適應(yīng)性提高。由美國Mathwork公司于1967年推出的MatrixLabory(縮寫為MATLAB)軟件包，是一種功能強(qiáng)、效率高便于進(jìn)行科學(xué)和工程計(jì)算的交互式軟件包[14]。在此環(huán)境下，所解問題的MATLAB語言表述形式和其數(shù)學(xué)表達(dá)形式相同，不需要按傳統(tǒng)方法編程。在MATLAB環(huán)境下編制一個(gè)簡(jiǎn)單的遺傳算法工具庫(SGA)，就可以利用MATLAB強(qiáng)大的仿真功能，進(jìn)行遺傳算法的各種仿真實(shí)驗(yàn)。一個(gè)基本的遺傳算法是將問題的求解表示成“染色體”，從而構(gòu)成一群“染色體”。將它們置于問題的“環(huán)境”中，根據(jù)適者生存的原則，從中選擇出適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，即再生(reproduction,selection)，通過交叉(crossover)、變異(mutation)兩種基因操作產(chǎn)生出新一代更適合環(huán)境的“染色體”群，這樣一代代不斷改進(jìn)，最后收斂到一個(gè)最適合環(huán)境的個(gè)體上(當(dāng)然也有其他的收斂準(zhǔn)則)，求得問題的最佳解。圖4-1給出了GA的流程圖。GA有如下3個(gè)基本算子:再生(reproduction/seletion)。再生算子從群體中按某一概率選擇個(gè)體，某個(gè)體Xi被選擇的概率Pi與其適應(yīng)值成正比。最通常的實(shí)現(xiàn)方法賭盤(roulettewheel)模型。交叉(Crossover)。交叉算子將被選中的2個(gè)個(gè)體的基因鏈按概率Pc進(jìn)行交叉，生成2個(gè)新的個(gè)體，交叉位置是隨機(jī)的。其中Pc是一個(gè)系統(tǒng)參數(shù)，即交叉概率。變異(Mutation)。變異算子按一定概率Pm將新個(gè)體的基因鏈的各位進(jìn)行變異，對(duì)二值基因鏈(0,1編碼)來說即是取反。Pm也是一個(gè)系統(tǒng)參數(shù)，即變異概率。以上各種算子的實(shí)現(xiàn)方法是多種多樣的，而且許多高級(jí)算子正不斷提出，以改進(jìn)GA的某些性能。由于GA性能具有一定脆弱性(brittleness)，因此GA本身的參數(shù)(即系統(tǒng)參數(shù))的選取對(duì)GA的運(yùn)行效果有很大影響。系統(tǒng)參數(shù)的選取一般遵循以下原則:(1)種群數(shù)目N。種群數(shù)目會(huì)影響GA的有效性。N太小，GA會(huì)很差或根本找不出問題的解，因?yàn)樘〉姆N群數(shù)目不能提供足夠的采樣點(diǎn)；N太大，會(huì)增加計(jì)算量，使收斂時(shí)間延長(zhǎng)。一般種群數(shù)目在20～160之間比較合適。(2)交叉概率Pc。此參數(shù)控制著交叉操作的頻率。Pc太大，會(huì)使高適應(yīng)值的結(jié)構(gòu)很快破壞掉；Pc太小，搜索會(huì)停滯不前。一般Pc取0.25～0.85。(3)變異概率Pm。它是增大種群多樣性的第二因素。Pm太小，不會(huì)產(chǎn)生新的基因塊；Pm太大，會(huì)使GA變成隨機(jī)搜索。一般Pm取0.01～0.20。圖4-1遺傳算法流程圖MATLAB中最重要的成分是函數(shù)，下面簡(jiǎn)要地介紹一下SGA庫中主要的函數(shù)及變量。在SGA庫中，經(jīng)常要使用的變量是Pop，它代表一個(gè)種群，是各種遺傳算子操作的對(duì)象。Pop本身是一個(gè)維數(shù)為popsize×itemsize的矩陣。之所以這樣做是考慮到MATLAB處理矩陣的強(qiáng)大能力。矩陣的每一行是一個(gè)維數(shù)為itemsize的向量(數(shù)組)，分別代表一個(gè)染色體。由于向量維數(shù)itemsize理論上可以無限增大，這就保證了染色體的長(zhǎng)度可以根據(jù)需要無限增長(zhǎng)。種群的大小是popsize，即染色體的個(gè)數(shù)。SGA中包含如下3個(gè)實(shí)現(xiàn)基本遺傳算法的函數(shù):Crossop，即交叉算子，以概率Pc在兩染色體上的隨機(jī)位置交換子串，格式為Pop=Crossop(Pop,Pc)，其中參數(shù)Pc代表交叉概率。Muta,即變異算子，以概率Pm對(duì)染色體上任一基因進(jìn)行干擾，格式為Pop=muta(Pop,Pm)，其中Pm代表變異概率。Repro,即繁殖(再生/選擇)算子，基本的選擇策略是采用賭盤模型。賭盤經(jīng)任意旋轉(zhuǎn)停止后指針?biāo)赶騾^(qū)域被選中，所以fi值大的個(gè)體被選中的概率就大。該函數(shù)格式為[Pop,fp]=repro(Pop,fp)。其中fp代表適應(yīng)值(fitness)向量，維數(shù)等于種群大小popsize，fp的第i個(gè)元素對(duì)應(yīng)于Pop的第i行向量，即種群的第i個(gè)染色體的適應(yīng)值。要實(shí)現(xiàn)遺傳算法的功能，還需要以下幾個(gè)重要的函數(shù):Initpop,即初始化種群。函數(shù)格式為Pop=Initpop(popsize,itemsize,m)。式中popsize及itemsize的含義如前所述，字符m是method的縮寫，其含義是產(chǎn)生初始種群的染色體串的方式。在本例中，此參數(shù)取b代表染色體取二進(jìn)制串;此參數(shù)取d代表染色體取十進(jìn)制串。Decode,即解碼函數(shù)。對(duì)應(yīng)于不同的問題域，需定義不同的解碼方式(編碼過程由手工完成)。Fof,即適值填充函數(shù)。函數(shù)格式為fp=fof(pop)，其功能是根據(jù)種群計(jì)算種群的適值向量。這也是一個(gè)和問題求解域緊密聯(lián)系的函數(shù)，需要用戶根據(jù)具體情況編制相應(yīng)的程序。以一個(gè)簡(jiǎn)單的求函數(shù)最值問題為例，說明GA的功能及SGA的可用性。函數(shù)形式取雙峰函數(shù)f(x)=1/[(x-0.3)2+0.01]+1/[(x-0.9)2+0.04]-6，自變量范圍取為[-1,2]。由圖4-2知，當(dāng)x=0.3時(shí)，函數(shù)y=f(x)取最大值96.5;當(dāng)x=0.9時(shí)，y=f(x)取局部極大值21.7。采用GA尋優(yōu)，每個(gè)個(gè)體的基因解碼為自變量x，適值函數(shù)取為400K/(Cmax-f(x))，K為114.3，Cmax=100。種群大小N取20，交叉率Pc取0.6，變異率Pm取0.1。以下是遺傳200代后獲得的結(jié)果。圖4-3顯示了種群中最佳個(gè)體適應(yīng)值增長(zhǎng)的情況。由于在再生算子中保留了父代種群中適值最高的個(gè)體，所以在圖4-4中幾乎看不到適應(yīng)值減小的現(xiàn)象。圖4-4顯示了GA的搜索過程。在一次具有代表性的實(shí)驗(yàn)中，第一代種群中適應(yīng)值最高的染色體經(jīng)解碼后其值為0.55，正好處在函數(shù)圖像中波谷的O點(diǎn)（見圖4-2），此時(shí)GA如向右搜索，則有可能找到一個(gè)局部極大點(diǎn)B，但GA向左搜索則會(huì)成功地找到全局最大點(diǎn)A，充分顯示了GA的全局尋優(yōu)功能。圖4-2雙峰函數(shù)示意圖圖4-3適應(yīng)值增長(zhǎng)情況圖4-4搜索過程圖最大類間方差圖像分割中的遺傳算法由第二章第二節(jié)可知，最大類間方差法所得兩組間方差：d(k)=(4-1)從1-m之間改變k值，求k使得d(k)=max(d(k))，然后，以k為閾值分割圖像，這樣就得到最佳的分割效果。顯然要得到(4-1)式中最大值d(k)，必須對(duì)1-m間所有的灰度值進(jìn)行方差計(jì)算，最后比較得到最大的方差，其計(jì)算量是非常大的，因此有必要尋找一種有效的計(jì)算方法來快速求解。最大類間方差的求解過程，就是在解空間中查找到一個(gè)最優(yōu)的解，使得其方差最大，而遺傳算法能非線快速查找最優(yōu)解K及最大的方差，其步驟如下：(1)為了使用遺傳算法，首先必須對(duì)實(shí)現(xiàn)解空間的數(shù)值編碼，產(chǎn)生染色體單元，由于灰度圖由0～255個(gè)灰度值組成，正好對(duì)應(yīng)著一個(gè)8位二進(jìn)制即一個(gè)字節(jié)，因此使用一個(gè)字節(jié)作為一個(gè)染色體.對(duì)于染色體的解碼正好是編碼的逆過程，就是這個(gè)字節(jié)的10進(jìn)制數(shù)。(2)其次初使化種群，產(chǎn)生一個(gè)規(guī)模為20的染色體種群，并隨機(jī)初始化每一染色體，得到20個(gè)不同的染色體，這個(gè)過程實(shí)際上決定了解的起始值，如果其選取過偏，則會(huì)造成最優(yōu)解收斂慢，計(jì)算時(shí)間長(zhǎng)的缺點(diǎn)，因此本算法采用平均分布方法產(chǎn)生20個(gè)種群。(3)接著對(duì)每一染色體進(jìn)行解碼。由最大類方差的分割閾值方法，可以設(shè)定其方差作為每一染色體的評(píng)價(jià)函數(shù)，即公式(4-1)，染色體得到方差越大，就越有可能逼近最優(yōu)的解。按照公式(4-1)的定義求出每一染色體的適應(yīng)值，對(duì)于所求的適應(yīng)值，求出每一染色體的選擇概率及累計(jì)概率，產(chǎn)生20個(gè)隨機(jī)數(shù)。選擇出隨機(jī)概率對(duì)應(yīng)的染色體作為遺傳運(yùn)算的一組種子，其中適應(yīng)值大的被選取的可能性大，而適應(yīng)值小的被選取的機(jī)會(huì)少其值對(duì)染色體進(jìn)行優(yōu)勝劣汰的自然選擇，又稱為競(jìng)爭(zhēng)。被選中的染色體作為遺傳種子，進(jìn)行遺傳運(yùn)算，這樣一代一代地進(jìn)行，每一代所得到適應(yīng)值都不相同，新一代中的染色體得到的適應(yīng)值較高，因此其解逼近于最大的值。(4)接下來進(jìn)行遺傳運(yùn)算：首先進(jìn)行雜交運(yùn)算，雜交運(yùn)算就是對(duì)染色體中的某些基因進(jìn)行交換，此過程中為了控制交換的位數(shù)，必須給定一個(gè)交雜率，交雜率越大，其交換的基因越多，其值變化就越快，解的收斂速度就越快，但其值太大，不利于求得最優(yōu)解。本算法對(duì)雜交率進(jìn)行改進(jìn)，給定雜交率為0.8，這樣解迅速向最優(yōu)解收斂，經(jīng)過4代后，修改其雜交率為0.3，雖然解的收斂變慢，但求解平穩(wěn)，較好地保證了最優(yōu)解的穩(wěn)定性。其次進(jìn)行遺傳算法的變異運(yùn)算，變異就是對(duì)種群的每一個(gè)染色中的某些位進(jìn)行異位，其異位的多少由變異率給定，與雜交運(yùn)算同樣的道理，先4代給出0.08，然后改為0.03，這樣得到了新的一代種群，不斷繁衍通過對(duì)實(shí)際圖像試算，一般當(dāng)繁衍達(dá)到10代時(shí)，都能得到最優(yōu)閾值K及最大的方差。由最大類間方差分割算法可知，對(duì)于每一個(gè)灰度值k，必須求得以下幾個(gè)參數(shù)，，，(參照(4-1)式)，不難發(fā)現(xiàn)對(duì)于每一個(gè)表達(dá)式都求出Pi，因此可先求出每個(gè)Pi，由于采用遺傳算法，其求解過程是非線性的，因此不必求出每一個(gè)k對(duì)應(yīng)的，，但對(duì)于最優(yōu)解某一鄰域內(nèi)的值，可能會(huì)重復(fù)計(jì)算，此時(shí)有必要保存已計(jì)算的k對(duì)應(yīng)的，，在下一代的運(yùn)算過程中，對(duì)于已經(jīng)完成的計(jì)算只要取出數(shù)據(jù)不必再計(jì)算了，這樣加快了算法的整體速度。圖像分割遺傳算法的性能分析使用最大類間方差的圖像分割算法，是以圖像的平均灰度值與前后景按概率為權(quán)達(dá)到方差最大的一種分化。要得到好的結(jié)果，一般而言是希望圖像的灰度直方圖成雙峰形狀[12]，然而在實(shí)際處理中圖像是千變?nèi)f化的，其灰度直方圖不一定呈現(xiàn)出雙峰現(xiàn)象，這時(shí)使用傳統(tǒng)方法求出的最佳閾值分割效果不是很理想，造成分割失敗。但是遺傳算法進(jìn)行求解時(shí)是非線的，會(huì)在一個(gè)局部?jī)?nèi)找到一個(gè)最優(yōu)的解代替代全局的最佳解，使用一個(gè)次優(yōu)解來分割圖像，不會(huì)造成圖像的分割失敗，這在圖像實(shí)際處理中是完全允許的。從運(yùn)算時(shí)間來看，最大類間方差的圖像分割算法主要包括了方差計(jì)算與圖像閾值分割運(yùn)算，對(duì)于每一種分割算法，圖像的閾值分割運(yùn)算時(shí)間是一樣，因此其關(guān)鍵是減少方差運(yùn)算的時(shí)間，傳統(tǒng)方法求解最優(yōu)的閾值K，必須對(duì)第一個(gè)灰度值k計(jì)算，2個(gè)量，然后按照公式(4-1)求出方差，當(dāng)所有灰度k值計(jì)算完成后比較找到最大的方差及對(duì)應(yīng)的灰度值k，以k作為最佳閾值分割圖像，設(shè)每一個(gè)灰度計(jì)算方差的時(shí)間為T，則總的計(jì)算時(shí)間為256T。本文所述的遺傳算法進(jìn)行計(jì)算，測(cè)試控制代數(shù)為15代，但從實(shí)驗(yàn)運(yùn)算結(jié)果可以看出，當(dāng)繁衍代數(shù)達(dá)到10代時(shí)，已達(dá)到最佳的結(jié)果，其評(píng)價(jià)函數(shù)也達(dá)到最大的值，從10代以后，其解在最優(yōu)解的左右俳徊，根據(jù)遺傳算法的特點(diǎn)，認(rèn)為此時(shí)的解已經(jīng)達(dá)到了最優(yōu)解，可以終止遺傳運(yùn)算。由實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)可以發(fā)現(xiàn)，此時(shí)只對(duì)50個(gè)灰度級(jí)的值進(jìn)行了計(jì)算，即時(shí)間約為50T，并且遺傳算法可以用于并行計(jì)算，其速度更快。在實(shí)際的圖像處理過程中，為了消除光照的影響，往往采用局部閾值的方法對(duì)圖像進(jìn)行一個(gè)m*n的劃分，對(duì)每個(gè)區(qū)域須求解最大類間方差，采用傳統(tǒng)算法對(duì)每一個(gè)區(qū)域求最大類間方差，即必須對(duì)m*n個(gè)區(qū)域求取最大類間方差，其運(yùn)算時(shí)間很長(zhǎng)，以有256個(gè)灰度級(jí)的大小為1000×1000的圖像為例，若子塊大小為100×100，共有100個(gè)子塊，則需要進(jìn)行25600次方差的計(jì)算，這種大量計(jì)算，嚴(yán)重影響到圖像分割任務(wù)的執(zhí)行[8]。而采用本文介紹的遺傳算法只要修改染色體的結(jié)構(gòu)，便可以同時(shí)對(duì)m*n個(gè)區(qū)域進(jìn)行計(jì)算，其算法的時(shí)間與總體閾值方法所用時(shí)間相當(dāng)。顯然，對(duì)于局部閾值分割算法，遺傳算法的速度將大大優(yōu)于傳統(tǒng)的算法。實(shí)驗(yàn)結(jié)果分析使用遺傳算法進(jìn)行最大類間方差的圖像分割，實(shí)際上是利用遺傳算法的快速優(yōu)化算法來求解最大的方差及對(duì)應(yīng)的閾值K。對(duì)圖4-5進(jìn)行最大類間方差的閾值計(jì)算并進(jìn)行圖像分割，得到了很好的結(jié)果。遺傳算法計(jì)算方差時(shí)是非線性的，從表1中4個(gè)圖像的計(jì)算可知，整個(gè)計(jì)算中只對(duì)200個(gè)灰度進(jìn)行了計(jì)算，并且對(duì)某些灰度方差的計(jì)算是重復(fù)的，因此對(duì)這些灰度只要計(jì)算一次即可。下表4-1為本算法與傳統(tǒng)算法的比較。表4-1本算法與傳統(tǒng)算法計(jì)算次數(shù)與閾值比較圖像代數(shù)本算法傳統(tǒng)算法方差計(jì)算次數(shù)閾值方差計(jì)算次數(shù)閾值110501082561082105010325610331050100256100410508025680圖4-5原始圖像的直方圖圖4-6原始圖像圖4-7繁衍到第三代的效果圖圖4-8結(jié)果圖圖4-9局部閾值分割結(jié)果圖本章小結(jié)本章是論文的核心部分，首先介紹了基于MATLAB軟件平臺(tái)的遺傳算法的實(shí)現(xiàn)，遺傳算法算子在MATLAB中的表達(dá)形式和編程的流程。隨后，由最大類間方差公式作為適應(yīng)度函數(shù)，編制遺傳算法的程序，確定各算子的參數(shù)。最后對(duì)算法的性能和結(jié)果圖進(jìn)行了詳細(xì)地分析和對(duì)比，可看出算法在搜索全局解和局部最優(yōu)解方面的優(yōu)越性。結(jié)論本文研究了最大類方差法的圖像分割，基于遺傳算法快速求出其閾值，實(shí)現(xiàn)了灰度分割。本文首先對(duì)灰度分割的基礎(chǔ)知識(shí)作了一個(gè)簡(jiǎn)單的介紹，包括灰度分割的方法和灰度門限的確定，著重于最大類間方差法的討論。隨后系統(tǒng)闡述了遺傳算法的算子、應(yīng)用步驟和性能特點(diǎn)。最后用MATLAB軟件平臺(tái)實(shí)現(xiàn)了圖像的分割，并作了性能分析。遺傳算法作為一種全局優(yōu)化算法正在得到廣泛的應(yīng)用，在MATLAB環(huán)境下用MATLAB語言編制了一個(gè)基本的圖像處理程序，并以實(shí)際圖像為應(yīng)用例子說明了SGA庫的應(yīng)用及遺傳算法的全局優(yōu)化效果。由于MATLAB軟件包強(qiáng)大的仿真功能以及良好的可擴(kuò)充性，在MATLAB環(huán)境下使用SGA庫，是對(duì)遺傳算法進(jìn)行仿真研究的一個(gè)有力工具。改進(jìn)后的遺傳算法用于最大類間方差閾值分割圖像時(shí)，非線性快速且穩(wěn)定地求解最大類間方差及對(duì)應(yīng)的灰度閾值，可以有效地提高圖像閾值分割的速度及性能，通過幾組圖像的對(duì)比可看出算法的優(yōu)越性，并且對(duì)于局部閾值分割算法，遺傳算法的速度將大大優(yōu)于傳統(tǒng)的算法。同時(shí)遺傳算法具有快速并行的運(yùn)算能力，從而實(shí)現(xiàn)對(duì)圖像分割并行計(jì)算，因此遺傳算法在圖像處理中具有廣泛的用途。由于編程經(jīng)驗(yàn)有限，所以程序的完整性和通用性都受到了限制，并且實(shí)用性有限，理論探討方面尚待改進(jìn)。但在完成設(shè)計(jì)的過程中本人學(xué)習(xí)到圖像處理方面的寶貴知識(shí)，對(duì)遺傳算法和其他一些人工智能理論的算法產(chǎn)生了濃厚的興趣。在今后的工作和學(xué)習(xí)中將繼續(xù)進(jìn)行更深入的研究。哈爾濱工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）致謝衷心感謝關(guān)宇東老師在畢業(yè)設(shè)計(jì)期間對(duì)我的指導(dǎo)和關(guān)心。本人在完成本科畢業(yè)設(shè)計(jì)期間，關(guān)老師經(jīng)常給予關(guān)心和幫助，親自來實(shí)驗(yàn)室進(jìn)行指導(dǎo)，定期檢查設(shè)計(jì)情況，并且細(xì)致的檢查了我的論文初稿，提出了寶貴的意見。衷心感謝106實(shí)驗(yàn)室的師兄和師姐對(duì)我的關(guān)心和幫助，特別感謝祿曉飛師兄對(duì)我本次設(shè)計(jì)的悉心指導(dǎo)，他嚴(yán)謹(jǐn)?shù)墓ぷ鲬B(tài)度和和廣博的專業(yè)知識(shí)令我受益匪淺。衷心感謝吳芝路老師和任廣輝老師為我提供了良好的實(shí)驗(yàn)室環(huán)境。衷心感謝應(yīng)用電子技術(shù)教研室的其他老師。衷心感謝在畢業(yè)設(shè)計(jì)期間所有關(guān)心和幫助過我的家人和朋友們。參考文獻(xiàn)MasaharuMunetomo，DavidE.Goldberg．AGeneticAlgorithmUsingLinkageidentificationbyNonlinearityCheck．InformationandDataAnalysis．1999Jean-PhilippeRennard，Ph.D．GeneticAlgorithmViewer:DemonstrationofaGeneticAlgorithm．IntrodutiontoGeneticAlgorithms．2000DanielL.Swets，BillPunch，JohnWeng．GeneticAlgorithmsforObjectRecognitioninaComplexScene．IEEE，1995K.R.Castleman．DigitalImageProcessing．PrenticeHall，1996：387-418周明，孫樹棟．遺傳算法原理及應(yīng)用．國防工業(yè)出版社，1998：18-65孫兆林．MATLAB6.X圖像處理．清華大學(xué)出版社，2002：240-263邢文訓(xùn)，謝金星．現(xiàn)代計(jì)算方法．清華大學(xué)出版社，1999：140-165王小平，曹立明．遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)．西安交通大學(xué)出版社，2002：235-251玄光男，程潤(rùn)偉．遺傳算法與工程設(shè)計(jì)．科學(xué)出版社，2000：5-15張文修，梁怡．遺傳算法的數(shù)學(xué)基礎(chǔ)．西安交通大學(xué)出版社，1999：146-176谷峰，吳勇，唐?。z傳算法的改進(jìn)．微機(jī)發(fā)展．2003，13(6)：80-82吳玲艷，沈庭芝，方子文．基于直方圖熵和遺傳算法的圖像分割法．兵工學(xué)報(bào)．1999，20(3)：255-258吳成才，劉靖，徐正科．圖像分割的遺傳算法方法．西安電子科技大學(xué)學(xué)報(bào)．996，23(1)：34-41謝勤嵐，陳紅，陶秋生MATLAB遺傳算法工具箱的設(shè)計(jì)．計(jì)算機(jī)與數(shù)字工程．2003，31(3)：37-40附錄1英文文獻(xiàn)翻譯遺傳算法縱觀：遺傳算法的論證遺傳算法導(dǎo)論物理學(xué)、生物學(xué)、經(jīng)濟(jì)學(xué)或社會(huì)學(xué)經(jīng)常需要處理最優(yōu)解問題。尤其是經(jīng)濟(jì)學(xué)已經(jīng)變成了該領(lǐng)域的專長(zhǎng)，總體來說，18世紀(jì)的一大部分?jǐn)?shù)學(xué)的發(fā)展都與這個(gè)課題有關(guān)（想一想那些重復(fù)出現(xiàn)的問題，比如求函數(shù)的導(dǎo)數(shù)來獲得極限值）。純分解方法已廣泛地證明了它的效率，然而它卻存在一個(gè)不可逾越弱點(diǎn)：實(shí)際情況很少遵循教授所給出的完美的微分函數(shù)。其它的方法，數(shù)學(xué)分析和隨機(jī)搜索已經(jīng)出現(xiàn)了。設(shè)想在一個(gè)多山的地區(qū)分散一些小的機(jī)器人。這些小機(jī)器人能夠找到最有效的路徑，當(dāng)一個(gè)機(jī)器人找到一個(gè)最高點(diǎn)，他宣稱他找到了最優(yōu)解。這種方法效率很高，但是并沒有證明最優(yōu)解已找到，每一個(gè)機(jī)器人都可能局限于局部的最優(yōu)解。這種方法只是在縮小搜索空間時(shí)起作用。什么可以把優(yōu)化方法與人工智能結(jié)合在一起呢？進(jìn)化和優(yōu)化現(xiàn)在看一下45,000,000年前的巴塞魚：巴塞魚這種魚正是鯨的始祖，它長(zhǎng)約15米、重5噸，它還有一個(gè)準(zhǔn)獨(dú)立的頭和后足，它呈波狀行動(dòng)，獵取小動(dòng)物，它的祖先的足退化成有肘關(guān)節(jié)的小的鰭狀肢。在這樣粘稠的水中行動(dòng)非常困難，需要付出很大的努力。人們必須有足夠的能力來移動(dòng)和控制它的蹤跡，這種魚的祖先其實(shí)不適合游泳。為了適應(yīng)環(huán)境。一種雙重現(xiàn)象發(fā)生了：由肘關(guān)節(jié)連接的手臂縮短，構(gòu)成鰭狀肢的基本構(gòu)架的手指延伸了。鰭狀肢這幅圖顯示了普通海豚的其中兩根手指過度肥大以至于對(duì)其它手指不利。巴塞魚是獵食性動(dòng)物，需要迅速和準(zhǔn)確。在這段時(shí)間里，它呈現(xiàn)出長(zhǎng)的手指和短的手臂，他們可以比從前行動(dòng)的更快、更精準(zhǔn)，因此壽命變長(zhǎng)并產(chǎn)生更多后代。同時(shí)，依據(jù)普遍的空氣動(dòng)力學(xué)原理其它的進(jìn)化也隨之發(fā)生了，比如從頭到腳的一體化、體形的進(jìn)化、尾鰭力量的增強(qiáng)……最后，進(jìn)化出適應(yīng)于水生環(huán)境的完美的物種。這種適應(yīng)過程，形態(tài)學(xué)上的優(yōu)化是非常完美的，以至于今天發(fā)現(xiàn)了鯊魚、海豚與潛水艇的相似性，但其源頭是起源于泥盆紀(jì)的一種軟骨魚類，在這之后才出現(xiàn)了哺乳動(dòng)物的雛形，即鯨類的祖先。因此達(dá)爾文的機(jī)械系統(tǒng)產(chǎn)生了一種優(yōu)化進(jìn)程，是針對(duì)魚類和其他水生動(dòng)物的流體力學(xué)最優(yōu)進(jìn)程以及翼龍、鳥和蝙蝠的空氣動(dòng)力學(xué)最優(yōu)進(jìn)程。這一觀察資料是遺傳算法的基礎(chǔ)。進(jìn)化和遺傳算法在60年代初來自于密歇根大學(xué)的John.Holland開始了它在遺傳算法方面的研究工作。第一個(gè)成就是1975年《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性》的出版。Holland有兩個(gè)目標(biāo)：改進(jìn)自然系統(tǒng)自適應(yīng)性進(jìn)程的認(rèn)識(shí)，實(shí)際一個(gè)有類似于自然系統(tǒng)特性的人工系統(tǒng)?；舅枷肴缦拢阂粋€(gè)給定的種群的遺傳庫潛在的包含了一個(gè)給定的自適應(yīng)性問題的解，或者說一個(gè)更好的解。這個(gè)解不是自動(dòng)生成的，因?yàn)樗蕾嚨幕蚣弦恍﹤€(gè)體所分割。只有不同基因組的配對(duì)才能得出解。簡(jiǎn)單的說，可以舉這個(gè)例子，巴塞魚的爪的縮短和手指的延長(zhǎng)是被兩個(gè)基因所控制。每一個(gè)個(gè)體有一個(gè)基因組，但是在復(fù)制和交叉過程中，新的基因組合產(chǎn)生了，最后，一個(gè)個(gè)體能夠從他們的父代繼承好的基因：它的爪現(xiàn)在是一個(gè)鰭狀肢。Holland方法是很有效是因?yàn)樗粌H考慮到了變異的作用（便已很少改變算法），而且它利用了基因的重組，（交叉）：這些重組，部分解的交叉大大改進(jìn)了算法逼近的能力，最終找到最佳值。遺傳算法的機(jī)能舉例來說，即將進(jìn)入一個(gè)簡(jiǎn)化遺傳的世界。有相聯(lián)系