[关闭]
@Aurora-xi 2019-06-27T02:12:01.000000Z 字数 11701 阅读 989

利用KNN算法识别并计算手写算式

KNN算法 手写数字 手写运算符

KNN算法简介

KNN算法又称为K近邻分类（k-nearest neighbor classification）算法.
核心思想：给定测试样本，基于某种距离度量找出训练集中与其最靠近的K个训练样本，然后基于这K个相邻点的信息进行预测。
通常，在分类任务中可使用”投票法”，即将这K个样本中出现最多的类别标记作为预测结果；在回归任务中可使用“平均法”，即将这k个样本的实际值输入标记的平均值作为预测结果；还可以基于距离远近进行加权平均或者加权投票，距离越近的样本权重越大。

一个简单的例子：
如下图，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？
KNN例子
如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形类。
如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。

一、要素

对于KNN而言有三个要素

1. K的选择

K值是KNN算法中为数不多的超参数之一，K值的选择也直接影响着模型的性能。
如果我们把k值设置的比较小，那么意味着我们期望个到一个更复杂和更精确的模型，同时更加容易过拟合。
相反，如果K值越大，模型机会越简单，一个很极端的例子就是如果将K值设置的与训练样本数量相等，即K=N，那么无论是什么类别的测试样本最后的测试结果都会是测试样本中数量最多的那个类。

2. 距离的度量

距离的度量描述了测试样本与训练样本的临近程度，这个临近程度就是K个样本选择的依据，在KNN算法中，如果特征是连续的，那么距离函数一般用曼哈顿距离或欧氏距离，如果特征是离散的，一般选用汉明距离。

3. 分类决策规则

通过上面提到的K与距离两个概念，我们就能选择出K个与测试样例最近的训练样本，如何根据这K个样本决定测试样例的类别就是KNN的分类决策规则，在KNN中最常用的就是多数表决规则。但是该规则有个缺点，严重依赖于训练样本的数目。

二、图像分类问题

那么KNN算法如何应用到图像分类问题中，其实问题也就是如何评价一张待分类的图像A与P个训练样本图像中间的距离呢？

其中关键的问题就是图像的特征选择成什么，把问题往更大的方面考虑下，对于图像而言，传统机器学习与深度学习的一个很大区别是后者的自动特征抽取，所以深度学习的问世在一定程度上改变了人们对图像处理问题的侧重点，从特征描述到网络结构。所以在下面我们可以不严格的分为两类考虑，直接使用图像与使用一种图像特征提取方法。

1. 直接分类

所谓的直接分类本质上是将图像的每个像素点的像素值作为特征，那么此时两种图像的距离（假设使用曼哈顿距离）就是每个对应位置的像素点的像素值差值的绝对值的和。
曼哈顿距离
那么两张图的曼哈顿距离为371。

2. 对特征分类

很多时候我们不会直接使用像素值作为图像的特征来使用，因为它并不能从本质上反映人对图像的认知，比如我们将一张图稍稍向一个方向平移一段距离，在人眼看来他们应该是一类，甚至就是同一张，但是如果用像素值计算距离的话，距离确很大.所以在更多的时候，要计算距离的对象是一些描述子生成的特征，而不是图像的像素。

但是，KNN在图像问题中几乎不会使用。主要原因是它的效率很差，“在线”学习的方式决定了样本量越大，分类过程就会越慢。

三、KNN思想总结

对KNN算法的思想简单总结一下，就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的步骤包括：

  1. 计算测试数据与各个训练数据之间的距离；
  2. 按照距离的递增关系进行排序；
  3. 选取距离最小的K个点；
  4. 确定前K个点所在类别的出现频率；
  5. 返回前K个点中出现频率最高的类别作为测试数据的预测分类。

因此，KNN算法有以下特点

  1. KNN的计算量和数据存储量都很大；
  2. KNN的思想简单，在某些方便可以带来很高的准确率，比如在我们将要研究的手写数字的识别问题上，KNN的准确率就非常高；
  3. KNN是一种在线的学习方式，效率低，而且样本量越大效率就越低。

识别手写数字

因为关于手写数字网上的资料比较多，所以我先从手写数字入手，学会别人的代码再自己实现想要的功能。

一、实现思路

其实思路很简单，利用KNN算法，需要训练数据，训练，测试数据三部分，就是怎么实现比较复杂…

训练的数据，一般都会是两个矩阵，一个矩阵存放着数据图像，另一个矩阵存放数据图像对应的数字。

首先对图片进行预处理，包括灰度化，平滑化，去燥二值化，腐蚀膨胀。（因为之前没怎么接触过这些，所以为了理解代码又从头理解了一遍，以下是查到的一些解释。）

具体代码如下

Mat data, labels;
Mat src = imread("train.jpg");
Mat gray_frame, thres_img, blur_img;
cvtColor(src, gray_frame, COLOR_BGR2GRAY);//灰度图
GaussianBlur(gray_frame, blur_img, Size(3, 3), 3, 3);//高斯平滑
adaptiveThreshold(blur_img, thres_img, 255, ADAPTIVE_THRESH_GAUSSIAN_C, THRESH_BINARY_INV, 151, 10);//二值化为黑底白字
Mat morph_img, tmp2, tmp3;
Mat kernerl = getStructuringElement(MORPH_RECT, Size(3, 3), Point(-1, -1));//获得结构元素
morphologyEx(thres_img, morph_img, MORPH_OPEN, kernerl, Point(-1, -1));//腐蚀膨胀
vector<vector<Point> > contours;
vector<Vec4i> hiearachy;
int k = 0;

之后获取结构元素，利用findContours识别出数字的外轮廓，画出矩形标记。

findContours(morph_img, contours, hiearachy, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_SIMPLE);//找轮廓

之后截取ROI区域，腐蚀膨胀，调整大小。（原程序这里是为了加入OpenCV自带的手写数字数据集，但是我因为要加入符号，没有用OpenCV的数据集。）通过putText函数将轮廓编码，然后将数据图像序列化后放入特征矩阵，对应的标注放入另一个矩阵。

for (int i = 0; i < contours.size(); i++)
    {
        Rect minrect = boundingRect(contours[con[i].order]);
        double area = contourArea(contours[con[i].order]);
        double ckbi = minrect.width / minrect.height;
        if( ckbi<4&& area>400 )
        {
            rectangle(src, minrect, Scalar(0, 255, 0), 1, 8);//标记
            Rect ROI = minrect;
            Mat ROI_img = morph_img(ROI);
            resize(ROI_img, ROI_img, Size(20, 20));
            ROI_img.copyTo(tmp2);
            stringstream stream;
            stream << k;
            string str;
            stream >> str;
            putText(src, str, ROI.tl(), FONT_HERSHEY_PLAIN, 1, Scalar(255, 0, 0), 1, 8);
            data.push_back(tmp2.reshape(0, 1));
            labels.push_back(k / 10);
            k++;
        }
    }

训练部分，直接使用KNN算法进行训练，KNN算法的具体实现在OpenCV的库里已经有了，所以直接调用就行。

测试数据图片导入的处理过程和训练数据处理基本相同，不再赘述。每导入一个数字，进行识别，得出结论并写在图片上，最终一起输出。

主函数代码如下

int main()
{
    Mat data, labels;
    Mat src = imread("train.jpg");
    Mat gray_frame, thres_img, blur_img;
    cvtColor(src, gray_frame, COLOR_BGR2GRAY);//灰度图
    GaussianBlur(gray_frame, blur_img, Size(3, 3), 3, 3);//高斯平滑
    adaptiveThreshold(blur_img, thres_img, 255, ADAPTIVE_THRESH_GAUSSIAN_C, THRESH_BINARY_INV, 151, 10);//二值化为黑底白字
    Mat morph_img, tmp2, tmp3;
    Mat kernerl = getStructuringElement(MORPH_RECT, Size(3, 3), Point(-1, -1));//获得结构元素
    morphologyEx(thres_img, morph_img, MORPH_OPEN, kernerl, Point(-1, -1));//腐蚀膨胀
    vector<vector<Point> > contours;
    vector<Vec4i> hiearachy;
    int k = 0;
    findContours(morph_img, contours, hiearachy, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_SIMPLE);//找轮廓
        vector<vector<Point> >::iterator It;
        Rect rect[150];
        int i=0;
        for(It = contours.begin();It < contours.end();It++)
        {
            Point2f vertex[4];
            rect[i] = boundingRect(*It);
            vertex[0] = rect[i].tl();
            vertex[1].x = (float)rect[i].tl().x, vertex[1].y = (float)rect[i].br().y;
            vertex[2] = rect[i].br();
            vertex[3].x = (float)rect[i].br().x, vertex[3].y = (float)rect[i].tl().y;
            con[i].x = (vertex[0].x+vertex[1].x+vertex[2].x+vertex[3].x) / 4.0;
            con[i].y = (vertex[0].y+vertex[1].y+vertex[2].y+vertex[3].y) / 4.0;
            con[i].order = i;
            i++;
        }
        sort(con,con+i,cmp);
    for (int i = 0; i < contours.size(); i++)
    {
        Rect minrect = boundingRect(contours[con[i].order]);
        double area = contourArea(contours[con[i].order]);
        double ckbi = minrect.width / minrect.height;
        if( ckbi<4&& area>400 )
        {
            rectangle(src, minrect, Scalar(0, 255, 0), 1, 8);//标记
            Rect ROI = minrect;
            Mat ROI_img = morph_img(ROI);
            resize(ROI_img, ROI_img, Size(20, 20));
            ROI_img.copyTo(tmp2);
            stringstream stream;
            stream << k;
            string str;
            stream >> str;
            putText(src, str, ROI.tl(), FONT_HERSHEY_PLAIN, 1, Scalar(255, 0, 0), 1, 8);
            data.push_back(tmp2.reshape(0, 1));
            labels.push_back(k / 10);
            k++;
        }
    }
    //imshow("Out", src);
    data.convertTo(data, CV_32F);
    int samplesNum = data.rows;
    int trainNum = 100;
    Mat trainData, trainLabels;
    trainData = data(Range(0, trainNum), Range::all());
    trainLabels = labels(Range(0, trainNum), Range::all());

    int K = 7;
    Ptr<TrainData> tData = TrainData::create(trainData, ROW_SAMPLE, trainLabels);
    Ptr<KNearest> model = KNearest::create();
    model->setDefaultK(K);
    model->setIsClassifier(true);
    model->train(tData);

    Mat src_test = imread("test.jpg");
    //imshow("Input img", src_test);
    Mat gray_test, thres_test, blur_test;
    cvtColor(src_test, gray_test, COLOR_BGR2GRAY);
    GaussianBlur(gray_test, blur_test, Size(3, 3), 3, 3);
    adaptiveThreshold(blur_test, thres_test, 255, ADAPTIVE_THRESH_GAUSSIAN_C, THRESH_BINARY_INV, 151, 10);
    Mat morph_test, predict_mat;
    morphologyEx(thres_test, morph_test, MORPH_OPEN, kernerl, Point(-1, -1));
    //imshow("Bin", morph_test);
    vector<vector<Point> > contours_test;
    vector<Vec4i> hiearachy_test;
    findContours(morph_test, contours_test, hiearachy_test, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_SIMPLE);
    int p=0;
    for (int i = 0; i <contours_test.size();i++)
    {
        Rect minrect_test = boundingRect(contours_test[i]);
        double area_test = contourArea(contours_test[i]);
        double ckbi_test = minrect_test.width / minrect_test.height;
        if (ckbi_test<4 && area_test>100)
        {
            rectangle(src_test, minrect_test, Scalar(0, 255, 0), 1, 8);
            //imshow("1",src_test);
            Rect ROI_test = minrect_test;
            Mat ROI_img_test = morph_test(ROI_test);
            resize(ROI_img_test, ROI_img_test, Size(20, 20));
            ROI_img_test.convertTo(ROI_img_test, CV_32F);
            ROI_img_test.copyTo(tmp3);
            predict_mat.push_back(tmp3.reshape(0, 1));
                Mat predict_simple = predict_mat.row(p);
            p++;
            float r = model->predict(predict_simple);
            stringstream stream;
            stream << r;
            string str;
            stream >> str;
            putText(src_test, str, ROI_test.tl(), FONT_HERSHEY_PLAIN, 1, Scalar(255, 0, 0), 1, 8);
        }
    }
    imshow("img_test", src_test);
    waitKey(0);
    return 0;
}

二、纯数字训练和测试结果

输入的训练数据是一张按顺序排列好的数字矩阵（打着格子写的23333）
10×10

让我们输入纯数字的图片来识别一下试试吧
纯数字测试1
虽然有的地方还有一些问题，比如有的1太小没被识别出来，但整体效果看起来效果还是不错的。

三、从手写数字到手写运算符

为了能完整识别一个算式，我们还需要在训练集中加入运算符。在调整后的程序中，我加入了“+”、“-”、“×”、“÷”、“（”、“）”六个字符。
代码中最重要的调整是下面这段，给新加入的字符编号，从而使他们在矩阵中有自己合适的位置。

stringstream stream;
t = k / 16;
stream << t;
string str;
stream >> str;
switch (t) {        //++++++
case 10: {str = "+"; break; }
case 11: {str = "-"; break; }
case 12: {str = "x"; break; }
case 13: {str = "/"; break; }
case 14: {str = "("; break; }
case 15: {str = ")"; break; }
}
putText(src, str, ROI.tl(), FONT_HERSHEY_PLAIN, 1, Scalar(255, 0, 0), 1, 8);
data.push_back(tmp2.reshape(0, 1)); //序列化后放入特征矩阵
//labels.push_back(k / 10);  //对应的标注        +++         // 符号及其对应 编码 +10  -11  x12 /13 (14  )15 
labels.push_back(k / 16);  //对应的标注
k++;

（代码太长，而且大部分跟上面的代码相似，因此不再放一次完整代码了）

修改后，输入的训练数据类似，只是加了六个字符。

16×16

同样的，我们再输入一张图片来测试一下

数字运算符测试

这个结果也还可以，但是运算符还是有时候会出错，包括上面图片里的“+”识别成“4”，还有“÷”识别成“+”，括号识别成1等等，在测试中都有出现。

这只是一个测试，项目文件夹下生成的分类器（KNNModel.xml）才是我们辛辛苦苦真正想要得到的东西，再次识别数字和运算符就不需要再次用这么长的代码来执行训练等操作了，我们可以直接调用分类器。下面我们就来调用一下练练手。

手写算式识别和计算

最重要的部分终于来啦~通过前面的工作，我们已经可以对图片中的数字和运算符进行单个的识别了。但是我感觉还不够，写在纸上，用手机拍照截取，上传到电脑上再移入文件夹里感觉很麻烦；而且识别准确率受到附近光源影响，时高时低；最重要的是我想要的自动计算结果的效果还没有完成，于是就有了下面的升级版代码。

升级版代码主要完成的功能包括支持手动调节HSV，摄像头读取信息，调用分类器完成识别数字和运算符，组成算式并自动计算出结果等。

一、思路与代码实现

1. 创建窗口等待识别

这里创建了两个窗口。

namedWindow("test");
namedWindow("SRC");

两个窗口中，一个用来显示摄像头的实时信息，一个用来显示处理过后的图像，并且可以手动调节HSV。

imshow("test", dst);
imshow("SRC", src);
char s = waitKey(30);
if (clc == 3000 || s == 's')
    break;
clc++;

待s键按下或时间足够时捕捉摄像头信息进行识别。

2. 创建控制条

控制条的目的是方便手动调节HSV，从而在不同环境下都能达到较好的识别效果。

cvCreateTrackbar("lowH", "test", &lowH, 179);
cvCreateTrackbar("highH", "test", &highH, 179);
cvCreateTrackbar("lowS", "test", &lowS, 255);
cvCreateTrackbar("highS", "test", &highS, 255);
cvCreateTrackbar("lowV", "test", &lowV, 255);
cvCreateTrackbar("highV", "test", &highV, 255);

3. 图片预处理

虽然是摄像头读取信息，但是实际处理的仍然是通过摄像头捕捉的图片。因此依然要像前文所述一样进行图片的预处理，不过有的地方有所不同，比如将RGB转化为HSV，是因为手动调节HSV相对更加方便。

cvtColor(src, img_hsv, COLOR_BGR2HSV); //RGB转换为HSV
vector<Mat> hsvSplite;
split(img_hsv, hsvSplite); //分成单通道
equalizeHist(hsvSplite[2], hsvSplite[2]); //直方图均值化只能是单通道
merge(hsvSplite, img_hsv); //合成
inRange(img_hsv, Scalar(lowH, lowS, lowV), Scalar(highH, highS, highV), dst); //color，在范围内的颜色变白色，其他变黑色
Mat element = getStructuringElement(MORPH_RECT, Size(3, 3));
morphologyEx(dst, dst, MORPH_OPEN, element); //开运算，去除一些噪点
morphologyEx(dst, dst, MORPH_CLOSE, element); //闭运算，连接一些连通域
dilate(dst, dst, element);
threshold(dst, dst, 0, 255, THRESH_BINARY);

对上面用到的处理方式做一下补充和解释

4. 识别并计算

下面就是这份代码中最重要的识别函数。

函数中加载KNN分类器（就是之前训练出来的分类器），像图片一样分别识别，并将信息按顺序保存。

计算时按顺序读出信息，分别对应成不同的数字或运算符，组成算式并计算。（组成算式之后，具体的计算就很容易了）

计算出的结果会立刻显示出来，同时也会打印在项目文件夹的一个txt文件里，里面写着“我算出来了，结果是……”。

void iJudge(Mat &src)
{
    Mat_<float> nums; //需要识别的图像数据
    Ptr<KNearest> knn = StatModel::load<KNearest>("KNNModel.xml"); //加载knn分类器
    vector<Mat> numsImg; //存放分割下来的数字图像
    cutLR(src, numsImg);
    vector<Mat>::iterator it; //用迭代器遍历数组
    char equation[100];
    int i = 0;
    cout << "Numbers: ";
    for (it = numsImg.begin(); it < numsImg.end(); it++)
    {
        nums = (*it).reshape(0, 1);    //将数据转化成一行
        nums.convertTo(nums, CV_32F); //转成32位浮点型数据
        Mat temp;
        float result = knn->findNearest(nums, 3, temp); //进行识别
        equation[i] = float2char(result);
        i++;
        cout << result << " ";
    }
    equation[i] = '\0';
    cout << endl << equation << endl;
    int result = calculate(equation);
    cout << result << endl;
    ofstream outfile("result.txt", ios::out | ios::trunc);
    outfile << "我算出来了，结果是" << result;
}

二、运行结果

为了对比显示出手动调节HSV的作用，我们进行了多次测试。

1.有台灯光照

我正坐在宿舍调试，此时台灯开着，我测试的时候没有对环境做出调整，也没有调整控制条的默认参数。

有台灯

这是我手拿一张写有算式的纸。从test窗口我们可以看到，默认参数的处理效果还是不错的，但是那张纸的右下角被我写了另一个算式，有一半进入了识别范围内，而我当时并没有发现这一点。

所以…由于我的疏忽而不是代码本身的原因，识别出的算式为72+9521+，计算结果为9593。

2.无台灯光照无调节

同样是这个环境，我关了台灯，重新识别了一次。

无台灯无调节

从图片中的摄像头图像可以看出，周围光明显变暗，纸上出现了一片阴影。

我没有调节默认参数，因此图像处理结果受到环境影响，也不是很好。

识别出来的算式只是7+9，结果是16。单纯看计算都没有问题，但是算式中的2和5被吞掉了。

3.无台灯光照有调节

鉴于上一次识别效果不好，我决定再识别一次，这次对HSV的参数进行调节。

无台灯有调节

从SRC窗口可以看出，光线还是和上一次一样的暗。但是这一次我们将lowS一项从默认值31调节到了86，图像处理结果比上一次好了很多。

识别也很顺利，识别出的算式是72+95，结果是167，正好是纸上的算式和我们想要的结果。

同时，计算结果也打印到了项目文件夹下的result.txt。

txt

其他

一、程序运行环境

1.Windows下

VS2017+OpenCV3.2.0

2.Ubuntu下

Ubuntu16.04+OpenCV3.3.1

二、程序运行条件

1.图片

将训练图片命名为“train.jpg”，测试图片命名为“test.jpg”，并放在程序所在文件夹下，也可通过路径搜寻图片。

2.头文件

Windows下相关头文件需要

#include“opencv2/opencv.hpp”

Ubuntu下相关头文件需要

#include "opencv2/objdetect/objdetect.hpp"
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include "opencv2/ml/ml.hpp"

3.运行环境搭建参考链接

VS2017官方下载地址
VS2017安装教程
OpenCV官方下载地址
OpenCV环境搭建教程

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注