KNN实现手写数字识别
KNN简介
物以类聚,人以群分就是KNN的算法的宗旨,要辨识一个人大概是社么样的人,可以从他的朋友圈入手,看他的盆友圈属于哪种类型(和哪种类型的盆友圈最接近,比如经常去夜店的二代、老实的码农、像我这样帅的人)就可以大致判断他也属于该类型的人。KNN就是将未知样本和已知样本集合进行比较,比较未知样本和所有已知样本的接近程度进行排序,最后提取前K个最接近的样本,看在这K个样本中哪种几何所占的比例最高,就将该未知样本归纳到该集合中。这里的K就是KNN的K的意思,NN不是指神经网络,而是最近邻(k-NearestNeighbor)。
手写数字识别
功能就不BB了,直接看效果图,就知道实现的是啥功能了,如下图:
开发环境
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实现比较简单,而且不需要训练,特定场合下精度也过得去。但是其计算量特别大,每次识别都要和所有的样本进行对比,如果样本量很多的化,其计算量就不忍直视了,而且比如本功能就需要未知样本的图像和已知样本的图像一样大小(只能识别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里面的可执行程序可以直接运行)。
上一篇: 摄像头识别手写数字
下一篇: Java 集合中的类关于线程安全