结合稀疏编码和空间约束的红外图像聚类分割研究*

宋长新 马克 秦川 肖鹏

(青海师范大学计算机学院,西宁 810008)

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

1 引言

红外图像的分割就是根据一致性准则将图像划分为互不重叠的各具特性的区域,并区分出感兴趣目标的过程[1,2],是红外图像在军事和民用中应用的前提.红外图像分割的好坏关系到目标检测、识别和精确定位等任务.通常采取的算法有阈值化分割、基于边缘的分割及基于区域的分割等[1].由于红外图像具有纹理少、对比度差、信噪比低及复杂背景干扰等特点,导致了红外图像分割问题的困难[3].为了克服这些困难,提高分割的准确性,人们提出了许多改进的分割算法,如结合直方图或熵的阈值化分割[1,4]、基于C-V模型的水平集分割[5]、空间约束聚类分割[6,7]等分割算法.其中基于聚类的红外图像分割算法是一种重要的分割算法,分割过程中不需过多的人工干预,具有较好的抗噪性,适于红外图像自动分割,得到了大量研究.常用的聚类分割算法有K-means算法、模糊C均值算法(FCM)等,主要采用的是词袋(BOF:bag of features)的思想[8],为了更准确地从复杂背景中分割重要区域,后又在上述聚类算法基础上提出了空间约束FCM分割算法[7,9,10]、模糊核聚类分割算法[3]等.这些算法本质上都是K-means算法,对非凸的数据结构和彼此交叠严重的数据存在局限性[8],也较少考虑像素点在空间上的依赖关系,导致分割效果并不理想.

本文结合稀疏编码算法提出了一种红外图像聚类分割算法.稀疏编码是在超完备基上的一种稀疏表示,是计算机视觉领域的研究热点之一,稀疏编码方法广泛应用于图像恢复、识别及检测等模式识别的各个方面[11−14].稀疏编码对K-means聚类算法的扩展在向量量化构造BOF特征进行识别时具有明显改善[11,15,16],但直接将上述稀疏编码用于聚类进行图像分割容易产生过分割,难以得到有意义的区域,造成像素归类的判断问题.为此,我们在字典学习过程中,将原子的聚类算法引入其中,有助于缩减字典中原子所属类别的数目,同时将稀疏编码系数同原子对聚类中心的隶属程度相结合来判断像素所属的类别.这种处理方式能通过字典更好地反映类别内像素的内在联系性,由于采用局部块进行处理,自然地引入了局部信息,而且这些约束条件与聚类算法相融合也较为自然,在此基础上进一步根据图像特点对图像中像素的邻域像素施加空间类别属性约束提高分割质量.实验结果表明,所提算法能更好地实现复杂背景及干扰下红外图像重要区域的准确分割提取.

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难的非凸优化问题,难以求解,通常用1范数代替0范数,很多文献已经证明两者具有等价性[12].上述代价函数同时对变量D和α求解是非凸函数,但如果固定其中一个变量求解另一个变量,则是一个凸函数优化问题,一般分为两步求解:字典学习和稀疏编码,在固定字典D时求解稀疏系数α,在固定稀疏系数α时学习字典D,多次迭代进行优化,直到收敛.当前稀疏编码应用的难点在于根据问题设计反映任务需要的字典.

3 空间约束下结合稀疏编码的聚类算法

3.1 稀疏编码观点下的K-means算法

K-means聚类算法是一种无监督类别划分方法,通过最小化样本和所属聚类中心的距离进行优化,其目标函数表示为:其中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算法相比,具有如下优点[11]:1)(3)式由于约束条件更为宽松,较K-means具有更低的目标函数误差,对样本有更低的重构误差,可保留样本更多的信息;2)通过稀疏性能捕捉图像更显著的特征;3)图像的统计特性表明图像块本身就具有稀疏性,更符合图像的特性.可以看出采用(3)式的样本只与几个聚类中心有关(对应于稀疏系数的非零元素),与其他的聚类中心不存在关系.

3.2 结合稀疏编码的聚类分割算法(SCC)

从(3)式中可以看出,样本xi从单纯的像素点聚类扩展到以该像素点为中心的图像块聚类,利于排除野点的干扰,具有一定的空间约束性;而且通过联合所有像素点所在像素块进行学习字典,各个局部像素块通过字典建立了某种联系,挖掘了它们之间一定的内在相关性,有利于利用像素的相似性进行聚类;稀疏系数可以捕捉图像更显著的特征,抑制图像中的非结构信息,如杂点、噪声和其他一些外来干扰.但直接将上述稀疏编码用于聚类进行图像分割有两个困难:1)由于K＞m,字典D中的原子个数较多,直接将D中的原子作为聚类中心会造成类别数过多,容易导致过分割,难以得到有意义的区域;2)得到的稀疏系数向量难以反映像素点所属的类,造成像素归类的判断问题.

我们采用的思想是在字典学习过程中,将原子的聚类算法引入其中,有助于缩减字典中原子所属类别的数目,防止产生过分割的问题;同时将稀疏编码系数同原子对聚类中心的隶属程度相结合来判断像素所属的类别.但是字典中原子之间具有较大的相关性,如果采用K-means聚类算法强制将原子划分为某一类别,容易产生较大的聚类误差,对后续的像素归类判断产生误导.这里我们采用FCM算法进行原子的聚类.FCM是在K-means算法的基础上引入了模糊隶属度的概念,样本可以归属于多个聚类中心,不再是硬划分.定义样本xi对第c类的模糊隶属度函数为wci,且隶属度函数w满足

ciFCM的目标函数为:式中 p ≥ 1 是隶属度指数,一般取为2.若式中的隶属度函数wci只取0或1,则为K-means聚类算法.通过迭代更新隶属度函数wci和聚类中心vc最小化目标代价函数.FCM与(3)式不同之处在于:FCM算法中样本通过欧氏距离与所有聚类中心有联系,而(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的归属度为

如果同时优化全部4个参数比较困难,这里采用交替优化迭代方法求解Z,U,V,W.随机选取样本初始化字典后,首先求解稀疏系数；然后更新字典；最后计算聚类中心和隶属度.具体求解算法如下.

1)稀疏编码:固定Z,V,W,即

2)字典学习:固定Z,U,W,学习字典V,此时的优化目标函数为

对V中的原子逐一进行求解,固定其他原子,则对原子vl有如下表示:

其中 qt是稀疏系数 U 的行向量 (t=1,···,J),U=[q1;q2;·;qJ]. 令与原子 vl无关的项 S=则 (10)式可以写成

其中η为调节参数,将上式对vl微分有

然后,归一化

如此对V中的原子逐一进行更新.

3)更新聚类中心:固定V,W,U,通过

4)更新隶属度:固定Z,V,U,通过

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

通过上述的多次迭代优化过程,可以求出字典V,稀疏系数U,字典聚类中心Z及隶属度W.最后完成聚类分割,需要判断像素点所属的类,计算样本xi对于聚类中心zc的归属度:根据样本对于各个聚类中心的归属度按照最大化原则进行分类,即可得到最终聚类结果,从而完成红外图像的聚类分割.

4 实验结果与分析

为了验证本文所提红外图像分割算法的性能,我们采用机载对地面飞机和道路的红外图像进行实验,分别如图1(a)和图3(a)所示,并采用K-means,FCM,模糊核聚类(KFCM)和结合空间信息的模糊聚类(SFCM)分割算法结果作为对比.首先,我们讨论一下具体的参数选择,FCM,KFCM,SFCM和本文算法中的隶属度指数p统一取为2,FCM,KFCM及SFCM算法的迭代次数为100,本文算法中稀疏性参数λ取0.001,γ=0.2,η=0.5.空间约束目的是使得邻域内的所有像素尽量具有相同的类别,对于SFCM和本文算法空间约束的邻域大小选择,正如文献[8—10]中所论述的,选择较大的邻域进行空间约束,如7×7,9×9等,虽能使得分割结果更为平滑完整,较好地消除野点及噪声,但难以避免会丢失图像中固有的边缘或较小目标等信息.一般来说,如果目标较大,且较为平滑完整,则可适当地选择较大邻域.对于本文的图像,我们选择大小为3×3的邻域用于SFCM和本文算法的实验;其中对于空间约束惩罚系数α,选取过小的α将难以起到空间约束的作用,选取过大的α将抹杀图像像素的固有属性,这里我们在SFCM和本文算法中选取空间约束惩罚系数α=4.KFCM算法所用的核函数及其参数在后面实验中给出.另外,本文算法由于采用像素邻域的图像块向量代替了原来的像素值,可以看出如果取较大的图像块,则容易抹杀了图像的细节信息,本文算法实验中选取图像块大小为3×3.如文献[11,12,20]所示,并对数据进行归一化处理,字典大小可以通过冗余性指数N和图像块向量维数m确定,即K=N×m,冗余性指数N反映了稀疏系数的稀疏性,N越大则越稀疏,本文中N取值范围可设为5—10.K-means,FCM,KFCM,SFCM及本文算法中如何选择类别数J是一个普遍的难题,与诸多文献类似,我们通过实验根据不同的问题选择不同的类别数.针对多组实验,本文算法的迭代次数统一选为50,其收敛性将在后面予以讨论.

实验中计算机为i5-2.5 GHz Intel酷睿处理器,4 GB内存,仿真工具为Matlab 7.10.红外图像分割的效果一般无法进行定量评价,一个广泛采用的评价原则就是看能否分割出期望的或者重要的区域,并且尽量区分背景区域和目标区域.本实验主要观察分割算法能否分割出重要区域,保持重要区域的完整性,抑制非重要区域对重要区域的误导.可以看出图1(a)和图2(a)所示的重要区域分别为飞机和道路.

图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分割算法飞机轮廓并不完整,含有大量的非相关区域;FCM较K-means分割算法在抑制非相关区域较K-means效果好,但飞机轮廓也不完整;KFCM由于通过核方法提高了特征的区分性(采用高斯核,所用核参数σ=10),较K-means和FCM分割算法大量抑制了非相关区域,由于没有考虑到空间信息,飞机轮廓并不完整;SFCM分割算法能较好抑制孤立的杂点,使得分割结果具有较好的平滑性,由于特征的较弱区分性,并不能去除大量的非相关区域;而本文所提的算法由于考虑了图像局部信息、像素之间的内在相关性以及空间类别属性约束信息,飞机轮廓保持比较完整,同时非相关区域被较好抑制,分割效果较为理想.

为了进一步验证算法的性能,对加入噪声的图像进行分割实验,在图1(a)中加入标准方差为20的高斯噪声,如图2(a)所示,K-means,FCM,KFCM,SFCM及本文算法中采用的类别数J取为8,本文算法所采用图像块大小为5×5,字典大小为100.从图2中可以看出,K-means,FCM分割算法中飞机轮廓被大量杂点干扰,难以判断;KFCM(采用高斯核,所用核参数σ=10)和SFCM具有一定的噪声抑制性,飞机轮廓也受到干扰,并不完整,同时混有大量非相关区域;而本文所提的算法飞机轮廓较为完整,由于所用图像块较大,噪声抑制很好,使得不属于飞机的像素被分为飞机像素,所以飞机轮廓有所扩大,但相比于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)算法虽能分割出道路的大致区域,但道路区域不够清晰、完整,同时也将非道路区域分割为道路;本文所提算法分割得到的道路区域清晰、完整,更为接近实际情况,而且基本消除了非道路区域及杂点的干扰.我们将噪声加入到红外图像中进行实验,在图3(a)中加入标准方差为20的高斯噪声,如图4(a)所示,K-means,FCM,KFCM,SFCM及本文算法中采用的类别数J取为3,本文算法所采用图像块大小3×3,字典大小50.K-means,FCM分割算法包含大量杂点,影响道路的判断,而且道路区域也不够完整;KFCM(采用高斯核,所用核参数σ=2)和SFCM分割算法可以较好地抑制部分野点,但道路区域也不够完整;本文所提算法分割得到的道路区域更为接近实际情况,而且基本消除了背景、杂点及噪声的干扰,分割效果较为理想.

图4 含噪图像分割结果对比 (a)噪声图像;(b)K-means分割;(c)FCM分割;(d)KFCM分割;(e)SFCM分割;(f)本文算法

图5 本文算法目标函数收敛性曲线 (a)图1;(b)图2;(c)图3;(d)图4

从实验结果可以看出,和传统的聚类算法相比,考虑了图像局部信息、像素之间的内在相关性以及空间类别属性约束信息能有效地改进红外图像分割结果,同类区域内部能呈现较好的一致性,对平滑完整的目标分割效果较好,所提算法在噪声环境下也具有更好的鲁棒性.针对四组仿真实验,我们补充了目标函数的收敛性曲线,如图5所示,可以看出本文算法经过50次迭代都可满足收敛要求.

5 结论

本文提出了一种结合稀疏编码和空间约束的红外图像聚类分割新算法,扩展了传统的聚类分割算法,考虑到像素之间的相关性,引入了空间类别属性约束信息,并给出了一种交替优化算法,联合学习字典、稀疏系数、聚类中心和隶属度,通过稀疏系数和隶属度构造像素归属度完成分割.本文所提算法充分利用了像素的内在相关性、局部信息以及空间类别属性约束信息,实验结果也表明,本文方法能有效提高红外图像重要区域的分割效果,很大程度上降低了背景杂波对感兴趣区域的分割干扰,适于复杂背景下红外目标的准确分割.但是该算法也存在一些需要解决的问题,如字典大小及约束性参数等采用的是经验值,如何自动选取这些参数有待进一步的研究.同时,为了更好地提高分割效果,将本文算法与结构字典[20]及有监督的判别性字典学习算法[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