基于圖像配準的混合遺傳FCM算法研究

李玉峰，李景芳

(1.沈陽航空航天大學 電子信息工程學院，遼寧 沈陽 110136；2.東南大學 移動通信國家重點實驗室，江蘇 南京 210096)

基于圖像配準的混合遺傳FCM算法研究

李玉峰1，2，李景芳1

(1.沈陽航空航天大學 電子信息工程學院，遼寧 沈陽 110136；2.東南大學 移動通信國家重點實驗室，江蘇 南京 210096)

摘要:針對目前圖像變化檢測的相關研究，提出一種新的算法：基于SAR圖像配準的混合遺傳FCM算法。算法主要分為4個步驟。第一步，利用Harris算法和SIFT算法對兩幅圖像進行匹配，證明它們是同源不同時相的圖像。第二步，利用兩種不同變化檢測方法提取初步差異圖像。第三步，利用PCA方法對差異圖像進行降維處理。第四步，利用混合遺傳FCM算法對特征矢量空間進行分類，并將分類結果與參考差異圖像進行比較，獲得變換信息。采用渥太華地區的部分圖像作為檢測算法的性能的數據庫。獲得的結果與FCM算法相比較，結果表明，提出的算法具有最高的全局正確率98.10%，算法效果更佳。

關鍵詞:圖像配準；變化檢測；PCA ；混合遺傳；FCM分割

SAR相對于可見光而言，由于其全天候、全天時的獨特的特點，應用范圍非常廣泛，可以檢測地震、洪災等的變化，能夠在第一時間獲得災區的公路、建筑物以及水利設備發生的受損情況，為災區居民轉移以及救助方式提供戰略支持[1]。而可見光是一種非主動式成像，所以在夜晚或者光照不足的條件下就無法獲得令人滿意的光學遙感圖像。所以，相比較而言，SAR越來越受到廣大研究人員的關注。

SAR圖像變化檢測方法可以分為兩大類：一是基于像素的變化檢測方式，目前比較常用的是圖像差值法和圖像比值法；二是基于區域的變化檢測方法，首先將SAR圖像進行分割，得到區域圖像，然后再在區域的基礎上進行分割[2]。

1圖像配準

通常意義上理解的圖像配準是指對同一地區的不同時間拍攝的圖像或者不同角度拍攝的圖像進行匹配，找出不同圖像的相同點或者相同區域，從而得到圖像間最佳的幾何變換關系[3-4]。通常在對圖像進行變化檢測之前，需要先對圖像進行配準處理。

本文中用到的兩幅圖像，從視覺上看是來源于同一地區，然后利用圖像配準技術驗證一下這兩幅圖像是否來源于同一地區。令其中一幅圖像為基準圖像，另外一幅圖像為待配準圖像。兩幅圖像之間的相似度越高，那么匹配程度也越高。本文中，圖像配準的作用主要是為了減少由于圖像失配等外界因素導致的不良影響。

本文圖像配準主要是基于特征點的圖像匹配。圖像特征點是指在水平、垂直方向上都發生極大變化的圖像像素點。Harris算子[5]提取角點的基本原理是：定義一個局部檢測窗口，當該窗口沿著不同方向移動時，觀察被局部窗口覆蓋區域的平均能量變化，如果該能量變化值超過設定的閾值，則將該窗口的中心像素點提取為角點。

SIFT算法[6]的基本思想為：根據高斯卷積核實現尺度空間的構建，然后在已完成的尺度空間內尋找極值點，并為極值點建立特征描述符。SIFT算法是一種局部特征描述子，它在圖像發生縮放、尺度變化以及角度旋轉時都具有不變性。

雖然SIFT算法的穩定性很好，但是它的運算量大，復雜度高。所以，本文采用將基于Harris角點的匹配方法和基于SIFT特征的匹配方法相結合。首先，利用Harris提取特征點，然后利用SIFT算法為每個特征點定義主方向保持旋轉不變性，最后生成特征向量的描述子。這樣，降低了匹配的復雜度，并且提高了算法的實時性和圖像的正確匹配率。

Harris-SIFT算法的流程圖如圖1所示。

圖1　Harris-SIFT算法的流程圖

其中，相似度判斷主要利用特征點之間的歐氏距離。假設與匹配點最小的歐氏距離差值為Dmin，次小值為Dmi_amin，如果這兩者的比值在規定的范圍內，則可以判定最小歐氏距離差值對應的點則是待匹配點。計算公式如下

(1)

式中：Threshold表示根據經驗求得的閾值。

2初步變化檢測

針對SAR圖像，目前比較通用的方法主要有差值法、相關系數法、圖像熵方法、直方圖比較法來對SAR圖像進行變化檢測[7]。利用3種算法來提取SAR圖像變化信息。

1)絕對值差分法：把兩幅不同時相的圖像相對像素作差，并取絕對值，就可以得到絕對值差分圖像Id,1。絕對值差分公式如下

(2)

式中：XT,1表示第一幅圖像某一點的像素值；XT,2表示第二幅圖像對應點的像素值。

2)對數比例法： 將兩幅不同時相的SAR圖像矩陣作比，并取絕對值，最后再取對數，形成對數比例圖像Id,2。對數比例法公式如下

(3)

式中：log表示自然對數。對數比例圖像用來改善低強度的像素。

3PCA處理

PCA方法主要應用于特征提取和降維處理[8-9]。從上述3個公式中獲得的圖像變化信息，用一個列矩陣Id(x,y)表示為

(4)

這3幅變化圖像的尺寸均為H×W，那么總共有HW個向量組成圖像中的像素。簡而言之，Id,k表示矢量Id(x,y)，而k表示范圍為1≤k≤N的指數，其中N=H×W。平均向量χ可以表示為

(5)

每個向量與平均向量的差為Δk=Id,k-χ。協方差矩陣CI的特征矢量為ei，相應的特征值為λi。協方差矩陣CI近似表示為

(6)

式中：利用N-1代替N，從而得到CI的無偏估計。假設，根據特征值的大小，即λi≥λi+1，將CI產生的特征向量按照降序排列。

將Id(x,y)投影于空間位置(i,j)處的每個像素的特征向量空間，從而得到特征矢量空間，即

(7)

協方差矩陣CI的特征向量按照矩陣A的行排列。矩陣的第一行是特征向量的最大特征值，以此類推。從而生成一個特征矢量空間，方便后續處理。

4遺傳算法和FCM算法

4.1遺傳算法

遺傳算法(GA)[10-11]的原理類似于生物界的適者生存，優勝劣汰機制。遺傳算法是一種隨即搜索方法，不依賴函數的連續性，能夠自適應地改變搜索方向，具有很好的并行性和全局搜索能力。遺傳算法最重要的就是控制參數的選擇。

控制參數的選擇方法如下：

1)基因串長度

本文主要是針對灰度圖像進行處理，并且采用二進制編碼，所以相關范圍保持在0～255之間即可。因此，本文選擇基因串的長度為8。

2)迭代次數

迭代次數T用來制定終止條件。本文采用迭代次數范圍為10～20。

3)種群大小

種群大小n即種群中染色體的多少。n太大會影響算法的效率，n太小會減少種群的多樣性。根據經驗，本文選擇的種群大小為30。

4)交叉概率

交叉概率pc是指pc×n個染色體進行了交換基因。pc的取值范圍為[0.6,0.9]。

5)變異概率

變異概率pm是指pm×n個染色體進行了基因取反操作。pc的取值范圍為[0.03,0.08]。

4.2FCM算法

FCM算法[12-13]的數學理論基礎已經很完善。近些年來，被引用到圖像處理領域中。它的實質是求解非凸優化問題的迭代算法。FCM算法的大致思想是：劃分到同一類別的對象的相似性盡可能得大；相反地，被劃分到不同類的對象之間的相似性盡可能地接近于0。

FCM算法通過多次迭代運算，反復校正聚類中心和隸屬度函數，所以FCM聚類又被叫做動態聚類。

FCM算法有一個很重要的函數，即隸屬度函數。隸屬度函數是用來確定每個數據點屬于某一類的程度的一種度量方法。

FCM算法的步驟如下：

1)初始化。即設置目標函數的精度，模糊指數，最大迭代次數等；

2)初始化模糊聚類中心；

3)更新隸屬度函數；

4)計算聚類中心；

假設集合X={x1,x2,…,xn}為特征空間Rn上的一個有限數據集合，并且把X劃分為c類，用V={v1,v2,…,vc}表示個數為c的聚類中心。FCM算法的目標函數可以表示為

(8)

FCM算法從初始化聚類中心開始，通過每次迭代運算收斂到目標函數的局部極小值點。

隸屬度函數uij的表示為

(9)

聚類中心zi的計算公式為

(10)

FCM算法通過對目標函數迭代計算，求出其最小值，從而獲得對數據集合的模糊分類。

5混合遺傳FCM算法

根據由遺傳算法改進的模糊c均值聚類算法，把差異圖像聚類成兩種類型：變化類型和未發生變化類型，得到最終的變化矩陣。

因為模糊c均值聚類算法是一種局部自適應迭代算法，聚類中心的初始化問題對其十分重要。如果聚類中心初始化不恰當，容易造成目標函數極小值局部收斂，導致聚類效果不佳，影響圖像分割，所以選擇遺傳算法對提取的初步信息進行聚類分析，獲得初始聚類中心。

為了克服這種影響，得到更好的聚類結果，本文提出了一種混合遺傳FCM算法[14]。

混合遺傳FCM算法的步驟如下：

1)計算初始值

通過遺傳算法獲得k類的聚類中心{z1,z2,…,zk}。

2)適應度的計算

在這一步驟中，通過求FCM的目標函數JFCM的極小值計算N條染色體的適應度f。適應度的計算如下

(11)

3)選擇

在這一步驟中，選擇具有最佳適應度fi的染色體作為下一代的父本。染色體選擇的概率pi為

(12)

4)交叉

交叉是用于繁殖的遺傳算子。交叉是一種交換信息的高效方式。這些信息來源于適應度高的染色體。如果沒有進行交叉操作，說明用于繁殖的染色體和其父系染色體很相像。在本文中，使用具有固定的交叉速率kc的單點交叉方法。

5)變異

每條染色體具有固定的變異速率km。

6)結束條件

如果迭代計算達到它的最大值，或者是兩個連續的迭代方案之間最小的改善值低于閾值，那么程序終止，輸出最佳方案。否則，用新產生的染色體代替之前步驟中的一些染色體，重復步驟2)～5)。

6仿真與分析

本文采用Matlab軟件作為實驗環境來驗證本文所提出算法的性能，程序中用到兩幅SAR圖像是關于渥太華城市的兩幅不同時相的圖像，是由加拿大渥太華防衛研究和發展中心提供的。

圖2所示的這兩幅圖像的數據大小均為290×350，由Radarsat SAR傳感器獲得。第一幅圖像是1997年7月在夏季洪水災害時拍攝的圖像。第二幅圖像是1997年8月在夏季洪水災害之后拍攝的圖像。在這兩幅圖像中，主要分為兩類區域，一類是水域，一類是土地。

a　1997年7月洪災時　　b　1997年8月洪災后

因為兩幅圖像是否是同源圖像，單單從視覺上是無法判定的。所以需要做一些相關實驗去證明這兩幅圖像是同源圖像。圖像配準是為了保證變化前后的兩幅圖像中的像素大小和地理位置是一致的。

通過觀察圖3可以發現，經過Harris算子處理，第一幅圖像的特征點個數是264，第二幅圖像的特征點個數為350。

a　1997年7月洪災時　　b　1997年8月洪災后

圖4是經過SIFT算子檢測后的結果，兩幅圖像的特征點個數減少，第一幅圖像的特征點個數186，第二幅圖像的特征點個數272。結果表明特征點數明顯。減少的原因是：Harris算法對尺度等因素不穩定，SIFT算法對尺度具有很好的穩定性，所以結合兩個算法，可以檢測出穩定的準確的特征點。然后求出穩定的特征點的特征向量，利用特征向量之間的歐氏距離判斷是否是匹配點對。距離最小的一對特征點就是本文要求的匹配點。

a　1997年7月洪災時　　b　1997年8月洪災后

圖5是在提取出兩幅不同圖像的特征點之后，利用特征點獨有的特征向量的歐氏距離進行判斷，是否是匹配點對。從圖5的匹配結果可以看出，這兩幅圖總共有3對精確的匹配點對。因為SAR圖像配準考慮的因素很多，而且配準精度一般要求在1對像素點對以上，所以可以判定這兩幅圖像是同源圖像，可以繼續后續的圖像變化檢測處理。

圖5　匹配結果

圖6是由兩幅不同時相的SAR圖像作為先驗信息合成的，利用繪圖軟件畫出來的，用來作為參考圖像。

圖6　參考圖像

圖7的運行結果是根據圖2所示的第一幅圖由遺傳算法和FCM算法分別求得的4個聚類中心值的對比。其中，實線表示遺傳算法求得的聚類中心，虛線表示FCM算法求得的聚類中心。從表1上可以看出，兩種算法最終得到的聚類中心值是一致的。

圖7　GA和FCM獲得的4個聚類中心值的比較

算法時間/s聚類中心1聚類中心2聚類中心3聚類中心4GA0.365791977127182FCMA12.83281877125181

但是從表1可以看出，遺傳算法的運行時間要遠小于FCM算法的運行時間。所以，由以上結果可以得出，首先利用遺傳算法求得聚類中心，然后利用FCM算法求得分割結果，可以節省運算時間。

圖8表示最終的分割結果。其中，圖8a表示混合遺傳FCM算法分割結果，圖8b表示FCM算法分割結果。從圖左上角可以明顯的發現聚類的結果不同，通過與圖7的參考圖像對比，得出混合遺傳FCM算法分割結果更好。

得到分割結果之后，再與參考圖像作差，可以得到最終的變化檢測結果。

最能真實反映變化檢測結果的數據還需要用如下參數表示。本文圖像總共有101 500個像素。

TP：正確檢測出來的變化像素個數。

TN：正確檢測出來的未發生變化的像素個數。

FN(漏檢)：把發生變化的像素檢測成未發生變化像素的個數。

FP(誤檢)：把未發生變化的像素檢測成發生變化的像素個數。

從上述方程得到的一些矩陣可以用來評價算法的性能。在本文中，采用如下的一些矩陣：

全局正確率(OA)表明算法的正確率

OA=(TP+TN)/(FN+FP+TP+TN)

(13)

關于不同方法的上述矩陣均在表2中顯示。結果表明，相對于其他算法，本文提出的算法具有最高的全局正確率98.10%，變化檢測效果更佳。

表2仿真結果

算法TPTNFNFPFN+FPOA/%FCM144618489211461001214797.88本文算法14966846091284641192598.10

7總結

本文主要根據FCM算法對初始值敏感的問題，提出了一種基于遺傳算法的改進FCM分割方法。因為FCM分割容易因為聚類中心初始值取值不當，而陷入局部極小值。而遺傳算法具有能夠得到局部最優解的能力。所以本文提到將兩種算法相結合求最佳聚類分割結果。并且在這之前，采用3種不同的初步變化檢測方法，盡可能地包含更多的信息。然后，利用PCA方法對提取的初步信息降維處理。混合遺傳FCM算法，相對于FCM算法有兩個很明顯的優勢：一是運算時間大大減少，因為本算法利用遺傳算法獲得聚類中心，而遺傳算法不存在求導等復雜運算；二是解決了FCM算法對初始聚類中心敏感的問題。

參考文獻：

[1]YAHYA N，KAMEL N S，MALIK A S. Subspace-based technique for speckle noise reduction in SAR images[J]. IEEE transactions on geoscience and remote sensing，2014，52(10)：6257-6271.

[2]MARIN C，BOVOLO F，BRUZZONE L. Building change detection in multitemporal very high resolution SAR images[J]. IEEE transactions on geoscience and remote sensing，2015，53(5)：2664-2682.

[3]丁南南，朱明.基于特征點的圖像配準技術研究[D].北京：中國科學院，2012.

[4]熊博蒞. SAR圖像配準及變化檢測技術研究[D].長沙：國防科學技術大學，2012.

[5]聶蘭蘇，唐雁．基于角點檢測的圖像拼接方法研究[D]．重慶：西南大學，2013.

[6]汪松，王俊平，王世奎. 基于SIFT算法的圖像匹配方法研究[D]. 西安：西安電子科技大學，2013.

[7]GONG M G，ZHOU Z Q，MA J J. Change detection in synthetic aperture radar images based on image fusion and fuzzy clustering[J]. IEEE transactions on image processing，2012，21(4)：2141-2151.

[8]劉瑛.基于主成分分析的遙感圖像分割算法[D].烏魯木齊：新疆大學，2011.

[9]莫德林，劉克江，曹彬才，等. 基于主成分分析的遙感圖像變化檢測[J].影像技術，2013(10)：53-56.

[10]喬陽，李恩，董鳳服.基于改進遺傳算法的圖像分割方法[D]. 成都：電子科技大學，2013.

[11]王雪，李莉. 基于遺傳算法的醫學圖像分割技術的研究[D]. 長春：長春理工大學，2013.

[12]張小峰，張彩明.基于模糊聚類算法的醫學圖像分割技術研究[D]. 濟南：山東大學，2014.

[13]趙洪宋，潘地林.基于遺傳算法和FCM的圖像自動標注[J].計算機與數字工程，2015(3)：497-500.

[14]HUNG C C，KULKARNI S，KUO B C. A new weighted fuzzy c-means clustering algorithm for remotely sensed image classification[J]. IEEE journal of selected topics in signal processing，2011，5(3)：543-553.

Hybrid genetic FCM algorithm research based on image registration

LI Yufeng1，2，LI Jingfang1

(1.SchoolofElectronicsandEngineering，ShenyangAerospaceUniversity，Shenyang110136，China；2.NationalMobileCommunicationsResearchLaboratory，SoutheastUniversity，Nanjing210096，China)

Abstract:A hybrid genetic FCM algorithm based on SAR images registration is proposed in this paper in view of the present researches of the image change detection. This proposed method is divided into three steps. In the first step，Harris algorithm and SIFT algorithm are used to match different images，proved that they are the homologous images from same region achieved at different time. In the second step，with the using of two change detection methods，the primarily difference image is obtained. In the third step，PCA method is used for feature extraction and dimension reduction. In the fourth step，the feature vector space information is divided into two classes based on hybrid genetic FCM algorithm. The change information is achieved by comparing the classification results and reference difference image. This method takes the parts of image of Ottawa area as data set for the performance evaluation. Compared with other FCM method， the results show that the change detection accuracy of the proposed algorithm reaches 98.10%， so it is better than other algorithms.

Key words:image registration； change detection； PCA； hybrid genetic； FCM segmentation

中圖分類號:TN915

文獻標志碼:A

DOI：10.16280/j.videoe.2016.03.002

基金項目：國家自然科學基金項目(61171081)；航空科學基金項目(20122654)；江蘇省博士后基金項目(1101077c)

作者簡介：

李玉峰(1969— )，教授，博士，主要研究方向為圖像壓縮與傳輸技術，無線通信理論及應用等；

李景芳(1989— )，女，碩士，主要研究方向為信號與信息處理，為本文通訊作者。

責任編輯：時雯

收稿日期：2015-07-26

文獻引用格式：李玉峰，李景芳.基于圖像配準的混合遺傳FCM算法研究[J].電視技術,2016，40(3)：5-10.

LI Y F，LI J F.Hybrid genetic FCM algorithm research based on image registration[J].Video engineering,2016,40(3)：5-10.