改進的HOG和SVM的硬筆漢字分類算法

肖愛迪，駱力明，劉 杰

(首都師范大學 信息工程學院，北京 100048)

0 引 言

傳統的基于圖像處理的漢字分類算法[1]分為3類：①基于漢字特征點標注的分類方法，該方法充分利用了漢字的端點、折點、交叉點、T形拐點等信息，但漢字分類的準確性依靠特征點標注的準確性[2]；②基于漢字骨架特征的相似度計算方法，該方法利用圖像的骨架、不變矩、灰度投影等方法對漢字進行特征描述，再結合相似度計算方法，根據差異區間實現漢字等級分類，但漢字細化過程中可能形態發生微變，引入新的毛刺[3]；③基于漢字結構特征的重疊模糊規范化雙彈性網格劃分方法，該方法在雙彈性網格中采用8鄰域模糊化特征方法，增加了特征間的相關性，但特征類間類內方差計算量大，提取速度較慢[4]。

針對以上問題，本文提出一種改進的分層HOG特征提取方法，在特征塊無重疊遍歷的前提下，均勻提取漢字網格特征，再分層統計2×2區域內的特征邊緣信息。該方法在保證特征穩定提取的同時，有效降低維度。該算法再采用SVM作為分類器，實現中小學漢字分類評價。實驗結果表明，提取的特征穩定、維度適中且分類準確率較高。

1 算法介紹

1.1 HOG特征提取

1.1.1 傳統HOG特征提取

方向梯度直方圖(histogram of oriented gradient，HOG)是一種計算并統計圖像局部區域的梯度方向直方圖來表示圖像特征的方法[5]。HOG表達的是圖像形狀信息分布，通過分割、統計、整合細胞單元(cells)內的直方圖構成圖像特征描述子。與其它特征描述方法相比，HOG提取的特征不僅穩定，而且對漢字輪廓信息有較好的體現。

HOG特征提取的詳細步驟如下：

(1)Gamma校正，調節圖像亮度的不均勻性，降低漢字圖像陰影和光照變化所帶來的影響[6]。本文采用的是一種非線性的Gamma校正方法，如式(1)所示

g(I)=Iγ

(1)

其中，I是指圖像中某點的像素值，g(I)為轉化后的像素值，γ為Gamma值。當γ<1時，提高了低灰度值區間的像素對比度，漢字框架呈現暗灰色；當γ>1時用于增強高灰度值區間的對比度，突出體現漢字整體結構特征。

(2)梯度計算。獲取水平方向和垂直方向的梯度分量是獲取HOG特征的前提條件。通過水平方向模板k=[-1,0,1] 和垂直方向模板k=[-1,0,1]T對原圖像做卷積運算，得到水平、垂直方向的梯度。如式(2)～式(5)所示

Gx(x,y)=Pixel(x+1,y)-Pixel(x-1,y)

(2)

Gy(x,y)=Pixel(x,y+1)-Pixel(x,y-1)

(3)

(4)

θ(x,y)=arctan(Gx(x,y)/Gy(x,y))

(5)

式中：Gx(x,y)、Gy(x,y) 分別表示水平、垂直方向的梯度，Pixel(x,y) 表示圖像在 (x,y) 點處的像素值。V(x,y)、θ(x,y) 分別表示像素點(x,y)處的梯度幅值和夾角。如圖1(a)、圖1(b)中分別代表HOG下的沿x、y方向的梯度圖。圖1(a)中突出描述漢字的垂直特征，對豎、斜豎筆畫提取較好，圖1(b)中則重點突出了水平方向特征。

圖1 圖像梯度

(3)構建細胞梯度直方圖并組合形成塊(block)。HOG特征提取的最小處理單元是細胞(cell)，將圖像劃分為若干個cells，將多個cell組成block，用block來表示漢字圖像的局部區域。HOG將梯度方向等分為9個bin梯度，梯度大小作為投影的權值。

(4)區間特征歸一化。由于block間存在特征間的重疊提取，局部光照變化不均等現象。因此，特征歸一化就尤為重要。采用L2范式作為歸一化公式，如式(6)所示

(6)

在傳統算法中，若利用一個128×128像素窗口(window)，以8個像素為步幅長度掃描，以8×8個像素為一個cell，形成了16×16=256個cells，將4×4個相鄰的cells視為一個block，那么，一張圖片包括13×13=169個像素塊，梯度方向為9，故得到HOG特征向量的維數為：4×4×169×9=24336維。不難發現，傳統HOG漢字特征提取時特征維度是巨大的。

1.1.2 改進HOG特征提取

基于1.1.1節的分析，不難看出HOG針對漢字特征提取時存在特征維度過大的現象，原因是HOG特征提取時會出現特征塊重疊現象，由此造成特征塊數量增加，每個塊中都包含多個9梯度的cells特征直方圖，由此導致了最終特征維度過大。為了解決該問題，參考漢字中基于網格技術的特征提取算法[7]，提出改進的HOG特征提取方法。

基于網格的分層HOG特征提取方法。在漢字網格劃分的思想下，優化HOG特征提取中出現的特征塊重疊現象，利用HOG算法將一張漢字圖片分成多個相同的無交叉區域，統計每個區域的方向梯度直方圖，這種方法雖能解決特征塊重疊現象，但會導致圖像出現網格邊緣化問題，即在網格分隔區域內出現特征斷裂現象。

圖2 網格特征

針對網格邊緣化問題，本文增加一個底層HOG特征提取層，將圖像分為4個cell區間，每個cell有9個bin通道，故底層產生36維特征向量。本文考慮以下3種網格劃分方式，有針對網格面積相同的均勻網格劃分如圖3(a)所示，有根據漢字圖像中的45°和135°方向上的對角密度的網格劃分如圖3(b)所示，還有以漢字結構特點的重心為圓心形成的圓形網格劃分如圖3(c)所示。

圖3 四區域網格劃分

底層HOG特征提取擬采用均勻網格的形式，相比于其它兩種劃分方式，均勻網格劃分的特征更符合漢字的結構特征，特別是對于漢字左右部件劃分較明確，所產生的網格邊緣干擾也是最小的。對角網格雖能穩定提取特征，但產生的網格邊緣干擾也較多。圓形網格提取特征不符合漢字結構特征，對“橫”“豎”“撇”“捺”四筆畫方面保留效果是最差的，同時產生了更多的網格干擾信息。

本文提出的基于網格的分層HOG提取漢字特征方法，可有效降低漢字維度，減少網格邊緣化現象。

算法步驟如下：

步驟1 將尺寸為128×128的漢字圖像以32×32的像素鄰域網格作為采樣窗口，以無重疊的方式遍歷整個漢字圖像，由此將一張漢字圖像分成了4×4個block，共計16個網格。由于網格的引入，造成了圖片在網格處邊緣化現象，給整個漢字輪廓特征帶來了干擾信息。

步驟2 引入底層的HOG特征提取向量，其提取采用類似步驟1的方法，將圖像劃分為均勻分布的2×2個網格單元，分別統計每個網格單元中的特征向量。然后，將兩層的特征向量相加，形成了分層次的HOG特征。再通過水平模板[-1.0,1]和垂直模板[-1,0,1]T來計算分層HOG的梯度方向和幅值。

步驟3 根據0°～180°的區間劃分為9個梯度通道來計算各層網格區域的梯度直方圖，并整合兩層的特征梯度直方圖。

步驟5 將歸一化后的直方圖向量組成一個n×m的矩陣用于表示漢字圖像的HOG特征，其中n為網格內直方圖的向量維數，m為整個漢字圖像所要計算的網格個數。

基于改進的HOG特征計算步驟如圖4所示，結果表明，改進算法將原本24 336維特征縮減為2340維。因此，該算法可有效解決漢字特征提取時維度過大的問題。

圖4 基于網格的分層HOG特征計算步驟

1.2 特征降維

采用基于網格的分層HOG特征提取后，漢字圖像維度得到了有效的降低，但圖像中的冗余信息和無關信息的干擾依舊存在。因此，特征降維就至關重要。主成分分析(principal components analysis，PCA)是對特征信息處理、壓縮和抽提的方法，將n維特征映射到k維上(k

假設I(x,y) 是大小為N×N的一幅漢字圖片，將其每一列相互連接，組成一個N2維度的向量。假設有m張漢字訓練樣本圖片，樣本集可以表示為 {xi∈RN×N,i=1,2,…,m}， 其中xi表示第i幅漢字圖像所構成的列向量，將所有的漢字樣本訓練圖像按列排成特征矩陣X，漢字圖像的均值向量η記為式(7)

(7)

則所有訓練樣本的協方差矩陣Sτ為式(8)

(8)

令A=[x1-η,x2-η,…,xm-η]， 有Sτ=AAT， 其維數為N2×N2，又令P=ATA， 矩陣Sτ的特征向量為μi，P的特征向量為vi，則需計算Sτ矩陣的非零特征值對應的特征向量，但由于協方差Sτ的維度過大，需采用奇異值分解定理[9]，μi和vi滿足式(9)，歸一化特征為式(10)

μi=Xvi

(9)

(10)

期望特征向量與總特征向量之比為閾值φ，閾值φ記為式(11)。閾值φ的選擇為PCA降維的核心，通過多組實驗，選用φ=0.96時效果最優

(11)

1.3 SVM訓練分類器

支持向量機[10](support vector machine，SVM)是一種建立在統計學VC維理論[11]和結構風險最小化基礎上的機器學習算法，其最早應用于二分類，也可解決多分類問題，較好地解決小樣本、非線性、高維數和局部極小值等問題[12]。

(12)

(13)

(14)

2 實驗設計

中小學硬筆漢字分類評價的總體框架分為：三級評價策略的建立、數據采集和樣本庫的建立、數據預處理、特征提取、特征降維、特征分類及比對，實驗總體框架如圖5所示。本節將在中小學硬筆漢字三級評價、樣本庫的建立、預處理3個部分進行分述。

圖5 實驗框架

2.1 中小學硬筆漢字三級評價

經過與書法專家討論，并結合《中小學書法教育指導綱要》[13]的要求所編寫的《書法教學指導》，總結形成了以橫平豎直、布白均勻、依字取勢、穿插呼應、有主有次、筆畫間關系為主的硬筆漢字評價原則。領域專家依據評價原則對左右結構、上下結構、包圍結構等結構各200個漢字進行三級制評價，即一級代表優，二級代表良，三級代表差。以左右結構漢字“的”字為例，評價示例圖見表1。

表1 書法漢字圖像評價示例

2.2 樣本庫的建立

樣本來自北京市某兩所學校的在讀中小學生所書寫的硬筆漢字字帖。針對左右結構的漢字“的”部分樣本集如圖6所示，不難看出，直接采集到的圖片存在噪聲和筆跡污染現象，因此，需要對漢字圖像進行預處理。

圖6 部分漢字“的”預處理后的樣本集

2.3 預處理

2.3.1 圖像尺寸歸一化

經OCR掃描后的漢字圖像為1400×1400像素，圖像尺寸過大，會有不必要的細節像素、部分噪聲的干擾，影響最終的實驗結果。現將圖像像素歸一化為128×128和256×256大小。

2.3.2 圖像光滑去噪

圖像去噪是通過移除噪聲來修復、完善原始圖像，其中主要的難點在于移除噪聲的同時，盡可能地保留圖像的細節、邊緣以及結構特征等。本文比較了3種濾波方式：雙邊濾波[14]、高斯濾波[15]、中值濾波[16]。隨機選取一張漢字圖片，效果對比如圖7所示。

圖7 3種濾波效果比較

實驗結果顯示，中值濾波相比于其它兩種算法，去噪效果較好且輪廓信息保留的也好，實驗結果最佳。

2.3.3 圖像二值化

圖像二值化是圖像處理中重要的一步。目前常用的二值化方法有：全局閾值法、局部閾值法、迭代法等[17]。

全局閾值法中最具代表性的就是OTSU算法，其基本思想是求取前景與背景兩部分最佳門限閾值。式(15)、式(16)表示從某一點到q點時，μ為平均灰度值，μi為i點處灰度值，ξ為類間方差，w0(μ0-μ)2、w1(μ1-μ)2分別為前景、背景兩部分類間方差，當存在某一閾值T時，式(16)取得最大值，此時T即為最佳閾值[18]

(15)

ξ=w0(μ0-μ)2+w1(μ1-μ)2

(16)

局部閾值法[19]中最具代表性的是Bersen算法，其基本思想是根據每個像素點所在局部窗口中像素的最值來獲取像素的閾值。該方法會導致漢字局部區域出現筆畫斷裂現象。

迭代法[19]的基本思想是利用循環迭代的方法，逐步逼近最佳閾值，此種方法通過多次迭代動態選擇最優的閾值。實驗結果如圖8所示。

圖8 平滑去噪后圖像二值化處理結果

實驗結果表明，預處理后，漢字圖像有效去除了網格虛線和油墨污染處的噪聲，為后續實驗進展奠定基礎。

3 實驗分析

實驗在WINDOWS 10操作系統，硬件配置為Inter(R) Core(TM) i7-6700CPU 3.4 GHz，8 GB RAM，編譯軟件為Visual Studio Code并結合4.1.1版本的opencv計算機視覺庫。本節將在參數分析實驗和對比實驗這兩個方面來分述中小學硬筆漢字分類算法。

3.1 參數分析實驗

漢字的結構類型以左右和上下結構為主[20]，特別是左右結構的漢字在漢字學習的初級階段中占比很高。故，選用代表性漢字“的”作為左右結構漢字進行參數分析實驗。選取195張經過預處理的圖片，其中評價為優、良、差各50張，共計150張漢字“的”組成訓練集，評價為優、良、差各15張，共計45張“的”組成測試集。

為了確保結論的可靠性，在評價為優、良、差各50張訓練集“的”中，每部分任選25張，共計75張作為一次實驗的訓練集。同理，每次的測試集在三級評價中任選8張，共計24張作為一次實驗的測試集，共計進行了10次獨立實驗。由于每次抽取的訓練和測試樣本集略有不同，所以準確率有一定波動。下面將分別分析圖像尺寸、區域劃分大小、梯度大小對實驗準確性的影響。

3.1.1 圖像尺寸參數實驗

由于漢字在不同尺寸下，提取特征維度、運行效率、分類準確率不同，故在128×128和256×256尺度下進行了10次獨立實驗，準確率如圖9所示。圖9中折線由上到下的平均準確率分別為：0.8124、0.7750、0.7249、0.6724。實驗結果顯示，在相同梯度、區域劃分時，128×128尺寸比256×256平均高出0.0374和0.0525。由此說明，圖像尺寸不能過大，過大的圖像反而帶來更多的噪聲，降低魯棒性。最終，以128×128尺寸構成漢字樣本集。

圖9 驗證圖像尺寸準確率對比

3.1.2 區域劃分參數實驗

比較不同區域大小(block)對實驗準確率的影響。在128×128尺寸下保證梯度不變，劃分不同block，進行了10次獨立實驗，實驗結果如圖10所示。由上到下平均準確率分別為：0.7167、0.8125、0.625。實驗結果表明，不能對圖像進行過分割，并且block存在極值。故最終選擇block大小的32×32像素大小為最佳。

圖10 區域劃分大小對實驗準確率的影響

3.1.3 梯度參數實驗

比較不同梯度(bins)方向大小對實驗準確率的影響。在“的”字樣本集中，圖像尺寸128×128，以32×32像素分塊時，且在0°～180°的區間內梯度9等分時，不同梯度大小對實驗準確率影響，即在bins=3,6,9,15,18分別進行了10次獨立實驗，平均準確率如圖11所示。根據結果顯示在bins為9時達到極值點。故最終選取bins=9為最佳。

圖11 180°梯度方向分塊個數對準確的影響

3.2 對比實驗

本節針對基于網格的分層HOG特征提取方法與傳統HOG特征提取在特征維度和輪廓特征提取方面作對比，并依據該方法實現對左右結構、上下結構、包圍結構漢字的三級分類并與傳統方法作對比。

3.2.1 特征實驗對比

針對中小學漢字的特殊性，即中小學生缺少大量書寫臨習實踐的能力，書寫的漢字樣本集會出現筆畫過粗、過深、油墨污染的現象，會帶來特征提取不準確的問題。傳統HOG可以很好的描述漢字的輪廓特征，起到細化漢字特征的作用，但傳統HOG存在特征提取維度大，易受外界無關因數的干擾問題。基于此，本文提出了基于網格的分層HOG特征提取算法，在保證漢字輪廓特征得到有效保留后，有效降低特征維度，優化運行效果，見表2。

表2 特征實驗比較

根據3.1節，表中傳統算法均按cells大小為8×8像素劃分，block大小為4×4個cells組成，梯度方向大小為9進行實驗。改進算法以32×32像素為一網格并按照不重疊的方式遍歷漢字圖像并結合底層的防止網格邊緣干擾的特征劃分作計算。實驗結果表明，改進后的基于網格的分層HOG特征提取相比傳統算法，在保證輪廓信息有效提取的同時，降低了特征維度。

3.2.2 分類實驗對比

基于上述參數分析實驗，本研究采用128×128的圖像大小，以32×32像素為一個網格區域，并以梯度大小為9進行實驗。由于漢字結構的多樣性，難以實現全部結構的漢字的對比。因此，本研究基于中小學常用漢字的背景下，對中小學生最常用的左右結構、上下結構、包圍結構的漢字樣本作為實驗對象。根據統計，選用最常用的漢字“的”字代表左右結構，“是”字帶表上下結構，“國”字代表包圍結構。針對“的”“是”“國”字樣本集，將專家評價為優、良、差的漢字各50張，共計150張漢字圖像作為訓練集，評價為優、良、差各15張共計45張組成漢字測試集，統計195張各結構漢字作為樣本集。測試預處理對實驗分類效果的影響，并且測試了改進的基于網格的分層HOG特征提取對實驗準確率、運行時間的影響。實驗結果見表3。

表3 算法結果比較

通過以上實驗可知，本文所提的改進算法，能夠有效應用在硬筆漢字的分類領域。實驗1和實驗2表明，經過預處理后的左右結構、上下結構、包圍結構漢字比原圖的分類效果提高11.1%、2.9%、9.4%，表明了預處理操作對本研究的重要性。實驗2和實驗3表明了本文所提改進方法與傳統方法相比，在漢字左右、上下、包圍結構下分類結果提高2%～5%，并使分類速度平均提高了約40%。

4 結束語

在中小學硬筆漢字分類評價的背景下，解決了漢字特征提取時特征冗余、維度過大，以及邊緣化的問題。并提出一套較為完整的中小學硬筆漢字評價框架。提出了針對不同結構漢字樣本集的基于網格的分層HOG特征提取算法，并且通過實驗預處理，去除漢字的噪聲和毛刺，又結合PCA進一步降維后采用SVM分類器實現了中小學硬筆漢字左右、上下、包圍結構的三級分類評價。實驗結果表明，在準確率提高的前提下，分類速度也獲得較大提升。評價指標的完善以及多結構漢字實驗是下一步的研究重點。