字母連寫筆畫跟蹤方法

李 璇，戴 永，王求真，喻世東，任 昆

LI Xuan,DAI Yong,WANG Qiuzhen,YU Shidong,REN Kun

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

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

1 引言

字母串寫成詞的文種，字母連寫有其可循規(guī)則，也是此類文種書寫學習的重要內容。實現(xiàn)字母連寫的智能輔導需克服的難點主要有：（1）連寫字母越多書寫難度越大，書寫指導的難度也越大；（2）單體字母筆跡越復雜導致連寫筆畫的筆跡越復雜；（3）連寫字母越多連寫筆畫越長導致筆跡的筆段數(shù)目增加，筆段形狀多樣化等。欲實現(xiàn)字母連寫智能輔導，連寫筆畫的跟蹤是關鍵。關于筆跡結構與跟蹤的研究，目前主要局限于單體文字及阿拉伯數(shù)字。如從局部特征著手跟蹤書寫筆跡[1-4]；建立面向書寫指導的大小寫英文字母筆畫與筆畫關系分析[5]；基于二次曲線的手繪圖識別方法[6]及通過分析筆跡遠點在手寫模式之間的關系的全局在線字符識別方法[7-9]等。毋容置疑，此類已有方法難以直接用于字母連寫筆畫筆跡曲線的跟蹤與識別。雖然連寫筆畫的總體結構無法比擬于任何范類曲線，但可分解為堪比范類曲線的筆段。從這一認識出發(fā)，本文提出基于圖域、時域筆跡關鍵點分割筆段并獲取筆段擬合范類曲線系數(shù)模板，利用系數(shù)模板實現(xiàn)跟蹤字母連寫筆畫的方法。從圖域提取起止點與閉環(huán)式交點鏈向量，從時域提取xy方向極點、正弦π點向量，由此構造兩域綜合關鍵點向量，通過該向量分割連寫筆畫形成有序的范類曲線的筆段模板。范類曲線設定為二次曲線、正弦曲線、直線三大類。模板筆段經最小二乘法獲取最佳擬合曲線的系數(shù)向量，而實寫筆段關鍵點直接與系數(shù)向量重構的擬合曲線進行貼近度分析。實驗文種為英文，文字連寫的實驗結構由文獻[10]提供，實驗對象為二字母連寫。實驗表明，該方法具有關鍵點計算可靠、筆段分割規(guī)模到位且形狀規(guī)范、擬合分析效果穩(wěn)定等優(yōu)點。該方法不難推廣到多于二字母連寫的連寫筆畫的跟蹤，為實現(xiàn)字母連寫智能教學提供了實用的連寫筆畫跟蹤技術基礎。

2 連寫筆畫結構分析

以文獻[7]提供的二連字母為研究對象，字母e 結尾的稱為第一類連寫，字母a/d/i/k/u、o/w/v等為領頭字母的分別稱為第二、第三類連寫，字母f/t 結尾的為第四類連寫。表1 列舉了前三類連寫結構中具有代表性的實際連寫類，第四類連寫筆畫只是與f/t連寫的其他字母起筆或終筆的橫向延長，筆畫較為簡單，本文不做具體分析。

表1 字母連寫結構分類

圖1（a）為“de”連寫的筆跡采樣圖；書寫過程如圖1（b）所示，筆跡以A為起點，沿箭頭方向行筆，以E為終點結束書寫；圖1（c）、（d）分別表示該筆畫x、y方向的時域走向圖。筆畫完整結構為非標準曲線，無法直接進行完整的筆跡跟蹤。比照范類曲線，該連寫筆畫可有序分割成五段范類曲線筆段，分別近似為橢圓筆段（A→B段）、直線筆段（B→Bx段）、拋物線筆段（Bx→C段）、橢圓筆段（C→D段）及拋物線筆段（D→E段）。

圖1 各類關鍵點的幾何構圖

綜合分析二連字母筆畫的結構特性，按筆段的擬似形狀及其數(shù)學模型結構將筆段歸納為二次曲線（包括橢圓類、橢圓弧類、拋物線等）、正弦曲線類和直線類等三大類，相關連寫字母示例如表2 所示，類別模糊的筆段提供多種擬合模板。

3 跟蹤模板構建

跟蹤模板為系數(shù)向量表達的筆段擬合曲線。

3.1 關鍵點向量生成

文字書寫圖域坐標以書寫格左上角為原點，向右為x軸正方向，向下為y軸正方向。實時采集圖域的筆跡點信息得到筆畫的圖域二維坐標序列向量，將圖域二維坐標序列向量進行時域分解得到分別以x、y為縱坐標的時域坐標序列向量。通過圖域、時域分析建立綜合的筆跡關鍵點描述向量來跟蹤分析實寫筆畫。

表2 特征筆段分類表

基于任意連寫字母串有且僅有一條連寫筆畫的基本事實，以下討論對象只針對連寫筆畫。圖域二維筆跡產生的關鍵點向量記為PG，時域單維筆跡產生的關鍵點點集記為PT；由PG、PT綜合生成的關鍵點向量記為PK。

3.1.1PG及其生成

嵌入式系統(tǒng)μOS按固定的時間間隔T對當前觸摸筆所在的位置進行坐標采集，用P表示由此得到具有時間順序的圖域二維坐標向量，P=[p0,p1,…,pn]=[(x0,y0),(x1,y1),…,(xn,yn)]。由向量P獲得的關鍵點向量記為PG=[ps,pe,pd]，每個關鍵點由四元結構表示，前兩元為圖域坐標，第三元為關鍵點在向量P中的時序碼，用C表示，第四元為關鍵點屬性碼，用S表示。

ps為連筆筆畫起點，ps=(xst,yst,Cst,Sst)；pe為連筆筆畫終點，pe=(xed,yed,Ced,Sed)；pd為連筆筆畫閉環(huán)式交點鏈，pd=[pd1,pd2,…,pdn0]，其中pdi=[(xdi1,ydi1,Cdi1,Sdi),(xdi2,ydi2,Cdi2,Sdi)](i∈{1,2,…,n0})，滿足條件|xdi1-xdi2|＜δ，|ydi1-ydi2|＜δ，Cdi1≠Cdi2，δ為閾值。例圖1（b）中A、B構成閉環(huán)式交點鏈pd的第一節(jié)點，C、D構成第二節(jié)點。

3.1.2PT及其生成

為實現(xiàn)字母連寫，不可避免會出現(xiàn)筆跡重疊或方向多變現(xiàn)象，如圖1（b）中“Bx→B”的筆段與“A→Bx”的筆段出現(xiàn)了大量重疊筆跡點，若只限于提取圖域關鍵點，關鍵點的屬性分析難度將增大，同時因可提取的關鍵點數(shù)量偏會將導致筆段分割不精準與形態(tài)識別的正確率下降，對此引入筆跡時域分解圖及相應的時域向量。分解向量P得時域向量,(x1,C1),…,(xn,Cn)]，,(y1,C1),…,(yn,Cn)]。通過對Px、Py的分析獲得筆畫單向單調性變化狀態(tài)、單向極值點信息。由Px、Py獲得的關鍵點向量記為Pt=[pxbt,pxpp,pxsz,pybt,pypp,pysz]。每個關鍵點元素為三元描述結構，第一元為x或y坐標信息，第二元為時序碼C，第三元為屬性碼S。

pxbt為筆畫在x方向的極大值點序列子向量，pxbt=，其 中，其余類同；pxpp為筆畫在x方向的極小值點序列子向量，為筆畫在x方向的正弦π 點子向量，；pybt、pypp為筆畫在y方向的極大、極小值點序列子向量，,為筆畫在y方向的正弦π 點子向量，。

極點運用單調法生成。正弦π 點生成方法：采用單調法獲得筆畫單調標注向量，若存在某筆段的單調標注向量滿足x、y方向單調性均保持不變，則過該筆段的兩端點求一條直線；若該直線與該筆段有且只有一個交點，則視該交點為筆畫x方向的正弦π 點，存入pxsz。

為方便后續(xù)處理使Pt與PG同維，將Pt中每個關鍵點子向量各自增加在時域中缺省的坐標元，相應的向量記為PT，PT=[pxb,pxp,pxz,pyb,pyp,pyz]，pxb,pxp,pxz,pyb,pyp,pyz依次對應pxbt,pxpp,pxsz,pybt,pypp,pysz。

3.1.3PK及其生成

按時序碼C由小到大綜合PG、PT得到綜合關鍵點向量PK=[pk(xi,yi,Ci,Si),(i=0,1,…,m)]。

算法1PK生成

輸入：P

輸出：PK，關鍵點跟蹤意見由Guidance析出

注釋：Dx[]、Dy[]分別為x、y方向的單調標注向量；Pt[]將時域關鍵點按類型及出現(xiàn)順序進行存儲；N[]統(tǒng)計除起止點外各類關鍵點的數(shù)目。σ(i)表示交點、極點及正弦π 點的關鍵點數(shù)目閾值；ηx、ηy表示x、y方向單調性變化的閾值向量集，以上閾值域為經驗求取。

3.2 筆段提取

筆段提取是指在PK中確定可提取筆段的起點與終點，一條被提取的筆段包含σ(σ≥2)個關鍵點。為了將無規(guī)則的連寫筆畫切分成易擬合的范類曲線筆段，PK以表2 所示曲線為類別，按“橢圓→正弦→橢圓弧→拋物線→直線”順序對PK所包含的曲線筆段進行提取。

算法2筆段提取

輸入：PK

輸出：筆段關鍵點子向量Vcut

注釋：Vcutcode[]儲存被提取筆段擬合類型碼，code(m)表示筆段擬合類型碼；Vcut[]存儲提取筆段子向量。函數(shù)PkRedistribution()、ConicPutIn()、SinusoidalPutIn()、LinePutIn()分別實現(xiàn)關鍵點重組，二次曲線，正弦曲線，直線擬合筆段提取功能。

3.3 筆段曲線擬合

將模板筆畫提取的筆段進行范類曲線擬合選取最佳擬合系數(shù)向量，該系數(shù)向量生成的擬合曲線即為跟蹤模板。當待擬合筆段所含關鍵點數(shù)大于或等于擬合所需方程數(shù)，直接代入關鍵點進行擬合，否則，以時序碼C差距最大為判斷依據，采用二分法在時距最遠的兩關鍵點間插入一輔析點（輔析點從向量P中提取），直到關鍵點數(shù)目足夠進行筆段擬合。記待擬合筆段中新的關鍵點向量為PKl，包含的關鍵點數(shù)為σl個。

（1）平面上二次曲線的一般方程為q=ax2+bxy+cy2+dx+ey+f=0，由最小二乘法迭代規(guī)則知擬合關鍵點數(shù)。利用最小二乘法獲得最佳擬合系數(shù)向量及相應的決定系數(shù)。

（2）平面上正弦曲線的一般方程為y=Acos(ωx)+Bsin(ωx)+C，其中ω=2πT，周期T=|Pa.x-Pb.x|由待擬合理想筆段中與拐點相鄰的極大極小值點x坐標確定，擬合關鍵點數(shù)。經最小二乘法擬合獲得最佳系數(shù)向量及相應的決定系數(shù)。

（3）平面上直線的一般方程為y=kx+l，擬合關鍵點數(shù)。經最小二乘法擬合獲得最佳系數(shù)向量及相應的決定系數(shù)。

4 跟蹤實現(xiàn)

實寫筆畫跟蹤過程為：求取實寫筆畫關鍵點并提取筆段關鍵點子向量，在提取筆段類型與模板筆段類型一致的條件下，將筆段關鍵點與對應最佳擬合系數(shù)向量還原的范類曲線進行貼近度分析。

由于書寫者實寫筆跡位置不會與模板筆跡位置完全一致，在計算決定系數(shù)前需先求得實寫筆跡中待分析筆段坐標中心，并平移至模板筆段坐標中心位置。實寫筆段筆跡點為p(xi,yi)，則，其中為模板筆跡點對應筆段x方向及y方向的坐標中心。

采用決定系數(shù)R對實寫筆段關鍵點與模板筆段的擬合曲線進行貼近度分析，有：

其中Qi表示實寫筆段坐標值，表示由對應系數(shù)向量還原的筆段擬合曲線的估計值，表示實寫筆段坐標平均值。根據實驗經驗對實寫筆跡與模板筆跡決定系數(shù)的差值進行閾值設定，并由決定系數(shù)R的閾值劃分獲得擬合貼近度的評價標準，見表3。

表3 的評價標準

表3 的評價標準

|R--R|rf≤0.01 1 0.01～0.03 0.9 0.03～0.05 0.8 0.05～0.10 0.7 0.10～0.20 0.6≥0.20 0

對于具有n條擬合筆段的筆畫，設為其第i條擬合筆段的書寫質量，wi(i=1,2,…,n)為基于筆段筆跡點數(shù)的權值，由于通常情況下長筆段書寫比短筆段書寫出現(xiàn)的書寫質量不佳現(xiàn)象要多，設l為參與曲線擬合的總筆跡點數(shù)，li為第i條筆段的筆跡點數(shù)，有。。系統(tǒng)則該實寫筆畫最終擬合貼近度為對擬合質量進行評價，根據評價等級向書寫者提供指導意見。

表4 實寫“he”連寫字母的原始筆跡點數(shù)據及關鍵點數(shù)據

5 實驗及效果分析

實驗平臺主硬件模塊包括7 in觸摸屏及S3C2440A，32 bit ARM920T 內核及其控制器，標準配置64 MB NAND_FLASH，標準配置64 MB SDRAM 等。軟件開發(fā)環(huán)境為VS2005，操作系統(tǒng)為WinCE 5.0，開發(fā)語言為C++，輔助開發(fā)語言為MATLAB。以四線格字格為例，書寫區(qū)域為N×M=80×80 點陣。

以“he”連寫為例，其模板的各筆段擬合系數(shù)向量分別為：

（1）橢圓擬合參數(shù)D=[0.637 8 0.673 2 0.374 1-83.11,-57.85 2939]，標準筆段擬合貼近度；

（2）正弦曲線擬合參數(shù)E=[-14.61 3.6 39.83 0.251 5]，標準筆段擬合貼近度；

（3）拋物線擬合參數(shù)D=[-0.564 8 0 0 -53.69 -5.182 1 015]，標準筆段擬合貼近度；

（4）直線擬合參數(shù)F=[-25.09 450.86]，標準筆段擬合貼近度。

圖2（a）為取自一位初二學生在本指導系統(tǒng)實際書寫“he”的截圖；圖2（b）為其點跡圖，筆跡數(shù)據見表5 中P欄，橫向兩兩表示一筆跡點的x、y坐標，PG從點跡圖中提取，共4 個點；圖2（c）、2（d）分別為筆跡x、y方向的時域圖，Pt由時域圖筆跡點生成，PT對應Pt中的關鍵點，共8 個點；圖2（e）為筆跡實際分割結果，圖中被標注的點為筆段分割點。各類關鍵點數(shù)據見表4 相應欄目，PKl欄中下劃線標注點為插入的輔析點。

采用MATELAB 求取書寫例字中模板筆畫筆段的曲線擬合系數(shù)向量，并采用計算決定系數(shù)R 的方式判斷擬合貼近度的優(yōu)劣?！癶e”連寫筆點被順序分割為橢圓，正弦曲線，拋物線和直線筆段。

圖2 實驗結果分析

實寫筆畫的筆段l1筆跡點數(shù)29，關鍵點數(shù)，與擬合曲線的貼近度為：1 - {[(46-44.93)2+ (39-39.51)2+ (30-30.02)2+ (27-26.56)2+(32-32.73)2+(42-41.97)2+(45-44.93)2]/[(46-37.29)2+(39-37.29)2+(30-37.29)2+(27-37.29)2+(32-37.29)2+(42-37.29)2+(45-37.29)2]}= 1-2.133/347.4 =0.993 9；同理有筆段l2筆跡點數(shù)33，，R2=0.932 3；筆段l3筆跡點數(shù)12，，R2=0.946 2；筆段l4筆跡點數(shù)27，，R2=0.996 0。

由此得該筆畫與標準筆畫的擬合貼近度為：rf=1×29 100+0.9×33 100+0.9×12 100+1×27 100=0.965，即該單筆畫連寫字母書寫的擬合貼近度為0.965。

圖3 給出多位同學在本指導系統(tǒng)實際書寫結果的典型截圖，圖（a）、（d）為第二類連寫例字，圖（b）、（c）為第三類連寫例字。其中圖3（b）、（c）的書寫有誤，經系統(tǒng)分析給出了指導意見，圖3（a）和3（d）給出了筆畫綜合得分。

圖3 學生實際書寫截圖

實驗分析見表5。每類實驗字母串結構由不同用戶書寫50 次。實驗數(shù)據表明，系統(tǒng)實時跟蹤時間、關鍵點誤提率等重要指標滿足實用要求。

表5 實驗效果分析

6 結束語

長期以來文字書寫教學系統(tǒng)的服務內容主要是單體文字書寫教學，隨著人們對文字書寫教學系統(tǒng)的功能的期望越來越高，字母連寫智能指導成為現(xiàn)今文字書寫指導系統(tǒng)所面臨的一項發(fā)展功能[11-12]。本文以英文字母連寫為例，研究了作為連寫字母的核心筆畫，即連寫筆畫的跟蹤方法，包括連寫筆畫的兩域關鍵點獲取、規(guī)范筆段分割、筆段形態(tài)擬合分析及跟蹤實驗等，為實現(xiàn)英文字母連寫智能指導功能提供了技術基礎，同時也可借鑒于其他可字母連寫的文種實現(xiàn)字母連寫智能指導。從系統(tǒng)的研究發(fā)展角度看，筆段曲線擬合可進一步應用動態(tài)規(guī)劃等先進理論[13-15]。

[1] Bahlmann C.Directional feature in online hand-writing recognition[J].Pattern Recognition，2006，39（1）：115-125.

[2] Bezine H，Alimi M，Derbel N，Handwriting trajectory movements controlled by a beta elliptic model[C]//Proceedings of International Conference on Document Analysis and Recognition，2003：1228-1232.

[3] Kherallah M，Haddad L，Alimi A，et al.On-line handwritten digit recognition based on trajectory and velocity modeling[J].Pattern Recognition Lett，2008，29：580-594.

[4] Plamondon J，Sargur N.On-line and off-Line handwriting recognition：A comprehensive survey[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（1）.

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

[6] 王淑俠，高滿屯，齊樂華.基于二次曲線的在線手繪圖識別[J].西北工業(yè)大學學報，2007（1）：37-41.

[7] Minoru M，Seiichi U，Hitoshi S.Global feature for online character recognition[J].Pattern Recognition Lett，2014，35（1）：142-148.

[8] Tappert C C，Suen C Y，Wakahara T.The state of the art in on-line handwriting recognition[J].IEEE Transactions Pattern Analysis and Machine Intelligence，1990，12（8）：787-808.

[9] Zadeh L A.Fuzzy logic=computing with words[J].IEEE Transactions on Fuzzy Systems，1996，4（2）：103-111.

[10] 龍恒充.英語手寫體鋼筆字帖·連寫訓練[M].成都：四川出版集團·天地出版社，2009.

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

[12] Lam H C，Ki W W，Law N，et al.Designing CALL for learning characaters[J].Journal of Computer Assisted Learning，2001，17（1）：115-128.

[13] 李蔚，黃云清.Lagrange 三角形單位分解有限元法的最優(yōu)誤差分析[J].湘潭大學自然科學學報，2012（2）：1-6.

[14] 黃永麗，朱會東，朱付保.一種基于三維虛擬爬行角色的路徑規(guī)劃技術[J].湘潭大學自然科學學報，2012（2）：122-126.

[15] 黃青群，朱志斌，盧鈺松.一般非線性規(guī)劃的組合同倫牛頓法[J].湘潭大學自然科學學報，2013（1）：21-24.