第25卷 第6期2002年6月
计 算 机 学 报CHIN ESE J. COM PU TERS
V o l. 25No. 6
J une 2002
一种组合特征抽取的新方法
杨 健 杨静宇 王正群 郭 丽
(南京理工大学计算机科学系 南京210094)
摘 要 该文提出了一种基于特征级融合的特征抽取新方法. 首先, 给出了一种合理的特征融合策略, 即利用复向量给出组合特征的表示, 将特征空间从实向量空间拓广到复向量空间. 然后, 发展了具有统计不相关性的鉴别分析的理论, 并将其用于复向量空间内最优鉴别特征的抽取. 最后, 在Concor dia 大学的CEN P ARM I 手写体阿拉伯数字数据库以及南京理工大学N U ST 603H W 手写汉字库上的试验结果表明, 所提出的组合特征抽取方法不仅具有很强的维数压缩能力, 而且较大幅度地提高了识别率. 关键词 特征融合, 特征抽取, 线性鉴别分析, 手写体字符识别中图法分类号:
T P301
A N ovel Feature Extraction Method Based on Feature Integration
YAN G J ia n YANG Jing -Yu W AN G Zheng -Qun GUO Li
(Departm ent of Computer Science , N anjing University of Science and Tec h nolog y , N anjin g 210094)
Abstract Feature level fusio n plays an impo rta nt ro le in the pro cess of data fusion. The adv an-tage o f feature lev el fusion lies in tw o aspects :Firstly , it can derive the most discriminatory in-forma tion from original m ultiple feature sets invo lv ed in fusion ; Seco ndly , it enables to eliminate the redundant info rm atio n within the o riginal fea ture sets and to make it possible fo r the decision
in real tim e. The classical feature fusio n based feature ex tractio n approach is to g roup tw o sets of fea ture v ecto rs into o ne unio n-vecto r (o r supervecto r) and then based o n them for feature ex trac-tion . This approach is alway s co mputatio nally ex pensive due to the high dim ensio nal superv ectors resulting fro m integ ra tion . To ov erco me the w eakness of the classical m ethod , a novel fea ture ex-traction method based on features fusion is dev elo ped in this paper. First of all, a ratio nal repre-sentatio n fo r integ rated fea tures by virtue o f co mplex v ecto rs is giv en, i. e. , two sets o f fea ture v ecto rs of a sam e sample are com bined tog ether by a complex v ector . As a result , the fea ture space becomes a complex v ector space rather tha n a real one. Then, to solv e the problem o f fea-ture ex traction in the integ ra ted complex vecto r space, the theo ry of the com plex unco rrela ted lin-ear discrimina nt analysis (ULDA ) is dev elo ped . Based on this theo ry , a generalized U LDA m ethod is propo sed . This metho d is suitable for feature ex tractio n in the com plex integ ra ted fea-ture space. Finally, the pro posed metho d is tested o n Co nco rdia Univ ersity CEN PARM I hand-w ritten digit da tabase and N UST603H W ha ndw ritten Chinese cha racter database built in Nanjing Univ ersity of Science and Technolo gy . The ex perimental results indica te that after feature ex trac-tion using the proposed metho d, the recog nition accuracy is increased sig nificantly as w ell as the dimensio n o f fea ture v ector is reduced largely. Mo reov er, the ex perimental results also dem on-收稿日期:2001-05-14; 修改稿收到日期:2002-02-26. 杨 健, 男, 1973年生, 博士研究生, 讲师, 主要研究方向为人脸检测与识别、手写体字符识别、信息融合. E-mail :yangjianw p @263. net. cn. 杨静宇, 男, 1941年生, 教授, 博士生导师, 主要研究领域为模式识别、计算机视觉、信息融合、智能机器人. 王正群, 男, 1965年生, 博士, 主要研究方向为模式识别、手写体汉字识别. 郭 丽, 女, 1975年生, 博士研究, 、.
6期杨 健等:一种组合特征抽取的新方法
571
stra te that the propo sed feature ex traction m ethod based on fea ture integ ra tio n is mo re po werful and mo re efficient than the classical o ne.
Keywords fea ture fusion , fea ture ex tractio n , linea r discriminant analy sis , handw ritten charac-ter reco gnitio n
方法不仅能大幅度地实现原始特征维数的压缩, 而且较大程度上提高了分类识别的效果. 此外
, 与传统的特征融合方法相比, 本文的方法不仅在一定程度上提高了识别率, 还具有速度快的优点.
1 引 言
近年来, 随着计算机技术的发展, 信息融合技术成为一种新兴的数据处理技术, 并已取得了可喜的进展[1]. 从处理对象层次的角度, 信息融合一般可划分为象素级(低层) 融合、特征级(中层) 融合和决策级(高层) 融合3个层次. 目前, 在模式识别领域, 以多分类器组合为代表的决策级融合技术已受到普遍的关注, 并在手写体字符识别等方面取得了较为成功的应用[2]. 但是, 就特征级的融合而言, 目前的研究成果较少.
其实, 特征级融合在信息融合过程中占有十分重要的地位. 特征级融合的优点是既保留了参与融合的多特征的有效鉴别信息, 又很大程度上消除了信息的冗余, 实现了可观的信息压缩, 从而有利于信息的实时处理.
目前, 有关特征级融合的传统方法(也是最为常用的方法) 是, 将两组特征直接合并为新的特征向量
[3]
2 组合特征抽取的原理与方法
2. 1 基本概念
设A , B 为模式样本空间K 上的两组特征集. 任意模式样本a ∈K , 它对应的两个特征向量分别为∈A 和β∈B , 我们用复向量V =α+i β(i 为虚数单α
位) 来表示a 的组合特征. 注意, 若两组特征α与β的维数不等, 低维的特征向量用零补足. 例如, α=(a 1, a 2, a 3) , β=(b 1, b 2) , 则组合特征为γ=(a 1+
T
ib 1, a 2+ib 2, a 3+i 0) .
K 上的组合特征空间定义为C ={α+i β|α∈A , β∈B }.明显地, 该空间为n 维复向量空间, 其中, n =max {dim A , dim B }.我们定义如下内积:
(X , Y ) =X H Y
(1)
T
T
. 具体地讲, 设A , B 为模式样本空间K 上的两
组经过标准化后的特征, 任意模式样本a ∈K , 它对应的两个特征向量分别设为T ∈A 和U ∈B , 则合并后的特征为V =
有效地提高识别率, 但其缺点也是明显的. (1) 由于特征合并后的维数是两原始特征的维数之和, 这就导致了合并后新特征的维数急剧增加, 从而使得组合后识别的速度大幅度地降低; (2) 在人脸识别等小样本问题中, 合并后的特征维数的增加常常导致类内散布矩阵出现奇异的情况, 这就为线性鉴别特征的抽取造成困难.
针对传统的特征融合方法存在的以上问题, 本文提出了一种新的特征融合策略及基于该融合特征的信息压缩方法. 该方法的基本思想是:首先, 利用复向量给出组合特征向量的合理表示; 然后, 在复特征空间内利用推广的鉴别分析法进行最优鉴别特征的抽取. 在离线手写体阿拉伯数字库和手写体有限
. 尽管这种方法在多数情况下能
其中, X , Y ∈C , H 为共轭转置符号.
定义了以上内积的复空间称为酉空间. 相应地, 酉空间内的类间散布矩阵、类内散布矩阵和总体散布矩阵分别定义为
L
S b =
L
∑
i =1
i P m i -m X -m i
m i -m X -m i
H
H
(2)
S w =
∑P
i =1
i /i
(3)
S t =b +S w =E {(X -m 0) (X -m 0) H }(4)
i 为第i 类训练样本的先验概率, i =, X /i 为第i 类训练样本的均值, m 0==
m
∑P
i =1
w i m i 为全体训练样本的均值.
由式(2) , (3) , (4) 的定义知, S w , S b , S t 均为Her-mite 阵, 且非负定. 当S w 可逆时, 易得S w , S t 均为正定矩阵.
酉空间内的Fisher 鉴别函数定义为
572
计 算 机 学 报 2002年
其中, φ为任一n 维非零复矢量.
由S w , S b 的非负定性知, 对于任意向量φ, 函数值J f 均为非负实数, 故酉空间内的Fisher 鉴别函数的物理意义和实空间内的情况完全相同.
当S w 可逆时, Fisher 准则与以下准则等价:
H b J =(6)
φS t φ2. 2 原理与方法
最近, Jin a nd Yang [4]提出了一种具有统计不相关性的鉴别分析方法, 并应用于人脸识别和手写体阿拉伯数字的识别等方面, 取得了良好的效果. 杨健、杨静宇等进一步发展具有统计不相关性的鉴别分析的理论, 给出了更为简明和全面的算法. 本文旨在将该方法进一步拓广, 用以解决组合特征空间(酉空间) 内的特征抽取问题. 为此, 我们先给出该鉴别法在酉空间内的表述.
具有统计不相关性的鉴别法旨在寻找一组满足共轭正交条件(7) 且使得Fisher 准则函数式(6) 达到极值的鉴别矢量φ1, φ2, …, φd .
1, i =j , H
φj S t φi =W ij =i , j =1, …, d (7)
0, i ≠j 具体地讲, 该最优鉴别矢量集的第一个鉴别矢量φ1
1, 取为Fisher 最优投影方向; 当前k 个鉴别矢量φ2, …, φk 取定后, 第k +1个鉴别矢量可通过求解以φ
下最优化问题得到
[5]
征值, 其中, q =rank (S b ).
推论2. 鉴别准则函数J X j =λj , j =1, 2, …, q .
推论3. S b X =λS t X 的关于S t 共轭正交的特征向量X 1, X 2, …, X n 线性无关, 且C =span {X 1, X 2, …, X n }.
为了讨论方便, 不妨设S b X =λS t X 的特征值满
1≥λ2≥…≥λn . 足λ
n
定理2. 设前k 个最优鉴别矢量φ1, φ2, …, φk
分别取为φ1=X 1, φ2=X 2, …, φk =X k , 则第(k +1) 个最优鉴别矢量φk +1可取为X k +1, 即模型1的最优解为X k +1.
证明. 若前k 个最优鉴别矢量φ1, φ2, …, φk
分别取为X 1, X 2, …, X k , 由推论3和模型1中的共轭正交条件知, φk +1只可能从C 的子空间span {X k +1,
k +1可表示为φk +1=X k +2, …, X n }中选取, 故φ
n
c k +1X k +1+c k +2X k +2+…+c n X n . 再由推论2可得
22
λk +1c k +1+…+λn c n
J (φk +1) =≤λk +1,
c k +1+…+c n
既然J (X k +1) =λ-k +1, 因此, h -k +1可取为X k +1.
证毕.
定理2告诉我们, 在酉空间内, 具有统计不相关性的最优鉴别矢量φ1, φ2, …, φd 可取为广义特征方程S b X =λS t X 的d 个最大特征值所对应的满足S t 共轭正交条件的特征向量X 1, X 2, …, X d . 再由推论1和Fisher 鉴别准则函数的物理意义知, 具有统计不相关性的有效鉴别矢量的个数最多为q , 这里, q =rank(S b ) ≤L -1, L 为模式样本类别数.
根据定理1, 酉空间内的最优鉴别矢量X 1, X 2, …, X d (d ≤q ) 满足式(9) , (10) 两个条件, 既然λj 为非负实数, 组合特征(复) 向量在鉴别方向X j 上投影的物理意义仍然十分明确, 即类间散布量为λj , 而类内散布量为1-λj .
在酉空间内, 最优鉴别矢量集X 1, X 2, …, X d 可构成如下线性变换
Y =H X , 其中, H =(X 1, X 2, …, X d )
该变换用于组合特征的抽取.
与文献[4,5]中的方法比较可见, 以往讨论的实向量空间内的鉴别特征抽取方法只是本文方法的一个特例, 也就是说, 本文在复空间内建立的鉴别分析方法更具有一般意义, 它完全适用于实空间内的H
m J H
模型1φj S t φ=0, j =1, 2, …, k
(8)
φ∈C
这里, C n 表示n 维酉空间.
以下, 我们具体讨论最优鉴别矢量集的求解问题.
定理1. 当S t 非奇异时, 广义特征方程S b X =λS t X 存在n 个关于S t 共轭正交的特征向量X 1, X 2,
1, λ2, …, λn , 且满足如…, X n 和n 个对应的实特征值λ下条件:
n
X S t X j =和
X S X j =
H i b
H i
1, 0, λi ,
i =j i ≠j ,
i =j ,
i , j =1, 2, …, n (9) i , j =1, 2, …, n (10)
(11)
0, i ≠j ,
由于S b , S t 均为Hermite 阵且S t 正定, 根据文献[6]的结论, 定理1成立. 再由S b 的非负定性, 容易得
到如下推论.
推论1. 广义特征方程S b X =λS t X 的特征值1, , λ
6期杨 健等:一种组合特征抽取的新方法
573
除了以上所介绍的方法外, 也可采用文献[7]中
3 加权组合策略
由于特征抽取方法与量纲选择的不同, 导致了参与组合的同一模式样本的两组特征α与U 之间在数量关系上可能存在较大的差别. 比如, α=(10, 11, 9) , β=(0. 1, 0. 9) . 若直接以γ=α+i β的方式进行组合, 两特征组合后的比重将明显失调. 为了使得两特征能够以近乎平等的地位参与组合, 达到较好的组合效果, 有必要考虑特征之间在数值上的均衡性问题. 因此, 实际中多采取加权组合的方法. 在此, 我们采取γ=α+i θ=θ+i β的形式进β或γα行组合, 其中, 权值θ称为组合系数. 易证明, 加权组合特征具有以下性质.
性质1. 当θ≠0时, 组合特征γ=α+i θβ与γ=(1/θ) α+i β等价. 性质2. 当θ→0时, 组合特征γ=α+i θβ等价于单特征α; 当θ→∞时(θ≠∞) , 组合特征γ=α+i θβ等价于单特征β.
以下, 我们讨论组合系数θ的估计方法. 影响组合系数选择的有两个主要因素, (1) 特征向量的长度, (2) 特征向量的维数. 不妨设两特征α与β以γ=α+i θβ的形式参与组合, 其中, α与β的维数分别为n 和m . 一方面, 考虑到特征的均衡性问题, 加权后α与θβ的长度应大致相同; 另一方面, 由于单特征α生成的散布矩阵的维数为n 2, 单特征β生成的散布矩阵的维数为m 2, 我们认为, 组合系数θ应与特征维数的平方成正比. 由此, 我们得到估计参数的经验公式:θ
2‖α‖2
θ=,
m ‖β‖2
(12)
T
T
提出的先将两组特征标准化后再进行组合的策略. 两种方法的组合效果基本相同.
4 试验结果与分析
试验1.
采用国际上广泛使用的Co ncordia 大学CEN-PARM I 手写体阿拉伯数字(0—9) 数据库, 其中有4000个训练样本和2000个测试样本. 利用文献[2]已提取出的如下两个图像特征:
f
G :256维Gabo r 变换特征; f
L :121维Leg endre 矩特征;
f
二者的组合采用C f =G f +i θL 的形式. 利用公式*(12) , 求出组合系数θ=30. 2399.
用本文提出的鉴别分析方法将原始特征及其它们的组合特征压缩到低维的鉴别特征空间内进行识别. 识别时为了充分利用各类的均值和方差信息, 我们采用二次Bayes 分类器, 由于该试验中各模式类的先验概率相同, 我们采用如下定义的Bayes 鉴别函数:
H -1ln |E l |+(x -_l ) E l (x -_l ). 22
其中, _l 与E l 分别表示第l 类的均值与协方差矩阵. g l (x ) =
若模式样本x 满足|g k (x ) |=min |g l (x ) |, 则x ∈l
k . 分类结果见表1. k
另外, 我们采用传统的特征合并法做了对比试验. 将256维的Gabor 变换特征与121维的Leg-endre 矩特征直接合并为377维的特征, 然后采用本文提出的鉴别分析方法进行维数压缩, 在二次Bay es 分类器下的识别结果见表1.
[3]
其中, ‖α‖2, ‖β‖2分别表示特征α与β的长度.
表1 Gabor 变换特征、Legendre 矩特征及其组合或合并后的特征在特征抽取后的分类结果对照表
特征单特征G f
单特征L f 组合特征C f 合并特征
0. 0. 0. 0.
维数(鉴别矢量个数)
[1**********]10
0. 0. 0. 0. [1**********]14
40. 2460. 1720. 1040. 109
0. 0. 0. 0. [1**********]88
60. 1660. 1140. 0730. 079
70. 1570. 0970. 0610. 069
0. 0. 0. 0. [1**********]61
90. 1530. 0970. 0580. 061
*=30. 2399. 注:组合特征C f 中, 组合系数θ
由表1可见, 两特征采用本文的方法组合后, 在
各个维度上, 识别错误率均较大幅度地降低. 当组合特征被压缩为9维时, 正确识别率较相同维度的Gabo r 压缩特征提高了9. 5%, 较Leg endre 压缩特Gabo r 变换(原始) 特征在该Bayes 分类器下的识别
率为83. 6%, 121维的Leg endre 矩原始特征在同一分类器下的识别率为90. 0%. 而从表1可以看出, 组合后的鉴别特征仅取5维时, 就可达到,
574
计 算 机 学 报
f
2002年
别分析方法具有极强的信息压缩能力.
由表1亦可见, 尽管传统的特征合并法也取得了不错的结果, 达到了93. 9%的正确识别率, 但仍低于本文方法得到的94. 3%的识别率. 另外, 本文方法的速度较快, 特征抽取和识别过程所消耗的总时间为435. 75s, 而传统的方法则需要596. 60s. 下面, 我们验证一下所估计的组合系数是否合
f
理. 给出一系列的θ值, 以C f =G f +i θL 的形式组合, 特征抽取后(压缩为9维) 所对应的识别结果见表2.
表2 组合系数变化时相应的分类结果
θ
1/1001/501/[1**********]530
错误率0. 1530. 1520. 1500. 1280. 0770. 0640. 0600. 0590. 0570. 058
θ*θ[***********]001E +5
*
接近(甚至达到) G 的错误率; 当θ越来越小时, 错误率趋向于L f 的错误率. 这与性质2的结论完全吻合.
试验2.
实验采用南京理工大学NU ST 603HW 手写汉字样本库. 该汉字库包含银行货币金额大写常用的零, 壹, …等19个汉字的样本. 每类样本数为400个(共7600个). 其中200个样本作为训练样本, 另外200个样本作为测试样本, 这样, 训练样本和测试样本总数均为3800个. 我们采用文献[8,9]的方法分别抽取汉字的以下两种特征:
:128维的交叉数特征, 该特征Cross -fea ture 反应汉字结构特征.
:128维的周边特征, 该特Peripheral -fea ture
征反应汉字字形特征.
二者的组合采用Cro ss +i θPeripheral 的形式.
*
利用公式(12) , 求出组合系数θ=0. 1199. 用本文的方法将原始特征及其它们的组合特征压缩到低维的鉴别特征空间内, 采用二次Bayes 分类器, 分类结果见表3.
由表3可见, 就识别率而言, 组合后的鉴别特征较组合前大大提高. 当维数被压缩为18时, 正确识别率达到了98. 3%. 该试验结果再次证明了所提出的组合特征抽取方法的有效性.
错误率0.
0. 0. 0. 0. 0. 0. 0. 0. 0. [***********][1**********]0
由表2可见, 我们估计的组合系数θ基本上是合理的, 与最优结果仅差0. 1个百分点. 此外, 亦可看出, 在一定的区间(20—40) 内, 分类错误率随着权值θ的变化十分稳定. 这就为组合系数的选择提供了较大的回旋余地. 而且, 当θ越来越大时, 错误率
表3 交叉数特征、周边特征及其组合在鉴别特征抽取后的分类结果对照表
特征Cross Periph eral 组合特征
维数(鉴别矢量个数)
20. 5140. 5140. 283
40. 2090. 2140. 097
60. 1410. 0980. 048
80. 0960. 0730. 029
100. 0830. 0570. 020
120. 0700. 0480. 022
140. 0720. 0420. 020
160. 0690. 0410. 020
180. 0690. 0390. 017
5 结 论
本文提出了一种特征融合的新策略, 并在此基础上探讨了组合特征抽取的具体方法, 推广了具有统计不相关性的鉴别分析的理论, 并由此得出了一种适用于复合特征抽取的简单而有效的算法. 本文的思想理论丰富了特征级融合的内涵. 如果说传统的特征合并法是串行的, 本文的方法则是并行的, 从而形成两种风格迥异的融合思想. 两种方法相比, 串行方法的优点是两特征在标准化后可以直接进行合并, 不需要估计组合系数, 但合并后的特征维数较高, 直接影响随后的特征抽取和分类识别的速度. 而并行方法的优点是特征组合后避免了维数的增加, 从而在提高识别率的同时不至于过多地增加时间开
销. 此外, 若原始特征能保证类内散布矩阵的可逆性, 不难从理论上证明, 采用本文方法得到的组合特征亦能保证这一点. 这就为直接采用线性鉴别分析进行特征抽取提供了便利.
另外, 值得一提的是, 本文的思想方法在处理某些问题时更具有直观意义. 例如, 在进行目标识别时, 如果同时获得了目标的灰度图像和深度图像, 我们完全可采用本文的思想方法将两类图像融合在一起, 这也是我们目前正在研究的问题.
参
1
考文献
Abidi M A, Gonzalez R C. Data Fu sion. San Diego :Academic Press, 1992
6期
2
杨 健等:一种组合特征抽取的新方法
575
Hu Zh ong-Shan, Lou Z, Yang J Y et al . Handw ritten digit recog nition bas ed on mu lti -classifier combination . Chinese J our-nal of Com puter, 1999, 22(4), 369-374(inCh inese)
(胡钟山, 娄 震, 杨静宇等. 基于多分类器组合的手写体数字识别. 计算机学报, 1999, 22(4):369-374)
6
(杨 健, 杨静宇, 金 忠. 最优鉴别特征的抽取及图像识别. 计算机研究与发展, 2001, 38(11):1331-1336)
Ding Xue-R en, Cai M iao-Ke. M atrix Th eory in Engin eering. Tian j in :Tianjin University Pres s, 1995(inChines e)
(丁学仁, 蔡庙可. 工程中的矩阵理论. 天津:天津大学出版社, 1995) 7
J ian Yang ,
J ing -yu Yang . General ized K -L trans fo rm based
Pattern Recognition , 2002, 35
combined feature extraction. (1):295-2978
Tang Y T. Offline recognition of Chinese handw riting by m ulti-feature and multilevel clas sification. IE EE Trans Pattern Analy-sis and M achine Intelligence , 1998, 20(5):556-5619
Tseng Y H, Kuo C C, Lee H J . Sp eeding u p Chines e ch aracter recognition in an au tomatic d ocument reading s ystem. Pattern Recog nition, 1998, 31(11):1601-
1612
3Cheng Jun-Liu, Harry W echsler. A shape-and texture-bas ed enhanced F ish er classifier for face recognition . IEEE Trans Im-age Processing, 2001, 10(4):598-608
4J in Z, Yang J Y, Hu Z S et al . Face recognition bas ed on uncor-related discriminant transformation. Pattern Recognition, 2001, 34(7):1405-1416
5
Yang J ian , Yang J Y , J in Z . A featu re ex traction approach us-ing op timal discriminant trans form and image recognition. J our-nal of Com puter Res earch and Developmen t, 2001, 38(11):1331-1336(inChines e)
YA NG Jian , ma le , bo rn in 1973, Ph. D. candidate. At the sa me time, h e is a lectur er in the Depa rtment o f Ap-plied M a th ema tics o f N anjing U niv er sity o f Science and Techno lo g y. H is curr ent research interests include fa ce recog ni-tion a nd detectio n , ha ndw ritten charac-ter recog nition and data fusio n.
YANG Jing -Yu , male, bo rn in 1941, pr ofessor a nd Ph. D. supe rvisor in the Depa rtment of Computer Science o f
Na njing U niv er sity of Science a nd T echnolog y. His cur rent research interests a re in the ar ea s of pa ttern recog nitio n, co mput er visio n , da ta fusio n and ar tificial intellig ence .
WANG Zheng -Qun , male , bo rn in 1973. N o w , he is a doc to r. H is cur re nt r esea rch interests include patte rn recog -nitio n, Chinese handw ritte n charac ter r eco g nitio n.
GUO Li , bo rn in 1975, Ph . D . ca ndidate . Her cur rent research interests include co nte nt-ba sed ima ge ret riev al and document analysis.