1. KNN原理

K最近鄰(kNN窗骑，k-NearestNeighbor)分類算法是一個理論上比較成熟的方法廉侧，也是最簡單的機器學(xué)習算法之一遭垛。所謂K最近鄰，就是k個最近的鄰居的意思姓惑，說的是每個樣本都可以用它最接近的k個鄰居來代表。

該方法的具體思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別按脚，則該樣本也屬于這個類別于毙。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象辅搬。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別唯沮。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時堪遂，只與極少量的相鄰樣本有關(guān)介蛉。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的溶褪，因此對于類域的交叉或重疊較多的待分樣本集來說币旧，KNN方法較其他方法更為適合。

簡單點說就是猿妈，有一個向量化的樣本庫吹菱，每個樣本都有一個標簽標識類別，輸入一個未知分類的樣本彭则，向量化之后跟樣本庫一一比對計算方差鳍刷，取方差最小的topN的樣本庫的樣本的分類標簽，用這N個標簽的類別代表輸入樣本的類別贰剥。

下面以一個驗證碼識別的案例詳細說明一下KNN的使用倾剿。

2.案例

Fig.1 驗證碼圖片示例

• 1）橫穿圖像的條形線條大部分貫穿字符坯癣；
• 2）圖像中心位置有高頻噪聲（近似椒鹽噪聲）瓶盛；
• 3）不同圖像字符起始位置不一致，需要動態(tài)定位示罗；
• 4）字符之前黏連惩猫、傾斜，不好分割蚜点；
• 5）相同字符字體不一致轧房，類似于手寫字體

要想利用KNN對Fig.1中的字符進行識別，首先需要克服以上的困難绍绘，對字符進行正確分割處理奶镶。這需要一些圖像處理的知識迟赃，圖像的計算其實就是矩陣的計算，有一定數(shù)學(xué)功底的同學(xué)稍微搜索一下原理就能很容易的理解下面將要介紹的內(nèi)容厂镇。

本文所有的實驗圖像和代碼均已提交到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.圖像形態(tài)學(xué)處理

為了能更清晰的識別字符，我們首先對圖像進行去噪并做二值化處理捺信。

Fig.2 圖像形態(tài)學(xué)處理

通過簡單裁切處理可以去掉一部分圖像開始和結(jié)尾的噪聲（如Fig.2中的圖1）酌媒。

分別用OTSU和高斯自適應(yīng)對圖像進行二值化后，我們發(fā)現(xiàn)二值化之后的圖像有很多麻點（Fig.2中的圖3和圖5）迄靠，這是因為原始圖像中有很多高頻的噪聲馍佑，需要首先去噪處理，我們選用高斯模糊（Fig.2中 圖2）梨水。高斯模糊之后再做二值化拭荤，可以看到圖像中的麻點消失了（Fig.2 中圖4和圖6）。

通過對比Fig.2中圖4和圖6我們發(fā)現(xiàn)疫诽，OTSU的二值化結(jié)果字符有很多細節(jié)丟失了舅世，而高斯自適應(yīng)二值化很好的保留了字符的細節(jié)，所以我們選擇高斯自適應(yīng)二值化算法奇徒。

二值化之后雏亚，水平方向橫穿整幅圖像的線條噪聲也保留了下來，所以我們需要把它去除掉摩钙，因為這條線特征比較明顯罢低，大部分是水平的辛慰，且穿過字符的部分比較細探熔，所以我們用[2*1]的算子對二值化之后的圖像做腐蝕運算燕垃，去掉水平噪聲（Fig.2中圖7）裹纳。水平噪聲雖然去掉了岔擂，但是有些字符的橫線也被腐蝕了棚潦，下面再用[2*2]的算子對圖像進行膨脹運算棺棵，得到比較飽滿的字符圖像（Fig.2中圖8）毫别。為啥選擇[2*1]和[2*2]的算子身弊，這些都是通過大量實驗得到的辟汰，有興趣的同學(xué)可以自己試驗一下，沒準能找到去噪更好的算子阱佛。

總結(jié)一下上面說的帖汞，為了得到清晰的去噪的字符二值化圖像，我們先后對圖像進行的操作為：簡單裁切 -> 高斯模糊 -> 高斯自適應(yīng)二值化 -> 垂直方向腐蝕 -> 膨脹 凑术。Fig.2中圖8為二值化最終的結(jié)果翩蘸。

形態(tài)學(xué)處理的代碼不多，直接上代碼供大家參考：
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定位

由于字符在圖像中的開始和結(jié)束位置是隨機的麦萤，我們不能通過固定的裁切獲取到ROI（region of interest鹿鳖，感興趣區(qū)域）圖像扁眯。所以需要對ROI進行定位。

現(xiàn)在我們已經(jīng)獲取了去噪之后的二值化圖像翅帜，現(xiàn)在需要精確定位字符所在的位置姻檀。我們采用像素投影的方法實現(xiàn)，步驟：
1）統(tǒng)計非0像素點個數(shù)在x軸方向投影涝滴，生成直方圖绣版；
2）利用滑動窗口對直方圖平滑去噪；
3）設(shè)置兩個指針分別從直方圖左和右進行計算歼疮，滿足閾值的位置設(shè)為ROI起始點杂抽；
4）對圖像進行裁切得到ROI圖像

Fig.3 ROI定位

這部分的代碼也比較簡單，有興趣的同學(xué)可以嘗試一下：
https://github.com/CarsonCao/knnCodeRecognition/blob/master/src/study/04_getROI.ipynb

2.4. 字符分割

在進行字符識別之前韩脏，還有一個很重要的工作缩麸，就是要對字符進行分割，另外我們只是對水平方向進行了ROI定位赡矢，垂直方向還需要在字符分割出來之后再針對單個字符進行精確定位杭朱。

Fig.4 字符黏連傾斜

字符有很多黏連和傾斜的情況，所以想要對字符分割不是很容易吹散。我們采用能量累加的方式進行計算弧械。我們可以將二值圖像的每個像素點看做是一個能量點，白色區(qū)域是能量高的區(qū)域空民，黑色為能量低的區(qū)域刃唐，我們需要在兩個字符之間尋找一條能量最小的像素細縫，能夠?qū)蓚€字符分割開來界轩。

Fig.5 能量累加矩陣

如Fig.5 所示画饥，用V(i,j)表示每個像素點的能量，初始化為對應(yīng)二值圖像的像素值耸棒。用E(i,j)表示累加能量荒澡。

利用上述原理，我們可以實現(xiàn)針對輕度黏連字符或者傾斜字符的分割袒啼。Fig.6和Fig.7對尋找最小能量細縫的過程進行了舉例說明哈扮。

Fig.6 一幅含有5和2數(shù)字的二值圖像

Fig.7 尋找最小累加能量細縫的過程

Fig.8字符分割

Fig.9字符標準化處理

2.5.字符標注

將分割好的字符進行分類整理，放入以字符命名的對應(yīng)文件夾中豺旬。這樣我們就建好了一個有標簽的樣本庫（也有叫訓(xùn)練庫）钠惩。

Fig.10

Fig.11

2.3.KNN分類

將樣本庫中的圖像向量化，輸入未知圖像族阅，依次做如下操作：
簡單裁切 -> 高斯模糊 -> 高斯自適應(yīng)二值化 -> 垂直方向腐蝕 -> 膨脹 -> ROI定位 -> 能量累加矩陣分割字符 -> 字符標準化 -> 字符向量化 -> 與樣本庫一一比對得到最相近topN的標簽 -> 輸出各個字符的分類結(jié)果

Fig.12圖像向量化

收集了2300個分割之后的字符圖像篓跛，分別按照3比1設(shè)置樣本庫和測試庫，識別成功率在98%以上坦刀。輸入原始圖像進行識別愧沟，成功率在60%~70%之間。因為原始圖像還需要對字符進行去噪分割鲤遥，這部分準確度沒有字符識別高沐寺。
最終的驗證碼識別代碼：
https://github.com/CarsonCao/knnCodeRecognition/tree/master/src/verificationCode_recognition