We were discussing this topic on the Magic Growth thread on the Game Design Corner, but I thought it would be more appropriate here. So what are your ideas of a method to recognise symbols drawn by the user with the mouse. I am testing some of my ideas at the minute, so I don''t want to tell you unless it works, but the way I see it, you would simply recognise a symbol by the variation of angles and the lenght of the segments tht form the line being drawn (we work on 1-stroke symbols). Any ideas ?

Hi ahw!

quote:
We were discussing this topic on the Magic Growth thread on the Game Design Corner, but I thought it would be more appropriate here.

Ehh, I think the AI-forum is more appropriate.

Hmm, one-segment symbols seems to be quite easy to recognise. Do you mean just one line with a length and direction?
How easy it is to recognise depends on how many classes you have and what data you have.

Do you have a 2D-array of pixels or do you actually know the positions of the endpoints?

More info please,

/Mankind gave birth to God.

I remember having heard of a method based on Momentums (or whatever they are called in english) in a introduction course in Computer Vision. It goes something like this:

1) You coppy the area of the screen where the symbol is drawn to an offscreen surface.

2) You convert it to a monochroome (or alternatively a greytone) bitmap. All "background" is deleted using some kind of mask or a threshold method. You then have a small bitmap with your symbol appears on an empty background (say background = black = 0, and symbol = white = 1 in a binar representation).

3) You calculate the momentums from the following formula:

m(i,j) = Sum[(x-x_0)^i * (y-y_0)^j]

Where (x_0, y_0) is the centre of the image. i, j is integer variables. You build a matrix of momentums with different values of i and j.

Oh, and then you only sum the pixels in your image belonging to the symbol. So for the example where white = 1 means symbol and black = 0 is background the pseuudo code would look like the following:

Loop x from Bitmap.Left to Bitmap.Right:  Loop y from Bitmap.Top to Bitmap.Bottom:    If Bitmap.GetPixel(x,y) = 1 Then:      m[i,j] = (x -x_0)^i * (y - y_0)^j 

This would get you a matrix representing some "features" of the symbol which do not depend upon the location of the symbol on the screen. By using a formula only a little more complex you can also get features that do not depend upon the size of the figure (just ask and I find the formula for you). You can compare this matrix of features to some stored in a database of valid symbols.

Well, don''t know if I make any sense. But just ask if I should try to explain it better.

Regards

nicba

sweet. Yes indeed it does seem to make sense. That's the approach I am taking, but no bitmap analysis stuff. That's bad bad bad in terms of speed (but I'd be happy to be proven the opposite).Would you mind sending me this code, or post it here ??

DDNewbie : Well, the idea is that the player is drawing some symbol while pressing the key. When the button is released you analyse what has been traced and do whatever you want with the recognised symbol. You have a sort of database of existing symbols to compare the one you have. And that's pretty much it.

I have my idea on how to do it, but I'd like to see other working ideas... that's why I am not clear as to how you get what But as soon as my stuff is working a bit, I'll brag about it loudly

To see what I am trying to achieve, look at a software called Sensiva, very very nice. That's the way I see my game interface (we had a course on interface design this year, that's how I came up with this idea).

I am soooo desperate to see that's it's already being done, ah well. At least it's from Peter Molyneux (see Black & White).

youpla :-P


Edited by - ahw on August 15, 2000 11:18:59 AM

quote: Original post by ahw

sweet. Yes indeed it does seem to make sense. That''s the approach I am taking, but no bitmap analysis stuff. That''s bad bad bad in terms of speed (but I''d be happy to be proven the opposite).Would you mind sending me this code, or post it here ??

Uhh, Im sorry but I do not have any code to show you. All I have is half a page describing the general idea and the mathematical formulas. I can give you the formula for calculating momentum that does not depend upon the size of the symbols buth the rest you must figure out yourself.

And about the bitmap analysis stuff, I don''t really see how you would avoid it. After all the thing you want recognised is a bitmap. And as long as the bitmap is off-screen there shouldn''t be any penalities involved. You "just" have to access the bitmap memory directly.

Regards

nicba

Just an idea: Instead of analyzing bitmap, analyze recorded mouse movement path.

WOW!! This Sensiva application is a creative piece of work... Now I understand what you mean by symbol recognition, and I''m starting to think about algorithms... sure looks nice...

sorry.. that was me..

-------------------------------
That's just my 200 bucks' worth!

..-=gLaDiAtOr=-..

quote: Original post by Meduzza

Just an idea: Instead of analyzing bitmap, analyze recorded mouse movement path.

Interesting idea, but I can see some problems:

1) There may be more than one way to draw a specific symbol. Say if you want to detect a circle you could both draw it clockwise and anti-clockwise and it would result in the same bitmap but different mouse movement. Your database have to be larger to recognise all posibilities. Could be a problem for complicated symbols.

2) You have to "sample" the mouse movement with some frequency. The generad mouse movement data could vary a great deal for the same symbol according to the speed with which the player draws the symbol. If he draws slowly and carefully you get a big set of data of recorded "mouse points". If the players draws swift you don''t get as much data. You must compare the recorded data to the database in a way that do not depend on the quantity of the recordings.

3) The set of recorded mouse movement would vary with the size of the symbol the player draws. Drawing a large box would not generate precisly the same data as drawing a small box. You need to have some filtering to "normalize" the recorded data to a "standard size box" before comparing it to the database.

Im not saying that this method couldn''t work or that it would be any worse than the method I suggested above. Only that I can''t see exactly how it should be done right now. Perhaps Meduzza has some proposals?

Regards

nicba

Hmm, I would do a symbol recognisation Neural Net.
But that might be overkill. It would work though. And it could be quite fast after the learning procedure.

/Mankind gave birth to God.