原文發(fā)表在個人博客Technology-手寫漢字識別，轉(zhuǎn)載請注明出處睬关。
本文主要介紹如何通過機器學(xué)習(xí)來實現(xiàn)手寫漢字識別矮燎，核心算法采用C++編寫，不足300行转砖，代碼開源在Github-HandWriteRecognition须鼎。
主要思路：
- 提取每個漢字的筆畫特征，保存成一個字庫;
- 通過手寫板或者觸摸板獲取用戶的手寫軌跡坐標(biāo);
- 坐標(biāo)預(yù)處理;
- 通過 KNN 算法府蔗，與字庫中的每個漢字進(jìn)行比較;
- 根據(jù)比較距離的大小進(jìn)行排序莉兰，輸出結(jié)果。
字庫
這里的字庫礁竞，是基于Tomoe Handwriting Dictionary字庫進(jìn)行特殊處理后糖荒，生成的model文件。
Tomoe字庫收集了漢字的每一筆的起始和轉(zhuǎn)折點模捂，可以認(rèn)為是特征點捶朵。例如
下面是“丁”字的表示蜘矢，分為兩筆，第一筆只有起點和終點综看，第二筆還包含了轉(zhuǎn)擇點：
<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字庫的缺點很明顯品腹，首先，其坐標(biāo)都是基于其本身的畫板大小的(1000*1000)红碑，而我們在進(jìn)行手寫識別時舞吭，無法預(yù)先知道觸摸屏或者手寫板的區(qū)域大小，所以析珊，必須對數(shù)據(jù)歸一到同一大小的面板中羡鸥，其次，其用的是xml格式忠寻，導(dǎo)致冗余字段非常多惧浴，字庫很大(8.8M)，非常占空間奕剃，而且加載時很慢衷旅。
針對，數(shù)據(jù)歸一處理的問題纵朋，后面的算法環(huán)節(jié)會提及處理方法柿顶。字庫文件過大的問題，這里采用自定義的格式操软，以“丁”字為例：
丁:[[(93,198),(913,205)][(495,203)(470,847)(405,784)]]
這樣嘁锯，將原來8.8M的大小壓縮到僅有1.5M，后面根據(jù)算法需要會進(jìn)一步壓縮寺鸥。
特征點
由于用戶手寫的坐標(biāo)，是連續(xù)的品山，而且非常多胆建，我們必須從中提取特征點，用于與詞庫中的特征點做比較肘交。特征點提取笆载，這里，我們用的是點到直線的距離來判斷涯呻，以“丁”字為例凉驻，其第二筆的特征點，首先是起始和結(jié)束點复罐，其次是轉(zhuǎn)擇點涝登，明顯可以看出轉(zhuǎn)折點離起始和結(jié)束點連成的直線，距離最遠(yuǎn)效诅。因此胀滚，只要我們設(shè)置合適的閾值趟济，就可以通過點到直線的距離，來找出轉(zhuǎn)折點咽笼，加上起始和結(jié)束點顷编，作為特征點。
因為剑刑，一筆筆畫可能有多個轉(zhuǎn)折點媳纬，所以，我們通過遞歸來完成：
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的最遠(yuǎn)點，然后計算該點到曲線B的最近距離其监，再反過來計算曲線B到曲線A的最短距離萌腿，取兩個最短距離的最大值，作為兩條曲線的相似度抖苦。
但是毁菱，在實驗中發(fā)現(xiàn)，Frechet Distance有著很大的缺陷锌历，首先贮庞，如果把整個字作為曲線，與另一個字比較究西，顯然是不行的窗慎，因為有些字可能非常復(fù)雜，例如“橢”卤材，曲線存在交叉遮斥，計算出來的距離沒有參考意義；其次扇丛，如果通過單筆畫進(jìn)行比較术吗，由于用戶的手寫區(qū)域與字庫的區(qū)域不一樣是重合的，所以帆精，計算出來的距離也會有問題较屿，例如:
字庫的“一”字坐標(biāo):(0, 50)->(20, 50)
手寫的“一”字坐標(biāo):(0, 80)->(20, 80)，距離：30
手寫的"|"字坐標(biāo):(10, 40)->(10, 60)卓练，距離：14
所以隘蝎，在實驗后，決定放棄使用Frechet Distance來判斷字的相似度襟企，而通過特征點構(gòu)成的直線的角度來比較嘱么，使用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;
}
特征點的數(shù)量可能不對應(yīng)，可以采用兩種方式來處理拴测，一種是插值乓旗，一種是采樣，這里是采樣的方式集索，另外屿愚，對于每一筆，還需要加上其起始點與上一筆的終點構(gòu)成直線的角度务荆，避免“丁”字識別成“十”字的情況妆距，計算方式如下：
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);
}
// 當(dāng)前筆與上一筆的位置差異
dist += fabs(largeStroke.points[0].diretion - smallStroke.points[0].diretion);
strokeDist = dist / minLength;
return strokeDist;
}
到此，我們可以獲取到用戶手寫字與字庫里面字函匕，單筆畫的相似程度娱据，通過加法，就可以得到整個字的相似程度盅惜，但是由于存在連筆的情況中剩，例如，一筆寫成兩筆抒寂，所以结啼，我們允許筆畫數(shù)的誤差在2以內(nèi)，但是在排序時屈芜，筆畫數(shù)越接近的郊愧，優(yōu)先級越高，計算方法如下：
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;
}
}
// 筆畫更接近的優(yōu)先級更高
return allStrokeDist / character1.strokeCount + character2.strokeCount - character1.strokeCount;
}
return dist;
}
注意井佑，到這里属铁，我們用到的只是兩點直線的角度，與坐標(biāo)的實際大小已經(jīng)沒有聯(lián)系躬翁，所以焦蘑，可以將字庫進(jìn)一步精簡為：
丁:[[0, 0.08][31.3, 16.09, 23.71]]
進(jìn)一步精簡詞庫的大小。
效果
通過搭建詞庫姆另，取特征點喇肋，以及匹配算法坟乾，我們可以看到手寫識別的最終效果如下：
只要手寫不是特別潦草迹辐，基本上第一個字就能識別出來。但是依然存在著依賴筆畫順序的問題甚侣，后面有空再優(yōu)化明吩。
看了又看：
