特征保持

特征保持（精选4篇）

特征保持 篇1

0 引言

一些图像传输应用场合由于传输带宽、实时性要求等限制,要求对图像进行低比特率压缩并传输,图像低比特率压缩会严重损失图像边缘、纹理等几何特征。当解压图像用于目标识别等任务时,需要进行特征提取,那么解压图像边缘等特征损失过多会严重干扰后续图像探测识别等任务,降低目标识别率[1]。因此在图像压缩技术发展迅速的同时,如何在图像低比特率压缩的同时将图像边缘等特征保留下来成为迫切需要解决的问题。

图像的大部分信息是由图像的特征如边缘和纹理表示的,单纯靠有损压缩提取和保持特征信息有一定困难。现有的应对边缘等特征损失的方法有图像增强后再压缩[2,3];图像解压后增强,对于边缘保持有一定效果。Dirck Schilling等人提出图像压缩编码与图像边缘特征保持相结合的图像压缩思想[4],适用于低比特率图像压缩传输。

近年来出现的基于小波的Contourlet变换(WBCT)[5,6,7]是一种方向性多尺度几何分析工具,它对图像边缘纹理等特征保持的性能优于小波变换,非常适合于低比特率图像压缩,因此,本文借鉴Dirck Schilling等人思想,考虑用基于小波的Contourlet变换压缩和边缘特征保持相结合的图像压缩方法进行低比特率图像压缩,以期达到图像压缩同时保留边缘特征的目的。

1 面向边缘特征保持的图像压缩方法

1.1 总体思想

我们的目的是在低比特率压缩条件下,解压图像可以更快地被人们所识别。因此面向边缘特征保持的图像压缩方法包括两个部分:图像压缩和边缘保持。方法流程如图1所示。源图像Io通过边缘检测器,检测出可能帮助人们识别图像的显著边缘E。然后对提取出的边缘通过标准边界链码,如Freeman链码,进行编码。编码后的边缘信息作为压缩信息的一个组成部分进行传输。源图像Io还需进行普通图像压缩,变换方式选取基于小波的Contourlet变换(WBCT)。最终的压缩图像包含边缘编码信息和图像变换压缩信息两部分。解码器通过结合边缘定位信息E和WBCT解压图像Ir的像素灰度信息,通过边缘保持重建,最终得到边缘信息保持的解压图像Ie。

下面将对面向边缘特征保持的图像压缩方法中的WBCT变换、边缘编码和边缘保持重建等主要环节的关键技术进行详细阐述。

1.2 基于小波的Contourlet变换(WBCT)

二维离散小波变换只能表示水平、垂直、对角三个方向的细节信息,不能分析其他方向。而方向性是图像的一个重要特征,如果对方向性分析不全面,就会导致它对图像边缘和纹理的表示效率不高。为了能更好的分析图像中的方向性,2002年Do和Martin Vetterli提出轮廓波(Contourlet)变换[8,9,10,11],它是一种多分辨率、多方向性的图像表示方法。Contourlet分解变换的实现分为两个步骤:拉普拉斯金字塔(Laplacian Pyramid,LP)分解和方向滤波器组(Directional Filter Bank,DFB)分解。其原理如图2(a)所示。每一次LP分解比Mallat分解[12]多出1/4的冗余信息,不利于图像压缩。因此Eslami等人提出了基于小波的contourlet变换(Wavelet-based Contourlet Transform,WBCT),一种非冗余版本的Contourlet变换。WBCT的基本思想是用小波变换的Mallat塔式分解代替Contourlet变换的LP分解,然后使用DFB分别对Mallat分解中的高频子带进行方向分解,其原理如图2(b)所示。

相同比例的WBCT系数和小波系数重建Barbara图像局部效果如图3所示,其中M表示重建所用系数个数。从图中看出,WBCT重建图像纹理特征较小波重建图像保持的更好,其信噪比高于小波重建图像。

1.3 边缘编码

对于边缘保持的处理,首先需要利用边缘算子检测出图像边缘,然后需要对边缘位置进行压缩编码,以确保图像解压缩后进行边缘保持操作时提供准确边缘位置。

链式编码是一种边界的编码表示法,是用曲线起始点的坐标和边界点方向代码来描述曲线或边界的方法。链式编码对多边形的表示具有很强的数据压缩能力,能够使数据量大为减少。Freeman链式编码[13]是二值图像的无损压缩编码算法,其基本编码规则是,对每个连通区域,首先选择一个边界点并记录下坐标,然后编码器沿着边界移动,每移动一步记录下本次移动所对应的方向码,直到编码器回到初始点结束,则这个连通区域被完全编码。然后对下一个连通区域同样编码。Freeman 4方向链码的方向数定义顺序如图4(a)所示。相应地,链码定义如图4(b)所示,即根据当前边界点相对于上一个边界点像素的坐标增量(Δx,Δy)来确定当前边界点的Freeman编码,编码取值分别为1、2、3、4,取代边界点原像素坐标,从而达到压缩目的。本文选取Freeman 4方向链码对边界编码。

1.4 边缘保持重建

低比特率压缩图像解压缩后,得到边缘损失的WBCT解压图像和边缘位置两部分信息,通过边缘保持重建得到最终边缘保持的解压图像。边缘保持重建示意如图5(a)(g)所示。图5(a)中显示的是原始图像边缘。重建流程参见图6,具体如图5。

1)解压缩:解码器通过解码得到WBCT逆变换结果,如图5(b)所示,同时解码器通过解码得到边缘位置;

2)平滑:图5(b)经过平滑得到平滑后边缘图5(c);

3)计算:根据平滑边缘图5(c)距离边缘位置两侧处的灰度值,计算得到理想边缘图5(d);

4)(d)-(c):理想边缘图5(d)与平滑边缘图5(c)之间相减得到灰度差值图5(e),这个差值是边缘保持重建所需的重要信息;

5)(b)+(e):差值图5(e)叠加在重建边缘图5(b)上,得到增强后的边缘图5(f);

6)平滑:最后,为消除增强边缘的突兀性,对增强边缘图5(f)进行平滑得到最终保持良好的边缘图5(g),完成边缘保持重建过程。

2 仿真实验结果

为验证基于WBCT的面向边缘特征保持的图像压缩算法的效果,以标准图像Rice和自选图像Road和Airport为例进行了仿真,并与基于普通WBCT压缩算法的结果进行了比较。对于检验指标的选取,由于图像对比度[14]通常表现了图像画质的清晰程度,边缘保持完整的图像较边缘模糊的图像对比度高,层次感强,清晰度高,因此用它来检验解压图像边缘保持程度。两种算法的重建结果比较见图7和表1。其中图7是对系数比例为1%的本文算法压缩重建结果和相同压缩比下普通WBCT压缩重建结果的比较。可以看出图7(g)~(i)相对于(d)~(f)边缘轮廓更加完整和清晰。

重建结果的对比度比较见表1。从表中数据可以看出,相同比特率下(对应本文算法WBCT系数分别为1%和0.5%)面向边缘特征保持的WBCT图像压缩算法相对于普通WBCT压缩算法的重建结果普遍具有更高的图像对比度。

3 结论

在低比特率图像传输应用中,用户尽可能准确地获取对图像内容的理解是非常重要的,它可以使用户操作变得高效。然而在低比特率下提高重建图像识别率的目标将比普通压缩需要更多处理过程。我们在前面已经详细阐述了一种面向边缘特征保持的图像压缩算法,允许在低比特率下重建有利于识别的图像。接下来的工作是提高边缘编码效率以使边缘尽可能占用很少的空间资源。进一步的计划是证明这种压缩方法对图像识别性能的影响,从而确切证明该压缩方法的有效性。

稀疏表示保持的鉴别特征选择算法 篇2

特征选择[1]用于从高维特征空间中选择特征子集,并保持特征子集的原始物理特性,根据使用类别标签与否,特征选择算法可分为非监督和监督两种,本文主要研究监督特征选择算法。经典的监督特征选择算法包括Relief F[2],Fisher Score[3]以及多簇 特征选择(Multi-Cluster Feature Selection,MCFS)[4]等,它们通过特征和类别标签之间的相关性来度量特征的重要性,但是大多数传统特征选择算法对每个特征的度量是独立进行的[3,5],并且将特征逐个添加至所选特征子空间,这种选择方式的局限性在于特征之间的相关性被忽略[4]。最近,l2,1范数正则化优化已经应用到特征选择算法,此类算法通过对特征选择矩阵进行l2,1范数最小化约束来选择特征[6,7]。

与此同时,稀疏表示作为一种基于部分数据的表示,已经吸引了越来越多的关注,并已广泛应用于模式识别和机器学习领域[8]。稀疏表示方法假设一个超完备字典中样本的稀疏线性组合可以重构一个给定的样本,例如Wright等提出的 基于稀疏 表示的分 类方法[9](Sparse Representation-based Classification,SRC),该方法的优化问题惩罚线性组合系数的l1范数,SRC尝试使用所有训练样本的稀疏线性组合来表示一个给定的测试样本,并且认为稀疏非零表示系数集中在测试样本的同类训练样本上。受到SRC的启发,很多基于稀疏表示的特征抽取算法出现,例如文献[10-11]提出的稀疏表示分类器引导的监督特征抽取算法,该算法旨在减少类内重构残差,并与此同时增加类间重构残差,但二者在目标函数的形式上有所不同,文献[10]采用比值方式文献[11]采用差值方式。与特征选择算法不同,特征抽取将原始特征进行转换从而实现数据降维,特征的原始物理特性发生变化。回顾经典的监督特征选择算法,却不存在与SRC直接关联的,本文提出了一种稀疏表示保持的鉴别特征选择(SRPFS)算法,旨在寻找一种线性映射使得在所选特征子空间中,样本的稀疏类内重构残差足够小并且稀疏类间重构残差足够大,并用于优化提出的l2,1范数最小化的目标函数。

1 基于稀疏表示的分类方法

假设样本集为X = [x1,x2,⋯,xn]∈ Rm × n,类别数为c ,类别标签向量z = [l1,l2,⋯,ln]T,其中ln表示X中第n个样本即xn的所属类,给定一个测试样本y ∈ Rm,然后使

用以训练样本为基础向量的超完备字典表示y ,如下:

假设式(1)的系统是欠定的( m< n ),通过求解如下的优化问题可以得到最稀疏解:

然而,公式(2)中的L0优化问题是NP难题而且非常耗时,最近的研究理论[12,13]表明式(2)也可以通过寻找以下优化问题的解决办法进行求解:

该优化问题可以在多项式时间内通过标准线性规

划算法来解决[14],或者使用一种更高效的算法[15],然后利用式(3)中求解的稀疏表示系数向量 δ 对y进行分类,令 φk:RM→ RM(k = 1,2,⋯,c) 表示一种能够从 δ 中选择出与第k类有关的稀疏表示系数的函数[9],即 φk(δ) ,然

后计算y及其第k类原型之间的残差:

如果rl′(y) = minkrk(y) ,SRC将y分到第l′ 类。

2 稀疏表示保持的鉴别特征选择

2.1问题描述

X中除第i个样本xi后,xi所属类为li剩余n - 1个样

本记为Xi= [x1,⋯,xi - 1,xi + 1,⋯,xn]∈ Rm × {n - 1},通过解决L1

优化问题 得到xi的关于Xi的稀疏表 示系数向 量

δiw定义为xi的稀疏类内表示系数向量,该向量的非零元素与li类训练样本相关;δib定义为xi的稀疏平均类间表示系数向量,该向量的非零元素与c类中除li类的剩余c - 1类训练样本相关,即c - 1类的稀疏平均类间表示系数向量;因此,xi的稀疏类内和类间重构分别表示为:

这里的目标是寻找一种特征选择矩阵U ∈ Rm × m进而选择出m′( m′ < m )个特征,U满足的条件为:元素只有‘0’或‘1’;每行或每列中‘1’的数目不超过1;只有m′ 行或列的元素为‘1’。

通过使用U可以使用特征选择后的类内以及类间训练样本对xi进行重构,即稀疏类内重构UTXiδiw以及稀疏类间重构UTXiδib,稀疏类内类间重构残差采用F-范数进行度量,表示如下:

基于SRC决策规则,希望在所选特征子空间中样本xi尽可能接近其稀疏类内重构并同时尽可能远离其稀疏类间重构,考虑所有样本,SRPFS的目标函数定义如下:

式中:β 是一个权衡参数;1m∈ Rm是一个元素为1的向量,然而式(10)是NP难题,因此将关于U的二元约束放松到l2,1范数最小化约束[6,7],此时目标函数可以重写为:

式中:α 是一个权衡参数;.2,1表示l2,1范数,l2,1正则化

项控制U的大小并同时保证U的行稀疏性(行元素接近于0),使SRPFS为数据表示选择出最具鉴别性的特征。

2.2优化

式(11)的向量形式表示如下:

式中 : Sw= [δ1w′,δ2w′,⋯,δnw′]∈ Rn × n, Sb= [δ1b′,δb2′,⋯,δbn′]∈Rn*n,δiw′以及 δib′分别定义为:

令:

对L(U) 关于U求导,可以得到下式:

t = t + 1 ;

∂L(U)

直到收敛准则满足;输出:U 。

= 2αPU - 2XSw(XT- STwXTU) + 2βXSb(XT- SbTXTU)

∂U

(16)

2.3 L(U) 的凹性研究

式中P是一个对角矩阵,第r (r = 1,2,⋯,m) 个轴元素为Prr= 1 (2U(r,:)2)。为了求解式(12)中的U ,对L(U)关于U求导,然而很难用理论证明L(U) 是凹函数,将∂L(U) ∂U置为0,得到关于U的更新规则:

∂L(U)

对式(16)中的

关于U求导,得到下式:

∂U

∂2L(U)

= 2αP + 2XSwSTwXT- 2βXSbSbTXT

(18)

∂U2

根据凹函数的性质,式(15)中的L(U) 是凹的,当且

U ← (αP + XSwSTwXT- βXSbSbTXT)-1(XSwXT- βXSbXT)

∂2L(U)

仅当式(18)中的

是正定的,令:

∂U2

(17)

G = 2XSwSTwXT- 2βXSbSbTXT

为了得到最优U ,重复上述过程直到收敛标准满足,即|L(Ut)- L(Ut + 1)|< ε ,算法1给出了优化的详细过程描述。

(19)

因此式(18)可以重写为:

∂2L(U)

= 2αP + G

(20)

∂U2

算法1:SRPFS算法

2αP是正定的因为它是一个轴元素为正数的对角矩阵,根据正定矩阵的定义,如果G是正定的很容易证明2αP + G是正定的,然而很难直接证明G的正定性,事实上通过在实验中对参数 β 进行控制来保证G的正定性,β 的取值在实验部分给出。在假设2αP + G是正定的前提下,通过下面的定理证明目标函数在算法1中的迭代过程中的收敛性:

输入:训练数据集X = [x1,x2,⋯,xn]∈ Rm × n,类别标

签向量z = [l1,l2,⋯,ln]T

,权衡参数 α ,β ;

将特征选 择矩阵U初始化为 单位矩阵 即

U0∈{0,1}m*m,迭代次数:t = 1 ;

|

n

通过式(5)计算稀疏表示系数向量 δi|

;

|

i = 1

通过式(13)和式(14)计算Sw以及Sb;重复:更新对角矩阵Pt,即:

定理1:式(12)中的目标函数值在算法1中的迭代过程中单调减小。

1

é

ùúúúú

ê2Ut - 1(1,:)2

证明:很容易证明式(12)就是解决以下的问题:

êêêêë

Pt=

⋯

+ αTr[UTPU]

mUin X - UTXSw2

- β X - UTXSb2

1

F

F

2Ut - 1(m,:)2ûú

(21)

通过式(17)更新Ut;

相应地,在第t次迭代中有:

2

2

- βX

- (Ut + 1)TXSb

+ αTr[UTPU] ⇒X

- (Ut + 1)TXSw

Ut + 1= mUin X - UTXSw2F

- β X - UTXSb2

+

F



F

F2

2

αTréë(Ut + 1)TPtUt + 1ùûX

- (Ut)TXSw

- βX- (Ut)TXSb

+ αTré(Ut)TPtUtù

F



F

ë

û

即:

utr+ 122

utr222utr2

2

2

2

2

X

- (Ut + 1)TXSw

- βX

- (Ut + 1)TXSb

- βX- (Ut)TXSb

X- (Ut)TXSw

+ α∑

+ α∑

⇒

F



F

F

æ

F



2utr2

r

r

utr+ 122

ö÷÷ø

2

2

+ α∑utr+ 12- αçç∑utr+ 12-∑r r r

X

- (Ut + 1)TXSw

- (Ut + 1)TXSb

- βX



F



F

2utr2

è

utr222utr2

æ

ö÷÷ø

2

2

- βX- (Ut)TXSb

+ α∑utr2- αçç∑utr2-∑r r r

X

- (Ut)TXSw

F

F



è

根据[7]中的引理,对于任意非零向量u ,ut∈ Rm,下面的不等式成立:

因此,有以下不等式成立:

即:

utr22

+ α∑utr+ 12X

+ αUt + 12,1X- (Ut)TXSw

它表明式(12)中的目标函数值在算法1中的迭代过程中单调减小。

3 实验

在本节中,通过实验验证算法SRPFS的性能,首先将SRPFS与经典的监督特征选择算法进行比较,然后分析SRPFS的收敛性。

3.1实验设置

4个公共数据集:Wine[16],Breast Cancer Wisconsin(Diagnostic)[16],Connectionist Bench (Sonar,Mines vs.Rocks)[16]以及COIL20[17],Wine,Breast Cancer Wisconsin和Connectionist Bench来自标准UCI库;来自哥伦比亚图像数据库的COIL20包含20个对象,数据集的描述在表1中给出。

将SRPFS与All Features,Fisher Score,MCFS,以及Relief F进行比较,实验中为保证式(20)中G的正定性,β 在4个数据集上分别设置为10-3,10-5,10-3,10-2,使用快速 迭代收缩 阈值算法(Fast Iterative Shrinkage and Thresholding Algorithm ,FISTA)[16]求解式(5),FISTA中的规范 化参数设 置为1,α 的调整范 围为{1,10-1,10-2},对于MCFS以及Relief F邻居样本数设置为5,由于Connectionist Bench和COIL20的特征数大于50,相应的所 选特征数 分别设为 {1,2,⋯,30} ,{1,2,⋯,512} ,即最大值取数据集维度的50%。

3.2分类识别率比较

对于每个数据集,随机选择每类样本集的5种方法在4个数据集上的平均最高识别率(±std)的比较,如表2所示。选择的样本中80%做训练集,剩余样本做测试集,为了证明不同算法的可靠性,将训练集以及测试集的选择过 程重复10次 ,All Features,Fisher Score,MCFS,Relief F以及SRPFS在4个数据集上的平均最高识别率及标准差在表2中给出,可以看出所有的特征选择算法优于All Features,因此,特征选择算法有助于提高识别率,由于SRPFS中保持了样本之间的稀疏相关性,SRPFS从识别率和稳定性两方面的性能明显优于其他方法。

3.3收敛性

在本节中,通过实验证明所提出的迭代算法单调减小目标函数值,直到收敛,图1展示了式(12)中的目标函数值在4个数据集上的收敛曲线图,可以看出目标函数在数次迭代后收敛。

4 结语

在本文中,提出了一种新的监督特征选择算法,称为稀疏表示保持的鉴别特征选择(SRPFS),其目的是选择鉴别性特征子集,使得在所选特征空间中,样本的稀疏类内重构残差和稀疏类间重构残差的差值最小化。通过实验验证SRPFS的性能并与其他4种方法即All Features,Fisher Score,MCFS,以及Relief F在4个公共数据集上进行比较,实验表明SRPFS在识别率以及稳定性方面明显优于其他方法。在未来,考虑将SRPFS的思想应用到非监督特征选择算法研究中,由于不使用样本的类别标签这将是一个更大的挑战。

摘要：稀疏表示作为一种基于部分数据的表示,已经吸引了越来越多的关注,并广泛应用于模式识别和机器学习领域。提出一种新的算法,称为稀疏表示保持的鉴别特征选择(SRPFS),其目的是选择鉴别性特征子集,使得在所选特征子空间中,样本的稀疏类内重构残差和稀疏类间重构残差的差值最小化。与传统算法选择特征的独立性方式不同,该算法以批处理方式选择最具鉴别性的特征,并用于优化提出的l2,1范数最小化的目标函数。在标准UCI数据集和哥伦比亚图像数据库的实验结果表明,该算法在识别性能和稳定性方面优于其他经典特征选择算法。

特征保持 篇3

关键词：局部保持投影,特征提取,半监督,高光谱

0 引 言

高光谱遥感技术利用成像光谱仪纳米级的光谱分辨率,以几十或几百个波段同时对地物成像,能够获得地物接近连续的光谱信息,成为高分辨对地观测系统的重要组成部分之一。然而,高光谱传感器为地物分类和识别提供细致光谱特征的同时也带来了大量的冗余数据,给后续分类处理带来了难度。为了去除这些冗余数据,通常需对高光谱数据进行特征提取。

局部保持投影[1](Locality Preserving Projections, LPP)是最近提出的一种线性特征提取算法,它是Laplacian Eigenmap[2] 流形学习算法的线性近似,该算法既克服了主成分分析和Fisher判别分析[3]等线性特征提取算法难以保持原始数据非线性流形的缺点,同时又解决了非线性流形学习方法[4]难以直接映射新样本的问题,因此在模式分类领域得到广泛应用[5,6]。然而,LPP算法仅能保持近邻样本对的局部结构,对原本相互远离的样本,LPP算法并未加以约束。对此,Yang等提出无监督鉴别保持投影算法[7],其在建模的同时考虑局部和非局部散度,从一定程度上克服了LPP存在的问题,但该算法在小样本条件下会出现矩阵奇异,导致算法无法求解。王建国等则利用非局部散度和局部散度之差作为鉴别准则,避免了矩阵奇异问题,然而分类精度有所降低[8]。

上述算法虽对LPP性能有一定改善作用,但其仅能够保证经过特征提取后样本的相对位置能够得到保持,无法保证提取的特征更容易分类。 针对这一缺点,本文提出一种改进算法,该算法在LPP算法的目标函数中加入标记样本信息,通过标记样本所携带的类别信息来约束未标记样本的相对位置;同时,还通过在目标函数中加入正则项以避免矩阵奇异问题。由于这种算法在训练过程中同时用到了标记样本和未标记样本——这是一种介于有监督学习和无监督学习之间的半监督学习思想[9],故将这种改进算法称为半监督保持投影(Semi-supervised Preserving Projections,SPP)算法。实验结果表明,经过改进的SPP算法进行特征提取后,不同类别样本的区分性增强,分类精度比LPP算法有较大提高。

1 局部保持投影算法

局部保持是一种典型的线性流形学习算法,其原理可用谱图理论进行解释。设X=[x1,x2,…,xN]是由m维向量构成的数据集合,x1,x2,…,xN∈Rm。LPP目标是寻找一个投影矩阵W,该矩阵可以将位于高维空间的数据映射至一个低维子空间Rd(d≪m)中,并同时尽可能使数据的局部相对位置保持不变,即:如果样本对在原始高维空间中是相互靠近的,那么经投影矩阵变换至低维子空间后,该数据对仍然保持相互靠近。令数据集在低维子空间Rd中表示为Z=[z1,z2,…,zN],则Z=WTX。

为了使数据的局部相对位置保持不变,LPP算法的目标函数定义如下:

$\min \left(\frac{1}{2}{\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm N}}\parallel }}\mathit{y}{}_i-\mathit{y}{}_j\parallel {}^2\mathit{S}{}_{ij}\right)(1)$

式中:yi=WTxi,且W=[w1,w2,…,wd];Sij是权重矩阵,采用k近邻法来定义:

$\mathit{S}{}_{ij}=\{\begin{array}{l}\exp \left(-\frac{\parallel \mathit{x}{}_i-\mathit{x}{}_j\parallel {}^2}{t}\right),\mathit{x}{}_i\in {\rm N}{}_k(x{}_j)\\ 0,\text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\end{array}(2)$

式中:t为大于0常数;Nk(xi)表示由xi的k个最近邻样本点组成的集合。

对式(1)进行简单的变量代换,可得到下式:

$\begin{array}{l}\frac{1}{2}{\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm N}}\parallel }}\mathit{y}{}_i-\mathit{y}{}_j\parallel {}^2\mathit{S}{}_{ij}\\ =\frac{1}{2}{\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm N}}\parallel }}\mathit{W}{}^{\text{Τ}}\mathit{x}{}_i-\mathit{W}{}^{\text{Τ}}\mathit{x}{}_j\parallel {}^2\mathit{S}{}_{ij}\\ ={\displaystyle \sum _i\mathit{W}}{}^{\text{Τ}}\mathit{x}{}_{i}d{}_{ii}\mathit{x}{}_i^{\text{Τ}}\mathit{W}-{\displaystyle \sum _{i,j}\mathit{W}}{}^{\text{Τ}}\mathit{x}{}_i\mathit{S}{}_{ij}\mathit{x}{}_j^{\text{Τ}}\mathit{W}\\ =\mathit{W}{}^{\text{Τ}}\mathit{X}(\mathit{D}-\mathit{S})\mathit{X}{}^{\text{Τ}}\mathit{W}\\ =\mathit{W}{}^{\text{Τ}}\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}}\mathit{W}(3)\end{array}$

式中:D=diag(d11,d22,…,dNN)为对角矩阵,其对角线上的元素的矩阵S中对应的列(或行)元素之和,即$d{}_{ii}={\displaystyle \sum _{j=1}^{{\rm N}}\mathit{S}}{}_{ij}‚\mathit{L}=\mathit{D}-\mathit{S}$,矩阵L为Laplacian矩阵。

2 半监督保持投影算法

局部保持投影算法能够使近邻样本对在低维子空间中仍然保持相互邻近,然而由于其没有利用标记样本所携带的类别信息,无法保证原始数据投影至低维空间后更有利于进行分类判别。为了克服LPP算法的这一缺点,本文提出一种同时利用大量未标记样本和少量标记样本的半监督保持投影(SPP)算法。在SPP算法中,为了利用标记样本的类别信息,在目标函数中引入了类似于Fisher判别思想[10]的类内散布矩阵和类间散布矩阵;并且定义了非局部结构信息,使非近邻样本对的相对结构在低维空间中也能得到保持;同时还在目标函数中增加一正则项,克服了矩阵奇异问题。

2.1 算法描述

假定标记样本集为L={xi,yi}${}_{i=1}^{{\rm N}}$,类别标签yi∈{1,2,…,c},其中c为样本类别总数; Nk为第k类的样本数目;x${}_i^k$为属于第k个类别的第i类样本。令S(w)和S(b)分别代表样本的类内散布矩阵和类间离散度矩阵,其定义分别如式(4)和式(5)所示:

$\begin{array}{l}\mathit{S}{}^{(w)}={\displaystyle \sum _{k=1}^c{\displaystyle \sum _{i=1}^{{\rm N}{}_k}(}}\mathit{x}{}_i^k-\mathit{\mu }{}^k)(\mathit{x}{}_i^k-\mathit{\mu }{}^k){}^{\text{Τ}}(4)\\ \mathit{S}{}^{(b)}={\displaystyle \sum _{k=1}^c{\rm N}}{}_k(\mathit{\mu }{}^k-\mathit{\mu })(\mathit{\mu }{}^k-\mathit{\mu }){}^{\text{Τ}}(5)\end{array}$

式中:μk为第k类样本的均值向量;μ为所有样本的均值向量,其定义如式(6)和式(7)所示:

$\begin{array}{l}\mathit{\mu }{}^k=\frac{1}{{\rm N}{}_k}{\displaystyle \sum _{i=1}^{{\rm N}{}_k}\mathit{x}}{}_i^k(6)\\ \mathit{\mu }=\frac{1}{{\rm N}}{\displaystyle \sum _{i=1}^{{\rm N}}\mathit{x}}{}_i(7)\end{array}$

通过求解式(8)所示的Fisher准则,即可实现同类样本在低维子空间中相互聚拢,非同类样本相互远离。

$J(\mathit{W})=\text{a}\text{r}\text{g}\text{m}\text{a}\text{x}\frac{\mathit{W}{}^{\text{Τ}}\mathit{S}{}^{(b)}\mathit{W}}{\mathit{W}{}^{\text{Τ}}\mathit{S}{}^{(w)}\mathit{W}}(8)$

式(8)的求解方法与式(3)类似,采用Lagrange乘子法求解,因此可将类内散布矩阵和类间散布矩阵加入目标函数式(3)中。最佳投影矩阵W的求解方法等同于求解如式(9)的特征值问题:

$\mathit{S}{}^{(b)}\mathit{W}=\lambda (\alpha \mathit{S}{}^{(w)}+(1-\alpha )\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}})\mathit{W}(9)$

利用式(9)求解出投影矩阵W,样本在低维子空间不仅能够保持局部结构;而且还利用标记样本的类别信息,使得同类样本聚集在一起,不同类样本相互远离。参数α控制着标记样本对投影矩阵的影响,由其取值范围为[0,1]:当α=1时,投影矩阵完全由标记样本确定;当α=0时,式(13)退化为LPP算法。

然而,仅保持样本在低维子空间中的局部结构不变并不能达到最佳的效果;对于原本相互远离的样本,应该在其投影到低维空间后也保持相互远离。为此,本文参照式(3)局部结构的定义,又定义了非局部结构的目标函数:

$\begin{array}{l}\max (\frac{1}{2}{\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm N}}\parallel }}\mathit{y}{}_i-\mathit{y}{}_j\parallel {}^2\tilde{\mathit{S}}{}_{ij})\\ =\max ({\displaystyle \sum _i\mathit{W}}{}^{\text{Τ}}\mathit{x}{}_i\tilde{d}{}_{ii}\mathit{x}{}_i^{\text{Τ}}\mathit{W}-{\displaystyle \sum _{i,j}\mathit{W}}{}^{\text{Τ}}\mathit{x}{}_i\tilde{\mathit{S}}{}_{ij}\mathit{x}{}_j^{\text{Τ}}\mathit{W})\\ =\max (\mathit{W}{}^{\text{Τ}}\mathit{X}\tilde{\mathit{L}}\mathit{X}{}^{\text{Τ}}W)(10)\end{array}$

式中:$\tilde{\mathit{L}}=\tilde{\mathit{D}}-\tilde{\mathit{S}}‚\tilde{\mathit{D}}=\text{d}\text{i}\text{a}\text{g}$$(\tilde{d}{}_{11},\tilde{d}{}_{22},\cdots ,\tilde{d}{}_{{\rm N}{\rm N}})‚\tilde{d}{}_{ii}={\displaystyle \sum _{j=1}^{{\rm N}}\tilde{\mathit{S}}}{}_{ij}$。$\tilde{\mathit{S}}$ij的定义如下:

$\tilde{\mathit{S}}{}_{ij}=\{\begin{array}{l}1-\exp \left(-\frac{\parallel \mathit{x}{}_i-\mathit{x}{}_j\parallel {}^2}{t}\right),\mathit{x}{}_i\notin {\rm N}{}_k(\mathit{x}{}_j)\\ 0,\text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\end{array}(11)$

将式(10)也加入式(9)中,得到式(12):

$(\alpha \mathit{S}{}^{(b)}+(1-\alpha )\mathit{X}\tilde{\mathit{L}}\mathit{X}{}^{\text{Τ}})\mathit{W}=\lambda (\alpha \mathit{S}{}^{(w)}+(1-\alpha )\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}})\mathit{W}(12)$

此时,利用式(12)得到投影矩阵W后,样本在低维子空间中不仅能够保持近邻样本的局部结构,并且可以保持非近邻样本对的非局部结构;同时,在式(12)中,标记样本的类别信息也得到利用,这使样本投影到低维空间后,属于同一类别的样本会更加靠近,属于不同类别的样本彼此远离。因此从分类角度考虑,利用该算法进行特征提取比原始的LPP算法更加适合进行后续分类处理。但是,在小样本条件下,式(12)等式右端的S(w)+XLXT可能为奇异矩阵,从而导致该特征值问题无法正常求解。为此,本文依照文献[11]的处理方法,通过添加一正则项从而使其变为非奇异矩阵:

$\begin{array}{l}(\alpha \mathit{S}{}^{(b)}+(1-\alpha )\mathit{X}\tilde{\mathit{L}}\mathit{X}{}^{\text{Τ}})\mathit{W}=\\ \lambda (\alpha \mathit{S}{}^{(w)}+(1-\alpha )\mathit{X}\mathit{L}\mathit{X}{}^{\text{Τ}}+\gamma {\rm I}{}^m)\mathit{W}(13)\end{array}$

最终,本文提出的SPP算法的投影矩阵由式(13)求解,该式是一个特征值求解问题,投影矩阵W为前r个最大特征值对应的特征向量组成的矩阵,r为子空间维数。

2.2 算法步骤

综上所述,SPP算法步骤可以归纳如下:

输入:N个m维原始空间数据组成的N×m矩阵X;

输出: N个d维特征空间数据组成的N×d矩阵Y,m≥d;

(1) 在原始空间中计算样本点之间的距离,找出每个未标记样本点的k个最近样本点;

(2) 计算未标记样本对间的权重矩阵Sij和$\tilde{\mathit{S}}$ij,由此可以分别计算未标记样本的局部结构XLXT和非局部结构X$\tilde{\mathit{L}}$XT;

(3) 对于标记样本,分别计算其类内散度S(w)和类间散布矩阵S(b);

(4) 根据式(13)求解投影矩阵W;

最终,原始高维数据在特征空间中的投影为Y=WTX。

3 实验结果与分析

实验采用机载可见/红外成像光谱仪AVIRIS获取的佛罗里达州肯尼迪中心(KSC)高光谱数据作为本文算法的验证数据(如图1所示)。该数据共有224个波段,实验中去除了受大气水分影响以及低信噪比的波段,保留了155个信噪比较高的波段构成数据集合。该数据集中有13类地物,本文选取数量较多的10类地物作为实验的样本集(见表1)。实验平台为Matlab 7.8,Pentium 4处理器 1.8 GHz,1 GB RAM,操作系统为Windows XP。

由第2节可知,本文提出的SPP算法有k,t,α,γ四个参数待定。由于这四个参数取值并无理论指导,故先通过实验确定这四个参数的最优取值。实验发现,参数k的取值对算法性能影响较小,故本文中直接给出该参数的取值k=5。实验选取表1中每类样本的20%作为训练样本集,其余样本作为测试集,采用K-近邻分类器对特征提取后的数据进行分类,实验结果如图2和图3所示。由实验结果可以看出:参数t,α,γ的取值对算法性能有极大影响,在该实验中,当α=0.8,t=0.1,γ=0.5时,算法SPP可以达到最优的特征提取效果。

为了验证SPP算法的有效性,实验还给出了在不同训练样本数量条件下SPP算法的分类精度,并与PCA,LPP以及文献[10]提出的半监督特征提取算法LGSSDR进行性能比较。实验采用K-近邻分类器(K-NN),使用分类结果精度衡量4种特征提取算法性能。实验选取表1所示样本集中的β%作为训练样本,剩余样本作为测试样本,β的取值范围为5～50。降维后的子空间维数取 [12]10。图4给出了在不同训练样本数量情况下4种特征提取算法在K-NN(k=1)分类器下的分类精度。

由图4的分类结果可以看出,由于PCA和LPP均为无监督特征提取算法,无法利用标记样本带来的监督信息,因此分类精度很低,难以满足实际应用要求。而本文提出的半监督保持投影算法SPP在原有LPP基础上加入了类内散度和类间散度,能够充分利用标记样本的类别信息来约束未标记样本点;使得样本投影到特征空间后,同类样本相互靠近,非同类相互远离,降低了分类难度,因此分类精度LPP算法有显著提高。同时,SPP算法的求解类似于Fisher判别分析,在标记样本数量较少时也会出现奇异矩阵,导致算法无法求解。为此,在目标函数的分母上增加了正则项,保证了算法在所有条件下均能够正常求解。

与LGSSDR算法相比:在标记样本数目较少时,本文提出的SPP算法的分类精度与LGSSDR算法相当;但是,随着标记样本数目的增加,SPP算法逐渐显现出其优势,分类精度高于LGSSDR算法。表2给出了4种特征提取算法在10种地物类型上的分类精度。由该表可以看出,在大多数地物类型中SPP算法的分类精度均高于其他三种算法,特别是在第2,3,5类中,SPP算法的分类精度得到显著提高。

4 结 论

LPP算法是基于样本的局部性进行建模,无法保证其提取出的特征有利于后续分类处理。对这一问题,本文提出了一种半监督保持映射(SPP)的特征提取算法。该算法充分利用标记样本的类别信息来约束未标记样本,使样本经SPP算法提取特征后,分类精度显著提高;同时正则项的加入避免了算法出现矩阵奇异问题。最后,通过实际KSC高光谱数据进行对比实验表明了SPP算法的有效性。

参考文献

[1]HE Xiao-fei,NIYOGI P.Locality preserving projections[J].Advance in Neural Information Processing Systems,2004,16:153-160.

[2]BELKIN M,NIYOGI P.Laplacian eigenmaps for dimen-sionality reduction and data representation[J].NeuralComputation,2003,15(6):1373-1396.

[3]DUDA R,HART P.Pattern classification and scene analy-sis[M].New York:Wiley,1973.

[4]宋欣,叶世伟.基于局部线性逼近的流形学习算法[J].计算机仿真,2008,25(7):86-89.

[5]郭金玉,苑玮琦.基于局部保持投影的掌纹识别[J].光学学报,2008,28(10):1920-1924.

[6]TANG Y,RICHARD R.A study of using locality preser-ving projections for feature extraction in speech recognition[C]//Proceedings of IEEE International Conference on A-coustics,Speech and Signal Processing.[S.l.]:IEEE,2008:159-1572.

[7]王建国,杨万扣,杨静宇.基于保持投影的最大散度差的特征抽取方法[J].模式识别与人工智能,2009,22(4):610-613.

[8]YANG Jian,ZHANG D,YANG Jing-yu,et al.Globallymaximizing locally minimizing unsupervised discriminantprojection with applications to face and palm biometrics[J].IEEE Trans.on Pattern Analysis and Machine Intelli-gence,2007,29(4):650-664.

[9]CHAPELLE O,SCHOLKOPF B.Semi-supervised learning[M].Cambridge,MIT Press:2006.

[10]韦佳,彭宏.基于局部与全局保持的半监督维数约减方法[J].软件学报,2008,19(11):2833-2842.

[11]KUO B C,LI C H,YANG J M.Kernel nonparametricweighted feature extraction for hyperspectral image classi-fication[J].IEEE Trans.on Geoscience and RemoteSensing,2009,47(4):1139-1155.

特征保持 篇4

点和边是CAD网络模型的重要组成因素, 可以直接影响其模型构建效益, 对模型建设具有至关重要的意义。在对全局轮廓形状特征保持的CAD网格模型进行简化的过程中要首先把握好模型点和边, 对点和边混合进行全面分析, 由该内容生成视觉感知信息, 从而确定模型表面分割内容。以前主要是依照模型结构对常规CAD网格模型进行分割, 这种分割在很大程度上影响了模型表面效果, 而在全局轮廓形状特征保持的CAD网格模型分割过程中, 主要从表面和轮廓特征出发, 由上述两项内容确定最终轮廓数据, 形成对应轮廓简化依据。在上述简化过程中系统轮廓与简化轮廓特征基本一致, 结构处理对全局不会造成任何影响, 这种分割效果对CAD网络模型简化具有非常好的促进作用。

当前全局轮廓形状特征保持的CAD网格模型轮廓简化中, 主要以离散曲率计算法实现系统数据的分析和计算, 对点、边网格进行构建, 依照网格体系完成基于点和边混合的边界轮廓分割, 轮廓简化效益非常显著。

2 改进QEM算法, 实现CAD网络模型特征简化

传统QEM算法只是对CAD网络模型进行分析, 并没有把握好CAD网络模型的全局特征。在该算法简化下, CAD网络模型全局特征效果大打折扣, 整体简化效益并不理想。在对QEM算法进行改进时, 针对全局特征性质, 对该算法内容进行了调整和转变, 其整体和局部特征保持效果均明显提升。因此, 在全局轮廓形状特征保持的CAD网格模型简化过程中可以适当选取基于改进的QEM算法实现模型全局优化。该体系可以依照该内容对机械表面特征进行分割, 依照对应算法得到边界轮廓曲线数据, 根据该数据完成系统处理, 形成网络模型的全局简化。该体系可以同时获取机械CAD网络模型的全局特征和局部特征, 可以及时依照轮廓特征分割图形, 形成对应曲线多边形。除此之外, 该体系还可以由上述多边形构建数学模型, 确定轮廓参照解, 以构建结果对轮廓全局进行简化, 从而优化全局轮廓形状特征保持的CAD网格模型简化效益。

3 保持形状特征, 实现CAD网络模型形状逼近

在对机械CAD网络模型进行初步简化后要对其边界形状进行把握, 要对上述过程中得到的特征多边形进行全面分析, 由上述多边形形成对应简化策略, 依照该多边形完成模型逼近, 从而保证简化后的机械CAD网络模型特征与原模型一致。在该过程中要对系统特征进行全面把握, 依照轮廓多边形点和边的位置对其实施逼近, 要严格保证逼近后的点和边的特征与原特征相似, 优化整体逼近网络模型。

全局轮廓形状特征保持的CAD网格模型简化过程中可以实时依照系统全局轮廓特征对其形状曲线进行调整, 要尽量保证逼近后数据信息符合QRM简化数据信息, 从而真正实现CAD网格模型特征的保持, 提升全局轮廓形状CAD网格模型简化效益。与此同时, 在该简化过程中还要把握好QEM简化后的模型特征轮廓曲线, 要对系统中的特征点和特征边进行约束, 形成对应点和边控制体系, 对上述特征结构进行保持。可以适当选取离散PSO算法进行系统点、边的计算和处理, 构造函数对逼近处理中出现的特征偏差进行分析, 及时调整, 从而实现全面逼近约束, 提升逼近的有效性和准确性, 改善全局轮廓形状特征保持的CAD网格模型简化质量。

4 多边形逼近调整, 实现CAD网络模型轮廓优化

全局轮廓形状特征保持的CAD网格模型简化过程中要对系统形状进行全面分析, 对其逼近后模型进行适当函数计算, 由计算结果对逼近进行调整, 从而保证逼近后的特征点和边的位置与原特征点和边的位置相同。要依照上述逼近后的点和边的位置对机械CAD模型进行完善, 对原始曲线在特征不变的状况下进行调整, 将机械CAD网络模型进一步提升。在该过程中需适当利用QEM简化中的局部特征, 根据系统中各项点的状况及系统状况对模型进行校验, 对拓扑关系和顶点位置进行调节和修改, 完成全局轮廓形状特征保持的CAD网格模型简化。

5 总结

作为机械CAD网络模型的重要组成部分, 全局轮廓形状特征保持简化不仅可以从根本上提升机械模型可视化效果, 还可以改进硬件交互及传输效益, 对机械生产具有至关重要的意义。在对全局轮廓形状特征保持的CAD网格模型进行简化的过程中, 人员要把握好点和边混合方法、改进QEM算法、保持全局形状、多边形逼近结果四项内容, 要不断对上述简化思路进行优化, 从而全面提升模型简化效益, 加速机械CAD系统发展进程。

参考文献

[1]周元莉.边界特征保持的机械CAD模型简化研究[D].哈尔滨工程大学, 2012.

[2]易兵, 刘振宇, 谭建荣.边界特征保持的网格模型分级二次误差简化算法[J].计算机辅助设计与图形学学报, 2012 (04) :427-434.

[3]杨钒沁.面向CAD应用的三维网格分割算法研究[D].浙江大学, 2007.