結合稀疏編碼和空間約束的紅外圖像聚類分割研究*

宋長新 馬克 秦川 肖鵬

(青海師范大學計算機學院,西寧 810008)

(2012年5月3日收到;2012年10月4日收到修改稿)

1 引言

紅外圖像的分割就是根據一致性準則將圖像劃分為互不重疊的各具特性的區(qū)域,并區(qū)分出感興趣目標的過程[1,2],是紅外圖像在軍事和民用中應用的前提.紅外圖像分割的好壞關系到目標檢測、識別和精確定位等任務.通常采取的算法有閾值化分割、基于邊緣的分割及基于區(qū)域的分割等[1].由于紅外圖像具有紋理少、對比度差、信噪比低及復雜背景干擾等特點,導致了紅外圖像分割問題的困難[3].為了克服這些困難,提高分割的準確性,人們提出了許多改進的分割算法,如結合直方圖或熵的閾值化分割[1,4]、基于C-V模型的水平集分割[5]、空間約束聚類分割[6,7]等分割算法.其中基于聚類的紅外圖像分割算法是一種重要的分割算法,分割過程中不需過多的人工干預,具有較好的抗噪性,適于紅外圖像自動分割,得到了大量研究.常用的聚類分割算法有K-means算法、模糊C均值算法(FCM)等,主要采用的是詞袋(BOF:bag of features)的思想[8],為了更準確地從復雜背景中分割重要區(qū)域,后又在上述聚類算法基礎上提出了空間約束FCM分割算法[7,9,10]、模糊核聚類分割算法[3]等.這些算法本質上都是K-means算法,對非凸的數據結構和彼此交疊嚴重的數據存在局限性[8],也較少考慮像素點在空間上的依賴關系,導致分割效果并不理想.

本文結合稀疏編碼算法提出了一種紅外圖像聚類分割算法.稀疏編碼是在超完備基上的一種稀疏表示,是計算機視覺領域的研究熱點之一,稀疏編碼方法廣泛應用于圖像恢復、識別及檢測等模式識別的各個方面[11?14].稀疏編碼對K-means聚類算法的擴展在向量量化構造BOF特征進行識別時具有明顯改善[11,15,16],但直接將上述稀疏編碼用于聚類進行圖像分割容易產生過分割,難以得到有意義的區(qū)域,造成像素歸類的判斷問題.為此,我們在字典學習過程中,將原子的聚類算法引入其中,有助于縮減字典中原子所屬類別的數目,同時將稀疏編碼系數同原子對聚類中心的隸屬程度相結合來判斷像素所屬的類別.這種處理方式能通過字典更好地反映類別內像素的內在聯(lián)系性,由于采用局部塊進行處理,自然地引入了局部信息,而且這些約束條件與聚類算法相融合也較為自然,在此基礎上進一步根據圖像特點對圖像中像素的鄰域像素施加空間類別屬性約束提高分割質量.實驗結果表明,所提算法能更好地實現復雜背景及干擾下紅外圖像重要區(qū)域的準確分割提取.

2 稀疏編碼基本概念

所謂稀疏編碼是指信號可以用一個過完備字典集中的少數幾個基向量的線性組合來表示,其所用的基向量個數要盡可能少,也就是稀疏[12],這些稀疏系數及其對應的字典可以反映信號的主要特征和內在結構.假設維數為m的n個樣本形成的數據 X=[x1,x2,···,xn]∈ Rm×n,其中 xi是第 i個樣本,有過完備字典 D=[d1,d2,···,dK]∈ Rm×K(K＞m),其中D中的每個列向量dk∈Rm×1稱為原子(也可稱基向量),滿足約束條件dTkdk≤1,K為字典中的原子個數,稀疏編碼模型就是通過最小化下面重構誤差求解信號的稀疏描述和過完備字典,即

其中 ‖·‖F表示 Frobenius范數 (簡稱 F 范數),‖·‖1是1范數,表示稀疏性約束,αi∈RK×1是xi的稀疏系數向量,A=[α1,α2,···,αn]∈ RK×n,參數 λ 平衡重構誤差和系數的稀疏性.可以看出上述稀疏性約束采用的是1范數,一般稀疏性用系數向量中的非零個數表示,即0范數,如果(1)式采用0范數約束則是一個NP難的非凸優(yōu)化問題,難以求解,通常用1范數代替0范數,很多文獻已經證明兩者具有等價性[12].上述代價函數同時對變量D和α求解是非凸函數,但如果固定其中一個變量求解另一個變量,則是一個凸函數優(yōu)化問題,一般分為兩步求解:字典學習和稀疏編碼,在固定字典D時求解稀疏系數α,在固定稀疏系數α時學習字典D,多次迭代進行優(yōu)化,直到收斂.當前稀疏編碼應用的難點在于根據問題設計反映任務需要的字典.

3 空間約束下結合稀疏編碼的聚類算法

3.1 稀疏編碼觀點下的K-means算法

K-means聚類算法是一種無監(jiān)督類別劃分方法,通過最小化樣本和所屬聚類中心的距離進行優(yōu)化,其目標函數表示為:其中vc為第c類聚類中心,J為類別數,是向量量化構造BOF特征的一個重要步驟.K-means聚類算法的目標函數等價于如下形式:

式中 V=[v1,v2,···,vJ]∈ Rm×J是聚類中心形成的矩陣;U=[u1,u2,···,un]∈ RJ×n是樣本對聚類中心的歸屬指標矩陣,其所有元素為非負值;函數card(x)表示x中的非零元素個數,card(ui)=1表示ui中只有一個元素非零,‖ui‖1=1確保 ui所有元素的絕對值之和為1,上述限制使得ui只有一個元素為1,其余均為0,也就是ui確定了樣本xi所屬的聚類中心,ui中的非零元素所在的位置對應了xi所屬的聚類中心,可以看出(2)式與原始K-means目標函數是等價的.但card(ui)=1限制條件嚴格,從而使得對xi的重構誤差較大,損失部分信息;如果放松該限制,會造成樣本屬于過多聚類中心,這時采用反映非零元素個數的稀疏性約束代替‖ui‖1=1,則在稀疏編碼觀點下的K-means聚類算法目標函數為[11,17]

其中 ‖vc‖≤1,該歸一化項的約束防止產生奇異解.稀疏編碼觀點下的K-means算法與原始K-means算法相比,具有如下優(yōu)點[11]:1)(3)式由于約束條件更為寬松,較K-means具有更低的目標函數誤差,對樣本有更低的重構誤差,可保留樣本更多的信息;2)通過稀疏性能捕捉圖像更顯著的特征;3)圖像的統(tǒng)計特性表明圖像塊本身就具有稀疏性,更符合圖像的特性.可以看出采用(3)式的樣本只與幾個聚類中心有關(對應于稀疏系數的非零元素),與其他的聚類中心不存在關系.

3.2 結合稀疏編碼的聚類分割算法(SCC)

從(3)式中可以看出,樣本xi從單純的像素點聚類擴展到以該像素點為中心的圖像塊聚類,利于排除野點的干擾,具有一定的空間約束性;而且通過聯(lián)合所有像素點所在像素塊進行學習字典,各個局部像素塊通過字典建立了某種聯(lián)系,挖掘了它們之間一定的內在相關性,有利于利用像素的相似性進行聚類;稀疏系數可以捕捉圖像更顯著的特征,抑制圖像中的非結構信息,如雜點、噪聲和其他一些外來干擾.但直接將上述稀疏編碼用于聚類進行圖像分割有兩個困難:1)由于K＞m,字典D中的原子個數較多,直接將D中的原子作為聚類中心會造成類別數過多,容易導致過分割,難以得到有意義的區(qū)域;2)得到的稀疏系數向量難以反映像素點所屬的類,造成像素歸類的判斷問題.

我們采用的思想是在字典學習過程中,將原子的聚類算法引入其中,有助于縮減字典中原子所屬類別的數目,防止產生過分割的問題;同時將稀疏編碼系數同原子對聚類中心的隸屬程度相結合來判斷像素所屬的類別.但是字典中原子之間具有較大的相關性,如果采用K-means聚類算法強制將原子劃分為某一類別,容易產生較大的聚類誤差,對后續(xù)的像素歸類判斷產生誤導.這里我們采用FCM算法進行原子的聚類.FCM是在K-means算法的基礎上引入了模糊隸屬度的概念,樣本可以歸屬于多個聚類中心,不再是硬劃分.定義樣本xi對第c類的模糊隸屬度函數為wci,且隸屬度函數w滿足

ciFCM的目標函數為:式中 p ≥ 1 是隸屬度指數,一般取為2.若式中的隸屬度函數wci只取0或1,則為K-means聚類算法.通過迭代更新隸屬度函數wci和聚類中心vc最小化目標代價函數.FCM與(3)式不同之處在于:FCM算法中樣本通過歐氏距離與所有聚類中心有聯(lián)系,而(3)式中樣本通過稀疏系數只與幾個聚類中心有關,這種基于稀疏系數的相關性正如上所述,反映的是圖像內在結構的相似性.根據以上分析,我們將基于FCM的原子聚類算法引入到(3)式中進行字典學習,給出如下目標函數:

其中γ為控制樣本重構誤差和原子聚類誤差比例的參數,zc表示原子的聚類中心.上式中第一項是樣本在字典下的重構誤差,反映字典和稀疏系數所含的樣本信息;第二項是稀疏性約束;第三項表示原子的聚類,反映原子的歸類問題,一般J?K,即將原子分為J類.如果γ過大,主要強調原子的聚類,則學習的字典V將有明顯的結構信息,相對來說會造成樣本重構誤差過大,弱化字典V反映的樣本信息;反之,如果γ過小,則學習的字典V將更多地反映樣本信息,從而弱化結構信息,難以取得較好的聚類效果.

3.3 空間約束下的SCC分割算法

圖像分割中的空間約束是一個重要的信息,文獻[8—10,15,16]相關結論表明,考慮空間約束能有效提高實驗效果,對于紅外圖像來說,其像素及其鄰域中的像素更具有類別屬性一致性的特點.我們將圖像像素的空間類別屬性約束引入(4)式中,給出下面的目標函數:

其中ρ為空間約束性懲罰因子.Ni,t以xi為中心窗口,大小為(2t+1)×(2t+1)的鄰域.NR為鄰域中像素的個數.rci是樣本xi對于聚類中心zc的歸屬度,其他參數同(4)式所述.上式第四項是空間類別屬性約束,反映某像素點及其鄰域像素應盡可能屬于相同的一類.為了求解上式,首先需要定義樣本對于聚類中心的歸屬度rci,要完成聚類分割,需要判斷像素點所屬的類.由于稀疏系數反映了樣本xi對字典中各個原子的權重大小,而字典中各個原子對聚類中心有不同的隸屬程度,所以我們定義樣本xi對于聚類中心zc的歸屬度為

如果同時優(yōu)化全部4個參數比較困難,這里采用交替優(yōu)化迭代方法求解Z,U,V,W.隨機選取樣本初始化字典后,首先求解稀疏系數；然后更新字典；最后計算聚類中心和隸屬度.具體求解算法如下.

1)稀疏編碼:固定Z,V,W,即

2)字典學習:固定Z,U,W,學習字典V,此時的優(yōu)化目標函數為

對V中的原子逐一進行求解,固定其他原子,則對原子vl有如下表示:

其中 qt是稀疏系數 U 的行向量 (t=1,···,J),U=[q1;q2;·;qJ]. 令與原子 vl無關的項 S=則 (10)式可以寫成

其中η為調節(jié)參數,將上式對vl微分有

然后,歸一化

如此對V中的原子逐一進行更新.

3)更新聚類中心:固定V,W,U,通過

4)更新隸屬度:固定Z,V,U,通過

求解W,根據拉格朗日乘子法有

通過上述的多次迭代優(yōu)化過程,可以求出字典V,稀疏系數U,字典聚類中心Z及隸屬度W.最后完成聚類分割,需要判斷像素點所屬的類,計算樣本xi對于聚類中心zc的歸屬度:根據樣本對于各個聚類中心的歸屬度按照最大化原則進行分類,即可得到最終聚類結果,從而完成紅外圖像的聚類分割.

4 實驗結果與分析

為了驗證本文所提紅外圖像分割算法的性能,我們采用機載對地面飛機和道路的紅外圖像進行實驗,分別如圖1(a)和圖3(a)所示,并采用K-means,FCM,模糊核聚類(KFCM)和結合空間信息的模糊聚類(SFCM)分割算法結果作為對比.首先,我們討論一下具體的參數選擇,FCM,KFCM,SFCM和本文算法中的隸屬度指數p統(tǒng)一取為2,FCM,KFCM及SFCM算法的迭代次數為100,本文算法中稀疏性參數λ取0.001,γ=0.2,η=0.5.空間約束目的是使得鄰域內的所有像素盡量具有相同的類別,對于SFCM和本文算法空間約束的鄰域大小選擇,正如文獻[8—10]中所論述的,選擇較大的鄰域進行空間約束,如7×7,9×9等,雖能使得分割結果更為平滑完整,較好地消除野點及噪聲,但難以避免會丟失圖像中固有的邊緣或較小目標等信息.一般來說,如果目標較大,且較為平滑完整,則可適當地選擇較大鄰域.對于本文的圖像,我們選擇大小為3×3的鄰域用于SFCM和本文算法的實驗;其中對于空間約束懲罰系數α,選取過小的α將難以起到空間約束的作用,選取過大的α將抹殺圖像像素的固有屬性,這里我們在SFCM和本文算法中選取空間約束懲罰系數α=4.KFCM算法所用的核函數及其參數在后面實驗中給出.另外,本文算法由于采用像素鄰域的圖像塊向量代替了原來的像素值,可以看出如果取較大的圖像塊,則容易抹殺了圖像的細節(jié)信息,本文算法實驗中選取圖像塊大小為3×3.如文獻[11,12,20]所示,并對數據進行歸一化處理,字典大小可以通過冗余性指數N和圖像塊向量維數m確定,即K=N×m,冗余性指數N反映了稀疏系數的稀疏性,N越大則越稀疏,本文中N取值范圍可設為5—10.K-means,FCM,KFCM,SFCM及本文算法中如何選擇類別數J是一個普遍的難題,與諸多文獻類似,我們通過實驗根據不同的問題選擇不同的類別數.針對多組實驗,本文算法的迭代次數統(tǒng)一選為50,其收斂性將在后面予以討論.

實驗中計算機為i5-2.5 GHz Intel酷睿處理器,4 GB內存,仿真工具為Matlab 7.10.紅外圖像分割的效果一般無法進行定量評價,一個廣泛采用的評價原則就是看能否分割出期望的或者重要的區(qū)域,并且盡量區(qū)分背景區(qū)域和目標區(qū)域.本實驗主要觀察分割算法能否分割出重要區(qū)域,保持重要區(qū)域的完整性,抑制非重要區(qū)域對重要區(qū)域的誤導.可以看出圖1(a)和圖2(a)所示的重要區(qū)域分別為飛機和道路.

圖1 分割結果對比 (a)原始圖像;(b)K-means分割;(c)FCM分割;(d)KFCM分割;(e)SFCM分割;(f)本文算法

圖2 含噪圖像分割結果對比 (a)噪聲圖像;(b)K-means分割;(c)FCM分割;(d)KFCM分割;(e)SFCM分割;(f)本文算法

對于圖 1(a)的分割實驗,K-means,FCM,KFCM,SFCM及本文算法中采用的類別數J取為8,本文算法所采用圖像塊大小為3×3,字典大小為50.從圖1的對比中可以看出,K-means分割算法飛機輪廓并不完整,含有大量的非相關區(qū)域;FCM較K-means分割算法在抑制非相關區(qū)域較K-means效果好,但飛機輪廓也不完整;KFCM由于通過核方法提高了特征的區(qū)分性(采用高斯核,所用核參數σ=10),較K-means和FCM分割算法大量抑制了非相關區(qū)域,由于沒有考慮到空間信息,飛機輪廓并不完整;SFCM分割算法能較好抑制孤立的雜點,使得分割結果具有較好的平滑性,由于特征的較弱區(qū)分性,并不能去除大量的非相關區(qū)域;而本文所提的算法由于考慮了圖像局部信息、像素之間的內在相關性以及空間類別屬性約束信息,飛機輪廓保持比較完整,同時非相關區(qū)域被較好抑制,分割效果較為理想.

為了進一步驗證算法的性能,對加入噪聲的圖像進行分割實驗,在圖1(a)中加入標準方差為20的高斯噪聲,如圖2(a)所示,K-means,FCM,KFCM,SFCM及本文算法中采用的類別數J取為8,本文算法所采用圖像塊大小為5×5,字典大小為100.從圖2中可以看出,K-means,FCM分割算法中飛機輪廓被大量雜點干擾,難以判斷;KFCM(采用高斯核,所用核參數σ=10)和SFCM具有一定的噪聲抑制性,飛機輪廓也受到干擾,并不完整,同時混有大量非相關區(qū)域;而本文所提的算法飛機輪廓較為完整,由于所用圖像塊較大,噪聲抑制很好,使得不屬于飛機的像素被分為飛機像素,所以飛機輪廓有所擴大,但相比于K-means,FCM,KFCM和SFCM分割算法,本文算法取得了較好的結果.為了更加證實所提算法有效性,下面我們對機載對地道路紅外圖像進行實驗.

圖3 分割結果對比 (a)原始圖像;(b)K-means分割;(c)FCM分割;(d)KFCM分割;(e)SFCM分割;(f)本文算法

對于圖 3(a)的分割實驗,K-means,FCM,KFCM,SFCM及本文算法中采用的類別數J取為3,本文算法所采用圖像塊大小3×3,字典大小50.K-means,FCM,SFCM和KFCM(采用高斯核,所用核參數σ=2)算法雖能分割出道路的大致區(qū)域,但道路區(qū)域不夠清晰、完整,同時也將非道路區(qū)域分割為道路;本文所提算法分割得到的道路區(qū)域清晰、完整,更為接近實際情況,而且基本消除了非道路區(qū)域及雜點的干擾.我們將噪聲加入到紅外圖像中進行實驗,在圖3(a)中加入標準方差為20的高斯噪聲,如圖4(a)所示,K-means,FCM,KFCM,SFCM及本文算法中采用的類別數J取為3,本文算法所采用圖像塊大小3×3,字典大小50.K-means,FCM分割算法包含大量雜點,影響道路的判斷,而且道路區(qū)域也不夠完整;KFCM(采用高斯核,所用核參數σ=2)和SFCM分割算法可以較好地抑制部分野點,但道路區(qū)域也不夠完整;本文所提算法分割得到的道路區(qū)域更為接近實際情況,而且基本消除了背景、雜點及噪聲的干擾,分割效果較為理想.

圖4 含噪圖像分割結果對比 (a)噪聲圖像;(b)K-means分割;(c)FCM分割;(d)KFCM分割;(e)SFCM分割;(f)本文算法

圖5 本文算法目標函數收斂性曲線 (a)圖1;(b)圖2;(c)圖3;(d)圖4

從實驗結果可以看出,和傳統(tǒng)的聚類算法相比,考慮了圖像局部信息、像素之間的內在相關性以及空間類別屬性約束信息能有效地改進紅外圖像分割結果,同類區(qū)域內部能呈現較好的一致性,對平滑完整的目標分割效果較好,所提算法在噪聲環(huán)境下也具有更好的魯棒性.針對四組仿真實驗,我們補充了目標函數的收斂性曲線,如圖5所示,可以看出本文算法經過50次迭代都可滿足收斂要求.

5 結論

本文提出了一種結合稀疏編碼和空間約束的紅外圖像聚類分割新算法,擴展了傳統(tǒng)的聚類分割算法,考慮到像素之間的相關性,引入了空間類別屬性約束信息,并給出了一種交替優(yōu)化算法,聯(lián)合學習字典、稀疏系數、聚類中心和隸屬度,通過稀疏系數和隸屬度構造像素歸屬度完成分割.本文所提算法充分利用了像素的內在相關性、局部信息以及空間類別屬性約束信息,實驗結果也表明,本文方法能有效提高紅外圖像重要區(qū)域的分割效果,很大程度上降低了背景雜波對感興趣區(qū)域的分割干擾,適于復雜背景下紅外目標的準確分割.但是該算法也存在一些需要解決的問題,如字典大小及約束性參數等采用的是經驗值,如何自動選取這些參數有待進一步的研究.同時,為了更好地提高分割效果,將本文算法與結構字典[20]及有監(jiān)督的判別性字典學習算法[21]相結合也是將來的研究方向.

[1]Wu Y Q,Zhang J K 2010 Acta Phys.Sin.59 5495(in Chinese)[吳一全,張金礦2010物理學報59 5495]

[2]Liang Y M,Zhai H C,Chang S J,Zhang S Y 2003 Acta Phys.Sin.52 11(in Chinese)[梁艷梅,翟宏琛,常勝江,張思遠2003物理學報52 11]

[3]Song C X 2009 Microelectronics and Computer 26 60(in Chinese)[宋長新2009微電子學與計算機26 60]

[4]Tang Y G,Di Q Y,Zhao L X 2009 Acta Phys.Sin.58 15(in Chinese)[唐英干,邸秋艷,趙立興2009物理學報58 15]

[5]Ren JJ,He M Y 2008 J.Infrared Millim.Waves 27 72(in Chinese)[任繼軍,何明一2008紅外與毫米波學報27 72]

[6]Fan J C,Han M,Wang J 2009 Pattern Recognition 42 2527

[7]Wu J,Li J,Liu J,Tian JW 2004 International Conference on Robotics and Biomimetics Shenyang China August 22–26,2004 p742

[8]Jia JH,Jiao L C 2010 J.Infrared Millim.Waves29 69(in Chinese)[賈建華,焦李成2010紅外與毫米波學報29 69]

[9]Chen S C,Zhang D Q 2004 IEEE Trans.Syst.Man Cybern.34 1907

[10]Zhao F,Jiao L C,Liu H Q 2011 Frontiers of Computer Science in China 1 45

[11]Yang J C,Yu K,Gong Y H,Huang T S 2009 IEEE Conference on Computer Vision and Pattern Recognition Miami,USA,June 20–25,2009 p1794

[12]Wright J,Ma Y,Mairal J,Spairo G,Huang T,Yan S 2010 Proc.IEEE 98 1031

[13]Zhuang L S,Gao H Y,Liu C,Yu N H 2011 Journal of Software 22(Suppl.2)89(in Chinese)[莊連生,高浩淵,劉超,俞能海2011軟件學報22(增2)89]

[14]Zhao J J,Tang Z Y,Yang J,Liu E Q,Zhou Y 2011 J.Infrared Millim.Waves 30 156(in Chinese)[趙佳佳,唐崢遠,楊杰,劉爾琦,周越2011紅外與毫米波學報30 156]

[15]Wang J J,Yang J C,Yu K,Lv F J,Huang T S,Gong Y H 2010 CVPR San Francisco,USA,June 13–18,2010 p3360

[16]Liu L Q,Wang L,Liu X W 2011 ICCV Barcelona,Spain,November 6–13,2011 p2486

[17]Gao S H,Tsang WH,Chia L T 2010 ECCV Crete,Greece,September 5–11,2010 p566

[18]Yuan L,Liu J,Ye J P 2011 NIPS Sierra,Nevada,December 16–17,2011 p232

[19]Lee H L,Battle A,Raina R,Andrew Y N 2007 NIPS Vancouver,B.C.,Canada,December 3–6,2007 p801

[20]Ramirez I,Sprechmann P,Sapiro G 2010 CVPR San Francisco,CA June 13–18,2010 p3501

[21]Dahl A L,Larsen R 2011 BMVC Dundee,UK,August 29–September 2,2011 p77.1