一種LLE降維表示的漢字字體識(shí)別方法

劉 聰，王存睿，許 爽

(大連民族大學(xué) a.信息與通信工程學(xué)院；b.計(jì)算機(jī)科學(xué)與工程學(xué)院；c.大連市漢字計(jì)算機(jī)字庫(kù)設(shè)計(jì)技術(shù)創(chuàng)新中心, 遼寧 大連 116605)

字體識(shí)別可作為字體侵權(quán)行為檢測(cè)的技術(shù)方法之一。不同的漢字字體的特征除了體現(xiàn)在字符形態(tài)的多個(gè)方面如部件的空間分布、疏密程度、中宮的聚集程度，還體現(xiàn)在筆畫的粗細(xì)、曲直、光滑度、筆鋒的變化、交叉點(diǎn)等方面，這將導(dǎo)致字體特征變得更加復(fù)雜，但同一字符的不同字體又具有較高的相似性，這給字體識(shí)別帶來(lái)諸多挑戰(zhàn)如圖1。

圖1 “乖”的不同字體

隨著漢字行業(yè)的發(fā)展，字體種類的增加，對(duì)于字體識(shí)別侵權(quán)往往需要識(shí)別不同混合字體，這將必然導(dǎo)致系統(tǒng)識(shí)別錯(cuò)誤率的上升。針對(duì)上述問(wèn)題，本文提出了一種基于LLE降維表示的漢字字體識(shí)別方法提高漢字字體識(shí)別的準(zhǔn)確性。

1 研究現(xiàn)狀

在相關(guān)研究中，字體識(shí)別可以分為兩類：第一種是字符無(wú)關(guān)字體識(shí)別，即在未知識(shí)別字體圖片表示具體字符，識(shí)別其字體分類屬性。第二種是已知字體圖像的字符編碼，進(jìn)而識(shí)別其字體分類屬性[1]。根據(jù)字體識(shí)別的對(duì)象是單字符還是多字符文本，字體識(shí)別又可以分為兩種，一種是基于單字符字體識(shí)別，另一種是基于多字符字體識(shí)別[2]。文獻(xiàn)[3]提出了一種基于經(jīng)驗(yàn)?zāi)Ｊ椒纸獾臐h字字體識(shí)別方法，選取反映漢字字體基本特征的8種筆畫作為模板，在漢字文檔圖像塊中隨機(jī)抽取筆畫信息，形成筆畫特征序列[3]。陳等人對(duì)單個(gè)漢字的字符圖像進(jìn)行小波分解，在變換圖像上提取小波特征，用線性鑒別分析技術(shù)(linear discriminant analysis, LDA)進(jìn)行特征選擇，使用修改二次判別函數(shù)(modified quadratic discriminant function, MQDF)分類器分類[4]。許等人使用了一種基于Gabor函數(shù)的全局紋理分析字體紋理[5];王等人提出一種基于特征點(diǎn)的個(gè)體分析法來(lái)解決漢字字體識(shí)別問(wèn)題，該方法適用于多語(yǔ)言混排情況[6]。Guang等人針對(duì)大規(guī)模視覺(jué)字體識(shí)別問(wèn)題，提出了基于最近類平均分類器的可擴(kuò)展方法，可以以較低的成本推廣到新類和新數(shù)據(jù)[7]。Huang等人提出了一種DropRegion方法來(lái)生成大量隨機(jī)變異字體樣本，該技術(shù)自適應(yīng)地構(gòu)造具有均衡信息的一組局部區(qū)域，DropRegion可以無(wú)縫嵌入IFN，實(shí)現(xiàn)端對(duì)端的訓(xùn)練，進(jìn)行字體分類[8]。Yanan Guo提出了一種新的特征選擇算法，線性判別分析Cauchy估計(jì)器用于單中文字體識(shí)別[9]。從以上方法可以得出，字體特征提取的可靠性和分類器的有效性決定了字體識(shí)別的準(zhǔn)確性。字體圖像數(shù)據(jù)維數(shù)較高，含有一些復(fù)雜的空間結(jié)構(gòu)問(wèn)題，可對(duì)高維字體數(shù)據(jù)流形降維進(jìn)而實(shí)現(xiàn)字體分類識(shí)別。

本研究從字體特征提取和分類這兩個(gè)角度出發(fā)，提出一種LLE降維表示的漢字字體識(shí)別方法嘗試解決這一問(wèn)題。

2 特征提取

在原始數(shù)據(jù)的特征數(shù)量很大，原始數(shù)據(jù)處于高維空間結(jié)構(gòu)中，通過(guò)變換映射將高維數(shù)據(jù)用低維空間來(lái)表示，這個(gè)過(guò)程叫特征提取[10]。特征提取廣義上來(lái)說(shuō)是一種變換，但是特征選擇是從已有的特征中選擇出一些有效的特征，達(dá)到降低維度的目的[11]。

為了突出字體的特征，在特征提取前，先要對(duì)圖片預(yù)處理如圖2。

圖2 字體特征提取流程圖

在字體特征提取過(guò)程中首先對(duì)圖像進(jìn)行尺寸歸一化，處理后的圖像像素大小均為32×32；為了降低因處理設(shè)備等原因?qū)D像質(zhì)量的影響，采用了濾波平滑去噪處理；為了減少字體顏色等因素的影響，將圖片灰度化，使其中的R=G=B；在灰度化圖像的基礎(chǔ)上對(duì)圖像進(jìn)行二值化處理，使得字體和背景完全為黑白兩色。LLE是非線性降維方法，也是特征提取中最常見(jiàn)的技術(shù)之一，它與ISOMAP試圖保持高維數(shù)據(jù)映射到低維空間的距離不同，LLE算法試圖保持鄰域內(nèi)樣本間的線性關(guān)系[12]。

在高維樣本空間樣本zi可用鄰近的樣本zj、zk、zl線性組合表示。

zi=wijzj+wikzk+wilzl。

(1)

為了在低維空間中局部點(diǎn)的相對(duì)位置關(guān)系仍然能夠保持，可以按照如下步驟進(jìn)行推演：

Step1：為高維數(shù)據(jù)Z中的每個(gè)樣本點(diǎn)zi選取k個(gè)近鄰點(diǎn)zi1,zi2,…zik；

Step2：為每個(gè)樣本點(diǎn)計(jì)算一組權(quán)重wi,i∈[1,k]借助權(quán)重用zik重構(gòu)zi；

Step3：將wi,i∈[1,k]擴(kuò)充為Wi。

3 數(shù)據(jù)集

為了驗(yàn)證字體識(shí)別方法的有效性，本文使用的數(shù)據(jù)都是常用字體數(shù)據(jù)，用到的字體包括黑體、楷體、圓體、裝飾體四種見(jiàn)表1。

表1 實(shí)驗(yàn)字體類別表

每個(gè)字體按照字典順序取出前300個(gè)漢字，每字體隨機(jī)從這300個(gè)漢字中選取200個(gè)作為訓(xùn)練樣本，剩余的100個(gè)作為測(cè)試用例，并將字符轉(zhuǎn)為32×32像素的字體圖片。

4 本文方法

本文采用LLE對(duì)字體降維處理如圖3。四種字體樣本降維后的可視化，降維后的特征向量為Pi=(p1,p2,…,pm)。其中pm=(pm1,pm2,…,pmn),n=100。圖中橫縱坐標(biāo)值不具備特定物理意義，對(duì)于不同特征提取方式，不同圖像預(yù)處理歸一化，值表示的含義不同，僅表示不同字體映射到低維空間的相對(duì)位置。

LLE關(guān)注于降維時(shí)保持樣本局部的線性特征，保持原有的拓?fù)浣Y(jié)構(gòu)。LLE是非線性降維技術(shù)，是流形學(xué)習(xí)中最經(jīng)典算法之一[13]。LLE算法將高維度字體特征映射到低維空間，且保持原有數(shù)據(jù)的特征空間。黑體HYb0gj、楷體HYh1gj、圓體HYe0gj、裝飾體AliHYAiHei四種字體在低維坐標(biāo)空間的聚類效果如圖3。

圖3 四種字體降維可視化

基于LLE降維表示的漢字字體識(shí)別方法分為兩部分。第一字體特征提取，首先，將字體圖像數(shù)據(jù)向量化，然后使用流形降維算法LLE將高維字體數(shù)據(jù)轉(zhuǎn)換成2維數(shù)據(jù)，在低維數(shù)據(jù)空間計(jì)算每個(gè)字體的聚類中心與聚類半徑Rk，保留到字體特征數(shù)據(jù)集。第二鄰近分類單字識(shí)別，將待識(shí)別的單字圖片利用流形學(xué)習(xí)降維算法LLE同樣降維到2維空間，在同一2維坐標(biāo)空間中，單字圖片2維點(diǎn)與字體特征數(shù)據(jù)集中字體聚類中心點(diǎn)的歐式距離作為字體的相似度判斷依據(jù)。字體識(shí)別流程如圖4。

圖4 字體識(shí)別流程圖

先構(gòu)建字體特征數(shù)據(jù)集，之后將要識(shí)別漢字單字圖像降至2維，計(jì)算字體特征數(shù)據(jù)集每個(gè)字體與單字相似度，將單字歸類為相似度最高字體。

構(gòu)建字體特征數(shù)據(jù)集。設(shè)x為降維后字體字符向量，K為字體類目數(shù)，Rk為第k個(gè)字體聚類半徑，Certerk為第k個(gè)字體聚類中心，dist(xi,xj)為兩字體字符在低維坐標(biāo)歐式距離，Ck為第k類族字體，t為單字測(cè)試圖片，t＇為降維后測(cè)試單字圖片，δ(t＇,k)表示單字t＇與第k類族字體相似度。

Step1：對(duì)聚類的每一類族隨機(jī)選取1個(gè)中心點(diǎn)；

Step2：遍歷特征數(shù)據(jù)，將每個(gè)數(shù)據(jù)劃分到對(duì)應(yīng)類族中心點(diǎn)集合；

Step3：計(jì)算每個(gè)類族中心點(diǎn)集合的平均值，并作為新中心點(diǎn)；

Step4：重復(fù)步驟2，3直到中心點(diǎn)不再收斂；

Step5：計(jì)算每個(gè)聚類半徑Rk。

兩點(diǎn)間歐式距離公式為

(2)

其中，x代表數(shù)據(jù)有m個(gè)屬性的向量。

(3)

式中：Ck表示第k類族；|Ck|表示第k類族數(shù)據(jù)對(duì)象的個(gè)數(shù)；Certerk表示第k類族中心點(diǎn)，其中

Rk=max(dist(xk,Certerk))，

(4)

其中，xi∈Ck。

字體特征集為

{(Certerk,Rk)|k=1,2,…,K}。

(5)

單字識(shí)別流程為

Step1:輸入單字圖片t；

Step2:字體圖片預(yù)處理；

Step3:使用LLE流形降維算法將字體圖片降到2維t＇；

Step4:使用公式(5～7)遍歷每個(gè)字體，獲得單字與各個(gè)字體相似度；

Step5:將單字歸類為相似度最高字體；

Step6:統(tǒng)計(jì)識(shí)別結(jié)果。

降維后單字t＇與字體Ck間的相似性由單字t＇與以Certerk為質(zhì)心，Rk為半徑的圓域歐式距離來(lái)度量，距離差越小，兩字體越相似。

D(t＇,k)=dist(Certerk,xt＇)-Rk。

(6)

若D(t＇,k)<=0，δ(t＇,k)=100%；

(7)

若D(t＇,k)>0，

(8)

5 設(shè)計(jì)實(shí)驗(yàn)與實(shí)驗(yàn)分析

對(duì)每組字體訓(xùn)練數(shù)據(jù)，使用流形降維算法映射到2維空間，求出每個(gè)字體質(zhì)心Certerk與圓域半徑Rk如圖5。圖中橫縱坐標(biāo)值不具備特定物理意義，對(duì)于不同特征提取方式，不同圖像預(yù)處理歸一化，值表示的含義不同，僅表示不同字體映射到低維空間的相對(duì)位置。

圖5 字體中心點(diǎn)

其中,Certerk表示第K個(gè)字體中心點(diǎn)坐標(biāo)，Rk表示第K個(gè)字體圓域半徑，圖中四種不同的聚類分別表示四種不同的字體，每個(gè)字體用不同顏色和形狀的點(diǎn)標(biāo)注，每個(gè)字體有一個(gè)字體中心點(diǎn)，其他字符到該字體中心點(diǎn)遠(yuǎn)近代表與該字體相似程度。

對(duì)于測(cè)試樣例按照10、20、25為一個(gè)單位進(jìn)行分組，每個(gè)分組最后計(jì)算平均識(shí)別率。實(shí)驗(yàn)結(jié)果見(jiàn)表2。

表2 四種字體平均識(shí)別率

通過(guò)對(duì)表2的實(shí)驗(yàn)結(jié)果分析可知，本文的方法對(duì)于不同的字體識(shí)別效果不一樣。因?yàn)椴煌煮w通過(guò)流形降維算法降維后聚類效果不一樣。該實(shí)驗(yàn)表明，基于LLE降維表示字體分類方法整體是有效的。

6 結(jié) 語(yǔ)

本文在單字圖片字體識(shí)別取得良好的效果，但是由于流形降維算法對(duì)某些字體降維聚類的效果并不是很好，導(dǎo)致實(shí)驗(yàn)對(duì)聚類中心點(diǎn)和聚類半徑的計(jì)算會(huì)有偏差，所以提高流形降維算法在字體上的聚類效果，有待進(jìn)一步的研究。