候选基于广义可信度阈值判别和多分辨率方向梯度直方图字符预分类

基于广义可信度阈值判别和多分辨率方向梯度直方图的字符预分类

基于广义可信度阈值判别和多分辨率方向

梯度直方图的字符预分类

第16卷第6期

2010年l2月

上海大学学报(自然科学版)

JO URNALO FSHANGHAIUNIVERS ITY(NATURALS CIENCE)

Vo1.16No.6

Dec.2010doi:10.3969/j.issn.1007—2861.2010.06.012

基于广义可信度阈值判别和多分辨率方向

梯度直方图的字符预分类

孙广玲,沈宙彪,陈岳军

(上海大学通信与信息工程学院,上海200072)

摘要:针对字符预分类问题,提出基于广义可信度阈值判别的规则和多分辨率方向梯度直方图特征,证明该规则具

有”错误率”和”平均候选类别数”的最优折衷.基于梯度图像高斯金字塔,提取了多分辨率方向梯度直方图特征.实

验结果表明,该规则和特征具有一定的优越性.

关键词:预分类;广义可信度;多分辨率方向梯度直方图

中图分类号:TP39文献标志码:A文章编

号:100%2861(2010)06-0614-06

CharacterPre-classificationBasedonGeneralizedConfidenceThreshold

DeterminationandMulti-re solutionHistogramsofO rientedGradients

SUNGuang—ling,SHENZhou-biao,CHENYue-jun

(SchoolofCommunicationandInformationEngineering,ShanghaiUniversity,Shanghai200072,C hi n a)

Ab s trac t:Forcharac terpre—classification,ageneralizedconfidencethresholddeterminationruleandmul ti—resolutionhistogramsoforientedgradientsfeatureareproposed.Itisshownthatanoptimaltradeoffbetweene drule.Fromthe Gaus sianpyramidofagradientimage,multi—re s olutionhi stograms ofo rientedgradients areextracted.

Experimentalresultsindicatesuperiorperformanceoftheprop osedruleandfeatures.

Keywords:pre—classification;generalizedconfidence;multi—resolutionhistogramofo rientedgradient

字符预分类是指根据待识字符的特征,给出一

个候选子集,待识字符所属唯一类别的确定只在

该候选子集中进行.并且,该候选子集应尽可能小,

同时以尽可能大的概率包含?.然而,在实际中,这

两个参数的变化关系恰恰是相反的,即随着候选子

集的减小,包含的概率减小,反之亦然.本工作的

研究内容主要包括2个方面:?获得这两个矛盾参

数较好折衷的预分类规则;?得到影响预分类性能

的预分类特征.

预分类方法可分为聚类法和逐一匹配法.聚类

法是指,首先通过一定的聚类准则将学习样本聚类,

并得到聚类中心;预分类时,计算待识样本与每个聚

类中心的距离,与待识样本的距离最近的一个或几

个聚类中所包含的字符类别就是候选类别.这种方

法虽然正确率较高,但预分类给出的候选类别数仍

然比较多.比如文献[1]的方法中,每个聚类平均包

收稿日期:2009-09-02

基金项目:上诲市教委科研基金资助项目(06AZ036)

通信作者:孙广玲(1973,),女,副教授,博士,研究方向为图像与视频处理分析,机器学习

第6期孙广玲,等:基于广义可信度阈值判别和多分辨率方向梯度直方图的字符预分类615

含的字符类别数接近全部类别数的1/10;文献[2]

中的方法虽然给出的候选类别数比较少,但却需要

设置很多经验性的参数,在一定程度上会影响预分

类的正确率.逐一匹配法是指,首先计算待识样本对

于每个类别的后验概率或距离,然后根据后验概率

或距离信息选出候选类别.候选类别数可以是事先

设定的固定值,即总是选择后验概率或距离排在前

面设定类别数的类别,也可以根据每次预分类结

果和阈值,给出满足条件的类别作为候选类别,这时

的候选类别数是变化的.逐一匹配法有诸多优

点,首先是参数设置很简单,只需设定唯一的判别参数,在候选类别数固定的情况下,固定候选类别数即是判别参数,而在候选类别数变化的情况下,阈值就是判别参数;其次,已有实验结果表明,在预分类器本身性能比较高的前提下,逐一匹配法可满足较高的预分正确率,相应的候选子集相对于全部类别数来说是相当少的.因此,我们选择逐一匹配法作为进一步研究的方向.考虑到街区距离判别函数具有计算简单的特点,并且适合于手写字符的识别,因此将其选为预分类器.

由于梯度特征区分度强且易提取,并且既适用于二值图像又适用于灰度图像],因此,将其选为预分类特征.事实上,梯度特征可以看作方向梯度直方图(histogramoforientedgradients.我们

应用Burt-Adelson提出的高斯金字塔(Gaussianpyramid)计算多分辨率方向梯度直方图(multi-resolutionhistogramsoforientedgradients,MHO G),将各分辨率HOG特征以串联的方式组合,然后利用线性判别分析进行融合以获得低维数且更有效的特征.

1基于广义可信度阈值判别的预分类

规则及其分析

1.1广义可信度

林晓帆等?. .提出了”广义可信度”的概念:如果

存在函数e(cc,I)和一个单调递增函数g(?),满足e(I)=g(P(l)),(1)

则称e(I)是属于类别的广义可信度.P(l

)表示属于类别的后验概率.对于输出距离的分类器来说,下式是对广义可信度的一个理想估计:e()-1一,(2)

式中,d()为类别数,为后验概率

阈值.该预分类规则具有最优的错误率和平均候选类别数的折衷.我们将其归纳为定理并给出证明.定理1对于分类器S,给定错误率P,当根据

规则1及后验概率阈值Tp.()选择候选集合时,分类器平均候选类别数?达到最低;同样,给定平均候选类别数?,当根据规则1及后验概率阈值r,P(?)选择候选集合时,分类器错误率P达到最低.证明先定义下列符号:P()表示样本的概

率密度函数;表示整个定义域;S.()表示对于样本,规则1给出的候选集合;S()表示对于样本,任意其他规则给出的候选集合;r()表示Js()

未包括真实类别的概率;rb()表示S()未包括真实类别的概率;P…表示使用规则1得到的错误率;

P.

表示使用任意其他规则得到的错误率;N表示使用规则1得到的平均候选类别数;N表示使用任意其他规则得到的平均候选类别数.基于上述定义,

可以得到P…,P.,N和?的表达式如下:

P. .

=

Jr()P()dx,(3)aX

P. .b=Irh(x)p()dx,(4)

?=Jn()P()dx,(5)

?=Jn()P()dx,(6)r():1一?P(I):1一o2i?Sa()

?P(l)一?P(I),toiE(sa 【)\Sb(x))toiE 【sa()f1Sb(x))

(7)

616上海大学学报(自然科学版)第16卷rh()=1一?P(?1)=1一

?P(f)一

?P(1),(8)

()=fSa()\()f+fs()nSb()i,(9)n()=fSb()\5()i+fSo()nSb()f.(10)

根据规则1,易得fP(?)?i?a());(11)

尸(f)?p,if??Sb()\5()?

首先,证明定理的前半部分.已知P=P.=P,即fgra()p()dfxFb()p()d=P.?(12)

将式(7)和(8)代入式(12)中,得到

儿=j [.,,,

P(cc,l)】 p()d?(13)

由式(11)可得,使用规则1达到的平均候选类别数为

,v=J凡(x)p()dx?J

南?川+

JxfSa()nSb()[p(x)dx?(I4)

以此类推,可得出使用任意其他规则达到的平均候选类别数为

?b=J(x)p()dx?Jy

南fx[川)?

JJSa()nSb()Ip(x)dx?(15)

又根据式(13),所以?.

然后,证明定理的后半部分.已知==,

即na()p()d=/l’ b()p()d:?(16)

将式(9)和(10)代入式(16)中,得到f(}S a()\()})P()dx=

1,(1 Sb()\s()1)p()dx.(17)

J 【1一(?).Is()\| s()l-

?p(o2I)lp()dx:

[卜善小,,P())

()』 fS a()\()f()dx.(18)

JI1一Tpp(N) ’ jSb()\5()J一

?P(.I)Ip():

[卜小))

(?)J. .ISbx)\s()Jp()dx.(19)

又根据式(17),所以P.?P..b.证毕.

:h………ife(I)>Tg,arg.m—axce(Ix)

式中,.为广义可信度阈值.

而Tg也可映射至一定的后验概率阈值Tp,因此,有

』 P(.)?,ie(?’ )?r,gc;(20)tp(tOI)?Tp,ife(l)?Tg.

第6期孙广玲,等:基于广义可信度阈值判别和多分辨率方向梯度直方图的字符预分类617

推论1对于分类器S,给定错误率P,当根据

规则2及广义可信度阈值(P)选择候选集合时,

分类器平均候选类别数?达到最低;同样,给定平

均候选类别数?,当根据规则2及广义可信度阈值

(N)选择候选集合时,分类器错误率P达到最低.

由于与广义可信度阈值作C次的比较运算,因

此,规则2的时间复杂度也为O(C).

文献[4]将预分类归结为对随机变量求解最

优候选集合问题.候选集合是全部类别组成的集合

的非空子集,即若全部类别数是C,则候选集合数是

2.一1.

所有的候选集合组成了候选集合空间,而最

优候选集合是在上的条件损失最少的候选集合.将候选集合空间按照候选集合的势(即候选集合的元素个数)分解为C个子区域,每个子区域中的候选集合的势都相同.搜索最优候选集合的过程如下:首先,在势相同的候选集合中搜索在上的未包括真实类别的条件概率最小的C个候选集合;然后,再从这C个候选集合中,搜索出在上的未包括真实类别的条件概率与势的线性组合构成的条件损失最少的候选集合,这就是最优候选集合.从这个搜索过程可以看出,候选类别数固定的预分类规则给出的候选集合,实际上是在势为固定候选类别数的候选集合中的最优解,而非整个候选集合空间中的最优解.因此,候选类别数固定的预分类规则不具有最优的错误率和平均候选类别数的折衷.同时,候选类别数固定的预分类规则还需要排序,所以效率也低于基于广义可信度阈值判别的预分类规则.

不难看出,错误率和平均候选类别数都取决于阈值.与错误率的关系为越低,错误率越低,反

之越高;而与平均候选类别数的关系为越低,平均候选类别数越多,反之越少.因此,错误率和平均候选类别数是互为矛盾的一对指标.在不同阈值下的错误率与平均候选类别数形成的曲线,可以表征和评价在分类器相同的情况下不同预分类规则的性能,或者在预分类规则相同的情况下不同分类器的