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



һֱʶƥʶ𷽷
ƽᡡҷ桡ݡ
ժҪ庺ֵʶһֱʶƥ人ʶ𷽷.ѡʶʶд˳򡢱ʶλΪҪʶ.ȣԤ׶ΣΪ˼СڷɢԣñʶܶȾ⻯ԹԱʶλý˷ԹڱʶеĻϣö̬滮㷨ѰҴʶʶѡʶеƥ·ݴ·õƥʶμȱٱʶκͶʶΣȻʶÿѡֵʶ룻󣬶ʶǰ10ĺѡ֣ƥʶμѡһб𣬴Ӷõյʶ.ʵʶ𷽷дʲݵ˳Ƚȶ庺֣յ˱ȽϺõʶЧ.
ؼʡд庺ʶ𣬱ʶУ̬滮㷨
ͼšTP391.4
A SEGMENT SEQUENCE MATCHING METHOD FOR ON-LINE
CHINESE CHARACTER RECOGNITION
TANG Jiang-Long, SUN Guang-Ling, LIU Jia-Feng, and HUANG Jian-Hua
(Department of Computer Science and Technology
Harbin Institute of Technology, Harbin 150001)
AbstractA method based on segment sequence matching is proposed for on-line Chinese character recognition. The stroke number, strode order, and stroke position are selected as the three primary recognizing features. Firstly, in order to lessen the dispersion in class, a non-linear shape normalization algorithm-line density equalization is used to equalize the stroke position. Then, dynamic programming algorithm is used to look for a optimal matching path between a candidate segment sequence and an unknown segment sequence; The matching segment set and lacked and reduced segments are obtained based on the optimal matching path; The distance between an unknown character and every candidate is calculated. Finally, the candidates whose distances are ordered pre-ten are deeply determined using the segment matching set and selecting other features, so the final recognizing result is obtained. The experimental results show that, the proposed method could yield good recognizing effect. 
Key wordson-line Chinese character recognition,segment sequence,dynamic programming algorithm
1
д庺ʶҪо壬ʵҲкҪӦüֵ1.ļˮƽõͻͽķչоĽѼ庺ֵʶ.庺ֵҪصǱʻ򲿼֮ճȽأʹڱʻ򲿼ʶ𷽷Իýϸߵʶʣص㵼庺ֵı˳仯Ͽ庺ֵı˳仯Լ٣Ϳúֵı˳Ϣȡʶ֮󣬽ʶΰպֵд˳ųһУдһ.庺ֱ˳ȶʹֵķʽΪ.Ȼڴ˻ϣڱʶеľ.ף23ӣExchangeAddɾDeleteֱӦʶΡȱٱʶΡʶ3ֶӳֵۼӺΪеľ.־һĺԣɾӳôʶʶĳʶεĳȣǴʶֵıʶγǷǳȶģҲʹյʶܲȶ.ΪˣֻýӺӣö̬滮㷨ڴʶʶѡʶ֮䣬Ѱҳһƥ·ݴ·õƥʶμȱٱʶκͶʶΣ33ͬľ빫ʽʶ3֮ͣǰ10ѡֽһбУҲѵõƥʶμ.ñķõƥʶμʶкͺѡеľ붼ߺԺ׼ȷ.
2Ԥ
ԤָȡʶκԤ.׶.
2.1һ
ддֵĴСһԱһͳһС.ȡ100100ķ.

(1)

(2)
(x,y)ǹһǰʶζ˵ꣻ(x,y)ǹһʶζ˵.
2.2Թ
Ϊ˼СڷֲķɢԼʹڷֲľֲľྡԶ룬ԹһĺֽзԹ.вñʶܶȾ⻯ķԹ3.
1.f(i,j)i=01I;j=0,1,JIJλ(i,j)ǷбʶδԽı־f(i,j)=1ʱʾ(i,j)бʶδԽf(i,j)=0ʱʾ(i,j)ޱʶδԽ
ڵiеıʶܶΪ(3)

(4)
ڵjеıʶܶΪ(5)

(6)
гĺں˵.
2.ʶηֲi,jϵıʶܶܺͷֱΪ

(7)

(8)
ʽ(3)ʽ(5)ʹһ,=0ʱ,»ҲĿռ򽫱ȫѹ;ķԹЧ̫ǿҶҲȻ,ӽԼЧ.,趨ֵΪ1.

(9)

(10)
(x,y)ΪԹǰֵ(x,y)ΪԹֵ.
3ʶ
3.1ȡƥ·
ƥ·Ӧܵһƣμͼ1.ͼʾ·вӦֵ2ֱ.ʶмƥ·ʽ£
ʶʶеĳn,Q={qj|j=1,2,n}

ͼ1
ѡʶеĳm,P={pi|j=1,2,n}

w1ΪȨֵ趨w1=1.2
x*hʾ*ʶͷ˵xֵy*hʾ*ʶͷ˵yֵx*tʾڪʶβ˵xֵy*tʾ*ʶβ˵yֵ⣺Rһ,seqʾ;ʹseq=min{seqk|k=1,2,}

jlʾlаĴʶʶĴʶʶκ.
oper(r1)=p1-q1
(il-1=iland jl-1=jl-1andjl-2jl-1)or(il-1=il-1and jl-1=jl)or(il-1=il-1and jl-1=jl-1)
ö̬滮㷨4ݽ㷨£
m=|P|n=|Q|
if(m0 or n  0 ) return FAIL
else
for i = 1 to m do
for j = 1 to n do
if( i = 1 and j = 1 )
Di,j = p1 - q1;
else if(Pointer(i,j-1)j = j-1 and Di-1,j=min(Di-1,j,Di-1,j-1) or Pointer(i,j-1)jj-1 and Di-1,j=min(Di-1,j,Di-1,j-1,Di,j-1)
Di,j=Di-1,j+w1len(pi);
else
Di,j=Di-1,j-1+pi- qj;
return Dm,nݣ
Di,jݱʾpiʶΪֹʶεӺѡʶqjʶΪֹʶεӴʶʶе̾.Pointer(i,j-1)jʾ(pi,qj-1)Ϊյ̾·յָĴʶʶеĴʶʶκ.
Ӧָ㷨ľ벢ʶ룻˲Ŀڵõƥ·ô·ʶ.
3.2Ѱƥʶμʶκȱٱʶ
(1)ƥʶμ
Ӷƥ·Ķ弰ƥ·ƥʶӦͼ1ʾˮƽ·б·.Ϊ
piMPl-qjMPl+|len(piMPl)-len(qjMPl)|=min{pil-qjl+|len(pil)-len(qjl)|,
(piMPl,qjMPl)HPl,(pil,qjl)HPl,l=1,2,s}
(piMPl,qjMPl)ΪƥʶζԣHPlΪlֲˮƽ·ϵıʶζԼϣsΪֲˮƽ·.б·ÿһӦıʶζԶƥʶζ.
(2)ʶ
ʶָʶʶδƥıʶ.
pil-qjl+|len(pil)-len(qjl)|min{pil-qjl+|len(pil)-len(qjl)|,
(piMPl,qjMPl)HPl,(pil,qjl)HPl,l=1,2,s}
ʽбʶζеqjʶζǶʶ.
(3ȱٱʶ
ȱٱʶָѡδƥıʶ.

VPkΪkֱֲ·ϵıʶζԼ,zΪֱֲ·.ʽбʶζеpiʶζǶʶ.
3.3ʶ
ʶ붨Ϊƥʧ֮.
(1)ƥ

(11)
C0ΪƥʶζԵĸpil,qjlֱʾlƥԵĺѡеıʶκʹʶеıʶ.
(2)ʧ
ַǣȱٱʶκͶʶ.
ȱٱʶ

(12)
C1ΪȱٱʶεĸplΪlȱٱʶ.
ڶʶ
ȶ4㣺
o1ΪʶεǰһʶƥԵƥβ˵һ˵㣬o2Ϊһ˵.
o3ΪʶεĺһʶƥԵƥͷ˵һ˵㣬o4Ϊһ˵.
(13)
C2ΪʶεĸohlΪlʶεͷ˵㣬otlΪlʶεβ˵㣬֮ľȡŷϾ.
Dis=Dis0+Dis1+Dis2;
(14)
ںѡʶеĳȲͬҪDisйһ.йһϵΪC0ƥʶζԵĸ
Dis1=Dis/C0;
(15)
4ǰ10ѡһб
ʶ𷽷ֵ㣬˱Ĳȡ˶ʶǰ10λĺһбʶ.һУÿһѵǶзѰҵƥʶμݴƥʶμͳƳģÿһʶһʶεӸʣÿһʶζʧʺÿһʶη루ȡ0123ַ룬ֱӦᡢƲࣩʣ

ʽNΪѵÿһѡ֣Ϊ

(16)
ʽmΪģбʶθ.
ʶFinalDis=Dis1+w2Dis2;(17)
w2ΪȨֵ趨w2=0.3.
5ʵ
Թһ֣ƽÿ200,100Ϊ(дд),100Ϊ(дԼϰд),200ռ757555.Խ£
1ʶͳƱ

1ѡǰ10ѡ
96.79%99.38%
92.95%98.68%

ʶԭ:
(1)ַ;
(2)ֹ,ʶ;
(3)ʶֱι,޷ʶ;
(4)дѼı˳. 
õҡ߼ƻĿĿ863-306-ZD03-02-06ͺʡȻѧĿ(ĿF9908).
߼飺ƽУ196011ʿڣҪоΪģʽʶϢ
˹ܵ.
ᣬŮ19745ʿоҪоΪд庺ʶ.
ҷ棬У196910ʿڣҪоΪ˹ܡģʽʶ.
ݾУ19757˶ʿоҪоΪѧϰ.
ߵλҵѧѧ빤ϵ150001
ο
1.ʶ.:廪ѧ,1992
(Zhang XingZhong. Chinese Character Recognition Technology(in Chinese). Beijing: Tsinghua University Press, 1992)
2Tsay Y T, Tsai W H. Attributed string matching by split-and-merge for on-line Chinese character recognition. IEEE Trans PAMI, 1993, 15(2): 180185
3Hiromitsu Yanada et al. A nonliner normalization method for handprinted kanji characters recognition-line density equalization. Pattern Recognition. 1990, 23(9): 10231029
4, . 㷨ݽṹ. : ӹҵ, 1998
(Fu QingXiang, Wang Xiaodong. Algorithm and Data Structure(in Chinese). Beijing: Electronics Industry Press, 1998)
ԭյڣ1999-02-08޸ĸյڣ1999-06-14.
