Pattern matching/recognition library for vectors (like OpenCV for image input)

Question

Does anyone know a good pattern matching/recognition library in C++ (oss preferred) that is able to detect whether a list of vectors is an arrow or some other class?

I already know OpenCV but this is meant to be used for raster graphics (or did I missed something?)... but I already have a vector geometry and it sounds strange to convert them back into a raster graphic where you have to detect the edges again.

So what I need is a library that uses a list of vectors as input instead of a raster graphic and can recognize if the vectors are an arrow (independent from the direction) and extract the parts of the arrow (head/tip/tail etc.).

Anyone who knows such a lib or has a hint where to look for this kind of problem (algorithms etc.)?

I try to change the way a UI is used. I already tried protractor algorithm and divided the recognition step into different parts, e.g. for arrow example:

1. draw, stop drawing and take result
2. treat first line as body (route line, arrow shaft)
3. wait for accept (=> result is recognised as simple line replace hand drawn graphic with route graphic) or next draw process
4. draw arrow head and take result coordinates
5. wait for accept/finish button (=> result is recognised as arrow and is no simple route)
6. a) replace hand drawn vectors by correct arrow graphic
7. b) or go on with any fletchings? bla, bla, bla

But I want to do this in a single step for all vector lines (regardless of the order and direction). Are there any recommendations?

And what if the first is a a polyline with an angle and there is also a recognition of a caret but the follow up symbology needs to decide between them?

I want to draw commands instead of searching it them in a burdened menu. But it is important to detect also the parts of a graphic (e.g. center line, left line, ...) and keep aspect ratio (dimension) as far as it is possible, which means that key coordinates should be kept, too (e.g. arrow tip). This is important for replacing the hand-drawn vectors with the corrected standard graphic.

Is this possible with a lib as a single task or should I stay at the current concept of recognising each polyline separately and look at the input order (e.g. first line must be the direction)?

You can look here to get an idea: http://depts.washington.edu/aimgroup/proj/dollar/ There is the $1 Recognizer algorithm and some derived ones and you can try them online.

The problem is, that my "commands" consists of multiple lines and every line might have a different special meaning in the context to get the complete graphic. The algorithms and libraries I already know (like the $1 Recognizer above) are more related to single gestures instead of a complex order of multiple gesture inputs which gets the precise meaning if interpreted as a whole sketch.

I think continuing with the interpretion of each line separately and not puting it into the whole context (recognise the whole sketch) could lead to a dead end. But maybe a mixed approach might get it.

Real life comparism: It is like when somebody draws a horse. You wouldn't say it is a horse if he just started to draw the first line - you'll need some more input, e.g. 4 legs etc.

(Well, I know not everyone is good in drawing and some horses could look like cows... but anyway, this should give you an idea what I mean.)

Any hints?

Update: I've found a video here that is close to the problem. The missing link is how parts of the structure are accessible after the recognition but this can be done in a separate step, too (after knowing what the drawing shows).

Answer 1

In my humble opinion I'don't think that there's a library in the wild that fulfils such specific needs. In the end you'll end up writing custom code.

Either way, the first thing you'll have to do is to extract classification features from every gesture you detect. You'll have then to put your acquired feature vectors in a feature space. Once you do this, there are literally a million things you can do in order to classify the feature vectors to one of the available classes (e.g., arrow, triangle etc.). For example, the guys from the University of Washington in the link you've supplied are doing their feature extraction in steps 1,2 and 3 and they classify the acquired feature vector in step 4.

The idea of breaking the gesture into sub-gestures sounds tempting, though I have a suspicion it will introduce problems in a matter of ways (e.g., how to detect the end of a sub-gesture and the beginning of the next) and it will also introduce a significant overhead since you will end up in additional steps and a short of a decision tree structure.

One other thing that I forgot to mention above is that you will also need to create a training data-set of a reasonable size in order to train your classifiers.

I won't get into the trouble of suggesting libraries, classifiers, linear algebra packages etc. since this is out of the scope in the first place (i.e., kindly I would suggest to search the web for specific components that will help you build your application).