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

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

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

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

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

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

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

0 引 言

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

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

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

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

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

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

一般情況下，測(cè)試集是普通的二進(jìn)制圖像文件，多數(shù)情況下，圖像尺寸不可能剛剛為32×32像素，而且圖像的上下左右都可能有空白，與訓(xùn)練集的特征不符合，因此在識(shí)別的開始階段，需要將圖像文件的有效部分轉(zhuǎn)換為訓(xùn)練集格式的32×32文本文件(否則會(huì)大大降低識(shí)別精度)，進(jìn)而轉(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ù)組對(duì)應(yīng)坐標(biāo)的值設(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時(shí)認(rèn)為是黑色的筆跡，對(duì)應(yīng)坐標(biāo)的數(shù)組值設(shè)置為1，否則設(shè)置為0.

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

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

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

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

2.3 數(shù)組3縮放為數(shù)組4(32×32的標(biāo)準(zhǔn)測(cè)試集)

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

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

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

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

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

圖6卷積算法示意圖

首先，計(jì)算2個(gè)方向的比例，

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

rateV=h3/h4=8/3=2.6666

(3)

然后，計(jì)算數(shù)組3區(qū)域的起點(diǎn)坐標(biāo)，

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

(4)

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

(5)

最后，計(jì)算數(shù)組3區(qū)域的終點(diǎn)坐標(biāo)，

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

(6)

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

(7)

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

3 算法實(shí)現(xiàn)與測(cè)試

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

4 結(jié) 語

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

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

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

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

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

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

[5]李志榮,楊丹,周奇.基于模板匹配的脫機(jī)手寫數(shù)字識(shí)別研究[J].哈爾濱師范大學(xué)學(xué)報(bào)(自然科學(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é)研究計(jì)劃(2017ZR0198)、 四川省科技廳應(yīng)用基礎(chǔ)計(jì)劃(2016JY0255)資助項(xiàng)目.

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