白曉東, 姜 杰, 鄧紅靜, 李 藝

(南京師范大學(xué) 1a.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院; 1b.教育科學(xué)學(xué)院，江蘇 南京 210023;2.江蘇省信息安全保密技術(shù)工程研究中心，江蘇 南京 210097)

?

基于相似度的手寫漢字筆劃鑒別方法實(shí)驗(yàn)研究

白曉東1a，2, 姜 杰1b, 鄧紅靜1b, 李 藝1b

(南京師范大學(xué) 1a.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院; 1b.教育科學(xué)學(xué)院，江蘇 南京 210023;2.江蘇省信息安全保密技術(shù)工程研究中心，江蘇 南京 210097)

針對(duì)手機(jī)和平板電腦上手寫漢字主流的xml存儲(chǔ)格式，提出了一種對(duì)識(shí)別用戶手寫漢字筆劃的算法。算法首先從三種結(jié)構(gòu)特征對(duì)手寫漢字進(jìn)行編碼，然后計(jì)算用戶字筆劃、模板字筆劃之間不同編碼集合的相似度，最后組合多種相似度識(shí)別手寫漢字的筆劃，并通過三種應(yīng)用實(shí)驗(yàn)驗(yàn)證方法的有效性。筆順的判別一直是手寫漢字識(shí)別的難點(diǎn)，文章中提出的方法筆順的識(shí)別率高達(dá)95%以上。此算法在用戶字的多筆、少筆判別、筆順判別、整字的正確性以及美觀性判別等方面都有著廣泛的應(yīng)用。

改進(jìn)型Hausdorff距離; 方位編碼; Voronoi圖; 拓?fù)湎嗨贫?/p>

0 引 言

當(dāng)前，以手機(jī)和平板電腦為代表的移動(dòng)式智能電子產(chǎn)品已經(jīng)成為人們生活中不可或缺的部分，與之相關(guān)的海量軟件也伴隨而來，在眾多的軟件中，漢字手寫軟件無疑是最具中國文化特色的產(chǎn)品，如今，漢字手寫類軟件已經(jīng)廣泛應(yīng)用于各個(gè)領(lǐng)域[1]。然而，為此類軟件提供支持的漢字手寫研究多集中在漢字識(shí)別環(huán)節(jié)，隨著人們對(duì)漢字手寫平臺(tái)需求的不斷深入，可能要求計(jì)算機(jī)對(duì)手寫漢字的正確性、美觀性、書寫風(fēng)格等做出評(píng)價(jià)，甚至要求計(jì)算機(jī)對(duì)書寫者性格、心理狀態(tài)等做出準(zhǔn)確的判斷，這給漢字手寫研究帶來了新的挑戰(zhàn)。

手寫漢字識(shí)別后研究所涉及的判斷與評(píng)價(jià)，其關(guān)鍵步驟是筆劃正確性識(shí)別：即判斷手寫漢字的每個(gè)筆劃是什么筆劃，書寫是否正確，同時(shí)判斷它的書寫順序是什么。然而，漢字的種類多樣、結(jié)構(gòu)復(fù)雜，每個(gè)漢字都由若干個(gè)筆劃組成；每個(gè)人書寫漢字的筆順和筆劃也可能不一樣，這就造成了書寫后的漢字可能存在不同程度的“畸變”，這些都給手寫漢字正確筆劃的辨識(shí)帶來了困難。

手寫漢字識(shí)別后研究通常都是通過與模板字比對(duì),完成對(duì)其細(xì)節(jié)的判斷與評(píng)價(jià)。人們辨識(shí)手寫漢字的某個(gè)筆劃時(shí)一般會(huì)這樣考慮：“在正確的方位上筆劃的形狀正確，同時(shí)它與其它筆劃的關(guān)系也是正確的，那么，就是這個(gè)筆劃”，由此可見，方位、形狀和筆劃間拓?fù)潢P(guān)系這三個(gè)手寫漢字的結(jié)構(gòu)特征是辨識(shí)正確筆劃的關(guān)鍵因素。本文通過抽取漢字筆劃上述三種特征的編碼，計(jì)算手寫漢字筆劃與模板字筆劃三種編碼的相似度，最后通過總相似度來決定手寫漢字筆劃與模板字筆劃的對(duì)應(yīng)關(guān)系，從而判斷出手寫漢字的筆劃是否書寫正確，筆順是否與標(biāo)準(zhǔn)字一致，而且可以發(fā)現(xiàn)是否有多筆、少筆的現(xiàn)象發(fā)生。與傳統(tǒng)處理方法相比，這種方法不需要對(duì)原始數(shù)據(jù)進(jìn)行平滑、規(guī)整等預(yù)處理，減少了中間環(huán)節(jié)，提高了識(shí)別效率。

1 判別前處理

聯(lián)機(jī)手寫漢字測試多采用CASIA的OLHWDB數(shù)據(jù)庫，而目前移動(dòng)設(shè)備主流的方法是將手寫漢字的軌跡信息和時(shí)間信息存儲(chǔ)在xml文件中，如圖1所示，用戶字和由專家書寫的模板字均保存于xml文件中：手寫漢字由筆劃stroke構(gòu)成，而stroke由point構(gòu)成，每個(gè)point記錄了筆尖(指尖)移動(dòng)軌跡的x、y坐標(biāo)和其時(shí)間戳，因此，移動(dòng)手寫設(shè)備中的漢字筆劃被表述成了二維空間的點(diǎn)集信息。判別前需要對(duì)模板字和用戶字進(jìn)行空間配準(zhǔn)，經(jīng)典配準(zhǔn)方法首先要計(jì)算匹配對(duì)象的最小覆蓋區(qū)域，如最小凸閉包(MCC)、最小外接矩形(MBR)和最小外接圓(MBC)等[2-3]，然后經(jīng)過仿射變換或RST變換使兩個(gè)匹配空間重合[4-5]。由于用戶字與模板字可能存在著較大差異，而且這種差異是個(gè)體的差異(例如用戶字可能存在多方向傾斜)，而非系統(tǒng)性的，因此用上述方法進(jìn)行空間配準(zhǔn)并不科學(xué)。本文根據(jù)移動(dòng)設(shè)備上手寫漢字筆劃的存儲(chǔ)特點(diǎn)，簡化了這一過程：首先以模板字點(diǎn)集中的xmin、xmax、ymin、ymax組成水平矩形作為待匹配空間，然后對(duì)用戶字的所有筆劃(點(diǎn)集)做RST變換，即

圖1 移動(dòng)設(shè)備上手寫漢字的存儲(chǔ)與比對(duì)

2 編碼的抽取

2.1 筆劃方位編碼和形狀編碼的抽取

以AR的對(duì)角線交叉點(diǎn)為圓心，將半對(duì)角線4等分分別為半徑，做4個(gè)同心圓，從圓心做射線8等分同心圓，則區(qū)域被分割為32份。同心圓從內(nèi)向外編號(hào)，分別為1到4，從水平45°開始順時(shí)針旋轉(zhuǎn)，8個(gè)方向依次編號(hào)為1～8，如圖2所示。

圖2 用于方位編碼和形狀編碼的坐標(biāo)體系

筆劃點(diǎn)集中的所有點(diǎn)都可以用c(i,j)來表示其方位，其中i表示此點(diǎn)所在的方向1～8，j表示此點(diǎn)距離中心點(diǎn)的遠(yuǎn)近，即相對(duì)位置1～4。筆劃k的方位編碼可以用c(i,j)的集合表示，即：

2.2 筆劃的拓?fù)潢P(guān)系編碼的抽取

筆劃的拓?fù)潢P(guān)系是筆劃間交、接、鄰、離的關(guān)系，它是識(shí)別筆劃時(shí)需要抽取的重要特征，可以通過常規(guī)的幾何方法獲取一個(gè)手寫漢字多個(gè)筆劃間的拓?fù)潢P(guān)系，但是過程非常繁瑣，而且容易出現(xiàn)誤判或漏判的情況，本文中采用一種基于Voronoi圖的筆劃拓?fù)潢P(guān)系判斷算法[6-8]，方便快捷且不會(huì)出現(xiàn)漏判的情況。

(a)

(b)

(c)

(d)

算法 foundTopolpgy(V(P)):

輸入 以漢字筆劃端點(diǎn)和筆段端點(diǎn)為基元的AR區(qū)域Voronoi圖。

輸出 每個(gè)筆劃與其它筆劃的拓?fù)潢P(guān)系集。

(1) 初始化隊(duì)列Q，將所有的筆劃(筆劃端點(diǎn)+筆段端點(diǎn))放入;

(2) 初始化隊(duì)列T，將所有的筆劃(筆劃端點(diǎn)+筆段端點(diǎn))放入;

(3)a=0;

(4) while(Q不空){

(5) 從Q中取出筆劃si;

(6) while(T不空且i!=j){

(7) 從T中取出筆劃sj;順序掃描si中的點(diǎn);

(10) 從T中去除sj;break;

(13) 從T中去除sj;break;

(14)a++;

(15) };

(17) 從T中去除sj;break;

(18) if(T不空且剩余筆劃數(shù)為t);

(20) 將所有的筆劃放入T;從Q中去除si;a=0;

(21) }。

3 相似度計(jì)算

3.1 方位相似度和形狀相似度的計(jì)算

方位相似度的計(jì)算要同時(shí)考慮方向和位置因素，而且二者同等重要，因此，可采用方向和位置的乘積關(guān)系表示方位。Hausdorff距離(HD)是衡量元素不相等點(diǎn)集相似性的經(jīng)典方法，Dubuisson和Jain[9]提出了改進(jìn)型Hausdorff距離(MHD)。MHD將單向Hausdorff距離定義為

算法 simpos(S,S')。

輸入 模板字方位碼集S和用戶字方位碼集S'。

輸出 方位相似度矩陣U。

(1) 初始化隊(duì)列Q，將S的所有筆劃放入;

(2) 初始化隊(duì)列T，將S'的所有的筆劃放入;

(3) while(T不為空){

(4) 從T中取出s'i;

(5) while(Q不為空){;

(6) 從Q中取出sj;

(7) 計(jì)算s'i和sj的方向MHD：HMND(s'i,sj);

(8) 計(jì)算s'i和sj的相對(duì)位置MHD：RMND(s'i,sj);

(9)U(i,j)=1-HMND(s'i,sj)×RMND(s'i,sj)/Tpos

(10) }

(11) 將S的所有筆劃放入Q;

(12) }

說明：Tdirection=max{HMND(s'1,s1),HMND(s'1,s2),…,HMND(s'm,sn)};

Tlocation=max{RMND(s'1,s1),RMND(s'1,s2),…,RMND(s'm,sn)};

方位相似度矩陣表示為

U=

V=

3.2 拓?fù)潢P(guān)系相似度的計(jì)算

拓?fù)潢P(guān)系相似度的計(jì)算要考慮交、接、鄰、離之間的遠(yuǎn)近關(guān)系[10-11]：交與接最相似，與鄰的關(guān)系次之，與交最不相似的是離；接與交、鄰的關(guān)系最相似，與離的關(guān)系最不相似；鄰與接、離的關(guān)系最相似，與交的關(guān)系最不相似；離與鄰最相似，與接的關(guān)系次之，與交的關(guān)系最不相似[12-13]。為了體現(xiàn)交、接、鄰、離之間的遠(yuǎn)近關(guān)系，定義筆劃sk的拓?fù)鋽?shù)量值：

ftopology(sk)=sk(intersect)×23+sk(phase)×22+sk(adjacent)×21+sk(depart)

識(shí)別筆劃，交的關(guān)系最為重要，接次之，然后才是鄰、離[14-15]，上述定義體現(xiàn)了這個(gè)因素。同時(shí)，將交、接、鄰、離映射成數(shù)值使用戶字和模板字在拓?fù)潢P(guān)系上具有了可比性。這樣定義用戶字筆劃s'i和模板字筆劃sj的拓?fù)湎嗨贫?/p>

拓?fù)潢P(guān)系相似度矩陣為

W=

3.3 總相似度

總相似度是通過計(jì)算3種特征相似度的加權(quán)平均得到的，設(shè)置不同特征的權(quán)值可以使總相似度更加體現(xiàn)手寫字的特點(diǎn)。由于用戶在書寫時(shí)隨意性較大，筆畫變形可能較嚴(yán)重，因此考慮給形狀相似度較小的權(quán)重。上文中的U、V、W矩陣都是無量綱的矩陣，通過矩陣的加權(quán)平均就可以獲得總相似度矩陣：

其中，ω1=ω2=0.4，ω3=0.2。矩陣S是用戶字筆劃識(shí)別的依據(jù)。通過S，可以對(duì)用戶的書寫做如下判斷：

(2) 是否存在錯(cuò)誤的筆劃：若S的行向量Pi的每一個(gè)分量ak，k=1,2,…,n均小于T，則筆劃i是錯(cuò)誤的筆劃。T是相似度閾值。

(4) 特殊情況的處理，用戶字筆劃i1和筆劃i2匹配到相同的模板字筆劃j：① 如果Pi1和Pi2都還有大于T的分量，則選ai1和ai2的較大者與筆劃j匹配；② 如果Pi1和Pi2中的某一個(gè)只存在一個(gè)大于T的分量，另一個(gè)還有大于T的分量，則選擇前者與j匹配；③ 如果Pi1和Pi2都只存在一個(gè)大于T的分量，則選擇ai1和ai2中較大者與筆劃j匹配，另一個(gè)被視為錯(cuò)誤的筆劃。

4 實(shí)驗(yàn)與分析

實(shí)驗(yàn)選擇三星GT-N8010作為手寫設(shè)備，屏幕大小10.1″，屏幕像素密度149PPI，4核CPU，主頻1.4 GHz，內(nèi)存2 GB，Android4.0操作系統(tǒng)。書寫工具為三星自帶1 024級(jí)靈敏度S-Pen手寫筆，實(shí)驗(yàn)程序模仿軟筆書法效果。軟件的界面風(fēng)格如圖4所示。測試字和測試對(duì)象的選擇強(qiáng)調(diào)對(duì)整體的覆蓋，以方便觀察算法的有效性。共選用550個(gè)漢字作為實(shí)驗(yàn)用字，事先由書法專家制作完成。這550個(gè)漢字中，根據(jù)漢字的特點(diǎn)分別選取了獨(dú)體字100個(gè)(I)、左右結(jié)構(gòu)的漢字100個(gè)(II)、上下結(jié)構(gòu)的漢字100個(gè)(III)、左中右結(jié)構(gòu)的漢字加上中下結(jié)構(gòu)的漢字100個(gè)(IV)、內(nèi)外結(jié)構(gòu)的漢字加半包圍結(jié)構(gòu)的漢字100個(gè)(V)、復(fù)雜結(jié)構(gòu)的漢字50個(gè)(VI)，為了驗(yàn)證算法的效果，在這些漢字中，還特別標(biāo)注了字形相似的漢字，例如“末”和“未”，“人”和“入”等，字形相似的漢字共52組，121個(gè)漢字(X)，每組2-4個(gè)漢字不等，為了做到無情境帶入，測試時(shí)X組的漢字不依組別，隨機(jī)呈現(xiàn)。括號(hào)中是每個(gè)組別的編號(hào)，550個(gè)測試漢字涵蓋了所有漢字結(jié)構(gòu)類型和繁簡程度。分別選擇小學(xué)生36人(P)、初中生45人(H)、普通成人20人(A)和文案工作者5人(I)作為書寫測試對(duì)象，他們分別代表漢字初學(xué)者、漢字學(xué)習(xí)者、漢字使用者和漢字書寫熟練者，可以覆蓋漢字書寫幾乎所有的人群，括號(hào)中是他們的類別。被試的書寫實(shí)驗(yàn)安排如表1所示。

第2組實(shí)驗(yàn)考慮到小學(xué)生是初學(xué)寫字，容易出現(xiàn)多筆、少筆、筆劃、筆順等錯(cuò)誤，而成年人已經(jīng)形成了固定的書寫習(xí)慣，也容易有上述錯(cuò)誤，讓他們寫結(jié)構(gòu)復(fù)雜的漢字錯(cuò)誤出現(xiàn)的頻率較高。第4組實(shí)驗(yàn)的考慮相同。實(shí)驗(yàn)共收集22 596個(gè)樣本，其中有效樣本19 372個(gè)，實(shí)驗(yàn)的分析過程在Eclipse KEPLER平臺(tái)J2EE版本上編寫java程序處理19 372個(gè)xml文件。

分別定義判斷多筆、少筆的查準(zhǔn)率和召回率為：

分別定義判斷錯(cuò)誤筆劃的查準(zhǔn)率和召回率為：

定義筆順的識(shí)別率為：

表2是實(shí)驗(yàn)結(jié)果列表。

表2 手寫漢字筆劃識(shí)別的實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)

從統(tǒng)計(jì)數(shù)據(jù)可以看出，多筆、少筆的識(shí)別基本沒有錯(cuò)誤，錯(cuò)誤筆劃的識(shí)別率也較高，筆順的識(shí)別率雖然也在95%以上，但是還有待于提高。

5 結(jié) 語

本文從手寫漢字的三種結(jié)構(gòu)特征出發(fā)，對(duì)手寫漢字進(jìn)行編碼，然后計(jì)算用戶字筆劃、模板字筆劃之間不同編碼集合的相似度，最后組合多種相似度識(shí)別手寫漢字的筆劃，并通過三種應(yīng)用的實(shí)驗(yàn)驗(yàn)證方法的有效性。筆順的判別一直是手寫漢字識(shí)別的難點(diǎn)，實(shí)驗(yàn)證明，本文提出的方法對(duì)筆順的識(shí)別率高達(dá)95%以上。

在此基礎(chǔ)上，可以進(jìn)一步研究如何評(píng)價(jià)手寫漢字的正確性和美觀性，還可以研究書寫者的寫字風(fēng)格和心理狀態(tài)，可以想見，這些研究在漢字書法教育、心理學(xué)等領(lǐng)域有著廣泛的應(yīng)用前景。

[1] 陳 鄒.用戶自適應(yīng)聯(lián)機(jī)手寫漢字識(shí)別方法[D].深圳:哈爾濱工業(yè)大學(xué)深圳研究生院,2010.

[2] Shahabi C,Safar M.Efficient retrival and spatial querying of 2D objects[C]∥Proceedings of the IEEE International Conference on Multimedia Computing and Systems(ICMCS),1999,2:611-617.

[3] Safar M，Shahabi C.2D topological and direction relations in the world of minimum bounding circles[C]∥1999 International Database Engineering and Applications Symposium,1999:239-247.

[4] Latecki L J,La k'mper R.Application of planarshape comparison to object retrieval in image databases[J].Pattern Recognition,2002,35(1):15-29.

[5] Bengtsson A, Eklundh. Shape Representation by Multiscale Contour Approximation[J]. EEE Transactions on Pattern Analysis and Machine Intelligence,1991,13(1):85-93.

[6] 周培德.計(jì)算幾何——算法分析與設(shè)計(jì)[M].北京：清華大學(xué)出版社,2000.

[7] CHEN Jun, LI Cheng-ming, LI Zhi-lin,et al. A Voronoi-based 9-intersectionModel forSpatial Relations[J]. International Journal of Geographical Information Science,2001, 15(3): 201-220.

[8] LI Zhi-lin,ZHAO Ren-liang,CHENJun.A Voronoi-based Spatial Algebra forSpatial Relations[J]. Progress inNatural Science, 2002, 12(7): 528-536.

[9] Dubuisson M P，JAIN A K.A modified Hausdorff distance for object matching[C]∥Proceedings of the 12th IAPR International Conference on Pattern Recognition,1994:566-568.

[10] Eliseo Clementini, Paolino Di Felice, Peter van Oosterom. A small set of formal topological relationships suitable for end-user interaction [C]∥Advances in Spatial Databases Lecture Notes in Computer Science,1993,692:277-295.

[11] Clementini E,Difelice P D. A comparison of methods for representing topological relationships [J]. Information Science,1995,3(3):149-178.

[12] 林金坤.拓?fù)鋵W(xué)基礎(chǔ)[M].北京:科學(xué)出版社,2004:48-55.

[13] 鄧 敏.矢量數(shù)據(jù)拓?fù)潢P(guān)系擴(kuò)展模型的理論與方法[D].武漢:武漢大學(xué),2003.

[14] 郭慶勝,杜曉初,劉 浩.空間拓?fù)潢P(guān)系定量描述與抽象方法研究[J].測繪學(xué)報(bào),2005,34(2):123-128.

[15] 鄧 敏,馮學(xué)智,陳曉勇.面目標(biāo)間拓?fù)潢P(guān)系形式化描述的層次模型[J].測繪學(xué)報(bào),2005,34(2):142-147.

Experiment Research on the for the Stroke of Handwritten Chinese Characters Identification Method Based on Similarity

BAIXiao-dong1a，2,JIANGJie1b,DENGHong-jing1b,LIYi1b

(1a. School of Computer Science and Technology, 1b. Education Technology Department of Education Science School, Nanjing Normal University, Nanjing 210097, China; 2. Jiangsu Engineering Research Center of Information Security Technoly, Nanjing 210097, China)

For the handwritten Chinese mainstream storage format of mobile phones and tablet PC, this paper proposes a handwritten Chinese character strokes recognition algorithms, Firstly the three structural features of handwritten Chinese characters are encoded, and then calculate the word stroke among users, templates word strokes similarity different set of encoding, and finally a combination of a variety of similarity recognize handwritten Chinese character strokes and three applications through experimental verification of the validity of the method. Stroke discrimination has been the difficulty of handwritten Chinese character recognition, and the recognition rate of the proposed method stroke up to 95%. The algorithm in user word multi pen and pen less discrimination, stroke identification, the whole character of the correctness and aesthetic judgment, etc. have a wide range of applications.

improved hausdorff distance; orientation coding; Voronoi diagram; topological similarity

2015-05-20

江蘇省高校哲學(xué)社會(huì)科學(xué)基金項(xiàng)目(2011SJB8800287)；江蘇省教育科學(xué)“十二五”規(guī)劃項(xiàng)目 (D/2011/01/055)

白曉東(1969-)，男，河北唐山人，碩士，講師，主要研究領(lǐng)域?yàn)橛?jì)算幾何、圖形學(xué)、圖像處理等。

Tel.：13851580972; E-mail: baixiaodong@njnu.edu.cn

HP 311

A

1006-7167(2015)12-0132-05