о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 5 Vol.36 No.5 1999



д庺ʶо
־ſ
ժҪһֹͳϵļģӦд庺ʶļѻͳƵĴʱMarkovģԹģͣͨһԽ.ֺ3׶ɣɡԽ롢Cacheѧϰ.ԽViterbi㷨ѡ.ӦHPC(ֳֻ)дԵдʶϵͳУʶΪ91.3%.
ؼʡMarkovģͣд庺ʶ 
ͼšTP391.4
A POST PROCESSING METHOD FOR ONLINE HANDWRITTEN
CHINESE CHARACTER RECOGNITION
XU Zhi-Ming, WANG Xiao-Long, ZHANG Kai, and GUAN Yi
(Department of Computer Science and Technology,Harbin Institute of Technology, Harbin150001)
(Department of Computer,The Hong Kong Polytechnic University,Hong Kong)
AbstractProposed in the paper here is a new post processing method integrating the rule-based grammar and the Markov language model for online handwritten Chinese character recognition. The Markov language model and the quantification rules model are bound to a linguistic decoder by word lattice. The post processing kernel engine consists of three stages: word lattice formation, linguistic decoder,and cache-based self-learning mechanism. The linguistic decoder adopts Viterbi search algorithm to search the best sentence hypothesis. The introduced technique has been applied to HPCs online handwritten Chinese character recognition,with a recognition accuracy rate of 91.3% achieved.
Key wordsMarkov language model, word lattice, online handwritten Chinese character recognition
1
дһõ˻ͨŷʽмݡȻص.д庺ʶһֱܼӿڵоص.͵д庺ʶϵͳһɣǰʶԽ.ǰʶд庺ֵɴиʣŶȣĺѡʸУԽӦģͶǰʶɵĺѡʸнһŽ.ԽģһɷΪͳƺͻڹ1.ͳƵMarkovģʺϴģʵıʶʶıУԵŹ㷺Ӧã23ݣڼʱͿռľԣֻܽͽMarkovģܴͣԵĽԼϵܴԶԼϵԵݹ󣻻ڹģʺϴıܴԶԼϵԵݹ󣬵ʺϴģϣԷӳӶ.ͳģͺ͹ķиԵŵȱ㣬ͬʱִŽǿĻ.о߰γһģͣ45.ͳģͺ͹ķϵķһ֣һַʽΪͳϢ뵽ķУγɸķһַʽΪͨѹ뵽ͳģ.ĲùģͣôMarkovͳģͺԹ򼯳һд庺ʶĺϵͳ.
2д庺ʶͳģ
д庺ʶǰʶɴпŶȵĺѡʸA=A1A2Am,AiΪiѡʸ.ÿѡʸAiӦһѡ.ģ͵ΪݺѡʸAĵĺC=C1C2Cmp(C/A)ѡC
(1)
Bayesʽ
(2)
p(A)C޹أ
(3)
p(A/C)Ϊд庺ʶϵͳǰʶɵĿŶȣʶ룩p(C)д庺ʶϵͳĺģṩ.ѡC=C1C2Cm䰴ĳֺз㷨зֳӦĴC=W1W2Wk赱ǰֻǰn-1йأɽnԪķn-1Markovģ.P(C)Ĺʽ㣺
(4)
ʵΪDnԪķĲռΪ|D|n,ڼʱͿռľԣֻܽͽMarkovģͣͳģֻܴԵĽԼϵԵԶԼϵΪ.n=1,2,3ʱnԪķֱUnigram,BigramTrigram.
ģ͵ѵϲ޴ѵûг֣ϡ.ĲԲֵ㷨ƽ.
3͹
1. A1+A2++AtBĶ򣬳ΪtԪ. Ai(1it)Ϊ.ɶ򹹳ɵļϣΪ.ԹɵļϣΪԼ.
2. Ԫؿɵݹض£
ϵͳʿΪDԼΪAΪR.
(1) wD,wԪأAttr(w)A
(2) еw1,w2,,wtDA1Attr(w1),A2Attr(w2),,AtAttr(wt)йA1+A2++AtBRʴw1,w2,wtһԪأB.A1+A2++AtBRΪ.
ҽ12ԪأΪe.
һԪضӦһ.ĸڵΪԪرӽڵΪԪأҶڵΪʵеĴʣԪصĴбΪWordlist(e)={W1W2Wn}.ɴ˿ɼԪ൱ھӵ﷨һ.
д庺ʶϵͳǰʶɵĺѡʸΪA=A1A2Am, AiΪiѡʸ.ÿѡʸAiӦһѡһֽڵ㣬еĺѡʸĺѡγmֽڵ.ϵͳʵеĿʵֽڵɴʽڵ㣬ڸôʵβڵ.ùڵķϹĽڵԪعڸԪصβڵУγԪؽڵ㣬еĽڵһͼ.аԪؽڵĴ񣬳Ԫ.ͼ1Ǵʾͼ.


ͼ1ʾͼ
3.еһ·ѡ.ԪУһѡΪӿʼʱ̵ʱ̵βԪؽڵУS=(e1e2en)eiһһڴ,бΪ:Wordlist(ei)={Wi1Wi2Witi}.
ԽǴӴһŵ·ѡ.е·Aʽͼ㷨Viterbi㷨ѡ.ĲViterbi㷨ŵѡѡۺΪ
f(S)=p(e1e2en)=1p(e1)2p(e2/e1)np(en/e1e2en-1)(5)
ЦiΪȨֵϵWordlist(ei)ĳȳȣΪͳƵͲͨѵģŻ.p(ei/e1e2ei-1)Ĺʽ㣺
(6)
ͳģΪBigram:
(7)
˵䣺һƯɰè.¹
rule1.AP+%+NPNP
rule2.AP+APAP
ʹùrule2ѡƯ͡ɰΪݴʶAP=ƯɰȻʹùrule1ѡƯɰġ͡èΪʶNP=Ưɰèѡһ͡ƯɰèͳģBigramһѡ.ѡĸΪp(s)=p(һ)p(/һ)p(Ưɰè/)p(Ưɰè/)ùʽ(7).ͨеѡѡp(s)ѡһƯɰèΪʶ.ɴ˿ɼʹùԴԶԼϵԵĵݹ.
Կ񹹳Խռ䣬ɴԪأ൱ڰ﷨мʾԪؽڵ㣬ԷϹ·νмȨԲϹ·򵥴ͳģͼ㣬ķMarkovͳģͨһдʶĺģУָͬŵѡγɵĺģ;ͳģͺ͹ķ˫صŵ㣬ԴԵԶԼϵԵݹ.
4д庺ʶ㷨
ͼ2ΪдʶĽṹͼд庺ʶĺ㷨3׶.ȴģɴ񣬹Խռ.ȻԽViterbi㷨ѡʵ·ѡΪԽʶ,پ˵УΪȷľӣCacheѧϰģ.CacheѧϰģûУľ޸ӦUnigram CacheBigram Cache,ϵͳӦûϰ.


ͼ2дʶṹͼ
4.1ģ
ģд庺ʶǰʶɵĺѡʸɴ.ģ3.ȱеĺѡȫֽڵ㣬Ȼеֽڵ㣬еĿʵֽڵȫɴʽڵ㣬еĽڵ㣬ڵĿƥһĽڵȫԪؽڵ.еĽڵ㰴ʱ̽ɵĴ񹹳Խռ.
4.2Խģ
ԽģǴӴѡŵ·ѡӣ.ĲViterbi㷨е·.һ׶ΣǰʶɵĺѡֵĿŶͨȨϵԺģ͵ĸʽͳͨȨϵԽCacheͳƿеĸͨCacheȨϵָͬ.ЩϵͳҪϸԱ֤ϵͳĿɿ.
4.3Cacheѧϰģ
Cacheһֶڼ.һѧϰĸɣԴûУľӣݴ洢ʽӦUnigramBigramͬ.ԽʱCacheеĸͨȨԺϵͳģ͵ĸʽCacheļȨϵͬϵͳѧϰʳ.
5ʵ
д庺ʶʵ.19931994ձͨѶΪģ͵ѵϣ2000֣.65000ʵBigramUnigramΪMarkovģ.ϲٷִз㷨з.ǰʶùҵѧϵġġд庺ʶϵͳ6ݣϵͳ2508˹༭Ĵʷ򡢶.ʵѡȡ5˵дݣÿд10仰,ÿ仰ƽΪ11.5֣ƽʶΪ91.3%.ʵ1ʾ.
1ʵ

ǰʶ1ѡΪȷֵƽʶ70.6%
ǰʶǰ10ѡȷֵƽʶ86.5%
ǰʶǰ20ѡȷֵƽʶ96.2%
ǰʶǰ30ѡȷֵƽʶ99.7%
д庺ʶƽʶʣͳƣ90.1%
д庺ʶƽʶʣͳ+91.3%


ͨʵԿǰʶѡȷʽϵͣǰ30ѡȷֵȷʽӽ100%д庺ʶʶʱǰʶѡʶߣ˵д庺ʶ㷨нǿʶ.ͳģͳƺ͹ϵĻģȣϵͳʶԼһٷֵ㣬˵ʺ͹ĸǶȾдڽһߣԱܸõظͳģ͵. 
6
һֹͳϵļģӦд庺ֺļѻͳƵĴʱMarkovģԹģͨһд庺ʶϵͳ.ϵͳдԵԶϵԵĵݹʵֺЧ.üֱӦдʶ򣬻Ӧӡˢ庺ʶѻд庺ʶУԡʶƴ뷨.
õҡ߼ƻĿ863-306-03-02-1.
߼飺־У196710ʿоҪд庺ʶȻⷽо.У19553ڣʿʦҪ˹ܺȻо.ſУ19646ʿҪʶо.㣬У19704ʿоҪºģ͵о.
ߵλ־ſ㡡ҵѧѧ뼼ϵ150001
ѧϵ
ο
1.еļģ͵оʿġ.ҵѧѧ뼼ϵ1997.6070
(Wang Xuan.The research of computational language model of speech and character input(in Chinese).Department of Computer Science and Technology of Harbin Institute of Technology,Harbin,1997.6070)
2Sproat R.An application of statistical optimization with dynamic programming to phonetic-input-to-character conversion for Chinese,In:Proc of R O C Computational Linguistics Conf .Taiwan, 1990.379390
3Ueberla J. Analyzing and improving statistical language models for speech recognition. School of Computer Science of Simon Fraser University, Vancouver,British Columbia,Canada,1994.1525
4Chen S F.Building probabilistic models for natural language, Department of Computer Science of Harvard University,Cambridge,1996.49
5Golding A R. A Bayesian hybrid method for context-sensitive spelling correction. In: Proc of the Third Workshop on Very Large Corpora. Cambridge,1995.3953
6ƽĺҷ.д庺ʶϵͳ.Ϣƣ1991,20(5):1821(Tang Xianglong,Shu Wenhao,Liu Jiafeng et al.The system of online handwritten Chinese character recognition based on association.Information and Control(in Chinese),1991,20(5):1821
ԭյڣ1998-06-22
޸ĸյڣ1999-01-21
