Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a series of 'images' described by a mixture of connected lines and curves. Users will draw on the screen, free hand, and my goal is to break their drawing down into a series of lines and curves that can be matched with the 'images' in my set.

For the sake of simplicity, let's assume this is occurring on a touch screen. These lines will be connected. Each time the user's finger moves, the dx and dy is recorded. The drawing is considered complete and analyzed when the user's finger leaves the screen.

I'm having trouble figuring out a good way to break the user's drawing down into lines. Is there any well known approach to this problem, a C++ library that solves it, or any good articles/technical papers on how to achieve this?

share|improve this question
    
For an interesting look at this sort of touch screen analysis, here is a speed run of the Brain Age DS game: youtube.com/watch?v=kWmnehkzRCo –  thedaian Sep 27 '11 at 14:39

5 Answers 5

up vote 12 down vote accepted

Recognising arbitrary shape vectors is hard!

A simpler technique is to use a grid and count the edges crossed by the stroke drawn by the user. This list of edges is used as a "signature" which is compared against a dictionary of signatures of pre-defined shapes.

Algorithm

  1. Sub-divide the input area into a grid (eg: 3x3 with infinite edges), and give each edge a unique ID. The exact size and number of divisions depends on your implementation. More grid divisions leads to greater versatility at the cost of robustness. Sub-divided grid area with labelled edges

  2. The user draws a line over the grid to create a stroke. Note that the grid does not actually need to be visible on the screen, but doing so will assist in the usability of the interface. User-drawn line over grid

  3. The path taken by the stroke is analysed for intersections with grid edges. Each edge that the stroke intersects is added to a list of edges. This becomes the signature for the character. In this example, the "S" curve intersects with the edges Y12, Y7, X7, Y8, Y13, X14, Y14, Y9. Grid intersections

  4. The signature is compared against a dictionary of pre-defined signatures and the closest match (or matches) is returned.

Usability considerations

  1. The user input will not be perfect and the search needs to cater for inexact matches caused by extra or missing edges in the input. One way to deal with this problem is to build a directed graph of the input. This will record the relationship of the points to each other. It will tell you that X7 comes before Y8, but after Y12 for example. The search then compares this against the graph of each character in the dictionary. Each node that matches is assigned a percentage based on the exactness of the match. The node (or nodes) with the highest total percentage matches is used as the overall match.

  2. Multiple variations of each character in the dictionary may also be helpful. In the example above, the signature is valid for the character when drawn from the upper-right quadrant, but it may be useful to have a signature for the same character drawn from the lower-left quadrant, which will essentially be the reverse of the example.

  3. Characters may be made of multiple strokes. For example if the user draws and upside-down "U" and then a "-" the algorithm may match this to two separate characters such as "n-", or it could combine the two strokes and recognise an "A". A time based heuristic could be used as the differentiator, so that multiple strokes in quick succession will result in one character, whereas strokes drawn with more time in-between will result in multiple characters.

  4. If the input system is to be used for hand-writing the number of potential characters and input styles can be large. A word dictionary and/or grammatical analysis could be used to find a set of characters which are most likely to occur next. This is intersected with the list of the matching character signatures to produce an likely candidate.

EDIT: Additional considerations

  1. It may not always be desirable to show the grid during input. In this case it may be necessary to scale the stroke before applying it to the grid. Naive scaling would work but the results may be skewed by points which fall far outside the input region. A workaround is to find the centroid (the average x,y coordinate) of the input stroke, then calculate the average distance of each point in the stroke from this centroid. The stroke is then scaled based on this average distance.

  2. I posted another answer with a different approach using vectors. That algorithm also used the Levenshtein distance to match the character signature. The same approach can be applied to this algorithm during the search phase.

share|improve this answer
    
Very nice answer. This deserves more upvotes ;) –  bummzack Sep 30 '11 at 7:42

To rephrase the original question:

You have a series of points which represent samples of a continuous (but not necessarily straight) line, and you want to represent that line using fewer samples.

Basically what you're trying to find is samples which don't contribute much to the overall shape of the line. The fastest way to do this, in my experience, is to, one at a time, calculate how much "error" would be introduced by removing each sample, and then actually remove the one which results in the least total error.

You then repeat this process, for each remaining point. You continue finding "what's the least bad point to remove" and removing it, as long as the total error induced in the line is less than some maximum "error" threshold.

Important that your error calculations need to be compared against the original line shape, NOT the progressively optimised shape, or else you can end up with the optimised line devolving away from the drawn shape.

I have sample code (from years ago) available here: http://www.vectorstorm.org/svn/repos/VectorStorm/trunk/Games/VectorPhysics/VP_Drawable.cpp

Look inside vpDrawable::OptimiseOutOneIndex() for my implementation of this process.

share|improve this answer
    
As I re-read the original question, I'm pretty sure that I misinterpreted what it was asking; it's not asking how to simplify the shape, it's actually attempting OCR, which is a completely different topic. Apologies for the confusion of my answer! –  Trevor Powell Sep 27 '11 at 15:21

I think you can find good resources by searching for articles about OCR. as far as I could understand your question your problem is a one of OCR sub-problems. you can also search for pattern recognition.

after searching a little bit, I've found this article. I just looked at images (didn't read it at all) and it seems like it's providing algorithm to extract both curves and lines. and it's doing a good job!

share|improve this answer
    
I'm checking out the paper, thanks. I've looked into OCR libraries, but I think it might be too much for such simple purposes. –  rawrgoesthelion Sep 26 '11 at 18:21

Here's an implementation of another algorithm: http://www.bytearray.org/?p=91

It works by decomposing the input stroke into a set of vectors which are multiples of 45 degrees. This simplified representation is compared against a database using the Levenshtein distance.

* Note: the Levenshtein distance can also be applied to the other algorithm I posted here.

share|improve this answer

Maybe you can use the Douglas-Peucker algorithm to find corners of the lines and break the lines that form points.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.