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

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

?

基于相似度的手寫漢字筆劃鑒別方法實驗研究

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

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

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

改進型Hausdorff距離; 方位編碼; Voronoi圖; 拓撲相似度

0 引 言

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

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

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

1 判別前處理

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

圖1 移動設備上手寫漢字的存儲與比對

2 編碼的抽取

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

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

圖2 用于方位編碼和形狀編碼的坐標體系

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

2.2 筆劃的拓撲關系編碼的抽取

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

(a)

(b)

(c)

(d)

算法 foundTopolpgy(V(P)):

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

輸出 每個筆劃與其它筆劃的拓撲關系集。

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

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

(3)a=0;

(4) while(Q不空){

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

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

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

(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 相似度計算

3.1 方位相似度和形狀相似度的計算

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

算法 simpos(S,S')。

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

輸出 方位相似度矩陣U。

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

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

(3) while(T不為空){

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

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

(6) 從Q中取出sj;

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

(8) 計算s'i和sj的相對位置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 拓撲關系相似度的計算

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

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

識別筆劃，交的關系最為重要，接次之，然后才是鄰、離[14-15]，上述定義體現(xiàn)了這個因素。同時，將交、接、鄰、離映射成數(shù)值使用戶字和模板字在拓撲關系上具有了可比性。這樣定義用戶字筆劃s'i和模板字筆劃sj的拓撲相似度

拓撲關系相似度矩陣為

W=

3.3 總相似度

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

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

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

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

4 實驗與分析

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

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

分別定義判斷多筆、少筆的查準率和召回率為：

分別定義判斷錯誤筆劃的查準率和召回率為：

定義筆順的識別率為：

表2是實驗結果列表。

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

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

5 結 語

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

在此基礎上，可以進一步研究如何評價手寫漢字的正確性和美觀性，還可以研究書寫者的寫字風格和心理狀態(tài)，可以想見，這些研究在漢字書法教育、心理學等領域有著廣泛的應用前景。

[1] 陳 鄒.用戶自適應聯(lián)機手寫漢字識別方法[D].深圳:哈爾濱工業(yè)大學深圳研究生院,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] 周培德.計算幾何——算法分析與設計[M].北京：清華大學出版社,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] 林金坤.拓撲學基礎[M].北京:科學出版社,2004:48-55.

[13] 鄧 敏.矢量數(shù)據(jù)拓撲關系擴展模型的理論與方法[D].武漢:武漢大學,2003.

[14] 郭慶勝,杜曉初,劉 浩.空間拓撲關系定量描述與抽象方法研究[J].測繪學報,2005,34(2):123-128.

[15] 鄧 敏,馮學智,陳曉勇.面目標間拓撲關系形式化描述的層次模型[J].測繪學報,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

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

白曉東(1969-)，男，河北唐山人，碩士，講師，主要研究領域為計算幾何、圖形學、圖像處理等。

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

HP 311

A

1006-7167(2015)12-0132-05