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

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

2、lt;p><b>　　學(xué) 院：</b></p><p><b>　　系：</b></p><p>　　專 業(yè)： 年級(jí)：</p><p><b>　　學(xué) 號(hào)：</b></p><p>　　指導(dǎo)教師（校內(nèi)）：

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

4、對(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)行劃格。</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>　　第二章 基因芯片圖像預(yù)處理- 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 自適應(yīng)中值濾波- 5 -</p><p>　　2.3.1 自適應(yīng)中值濾波原理-

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

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

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

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

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

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

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

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

19、方法利用遺傳算法的優(yōu)點(diǎn)進(jìn)行圖像的網(wǎng)格定位，具有很大程度上的自動(dòng)性, 主要的不足在于計(jì)算量較大，比較耗時(shí)。</p><p>　　(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)特征。</p><p>　　(5) 基于爬山算法的網(wǎng)格定位方法。利用局部搜索求解最

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

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

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

23、波[6]、形態(tài)學(xué)濾波[7]和低通濾波等。每一種方法都有其各自的適用性特點(diǎn)。</p><p>　　中值濾波作為當(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)行去噪處理。</p><

24、p><b>　　2.2 中值濾波</b></p><p>　　中值濾波是一種非線性濾波，對(duì)隨機(jī)輸入信號(hào)的嚴(yán)格數(shù)學(xué)分析比較復(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)行介紹。</p><p>　　2.2.

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

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

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

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

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

30、</p><p>　　圖2.1 二維中值濾波器的不同窗口選擇</p><p>　　2.2.2 中值濾波的主要特征</p><p>　　(1)對(duì)某些輸入信號(hào)中值濾波的不變性</p><p>　　對(duì)某些特定的輸入信號(hào)，如在窗口內(nèi)單調(diào)增加或單調(diào)減少的序列，中值濾波輸出信號(hào)仍保持輸入信號(hà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;　　二維中值濾波的不變性要復(fù)雜些，它不但與輸入信號(hào)有關(guān)，而且還與窗口形狀有關(guān)。一般來說，與窗口對(duì)頂角連線垂直的邊緣保持不變性。利用這個(gè)特點(diǎn)，可以使中值濾波既能去除圖像的噪聲，又能保持圖像中一些物體的邊緣。</p><p>　　對(duì)于一些周期性的數(shù)據(jù)序列，中值濾波也存在著不變性。例如，下列一維周期性二值序列</p><p>　　若設(shè)窗口長(zhǎng)度為9，則中值濾波對(duì)此序列保持不變性。對(duì)于二維周期序

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

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

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

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

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

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

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

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

41、gt;　　第三章 爬山法</b></p><p>　　3.1 爬山算法簡(jiǎn)介</p><p>　　爬山算法是利用向目標(biāo)函數(shù)值增加（減少）的方向持續(xù)移動(dòng)的簡(jiǎn)單循環(huán)過程來搜索局部極大（極?。┲档囊环N局部擇優(yōu)搜索算法[13]，該搜索算法簡(jiǎn)單有效，并成功地解決許多最優(yōu)化問題，該算法首先要選擇能精確估計(jì)問題解的啟發(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>　　從當(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)向山峰的高處攀爬的目的。如此循環(huán)直到達(dá)到最高點(diǎn)。</p><p>　　爬山算法的流程圖如下：</p><p>　　3.3 爬山算法的優(yōu)缺點(diǎn)</p><p><b

46、>　　優(yōu)點(diǎn) </b></p><p>　　避免遍歷，通過啟發(fā)選擇部分節(jié)點(diǎn)，從而達(dá)到提高效率的目的。 </p><p><b>　　缺點(diǎn) </b></p><p>　　因?yàn)椴皇侨嫠阉?，所以結(jié)果可能不是最佳。 </p><p>　　爬山算法一般存在以下問題： </p><p>　　

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

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

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

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

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

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

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

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

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

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

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

58、一個(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）。圖示如下：</p><p>　　第二步，水平(垂直)掃描，找出水平(垂直)方向上峰值的位置：從初始最大值點(diǎn)開始，先水平向左，再水平

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

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

61、中心坐標(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)格。</p><p>　　4.3 基因芯片網(wǎng)格定位結(jié)果</p><p>　　基于

62、以上原理，我們用爬山算法進(jìn)行網(wǎng)格定位。在用MATLAB編程實(shí)現(xiàn)的過程中，需要設(shè)置幾個(gè)重要的參數(shù)。根據(jù)實(shí)驗(yàn)用圖的具體情況，相關(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 所有樣本點(diǎn)中心初步估計(jì)<

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

64、比。</p><p>　　表4.2 s取不同參數(shù)對(duì)比</p><p><b>　　同參數(shù)對(duì)比</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>　　由以上對(duì)比可以看出，步長(zhǎng)s為8、10、12時(shí)，都能準(zhǔn)確定位劃格，s為14時(shí)已不能準(zhǔn)確

66、定位。說明步長(zhǎng)s太大時(shí)不能準(zhǔn)確找到樣本點(diǎn)中心，同時(shí)步長(zhǎng)s太小時(shí)，又會(huì)加大計(jì)算量。</p><p>　　表三 nb*mb取不同參數(shù)對(duì)比</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>　　由以上對(duì)比可以看出，圖像子塊B大小選取也會(huì)影響結(jié)果，取11*11時(shí)不能準(zhǔn)確定位，取17*1

68、7時(shí)，結(jié)果也有小部分變形。</p><p>　　將該定位方法運(yùn)用在其他幾幅基因芯片圖像上，并根據(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可以看出，對(duì)于不同的基因芯片圖像，該方法同樣取得了不錯(cuò)的網(wǎng)格定位效果，這說明爬山算法在基因芯片網(wǎng)格定位方面具有很好的適用性能。</p><p>　　4.4實(shí)驗(yàn)中的不足之處</p><p>

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

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

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

73、方法，是對(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)。</p><p>　　本論文主要利用爬山算法完成對(duì)基因芯片圖像的網(wǎng)格定位。論文中所用的方法原理簡(jiǎn)單，便于編程實(shí)現(xiàn)，具有簡(jiǎn)捷直觀的優(yōu)點(diǎn)，而且效果也同樣很理想。在對(duì)多幅圖像進(jìn)行實(shí)驗(yàn)后

74、，發(fā)現(xiàn)這種方法適用性也很強(qiáng)。</p><p>　　由于時(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)格定位方法將成為以后在這方面努力的方向。</p><p><

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

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

77、東南大學(xué)學(xué)報(bào)，2000,30(5)：1-6.</p><p>　　[3] 學(xué)位論文:李軼博.基于遺傳算法和變形模板的基因芯片圖像網(wǎng)格定位方法[D].河北,河北工業(yè)大學(xué),2004.</p><p>　　[4] 期刊:劉國(guó)傳,伯曉晨,王升啟,陸琳.生物芯片圖像分析的研究進(jìn)展[J].中國(guó)醫(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è)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2005,34(4):63—66.</p>

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

80、p><p>　　[10] 期刊:袁西霞,岳建華,趙賢任.MATLAB在中值濾波改進(jìn)算法中的應(yīng)用[J].廣東工業(yè)大學(xué)學(xué)報(bào),2007,24(1):33--35</p><p>　　[11] 專著:張汗靈.MATLAB在圖像處理中的應(yīng)用[M].北京:清華大學(xué)出版社,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] 蔡瑞英，李長(zhǎng)河. 人工智能 [M]. 武漢：武漢理工大學(xué)出版社，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