基于決策導向非循環圖支持向量機的脫機手寫體漢字識別

吳仕蓮 楊杰 趙冬琴

摘要：目前脫機手寫體漢字識別在小字符集方面取到了比較好的效果，但在大字符集方面仍存在著識別速度慢、準確率低等問題。不同于傳統的二叉樹方法，本文將決策導向非循環圖用于漢字識別，并加以改進。仿真實驗表明，該算法能對大字符集的手寫體漢字進行識別，有效減小了誤差，具有較高的識別率。

關鍵詞：支持向量機 多分類 脫機手寫體漢字 決策導向非循環圖

中圖分類號：TP391.4 文獻標識碼：A 文章編號：1007-9416（2016）07-0041-02

Abstract：Currently，off-line handwritten Chinese characters recognition in the small category character recognition has obtained good effect. However，recognition in large character set still has the weakness of low efficiency and low accuracy.This paper presented an improved SVM-based algorithm of Decision Direct Acyclic Graph（ DDAG）. Simulation results demonstrate that the algorithm can recognize large character set of handwritten Chinese character and has high recognition performance.

Key Words：SVM；multi-classification；Handwritten Chinese Characters；DDAG

字符識別技術已經發展了幾十年，對英文來說，識別技術已經足夠成熟了[1]。而中文卻存在漢字字符集字量過大的問題，使得多分類問題愈加困難，對漢字的識別研究也集中于小字符集方面。傳統的識別技術如神經網絡、決策樹等識別方法也存在識別速度慢、識別率不高等問題[2]。而SVM在識別手寫體漢字上具有識別率高、識別速度快的優點[3]。針對SVM中常用的多分類方法存在的識別速度慢、誤差大的問題，文章提出一種將決策導向非循環圖用于漢字識別并加以改進的算法，并成功應用于大字符集的漢字識別方面。

1 支持向量機

1.1 SVM分類器

支持向量機（ Support Vector Machine，SVM）這一概念是Vapnik等人在20世紀90年代中期首次提出的。它在泛化能力和有限個訓練樣本的學習精度間取得了很好的平衡，由此獲得了較好的推廣能力。支持向量機 靈活地根植于凸優化理論，因此具有良好的最優化性。同時，SVM建立于結構風險最小化準則上，從而使得支持向量機分類器具有較好的推廣能力 ，已得到了廣泛的應用。SVM起初對線性可分情況進行分析，而對于漢字識別的非線性分類問題，用核函數將特征向量從低維空間映射到高維空間，使低維空間的非線性分類問題轉換為高維空間的線性分類問題，在高維空間采用線性分類算法對漢字的非線性特征進行分析。在二分類問題中，給定樣本

，，則svm的判決函數就是下式

（1）

其中是（2）式約束問題的最優解

（2）

（3）

（4）

其中為拉格朗日乘子，C為懲罰因子，b是分類閾值，b的計算公式如下

（5）

K為核函數，定義了一個從低維空間到高維空間的映射，是一種計算映射到高維空間之后內積的一種簡便方法。主要有

（1）線性內核：

（2）徑向基內核（RBF）：

（3）多項式內核：

（4）sigmoid核：

本文采用的應用最廣的RBF核函數，在手寫體識別領域也取得了較好的效果。SVM的計算機實現則采用smo的改進算法。

1.2 多分類問題

SVM本來是針對二分類問題提出來的，而漢字識別卻是多分類問題，所以要構造多類分類器，目前主要是通過多個二分類器組合實現多類分類的功能。常見方法有one-against-one、one-against-rest兩種。

（1）一對其他法（one-against-rest）：即在訓練時依次把某個類別的樣本歸為一類，其他剩余的樣本歸為另一類，這樣k個類別的樣本就構造出了k個二分類器。分類時比較的值，將最大值對應類別賦給待分類樣本。

（2）一對一法（one-against-one）：在任意兩類樣本之間設計一個二分類器，即k個類別的樣本就需要設計k（k-1）/2個二分類器。當對一個待識別樣本進行分類時，用所有的二分類器對樣本進行“投票”，該待分類樣本的類別就是最后得票最多的類別。一對一分類方法簡單有效，并且訓練時間較短，適合大字符集的漢字識別這樣的大規模數據。因此本文選擇一對一法訓練二分類器。

2 決策導向非循環圖

2.1 決策導向非循環圖基本原理

決策導向非循環圖DDAG（Decision Direct Acyclic Graph），對于n類分類問題，DDAG采用一對一（one against one）的方法訓練分類器，即得到n（n-1）/2個二分類器。為了解決k類分類問題，首先需要訓練k（k-1）/2個分類器，然后DDAG識別需經過下列步驟

（1）生成類別系列，，并且定義i與j，初始化分別指向序列的開頭與結尾

（2）對于待識別樣本x，用二類分類器進行分類，其中表示由和類訓練樣本訓練而成的二分類器。

（3）如果類，則令；如果，則令。再回到②，直到，此時i指向的類別即為待分類樣本x的類別。

結果如圖1所示。

可以看出，DDAG采用了1-v-1的多類SVM基本結構[8]。對于一個N類問題的分類過程，DDAG為了對某待測樣本進行分類，只需要構造n-1個決策點，相對其他方法而言速度更快，并且準確度更高，不存在誤分、拒分。

2.2 基于改進DDAG的支持向量機

傳統支持向量機采用一對一或者一對其它方法設計多分類器時，會存在誤分、拒分區域。而層次結構固有的弊端就是自上而下的誤差累積，DDAG也不能避免。從圖1中可以看出誤差從根節點向下逐漸累積，并且越靠近根節點的分類性能對整個分類模型的影響越大。因此在生成DDAG的過程中，應該讓更容易分離的兩類更早分離出來。而傳統DDAG隨機生成類別序列，并沒有刻意早分離容易分離的兩類。為了減少累積誤差，提高識別率，應將容易分離的兩類分別放置在類別序列的兩端，即在漢字識別過程中，應該將形近字訓練成的二分類器放在葉子節點處，字形差別大的漢字訓練成的二分類器放在上層節點。令p，q分別表示第p類和第q類漢字，在DDAG的第①步產生類別系列時，設，，對于形近字，應盡可能使i=j+1；對于字形差別比較大的漢字，則應盡可能使i+j=k+1。這樣在識別過程中，從根節點到葉子節點的過程中，都是先分類差別大的2類，大大減少了上層節點的累積誤差。

但在具體的計算機實現中，形近字的劃分卻很困難。采用聚類的方法無疑會很大程度上增加計算量，并且也不能很好的區分漢字的字形差異程度。而漢字的UTF-8編碼是按照拼音排列的，即音近字的編碼是相鄰的。一般而言，很多形近字也是音近的，所以很大程度上可以用UTF-8編碼來代表漢字的字形，即認為編碼相鄰的漢字是形近字，編碼差別越大，字形差別越大。這樣在生成類別序列時，只需要按照編碼逐個填入對應的漢字類別即可。對于n個漢字的分類，具體算法流程如下：

Step1：采用一對一的方法來訓練分類器，得到n（n-1）/2個二分類器；

Step2：根據UTF-8編碼從前往后依次給漢字標注為第1類，第2類...第i類...第n類；

Step3：生成類別系列時，令；

Step4：對于待識別樣本x，用二類分類器進行分類，其中表示由和類訓練樣本訓練而成的二分類器；

Step5：如果類，則令；如果，則令。再回到②，直到；

Step6：根據查找對應的UTF-8編碼，并根據編碼確定并輸出對應的漢字。

3 仿真實驗及分析

在識別之前對獲取文字圖像進行預處理，具體流程如下：

3.1 二值化處理

即先將24位真彩色圖像轉化為8位灰度圖像，然后使用otsu方法進行最佳全局閾值處理得到二值圖像。

3.2 圖像分割及特征提取

在分割之前之前獲得的二值圖像采用中值濾波方法做平滑去噪，然后使用投影方法分割出每個字符。有如下幾種常用的特征： （1）灰度或顏色的統計特征；（2）紋理與邊緣特征；（3）圖像的代數特征；（4）圖像變換系數特征。而本文采用一種較為便捷的特征提取方法，將文本圖像歸一化為32*16大小的圖像；然后將圖像網格化，劃分成3*3網格，分別統計每個網格中黑色像素點的個數，這組成特征向量的前9維，然后統計兩條橫分割線和兩條縱分割線上黑色像素點的個數，組成整個13維的特征向量。

實驗根據UTF-8編碼選取常用的3729個漢字，每個漢字取40個訓練樣本，10個測試樣本，核函數選擇徑向基函數，懲罰因子C為1.2，松弛變量為0.001，識別結果如表1所示。

從表1可以看出，DDAG在大字符集手寫體漢字的識別中具有較高的識別率，同時改進后的DDAG也減少了累積誤差，提高了識別率。仿真實驗表明，該算法能對大字符集的手寫體漢字進行識別，很大程度上減少了累積誤差，具有較高的識別率。

參考文獻

[1]In-Jung Kim and Xiaohui. Handwritten Hangul recognition using deep convolutional neural networks.Springer Berlin Heidelberg，2015.

[2]李瓊，陳利，王維虎，基于 SVM 的手寫體數字快速識別方法研究[J].計算機技術與發展，2014，（02）.

[3]張芳，汪成軍.基于支持向量機的手寫體漢字的識別[J].計算機與數字工程，2006，（01）.

[4]朱程輝，項思俊.手寫體漢字識別的二叉樹 SVM算法研究[J].智能、算法、系統工程，2009，（09）.

[5]Keerithi SS，Shevade SK，Bhattacharyya C， et al. Improvements to Platt' s SMO Algorithm for SVM Classifier Design[ J] .Neural Computation， 2001，13（ 3）： 637～ 649.

[6]秦朗.基于二叉樹多層分類SVM的脫機手寫體漢字識別方法研究[D].合肥：合肥工業大學，2010.

[7]劉勇，全廷偉.基于 DAG-SVMS 的 SVM 多類分類方法[J].統計與決策，2007，248（20）：14-148.

[8]李昆侖.一種基于有向無環圖的多類SVM分類器[J].模式識別與人工智能，2003，（02）.

[9]汪政，邵良杉.多類支持向量機分類算法—DDAG[J].研究開發，2010，（07）.

[10]翟俊海，趙文秀，王熙照.圖像特征提取研究[J].河北大學學報，2009，（01）.