四步写出一个简单的手游手写识别算法

wuye

井号键编译

　　如何写一个简单的手写识别算法，可以精准快速的识别出自定义的简单图形：

　　把所有的笔画定义了个8个方向，然后将B的笔画可以分解成一个字符串。然后当人在触摸屏上画出一个符号时，也将它分解成8个方向的字符串，最后比较两个字符串的距离就能判断出和不同符号的近似度。

　　实现起来也很简单，第一步去噪，因为不同触摸屏的采样频率不同。

　　实现代码：

1. void GestureAlgorithm::addPoint(int x, int y){int d_x, d_y;
   
2. d_x = x-positions.back().x;d_y = y-positions.back().y;
   
3. if( d_x*d_x + d_y*d_y >= MIN_MOVEMENT){updateStatistic(x, y);recognizeGesture();}}
   
4. void GestureAlgorithm::updateStatistic(int x, int y){positions.push_back(Point(x, y));point_num = positions.size();if(point_num >1){// For Point Recognizationdist_sum += positions.begin()->dist(x,y);dist_average =dist_sum/(point_num - 1);
   
5. // For Line Recognization// Need a patch for the V0 calculation.Point v0 = Point(positions[1].x - positions[0].x, positions[0].y );Point v1 = Point(x - positions[0].x, y -positions[0].y);if(normalize(v0) && normalize( v1)){float theta = acos(dot(v0, v1));theta_sum += theta;theta_sqsum += sq(theta);theta_average = theta_sum / (float)(point_num - 1);theta_factor = sqrt((float)(point_num - 1)*theta_sqsum - sq(theta_sum))/(point_num-1);}}mainDirections = detectDirection(positions);
   
6. //Statistic Updatepos_x_sum += x;pos_y_sum += y;pos_xx_sum += sq(x);pos_xy_sum += x * y;
   
7. midPoint = Point(pos_x_sum/point_num, pos_y_sum/point_num);curGestureRender->render_bbox->addPoint(x, y);}

复制代码

　　第二步把去噪后的数据转换成方向序列，把之前得到的点换成方向序列，并把方向序列归纳到之前定义的8个方向中去。

　　实现代码：

1. PosList GestureAlgorithm::limitDirections(const PosList &positions)
   
2. {
   
3. PosList res;
   
4. int lastx, lasty;
   
5. bool firstTime = true;
   
6. 
   
7. for( PosList::const_iterator ii = positions.begin(); ii != positions.end(); ++ii )
   
8. {
   
9. if( firstTime )
   
10. {
    
11. lastx = ii->x;
    
12. lasty = ii->y;
    
13. 
    
14. firstTime = false;
    
15. }
    
16. else
    
17. {
    
18. int dx, dy;
    
19. 
    
20. dx = ii->x – lastx;
    
21. dy = ii->y – lasty;
    
22. 
    
23. if( dy > 0 )
    
24. {
    
25. if( dx > dy || -dx > dy )
    
26. dy = 0;
    
27. else
    
28. dx = 0;
    
29. }
    
30. else
    
31. {
    
32. if( dx > -dy || -dx > -dy )
    
33. dy = 0;
    
34. else
    
35. dx = 0;
    
36. }
    
37. res.push_back( Point( dx, dy ) );
    
38. lastx = ii->x;
    
39. lasty = ii->y;
    
40. }
    
41. }
    
42. 
    
43. return res;
    
44. }
    
45.                

复制代码

　　第三步把连续一致的方向合并。

　　实现代码：

1. Position Num:  141
   
2.         X=  113 Y= 0
   
3.         X= 0 Y= -15
   
4.         X=  0 Y= 179
   
5.         X= 13 Y= 0
   
6.         X=  -110 Y= 0
   
7.         X= 0 Y= 6
   
8.         X=  0 Y= -101
   
9.         X= 3 Y= 0
   
10.         Directions Number: 8
    
11.         Directions Length:540
    
12.         UP Number: 3 Down Number: 2 Left: 1 right 2
    
13.         Position Num:  142

复制代码

1. PosList GestureAlgorithm::simplify(const PosList &positions)
   
2. {
   
3. PosList res;
   
4. int lastdx = 0, lastdy = 0;
   
5. bool firstTime = true;
   
6. int index=0;
   
7. for( PosList::const_iterator ii = positions.begin(); ii != positions.end(); ++ii )
   
8. {
   
9. if( firstTime )
   
10. {
    
11. lastdx = ii->x;
    
12. lastdy = ii->y;
    
13. firstTime = false;
    
14. }
    
15. else
    
16. {
    
17. bool joined = false;
    
18. if( (lastdx > 0 && ii->x > 0) || (lastdx < 0 && ii->x < 0) )
    
19. {
    
20. lastdx += ii->x;
    
21. joined = true;
    
22. }
    
23. if( (lastdy > 0 && ii->y > 0) || (lastdy < 0 && ii->y < 0) )
    
24. {
    
25. lastdy += ii->y;
    
26. joined = true;
    
27. }
    
28. if( !joined )
    
29. {
    
30. res.push_back( Point( lastdx, lastdy ) );
    
31. lastdx = ii->x;
    
32. lastdy = ii->y;
    
33. }
    
34. }
    
35. }
    
36. if( lastdx != 0 || lastdy != 0 )
    
37. {
    
38. res.push_back( Point( lastdx, lastdy ) );
    
39. }
    
40. return res;
    
41. }

复制代码

　　第四步把小片段的移动略去，最后就能得出其实是画了一个凹的形状。

　　实现代码：

1. PosList GestureAlgorithm::removeShortestNoise(const PosList &positions)
   
2. {
   
3.     PosList res;
   
4.     int shortestSoFar;
   
5.     PosList::const_iterator shortest;
   
6.     bool firstTime = true;
   
7. 
   
8.     for( PosList::const_iterator ii = positions.begin(); ii != positions.end(); ++ii )
   
9.     {
   
10.         if( firstTime )
    
11.         {
    
12.             shortestSoFar = ii->x*ii->x + ii->y*ii->y;
    
13.             shortest = ii;
    
14. 
    
15.             firstTime = false;
    
16.         }
    
17.         else
    
18.         {
    
19.             if( (ii->x*ii->x + ii->y*ii->y) < shortestSoFar )             {                 shortestSoFar = ii->x*ii->x + ii->y*ii->y;
    
20.                 shortest = ii;
    
21.             }
    
22.         }
    
23.     }
    
24. 
    
25.     for( PosList::const_iterator ii = positions.begin(); ii != positions.end(); ++ii )
    
26.     {
    
27.         if( ii != shortest)
    
28.             res.push_back( *ii );
    
29.     }
    
30. 
    
31.     return res;
    
32. }
    
33. 
    
34. PosList GestureAlgorithm::detectDirection(const PosList &positions)
    
35. {
    
36.     PosList directions = simplify(limitDirections(positions));
    
37.     double minLength = calcLength(directions) *minMatch;
    
38. 
    
39.     while(directions.size() > 0 && calcLength(removeShortestNoise(directions)) > minLength)
    
40.     {
    
41.         directions = simplify(removeShortestNoise(directions));
    
42.     }
    
43. 
    
44.     upNum = 0; downNum = 0; leftNum = 0; rightNum =0;
    
45.     for(int i = 0; i< directions.size(); i++)     {         if(directions[i].y >= 0 && directions[i].x ==0)
    
46.             upNum++;
    
47.         else if(directions[i].y < 0 && directions[i].x ==0)             downNum++;         else if(directions[i].x >= 0 && directions[i].y ==0 )
    
48.             leftNum++;
    
49.         else if(directions[i].x < 0 && directions[i].y ==0 )
    
50.             rightNum++;
    
51.     }
    
52.     return directions;
    
53. }

复制代码

　　这个算法的厉害之处是可以实时识别，画到一半也能判断出来。

jiangcaiyang

如果代码排版一下，将是好文章。

babyandkitty

mark一下

yonny321

表示完全看不懂，不懂代码