基于爬山算法的基因芯片圖像網(wǎng)格定位畢業(yè)設(shè)計(jì)

1、基于爬山算法的基因芯片圖像網(wǎng)格定位摘要 劃格是準(zhǔn)確定位基因芯片圖像中雜交熒光樣點(diǎn)并提取樣點(diǎn)雜交強(qiáng)度信息必不可少的步驟，本文實(shí)現(xiàn)了一種基于爬山法的基因芯片圖像自動(dòng)劃格算法。爬山算法是一種局部擇優(yōu)的方法，采用啟發(fā)式方法，是對(duì)深度優(yōu)先搜索的一種改進(jìn)，它利用反饋信息幫助生成解的決策，屬于人工智能算法的一種。文中介紹了基因芯片圖像預(yù)處理和爬山算法的相關(guān)知識(shí)，并介紹了運(yùn)用爬山算法對(duì)基因芯片圖像進(jìn)行網(wǎng)格定位的方法，最后在matlab軟件上編程實(shí)現(xiàn)，完成了對(duì)基因芯片的網(wǎng)格定位。運(yùn)用該種方法對(duì)多幅基因芯片圖像進(jìn)行實(shí)驗(yàn)，都取得了不錯(cuò)的網(wǎng)格定位效果。實(shí)驗(yàn)表明，該算法能有效地對(duì)基因芯片點(diǎn)陣圖像進(jìn)行劃格。關(guān)鍵詞：爬山算

2、法 基因芯片圖像 網(wǎng)格定位gene chip image grid localization based on genetic algorithmabstract gridding is the essential step of accurate positioning fluorescent hybridization samples and extracted the information of hybridization intensity samples from microarray image. this paper proposed a aotomatic gridding

3、and spot quantification technique based on hill-climbing approach,which tackes a microarray image as input. hill-climbing apprach is a method select the best from part, using heuristic methods, is a improvement the depth-first search, and it uses feedback information to help calculate the solution,w

4、hich is belong to artificial intelligence algorithm. this paper introduces the gene chip image preprocessing algorithms and the knowledge of hill-climbing apprach,and alse introduces how to use the climbing apprach to grid and quantify the spot of the gene chip image, at the final, programming and c

5、omplete gridding spot quantification of gene chips in matlab. several gene chip images experiments using this apprach result good. experiments show that this algorithm can effectively grid the microarray image.key words：hill-climbing approach gene chip image grid location目 錄摘要iiabstract .iii目 錄iv第一章

6、 引言- 1 -1.1選題背景- 1 -1.2網(wǎng)格定位的主要方法- 1 -1.3 本論文的主要工作- 2 -第二章 基因芯片圖像預(yù)處理- 3 -2.1 基因芯片圖像的去噪處理- 3 -2.2 中值濾波- 3 -2.2.1 中值濾波原理- 3 -2.2.2 中值濾波的主要特征- 4 -2.3 自適應(yīng)中值濾波- 5 -2.3.1 自適應(yīng)中值濾波原理- 6 -2.3.2 自適應(yīng)中值濾波在基因芯片圖像中的應(yīng)用- 6 -第三章 爬山法- 8 -3.1 爬山算法簡介- 8 -3.2 爬山算法的一般描述- 8 -3.3 爬山算法的優(yōu)缺點(diǎn)- 9 -第四章 基因芯片圖像網(wǎng)格定位的實(shí)現(xiàn)- 10 -4.1基因芯片網(wǎng)

7、格定位的一般原理- 10 -4.2 基于爬山算法的劃格原理- 12 -4.2.1目標(biāo)加權(quán)函數(shù)- 12 -4.2.2 爬山算法搜索樣本點(diǎn)- 13 -4.2.3 劃網(wǎng)格- 15 -4.3 基因芯片網(wǎng)格定位結(jié)果- 15 -4.4實(shí)驗(yàn)中的不足之處- 26 -結(jié)論- 27 -致謝語- 28 -參考文獻(xiàn)- 29 -第一章 引言1.1選題背景隨著人類基因組計(jì)劃的不斷推進(jìn), 對(duì)基因有效快速的檢測(cè)變得越來越重要。基因芯片技術(shù)以其可同時(shí)、快速、準(zhǔn)確地分析大量基因組信息的特點(diǎn)而具有重大實(shí)用價(jià)值1。芯片技術(shù)可以廣泛應(yīng)用在疾病診斷、藥物篩選及基因測(cè)序等生命科學(xué)領(lǐng)域。因此，以基因芯片為代表的生物芯片技術(shù)的深入研究和廣泛應(yīng)

8、用，將對(duì)21世紀(jì)人類生活和健康產(chǎn)生極其深遠(yuǎn)的影響。在基因芯片技術(shù)中,芯片分析是至關(guān)重要的一個(gè)環(huán)節(jié),分析的可靠性、準(zhǔn)確性直接影響芯片的推廣應(yīng)用?；蛐酒c經(jīng)過熒光標(biāo)記的樣品雜交后, 產(chǎn)生熒光圖像?；蛐酒綔y(cè)到的信息就包含在每一個(gè)探針的熒光強(qiáng)度中。要進(jìn)行芯片分析,首要任務(wù)就是進(jìn)行網(wǎng)格定位, 也就是將基因芯片的探針與基因芯片的熒光圖像的各區(qū)域建立對(duì)應(yīng)關(guān)系?？梢哉f,網(wǎng)格定位是進(jìn)行后續(xù)芯片分析的前提?；蛐酒瑧?yīng)用的整個(gè)過程如下圖1.1所示，與圖像處理相關(guān)的工作處于整個(gè)過程的末端，屬于數(shù)據(jù)分析2。分析基因芯片圖像，即熒光圖像處理的目的是為了獲取每個(gè)靶位點(diǎn)的探針強(qiáng)度或比率，然后聯(lián)系所打印的克隆靶基因的信息

9、，就可以容易地解釋結(jié)果，并進(jìn)一步進(jìn)行高層次的分析3。芯片設(shè)計(jì)芯片制備雜交試驗(yàn)數(shù)據(jù)分析圖1.1 基因芯片應(yīng)用過程1.2網(wǎng)格定位的主要方法目前，用于基因芯片圖像網(wǎng)格定位的方法主要有半自動(dòng)網(wǎng)格定位、基于爬山算法的網(wǎng)格定位算法、基于數(shù)學(xué)形態(tài)的網(wǎng)格定位方法、基于圖像投影的網(wǎng)格定位方法和基于遺傳算法的自動(dòng)網(wǎng)格定位等幾種。(1) 基于投影的網(wǎng)格定位方法。該方法將分析目標(biāo)鎖定于基因芯片圖像的投影信號(hào)上,從而將二維圖像處理問題轉(zhuǎn)化為一維數(shù)字信號(hào)處理問題，大大減少了算法的復(fù)雜度4。(2) 半自動(dòng)網(wǎng)格定位。該方法在芯片點(diǎn)陣數(shù)不多的情況下具有直觀與快速的特點(diǎn), 但是隨著芯片點(diǎn)陣數(shù)的增加, 該方法不僅費(fèi)時(shí)而且精確度下降

10、, 因而不適應(yīng)大規(guī)模、高密度基因芯片圖像的分析。(3) 基于遺傳算法的網(wǎng)格定位方法5。該方法利用遺傳算法的優(yōu)點(diǎn)進(jìn)行圖像的網(wǎng)格定位，具有很大程度上的自動(dòng)性, 主要的不足在于計(jì)算量較大，比較耗時(shí)。(4) 基于數(shù)學(xué)形態(tài)的網(wǎng)格定位方法。該方法的基本思想是利用一個(gè)稱作結(jié)構(gòu)元素的“探針”手機(jī)信號(hào)的信息，探針在信號(hào)中不斷移動(dòng)即可考察信號(hào)各個(gè)部分之間的相互關(guān)系，并提取有用信息分析與描述信號(hào)特征。(5) 基于爬山算法的網(wǎng)格定位方法。利用局部搜索求解最優(yōu)解，找出所有斑點(diǎn)的中心進(jìn)行網(wǎng)格定位，能精確找出所有斑點(diǎn)的中心。1.3 本論文的主要工作本文使用基于爬山算法的基因芯片圖像自動(dòng)劃格，并在matlab工具上實(shí)現(xiàn)，其過

11、程如圖1.2所示?；蛐酒瑘D像預(yù)處理爬山算法搜索畫線，完成定位圖像去噪局部最優(yōu)點(diǎn)樣本點(diǎn)尺寸所有樣本點(diǎn)圖1.2 基于爬山算法的網(wǎng)格定位過程本論文具體工作如下：第一章為緒論部分。第二章論述圖像預(yù)處理的相關(guān)理論知識(shí)。采用中值濾波的方法對(duì)基因芯片圖像進(jìn)行去噪。第三章論述爬山算法的相關(guān)理論知識(shí)。主要闡述了爬山算法中的一些概念，以及爬山算法的基本流程。第四章為程序?qū)崿F(xiàn)部分。運(yùn)用爬山算法在matlab軟件上編程實(shí)現(xiàn)對(duì)基因芯片圖像的網(wǎng)格定位。第二章 基因芯片圖像預(yù)處理2.1 基因芯片圖像的去噪處理基因芯片在制作過程中，受到多方面因素的干擾，圖像會(huì)被一些可見或不可見的噪聲“污染”，這些噪聲將對(duì)自動(dòng)網(wǎng)格定位造成負(fù)

12、面影響。在網(wǎng)格定位之前先對(duì)圖像進(jìn)行去噪處理是非常有必要的，也是基因芯片應(yīng)用過程中的一個(gè)很重要的步驟。圖像去噪的方法有很多，目前常用的有均值濾波、中值濾波、維納濾波、圖像小波域?yàn)V波6、形態(tài)學(xué)濾波7和低通濾波等。每一種方法都有其各自的適用性特點(diǎn)。中值濾波作為當(dāng)前應(yīng)用最廣的濾波方法之一，能夠克服線性濾波器所帶來的圖像細(xì)節(jié)模糊，并且對(duì)濾除脈沖干擾及圖像掃描噪聲有很好的效果。此外，在實(shí)際運(yùn)算過程中并不需要圖像的統(tǒng)計(jì)特征，這也帶來了不少方便8。本節(jié)將介紹中值濾波，并在中值濾波的基礎(chǔ)上進(jìn)行改進(jìn)，用自適應(yīng)中值濾波算法對(duì)圖像進(jìn)行去噪處理。2.2 中值濾波中值濾波是一種非線性濾波，對(duì)隨機(jī)輸入信號(hào)的嚴(yán)格數(shù)學(xué)分析比較

13、復(fù)雜，它首先是被應(yīng)用于一維信號(hào)處理技術(shù)中，后來被二維圖像信號(hào)處理技術(shù)所引用。在應(yīng)用上，中值濾波有很多的優(yōu)點(diǎn)。但是對(duì)一些細(xì)節(jié)多，特別是點(diǎn)、線、尖頂細(xì)節(jié)多的圖像不宜采用中值濾波的方法。下面我們對(duì)中值濾波的原理進(jìn)行介紹。2.2.1 中值濾波原理所謂“中值”就是指將一個(gè)數(shù)據(jù)序列中的數(shù)據(jù)按照從大到小(或者相反)的順序排列，如果這個(gè)序列的長度為奇數(shù)，則排在中間的那個(gè)數(shù)就是此序列的中值；如果數(shù)據(jù)序列的長度是偶數(shù)，可以定義處于中間兩個(gè)數(shù)的平均數(shù)為中值。因此，中值濾波最簡單的辦法就是用一個(gè)含有奇數(shù)點(diǎn)的條形或方形滑動(dòng)窗口在被處理的圖像上逐點(diǎn)滑動(dòng)，將窗口正中那個(gè)點(diǎn)的值用窗口內(nèi)各點(diǎn)灰度的中指代替9。假設(shè)窗口內(nèi)有五點(diǎn)，

14、其值分別為70，90，180，120，130。那么此窗口內(nèi)中值即為120。一般地，設(shè)有一個(gè)一維序列，取窗口長度為 (為奇數(shù))，對(duì)此一維序列進(jìn)行中值濾波，就是從輸入序列中相繼抽出個(gè)數(shù)；其中為窗口的中心點(diǎn)值， 。再將這個(gè)點(diǎn)值按其數(shù)值大小排序，取其序號(hào)為正中間那個(gè)數(shù)作為濾波輸出。用數(shù)學(xué)公式表示為： （2-1）式中 ，。采用條形窗口的方法是一維中值濾波，將這種方法推廣到二維，采用方形窗口，就形成二維中值濾波。二維中值濾波可由式（2-2）表示 （2-2）式中 濾波器窗口； 二維數(shù)據(jù)序列。窗口的尺寸。二維中值濾波的窗口形狀和尺寸設(shè)計(jì)對(duì)濾波效果影響較大。不同的圖像內(nèi)容和不同的應(yīng)用要求，往往采用不同的窗口形狀

15、和尺寸。常用的二維中值濾波窗口形狀有線狀、方形、圓形、十字形以及圓環(huán)形等。窗口尺寸一般先用3，再取5，逐點(diǎn)增大，直到其濾波效果滿意為止。一般來說，對(duì)于有緩變的較長輪廓物體的圖像，采用方形或圓形窗口為宜；對(duì)于包含有尖頂角物體的圖像，適宜采用十字形窗口。濾波窗口大小的選擇，一般以不超過圖像中最小有效物體的尺寸為宜。使用二維中值濾波需注意的是要保持圖像中有效的細(xì)線物體。 (a)3 3窗口 (b)55窗口 (c)“圓”形窗口 (d)“十”字形窗口圖2.1 二維中值濾波器的不同窗口選擇2.2.2 中值濾波的主要特征(1)對(duì)某些輸入信號(hào)中值濾波的不變性對(duì)某些特定的輸入信號(hào)，如在窗口內(nèi)單調(diào)增加或單調(diào)減少的序

16、列，中值濾波輸出信號(hào)仍保持輸入信號(hào)不變，即 （2-3）或 （2-4）則有 （2-5） 二維中值濾波的不變性要復(fù)雜些，它不但與輸入信號(hào)有關(guān)，而且還與窗口形狀有關(guān)。一般來說，與窗口對(duì)頂角連線垂直的邊緣保持不變性。利用這個(gè)特點(diǎn)，可以使中值濾波既能去除圖像的噪聲，又能保持圖像中一些物體的邊緣。 對(duì)于一些周期性的數(shù)據(jù)序列，中值濾波也存在著不變性。例如，下列一維周期性二值序列 若設(shè)窗口長度為9，則中值濾波對(duì)此序列保持不變性。對(duì)于二維周期序列不變性，如周期網(wǎng)狀圖案，分析起來就更復(fù)雜了，可以通過實(shí)驗(yàn)改變窗口形狀和尺寸來獲得。 (2)中值濾波去噪聲性能 中值濾波是非線性運(yùn)算，因此對(duì)于隨機(jī)性質(zhì)的噪聲輸入數(shù)學(xué)分析是

17、相當(dāng)復(fù)雜的。對(duì)于零均值正態(tài)分布的噪聲輸入，中值濾波輸出的噪聲方差可以近似為9 （2-6）式中 輸入噪聲功率（方差）； 輸入噪聲均值； 中值濾波窗口長度； 輸入噪聲密度函數(shù)。（3）中值濾波的頻譜特性 由于中值濾波是非線性運(yùn)算，在輸入與輸出之間的頻譜上不存在一一對(duì)應(yīng)的關(guān)系。故不能用一般線性濾波器頻率特性的研究方法。設(shè)g為輸入信號(hào)頻譜，f為輸出信號(hào)頻譜，定義 （2-7）為中值濾波器的頻率響應(yīng)特性，h與g有關(guān)。2.3 自適應(yīng)中值濾波中值濾波的去噪效果依賴于濾波窗口的大小及參與中值計(jì)算的像素點(diǎn)數(shù)目9 ，對(duì)于不考慮圖像特征在不同位置之間的差異的情況，中值濾波會(huì)有比較好的效果。但在有些應(yīng)用中，需要使用能夠根

18、據(jù)被濾波區(qū)域的圖像特征自適應(yīng)的濾波器來改進(jìn)圖像6，鑒于此，下面我們來考慮自適應(yīng)中值濾波算法。自適應(yīng)中值濾波算法是對(duì)中值濾波的一種改進(jìn),相對(duì)于中值濾波而言,它能夠處理空間密度更大的沖激噪聲,并且平滑非沖激噪聲時(shí),還可保存更多的圖像細(xì)節(jié)10。2.3.1 自適應(yīng)中值濾波原理其原理10-11詳細(xì)說明如下：設(shè)表示一個(gè)將要被處理的子圖像，其中心在處，為允許的最大自適應(yīng)濾波器窗口的尺寸。令表示中的最小亮度值；表示中的最大亮度值；表示中的亮度中值；表示坐標(biāo)處的亮度值。自適應(yīng)中值濾波器算法工作在兩個(gè)層次,分別定義為和，即：若,則轉(zhuǎn)向，否則增加窗口尺寸；若窗口尺寸，則重復(fù)，否則輸出 。：若，則輸出；否則輸出 。用

19、來判斷是否為一脈沖，用來判斷是否為一脈沖。如果和zxy都不是脈沖，則算法就利用輸出一個(gè)不變的像素值來代替鄰域中值作為輸出,以避免不必要的細(xì)節(jié)損失。為了改進(jìn)標(biāo)準(zhǔn)中值濾波算法處理空間密度較大的沖激噪聲能力不足的問題，自適應(yīng)中值濾波算法采用了通過擴(kuò)大窗口來相對(duì)地減少?zèng)_激噪聲空間密度的這一策略。2.3.2 自適應(yīng)中值濾波在基因芯片圖像中的應(yīng)用圖2.2中的幾幅圖是用中值濾波和自適應(yīng)中值濾波算法以及取不同值時(shí)的去噪結(jié)果之間的比較。 (a)原始圖像 (b)中值濾波后的圖像 (c)自適應(yīng)中值濾波后的圖像 (d)自適應(yīng)中值濾波后的圖像圖2.2中值濾波去噪后的實(shí)驗(yàn)結(jié)果由實(shí)驗(yàn)結(jié)果可以看出，自適應(yīng)中值濾波算法與傳統(tǒng)的

20、中值濾波算法相比，保持了點(diǎn)的尖銳性及其細(xì)節(jié),有明顯的改進(jìn)。第三章 爬山法3.1 爬山算法簡介爬山算法是利用向目標(biāo)函數(shù)值增加（減少）的方向持續(xù)移動(dòng)的簡單循環(huán)過程來搜索局部極大（極?。┲档囊环N局部擇優(yōu)搜索算法13，該搜索算法簡單有效，并成功地解決許多最優(yōu)化問題，該算法首先要選擇能精確估計(jì)問題解的啟發(fā)信息，然后才能更快獲得最優(yōu)解。3.2 爬山算法的一般描述 function hill-climbing(problem) returns a state that is a local maximum inputs: problem, a problem local variables: current

21、, a node neighbor, a node current - make-node(initial-stateproblem) loop do neighbor - a highest-valued successor of current if valueneighbor= valuecurrent then return statecurrent current - neighbor算法解釋： 從當(dāng)前的節(jié)點(diǎn)開始，和周圍的鄰居節(jié)點(diǎn)的值進(jìn)行比較。 如果當(dāng)前節(jié)點(diǎn)是最大的，那么返回當(dāng)前節(jié)點(diǎn)，作為最大值(即山峰最高點(diǎn))；反之就用最高的鄰居節(jié)點(diǎn)來，替換當(dāng)前節(jié)點(diǎn)，從而實(shí)現(xiàn)向山峰的高處攀爬的目的。

22、如此循環(huán)直到達(dá)到最高點(diǎn)。爬山算法的流程圖如下：開始與周圍節(jié)點(diǎn)比較當(dāng)前節(jié)點(diǎn)是否最大結(jié)束是以最大點(diǎn)為當(dāng)前節(jié)點(diǎn)選擇開始節(jié)點(diǎn)否圖3.1 爬山算法流程圖3.3 爬山算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn) 避免遍歷，通過啟發(fā)選擇部分節(jié)點(diǎn)，從而達(dá)到提高效率的目的。 缺點(diǎn) 因?yàn)椴皇侨嫠阉?，所以結(jié)果可能不是最佳。 爬山算法一般存在以下問題： 1）、局部最大：某個(gè)節(jié)點(diǎn)比周圍任何一個(gè)鄰居都高，但是它卻不是整個(gè)問題的最高點(diǎn)。 2）、高地：也稱為平頂，搜索一旦到達(dá)高地，就無法確定搜索最佳方向，會(huì)產(chǎn)生隨機(jī)走動(dòng)，使得搜索效率降低。 3）、山脊：搜索可能會(huì)在山脊的兩面來回震蕩，前進(jìn)步伐很小。第四章 基因芯片圖像網(wǎng)格定位的實(shí)現(xiàn)以上章節(jié)中我們介紹了

23、基因芯片圖像預(yù)處理的相關(guān)知識(shí)，并且介紹了爬山算法的相關(guān)理論知識(shí)，本章節(jié)中，我們主要借助于matlab工具用爬山算法實(shí)現(xiàn)對(duì)基因芯片圖像的網(wǎng)格定位。4.1基因芯片網(wǎng)格定位的一般原理在一個(gè)制作完成的基因芯片中，包含著許多的信號(hào)點(diǎn)，對(duì)其中的一個(gè)信號(hào)點(diǎn)進(jìn)行網(wǎng)格定位，我們需要確定四條線，如下圖4.1所示：d embed equation.3 a embed equation.3 c embed equation.3 b embed equation.3 下邊界左邊界右邊界上邊界圖4.1 基因點(diǎn)分割示意圖在圖4.1中，我們將圖中的黑點(diǎn)看作是信號(hào)點(diǎn)，當(dāng)我們確定了上邊界、下邊界、左邊界以及右邊界以后，我們就完成

24、了對(duì)這個(gè)信號(hào)點(diǎn)的網(wǎng)格定位。在完成了對(duì)基因芯片中所有信號(hào)點(diǎn)的網(wǎng)格定位以后，便實(shí)現(xiàn)了基因芯片的網(wǎng)格定位14?，F(xiàn)假設(shè)我們需要對(duì)圖4.2中的基因芯片進(jìn)行網(wǎng)格定位。由于一個(gè)制作完成并經(jīng)過校正后的基因芯片具有以下優(yōu)點(diǎn)12：（1）基因點(diǎn)在水平方向上呈水平排列，且在豎直方向上呈垂直排列；（2）各基因點(diǎn)間的距離大致相等。圖4.2 基因芯片因此，我們可以利用以上優(yōu)點(diǎn)，對(duì)基因芯片采取以下網(wǎng)格定位方法：確定樣本中心位置；：確定水平方向上網(wǎng)格線的距離，通過可以同時(shí)確定出水平方向上其他的的網(wǎng)格線；：確定出豎直方向上網(wǎng)格線的距離，通過可以同時(shí)確定出豎直方向上其他的網(wǎng)格線。在完成以上三步之后，該基因芯片的網(wǎng)格定位便完成了。定

25、位效果如下圖4.3所示：圖4.3 網(wǎng)格定位效果圖 通過以上的理論介紹，可以看出，要完成對(duì)一幅已經(jīng)過校正的基因芯片圖像的網(wǎng)格定位，我們現(xiàn)在所需要做的工作就是確定樣本點(diǎn)中心位置，以及距離和。4.2 基于爬山算法的劃格原理本算法利用目標(biāo)函數(shù)和爬山算法的一系列步驟來搜索基因芯片圖像中的網(wǎng)格線，具體分為以下兩步：（1） 利用加權(quán)目標(biāo)函數(shù)從芯片圖像中任意r個(gè)像素開始通過爬山算法搜索樣本點(diǎn)的大?。颖军c(diǎn)寬度）；（2）利用所獲得的樣本點(diǎn)寬度值和一個(gè)遞歸算法來對(duì)芯片圖像中的所有樣本點(diǎn)進(jìn)行劃格，在遞歸算法中，通過在樣本點(diǎn)范圍內(nèi)用爬山算法搜索局部極大值來修正樣本點(diǎn)寬度值15。圖4.4為本劃格算法完整流程圖。開始求局

26、部極值搜索水平樣本點(diǎn)搜索垂直樣本點(diǎn)樣本點(diǎn)尺寸搜索全部樣本點(diǎn)水平網(wǎng)格線檢測(cè)垂直網(wǎng)格線檢測(cè)結(jié)束圖4.4 基于爬山算法的網(wǎng)格定位過程4.2.1目標(biāo)加權(quán)函數(shù)設(shè)圖像子塊為b=bij，i=1nh，j=1mh, bijz+ ，xij=xij,yijt是第i行j列的像素點(diǎn)的坐標(biāo)，即xij是第i行j列的像素點(diǎn)在圖像子圖b中的相對(duì)位置。目標(biāo)函數(shù)以圖像子塊的像素灰度矩陣為輸入?yún)?shù)，以圖像子塊內(nèi)各像素到圖像子塊中心點(diǎn)距離作為隨機(jī)變量，通過計(jì)算每個(gè)像素的概率分布來計(jì)算圖像子塊的能量，最常用的概率分布函數(shù)有以下3種：均勻分布函數(shù)、指數(shù)分布函數(shù)和正態(tài)分布函數(shù)。(1) 均勻分布目標(biāo)函數(shù)：假設(shè)每個(gè)像素點(diǎn)服從二元均與分布，即每個(gè)

27、像素點(diǎn)具有相等的權(quán)值，b的目標(biāo)函數(shù)值按如下公式計(jì)算：即圖像子塊b的目標(biāo)函數(shù)值等于圖像子塊b內(nèi)所有像素點(diǎn)的灰度值之和。(2) 指數(shù)分布目標(biāo)函數(shù)：首先估算圖像子塊的分布中心c=nb/2,mb/2t,然后計(jì)算圖像子塊內(nèi)各像素xij到圖像子塊中心的距離：dij=(c-x)t (c-x)t，假設(shè)dij為一指數(shù)隨機(jī)變量，則加權(quán)目標(biāo)函數(shù)值按如下公式計(jì)算： 其中，是分布參數(shù)。 (3) 正態(tài)分布目標(biāo)函數(shù)：假設(shè)加權(quán)目標(biāo)函數(shù)服從二元正態(tài)分布，其均值為 c，協(xié)方差矩陣為：則目標(biāo)函數(shù)值按如下公式計(jì)算：該函數(shù)唯一的參數(shù)是方差以上所討論的是3個(gè)最常用的統(tǒng)計(jì)分布函數(shù)，雖然有許多目標(biāo)函數(shù)可以用，但是為了簡便起見，本算法使用指數(shù)

28、分布目標(biāo)函數(shù)。4.2.2 爬山算法搜索樣本點(diǎn)第一步，利用爬山算法搜索目標(biāo)函數(shù)的局部極大值來定位樣本點(diǎn)：從任意r個(gè)不開始點(diǎn)，以g為掃描范圍，每隔s個(gè)像素掃描一個(gè)nb*mb子矩陣塊，對(duì)子矩陣塊求目標(biāo)函數(shù)值(即子矩陣塊灰度總和)，再以最大值點(diǎn)為中心，nb*mb范圍內(nèi)每個(gè)像素點(diǎn)的目標(biāo)函數(shù)值，函數(shù)值最大的點(diǎn)即為初始最大值點(diǎn)。r個(gè)開始點(diǎn)有r個(gè)初始最大值點(diǎn)。開始點(diǎn)的x和y最表至少相差g個(gè)像素（本算法中設(shè)掃描范圍g=41，s=10，nb、mb取15）。圖示如下：開始點(diǎn)（x,y）位于中心圖像子塊b掃描范圍g(x+20,y+20)圖4.5 起始點(diǎn)求局部極大值點(diǎn)第二步，水平(垂直)掃描，找出水平(垂直)方向上峰值的

29、位置：從初始最大值點(diǎn)開始，先水平向左，再水平向右，求局部極大值點(diǎn)，得到一組峰值點(diǎn)位置數(shù)組hpeak，垂直方向上以同樣方法可得到數(shù)組vpeak。第三步，找出所有樣本點(diǎn)中心：通過計(jì)算hpeak或vpeak中峰值位置差異來估計(jì)“樣本點(diǎn)”寬度，因此，第i(i=1, , r)個(gè)起始點(diǎn)位置的平均樣本點(diǎn)寬度計(jì)算如下：r個(gè)初始最大值點(diǎn)都計(jì)算一遍后，可得r個(gè)，就可計(jì)算出水平方向上的均值(同樣可得垂直方向的均值)：利用以上得到的均值，從任意一個(gè)初始最大值點(diǎn)開始，水平向左(向右)掃描個(gè)像素，搜索局部最大值點(diǎn)，當(dāng)一行結(jié)束后，再利用，對(duì)垂直方向做類似操作。因此就可得樣本點(diǎn)的坐標(biāo)矩陣c=cij中，其中cij=xij, y

30、ijt。4.2.3 劃網(wǎng)格利用以上說得的樣本點(diǎn)中心坐標(biāo)矩陣c，對(duì)橫坐標(biāo)xij構(gòu)造直方圖，直方圖中每一個(gè)峰值對(duì)應(yīng)一列樣本點(diǎn)中心的精確坐標(biāo)，方法為：y,x=max(hist)，讀取直方圖的峰值y及峰值對(duì)應(yīng)坐標(biāo)x，將坐標(biāo)x存進(jìn)數(shù)組，然后將這一座峰對(duì)應(yīng)c的值設(shè)為0，再次構(gòu)造直方圖，一直循環(huán)，直到峰值為0。兩相鄰峰值的中點(diǎn)處就是一條列網(wǎng)格。同樣的方法可以得到行網(wǎng)格。4.3 基因芯片網(wǎng)格定位結(jié)果基于以上原理，我們用爬山算法進(jìn)行網(wǎng)格定位。在用matlab編程實(shí)現(xiàn)的過程中，需要設(shè)置幾個(gè)重要的參數(shù)。根據(jù)實(shí)驗(yàn)用圖的具體情況，相關(guān)參數(shù)的設(shè)置如下表一所示：表4.1 網(wǎng)格定位參數(shù)設(shè)置表參數(shù)值掃描范圍g41步長s8子圖塊

31、大?。╪b* mb）15*15開始點(diǎn)個(gè)數(shù)r1按照上表設(shè)置參數(shù)，完成基因芯片的網(wǎng)格定位，網(wǎng)格定位結(jié)果如下圖4.6、圖4.7所示：圖4.6.1 所有樣本點(diǎn)中心初步估計(jì)圖4.6.2 基因芯片網(wǎng)格定位結(jié)果在圖4.6的結(jié)果中，我們可以看到，運(yùn)用爬山算法，基因芯片有很好的網(wǎng)格定位效果。通過以上的理論分析，可以看出，在整個(gè)網(wǎng)格定位過程中，影響定位結(jié)果的參數(shù)有二個(gè)，即：s，nb*mb?，F(xiàn)在，我們對(duì)同一幅基因芯片圖像在定位過程中的這二個(gè)參數(shù)按照表二、表三進(jìn)行不同的設(shè)置，結(jié)果與圖4.6對(duì)比。表4.2 s取不同參數(shù)對(duì)比圖4.7圖4.8圖4.9g414141s101214nb*mb15*1515*1515*15同參數(shù)

32、對(duì)比圖4.7.1圖4.7.2圖4.8.1 圖4.8.2圖4.9.1圖4.9.2由以上對(duì)比可以看出，步長s為8、10、12時(shí)，都能準(zhǔn)確定位劃格，s為14時(shí)已不能準(zhǔn)確定位。說明步長s太大時(shí)不能準(zhǔn)確找到樣本點(diǎn)中心，同時(shí)步長s太小時(shí)，又會(huì)加大計(jì)算量。表三 nb*mb取不同參數(shù)對(duì)比圖4.10圖4.11圖4.12g414141s888nb*mb11*1113*1317*17圖4.10.1圖4.10.2圖4.11.1圖4.11.2圖4.12.1圖4.12.2由以上對(duì)比可以看出，圖像子塊b大小選取也會(huì)影響結(jié)果，取11*11時(shí)不能準(zhǔn)確定位，取17*17時(shí)，結(jié)果也有小部分變形。將該定位方法運(yùn)用在其他幾幅基因芯片圖

33、像上，并根據(jù)圖片具體情況設(shè)置好參數(shù)，定位效果如圖4.13、圖4.14所示。圖4.13.1圖4.13.2圖4.14.1圖4.14.2通過圖4.13、圖4.14可以看出，對(duì)于不同的基因芯片圖像，該方法同樣取得了不錯(cuò)的網(wǎng)格定位效果，這說明爬山算法在基因芯片網(wǎng)格定位方面具有很好的適用性能。4.4實(shí)驗(yàn)中的不足之處本實(shí)驗(yàn)通過爬山算法對(duì)基因芯片進(jìn)行網(wǎng)格定位，初步達(dá)到了實(shí)驗(yàn)效果，但是其中的不足之處也再所難免，現(xiàn)將主要的不足之處闡述如下，以便于在以后的繼續(xù)研究中進(jìn)行改進(jìn)。（1）本實(shí)驗(yàn)中的優(yōu)化工作做的還不是很完善，以至于在實(shí)驗(yàn)運(yùn)行過程中耗用的時(shí)間比較長。（2）由于本文論述的方法主要針對(duì)經(jīng)過校正后的基因芯片，所以可

34、以加入校正基因芯片的相關(guān)內(nèi)容，以使整個(gè)定位過程更加的完整。（3）可以考慮采用其他圖片預(yù)處理的方法，使經(jīng)過預(yù)處理后的基因芯片圖像效果更好，這樣網(wǎng)格定位的效果也相應(yīng)的會(huì)更好。結(jié)論圖像處理與分析是基因芯片技術(shù)應(yīng)用的關(guān)鍵，如何做好圖像處理與分析工作是目前基因芯片技術(shù)應(yīng)用中主要研究的內(nèi)容。基因芯片在制作過程中，由于受到多方面因素的干擾，難免會(huì)帶有噪聲，這對(duì)后期的芯片分析和信息提取等工作造成了很多負(fù)面的影響。在進(jìn)行芯片分析之前先對(duì)噪聲進(jìn)行處理會(huì)使分析結(jié)果更加準(zhǔn)確可靠。將基因芯片圖像進(jìn)行二值化處理，可以減小圖像的數(shù)據(jù)量，使得分析過程更加簡潔快速。通過去噪和二值化，先對(duì)基因芯片圖像進(jìn)行預(yù)處理，在基因芯片分析過

35、程中顯得很有必要。爬山算法是一種局部擇優(yōu)的方法，采用啟發(fā)式方法，是對(duì)深度優(yōu)先搜索的一種改進(jìn)，它利用反饋信息幫助生成解的決策，屬于人工智能算法的一種。由于上述優(yōu)點(diǎn)，爬山算法已被廣泛應(yīng)用于工程設(shè)計(jì)優(yōu)化中。利用爬山算法對(duì)基因芯片圖像進(jìn)行網(wǎng)格定位，是一種行之有效的方法。本論文的實(shí)驗(yàn)結(jié)果也正說明了這一點(diǎn)。本論文主要利用爬山算法完成對(duì)基因芯片圖像的網(wǎng)格定位。論文中所用的方法原理簡單，便于編程實(shí)現(xiàn)，具有簡捷直觀的優(yōu)點(diǎn)，而且效果也同樣很理想。在對(duì)多幅圖像進(jìn)行實(shí)驗(yàn)后，發(fā)現(xiàn)這種方法適用性也很強(qiáng)。由于時(shí)間和作者水平的限制，論文中以及實(shí)驗(yàn)過程中還存在很多不足之處，對(duì)基于爬山算法的基因芯片圖像網(wǎng)格定位的研究也還不夠深入。本課題是針對(duì)具體的基因芯片進(jìn)行研究的，實(shí)驗(yàn)中各參數(shù)也是根據(jù)具體圖片的特征人工進(jìn)行設(shè)定的，這使得該方法不具備很好的自動(dòng)性。因此，一種更合理的而且自動(dòng)性強(qiáng)的網(wǎng)格定位方法將成為以后在這方面努力的方向。致謝語本論文是在導(dǎo)師xxx的悉心關(guān)懷和精心指導(dǎo)下完成的。無論是論文的選題，還是在研究中的各個(gè)階段，x教授都給予了大量的幫助，并提出了很多寶貴的意見。在論文完成之際，在此向xxx表示衷心地感謝。并對(duì)老師淵博的學(xué)識(shí)和嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度表示最崇高的敬意。同時(shí)，也感謝xx學(xué)姐給予我的幫助。學(xué)姐的幫助對(duì)于我論文工作的順利完成有著重要的作用。對(duì)于學(xué)姐的耐心也表達(dá)我的