一種LLE降維表示的漢字字體識別方法

劉 聰，王存睿，許 爽

(大連民族大學 a.信息與通信工程學院；b.計算機科學與工程學院；c.大連市漢字計算機字庫設計技術創新中心, 遼寧 大連 116605)

字體識別可作為字體侵權行為檢測的技術方法之一。不同的漢字字體的特征除了體現在字符形態的多個方面如部件的空間分布、疏密程度、中宮的聚集程度，還體現在筆畫的粗細、曲直、光滑度、筆鋒的變化、交叉點等方面，這將導致字體特征變得更加復雜，但同一字符的不同字體又具有較高的相似性，這給字體識別帶來諸多挑戰如圖1。

圖1 “乖”的不同字體

隨著漢字行業的發展，字體種類的增加，對于字體識別侵權往往需要識別不同混合字體，這將必然導致系統識別錯誤率的上升。針對上述問題，本文提出了一種基于LLE降維表示的漢字字體識別方法提高漢字字體識別的準確性。

1 研究現狀

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

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

2 特征提取

在原始數據的特征數量很大，原始數據處于高維空間結構中，通過變換映射將高維數據用低維空間來表示，這個過程叫特征提取[10]。特征提取廣義上來說是一種變換，但是特征選擇是從已有的特征中選擇出一些有效的特征，達到降低維度的目的[11]。

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

圖2 字體特征提取流程圖

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

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

zi=wijzj+wikzk+wilzl。

(1)

為了在低維空間中局部點的相對位置關系仍然能夠保持，可以按照如下步驟進行推演：

Step1：為高維數據Z中的每個樣本點zi選取k個近鄰點zi1,zi2,…zik；

Step2：為每個樣本點計算一組權重wi,i∈[1,k]借助權重用zik重構zi；

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

3 數據集

為了驗證字體識別方法的有效性，本文使用的數據都是常用字體數據，用到的字體包括黑體、楷體、圓體、裝飾體四種見表1。

表1 實驗字體類別表

每個字體按照字典順序取出前300個漢字，每字體隨機從這300個漢字中選取200個作為訓練樣本，剩余的100個作為測試用例，并將字符轉為32×32像素的字體圖片。

4 本文方法

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

LLE關注于降維時保持樣本局部的線性特征，保持原有的拓撲結構。LLE是非線性降維技術，是流形學習中最經典算法之一[13]。LLE算法將高維度字體特征映射到低維空間，且保持原有數據的特征空間。黑體HYb0gj、楷體HYh1gj、圓體HYe0gj、裝飾體AliHYAiHei四種字體在低維坐標空間的聚類效果如圖3。

圖3 四種字體降維可視化

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

圖4 字體識別流程圖

先構建字體特征數據集，之后將要識別漢字單字圖像降至2維，計算字體特征數據集每個字體與單字相似度，將單字歸類為相似度最高字體。

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

Step1：對聚類的每一類族隨機選取1個中心點；

Step2：遍歷特征數據，將每個數據劃分到對應類族中心點集合；

Step3：計算每個類族中心點集合的平均值，并作為新中心點；

Step4：重復步驟2，3直到中心點不再收斂；

Step5：計算每個聚類半徑Rk。

兩點間歐式距離公式為

(2)

其中，x代表數據有m個屬性的向量。

(3)

式中：Ck表示第k類族；|Ck|表示第k類族數據對象的個數；Certerk表示第k類族中心點，其中

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

(4)

其中，xi∈Ck。

字體特征集為

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

(5)

單字識別流程為

Step1:輸入單字圖片t；

Step2:字體圖片預處理；

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

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

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

Step6:統計識別結果。

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

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

(6)

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

(7)

若D(t＇,k)>0，

(8)

5 設計實驗與實驗分析

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

圖5 字體中心點

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

對于測試樣例按照10、20、25為一個單位進行分組，每個分組最后計算平均識別率。實驗結果見表2。

表2 四種字體平均識別率

通過對表2的實驗結果分析可知，本文的方法對于不同的字體識別效果不一樣。因為不同字體通過流形降維算法降維后聚類效果不一樣。該實驗表明，基于LLE降維表示字體分類方法整體是有效的。

6 結 語

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