基于KNN算法的手写数字识别研究

赵卫东，刘永红，鄢 涛，于 曦

(1.成都大学 模式识别与智能信息处理四川省高校重点实验室，四川 成都 610106;2.成都大学 信息科学与工程学院，四川 成都 610106)

基于KNN算法的手写数字识别研究

赵卫东1,2，刘永红1,2，鄢 涛1,2，于 曦1,2

(1.成都大学 模式识别与智能信息处理四川省高校重点实验室，四川 成都 610106;2.成都大学 信息科学与工程学院，四川 成都 610106)

KNN算法用于手写数字识别的时候，需要将待识别的手写数字图像(测试集)与一些已知的手写数字图像(训练集)联合在一起求向量之间的最短距离，才能判断待识别数字图像的分类.设计了一种将测试集图像中的数据与尺寸转换为与训练集图像完全相似的转换算法，并在此基础上，将测试集和训练集都转换成有相同列数量的一维向量，进而求出向量之间的距离，并通过编写Python程序对该算法进行了验证.测试结果表明，该方法对手写数字图像的正确识别率能够达到95%以上.

KNN;Python;训练集;测试集

0 引 言

KNN算法也称K近邻算法(K-nearest neighbor,KNN)，是一种基本分类与回归方法，也是手写数字识别的基础算法之一[1-3].在实际应用中，KNN算法的输入为实例的特征向量，对应于特征空间的点，输出为实例的类别.KNN算法假设已经准备好1个训练数据集，其中每个实例的类别是预先指定的.分类时，对新的实例(测试数据集)，根据K个最近邻的训练实例的类别，通过多数表决等方式进行预测.K值的选择、距离度量及分类决策规则是KNN算法的3个基本元素[4].在通常情况下，训练集图像是已经剪裁成统一规格且四周没有空白空间的二值化图像，而测试集可以是任意图像，不能直接与训练集进行比较.目前，针对图像转换方面的研究比较少，对此，本研究设计了一种将测试集的数据转换为与训练集相同规格的数据的算法.

1 训练集和测试集

不失一般性，假设训练集是由多个文本文件组成的集合，每个文件表示1个已知的数字(0～9)，每个文件的格式是1个32×32的文本文件.文件中的0表示白色，是底色；1表示黑色，是数字的笔迹.图1、图2分别为数字8的手写笔迹图像与文本文件.

尽管采用文本格式存储图像不能有效地利用内存空间，但为了方便理解，还是应将图像转换为文本格式[2].在实际识别算法中，需要将每个文件的32行按首尾顺序连接，合并为1行，形成1个1×1 024的特征向量.训练集的主要特点是，由于数字的高度通常大于宽度，所以有些数字左右两边需要用全0的列填充，数字1构成的形状处于图像的横向正中间，训练集的上下部分没有空白区域.

图1数字8的手写笔迹图像

图2数字8的文本文件

一般情况下，测试集是普通的二进制图像文件，多数情况下，图像尺寸不可能刚刚为32×32像素，而且图像的上下左右都可能有空白，与训练集的特征不符合，因此在识别的开始阶段，需要将图像文件的有效部分转换为训练集格式的32×32文本文件(否则会大大降低识别精度)，进而转换为1×1 024的特征向量.

2 手写图像转换为训练集的算法

2.1 图像转换为二值数组(img2Array)

首先，需要将灰度图像转换为只有0与1数字的“数组1”，数组1的尺寸与图像尺寸一样大.该算法的函数是img2Array.算法的关键是根据图像的像素值把数组对应坐标的值设置为0或1，此根据像素的亮度值(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时认为是黑色的笔迹，对应坐标的数组值设置为1，否则设置为0.

其次，需要去掉“数组1”的上下与左右的空白行，只留下有效的“净”数字数据，这样就生成了“数组2”.事实上，数组2的尺寸仍然不是32×32的标准测试集尺寸.数字图像的二值化如图3所示.

图3数字图像的二值化

2.2 数组2缩放为长宽一致的数组3

假设“数组2”高度大于宽度，由于测试集高度与宽度相等，所以必须扩展数组2的宽度，使其等于高度.具体方法为，首先生成1个全0的数组3，高度和宽度都等于数组2的高度，然后将数组2的值复制到数组3的中间，结果如图4所示.

2.3 数组3缩放为数组4(32×32的标准测试集)

“数组3”是高度和宽度相同的二维数组，但却不是32×32的.测试集要求是32×32的数组，所以需要新生成1个32×32的全0数组4，然后设置数组4中每个的数值，结果如图5所示.

图4生成长宽一致的数组3

图5数组3通过卷积算法变换为数组4

不失一般性，为了简化描述，假设数组3的尺寸是(17,8)，数组4的尺寸是(5，3)，如图6所示，计算数组4中每个点的值.

假设数组4中P4点的坐标是(row,col)=(1,2)，即第2行，第3列，则数组P4点的值是0还是1呢？对此，本研究利用卷积法(见图6)，即用数组3的1个区域的平均值汇总为P4点的值.

图6卷积算法示意图

首先，计算2个方向的比例，

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

rateV=h3/h4=8/3=2.6666

(3)

然后，计算数组3区域的起点坐标，

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

(4)

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

(5)

最后，计算数组3区域的终点坐标，

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

(6)

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

(7)

有了数组3区域(灰色区域)之后，就可以求出该子区域的平均数.如果平均数≥0.5，则数组4中的P4点的值为1，否则为0.

3 算法实现与测试

本算法在测试时，首先通过Python编程实验，选取了1 936个训练集数字图像[3]，并对1 000个手写数字进行了识别.测试结果表明，正确率大于95%.由于实验中采用了连续数字，而不是单个数字，因而更贴近实际应用.对于连续数字，只需要根据数字之间的空行和空列将数字图像分开，再分别识别即可.图7是6组数字的识别实验结果.从测试结果看，只错了1个数字，8识别成了3.

4 结 语

基于KNN算法的数字识别准确率依赖于训练集规模及训练集和测试集的相似度，训练集图像越多，训练集与测试集相似度越高，识别率就越高[5].数字识别算法的评判指标之一是识别速度，而KNN算法的识别速度也与训练集规模有关，训练集越多，识别速度越慢.事实上，若要高的识别准确率，就必须有大量的测试集图像，而若要快速的识别速度，又不能有太多的测试集图像.因此，在实际应用中，通常采用折中的办法，即，取合适的训练集数量，同时使用速度更快的硬件设备，以此来满足实际需求.

图7连续手写数字识别效果

[1]田绍兴,陈劲杰. 基于KNN的手写数字的识别[J].农业装备与车辆工程,2017,55(10):96-98.

[2]Harrington P.机器学习实战[M].李锐，李鹏，曲亚东，等译.北京:人民邮电出版社,2011.

[3]赵永科.深度学习21天实战[M].北京：电子工业出版社,2016.

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

[5]李志荣,杨丹,周奇.基于模板匹配的脱机手写数字识别研究[J].哈尔滨师范大学学报(自然科学版),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.

四川省科技厅软件科学研究计划(2017ZR0198)、 四川省科技厅应用基础计划(2016JY0255)资助项目.

赵卫东(1968 — )，男，硕士，副教授，从事软件工程与模式识别研究.