??? 摘 要： 提出了一種基于LTS Hausdorff距離與遺傳算法" title="遺傳算法">遺傳算法的圖像配準(zhǔn)" title="圖像配準(zhǔn)">圖像配準(zhǔn)方法,。算法首先對(duì)參考圖像和待配準(zhǔn)圖像進(jìn)行壓縮、二值化" title="二值化">二值化和邊緣檢測(cè)" title="邊緣檢測(cè)">邊緣檢測(cè)預(yù)處理，然后在此基礎(chǔ)上結(jié)合遺傳算法對(duì)待配準(zhǔn)圖像進(jìn)行配準(zhǔn)操作,。
??? 關(guān)鍵詞： 圖像配準(zhǔn)? 遺傳算法? LTS Hausdorff距離? 邊緣檢測(cè)? 二值化
???
??? 圖像配準(zhǔn)是圖像處理" title="圖像處理">圖像處理的基本任務(wù)之一,，它的主要作用是將不同時(shí)間,、不同傳感器,、不同視角及不同拍攝條件下獲取的兩幅或多幅圖像進(jìn)行匹配(主要是幾何意義上的)。近年來(lái),，對(duì)圖像配準(zhǔn)技術(shù)的研究涵蓋了多個(gè)應(yīng)用領(lǐng)域,，在計(jì)算機(jī)視覺(jué)、模式化識(shí)別,、醫(yī)學(xué)圖像分析和遙感數(shù)據(jù)處理等學(xué)科中,，圖像配準(zhǔn)技術(shù)均占有舉足輕重的地位，圖像配準(zhǔn)己成為很多研究課題的必備環(huán)節(jié),。
??? 圖像配準(zhǔn)中的一個(gè)關(guān)鍵問(wèn)題是如何利用一種行之有效的方法來(lái)評(píng)價(jià)圖像間的相似程度,。自1991年Daniel P.Huttenlocher與William J.Rucklidge等人提出了一種基于Hausdorff距離的計(jì)算圖像間的相似度的方法[1]后，Hausdorff距離作為一種評(píng)價(jià)兩個(gè)圖形位置關(guān)系的量化標(biāo)準(zhǔn)已被大量應(yīng)用到圖像配準(zhǔn)的研究領(lǐng)域中,，其良好的配準(zhǔn)精度也被大量的實(shí)驗(yàn)和研究所證明,。盡管在圖像配準(zhǔn)中，單純的Hausdorff距離計(jì)算上存在一個(gè)比較大的缺點(diǎn),，即對(duì)于噪聲和孤立點(diǎn)的敏感性,，但由Hausdorrff距離改進(jìn)的LTS（Least Trimmed Square）Hausdorff距離卻可以很好地克服這些問(wèn)題,，因此作為一種改進(jìn)方法,，LTS Hausdorff距離在數(shù)字圖像的配準(zhǔn)中的精確度與穩(wěn)定性都比較理想。
??? 作為一種有效而且實(shí)用的優(yōu)化算法——遺傳算法在很多方面得到了應(yīng)用,。在圖像處理方面,，Chalermwat,、Ghazawi等人將遺傳算法應(yīng)用于圖像的配準(zhǔn)；而B(niǎo)rumby,、Theiler等人則利用遺傳算法進(jìn)行圖像的特征提取,。從他們的實(shí)驗(yàn)結(jié)果來(lái)看，遺傳算法在圖像處理方面具有很好的優(yōu)化效果,。
??? 本文首先將參考圖像與待配準(zhǔn)的圖像進(jìn)行預(yù)處理（圖像的壓縮,、二值化和特征提取）,，以避免在計(jì)算Hausdorff距離時(shí)產(chǎn)生過(guò)大的代價(jià),，然后在此基礎(chǔ)上結(jié)合遺傳算法對(duì)待配準(zhǔn)圖像進(jìn)行配準(zhǔn)操作（平移、旋轉(zhuǎn),、幅度變換）,，最終的目的是通過(guò)遺傳算法搜索到最優(yōu)的平移、旋轉(zhuǎn)和幅度變換參數(shù),。實(shí)驗(yàn)表明,，這種方法可以有效地抵抗在配準(zhǔn)的過(guò)程中產(chǎn)生的噪聲和孤立點(diǎn)的影響，并且在保證一定的配準(zhǔn)精度的前提下可以提高配準(zhǔn)的效率,，算法的健壯性良好,。
1 算法的基本原理
1.1 Hausdorff距離及其改進(jìn)
??? Hausdorff距離是一種極大極小距離，它主要用于測(cè)量?jī)蓚€(gè)點(diǎn)集的匹配程度,。Hausdorff距離的引入使物體匹配基于一種新的測(cè)度,，它能更為有效地表征物體輪廓邊緣之間的相似度。
??? 給定兩個(gè)點(diǎn)集A={a1,，a2,，…，ap}和B={b1,，b2,，…，bp},，則A,、B之間的Hausdorff距離定義如下[2]：
????H(A,B)=max(h(A,B),h(B,A))
??? 式中，
稱為前向的Hausdorff距離,，
稱為后向的Hausdorff距離,，||·||為定義在點(diǎn)集A和B上的某種距離范式，本文使用的是L2范式(歐式距離),。對(duì)于任何兩個(gè)點(diǎn)集A,、B，若H(A,，B)=d,，則表明對(duì)于任何點(diǎn)a∈A,，與B中的任何點(diǎn)b∈B的距離必定不會(huì)超過(guò)d，而且反過(guò)來(lái)對(duì)于B也是成立的,。因此,，Hausdorff距離可以有效地衡量?jī)蓚€(gè)點(diǎn)集(尤其是幾何圖形)間的位置關(guān)系，但是在圖像處理的實(shí)際應(yīng)用中原始的Hausdorff距離在計(jì)算的過(guò)程中存在一個(gè)比較大的缺點(diǎn),，即對(duì)噪聲和孤立點(diǎn)的敏感,，這個(gè)缺點(diǎn)嚴(yán)重影響了圖像配準(zhǔn)的整體準(zhǔn)確性和算法的健壯性。為了克服這一缺點(diǎn),，本文使用的是Hausdorff距離的改進(jìn)形式——LTS Hausdorff距離[3]：
??? 
??? 式中,，H=h×NA，NA為A中的點(diǎn)的個(gè)數(shù),，h∈[0.6,，0.9]，dB(a)(i)表示在從點(diǎn)a到B集合中每個(gè)點(diǎn)的距離中第i大的值,。由公式可以看出,，LTS Hausdorff距離取的并不是最小距離中的最大值，而是用一種排序再求部分均值的方法來(lái)確定A,、B之間的距離,，從而在很大程度上減小了噪聲和孤立點(diǎn)對(duì)精度和穩(wěn)定性的影響。
1.2 遺傳算法
??? 遺傳算法(GA)作為一種求解全局最優(yōu)化的方法,，在許多領(lǐng)域的理論與工程實(shí)踐中都有成功的應(yīng)用,。其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，搜索不依賴于梯度的信息[4],。
??? 遺傳算法使用所謂的遺傳算子（genetic operators）作用于群體P(t)中,，進(jìn)行下述的遺傳操作，從而得到新一代群體P(t+1),。
??? (1)選擇(selection)：根據(jù)每個(gè)個(gè)體的適應(yīng)度,，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體P(t+1),。
??? (2)交叉(crossover)：將群體P(t)內(nèi)的每個(gè)個(gè)體隨即搭配成對(duì),，對(duì)每一對(duì)個(gè)體，以某個(gè)概率（稱為交叉概率(crossover rate）)交換它們之間的部分染色體,。
??? (3)變異（mutation）：對(duì)群體P(t)中的每一個(gè)個(gè)體,，以某一概率（稱為變異概率(mutation rate）)改變某一個(gè)或某一些基因坐上的基因值為其他的等位基因。
2 算法的實(shí)現(xiàn)
??? 本文所提出的圖像配準(zhǔn)算法的主要思路是：首先對(duì)圖像進(jìn)行預(yù)處理,，然后在一定的范圍內(nèi),，通過(guò)遺傳算法搜索圖像配準(zhǔn)的最佳變化參數(shù)(角度變換量α、X軸平移量α,、Y軸平移量y及幅度變換量s）,。在遺傳算法的執(zhí)行過(guò)程中，利用LTS Hausdorff距離作為遺傳算法的適應(yīng)度函數(shù),，來(lái)判別每一代種群中的個(gè)體的好壞,，然后可以確定哪些變換可以保留到下一代繼續(xù)進(jìn)行遺傳操作，最后當(dāng)遺傳算法停止的時(shí)候,，就可以確定最優(yōu)的變換參數(shù),。
2.1 算法的實(shí)現(xiàn)流程
??? 在整個(gè)配準(zhǔn)過(guò)程開(kāi)始之前，首先要對(duì)參考圖像和待配準(zhǔn)圖像進(jìn)行預(yù)處理,，預(yù)處理主要包括：對(duì)圖像的壓縮,、二值化和邊緣檢測(cè)。對(duì)圖像的壓縮主要是為了在保證一定精度的前提下減少計(jì)算過(guò)程的代價(jià),，之后的二值化本文主要采用自適應(yīng)的閾值分割算法,，最后的邊緣檢測(cè)的目的主要是提取圖像中的特征，通過(guò)對(duì)兩幅圖像特征的配準(zhǔn)可以進(jìn)一步地減少算法的復(fù)雜度,。 本文使用的“canny”算子的邊緣檢測(cè)算法,，最后就是對(duì)預(yù)處理過(guò)的圖像進(jìn)行具體的遺傳算法的圖像配準(zhǔn)的操作。算法的實(shí)現(xiàn)流程圖如圖1所示,。
??????????????? 
2.2 遺傳算法的個(gè)體編碼
??? 編碼是應(yīng)用遺傳算法時(shí)要解決的一個(gè)首要問(wèn)題,，而且也是設(shè)計(jì)遺傳算法的一個(gè)關(guān)鍵步驟。編碼的方法除了決定個(gè)體的染色體排列形式外,，還決定了個(gè)體從搜索空間的基因型變換到解空間的表現(xiàn)型時(shí)的解碼過(guò)程,，同時(shí)也影響了交叉和變異操作。遺傳算法的編碼方法很多,，其中二進(jìn)制編碼是最基本也是最常用的方法,，但是在圖像配準(zhǔn)中二進(jìn)制編碼存在著比較大的缺點(diǎn)：由于配準(zhǔn)的圖像尺寸可能不同，所以二進(jìn)制編碼的位數(shù)無(wú)法事先確定,，若圖像的尺寸改變了,，可能就要修改染色體中編碼的位數(shù)來(lái)適應(yīng)不同的解空間，因此本文采用的是實(shí)數(shù)編碼,。本文要搜索的變換參數(shù)包括X軸平移距離x,、Y軸平移距離y、旋轉(zhuǎn)角度?琢及尺寸變換s,?？梢园堰@些參數(shù)定義為一個(gè)四元組（x、y,、α,、s），并采用實(shí)數(shù)編碼的方式對(duì)這個(gè)四元組進(jìn)行編碼,，然后作為遺傳算法中的個(gè)體的樣本,。
2.3 遺傳算法所選取的適應(yīng)度函數(shù)
??? 在整個(gè)配準(zhǔn)的過(guò)程中,，核心問(wèn)題是必須有一個(gè)合適的個(gè)體評(píng)價(jià)函數(shù)作為適應(yīng)度函數(shù)。所謂的個(gè)體評(píng)價(jià)函數(shù)就是兩幅圖像的相似性的量度,，本文是以LTS Hausdorff距離作為評(píng)價(jià)兩幅圖像間相似程度的評(píng)價(jià)函數(shù),，并作為遺傳算法中個(gè)體的適度函數(shù)應(yīng)用到遺傳算法的具體操作中。適度函數(shù)如下：
??? 
式中,，t是遺傳算法的代數(shù),，i是第t代中的第i個(gè)個(gè)體，R代表的是經(jīng)過(guò)了預(yù)處理后的參考圖像,，而Mi代表在第t代的遺傳操作中的第i個(gè)個(gè)體的待配準(zhǔn)圖像,。
2.4 遺傳算法的選擇機(jī)制及交叉概率和變異概率
??? 在確定了編碼方法和適度函數(shù)后，整個(gè)算法的重點(diǎn)就轉(zhuǎn)移到遺傳算法的細(xì)節(jié)上,，其中一個(gè)比較重要的問(wèn)題是選擇機(jī)制的確定,。選擇是遺傳操作的一部分，其任務(wù)是參照適度函數(shù)的標(biāo)準(zhǔn)按照一定的選擇機(jī)制來(lái)保留優(yōu)勢(shì)個(gè)體,，淘汰劣質(zhì)的個(gè)體,。本文采用的是適應(yīng)度比例與最佳個(gè)體保存相結(jié)合的選擇機(jī)制，設(shè)群體大小為n,，其中個(gè)體i的適應(yīng)度為Fi,，按照適應(yīng)度比例方法，個(gè)體i被選中的概率為：
??? 
??? 交叉概率和變異概率的確定應(yīng)滿足的原則是：一方面能保證個(gè)體的多樣性,，防止過(guò)早的收斂,；另一方面又不會(huì)使算法過(guò)渡發(fā)散。針對(duì)本文的具體配準(zhǔn)問(wèn)題和算法,，經(jīng)過(guò)反復(fù)實(shí)驗(yàn)測(cè)試,，本文確定的交叉概率PC=0.8，變異概率PM=0.07,。
3 實(shí)驗(yàn)結(jié)果
??? 本文所有實(shí)驗(yàn)都是在Matlab7.1環(huán)境下完成的,，運(yùn)行實(shí)驗(yàn)的計(jì)算機(jī)配置是：P4 1.8G、512MB內(nèi)存,。實(shí)驗(yàn)選取了兩幅醫(yī)學(xué)圖像,，其中作為參考圖像的是一位病人腦部的某一層面的MIR圖，如圖2(a)所示,。而待配準(zhǔn)圖像是該病人腦部同一層面的PET圖,，如圖2(b)所示，兩幅圖像的原始尺寸是512×512像素,。經(jīng)過(guò)預(yù)處理后的兩幅圖像分別如圖2(c),、圖2(d)所示。圖2(e)是經(jīng)過(guò)配準(zhǔn)后的PET圖，圖2(f)是配準(zhǔn)后的PET圖與MRI圖的對(duì)比效果,。經(jīng)過(guò)20次配準(zhǔn)后得到的數(shù)據(jù)的平均誤差如表1所示,。
???????????????????? 
??????????????????????? 
??? 使用不同的算法對(duì)以上的圖像配準(zhǔn)后的配準(zhǔn)變換數(shù)據(jù)對(duì)比分別如表2、表3所示,。表2是原始的參考圖像和待配準(zhǔn)的圖像分別經(jīng)過(guò)兩種算法配準(zhǔn)后的數(shù)據(jù),，表3是兩幅圖像分別加入噪聲后分別經(jīng)過(guò)兩種算法配準(zhǔn)后的數(shù)據(jù)。其中算法1是“原始的Hausdorff距離結(jié)合遺傳算法的配準(zhǔn)”,，算法2是“LTS Hausdorff距離結(jié)合遺傳算法的配準(zhǔn)”。由表2,、表3數(shù)據(jù)可以看出,，當(dāng)圖像的質(zhì)量比較好時(shí)，用兩種算法配準(zhǔn)后的數(shù)據(jù)非常地相似,，但是一旦圖像中的噪聲比較明顯時(shí),，算法1的數(shù)據(jù)前后變化就比較大，這就證明了基于原始的Hausdorff距離的遺傳算法配準(zhǔn)受圖像的噪聲和孤立點(diǎn)的影響比較大,，算法的健壯性不好,；而算法2的數(shù)據(jù)在表2和表3中的變化不是很明顯，說(shuō)明了LTS Hausdorff距離結(jié)合遺產(chǎn)算法的圖像配準(zhǔn)算法的穩(wěn)定性較好,。
???????????????????????? 
????????????????????????? 
??? 本文提出的圖像配準(zhǔn)方法,，通過(guò)遺傳算法結(jié)合LTS Hausdorff距離實(shí)現(xiàn)兩幅不同模態(tài)的醫(yī)學(xué)圖像的配準(zhǔn)。為了避免在計(jì)算距離時(shí)產(chǎn)生太大的代價(jià),，筆者首先通過(guò)壓縮圖像和邊緣檢測(cè)的方法對(duì)原始圖像進(jìn)行預(yù)處理,，提取出配準(zhǔn)所需的特征圖像；然后利用LTS Hausdorff距離作為適度函數(shù)的標(biāo)準(zhǔn),，再使用遺傳算法搜索配準(zhǔn)的最優(yōu)變換參數(shù),。試驗(yàn)證明，本文提出的算法可以滿足一定的配準(zhǔn)精度要求,，而且健壯性也比較好,。
參考文獻(xiàn)
[1] HUTTENLOCHER D P，KLANDERMAN G,，RUCKLIDGE W J.Comparing images using the hausdorff distance.IEEE?Transactions on Pattern Analysis and Machine Intelligence[J],，1993，(15)：850-863.
[2] HUTTENLOCHER D P,，RUCKLIDGE W J.A multi-resolution technique for comparing images using the Hausdorff distance.IEEE Transactions un Pattern Analysis and Machine Intelligence[J],，1993,(14)：705-706.
[3] SIM D G，KWON O K,，PARK R H.Object matching algorithms using robust hausdorff distance measures.IEEE Transactions On Image Processing[J],，2004，15(3)：425-428.
[4] HOLLAND J H.Adaptation in natural and artificial system[M].Ann Arbor：University of Michigan Press，1975：30-58.?