#144223 - adzz182 - Tue Oct 30, 2007 12:25 pm
I am currently working on a simple strategy-RPG style game, but have hit a problem - i have never dealt with analogue input before and dont know a thing about Pattern Recognition. From what Ive researched Ive found that "Elastic Matching" would suit my need best (although any suggestions of a better method are welcome). Does anyone know of any resources which explain pattern recognition?
I am currently looking through the source for a program i found called XMerlin (handwriting recognition). What i need is something that explains the theory behind it so i can alter this method to suit my need.
The system i am creating must:
1. Recognise a pattern from a limited pattern base (probably around 4-6)
2. Compare how similar the 'input pattern' is to the original and score it. (Will solve this problem later).
3. If no pattern is close to the input it should respond accordingly (instead of selecting the closest pattern)
The largest problem is that pattern recognition is usually very demanding and takes a long time to process (i believe). But this system must be able to process the patterns quickly. Is this possible with the DS's resources? or am i being too demanding
Thanks
#144231 - OOPMan - Tue Oct 30, 2007 2:50 pm
What kind of patterns are you looking to use?
Complex patterns, or fairly simple ones?
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI
You can find my NDS homebrew projects here...
#144240 - adzz182 - Tue Oct 30, 2007 5:34 pm
They would be extremely simple patterns. It would be for when the user chooses to use magic - instead of just selecting magic from a menu they could draw a symbol on the bottom screen.
Was also going to then allow the user to choose the area of effect. So, perhaps on a 2D birds-eye view of the map, they could draw a circle around themselves as the area, or a dot to perform a precise attack, or a line to perform a directional attack.
I do have many ideas right now on how i would implement this - but i am having computer problems right now and cannot compile/test anything i make. I was just really looking for some literature on how this is done - maybe an online tutorial or a book which discusses the topic..... i dont really want a bunch of code...
#144242 - NeX - Tue Oct 30, 2007 6:20 pm
As for the circling business, work out the average of all the points touched (therefore the centre) and the average distance between all touched points and that centre.
_________________
Strummer or Drummer?.
Or maybe you would rather play with sand? Sandscape is for you in that case.
#144295 - OOPMan - Wed Oct 31, 2007 8:09 am
You could take a look at my QuikWriting library. It's linked to via my blog.
It uses a 3x3 grid and allows symbol recognition within the confines of that grid based on entry point and exit point from and to the center square.
It's based on the QuikWriting text-input scheme, but could quite easily be adapted for magic symbol drawing.
_________________
"My boot, your face..." - Attributed to OOPMan, Emperor of Eroticon VI
You can find my NDS homebrew projects here...
#144301 - rhaegar - Wed Oct 31, 2007 9:16 am
Hidden Markov Models should be just what you need. It's sequential based, so with a touch screen, it would be far better suited than elastic matching which works on an image. Processing should be very fast and can run while you draw.
#144313 - adzz182 - Wed Oct 31, 2007 1:52 pm
Thanks for the info on Hidden Markov Models! Ive been researching it and have come up with a process which i think may work:
INPUT
DURING INPUT
DATA COLLECTION
----1. Check the screen is still active every X cycles.
----2. Every X2 cycles sample of the position of the stylus.
--------If the sample is surficiantly distant from the previous sample, record the position.
PREPROCESSING
----3. Once you have surficient data check each for duplicates (successives which have [near] identical values)
----4. Remove any duplicates (if there are many duplicates then the sampling is too frequent)
SMOOTHING
----5. Calculate a smooth stylus trajectory (remove any noise from strokes) by comparing samples to those before and after it.
----6. Remove any noise.
POST-INPUT
NORMALISATION
----7. Convert each screen location to a relative location from the start point.
----8. Multiply all values to get a standard size/shape. i.e. If pattern is too small - increase size.
--------(This should only really be a problem for size, as rotation will be standard).
-------- You could then calculate the transition between samples. Which could be stored in an 2 arrays.
PATTERN MODDELING
----1. Have the system record input of a single pattern several times.
----2. Calculate the transition from each point to the next for comparison to the input.
#144332 - bean_xp - Wed Oct 31, 2007 6:09 pm
Just thought you might like to see how the game "ocular ink" handles this type of input in a RPG environment, as I personally think it is effective and simple. I'm sure if you contact them they may give you the run down of how it works.
Link
Hope this serves as an inspiration to others looking for a similar system.
#144382 - rhaegar - Thu Nov 01, 2007 10:07 am
I think your making it more complicated than is needed. Something simple like this would be sufficient.
| Code: |
start on touchscreen down
for every frame
process HMM probilities (viterbi algorithm) on raw touchscreen coordinates in real time
stop on touchscreen up
select model with highest probability
|
There shouldnt be any need for noise removal. Removing duplicates may probably help the result slightly, though the difference wouldnt be worth the effort.
I would personally use the angle, either relative to the start or relative to the previous point (relative to start would probably be better), and ignore distance the distance. The full 360degrees could be quantised down to 16 or even 8 sectors. This way there woudlnt be a problem with size, and you can do the processing as you draw, as there would be no need for postprocessing on the input data. This will end up with using a single element (the angle) in the feature vector, resulting in a very simple implementation and an almost neglegiable processing time.
You could probably add in a second feature, which either says if the point has gotten closer or further away from the starting position relative to the previous point. This should improve the result quite a bit, and shouldnt have much impact on the processing. Though depending on what your symbols look like, probably wont change the final result.
The hard part of this would be training up the models. You'll need to capture some examples of the symbols you want (about 20 for each should be enough, though the more the better) and train up HMM models for use in the decoding. HTK or GHMM (do a google for them) will have source code that you can compile on your computer to do the training.
#144384 - Mighty Max - Thu Nov 01, 2007 10:54 am
If one is going to implement this. Could you do this as a reusable library?
_________________
GBAMP Multiboot
#144386 - adzz182 - Thu Nov 01, 2007 12:27 pm
The reason i was going to do the distance between each point was bacause i came up with a problem. As you are not actually taking the entire input (which would be impossible for a computer) but are taking samples of the input every cycle, by just taking a sample every frame (irrespective of the distance from the previous point) wouldnt the speed of the drawing seriously effect the recognition? Im sorry about all the questions, its just that i cannot do any programming until my new HDD arrives.
And I would not mind sharing the source once i have it working, the only problem may be that i program in Pascal, im sure you would be able to translate it into C though (if you program in C).
#144406 - HyperHacker - Thu Nov 01, 2007 5:53 pm
Would this method be any good for Japanese handwriting recognition? Considering the characters can be as simple as ノ or as complex as, say, 鷹箸*, or even more, it needs to be able to handle all different levels of complexities.
*I just typed random Japanese names until I got a nice complex-looking one. :p
_________________
I'm a PSP hacker now, but I still <3 DS.
#144424 - adzz182 - Thu Nov 01, 2007 9:41 pm
i was also thinking about also using this for japanese character recognition (JCR). I think it would work very well with JCR. As Kanji have specific stroke orders (and kana are simple) it shoudl be easy to create a program to recognise them. You could try to recognise a whole character, but i think it would be better to recognise a series of strokes. This would simplify the recognition process and also greatly decrease the character base (by searching through those which have the same number of strokes). This would probably mean you would have to write the strokes in the correct order
(i dont know whether you see that as a good thing or a bad thing ;p).
I have not yet been able to do anythingfor the DS yet, as my laptop still isnt working, though i have created a little delphi app. on a uni comp to try and test this out, and it seems to be working quite well. No recognition yet, but im getting input and recording where the mouse moves while it is being clicked. Will keep woring on ti though.
#144466 - rhaegar - Fri Nov 02, 2007 5:12 am
I was initially thinking about doing up a handwriting recognition (english) system for the DS, thought it wouldnt be too hard. My general idea would be to detect different strokes, and have another classification layer ontop to determine the most probably sequence of characters to generate the observed strokes. Though the more I thought about it, the more complicated it looked. Dont really have the patience, time or expertise to do something of that scale.
This discussion resparked my interest, though simply doing a simple symbol recognition system would be far more feasable. There seems to be some interest in this, so depending on circumstances, I should have a library, compelte with instructions and a training toolkit done up in time for christmas :)
Here's somehting very simple I hacked together over night as a little demo.
http://www.megaupload.com/?d=UJLJIUE0
#144505 - HyperHacker - Sat Nov 03, 2007 2:42 am
| adzz182 wrote: |
You could try to recognise a whole character, but i think it would be better to recognise a series of strokes. This would simplify the recognition process and also greatly decrease the character base (by searching through those which have the same number of strokes). This would probably mean you would have to write the strokes in the correct order
(i dont know whether you see that as a good thing or a bad thing ;p). |
Well I was hoping to make a program that teaches you how to draw the characters. Recognizing one stroke at a time would be fine, since you'd be drawing one at a time. It'd be nice if it could still recognize the characters when the strokes were drawn in the wrong order, but probably not necessary.
Of course once I had that working, I might try to build an actual Japanese input system for fun, just because I don't think I've ever seen one on the DS. :-p
_________________
I'm a PSP hacker now, but I still <3 DS.
#145487 - bsder - Fri Nov 16, 2007 1:45 pm
| Quote: |
Of course once I had that working, I might try to build an actual Japanese input system for fun, just because I don't think I've ever seen one on the DS. :-p |
You are aware that the only Japanese dictionary I have ever seen which allows you to actually enter Kanji as handwriting is for the DS? Right?
Kanji Sonomama Rakubiki Jiten--*very* handy when learning Japanese
However, it does appear to be a HMM model recognizer. It can't even recognize some of the simplest characters if you get the stroke order wrong.
#145520 - tepples - Sat Nov 17, 2007 4:24 am
| bsder wrote: |
| You are aware that the only Japanese dictionary I have ever seen which allows you to actually enter Kanji as handwriting is for the DS? Right? |
Are you claiming that all these don't? How does Japanese input typically work on a Pocket PC?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.