基于遺傳算法的漢字書寫水平評估算法研究

陳 潔,王 強,杜 嶸

(江蘇金盾檢測技術(shù)股份有限公司,江蘇 南京 210042)

0 引言

我國中小學(xué)生教育高度重視漢字書寫,2022 年教育部印發(fā)義務(wù)教育語文課程新標準,依據(jù)該標準,在三至六年級語文課程學(xué)習(xí)中,每周應(yīng)至少安排1 課時書法課,并且中小學(xué)生都需要掌握毛筆楷書[1]。 由于漢字的字形數(shù)量繁多、結(jié)構(gòu)復(fù)雜、書寫有規(guī)律、形體差異度高等特點,目前對中小學(xué)生漢字書寫水平的評估主要依靠教師人工評估。 人工評估方式較大地增加了語文教師的工作量,在確保評估質(zhì)量的前提下,批閱速度很難大幅提升。 因此,目前有較多的研究嘗試采用計算機算法評估漢字書寫水平,采用的方法主要集中在機器學(xué)習(xí)和人工智能領(lǐng)域,比較典型的有以下3 類。

第一類:將書寫過程視為筆跡的移動過程,提取動態(tài)信息[2-3],通過與標準字的動態(tài)信息與筆畫粗細分析和對比實現(xiàn)評估。 由于書寫的動態(tài)信息獲取需要使用電子設(shè)備,此類方法又稱為聯(lián)機評估。

第二類:基于機器學(xué)習(xí)的方法,如深度學(xué)習(xí)[4]、SVM 分類的方法[5],嘗試通過特征學(xué)習(xí),將被評估的字歸類成優(yōu)、良、中、差4 個級別實現(xiàn)評估。

第三類:通過書寫字的骨架和輪廓實現(xiàn)評估[6],基于待評估字與標準字的骨架差異度實現(xiàn)分析,給出評估結(jié)果。

第二、三類方法由于不需要使用電子設(shè)備提取動態(tài)信息,又稱為脫機評估。 從上述的各類方法可以看出,第一類聯(lián)機評估方法需要使用專用電子采集設(shè)備,不便于在日常學(xué)習(xí)環(huán)境中應(yīng)用推廣,而第二類方法需要大量的訓(xùn)練數(shù)據(jù)集以及復(fù)雜的神經(jīng)網(wǎng)絡(luò)架構(gòu),存在訓(xùn)練難度大、周期長且難以提供書寫問題分析等不足。

綜合分析第一、二類方法的不足,本文討論的算法采用的是第三類方法。 中小學(xué)生書寫多為硬筆書寫的正楷,筆畫粗細與書寫水平評估結(jié)果關(guān)聯(lián)度不高,實現(xiàn)書寫水平判斷的關(guān)鍵在于字的骨架和輪廓。由于漢字結(jié)構(gòu)的復(fù)雜性和書寫過程的隨機性,通過圖像提取漢字的骨架和輪廓比較困難。 因此,本文所提的方法將待評估漢字的筆畫交叉點作為書寫水平的評估特征,通過分析待評估漢字的筆畫交叉點與標準字筆畫交叉點的偏移程度實現(xiàn)對書寫水平的評估。本文方法的優(yōu)點在于不需要大量的訓(xùn)練數(shù)據(jù)與復(fù)雜的訓(xùn)練過程就可以實現(xiàn)對書寫水平的評估,而且可以根據(jù)評估字不同部位的交叉點偏移度分析出書寫者的書寫問題。

1 關(guān)鍵點配準與遺傳算法

1.1 關(guān)鍵點配準

關(guān)鍵點配準是指找到兩幅圖片上的關(guān)鍵點序列的對應(yīng)關(guān)系,即:存在P1、P2兩張圖片,其中(x1,x2,…, xn)∈P1,(y1, y2,…, yn)∈P2, 找到點集X與點集Y 的對應(yīng)關(guān)系如式(1)所示:

其中:f()是點x 與點y 的配對評估函數(shù),根據(jù)配對的應(yīng)用目標不同有不同的評估函數(shù)。 關(guān)鍵點配準算法一般要求在完成點配對之后,各點對評估函數(shù)值的總和最小。

關(guān)鍵點配準算法的應(yīng)用范圍很廣,指紋識別是其最為經(jīng)典的應(yīng)用[7],除此之外,還有醫(yī)學(xué)圖像配準、點云配準等[8-9]。 這些應(yīng)用場景下將關(guān)鍵點配準算法視為矩陣的變換,因為類似指紋、點云的應(yīng)用場景下,兩張圖片相對應(yīng)的點在各自所在的點集中相對空間位置變化不是很大,可以視為點集矩陣的剛性變換,如:點集的平移與旋轉(zhuǎn)來實現(xiàn)配準。 但是,在本文的應(yīng)用目標下,由于書寫的隨意性,待評估字圖片中提取的筆畫交叉點與標準字的筆畫交叉點之間很難采用剛性變換匹配。 因此,本文提出基于鄰近點相對位置的筆畫交叉點配對評估函數(shù),采用搜索交叉點配對空間的方式實現(xiàn)配準。

1.2 遺傳算法

遺傳算法(Genetic Algorithm,GA)是一種優(yōu)化求解的算法,1995 年由John holland 博士提出[10],與粒子群算法、蟻群算法等都屬于擬生類的優(yōu)化算法,其基本思路是模擬生物進化過程中基因的演化,在目標求解空間中找到優(yōu)解。 遺傳算法的核心組成包括:

(1)編碼策略。

編碼策略即提出一種編碼方案,將問題的求解空間映射成基因序列。 基因序列一般是一個二進制序列,每個序列對應(yīng)一個求解空間中的解。

(2)適應(yīng)度函數(shù)。

適應(yīng)度函數(shù)即評估函數(shù),評估某一個編碼序列對于目標問題求解的優(yōu)劣度,優(yōu)劣度會影響到下一步遺傳操作。 適應(yīng)度函數(shù)需要滿足單值、連續(xù)、非負等要求。

(3)遺傳操作。

當前已有的編碼序列集合中,通過對遺傳操作生成下一代基因編碼序列。 主要有:變異操作按一定概率修改編碼序列中的位。 交叉操作按一定概率交換兩個序列的不同編碼部位;選擇操作按適應(yīng)度函數(shù)找到最優(yōu)的N 個序列,直接放入下一代序列集合。

本文需要實現(xiàn)的是待評估書寫字與標準字的關(guān)鍵點配準,而使用二進制編碼序列可以很方便地表達點配準方案,如:編碼序列中的1 位表示點配準的對應(yīng)點。 因此本文的求解目標可以很方便地轉(zhuǎn)換成遺傳算法的編碼方式,采用遺傳算法實現(xiàn)關(guān)鍵點配準的求解。 此外,本文采用遺傳算法實現(xiàn)筆畫交叉點配對方案的搜索,尋找關(guān)鍵點配準優(yōu)解方案,還有兩個原因:一是單字配準的計算量仍然可觀,據(jù)統(tǒng)計,漢字平均筆畫有11.2 畫,交叉點平均10 個左右,按全局搜索則關(guān)鍵點配對的方案平均超過百次,每次都需要執(zhí)行評估相關(guān)的浮點計算,因此單字配準的計算量仍較大;二是遺傳算法比較適應(yīng)于分布式計算架構(gòu),按本文前述需要實現(xiàn)對中小學(xué)生的日常書寫字評估,而正常一所中小學(xué)生每周的書寫作業(yè)產(chǎn)生的待評估書寫數(shù)量很大。 遺傳算法本質(zhì)上是可以并行分布式的,所以基于分布式計算框架實現(xiàn)的遺傳算法適應(yīng)于本文應(yīng)用場景的需要。 因此,本文在進行了關(guān)鍵點配準的相關(guān)研究之后,選用遺傳算法實現(xiàn)對筆畫交叉點的配準求解空間搜索。

2 基于遺傳算法的筆畫交叉點配準算法

2.1 筆畫交叉點向量的構(gòu)建

通常漢字書寫的脫機評價算法在評價之前,需要對用戶書寫的漢字圖片進行相關(guān)的平滑、去噪與二值化處理,再對漢字圖片進行細化、去毛刺等算法處理,獲得待評價漢字的筆畫交叉點。 由于本文關(guān)注的是關(guān)鍵點配準問題,此類的預(yù)處理并不是本文算法解決問題的主要范圍。 為此,本文采用人工標注的方式實現(xiàn)對標準字與待評估字筆畫交叉點的提取。 人工標注筆畫交叉點的標準字與待評估字如圖1—2 所示。

圖1 標注交叉點的標準書寫字

如圖1 和圖2 所示,本文通過直接在寫字書的圖片上標注出交叉點,以獲取各交叉點的二維坐標位置。 雖然圖1 和圖2 經(jīng)過拍照書寫字來采集電子圖片,并縮放到同樣大小的尺寸,但由于拍照遠近、書寫位置與大小的變化,直接使用筆畫交叉點的二維坐標作為評估算法的點向量顯然無法實現(xiàn)有效評估。

圖2 標注交叉點的待評估書寫字

結(jié)合漢字從上向下、從左向右的書寫習(xí)慣以及交叉點配準主要依賴于周邊相鄰的點,本文采用相鄰位置構(gòu)建交叉點向量。 對于相鄰的點,本文給定的判斷算法如下。

算法1:關(guān)鍵點X 的相鄰點集構(gòu)建算法。

(1)假設(shè)存在一點X,其二維坐標為(x1,x2),設(shè)X 的相鄰點集合E 為空;

(2)構(gòu)建候選點集C,將圖中所有關(guān)鍵點排序放入C,C 中各點的排序是以各點與X 的歐氏距離從小到大排列;

(3)構(gòu)建邊集合L,邊集合為相鄰點集合E 中各點按順序依次連接形成的封閉多邊形的邊;

(4)以X 為起點,從候選點集中取出Y 作為終點,構(gòu)建線段XY;

(5)判斷線段XY 與邊集合L 中的邊是否相交;

(6)如果相交,則Y 不是X 點的相鄰點,丟棄該點;如果不相交,則將Y 放置到相鄰點集E 中,同時從候選點集中刪除Y。

顯然,依據(jù)上述算法通常一點最多有3 個相鄰點。 根據(jù)最終本文算法的配準評估,可以預(yù)定相鄰集合的最少點數(shù),來增加配準點的相鄰點個數(shù)。 基于上述相鄰點的構(gòu)建算法,本文給出的點向量定義如下:

假設(shè)存在一點X,其相鄰點集合E,且相鄰點集合E 的長度為N,則X 的點向量空間維度為N,其中第i 維是X 與相鄰點集合E 中第i 點構(gòu)建的距離與角度對< γ,θ>:

如上所述,則本文構(gòu)建的長度N 的關(guān)鍵點向量為:(<γ1,θ1>,<γ2,θ2>,…,<γn,θn>)。 在構(gòu)建完成之后,再進一步對點向量各維度歐氏距離進行規(guī)一化,如式(3)所示,最終得到本文的關(guān)鍵點向量。

2.2 編碼與關(guān)鍵點配準評估函數(shù)

編碼是遺傳算法的基礎(chǔ),由于漢字書寫的隨意性,經(jīng)常會有待評估書寫字的筆畫交叉點數(shù)與標準字的筆畫交叉點數(shù)不一致,因此,本文的編碼方案選擇二者中最大交叉點數(shù)作為編碼的長度,具體的編碼方式如下:

若標準字的筆畫交叉點數(shù)為N,待評估書寫字的筆畫交叉點數(shù)為M,且有N>M,則本文算法的編碼長度為N。 若某個編碼的第i 位為1,且其為該編碼的第j 個1 位,則其代表待評估書寫字的第j 個關(guān)鍵點應(yīng)與N 的第i 個關(guān)鍵點配準。

若M>N,反之亦然。 關(guān)鍵點配準評估函數(shù)也是本文遺傳算法的適應(yīng)度函數(shù),實現(xiàn)對已有編碼表達的關(guān)鍵點配準方案的評估。 設(shè)有關(guān)鍵點向量對,首先給出針對該關(guān)鍵點向量的配準評估函數(shù)如式(4):

由于各關(guān)鍵點的相鄰點個數(shù)并不一定相同,因此在評估函數(shù)中,定義n 為關(guān)鍵點向量i 與關(guān)鍵點向量j這二者相鄰點個數(shù)的最小值。 G(i,j)值為二關(guān)鍵點配準之后,前n 個相鄰點的二二對應(yīng)圍成的幾何三角形面積的平均值。 從上文所述的關(guān)鍵點向量定義可知,關(guān)鍵點向量的維度是按對應(yīng)相鄰點與關(guān)鍵點的距離遠近,從小到大排序。 因此G(i,j)函數(shù)體現(xiàn)出離關(guān)鍵點越近的相鄰點對配準評估的值影響越大。 此外,顯然,G(i,j)值越小,兩個關(guān)鍵點的配準效果越好。

基于上式(4),本文提出關(guān)鍵點配準評估函數(shù)如下式(5):

從式(5)可以看出,設(shè)有標準字的筆畫交叉點向量數(shù)N,待評估書寫字的筆畫交叉點向量數(shù)M,且N

除了上述的編碼與評估函數(shù)之外,由于本文關(guān)鍵點配準對編碼的長度和編碼中1 的位數(shù)有要求。 因此,需要對遺傳算法的變異、交叉操作時,做一定的修改,以保證生成的新編碼中1 的位數(shù)與需要配準的關(guān)鍵點個數(shù)相同。

4 實驗與總結(jié)

基于上述本文關(guān)鍵點向量的構(gòu)建與評估函數(shù),本文實現(xiàn)了遺傳算法的改造,并完成了小樣本數(shù)據(jù)的配準實現(xiàn)。 本文按漢字的結(jié)構(gòu)分成上下、左右、包圍以及獨體4 種類型,每種類型一共選擇了20 個漢字,選擇了20 個小學(xué)生,每個漢字書寫4 次,然后采集形成圖片集,如圖3 所示。

圖3 待評估漢字樣本

同時,本文也開發(fā)了一個小型的JS 前端頁面,用于采集待評估漢字的筆畫交叉點,構(gòu)建交叉點數(shù)據(jù)集,對于書寫字算法與標準字的最終配準結(jié)果判斷,本文采用人工目測的方式,依據(jù)配準點所在字的大體位置,將配準最終結(jié)果分成4 類,準確、較準、一般、差。 基于數(shù)據(jù)集,實現(xiàn)并驗證了本文算法。 在默認的相鄰點判斷算法情況下,也即1 個關(guān)鍵點最多有3 個相鄰點,配準結(jié)果準確率為78.74%,而默認相鄰點為4 個的情況下,配準結(jié)果準確率為88.61%。

由本文的實驗結(jié)果可以看出,本文的算法具有較高的實用性,與其他同類聯(lián)機評估或者使用深度學(xué)習(xí)的方法相比,本文算法不需要大量的數(shù)據(jù)集,也不需要復(fù)雜的訓(xùn)練過程。 本文算法基于遺傳算法,能適應(yīng)大規(guī)模評估的需要,因而也具有一定的應(yīng)用推廣優(yōu)勢。