??? 摘 要： 提出了一種基于LTS Hausdorff距離與遺傳算法" title="遺傳算法">遺傳算法的圖像配準(zhǔn)" title="圖像配準(zhǔn)">圖像配準(zhǔn)方法。算法首先對參考圖像和待配準(zhǔn)圖像進(jìn)行壓縮、二值化" title="二值化">二值化和邊緣檢測" title="邊緣檢測">邊緣檢測預(yù)處理，然后在此基礎(chǔ)上結(jié)合遺傳算法對待配準(zhǔn)圖像進(jìn)行配準(zhǔn)操作。
??? 關(guān)鍵詞： 圖像配準(zhǔn)? 遺傳算法? LTS Hausdorff距離? 邊緣檢測? 二值化

???

??? 圖像配準(zhǔn)是圖像處理" title="圖像處理">圖像處理的基本任務(wù)之一，它的主要作用是將不同時間、不同傳感器、不同視角及不同拍攝條件下獲取的兩幅或多幅圖像進(jìn)行匹配(主要是幾何意義上的)。近年來，對圖像配準(zhǔn)技術(shù)的研究涵蓋了多個應(yīng)用領(lǐng)域，在計算機(jī)視覺、模式化識別、醫(yī)學(xué)圖像分析和遙感數(shù)據(jù)處理等學(xué)科中，圖像配準(zhǔn)技術(shù)均占有舉足輕重的地位，圖像配準(zhǔn)己成為很多研究課題的必備環(huán)節(jié)。
??? 圖像配準(zhǔn)中的一個關(guān)鍵問題是如何利用一種行之有效的方法來評價圖像間的相似程度。自1991年Daniel P.Huttenlocher與William J.Rucklidge等人提出了一種基于Hausdorff距離的計算圖像間的相似度的方法^[1]后，Hausdorff距離作為一種評價兩個圖形位置關(guān)系的量化標(biāo)準(zhǔn)已被大量應(yīng)用到圖像配準(zhǔn)的研究領(lǐng)域中，其良好的配準(zhǔn)精度也被大量的實驗和研究所證明。盡管在圖像配準(zhǔn)中，單純的Hausdorff距離計算上存在一個比較大的缺點，即對于噪聲和孤立點的敏感性，但由Hausdorrff距離改進(jìn)的LTS（Least Trimmed Square）Hausdorff距離卻可以很好地克服這些問題，因此作為一種改進(jìn)方法，LTS Hausdorff距離在數(shù)字圖像的配準(zhǔn)中的精確度與穩(wěn)定性都比較理想。
??? 作為一種有效而且實用的優(yōu)化算法——遺傳算法在很多方面得到了應(yīng)用。在圖像處理方面，Chalermwat、Ghazawi等人將遺傳算法應(yīng)用于圖像的配準(zhǔn)；而Brumby、Theiler等人則利用遺傳算法進(jìn)行圖像的特征提取。從他們的實驗結(jié)果來看，遺傳算法在圖像處理方面具有很好的優(yōu)化效果。
??? 本文首先將參考圖像與待配準(zhǔn)的圖像進(jìn)行預(yù)處理（圖像的壓縮、二值化和特征提?。员苊庠谟嬎鉎ausdorff距離時產(chǎn)生過大的代價，然后在此基礎(chǔ)上結(jié)合遺傳算法對待配準(zhǔn)圖像進(jìn)行配準(zhǔn)操作（平移、旋轉(zhuǎn)、幅度變換），最終的目的是通過遺傳算法搜索到最優(yōu)的平移、旋轉(zhuǎn)和幅度變換參數(shù)。實驗表明，這種方法可以有效地抵抗在配準(zhǔn)的過程中產(chǎn)生的噪聲和孤立點的影響，并且在保證一定的配準(zhǔn)精度的前提下可以提高配準(zhǔn)的效率，算法的健壯性良好。
1 算法的基本原理
1.1 Hausdorff距離及其改進(jìn)
??? Hausdorff距離是一種極大極小距離，它主要用于測量兩個點集的匹配程度。Hausdorff距離的引入使物體匹配基于一種新的測度，它能更為有效地表征物體輪廓邊緣之間的相似度。
??? 給定兩個點集A={a₁，a₂，…，a_p}和B={b₁，b₂，…，b_p}，則A、B之間的Hausdorff距離定義如下^[2]：
????H(A,B)=max(h(A,B),h(B,A))
??? 式中，稱為前向的Hausdorff距離，稱為后向的Hausdorff距離，||·||為定義在點集A和B上的某種距離范式，本文使用的是L2范式(歐式距離)。對于任何兩個點集A、B，若H(A，B)=d，則表明對于任何點a∈A，與B中的任何點b∈B的距離必定不會超過d，而且反過來對于B也是成立的。因此，Hausdorff距離可以有效地衡量兩個點集(尤其是幾何圖形)間的位置關(guān)系，但是在圖像處理的實際應(yīng)用中原始的Hausdorff距離在計算的過程中存在一個比較大的缺點，即對噪聲和孤立點的敏感，這個缺點嚴(yán)重影響了圖像配準(zhǔn)的整體準(zhǔn)確性和算法的健壯性。為了克服這一缺點，本文使用的是Hausdorff距離的改進(jìn)形式——LTS Hausdorff距離^[3]：
???
??? 式中，H=h×N_A，N_A為A中的點的個數(shù)，h∈[0.6，0.9]，dB(a)(i)表示在從點a到B集合中每個點的距離中第i大的值。由公式可以看出，LTS Hausdorff距離取的并不是最小距離中的最大值，而是用一種排序再求部分均值的方法來確定A、B之間的距離，從而在很大程度上減小了噪聲和孤立點對精度和穩(wěn)定性的影響。
1.2 遺傳算法
??? 遺傳算法(GA)作為一種求解全局最優(yōu)化的方法，在許多領(lǐng)域的理論與工程實踐中都有成功的應(yīng)用。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度的信息^[4]。
??? 遺傳算法使用所謂的遺傳算子（genetic operators）作用于群體P(t)中，進(jìn)行下述的遺傳操作，從而得到新一代群體P(t+1)。
??? (1)選擇(selection)：根據(jù)每個個體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個體遺傳到下一代群體P(t+1)。
??? (2)交叉(crossover)：將群體P(t)內(nèi)的每個個體隨即搭配成對，對每一對個體，以某個概率（稱為交叉概率(crossover rate）)交換它們之間的部分染色體。
??? (3)變異（mutation）：對群體P(t)中的每一個個體，以某一概率（稱為變異概率(mutation rate）)改變某一個或某一些基因坐上的基因值為其他的等位基因。
2 算法的實現(xiàn)
??? 本文所提出的圖像配準(zhǔn)算法的主要思路是：首先對圖像進(jìn)行預(yù)處理，然后在一定的范圍內(nèi)，通過遺傳算法搜索圖像配準(zhǔn)的最佳變化參數(shù)(角度變換量α、X軸平移量α、Y軸平移量y及幅度變換量s）。在遺傳算法的執(zhí)行過程中，利用LTS Hausdorff距離作為遺傳算法的適應(yīng)度函數(shù)，來判別每一代種群中的個體的好壞，然后可以確定哪些變換可以保留到下一代繼續(xù)進(jìn)行遺傳操作，最后當(dāng)遺傳算法停止的時候，就可以確定最優(yōu)的變換參數(shù)。
2.1 算法的實現(xiàn)流程
??? 在整個配準(zhǔn)過程開始之前，首先要對參考圖像和待配準(zhǔn)圖像進(jìn)行預(yù)處理，預(yù)處理主要包括：對圖像的壓縮、二值化和邊緣檢測。對圖像的壓縮主要是為了在保證一定精度的前提下減少計算過程的代價，之后的二值化本文主要采用自適應(yīng)的閾值分割算法，最后的邊緣檢測的目的主要是提取圖像中的特征，通過對兩幅圖像特征的配準(zhǔn)可以進(jìn)一步地減少算法的復(fù)雜度。 本文使用的“canny”算子的邊緣檢測算法，最后就是對預(yù)處理過的圖像進(jìn)行具體的遺傳算法的圖像配準(zhǔn)的操作。算法的實現(xiàn)流程圖如圖1所示。

???????????????
2.2 遺傳算法的個體編碼
??? 編碼是應(yīng)用遺傳算法時要解決的一個首要問題，而且也是設(shè)計遺傳算法的一個關(guān)鍵步驟。編碼的方法除了決定個體的染色體排列形式外，還決定了個體從搜索空間的基因型變換到解空間的表現(xiàn)型時的解碼過程，同時也影響了交叉和變異操作。遺傳算法的編碼方法很多，其中二進(jìn)制編碼是最基本也是最常用的方法，但是在圖像配準(zhǔn)中二進(jìn)制編碼存在著比較大的缺點：由于配準(zhǔn)的圖像尺寸可能不同，所以二進(jìn)制編碼的位數(shù)無法事先確定，若圖像的尺寸改變了，可能就要修改染色體中編碼的位數(shù)來適應(yīng)不同的解空間，因此本文采用的是實數(shù)編碼。本文要搜索的變換參數(shù)包括X軸平移距離x、Y軸平移距離y、旋轉(zhuǎn)角度?琢及尺寸變換s。可以把這些參數(shù)定義為一個四元組（x、y、α、s），并采用實數(shù)編碼的方式對這個四元組進(jìn)行編碼，然后作為遺傳算法中的個體的樣本。
2.3 遺傳算法所選取的適應(yīng)度函數(shù)
??? 在整個配準(zhǔn)的過程中，核心問題是必須有一個合適的個體評價函數(shù)作為適應(yīng)度函數(shù)。所謂的個體評價函數(shù)就是兩幅圖像的相似性的量度，本文是以LTS Hausdorff距離作為評價兩幅圖像間相似程度的評價函數(shù)，并作為遺傳算法中個體的適度函數(shù)應(yīng)用到遺傳算法的具體操作中。適度函數(shù)如下：
???
式中，t是遺傳算法的代數(shù)，i是第t代中的第i個個體，R代表的是經(jīng)過了預(yù)處理后的參考圖像，而M_i代表在第t代的遺傳操作中的第i個個體的待配準(zhǔn)圖像。
2.4 遺傳算法的選擇機(jī)制及交叉概率和變異概率
??? 在確定了編碼方法和適度函數(shù)后，整個算法的重點就轉(zhuǎn)移到遺傳算法的細(xì)節(jié)上，其中一個比較重要的問題是選擇機(jī)制的確定。選擇是遺傳操作的一部分，其任務(wù)是參照適度函數(shù)的標(biāo)準(zhǔn)按照一定的選擇機(jī)制來保留優(yōu)勢個體，淘汰劣質(zhì)的個體。本文采用的是適應(yīng)度比例與最佳個體保存相結(jié)合的選擇機(jī)制，設(shè)群體大小為n，其中個體i的適應(yīng)度為F_i，按照適應(yīng)度比例方法，個體i被選中的概率為：
???
??? 交叉概率和變異概率的確定應(yīng)滿足的原則是：一方面能保證個體的多樣性，防止過早的收斂；另一方面又不會使算法過渡發(fā)散。針對本文的具體配準(zhǔn)問題和算法，經(jīng)過反復(fù)實驗測試，本文確定的交叉概率PC=0.8，變異概率PM=0.07。
3 實驗結(jié)果
??? 本文所有實驗都是在Matlab7.1環(huán)境下完成的，運行實驗的計算機(jī)配置是：P4 1.8G、512MB內(nèi)存。實驗選取了兩幅醫(yī)學(xué)圖像，其中作為參考圖像的是一位病人腦部的某一層面的MIR圖，如圖2(a)所示。而待配準(zhǔn)圖像是該病人腦部同一層面的PET圖，如圖2(b)所示，兩幅圖像的原始尺寸是512×512像素。經(jīng)過預(yù)處理后的兩幅圖像分別如圖2(c)、圖2(d)所示。圖2(e)是經(jīng)過配準(zhǔn)后的PET圖，圖2(f)是配準(zhǔn)后的PET圖與MRI圖的對比效果。經(jīng)過20次配準(zhǔn)后得到的數(shù)據(jù)的平均誤差如表1所示。
????????????????????

???????????????????????

??? 使用不同的算法對以上的圖像配準(zhǔn)后的配準(zhǔn)變換數(shù)據(jù)對比分別如表2、表3所示。表2是原始的參考圖像和待配準(zhǔn)的圖像分別經(jīng)過兩種算法配準(zhǔn)后的數(shù)據(jù)，表3是兩幅圖像分別加入噪聲后分別經(jīng)過兩種算法配準(zhǔn)后的數(shù)據(jù)。其中算法1是“原始的Hausdorff距離結(jié)合遺傳算法的配準(zhǔn)”，算法2是“LTS Hausdorff距離結(jié)合遺傳算法的配準(zhǔn)”。由表2、表3數(shù)據(jù)可以看出，當(dāng)圖像的質(zhì)量比較好時，用兩種算法配準(zhǔn)后的數(shù)據(jù)非常地相似，但是一旦圖像中的噪聲比較明顯時，算法1的數(shù)據(jù)前后變化就比較大，這就證明了基于原始的Hausdorff距離的遺傳算法配準(zhǔn)受圖像的噪聲和孤立點的影響比較大，算法的健壯性不好；而算法2的數(shù)據(jù)在表2和表3中的變化不是很明顯，說明了LTS Hausdorff距離結(jié)合遺產(chǎn)算法的圖像配準(zhǔn)算法的穩(wěn)定性較好。

????????????????????????

?????????????????????????
??? 本文提出的圖像配準(zhǔn)方法，通過遺傳算法結(jié)合LTS Hausdorff距離實現(xiàn)兩幅不同模態(tài)的醫(yī)學(xué)圖像的配準(zhǔn)。為了避免在計算距離時產(chǎn)生太大的代價，筆者首先通過壓縮圖像和邊緣檢測的方法對原始圖像進(jìn)行預(yù)處理，提取出配準(zhǔn)所需的特征圖像；然后利用LTS Hausdorff距離作為適度函數(shù)的標(biāo)準(zhǔn)，再使用遺傳算法搜索配準(zhǔn)的最優(yōu)變換參數(shù)。試驗證明，本文提出的算法可以滿足一定的配準(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.?