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