基于圖像配準(zhǔn)的混合遺傳FCM算法研究

李玉峰，李景芳

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

基于圖像配準(zhǔn)的混合遺傳FCM算法研究

李玉峰1，2，李景芳1

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

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

關(guān)鍵詞:圖像配準(zhǔn)；變化檢測；PCA ；混合遺傳；FCM分割

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

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

1圖像配準(zhǔn)

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

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

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

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

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

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

圖1　Harris-SIFT算法的流程圖

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

(1)

式中：Threshold表示根據(jù)經(jīng)驗(yàn)求得的閾值。

2初步變化檢測

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

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

(2)

式中：XT,1表示第一幅圖像某一點(diǎn)的像素值；XT,2表示第二幅圖像對應(yīng)點(diǎn)的像素值。

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

(3)

式中：log表示自然對數(shù)。對數(shù)比例圖像用來改善低強(qiáng)度的像素。

3PCA處理

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

(4)

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

(5)

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

(6)

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

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

(7)

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

4遺傳算法和FCM算法

4.1遺傳算法

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

控制參數(shù)的選擇方法如下：

1)基因串長度

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

2)迭代次數(shù)

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

3)種群大小

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

4)交叉概率

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

5)變異概率

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

4.2FCM算法

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

FCM算法通過多次迭代運(yùn)算，反復(fù)校正聚類中心和隸屬度函數(shù)，所以FCM聚類又被叫做動態(tài)聚類。

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

FCM算法的步驟如下：

1)初始化。即設(shè)置目標(biāo)函數(shù)的精度，模糊指數(shù)，最大迭代次數(shù)等；

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

3)更新隸屬度函數(shù)；

4)計算聚類中心；

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

(8)

FCM算法從初始化聚類中心開始，通過每次迭代運(yùn)算收斂到目標(biāo)函數(shù)的局部極小值點(diǎn)。

隸屬度函數(shù)uij的表示為

(9)

聚類中心zi的計算公式為

(10)

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

5混合遺傳FCM算法

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

因?yàn)槟：齝均值聚類算法是一種局部自適應(yīng)迭代算法，聚類中心的初始化問題對其十分重要。如果聚類中心初始化不恰當(dāng)，容易造成目標(biāo)函數(shù)極小值局部收斂，導(dǎo)致聚類效果不佳，影響圖像分割，所以選擇遺傳算法對提取的初步信息進(jìn)行聚類分析，獲得初始聚類中心。

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

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

1)計算初始值

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

2)適應(yīng)度的計算

在這一步驟中，通過求FCM的目標(biāo)函數(shù)JFCM的極小值計算N條染色體的適應(yīng)度f。適應(yīng)度的計算如下

(11)

3)選擇

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

(12)

4)交叉

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

5)變異

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

6)結(jié)束條件

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

6仿真與分析

本文采用Matlab軟件作為實(shí)驗(yàn)環(huán)境來驗(yàn)證本文所提出算法的性能，程序中用到兩幅SAR圖像是關(guān)于渥太華城市的兩幅不同時相的圖像，是由加拿大渥太華防衛(wèi)研究和發(fā)展中心提供的。

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

a　1997年7月洪災(zāi)時　　b　1997年8月洪災(zāi)后

因?yàn)閮煞鶊D像是否是同源圖像，單單從視覺上是無法判定的。所以需要做一些相關(guān)實(shí)驗(yàn)去證明這兩幅圖像是同源圖像。圖像配準(zhǔn)是為了保證變化前后的兩幅圖像中的像素大小和地理位置是一致的。

通過觀察圖3可以發(fā)現(xiàn)，經(jīng)過Harris算子處理，第一幅圖像的特征點(diǎn)個數(shù)是264，第二幅圖像的特征點(diǎn)個數(shù)為350。

a　1997年7月洪災(zāi)時　　b　1997年8月洪災(zāi)后

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

a　1997年7月洪災(zāi)時　　b　1997年8月洪災(zāi)后

圖5是在提取出兩幅不同圖像的特征點(diǎn)之后，利用特征點(diǎn)獨(dú)有的特征向量的歐氏距離進(jìn)行判斷，是否是匹配點(diǎn)對。從圖5的匹配結(jié)果可以看出，這兩幅圖總共有3對精確的匹配點(diǎn)對。因?yàn)镾AR圖像配準(zhǔn)考慮的因素很多，而且配準(zhǔn)精度一般要求在1對像素點(diǎn)對以上，所以可以判定這兩幅圖像是同源圖像，可以繼續(xù)后續(xù)的圖像變化檢測處理。

圖5　匹配結(jié)果

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

圖6　參考圖像

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

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

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

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

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

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

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

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

TN：正確檢測出來的未發(fā)生變化的像素個數(shù)。

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

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

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

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

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

(13)

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

表2仿真結(jié)果

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

7總結(jié)

本文主要根據(jù)FCM算法對初始值敏感的問題，提出了一種基于遺傳算法的改進(jìn)FCM分割方法。因?yàn)镕CM分割容易因?yàn)榫垲愔行某跏贾等≈挡划?dāng)，而陷入局部極小值。而遺傳算法具有能夠得到局部最優(yōu)解的能力。所以本文提到將兩種算法相結(jié)合求最佳聚類分割結(jié)果。并且在這之前，采用3種不同的初步變化檢測方法，盡可能地包含更多的信息。然后，利用PCA方法對提取的初步信息降維處理。混合遺傳FCM算法，相對于FCM算法有兩個很明顯的優(yōu)勢：一是運(yùn)算時間大大減少，因?yàn)楸舅惴ɡ眠z傳算法獲得聚類中心，而遺傳算法不存在求導(dǎo)等復(fù)雜運(yùn)算；二是解決了FCM算法對初始聚類中心敏感的問題。

參考文獻(xiàn)：

[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]丁南南，朱明.基于特征點(diǎn)的圖像配準(zhǔn)技術(shù)研究[D].北京：中國科學(xué)院，2012.

[4]熊博蒞. SAR圖像配準(zhǔn)及變化檢測技術(shù)研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2012.

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

[6]汪松，王俊平，王世奎. 基于SIFT算法的圖像匹配方法研究[D]. 西安：西安電子科技大學(xué)，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].烏魯木齊：新疆大學(xué)，2011.

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

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

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

[12]張小峰，張彩明.基于模糊聚類算法的醫(yī)學(xué)圖像分割技術(shù)研究[D]. 濟(jì)南：山東大學(xué)，2014.

[13]趙洪宋，潘地林.基于遺傳算法和FCM的圖像自動標(biāo)注[J].計算機(jī)與數(shù)字工程，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

文獻(xiàn)標(biāo)志碼:A

DOI：10.16280/j.videoe.2016.03.002

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

作者簡介：

李玉峰(1969— )，教授，博士，主要研究方向?yàn)閳D像壓縮與傳輸技術(shù)，無線通信理論及應(yīng)用等；

李景芳(1989— )，女，碩士，主要研究方向?yàn)樾盘柵c信息處理，為本文通訊作者。

責(zé)任編輯：時雯

收稿日期：2015-07-26

文獻(xiàn)引用格式：李玉峰，李景芳.基于圖像配準(zhǔn)的混合遺傳FCM算法研究[J].電視技術(shù),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.