1. KNN原理

K最近邻(kNN，k-NearestNeighbor)分类算法是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。

该方法的具体思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

简单点说就是，有一个向量化的样本库，每个样本都有一个标签标识类别，输入一个未知分类的样本，向量化之后跟样本库一一比对计算方差，取方差最小的topN的样本库的样本的分类标签，用这N个标签的类别代表输入样本的类别。

下面以一个验证码识别的案例详细说明一下KNN的使用。

2.案例

Fig.1 验证码图片示例

• 1）横穿图像的条形线条大部分贯穿字符；
• 2）图像中心位置有高频噪声（近似椒盐噪声）；
• 3）不同图像字符起始位置不一致，需要动态定位；
• 4）字符之前黏连、倾斜，不好分割；
• 5）相同字符字体不一致，类似于手写字体

要想利用KNN对Fig.1中的字符进行识别，首先需要克服以上的困难，对字符进行正确分割处理。这需要一些图像处理的知识，图像的计算其实就是矩阵的计算，有一定数学功底的同学稍微搜索一下原理就能很容易的理解下面将要介绍的内容。

本文所有的实验图像和代码均已提交到github中，项目所在位置：https://github.com/CarsonCao/knnCodeRecognition

2.1.准备工作

python版本：
python 3.5+
安装pip3：
sudo apt-get install -y python3-pip
安装opencv：
pip3 install opencv-python
安装numpy：
pip3 install numpy
安装matplotlib：
pip3 install matplotlib
安装jupyter：
sudo pip3 install jupyter

2.2.图像形态学处理

为了能更清晰的识别字符，我们首先对图像进行去噪并做二值化处理。

Fig.2 图像形态学处理

通过简单裁切处理可以去掉一部分图像开始和结尾的噪声（如Fig.2中的图1）。

分别用OTSU和高斯自适应对图像进行二值化后，我们发现二值化之后的图像有很多麻点（Fig.2中的图3和图5），这是因为原始图像中有很多高频的噪声，需要首先去噪处理，我们选用高斯模糊（Fig.2中 图2）。高斯模糊之后再做二值化，可以看到图像中的麻点消失了（Fig.2 中图4和图6）。

通过对比Fig.2中图4和图6我们发现，OTSU的二值化结果字符有很多细节丢失了，而高斯自适应二值化很好的保留了字符的细节，所以我们选择高斯自适应二值化算法。

二值化之后，水平方向横穿整幅图像的线条噪声也保留了下来，所以我们需要把它去除掉，因为这条线特征比较明显，大部分是水平的，且穿过字符的部分比较细，所以我们用[2*1]的算子对二值化之后的图像做腐蚀运算，去掉水平噪声（Fig.2中图7）。水平噪声虽然去掉了，但是有些字符的横线也被腐蚀了，下面再用[2*2]的算子对图像进行膨胀运算，得到比较饱满的字符图像（Fig.2中图8）。为啥选择[2*1]和[2*2]的算子，这些都是通过大量实验得到的，有兴趣的同学可以自己试验一下，没准能找到去噪更好的算子。

总结一下上面说的，为了得到清晰的去噪的字符二值化图像，我们先后对图像进行的操作为：简单裁切 -> 高斯模糊 -> 高斯自适应二值化 -> 垂直方向腐蚀 -> 膨胀 。Fig.2中图8为二值化最终的结果。

形态学处理的代码不多，直接上代码供大家参考：
https://github.com/CarsonCao/knnCodeRecognition/blob/master/src/study/03_threshold.ipynb

import cv2      
import numpy as np 
import matplotlib.pyplot as plt  
import os

def imgThreshold(img, num):

    height, width = img.shape

    img_seg = img[8:height,40:width-40]

    ##图像二值化##
    # Gaussian模糊去噪
    blur = cv2.GaussianBlur(img_seg,(5,5),0)

    # Otsu's threholding without gaussian blur
    ret1,th1 = cv2.threshold(img_seg,0,255,cv2.THRESH_BINARY_INV+cv2.THRESH_OTSU)

    # Otsu's threholding with gaussian blur
    ret2,th2 = cv2.threshold(blur,0,255,cv2.THRESH_BINARY_INV+cv2.THRESH_OTSU)

    # gaussian adaptiveThreshold without gaussian blur
    th3 = cv2.adaptiveThreshold(img_seg,255,cv2.ADAPTIVE_THRESH_GAUSSIAN_C,\
                cv2.THRESH_BINARY_INV,11,3)

    # gaussian adaptiveThreshold with gaussian blur
    th4 = cv2.adaptiveThreshold(blur,255,cv2.ADAPTIVE_THRESH_GAUSSIAN_C,\
                cv2.THRESH_BINARY_INV,11,3)

    # 垂直方向腐蚀
    kernel = np.ones((2,1),np.uint8)
    erosion = cv2.erode(th4,kernel,iterations = 3)
    
   #膨胀
    kernel2 = np.ones((2,2),np.uint8)
    dilation = cv2.dilate(erosion,kernel2,iterations = 1)
    
    # plot images
    #     plt.subplot(5,1,1),plt.imshow(img_seg,'gray')
    #     plt.title(''), plt.xticks([]), plt.yticks([])
    #     plt.show()

    # saving result
    cv2.imwrite("../../images/study/threshold/" + str(num) + "_1_chop.jpg", img_seg, [int(cv2.IMWRITE_JPEG_QUALITY), 100])  
    cv2.imwrite("../../images/study/threshold/" + str(num) + "_2_blur.jpg", blur, [int(cv2.IMWRITE_JPEG_QUALITY), 100])  
    cv2.imwrite("../../images/study/threshold/" + str(num) + "_3_otsu.jpg", th1, [int(cv2.IMWRITE_JPEG_QUALITY), 100])  
    cv2.imwrite("../../images/study/threshold/" + str(num) + "_4_otsu_blur.jpg", th2, [int(cv2.IMWRITE_JPEG_QUALITY), 100])  
    cv2.imwrite("../../images/study/threshold/" + str(num) + "_5_gauss.jpg", th3, [int(cv2.IMWRITE_JPEG_QUALITY), 100])  
    cv2.imwrite("../../images/study/threshold/" + str(num) + "_6_gauss_blur.jpg", th4, [int(cv2.IMWRITE_JPEG_QUALITY), 100])  
    cv2.imwrite("../../images/study/threshold/" + str(num) + "_7_erosion.jpg", erosion, [int(cv2.IMWRITE_JPEG_QUALITY), 100]) 
    cv2.imwrite("../../images/study/threshold/" + str(num) + "_8_dilation.jpg", dilation, [int(cv2.IMWRITE_JPEG_QUALITY), 100]) 


if __name__ == '__main__': 
    for i in range(0,10):
        file =  "../../images/study/input/"+str(i)+".jpg"
        if not os.path.exists(file):
            continue
        img = cv2.imread(file, 0)  #直接读取成灰度图片
        imgThreshold(img, i)

2.3.ROI定位

由于字符在图像中的开始和结束位置是随机的，我们不能通过固定的裁切获取到ROI（region of interest，感兴趣区域）图像。所以需要对ROI进行定位。

现在我们已经获取了去噪之后的二值化图像，现在需要精确定位字符所在的位置。我们采用像素投影的方法实现，步骤：
1）统计非0像素点个数在x轴方向投影，生成直方图；
2）利用滑动窗口对直方图平滑去噪；
3）设置两个指针分别从直方图左和右进行计算，满足阈值的位置设为ROI起始点；
4）对图像进行裁切得到ROI图像

Fig.3 ROI定位

这部分的代码也比较简单，有兴趣的同学可以尝试一下：
https://github.com/CarsonCao/knnCodeRecognition/blob/master/src/study/04_getROI.ipynb

2.4. 字符分割

在进行字符识别之前，还有一个很重要的工作，就是要对字符进行分割，另外我们只是对水平方向进行了ROI定位，垂直方向还需要在字符分割出来之后再针对单个字符进行精确定位。

Fig.4 字符黏连倾斜

字符有很多黏连和倾斜的情况，所以想要对字符分割不是很容易。我们采用能量累加的方式进行计算。我们可以将二值图像的每个像素点看做是一个能量点，白色区域是能量高的区域，黑色为能量低的区域，我们需要在两个字符之间寻找一条能量最小的像素细缝，能够将两个字符分割开来。

Fig.5 能量累加矩阵

如Fig.5 所示，用V(i,j)表示每个像素点的能量，初始化为对应二值图像的像素值。用E(i,j)表示累加能量。

利用上述原理，我们可以实现针对轻度黏连字符或者倾斜字符的分割。Fig.6和Fig.7对寻找最小能量细缝的过程进行了举例说明。

Fig.6 一幅含有5和2数字的二值图像

Fig.7 寻找最小累加能量细缝的过程

Fig.8字符分割

Fig.9字符标准化处理

2.5.字符标注

将分割好的字符进行分类整理，放入以字符命名的对应文件夹中。这样我们就建好了一个有标签的样本库（也有叫训练库）。

Fig.10

Fig.11

2.3.KNN分类

将样本库中的图像向量化，输入未知图像，依次做如下操作：
简单裁切 -> 高斯模糊 -> 高斯自适应二值化 -> 垂直方向腐蚀 -> 膨胀 -> ROI定位 -> 能量累加矩阵分割字符 -> 字符标准化 -> 字符向量化 -> 与样本库一一比对得到最相近topN的标签 -> 输出各个字符的分类结果

Fig.12图像向量化

收集了2300个分割之后的字符图像，分别按照3比1设置样本库和测试库，识别成功率在98%以上。输入原始图像进行识别，成功率在60%~70%之间。因为原始图像还需要对字符进行去噪分割，这部分准确度没有字符识别高。
最终的验证码识别代码：
https://github.com/CarsonCao/knnCodeRecognition/tree/master/src/verificationCode_recognition