欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

KNN实现手写数字识别

程序员文章站 2024-03-07 20:45:13
...

KNN简介

    物以类聚,人以群分就是KNN的算法的宗旨,要辨识一个人大概是社么样的人,可以从他的朋友圈入手,看他的盆友圈属于哪种类型(和哪种类型的盆友圈最接近,比如经常去夜店的二代、老实的码农、像我这样帅的人)就可以大致判断他也属于该类型的人。KNN就是将未知样本和已知样本集合进行比较,比较未知样本和所有已知样本的接近程度进行排序,最后提取前K个最接近的样本,看在这K个样本中哪种几何所占的比例最高,就将该未知样本归纳到该集合中。这里的K就是KNN的K的意思,NN不是指神经网络,而是最近邻(k-NearestNeighbor)。

手写数字识别

    功能就不BB了,直接看效果图,就知道实现的是啥功能了,如下图:

KNN实现手写数字识别

开发环境

    Windows10 + VS2013 + Qt580 + OpenCV300

主要代码

训练过程
// 载入样本
Mat digitsSet = imread("digits.png");
Mat gray;
cvtColor(digitsSet, gray, CV_BGR2GRAY);
threshold(gray, gray, 0, 255, CV_THRESH_BINARY);
// digits.png为2000 * 1000,其中每个数字的大小为20 * 20,
// 总共有5000((2000*1000) / (20*20))个数字,类型为[0~9],
// [0~9]10个数字每个数字有5000/10 = 500个样本
// 对其分割成单个20 * 20的图像并序列化成(转化成一个一维的数组)
int side = 20;
int m = gray.rows / side;
int n = gray.cols / side;	
Mat data, labels;			
for (int i = 0; i < m; i++){

	int offsetRow = i * side;				
	for (int j = 0; j < n; j++){

		int offsetCol = j * side;		
		// 截取20*20的小块
		Mat tmp;
		gray(Range(offsetRow, offsetRow + side), Range(offsetCol, offsetCol + side)).copyTo(tmp);
		data.push_back(tmp.reshape(0, 1));  // 序列化转换成一个一维向量
		labels.push_back(i / 5);			// 每500个为一个label类型			
	}
}
data.convertTo(data, CV_32F);	

// 使用KNN算法训练
int K = 51;	// 改变K值可能会出现不同的效果,K值越大,识别速度越慢
Ptr<TrainData> tData = TrainData::create(data, ROW_SAMPLE, labels);
model = KNearest::create();
model->setDefaultK(K);
model->setIsClassifier(true);
model->train(tData);
识别过程
Mat zoom;
// 缩放手写图像到20*20,因为UI上的手写板我布局成200*200,所以需要缩小到原来的0.1倍
// frame初始化为灰度图像,并且只有0和255这两个像素值,就是二值图
zoom = zoomImage(0.1, frame);	
// 序列化	
Mat reshapeImage = zoom.reshape(0, 1);
reshapeImage.convertTo(reshapeImage, CV_32F);
// 开始用KNN预测分类,返回识别结果
float r = model->predict(reshapeImage);

注:digits.png是opencv提供的手写数字样本集合,训练代码中的data的每一行都是样本数字的序列,总共有5000个数字图像, 每个数字为20*20=400的序列,所以data就是一个400*5000的矩阵。digits.png和data矩阵如下两图所示:

KNN实现手写数字识别

KNN实现手写数字识别

总结

    KNN实现比较简单,而且不需要训练,特定场合下精度也过得去。但是其计算量特别大,每次识别都要和所有的样本进行对比,如果样本量很多的化,其计算量就不忍直视了,而且比如本功能就需要未知样本的图像和已知样本的图像一样大小(只能识别20*20的图像),要对比较大的图像进行缩小,缩小就是失真,而且是通过空间距离来比较的,这就有很大问题了,比如吧数字写的和已知样本的数字大小差异比较大,几乎是识别不了的。

优化

    1、不通过空间距离来排序前K个最优样本,通过轮廓匹配的相似度来排序前K个最优样本,因为轮廓匹配有尺度和旋转不变的特点,所以可以降低图像大小不一致,图像发生旋转匹配错误的概率。2.给前K个最优样本加权重,就是最好的样本权重为1,第二个开始依次减低权重%10。

主要代码(自己建立KNN训练和识别过程)

Knn4Digits.h
#include <opencv2/opencv.hpp>
#include <opencv2/highgui/highgui.hpp>  
#include <opencv2/imgproc/imgproc.hpp>  
#include <opencv2/core/core.hpp> 
#include <opencv2/features2d/features2d.hpp>
#include <opencv2/flann/flann.hpp>
#include <opencv.hpp>
#include <opencv2/ml/ml.hpp>

using namespace std;
using namespace cv;

class Knn4Digits
{
public:
	Knn4Digits();
	~Knn4Digits();

	// 训练
	bool train(vector<vector<Point>> _data, vector<int> _label);
	// 预测
	int predict(vector<Point> _samples);
	// 设置K值
	void setK(int _k){ k = _k; }

private:
	int k;
	// 训练数据集合,这里为digits.png中所有数字的最大外轮廓的点集的集合
	vector<vector<Point>> data;	
	// 轮廓的标签
	vector<int> label;
};
Knn4Digits.cpp
#include "Knn4Digits.h"

Knn4Digits::Knn4Digits(){

	setK(5);
}

Knn4Digits::~Knn4Digits(){

}

bool Knn4Digits::train(vector<vector<Point>> _data, vector<int> _label){

	if (_data.size() == 0 || _label.size() == 0 || _data.size() != _label.size()) 
		return false;
	data	= _data;	// 载入样本轮廓点集
	label	= _label;	// 载入轮廓标签
	return true;
}

int Knn4Digits::predict(vector<Point> _samples){

	vector<double> rVec;
	rVec.clear();
	double vote[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
	for (int i = 0; i < data.size(); i++){

		// 进行轮廓匹配 
		// r越小(接近于0)代表月匹配
		double r = matchShapes(_samples, data[i], CV_CONTOURS_MATCH_I3, 1.0); 
		// 保存未知轮廓和所有已知轮廓的匹配结果
		rVec.push_back(r);
	}

	vector<int> bestVec;	// 最优的匹配标签
	bestVec.clear();
	bool isPass = false;
	int times = 0;
	// 选出K个最优的匹配标签
	for (int i = 0; i < k; i++){

		double rMin = rVec[0];
		int index = 0;
		for (int j = 1; j < rVec.size(); j++){

			for (int kk = 0; kk < bestVec.size(); kk++){

				if (bestVec[kk] == j){

					isPass = true;
					break;
				}
			}
			if (isPass == true){

				isPass = false;
				continue;
			}
			if (rMin > rVec[j]){

				rMin = rVec[j];
				index = j;
			}	
		}
		
		bestVec.push_back(index);
		vote[label[index]] += (1 - times / (2*k));// 权重
		times++;
	}

	// 从最优的集合中选出最最优的标签就是预测结果
	double maxVote = vote[0];
	int result = 0;
	for (int i = 1; i < 10; i++){

		if (maxVote < vote[i]){

			maxVote = vote[i];
			result = i;
		}
	}
	return result;
}

实验结果

    优化后的识别率会明显有提高,但是6和9的识别错误的概率非常高。因为轮廓匹配具有旋转不变性,6旋转180°就是9···,所以结果可想而知。

举一反三

    同样的我们可以制作一系列的英文字母进行KNN识别。

附件

    源代码工程戳这里(注:release里面的可执行程序可以直接运行)。