陳 潔,王 強(qiáng),杜 嶸

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

0 引言

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

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

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

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

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

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

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

1.1 關(guān)鍵點(diǎn)配準(zhǔn)

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

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

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

1.2 遺傳算法

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

(1)編碼策略。

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

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

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

(3)遺傳操作。

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

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

2 基于遺傳算法的筆畫交叉點(diǎn)配準(zhǔn)算法

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

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

圖1 標(biāo)注交叉點(diǎn)的標(biāo)準(zhǔn)書寫字

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

圖2 標(biāo)注交叉點(diǎn)的待評(píng)估書寫字

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

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

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

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

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

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

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

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

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

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

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

2.2 編碼與關(guān)鍵點(diǎn)配準(zhǔn)評(píng)估函數(shù)

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

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

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

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

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

從式(5)可以看出,設(shè)有標(biāo)準(zhǔn)字的筆畫交叉點(diǎn)向量數(shù)N,待評(píng)估書寫字的筆畫交叉點(diǎn)向量數(shù)M,且N

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

4 實(shí)驗(yàn)與總結(jié)

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

圖3 待評(píng)估漢字樣本

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

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