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

1、<p><b>　　本科畢業(yè)論文</b></p><p>　　(科研訓練、畢業(yè)設(shè)計)</p><p>　　題 目：基于爬山法的基因芯片圖像</p><p><b>　　自動劃格算法</b></p><p><b>　　姓 名：</b></p>&

2、lt;p><b>　　學 院：</b></p><p><b>　　系：</b></p><p>　　專 業(yè)： 年級：</p><p><b>　　學 號：</b></p><p>　　指導教師（校內(nèi)）：

3、 職稱：</p><p>　　指導教師（校外）： 職稱：</p><p>　　基于爬山算法的基因芯片圖像網(wǎng)格定位</p><p>　　摘要 劃格是準確定位基因芯片圖像中雜交熒光樣點并提取樣點雜交強度信息必不可少的步驟，本文實現(xiàn)了一種基于爬山法的基因芯片圖像自動劃格算法。爬山算法是一種局部擇優(yōu)的方法，采用啟發(fā)式方法，是

4、對深度優(yōu)先搜索的一種改進，它利用反饋信息幫助生成解的決策，屬于人工智能算法的一種。文中介紹了基因芯片圖像預處理和爬山算法的相關(guān)知識，并介紹了運用爬山算法對基因芯片圖像進行網(wǎng)格定位的方法，最后在MATLAB軟件上編程實現(xiàn)，完成了對基因芯片的網(wǎng)格定位。運用該種方法對多幅基因芯片圖像進行實驗，都取得了不錯的網(wǎng)格定位效果。實驗表明，該算法能有效地對基因芯片點陣圖像進行劃格。</p><p>　　關(guān)鍵詞：爬山算法 基因芯

5、片圖像 網(wǎng)格定位</p><p>　　Gene Chip Image Grid Localization Based on Genetic Algorithm</p><p>　　Abstract Gridding is the essential step of accurate positioning fluorescent hybridization samples and ex

6、tracted the information of hybridization intensity samples from microarray image. This paper proposed a aotomatic gridding and spot quantification technique based on hill-climbing approach,which tackes a microarray image

7、 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 h</p><p>　　Key words：hill-climbin

8、g approach Gene chip image Grid Location</p><p><b>　　目 錄</b></p><p><b>　　摘要II</b></p><p>　　Abstract .III</p><p><b>　　目 錄IV</b>&

9、lt;/p><p>　　第一章 引言- 1 -</p><p>　　1.1選題背景- 1 -</p><p>　　1.2網(wǎng)格定位的主要方法- 1 -</p><p>　　1.3 本論文的主要工作- 2 -</p><p>　　第二章 基因芯片圖像預處理- 3 -</p><p>　　2.1

10、 基因芯片圖像的去噪處理- 3 -</p><p>　　2.2 中值濾波- 3 -</p><p>　　2.2.1 中值濾波原理- 3 -</p><p>　　2.2.2 中值濾波的主要特征- 4 -</p><p>　　2.3 自適應中值濾波- 5 -</p><p>　　2.3.1 自適應中值濾波原理-

11、 6 -</p><p>　　2.3.2 自適應中值濾波在基因芯片圖像中的應用- 6 -</p><p>　　第三章 爬山法- 8 -</p><p>　　3.1 爬山算法簡介- 8 -</p><p>　　3.2 爬山算法的一般描述- 8 -</p><p>　　3.3 爬山算法的優(yōu)缺點- 9 -</

12、p><p>　　第四章 基因芯片圖像網(wǎng)格定位的實現(xiàn)- 10 -</p><p>　　4.1基因芯片網(wǎng)格定位的一般原理- 10 -</p><p>　　4.2 基于爬山算法的劃格原理- 12 -</p><p>　　4.2.1目標加權(quán)函數(shù)- 12 -</p><p>　　4.2.2 爬山算法搜索樣本點- 13 -&

13、lt;/p><p>　　4.2.3 劃網(wǎng)格- 15 -</p><p>　　4.3 基因芯片網(wǎng)格定位結(jié)果- 15 -</p><p>　　4.4實驗中的不足之處- 26 -</p><p><b>　　結(jié)論- 27 -</b></p><p>　　致謝語- 28 -</p>&

14、lt;p>　?。蹍⒖嘉墨I］- 29 -</p><p><b>　　第一章 引言</b></p><p><b>　　1.1選題背景</b></p><p>　　隨著人類基因組計劃的不斷推進, 對基因有效快速的檢測變得越來越重要?；蛐酒夹g(shù)以其可同時、快速、準確地分析大量基因組信息的特點而具有重大實用價值[1]。

15、芯片技術(shù)可以廣泛應用在疾病診斷、藥物篩選及基因測序等生命科學領(lǐng)域。因此，以基因芯片為代表的生物芯片技術(shù)的深入研究和廣泛應用，將對21世紀人類生活和健康產(chǎn)生極其深遠的影響。</p><p>　　在基因芯片技術(shù)中,芯片分析是至關(guān)重要的一個環(huán)節(jié),分析的可靠性、準確性直接影響芯片的推廣應用?；蛐酒c經(jīng)過熒光標記的樣品雜交后, 產(chǎn)生熒光圖像?；蛐酒綔y到的信息就包含在每一個探針的熒光強度中。要進行芯片分析,首要任務就是

16、進行網(wǎng)格定位, 也就是將基因芯片的探針與基因芯片的熒光圖像的各區(qū)域建立對應關(guān)系?？梢哉f,網(wǎng)格定位是進行后續(xù)芯片分析的前提。</p><p>　　基因芯片應用的整個過程如下圖1.1所示，與圖像處理相關(guān)的工作處于整個過程的末端，屬于數(shù)據(jù)分析[2]。分析基因芯片圖像，即熒光圖像處理的目的是為了獲取每個靶位點的探針強度或比率，然后聯(lián)系所打印的克隆靶基因的信息，就可以容易地解釋結(jié)果，并進一步進行高層次的分析[3]。<

17、/p><p>　　圖1.1 基因芯片應用過程</p><p>　　1.2網(wǎng)格定位的主要方法</p><p>　　目前，用于基因芯片圖像網(wǎng)格定位的方法主要有半自動網(wǎng)格定位、基于爬山算法的網(wǎng)格定位算法、基于數(shù)學形態(tài)的網(wǎng)格定位方法、基于圖像投影的網(wǎng)格定位方法和基于遺傳算法的自動網(wǎng)格定位等幾種。</p><p>　　(1) 基于投影的網(wǎng)格定位方法。該方法

18、將分析目標鎖定于基因芯片圖像的投影信號上,從而將二維圖像處理問題轉(zhuǎn)化為一維數(shù)字信號處理問題，大大減少了算法的復雜度[4]。</p><p>　　(2) 半自動網(wǎng)格定位。該方法在芯片點陣數(shù)不多的情況下具有直觀與快速的特點, 但是隨著芯片點陣數(shù)的增加, 該方法不僅費時而且精確度下降, 因而不適應大規(guī)模、高密度基因芯片圖像的分析。</p><p>　　(3) 基于遺傳算法的網(wǎng)格定位方法[5]。該

19、方法利用遺傳算法的優(yōu)點進行圖像的網(wǎng)格定位，具有很大程度上的自動性, 主要的不足在于計算量較大，比較耗時。</p><p>　　(4) 基于數(shù)學形態(tài)的網(wǎng)格定位方法。該方法的基本思想是利用一個稱作結(jié)構(gòu)元素的“探針”手機信號的信息，探針在信號中不斷移動即可考察信號各個部分之間的相互關(guān)系，并提取有用信息分析與描述信號特征。</p><p>　　(5) 基于爬山算法的網(wǎng)格定位方法。利用局部搜索求解最

20、優(yōu)解，找出所有斑點的中心進行網(wǎng)格定位，能精確找出所有斑點的中心。</p><p>　　1.3 本論文的主要工作</p><p>　　本文使用基于爬山算法的基因芯片圖像自動劃格，并在MATLAB工具上實現(xiàn)，其過程如圖1.2所示。</p><p>　　本論文具體工作如下：</p><p><b>　　第一章為緒論部分。</b>

21、;</p><p>　　第二章論述圖像預處理的相關(guān)理論知識。采用中值濾波的方法對基因芯片圖像進行去噪。</p><p>　　第三章論述爬山算法的相關(guān)理論知識。主要闡述了爬山算法中的一些概念，以及爬山算法的基本流程。</p><p>　　第四章為程序?qū)崿F(xiàn)部分。運用爬山算法在MATLAB軟件上編程實現(xiàn)對基因芯片圖像的網(wǎng)格定位。</p><p>　

22、　第二章 基因芯片圖像預處理</p><p>　　2.1 基因芯片圖像的去噪處理</p><p>　　基因芯片在制作過程中，受到多方面因素的干擾，圖像會被一些可見或不可見的噪聲“污染”，這些噪聲將對自動網(wǎng)格定位造成負面影響。在網(wǎng)格定位之前先對圖像進行去噪處理是非常有必要的，也是基因芯片應用過程中的一個很重要的步驟。圖像去噪的方法有很多，目前常用的有均值濾波、中值濾波、維納濾波、圖像小波域濾

23、波[6]、形態(tài)學濾波[7]和低通濾波等。每一種方法都有其各自的適用性特點。</p><p>　　中值濾波作為當前應用最廣的濾波方法之一，能夠克服線性濾波器所帶來的圖像細節(jié)模糊，并且對濾除脈沖干擾及圖像掃描噪聲有很好的效果。此外，在實際運算過程中并不需要圖像的統(tǒng)計特征，這也帶來了不少方便[8]。本節(jié)將介紹中值濾波，并在中值濾波的基礎(chǔ)上進行改進，用自適應中值濾波算法對圖像進行去噪處理。</p><

24、p><b>　　2.2 中值濾波</b></p><p>　　中值濾波是一種非線性濾波，對隨機輸入信號的嚴格數(shù)學分析比較復雜，它首先是被應用于一維信號處理技術(shù)中，后來被二維圖像信號處理技術(shù)所引用。在應用上，中值濾波有很多的優(yōu)點。但是對一些細節(jié)多，特別是點、線、尖頂細節(jié)多的圖像不宜采用中值濾波的方法。下面我們對中值濾波的原理進行介紹。</p><p>　　2.2.

25、1 中值濾波原理</p><p>　　所謂“中值”就是指將一個數(shù)據(jù)序列中的數(shù)據(jù)按照從大到小(或者相反)的順序排列，如果這個序列的長度為奇數(shù)，則排在中間的那個數(shù)就是此序列的中值；如果數(shù)據(jù)序列的長度是偶數(shù)，可以定義處于中間兩個數(shù)的平均數(shù)為中值。因此，中值濾波最簡單的辦法就是用一個含有奇數(shù)點的條形或方形滑動窗口在被處理的圖像上逐點滑動，將窗口正中那個點的值用窗口內(nèi)各點灰度的中指代替[9]。假設(shè)窗口內(nèi)有五點，其值分別為7

26、0，90，180，120，130。那么此窗口內(nèi)中值即為120。</p><p>　　一般地，設(shè)有一個一維序列，取窗口長度為 (為奇數(shù))，對此一維序列進行中值濾波，就是從輸入序列中相繼抽出個數(shù)；其中為窗口的中心點值， 。再將這個點值按其數(shù)值大小排序，取其序號為正中間那個數(shù)作為濾波輸出。用數(shù)學公式表示為：</p><p><b>　　（2-1）</b></p>

27、<p><b>　　式中 ，。</b></p><p>　　采用條形窗口的方法是一維中值濾波，將這種方法推廣到二維，采用方形窗口，就形成二維中值濾波。二維中值濾波可由式（2-2）表示</p><p><b>　　（2-2）</b></p><p>　　式中 ——濾波器窗口；</p><

28、p><b>　　——二維數(shù)據(jù)序列。</b></p><p><b>　　窗口的尺寸。</b></p><p>　　二維中值濾波的窗口形狀和尺寸設(shè)計對濾波效果影響較大。不同的圖像內(nèi)容和不同的應用要求，往往采用不同的窗口形狀和尺寸。常用的二維中值濾波窗口形狀有線狀、方形、圓形、十字形以及圓環(huán)形等。窗口尺寸一般先用3，再取5，逐點增大，直到其濾波

29、效果滿意為止。一般來說，對于有緩變的較長輪廓物體的圖像，采用方形或圓形窗口為宜；對于包含有尖頂角物體的圖像，適宜采用十字形窗口。濾波窗口大小的選擇，一般以不超過圖像中最小有效物體的尺寸為宜。使用二維中值濾波需注意的是要保持圖像中有效的細線物體。</p><p>　　(a)3 ×3窗口 (b)5×5窗口 (c)“圓”形窗口 (d)“十”字形窗口

30、</p><p>　　圖2.1 二維中值濾波器的不同窗口選擇</p><p>　　2.2.2 中值濾波的主要特征</p><p>　　(1)對某些輸入信號中值濾波的不變性</p><p>　　對某些特定的輸入信號，如在窗口內(nèi)單調(diào)增加或單調(diào)減少的序列，中值濾波輸出信號仍保持輸入信號不變，即</p><p><b&

31、gt;　?。?-3）</b></p><p><b>　　或</b></p><p><b>　?。?-4）</b></p><p><b>　　則有</b></p><p><b>　?。?-5）</b></p><p&g

32、t;　　二維中值濾波的不變性要復雜些，它不但與輸入信號有關(guān)，而且還與窗口形狀有關(guān)。一般來說，與窗口對頂角連線垂直的邊緣保持不變性。利用這個特點，可以使中值濾波既能去除圖像的噪聲，又能保持圖像中一些物體的邊緣。</p><p>　　對于一些周期性的數(shù)據(jù)序列，中值濾波也存在著不變性。例如，下列一維周期性二值序列</p><p>　　若設(shè)窗口長度為9，則中值濾波對此序列保持不變性。對于二維周期序

33、列不變性，如周期網(wǎng)狀圖案，分析起來就更復雜了，可以通過實驗改變窗口形狀和尺寸來獲得。</p><p>　　(2)中值濾波去噪聲性能</p><p>　　中值濾波是非線性運算，因此對于隨機性質(zhì)的噪聲輸入數(shù)學分析是相當復雜的。對于零均值正態(tài)分布的噪聲輸入，中值濾波輸出的噪聲方差可以近似為[9]</p><p><b>　　（2-6）</b><

34、/p><p>　　式中 ——輸入噪聲功率（方差）；</p><p>　　——輸入噪聲均值；</p><p>　　——中值濾波窗口長度；</p><p>　　——輸入噪聲密度函數(shù)。</p><p>　?。?）中值濾波的頻譜特性</p><p>　　由于中值濾波是非線性運算，在輸入與輸出之間的頻譜

35、上不存在一一對應的關(guān)系。故不能用一般線性濾波器頻率特性的研究方法。設(shè)G為輸入信號頻譜，F(xiàn)為輸出信號頻譜，定義</p><p><b>　　（2-7）</b></p><p>　　為中值濾波器的頻率響應特性，H與G有關(guān)。</p><p>　　2.3 自適應中值濾波</p><p>　　中值濾波的去噪效果依賴于濾波窗口的大小

36、及參與中值計算的像素點數(shù)目[9] ，對于不考慮圖像特征在不同位置之間的差異的情況，中值濾波會有比較好的效果。但在有些應用中，需要使用能夠根據(jù)被濾波區(qū)域的圖像特征自適應的濾波器來改進圖像[6]，鑒于此，下面我們來考慮自適應中值濾波算法。自適應中值濾波算法是對中值濾波的一種改進,相對于中值濾波而言,它能夠處理空間密度更大的沖激噪聲,并且平滑非沖激噪聲時,還可保存更多的圖像細節(jié)[10]。</p><p>　　2.3.1

37、 自適應中值濾波原理</p><p>　　其原理[10-11]詳細說明如下：</p><p>　　設(shè)表示一個將要被處理的子圖像，其中心在處，為允許的最大自適應濾波器窗口的尺寸。</p><p>　　令表示中的最小亮度值；表示中的最大亮度值；表示中的亮度中值；表示坐標處的亮度值。</p><p>　　自適應中值濾波器算法工作在兩個層次,分別定義

38、為和，即</p><p>　　：若,則轉(zhuǎn)向，否則增加窗口尺寸；若窗口尺寸，則重復，否則輸出 。</p><p>　?。喝?，則輸出；否則輸出 。</p><p>　　用來判斷是否為一脈沖，用來判斷是否為一脈沖。如果和Zxy都不是脈沖，則算法就利用輸出一個不變的像素值來代替鄰域中值作為輸出,以避免不必要的細節(jié)損失。為了改進標準中值濾波算法處理空間密度較大的沖激噪聲能力

39、不足的問題，自適應中值濾波算法采用了通過擴大窗口來相對地減少沖激噪聲空間密度的這一策略。</p><p>　　2.3.2 自適應中值濾波在基因芯片圖像中的應用</p><p>　　圖2.2中的幾幅圖是用中值濾波和自適應中值濾波算法以及取不同值時的去噪結(jié)果之間的比較。</p><p>　　(a)原始圖像

40、 (b)中值濾波后的圖像 </p><p>　　(c)自適應中值濾波后的圖像 (d)自適應中值濾波后的圖像</p><p>　　圖2.2中值濾波去噪后的實驗結(jié)果</p><p>　　由實驗結(jié)果可以看出，自適應中值濾波算法與傳統(tǒng)的中值濾波算法相比，保持了點的尖銳性及其細節(jié),有明顯的改進。</p><p><b&

41、gt;　　第三章 爬山法</b></p><p>　　3.1 爬山算法簡介</p><p>　　爬山算法是利用向目標函數(shù)值增加（減少）的方向持續(xù)移動的簡單循環(huán)過程來搜索局部極大（極小）值的一種局部擇優(yōu)搜索算法[13]，該搜索算法簡單有效，并成功地解決許多最優(yōu)化問題，該算法首先要選擇能精確估計問題解的啟發(fā)信息，然后才能更快獲得最優(yōu)解。</p><p>　　

42、3.2 爬山算法的一般描述</p><p>　　Function hill-climbing(problem) </p><p>　　returns a state that is a local maximum 　　 </p><p>　　inputs: problem, a problem 　　</p><p>　　local vari

43、ables: current, a node 　　 </p><p>　　neighbor, a node 　</p><p>　　current <- MAKE-NODE(INITIAL-STATE[problem]) 　　</p><p>　　loop do 　　</p><p>　　neighbor <- a highest

44、-valued successor of current 　　</p><p>　　if VALUE[neighbor]<= VALUE[current] then return STATE[current] 　　</p><p>　　current <- neighbor</p><p><b>　　算法解釋： </b></

45、p><p>　　從當前的節(jié)點開始，和周圍的鄰居節(jié)點的值進行比較。 如果當前節(jié)點是最大的，那么返回當前節(jié)點，作為最大值(即山峰最高點)；反之就用最高的鄰居節(jié)點來，替換當前節(jié)點，從而實現(xiàn)向山峰的高處攀爬的目的。如此循環(huán)直到達到最高點。</p><p>　　爬山算法的流程圖如下：</p><p>　　3.3 爬山算法的優(yōu)缺點</p><p><b

46、>　　優(yōu)點 </b></p><p>　　避免遍歷，通過啟發(fā)選擇部分節(jié)點，從而達到提高效率的目的。 </p><p><b>　　缺點 </b></p><p>　　因為不是全面搜索，所以結(jié)果可能不是最佳。 </p><p>　　爬山算法一般存在以下問題： </p><p>　　

47、1）、局部最大：某個節(jié)點比周圍任何一個鄰居都高，但是它卻不是整個問題的最高點。 </p><p>　　2）、高地：也稱為平頂，搜索一旦到達高地，就無法確定搜索最佳方向，會產(chǎn)生隨機走動，使得搜索效率降低。 </p><p>　　3）、山脊：搜索可能會在山脊的兩面來回震蕩，前進步伐很小。</p><p>　　第四章 基因芯片圖像網(wǎng)格定位的實現(xiàn)</p>&l

48、t;p>　　以上章節(jié)中我們介紹了基因芯片圖像預處理的相關(guān)知識，并且介紹了爬山算法的相關(guān)理論知識，本章節(jié)中，我們主要借助于MATLAB工具用爬山算法實現(xiàn)對基因芯片圖像的網(wǎng)格定位。</p><p>　　4.1基因芯片網(wǎng)格定位的一般原理</p><p>　　在一個制作完成的基因芯片中，包含著許多的信號點，對其中的一個信號點進行網(wǎng)格定位，我們需要確定四條線，如下圖4.1所示：</p&g

49、t;<p>　　圖4.1 基因點分割示意圖</p><p>　　在圖4.1中，我們將圖中的黑點看作是信號點，當我們確定了上邊界、下邊界、左邊界以及右邊界以后，我們就完成了對這個信號點的網(wǎng)格定位。在完成了對基因芯片中所有信號點的網(wǎng)格定位以后，便實現(xiàn)了基因芯片的網(wǎng)格定位[14]。</p><p>　　現(xiàn)假設(shè)我們需要對圖4.2中的基因芯片進行網(wǎng)格定位。由于一個制作完成并經(jīng)過校正后的

50、基因芯片具有以下優(yōu)點[12]：</p><p>　?。?）基因點在水平方向上呈水平排列，且在豎直方向上呈垂直排列；</p><p>　?。?）各基因點間的距離大致相等。</p><p><b>　　圖4.2 基因芯片</b></p><p>　　因此，我們可以利用以上優(yōu)點，對基因芯片采取以下網(wǎng)格定位方法：</p&g

51、t;<p>　　：確定樣本中心位置；</p><p>　?。捍_定水平方向上網(wǎng)格線的距離，通過可以同時確定出水平方向上其他的的網(wǎng)格線；</p><p>　?。捍_定出豎直方向上網(wǎng)格線的距離，通過可以同時確定出豎直方向上其他的網(wǎng)格線。</p><p>　　在完成以上三步之后，該基因芯片的網(wǎng)格定位便完成了。定位效果如下圖4.3所示：</p>&l

52、t;p>　　通過以上的理論介紹，可以看出，要完成對一幅已經(jīng)過校正的基因芯片圖像的網(wǎng)格定位，我們現(xiàn)在所需要做的工作就是確定樣本點中心位置，以及距離和。</p><p>　　4.2 基于爬山算法的劃格原理</p><p>　　本算法利用目標函數(shù)和爬山算法的一系列步驟來搜索基因芯片圖像中的網(wǎng)格線，具體分為以下兩步：</p><p>　?。?） 利用加權(quán)目標函數(shù)從芯片

53、圖像中任意r個像素開始通過爬山算法搜索樣本點的大小（樣本點寬度）；</p><p>　　（2）利用所獲得的樣本點寬度值和一個遞歸算法來對芯片圖像中的所有樣本點進行劃格，在遞歸算法中，通過在樣本點范圍內(nèi)用爬山算法搜索局部極大值來修正樣本點寬度值[15]。</p><p>　　圖4.4為本劃格算法完整流程圖。</p><p>　　4.2.1目標加權(quán)函數(shù)</p>

54、;<p>　　設(shè)圖像子塊為B={bij}，i=1…nh，j=1…mh, bij∈Z+ ，Xij=[xij,yij]t是第i行j列的像素點的坐標，即Xij是第i行j列的像素點在圖像子圖B中的相對位置。</p><p>　　目標函數(shù)以圖像子塊的像素灰度矩陣為輸入?yún)?shù)，以圖像子塊內(nèi)各像素到圖像子塊中心點距離作為隨機變量，通過計算每個像素的概率分布來計算圖像子塊的能量，最常用的概率分布函數(shù)有以下3種：均勻分

55、布函數(shù)、指數(shù)分布函數(shù)和正態(tài)分布函數(shù)。</p><p>　　(1) 均勻分布目標函數(shù)：假設(shè)每個像素點服從二元均與分布，即每個像素點具有相等的權(quán)值，B的目標函數(shù)值按如下公式計算：</p><p>　　即圖像子塊B的目標函數(shù)值等于圖像子塊B內(nèi)所有像素點的灰度值之和。</p><p>　　(2) 指數(shù)分布目標函數(shù)：首先估算圖像子塊的分布中心C=[nb/2,mb/2]t,然后

56、計算圖像子塊內(nèi)各像素Xij到圖像子塊中心的距離：dij=[(C-X)t (C-X)]t，假設(shè)dij為一指數(shù)隨機變量，則加權(quán)目標函數(shù)值按如下公式計算：</p><p>　　其中，λ是分布參數(shù)。</p><p>　　(3) 正態(tài)分布目標函數(shù)：假設(shè)加權(quán)目標函數(shù)服從二元正態(tài)分布，其均值為 c，協(xié)方差矩陣為：</p><p>　　則目標函數(shù)值按如下公式計算：</p>

57、;<p>　　該函數(shù)唯一的參數(shù)是方差</p><p>　　以上所討論的是3個最常用的統(tǒng)計分布函數(shù)，雖然有許多目標函數(shù)可以用，但是為了簡便起見，本算法使用指數(shù)分布目標函數(shù)。</p><p>　　4.2.2 爬山算法搜索樣本點</p><p>　　第一步，利用爬山算法搜索目標函數(shù)的局部極大值來定位樣本點：從任意r個不開始點，以g為掃描范圍，每隔s個像素掃描

58、一個nb*mb子矩陣塊，對子矩陣塊求目標函數(shù)值(即子矩陣塊灰度總和)，再以最大值點為中心，nb*mb范圍內(nèi)每個像素點的目標函數(shù)值，函數(shù)值最大的點即為初始最大值點。r個開始點有r個初始最大值點。開始點的x和y最表至少相差g個像素（本算法中設(shè)掃描范圍g=41，s=10，nb、mb取15）。圖示如下：</p><p>　　第二步，水平(垂直)掃描，找出水平(垂直)方向上峰值的位置：從初始最大值點開始，先水平向左，再水平

59、向右，求局部極大值點，得到一組峰值點位置數(shù)組hpeak，垂直方向上以同樣方法可得到數(shù)組vpeak。</p><p>　　第三步，找出所有樣本點中心：通過計算hpeak或vpeak中峰值位置差異來估計“樣本點”寬度，因此，第i(i=1, …, r)個起始點位置的平均樣本點寬度計算如下：</p><p>　　r個初始最大值點都計算一遍后，可得r個，就可計算出水平方向上的均值(同樣可得垂直方向的

60、均值)：</p><p>　　利用以上得到的均值，從任意一個初始最大值點開始，水平向左(向右)掃描個像素，搜索局部最大值點，當一行結(jié)束后，再利用，對垂直方向做類似操作。因此就可得樣本點的坐標矩陣C={cij}中，其中cij=[xij, yij]t。</p><p><b>　　4.2.3 劃網(wǎng)格</b></p><p>　　利用以上說得的樣本點

61、中心坐標矩陣C，對橫坐標xij構(gòu)造直方圖，直方圖中每一個峰值對應一列樣本點中心的精確坐標，方法為：[y,x]=max(hist)，讀取直方圖的峰值y及峰值對應坐標x，將坐標x存進數(shù)組，然后將這一座峰對應C的值設(shè)為0，再次構(gòu)造直方圖，一直循環(huán)，直到峰值為0。兩相鄰峰值的中點處就是一條列網(wǎng)格。同樣的方法可以得到行網(wǎng)格。</p><p>　　4.3 基因芯片網(wǎng)格定位結(jié)果</p><p>　　基于

62、以上原理，我們用爬山算法進行網(wǎng)格定位。在用MATLAB編程實現(xiàn)的過程中，需要設(shè)置幾個重要的參數(shù)。根據(jù)實驗用圖的具體情況，相關(guān)參數(shù)的設(shè)置如下表一所示：</p><p>　　表4.1 網(wǎng)格定位參數(shù)設(shè)置表</p><p>　　按照上表設(shè)置參數(shù)，完成基因芯片的網(wǎng)格定位，網(wǎng)格定位結(jié)果如下圖4.6、圖4.7所示：</p><p>　　圖4.6.1 所有樣本點中心初步估計<

63、/p><p>　　圖4.6.2 基因芯片網(wǎng)格定位結(jié)果</p><p>　　在圖4.6的結(jié)果中，我們可以看到，運用爬山算法，基因芯片有很好的網(wǎng)格定位效果。</p><p>　　通過以上的理論分析，可以看出，在整個網(wǎng)格定位過程中，影響定位結(jié)果的參數(shù)有二個，即：s，nb*mb。現(xiàn)在，我們對同一幅基因芯片圖像在定位過程中的這二個參數(shù)按照表二、表三進行不同的設(shè)置，結(jié)果與圖4.6對

64、比。</p><p>　　表4.2 s取不同參數(shù)對比</p><p><b>　　同參數(shù)對比</b></p><p><b>　　圖4.7.1</b></p><p><b>　　圖4.7.2</b></p><p><b>　　圖4.8.1

65、 </b></p><p><b>　　圖4.8.2</b></p><p><b>　　圖4.9.1</b></p><p><b>　　圖4.9.2</b></p><p>　　由以上對比可以看出，步長s為8、10、12時，都能準確定位劃格，s為14時已不能準確

66、定位。說明步長s太大時不能準確找到樣本點中心，同時步長s太小時，又會加大計算量。</p><p>　　表三 nb*mb取不同參數(shù)對比</p><p><b>　　圖4.10.1</b></p><p><b>　　圖4.10.2</b></p><p><b>　　圖4.11.1</

67、b></p><p><b>　　圖4.11.2</b></p><p><b>　　圖4.12.1</b></p><p><b>　　圖4.12.2</b></p><p>　　由以上對比可以看出，圖像子塊B大小選取也會影響結(jié)果，取11*11時不能準確定位，取17*1

68、7時，結(jié)果也有小部分變形。</p><p>　　將該定位方法運用在其他幾幅基因芯片圖像上，并根據(jù)圖片具體情況設(shè)置好參數(shù)，定位效果如圖4.13、圖4.14所示。</p><p><b>　　圖4.13.1</b></p><p><b>　　圖4.13.2</b></p><p><b>　

69、　圖4.14.1</b></p><p><b>　　圖4.14.2</b></p><p>　　通過圖4.13、圖4.14可以看出，對于不同的基因芯片圖像，該方法同樣取得了不錯的網(wǎng)格定位效果，這說明爬山算法在基因芯片網(wǎng)格定位方面具有很好的適用性能。</p><p>　　4.4實驗中的不足之處</p><p>

70、;　　本實驗通過爬山算法對基因芯片進行網(wǎng)格定位，初步達到了實驗效果，但是其中的不足之處也再所難免，現(xiàn)將主要的不足之處闡述如下，以便于在以后的繼續(xù)研究中進行改進。</p><p>　?。?）本實驗中的優(yōu)化工作做的還不是很完善，以至于在實驗運行過程中耗用的時間比較長。</p><p>　?。?）由于本文論述的方法主要針對經(jīng)過校正后的基因芯片，所以可以加入校正基因芯片的相關(guān)內(nèi)容，以使整個定位過程

71、更加的完整。</p><p>　　（3）可以考慮采用其他圖片預處理的方法，使經(jīng)過預處理后的基因芯片圖像效果更好，這樣網(wǎng)格定位的效果也相應的會更好。</p><p><b>　　結(jié)論</b></p><p>　　圖像處理與分析是基因芯片技術(shù)應用的關(guān)鍵，如何做好圖像處理與分析工作是目前基因芯片技術(shù)應用中主要研究的內(nèi)容。</p><

72、;p>　　基因芯片在制作過程中，由于受到多方面因素的干擾，難免會帶有噪聲，這對后期的芯片分析和信息提取等工作造成了很多負面的影響。在進行芯片分析之前先對噪聲進行處理會使分析結(jié)果更加準確可靠。將基因芯片圖像進行二值化處理，可以減小圖像的數(shù)據(jù)量，使得分析過程更加簡潔快速。通過去噪和二值化，先對基因芯片圖像進行預處理，在基因芯片分析過程中顯得很有必要。</p><p>　　爬山算法是一種局部擇優(yōu)的方法，采用啟發(fā)式

73、方法，是對深度優(yōu)先搜索的一種改進，它利用反饋信息幫助生成解的決策，屬于人工智能算法的一種。由于上述優(yōu)點，爬山算法已被廣泛應用于工程設(shè)計優(yōu)化中。利用爬山算法對基因芯片圖像進行網(wǎng)格定位，是一種行之有效的方法。本論文的實驗結(jié)果也正說明了這一點。</p><p>　　本論文主要利用爬山算法完成對基因芯片圖像的網(wǎng)格定位。論文中所用的方法原理簡單，便于編程實現(xiàn)，具有簡捷直觀的優(yōu)點，而且效果也同樣很理想。在對多幅圖像進行實驗后

74、，發(fā)現(xiàn)這種方法適用性也很強。</p><p>　　由于時間和作者水平的限制，論文中以及實驗過程中還存在很多不足之處，對基于爬山算法的基因芯片圖像網(wǎng)格定位的研究也還不夠深入。本課題是針對具體的基因芯片進行研究的，實驗中各參數(shù)也是根據(jù)具體圖片的特征人工進行設(shè)定的，這使得該方法不具備很好的自動性。因此，一種更合理的而且自動性強的網(wǎng)格定位方法將成為以后在這方面努力的方向。</p><p><

75、b>　　致謝語</b></p><p>　　本論文是在導師XXX的悉心關(guān)懷和精心指導下完成的。無論是論文的選題，還是在研究中的各個階段，X教授都給予了大量的幫助，并提出了很多寶貴的意見。在論文完成之際，在此向XXX表示衷心地感謝。并對老師淵博的學識和嚴謹?shù)闹螌W態(tài)度表示最崇高的敬意。</p><p>　　同時，也感謝XX學姐給予我的幫助。學姐的幫助對于我論文工作的順利完成有

76、著重要的作用。對于學姐的耐心也表達我的欽佩之情。</p><p><b>　?。蹍⒖嘉墨I］</b></p><p>　　[1] 期刊:李興珊,孫嘯,袁春偉.基于遺傳算法的基因芯片圖像網(wǎng)格定位[J].生物物理學報，2002,18(2):223—226.</p><p>　　[2] 期刊:孫嘯，王曄，張曉莉等．基因芯片設(shè)計及數(shù)據(jù)分析軟件系統(tǒng)[J]．

77、東南大學學報，2000,30(5)：1-6.</p><p>　　[3] 學位論文:李軼博.基于遺傳算法和變形模板的基因芯片圖像網(wǎng)格定位方法[D].河北,河北工業(yè)大學,2004.</p><p>　　[4] 期刊:劉國傳,伯曉晨,王升啟,陸琳.生物芯片圖像分析的研究進展[J].中國醫(yī)療器械雜志,2007,31(2):108.</p><p>　　[5] 期刊:Che

78、e M, Yang R, Hubbel, etal. Accessing genetic information with high density DNA arrays[J]. Science ,1996,274(5287):610～613.</p><p>　　[6] 期刊:寧媛,李皖.圖像去噪的幾種方法分析比較[J].貴州工業(yè)大學學報(自然科學版)，2005,34(4):63—66.</p>

79、<p>　　[7] 期刊:許暖,凌玉華,楊欣榮,廖力清.基于數(shù)學形態(tài)學的基因芯片圖像濾波[J].生物技術(shù)通訊,2006:63—65.</p><p>　　[8] 專著:朱秀昌,劉峰,胡棟.數(shù)字圖像處理與圖像通信[M].北京:北京郵電大學出版社，2008.</p><p>　　[9] 專著:唐良瑞,馬明全,景曉軍等.圖像處理實用技術(shù)[M].北京:化學工業(yè)出版社，2001.</

80、p><p>　　[10] 期刊:袁西霞,岳建華,趙賢任.MATLAB在中值濾波改進算法中的應用[J].廣東工業(yè)大學學報,2007,24(1):33--35</p><p>　　[11] 專著:張汗靈.MATLAB在圖像處理中的應用[M].北京:清華大學出版社,2008.</p><p>　　[12] 期刊:Luis Rueda，Vidya Vidyadharan．A H

81、ill-Climbing Approach for Automatic Gridding of cDNA Microarray Images[J]．IEEE/ACM Transactions on Computational Biology and Bioinformatics，2006,3(1)：72-83．</p><p>　　[13] 蔡瑞英，李長河. 人工智能 [M]. 武漢：武漢理工大學出版社，2003

82、</p><p>　　[14] 期刊:Istepanian Robert S.H. Microarry Image Processing．Current Status and Future Direction[J].IEEE.2003,2(4)：173-174．</p><p>　　[15] vidyadharan v. aotomatic Gridding of DNA Microarr