Pattern Recognition

[Chewy509]

Hi Guys,

A quick question for the programmers among us.

Does anyone know of a suitable pattern recognition algorithm that returns a probability of match, when the input patterns are a string a compass bearings that define a shape. (A bearing of direction is sampled every x time).

eg
shape 1: 0 45 45 270 0 - Is a triangle
shape 2: 0 90 180 270 0 - Is a square.
shape 3: 15 60 60 285 15 - is a what?

So function comparing shape 1 and 2 will return 0.2 (or close to), and a function comparing 1 and 3 will return 1.0.

The other key is that the pattern in shape 3, may be a subset of the values in the pattern to be matched.

I've thought of using naive bayes, but would like to know of any others?

PS. The typical number of values within a pattern will be between 1000 and 2000.

 

[Chewy509]

A couple of other things...

Since this is to be used in a robot (so it can recognise paths it has taken), memory space is very limited (I have approximately 8KB spare for code/data for the algorithm), and the environment doesn't allow recursive techniques, nor dynamic memory. (It's coded in a subset of C, but that shouldn't matter in this case, since I'm after a technique/algorithm rather than raw code).

The shapes/paths are trained into the robot, so at the start it doesn't know any shapes/paths, but will learn them. When it encounters the same shape/path twice it's to use the new knowledge to augment the existing known pattern, rather than storing a new pattern. (That's the easy part, it's recognising it has the same pattern twice that I need some advise on). All the shapes to be taught are the same size, so the same shape but at different sizes are considered different. (If size irreverence was an issue, I would simple RLE the pattern, before comparison).

 

[BingBangBop]

I'm not positive, but I think this will work. Given the compass bearings, you need to calculate out the vertices and the center (so you can sequentially rotate it in small increments throughout the entire 360 degree range and recalculate the vertices) Then calculate standard error between each rotation and each known patterns of vertices with the same number of vertices. If the standard error is low enough, you can assume that they are the same or at least a very similar patterns.

 

[Handruin]

I can't say I know enough about pattern recognition to help you with finding a suitable pattern, but after reading a little bit on the subject, I found a list of algorithms here that you probably already found. The Naive Bayes classifier you mentioned seems to be classified under Classification algorithms (supervised algorithms predicting categorical labels). I understand why that fits in your pattern recognition challenge. That seems like the area in which you've described. The robot will be trained of the patterns (supervised) and then needs to predict similar patterns withing a tolerance (walks like a duck and quacks like a duck)?

 

[Chewy509]

Thanks guys.

BBB, I had thought about that, but have to take into account performance consideration of vertex rotation calculations in the robot. (Based on a 36MHz Amtel SAM7L64 (ARM7) CPU).

Speaking with the lecturer about it, basically we came up with the idea of comparing deltas between each reading of the compass, so you would get a sequence like 0, 0, 0, 45, 0, 0, etc, and you could compare the deltas inline (basically return a number matched / samples), and use some form of windowing technique to perform the recognition of the sequences. (Like a diff tool does when looking for similar text), but the window could only slide so far.

So, a square becomes 90, 90, 90, 90, and triangle becomes 90, 135, 0, 135, and so on.

 

[BingBangBop]

I think I can get rid of a lot of the calculations.

Again convert the compass bearings to vertices. transform the points so that one of them is at 0,0. Now compare the vertices to all the know patterns (stored as a set of vertices with one point at 0,0). If all the vertices match (or within a margin of error) then the patterns are the same. If there are no matches then transform the next point to 0,0 and again compare against all known pattern. Continue transforming till all the vertices have been transformed to 0,0 and compared. When comparing, note that there are two adjacent points to 0,0 so you have to compare in both directions in case the path was reversed.

This way instead of having to calculate rotations you'll be doing transformations which are a significantly less intensive calculation and you'll only do as many of these transformations as the number of vertices which is a lot fewer than rotations in small increments over the entire 360 degrees.

While not as accurate as applying standard error to all the verticies, it will use far fewer calculations to simply apply a range to each vertex and if the two points are within a specified range of each other you can claim that they are at the same location.