聯(lián)機手寫識別在手機游戲中的應用研究

唐勝凱 孫彩虹

摘要：聯(lián)機手寫識別在手機游戲中的應用已有相關(guān)產(chǎn)品，其中一個成功案例是將手寫筆跡轉(zhuǎn)換為方向碼序列進行模式匹配，取相似度最高的模式作為識別結(jié)果。但是這種算法的健壯性差，對不規(guī)范的手寫筆跡識別率低，而且算法的效率可進一步優(yōu)化。針對這些缺陷，通過優(yōu)化手寫筆跡方向模型和編輯距離算法，提出了一種基于方向組的聯(lián)機手寫識別算法。通過對比實驗證明，改進后的算法有效提高了聯(lián)機手寫識別系統(tǒng)的健壯性和識別率，而且算法的運行效率更高。

關(guān)鍵詞：聯(lián)機手寫識別；手機游戲；健壯性；方向碼；方向碼序列

中圖分類號：TP391 文獻標識碼：A

文章編號：1009-3044（2019）13-0201-04

Applied Research of Online Handwriting Recognition in Mobile Game

TANG Sheng-kai，SUN Cai-hong

（School of information， Renmin University of China， Beijing 100872，China）

Abstract： Online handwriting recognition has been applied in mobile games， a successful case is to convert the handwriting into a direction code sequence for pattern matching. The highest mode is used as the recognition result. However， the robustness of this algorithm is poor， the handwriting recognition rate is low， and the performance of the algorithm can be further optimized. To make up for these defects， an online handwriting recognition algorithm based on direction group is proposed by optimizing handwriting direction model and editing distance algorithm. The comparison experiments show that the improved algorithm effectively improves the robustness and recognition rate of the online handwriting recognition system， and the performance of the algorithm is higher.

Key words：online handwriting recognition； mobile game； robustness； direction code； direction code sequence

1 引言

聯(lián)機手寫識別開始于1960年[2]，是模式識別的一個重要研究方向[3]。聯(lián)機手寫識別技術(shù)不僅在理論上有重要的研究意義，而且在實際中也有很重要的應用價值[4]。隨著半導體和計算機技術(shù)的發(fā)展以及模式識別領(lǐng)域理論和方法研究的不斷深入和完善，到20世紀80年代后期，聯(lián)機手寫識別技術(shù)的研究已經(jīng)朝著實用的方向努力，特別是英文，已經(jīng)開始研究完全無限制的整句識別技術(shù)[4]。

手機游戲中的很多符號都是根據(jù)游戲風格而設(shè)計的特殊符號，不能通過鍵盤輸入，只能通過手寫輸入。聯(lián)機手寫識別在手機游戲中的應用，國外已有Maigc Touch 等相關(guān)產(chǎn)品，但是國內(nèi)這方面的研究很少。其中一個成功案例[7]所采用的方法是把手寫筆跡細進行8方向編碼[5，6]得到方向碼序列[4]，通過計算其與字典中的方向碼序列的相似度，取相似度最高的符號作為識別結(jié)果。但是這種算法的健壯性差，時間復雜度和內(nèi)存占用都比較高。因此，對這種聯(lián)機手寫識別算法進行了一系列改進和優(yōu)化，提出了一種基于方向組的聯(lián)機手寫識別算法，使得改進后的算法具有更高的健壯性和識別率，算法復雜度更低，顯著提升了聯(lián)機手寫識別系統(tǒng)的性能，可有效改善用戶的實時交互體驗。

2 聯(lián)機手寫識別算法原理

聯(lián)機手寫識別原理如圖1所示，當用戶在觸摸屏上進行手寫時，系統(tǒng)以一定的頻率記錄筆跡信息，即一系列的坐標點，這些坐標點是離散的，并且相鄰兩點的連線是計算機所能分辨的最小線段，用8個方向碼分別標記每個線段所屬的方向，每個手寫筆跡都可以產(chǎn)生出一個方向碼序列[4]，通過計算其與字典中的方向碼序列的相似度，取相似度最高的作為識別結(jié)果。

2.1 方向碼

方向碼是表示手寫筆跡方向的數(shù)字或字母。把手寫筆跡轉(zhuǎn)換為方向碼序列的過程是，從頭至尾遍歷手寫筆跡的一系列坐標點，每次取相鄰的兩個坐標點，前面的點P1（x1， y1）稱為起點，后面的點P2（x2， y2）稱為終點，以起點P1為圓心，把觸摸屏劃分為八個圓心角相等的扇形，按順序依次編號為1， 2， 3， 4， 5， 6， 7， 8，終點P2落在哪個扇形，兩點連線的方向碼就是對應扇形的編號，如圖3所示。圖3中的角度是P1與P2的連線與觸摸屏水平線的夾角，可以看出每個方向的擺動范圍是45度。

先根據(jù)相鄰坐標點的相對位置，確定終點落在哪個象限，再根據(jù)兩點連線與水平線的夾角確定方向碼[7]，需要注意的是，觸摸屏坐標系的原點在左上角，而且Y軸方向是指向下的，具體算法如下：

算法1：確定手寫筆跡坐標點所在象限

以 P1 為原點，判斷 P2 所在象限 Q：

如果 x2 >= x1，則 P2 在第一、四象限：

如果 y2 <= y1 ，則 P2 在第一象限 Q = 1

否則P2 在第四象限Q = 4

否則 P2 在第二、三象限：

如果 y2 <= y1 ，則 P2 在第二象限 Q = 2

否則P2 在第三象限 Q = 3

算法2：將手寫筆跡坐標點轉(zhuǎn)換為方向碼

計算P1 與P2 的連線與水平線的夾角 θ

根據(jù)P2所在象限 Q 和 θ 判定P1 與P2 連線的方向碼 C

2.2 方向碼序列

預處理是聯(lián)機手寫識別的重要一環(huán)，分為兩步：第一步是對原始點坐標的濾波；第二步是對由這些點的坐標所計算出來的方向碼的濾波[5]。

由于手寫的隨意性，得到的一系列手寫筆跡坐標點不能直接用于方向碼轉(zhuǎn)換，需要先進行濾波，去除冗余和噪聲點，來消除因不同的手寫習慣對系統(tǒng)造成的影響。

對手寫筆跡坐標點進行編碼得到的方向碼序列中可能有相鄰的重復方向碼，例如：2，3，3，3，1，1。在進行模式匹配前，還需要去除方向碼序列中相鄰的重復方向碼，減少后續(xù)模式匹配的計算量。

在定義方向碼序列字典時，要考慮用戶的不同手寫習慣，比如有人喜歡正寫，有人喜歡反寫，即使同一個人每次下筆的方向也可能不同。用方向碼序列表示一個符號，可以很方便地支持不同的寫法，表1給出了幾種符號的方向碼序列定義實例：

2.3 方向碼序列相似度計算

決定聯(lián)機手寫識別系統(tǒng)性能的關(guān)鍵因素是模式匹配算法，其優(yōu)劣直接影響著最終的識別率高低。距離匹配是一種常用的模式匹配方法[9]，具體來說就是用采樣得到的手寫筆跡方向碼序列 test 與字典中的方向碼序列pattern[i]（i=1，2，…，n，n為字典容量）進行逐一匹配，計算test與pattern[i] 之間的距離 D（test， pattern[i]），再換算為相似度 similarity，取相似度最大的模式所對應的符號作為識別結(jié)果。相似度計算公式如下：

similarity = 1 – D（test， pattern[i]） / L

其中 L 表示方向碼序列的最大長度。

文獻[7]采用萊文斯坦距離度量方向碼序列之間的差異。萊文斯坦距離（Levenshtein Distance），又稱編輯距離，是由俄羅斯科學家弗拉基米爾·萊文斯坦（Vladimir Levenshtein）于1965年在文獻[11]中提出的算法，是一種常用的字符串編輯距離度量方法，在多個領(lǐng)域得到了廣泛應用。萊文斯坦距離[10]是指兩個字符串之間，由一個字符串轉(zhuǎn)換為另一個字符串所需的最少編輯操作次數(shù)，允許的編輯操作包括三種：將一個字符替換成另一個字符，插入一個字符，刪除一個字符。

算法3：萊文斯坦距離算法

m = test的長度

n = pattern 的長度

cost 整數(shù)，用于記錄編輯距離

D 矩陣，用于記錄中間計算的萊文斯坦距離

如果m == 0，則返回n并退出。

如果n == 0，則返回m并退出。

初始化萊文斯坦距離 D 矩陣的第一行和第一列：

for （i = 0； i < m； i++） D[i][0] = i；

for （j = 0； j < n； j++） D[0][j] = j；

for （i = 0； i < m； i++）

遍歷 test中的每個方向碼 test[i]

for （j = 0； j < n； j++）

遍歷 pattern中的每個方向碼 pattern[j]

如果 test[i] == pattern[j] 則編輯距離 cost = 0

否則編輯距離 cost = 1

插入一個字符的代價 c1 = D[i-1][j]+1

刪除一個字符的代價 c2 = D[i][j-1]+1

替換一個字符的代價c3 = D[i-1][j-1] + cost

D[i][j] = min（c1， c2， c3） 三種代價中取最小的

返回最終的萊文斯坦距離 d[n][m]

3 改進聯(lián)機手寫識別算法

這種基于方向碼的方案能有效利用手寫筆跡的特征，能很好地滿足手寫輸入的實時性要求。通過多組實驗發(fā)現(xiàn)，這種算法對于規(guī)范的手寫筆跡識別率較高。但是對于不規(guī)范的手寫筆跡，這種算法的識別率就很低了。用戶的自然輸入往往比較隨意，強制所有用戶進行規(guī)范輸入是不現(xiàn)實的。所以聯(lián)機手寫識別系統(tǒng)要達到比較理想的應用水平，必須對核心算法進行改進，增強其健壯性也就是抗干擾能力，這是聯(lián)機手寫識別技術(shù)的難點。

在計算方向碼序列的萊文斯坦距離時，算法的時間復雜度和空間復雜度都是 O（m*n），通過對算法的分析和測試，發(fā)現(xiàn)算法的時間效率和空間效率都可以進一步優(yōu)化。

3.1 健壯性優(yōu)化

通過對以上算法的測試和分析，可以發(fā)現(xiàn)用8個方向表示手寫筆跡太粗略，尤其是對弧線較多的符號，算法的健壯性較差。針對這些缺陷，下文提出了一種基于方向碼組的聯(lián)機手寫識別算法，用方向碼組來定義符號的方向碼序列模式。計算萊文斯坦距離時，根據(jù)方向碼在方向碼組中的位置，來確定編輯距離大小，從而使得計算結(jié)果更符合手寫筆跡的實際情況，有效提高了聯(lián)機手寫識別系統(tǒng)的健壯性和識別率。

3.1.1 方向碼細化

文獻[1]把筆跡方向特征從4個方向延伸到8個方向，識別率得到很大程度的提高。這里把筆跡方向特征從8個方向細化為16個方向，方向碼依次為：0，1，…9，a，…，f 共 16 個字符，如圖4所示：

細化后的單個方向擺動范圍從 45o 縮小到了 22.5o，但是下面定義的方向碼組可以讓擺動范圍擴大到67.5 o，可有效處理不規(guī)范的手寫筆跡。

3.1.2 帶權(quán)重的方向碼組

每個方向碼組由一個主方向和2～4個輔方向組成，共3～5個方向碼，例如：'9a8'，其中‘9是主方向碼，排在第一位，‘a(chǎn)和‘8是輔方向碼，排在后面，輔方向碼的順序可以顛倒，也就是說‘9a8和‘98a是同一個方向碼組。

對方向碼組中的權(quán)重分配如下：主方向的權(quán)重是1.0，輔方向的權(quán)重都是0.8。例如，如果手寫筆跡的方向碼是9，則其與方向碼組‘9a8的相似度是1.0，如果手寫筆跡的方向碼是8或a，則其與方向碼組‘9a8的相似度是0.8。

3.1.3 方向碼序列模式優(yōu)化

在定義手寫筆跡的方向碼序列字典時，采用方向碼組作為一個基本單位，表2給出了幾種符號的方向碼組序列定義實例：

3.2 方向碼序列相似度算法優(yōu)化

單純的字符串可以通過替換、插入、刪除等三種基本操作轉(zhuǎn)換為另一個字符串，萊文斯坦距離所要計算的是字符串編輯距離中的最小距離，所以在計算過程中，遇到對應位置字符不同時，不能只考慮字符替換而一直進行編輯距離的累加，還要考慮插入字符和刪除字符的情況，取編輯距離最小的操作。

但是，手寫筆跡的每一段都是首尾銜接的，不能隨意刪除方向碼或插入方向碼，所以在計算萊文斯坦距離時，遇到對應位置方向碼不同時，只處理當前方向碼即可，不用考慮插入方向碼和刪除方向碼的情況，這樣得到的計算結(jié)果更符合實際情況。

因此，從方向碼序列的這個特點入手，對萊文斯坦距離的計算過程進行優(yōu)化，不再進行嵌套循環(huán)，而是一遍通過。具體來說，就是先遍歷手寫筆跡的方向碼序列，遍歷結(jié)束后，如果系統(tǒng)定義的方向碼序列模式還沒到最后，則繼續(xù)檢查其余的方向碼組，直到最后。改進后的算法，時間復雜度降為 O（max（m， n））。

由于新算法不需要記錄中間計算結(jié)果，可以對原算法的數(shù)據(jù)結(jié)構(gòu)進行優(yōu)化，去掉二維數(shù)組，改用一個數(shù)值變量保存計算結(jié)果即可。改進后的算法，空間復雜度降為 O（1）。

經(jīng)測試，新算法的計算結(jié)果比原算法更符合實際，健壯性顯著提高，而且時間復雜度和空間復雜度都減少了很多。

設(shè)m為手寫筆跡方向碼序列 test 的長度，n為系統(tǒng)定義的方向碼序列模式 pattern 的長度，那么優(yōu)化之后的萊文斯坦距離算法如下：

算法4：優(yōu)化之后的萊文斯坦距離算法

方向組長度 groupLength = 3

如果m == 0，則返回n并退出。

如果n == 0，則返回m并退出。

初始化萊文斯坦距離 cost = 0

start = 0 用于pattern子串起始索引

for （i = 0； i < m； i++） 遍歷 test 中的每個方向碼

方向碼組 group = pattern 的子串 （start， start + groupLength）

如果 test[i] 不在 group 中：

如果 pattern 還有下一組，且 i > 0：

則切換到 pattern 下一組 start = start + groupLength

i = i -1 再次檢查 test 當前方向碼

否則 pattern 到尾部或 test[0] 不在方向碼組中：

開頭不對或結(jié)尾不對，直接扣分 cost + 1

否則 test[i] 在 group 中：

如果 test[i] 是 group 的第一個元素，則不扣分

否則 test[i] 是輔方向，要分情況處理：

如果 pattern 還有下一組，則 cost + 0.2

否則 pattern 到最后了，對 test 多余的輔方向不再扣分

若 pattern 還沒到最后，則取下一組，直到最后

如果 test 最后一個方向碼在 group 中，則不扣分。

否則直接扣分 cost = cost + 1

3.3 根據(jù)手機游戲的特點進一步優(yōu)化算法

與漢字識別不同的是，手機游戲符號識別不用匹配字典中所有的符號，只匹配顯示中的符號即可，這樣可以進一步降低算法的復雜度，而且可以解決相似度高的符號問題。設(shè)計字典時，如果兩個符號相似度很高，則歸并到一個組，在抽取符號時，如果某個組的符號在顯示中，則取其他組中的符號，使得顯示中的符號彼此相似度很低。

4 實驗測試和結(jié)果分析

4.1 實驗設(shè)計

開發(fā)環(huán)境是Windows 7操作系統(tǒng)白鷺引擎5.2.6，實現(xiàn)了一個手機游戲，用于比較新算法和原算法的健壯性和識別率，實驗環(huán)境是安卓手機，如圖5所示：

游戲開始后會從屏幕下方冒出氣球，氣球上有待匹配的符號，用戶在觸摸屏上手寫符號，如果匹配成功，則氣球消失得分+1，否則氣球飛走生命-1，直到生命為0或達到樣本容量上限游戲結(jié)束。

4.2 實驗結(jié)果分析

采用對比實驗分別測試原算法和新算法，分析二者的差異，進而得出實驗結(jié)論。實驗要收集的數(shù)據(jù)包括手寫筆跡的規(guī)范性、識別率等，把20種符號從簡單到復雜分成5組分別進行實驗，每組實驗隨機抽取100個樣本，每個樣本只手寫一次（正向書寫或反向書寫，反向書寫也可以很規(guī)范，所以不再單獨做反向書寫實驗），相似度閾值取0.6，即相似度大于60%才認為匹配成功，得到的實驗數(shù)據(jù)如表3和表4所示：

從表3和表4可以看出，新算法對規(guī)范度高的手寫筆跡具有更高的識別率，對規(guī)范度低的筆跡識別率也在93%以上。

4.3 實驗結(jié)論

通過對比實驗與分析，可以證明新算法的健壯性和識別率都得到了顯著提高，克服了原算法健壯性差、識別率低、內(nèi)存占用高、時間復雜度高的缺陷，使聯(lián)機手寫識別系統(tǒng)的性能得到有效提升，更符合智能手機應用的運行要求。

5 總結(jié)與展望

基于方向組和改進編輯距離的聯(lián)機手寫識別算法，細化了手寫筆跡方向模型，定義了帶權(quán)重的方向碼組，優(yōu)化了方向碼序列相似度計算過程。通過多組實驗證明，這種新算法健壯性強、識別率高，而且時間復雜度和內(nèi)存占用更低。

l 對于沒有明顯的開頭和結(jié)尾的符號不能很好地定義，例如：☆，∞，O等，從任意一點開始手寫都行，需要支持所有方向開頭的方向碼序列，考慮正反方向和不規(guī)范寫法，則需要定義的方向碼序列太多。

l 沒有利用筆段的長度信息。

聯(lián)機手寫識別不僅具有廣闊的應用前景，而且還有重要的理論價值[8]。研究手寫識別可以幫助認識高難度模式識別的一般規(guī)律，發(fā)展新的模式識別理論。由于手寫識別問題的復雜性和多重性，其在許多學科的研究中具有很高的理論探索價值和啟發(fā)創(chuàng)造作用；激發(fā)了大量新思想和新方法，促進了相關(guān)學科的深入發(fā)展。在信息技術(shù)日新月異的21世紀，越來越智能、越來越人性化的信息設(shè)備正逐步走入人們的日常生活，聯(lián)機手寫識別技術(shù)一定會得到進一步的發(fā)展和普及。

參考文獻：

[1] Z.L. Bai， Q. Huo， A Study on the Use of 8-Directional Features for Online Handwritten Chinese Character Recognition [C]， in Proc. IEEE ICDAR ，2005（1）：262-266.

[2] 白真龍，霍強. 在聯(lián)機手寫中文識別中一種針對8方向特征提取的改進算法[C]. 中文信息處理前沿進展——中國中文信息學會二十五周年學術(shù)會議，2006：484-492.

[3] 鄒明福，鈕興昱. 聯(lián)機手寫英文識別[J].計算機研究與發(fā)展，2006.43（1）：138-144.

[4] 樊慶林. 基于筆畫的聯(lián)機手寫漢字識別系統(tǒng)的研究與實現(xiàn)[D].安徽大學，2007.

[5] 劉光澤. 聯(lián)機手寫漢字識別的設(shè)計與實現(xiàn)[D].中國民航大學，2011.

[6] 索南尖措，關(guān)白，李雷，等.藏文聯(lián)機手寫識別的研究與實現(xiàn)[J].計算機時代，2017（7） ：10-12.

[7] A閃. 仿Magic Touch中的手寫識別算法[EB/OL]. https：//ashan.org/archives/685. 2016-02-05.

[8] 羅巧玲. 聯(lián)機手寫漢字識別關(guān)鍵技術(shù)研究[D].華中科技大學，2009.

[9] 呂新橋. 聯(lián)機手寫漢字識別技術(shù)研究[D].華中科技大學，2009.

[10] 陳正銘，霍英.編輯距離算法在中文文本相似度計算中的優(yōu)化與實現(xiàn)[J].韶關(guān)學院學報，2015（12）.

[11] Levenshtein V I. Binary Codes Capable of Correcting Spurious Insertions and Deletions of Ones[J]. Problems of Information Transmission， 1965， 1（1）： 8-17.

【通聯(lián)編輯：唐一東】