基于試探的未知類別聚類的識別算法應用研究

張 飛

(安徽廣播電視大學 計算機系，安徽 阜陽 236000)

長期以來手寫字體識別技術是圖像處理領域的研究重點，不僅在交通運輸、刑偵、智能農業上有著廣泛的應用，在學習網絡、機器學習等模式識別領域也占據著十分重要的地位[1].手寫字體識別技術有很多，包括卷積神經網絡、機器視覺、深度學習、BP算法等[2-5].羅麟等人利用精簡化網絡層次的卷積神經網絡對低質量筆跡圖像進行特征識別，避免了神經網絡受制于原圖學習模式的限制問題[2].陳施碩通過機器視覺技術對手寫字體輪廓邊緣特征進行提取識別，與傳統試卷手寫字體分數識別方法相比更省時省力，但對于小字體或模糊字體的輪廓特征提取精準度較低[4].陳子寧借助BP算法(人工神經網絡)對手寫脫機字符進行模式識別，通過log-sigmoid函數設計隱含層神經元能夠準確對手寫字母進行分類識別，但是漢字數量大，分類和識別效果不好[5].目前仍沒有一套很完善的識別算法，真正的無限制手寫體字符識別的研究還有待進一步加強.同時，類似于神經網絡、BP算法、主成分分析等深層次算法盡管可以獲取高精度的圖像識別效果，但對于編程和軟件具有較強的依賴性因而限制其發展[6-8].而類別聚類算法的識別技術是通過數據集的相似性樣本進行歸類的識別算法，利用距離標準化處理消除特征之間量綱差異從而實現字體的識別[9].本文依據聚類尋找標準模式，建立基于試探的未知類別聚類算法的手寫字體識別系統.通過手寫字體與編制字體的數字特征提取，結合聚類分析的模式相似性測量實現目標字體的有效識別，為建立高效手寫字體聚類識別技術奠定基礎.

1 聚類算法的概述

1.1 基于試探的未知類別聚類算法

基于試探的未知類別聚類算法是一種簡單的運算方法，定義誤差平方和為：

(1)

其中，M是聚類中心的個數，M應該小于樣品的總個數；wi是聚類中心；Xwi是wi的重心；針對所有樣品假設某種分類方案，計算J值最小的那一種分類方案，則認為該種方法為最優分類.

1.2 模式相似性測量

(1)樣品與樣品之間的距離

假設兩個樣品特征值分別為Xi，Xj，即

Xi=(Xi1,Xi2,…Xim)T，Xj=(Xj1,Xj2,…Xjm)T,

(2)

為了評定兩個樣品是否屬于同一類，可以通過兩個樣品之間的距離進行判斷，距離的大小決定了樣品的類別歸屬[10].樣品距離計算的方法有很多種，包括二值法、夾角余弦法、歐式距離法等[11].本文主要研究歐式距離法.計算公式如下所示：

(3)

Dij越小則兩個樣品距離越近，就越相似.

(2)樣品與類之間的距離

假設ω代表某類樣品的集合，ω中有n個樣品，X是某一個待測樣品.樣品與類之間的距離可描述為：

(4)

2 識別系統的設計與實現

利用vc++6.0環境進行手寫體數字識別系統設計，如圖1所示.該系統橫向主要分為字體輸入、預處理、特征提取、分類決策和結果輸出5個部分；縱向可分為未知類別模式的分類和分類器的訓練兩個部分.其中未知類別模式的分類，主要用于對手寫字體的數據特征提取分類，而分類器的訓練主要通過已有的標準字體對手寫字體進行訓練，利用固有的判別函數對分類決策進行誤差分析，從而實現準確的聚類識別.

圖1 手寫體數字識別系統結構

2.1 數字的錄入

本系統為處理的聚類問題提供了2種數據錄入方式，分別為手寫字體輸入和標準字體輸入.以隨機書寫數字1、2、4、3、5、1、2、5、8、4、3為例，進行識別系統識別能力考察，如圖2所示.

(a) 標準數字錄入

(b)手寫數字錄入圖2 數字錄入示例

其中，手寫錄入通過按住鼠標左鍵，在左視圖中移動鼠標，可以輸入手寫數字.手寫數字的筆畫必須連續，不能斷裂，否則將被認為是不同的數字.部分代碼實現如下：

void CModeView∷OnLButtonDown(UINT nFlags,CPoint point)

lButtonDown=true；

CView∷OnLButtonDown(nFlags,point)；

void CModeView∷OnMouseMove(UINT nFlags,CPoint point)

if (stateDoc && lButtonDown)

if (point.x>4 && point.x+34 && point.y+4

CRect rc；

rc.left=point.x-5；

rc.right=point.x+5；

rc.top=point.y-5；

rc.bottom=point.y+5；

for(int x=point.x-4；x

for(int y=point.y-4；y

if((x-point.x)*(x-point.x)+(y-point.y)*(y-point.y)<25)

if (statePen)

2.2 圖像的標識及特征提取

圖像的標識是通過連通域判別的方式進行.其中，圖像中與像素(x，y)對應的點集合{(x+p，y+q)；((p，q)是一對有意義的整數)}稱之為像素(x，y)的鄰域.一般可以分為4鄰域和8鄰域.而有像素f(x，y)=f(x+i，y+j)，i，j在圖像區域R內存在，f(x，y)與f(x+i，y+j)路徑中的鄰接點存在4點鄰域連通成分(如圖3)或8點鄰域連通成分(如圖3)，則點f(x，y)與f(x+i，y+j)連通.在圖像內可能存在多個連通成分，每個非連通成分都對應一個目標圖像區，給各目標圖像區分配相應標號的工作稱為標記.在二值圖像中進行物體標識，采用8連通域判別方法，如圖3所示，圖中有A，B，C 3個不連通的物體.

圖3 物體標識示意圖

對各個樣品進行標號，檢測緩沖區，從左到右、從上到下，依次檢測每個像素，如果發現某像素點像素值小于閾值T，則依次檢測該點的右上、正上、左上及左前共4個點的像素值，根據前面介紹的8個準則進行連通性的判斷，并標識物體，將物體的像素值改為標號.依次逐行檢測至掃描結束.獲得各個樣品所在位置及編號.在上述基礎上，將每個物體分成7*7等份，計算每一等份中黑像素所占比例，作為特征值，因此，每個物體提取了49個特征.調用voidCCluster∷CalFeature(int index,CPoint It,CPoint rb)函數，獲得所有樣品特征放入m_pattern的特征值中，m_pattern是樣品的特征數據結構.

2.3 基于試探的未知類別聚類算法的識別結果

設有n個樣品X1,X2,…Xn，patternnum=n.選一個樣品作為第一個聚類中心C1，不妨令C1=X1.Centernum記錄當前中心的數目，centernum=1.通過對話框讀入閾值T，輸出所有樣品之間的最大與最小距離為T的參考.對所有樣品，計算該樣品m_pattern[i]到所有聚類中心m_center[j]的距離，找到最小值Dj(0≤j

圖4 聚類結果

從圖4中可以看出，手寫數字1、2、4、3、5、1、2、5、8、4、3聚類后總共分為6類，分別為1、2、4、3、5、8.而數字4和3存在兩個數字重復，在類別上分別為類別3和類別4；所有的數字識別和分類均準確，準確率達到100%，說明該聚類識別系統的手寫數字識別效果還是滿足實際需求的.

3 結 論

將聚類法應用于手寫體數字識別是聚類法研究最為成功的方面之一，它為手寫體數字識別提供了一種新的、行之有效的方法.本文對手寫數字特征進行提取，采用最鄰近規則算法進行聚類分析，并運用VC++語言編寫數字手寫識別系統，加強對聚類法應用方面的認識和實際運用能力.但由于最鄰近規則的試探法受到閾值T的影響很大，造成系統設計應用新的識別算法的識別率不高，后續應該深化降低對閾值T影響的程度.