神刀安全网

300行代码实现手写汉字识别

原文发表在个人博客Technology-手写汉字识别,转载请注明出处。

本文主要介绍如何通过机器学习来实现手写汉字识别,核心算法采用C++编写,不足300行,代码开源在Github-HandWriteRecognition

主要思路:

  • 提取每个汉字的笔画特征,保存成一个字库;
  • 通过手写板或者触摸板获取用户的手写轨迹坐标;
  • 坐标预处理;
  • 通过 KNN 算法,与字库中的每个汉字进行比较;
  • 根据比较距离的大小进行排序,输出结果。

字库

这里的字库,是基于Tomoe Handwriting Dictionary字库进行特殊处理后,生成的model文件。

Tomoe字库收集了汉字的每一笔的起始和转折点,可以认为是特征点。例如
下面是“丁”字的表示,分为两笔,第一笔只有起点和终点,第二笔还包含了转择点:

<character>     <utf8>丁</utf8>     <strokes>       <stroke>         <point x="93" y="198"/>         <point x="913" y="205"/>       </stroke>       <stroke>         <point x="495" y="203"/>         <point x="470" y="847"/>         <point x="405" y="784"/>       </stroke>     </strokes>   </character>

但是Tomoe字库的缺点很明显,首先,其坐标都是基于其本身的画板大小的(1000*1000),而我们在进行手写识别时,无法预先知道触摸屏或者手写板的区域大小,所以,必须对数据归一到同一大小的面板中,其次,其用的是xml格式,导致冗余字段非常多,字库很大(8.8M),非常占空间,而且加载时很慢。

针对,数据归一处理的问题,后面的算法环节会提及处理方法。字库文件过大的问题,这里采用自定义的格式,以“丁”字为例:

丁:[[(93,198),(913,205)][(495,203)(470,847)(405,784)]]

这样,将原来8.8M的大小压缩到仅有1.5M,后面根据算法需要会进一步压缩。

特征点

由于用户手写的坐标,是连续的,而且非常多,我们必须从中提取特征点,用于与词库中的特征点做比较。特征点提取,这里,我们用的是点到直线的距离来判断,以“丁”字为例,其第二笔的特征点,首先是起始和结束点,其次是转择点,明显可以看出转折点离起始和结束点连成的直线,距离最远。因此,只要我们设置合适的阈值,就可以通过点到直线的距离,来找出转折点,加上起始和结束点,作为特征点。

因为,一笔笔画可能有多个转折点,所以,我们通过递归来完成:

void turnPoints(Stroke *stroke, std::vector<Point> *points, int pointIndex1, int pointIndex2){     if(pointIndex1 < 0 || pointIndex2 <= 0 || pointIndex1 >= pointIndex2 - 1)         return;     const float a = stroke->points[pointIndex2].x - stroke->points[pointIndex1].x;     const float b = stroke->points[pointIndex2].y - stroke->points[pointIndex1].y;     const float c = stroke->points[pointIndex1].x * stroke->points[pointIndex2].y - stroke->points[pointIndex2].x * stroke->points[pointIndex1].y;     float max = 3000;     int maxDistPointIndex = -1;     for(int i = pointIndex1 + 1; i < pointIndex2; ++i){         Point point = stroke->points[i];         const float dist = fabs((a * point.y) -(b * point.x) + c);         std::cout << dist << std::endl;         if (dist > max) {             max = dist;             maxDistPointIndex = i;         }     }     if(maxDistPointIndex != -1){         turnPoints(stroke, points, pointIndex1, maxDistPointIndex);         points->push_back(stroke->points[maxDistPointIndex]);         turnPoints(stroke, points, maxDistPointIndex, pointIndex2);     } }

算法

Frechet

这里用到的算法,一开始是采用Frechet Distance来判断的。

Frechet Distance:首先找出曲线A到曲线B的最远点,然后计算该点到曲线B的最近距离,再反过来计算曲线B到曲线A的最短距离,取两个最短距离的最大值,作为两条曲线的相似度。

但是,在实验中发现,Frechet Distance有着很大的缺陷,首先,如果把整个字作为曲线,与另一个字比较,显然是不行的,因为有些字可能非常复杂,例如“椭”,曲线存在交叉,计算出来的距离没有参考意义;其次,如果通过单笔画进行比较,由于用户的手写区域与字库的区域不一样是重合的,所以,计算出来的距离也会有问题,例如:

字库的“一”字坐标:(0, 50)->(20, 50) 手写的“一”字坐标:(0, 80)->(20, 80),距离:30 手写的"|"字坐标:(10, 40)->(10, 60),距离:14

所以,在实验后,决定放弃使用Frechet Distance来判断字的相似度,而通过特征点构成的直线的角度来比较,使用KNN算法。

KNN

首先,计算单笔画的相似度,单笔画的特征点与前一点的直线的角度,计算方式:

double diretion(const Point &lastPoint, const Point &startPoint){     double result = -1;     result = atan2(startPoint.y - lastPoint.y,  startPoint.x - lastPoint.x) * 10;     return result; }

特征点的数量可能不对应,可以采用两种方式来处理,一种是插值,一种是采样,这里是采样的方式,另外,对于每一笔,还需要加上其起始点与上一笔的终点构成直线的角度,避免“丁”字识别成“十”字的情况,计算方式如下:

double distBetweenStrokes(const Stroke &stroke1, const Stroke &stroke2){     double strokeDist = MAXFLOAT;     double dist = 0.0f;     int minLength = fmin(stroke1.points.size(), stroke2.points.size());     Stroke largeStroke = stroke1.points.size() > minLength ? stroke1 : stroke2;     Stroke smallStroke = stroke1.points.size() > minLength ? stroke2 : stroke1;     for(int j = 1; j < minLength; ++j){         double diretion1 = largeStroke.points[j].diretion;         double diretion2 = smallStroke.points[j].diretion;         dist += fabs(diretion1 - diretion2);     }     // 当前笔与上一笔的位置差异     dist += fabs(largeStroke.points[0].diretion - smallStroke.points[0].diretion);     strokeDist = dist / minLength;     return strokeDist; }

到此,我们可以获取到用户手写字与字库里面字,单笔画的相似程度,通过加法,就可以得到整个字的相似程度,但是由于存在连笔的情况,例如,一笔写成两笔,所以,我们允许笔画数的误差在2以内,但是在排序时,笔画数越接近的,优先级越高,计算方法如下:

double dist(const Character &character1, const Character &character2){     double dist = MAXFLOAT;     if(character2.strokeCount >= character1.strokeCount && character2.strokeCount <= character1.strokeCount + 2){         double allStrokeDist = 0.0f;         for(int i = 0; i < character1.strokeCount; ++i){             Stroke stroke1 = character1.strokes[i];             Stroke stroke2 = character2.strokes[i];             double strokeDist = distBetweenStrokes(stroke1, stroke2);             allStrokeDist += strokeDist;             if(strokeDist > MAX_DIFF_PER_STROKE){                 allStrokeDist = MAXFLOAT;                 return allStrokeDist;             }         }         // 笔画更接近的优先级更高         return allStrokeDist / character1.strokeCount + character2.strokeCount - character1.strokeCount;     }     return dist; }

注意,到这里,我们用到的只是两点直线的角度,与坐标的实际大小已经没有联系,所以,可以将字库进一步精简为:

丁:[[0, 0.08][31.3, 16.09, 23.71]]

进一步精简词库的大小。

效果

通过搭建词库,取特征点,以及匹配算法,我们可以看到手写识别的最终效果如下:

300行代码实现手写汉字识别

300行代码实现手写汉字识别

300行代码实现手写汉字识别

300行代码实现手写汉字识别

只要手写不是特别潦草,基本上第一个字就能识别出来。但是依然存在着依赖笔画顺序的问题,后面有空再优化。

看了又看:

如何在一周内做一款拼音输入法
iOS-线程同步详解

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 300行代码实现手写汉字识别

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址