文字書寫過程描述字自動生成

彭喻杰，戴 永

PENG Yujie,DAI Yong

湘潭大學 智能計算與信息處理教育部重點實驗室，湖南 湘潭411105

Key Laboratory of Intelligent Computing& Information Processing,Ministry of Education,Xiangtan University,Xiangtan,Hunan 411105,China

1 引言

多文種融合是當前文字書寫自動教學系統的研究方向，文獻[1]給出一種多文種融合文字書寫自動教學系統的技術框架，涉及簿筆隱喻[2]、在線監督、宜教筆跡處理[3]、語音融合[4]、教學知識表達、具體文種的自動教學實現[5-8]及教室系統構建[9]等。文[2]提出觸摸屏書寫特有問題即筆力評價策略；文[3]針對書寫教學改進傳統的筆跡信息前置處理方法；文[4]為適用多文種教學需求，探討多文種融合語音信息處理技術；文[5-8]分別就英語單體字母與連寫字母、漢字書寫等的教學方法進行研究；文[9]實現以文字書寫教學裝置為終端的教室系統構想，作為系列篇，該文探討教學知識點的核心字段：文字書寫過程描述字。眾所周知，不同文種文字書寫過程具備公共與獨特形態、規則等，據此提出能適用多文種文字書寫過程計算的描述字結構及其自動生成的方法。將文字書寫過程中的內容分為主導筆順和約束筆順兩大類，主導筆順對應的描述字包括筆畫編碼、筆畫關系與部件關系編碼，約束筆順對應的描述字含錯交、錯離序列碼等字段；定義描述字結構；依據要素元編碼應滿足的基本要求，設計其編碼空間生成機制；給出主導及約束筆順的自動生成算法。漢字、英文、漢語拼音三文種文字融合的實驗與分析表明，描述字結構可滿足不同文種文字書寫過程的表達，筆畫、筆畫關系、部件關系等知識要素可正確分類。與手工法相比，工作效率、知識的準確率提高，信息冗余度降低，有效克服了多語源導致知識點數據類型多、計算結構復雜及知識量大等給文字書寫過程描述字創建帶來的困局。

2 描述字結構

文字書寫過程包括的內容分為主導筆順與約束筆順兩大類。主導筆順指人們公認的文字書寫順序，要素有筆畫、筆畫關系、部件關系等。約束筆順具有預測性，設置錯交與錯離兩類，錯交筆順指當前寫出筆畫與跨緊鄰的已寫筆畫形成的錯誤十字交筆畫對偶序列；錯離筆順指當前寫出筆畫與跨緊鄰已寫筆畫正確關系缺失的描述結構序列。圖1 為描述字結構圖。

圖1 描述字字段結構圖

s、? 分別表示筆畫與關系，?s、?ρ依次表示筆畫關系、部件(G) 關系。設文字W包含k條筆畫，即W={s1，s2，…，sk}，主導筆順記為s1→s2→…→sk，對于si，sj，如果i=j+1，i，j∈{1，2，…，k}，稱si，sj為緊鄰筆畫；當i＞j+1，且si，sj成錯誤十字交關系時，由(si，sj)構成的序列稱為錯交筆順，筆順對偶集合記為SEC，若預測W存在z次錯交，；i＞j+1，且si，sj未形成應有的?s，稱si、sj錯離?s，記為(si，sj，?s，θ)，θ為?s的畸變系數，根據?s的屬性設置。4 元結構形成的序列稱為錯離筆順，筆順元素集合記為SEL。若 預測W存在q次錯離，。圖2（a）、（b）為第3、1筆畫錯交，圖2（c）為第4、1 畫錯離，圖2（d）為第3、1 筆畫錯離。

圖2 文字書寫結構示例

設被練習書寫的文字由c個部件組成，c個部件存在h層嵌套結構，文字書寫過程的描述字結構定義為：。其中，與W的元素序列s1，s2，…，sk有 序 對 應，如s1…11為W中 的s1，為W中的sk，其余類推；；i＞j+1，i，j∈{1，2，…，k}；u＞v+1，u，v∈{1，2，…，k}。

3 要素元編碼空間

為使描述字能多文種通用，要素元編碼應達到的基本要求為：（1）不同要素有明顯的數值段；（2）能體現不同文種共享與獨特要素的區別；（3）具有能自動適用于文種增加和要素元數量變化的編碼機制等。

基于任意文種構字筆畫長短存在差異的基本事實，將筆畫規模進行n粒度劃分。文字書寫格為N×N像素，粒度間隔為σ，粒度劃分范圍為δmin+(m-1)σ≤δi≤δmin+mσ，δmin是最短筆畫長度，δi為當前粒度范圍，m∈{1，2，…，n}，σ=N/(N-δmin)。要素元的編碼遞進結構設置：筆畫→筆畫關系→部件關系┫共享筆畫→獨特筆畫→共享筆畫關系→獨特筆畫關系→共享部件關系→獨特部件關系。

g1、g2、g3、g4、g5、g6分別表示系統可教學文種的共享與獨特的筆畫、筆畫關系及部件關系數目，μ1、μ2、μ3、μ4、μ5、μ6分別表示各數目的裕量。筆畫編碼為基準編碼，單粒度占用編碼范圍為1～(g1+g2)，當粒度為m時，編碼范圍為1～m×(g1+g2)，考慮裕量，確認的筆畫編碼范圍為1～m×(g1+μ1+g2+μ2)，最大值需j位表示，個位為1，高位為j-1 個0 是首條共享筆畫的編碼。編碼數目為m×(g1+μ1+g2+μ2)。s編碼的最高位位值用bitmax表示，令B1為對應于筆畫關系?s類編碼，當s(bitmax)+b≤9，b∈{1，2，…，8}，B1取j位，且s(bitmax)＜B1(bitmax)≤s(bitmax)+b，低j-1 位編碼全取0；否則B1取j+1位，B1(bitmax)=1，低j位編碼全取0。確認的?s類編碼范圍為B1(bitmax)×10(j-1∩or∩j)～[B1(bitmax)×10(j-1∩or∩j)+(g3+μ3+g4+μ4)]。B1(bitmax)×10(j-1∩or∩j)為首個共享筆畫關系的編碼。從文字書寫教學的角度出發，筆畫關系編碼需進行多層次空間關系描述。設建立e層空間關系，?s編碼的完整結構定義為B1(B2B3…Be+1)，B2B3…Be+1為空間關系細分描述碼，Bi是對Bi-1的進一步細分(i∈{2，3，…，e+1}，Bi∈{0，1，…，9})，e+1 越大，空間關系描述越精細。設b2b3…be+1依次分別對應B2B3…Be+1的取碼數量，筆畫關系編碼數目為(g3+μ3+g4+μ4)×b2×b3…×be+1。部件關系與筆畫關系的接碼及其編碼原理基本類似筆畫關系與筆畫，不同之處在于部件關系編碼的結尾碼字標注的該部件與后續多少部件構成該關系編碼所標注的關系，用x表示結尾碼，其缺省值為1，x無當前空間標識作用，因此不影響編碼數量。

4 生成算法

將文字書寫過程描述字表示為向量D，D=[S R SECSEL]，其 中，為 筆 畫 子向量；，為 關 系 子向量，由?s、?ρ共同組成；，為錯交子向量；，為錯離子向量。通過對文字標準書寫過程跟蹤有序生成S、R、SEC、SEL。跟蹤主導筆順不但要產生S、R，還要為生成SEC、SEL準備筆畫數據。R中既有?s，也有?ρ，兩者的生成方法有較大區別。

4.1 S 與?s 編碼

借鑒已有成果[10-11]對當前書寫筆畫si(i=2，3，…，k)進行識別，將識別結果的筆畫編碼有序存入S。在si、si-1之間進行e+1 次計算分析，將的屬性編碼有序存入R。當si、si-1之間無法在系統中找到相應的計算模型分析時，在si、si-1之間預置部件分割的通用標志。寫完文字最后一條筆畫，即i=k，S生成結束；R中?s有確定的代碼，但其中需進一步分析；提供k行筆跡數據陣列P[k，lmax]，lmax為該字最長的筆畫筆跡點數量。

4.2 ?ρ 編碼

部件關系依托R、P[k，lmax]分析。設R中存在a個。在R中搜素到(j=1，2，…，a)，在P[k，lmax]中獲取Gj、Gj+1所含s，利用部件關系分析模型計算Mj_Mj+1關系，將分析結果對應的編碼有序存于位置。第1 輪均按x=1 建立部件關系，第2 輪進行跨部件關系分析，即如果Gj_Gj+2關系與Gj_Gj+1關系相同，則x+1。依次類推，直至j=a-2。

算法1識別與賦碼

輸入：R（含），P[k，lmax]

注釋：RecMRelation（）為部件關系識別函數，Cpart為部件關系編碼容器，對應,x為部件關系細分編碼。

4.3 SEC 預測

文字書寫主導筆順正確，進行錯交碼對偶預測。在P[k，lmax]中，對于si、sj，將si兩端點的筆段按其形態進行延伸，對所有的sj(j∈{i-2，i-3，…，1})進行十字交關系分析，形成初選筆畫書寫序號構成的十字交序號對偶序列，借助共享工作容器進行對偶元素去留分析，分析模型為

即將si端點到si、sj交點距離最短的那一對(i，j)有序填入SEC。dis(wi_endp，wiwj_Inters)為si端點到si、sj十字交點的距離計算函數。

4.4 SEL 預測

對于書寫結構確認正確的W，設其存在q對有可能產生錯離的筆畫，在P[k，lmax]中取第τ對可能產生錯離的si、sj，記為siτ、sjτ，τ=1，2，…，q，識別siτ、sjτ之間的關系，并根據類別選擇θ，將對應的編碼、當前(i，j)和θ一起構成(iτ，jτ，，θτ)結構，將此結構先存儲在共享工作容器內。如此，完成q對筆畫的錯離碼鏈在SEL中的生成。

算法2生成錯離子向量

輸入：P[k，lmax]

輸出：SEL

注釋：nodical 兩筆畫交點，Cerrorl 錯離關系對偶容器，對應SEL。

4.5 主要步驟

描述字生成過程分為兩個階段，第一階段是跟蹤文字書寫過程實時生成S、R中的?s及P[k，lmax]；第二階段是基于P[k，lmax]生成R中的?ρ、SEC、SEL。

步驟1讀入當前書寫筆畫數據。

步驟2對筆畫數據進行前置處理，并有序存入P[k，lmax]。

步驟3識別當前筆畫，將對應的筆畫編碼有序存入S。

步驟4對于非第1 條筆畫，分析其與前條筆畫的關系，存在關系，將關系碼有序存入R；不存在則存入部件分割標注。

步驟5有文字寫完信息否?無則轉步驟1。

步驟6基于P[k，lmax]查詢部件分割標志，識別部件關系，將關系碼替代分割標志符。

步驟7基于P[k，lmax]預測錯交筆畫，將預測的錯交。筆畫的序號對偶有序存入SEC。

步驟8基于P[k，lmax]預測錯離筆畫，將預測的錯離筆畫的4 元結構有序存入SEL。

步驟9結束。

5 實驗及效果分析

實驗平臺主要硬件模塊包括7 英寸觸摸屏及S3C2440A，32bit ARM920T 內核及其控制器，標準配置64MB NAND_FLASH，標 準配置64MB SDRAM 等。軟件開發環境為VS2005，操作系統為wince 5.0，開發語言為C++。書寫區域是N×M=80×80 點陣。采用文獻[3]方法對筆跡信息進行前置處理。以漢字（L1）、英文（L2）、漢拼（L3）融合為例。三文種融合的要素元編碼空間信息結構如表1 構如表1 所示。

表1 中β、|β|、?、|?|、φ、|φ|分別為各要素元素集合與相應集合所含的元素數目，(L1，L2，L3)中(L1，L2，L3)表示參入組合的文種（其余類解），沒有參數的子集欄目表明該子集為空。取筆畫粒度m=2，即筆畫規模按長、短2 種狀態設置，g1+g2=69，取μ1=13，μ2=17，編碼空間為001～198；筆畫關系空間采用3_3 細分編碼，即e(s?)=2，b2=3，b3=3，B2，B3∈{0，1，2}g3=4，g4=5，取μ3=2，μ4=9，編碼空間為20000～21922；部件關系空 間 采 用3 區 位 細 分 編 碼，即e(p?)=1，b2=3，B2∈{0，1，2}，g5=2，g6=1，取μ5=2，μ6=5，編碼空間為3000x～3192x。圖3 所示為“體”、“E”字的書寫教學知識形態或模板結構及其D的生成內容。

對于模板“體”，寫完第1 條筆畫，筆跡點坐標數據被記錄于P[1]，筆畫識別模塊將該識別結果“008”存于Cstroke（筆畫碼）容器，并在圖3（a）界面的S子窗口顯示；第2 條寫完，筆跡數據放入P[2]，識別結果“006”放入前條筆畫編碼之后。依據P[1]、P[2]進行第2、1 條筆畫關系識別，該關系為T 字交關系，生存的編碼為“20311”，存于Crelation（關系碼）容器，并顯示于圖3（a）的R子窗口。第3 畫“短橫”與第2 畫“長豎”本系統無法確定兩者空間關系，在第2 畫之后插入部件分割標志代碼p，將兩者定制在兩個緊鄰部件中，并記錄該標志在Crelation 中序號。如此直至第7 條筆畫即該字的最后一條筆畫寫完，主導筆順的Cstroke生成結束，Crelation筆畫關系編碼生成完畢，但部件關系待進一步分析確定。“體”的書寫數據P[k，lmax]見表2 所示，其中k=7，lmax=42，xmax=63，xmin=19，ymax=62，ymin=24。

表1 三文種融合的要素元編碼空間

圖3 描述碼生成實例

表2 “體”字的P[k，lmax]

根據記錄的標注符在Crelation 中的序號，第1 輪按序進行由標注符分割的筆畫子集（部件）之間的關系識別。該文字只記錄了1 個標注符，且序號為2，即圖3（a）“體”在書寫過程中被定制為G1和G2兩個部件，G1?{P[1]，P[2]}，G2?{P[3]，P[4]，P[5]，P[6]，P[7]}。利用均質比較法識別G1、G2關系為居中左右關系，賦予30011 碼，該碼存于Crelation 容器，并顯示在圖3（a）的R子窗口。從P[3]開始進行錯交預測。端點筆段長度取5，延伸步長取2，延伸長度至文字最值邊線，預測結果存入Cerrorc（錯交碼）容器，并顯示在圖3（a）的SEC子窗口。從P[3]開始進行錯離預測，十字交取θ=0，點與筆畫T字交取θ=2，端點T 字取θ=5，預測結果存入Cerrorl（錯離碼）容器，并顯示在圖3（a）的SEL子窗口。

圖3（b）為英文大寫字母“E”的書寫模板及其D，該字存在一對預測錯交筆畫，無錯離結構。

對30 個英文字母，30 個漢語拼音字母，340 個漢字進行編碼實驗，正確率達到98.3%，錄入速率與人工編碼比較，效率提高15%，冗碼率如圖4 所示，字數越多，人工冗碼率越大，而自動編碼較平穩。

圖4 手動與自動生成描述字冗碼率對比

6 結束語

描述字自動生成是多文種融合的文字書寫教學系統關鍵技術之一。本文從文字書寫過程的角度給出適用于多文種融合的描述字結構，提出要素元編碼空間構建方法，設計并實現文字書寫過程描述字自動生成算法。描述字為教學知識點不可或缺內容，知識庫為獨立系統，其結構與功能不僅應便于描述字自動生成及知識運用，還應便于知識管理，如入出庫位置檢索、知識增減、知識調整、知識閱讀等。文獻[1]系統的教學知識來源于本文系統，即本文成果在文獻[1]系統中得到實用。多文種融合的文字書寫過程描述字自動生成方法的深化研究可借鑒文獻[12]等提供的多目標進化算法理論成果，各類關系識別方法的改進可參考文獻[13-15]等。

[1] 戴永，劉任任，王求真，等.可聯網交互的多功能規定格式習字系統及方法：中國，ZL201010149767.2[P].2010-09-01.

[2] 樊亮，戴永，覃冰梅.觸摸屏手寫漢字筆畫的筆力模糊評價[J].中文信息學報，2013，27（2）：91-97.

[3] 戴永，張維靜，孫廣武.基于文字書寫教學的筆跡噪聲處理[J].計算機工程與應用，2014，50（14）：164-167.

[4] 孫廣武，戴永，喻世東，等.音素關聯的多文種語音融合編碼方法[J].計算機工程與應用，2013，49（19）：217-221.

[5] 戴永，王心覺，張維靜，等.面向指導的自由式英文字母書寫跟蹤[J].湘潭大學自然科學學報，2012，34（2）：85-89.

[6] 李璇，戴永，王求真，等.字母連寫筆畫跟蹤方法[J/OL].計算機工程與應用.http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1310-0413.html.

[7] 王耀，戴永.規定格式文字書寫練習質量普適評價[J].計算機工程與應用，2010，46（29）：69-72.

[8] 王求真，戴永，樊亮，等.漢字書寫質量的模糊分析方法[J].計算機工程與應用，2013，49（21）：180-185.

[9] 彭喻杰，戴永.嵌入式習字教室系統[J/OL].計算機工程與應用.http://www.cnki.net/kcms/detail/11.2127TP.20150129.1119.022.html.

[10] Liu Chenglin，Jaeger S，Nakagawa M.Online recognition of Chinese characters：The state-of-the-art[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2004，26（2）：198-203.

[11] Tan C K.An algorithm for online strokes verification of Chinese characters using discrete features[C]//8th International Workshop on Frontiers in Handwriting Recgnition，Niagara-on-the-Lake，Ontario，Canada，2000：339-344.

[12] 鄭金華.多目標進化算法及其應用[M].北京：科學出版社，2007.

[13] Hu Zhihui，Xu Yun，Huang Liusheng，et al.A Chinese handwriting education system with automatic error detection[J].Journal of Software，2009，4（2）：101-107.

[14] Hammadi M，Bezine H，Njah S，et al.Towards an educational tool for Arabic handwriting learning[C]//International Conference on Education and e-Learning Innovations（ICEELI）.IEEE，2012，1（6）：1-6.

[15] Yamaguchi T，Muranaka N，Tokumaru M.Evalution of online handwritten characters for penmanship learning support system[C]//Proceedings of the 14th International Conference，HCI International 2011.Orlando，FL，USA：Human-Computer Interaction，2011：121-130.