趙衛(wèi)東，劉永紅，鄢 濤，于 曦

(1.成都大學(xué) 模式識別與智能信息處理四川省高校重點實驗室，四川 成都 610106;2.成都大學(xué) 信息科學(xué)與工程學(xué)院，四川 成都 610106)

基于KNN算法的手寫數(shù)字識別研究

趙衛(wèi)東1,2，劉永紅1,2，鄢 濤1,2，于 曦1,2

(1.成都大學(xué) 模式識別與智能信息處理四川省高校重點實驗室，四川 成都 610106;2.成都大學(xué) 信息科學(xué)與工程學(xué)院，四川 成都 610106)

KNN算法用于手寫數(shù)字識別的時候，需要將待識別的手寫數(shù)字圖像(測試集)與一些已知的手寫數(shù)字圖像(訓(xùn)練集)聯(lián)合在一起求向量之間的最短距離，才能判斷待識別數(shù)字圖像的分類.設(shè)計了一種將測試集圖像中的數(shù)據(jù)與尺寸轉(zhuǎn)換為與訓(xùn)練集圖像完全相似的轉(zhuǎn)換算法，并在此基礎(chǔ)上，將測試集和訓(xùn)練集都轉(zhuǎn)換成有相同列數(shù)量的一維向量，進而求出向量之間的距離，并通過編寫Python程序?qū)υ撍惴ㄟM行了驗證.測試結(jié)果表明，該方法對手寫數(shù)字圖像的正確識別率能夠達到95%以上.

KNN;Python;訓(xùn)練集;測試集

0 引 言

KNN算法也稱K近鄰算法(K-nearest neighbor,KNN)，是一種基本分類與回歸方法，也是手寫數(shù)字識別的基礎(chǔ)算法之一[1-3].在實際應(yīng)用中，KNN算法的輸入為實例的特征向量，對應(yīng)于特征空間的點，輸出為實例的類別.KNN算法假設(shè)已經(jīng)準備好1個訓(xùn)練數(shù)據(jù)集，其中每個實例的類別是預(yù)先指定的.分類時，對新的實例(測試數(shù)據(jù)集)，根據(jù)K個最近鄰的訓(xùn)練實例的類別，通過多數(shù)表決等方式進行預(yù)測.K值的選擇、距離度量及分類決策規(guī)則是KNN算法的3個基本元素[4].在通常情況下，訓(xùn)練集圖像是已經(jīng)剪裁成統(tǒng)一規(guī)格且四周沒有空白空間的二值化圖像，而測試集可以是任意圖像，不能直接與訓(xùn)練集進行比較.目前，針對圖像轉(zhuǎn)換方面的研究比較少，對此，本研究設(shè)計了一種將測試集的數(shù)據(jù)轉(zhuǎn)換為與訓(xùn)練集相同規(guī)格的數(shù)據(jù)的算法.

1 訓(xùn)練集和測試集

不失一般性，假設(shè)訓(xùn)練集是由多個文本文件組成的集合，每個文件表示1個已知的數(shù)字(0～9)，每個文件的格式是1個32×32的文本文件.文件中的0表示白色，是底色；1表示黑色，是數(shù)字的筆跡.圖1、圖2分別為數(shù)字8的手寫筆跡圖像與文本文件.

盡管采用文本格式存儲圖像不能有效地利用內(nèi)存空間，但為了方便理解，還是應(yīng)將圖像轉(zhuǎn)換為文本格式[2].在實際識別算法中，需要將每個文件的32行按首尾順序連接，合并為1行，形成1個1×1 024的特征向量.訓(xùn)練集的主要特點是，由于數(shù)字的高度通常大于寬度，所以有些數(shù)字左右兩邊需要用全0的列填充，數(shù)字1構(gòu)成的形狀處于圖像的橫向正中間，訓(xùn)練集的上下部分沒有空白區(qū)域.

圖1數(shù)字8的手寫筆跡圖像

圖2數(shù)字8的文本文件

一般情況下，測試集是普通的二進制圖像文件，多數(shù)情況下，圖像尺寸不可能剛剛為32×32像素，而且圖像的上下左右都可能有空白，與訓(xùn)練集的特征不符合，因此在識別的開始階段，需要將圖像文件的有效部分轉(zhuǎn)換為訓(xùn)練集格式的32×32文本文件(否則會大大降低識別精度)，進而轉(zhuǎn)換為1×1 024的特征向量.

2 手寫圖像轉(zhuǎn)換為訓(xùn)練集的算法

2.1 圖像轉(zhuǎn)換為二值數(shù)組(img2Array)

首先，需要將灰度圖像轉(zhuǎn)換為只有0與1數(shù)字的“數(shù)組1”，數(shù)組1的尺寸與圖像尺寸一樣大.該算法的函數(shù)是img2Array.算法的關(guān)鍵是根據(jù)圖像的像素值把數(shù)組對應(yīng)坐標的值設(shè)置為0或1，此根據(jù)像素的亮度值(brightness)來定.式(1)與式(2)都可以確定亮度值，

brightness=red×0.3333+green×0.3333+

blue×0.3333

(1)

brightness=red×0.299+green×0.587+

blue×0.114

(2)

brightness值的范圍是[0,255]，所以，brightness<127時認為是黑色的筆跡，對應(yīng)坐標的數(shù)組值設(shè)置為1，否則設(shè)置為0.

其次，需要去掉“數(shù)組1”的上下與左右的空白行，只留下有效的“凈”數(shù)字數(shù)據(jù)，這樣就生成了“數(shù)組2”.事實上，數(shù)組2的尺寸仍然不是32×32的標準測試集尺寸.數(shù)字圖像的二值化如圖3所示.

圖3數(shù)字圖像的二值化

2.2 數(shù)組2縮放為長寬一致的數(shù)組3

假設(shè)“數(shù)組2”高度大于寬度，由于測試集高度與寬度相等，所以必須擴展數(shù)組2的寬度，使其等于高度.具體方法為，首先生成1個全0的數(shù)組3，高度和寬度都等于數(shù)組2的高度，然后將數(shù)組2的值復(fù)制到數(shù)組3的中間，結(jié)果如圖4所示.

2.3 數(shù)組3縮放為數(shù)組4(32×32的標準測試集)

“數(shù)組3”是高度和寬度相同的二維數(shù)組，但卻不是32×32的.測試集要求是32×32的數(shù)組，所以需要新生成1個32×32的全0數(shù)組4，然后設(shè)置數(shù)組4中每個的數(shù)值，結(jié)果如圖5所示.

圖4生成長寬一致的數(shù)組3

圖5數(shù)組3通過卷積算法變換為數(shù)組4

不失一般性，為了簡化描述，假設(shè)數(shù)組3的尺寸是(17,8)，數(shù)組4的尺寸是(5，3)，如圖6所示，計算數(shù)組4中每個點的值.

假設(shè)數(shù)組4中P4點的坐標是(row,col)=(1,2)，即第2行，第3列，則數(shù)組P4點的值是0還是1呢？對此，本研究利用卷積法(見圖6)，即用數(shù)組3的1個區(qū)域的平均值匯總為P4點的值.

圖6卷積算法示意圖

首先，計算2個方向的比例，

rateH =w3/w4=17/4=3.4，

rateV=h3/h4=8/3=2.6666

(3)

然后，計算數(shù)組3區(qū)域的起點坐標，

startH=(col×3.4)下取整=7

(4)

startV=(row×rateV)下取整=2

(5)

最后，計算數(shù)組3區(qū)域的終點坐標，

endH=(startH+rateH)上取整=11

(6)

endV=(startV+rateV)上取整=6

(7)

有了數(shù)組3區(qū)域(灰色區(qū)域)之后，就可以求出該子區(qū)域的平均數(shù).如果平均數(shù)≥0.5，則數(shù)組4中的P4點的值為1，否則為0.

3 算法實現(xiàn)與測試

本算法在測試時，首先通過Python編程實驗，選取了1 936個訓(xùn)練集數(shù)字圖像[3]，并對1 000個手寫數(shù)字進行了識別.測試結(jié)果表明，正確率大于95%.由于實驗中采用了連續(xù)數(shù)字，而不是單個數(shù)字，因而更貼近實際應(yīng)用.對于連續(xù)數(shù)字，只需要根據(jù)數(shù)字之間的空行和空列將數(shù)字圖像分開，再分別識別即可.圖7是6組數(shù)字的識別實驗結(jié)果.從測試結(jié)果看，只錯了1個數(shù)字，8識別成了3.

4 結(jié) 語

基于KNN算法的數(shù)字識別準確率依賴于訓(xùn)練集規(guī)模及訓(xùn)練集和測試集的相似度，訓(xùn)練集圖像越多，訓(xùn)練集與測試集相似度越高，識別率就越高[5].數(shù)字識別算法的評判指標之一是識別速度，而KNN算法的識別速度也與訓(xùn)練集規(guī)模有關(guān)，訓(xùn)練集越多，識別速度越慢.事實上，若要高的識別準確率，就必須有大量的測試集圖像，而若要快速的識別速度，又不能有太多的測試集圖像.因此，在實際應(yīng)用中，通常采用折中的辦法，即，取合適的訓(xùn)練集數(shù)量，同時使用速度更快的硬件設(shè)備，以此來滿足實際需求.

圖7連續(xù)手寫數(shù)字識別效果

[1]田紹興,陳勁杰. 基于KNN的手寫數(shù)字的識別[J].農(nóng)業(yè)裝備與車輛工程,2017,55(10):96-98.

[2]Harrington P.機器學(xué)習(xí)實戰(zhàn)[M].李銳，李鵬，曲亞東，等譯.北京:人民郵電出版社,2011.

[3]趙永科.深度學(xué)習(xí)21天實戰(zhàn)[M].北京：電子工業(yè)出版社,2016.

[4]Sebastiani F.Machinelearninginautomatedtextcatagorizaition[J].ACM Comput Surv,2002,31(2):1-17.

[5]李志榮,楊丹,周奇.基于模板匹配的脫機手寫數(shù)字識別研究[J].哈爾濱師范大學(xué)學(xué)報(自然科學(xué)版),2009,25(4):86-95.

ResearchonHandwrittenNumeralRecognitionBasedonKNNAlgorithm

ZHAOWeidong1,2,LIUYonghong1,2,YANTao1,2,YUXi1,2

(1.Key Laboratory of Pattern Recognition and Intelligent Information Processing of Sichuan Province，Chengdu University, Chengdu 610106,China;

2.School of Information Science and Engineering, Chengdu University, Chengdu 610106, China)

When KNN algorithm is used for handwritten numeral recognition,it is necessary to combine the handwritten numeral images(test set) to be recognized with the known handwritten numeral images(training set) to find the shortest distance between vectors,so that we can identify the classification of digital images to be recognized.This paper designs a transformation method that transforms the data and size of the test set into a completely similar image to the training set.Based on that,the test set and training set are transformed into one-dimensional vectors with the same number of columns, and then the distance between vectors is obtained.Finally,the algorithm is verified by writing Python program.Experimental results show that the correct recognition rate of handwritten digital images can reach over 95%.

KNN;python;training set;test set

TP391.43

A

1004-5422(2017)04-0382-03

2017-11-23.

四川省科技廳軟件科學(xué)研究計劃(2017ZR0198)、 四川省科技廳應(yīng)用基礎(chǔ)計劃(2016JY0255)資助項目.

趙衛(wèi)東(1968 — )，男，碩士，副教授，從事軟件工程與模式識別研究.