>>>  創業先鋒 眾人拾柴火焰高  >>>

簡體     傳統

　　如何寫一個簡單的手寫識別算法，可以精準快速的識別出自定義的簡單圖形：

　　把所有的筆畫定義了個8個方向，然后將B的筆畫可以分解成一個字符串。然后當人在觸摸屏上畫出一個符號時，也將它分解成8個方向的字符串，最后比較兩個字符串的距離就能判斷出和不同符號的近似度。

　　實現起來也很簡單，第一步去噪，因為不同觸摸屏的采樣頻率不同。

　　實現代碼：

void GestureAlgorithm::addPoint(int x, int y)
{
int d_x, d_y;

d_x = x-positions.back().x;
d_y = y-positions.back().y;

if( d_x*d_x + d_y*d_y >= MIN_MOVEMENT)
{
updateStatistic(x, y);
recognizeGesture();
}
}

void GestureAlgorithm::updateStatistic(int x, int y)
{
positions.push_back(Point(x, y));
point_num = positions.size();
if(point_num >1)
{
// For Point Recognization
dist_sum += positions.begin()->dist(x,y);
dist_average =dist_sum/(point_num - 1);

// 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);

//Statistic Update
pos_x_sum += x;
pos_y_sum += y;
pos_xx_sum += sq(x);
pos_xy_sum += x * y;

midPoint = Point(pos_x_sum/point_num, pos_y_sum/point_num);
curGestureRender->render_bbox->addPoint(x, y);
}

　　第二步把去噪后的數據轉換成方向序列，把之前得到的點換成方向序列，并把方向序列歸納到之前定義的8個方向中去。

　　實現代碼：

PosList GestureAlgorithm::limitDirections(const PosList &positions)
{
PosList res;
int lastx, lasty;
bool firstTime = true;

for( PosList::const_iterator ii = positions.begin(); ii != positions.end(); ++ii )
{
if( firstTime )
{
lastx = ii->x;
lasty = ii->y;

firstTime = false;
}
else
{
int dx, dy;

dx = ii->x – lastx;
dy = ii->y – lasty;

if( dy > 0 )
{
if( dx > dy || -dx > dy )
dy = 0;
else
dx = 0;
}
else
{
if( dx > -dy || -dx > -dy )
dy = 0;
else
dx = 0;
}
res.push_back( Point( dx, dy ) );
lastx = ii->x;
lasty = ii->y;
}
}

return res;
}

　　第三步把連續一致的方向合并。

　　實現代碼：

	Position Num:  141
	X=  113 Y= 0
	X= 0 Y= -15
	X=  0 Y= 179
	X= 13 Y= 0
	X=  -110 Y= 0
	X= 0 Y= 6
	X=  0 Y= -101
	X= 3 Y= 0
	Directions Number: 8
	Directions Length:540
	UP Number: 3 Down Number: 2 Left: 1 right 2
	Position Num:  142			

PosList GestureAlgorithm::simplify(const PosList &positions)
{
PosList res;
int lastdx = 0, lastdy = 0;
bool firstTime = true;
int index=0;
for( PosList::const_iterator ii = positions.begin(); ii != positions.end(); ++ii )
{
if( firstTime )
{
lastdx = ii->x;
lastdy = ii->y;
firstTime = false;
}
else
{
bool joined = false;
if( (lastdx > 0 && ii->x > 0) || (lastdx < 0 && ii->x < 0) )
{
lastdx += ii->x;
joined = true;
}
if( (lastdy > 0 && ii->y > 0) || (lastdy < 0 && ii->y < 0) )
{
lastdy += ii->y;
joined = true;
}
if( !joined )
{
res.push_back( Point( lastdx, lastdy ) );
lastdx = ii->x;
lastdy = ii->y;
}
}
}
if( lastdx != 0 || lastdy != 0 )
{
res.push_back( Point( lastdx, lastdy ) );
}
return res;
}		

　　第四步把小片段的移動略去，最后就能得出其實是畫了一個凹的形狀。

　　實現代碼：

PosList GestureAlgorithm::removeShortestNoise(const PosList &positions)
{
    PosList res;
    int shortestSoFar;
    PosList::const_iterator shortest;
    bool firstTime = true;

    for( PosList::const_iterator ii = positions.begin(); ii != positions.end(); ++ii )
    {
        if( firstTime )
        {
            shortestSoFar = ii->x*ii->x + ii->y*ii->y;
            shortest = ii;

            firstTime = false;
        }
        else
        {
            if( (ii->x*ii->x + ii->y*ii->y) < shortestSoFar )             {                 shortestSoFar = ii->x*ii->x + ii->y*ii->y;
                shortest = ii;
            }
        }
    }

    for( PosList::const_iterator ii = positions.begin(); ii != positions.end(); ++ii )
    {
        if( ii != shortest)
            res.push_back( *ii );
    }

    return res;
}

PosList GestureAlgorithm::detectDirection(const PosList &positions)
{
    PosList directions = simplify(limitDirections(positions));
    double minLength = calcLength(directions) *minMatch;

    while(directions.size() > 0 && calcLength(removeShortestNoise(directions)) > minLength)
    {
        directions = simplify(removeShortestNoise(directions));
    }

    upNum = 0; downNum = 0; leftNum = 0; rightNum =0;
    for(int i = 0; i< directions.size(); i++)     {         if(directions[i].y >= 0 && directions[i].x ==0)
            upNum++;
        else if(directions[i].y < 0 && directions[i].x ==0)             downNum++;         else if(directions[i].x >= 0 && directions[i].y ==0 )
            leftNum++;
        else if(directions[i].x < 0 && directions[i].y ==0 )
            rightNum++;
    }
    return directions;
}		

　　這個算法的厲害之處是可以實時識別，畫到一半也能判斷出來。

GameRes游資網 2015-08-23 08:48:18