[완료]마우스 제스쳐 인식과 내적에 대한 질문입니다.

안녕하세요 이글은

블랙 앤 화이트에서 사용했던 마우스를 이용하여 특정한 패턴을 그리면 반응하는

글에 대한 질문입니다. 원문은

http://www.gamedev.net/reference/articles/article2039.asp 에 있습니다.

간단하게 점이 32개가 모여서 선을 만들게 되어있습니다.

이 선이 미리 정의된 다른 선과 비교를 하여 비슷한지 여부를 판단하게 됩니다.

이를 위해 내적을 이용하게 됩니다. 사실 저는 수학적 능력이 부족하여 그냥 각각의

점들의 위치를 비교하면 되지 않을까 했지만 본문에서 이렇게 내적을 사용하여 급호기심에

질문을 하게됩니다.

신기한것은 제가 고등학교때 배웠던 내적의 경우 2차원 벡터였습니다.

aㆍb = x1x2 + y1y2 = |a||b|cosθ

정도의 공식으로 알수 있었습니다. 그런데 이 글에서

The only difference is that our vectors are not 2 or 3 dimensional, but 2*N dimensional, where N is the number of points in the gesture. Otherwise it's the same familiar x1*x2 + y1*y2 +… (Professional statisticians call this formula correlation; now you know that's the good old dot product in disguise)

2, 3차원 벡터가 아니면 N이 점의 갯수인, 2*N차원 벡터로 계산을

x1*x2 + y1*y2 +(32개 점중 첫번째 점)
x1*x2 + y1*y2 +(32개 점중 두번째 점)
.............
x1*x2 + y1*y2 (32개 점중 32번째 점)

하여 전부 더해진 값으로 계산해줍니다.

그리고 나서

cosθ = (uㆍv) / (sqrt(uㆍu) * sqrt(vㆍv))

cosθ를 구해주어 1(두 벡터가 0도 차이가 나면 1이 되며 이게 완전하게 매칭된것입니다.)

두 벡터 사이에서는 알겠습니다만 어떻게 이렇게 연속된 점들간에 내적을 통해서도 cosθ를

이용해 얼마나 유사한지를 판단할수 있는데 내적을 쓸수 있는지 궁금합니다.

이런 심화된 내적들은 수학은 선형대수에 있는 건가요?

막상 쓰려고 하니 어떻게 돌아가는지가 참 궁금하네요. 그럼 좋은 하루 되세요

이 아래 부분이 매칭 부분관련 글 입니다.
-----------------------------------------------------------------------
Shape Up!

How would we like our magic shape matcher to work? I'd be nice if it would compare the gesture, drawn by user to one of the stored gestures, then it'd return a score: say, 1 for a perfect match, a number, slightly less than 1 for a similar shape and a small or even negative number for a very different shape. We can then compare the input to each of the gestures in our database, pick the one with the highest ranking, and if the ranking is high enough, we say "That's what it is!"

OK, it's easy to say, but how do you actually do it? Well, look closer at the requirements for the shape matcher, does it remind you of something? No? How about good old dot product? If you give it two normalized vectors it'll return 1 if the vectors are exactly the same, it will return a value slightly less than 1 for vectors that point in more-or-less same direction and it'll return a low or even negative number for vectors that point in wildly different (or opposite) directions. Amazingly enough, it works just as well for shape matching! The only difference is that our vectors are not 2 or 3 dimensional, but 2*N dimensional, where N is the number of points in the gesture. Otherwise it's the same familiar x1*x2 + y1*y2 +… (Professional statisticians call this formula correlation; now you know that's the good old dot product in disguise)

So how exactly do you use dot-product to compare shapes? You simply unroll each gesture into an array of numbers and manipulate these arrays as if they were familiar geometrical vectors. (What if the arrays turn out to have different dimensions? Well, then you know it is not a good match, for differing dimensions mean different number of points, and a different number of points means different number of strokes in corresponding gestures, which allows us to reject the match right away. This is why we made each stroke precisely 32 points long.)

float GestureDotProduct(const CGesture& gesture1, const CGesture& gesture2)
{
   if ( gesture1.size() != gesture2.size() ) return -1;
 
   CGesture::const_iterator i1;
   CGesture::const_iterator i2;
   float dotProduct = 0.0f;
 
   for ( i1 = gesture1.begin(), i2 = gesture2.begin();
         i1 != gesture1.end() && i2 != gesture2.end();
         ++i1, ++i2 )
   {
      const CStroke& stroke1 = *i1;
      const CStroke& stroke2 = *i2;
      if ( stroke1.size() != stroke2.size() ) return -1;
 
      CStroke::const_iterator j1;
      CStroke::const_iterator j2;
      for ( j1 = stroke1.begin(), j2 = stroke2.begin();
            j1 != stroke1.end() && j2 != stroke2.end();
            ++j1, ++j2 )
      {
         const CPoint2D& pt1 = *j1;
         const CPoint2D& pt2 = *j2;
         dotProduct += pt1.x * pt2.x + pt1.y * pt2.y;
      }
   }
 
   return dotProduct;
}
 
float Match(const CGesture& gesture1, const CGesture& gesture2 )
{
   float score = GestureDotProduct(gesture1,gesture2);
   if ( score <= 0.0f ) return 0.0f; //No match for sure
   //at this point our gesture-vectors are not quite normalized
   yet - their dot product with themselves is not 1.
 
   //we normalize the score itself
 
   //this is basically a version of a famous formula for a cosine of the 
   //angle between 2 vectors:
   //cos a = (u.v) / (sqrt(u.u) * sqrt(v.v)) = (u.v) / sqrt((u.u) * (v.v))
   score /= sqrtf(GestureDotProduct(gesture1, gesture1) *
                  GestureDotProduct(gesture2, gesture2));
   return score;
}